Leyes de De Morgan
Las leyes de Morgan son identidades entre propuestas lógicas. Fueron formulados por el matemático británico Augustus De Morgan (1806-1871).
Hablado en francés
En lógica clásica , la negación de la disyunción de dos proposiciones es equivalente a la conjunción de las negaciones de las dos proposiciones, lo que significa que "no (A o B)" es idéntico a "(no A) y (no B)" .
Aún en la lógica clásica , la negación de la conjunción de dos proposiciones es equivalente a la disyunción de las negaciones de las dos proposiciones, lo que significa que "no (A y B)" es idéntico a "(no A) o (no B) ".
Enunciado matemático
Sabiendo que la conjunción se expresa mediante el signo :, la disyunción se expresa mediante el signo: y se escribe la negación de una fórmula .
∧{\ Displaystyle \ land}
∨{\ Displaystyle \ lor}
F{\ Displaystyle F}
F¯{\ Displaystyle {\ overline {F}}}![\ overline {{F}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d122dfa2be8a341b1c30e7b3405af6ac2c157105)
- (A∧B)¯↔(A¯)∨(B¯){\ Displaystyle {\ overline {(A \ land B)}} \ leftrightarrow ({\ overline {A}}) \ lor ({\ overline {B}})}
![\ overline {(A \ land B)} \ leftrightarrow (\ overline {A}) \ lor (\ overline {B})](https://wikimedia.org/api/rest_v1/media/math/render/svg/4258ff91ec90b3400a55a9d419a0b77f8825b48d)
- (A∨B)¯↔(A¯)∧(B¯){\ Displaystyle {\ overline {(A \ lor B)}} \ leftrightarrow ({\ overline {A}}) \ land ({\ overline {B}})}
![\ overline {(A \ lor B)} \ leftrightarrow (\ overline {A}) \ land (\ overline {B})](https://wikimedia.org/api/rest_v1/media/math/render/svg/6e474c7591fc05198e84ecb18c2cdc46c4bc344c)
De estas cuatro implicaciones válidas en la lógica clásica, tres son válidas en la lógica intuicionista , pero no:
(A∧B)¯→(A¯)∨(B¯){\ Displaystyle {\ overline {(A \ land B)}} \ rightarrow ({\ overline {A}}) \ lor ({\ overline {B}})}
Justificación
Para justificar estas fórmulas, es por ejemplo, utilizar el método semántica de tablas de verdad . Recordamos que dos fórmulas son equivalentes si y solo si tienen la misma tabla de verdad.
(A∧B)¯↔(A¯)∨(B¯){\ Displaystyle {\ overline {(A \ land B)}} \ leftrightarrow ({\ overline {A}}) \ lor ({\ overline {B}})}
|
A{\ Displaystyle A}![A](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3) |
B{\ Displaystyle B}![B](https://wikimedia.org/api/rest_v1/media/math/render/svg/47136aad860d145f75f3eed3022df827cee94d7a) |
A∧B{\ Displaystyle A \ land B}![A \ tierra B](https://wikimedia.org/api/rest_v1/media/math/render/svg/74954195333a8593163b93a9688695b8dc74da55) |
(A∧B)¯{\ Displaystyle {\ overline {(A \ land B)}}}![\ overline {(A \ land B)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5201cbac64b7794e1fb9730b3de0e21abb36d841) |
A¯{\ Displaystyle {\ overline {A}}}![\ overline {A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92efef0e89bdc77f6a848764195ef5b9d9bfcc6a) |
B¯{\ Displaystyle {\ overline {B}}}![\ overline B](https://wikimedia.org/api/rest_v1/media/math/render/svg/164e5a0ce2bdc0686a2206a4c31f61135bd6ea60) |
(A¯)∨(B¯){\ Displaystyle ({\ overline {A}}) \ lor ({\ overline {B}})}
|
0 |
0 |
0 |
1 |
1 |
1 |
1
|
0 |
1 |
0 |
1 |
1 |
0 |
1
|
1 |
0 |
0 |
1 |
0 |
1 |
1
|
1 |
1 |
1 |
0 |
0 |
0 |
0
|
(A∨B)¯↔(A¯)∧(B¯){\ Displaystyle {\ overline {(A \ lor B)}} \ leftrightarrow ({\ overline {A}}) \ land ({\ overline {B}})}
|
A{\ Displaystyle A}![A](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3) |
B{\ Displaystyle B}![B](https://wikimedia.org/api/rest_v1/media/math/render/svg/47136aad860d145f75f3eed3022df827cee94d7a) |
A∨B{\ Displaystyle A \ lor B}![A \ lor B](https://wikimedia.org/api/rest_v1/media/math/render/svg/9b9c9c90857c12727201dd9e47a4e7c8658fdbc5) |
(A∨B)¯{\ Displaystyle {\ overline {(A \ lor B)}}}![\ overline {(A \ lor B)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6cdbdd7568f960fd6ab318acac5e32ddcc35b614) |
A¯{\ Displaystyle {\ overline {A}}}![\ overline A](https://wikimedia.org/api/rest_v1/media/math/render/svg/92efef0e89bdc77f6a848764195ef5b9d9bfcc6a) |
B¯{\ Displaystyle {\ overline {B}}}![\ overline B](https://wikimedia.org/api/rest_v1/media/math/render/svg/164e5a0ce2bdc0686a2206a4c31f61135bd6ea60) |
(A¯)∧(B¯){\ Displaystyle ({\ overline {A}}) \ land ({\ overline {B}})}
|
0 |
0 |
0 |
1 |
1 |
1 |
1
|
0 |
1 |
1 |
0 |
1 |
0 |
0
|
1 |
0 |
1 |
0 |
0 |
1 |
0
|
1 |
1 |
1 |
0 |
0 |
0 |
0
|
Generalización
Los enunciados de De Morgan se generalizan a proposiciones por inducción, utilizando la asociatividad de las leyes y su doble distributividad . Como las dos pruebas son simétricas (basta con reemplazar una ley por la otra), aquí solo damos eso para la primera ley.
no{\ Displaystyle n}
∧{\ Displaystyle \ land}
∨{\ Displaystyle \ lor}![\ lor](https://wikimedia.org/api/rest_v1/media/math/render/svg/ab47f6b1f589aedcf14638df1d63049d233d851a)
- Fiel al rango no=2{\ Displaystyle n = 2}
- Tan fiel a la fila no{\ Displaystyle n}
(A1∧A2∧...∧Ano∧Ano+1)¯{\ Displaystyle {\ overline {(A_ {1} \ land A_ {2} \ land ... \ land A_ {n} \ land A_ {n + 1})}}}
↔((A1∧A2∧...∧Ano)∧Ano+1)¯{\ Displaystyle \ leftrightarrow {\ overline {((A_ {1} \ land A_ {2} \ land ... \ land A_ {n}) \ land A_ {n + 1})}}}
↔((A1∧A2∧...∧Ano)¯)∨(Ano+1¯){\ Displaystyle \ leftrightarrow ({\ overline {(A_ {1} \ land A_ {2} \ land ... \ land A_ {n})}}) \ lor ({\ overline {A_ {n + 1}} })}
↔((A1¯)∨(A2¯)∨...∨(Ano¯))∨(Ano+1¯){\ Displaystyle \ leftrightarrow (({\ overline {A_ {1}}}) \ lor ({\ overline {A_ {2}}}) \ lor ... \ lor ({\ overline {A_ {n}}} )) \ lor ({\ overline {A_ {n + 1}}})}
- La generalización de estas reglas más allá de lo finito da las reglas de indefinibilidad de los cuantificadores universales y existenciales del cálculo de predicados clásico. El cuantificador universal puede verse como una generalización de la conjunción y el cuantificador existencial como una generalización de la disyunción (no exclusiva).
∀X(AX¯)↔∃X(AX)¯{\ Displaystyle \ forall x ({\ overline {Ax}}) \ leftrightarrow {\ overline {\ existe x (Ax)}}}
∃X(AX¯)↔∀X(AX)¯{\ Displaystyle \ existe x ({\ overline {Ax}}) \ leftrightarrow {\ overline {\ forall x (Ax)}}}
Y de estas cuatro implicaciones clásicas, solo una no es válida en la lógica intuicionista .
∀X(AX)¯→∃X(AX¯){\ Displaystyle {\ overline {\ forall x (Ax)}} \ rightarrow \ exist x ({\ overline {Ax}})}![\ overline {\ forall x (Ax)} \ rightarrow \ exist x (\ overline {Ax})](https://wikimedia.org/api/rest_v1/media/math/render/svg/567d7c70c935260a2e987c84574310fcc20ee9e5)
En la lógica intuicionista
En la lógica intuicionista, solo tenemos una forma debilitada de las leyes de De Morgan. Solo existen las implicaciones
- ¬(A∨B)→(¬A∧¬B){\ Displaystyle \ lnot (A \ lor B) \ to (\ lnot A \ land \ lnot B)}
![{\ Displaystyle \ lnot (A \ lor B) \ to (\ lnot A \ land \ lnot B)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c8c34ea1462ebea51396d69e83e1151fc1a3a74c)
- (¬A∧¬B)→¬(A∨B){\ Displaystyle (\ lnot A \ land \ lnot B) \ to \ lnot (A \ lor B)}
![{\ Displaystyle (\ lnot A \ land \ lnot B) \ to \ lnot (A \ lor B)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/55c9eca60a27a13094b850cec1dc42c021957354)
- (¬A∨¬B)→¬(A∧B){\ Displaystyle (\ lnot A \ lor \ lnot B) \ to \ lnot (A \ land B)}
![{\ Displaystyle (\ lnot A \ lor \ lnot B) \ to \ lnot (A \ land B)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5e4019e4002851c88fa73a5bf47a90e9963b2812)
Demostremos la primera implicación. Para eso tenemos que demostrar que admitiendo que tenemos . Por tanto, debemos demostrar que disparamos y que disparamos . Probemos el primero. Esto equivale a demostrar que de y de , tenemos . Oro . Por lo tanto, es suficiente aplicar dos veces modus ponens (eliminación de la implicación).
¬(A∨B){\ Displaystyle \ lnot (A \ lor B)}
¬A∧¬B{\ Displaystyle \ lnot A \ land \ lnot B}
¬(A∨B){\ Displaystyle \ lnot (A \ lor B)}
A→⊥{\ Displaystyle A \ to \ bot}
¬(A∨B){\ Displaystyle \ lnot (A \ lor B)}
B→⊥{\ Displaystyle B \ to \ bot}
(A∨B)→⊥{\ Displaystyle (A \ lor B) \ to \ bot}
A{\ Displaystyle A}
⊥{\ Displaystyle \ bot}
A→(A∨B){\ Displaystyle A \ a (A \ lor B)}![{\ Displaystyle A \ a (A \ lor B)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8fe30d0a9129e73b68a860b7fcc2e2e26ce30e1f)
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">