Binary, Trinary and Quaternary Boolean Operators

[version 1.0, February, 2004]

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


	5 + 7
the 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 = 12
In 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

Some operators work only on particular kinds of operands. For example, addition, subtraction, multiplication and division, as taught in elementary school, only work on numbers. Computer programmers are familiar with operators that only work on the numbers 0 and 1 and whose results are always a 0 or a 1. These are called Boolean operators, after George Boole (1815-1864), a mathematician who invented a system of algebra based entirely on the numbers 0 and 1. For example, the result of the "AND" operator is 1 only when both operands are 1. We can express that fact in a little table:

               - Result table for AND operator -

        Left Operand        Right Operand        Result
                   0                    0             0
                   0                    1             0
                   1                    0             0
                   1                    1             1
This 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             0
We 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            b4
Thus, 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 * 2
The "*" 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    1
Note 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 that takes two operands is called a "binary" operator. The "+" in "5 + 7" is a binary operator, even though the operands are not expressed using the binary number system. The Boolean operators we've been discussing so far have been binary Boolean operators. That is to say, they take two operands, each being either a 0 or a 1, and they yield a result which is either a 0 or a 1. Because of the three meanings of "binary" -- having two operands vs. being expressed with 0s and 1s vs. having as possible values only 0 and 1 -- we need to careful with our words. That's why I use the word "Boolean" to mean "having as possible values only 0 and 1".

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 = 7
can be read "twelve plus the negative of five is equal to seven." The "-" operates only on the "5". But in

                   12 - 5 = 7
the "-" 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  1
Again, 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

Trinary Boolean operators take three Boolean operands. (Trinary operators are sometimes called "ternary" operators.) Here is a table showing result columns for three such 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

The familiar notation for binary operators has us place a symbol for the operator between the two operands. When more than two operands are involved, we will write something like:

            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

We can put any number of operators into expressions such as:

             not( and( or( 1, 0 ), 0 ) ) = 1 
If 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          )
                            1

We 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 binary operator because it takes two operands. It is not a Boolean operator because its operands are not the values 0 or 1. The result of the LC operator is a trinary operator. To rephrase, LC is a binary operator which takes binary Boolean operators as operands and produces a trinary Boolean operator as a result. In the above definition, the notation "LC( bop1, bop2 )" stands for that resulting trinary operator. "LC( bop1, bop2 )( a, b, c )" stands for that trinary operator applied to operands a, b and c.


"Composable" Trinary Operators

For a while, I thought that perhaps any trinary Boolean operator could be expressed as the "left composition" of two binary Boolean operators. The following output from a computer program (cobop.c) convinced me that I was wrong:

	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

Remember, 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

Before answering that question, I need to show another style of displaying the results of a binary Boolean operation:

                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>

[Go to m3peeps.org home page]

Read Manifesto for the Peoples of the Third Millennium