Posterior: Ejercicios Arriba: Sintaxis Anterior: Reglas convencionales de buena

Deducción natural

Los procedimientos de deducción natural se definen en el lenguaje $\mbox{\rm Pbf}(X)$.

Definición 2.4 (Axiomas)   El conjunto de AXIOMAS PROPOSICIONALES, sobre el conjunto de variables proposicionales $X$, es

$$\mbox{\rm Ax}(X)= \mbox{\rm Ax}_1(X)\cup \mbox{\rm Ax}_2(X)\cup \mbox{\rm Ax}_3(X) \subset \mbox{\rm Pbf}(X)$$ (5)

donde

$$\mbox{\rm Ax}_1(X) = \{ p\rightarrow(q\rightarrow p) \vert p,q\in\mbox{\rm Pbf}(X)\}$$ (6)

$$\mbox{\rm Ax}_2(X) = \{ \left(p\rightarrow(q\rightarrow r)\right)\rightarrow \left((p\rightarrow q)\rightarrow(p\rightarrow r)\right) \vert p,q,r\in\mbox{\rm Pbf}(X)\}$$ (7)

$$\mbox{\rm Ax}_3(X) = \{ \left(\neg p\rightarrow q\right) \rightarrow \left(\left(\neg ... ...tarrow \neg q\right)\rightarrow p\right) \vert p,q\in\mbox{\rm Pbf}(X)\}%%\\$$ (8)

La regla MODUS PONENS (MP) se sintetiza como

$$\begin{array}{cc} \begin{array}{l} p\rightarrow q \\ p \end{array} \\ \hline q \end{array}$$ (9)

y significa que toda vez que en una línea de razonamiento aparecen $p \rightarrow q$ y $p$ entonces se puede añadir $q$.

Definición 2.5 (Pruebas)   Sea $H\subset \mbox{\rm Pbf}(X)$ una colección de proposiciones bien formadas, llamadas hipótesis. Una PRUEBA es una sucesión finita $D=[p_1,\ldots,p_n]$ de proposiciones bien formadas tal que $\forall i\leq n$:

• $p_i\in\mbox{\rm Ax}(X)$, o
• $p_i\in H$, o
• $\exists j,k<i:\ p_k=(p_j\rightarrow p_i)$

En este caso la prueba $D$ se dice ser una prueba de $p_n$ a partir de $H$.

Toda prueba $D$ es entonces una sucesión finita de proposiciones bien formadas, es decir, $D\in\mbox{\it Pbf}(X)^*$.

Definición 2.6 (Demostrabilidad)   Se dice que $p\in \mbox{\rm Pbf}(X)$ es DEMOSTRABLE a partir de $H\subset \mbox{\rm Pbf}(X)$, y se escribe $H\vdash p$, si existe una prueba $D$ de $p$ a partir de $H$. El conjunto $\mbox{\it Ded}(H)=\{p\in \mbox{\rm Pbf}(X)\vert H\vdash p\}$ de DEDUCCIONES LÓGICAS de $H$ es llamado también la TEOR´iA de $H$. Una proposición $p$ es un TEOREMA si $p\in \mbox{\it Ded}(\emptyset)$, es decir, si $p$ se deduce de los axiomas.

Ya que las pruebas son de longitud finita, necesariamente para cualquier $H\subset \mbox{\rm Pbf}(X)$ se tiene $\mbox{\it Ded}(H)= \mbox{\it Ded}(\mbox{\it Ded}(H))$. Ilustremos la noción de deducción lógica con algunos ejemplos.

Proposición 2.1   Para cualesquiera $p,q,r\in \mbox{\rm Pbf}(X)$ se cumplen las siguientes relaciones:

$$\begin{array}{rll} A) & \vdash p\rightarrow p & \\ B) & \{... ...p & \mbox{\rm Principio de doble negaci\'on} %%\\ \end{array}$$

Demostración
A) Veamos que $\vdash p\rightarrow p$. Una prueba es la siguiente:

1.

$(p\rightarrow((p\rightarrow p)\rightarrow p))\rightarrow ((p\rightarrow(p\rightarrow p))\rightarrow (p\rightarrow p)))$ ( $\mbox{\rm Ax}_2$)

2.

$p\rightarrow((p\rightarrow p)\rightarrow p)$ ( $\mbox{\rm Ax}_1$)

3.

$(p\rightarrow(p\rightarrow p))\rightarrow (p\rightarrow p))$ ( $\mbox{\rm MP}\ 1,2$)

4.

$p\rightarrow(p\rightarrow p)$ ( $\mbox{\rm Ax}_1$)

5.

$p\rightarrow p$ ( $\mbox{\rm MP}\ 3,2$)

B) Veamos que $\{p,\neg p\} \vdash q$. Una prueba es la siguiente:

1.

$\left(\neg q\rightarrow p\right) \rightarrow \left(\left(\neg q\rightarrow \neg p\right)\rightarrow q\right)$ ( $\mbox{\rm Ax}_3$)

2.

$p\rightarrow(\neg q\rightarrow p)$ ( $\mbox{\rm Ax}_1$)

3.

$p$ ( $\mbox{\rm Hip}$)

4.

$\neg q\rightarrow p$ ( $\mbox{\rm MP}\ 2,3$)

5.

$\left(\neg q\rightarrow \neg p\right)\rightarrow q$ ( $\mbox{\rm MP}\ 1,4$)

6.

$\neg p\rightarrow(\neg q\rightarrow \neg p)$ ( $\mbox{\rm Ax}_1$)

7.

$\neg p$ ( $\mbox{\rm Hip}$)

8.

$\neg q\rightarrow \neg p$ ( $\mbox{\rm MP}\ 6,7$)

9.

$q$ ( $\mbox{\rm MP}\ 5,8$)

C) Veamos que $\{p\rightarrow q, q\rightarrow r\} \vdash p\rightarrow r$. Una prueba es la siguiente:

1.

$(p\rightarrow(q\rightarrow r))\rightarrow ((p\rightarrow q)\rightarrow (p\rightarrow r))$ ( $\mbox{\rm Ax}_2$)

2.

$(q\rightarrow r)\rightarrow(p\rightarrow (q\rightarrow r))$ ( $\mbox{\rm Ax}_1$)

3.

$q\rightarrow r$ ( $\mbox{\rm Hip}$)

4.

$p\rightarrow (q\rightarrow r)$ ( $\mbox{\rm MP}\ 2,3$)

5.

$(p\rightarrow q)\rightarrow (p\rightarrow r)$ ( $\mbox{\rm MP}\ 1,4$)

6.

$p \rightarrow q$ ( $\mbox{\rm Hip}$)

7.

$p\rightarrow r$ ( $\mbox{\rm MP}\ 5,6$)

D) Veamos que $\{\neg \neg p\} \vdash p$. Para esto hemos de calcar una prueba de la proposición $\neg p\rightarrow \neg p$ siguiendo el esquema en A) para continuar luego como sigue:

$\vdots$

$\vdots$ ($\vdots$)

5.

$\neg p\rightarrow \neg p$ ( $\mbox{\rm Teo}$)

6.

$\left(\neg p\rightarrow \neg p\right) \rightarrow \left(\left(\neg p\rightarrow \neg \neg p\right)\rightarrow p\right)$ ( $\mbox{\rm Ax}_3$)

7.

$\left(\neg p\rightarrow \neg \neg p\right)\rightarrow p$ ( $\mbox{\rm MP}\ 6,5$)

8.

$\neg \neg p\rightarrow(\neg p\rightarrow \neg \neg p)$ ( $\mbox{\rm Ax}_1$)

9.

$\neg \neg p$ ( $\mbox{\rm Hip}$)

10.

$\neg p\rightarrow \neg \neg p$ ( $\mbox{\rm MP}\ 8,9$)

11.

$p$ ( $\mbox{\rm MP}\ 7,10$)

$\quad\Box$

Proposición 2.2   Para cualesquiera $p,q\in \mbox{\rm Pbf}(X)$ se cumple la siguiente relación: $\{\neg q\rightarrow \neg p,p\}\vdash q$ MODUS TOLLENS

Demostración
Una prueba es la siguiente:

1.

$(\neg q\rightarrow \neg p)\rightarrow ((\neg q\rightarrow p)\rightarrow q)$ ( $\mbox{\rm Ax}_3$)

2.

$\neg q\rightarrow \neg p$ ( $\mbox{\rm Hip}$)

3.

$(\neg q\rightarrow p)\rightarrow q$ ( $\mbox{\rm MP}\ 1,2$)

4.

$p\rightarrow(\neg q\rightarrow p)$ ( $\mbox{\rm Ax}_1$)

5.

$p$ ( $\mbox{\rm Hip}$)

6.

$\neg q\rightarrow p$ ( $\mbox{\rm MP}\ 4,5$)

7.

$q$ ( $\mbox{\rm MP}\ 3,6$)

$\quad\Box$ Toda prueba puede ser vista como un árbol, que de hecho ha de ser binario en el cálculo proposicional, donde la raíz tiene como etiqueta el índice de la tesis en la prueba y las hojas tienen como etiquetas índices de axiomas o de hipótesis. Definiremos a los árboles de pruebas de manera inductiva.

Definición 2.7   Sea $D\in\mbox{\it Pbf}(X)^*$ una prueba de longitud $n$. Y sea $p_i$ una proposición en $D$, con $i\leq n$. La SUBPRUEBA INDICADA de $p_i$ en $D$ se define inductivamente en términos de cómo se haya obtenido $p_i$: Caso base. Si $p_i$ fuese un axioma o una hipótesis entonces $D_i=[(i:p_i)]$. Caso inductivo. Si $p_i$ se obtiene de dos proposiciones previas por modus ponens, es decir, si existen $k,j<i$ tales que $p_k=(p_j\rightarrow p_i)$, entonces sean $D_k$ y $D_j$ las correspondientes subpruebas indicadas de $p_k$ y $p_j$. Con ellas, se hace $D_i=D_k*D_j*[(i:p_i)]$, donde $*$ denota la operación de concatenación.

En otras palabras, la demostración indicada de una proposición $p$ en una demostración dada $D$, consiste en extraer las proposiciones involucradas en demostrar $p$, enumerándolas con los mismos números asignados por $D$.

Definición 2.8   Sea $D\in\mbox{\it Pbf}(X)^*$ una prueba de longitud $n$. Definimos inductivamente en términos de $n$ a $\mbox{\it\'Arbol}(D)$: Caso base. Si $n=1$ entonces $D=[p_1]$ y $p_1$ es un axioma o es una hipótesis. En tal caso $\mbox{\it\'Arbol}(D)$ consta de un único nodo raíz con etiqueta $(1:I)$ donde $I$ es el tipo de axioma, si $p_1$ fuese un axioma, o bien $(1:\mbox{\rm Hip})$, si $p_1$ fuese una hipótesis. Caso inductivo. Si $n>1$ entonces $p_n$ se obtiene por modus ponens de dos proposiciones previas $p_k,p_j$: $p_k=(p_j\rightarrow p_i)$. En tal caso, sean $D_k$ y $D_j$ las correspondientes subpruebas indicadas de $p_k$ y $p_j$. $\mbox{\it\'Arbol}(D)$ será entonces el árbol cuya raíz tiene etiqueta $(n:\mbox{\rm Hip})$, y cuyos subárboles izquierdo y derecho son $\mbox{\it\'Arbol}(D_k)$ y $\mbox{\it\'Arbol}(D_j)$, respectivamente.

Ejemplo 2.3   Consideremos las fórmulas de la proposición  2.2.1. En la figura 2.3 presentamos el árbol del teorema en $A$). En la figura 2.4 presentamos el árbol de la deducción en $B$).

Observamos en estos caso que la ``tesis'' corresponde a la raíz y los axiomas o las hipótesis a las hojas. Los árboles son binarios porque la regla de modus ponens es la única que se aplica y ésta involucra a exactamente dos proposiciones.

Figure 2.3: Árbol de demostración del teorema $\vdash p\rightarrow p$.

Figure 2.4: Árbol de demostración de la deducción $\{p,\neg p\} \vdash q$.

De los ejemplos vistos, queda la impresión de que el proceso de deducción mostrado, llamado por algunos autores DEDUCCIÓN NATURAL, es, precisamente ``poco natural'', en el sentido de que el hallazgo de una prueba puede ser difícil. El siguiente teorema permite transformar pruebas en otras pruebas, de manera algorítmica. Este es un importante teorema en la lógica matemática.

Teorema 2.1 (de la deducción (Hildebrand, 1930))   Sea $H\subset \mbox{\rm Pbf}(X)$ un conjunto de proposiciones bien formadas y sean $p,q\in \mbox{\rm Pbf}(X)$ otras dos proposiciones. Entonces:

$$H\vdash (p\rightarrow q)\ \ \ \Leftrightarrow\ \ \ H\cup\{p\} \vdash q$$ (10)

De hecho, la demostración del teorema de la deducción permite transformar algorítmicamente una prueba de $p \rightarrow q$ a partir de $H$ en una prueba de $q$ a partir de $H\cup\{p\}$, y viceversa. Demostración
$\Rightarrow$) Supongamos que $P$ es una sucesión de $n$ proposiciones que forma una prueba de $p \rightarrow q$ a partir de $H$. Entonces, al concatenarle las siguientes dos proposiciones obtenemos una prueba de $q$ a partir de $H\cup\{p\}$:

$n+1$.

$p$ ( $\mbox{\rm Hip}$)

$n+2$.

$q$ ( $\mbox{\rm MP}\ n,n+1$)

$\Leftarrow$) Supongamos que $P$ es una sucesión de $n$ proposiciones que forma una prueba de $q$ a partir de $H\cup\{p\}$. Razonando por inducción en $n$ construiremos una prueba de $p \rightarrow q$ a partir de $H$.

Caso base. Si $n=1$ entonces $q$ es bien un axioma o una hipótesis, es decir, pertenece a $H\cup\{p\}$. Si $q=p$ entonces $(p\rightarrow q)= (p\rightarrow p)$ es un teorema (véase el ejemplo A) en la proposición 2.2.1 anterior). En otro caso, una prueba de $p \rightarrow q$ a partir de $H$ es la siguiente:

1.

$q\rightarrow (p\rightarrow q)$ ( $\mbox{\rm Ax}_1$)

2.

$q$ ( $\mbox{\rm Hip. o Ax.}$)

3.

$p \rightarrow q$ ( $\mbox{\rm MP}\ 1,2$)

Caso inductivo. Supongamos $n>1$ y, de acuerdo con el Principio de Inducción, que la equivalencia (10) vale cuando las pruebas requieren menos de $n$ pasos. Comp $P$ es una prueba de $q$ a partir de $H\cup\{p\}$ con exactamente $n$ pasos, la última justificación en esa prueba debe ser Modus Ponens. Así pues para algunos pasos $n_1,n_2<n$ las correspondientes proposiciones han de ser de la forma $p_{n_1}=(q_1\rightarrow q)$ y $p_{n_2}=q_1$. Por la hipótesis de inducción se tiene que existe una prueba $Q_1$ de que $H\vdash (p\rightarrow p_{n_1})$ y una prueba $Q_2$ de que $H\vdash (p\rightarrow p_{n_2})$, digamos que de $m_1$ y $m_2$ pasos. La concatenación de $Q_1$ y $Q_2$ con los siguientes pasos da una prueba de $p \rightarrow q$ a partir de $H$:

$m_1+m_2+1$.

$(p\rightarrow (q_1\rightarrow q))\rightarrow ((p\rightarrow q_1)\rightarrow (p\rightarrow q))$ ( $\mbox{\rm Ax}_2$)

$m_1+m_2+2$.

$(p\rightarrow q_1)\rightarrow (p\rightarrow q)$ ( $\mbox{\rm MP}\ \scriptstyle{m_1+m_2+1,m_1}$)

$m_1+m_2+3$.

$p \rightarrow q$ ( $\mbox{\rm MP}\ \scriptstyle{m_1+m_2+2,m_1+m_2}$)

$\quad\Box$ Siguiendo esta demostración, el lector no tendrá problema alguno para precisar un algoritmo recursivo que tome como entrada la prueba $P$ de una proposición $q$ a partir de $H\cup\{p\}$, y produzca como salida una prueba $Q$ de $p \rightarrow q$ a partir de $H$. Aplicando el Teorema de la Deducción a las deducciones hechas en la proposición 2.2.1, obtenemos inmediatamente:

Proposición 2.3   Para cualesquiera $p,q,r\in \mbox{\rm Pbf}(X)$ las siguientes proposiciones son teoremas:

$$\begin{array}{rll} B') & p\rightarrow (\neg p\rightarrow q) ... ...p & \mbox{\rm Principio de doble negaci\'on} %%\\ \end{array}$$

Demostración
Sólo demostraremos el enunciado $E')$ pues los anteriores se siguen inmediatamente. De $D')$ se tiene que $\neg \neg \neg p \rightarrow \neg p$ es un teorema. Utilizando este hecho y el Teorema de Deducción, basta probar $p\vdash \neg \neg p$. Procedamos como sigue:

1.

$\left(\neg \neg \neg p \rightarrow p\right) \rightarrow \left(\left(\neg \neg \neg p \rightarrow \neg p\right) \rightarrow \neg \neg p \right)$ ( $\mbox{\rm Ax}_3$)

2.

$p \rightarrow \left(\neg \neg \neg p \rightarrow p\right)$ ( $\mbox{\rm Ax}_1$)

3.

$p$ ( $\mbox{\rm Hip.}$)

4.

$\neg \neg \neg p \rightarrow p$ ( $\mbox{\rm MP}\ 2,3$)

5.

$\left(\neg \neg \neg p \rightarrow \neg p\right) \rightarrow \neg \neg p$ ( $\mbox{\rm MP}\ 1,4$)

6.

$\neg \neg \neg p \rightarrow \neg p$ ( $\mbox{\rm Teorema}$)

7.

$\neg \neg p$ ( $\mbox{\rm MP}\ 5,6$)

$\quad\Box$

Proposición 2.4   Para cualesquiera $p,q\in \mbox{\rm Pbf}(X)$ se cumple la siguiente relación: $\vdash (p\rightarrow q)\rightarrow (\neg q\rightarrow \neg p)$ PRINCIPIO DE CONTRAPOSICIÓN

Demostración
En efecto, por Modus Tollens, $\{p\rightarrow q,\neg q\}\vdash \neg p$. Luego, por el Teorema de Deducción, $\vdash (p\rightarrow q)\rightarrow (\neg q\rightarrow \neg p)$. $\quad\Box$ Para concluir esta sección presentaremos la noción de consistencia formal.

Definición 2.9   Un conjunto $H\subset \mbox{\rm Pbf}(X)$ se dice ser FORMALMENTE INCONSISTENTE si existe una proposición $p\in \mbox{\rm Pbf}(X)$ tal que $H\vdash p$ y $H\vdash \neg p$. El conjunto $H$ es FORMALMENTE CONSISTENTE si no es inconsistente, vale decir, si vale que

$$\mbox{\it para cualquier }p\in \mbox{\rm Pbf}(X):\ H\vdash p\ \Rightarrow\ H\not\vdash \neg p$$ (11)

Naturalmente se tiene la siguiente

Proposición 2.5   Sea $H\subset \mbox{\rm Pbf}(X)$. Entonces

$$H\mbox{\it es formalmente inconsistente }\ \Leftrightarrow\ \mbox{\it Ded}(H) = \mbox{\rm Pbf}(X)$$ (12)

Demostración
$\Rightarrow)$ Supongamos $H$ formalmente inconsistente. Sea $p\in \mbox{\rm Pbf}(X)$ tal que $H\vdash p$ y $H\vdash \neg p$. Sea ahora $q\in \mbox{\rm Pbf}(X)$ una proposición cualquiera. Veamos que $H\vdash q$. En efecto, una prueba es la siguiente:

1.

$\left(\neg q\rightarrow p\right) \rightarrow \left(\left(\neg q\rightarrow \neg p\right)\rightarrow q\right)$ ( $\mbox{\rm Ax}_3$)

2.

$p \rightarrow \left(\neg q \rightarrow p\right)$ ( $\mbox{\rm Ax}_1$)

3.

$p$ ( $\mbox{\rm Hip.}$)

4.

$\neg q\rightarrow p$ ( $\mbox{\rm MP}\ 2,3$)

5.

$\left(\neg q\rightarrow \neg p\right)\rightarrow q$ ( $\mbox{\rm MP}\ 1,4$)

6.

$\neg p \rightarrow \left(\neg q \rightarrow \neg p\right)$ ( $\mbox{\rm Ax}_1$)

7.

$\neg p$ ( $\mbox{\rm Hip.}$)

8.

$\neg q\rightarrow \neg p$ ( $\mbox{\rm MP}\ 6,7$)

9.

$q$ ( $\mbox{\rm MP}\ 5,8$)

$\Leftarrow)$ Supongamos que $\mbox{\it Ded}(H) = \mbox{\rm Pbf}(X)$. Entonces para cualquier $p\in \mbox{\rm Pbf}(X)$ se tiene que $H\vdash p$ y además $H\vdash \neg p$, es decir, $H$ es formalmente inconsistente. $\quad\Box$ Un criterio para decidir cuándo un conjunto de proposiciones de inconsistente lo da el siguiente

Teorema 2.2 (de Compacidad)   Un conjunto (acaso infinito) de proposiciones $H\subset \mbox{\rm Pbf}(X)$ es consistente si y sólo si cualquier subconjunto finito de él lo es. En otras palabras, $H$ es inconsistente si y sólo si posee un subconjunto finito que en sí es inconsistente.

La demostración es directa y se debe únicamente a que las pruebas involucran sólo un número finito de proposiciones. $\quad\Box$
Posterior: Ejercicios Arriba: Sintaxis Anterior: Reglas convencionales de buena