Leyes de De Morgan
Enviado por josefo787 • 13 de Marzo de 2014 • 1.733 Palabras (7 Páginas) • 229 Visitas
Leyes de De Morgan
En lógica proposicional y álgebra de Boole, las leyes de De Morgan1 2 3 son un par de reglas de transformación que son ambas reglas de inferencia válidas. Las normas permiten la expresión de las conjunciones y disyunciones puramente en términos de sí vía negación.
Las reglas se pueden expresar en español como:
La negación de la conjunción es la disyunción de las negaciones.
La negación de la disyunción es la conjunción de las negaciones.
o informalmente como:
"no (A y B)" es lo mismo que "(no A) o (no B)"
y también,
"no (A o B)" es lo mismo que "(no A) y (no B)"
Las reglas pueden ser expresadas en un lenguaje formal con dos proposiciones P y Q, de esta forma:
\neg(P\land Q)\iff(\neg P)\lor(\neg Q)
\neg(P\lor Q)\iff(\neg P)\land(\neg Q)
donde:
¬ es el operador de negación (NO)
\land es el operador de conjunción (Y)
\lor es el operador de disyunción (O)
⇔ es un símbolo metalógico que significa "puede ser reemplazado en una mediante una prueba lógica"
Entre la aplicaciones de las normas se incluyen la simplificación de expresiones lógicas en programas de computación y diseño de circuitos digitales. Las leyes de De Morgan son un ejemplo de concepto más general de dualidad matemática.
Índice [ocultar]
1 Notación formal
1.1 Forma de sustitución
1.1.1 Conjunción
1.1.2 Disyunción
1.1.3 Negaciones de operadores en las conjunciones y disyunciones
1.2 Teoría de conjuntos y el álgebra de Boole
1.3 Ingeniería
2 Historia
3 Prueba informal
3.1 Negación de una disyunción
4 Prueba formal
5 Extensiones
6 Véase también
7 Referencias
8 Enlaces externos
Notación formal[editar]
La regla de la negación de la conjunción puede se puede escribir en la subsiguiente notación:
\neg(P \and Q) \vdash (\neg P \or \neg Q)
La negación de la regla de disyunción se puede escribir como:
\neg(P \or Q) \vdash (\neg P \and \neg Q)
En forma de regla: negación de la conjunción
\frac{\neg (P \and Q)}{\therefore \neg P \or \neg Q}
y negación de la disyunción
\frac{\neg (P \or Q)}{\therefore \neg P \and \neg Q}
y se expresa como una tautología verdad-funcional o teorema de lógica proposicional:
\neg (P \and Q) \to (\neg P \or \neg Q)
\neg (P \or Q) \to (\neg P \and \neg Q)
donde P, y Q son proposiciones expresadas en algún sistema formal.
Forma de sustitución[editar]
Normalmente, las Leyes de De Morgan se muestran en forma compacta como se muestra arriba, con la negación de la salida de la izquierda y la negación de las entradas a la derecha.
Conjunción[editar]
La conjunción de dos preposiciones es equivalente a la negación de la disyunción de los términos negados
\frac{P \and Q}{\ \neg (\neg P \or \neg Q)}
Disyunción[editar]
La disyunción de dos preposiciones es equivalente a la negación de la conjunción de la negación de P y la negación de Q
\frac{P \or Q}{\ \neg ( \neg P \and \neg Q)}
Negaciones de operadores en las conjunciones y disyunciones[editar]
Conjunción con P negada
La conjunción de la proposición P negada y la preposición Q es equivalente a la negación de la disyunción de P y la negación de Q
\frac{\neg P \and Q}{\ \neg (P \or \neg Q)}
Conjunción con Q negada
La conjunción de la proposición P y la preposición Q negada es equivalente a la negación de la disyunción de la negación de P y Q
\frac{P \and \neg Q}{\ \neg (\neg P \or Q)}
Conjunción tanto de P como de Q negadas
La conjunción de la proposición P y Q negadas es equivalente a la negación de la disyunción de P y Q
\frac{\neg P \and \neg Q}{\ \neg (P \or Q)}
Disyunción con P negada
La disyunción de la proposición P negada y la preposición Q es equivalente a la negación de la conjunción de P y la negación de Q
\frac{\neg P \or Q}{\ \neg (P \and \neg Q)}
Esta forma también es equivalente al implica de la negación del término P y la negación del término Q
\frac{\neg P \or Q}{\ \neg P \rightarrow \neg Q)}
Disyunción con Q negada
La disyunción de la proposición P y la preposición Q negada es equivalente a la negación de la disyunción de la negación de P y Q
\frac{P \or \neg Q}{\ \neg (\neg P \and Q)}
Disyunción tanto de P como de Q negadas
La disyunción de la proposición P y Q negadas es equivalente a la conjunción de la disyunción de P y Q
\frac{\neg P \or \neg Q}{\ \neg (P \and Q)}
Esto pone de relieve la necesidad de invertir tanto en las entradas como en las salidas, así como también cambiar el operador, haciendo una sustitución.
Teoría de conjuntos y el álgebra de Boole[editar]
En la teoría de conjuntos y el álgebra de Boole, a menudo se indica como "Intercambio de Unión e intersección bajo la complementación",4 que puede ser expresado formalmente como:
\overline{A \cup B}\equiv\overline{A} \cap \overline{B}
\overline{A \cap B}\equiv\overline{A} \cup \overline{B} que puede ser expresado formalmente como:
donde:
A es la negación de A, la línea alta está escrita sobre las términos que se niegan
∩ es el intersección operador (Y)
∪ es el operador unión (O)
La forma generalizada es:
\overline{\bigcap_{i \in I} A_{i}}\equiv\bigcup_{i \in I} \overline{A_{i}}
\overline{\bigcup_{i \in I} A_{i}}\equiv\bigcap_{i
...