Boolean Algebras Canonically Defined - Boolean Algebras of Boolean Operations

Boolean Algebras of Boolean Operations

The n-ary Boolean operations themselves constitute a power set algebra 2W, namely when W is taken to be the set of 2n valuations of the n inputs. In terms of the naming system of operations nf_i where i in binary is a column of a truth table, the columns can be combined with Boolean operations of any arity to produce other columns present in the table. That is, we can apply any Boolean operation of arity m to m Boolean operations of arity n to yield a Boolean operation of arity n, for any m and n.

The practical significance of this convention for both software and hardware is that n-ary Boolean operations can be represented as words of the appropriate length. For example each of the 256 ternary Boolean operations can be represented as an unsigned byte. The available logical operations such as AND and OR can then be used to form new operations. If we take x, y, and z (dispensing with subscripted variables for now) to be 10101010, 11001100, and 11110000 respectively (170, 204, and 240 in decimal, 0xaa, 0xcc, and 0xf0 in hexadecimal), their pairwise conjunctions are x∧y = 10001000, y∧z = 11000000, and z∧x = 10100000, while their pairwise disjunctions are x∨y = 11101110, y∨z = 11111100, and z∨x = 11111010. The disjunction of the three conjunctions is 11101000, which also happens to be the conjunction of three disjunctions. We have thus calculated, with a dozen or so logical operations on bytes, that the two ternary operations

(x∧y)∨(y∧z)∨(z∧x)

and

(x∨y)∧(y∨z)∧(z∨x)

are actually the same operation. That is, we have proved the equational identity

(x∧y)∨(y∧z)∨(z∧x) = (x∨y)∧(y∨z)∧(z∨x),

for the two-element Boolean algebra. By the definition of "Boolean algebra" this identity must therefore hold in every Boolean algebra.

This ternary operation incidentally formed the basis for Grau's ternary Boolean algebras, which he axiomatized in terms of this operation and negation. The operation is symmetric, meaning that its value is independent of any of the 3! = 6 permutations of its arguments. The two halves of its truth table 11101000 are the truth tables for ∨, 1110, and ∧, 1000, so the operation can be phrased as if z then x∨y else x∧y. Since it is symmetric it can equally well be phrased as either of if x then y∨z else y∧z, or if y then z∨x else z∧x. Viewed as a labeling of the 8-vertex 3-cube, the upper half is labeled 1 and the lower half 0; for this reason it has been called the median operator, with the evident generalization to any odd number of variables (odd in order to avoid the tie when exactly half the variables are 0).