Diferencia entre revisiones de «Práctica 5 (LyC Verano)»

De Cuba-Wiki
 
(No se muestran 30 ediciones intermedias de 8 usuarios)
Línea 1: Línea 1:
==Ejercicio 01==
{{Back|Lógica y Computabilidad}}
<pre>
SP3 = (¬φ → ¬ψ) → [ (¬φ → ψ) → φ ] = 1 <=>
    (¬φ → ¬ψ) = 0    ٧  [ (¬φ → ψ) → φ ] = 1
    ¬φ = 0  ٧ ¬ψ = 1          (¬φ → ψ) = 0  ٧  φ = 1
    φ = 1  ٧  ψ = 0        ¬φ = 0  ٧  ψ = 1
                              φ = 1  ٧  ψ = 1
</pre>
Con lo cual, SP3 vale si
<br>(φ=1 ٧ ψ=0) ٧ (φ=1 ٧ ψ=1) ٧ (φ=1), que equivale a
<br>(φ=1) ٧ (ψ=0 ٧ ψ=1), que equivale a
<br>(φ=1) ٧ T = tautologia
<br> -> SP3 es tautologia


==Ejercicio 02==
==Ejercicio 02==
===a)===
===a)===
*1.SP3: (¬φ → ¬<font color=red>φ</font>) → [ (¬φ → <font color=red>φ</font>) → φ ]
''consultar por las dudas''
*2.VALE: (¬φ → ¬φ) (ya que p p es tautologia)
 
*3.MP 1 y 2: (¬φ → φ) → φ
*1.SP1: ¬φ → ((¬φ → ¬φ) → ¬φ)
→ (¬φ → φ) → φ es tautologia
*2.SP2: (¬φ → ((¬φ → ¬φ) → ¬φ)) → ((¬φ → (¬φ → ¬φ)) → (¬φ → ¬φ))
*3.MP1y2: (¬φ → (¬φ → ¬φ)) → (¬φ → ¬φ)
*4.SP1: ¬φ → (¬φ → ¬φ)
*5.MP3y4: (¬φ ¬φ)
*6.SP3: (¬φ → ¬φ) → ((¬φ → φ) → φ)
*7.MP5y6: (¬φ φ) →  φ
|- (¬φ → φ) → φ


===b)===
===b)===
Línea 28: Línea 22:
*6.AXb: φ→ψ
*6.AXb: φ→ψ
*7.MP 5 y 6: φ→θ
*7.MP 5 y 6: φ→θ
→ {φ→ψ,ψ→θ} infiere φ→θ
→ {φ→ψ,ψ→θ} |- φ→θ


===c)===
===c)===
Línea 37: Línea 31:
*3.MP 1 y 2: (¬φ → ψ) → φ
*3.MP 1 y 2: (¬φ → ψ) → φ
*4.SP1: ψ → (¬φ → ψ)
*4.SP1: ψ → (¬φ → ψ)
*5.USANDO 3 y 4: {ψ → (¬φ → ψ), (¬φ → ψ) → φ} |- (ψ → φ) (x punto b)
*5.USANDO 3 y 4: {<font color=red>ψ</font> → (¬φ → ψ), (¬φ → ψ) → <font color=red>φ</font>} |- (ψ → φ) (x punto b)
<br>→Vale (ψ → φ)
<br>→Vale (ψ → φ)
<br>→(¬φ → ¬ψ)→(ψ → φ) es teorema
<br>→ |- (¬φ → ¬ψ)→(ψ → φ)


==Ejercicio 03==
==Ejercicio 03==
==Ejercicio 04==
'''(Sientanse libres de cambiar esta respuesta por alguna mas formal)'''<br>
Si Γ+ tiene un axioma que es contradicción luego ya se puede decir que Γ+ es inconsistente ya que es la negacion de una tautología que son los otros axiomas.<br>
Por otro lado si Γ+ tiene un axioma que es una contingencia luego hay para algunas valuaciones en instanciaciones de ese axioma que el resultado es 1 y en otras valuaciones que da 0.<br>
Buscamos que valores de nuestro esquema deberían ser 0 y cuales 1 para que nuestro esquema de 0<br>
Luego en los lugares donde deberiamos instanciar una formula con una valuacion que de 0, ponemos una formula que sea contradiccion, y donde debería ser uno ponemos una formula que sea tautología. Luego nuestro esquema se transformará en una contradicción con lo cual volvemos al ejemplo anterior.<br>
Ejemplo:<br>
Sea nuestro esquema de axioma: φ → ψ <br>
Luego para que esto sea contradiccion φ debería ser 1 y ψ debería ser 0.<br>
Para lograr esto instanciamos φ en una tautologia y ψ en una contradicción. <br>
Luego nuestro axioma será una contradicción.<br>
 
==Ejercicio 05==
===a)===
===a)===
'''Inducción:'''<br>
C.B. : Es facil verlo.<br>
H.I. : Es consistente Γn<br>
q.v.q. : Si cumple Γn entonces cumple Γn+1<br>
<br>
Por la manera en que se construye hay que ver 2 casos:
Γn U φn : Es consistente por definición
Γn U ¬φn: El problema se reduce a mostrar que si Γn U φn es inconsistente, luego y Γn es consistente, luego Γn U ¬φn tambien lo es.
===b)===
===b)===
===c)===
===c)===
Demostrar que Γ+ |- φ => φ <math>\in</math> Γ+ .
Sabemos que Γ+ |- φ entonces queremos ver que φ <math>\in</math> Γ+ .
Hay dos casos:
1) Si φ <math>\in</math> Γ+ es trivialmente verdadero. <br/>
2) Supongo φ <math>\notin</math> Γ+ entonces por 4) b) ¬φ <math>\in</math> Γ+ => Γ+ |- ¬φ pero por hipótesis Γ+ |- φ => Γ+ es inconsistente (ABSURDO!)
El absurdo provino de suponer que φ <math>\notin</math> Γ+, por lo que φ <math>\in</math> Γ+ .
===d)===
===d)===


==Ejercicio 05==
==(Ejercicio que no está en la práctica del 2º cuatrimestre 2009)==
===a)===
===a)===
<pre>
<pre>
Línea 69: Línea 95:
((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)     (p1 ٧ p2) → p3
         ¬p3                    p2               (p1 ٧ p2)  
         ¬p3                    p2       ¬(p1 ٧ p2)     p3
                                  ¬p3                ¬p3
                                ¬p3           ¬p1
                                              ¬p2
</pre>
</pre>


¬P = (p1 ٨ ¬p3) ٧ (p2 ٨ ¬p3) ٧ ¬p3 = (p1 ٧ p2 ٧ T) ٨ ¬p3 = ¬p3. Es una contingencia
¬P = (p1 ٨ ¬p3) ٧ (p2 ٨ ¬p3) ٧ (¬p1 ٨ ¬p2) ٧ ¬p3 = (¬p3 ٨ (p1 ٧ p2)) ٧ (¬p2 ٨ ¬p1) = (¬p3 ٨ ¬a) ٧ a ٧ p3 = 1.


Nota: NO es una contingencia. Este árbol sólo logra probar que la fórmula NO ES TAUTOLOGÍA. Ahora habría que agregar el árbol para la fórmula sin negar y ver si se cierran o no todas sus ramas. Si se cierran todas, es una contradicción (en este caso ocurre eso), si queda alguna abierta, entonces sí, es una contingencia.
¬P = 1, entonces P = 0. P es una contradicción.


===c)===
===c)===
Línea 89: Línea 116:
¬P = ((¬p1 ٧ ¬p2) ٧ p3) ٨ ¬p4. Como cada variable aparece 1 vez, ¬P es contingencia
¬P = ((¬p1 ٧ ¬p2) ٧ p3) ٨ ¬p4. Como cada variable aparece 1 vez, ¬P es contingencia


==Ejercicio 06==
==(Ejercicio que no está en la práctica del 2º cuatrimestre 2009)==
===a)===
===a)===
<pre>
<pre>
Línea 138: Línea 165:
</pre>
</pre>


==Ejercicio 07==
==Ejercicio ==
===a)===
===a)===
{p},{p->q}
(cualquiera que no tenga negaciones seguro que cumple)
===b)===
===b)===


==Ejercicio 08==
==(Ejercicio que no está en la práctica del 2º cuatrimestre 2009)==
<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 09==
==Ejercicio 06==
 
<br>c<=>b) Trivial (uno es el reciproco del otro)
 
<br>a->c) Γ es insatisfacible ->
* Γ|=α -> <math>\exists</math> Γ0 <math>\subseteq</math> Γ tq Γ0|=α
* Γ|=¬α -> <math>\exists</math> Γ1 <math>\subseteq</math> Γ tq Γ1|=¬α
-> Γ0 U Γ1 |= α y Γ0 U Γ1 |= ¬α -> Γ0 U Γ1 es insatisfacible
 
<br>c->a) <math>\exists</math> Γ0 finito insatisfacible tq Γ0 <math>\subseteq</math> ΓU{¬α}. Se tienen estos casos:
* 1. Γ0 <math>\subseteq</math> Γ insatisfacible -> Γ0|=α
* 2. Γ0 = {¬α} insatisfacible -> ¬α es contradiccion -> α es tautologia -> Γ0|=α
* 3. Γ0 <math>\subseteq</math> Γ1U{¬α} insatisfacible -> Γ1|=α


==Ejercicio 10==
==Ejercicio 07==
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
Como Γ1 U Γ2 es insatisfacible, por compacidad existe Γ0 <math>\subseteq</math> Γ1 U Γ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 Γ2 ∩ Γ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 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 12==
==Ejercicio 09==
Supongamos que ninguna formula de la forma α1 ٧...٧ αn sea tautologia. Esto es lo mismo que decir que ninguna formula de la forma ¬α1 ٨ ... ٨ ¬αn no es contradiccion. Pero esto ultimo es lo mismo que decir que todo subconjunto finito de negaciones de formulas de Γ es satisfacible. Entonces ¬Γ = {¬α, α ε Γ} es satisfacible. Entonces, existe v valuacion tal que v(¬α) = 1 para todo α en Γ. Esto contradice la hipotesis de que v satisface al menos una formula de Γ. Entonces, tienen que existir finitas formulas α1, ... , αn tales que su disyuncion es una tautologia.
Supongamos que ninguna formula de la forma α1 ٧...٧ αn sea tautologia. Esto es lo mismo que decir que ninguna formula de la forma ¬α1 ٨ ... ٨ ¬αn no es contradiccion. Pero esto ultimo es lo mismo que decir que todo subconjunto finito de negaciones de formulas de Γ es satisfacible. Entonces ¬Γ = {¬α, α ε Γ} es satisfacible. Entonces, existe v valuacion tal que v(¬α) = 1 para todo α en Γ. Esto contradice la hipotesis de que v satisface al menos una formula de Γ. Entonces, tienen que existir finitas formulas α1, ... , αn tales que su disyuncion es una tautologia.


==Ejercicio 13==
==Ejercicio 10==
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:Lógica y Computabilidad]]
[[Category:Prácticas]]

Revisión actual - 19:51 8 dic 2009

Plantilla:Back

Ejercicio 02

a)

consultar por las dudas

  • 1.SP1: ¬φ → ((¬φ → ¬φ) → ¬φ)
  • 2.SP2: (¬φ → ((¬φ → ¬φ) → ¬φ)) → ((¬φ → (¬φ → ¬φ)) → (¬φ → ¬φ))
  • 3.MP1y2: (¬φ → (¬φ → ¬φ)) → (¬φ → ¬φ)
  • 4.SP1: ¬φ → (¬φ → ¬φ)
  • 5.MP3y4: (¬φ → ¬φ)
  • 6.SP3: (¬φ → ¬φ) → ((¬φ → φ) → φ)
  • 7.MP5y6: (¬φ → φ) → φ

|- (¬φ → φ) → φ

b)

  • 1.SP1: (ψ→θ)→( φ→(ψ→θ) )
  • 2.AXb: ψ→θ
  • 3.MP 1 y 2: φ→(ψ→θ)
  • 4.SP2: ( φ→(ψ→θ) ) → ( (φ→ψ)→(φ→θ) )
  • 5.MP 3 y 4: (φ→ψ)→(φ→θ)
  • 6.AXb: φ→ψ
  • 7.MP 5 y 6: φ→θ

→ {φ→ψ,ψ→θ} |- φ→θ

c)


Si (¬φ → ¬ψ) es F, la formula es tautologia.
Si (¬φ → ¬ψ) es T, entonces hay que probar que vale (ψ→φ). Entonces:

  • 1.SP3: (¬φ → ¬ψ) → [ (¬φ → ψ) → φ ]
  • 2.VALE: (¬φ → ¬ψ) (x HI)
  • 3.MP 1 y 2: (¬φ → ψ) → φ
  • 4.SP1: ψ → (¬φ → ψ)
  • 5.USANDO 3 y 4: {ψ → (¬φ → ψ), (¬φ → ψ) → φ} |- (ψ → φ) (x punto b)


→Vale (ψ → φ)
→ |- (¬φ → ¬ψ)→(ψ → φ)

Ejercicio 03

(Sientanse libres de cambiar esta respuesta por alguna mas formal)
Si Γ+ tiene un axioma que es contradicción luego ya se puede decir que Γ+ es inconsistente ya que es la negacion de una tautología que son los otros axiomas.
Por otro lado si Γ+ tiene un axioma que es una contingencia luego hay para algunas valuaciones en instanciaciones de ese axioma que el resultado es 1 y en otras valuaciones que da 0.
Buscamos que valores de nuestro esquema deberían ser 0 y cuales 1 para que nuestro esquema de 0
Luego en los lugares donde deberiamos instanciar una formula con una valuacion que de 0, ponemos una formula que sea contradiccion, y donde debería ser uno ponemos una formula que sea tautología. Luego nuestro esquema se transformará en una contradicción con lo cual volvemos al ejemplo anterior.
Ejemplo:
Sea nuestro esquema de axioma: φ → ψ
Luego para que esto sea contradiccion φ debería ser 1 y ψ debería ser 0.
Para lograr esto instanciamos φ en una tautologia y ψ en una contradicción.
Luego nuestro axioma será una contradicción.

Ejercicio 05

a)

Inducción:
C.B. : Es facil verlo.
H.I. : Es consistente Γn
q.v.q. : Si cumple Γn entonces cumple Γn+1

Por la manera en que se construye hay que ver 2 casos: Γn U φn : Es consistente por definición Γn U ¬φn: El problema se reduce a mostrar que si Γn U φn es inconsistente, luego y Γn es consistente, luego Γn U ¬φn tambien lo es.

b)

c)

Demostrar que Γ+ |- φ => φ Γ+ .

Sabemos que Γ+ |- φ entonces queremos ver que φ Γ+ .

Hay dos casos:

1) Si φ Γ+ es trivialmente verdadero.
2) Supongo φ Γ+ entonces por 4) b) ¬φ Γ+ => Γ+ |- ¬φ pero por hipótesis Γ+ |- φ => Γ+ es inconsistente (ABSURDO!)

El absurdo provino de suponer que φ Γ+, por lo que φ Γ+ .

d)

(Ejercicio que no está en la práctica del 2º cuatrimestre 2009)

a)

¬(¬(p1 ٧ p2) → ((p3 ٨ p1) ٧ (p2 → p3)))
  	  ¬(p1 ٧ p2)
      ¬((p3 ٨ p1) ٧ (p2 → p3))
	       ¬p1
	       ¬p2
             ¬(p3 ٨ p1)
             ¬(p2 → p3)
              ¬p3   ¬p1
               p2    p2
              ¬p3   ¬p3
               x      x

→ P es tautologia

b)

((p1 → p3) → ((p2 → p3) → ((p1 ٧ p2) → p3)))
      ¬(p1 → p3)     (p2 → p3) → ((p1 ٧ p2) → p3))
           p1                ¬(p2 → p3)      (p1 ٧ p2) → p3
         ¬p3                     p2        ¬(p1 ٧ p2)     p3
                                ¬p3            ¬p1
                                               ¬p2

¬P = (p1 ٨ ¬p3) ٧ (p2 ٨ ¬p3) ٧ (¬p1 ٨ ¬p2) ٧ ¬p3 = (¬p3 ٨ (p1 ٧ p2)) ٧ (¬p2 ٨ ¬p1) = (¬p3 ٨ ¬a) ٧ a ٧ p3 = 1.

¬P = 1, entonces P = 0. P es una contradicción.

c)

¬((¬¬¬(p1 ٨ p2) ٧ p3) → p4)
   (¬¬¬(p1 ٨ p2) ٧ p3)
             ¬p4
¬¬¬(p1 ٨ p2)     p3
¬(p1 ٨ p2)
¬p1     ¬p2

¬P = ((¬p1 ٧ ¬p2) ٧ p3) ٨ ¬p4. Como cada variable aparece 1 vez, ¬P es contingencia

(Ejercicio que no está en la práctica del 2º cuatrimestre 2009)

a)

(((p0 ٨ ¬p0) ٨ p1) ٨ ¬(p1 ٨ (p1 → p0)))
          ((p0 ٨ ¬p0) ٨ p1)
          ¬(p1 ٨ (p1 → p0))
              (p0 ٨ ¬p0)
                 p1
           ¬p1   ¬(p1 → p0)
           ¬p0       p0
           ¬p0      ¬p0
            x        p1
                    ¬p0
                     x

Agrego una cosa. Cabe destacar que si un conjunto de formulas es insatisfacible, entonces, cualquier formula es consecuencia semantica de este. Por lo tanto, pertenece a Con(r).

b)

((p1 ٨ (p1 → ¬p0)) ٨ ¬(p1 → p0))
        (p1 ٨ (p1 → ¬p0))
           ¬(p1 → p0)
                p1
          (p1 → ¬p0)
               p1     
             ¬p0
        ¬p1      ¬p0
         x

c)

(((p1 ٨ (p2 ٧ p0)) ٨ (p1 ٨ p0)) ٨ ¬((p1 ٨ p2) → p0))
         ((p1 ٨ (p2 ٧ p0)) ٨ (p1 ٨ p0))
              ¬((p1 ٨ p2) → p0)
               (p1 ٨ (p2 ٧ p0))
                  (p1 ٨ p0)
                  (p1 ٨ p2)
                     ¬p0
                       p1
                  (p2 ٧ p0)
                       p1
                       p0
                       p1
                       p2
                    p2  p0
                    x    x

Ejercicio

a)

{p},{p->q} (cualquiera que no tenga negaciones seguro que cumple)

b)

(Ejercicio que no está en la práctica del 2º cuatrimestre 2009)


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.
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.
c) V (Esta demostrada en algun lado, pero no me acuerdo donde)

Ejercicio 06


c<=>b) Trivial (uno es el reciproco del otro)


a->c) Γ es insatisfacible ->

  • Γ|=α -> Γ0 Γ tq Γ0|=α
  • Γ|=¬α -> Γ1 Γ tq Γ1|=¬α

-> Γ0 U Γ1 |= α y Γ0 U Γ1 |= ¬α -> Γ0 U Γ1 es insatisfacible


c->a) Γ0 finito insatisfacible tq Γ0 ΓU{¬α}. Se tienen estos casos:

  • 1. Γ0 Γ insatisfacible -> Γ0|=α
  • 2. Γ0 = {¬α} insatisfacible -> ¬α es contradiccion -> α es tautologia -> Γ0|=α
  • 3. Γ0 Γ1U{¬α} insatisfacible -> Γ1|=α

Ejercicio 07

Como Γ1 U Γ2 es insatisfacible, por compacidad existe Γ0 Γ1 U Γ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 Γ2 ∩ Γ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 11 (¿?)


Sea Γ' Γ 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 α Γ"). 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).


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 09

Supongamos que ninguna formula de la forma α1 ٧...٧ αn sea tautologia. Esto es lo mismo que decir que ninguna formula de la forma ¬α1 ٨ ... ٨ ¬αn no es contradiccion. Pero esto ultimo es lo mismo que decir que todo subconjunto finito de negaciones de formulas de Γ es satisfacible. Entonces ¬Γ = {¬α, α ε Γ} es satisfacible. Entonces, existe v valuacion tal que v(¬α) = 1 para todo α en Γ. Esto contradice la hipotesis de que v satisface al menos una formula de Γ. Entonces, tienen que existir finitas formulas α1, ... , αn tales que su disyuncion es una tautologia.

Ejercicio 10

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, {α} |= γ .