Lleis de De Morgan

Plantilla:Regles de transformació En llògica proposicional i àlgebra de Boole, les lleis de De Morgan són un parell de regles de transformació que són abdós regles d'inferència vàlides. Les normes permeten l'expressió de les conjuncions i disjunció purament en térmens de negació.

Lleis de De Morgan

Les regles es poden expressar en espanyol.La negació de la conjunció és la disjunció de les negacions.
La negació de la disjunció és la conjunció de les negacions. o informalmente com: «no (A i B)» és lo mateix que «(no A) o (no B)»

i també,

«no (A o B)» és lo mateix que «(no A) i (no B)»

Les regles poden ser expressades en llenguage formal en dos proposicions P i Q, d'esta forma:

$\mathrm{\neg }(P\wedge Q)⟺(\mathrm{\neg }P)\vee (\mathrm{\neg }Q)$

$\mathrm{\neg }(P\vee Q)⟺(\mathrm{\neg }P)\wedge (\mathrm{\neg }Q)$

a on:

• ¬ és l'operador de negació (NO)
• $\wedge$ és l'operador de conjunció (I)
• $\vee$ és l'operador de disjunció (O)
• ⇔ és un símbol metalógico que significa «pot ser reemplaçat en una prova llògica»

Entre les aplicacions de les normes s'inclouen la simplificació d'expressions llògiques en programes de computació i disseny de circuits digitals. Les lleis de De Morgan són un eixemple de concepte més general de dualitat matemàtica.

Teoria de conjunts i l'àlgebra de Boole

En la teoria de conjunts i l'àlgebra de Boole, a sovint s'indica com a «intercanvi d'unió i intersecció baix complementaris», que pot ser expressat formalment com:

• $\overline{A\cup B}\equiv \bar{A}\cap \bar{B}$
• $\overline{A\cap B}\equiv \bar{A}\cup \bar{B}$

a on:

• A és la negació de A, la llínea alta està escrita sobre les térmens que es neguen
• $\cap$ és l'operador intersecció (I)
• $\cup$ és l'operador unió (O)

La forma generalisada és:

$\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\in I}\overline{A_i}$

a on I és un conjunt indexat, possiblement no numerable.

Es pot recordar la llei de De Morgan, en notació de conjunt, per mig de la regla nemotécnica "trencar la llínea, canviar el signe".

Notació formal

La regla de la negació de la conjunció es pot escriure en la subsegüent notació:

$\mathrm{\neg }(P\wedge Q)⊢(\mathrm{\neg }P\vee \mathrm{\neg }Q)$

La regla de la negació de disjunció es pot escriure com:

$\mathrm{\neg }(P\vee Q)⊢(\mathrm{\neg }P\wedge \mathrm{\neg }Q)$

En forma de regla: negació de la conjunció

$\frac{\mathrm{\neg }(P\wedge Q)}{\therefore \mathrm{\neg }P\vee \mathrm{\neg }Q}$

i negació de la disjunció

$\frac{\mathrm{\neg }(P\vee Q)}{\therefore \mathrm{\neg }P\wedge \mathrm{\neg }Q}$

i s'expressa com una tautologia veritat-funcional o teorema de llògica proposicional:

$\mathrm{\neg }(P\wedge Q)\to (\mathrm{\neg }P\vee \mathrm{\neg }Q)$

$\mathrm{\neg }(P\vee Q)\to (\mathrm{\neg }P\wedge \mathrm{\neg }Q)$

a on $P$, i $Q$ són proposicions expressades en algun sistema formal.

Forma de substitució

Normalment, les lleis de De Morgan es mostren en forma compacta com es mostren dalt, en la negació de l'eixida de l'esquerra i la de les entrades a la dreta. Encara que una forma de substitució més clara per a la conjunció i la disjunció és la que es mostra avall:

Conjunció

La conjunció de dos proposicions és equivalent a la negació de la disjunció dels térmens negats

$\frac{P\wedge Q}{\mathrm{\neg }(\mathrm{\neg }P\vee \mathrm{\neg }Q)}$

Disjunció

La disjunció de dos proposicions és equivalent a la negació de la conjunció de la negació de P i la negació de Q

$\frac{P\vee Q}{\mathrm{\neg }(\mathrm{\neg }P\wedge \mathrm{\neg }Q)}$

Negacions d'operadors en les conjuncions i disjunció

Conjunció en P negada

La conjunció de la proposició P negada i la preposició Q és equivalent a la negació de la disjunció de P i la negació de Q

$\frac{\mathrm{\neg }P\wedge Q}{\mathrm{\neg }(P\vee \mathrm{\neg }Q)}$

Conjunció en Q negada

La conjunció de la proposició P i la preposició Q negada és equivalent a la negació de la disjunció de la negació de P i Q

$\frac{P\wedge \mathrm{\neg }Q}{\mathrm{\neg }(\mathrm{\neg }P\vee Q)}$

Conjunció tant de P com de Q negades

La conjunció de la proposició P i Q negades és equivalent a la negació de la disjunció de P i Q

$\frac{\mathrm{\neg }P\wedge \mathrm{\neg }Q}{\mathrm{\neg }(P\vee Q)}$

Disjunció en P negada

La disjunció de la proposició P negada i la preposició Q és equivalent a la negació de la conjunció de P i la negació de Q

$\frac{\mathrm{\neg }P\vee Q}{\mathrm{\neg }(P\wedge \mathrm{\neg }Q)}$

Esta forma també és equivalent a l'implica de la negació del terme P i la negació del terme Q

$\frac{\mathrm{\neg }(P\vee Q)}{\mathrm{\neg }(\mathrm{\neg }P\to Q)}$

Disjunció en Q negada

La disjunció de la proposició P i la preposició Q negada és equivalent a la negació de la conjunció de la negació de P i Q

$\frac{P\vee \mathrm{\neg }Q}{\mathrm{\neg }(\mathrm{\neg }P\wedge Q)}$

Disjunció tant de P com de Q negades

La disjunció de la proposició P i Q negades és equivalent a la conjunció de la disjunció de P i Q

$\frac{\mathrm{\neg }P\vee \mathrm{\neg }Q}{\mathrm{\neg }(P\wedge Q)}$

Açò posa de relleu la necessitat d'invertir tant en les entrades com en les eixides, aixina com també canviar l'operador, fent una substitució.

Ingenieria

En ingenieria electrònica i informàtica, la llei de De Morgan s'escriu comunament com:

$\overline{A\cdot B}\equiv \bar{A}+\bar{B}$

$\overline{A+B}\equiv \bar{A}\cdot \bar{B}$

Que es pot llegir com:

La negació del producte és igual a la suma dels negats.

La negació de la suma és igual al producte dels negats.

a on:

• $\cdot$ és el producte llògic (I).
• $+$ és la suma llògica (O).
• la barra superior és la negació llògica (NO) de lo que està per baix de la barra superior.

Vore també

• Isomorfisme (operador NO com a isomorfisme entre llògica positiva i llògica negativa)
• Llistadels temes d'àlgebra de Boole
• Proposició