Boolean Algebras Canonically Defined - Truth Tables

Truth Tables

The finitary operations on {0,1} may be exhibited as truth tables, thinking of 0 and 1 as the truth values false and true. They can be laid out in a uniform and application-independent way that allows us to name, or at least number, them individually. These names provide a convenient shorthand for the Boolean operations. The names of the n-ary operations are binary numbers of 2n bits. There being 22n such operations, one cannot ask for a more succinct nomenclature! Note that each finitary operation can be called a switching function.

This layout and associated naming of operations is illustrated here in full for arities from 0 to 2.

These tables continue at higher arities, with 2n rows at arity n, each row giving a valuation or binding of the n variables x₀,…x_n−1 and each column headed nf_i giving the value nf_i(x₀,…,x_n−1) of the i-th n-ary operation at that valuation. The operations include the variables, for example 1f₂ is x₀ while 2f₁₀ is x₀ (as two copies of its unary counterpart) and 2f₁₂ is x₁ (with no unary counterpart). Negation or complement ¬x₀ appears as 1f₁ and again as 2f₅, along with 2f₃ (¬x₁, which did not appear at arity 1), disjunction or union x₀∨x₁ as 2f₁₄, conjunction or intersection x₀∧x₁ as 2f₈, implication x₀→x₁ as 2f₁₃, exclusive-or symmetric difference x₀⊕x₁ as 2f₆, set difference x₀−x₁ as 2f₂, and so on.

As a minor detail important more for its form than its content, the operations of an algebra are traditionally organized as a list. Although we are here indexing the operations of a Boolean algebra by the finitary operations on {0,1}, the truth-table presentation above serendipitously orders the operations first by arity and second by the layout of the tables for each arity. This permits organizing the clone of all Boolean operations in the traditional list format. The list order for the operations of a given arity is determined by the following two rules.

(i) The i-th row in the left half of the table is the binary representation of i with its least significant or 0-th bit on the left ("little-endian" order, originally proposed by Alan Turing, so it would not be unreasonable to call it Turing order).

(ii) The j-th column in the right half of the table is the binary representation of j, again in little-endian order. In effect the subscript of the operation is the truth table of that operation. By analogy with Gödel numbering of computable functions one might call this numbering of the Boolean operations the Boole numbering.

When programming in C or Java, bitwise disjunction is denoted x|y, conjunction x&y, and negation ~x. A program can therefore represent for example the operation x∧(y∨z) in these languages as x&(y|z), having previously set x = 0xaa, y = 0xcc, and z = 0xf0 (the "0x" indicates that the following constant is to be read in hexadecimal or base 16), either by assignment to variables or defined as macros. These one-byte (eight-bit) constants correspond to the columns for the input variables in the extension of the above tables to three variables. This technique is almost universally used in raster graphics hardware to provide a flexible variety of ways of combining and masking images, the typical operations being ternary and acting simultaneously on source, destination, and mask bits.