Indietro

ⓘ Teoremi di De Morgan




Teoremi di De Morgan
                                     

ⓘ Teoremi di De Morgan

I teoremi di De Morgan, o leggi di De Morgan sono relativi alla logica booleana e stabiliscono relazioni di equivalenza tra gli operatori di congiunzione logica "and" e "or". Sono utilizzati per lanalisi di circuiti logici.

                                     

1. 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}.

Limmediata generalizzazione a un numero 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: