Arithmetic, algebra, geometry, calculus, and statistics are the five main pillars of mathematics that are enacted in curricula from grade school through postsecondary education. As such, one of the more under-appreciated domains of mathematics is logic, with its syntactics rarely examined but its semantics ubiquitous in every aspect of society. Logic has been a human formulation since the dawn of humanity itself, but the foundations for modern digital logic were laid by English mathematician George Boole (1815-1864) in his 1854 work Laws of Thought. An understanding of Boolean logic–and by extension, Boolean algebra–is essential in understanding the workings of modern digital technology that are widely taken for granted.

Image Courtesy of Britannica

To maintain quantitative structure, True and False, the basic units of logic, are assigned values of 1 and 0, respectively. We will now examine the fundamental operations of Boolean algebra.

AND [*]

By definition, a statement containing the conjunction “and” is true only when both conditions in question are true. If I say, “I am at home AND I am in my dorm,” then the entire statement is false, even though the first condition (me being at home) is true. If the truth or falsity of each condition is denoted by 1 or 0, respectively, the following holds:

• 0 AND 0 = 0
• 0 AND 1 = 0
• 1 AND 0 = 0
• 1 AND 1 = 1

It is clear that the Boolean AND operation can be modeled as a traditional multiplication (*), for any false condition is said to annihilate the entire statement to 0 (False).

Inclusive OR [+]

In contrast with the definition of AND, an inclusive OR statement is true when either of the conditions in question is true. Inclusive means that the statement is still regarded as true if both conditions are true. This deviates from the traditional English definition of the word “or,” which is defined in the exclusive sense. As expressed below, an inclusive OR statement is only false when both conditions are false:

• 0 OR 0 = 0
• 0 OR 1 = 1
• 1 OR 0 = 1
• 1 OR 1 = 1

Boole synthesizes the inclusive OR operation with the arithmetic operation of addition (+). This differs from the traditional definition of addition in the last statement (1 + 1 = 1).

Exclusive Or (XOR)

As mentioned in the previous section, the exclusive OR operation excludes from truth the statement where both conditions are true:

• 0 XOR 0 = 0
• 0 XOR 1 = 1
• 1 XOR 0 = 1
• 1 XOR 1 = 0

NOT [~]

Trivially, the NOT operation simply reverses the truth value of a singular (non-combinational) statement. Indeed, something that is “not false” is “true,” and something that is “not true” is “false.”

• ~0 = 1
• ~1 = 0

It is important to note that there exists an order of operations in Boolean algebra. Just as traditional algebraic expressions with several terms are evaluated in this order–

1. Parentheses/Brackets/Grouping Symbols
2. Exponentiation
3. Multiplication and Division
4. Addition and Subtraction–

the Boolean operations are evaluated in this order–

1. Parenthetical Terms/NOT (corresponds to grouping of terms)
2. AND (similar to multiplication)
3. OR/XOR (similar to addition)

For example, the expression 1 AND (0 XOR 1) OR ~1 OR (1 AND ~0) AND ~~~1 is evaluated by the following procedure:

1. Separately evaluate expressions in parentheses and simplify negated (NOT) terms: 1 AND 1 OR 0 OR 1 AND 0
2. Evaluate AND expressions: 1 OR 0 OR 0
3. Evaluate OR expressions (although there is a triple instead of a pair of conditions, it remains that any true condition yields a true statement) 1

In next week’s post, I will detail more involved and intriguing operations as well as the innumerable (indeed, uncountably infinite) applications of Boolean logic that permeate modern life.