Diferencia entre revisiones de «Relación 7»
De Lógica informática (2014-15)
(→Relación 7: Temas 1 a 6) |
|||
| Línea 10: | Línea 10: | ||
'''Solución:''' | '''Solución:''' | ||
| + | 1. Suponemos: | ||
| + | S = {p} | ||
| + | T = {p ^ ¬p} | ||
| + | Por tanto | ||
| + | |||
| + | S U T = {p, p ^ ¬p} | ||
| + | |||
| + | Un conjunto de fórmulas es consistente cuando existe algún modelo que verifique todas las fórmulas del conjunto. | ||
| + | Como {p ^ ¬p} no tiene ningún modelo, {p, p ^ ¬p} tampoco lo tendrá. | ||
| + | |||
| + | 2. En el apartado anterior hemos demostrado que con ser uno de los conjuntos inconsistentes, el conjunto resultante de la unión será inconsistente. | ||
| + | |||
| + | 3. Suponemos: | ||
| + | S = {p} | ||
| + | T = {p ^ ¬p, p} | ||
| + | |||
| + | Por tanto | ||
| + | |||
| + | S ∩ T = {p} | ||
| + | |||
| + | En contraposición con los apartados anteriores, al tener ahora la intersección de un conjunto consistente y otro inconsistente, sí se cumple la consistencia en el conjunto resultante de la intersección. | ||
| + | |||
| + | {p} es consistente y {p ^ ¬p, p} es inconsistente. Sin embargo, la intersección elimina las fórmulas inconsistentes (por ser S un conjunto consistente), lo que implica que la intersección sea también consistente. | ||
| + | |||
| + | 4. En el apartado anterior hemos demostrado que la intersección de S consistente y T inconsistente resulta en un conjunto consistente. | ||
---- | ---- | ||
'''Ejercicio 2.''' Demostrar por deducción natural, tableros semánticos y resolución | '''Ejercicio 2.''' Demostrar por deducción natural, tableros semánticos y resolución | ||
Revisión del 11:50 16 nov 2014
Relación 7: Temas 1 a 6
Ejercicio 1. Sean S y T conjuntos de fórmulas. Demostrar o refutar las siguientes sentencias:
- Si S es consistente y T es inconsistente, entonces S ∪ T es consistente.
- Si S es consistente y T es inconsistente, entonces S ∪ T es inconsistente.
- Si S es consistente y T es inconsistente, entonces S ∩ T es consistente.
- Si S es consistente y T es inconsistente, entonces S ∩ T es inconsistente.
Solución: 1. Suponemos: S = {p} T = {p ^ ¬p}
Por tanto
S U T = {p, p ^ ¬p}
Un conjunto de fórmulas es consistente cuando existe algún modelo que verifique todas las fórmulas del conjunto. Como {p ^ ¬p} no tiene ningún modelo, {p, p ^ ¬p} tampoco lo tendrá.
2. En el apartado anterior hemos demostrado que con ser uno de los conjuntos inconsistentes, el conjunto resultante de la unión será inconsistente.
3. Suponemos: S = {p} T = {p ^ ¬p, p}
Por tanto
S ∩ T = {p}
En contraposición con los apartados anteriores, al tener ahora la intersección de un conjunto consistente y otro inconsistente, sí se cumple la consistencia en el conjunto resultante de la intersección.
{p} es consistente y {p ^ ¬p, p} es inconsistente. Sin embargo, la intersección elimina las fórmulas inconsistentes (por ser S un conjunto consistente), lo que implica que la intersección sea también consistente.
4. En el apartado anterior hemos demostrado que la intersección de S consistente y T inconsistente resulta en un conjunto consistente.
Ejercicio 2. Demostrar por deducción natural, tableros semánticos y resolución
- ¬(p ∧ ¬q) ⊧ p → q
Solución:
Ejercicio 3. Un pirata se encuentra con cuatro cofres y una inscripción en cada uno de ellos. En el primer cofre dice "El tesoro no está aquí". En el segundo, dice "El tesoro está en el cofre 3". En el tercero dice "El cofre 1 dice la verdad". Y, en el cuarto dice "El cofre 2 miente". Ayuda al pirata a encontrar el tesoro, sabiendo que de los cuatro letreros, al menos tres mienten.
Solución:
Ejercicio 4. Decidir, utilizando formas normales, si la fórmula
- (p → ¬(q → ¬r)) ∧ (r → ¬q)
es insatisfactible o una tautología.
Solución:
Ejercicio 5. Decidir, usando el algoritmo DPLL y resolución, si el conjunto de cláusulas
- {{p,r,¬s}, {¬q,s}, {¬p,¬s,¬r}, {¬p,s,q},{s,q,p}, {¬q,¬r}, {¬s,¬r,p}}
es consistente. En caso de que lo sea, proporcionar un modelo del mismo.
Solución: