De Morgans lagar

Från Wikipedia
Hoppa till: navigering, sök
AND ANSI.svg
 Logisk operator (Logisk grind
Se även

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

där och ä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:

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

Den allmänna formen är

där I är en indexmängd och ä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å):

NAND-gate-US.png = OR2N-gate-US.svg
0 0 1 1
0 1 1 1
1 0 1 1
1 1 0 0
NOR-gate-US.png = Not A and not B.png
0 0 1 1
0 1 0 0
1 0 0 0
1 1 0 0

Referenser[redigera | redigera wikitext]

  • 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.