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.

Log in or register to write something here or to contact authors.