Abstract Algebra/Boolean algebra

Boolean Algebra

Boolean algebra is a deductive mathematical system closed over the values zero and one (false and true). A binary operator defined over this set of values accepts two boolean inputs and produces a single boolean output.

For any given algebra system, there are some initial assumptions, or postulates that the system follows. You can deduce additional rules, theorems, and other properties of the system from this basic set of postulates:

• Closure: The boolean system is closed with respect to a binary operator if for every pair of boolean values it produces a boolean result. For example, logical AND is closed in the boolean system because it accepts only boolean operands and produces only boolean results.
• Commutativity: A binary operator "#" is said to be commutative if A # B = B # A for all possible boolean values A and B.
• Associativity: A binary operator "#" is said to be associative if (A # B) # C = A # (B # C) for all boolean values A, B, and C.
• Distribution: Two binary operators "#" and "%" are distributive if A # (B % C) = (A # B) % (A # C) for all boolean values A, B, and C.
• Identity: A boolean value I is said to be the identity element with respect to some binary operator "#" if A # I = A
• Inverse: A boolean value I is said to be the inverse element with respect to some binary operator "#" if A # I = B and B ≠ A (i.e., B is the opposite value of A).

For our purposes, we will base boolean algebra on the following set of operators and values:

• The two possible values in the boolean system are zero and one. Often we will call these values false and true (respectively).
• The symbol "∧" represents the logical AND operation (conjunction); e.g., A ∧ B is the result of logically ANDing the boolean values A and B. When using single letter variable names, this text will drop the "∧" symbol; Therefore, AB also represents the logical AND of the variables A and B (we will also call this the product of A and B).
• The symbol "∨" represents the logical OR operation (disjunction); e.g., A ∨ B is the result of logical ORing the boolean values A and B. (We will also call this the sum of A and B.)
• Logical complement, negation, or NOT, is a unary operator. This text will use the prime symbol (′) to denote logical negation. For example, A′ denotes the logical NOT of A.
• If several different operators appear in a single boolean expression, the result of the expression depends on the precedence of the operators. We'll use the following precedences (from highest to lowest) for the boolean operators: parenthesis, logical NOT, logical AND, then logical OR. The logical AND and OR operators are left associative. The logical NOT operation is right associative, although it would produce the same result using left or right associativity since it is a unary operator.

We will also use the following set of postulates:

1. Boolean algebra is closed under the AND, OR, and NOT operations.
2. The identity element with respect to ∧ is one and ∨ is zero. There is no identity element with respect to logical NOT.
3. The ∧ and ∨ operators are commutative.
4. ∧ and ∨ are distributive with respect to one another. That is, A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C) and A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C).
5. For every value A there exists a value A′ such that A ∧ A′ = 0 and A ∨ A′ = 1. This value is the logical complement (or NOT) of A.
6. ∧ and ∨ are both associative. That is, (A ∧ B) ∧ C = A ∧ (B ∧ C) and (A ∨ B) ∨ C = A ∨ (B ∨ C).

You can prove all other theorems in boolean algebra using these postulates. This text will not go into the formal proofs of these theorems, however, it is a good idea to familiarize yourself with some important theorems in boolean algebra. A sampling include:

1. A ∨ A = A
2. A ∧ A = A
3. A ∨ 0 = A
4. A ∧ 1 = A
5. A ∧ 0 = 0
6. A ∨ 1 = 1
7. (A ∨ B)′ = A′ ∧ B′
8. (A ∧ B)′ = A′ ∨ B′
9. A ∨ A ∧ B = A
10. A ∧ (A ∨ B) = A
11. A ∨ A′B = A ∨ B
12. A′ ∧ (A ∨ B′) = A′ B′
13. AB ∨ AB′ = A
14. (A′ ∨ B′) ∧ (A′ ∨ B) = A′
15. A ∨ A′ = 1
16. A ∧ A′ = 0

Theorems seven and eight above are known as DeMorgan's Theorems after the mathematician who discovered them.

The theorems above appear in pairs. Each pair (e.g. 1 & 2, 3 & 4, etc.) form a dual. An important principle in the boolean algebra system is that of duality. Any valid expression you can create using the postulates and theorems of boolean algebra remains valid if you interchange the operators and constants appearing in the expression. Specifically, if you exchange the ∧ and ∨ operators and swap the 0 and 1 values in an expression. you will wind up with an expression that obeys all the rules of boolean algebra. This does not mean the dual expression computes the same values, it only means that both expressions are legal in the boolean algebra system. Therefore, this is an easy way to generate a second theorem for any fact you prove in the boolean algebra system.

Although we will not be proving any theorems for the sake of boolean algebra in this text, we will use these theorems to show that two boolean equations are identical. This is an important operation when attempting to produce canonical representations of a boolean expression or when simplifying a boolean expression.

Boolean Functions and Truth Tables

A boolean expression is a sequence of zeros, ones, and literals separated by boolean operators. A literal is a primed (negated) or unprimed variable name. For our purposes, all variable names will be a single alphabetic character. A boolean function is a specific boolean expression; we will generally give boolean functions the name "F" with a possible subscript. For example, consider the following function:

F₀ = AB ∨ C

This function computes the logical AND of A and B and then logically ORs this result with C. If A=1, B=0, and C=1, then F₀ returns the value one (1 ∧ 0 ∨ 1 = 1).

Another way to represent a boolean function is a via a truth table. The previous chapter used truth tables to represent the AND and OR functions. Those truth tables took the forms:

AND Truth Table

AND	0	1
0	0	0
1	0	1

OR Truth Table

OR	0	1
0	0	1
1	1	1

For binary operators with two input variables, this form of a truth table is very natural and convenient. However, reconsider the boolean function F₀ above. That function has three input variables, not two. Therefore, one cannot use the truth table format given above. Fortunately, it is still very easy to construct truth tables for three or more variables. The following example shows one way to do this for functions of three variables:

A	B	C	AB	AB ∨ C
0	0	0	0	0
0	0	1	0	1
0	1	0	0	0
0	1	1	0	1
1	0	0	0	0
1	0	1	0	1
1	1	0	1	1
1	1	1	1	1