De Morgans lagar

De Morgans lagar är två slutledningsregler inom logik och boolesk algebra, uppkallade efter Augustus de Morgan på 1800-talet. Lagarna var kända redan på medeltiden och formulerades språkligt av William Ockham på 1400-talet. Reglerna, uttryckta som tautologier eller som teorem inom satslogiken, är

${\displaystyle {\begin{aligned}\neg (P\land Q)&\to \neg P\lor \neg Q\\\neg (P\lor Q)&\to \neg P\land \neg Q\end{aligned}}}$

Logisk operator (Logisk grind)
Negation (NOT) Konjunktion (AND, NAND) Disjunktion (OR, XOR, NOR) Implikation Ekvivalens (XNOR)
Se även
Logisk operator (konnektiv) Sanningsfunktion Sanningsvärdetabell De Morgans lagar
Denna tabell: visa • redigera

där ${\displaystyle P}$ och ${\displaystyle Q}$ är påståenden. Den första regeln är en negation av en konjunktion och den andra, en negation av en disjunktion.

Informellt kan lagarna skrivas

inte (P och Q) = inte P eller inte Q

inte (P eller Q) = inte P och inte Q

Reglerna har motsvarigheter inom mängdläran:

${\displaystyle (A\cap B)^{\complement }=A^{\complement }\cup B^{\complement }}$

${\displaystyle (A\cup B)^{\complement }=A^{\complement }\cap B^{\complement }}$

där ∩ är snittoperatorn och ∪ är unionsoperatorn.

Den allmänna formen är

${\displaystyle {\begin{aligned}{\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}}},\end{aligned}}}$

där I är en indexmängd och ${\displaystyle {\overline {A}}}$ är A:s negation.

De Morgans lagar har tillämpningar inom digitaltekniken vid konstruktion av logiska kretselement. De Morgans lagar motsvaras av logiska grindar enligt (1 = hög nivå, 0 = låg nivå):

=

${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle \neg (A\land B)}$ ${\displaystyle \neg A\lor \neg B}$ 0 0 1 1 0 1 1 1 1 0 1 1 1 1 0 0

=

${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle \neg (A\lor B)}$ ${\displaystyle \neg A\land \neg B}$ 0 0 1 1 0 1 0 0 1 0 0 0 1 1 0 0

Referenser

• Karl-Johan Bäckström, Diskret matematik, Studentlitteratur, Lund 1986.
• Raymond M Smullyan, First-Order Logic, Springer-Verlag, Berlin Heidelberg, New York, 1968.
• Elliott Mendelson, Elementary Logic, Oxford University Press, London 1965.
• Göran Hermerén, Satslogik, Studentlitteratur, Lund 1967.
• Per-Erik Danielsson, Digital teknik, Studentlitteratur, Lund 1974.