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.