If you look at the
identities that appear in
Boolean algebra, you might notice something
odd: each identity appears
twice, but with
AND and
OR swapped!
For instance, the distributive law is
x(y+z) = xy+xz
and if we swap
+ and
. we get the other distributive law
x+yz = (x+y)(x+z)
Coincidence? I think not!
In fact, this duality can be proven to be correct. Specifically, we may state and prove:
THEOREM: Let A=B be some boolean identity (that is, A and B are both formulae in variables x1,...,xn that are equal for all assignments of values). Then A-=B- is also an identity, where A- denotes the formula you get from A by rewriting + as . and . as + (brackets should be added to preserve our normal notions of operator precedence).
The proof is actually trivial: just recurse along the structure of each formula, applying De Morgan's Laws at each step, to prove
A-(x1,...,xn) = A(x1',...,xn')'.
The theorem follows immediately.