Diferencia entre revisiones de «Relación 2»
De Lógica informática (2014-15)
| (No se muestran 25 ediciones intermedias de 6 usuarios) | |||
| Línea 1: | Línea 1: | ||
=== Relación 2: Semántica proposicional === | === Relación 2: Semántica proposicional === | ||
| + | |||
| + | <div style="color: red"> | ||
| + | '''Nota.''' En todos los ejercicios hay que '''razonar''' la respuesta. | ||
| + | </div> | ||
---- | ---- | ||
| Línea 5: | Línea 9: | ||
# p → (q → r ∧ q) | # p → (q → r ∧ q) | ||
| − | # q → (p ∧ ¬p) → r | + | # q → ((p ∧ ¬p) → r) |
# (p ↔ q) ∧ (p → ¬q) ∧ p | # (p ↔ q) ∧ (p → ¬q) ∧ p | ||
# (p ∧ r) ∨ (¬ p ∧ q) → ¬ q | # (p ∧ r) ∨ (¬ p ∧ q) → ¬ q | ||
| Línea 11: | Línea 15: | ||
---- | ---- | ||
| − | ''' | + | '''Solución:''' |
| + | * Contingente y satisfacible: 1,2 Y 4 | ||
| + | * Contradicción e insatisfacible: 3 | ||
| + | '''2ª Solución del 1º apartado:''' | ||
| + | |||
| + | Por el método de Quine, sabemos que no es tautología porque para la valoración I(p)=1, I(q)=1, I(r)=0 obtenemos que la fórmula es insatisfacible. | ||
| + | Es contingente ya que para la valoración I(p)=0, I(q)=1, I(r)=0 la fórmula es satisfacible. | ||
| + | |||
| + | '''2ª Solución del 2º apartado:''' | ||
| + | |||
| + | La subfófmula (p ∧ ¬p) siempre será falsa, por lo tanto la fórmula solo será cierta cuando I(q)=0, independientemente de lo que valga r. Contingente. | ||
| + | |||
| + | '''2ª Solución del 3º apartado:''' | ||
| + | |||
| + | p | q | fórmula | ||
| + | 0 | 0 | 0 | ||
| + | 0 | 1 | 0 | ||
| + | 1 | 0 | 0 | ||
| + | 1 | 1 | 0 | ||
| + | |||
| + | Contradicción, su tabla de verdad siempre vale 0. | ||
| + | |||
| + | ''Comentario:'' Las [http://es.wikipedia.org/wiki/Ayuda:Tablas tablas] también se pueden escribir como sigue | ||
| + | |||
| + | {| border="1" | ||
| + | | p || q || fórmula | ||
| + | |- | ||
| + | | 0 || 0 || 0 | ||
| + | |- | ||
| + | | 0 || 1 || 0 | ||
| + | |- | ||
| + | | 1 || 0 || 0 | ||
| + | |- | ||
| + | | 1 || 1 || 0 | ||
| + | |} | ||
| + | |||
| + | '''2ª Solución del 4º apartado:''' | ||
| + | |||
| + | Al realizar su tabla de verdad, obtenemos que es cierta para algunos casos y falsas para otros, por lo tanto la fórmula es contingente. | ||
| + | |||
| + | ''' Otra solución ''' | ||
| + | 1. Contingente y satisfactible | ||
| + | 2. Contingente y satisfactible | ||
| + | 3. Contradicción, por tanto insatisfactible | ||
| + | 4. Contingente y satisfactible | ||
| + | |||
---- | ---- | ||
'''Ejercicio 2.''' Un rey somete a un prisionero a la siguiente prueba: lo enfrenta a dos puertas, de las que el prisionero debe elegir una, y entrar en la habitación correspondiente. Se informa al prisionero que en cada una de las habitaciones puede haber un tigre o una dama. Como es natural, el prisionero debe elegir la puerta que le lleva a la dama (entre otras cosas, para no ser devorado por el tigre). Para ayudarle, en cada puerta hay un letrero: | '''Ejercicio 2.''' Un rey somete a un prisionero a la siguiente prueba: lo enfrenta a dos puertas, de las que el prisionero debe elegir una, y entrar en la habitación correspondiente. Se informa al prisionero que en cada una de las habitaciones puede haber un tigre o una dama. Como es natural, el prisionero debe elegir la puerta que le lleva a la dama (entre otras cosas, para no ser devorado por el tigre). Para ayudarle, en cada puerta hay un letrero: | ||
| Línea 22: | Línea 71: | ||
---- | ---- | ||
| − | '''Solución:''' | + | '''Solución 1:''' La pista correcta es la de la pista uno, por lo tanto, será la primera puerta la que salve al prisionero. |
| + | |||
| + | '''Solución 2:''' Uno de los dos carteles dice la verdad, lógicamente es el segundo, puesto que lo dice el enunciado. Por lo tanto, la primera puerta | ||
| + | no dice la verdad, y el prisionero debería entrar en la puerta 2 si quiere seguir con vida. | ||
| + | '''Solución 3''' | ||
| + | Si hacemos el ejemplo con fórmulas tendríamos: | ||
| + | p= en esta habitación hay una dama | ||
| + | q= en la otra hay un tigre | ||
| + | r= en una de estas habitaciones hay una dama | ||
| + | s= en una de estas habitaciones hay un tigre | ||
| + | De manera que el cartel de puerta 1= p & q, esta fórmula si admite hipótesis del tipo ~p & q, p & ~q, ~p & ~q de las cuales la única cierta es la primera | ||
| + | La fórmula el cartel de la puerta 2= r & s no admite mas hipótesis puesto que ~r y ~s son contradicciones y siempre es verdad por tanto | ||
| + | Pienso que por eliminación el cartel de la puerta 1 miente y debe elegir la puerta 2 | ||
---- | ---- | ||
'''Ejercicio 3.''' ¿Existe un conjunto S de tres fórmulas tal que de todos los subconjuntos de S sólo uno es consistente? | '''Ejercicio 3.''' ¿Existe un conjunto S de tres fórmulas tal que de todos los subconjuntos de S sólo uno es consistente? | ||
---- | ---- | ||
| − | '''Solución:''' | + | '''Solución:''' S = { p ^ ¬p , q ^ ¬q, r}. |
| Línea 35: | Línea 96: | ||
---- | ---- | ||
| − | '''Solución:''' | + | '''Solución 1:''' p → q ^ ¬q: no es satisfascible F: contraejemplo no válido |
| + | |||
| + | '''Solución 2:''' Sí, ya que el único modelo de F, al ser atómica, es 1, y para que F → G sea satisfascible, G no puede dar 0. Por tanto, G tiene que ser satisfascible. | ||
| + | |||
| + | '''Solución 3:''' | ||
| + | |||
| + | Para que F -> G sea satisfactible, partiendo de que F es satisfactible ( es decir puede ser "1" en la fórmula anterior ) G debe ser "1" para que la implicación sea "1". Por tanto G es satisfactible. | ||
---- | ---- | ||
| Línea 44: | Línea 111: | ||
---- | ---- | ||
| − | '''Solución | + | '''Solución del 1º apartado''' |
| + | Sea F = p ^ ¬p → q. F es tautología, pero la subfórmula p ^ ¬p es insatisfacible. | ||
| + | |||
| + | '''Solución del 2º apartado''' | ||
| + | p v p | ||
Revisión actual del 16:28 5 oct 2014
Relación 2: Semántica proposicional
Nota. En todos los ejercicios hay que razonar la respuesta.
Ejercicio 1. Clasificar las fórmulas siguientes en tautologías, contingentes y contradicciones. ¿Cuáles son satisfacibles? ¿Cuáles son insatisfacibles?
- p → (q → r ∧ q)
- q → ((p ∧ ¬p) → r)
- (p ↔ q) ∧ (p → ¬q) ∧ p
- (p ∧ r) ∨ (¬ p ∧ q) → ¬ q
Solución:
- Contingente y satisfacible: 1,2 Y 4
- Contradicción e insatisfacible: 3
2ª Solución del 1º apartado:
Por el método de Quine, sabemos que no es tautología porque para la valoración I(p)=1, I(q)=1, I(r)=0 obtenemos que la fórmula es insatisfacible. Es contingente ya que para la valoración I(p)=0, I(q)=1, I(r)=0 la fórmula es satisfacible.
2ª Solución del 2º apartado:
La subfófmula (p ∧ ¬p) siempre será falsa, por lo tanto la fórmula solo será cierta cuando I(q)=0, independientemente de lo que valga r. Contingente.
2ª Solución del 3º apartado:
p | q | fórmula 0 | 0 | 0 0 | 1 | 0 1 | 0 | 0 1 | 1 | 0
Contradicción, su tabla de verdad siempre vale 0.
Comentario: Las tablas también se pueden escribir como sigue
| p | q | fórmula |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
2ª Solución del 4º apartado:
Al realizar su tabla de verdad, obtenemos que es cierta para algunos casos y falsas para otros, por lo tanto la fórmula es contingente.
Otra solución
1. Contingente y satisfactible 2. Contingente y satisfactible 3. Contradicción, por tanto insatisfactible 4. Contingente y satisfactible
Ejercicio 2. Un rey somete a un prisionero a la siguiente prueba: lo enfrenta a dos puertas, de las que el prisionero debe elegir una, y entrar en la habitación correspondiente. Se informa al prisionero que en cada una de las habitaciones puede haber un tigre o una dama. Como es natural, el prisionero debe elegir la puerta que le lleva a la dama (entre otras cosas, para no ser devorado por el tigre). Para ayudarle, en cada puerta hay un letrero:
- puerta 1: en esta habitación hay una dama y en la otra un tigre.
- puerta 2: en una de estas habitaciones hay una dama y en una de estas habitaciones hay un tigre.
Sabiendo que uno de los carteles dice la verdad y el otro no, determinar la puerta que debe de elegir el prisionero.
Solución 1: La pista correcta es la de la pista uno, por lo tanto, será la primera puerta la que salve al prisionero.
Solución 2: Uno de los dos carteles dice la verdad, lógicamente es el segundo, puesto que lo dice el enunciado. Por lo tanto, la primera puerta no dice la verdad, y el prisionero debería entrar en la puerta 2 si quiere seguir con vida.
Solución 3 Si hacemos el ejemplo con fórmulas tendríamos:
p= en esta habitación hay una dama q= en la otra hay un tigre r= en una de estas habitaciones hay una dama s= en una de estas habitaciones hay un tigre
De manera que el cartel de puerta 1= p & q, esta fórmula si admite hipótesis del tipo ~p & q, p & ~q, ~p & ~q de las cuales la única cierta es la primera La fórmula el cartel de la puerta 2= r & s no admite mas hipótesis puesto que ~r y ~s son contradicciones y siempre es verdad por tanto Pienso que por eliminación el cartel de la puerta 1 miente y debe elegir la puerta 2
Ejercicio 3. ¿Existe un conjunto S de tres fórmulas tal que de todos los subconjuntos de S sólo uno es consistente?
Solución: S = { p ^ ¬p , q ^ ¬q, r}.
Ejercicio 4. ¿Es cierto que si F → G y F son satisfacibles, entonces G es satisfacible? Si es cierto, dar una explicación. Si no es cierto, dar un contraejemplo.
Solución 1: p → q ^ ¬q: no es satisfascible F: contraejemplo no válido
Solución 2: Sí, ya que el único modelo de F, al ser atómica, es 1, y para que F → G sea satisfascible, G no puede dar 0. Por tanto, G tiene que ser satisfascible.
Solución 3:
Para que F -> G sea satisfactible, partiendo de que F es satisfactible ( es decir puede ser "1" en la fórmula anterior ) G debe ser "1" para que la implicación sea "1". Por tanto G es satisfactible.
Ejercicio 5. Demostrar o refutar las siguientes proposiciones:
- Si F es una fórmula satisfacible, entonces todas las subfórmulas de F son satisfacibles.
- Existen fórmulas válidas tales que todas sus subfórmulas son válidas.
Solución del 1º apartado Sea F = p ^ ¬p → q. F es tautología, pero la subfórmula p ^ ¬p es insatisfacible.
Solución del 2º apartado p v p