Posterior: Coherencia y completitud Arriba: Cálculo proposicional Anterior: Deducción natural

Ejercicios

1. Encuentre las negaciones de las siguientes proposiciones:

1. $p_1 \leftrightarrow ( p_2 \rightarrow \neg p_3 )$
2. $( p_1 \lor(\neg p_2 \land \neg p_3 ) )\lor( p_1 \lor(\neg p_3 \land \neg p_2 ) )\lor( p_2 \lor(\neg p_1 \land \neg p_3 ) )$

2. Sea $\mbox{\rm AX}_0$ el conjunto de axiomas $\mbox{\rm Ax}_1,\mbox{\rm Ax}_2$ y $\mbox{\rm Ax}_3$ vistos en clase. Si para una proposición $\phi$ se tiene $\vdash \phi$, escribiremos aquí $\vdash_{\mbox{\rm AX}_0} \phi$. Sea $\mbox{\rm Ax}_3'$ el siguiente esquema de axiomas:

$$\mbox{\rm Ax}_3' : (\neg \psi \rightarrow \neg \phi) \rightarrow (\phi \rightarrow \psi).$$

Sea $\mbox{\rm AX}_1 = \{\mbox{\rm Ax}_1,\mbox{\rm Ax}_2, \mbox{\rm Ax}_3'\}$. $\mbox{\rm AX}_1$ consiste de sustituir el esquema $\mbox{\rm Ax}_3$ por $\mbox{\rm Ax}_3'$ en $\mbox{\rm AX}_0$. La propiedad de ser demostrable en $\mbox{\rm AX}_1$ se define de igual manera que en $\mbox{\rm AX}_0$. Si $\phi$ es un teorema en $\mbox{\rm AX}_1$ escribiremos $\vdash_{\mbox{\rm AX}_1} \phi$. Demuestre la proposiciones siguientes:

1. El Teorema de Deducción es válido también para $\mbox{\rm Axi}_1$.
2. Los axiomas de $\mbox{\rm Ax}_3$ se pueden demostrar en $\mbox{\rm AX}_1$.
3. Los axiomas de $\mbox{\rm Ax}_3'$ se pueden demostrar en $\mbox{\rm AX}_0$.
4. $\forall \phi\in\mbox{\it Pbf}:\;\vdash_{\mbox{\rm AX}_0} \phi\;\Leftrightarrow\;\vdash_{\mbox{\rm AX}_1} \phi$.

3. Escriba pruebas en $\mbox{\rm AX}_0$ de los siguientes teoremas

1. $\phi \rightarrow ( \psi \rightarrow (\phi \rightarrow \psi))$.
2. $( \psi \rightarrow \phi) \rightarrow ( \neg \phi \rightarrow \neg \psi)$

4. Sea $\mbox{\rm AX}_2$ el sistema que se obtiene de $\mbox{\rm AX}_0$ al añadir el esquema de axiomas

$$\mbox{\rm Ax}_4 : (\neg \phi \rightarrow \psi) \rightarrow (\phi \rightarrow \neg \psi).$$

Muestre que $\mbox{\rm AX}_2$ es formalmente inconsistente.

5. Ley de permutación de premisas. Muestre que cualesquiera que sean $\phi, \psi,\chi$ se tiene

$$\{\phi \rightarrow ( \psi \rightarrow \chi )\} \vdash \psi \rightarrow (\phi \rightarrow \chi)$$

6. Exprese a la proposición $\phi \leftrightarrow \phi \lor (\phi \land \psi)$ en términos de $\neg$ y $\rightarrow$ únicamente.

7. Muestre que la expresión resultante en el ejercicio anterior es un teorema.

8. Sea $\mbox{\rm LX}_0$ el conjunto de axiomas $\mbox{\rm Lx}_1,\mbox{\rm Lx}_2$ y $\mbox{\rm Lx}_3$ siguientes:

$$\begin{eqnarray*} \mbox{\rm Lx}_1 &:& \left(\phi\rightarrow\psi\right)\rightarr... ...m Lx}_3 &:& \phi\rightarrow\left(\neg\phi\rightarrow\psi\right) \end{eqnarray*}$$

e introduzcamos la regla de modus ponens. Si para una proposición $\phi$ se tiene $\vdash \phi$, escribiremos aquí $\vdash_{\mbox{\rm LX}_0} \phi$. Decida si el sistema deductivo $\mbox{\rm AX}_0$ visto en clase subsume al $\mbox{\rm LX}_0$. Es decir, si para cualquier $\phi$ se cumple:

$$\vdash_{\mbox{\rm AX}_0} \phi \ \ \ \Rightarrow \ \ \ \vdash_{\mbox{\rm LX}_0} \phi.$$

9. Decida si el sistema deductivo $\mbox{\rm LX}_0$ del ejercicio anterior subsume al $\mbox{\rm AX}_0$ visto en clase. Es decir, si para cualquier $\phi$ se cumple:

$$\vdash_{\mbox{\rm LX}_0} \phi \ \ \ \Rightarrow \ \ \ \vdash_{\mbox{\rm AX}_0} \phi.$$

10. Subcálculo proposicional con la equivalencia. Considérese únicamente proposiciones con el conectivo $\leftrightarrow$. Específicamente, si $X=\{x_1,\ldots,x_n\}$ es un conjunto finito de variables proposicionales, se define $\mbox{\rm Pbf}_E(X)$ como sigue:

$$\begin{eqnarray*} x\in X &\Rightarrow& x\in \mbox{\rm Pbf}_E(X)\\ \phi,\psi\i... ...) &\Rightarrow& \phi\leftrightarrow\psi\in \mbox{\rm Pbf}_E(X). \end{eqnarray*}$$

Sea $A_{E,1}$ el sistema que consiste de los siguientes esquemas de axiomas:

$$\begin{eqnarray*} \mbox{\rm A}_{E,11} &:& \left(\left(\phi\leftrightarrow\psi\r... ...ght) \leftrightarrow \left(\psi\leftrightarrow\phi\right) %%\\ \end{eqnarray*}$$

y sea $A_{E,2}$ el sistema que consiste del siguiente esquema de axiomas:

$$\mbox{\rm A}_{E,21}:\ \left(\phi\leftrightarrow\psi\right)\... ...ight)\leftrightarrow\left(\psi\leftrightarrow\xi\right)\right).$$

Considérese con cualquiera de estos sistemas la regla modus ponens como la única de inferencia. Decida si el sistema $A_{E,1}$ es equivalente al $A_{E,2}$.

11. Muestre que todo teorema en el sistema $A_{E,1}$ del ejercicio anterior es también un teorema en el sistema $\mbox{\rm AX}_0$ visto en clase.

12. Considere el juego del AJEDREZ. Una configuración es cualquier manera de colocar las, o algunas, piezas del juego en el tablero del juego. Considere el sistema formal cuyo único axioma es la configuración inicial de cada partida y cuyas reglas de inferencia son precisamente las reglas del juego.

1. Caracterice a los teoremas en AJEDREZ.
2. Sea $P_{A,1}$ el conjunto de correspondencias que a cada casilla en el tablero le asocia una o ninguna pieza. Dé ejemplos de proposiciones en $P_{A,1}$ que no sean teoremas, es decir, que no sean deducibles en AJEDREZ.
3. Sea $P_{A,2}$ el conjunto de configuraciones que pueden aparecer en partidas legales. ¿Existen en este caso proposiciones que no sean deducibles?
4. Bosqueje un procedimiento para determinar si una configuración es o no un teorema.

13. Considere el CUBO DE RUBIK. Éste consta de 27 dados, los cuales dan $6\times 9=54$ subcaras externas. Sea RUBIK el sistema formal cuyo único axioma es la configuración inicial del cubo, es decir aquella en la que las 9 subcaras de cada una de las 6 caras del cubo de Rubik tienen un mismo color, y cuyas reglas de inferencia están dadas por los movimientos legales del cubo de Rubik.

1. Caracterice a los teoremas en RUBIK.
2. Sea $P_{R,1}$ el conjunto de correspondencias que a cada subcara externa le asocia un color. Dé ejemplos de proposiciones en $P_{R,1}$ que no sean teoremas, es decir, que no sean deducibles en RUBIK.
3. Busque en un libro de álgebra o del cubo de Rubik la caracterización de un conjunto $P_{A,2}$ de configuraciones tal que todas las configuraciones en él sean deducibles.
4. Bosqueje un procedimiento para determinar si una configuración es o no un teorema (observe que se pide ``un procedimiento'', no ``un procedimiento óptimo'').

14. Considere el alfabeto que consta de dos símbolos $A=\{a,b\}$. Sea $P_{A}=A^*$ el diccionario de $A$, es decir, el conjunto de todas las palabras de longitud finita sobre $A$. Considere las siguientes dos reglas de inferencia:

$$\begin{array}{cc} {\displaystyle{X \over Xb}} & {\displaystyle{X \over aXa}} \end{array}$$

Considere como único axioma a la palabra $a$.

1. Caracterice a los teoremas en ese sistema.
2. Dé ejemplos de proposiciones en $P_{A}$ que no sean teoremas, es decir, que no sean deducibles en ese sistema.
3. Bosqueje un procedimiento para determinar si una palabra en $P_{A}$ es o no un teorema.

15. Definición formal de la conjunción. En el sistema formal $\mbox{\rm Pbf}_H(X)$, con el conjunto de axiomas $\mbox{\rm AX}_0= \mbox{\rm Ax}_1 \cup \mbox{\rm Ax}_2 \cup \mbox{\rm Ax}_3$ escribimos $\phi\land \psi$ como una abreviatura de la proposición $\neg(\phi\rightarrow \neg\psi)$. Muestre que, cualesquiera que sean las proposiciones $\phi$, $\psi$ se tiene:

1. $\vdash_{\mbox{\rm AX}_0} (\phi\land\psi)\rightarrow \psi$
2. $\vdash_{\mbox{\rm AX}_0} (\phi\land\psi)\rightarrow \phi$
3. $\vdash_{\mbox{\rm AX}_0} \phi \rightarrow (\psi\rightarrow \phi\land\psi)$

16. Definición formal de la disyunción. En el sistema formal $\mbox{\rm Pbf}_H(X)$, escribimos $\phi\lor \psi$ como una abreviatura de la proposición $\neg\phi\rightarrow \psi$. Muestre que, cualesquiera que sean las proposiciones $\phi$, $\psi$, $\xi$ se tiene:

1. $\vdash_{\mbox{\rm AX}_0} \psi\rightarrow (\phi\lor\psi)$
2. $\vdash_{\mbox{\rm AX}_0} \phi\rightarrow (\phi\lor\psi)$
3. $\vdash_{\mbox{\rm AX}_0} (\phi\rightarrow \xi) \rightarrow ((\psi\rightarrow \xi) \rightarrow (\phi\lor\psi\rightarrow \xi)$

17. Muestre que si $\{\phi_1,\ldots,\phi_k,\psi\}\vdash_{\mbox{\rm AX}_0} \xi$ y también $\{\phi_1,\ldots,\phi_k,\psi\}\vdash_{\mbox{\rm AX}_0} \neg\xi$ entonces necesariamente $\{\phi_1,\ldots,\phi_k\}\vdash_{\mbox{\rm AX}_0} \neg\psi$.

18. Muestre que para cualesquiera tres proposiciones $\phi$, $\psi$ y $\xi$:

$$\{\psi,\phi\rightarrow (\psi\rightarrow \xi)\}\vdash_{\mbox{\rm AX}_0} \phi\rightarrow \xi.$$

19. Recordamos que si $\Phi$ es un conjunto de proposiciones, entonces su teoría es $\mbox{\it Teo}(\Phi)=\{\phi\vert\Phi\vdash_{\mbox{\rm AX}_0} \phi\}$. Muestre que $\mbox{\it Teo}(\mbox{\it Teo}(\Phi))= \mbox{\it Teo}(\Phi)$, cualquiera que sea $\Phi$.

20. Un conjunto de proposiciones $\Phi$ es inconsistente si existe una proposición $\phi$ tal que $\phi,\neg\phi\in\mbox{\it Teo}(\Phi)$. Muestre que $\Phi$ es inconsistente si y sólo si $\mbox{\it Teo}(\Phi)$ consta de todas las proposiciones ben formadas.
Posterior: Coherencia y completitud Arriba: Cálculo proposicional Anterior: Deducción natural