Revisión actual |
Tu texto |
Línea 1: |
Línea 1: |
| {{Back|Lógica y Computabilidad}}
| | ==Ejercicio 01== |
| | |
| ==Ejercicio 02== | | ==Ejercicio 02== |
| ===a)=== | | ===a)=== |
| ''consultar por las dudas''
| | *1.SP3: (¬φ → ¬<font color=red>φ</font>) → [ (¬φ → <font color=red>φ</font>) → φ ] |
| | | *2.VALE: (¬φ → ¬φ) (ya que p → p es tautologia) |
| *1.SP1: ¬φ → ((¬φ → ¬φ) → ¬φ) | | *3.MP 1 y 2: (¬φ → φ) → φ |
| *2.SP2: (¬φ → ((¬φ → ¬φ) → ¬φ)) → ((¬φ → (¬φ → ¬φ)) → (¬φ → ¬φ))
| | → (¬φ → φ) → φ es tautologia |
| *3.MP1y2: (¬φ → (¬φ → ¬φ)) → (¬φ → ¬φ) | |
| *4.SP1: ¬φ → (¬φ → ¬φ)
| |
| *5.MP3y4: (¬φ → ¬φ)
| |
| *6.SP3: (¬φ → ¬φ) → ((¬φ → φ) → φ) | |
| *7.MP5y6: (¬φ → φ) → φ
| |
| |- (¬φ → φ) → φ
| |
|
| |
|
| ===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)=== |
| <br>Si (¬φ → ¬ψ) es F, la formula es tautologia.
| | |
| <br>Si (¬φ → ¬ψ) es T, entonces hay que probar que vale (ψ→φ). Entonces:
| | (Falta terminar) |
| *1.SP3: (¬φ → ¬ψ) → [ (¬φ → ψ) → φ ] | | *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.VALE: (¬φ → ¬ψ) (x HI)
| | *2.SP1: φ→[ψ → φ] |
| *3.MP 1 y 2: (¬φ → ψ) → φ
| | *3.VALE: [¬φ → ¬ψ]→(φ→[ψ → φ]) = [¬φ → ¬ψ]→T = tautologia |
| *4.SP1: ψ → (¬φ → ψ)
| | *4.MP 1 y 3: ([¬φ → ¬ψ]→φ)→([¬φ → ¬ψ]→[ψ → φ]) |
| *5.USANDO 3 y 4: {<font color=red>ψ</font> → (¬φ → ψ), (¬φ → ψ) → <font color=red>φ</font>} |- (ψ → φ) (x punto b)
| | *5.?? |
| <br>→Vale (ψ → φ)
| |
| <br>→ |- (¬φ → ¬ψ)→(ψ → φ)
| |
|
| |
|
| ==Ejercicio 03== | | ==Ejercicio 03== |
| '''(Sientanse libres de cambiar esta respuesta por alguna mas formal)'''<br>
| | ==Ejercicio 04== |
| 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== | | ==Ejercicio 05== |
| ===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)===
| |
| ===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)===
| |
|
| |
| ==(Ejercicio que no está en la práctica del 2º cuatrimestre 2009)==
| |
| ===a)=== | | ===a)=== |
| <pre> | | <pre> |
Línea 89: |
Línea 43: |
| x x | | x x |
| </pre> | | </pre> |
| → P es tautologia
| | →P es tautologia. |
|
| |
|
| ===b)=== | | ===b)=== |
Línea 95: |
Línea 49: |
| ((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 | | ¬p3 p2 (p1 ٧ p2) |
| ¬p3 ¬p1
| | ¬p3 ¬p3 |
| ¬p2
| |
| </pre> | | </pre> |
|
| |
|
| ¬P = (p1 ٨ ¬p3) ٧ (p2 ٨ ¬p3) ٧ (¬p1 ٨ ¬p2) ٧ ¬p3 = (¬p3 ٨ (p1 ٧ p2)) ٧ (¬p2 ٨ ¬p1) = (¬p3 ٨ ¬a) ٧ a ٧ p3 = 1. | | ¬P = (p1 ٨ ¬p3) ٧ (p2 ٨ ¬p3) ٧ ¬p3 = (p1 ٧ p2 ٧ T) ٨ ¬p3 = ¬p3. Es una contingencia |
| | |
| ¬P = 1, entonces P = 0. P es una contradicción.
| |
|
| |
|
| ===c)=== | | ===c)=== |
Línea 114: |
Línea 65: |
| ¬p1 ¬p2 | | ¬p1 ¬p2 |
| </pre> | | </pre> |
| ¬P = ((¬p1 ٧ ¬p2) ٧ p3) ٨ ¬p4. Como cada variable aparece 1 vez, ¬P es contingencia | | ¬P = ((¬p1 ٧ ¬p2) ٨ ¬p4) ٧ p3. Como cada variable aparece 1 vez, ¬P es contingencia |
|
| |
|
| ==(Ejercicio que no está en la práctica del 2º cuatrimestre 2009)== | | ==Ejercicio 06== |
| ===a)=== | | ===a)=== |
| <pre> | | <pre> |
| (((p0 ٨ ¬p0) ٨ p1) ٨ ¬(p1 ٨ (p1 → p0))) | | (((p0 ٨ ¬p0) ٨ p1) ٨ ¬(p1 ٨ (p1 → p0))) |
| ((p0 ٨ ¬p0) ٨ p1)
| | ((p0 ٨ ¬p0) ٨ p1) |
| ¬(p1 ٨ (p1 → p0))
| | ¬(p1 ٨ (p1 → p0)) |
| (p0 ٨ ¬p0)
| | (p0 ٨ ¬p0) |
| p1
| | p1 |
| ¬p1 ¬(p1 → p0)
| | ¬p1 |
| ¬p0 p0 | | p0 ¬(p1 → p0) |
| ¬p0 ¬p0
| | ¬p0 p0 |
| x p1
| | x ¬p0 |
| ¬p0
| | p1 |
| x
| | ¬p0 |
| | x |
| </pre> | | </pre> |
|
| |
| Agrego una cosa. Cabe destacar que si un conjunto de formulas es insatisfacible, entonces, cualquier formula es consecuencia semantica de este. Por lo tanto, <math>alfa</math> pertenece a Con(r).
| |
|
| |
| ===b)=== | | ===b)=== |
| <pre> | | <pre> |
Línea 165: |
Línea 114: |
| </pre> | | </pre> |
|
| |
|
| ==Ejercicio == | | ==Ejercicio 07== |
| ===a)=== | | ==Ejercicio 08== |
| {p},{p->q}
| |
| (cualquiera que no tenga negaciones seguro que cumple)
| |
| | |
| ===b)===
| |
| | |
| ==(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 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 07==
| |
| 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 (¿?)==
| |
| <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 Γ.
| |
|
| |
|
| ==Ejercicio 09== | | ==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== | | ==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, {α} |= γ .
| | <font color=white>code0401</font> |
| | ==Ejercicio 11== |
| | <font color=white>code0403</font> |
| | ==Ejercicio 12== |
| | ==Ejercicio 13== |
| | <font color=white>code0406</font> |
|
| |
|
| [[Category:Prácticas]] | | [[Category:Lógica y Computabilidad]] |