Pruebas por Inducción: Reglas Generalizadas de De Morgan y Distribución
RESUMEN
En esta clase se aborda el tema de las pruebas por inducción en matemáticas y lógica proposicional. Se explican los dos tipos de pruebas existentes: las pruebas internas o deductivas que se basan en las reglas de la lógica, y las pruebas externas o metamatemáticas que son necesarias para probar afirmaciones que se refieren a la lógica en sí misma. Se introduce la Inducción Matemática como un método de demostración que permite demostrar que ciertas afirmaciones valen para todos los números naturales. Se presenta un ejemplo con la demostración correspondiente y se explican las formas generalizadas de las leyes de De Morgan y de las leyes distributivas en lógica proposicional, junto con sus respectivas demostraciones por inducción. Esta clase es de gran importancia para entender los fundamentos de la matemática y la lógica, y para aplicarlos en diferentes áreas del conocimiento.
OBJETIVOS DE APRENDIZAJE:
Al finalizar esta clase, el estudiante será capaz de:
- Reconocer los dos tipos de pruebas que se deben distinguir: pruebas internas o deductivas y pruebas externas o metamatemáticas.
- Aplicar inducción matemática para hacer demostraciones sobre los números naturales y en la lógica proposicional
- Utilizar las notaciones de conjuntorias y disyuntorias para escribir expresiones de la lógica proposicional.
- Comprender la forma generalizada de las leyes de DeMorgan y de Distribución de la Lógica Proposicional
- Comprender el concepto de hipótesis de inducción y su papel en la demostración por inducción.
ÍNDICE
PRUEBAS INTERNAS Y EXTERNAS
PRUEBAS POR INDUCCIÓN MATEMÁTICA
PRUEBAS POR INDUCCIÓN EN LÓGICA PROPOSICIONAL
FORMA GENERALIZADA DE LAS LEYES DE DE MORGAN
FORMA GENERALIZADA DE LAS LEYES DISTRIBUTIVAS
Pruebas internas y externas
Existen dos tipos de pruebas que deben ser distinguidas. Hasta ahora hemos visto muchos ejemplos de pruebas formales. Este tipo de pruebas emergen desde las reglas de la lógica. Tales pruebas se dicen que tienen lugar «dentro de la lógica», y por lo tanto nos referimos a ellas también por el nombre de «pruebas internas» o deductivas. Este tipo de pruebas formales tienen un enfoque limitado, porque sólo sirven para probar afirmaciones que pueden ser escritas en el lenguaje de la lógica. Sin embargo, podríamos querer probar algunas cosas sobre la lógica misma. Podríamos querer probar que todas las afirmaciones de la lógica proposicional cumplen con cierta propiedad. Tales afirmaciones que se refieren a la lógica en sí misma no pueden ni ser establecidas ni probadas dentro de la lógica. Para probar tales afirmaciones utilizamos una prueba externa Las pruebas externas algunas veces son llamadas «metamatemáticas» y ya nos hemos encontrado con este tipo de cosas, como cuando vimos el (meta)teorema de deducción. Es aquí donde contextualizamos las pruebas inductivas.
Pruebas por Inducción Matemática
La Inducción Matemática es un método de demostración que nos permite demostrar que algunas cosas valen para todos los números naturales.
EJEMPLO:
Es posible probar todo número de la forma 11^n - 4^n, donde n es cualquier número natural, siempre es divisible por 7.
DEMOSTRACIÓN: Si observamos lo que ocurre con n=1 veremos que:
11^1 - 4^1 = 7
que obviamente, es divisible por 7.
Ahora supongamos que 11^n - 4^n es divisible para un n=k. A partir de esto probaremos que en consecuencia tal expresión también se cumplirá para n=k+1. Esto lo podemos realizar de la siguiente forma:
Por lo tanto, si 11^k - 4^k es divisible por 7, en consecuencia lo será 11 ( 11^{k} - 4^{k} ) + 7\cdot 4^{k}, que es lo mismo que decir que 11^{k+1} - 4^{k+1} es divisible por 7. De aquí tenemos que si 11^k - 4^k es divisible para k=1, entonces lo será para k=2, k=3, k=4,\cdots y asi sucesivamente, y por tanto, divisible para cualquier n\in\mathbb{N}. Cuando esto ocurre decimos que la inducción es completa. ■
Pruebas por Inducción en Lógica Proposicional
Para las pruebas por inducción que realizaremos a continuación, sera primero necesario introducir el siguiente convenio de notación
NOTACIÓN: Sean F_1,\cdots, F_n un conjunto finito de expresiones cualesquiera de la lógica proposicional. Se introducen las conjuntorias y disyuntorias de estas expresiones a través de:
\displaystyle \bigwedge_{i=1}^n F_i := F_1\wedge \cdots \wedge F_n
\displaystyle \bigvee_{i=1}^n F_i := F_1\vee \cdots \vee F_n
Con esto podremos tratar ahora con las siguientes dos formas generalizadas.
Forma Generalizada de las Leyes de De Morgan
Dado un conjunto finito de expresiones de la lógica proposicional F_1,\cdots, F_n, se cumplirán siempre las siguientes dos propiedades:
\displaystyle\neg\left(\bigwedge_{i=1}^n F_i \right) \equiv \left( \bigvee_{i=1}^n \neg F_i \right)
\displaystyle\neg\left(\bigvee_{i=1}^n F_i \right) \equiv \left( \bigwedge_{i=1}^n \neg F_i \right)
DEMOSTRACIÓN: Primero probaremos por inducción sobre n que \neg\left(\bigwedge_{i=1}^n F_i \right) \equiv \left( \bigvee_{i=1}^n \neg F_i \right)
Primero debemos revisar lo que ocurre con el caso inicial n=1. En este caso es claro que \neg F_1 \equiv \neg\left(\bigwedge_{i=1}^1F_i\right)\equiv \left(\bigvee_{i=1}^n \neg F_i \right) \equiv\neg F_1
Supongamos ahora que la propiedad funciona para algún n=k; es decir, que dada una colección finita de expresiones F_1, F_2, \cdots, F_k se cumple que:
\displaystyle \neg\left(\bigwedge_{i=1}^k F_i\right) \equiv \left(\bigvee_{i=1}^k \neg F_i\right)
Entonces probaremos que en consecuencia vale
\displaystyle \neg\left(\bigwedge_{i=1}^{k+1} F_i\right) \equiv \left(\bigvee_{i=1}^{k+1} \neg F_i\right)
Utilizando la definición de la conjuntoria tenemos que:
\displaystyle \neg\left(\bigwedge_{i=1}^{k+1} F_i\right) := \neg\left[\left(\bigwedge_{i=1}^{k} F_i\right) \wedge F_{k+1}\right]
Sobre esta expresión podemos aplicar las leyes de De Morgan (la usual sobre dos términos) para obtener:
\displaystyle \neg\left(\bigwedge_{i=1}^{k+1} F_i\right)\equiv \left[\neg\left(\bigwedge_{i=1}^{k} F_i\right) \vee \neg F_{k+1}\right]
Ahora, si aplicamos la hipótesis de inducción, obtendremos:
\displaystyle \neg\left(\bigwedge_{i=1}^{k+1} F_i\right)\equiv \left[ \left(\bigvee_{i=1}^k \neg F_i\right) \vee \neg F_{k+1}\right] := \left(\bigvee_{i=1}^{k+1}\neg F_i \right)
Y por este motivo la inducción es completa y la propiedad vale para todo n en general. La segunda relación se puede obtener de un modo completamente análogo, por lo que lo dejaré como ejercicio para el lector muajaja!
Forma Generalizada de las Leyes Distributivas
De forma similar a las leyes de De Morgan, las leyes de distribución se pueden generalizar de la siguiente manera. Sean \{F_1, \cdots, F_n\} y \{G_1,\cdots, G_m\} dos conjuntos finitos de expresiones cualesquiera, entonces valen las siguientes equivalencias:
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^m G_j \right) \right] \equiv \left[\bigwedge_{i=1}^n\left(\bigwedge_{j=1}^m(F_i\vee G_j) \right) \right]
\displaystyle \left[ \left(\bigvee_{i=1}^n F_i \right) \wedge \left(\bigvee_{j=1}^m G_j \right) \right] \equiv \left[\bigvee_{i=1}^n\left(\bigvee_{j=1}^m(F_i\wedge G_j) \right) \right]
DEMOSTRACIÓN: Para construir esta demostración debemos hacer una inducción doble, sobre n y m. A continuación haré la inducción primero sobre n y luego sobre m para la expresión \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^m G_j \right) \right] \equiv \left[\bigwedge_{i=1}^n\left(\bigwedge_{j=1}^m(F_i\vee G_j) \right) \right]
Si tomamos m=1, entonces esta expresión queda escrita como
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^1 G_j \right) \right] \equiv \left[\bigwedge_{i=1}^n\left(\bigwedge_{j=1}^1(F_i\vee G_j) \right) \right].
Que es lo mismo que decir:
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee G_1 \right] \equiv \left[\bigwedge_{i=1}^n\left( F_i\vee G_1 \right) \right].
Ahora demostraremos que ésta expresión por inducción sobre n.
Si tomamos n=1, entonces la expresión se reduce a
F_1 \vee G_1 \equiv F_1 \vee G_1.
Cosa que ya sabemos, es cierta. Ahora supongamos que se cumple para un n=k cualquiera; es decir, la hipótesis de inducción será:
\displaystyle \left[ \left(\bigwedge_{i=1}^k F_i \right) \vee G_1 \right] \equiv \left[\bigwedge_{i=1}^k\left( F_i\vee G_1 \right) \right].
Entonces, a partir de ésto mostraremos que en consecuencia se cumple para un n=k+1.
Por la definición de conjuntoria se tiene que:
\displaystyle \left[\left(\bigwedge_{i=1}^{k+1}F_i \right) \vee G_1 \right] := \left[\left(\left(\bigwedge_{i=1}^{k}F_i \right)\wedge F_{k+1} \right) \vee G_1 \right]
Ahora, usando la \vee-distribución, tendremos que:
\displaystyle \left[\left(\bigwedge_{i=1}^{k+1}F_i \right) \vee G_1 \right] \equiv \left[\left(\left(\bigwedge_{i=1}^{k}F_i \right)\vee G_{1} \right) \wedge \left(F_{k+1} \vee G_1 \right) \right]
Y justo en este punto podemos usar la hipótesis de inducción para obtener:
\displaystyle \left[\left(\bigwedge_{i=1}^{k+1}F_i \right) \vee G_1 \right] \equiv \left[\left(\bigwedge_{i=1}^k\left( F_i\vee G_1 \right) \right) \wedge \left(F_{k+1} \vee G_1 \right) \right] := \left[\bigwedge_{i=1}^{k+1}(F_{i}\vee G_1 \right]
Por lo tanto, hemos probado por inducción que para todo n\in\mathbb{N} que se cumple
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right)\vee G_1\right] \equiv \left[\bigwedge_{i=1}^n(F_i\vee G_1)\right]
Completando la inducción sobre n hemos corroborado que funciona el caso inicial para m=1, ahora sólo nos falta completar la inducción sobre m. Para hacer esto último establecemos la hipótesis de inducción para un m=l, es decir, que funciona
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^l G_j \right) \right] \equiv \left[\bigwedge_{i=1}^n\left(\bigwedge_{j=1}^l(F_i\vee G_j) \right) \right]
y a partir de esto probaremos que tambien funciona para m=l+1.
Partiendo, como siempre, desde la definición de conjuntoria tenemos que
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{l+1} G_j \right) \right] := \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\left(\bigwedge_{j=1}^{l} G_j \right) \wedge G_{l+1}\right) \right]
Ahora, usando la \vee-distribución se tendrá
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{l+1} G_j \right) \right] \equiv \left[ \left( \left(\bigwedge_{i=1}^n F_i \right) \vee \left( \bigwedge_{j=1}^l G_j \right) \right) \wedge \left( \left( \bigwedge_{i=1}^n F_i \right)\vee G_{l+1} \right) \right]
En consecuencia, utilizando la hipótesis de inducción podrás escribir
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{l+1} G_j \right) \right] \equiv \left[ \bigwedge_{i=1}^n\left(\bigwedge_{j=1}^l(F_i\vee G_j) \right) \wedge \left( \left( \bigwedge_{i=1}^n F_i \right)\vee G_{l+1} \right) \right]
Y si ahora tomamos el resultado de la inducción sobre n
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{l+1} G_j \right) \right] \equiv \left[ \bigwedge_{i=1}^n\left(\bigwedge_{j=1}^l(F_i\vee G_j) \right) \wedge \left( \bigwedge_{i=1}^n (F_i \vee G_{l+1} )\right) \right]
Que, finalmente, por la definición de conjuntoria nos queda
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{l+1} G_j \right) \right] \equiv \left[ \bigwedge_{i=1}^n\left(\bigwedge_{j=1}^{l+1}(F_i\vee G_j) \right) \right]
Y por lo tanto, la inducción sobre m es completa y la expresión
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{m} G_j \right) \right] \equiv \left[ \bigwedge_{i=1}^n\left(\bigwedge_{j=1}^{m}(F_i\vee G_j) \right) \right]
es válida para todo n,m\in\mathbb{N}.
Este recorrido por las pruebas por inducción ha demostrado cómo se pueden aplicar técnicas rigurosas de demostración matemática no solo en el ámbito de los números naturales, sino también en la lógica proposicional. A través de la inducción, hemos logrado establecer la validez de las formas generalizadas de las leyes de De Morgan y las leyes distributivas, reforzando así la comprensión de los fundamentos lógicos que subyacen en diversas áreas del conocimiento matemático. Este enfoque no solo es esencial para el desarrollo de habilidades de razonamiento abstracto, sino que también sirve como una herramienta poderosa para abordar problemas complejos en matemáticas y más allá.