Diferencia entre revisiones de «Práctica 6: Árboles del Cálculo de Predicados (Lógica y Computabilidad)»
(No se muestran 10 ediciones intermedias del mismo usuario) | |||
Línea 32: | Línea 32: | ||
==Ejercicio 02== | ==Ejercicio 02== | ||
Salen todos bastante fácil usando árboles. | |||
==Ejercicio 03== | ==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:#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. | |||
==Ejercicio 04== | ==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 05== | ||
==Ejercicio 06== | ==Ejercicio 06== |
Revisión actual - 01:23 7 ago 2010
Ejercicio 01[editar]
¬((∀x∃y(P(x, y) -> P(y, x))) -> (∀x∀y(P(x, y -> ∃zP(z, x)))))
∀x∃y(P(x, y) -> P(y, x))
¬∀x∀y(P(x, y -> ∃zP(z, x)))
∃x∃y¬(P(x, y) -> ∃zP(z, x))
∃y¬(P(a1, y) -> ∃zP(z, a1))
¬(P(a1, a2) -> ∃zP(z, a1))
P(a1, a2)
¬∃P(z, a1)
∀z¬P(z, a1)
∃y(P(a1, y) -> P(y, a1))
P(a1, a3) -> P(a3, a1)
¬P(a1, a3) P(a3, a1)
¬P(a3, a1)
×
¬((∀x∃y(P(x, y) -> P(y, x))) -> (∀x∀y(P(x, y -> ∃zP(z, x)))))
∀x∀y(P(x, y -> ∃zP(z, x)))
¬∀x∃y(P(x, y) -> P(y, x))
∃x∀y(P(x, y) -> P(y, x))
∀y(P(a1, y) -> P(y, a1))
∀y(P(a1, y) -> ∃zP(z, a1))
P(a1, a2) -> ∃zP(z, a1)
¬P(a1, a2)
P(a1, a2) -> P(a2, a1)
¬P(a1, a2) P(a2, a1)
∃zP(z, a1)
P(a3, a1)
P(a1, a3) -> P(a3, a1)
¬P(a1, a3) P(a3, a1)
Ejercicio 02[editar]
Salen todos bastante fácil usando árboles.
Ejercicio 03[editar]
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:
¬(φ→(∀x)φ) | ||
φ | ||
¬(∀x)φ | ||
¬φ[x/c] | donde c es una constante. | |
¬φ | ¬φ[x/c] ≡ φ, pues φ es un enunciado universalmente válido. | |
× |
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[editar]
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:
Sean β, α1, ..., αk enunciados, entonces {α1, ..., αk} ⊨ β si y sólo si el enunciado α1 ∧ ... ∧ αk ∧ ¬β origina un árbol de refutación cerrado.
Entonces procedemos a construir un árbol de refutación de φ ∧ (φ→ψ) ∧ ¬ψ:
( (φ ∧ (φ→ψ)) ∧ ¬ψ ) | |
(φ ∧ (φ→ψ)) | |
¬ψ | |
φ | |
(φ→ψ) | |
¬φ | ψ |
× | × |
Luego como el árbol es cerrado, la relación de consecuencia se cumple y queda demostrado lo que nos piden.
Ejercicio 05[editar]
Ejercicio 06[editar]
1. (∀x∃yP(x, y)) ^ ¬(∃y∀xP(x, y))
∀x∃yP(x, y)
¬∃y∀xP(x, y)
∃yP(a, y)
P(a, b)
¬∀xP(x, b)
¬P(c, b)
Contraejemplo: I =< {a, b}, {(a, b), (b, a)} >
2. (∃y∀xP(x, y)) ^ ¬(∀x∃yP(x, y))
∃y∀xP(x, y)
¬∀x∃yP(x, y)
∀xP(x, a)
¬∃yP(b, y)
P(b, a)
¬P(b, a)
×
Ejercicio 07[editar]
Ejercicio 08[editar]
Ejercicio 09[editar]
1. (α1 ^ α2 ^ α3) ^ ¬α4 = ∀x∀y∀z((P(x, y) ^ P(y, z)) ->
P(x, z))
∀x∀y(P(x, y) -> P(y, x))
∀x∃yP(x, y)
¬∀xP(x, x)
¬P(a, a)
∃yP(a, y)
P(a, b)
∀y(P(a, y) -> P(y, a))
P(a, b) -> P(b, a)
∀y∀z((P(a, y) ^ P(y, z)) -> P(a, z))
∀z((P(a, b) ^ P(b, z)) -> P(a, z))
(P(a, b) ^ P(b, a)) -> P(a, a)
¬(P(a, b) ^ P(b, a)) P(a, a)
¬P(a, b) ¬P(b, a) ×
× ¬P(a, b) P(b, a)
× ×
2. (α1 ^ α3) ^ ¬α4 = ∀x∀y∀z((P(x, y) ^ P(y, z)) -> P(x, z))
∀x∃yP(x, y)
¬∀xP(x, x)
¬P(a, a)
∃yP(a, y)
P(a, b)
∀y∀z((P(a, y) ^ P(y, z)) -> P(a, z))
∀z((P(a, b) ^ P(b, z)) -> P(a, z))
(P(a, b) ^ P(b, a)) -> P(a, a)
¬(P(a, b) ^ P(b, a)) P(a, a)
¬P(a, b) ¬P(b, a) ×
×
Contraejemplos:
a) {N,<}
b) < {a, b}, {(a, b), (b, b)} >