Prueba algebraica de los Teoremas de De Morgan

Question

¿Podría alguien darme una prueba algebraica de los Teoremas de De Morgan?

Ya conozco la prueba gráfica con la tabla de verdad, pero necesito entender la forma algebraica.

---

EDITAR

Intento explicar mejor. Imagina tener los dos teoremas:

NO(a * b) = NO(a) + NO(b)
NO(a + b) = NO(a) * NO(b)

¿Qué respondes a alguien que te dice: "Muéstrame por qué estos dos teoremas se verifican sin utilizar las tablas de verdad"?

Answer 1

A continuación, por ejemplo Wikipedia, vamos a definir un álgebra booleana como un conjunto $A$, junto con dos operaciones binarias $\land$ y $\lor$, una operación unaria $'$, y dos operaciones nulas $0$ y $1$, que satisfacen los siguientes axiomas: $$\begin{align*} a\lor(b\lor c) &= (a\lor b)\lor c, & a\land(b\land c) &= (a\land b)\land c, &&\text{(asociatividad)}\\ a\lor b &= b\lor a, & a\land b &= b\land a, &&\text{(conmutatividad)}\\ a\lor(a\land b) &= a, & a\land (a\lor b) &= a, &&\text{(absorción)}\\ a\lor(b\land c) &= (a\lor b)\land (a\lor c), & a\land(b\lor c) &= (a\land b)\lor (a\land c) &&\text{(distributividad)}\\ a\lor a' &= 1, & a\land a' &= 0. &&\text{(complementos)} \end{align*}$$

Quieres usar estos axiomas para demostrar que $(a\land b)' = a'\lor b'$ y $(a\lor b)' = a'\land b'$.

Lema 1. $a\land 1 = a$ y $a\lor 0 = a$ para todo $a$.

Prueba. $a \land 1 = a\land(a\lor a') = a$, por complementos y absorción; de manera similar, $a\lor 0 = a\lor(a\land a') = a$ por complementos y absorción. $\Box$

Lema 2. $a\land 0 = 0$ y $a\lor 1 = 1$ para todo $a$.

Prueba. $a\land 0 = a\land (a\land a') = (a\land a)\land a' = a\land a' = 0$. Y $a\lor 1 = a\lor(a\lor a') = (a\lor a)\lor a' = a\lor a' = 1$. $\Box$

Lema 3. Si $a\land b' = 0$ y $a\lor b'=1$, entonces $a=b$.

Prueba. $$\begin{align*} b &= b\land 1\\ &= b\land(a\lor b')\\ &= (b\land a)\lor (b\land b')\\ &= (b\land a)\lor 0\\ &= (b\land a)\lor (a\land b')\\ &= (a\land b)\lor(a\land b')\\ &= a\land (b\lor b')\\ &= a\land 1\\ &= a.\ \Box \end{align*}$$

Lema 4. Para todo $a$, $(a')' = a$.

Prueba. Por el Lema 3, basta con demostrar que $(a')'\land a' = 0$ y $(a')'\lor a' = 1$. Pero esto se sigue directamente por complementación. $\Box$

Teorema. $(a\land b)' = a'\lor b'$.

Por los Lemas 3 y 4, basta con mostrar que $(a\land b)\land (a'\lor b') = 0$ y $(a\land b)\lor (a'\lor b') = 1$; pues por el Lema 4, esto es lo mismo que probar $(a\land b)\land (a'\lor b')'' =0$ y $(a\land b)\lor (a'\lor b')'' = 1$; por el Lema 3, esto nos da $(a\land b) = (a'\lor b')'$, y aplicando de nuevo el Lema 4 obtenemos $(a\land b)' = (a'\lor b')'' = a'\lor b'$, que es lo que queríamos.

Tenemos: $$\begin{align*} (a\land b)\land(a'\lor b') &= \bigl((a\land b)\land a')\bigr) \lor \bigl((a\land b)\land b') &&\text{(por distributividad)}\\ &= \bigl( (a\land a')\land b\bigr) \lor \bigl( a\land (b\land b')\bigr) &&\text{(por asociatividad y conmutatividad)}\\ &= ( 0\land b) \lor (a\land 0)\\ &= 0 \lor 0\\ &= 0. \end{align*}$$ Y $$\begin{align*} (a\land b)\lor(a'\lor b') &= \bigl( (a\land b)\lor a'\bigr) \lor b'&&\text{(por asociatividad)}\\ &= \bigl( (a\lor a') \land (b\lor a')\bigr) \lor b'&&\text{(por distributividad)}\\ &= \bigl( 1\land (b\lor a')\bigr) \lor b'&&\text{(por complementos)}\\ &= (b\lor a')\lor b'&&\text{(por Lema 1)}\\ &= (b\lor b')\lor a'&&\text{(por conmutatividad y asociatividad)}\\ &= 1\lor a'&&\text{(por complementos)}\\ &= 1 &&\text{(por Lema 2)}. \end{align*}$$ Como $(a\land b)\land (a'\lor b') = 0$ y $(a\land b)\lor (a'\lor b') = 1$, se sigue la conclusión. $\Box$

Teorema. $(a\lor b)' = a'\land b'$.

Prueba. Dejado como ejercicio para el lector interesado. $\Box$

Answer 2

Dejemos que ~ represente la función de negación "NOT", y -> la implicación (material). Entonces, en un sistema de deducción natural (con una regla de eliminación de negación que va "de una suposición que es una negación que conduce a una contradicción, podemos inferir la fórmula bien formada (sub) que la negación niega) las pruebas podrían desarrollarse de la siguiente manera:

1  |    ~(a*b) suposición 
2  ||   ~(~a+~b) suposición
3  |||  ~a suposición
4  |||  (~a+~b) 3 + introducción
5  |||  ((~a+~b)*~(~a+~b)) 2, 4 * introducción
6  ||   a 3-5 eliminación de ~
7  |||  ~b suposición
8  |||  (~a+~b) 7 + introducción
9  |||  ((~a+~b)*~(~a+~b)) 2, 8 * introducción
10 ||   b 7-9 eliminación de ~
11 ||   (a*b) 6, 10 * introducción
12 ||   ((a*b)*~(a*b)) 1, 11 * introducción
13 |    (~a+~b) 2-12 eliminación de ~
14      (~(a*b)->(~a+~b)) 1-13 -> introducción
15 |    (~a+~b) suposición
16 ||   (a*b) suposición
17 ||   a 16 * eliminación
18 |||  ~a suposición
19 |||| b suposición
20 |||| (a*~a) 17, 18 * introducción
21 |||  ~b 19-20 ~ introducción
22 ||   (~a->~b) 18-21 -> introducción
23 |||  ~b suposición
24 ||   (~b->~b) 23-23 -> introducción
25 ||   ~b 15, 22, 24 + eliminación
26 ||   b 16 * eliminación
27 ||   (b*~b) 25, 26 * introducción
28 |   ~(a*b) 16-27 ~ introducción
29     ((~a+~b)->~(a*b)) 15-28 -> introducción
30     (~(a*b)=(~a+~b)) 14, 29 = introducción

1  |   ~(a+b) suposición
2  ||  a suposición
3  ||  (a+b) 2 + introducción
4  ||  ((a+b)*~(a+b)) 1, 3 * introducción
5  |   ~a 2-4 ~ introducción
6  ||  b suposición
7  ||  (a+b) 6 + introducción
8  ||  ((a+b)*~(a+b)) 7, 1 * introducción
9  |   ~b 6-8 ~ introducción
10 |   (~a*~b) 5, 9 * introducción
11     (~(a+b)->(~a*~b)) 1-10 -> introducción
12 |   (~a*~b) suposición
13 ||  (a+b) suposición
14 |||  a suposición
15 ||  (a->a) 14-14 -> introducción
16 |||  b suposición
17 |||| ~a suposición
18 |||| ~b 12 * eliminación
19 |||| (b*~b) 16, 18 * introducción
20 |||  a 17-19 ~ eliminación
21 ||  (b->a) 16-20 -> introducción
22 ||   a 13, 15, 21 + eliminación
23 ||   ~a 12 * eliminación
24 ||  (a*~a) 22, 23 * introducción
25 |   ~(a+b) 13-24 ~ introducción
26     ((~a*~b)->~(a+b)) 12-25 -> introducción
27     (~(a+b)=(~a*~b)) 11, 26 = introducción

Una técnica básica utilizada allí consiste en no inferir una contradicción tan pronto como se tenga la capacidad de hacerlo, sino introducir una suposición que no se desea conservar, e inferir una contradicción para deshacerse de ella. Personalmente, encontraría esto muy complicado si no llevara un registro del ámbito como hice arriba.

Se señala que existe un metateorema que establece que si un teorema se cumple en el cálculo proposicional clásico, también existirá un teorema correspondiente en todas las Álgebras de Boole. Dado que lo anterior consiste en demostraciones en el cálculo proposicional clásico, por ese metateorema, también son válidas para todas las Álgebras de Boole.

Answer 3

Las tablas de verdad son un resumen del álgebra subyacente; sin una especificación más clara de lo que quieres decir con "la manera algebraica", no sé qué querrías aparte de las tablas de verdad. Podrías dividirlo en casos ("si $A=0$ y $B=0$ entonces $(A+B)' = 0' = 1 = 1 \cdot 1 = A' \cdot B'$", y así sucesivamente), pero esto es exactamente lo que te dice la tabla de verdad.

Answer 4

¿Qué respondes a alguien que dice: "Muéstrame por qué estos dos teoremas se verifican sin usar las tablas de verdad"?

El ejemplo más simple que puedo pensar para las leyes de De Morgan es:

Si preguntas:
"¿Cuándo una declaración $AND$ (o $\land$) no es $verdadera$?",
entonces la respuesta es:
"Si alguna de las dos afirmaciones involucradas es $falsa$."

Lo anterior se describe simbólicamente con: $$\lnot(a \land b) = \lnot a \lor \lnot b $$

De manera similar, si preguntas:
"¿Cuándo una declaración $OR$ (o $\lor$) no es $verdadera$?",
entonces la respuesta es:
"Cuando ambas afirmaciones involucradas son $falsas$."

Lo cual se expresa simbólicamente como:

$$\lnot(a \lor b) = \lnot a \land \lnot b$$

Así, las leyes de De Morgan podrían considerarse como un criterio para que el resultado de los operadores lógicos $OR$ y $AND$ sea $falso$.

---

Respuesta más complicada:

Teniendo en cuenta:

Las afirmaciones $\lnot \forall x \in U(p(x))$ y $\exists x \in U(\lnot p(x))$ son equivalentes.

Las leyes de De Morgan podrían considerarse como una reducción de la relación que la negación, $\neg$, establece entre las afirmaciones de "para todo", $\forall$, y de "existe", $\exists$, de un número potencialmente infinito de afirmaciones sobre un universo infinito a un número finito de afirmaciones.

Answer 5

Al transferir el problema del álgebra booleana $(\mathbb Z_2, \neg, \vee, \wedge)$ al anillo booleano $(\mathbb Z_2, 1, +, \cdot)$, donde $1$ significa VERDADERO, $+$ significa O EXCLUSIVO y $\cdot$ significa Y y usando las equivalencias

$\neg a \iff (1+a)$
$a\vee b \iff (a+b+ab)$
$a\wedge b \iff (a\cdot b)

hace la tarea muy algebraica y bastante directa.

$\neg(a\wedge b)\iff (1+ab)$
$(\neg a \vee \neg b)\iff ((1+a)+(1+b)+(1+a)(1+b))=a+b+1+a+b+ab=1+ab$ (recuerda que $x+x=0)

y

$\neg(a\vee b)\iff (1+(a+b+ab))$
$(\neg a)\wedge\neg b)(1+a)(1+b)=1+a+b+ab$