Binary, Trinary and Quaternary Boolean Operators

For a computer programmer, much of mathematics is about "operators" and "operands." In the expression

5 + 7the plus sign ("+") is the "operator." The "operands" are the numbers 5 and 7. We think of the "operator" as "doing something" and of the "operands" as things to which something is "done." You "do addition" to the numbers 5 and 7 and the "result" is the number 12.

Computer programmers are familiar with an "assignment operator," which looks like this in some programming languages:

NUM2 = 12In that case, the left operand, NUM2, is a "variable" and the right operand, 12, is the value that is to be assigned to the variable.

Different Kinds of Operands

- Result table for AND operator - Left Operand Right Operand Result 0 0 0 0 1 0 1 0 0 1 1 1This makes sense if we think of the number 1 as standing for "true" and the number 0 as standing for "false." If I combine two statements with the word "and," the combined statement is true only if both parts of it are true. "My car is blue and it is a Ford" would be false if my car were red or a Chevy. The "OR" operator is much more generous:

- Result table for OR operator - Left Operand Right Operand Result 0 0 0 0 1 1 1 0 1 1 1 1"My car is blue OR it is a Ford" would be true if at least one part of the statement were true. Now, in common speach, we often use the word "or" exclusively. In other words, we mean that the first part or the second part of the combined statement is true, but that the two parts are not both true. In the computer business, that kind of "or" is called "exclusive or" or "xor" (pronounced "EX-or") for short:

- Result table for XOR operator - Left Operand Right Operand Result 0 0 0 0 1 1 1 0 1 1 1 0We can make a general sort of operator table like this:

- Result table for XXX operator - Left Operand Right Operand Result 0 0 b1 0 1 b2 1 0 b3 1 1 b4Thus, if we ask how many operators there are of the kind we have been discussing, the answer is: as many as the number of different possible result columns in the above table. How do we figure that out?

First, a definition: A "bit" is a "binary digit." It is "binary" because it can have only two possible values: 0 or 1. It is also "binary" because a string of "bits" can express a number in the base-2 numbering system. Our familiar number system is "base-10" and makes use of the ten digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9. The "binary number system" uses only the digits 0 and 1.

The result column in the above table contains four bits which we call b1, b2, b3 and b4. If we were only dealing with b1, there would be only two possibilities: 0 or 1. If we have b1 and b2, there are twice as many possibilities: each possibility of b1 followed by a 0 and then each possibility of b1 followed by a 1. If we tack on b3, we have again twice as many possibilities, and so on with b4. Thus, the total number of possible different result columns is:

2 * 2 * 2 * 2The "*" stands for "multiply." (Most computer keyboards don't have the "thin X" that school textbooks use.) "2 * 2 * 2 * 2" is also called "two to the fourth power" because there are 4 numbers 2 all multiplied together. A short way of writing that is "2**4". The two asterisks together mean "to the power of." In general, at least in this article you are reading, "X**Y" means "take Y numbers X and multiply them all together."

Some of the 16 different operators are boring. One operator (which I call "SET") simply gives a result of 1 regardless of what the operands are. Another ("RESET") always gives a result of 0. Here is a complete table of Boolean operators with two operands:

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 1Note that I've used bit sequences instead of names for the column headings. Also note that the headings are, in a manner of speaking, the columns they head turned over on their sides. Thus, any Boolean operator with two operands can be represented by a sequence of four bits. "0000" is RESET, "0111" is OR, "0110" is XOR, etc.

Different Numbers of Operands

An operator taking only one operand is called a "unary" operator. In ordinary arithmatic, the minus sign ("-") can represent the binary operation of subtraction or it can represent the unary operation "take the negative of." Thus,

12 + -5 = 7can be read "twelve plus the negative of five is equal to seven." The "-" operates only on the "5". But in

12 - 5 = 7the "-" is a binary operator, acting on both the 12 and the 5.

Here is a table of unary Boolean operators:

operand 00 01 10 11 0 0 0 1 1 1 0 1 0 1Again, 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). "Invert" is sometimes called "not" and sometimes symbolized with a tilda ("~"). Thus, we might write "~1 = 0" or "~0 = 1".

With the binary Boolean operators, we had 4 distinct sets of operands. There are, rather obviously, only two "distinct sets of operands" for unary Boolean operators. Thus, the number of different unary Boolean operators is 2**2, or 4.

Trinary Boolean 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"00000000" is a trinary version of RESET; "11111111" is a trinary SET. The middle column, headed by "00010111" is for what is called the "majority operator" because the result is whatever digit forms a "majority" among the operand bits.

Note that, with three operands, we have eight distinct sets of operands. So the number of different trinary Boolean operators is 2**8, which is 256. If we take into account these facts:

number of distinct sets of operands = 2**(number of operands) number of operators = 2**(number of distinct sets of operands)we come up with the formula:

number of operators = 2**( 2**( number of operands ) )We can see that the number of possible operators increases rapidly with the number of operands:

kind of number of number of Boolean operator operands operators unary 1 4 binary 2 16 trinary 3 256 quaternary 4 65,536 quintary 5 4,294,967,296

Notation

quat-op-X( o1, o2, o3, o4 )which would be for some quaternary operator called "quat-op-X" applied to the operands o1, o2, o3 and o4. We can also use that style for unary, binary or trinary operators:

not( 0 ) = 1 and( 0, 1 ) = 0 majority( 0, 1, 0 ) = 0

Operating on operators

not( and( or( 1, 0 ), 0 ) ) = 1If you actually had to compute that, you would have to work "from the inside out," something like this:

not( and( or( 1, 0 ), 0 ) ) not( and( 1 , 0 ) ) not( 0 ) 1We can define operators in terms of other operators. For example, we might define an "all or nothing" binary Boolean operator, AON, which would give a result of 1 if both operands were 0 or if both operands were 1:

for Boolean values A and B, aon( A, B ) is defined as: not( xor( A, B ) )We can even define operators that operate on other operators. For example, I'll define what I will call "the left composition operator," LC for short, of two binary operators, bop1 and bop2, as follows:

LC( bop1, bop2 ) is the trinary operator such that: LC( bop1, bop2 )( a, b, c ) = bop2( bop1( a, b ), c )We must be careful with our words here. LC is a

"Composable" Trinary Operators

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 22Remember, a trinary Boolean operator has 8 different possible operand sets, so it can be represented by a sequence of 8 bits, as in the "result tables" earlier in this article. In the above table, the row headings would be the first four bits of a result column and the column headings would be the last four bits. The entries in the table are the number of times the particular trinary operator shows up as the Left Composition of two binary Boolean operators. I put ".." in the table instead of "0" to make the overall pattern stand out.

The table shows us that most trinary Boolean operators are not "left composable" and that most of the ones that are "left composable" can be composed in exactly two different ways. This led me to wonder: Given one pair of binary Boolean operators that compose to a trinary operator, how can we find the other pair that compose to the same thing? In other words, given binary Boolean operators bop1 and bop2, find different operators bop3 and bop4 such that:

LC( bop1, bop2 ) = LC( bop3, bop4 )

Square Result Tables

0 1 --------- 0 | 0 | 0 | |---|---| 1 | 0 | 1 | ---------The row headings are for the first operand, the column headings are for the second operand. Now I can introduce a unary operator which operates on a binary operator and yields another binary operator. If BOP is a binary operator with the table:

0 1 --------- 0 | a | b | |---|---| 1 | c | d | ---------then row_switch( BOP ) has the table

0 1 --------- 0 | c | d | |---|---| 1 | a | b | ---------We need one more unary operator. If the result table entries for binary operator BOP are a, b, c and d, then the complement of BOP, or comp( BOP ), would have table entries ~a, ~b, ~c and ~d. In other words, turn all the zeros to ones and all the ones to zeros.

We can now answer the main question:

LC( bop1, bop2 ) = LC( comp( bop1 ), row_switch( bop2 ) )I leave the illustration of the above to the reader.

Copyright © 2004

Share on Twitter:

Tweet

HTML type link:

<a href="http://m3peeps.org/btqbo.htm">Binary, Trinary and Quaternary Boolean Operators</a>