Download leyes de morgan - Gabriel Montero

LEYESDE
MORGAN
[ING.JOSÉJULIOGONZALEZALVAREZ]
GABRIELMONTERO
I.S.C
01/10/16
MIXTO
LEYES DE MORGAN
¬(P
Q)
(¬P )
(¬Q)
¬(P Q)
donde:
(¬P )
(¬Q)
• ¬ es el operador de negación (NO)
•
es el operador de conjunción (Y)
•
es el operador de disyunción (O)
•
es un símbolo metalógico que signi ca “puede ser
reemplazado en una prueba lógica"
Entre la aplicaciones de las normas se incluyen la simplicació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.
Representación gráfica de las leyes de De Morgan
En lógica proposicional y álgebra de Boole, las leyes de
De Morgan[1][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)"
1
Notación formal
La regla de la negación de la conjunción se puede escribir en
la subsiguiente notación:
¬(P Q) (¬P ¬Q)
La negación de la regla de disyunción se puede escribir
como:
¬(P Q) (¬P ¬Q)
En forma de regla: negación de la conjunción
¬(P Q)
¬P ¬Q
y negación de la disyunción
¬(P Q)
¬P ¬Q
y se expresa como una tautología verdad-funcional o
teorema de lógica proposicional:
Las reglas pueden ser expresadas en un lenguaje formal
con dos proposiciones P y Q, de esta forma:
1
3
¬(P
Q) → (¬P
¬Q)
¬(P
Q) → (¬P
¬Q)
donde P , y Q son proposiciones expresadas en algún sistema formal.
1.1
¬P ¬Q
¬(P 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
Forma de sustitución
Normalmente, las leyes de De Morgan se muestran en forma compacta como se muestran arriba, con la nega- ción de la salida de la izquierda y la de las entradas a la
¬P Q
derecha.
¬(P ¬Q)
1.1.1
Conjunción
La conjunción de dos preposiciones es equivalente a la
negación de la disyunción de los términos negados
P Q
¬(¬P ¬Q)
1.1.2
Esta forma también es equivalente al implica de la negación del término P y la negación del término Q
¬(P Q)
¬(¬P → 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
Disyunción
La disyunción de dos preposiciones es equivalente a la ne- P ¬Q
gación de la conjunción de la negación de P y la negación
¬(¬P
Q)
de Q
P Q
¬(¬P ¬Q)
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
1.1.3
Negaciones de operadores en las conjunciones
y disyunciones
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
¬P ¬Q
¬(P Q)
Esto pone de relieve la necesidad de invertir tanto en las
entradas como en las salidas, así como también cambiar el
La conjunción de la proposición P negada y la preposición Q
operador, haciendo una sustitución.
es equivalente a la negación de la disyunción de P y la negación de Q
Conjunción con P negada
1.2
¬P Q
¬(P ¬Q)
Teoría de conjuntos y el álgebra de
Boole
En la teoría de conjuntos y el álgebra de Boole, a menudo se
indica como “Intercambio de Unión e intersección ba- jo la
[4]
La conjunción de la proposición P y la preposición Q ne- complementación”, que puede ser expresado forgada es equivalente a la negación de la disyunción de la malmente como:
negación de P y Q
• A B ≡ A ∩B
• A ∩B ≡ A B que puede ser expresado formalP ¬Q
mente como:
¬(¬P Q)
donde:
Conjunción tanto de P como de Q negadas
Conjunción con Q negada
4
•
es el intersección operador (Y)
•
es el operador unión (O)
La forma generalizada es:
∩
Ai ≡
Ai
i I
i I
Ai ≡
i I
∩
3.1 Negación de una disyunción
En el caso de su aplicación a una disyunción, considere
la siguiente a rmación: “es falso que uno de A o B es
verdadero”, que se escribe como:
Ai
Se puede recordar la ley de De Morgan, en notación de
conjunto, mediante la regla nemotécnica “romper la línea,
cambiarelsigno”.[5]
1.3
Ingeniería
En ingeniería electrónica e informática, la ley de De Morgan se escribe comúnmente como:
A ·B ≡A + B
A + B ≡A ·B
El teorema de De Morgan se puede aplicar tanto a la
negación de una disyunción como a la negación de una
conjunción en la totalidad o parte de una fórmula.
i I
donde I es un conjunto indexado, posiblemente incontable.
3 Prueba
informal
• A es la negación de A, la línea alta está escrita sobre
las términos que se niegan
donde:
• · es el Y lógico
• + es el O lógico
La ley lleva el nombre de Augustus De Morgan (18061871)[6] que presentó una versión formal de las leyes de
la lógica proposicional clásica. La formulación de De
Morgan fue in uenciado por la alegorización de la lógica emprendida por George Boole, que más tarde consolidó la a rmación de De Morgan para el hallazgo. Aunque Aristóteles ya había hecho una observación similar y
eran conocidas por los lógicos griegos y medievales[7]
(en el siglo XIV, Guillermo de Ockham escribió las palabras que resultarían leyendo las leyes a cabo),[8] A De
Morgan se le da crédito de a rmar formalmente las leyes
y de su incorporación al lenguaje de la lógica. Las leyes
de De Morgan pueden ser probadas fácilmente, e incluso puede parecer triviales.[9] Sin embargo, estas leyes son
En que se ha establecido que ni A ni B es cierto, enton- ces
debe seguir que tanto A no es verdad como B no es
verdad, que puede ser escrito directamente como:
(¬A)
Trabajando en dirección opuesta, la segunda expresión
a rma que A es falsa y B es falsa (o equivalentemente
que “no A” y “no B” son verdaderas). Sabiendo esto, una
disyunción de A y B también debe ser falsas. Por lo tan- to,
la negación de dicha separación debe ser verdad, y el
resultado es idéntico al de la primera reivindicación.
4
(¬B)
Presentadas en español, esto sigue la lógica de que “Como
es falso que dos cosas sean verdaderas, al menos uno de
ellos debe ser falsa.”
• la barra superior es el NO lógico de lo que está por
debajo de la barra superior.
2
Histo
ria
¬(A B)
Prueba
formal
La prueba que (A∩B)c = Ac B c se realiza por primera
probando que (A ∩ B)c Ac B c , y luego probando
queAc B c (A ∩B)c obviamenteesteprocedimiento es
válido.
Considérese x (A ∩ B)c . Entonces x ̸ A ∩ B . Ya
que A ∩ B = {y|y A y y
B} , entonces ya sea
x ̸ A o x ̸ B . Si x ̸ A , entonces x Ac
, entonces x
Ac B c . De otro modo, si x ̸ B ,
c
entonces x B , por lo tanto x Ac B c . Debido a que
esto es cierto para cualquier arbitrario x (A ∩B)c
, entonces x (A ∩ B)c , x Ac B c , y entonces
(A ∩ B)c Ac B c .
Para probar la dirección inversa, asumir que x
Ac
B c de tal forma que x ̸ (A ∩B)c
. Entonces x A ∩Bc
. De ello resulta que x A y x B . Entonces x ̸ A
, contradiciendo
y x ̸ B c . Pero luego x ̸ c Ac cB
la hipótesis de que x A B
. Por lo tanto, x
Ac B , x (A ∩ B)c , y Ac B
(A ∩ B)c .
c
c
c
Como A
B
(A ∩ B) y (A ∩ B)c
Ac B c ,
5
De manera similar, se comprueba la otra ley de De Mor- Relacionar estas dualidades del cuanti cador a las leyes
gan, que (A B)c = Ac ∩ B c .
de De Morgan, establecer un modelo con un pequeño nú
mero de elementos en su dominio D, tales como
5
Extensio
nes
D = {a, b, c}.
Entonces
&≥1
≥1
y
x P (x) ≡ P (a) P (b) P (c)
x P (x) ≡ P (a) P (b) P (c).
Pero, usando las leyes de De Morgan,
P (a)
P (b) P (c) ≡ ¬(¬P (a)
¬P (b)
¬P (c))
y
Las leyes de De Morgan representadas como un circuito con puertas lógicas
P (a)
En extensiones de la lógica proposicional, se mantiene la
dualidad clásica, (es decir, a cualquier operador lógi- co
siempre podemos encontrar su doble), ya que en la
presencia de las identidades que rigen la negación, siempre se puede introducir un operador que sea el doble de
De Morgan del otro. Esto conduce a una importante propiedad 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 en la que solo se
producen negaciones aplicadas a las atómicas no lógicas
de la fórmula. La existencia de formas normales negadas
conduce a muchas aplicaciones, por ejemplo en el diseño
de circuitos digitales, donde se utiliza para manipular los
tipos de compuertas lógicas, y en la lógica formal, don- de
es un requisito previo para encontrar la forma normal
conjuntiva y la forma normal disyuntiva de una fórmu- la.
Los programadores de computadoras los utilizan para
simpli car o bien negar complicadas condiciones lógicas.
También suelen ser útiles para los cálculos en la teoría de
probabilidad elemental.
P (b) P (c) ≡ ¬(¬P (a) ¬P (b) ¬P (c)),
veri cando las dualidades del cuanti cador en el modelo.
Entonces, las dualidades del cuanti cador pueden ser extendidas aún más a la lógica modal, que relaciona el
cuadro de los operadores (“necesariamente”) y diaman- te
(“posiblemente”):
□p ≡ ¬ ¬p,
p ≡ ¬□¬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, se puede entender la relación de
estos operadores modales a la cuanti cación mediante la
creación de modelos utilizando la semántica de Kripke.
6
Vamos a de nir el dual de cualquier operador P(p, q, ...) en función de las proposiciones elementales p, q, ... para
ser el operador Pd de nido por
• Isomorfismo (operador NO como isomor smo entre
lógica positiva y lógica negativa)
• Lista de los temas de álgebra de Boole
Pd (p, q, ...) = ¬P (¬p, ¬q, . . . ).
Esta idea se puede generalizar a los cuanti cadores, así
que, por ejemplo el cuantificador universal y cuantificador
existencial son duales:
Véase
también
7
Referen
cias
[1] Copi y Cohen
x P (x) ≡ ¬ x ¬P (x),
[2] Hurley
x P (x) ≡ ¬ x ¬P (x).
[3] Moore y Parker