Wetten van De Morgan

Uit Wikipedia, de vrije encyclopedie

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

Een eenvoudig voorbeeld illustreert deze wetten:

A = ik heb een fiets

B = ik heb een auto

De als eerste genoemde wet geeft in dit geval: "Zeggen dat het niet waar is dat ik zowel een auto als een fiets heb, is hetzelfde als zeggen dat ik geen fiets heb of geen auto." En de tweede: "Zeggen dat het niet waar is dat ik een auto of een fiets heb, is hetzelfde als zeggen dat ik geen fiets en geen auto heb."

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