Diferencia entre revisiones de «Práctica 6: Árboles del Cálculo de Predicados (Lógica y Computabilidad)»
Línea 33: | Línea 33: | ||
==Ejercicio 02== | ==Ejercicio 02== | ||
==Ejercicio 03== | ==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. | |||
<br> | Se procede a dicha demostración mediante un árbol de refutación con la siguiente forma: | ||
<br> | |||
<br> | ''¬(φ→∀xφ)''<br /> | ||
<br> | ''φ''<br /> | ||
<br>× | ''¬∀xφ''<br /> | ||
''¬φ[x/c]'', donde ''c'' es una constante.<br /> | |||
''¬φ'', pues ''φ'' es un enunciado universalmente válido.<br /> | |||
''×'' | |||
==Ejercicio 04== | ==Ejercicio 04== |
Revisión del 23:32 6 ago 2010
Ejercicio 01
¬((∀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
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φ)
φ
¬∀xφ
¬φ[x/c], donde c es una constante.
¬φ, pues φ es un enunciado universalmente válido.
×
Ejercicio 04
Ejercicio 05
Ejercicio 06
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
Ejercicio 08
Ejercicio 09
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)} >