Práctica 5 (LyC Verano)
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, {α} |= γ .
