Boolean Algebra

Back to the Main Page

A 4-basis for Boolean algebra (BA) in terms of join (v), meet (^), and complement (c).

    x v (y v z) = y v (x v z).  % AJ
    x ^ y = c(c(x) v c(y)).     % DM
    x v c(x) = y v c(y).        % ONE
    (x v c(y)) ^ (x v y) = x.   % CUT
Here are proofs of distributivity, modularity, CC, and B1 from the BA 4-basis.
    otter < > BA1.out
    otter < > BA2.out
    otter < > BA3.out
Independence of the BA 4-basis is open. In particular, we have not been able to find a proof or countermodel of
    { AJ, DM, CUT } => ONE.
The simplest multiequation basis we know of for BA in terms of join and complement is the following, due to C.A. Meredith [13].
    c(c(x) v y) v x = x.                  % MER_1
    c(c(x) v y) v (z v y) = y v (z v x).  % MER_2
The Robbins 3-basis for BA (in terms of join and complement) is the following [12].
    (x v y) v z = x v (y v z).       % AJ2
    x v y = y v x.                   % CJ
    c(c(x v c(y)) v c(x v y)) = x.   % Robbins