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.
- 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.
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.
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
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
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.
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 )
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
You may make paper or electronic copies of this essay
for your own enjoyment and edification.
If you wish to link to this article, try copying and pasting:
<a href="http://m3peeps.org/btqbo.htm">Binary, Trinary and Quaternary Boolean Operators</a>