Boolean functions' invariant properties.

From: conesetter (conesetter_at_btopenworld.com)
Date: 05/28/04 

Date: 28 May 2004 10:12:00 -0700

A Boolean function can be represented in two normal forms and in many
others. This is an attempt to find for any Boolean function a system
of invariants, a set of features which characterize the function, and
which all its representations have in common.
  Consider a Boolean formula in n distinct variables, each occurring
once only. Assume for now that the complement or negation symbol ¬ is
absent. For each pair of variables, say x and y, there is a smallest
bracket which contains them both, their linking bracket, and has a
function symbol, their linking function or link which is one of two,
say A (cap or intersection or conjunction) and U (cup or union or
disjunction).
  The essential property is that for any two variables their linking
function remains the same under all Boolean transformations of the
formula.
  Notation: Letters from the end of the alphabet represent variables,
letters from the beginning represent formulas.
  If x, y and z are respectively in a, b and c then their three links
remain the same when (aAb)Uc is replaced under the distributive law by
(aUc)A(bUc) and conversly. Similarly for the dual formula. The effects
of the commutative and associative laws are trivially null.
  Note that under applications of the distributive law some
sub-formulas and therefore also their contained variables get
duplicated but the duplications retain the same links. Our derivation
of links applies where the start-formula has no duplications. Formulas
otherwise containing duplications may be regarded as having been got
from repetition-free start-formulas in a suitably greater number of
variables by introducing identifying conditions on some of its
variables. So their existence does not indicate a deficiency in the
theory.
  If the variables are x1, x2 ...xn let the link between xh and xk be
Lhk. These L's, which have values A and U, are the invariants of the
Boolean function. Any repetition-free formula for the function
determines them uniquely. They can be displayed in a table or matrix,
putting the variables along top or bottom and side and the links in
the body. The table is symmetrical with the leading diagonal empty.
  We consider how to get a disjunctive normal form from the tabular
form. A set of variables will be called fellows under A if A is the
link for every pair of variables in the set. It will be called
complete if it is not contained in any larger set of fellows under A.
A variable with no fellows forms a one-element complete set. Obtain
all complete sets of fellows under A and form them into conjunctions.
A disjunction of these conjunctions is a disjunctive normal form
equivalent to the tabular form since the tabular form can be recovered
from it.
  A dual definition and process yields a conjunctive normal form.
  An example: ((wAx)Uy)Az. The tabular form is
    w x y z
 w A U A
 x A U A
 y U U A
 z A A A
  Complete sets under A are w.x,z and y,z giving the DNF
(wAxAz)U(yAz).
  Complete sets under U are w,y and x,y and z giving the CNF
(wUy)A(xUy)Az.
  Now to re-introduce the complement or negation function ¬. Since
¬(aUb) is equivalent to ¬aA¬b, and dually, the above does not work
when a link A or U is in the scope of ¬. However the equivalences just
noted allow ¬ to be pushed down to the variables so then one has U and
A applied only to literals, that is to variables and their
complements. Then the above theory applies to formulas made up of
literals.
  
  Copyright May2004 conesetter. References are welcome, use requires
consent.