Edición de «Práctica 5 (LyC Verano)»
De Cuba-Wiki
Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.
Revisión actual | Tu texto | ||
Línea 1: | Línea 1: | ||
==Ejercicio 01== | |||
==Ejercicio 02== | ==Ejercicio 02== | ||
===a)=== | ===a)=== | ||
*1.SP3: (¬φ → ¬<font color=red>φ</font>) → [ (¬φ → <font color=red>φ</font>) → φ ] | |||
*2.VALE: (¬φ → ¬φ) (ya que p → p es tautologia) | |||
*1. | *3.MP 1 y 2: (¬φ → φ) → φ | ||
→ (¬φ → φ) → φ es tautologia | |||
* | |||
* | |||
===b)=== | ===b)=== | ||
Línea 22: | Línea 15: | ||
*6.AXb: φ→ψ | *6.AXb: φ→ψ | ||
*7.MP 5 y 6: φ→θ | *7.MP 5 y 6: φ→θ | ||
→ {φ→ψ,ψ→θ} | → {φ→ψ,ψ→θ} infiere φ→θ | ||
===c)=== | ===c)=== | ||
(Falta terminar) | |||
*1. | *1.SP2: ( <font color=red>[¬φ → ¬ψ]</font>→(<font color=blue>φ</font>→<font color=red>[ψ → φ]</font>) ) → ( (<font color=red>[¬φ → ¬ψ]</font>→<font color=blue>φ</font>)→(<font color=red>[¬φ → ¬ψ]</font>→<font color=red>[ψ → φ]</font>) ) | ||
*2.SP1: φ→[ψ → φ] | |||
*3.VALE: [¬φ → ¬ψ]→(φ→[ψ → φ]) = [¬φ → ¬ψ]→T = tautologia | |||
*4.MP 1 y 3: ([¬φ → ¬ψ]→φ)→([¬φ → ¬ψ]→[ψ → φ]) | |||
*5.?? | |||
==Ejercicio 03== | ==Ejercicio 03== | ||
==Ejercicio 04== | |||
==Ejercicio | |||
===a)=== | ===a)=== | ||
===b)=== | ===b)=== | ||
===c)=== | ===c)=== | ||
===d)=== | ===d)=== | ||
== | ==Ejercicio 05== | ||
===a)=== | ===a)=== | ||
<pre> | <pre> | ||
Línea 95: | Línea 54: | ||
((p1 → p3) → ((p2 → p3) → ((p1 ٧ p2) → p3))) | ((p1 → p3) → ((p2 → p3) → ((p1 ٧ p2) → p3))) | ||
¬(p1 → p3) (p2 → p3) → ((p1 ٧ p2) → p3)) | ¬(p1 → p3) (p2 → p3) → ((p1 ٧ p2) → p3)) | ||
p1 ¬(p2 → p3) | p1 ¬(p2 → p3) ¬((p1 ٧ p2) → p3) | ||
¬p3 p2 | ¬p3 p2 (p1 ٧ p2) | ||
¬p3 ¬p3 | |||
</pre> | </pre> | ||
¬P = (p1 ٨ ¬p3) ٧ (p2 ٨ ¬p3 | ¬P = (p1 ٨ ¬p3) ٧ (p2 ٨ ¬p3) ٧ ¬p3 = (p1 ٧ p2 ٧ T) ٨ ¬p3 = ¬p3. Es una contingencia | ||
===c)=== | ===c)=== | ||
Línea 114: | Línea 70: | ||
¬p1 ¬p2 | ¬p1 ¬p2 | ||
</pre> | </pre> | ||
¬P = ((¬p1 ٧ ¬p2) ٧ p3 | ¬P = ((¬p1 ٧ ¬p2) ٨ ¬p4) ٧ p3. Como cada variable aparece 1 vez, ¬P es contingencia | ||
== | ==Ejercicio 06== | ||
===a)=== | ===a)=== | ||
<pre> | <pre> | ||
(((p0 ٨ ¬p0) ٨ p1) ٨ ¬(p1 ٨ (p1 → p0))) | (((p0 ٨ ¬p0) ٨ p1) ٨ ¬(p1 ٨ (p1 → p0))) | ||
((p0 ٨ ¬p0) ٨ p1) | |||
¬(p1 ٨ (p1 → p0)) | |||
(p0 ٨ ¬p0) | |||
p1 | |||
¬p1 | |||
¬p0 | p0 ¬(p1 → p0) | ||
¬p0 p0 | |||
x ¬p0 | |||
p1 | |||
¬p0 | |||
x | |||
</pre> | </pre> | ||
===b)=== | ===b)=== | ||
<pre> | <pre> | ||
Línea 165: | Línea 119: | ||
</pre> | </pre> | ||
==Ejercicio == | ==Ejercicio 07== | ||
===a)=== | ===a)=== | ||
===b)=== | ===b)=== | ||
== | ==Ejercicio 08== | ||
<br>a) F El unico arbol de la formula p1 es ella misma, que es un arbol abierto. Sin embargo, la formula no es una tautologia. | <br>a) F El unico arbol de la formula p1 es ella misma, que es un arbol abierto. Sin embargo, la formula no es una tautologia. | ||
<br>b) F El arbol (p1 ٨ ¬p1) para esa misma formula no es cerrado, pero la formula es una contradiccion. El asunto es que el arbol no esta completo. | <br>b) F El arbol (p1 ٨ ¬p1) para esa misma formula no es cerrado, pero la formula es una contradiccion. El asunto es que el arbol no esta completo. | ||
<br>c) V (Esta demostrada en algun lado, pero no me acuerdo donde) | <br>c) V (Esta demostrada en algun lado, pero no me acuerdo donde) | ||
==Ejercicio | ==Ejercicio 09== | ||
===a)=== | |||
===b)=== | |||
===c)=== | |||
==Ejercicio 10== | |||
Como Γ1∪Γ2 es insatisfacible, por compacidad existe Γ0 <math>\subseteq</math> Γ1∪Γ2 finito e insatisfacible. Este conjunto tiene que tener por lo menos una formula de Γ1 y una de Γ2. Si no, serıa satisfacible. Si llamamos α1,..,αn a las formulas de Γ1 ∩ Γ0 y β1,..,βm a las de Γ1 ∩ Γ0, podemos hacer α = α1 ٨..٨ αn y β = β1 ٨..٨ βm. Es claro que β ε C(Γ1) y que β ε C(Γ2). Ademas, α ٨ β es una contradiccion. Pero α ٨ β ≡ ¬(¬α ٧ ¬β) ≡ ¬(α → ¬β), de lo cual podemos concluir que (α → ¬β) es una tautologia | |||
==Ejercicio | |||
Como | |||
==Ejercicio 11 | ==Ejercicio 11== | ||
<br>Sea Γ' <math>\subseteq</math> Γ finito. Veamos por induccion en su cantidad de elementos que es satisfacible. Si #Γ' = 1, sabemos que es satisfacible pues consta de una sola contingencia. Supongamos que todo Γ' de menos de n elementos es satisfacible. Sea Γ' con n elementos. Entonces, Γ' = {α} U Γ" (con α <math>\notin</math> Γ"). Sea v una valuacion que satisface a Γ" (existe por HI). Sea w una valuacion que satisface a α. Construimos v' como sigue. En las variables de α, da lo mismo que w. En las demas variables, da lo mismo que v. Esta valuacion satisface a Γ'. Entonces, como todo subconjunto finito es satisfacible, Γ es satisfacible (por compacidad). | <br>Sea Γ' <math>\subseteq</math> Γ finito. Veamos por induccion en su cantidad de elementos que es satisfacible. Si #Γ' = 1, sabemos que es satisfacible pues consta de una sola contingencia. Supongamos que todo Γ' de menos de n elementos es satisfacible. Sea Γ' con n elementos. Entonces, Γ' = {α} U Γ" (con α <math>\notin</math> Γ"). Sea v una valuacion que satisface a Γ" (existe por HI). Sea w una valuacion que satisface a α. Construimos v' como sigue. En las variables de α, da lo mismo que w. En las demas variables, da lo mismo que v. Esta valuacion satisface a Γ'. Entonces, como todo subconjunto finito es satisfacible, Γ es satisfacible (por compacidad). | ||
<br>Si no queremos usar compacidad, vemos directamente que Γ es satisfacible. Para cada elemento αi hay una valuacion vi. Construimos la valuacion v que es igual a cada vi en las variables de αi, y 0 en las variables que no aparezcan en Γ. Esta bien definida por las intersecciones vacias. v satisface a Γ. | <br>Si no queremos usar compacidad, vemos directamente que Γ es satisfacible. Para cada elemento αi hay una valuacion vi. Construimos la valuacion v que es igual a cada vi en las variables de αi, y 0 en las variables que no aparezcan en Γ. Esta bien definida por las intersecciones vacias. v satisface a Γ. | ||
==Ejercicio | ==Ejercicio 12== | ||
==Ejercicio 13== | |||
==Ejercicio | |||
Recordemos que {P} |= Q sii (P → Q) es una tautologia. Y esto tambien es equivalente a que [P] <= [Q]. Con esto en mente, supongamos que Γ |= γ. Entonces, por compacidad, existe un subconjunto finito Γ0 = {α1, ... , αn} de Γ tal que {α1, ... , αn} |= γ . Miremos el cociente finito Γ0/ ≡. La hipotesis de que α → β es tautologia o β → α es tautologia se puede traducir en que este cociente se puede ordenar totalmente. Sea [α] su primer elemento. Es claro que todos los elementos de [α] son consecuencia de α. Los elementos de clases mayores tambien, pues se tiene que α → β es tautologia para toda β que este en una clase [P] tal que [α] <= [P]. Entonces, todo Γ0 es consecuencia de α. Luego, {α} |= γ . | Recordemos que {P} |= Q sii (P → Q) es una tautologia. Y esto tambien es equivalente a que [P] <= [Q]. Con esto en mente, supongamos que Γ |= γ. Entonces, por compacidad, existe un subconjunto finito Γ0 = {α1, ... , αn} de Γ tal que {α1, ... , αn} |= γ . Miremos el cociente finito Γ0/ ≡. La hipotesis de que α → β es tautologia o β → α es tautologia se puede traducir en que este cociente se puede ordenar totalmente. Sea [α] su primer elemento. Es claro que todos los elementos de [α] son consecuencia de α. Los elementos de clases mayores tambien, pues se tiene que α → β es tautologia para toda β que este en una clase [P] tal que [α] <= [P]. Entonces, todo Γ0 es consecuencia de α. Luego, {α} |= γ . | ||
[[Category: | [[Category:Lógica y Computabilidad]] |