Leyes de de morgan

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Pareja de equivalencias lógicas

Las leyes de De Morgan representadas con los diagramas de Venn. En cada caso, el conjunto resultante es el conjunto de todos los puntos en cualquier sombra de azul.

En lógica proposicional y álgebra booleana, las leyes de De Morgan, también conocidas como teorema de De Morgan, son un par de reglas de transformación que ambas son reglas válidas de inferencia. Llevan el nombre de Augustus De Morgan, un matemático británico del siglo XIX. Las reglas permiten la expresión de conjunciones y disyunciones puramente en términos mutuos a través de la negación.

Las reglas se pueden expresar en inglés como:

La negación de una disyunción es la conjunción de las negaciones
La negación de una conjunción es la disyunción de las negaciones

El complemento de la unión de dos conjuntos es el mismo que la intersección de sus complementos
El complemento de la intersección de dos conjuntos es el mismo que la unión de sus complementos

no (A o B) = (no A) y (no B)
no (A y B) = (no A) o (no B)

donde "A o B" es un "inclusivo o" lo que significa al menos uno de A o B en lugar de un "exclusivo o" eso significa exactamente uno de A o B.

En teoría de conjuntos y álgebra booleana, se escriben formalmente como

{displaystyle {begin{aligned}{overline {Acup B}}&={overline {A}}cap {overline {B}},\{overline {Acap B}}&={overline {A}}cup {overline {B}},end{aligned}}}

dónde

$A$ y $B$ son sets,
${overline {A}}$ es el complemento de $A$ ,
$cap$ es la intersección, y
$cup$ es el sindicato.

En esta tabla de verdad se muestra la equivalencia de ¬δ ¬φ ∧ ↓.

En lenguaje formal, las reglas se escriben como

neg (Plor Q)iff (neg P)land (neg Q),

neg (Pland Q)iff (neg P)lor (neg Q)

dónde

P y Q son proposiciones,
$neg$ es el operador de lógica de negación (NOT),
$land$ es el operador de lógica de conjunción (AND),
$lor$ es el operador de lógica de disyunción (OR),
$iff$ es un símbolo metalógico que significa "puede ser reemplazado en una prueba lógica con".

Puedes ver la tabla de verdad de la segunda regla en la tabla.

Las aplicaciones de las reglas incluyen la simplificación de expresiones lógicas en programas de computadora y diseños de circuitos digitales. Las leyes de De Morgan son un ejemplo de un concepto más general de dualidad matemática.

Notación formal

La regla de la negación de la conjunción se puede escribir en notación secuencial:

{displaystyle neg (Pland Q)vdash (neg Plor neg Q)}

{displaystyle (neg Plor neg Q)vdash neg (Pland Q)}

La regla de la negación de la disyunción puede escribirse como:

{displaystyle neg (Plor Q)vdash (neg Pland neg Q)}

{displaystyle (neg Pland neg Q)vdash neg (Plor Q)}

En forma de regla: negación de conjunción

{displaystyle {frac {neg (Pland Q)}{therefore neg Plor neg Q}}}

{displaystyle {frac {neg Plor neg Q}{therefore neg (Pland Q)}}}

y negación de la disyunción

{displaystyle {frac {neg (Plor Q)}{therefore neg Pland neg Q}}}

{displaystyle {frac {neg Pland neg Q}{therefore neg (Plor Q)}}}

y expresado como una tautología funcional veritativa o teorema de lógica proposicional:

{displaystyle {begin{aligned}neg (Pland Q)&to (neg Plor neg Q),\(neg Plor neg Q)&to neg (Pland Q),\neg (Plor Q)&to (neg Pland neg Q),\(neg Pland neg Q)&to neg (Plor Q),end{aligned}}}

Donde $P$ y $Q$ son propuestas expresadas en algún sistema formal.

Formulario de sustitución

Las leyes de De Morgan normalmente se muestran en la forma compacta de arriba, con la negación de la salida a la izquierda y la negación de las entradas a la derecha. Una forma más clara de sustitución se puede establecer como:

{displaystyle {begin{aligned}(Pland Q)&Longleftrightarrow neg (neg Plor neg Q),\(Plor Q)&Longleftrightarrow neg (neg Pland neg Q).end{aligned}}}

Esto enfatiza la necesidad de invertir tanto las entradas como las salidas, así como cambiar el operador al hacer una sustitución.

Las leyes tienen una brecha importante para el ( ${displaystyle neg (neg p)iff p}$ Ley de doble negación. $mathbb {L}$ , para convertirse en un sistema lógico formal: ${displaystyle p,q,r,....,emptyset in mathbb {L} }$ secuencia reporta símbolos que se definen bien formados al primer orden. El mismo sistema tiene esas conjunciones: ${displaystyle C_{|j}:x | xin set::{landloriffvdash }}$ . Obviamente, ${displaystyle C_{|j}=set, xin C_{|j}}$ es el conocimiento válido, entonces hay al menos uno $x$ conjunción, que - $T$ número —en la tabla de la verdad, proposición básica $x$ — es igual al contexto de existencia atómica $x$ , por supuesto según el ${displaystyle forall x:(mathbb {L} vDash forall csubsetneq C_{|j}, xin c)}$ conocimiento. Consideramos la teoría de la equivalencia, la lógica sí. En este punto, De Morgan Laws muestra efecto que es hacia arriba o hacia abajo, el contexto atómico de $x$ .

Teoría de conjuntos y álgebra booleana

En teoría de conjuntos y álgebra booleana, a menudo se expresa como "intercambio de unión e intersección bajo complementación", que se puede expresar formalmente como:

{displaystyle {begin{aligned}{overline {Acup B}}&={overline {A}}cap {overline {B}},\{overline {Acap B}}&={overline {A}}cup {overline {B}},end{aligned}}}

donde:

${overline {A}}$ es la negación de $A$ , la línea general que se escribe sobre los términos a ser negada,
$cap$ es el operador de intersección (AND),
$cup$ es el operador sindical (OR).

Uniones e intersecciones de cualquier número de conjuntos

La forma generalizada es

{begin{aligned}{overline {bigcap _{iin I}A_{i}}}&equiv bigcup _{iin I}{overline {A_{i}}},\{overline {bigcup _{iin I}A_{i}}}&equiv bigcap _{iin I}{overline {A_{i}}},end{aligned}}

donde $I$ es un conjunto de indexación, posiblemente contable o incontablemente infinito.

En notación de conjuntos, las leyes de De Morgan se pueden recordar usando el mnemotécnico "romper la línea, cambiar el signo".

Ingeniería

En ingeniería eléctrica e informática, las leyes de De Morgan se escriben comúnmente como:

{displaystyle {overline {(Acdot B)}}equiv {overline {(A}}+{overline {B)}}}

{overline {A+B}}equiv {overline {A}}cdot {overline {B}},

donde:

$cdot$ es la lógica Y,
$+$ es el OR lógico,
el sobre la barra es la lógica NO de lo que está debajo de la barra.

Búsqueda de texto

Las leyes de De Morgan se aplican comúnmente a la búsqueda de texto mediante operadores booleanos AND, OR y NOT. Considere un conjunto de documentos que contienen las palabras "gatos" y "perros". Las leyes de De Morgan sostienen que estas dos búsquedas devolverán el mismo conjunto de documentos:

Búsqueda A: NO (gatos o perros)

Búsqueda B: (no gatos) Y (no perros)

El corpus de documentos que contienen "gatos" o "perros" puede ser representado por cuatro documentos:

Documento 1: Contiene sólo la palabra "cats".

Documento 2: Contiene sólo "perros".

Documento 3: Contiene tanto "cats" como "perros".

Documento 4: No contiene "cats" ni "perros".

Para evaluar la Búsqueda A, claramente la búsqueda "(gatos O perros)" llegará a los Documentos 1, 2 y 3. Por lo tanto, la negación de esa búsqueda (que es la Búsqueda A) afectará a todo lo demás, que es el Documento 4.

Al evaluar la búsqueda B, la búsqueda "(NO gatos)" encontrará documentos que no contengan "gatos", que son los Documentos 2 y 4. De manera similar, la búsqueda "(NO perros)" acertará en los Documentos 1 y 4. Al aplicar el operador AND a estas dos búsquedas (que es la Búsqueda B) se acertará en los documentos que son comunes a estas dos búsquedas, que es el Documento 4.

Se puede aplicar una evaluación similar para mostrar que las siguientes dos búsquedas devolverán el mismo conjunto de documentos (Documentos 1, 2, 4):

Búsqueda C: NO (gatos y perros),

Búsqueda D: (NO gatos) OR (NO perros).

Historia

Las leyes llevan el nombre de Augustus De Morgan (1806–1871), quien introdujo una versión formal de las leyes en la lógica proposicional clásica. La formulación de De Morgan estuvo influenciada por la algebrización de la lógica realizada por George Boole, que más tarde consolidó la afirmación de De Morgan sobre el hallazgo. Sin embargo, Aristóteles hizo una observación similar, y era conocida por los lógicos griegos y medievales. Por ejemplo, en el siglo XIV, Guillermo de Ockham escribió las palabras que resultarían de la lectura de las leyes. Jean Buridan, en su Summulae de Dialectica, también describe reglas de conversión que siguen las líneas de las leyes de De Morgan. Aún así, se le da crédito a De Morgan por establecer las leyes en los términos de la lógica formal moderna e incorporarlas al lenguaje de la lógica. Las leyes de De Morgan se pueden probar fácilmente y hasta pueden parecer triviales. No obstante, estas leyes son útiles para hacer inferencias válidas en pruebas y argumentos deductivos.

Prueba informal

El teorema de De Morgan se puede aplicar a la negación de una disyunción o la negación de una conjunción en todo o en parte de una fórmula.

Negación de una disyunción

En el caso de su aplicación a una disyunción, considere la siguiente afirmación: "es falso que cualquiera de A o B sea verdadero", que se escribe como:

neg (Alor B).

En cuanto se ha establecido que ni ni A ni B son verdaderas, entonces debe seguirse que tanto A como B no son verdaderas, lo que puede escribirse directamente como:

(neg A)wedge (neg B).

Si A o B fueran verdaderos, entonces la disyunción de A y B sería verdadera, haciendo falsa su negación. Presentado en inglés, esto sigue la lógica de que "dado que dos cosas son ambas falsas, también es falso que cualquiera de ellas sea verdadera".

Trabajando en la dirección opuesta, la segunda expresión afirma que A es falso y B es falso (o de manera equivalente que 'no A' y 'no B' son verdaderos). Sabiendo esto, una disyunción de A y B también debe ser falsa. La negación de dicha disyunción debe, pues, ser verdadera, y el resultado es idéntico al de la primera pretensión.

Negación de una conjunción

La aplicación del teorema de De Morgan a la conjunción es muy similar a su aplicación a la disyunción tanto en la forma como en la lógica. Considere la siguiente afirmación: "es falso que tanto A como B sean verdaderas", que se escribe como:

neg (Aland B).

Para que esta afirmación sea verdadera, tanto A como B deben ser falsos, ya que si ambos fueran verdaderos, entonces la conjunción de A y B sería verdadera, lo que haría que su negación fuera falsa. Por lo tanto, uno (al menos) o más de A y B deben ser falsos (o de manera equivalente, uno o más de 'no A' y 'no B' deben ser verdaderos). Esto se puede escribir directamente como,

(neg A)lor (neg B).

Presentado en inglés, sigue la lógica de que "ya que es falso que dos cosas sean ambas verdaderas, al menos una de ellas debe ser falsa".

Trabajando de nuevo en la dirección opuesta, la segunda expresión afirma que al menos uno de "no A" y "no B" debe ser verdadero, o de manera equivalente que al menos uno de A y B debe ser falso. Como al menos uno de ellos debe ser falso, su conjunción también sería falsa. La negación de dicha conjunción da como resultado una expresión verdadera, y esta expresión es idéntica a la primera afirmación.

Prueba formal

Aquí usamos ${displaystyle A^{complement }}$ to denote the complement of A. La prueba de que ${displaystyle (Acap B)^{complement }=A^{complement }cup B^{complement }}$ se completa en 2 pasos probando ambos ${displaystyle (Acap B)^{complement }subseteq A^{complement }cup B^{complement }}$ y ${displaystyle A^{complement }cup B^{complement }subseteq (Acap B)^{complement }}$ .

Parte 1

Vamos ${displaystyle xin (Acap B)^{complement }}$ . Entonces, $xnot in Acap B$ .

Porque... ${displaystyle Acap B={,y | yin Awedge yin B,}}$ , debe ser el caso de que $xnot in A$ o $xnot in B$ .

Si $xnot in A$ , entonces ${displaystyle xin A^{complement }}$ Así que ${displaystyle xin A^{complement }cup B^{complement }}$ .

Del mismo modo, si $xnot in B$ , entonces ${displaystyle xin B^{complement }}$ Así que ${displaystyle xin A^{complement }cup B^{complement }}$ .

Así, ${displaystyle forall x{Big (}xin (Acap B)^{complement }implies xin A^{complement }cup B^{complement }{Big)}}$ ;

es decir, ${displaystyle (Acap B)^{complement }subseteq A^{complement }cup B^{complement }}$ .

Parte 2

Para probar la dirección inversa, deja ${displaystyle xin A^{complement }cup B^{complement }}$ , y para la contradicción asumir ${displaystyle xnot in (Acap B)^{complement }}$ .

En virtud de ese supuesto, debe ser el caso de que $xin Acap B$ ,

por lo que sigue que $xin A$ y $xin B$ , y así ${displaystyle xnot in A^{complement }}$ y ${displaystyle xnot in B^{complement }}$ .

Sin embargo, eso significa ${displaystyle xnot in A^{complement }cup B^{complement }}$ , en contradicción con la hipótesis de que ${displaystyle xin A^{complement }cup B^{complement }}$ ,

por consiguiente, la hipótesis ${displaystyle xnot in (Acap B)^{complement }}$ no debe ser el caso, lo que significa que ${displaystyle xin (Acap B)^{complement }}$ .

Por lo tanto, ${displaystyle forall x{Big (}xin A^{complement }cup B^{complement }implies xin (Acap B)^{complement }{Big)}}$ ,

es decir, ${displaystyle A^{complement }cup B^{complement }subseteq (Acap B)^{complement }}$ .

Conclusión

Si ${displaystyle A^{complement }cup B^{complement }subseteq (Acap B)^{complement }}$ y ${displaystyle (Acap B)^{complement }subseteq A^{complement }cup B^{complement }}$ , entonces ${displaystyle (Acap B)^{complement }=A^{complement }cup B^{complement }}$ ; esto concluye la prueba de la ley de De Morgan.

La otra ley de De Morgan, ${displaystyle (Acup B)^{complement }=A^{complement }cap B^{complement }}$ , se ha demostrado de forma similar.

Generalizar la dualidad de De Morgan

Las Leyes de De Morgan representaban como un circuito con puertas lógicas (Esquemas de la Comisión Electrotécnica Internacional).

En las extensiones de la lógica proposicional clásica, la dualidad aún se mantiene (es decir, para cualquier operador lógico uno siempre puede encontrar su dual), ya que en presencia de las identidades que gobiernan la negación, uno siempre puede introducir un operador que es el De Morgan dual de otro. Esto lleva a una propiedad importante de la lógica basada en la lógica clásica, a saber, la existencia de formas normales de negación: cualquier fórmula es equivalente a otra fórmula donde las negaciones solo ocurren aplicadas a los átomos no lógicos de la fórmula. La existencia de formas normales de negación impulsa muchas aplicaciones, por ejemplo, en el diseño de circuitos digitales, donde se utiliza para manipular los tipos de puertas lógicas, y en lógica formal, donde se necesita encontrar la forma normal conjuntiva y la forma normal disyuntiva de un fórmula. Los programadores de computadoras los usan para simplificar o negar adecuadamente condiciones lógicas complicadas. También suelen ser útiles en los cálculos de la teoría elemental de la probabilidad.

Definir el doble de cualquier operador proposición P(p, q,...) dependiendo de las proposiciones elementales p, qPara ser el operador ${mbox{P}}^{d}$ definidas por

{mbox{P}}^{d}(p,q,...)=neg P(neg p,neg q,dots).

Extensión a predicado y lógica modal

Esta dualidad se puede generalizar a los cuantificadores, por ejemplo, el cuantificador universal y el cuantificador existencial son duales:

{displaystyle forall x,P(x)equiv neg [exists x,neg P(x)]}

{displaystyle exists x,P(x)equiv neg [forall x,neg P(x)]}

Para relacionar estas dualidades de cuantificadores con las leyes de De Morgan, configure un modelo con una pequeña cantidad de elementos en su dominio D, como

D =a, b, c}.

Entonces

forall x,P(x)equiv P(a)land P(b)land P(c)

{displaystyle exists x,P(x)equiv P(a)lor P(b)lor P(c).}

Pero, usando las leyes de De Morgan,

P(a)land P(b)land P(c)equiv neg (neg P(a)lor neg P(b)lor neg P(c))

P(a)lor P(b)lor P(c)equiv neg (neg P(a)land neg P(b)land neg P(c)),

verificando las dualidades del cuantificador en el modelo.

Entonces, las dualidades del cuantificador se pueden extender más a la lógica modal, relacionando los operadores de caja ("necesariamente") y diamante ("posiblemente"):

Box pequiv neg Diamond neg p,

{displaystyle Diamond pequiv neg Box neg p.}

En su aplicación a las modalidades aléticas de posibilidad y necesidad, Aristóteles observó este caso, y en el caso de la lógica modal normal, la relación de estos operadores modales con la cuantificación se puede entender estableciendo modelos utilizando la semántica de Kripke.

En la lógica intuicionista

Tres de las cuatro implicaciones de las leyes de Morgan se cumplen en la lógica intuicionista. Específicamente, tenemos

neg (Plor Q)iff (neg P)land (neg Q),

{displaystyle (Plor Q)rightarrow neg ((neg P)land (neg Q)),}

{displaystyle (Pland Q)rightarrow neg ((neg P)lor (neg Q)),}

{displaystyle (neg P)lor (neg Q)rightarrow neg (Pland Q)}

mientras que el recíproco de la última implicación no se cumple en la lógica intuicionista pura y sería equivalente a la ley del medio excluido débil

{displaystyle neg Plor neg neg P}

que se puede utilizar como base para una lógica intermedia.

Esto sigue siendo cierto si la negación $neg P$ es reemplazado por implicación ${displaystyle Prightarrow C}$ para algún predicado constante arbitrario C, lo que significa que las leyes anteriores todavía son ciertas en la lógica mínima.

Del mismo modo, las leyes del cuantificador:

{displaystyle forall x,neg P(x)iff neg [exists x,P(x)]}

{displaystyle forall x,P(x)rightarrow neg [exists x,neg P(x)]}

{displaystyle exists x,P(x)rightarrow neg [forall x,neg P(x)]}

{displaystyle exists x,neg P(x)rightarrow neg [forall x,P(x)]}

son tautologías incluso en lógica mínima con la negación reemplazada por la implicación de una Q fija, mientras que la inversa de la última ley no tiene por qué ser cierta en general.

En ingeniería informática

Las leyes de De Morgan se utilizan ampliamente en ingeniería informática y lógica digital con el fin de simplificar los diseños de circuitos.

Contenido relacionado

Más resultados...