Wetten van De Morgan

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

De wetten van De Morgan, of regels van De Morgan, zijn twee wetten in de formele logica die een verband leggen tussen de beide logische operatoren EN en OF en de negatie. Deze relatie wordt ook de dualiteit van De Morgan genoemd. Zij zijn genoemd naar de Britse wiskundige Augustus De Morgan, maar waren al eerder bekend.

Voor twee proposities A en B luiden de wetten:

niet (a en b) = (niet a) of (niet b)
niet (a of b) = (niet a) en (niet b)

In symbolen, waarbij EN door . wordt voorgesteld, OF door + en NIET door een overstreping, wordt dat:

\overline{A \cdot B} = \overline{A} + \overline{B}


\overline{A + B} = \overline{A}  \cdot \overline{B}

De wetten kunnen gegeneraliseerd worden voor meer dan twee proposities:

\overline{\prod_{i=1}^{n} P_i} = \sum_{i=1}^{n} \overline{P_i} ofwel: \overline{P_1 \cdot P_2 \cdot ... \cdot P_n} = \overline{P_1} + \overline{P_2} + ... + \overline{P_n}


\overline{\sum_{i=1}^{n} P_i} = \prod_{i=1}^{n} \overline{P_i} ofwel: \overline{P_1 + P_2 + ... + P_n} = \overline{P_1} \cdot \overline{P_2} \cdot ... \cdot \overline{P_n}

Voorbeeld[bewerken]

Een eenvoudig voorbeeld illustreert deze wetten:

A = ik heb een fiets
B = ik heb een auto
X = ik kan naar het werk rijden

De als eerste genoemde wet geeft in dit geval:

"Ik kan naar mijn werk rijden als ik een auto of een fiets heb."
X=A+B
\Longleftrightarrow
"Ik kan dus niet naar mijn werk rijden als ik geen auto en geen fiets heb."
\overline{X}=\overline{A} \cdot \overline{B}

Verband met andere logica[bewerken]

De formulering van De Morgan is beïnvloed door de ontwikkeling van de Booleaanse algebra door George Boole, waaruit blijkt dat De Morgan de wet eerder vond dan Boole. Nochtans waren soortgelijke observaties al gedaan door Aristoteles en was de wet gekend door Griekse en middeleeuwse denkers, zoals de logicus Willem van Ockham.

In de formele logica worden de wetten gewoonlijk geschreven als:

\neg(P\wedge Q)=(\neg P)\vee(\neg Q)
\neg(P\vee Q)=(\neg P)\wedge(\neg Q)

en in de verzamelingenleer als:

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