= De Morgan dual of a Boolean function
{c}
{title2=$f^*(x)=\neg f(\neg x)$}
= De Morgan dual
{c}
{synonym}
For a <Boolean function> $f$ of $n$ input <bits>, define its <De Morgan dual> by complementing every input, applying $f$, and complementing the output:
$$
f^*(x_1,\ldots,x_n)=1-f(1-x_1,\ldots,1-x_n).
$$
<De Morgan's laws> say that the <De Morgan dual> of <logical conjunction> is <logical disjunction>, and conversely. The constant zero <Boolean function> becomes constant one. This is different from merely negating the output: for AND, output <logical negation> gives one at $(0,0)$, whereas the <De Morgan dual> gives zero there.
Taking the <De Morgan dual> twice restores the original <Boolean function>:
$$
(f^*)^*(x)=1-\bigl(1-f(x)\bigr)=f(x).
$$
Here each input is complemented twice as well. For a <Boolean formula> built from AND, OR, NOT and constants, its <De Morgan dual> can therefore be obtained by exchanging AND with OR and zero with one throughout, leaving input names and NOT in place. A structural <induction> proves the rule: it holds for an input and each constant, <De Morgan's laws> handle the two binary <logical connectives>, and double <logical negation> handles NOT. This symmetry lets one translate a complex test systematically instead of guessing where its failures occur.
Back to article page
