DeMorgan's theorem
<logic> A logical theorem which states that the complement of a
conjunction is the disjunction of the complements or vice versa. In symbols:
not (x and y) = (not x) or (not y)
not (x or y) = (not x) and (not y)
E.g. if it is not the case that I am tall and thin then I am either short
or fat (or both). The theorem can be extended to
combinations of more than two terms in the obvious
way.
The same laws also apply to sets, replacing logical complement with set
complement, conjunction ("and") with set intersection, and disjunction ("or")
with set union.
A (C) programmer might use this to re-write
if (!foo && !bar) ...
as
if (!(foo || bar)) ...
thus saving one operator application (though an optimising compiler should
do the same, leaving the programmer free to use
whichever form seemed clearest).
(1995-12-14)
Nearby terms:
demo mode « demon « Demon Internet Ltd. «
DeMorgan's theorem » demo version » Denis Howe »
Dennis Ritchie
|