Relación 2b

Relación 2b: Sintaxis y semántica de la Lógica proposicional

---

Ejercicio 1. 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: (Nota: Podemos suponer que en una habitacion hay un tigre o una dama exclusivamente pues si se diera que en una misma habitación estuviera el tigre y la dama, el prisionero no debería estar buscando la habitación de la dama, pues si la encontrara el resultado sería desastroso)

Entonces podemos suponer que si el tigre no está en una entonces está en la otra y análogamente con la dama.

p:"Tigre en 1 y Dama en 2"
¬p:"Tigre en 2 y Dama en 1"

Luego tenemos, segun lo que ha dicho el Rey que:

(p ⋁ ¬p)

 Puerta 1 dice "En esta habitacion hay una dama y en la otra un tigre"
          es decir 1 dice: p

    q: "En una habitacion hay una dama"
    s: "En una habitacion hay un tigre"

 Puerta 2 dice "En una de estas habitaciones hay un tigre
               y en una de estas habitaciones hay una dama"
                 es decir 2 dice: q ⋀ s

a: 1 dice verdad
b: 2 dice verdad

Tenemos entonces por el enunciado que a<--->¬b

Supongamos: que 1 dice la verdad (I(a)=1)si y solo si2 miente(I(¬b)=1) y entonces tenemos que en la habitacion 1 hay una dama y en la otra un tigre(I(p)=1) y que en ninguna habitacion hay una tigre y en ninguna hay una dama(I(¬(q ⋀ s), y esto implicaria que en 1 no hay dama ni tigre y en dos tampoco.

F= (p ⋁ ¬p) ⋀ ((a <––> ¬b) ——> (p ⋀ (¬(q ⋀ s)—–>(¬(p ⋁ ¬p)))))

Pero para nuestra interpretación I(F)={I(a) = I(¬b) = I(p) = I(¬(q ⋀ s)) = 1} nos sale que I(F)=0

Luego La puerta 1 no dice la verdad y la puerta 2 dice la verdad, y por tanto en la habitación 1 está el tigre y en la habitacion 2 está la dama que es por donde debe escapar el prisionero

Solución alternativa 2.0

Haciendo paso a paso el problema vemos que de la primera información que se le da al prisionero no se deduce que si en una puerta hay una dama en la otra debe haber un tigre, sino simplemente que en una misma habitación solo puede haber o la dama o el tigre a la vez, pero no sabemos nada de la otra puerta. La afirmación de que una dama en una habitación implica tigre en la otra la sacamos de los letreros de las puertas, así pues, lo primero que haremos es establecer las siguiente proposiciones

p:"Dama en la puerta 1"
¬p:"No hay Dama en puenta 1" ≡ "Tigre en puerta 1"
q:"Dama en la puerta 2"
¬q:"No hay Dama en puenta 2" ≡ "Tigre en puerta 2"

Si consideramos F = (p ⋀ ¬q) la afirmación de la puerta 1 dice F.

La puerta 2 dice (p ⋁ q) ⋀ (¬p ⋁ ¬q) = ((p ⋁ q)⋀ ¬p) ⋁ ((p ⋁ q) ⋀ ¬q) = (p ⋀ ¬p) ⋁ (q ⋀ ¬p) ⋁ (p ⋀ ¬q) ⋁ (q ⋀ ¬q).

Como sabemos que (p ⋀ ¬p) y (q ⋀ ¬q) no pueden cumplirse podemos descartarlas.

Si consideramos G = (¬p ⋀ q) y teniendo en cuenta lo anterior, de la afirmación de la puerta 2 se deduce F ⋁ G

Como se nos informa de que una puerta dice la verdad y la otra no, estudiamos los dos casos posibles.

En el primer caso supongamos que la puerta 1 dice la verdad y la otra miente entonces se tiene

F <--> ¬(F ⋁ G) = F <--> (¬F ⋀ ¬G) = (F <--> ¬F) ⋀ (F <--> ¬G). 
Y como  F <--> ¬F sabemos que es insatisfacible, entonces F <--> ¬(F ⋁ G) es insatisfacible.

Ahora vamos con el caso de que la primera puerta miente y la segunda dice la verdad tenemos que

¬F <--> (F ⋁ G) = (¬F <--> F) ⋁ (¬F <--> G).

La primera fórmula de la disyunción ya sabemos que es insatisfacible, por tanto veamos la segunda.

(¬F <-->G) = ¬(p ⋀¬q)<-->(¬p ⋀ q) = ((p ⋀ q)⋁(¬p⋀¬q)⋁(¬p ⋀ q))<-->(¬p ⋀ q) =
= (((p ⋀ q)⋁(¬p⋀¬q))<-->(¬p⋀q))⋁((¬p⋀q)<-->(¬p⋀q)) 

Vemos claramente que es satisfacible, Por tanto el prisionero deberá de abrir la segunda puerta para encontrar a la dama.

---

Ejercicio 2. Sean S y T conjuntos de fórmulas. Demostrar o refutar las siguientes afirmaciones:

• 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.
• Si S es consistente y T es inconsistente, entonces S ∩ T es consistente.

---

Solución:

---

Ejercicio 3. Da un ejemplo de tres fórmulas F₁ , F₂ , y F₃ tales que F₁ ∧ F₂ ∧ F₃ sea insatisfactible y donde cualquier conjunción de todas ellas menos una sea satisfactible. Generalízalo a n fórmulas.

---

Solución:

Daremos un ejemplo del caso general. Para ello basta tomar F_i tautología, F_j satisfacible con i=/j y el resto de fórmulas F_k insatisfacibles con k=/i,j siendo i,j,k \in {1,2,...,n}

Pablo José Gerlach Mena

Solución 2:

Eso es falso Pablo, no puedo haber ninguna insatisfacible, ya que dada si existe una insatisfacible cuando coges esa y n-2 fórmulas mas, la conjunción de dichas es insatisfacible y no cumple la segunda propiedad de que cualquier conjunción de todas ellas menos una sea satisfacible.

La solución sería:

F₁= p

F₂ = p->¬q

F₃ = (p/\¬q) -> q

Con estas fórmulas se da que la conjunción de todas es insatisfacible y la conjunción de dos a dos es satisfacible.

La generalización a n fórmulas no la he demostrado aún.(3 minutos mas tarde)

Demostrada la generalización en n

Sean p_i con i= 1,2.. n-1. Denotamos por:

F₁=p_1

F_j= p_1-> ¬p_j j=2,3..n-1.

F_n= (p_1\/¬p_1)-> p_2\/p_3\/..\/p_n-1

Se puede comprobar mediante recursión que esto funciona.

---

Ejercicio 4.

• Probar que la fórmula (((p → q) → p) → p) es una tautología
• Si definimos recursivamente A(0) = (p → q) y A(n+1) = (A(n) → p), ¿para qué

valores de n es A es una tautología?

---

Solución:

se puede hacer con tablas de verdad: suponemos que es falsa

(((p → q) → p) → p)

             0
        1      0
   0      1    

(((p → q) → p) → p)

             0
        1      0
   0      0
 1   0

(((p → q) → p) → p)

             0
        1      0
   1      1

estas son todas las interpretaciones posibles y vemos que en todas hay contradicción (en negrita) asi que es siempre verdadera