Premises of Boolean Logic

Recommended Prior Reading:


Introduction

In the mid 19th century, British mathematician George Boole formalized a system of two-state logic that would ultimately be named after him. Boolean logic is binary; that is, any given variable or constant has only two possible values: true or false. True is often represented as one (1) and false as zero (0), as these are mathematically convenient numbers and useful shorthand.

Boolean logic is indispensable for the description and design of discrete binary systems. Discrete in this context means finite; having a limited set of fixed possibilities. This property is important and interesting because discrete systems can be described with whole numbers (integers). Furthermore, the number of integers required to fully describe such a system is always limited and enumerable -- though the number may be huge, there is never a case of infinite possibilities. This is to be contrasted with continuous or analog systems, which require arbitrarily precise fractional numbers (so-called "real" numbers).

Modern computer systems are discrete and binary; all information is coded into states of the machine represented by a very large collection of boolean variables. In the context of computer memory or processing, each one of those boolean variables is called a bit (binary digit).

Since one bit by itself is just a simple on/off switch which can only represent two states, multiple bits are generally packed together into a group. Eight contiguous bits are called a "byte", and some number of bytes taken together constitute a "word". (How many depends on the computer architecture, but it is usually to 2, 4, 8 or 16 bytes.) Collecting bits together in this manner allows one to create compound variables which can represent many different states. The byte, for instance, can represent 256 states, as two to the eighth (28) is 256. The growth in possible states is exponential in base two, such that when you move to two bytes (16 bits) you already have 216 = 65,536 states available. Each of these distinct states can be assigned a meaning, such that having more states indicates the ability to store more information. Naturally, we do not need to store all information in the same variable and in practice do not do so. Instead, computer memory is organized into a very large array of bytes or words, and each individual one can be used independently.

But how do we use these bits and bytes to do useful work? In ordinary algebra, we are accustomed to using operations such as addition, subtraction, multiplication, and division to manipulate numbers and achieve meaningful results. Boolean algebra has an analogous set of core operations. The basic six Boolean operations are named NOT, AND, OR, XOR, NAND, and NOR. The names may sound strange at first, but will make sense as the logic is revealed.

Operation NOT

NOT is the inversion or opposition operator. It takes the current state of a bit and toggles it to the other state. If it is true, it becomes false; if false, it becomes true. For an array of bits such as a byte or word, the effect of the operation is to apply the inversion across each bit in the input operand. For example:

Input: %1 = 1
   NOT %1 = 0
   NOT  1 = 0

Input: %1001 = 9

   NOT %1001 = %0110
   NOT 9 = 6

Input: %1100 = 12

   NOT %1100 = %0011
   NOT 12 = 3

Input: %10101010 = 170

   NOT %10101010 = %01010101
   NOT 170 = 85

The use of the percentage sign prefix in these examples is an indication of a binary (base-2) number. Numbers without any particular identifier should be presumed to be base-10 (decimal).

NOT is an unary operator, meaning that it accepts one input (as shown in the examples). As with all normal boolean or arithmetic operations, it produces one output. NOT happens to be the only one of the primary boolean operators which is unary; all the others take two inputs, as we shall see.

So what is this operator good for? Why does it exist? NOT provides the ability to toggle bits, much as flipping a light switch changes the system from open to closed or closed to open. A common use of NOT is to invert the value of a boolean expression so that it can be checked against the desired true/false constant. For instance:

if not lvRoomIsCold :
  activateAirConditioner()

if lvRoomIsCold == false :
  activateAirConditioner()

The two pieces of logic are equivalent, but using NOT is shorter. This is all the more the case when NOT is represented by a single symbol such as ! instead of a word.

NOT can be more useful in hardware than in software. In hardware, it is generally possible to invert a single boolean input or output. Whereas in software, if the computer architecture provides a NOT operation it usually does not come with the ability to invert just one bit. Rather, you must invert the entire variable (and all its bits), or nothing. This lack of precision restrains its software usage to relatively simple scenarios. The example psuedo-code shows one common use -- when a whole variable, whatever its actual size in bits, is used to represent a single boolean state. Another case is when a series of comparisons or calculations results in a boolean value, which needs to be inverted to produce the desired logic.

All boolean operations can be formally defined by a "truth table", which enumerates all possible inputs and their resulting output. Here is the truth table for NOT:

Input Output
false true
true false

Operation AND

Moving on, let's look at the more powerful operation AND. Unlike NOT, AND is binary -- it requires at least two inputs. AND is called the conjunction operator or simply conjunction. Its output matches what you might expect from the name; true only when both operands are true. If one, the other, or both are false the output will be false.

What happens when we have two input operands that are more than one bit long? The rule of all the basic binary boolean operators is to produce one output for each pair of corresponding bits in the input. That is, if we take two bytes and AND them together, we will get one byte output and the values of its bits will be determined by individually ANDing each set of two aligned bits in the inputs. Observe:

Inputs: %1 = 1 , %0 = 0

        %1       1
    AND %0   AND 0
    ------   -----
      = %0     = 0

Inputs: %10 = 2 , %11 = 3

        %10       2
    AND %11   AND 3
    -------   -----
      = %10     = 2

Inputs: %1011 = 11 , %0100 = 4

        %1011       11
    AND %0100   AND  4
    ---------   ------
      = %0000      = 0

Inputs: %00011111 = 31 , %11100001 = 225

        %00011111         31
    AND %11100001    AND 225
    -------------    -------
      = %00000001        = 1

How odd, you say. Whatever could this be useful for?

AND has two primary functions. For one, it is used to check that a series of conditions are all met, where each of the conditions is either represented by or can be reduced to a boolean variable. The second use is clever; by setting only the bits you wish to preserve in operand B and leaving the others zero, the corresponding "chosen" bits of operand A appear in the output while all the others become zero. When used in this fashion, operand B is called the bitmask or just "mask" for short. We say that the AND operation "masks out" or disables the undesired bits. This is especially useful when several smaller variables are packed into a single wider variable, such as a word. AND allows us to extract the particular bits that need to be read while ignoring the rest.

Why not just allocate a full word for each variable needed? Storage efficiency. If a word is 16-bits, we can get 16 boolean variables out of it. If we used a full word for each, sixteen times the memory would be needed. With 32-bit words the efficiency difference is 32 times, and so forth. Even if the sub-variables are several bits or a whole byte each, the memory savings are often still worth it.

Conditional logic can often be made clearer or shorter using AND. Compare the two test cases:

if X == -20 :
  if Y > 100 :
    execute()

if X == -20 and Y > 100 :
  execute()

In any similar case where only one or a few of many possible outcomes receives special handling, logical operators help simplify the structure and cut down on the nesting of conditions. However, if most or all of the possible outcomes each require different behavior, the advantage of brevity is lost.

With operand A's value laid out along the first column, and operand B's value laid out along the first row, AND functions according to this truth table:

AND false true
false false false
true false true

Operation OR

Where there's an AND there must be an OR, right? Boolean OR is also a binary operator, but it may not be exactly what you expect. There are two ways the word "or" can be used in English grammar -- either in an inclusive sense or in an exclusive sense. The OR operation follows the inclusive logic, which means it has the same reasoning as "any". (This in contrast to AND's "all".) Therefore, the result of an OR operation is true if any of its operands are true. Formally, we call this logic an inclusive disjunction.

Examples of OR usage:

Inputs: %0 = 0 , %1 = 1

        %0       0
     OR %1    OR 1
     -----    ----
      = %1     = 1

Inputs: %00 = 0 , %11 = 3

        %00       0
     OR %11    OR 3
     ------    ----
      = %11     = 3

Inputs: %1001 = 9 , %1100 = 12

        %1001        9
     OR %1100    OR 12
     --------    -----
      = %1101     = 13

Inputs: %11110000 = 240 , %00011110 = 30

        %11110000        240
     OR %00011110     OR  30
     ------------     ------
      = %11111110      = 254

Seeing a pattern here? Where AND was used to check for all conditions, OR is used to check for any. Further, where AND was used to turn bits off with a mask, OR is used to turn bits on with a mask. AND and OR are perfect counterparts to one another. This counterpart relationship is generally called "dualism"; AND and OR are duals in such a sense. Note that this is a different concept than inverse functions. You can use an OR operation to reverse the effect of an AND operation, or an AND to reverse the effect of an OR, only if you know what the original starting values were. (Q and R) or R does not equal Q in many cases.

Complex conditional logic is made easy by combining AND and OR together:

if A == 5 :
  if B > 8 :
    execute()
else :
  if C == 3 :
    execute()

if (A == 5 and B > 8) or C = 3 :
  execute()

The truth table for OR:

OR false true
false false true
true true true

Operation XOR

What about that other logical meaning to "or"? Turns out there's a boolean operator for it, too. Aptly, it is called exclusive OR. Usually you will see it abbreviated as XOR, but in some cases EOR is also used.

Exclusive OR is the exclusive disjunction -- one or the other, but not both. In order to be true you must strictly have one of the two operands true. If both are false or both are true the result is false. Let's run through some examples of such an effect:

Inputs: %1 = 1 , %0 = 0

        %1       1
    XOR %0   XOR 0
    ------   -----
      = %1     = 1

Inputs: %10 = 2 , %01 = 1

        %10        2
    XOR %01    XOR 1
    -------    -----
      = %11      = 3

Inputs: %1111 = 15 , %0101 = 5

        %1111        15
    XOR %0101    XOR  5
    ---------    ------
      = %1010      = 10

Inputs: %10001000 = 136 , %00010001 = 17

        %10001000        136
    XOR %00010001    XOR  17
    -------------    -------
      = %10011001      = 153

Two purposes can be accomplished easily with XOR. One, it is a quick test for whether two values are equal. When they are, the result of XORing them together will always be zero. Inequality will be shown by a non-zero output, and the output bits which are on precisely indicate which bits differed. To understand how this works, consider it as follows. Each bit in operand B that holds an true value will toggle (invert) the corresponding bit in operand A. However, any false bit in operand B merely copies the corresponding bit in A to the output. Ones that appear in the output must therefore be either a differing on-bit copied from A or a zero in A that was toggled by B. Matched one bits in A will become disabled, and the matched zeroes fall through in the result.

There is a second and more powerful purpose to XOR that may have become apparent from the previous analysis: it can be used to toggle arbitrary bits. When using operand B as the bitmask, any bit position set in that second operand will be take on the opposite value of its corresponding bit in operand A in the output. The zero bit places will copy the corresponding bit in operand A as is.

Now, an interesting question: why use NOT when XOR exists? The exclusive OR provides all the function of NOT and more, so strictly speaking there is no need for NOT. Some computer architectures don't even give you a NOT instruction for this reason. For hardware, however, XOR is much more complex and thus slower and bulkier than a simple inverter. One can see the relative complexity by decomposing XOR into a set of AND and OR functions. Logically, q XOR p = (q OR p) AND (NOT[q AND p]). Another way to say that is q XOR p = (q AND [NOT p]) OR ([NOT q] AND p).

XOR doesn't get used much in conditional logic. Here's an example that shows how it can be used:

if RHandItemClass == "weapon" :
  if LHandItemClass != "weapon" :
    equip()

else
  if LHandItemClass == "weapon" :
    equip()


if (RHandItemClass == "weapon") xor (LHandItemClass == "weapon") :
  equip()

This example is demonstrating the implementation of a fairly arbitrary restriction that appears in some games. The current character has two hands, but is only permitted by rule to wield a weapon in one of them. Additionally, in this case the character is forced to wield at least one weapon to finish the equipment phase at all; nothing will happen if the restrictions are not met.

XOR is only useful in control logic when you have two conditions, both of which would be sufficient standalone, but when they occur together cancel the effect or validity. Such cases of mutual exclusion are relatively rare.

As mentioned earlier, XOR is the same as an inequality test for boolean variables. Instead of q XOR p, it is often clearer to use the inequality operator directly. This is typically written either q != p or q <> p. Some languages allow you to use whole-variable boolean logic tests on non-boolean variables such as integers. Don't do that. If it makes sense to do boolean logic, for clarity's sake convert to booleans first. Better yet, use boolean variables from the start.

That said, on to mighty XOR's truth table:

XOR false true
false false true
true true false

Operations NAND and NOR

So it is that we come to the last two operations of the pack: NAND and NOR. These are the least commonly used of the bunch in software, yet the most commonly used in hardware. The reason why they're prevalent in computer hardware is that both NAND and NOR are "functionally complete" in and of themselves. For a set of one or more boolean operations to be functionally complete, it must be possible to implement every possible boolean function using that set. This is equivalent to being able to construct an expression using just operations from the set to implement each and every truth table.

NAND and NOR are special in the regard that just NAND or just NOR, used alone, are enough to do that. It's quite a useful property to have if your goal is to keep the number of distinct operations down. Of course, there are cost and reliability reasons to want to do that.

The names NAND and NOR are contractions of NOT AND and NOT OR. By this, you can infer what sort of boolean function they implement. NAND is the same as NOT(q AND p) and NOR is the same as NOT(q OR p). The NOT is applied after the inner function on the result.

Significantly, the output would not be the same as inverting both of the input operands and then executing the inner operation. Examine the following equivalencies:

NOT(q)  OR NOT(p) = NOT(q AND p) = q NAND p
NOT(q) AND NOT(p) = NOT(q  OR p) = q  NOR p

Notice how the OR changes to AND and the AND changes to OR. The principle rule behind these conversions between AND expressions and OR expressions is called De Morgan's law.

NAND or NOR are almost never used directly in software branching logic, due largely to the fact that most programming languages do not provide them. As a result, you will generally see the equivalent NOT-based expression instead.

That said, NAND and NOR would be generally more useful to have for conditional logic than XOR is. NAND fulfills situations where two conditions must not both be met, but any other possibility is fine. NOR is even better; it checks whether both conditions are false.

NAND Condition Example:

while true :
  if StageGoal1 == false :
    continueStage()

  else :
    if StageGoal2 == false :
      continueStage()
    else :
      break

while (StageGoal1 == false) or (StageGoal2 == false) :
  continueStage()

while StageGoal1 nand StageGoal2 :
  continueStage()

NOR Condition Example:

while true :
  if PlayerDead == false :
    if ClockRanOut == false :
      execMainLoop()
    else :
      break

  else :
    break

while (PlayerDead == false) and (ClockRanOut == false) :
  execMainLoop()

while PlayerDead nor ClockRanOut :
  execMainLoop()

For completeness, the truth tables for NAND and NOR:

NAND false true
false true true
true true false
NOR false true
false true false
true false false

More than Two Inputs

While thinking about these last five binary operators, you may have wondered what would happen if instead of two inputs there were three or more. It turns out that this is both possible and that the result is well-defined. The effect of running three or more operands into these boolean functions is the same as taking two inputs at a time, evaluating them, and then chaining the result into another of the same operation. Put more succinctly, AND(a, b, c) = a AND b AND c. Similarly, OR(a, b, c) = a OR b OR c. Evaluation from left to right is the norm.

Where things become a little odd is with an operator like XOR. XOR is well-defined on additional inputs and still has the chain-like behavior. However, when using three or more inputs it no longer makes much sense to talk about toggling bits or checking for inequality. Instead, 3+ input XOR tests are a question of whether there are an odd or even number of true values in the input. Both XOR(a, b, c) and XOR(a, b, c, d) evaluate as true when an odd number of the inputs is true, but false when zero or an even number are true. A fair way to understand this is conceptualizing each pair of one bits as canceling out or nullifying each other -- leaving zero or false. What's left will be either exactly one or exactly zero true values, which evaluate just like the two-input XOR does.

Fortunately, NAND and NOR are not so tricky in their expanded case. NAND(a, b, c) provides true so long as any of the three inputs is false. NOR(a, b, c), on the other hand, is true when all the inputs are false. If that sounds a lot like NAND is an OR with its inputs inverted and NOR is an AND with its inputs inverted -- indeed, they are.