De Morgans lagar

 Logisk operator (Logisk grind) 
  • Negation (NOT)
  • Konjunktion (AND, NAND)
  • Disjunktion (OR, XOR, NOR)
  • Implikation
  • Ekvivalens (XNOR)
Se även
Denna tabell: visa • redigera

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

¬ ( P ∧ Q ) → ¬ P ∨ ¬ Q ¬ ( P ∨ Q ) → ¬ P ∧ ¬ Q {\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 P {\displaystyle P} och Q {\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:

( A ∩ B ) ∁ = A ∁ ∪ B ∁ {\displaystyle (A\cap B)^{\complement }=A^{\complement }\cup B^{\complement }}
( A ∪ B ) ∁ = A ∁ ∩ B ∁ {\displaystyle (A\cup B)^{\complement }=A^{\complement }\cap B^{\complement }}

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

Den allmänna formen är

⋂ i ∈ I A i ¯ ≡ ⋃ i ∈ I A i ¯ , ⋃ i ∈ I A i ¯ ≡ ⋂ i ∈ I A i ¯ , {\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 A ¯ {\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å):

=
A {\displaystyle A} B {\displaystyle B} ¬ ( A ∧ B ) {\displaystyle \neg (A\land B)} ¬ A ∨ ¬ B {\displaystyle \neg A\lor \neg B}
0 0 1 1
0 1 1 1
1 0 1 1
1 1 0 0
=
A {\displaystyle A} B {\displaystyle B} ¬ ( A ∨ B ) {\displaystyle \neg (A\lor B)} ¬ A ∧ ¬ 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.