Wetten van De Morgan

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

Voor twee proposities ${\displaystyle A}$ en ${\displaystyle B}$ luiden de wetten:

niet (${\displaystyle A}$ en ${\displaystyle B}$) = (niet ${\displaystyle A}$) of (niet ${\displaystyle B}$)

niet (${\displaystyle A}$ of ${\displaystyle B}$) = (niet ${\displaystyle A}$) en (niet ${\displaystyle B}$)

In symbolen, waarbij de conjunctie 'en' door een · wordt weergegeven, de disjunctie 'of' door een + en de negatie 'niet' door een overstreping, wordt dat:

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

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

De wetten kunnen worden gegeneraliseerd voor meer dan twee proposities:

${\displaystyle {\overline {\prod _{i=1}^{n}P_{i}}}=\sum _{i=1}^{n}{\overline {P_{i}}}}$ ofwel: ${\displaystyle {\overline {P_{1}\cdot P_{2}\cdot \ldots \cdot P_{n}}}={\overline {P_{1}}}+{\overline {P_{2}}}+\ldots +{\overline {P_{n}}}}$

${\displaystyle {\overline {\sum _{i=1}^{n}P_{i}}}=\prod _{i=1}^{n}{\overline {P_{i}}}}$ ofwel: ${\displaystyle {\overline {P_{1}+P_{2}+\ldots +P_{n}}}={\overline {P_{1}}}\cdot {\overline {P_{2}}}\cdot \ldots \cdot {\overline {P_{n}}}}$

Voorbeeld

Een eenvoudig voorbeeld illustreert deze wetten:

${\displaystyle A}$ = ik heb een fiets

${\displaystyle B}$ = ik heb een auto

${\displaystyle 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."

${\displaystyle X=A+B}$

${\displaystyle \Longleftrightarrow }$

"Ik kan dus niet naar mijn werk rijden als ik geen auto en geen fiets heb."

${\displaystyle {\overline {X}}={\overline {A}}\cdot {\overline {B}}}$

Verband met andere vormen van logica

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 later 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.^[bron?]

De wetten worden in de wiskundige logica gewoonlijk geschreven als:

${\displaystyle \neg (P\wedge Q)=(\neg P)\vee (\neg Q)}$

${\displaystyle \neg (P\vee Q)=(\neg P)\wedge (\neg Q)}$

en in de verzamelingenleer als:

${\displaystyle (A\cap B)^{c}=A^{c}\cup B^{c}}$

${\displaystyle (A\cup B)^{c}=A^{c}\cap B^{c}}$

Bronvermelding

• Dit artikel of een eerdere versie ervan is een (gedeeltelijke) vertaling van het artikel De Morgan's laws op de Engelstalige Wikipedia, dat onder de licentie Creative Commons Naamsvermelding/Gelijk delen valt. Zie de bewerkingsgeschiedenis aldaar.