Reducible Boolean functions
J. C. C. McKinsey · Bulletin of the American Mathematical Society · 1936
In this note I establish a condition that a Boolean function of n variables, say/, be reducible to a product of two Boolean functions f\ and / 2 , where ƒ involves variables not occurring in ft; and, similarly, that ƒ be reducible to /i+/2, or to f\ o/ 2 , or to /iA/ 2 .*These results are of interest in connection with the general theory of Boolean operations, since every Boolean operation can be regarded as a Boolean function.In order to state my results briefly, I use the symbol 0, which stands ambiguously for any one of the four operations X, +, o , A. Thus each of my theorems really comprises four theorems, which can be obtained from the given theorem by substituting first X for 0 throughout, then +, then o , and then A. The theorems now follow.be given, then a necessary and sufficient condition that there exist a g and an h, so that J\%ly ' ' ' y Xn) == g\%l) ' ' ' J %PJ VP ft\Xq, ' ' ' , X n ) j is that * The operation a o b is defined by a o b = ab' -\-a'b\ and the operation aAb is defined by aAb = ab-{-a'b'.These operations, which are mutually dual, are associative and commutative, and satisfy the further laws: (a o b) f = a o b' =aAb, a o l=aA0=a', a o a = aAa'=0, a oO=aAl=a.For a further discussion, see Bernstein's paper, Postulates f or Boolean algebra involving the operation of complete disjunction, to appear in the Annals of Mathematics.For a detailed treatment of a o b, see the two papers by M. H. Stone: Postulates for Boolean algebra and generalized Boolean algebra, American Journal of Mathematics, vol.57 (1935), pp.703-732, and Subsumption of the theory of Boolean algebras under the theory of rings, Proceedings of the National Academy of Sciences, vol.21 (1935), pp.103-105.Stone writes aAb for what I designate by a o b, and he does not discuss the relation which I denote by aAb.