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 *x*_{1},...,*x*_{n} 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^{-}(*x*_{1},...,*x*_{n}) = A(*x*_{1}',...,*x*_{n}')'.

The theorem follows immediately.