De Morgans lagar

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

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}}}$

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.