Edición de «Práctica 6: Árboles del Cálculo de Predicados (Lógica y Computabilidad)»

{{Back|Lógica y Computabilidad}}

==Ejercicio 01==
<br>¬((∀x∃y(P(x, y) -> P(y, x))) -> (∀x∀y(P(x, y -> ∃zP(z, x)))))
<br>∀x∃y(P(x, y) -> P(y, x))
<br>¬∀x∀y(P(x, y -> ∃zP(z, x)))
<br>∃x∃y¬(P(x, y) -> ∃zP(z, x))
<br>∃y¬(P(a1, y) -> ∃zP(z, a1))
<br>¬(P(a1, a2) -> ∃zP(z, a1))
<br>P(a1, a2)
<br>¬∃P(z, a1)
<br>∀z¬P(z, a1)
<br>∃y(P(a1, y) -> P(y, a1))
<br>P(a1, a3) -> P(a3, a1)
<br>¬P(a1, a3) P(a3, a1)
<br>¬P(a3, a1)
<br>×
<br>¬((∀x∃y(P(x, y) -> P(y, x))) -> (∀x∀y(P(x, y -> ∃zP(z, x)))))
<br>∀x∀y(P(x, y -> ∃zP(z, x)))
<br>¬∀x∃y(P(x, y) -> P(y, x))
<br>∃x∀y(P(x, y) -> P(y, x))
<br>∀y(P(a1, y) -> P(y, a1))
<br>∀y(P(a1, y) -> ∃zP(z, a1))
<br>P(a1, a2) -> ∃zP(z, a1)
<br>¬P(a1, a2)
<br>P(a1, a2) -> P(a2, a1)
<br>¬P(a1, a2) P(a2, a1)
<br>∃zP(z, a1)
<br>P(a3, a1)
<br>P(a1, a3) -> P(a3, a1)
<br>¬P(a1, a3) P(a3, a1)

==Ejercicio 02==
==Ejercicio 03==
Se quiere ver que si ⊨φ entonces ⊨∀xφ. Esto es lo mismo que ver que ⊨(φ→∀xφ).
Luego, si se logra probar que ¬(φ→∀xφ) es insatisfacible, listo. 
Se procede a dicha demostración mediante un árbol de refutación con la siguiente forma:

''¬(φ→∀xφ)''<br />
''φ''<br />
''¬∀xφ''<br />
''¬φ[x/c]'', donde ''c'' es una constante.<br />
''¬φ'', pues ''φ'' es un enunciado universalmente válido.<br />
''×''

==Ejercicio 04==

Si prestamos atención, en realidad nos están pidiendo demostrar que ''ψ'' es consecuencia de ''φ'' y (''φ→ψ''). Es decir, la preservación de la validez del ''modus ponens'' en lógica de primer orden.

Hay un corolario que dice:<br />
<span style="color:#505080">Sean ''β'', ''α''<sub>1</sub>, ..., ''α''<sub>k</sub> enunciados, entonces  {''α''<sub>1</sub>, ..., ''α''<sub>k</sub>} ⊨ ''β'' si y sólo si el enunciado ''α''<sub>1</sub> ∧ ... ∧ ''α''<sub>k</sub> ∧ ¬β origina un árbol de refutación cerrado.</span>

Entonces procedemos a construir un árbol de refutación de ''φ'' ∧ (''φ→ψ'') ∧ ''¬ψ'':

{| class="wikitable" style="text-align: center"
|- 
| colspan="2" | ( (''φ'' ∧ (''φ→ψ'')) ∧ ''¬ψ'' )
|- 
| colspan="2" | (''φ'' ∧ (''φ→ψ''))
|-
| colspan="2" | ''¬ψ''
|-
| colspan="2" | ''φ''
|-
| colspan="2" | (''φ''→''ψ'')
|-
| ''¬φ'' 
| ''ψ''
|-
| × 
| ×
|}

Luego como el árbol es cerrado, la relación de consecuencia se cumple y queda demostrado lo que nos piden.

==Ejercicio 05==
==Ejercicio 06==
<br>1. (∀x∃yP(x, y)) ^ ¬(∃y∀xP(x, y))
<br>∀x∃yP(x, y)
<br>¬∃y∀xP(x, y)
<br>∃yP(a, y)
<br>P(a, b)
<br>¬∀xP(x, b)
<br>¬P(c, b)
<br>Contraejemplo: I =< {a, b}, {(a, b), (b, a)} >

<br>2. (∃y∀xP(x, y)) ^ ¬(∀x∃yP(x, y))
<br>∃y∀xP(x, y)
<br>¬∀x∃yP(x, y)
<br>∀xP(x, a)
<br>¬∃yP(b, y)
<br>P(b, a)
<br>¬P(b, a)
<br>×

==Ejercicio 07==
==Ejercicio 08==
==Ejercicio 09==
<br>1. (α1 ^ α2 ^ α3) ^ ¬α4 = ∀x∀y∀z((P(x, y) ^ P(y, z)) -> <br>P(x, z))
<br>∀x∀y(P(x, y) -> P(y, x))
<br>∀x∃yP(x, y)
<br>¬∀xP(x, x)
<br>¬P(a, a)
<br>∃yP(a, y)
<br>P(a, b)
<br>∀y(P(a, y) -> P(y, a))
<br>P(a, b) -> P(b, a)
<br>∀y∀z((P(a, y) ^ P(y, z)) -> P(a, z))
<br>∀z((P(a, b) ^ P(b, z)) -> P(a, z))
<br>(P(a, b) ^ P(b, a)) -> P(a, a)
<br>¬(P(a, b) ^ P(b, a))  P(a, a)
<br>¬P(a, b) ¬P(b, a) ×
<br>× ¬P(a, b) P(b, a)
<br>     ×       ×

<br>2. (α1 ^ α3) ^ ¬α4 = ∀x∀y∀z((P(x, y) ^ P(y, z)) -> P(x, z))
<br>∀x∃yP(x, y)
<br>¬∀xP(x, x)
<br>¬P(a, a)
<br>∃yP(a, y)
<br>P(a, b)
<br>∀y∀z((P(a, y) ^ P(y, z)) -> P(a, z))
<br>∀z((P(a, b) ^ P(b, z)) -> P(a, z))
<br>(P(a, b) ^ P(b, a)) -> P(a, a)
<br>¬(P(a, b) ^ P(b, a)) P(a, a)
<br>¬P(a, b) ¬P(b, a) ×
<br>×
<br>Contraejemplos:
<br>a) {N,<}
<br>b) < {a, b}, {(a, b), (b, b)} >

==Ejercicio 10==
==Ejercicio 11==

[[Category:Prácticas]]
@@ Línea 32: / Línea 32: @@
 ==Ejercicio 02==
-Salen todos bastante fácil usando árboles.
 ==Ejercicio 03==
-Lo que nos piden ver es que si ⊨''φ'' entonces ⊨(∀''x'')''φ'' (la ida de la ''clausura universal''). Esto es lo mismo que ver que ⊨(''φ''→(∀''x'')''φ'').
+Se quiere ver que si ⊨φ entonces ⊨∀xφ. Esto es lo mismo que ver que ⊨(φ→∀xφ).
-Luego, si logramos probar que ¬(''φ''→(∀''x'')''φ'') es insatisfacible, habremos demostrado lo que nos piden.
+Luego, si se logra probar que ¬(φ→∀xφ) es insatisfacible, listo.
+Se procede a dicha demostración mediante un árbol de refutación con la siguiente forma:
-Hagámoslo mediante el siguiente árbol de refutación:
-{| class="wikitable" style="text-align:center"
-|-
-| colspan="2" | ¬(''φ''→(∀''x'')''φ'')
-|
-|-
-| colspan="2" | ''φ''
-|
-|-
-| colspan="2" | ¬(∀''x'')''φ''
-|
-|-
-| colspan="2" | ¬''φ''[''x''/''c'']
-| style="text-align:left;color:#607060" | donde ''c'' es una constante.
-|-
-| colspan="2" | ¬''φ''
-| style="text-align:left;color:#607060" | ¬''φ''[''x''/''c''] ≡ ''φ'', pues ''φ'' es un enunciado universalmente válido.
-|-
-| colspan="2" | ×
-|
-|}
-Como el árbol es cerrado, la negación de lo que queríamos demostrar es insatisfacible y por lo tanto queda demostrado lo que se pedía.
+''¬(φ→∀xφ)''<br />
+''φ''<br />
+''¬∀xφ''<br />
+''¬φ[x/c]'', donde ''c'' es una constante.<br />
+''¬φ'', pues ''φ'' es un enunciado universalmente válido.<br />
+''×''
 ==Ejercicio 04==