Acciones

Diferencia entre revisiones de «Relación 2»

De Lógica informática (2014-15)

(→‎Relación 2: Semántica proposicional)
 
(No se muestran 17 ediciones intermedias de 4 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 15: Línea 19:
 
* Contradicción  e insatisfacible: 3
 
* 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 24: Línea 71:
 
----
 
----
  
−
'''Solución:''' La pista correcta es la de la pista uno, por lo tanto, será la primera puerta la que salve al 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.
  
−
''Comentario:'' Hay que razonar la respuesta.
+
'''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
−
 
 
−
'''Solución:''' 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.
 
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?
Línea 42: Línea 96:
 
----
 
----
  
−
'''Solución:''' p → q ^ ¬q
+
'''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 51: 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.
+
Sea F = p ^ ¬p → q. F es tautología, pero la subfórmula p ^ ¬p es insatisfacible.
−
# p v p
+
 
 +
'''Solución del 2º apartado'''
 +
p v p

Revisión actual del 17: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?

  1. p → (q → r ∧ q)
  2. q → ((p ∧ ¬p) → r)
  3. (p ↔ q) ∧ (p → ¬q) ∧ p
  4. (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:

  1. Si F es una fórmula satisfacible, entonces todas las subfórmulas de F son satisfacibles.
  2. 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

Obtenido de «https://www.glc.us.es/~jalonso/ejerciciosLI2014/index.php?title=Relación_2&oldid=98»