Boolean Logic and Gates

Boolean logic, named after English mathematician George Boole (1815 – 1864), specifies rules for manipulating True (T) and False (F) values, known as Boolean values.  Boolean expressions, expressions that evaluate to T or F, are important in computer science because they can be converted to circuits.  The design and logic design of hardware pertains to the design and construction of new circuits.  A bit, or a binary value of 0 or 1, maps to F/T of Boolean logic.

The three basic Boolean operations are NOT, AND, and OR.  The NOT operator is a unary operator, meaning that it only takes one value, or argument. The NOT operator toggles Boolean F to Boolean T, and conversely.  E.g. NOT(T) is F.  Denoting T as binary 1 and F as binary 0, NOT(1) = 0 and NOT(0) = 1.  The AND operator is a binary operator (not to be confused with the binary number system), indicating that two arguments are required.  Two Boolean values, when AND is applied, results in T only if both arguments are T.  Otherwise, the result of the AND binary operator is F.  That is, F AND F = F, F AND T = F, T AND F = F, and T AND T = T.  The OR operator is also a binary operator.  Two Boolean values, when OR is applied, results in T if one of the arguments is T.  If both arguments are F, then the result of the OR operation is F.  That is, F OR F = F, F OR T = T, T OR F = T, and T OR T = T.

The AND and OR operators can be combined with the NOT operator to yield the NAND (NOT AND) and NOR (NOT OR) binary operators.  The result of NAND and NOR is simply the NOT of AND and NOT of OR, respectively.

The binary XOR, or exclusive OR operator (also called the exclusive disjunction operator), results in T only if the two arguments are different; that is, if one is T and the other F.  Therefore, F XOR F = F, F XOR T = T, T XOR F = F, and T XOR T = F.  Note that the AND, OR, NAND, NOR, and XOR operations are commutative; that is, A AND B = B AND A, A XOR B = B XOR A, etc.

Truth tables are 2 x 2 tables that express the Boolean true/false values for Boolean expressions for each possible true/false input.  The table has 2 rows and 2 columns because there are only two Boolean variables: T or 1, and F or 0.  The truth table for the logical AND operation is given below:

The truth table for the logical OR operation is expressed in the following table:

The truth tables for the logical NAND, NOR, and XOR operations are given in the tables below:

An interesting characteristic of the XOR operator is that is non-destructive.  That is, given binary numbers A and B and C = A XOR B (that is, C is the result of applying the XOR operation bit-wise, on each bit of A and B), then A can be recovered by calculating C XOR B, and B can be recovered from calculating C XOR A.  For example, suppose that A = 1101 1001₂ and B = 0010 1101₂.  Applying the XOR operator in a bit-wise manner to A and B yields:

1101 1001

XOR    0010 1101

1111 0100

Consequently, C = 1111 01002.  Now C XOR B (or B XOR C, since the XOR operator is commutative) is calculated.

1111 0100

XOR    0010 1101

1101 1001

The result of the XOR operation is 1101 1001₂ = A.  Therefore, the original value of A was recovered.  Similarly, the calculation of C XOR A (or A XOR C) follows:

1111 0100

XOR    1101 1001

0010 1101

The result is 0010 1101₂ = B.  Thus, B was recovered from A and C.  The non-destructive characteristic of the XOR operator has applications in cryptography and image processing.

Boolean operators can also be combined.  For instance, in evaluating (T AND F) OR (F NAND T), each expression in parentheses is evaluated, and the OR operator is applied to the two resulting Boolean values.  In the example (T AND F) evaluates to F, and (F NAND T) evaluates to NOT(F AND T) = NOT(F) = T.  Since F OR T evaluates to T, the expression (T AND F) OR (F NAND T) evaluates to T.  Combining such Boolean operations can have an arbitrary level of complexity and number of expressions.

Boolean operators are used to evaluate conditions that are used in computer programs.  For example, suppose the condition (4 > 5) is to be evaluated.  Since 4 is not greater than 5, the expression (4 > 5) evaluates to F.  The expression (4 + 100 = 104) evaluates to TRUE.  In computer programs, any combination of these expressions can be evaluated.  For example,

(0 ≤ x) AND (x ≤ 35)

(a = 12) OR (a > 70)

NOT (x = 50.9)

Suppose the following Boolean expression is to be evaluated: ((a AND b) OR (a XOR b)) NAND (NOT(a) NOR b).

If a = 1 (Boolean T) and b = 1 (Boolean T), then:

(a AND b) = (1 AND 1) = 1 (Boolean T)

(a XOR b) = (1 XOR 1) = 0 (Boolean F)

Therefore, ((a AND b) OR (a XOR b)) = 1 OR 0 = 1

Continuing, NOT(a) = NOT(1) = 0

(NOT(a) NOR b) = NOT(0 OR 1) = NOT(1) = 0

Therefore, the expression is simplified to 1 NAND 0 = NOT(1 AND 0) = NOT(0) = 1 (Boolean T).

The truth table for the expression is given as follows:

Expression: ((a AND b) OR (a XOR b)) NAND (NOT(a) NOR b)

As another example, consider the expression:

NOT(NOT(a XOR (a AND B)) OR (a NOR (a AND (a XOR b))))

This expression looks rather complex but can be evaluated if each sub-expression is evaluated, and the results are carefully combined.  The truth table for the expression is below.  The reader is encouraged to evaluate the four possibilities in the truth table and verify the results with the truth table below.

Expression: NOT(NOT(a XOR (a AND B)) OR (a NOR (a AND (a XOR b))))

The expressions given as examples above can undergo a process of simplification, whereby they become easier to evaluate and to implement in hardware as circuits.  Such simplification follows from the rules of Boolean logic.  However, this topic is beyond the scope of the current discussion.

Boolean logic is used to design gates, which are electronic devices that operate on inputs to produce outputs.  Each gate corresponds to a specific Boolean operator.  Gates are built from transistors.  A NOT gate is built from a single transistor.  AND and OR gates require three transistors.  Both NAND and NOR gates are built from two transistors.  These gates are combined to form computer circuits.  A circuit has input wires, gates connected by wires, and output wires.  The output of the circuit only depends only on the inputs applied to the circuit. Control circuits are used to implement the process of making decisions, determining the order of operations, or selecting data values.  A multiplexor circuit selects one output from among many inputs.  There are generally 2n input lines, n selector lines, and a single output line.  Each input line corresponds to a unique pattern on selector lines.  A decoder circuit sends a signal out on only one output, chosen by its input.  For a decoder with n input lines, there are 2ⁿ output lines, where each output line corresponds to a unique pattern on input lines.  The chosen output line has a Boolean value of 1, while the other output lines have output values of Boolean 0.

[NEXT]