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==

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'')''φ'').
Luego, si logramos probar que ¬(''φ''→(∀''x'')''φ'') es insatisfacible, habremos demostrado lo que nos piden. 

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:#708070" | donde ''c'' es una constante.
|-
| colspan="2" | ¬''φ''
| style="text-align:left;color:#708070" | ¬''φ''[''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.

==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]]