Composition of Boolean Operators

(June, 2003)

Note: Most of the material in this essay is now covered in my paper Binary, Trinary and Quaternary Boolean Operators , which I believe is more readable.

A Boolean operator is one whose operands are 1s or 0s. The words unary, binary, trinary, quaternary and quintary refer to the number of operands: 1, 2, 3, 4 and 5, respectively. (I hope I'm using these words correctly...)

I ran across an interesting question on Slashdot some months ago. Consider the trinary operation "bit voting": If the majority of bits are 1, then the result is 1. If the majority of bits are 0, then the result is 0. Now express that operation in terms of AND (&) and OR (|). If the operand bits are a, b and c, then the answer is: a&b | b&c | a&c. I came up with the convoluted: a & ( b|c ) | b&c.

I began to wonder if the answer could be expressed as the composition of two binary operators, like this:

( a bop1 b ) bop2 c

Turns out, it can't be. Before I explain why, I must digress.

Unary Operators

We can illustrate the fact that there are four distinct unary operators as follows:

operand 00 01 10 11 0 0 0 1 1 1 0 1 0 1

The numerical headings represent the operators. We could give names to these operators such as Reset (00), Leave Alone (01), Invert (10) and Set (11). We can express an entry in the above table with function notation: Set( 0 ) = 1. or: LeaveAlone( 1 ) = 1. or "10"( 0 ) = 1. The obvious point is that a column of values is the same as the column heading turned on its edge.

Binary Operators

The exercise becomes a bit more interesting when we consider binary operators:

operands 0000 0001 0010 0011 0100 0101 0110 0111 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 operands 1000 1001 1010 1011 1100 1101 1110 1111 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1

Some of the above are old favorites: "0001" is our good friend AND and "0111" is OR. "0110" is "exclusive or," or XOR as we programmers say. Each column represents a distinct binary Boolean operation. Most do not have common names.

We can construct a formula for "number of distinct operators" given "number of Boolean operands":

# of operators = 2 ** (# of rows in table)
# of rows in table = 2 ** # of operands

OR:

operators = 2 ** ( 2 ** operands )

So, given 1 operand, there are 2 ** ( 2 ** 1 ) = 4 operators. For 2 operands, there are 2 ** ( 2 ** 2 ) = 16 operators. There are 256 trinary operators, 65,536 quaternary operators and 4,294,967,296 quintary operators. Six operands would yield about 1.84 * 10**19 possible operators. My brain shuts down at any number of operands greater than 5. The Perl programming language, which I used for the calculations in this paragraph, shuts down at 10 operands, giving the result "inf", although, technically, pdfe (pretty darn friggin' enormous), would be more accurate.

Trinary Operators

Let's look at part of the table of trinary operators:

operands. 00000000 . . . 00010111 . . . 11111111 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 0 0 1 0 1 1 0 1 1 1 0 0 0 0 1 1 0 1 0 1 1 1 1 0 0 1 1 1 1 1 0 1 1

Only three operators are illustrated, the middle one being the "voting" operator. The main point to keep in mind is that a trinary boolean operator can be represented by a string of eight binary digits. We can, in effect, use the three operand bits as an index into the eight operator bits to get the result of the operation for a particular combination of operands. The C code for an arbitrary trinary operation might look like this:

result = ( 0x80 >> operands ) & operator;

For an arbitrary binary operation, the code might be:

result = ( 0x08 >> operands ) & operator;

Composition of Operators

What I mean by "composition" is: Take any two binary operators, bop1 and bop2, then construct a table as follows:

( 0 bop1 0 ) bop2 0 = b0 ( 0 bop1 0 ) bop2 1 = b1 ( 0 bop1 1 ) bop2 0 = b2 ( 0 bop1 1 ) bop2 1 = b3 ( 1 bop1 0 ) bop2 0 = b4 ( 1 bop1 0 ) bop2 1 = b5 ( 1 bop1 1 ) bop2 0 = b6 ( 1 bop1 1 ) bop2 1 = b7

The b0...b7 can be regarded as a trinary operator (top) "composed" of the binary operators bop1 and bop2 so that for any boolean operands a, b and c, we would have

top( a, b, c ) = ( a bop1 b ) bop2 c

or, to use function style notation on both sides,

top( a, b, c ) = bop2( bop1( a, b ), c )

Since there are 16 binary boolean operators, there are 16 * 16 = 256 ways of "composing" them. (What happens when you shift the parentheses is left as an exercise for the reader. ;) ) Anyway, note that sometimes different combinations of bop1 and bop2 will compose to the same thing. For example, if bop2 is "1111", then the result will always be "11111111" regardless of what bop1 is. Thus, at least 16 of the 256 different compositions are equivalent to each other. Since there are 256 trinary boolean operators, some will not be decomposable into two binary boolean operators. In particular, the "voting" operator is not decomposable. I would explain this fact as follows: Once you compute bop1( a, b ), it is impossible for c to interact separately with a and b. Such interaction is essential in the "voting" operation. (That is an "explanation," not a "proof!")

Table of Compositions

I wrote a program to illustrate how often each trinary boolean operator gets composed by different combinations of binary boolean operators. The code is in the file cobop.c. Here is the output:

22 02 02 02 02 02 .. .. 02 .. 02 .. 02 .. .. 02 02 02 .. .. 02 02 .. .. .. .. .. .. .. .. .. .. 02 .. 02 .. .. .. .. .. 02 .. 02 .. .. .. .. .. 02 .. .. 02 .. .. .. .. .. .. .. .. 02 .. .. 02 02 02 .. .. 02 02 .. .. .. .. .. .. .. .. .. .. 02 02 .. .. 02 22 02 02 .. 02 02 .. .. 02 .. 02 .. .. .. .. .. 02 02 .. .. 02 02 .. .. .. .. .. .. .. .. .. .. 02 .. 02 .. .. .. .. .. 02 .. 02 02 .. 02 .. .. .. .. .. 02 .. 02 .. .. .. .. .. .. .. .. .. .. 02 02 .. .. 02 02 .. .. .. .. .. 02 .. 02 .. .. 02 02 .. 02 02 22 02 .. .. 02 02 .. .. .. .. .. .. .. .. .. .. 02 02 .. .. 02 02 02 .. .. 02 .. .. .. .. .. .. .. .. 02 .. .. 02 .. .. .. .. .. 02 .. 02 .. .. .. .. .. 02 .. 02 .. .. .. .. .. .. .. .. .. .. 02 02 .. .. 02 02 02 .. .. 02 .. 02 .. 02 .. .. 02 02 02 02 02 22

The row headings would be the first four bits of the trinary operator. The column headings would be the last four bits. The ".." entries are for zero values and are used simply to make the non-zero values stand out better.

I'm not going to hurt my brain by thinking too hard about what it all means, but I do like the looks of it! And, of course, it got me thinking about quaternary boolean operators: how they can be composed, how the composition tables could be displayed, etc.

Surfing the Fourth Dimension

Since it takes 16 bits to represent a quaternary operator, it is possible to place them in a sort of four dimensional table -- 4 bits per dimension. Two dimensions define a plane. The values within that plane can be displayed on a two dimensional computer screen. My coqo.c ("composition of quaternary operators") does that. If you have the "ncurses" library on your machine, you can download the source and compile it. By the way, for any readers who have trouble with "four dimensions," I recommend the short novel "Flatland: a romance of many dimensions" by Edwin A. Abbott.

The output does, in some odd way, look like the above output for the trinary operators. What I'd like to do some day would be to study 3D graphics and present "cubic slices" of the 4D table. Might be interesting. Also fun would be to have a 16 gigabyte machine and do some kind of study of quintary operators. I'm sure that 5 years from now such things will be available at K-Mart for under $200, so I'll just wait...

The Machine Itself Rages Against Reductionism

Interestingly, most trinary operators cannot be composed from two binary operators. Most quaternary operators cannot be composed from a trinary and a binary operator. If you need the proof for this and you can't figure it out yourself, send me an e-mail.

So what are the operators of life and how many and what kind of operands do they take? Something to think about. Maybe life really is too complicated to be broken down into a few neat little absolutist formulas. So says my computer!

If you wish to link to this article, try copying and pasting:

<a href="http://m3peeps.org/cobop.htm">Composition of Boolean Operators</a>

[Go to m3peeps.org home page]

Read Manifesto for the Peoples of the Third Millennium