# Abstract Algebra/Boolean algebra

## Boolean Algebra

[edit | edit source]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:

The boolean system is**Closure:***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.A binary operator "#" is said to be commutative if A # B = B # A for all possible boolean values A and B.**Commutativity:**A binary operator "#" is said to be associative if (A # B) # C = A # (B # C) for all boolean values A, B, and C.**Associativity:**Two binary operators "#" and "%" are distributive if A # (B % C) = (A # B) % (A # C) for all boolean values A, B, and C.**Distribution:**A boolean value I is said to be the identity element with respect to some binary operator "#" if A # I = A**Identity:**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).**Inverse:**

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**AND**ing 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**OR**ing 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:

- Boolean algebra is closed under the
**AND**,**OR**, and**NOT**operations. - The identity element with respect to ∧ is one and ∨ is zero. There is no identity element with respect to logical
**NOT**. - The ∧ and ∨ operators are commutative.
- ∧ 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).
- 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. - ∧ 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:

- A ∨ A = A
- A ∧ A = A
- A ∨ 0 = A
- A ∧ 1 = A
- A ∧ 0 = 0
- A ∨ 1 = 1
- (A ∨ B)′ = A′ ∧ B′
- (A ∧ B)′ = A′ ∨ B′
- A ∨ A ∧ B = A
- A ∧ (A ∨ B) = A
- A ∨ A′B = A ∨ B
- A′ ∧ (A ∨ B′) = A′ B′
- AB ∨ AB′ = A
- (A′ ∨ B′) ∧ (A′ ∨ B) = A′
- A ∨ A′ = 1
- 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

[edit | edit source]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

_{0}This function computes the logical **AND** of A and B and then logically **OR**s this result with C. If A=1, B=0, and C=1, then F_{0} 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

[edit | edit source]AND | 0 | 1 |
---|---|---|

0 | 0 | 0 |

1 | 0 | 1 |

### OR Truth Table

[edit | edit source]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 _{0}* 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 |