| Revisión actual |
Tu texto |
| Línea 1: |
Línea 1: |
| {{Back|Lógica y Computabilidad}}
| |
|
| |
| ==Ejercicio 01== | | ==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))) -> (∀x∀y(P(x, y -> ∃zP(z, x))))) |
| Línea 32: |
Línea 30: |
|
| |
|
| ==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== |
| <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 07== |
| ==Ejercicio 08== | | ==Ejercicio 08== |
| ==Ejercicio 09== | | ==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 10== |
| ==Ejercicio 11== | | ==Ejercicio 11== |
|
| |
| [[Category:Prácticas]]
| |
