Relación 2b
De Lógica Matemática y fundamentos (2015-16)
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:
<math>Regla \quad 1: I(Puerta \quad 1) \neq I(Puerta \quad 2)</math>
<math>Regla \quad 2: \exists x=1,2 \quad : \quad I(Puerta \quad x) =1</math>
<math>I(Puerta \quad 1) = 1 \rightarrow I(Puerta \quad 2) = 1 \rightarrow \leftarrow \quad (R1) </math>
<math>\rightarrow I(Puerta \quad 1) = 0\rightarrow I(Puerta \quad 2) =1</math>
Luego, hay que entrar en la puerta 2.
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.
Solución:
Probemos la primera afirmación:
Sea S = {F₁,F₂..Fn} y T = {G₁,G₂..Gn}
Sabemos que un conjunto de fórmulas es consistente syss existe un modelo para la conjuncion de todas sus formulas.
Por tanto como T es inconsistente G₁∧G₂∧...∧Gn no tiene modelos, es decir; I(G₁∧G₂∧...∧Gn)=0 Para cualquier I.
Como <math>\equiv</math>(F₁∧F₂∧..∧Fn∧G₁∧G₂∧..∧Gn) = (F₁∧F₂∧..∧Fn)∧(G₁∧G₂∧..∧Gn) no existe modelo para (F₁∧F₂∧..∧Fn)∧(G₁∧G₂∧..∧Gn),
lo que implica que S ∪ T es inconsistente Q.E.D
Probemos la segunda afirmación:
En primer lugar probemos la monotonía:
Sea M = {H₁,H₂..Hn} un conjunto cualquiera de fórmulas y <math>L \subset M</math> un subconjunto.Entonces si M es consistente L es consistente.
Demostración:
Por Hipótesis, como M es consistente, entonces existe interpretación I tal que I(Hi)=1 para todo <math> 1 \leq i \leq n</math>.
Por tanto como L={Hi₁,Hi₂..Him}, L es consistente. Con esto es inmediato probar que S ∩ T es consistente, pues S ∩ T esta contenido en S.
Así pues S ∩ T es consistente Q.E.D
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:
<math>\lnot p,\lnot q , p \vee q </math>
La generalización a n fórmulas sería <math>\lnot p1,\lnot p2...\lnot p(n-1) </math> y <math>Fn = p1 \vee p2 \vee ...\vee p(n-1) </math>
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:
- Demostramos que es tautología mediante una tabla de verdad:
<math> \begin{array}{|c|c|c|c|c|} p & q & p -> q & (p -> q)->q & ((p -> q) -> p) -> p \\ \hline 1&1&1&1&1\\ 1&0&0&1&1\\ 0&1&1&0&1\\ 0&0&1&0&1\\ \end{array} </math>
- A(n) es tautología para n par.