Questa voce o sezione sull'argomento matematica non cita le fonti necessarie o quelle presenti sono insufficienti .
Rappresentazione delle leggi di De Morgan attraverso due diagrammi di Venn. In ciascun caso l'insieme risultante è quello colorato di blu o qualche sua sfumatura Le leggi di De Morgan , o teoremi di De Morgan, sono relative alla logica booleana e stabiliscono relazioni di equivalenza tra gli operatori di congiunzione e disgiunzione logica.
Sono utilizzate per l'analisi di circuiti logici (elettrici, elettronici, pneumatici, comunque binari, cioè ON-OFF) e per la dimostrazione di teoremi basati regole logiche.
I teoremi I due teoremi sono duali:
A ⋅ B ¯ = A ¯ + B ¯ {\displaystyle {\overline {A\cdot B}}={\overline {A}}+{\overline {B}}} A + B ¯ = A ¯ ⋅ B ¯ {\displaystyle {\overline {A+B}}={\overline {A}}\cdot {\overline {B}}} Con riferimento a termini insiemistici, il primo si enuncia affermando che se un elemento non appartiene ad A {\displaystyle A} per B {\displaystyle B} , allora o non appartiene ad A {\displaystyle A} o non appartiene a B {\displaystyle B} o non appartiene ad entrambi. Il secondo teorema si enuncia affermando che se un elemento non appartiene ad A + B {\displaystyle A+B} , allora non appartiene ad A {\displaystyle A} e non appartiene a B {\displaystyle B} .
È immediata la generalizzazione a un numero n {\displaystyle n} di variabili:
A ⋅ B ⋅ C ⋯ ¯ = A ¯ + B ¯ + C ¯ + … {\displaystyle {\overline {A\cdot B\cdot C\cdots }}={\overline {A}}+{\overline {B}}+{\overline {C}}+\dots } A + B + C + … ¯ = A ¯ ⋅ B ¯ ⋅ C ¯ … {\displaystyle {\overline {A+B+C+\dots }}={\overline {A}}\cdot {\overline {B}}\cdot {\overline {C}}\dots } Nella logica proposizionale possono essere formulate in vario modo:
¬ ( a ∧ b ) = ¬ a ∨ ¬ b ¬ ( a ∨ b ) = ¬ a ∧ ¬ b {\displaystyle {\begin{matrix}\neg {(a\wedge b)}=\neg {a}\vee \neg {b}\\\neg {(a\vee b)}=\neg {a}\wedge \neg {b}\end{matrix}}\quad } oppure
( a ∧ b ) ¯ = a ¯ ∨ b ¯ ( a ∨ b ) ¯ = a ¯ ∧ b ¯ {\displaystyle \quad {\begin{matrix}{\overline {(a\wedge b)}}={\overline {a}}\vee {\overline {b}}\\{\overline {(a\vee b)}}={\overline {a}}\wedge {\overline {b}}\end{matrix}}} oppure
¬ ( P ∧ Q ) = ( ¬ P ) ∨ ( ¬ Q ) ¬ ( P ∨ Q ) = ( ¬ P ) ∧ ( ¬ Q ) {\displaystyle {\begin{matrix}\neg (P\wedge Q)=(\neg P)\vee (\neg Q)\\\neg (P\vee Q)=(\neg P)\wedge (\neg Q)\end{matrix}}} e nella teoria degli insiemi:
( A ∩ B ) C = A C ∪ B C {\displaystyle (A\cap B)^{C}=A^{C}\cup B^{C}} oppure
( A ∩ B ) ¯ = A ¯ ∪ B ¯ {\displaystyle {\overline {(A\cap B)}}={\overline {A}}\cup {\overline {B}}} e
( A ∪ B ) C = A C ∩ B C {\displaystyle (A\cup B)^{C}=A^{C}\cap B^{C}} oppure
( A ∪ B ) ¯ = A ¯ ∩ B ¯ {\displaystyle {\overline {(A\cup B)}}={\overline {A}}\cap {\overline {B}}} In pratica esse descrivono il comportamento dei connettivi logici (AND e OR) quando una negazione viene tolta da o inserita in una formula in parentesi. Se si raccoglie la negazione fuori parentesi o la si distribuisce tra i termini in parentesi, il connettivo si trasforma nel suo opposto.
Espresse in forma tabellare:
¬(W+Y) = (¬W) * (¬Y) ¬(W*Y) = (¬W) + (¬Y) 1 + W = 1 0 * W = 0 0 + W = W 1 * W = W
Dimostrazione I teoremi si possono dimostrare sia algebricamente che con l'ausilio della tabella della verità , essendo i casi da provare in numero finito:
Primo teorema
Dimostrazione tabellare p {\displaystyle p} q {\displaystyle q} p ¯ {\displaystyle {\overline {p}}} q ¯ {\displaystyle {\overline {q}}} p ∨ q {\displaystyle p\vee q} p ∨ q ¯ {\displaystyle {\overline {p\vee q}}} p ¯ ∧ q ¯ {\displaystyle {\overline {p}}\wedge {\overline {q}}} V V F F V F F V F F V V F F F V V F V F F F F V V F V V
Dimostrazione algebrica Prima di passare alla dimostrazione è utile annotare alcune proprietà e definizioni dell'algebra booleana; si considerino a {\displaystyle \mathbf {a} } , b {\displaystyle \mathbf {b} } e c {\displaystyle \mathbf {c} } tre variabili booleane:
0 ¯ = 1 {\displaystyle {\overline {0}}=1} e, viceversa, 1 ¯ = 0 {\displaystyle {\overline {1}}=0} a ¯ {\displaystyle \mathbf {\overline {a}} } è la negazione logica di a {\displaystyle \mathbf {a} } a = a ¯ ¯ {\displaystyle \mathbf {a} ={\overline {\overline {\mathbf {a} }}}} (due negazioni logiche si elidono così che una variabile negata due volte equivale alla variabile stessa non negata) a + 1 = 1 {\displaystyle \mathbf {a} +1=1} a ⋅ 0 = 0 {\displaystyle \mathbf {a} \cdot 0=0} a + a ¯ = 1 {\displaystyle \mathbf {a} +\mathbf {\overline {a}} =1} a ⋅ a ¯ = 0 {\displaystyle \mathbf {a} \cdot \mathbf {\overline {a}} =0} ( a + b ) + c = a + ( b + c ) {\displaystyle \left(\mathbf {a} +\mathbf {b} \right)+\mathbf {c} =\mathbf {a} +\left(\mathbf {b} +\mathbf {c} \right)} ( a ⋅ b ) ⋅ c = a ⋅ ( b ⋅ c ) {\displaystyle \left(\mathbf {a} \cdot \mathbf {b} \right)\cdot \mathbf {c} =\mathbf {a} \cdot \left(\mathbf {b} \cdot \mathbf {c} \right)} ( a + b ) ⋅ c = ( a ⋅ c ) + ( b ⋅ c ) {\displaystyle \left(\mathbf {a} +\mathbf {b} \right)\cdot \mathbf {c} =\left(\mathbf {a} \cdot \mathbf {c} \right)+\left(\mathbf {b} \cdot \mathbf {c} \right)} a + ( b ⋅ c ) = ( a + b ) ⋅ ( a + c ) {\displaystyle \mathbf {a} +\left(\mathbf {b} \cdot \mathbf {c} \right)=\left(\mathbf {a} +\mathbf {b} \right)\cdot \left(\mathbf {a} +\mathbf {c} \right)} (notare come questa proprietà sia valida solamente nell'algebra booleana, non nella comune algebra) DIMOSTRAZIONE :
I) ( a + b ) + a ¯ ⋅ b ¯ = {\displaystyle \left(\mathbf {a} +\mathbf {b} \right)+{\overline {\mathbf {a} }}\cdot {\overline {\mathbf {b} }}=}
(Si applica la proprietà 11 )
= [ ( a + b ) + a ¯ ] ⋅ [ ( a + b ) + b ¯ ] = {\displaystyle =\left[\left(\mathbf {a} +\mathbf {b} \right)+{\overline {\mathbf {a} }}\right]\cdot \left[\left(\mathbf {a} +\mathbf {b} \right)+\mathbf {\overline {b}} \right]=}
(Si applica la proprietà 8 )
= [ ( a + a ¯ ) + b ] ⋅ [ ( b + b ¯ ) + a ] = {\displaystyle =\left[\left(\mathbf {a} +{\overline {\mathbf {a} }}\right)+\mathbf {b} \right]\cdot \left[\left(\mathbf {b} +{\overline {\mathbf {b} }}\right)+\mathbf {a} \right]=}
(Si applica la proprietà 6 )
= [ ( 1 ) + b ] ⋅ [ ( 1 ) + a ] = {\displaystyle =\left[\left(1\right)+\mathbf {b} \right]\cdot \left[\left(1\right)+\mathbf {a} \right]=}
(Si applica la proprietà 4 )
= 1 + 1 = 1 {\displaystyle =1+1=1}
II) ( a + b ) ⋅ ( a ¯ ⋅ b ¯ ) = {\displaystyle \left(\mathbf {a} +\mathbf {b} \right)\cdot \left({\overline {\mathbf {a} }}\cdot {\overline {\mathbf {b} }}\right)=}
(Si applica la proprietà 10 )
= a ⋅ ( a ¯ ⋅ b ¯ ) + b ⋅ ( a ¯ ⋅ b ¯ ) = {\displaystyle =\mathbf {a} \cdot \left({\overline {\mathbf {a} }}\cdot {\overline {\mathbf {b} }}\right)+\mathbf {b} \cdot \left({\overline {\mathbf {a} }}\cdot {\overline {\mathbf {b} }}\right)=}
(Si applica la proprietà 9 )
= b ¯ ⋅ ( a ⋅ a ¯ ) + a ¯ ⋅ ( b ⋅ b ¯ ) = {\displaystyle ={\overline {\mathbf {b} }}\cdot \left(\mathbf {a} \cdot {\overline {\mathbf {a} }}\right)+{\overline {\mathbf {a} }}\cdot \left(\mathbf {b} \cdot {\overline {\mathbf {b} }}\right)=}
(Si applica la proprietà 7 )
= b ¯ ⋅ ( 0 ) + a ¯ ⋅ ( 0 ) = {\displaystyle ={\overline {\mathbf {b} }}\cdot \left(0\right)+{\overline {\mathbf {a} }}\cdot \left(0\right)=}
(Si applica la proprietà 5 )
= 0 + 0 = 0 {\displaystyle =0+0=0}
Sia ora c = a ¯ ⋅ b ¯ {\displaystyle \mathbf {c} ={\overline {\mathbf {a} }}\cdot {\overline {\mathbf {b} }}} ; otteniamo da I) e II) rispettivamente le equazioni:
I-bis) ( a + b ) + c = 1 {\displaystyle \left(\mathbf {a} +\mathbf {b} \right)+\mathbf {c} =1}
II-bis) ( a + b ) ⋅ c = 0 {\displaystyle \left(\mathbf {a} +\mathbf {b} \right)\cdot \mathbf {c} =0}
Unendo le proprietà 6) e 7) rispettivamente alle equazioni I-bis) e II-bis) si possono impostare i due sistemi equivalenti:
s1) { ( a + b ) + ( a + b ) ¯ = 1 ( a + b ) + c = 1 ⟹ c = ( a + b ) ¯ ⟹ c ¯ = ( a + b ) {\displaystyle {\begin{cases}\left(\mathbf {a} +\mathbf {b} \right)+{\overline {\left(\mathbf {a} +\mathbf {b} \right)}}=1\\\left(\mathbf {a} +\mathbf {b} \right)+\mathbf {c} =1\end{cases}}\implies \mathbf {c} ={\overline {\left(\mathbf {a} +\mathbf {b} \right)}}\implies {\overline {\mathbf {c} }}=\left(\mathbf {a} +\mathbf {b} \right)}
s2) { ( a + b ) ⋅ ( a + b ) ¯ = 0 ( a + b ) ⋅ c = 0 ⟹ c = ( a + b ) ¯ ⟹ c ¯ = ( a + b ) {\displaystyle {\begin{cases}\left(\mathbf {a} +\mathbf {b} \right)\cdot {\overline {\left(\mathbf {a} +\mathbf {b} \right)}}=0\\\left(\mathbf {a} +\mathbf {b} \right)\cdot \mathbf {c} =0\end{cases}}\implies \mathbf {c} ={\overline {\left(\mathbf {a} +\mathbf {b} \right)}}\implies {\overline {\mathbf {c} }}=\left(\mathbf {a} +\mathbf {b} \right)}
Adoperando nuovamente la sostituzione c = a ¯ ⋅ b ¯ {\displaystyle \mathbf {c} ={\overline {\mathbf {a} }}\cdot {\overline {\mathbf {b} }}} e, successivamente, la proprietà 3), si ottiene infine:
c ¯ = ( a + b ) ⟹ a ¯ ⋅ b ¯ ¯ = ( a + b ) ⟹ a ¯ ⋅ b ¯ = ( a + b ) ¯ {\displaystyle {\overline {\mathbf {c} }}=\left(\mathbf {a} +\mathbf {b} \right)\implies {\overline {{\overline {\mathbf {a} }}\cdot {\overline {\mathbf {b} }}}}=\left(\mathbf {a} +\mathbf {b} \right)\implies {\overline {\mathbf {a} }}\cdot {\overline {\mathbf {b} }}={\overline {\left(\mathbf {a} +\mathbf {b} \right)}}}
c.v.d.
Secondo teorema
Dimostrazione tabellare p {\displaystyle p} q {\displaystyle q} p ¯ {\displaystyle {\overline {p}}} q ¯ {\displaystyle {\overline {q}}} p ∧ q {\displaystyle p\wedge q} p ∧ q ¯ {\displaystyle {\overline {p\wedge q}}} p ¯ ∨ q ¯ {\displaystyle {\overline {p}}\vee {\overline {q}}} V V F F V F F V F F V F V V F V V F F V V F F V V F V V
Dimostrazione algebrica Questa sezione sull'argomento matematica è ancora vuota . Aiutaci a scriverla!
Voci correlate Algebra di Boole Funzione booleana Teorema di Shannon (elettronica) Teorema dell'assorbimento
Collegamenti esterni De Morgan, leggi di , in Enciclopedia della Matematica , Istituto dell'Enciclopedia Italiana , 2013. (EN ) De Morgan laws , su Enciclopedia Britannica , Encyclopædia Britannica, Inc. (EN ) Eric W. Weisstein, Leggi di De Morgan , su MathWorld , Wolfram Research. (EN ) Leggi di De Morgan , su Encyclopaedia of Mathematics , Springer e European Mathematical Society. (EN ) Denis Howe, DeMorgan's theorem , in Free On-line Dictionary of Computing . Disponibile con licenza GFDL Portale Matematica : accedi alle voci di Wikipedia che trattano di matematica