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 i satslogiken skrivs:

\begin{align}
  \neg (P \and Q) &\to \neg P \or \neg Q \\
   \neg (P \or Q) &\to \neg P \and \neg Q
\end{align}

där P and 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 uttryckas som:

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:

(A\cap B)^\complement=A^\complement\cup B^\complement
(A\cup B)^\complement=A^\complement\cap B^\complement

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

NAND-gate-US.png = OR2N-gate-US.svg
A B A NAND B NOT-A OR NOT-B
H H L L
H L H H
L H H H
L L H H
NOR-gate-US.png = Not A and not B.png
A B A NOR B NOT-A AND NOT-B
H H L L
H L L L
L H L L
L L H H


Källor[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.