If you look at the identiti
es that appear in Boolean algebra
, you might notice something odd
: each identity appears twice
, but with AND
and OR swap
For instance, the distributive law is
x(y+z) = xy+xz
and if we swap +
we get the other distributive law
Coincidence? I think not!
x+yz = (x+y)(x+z)
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.