Abstract Algebra/Boolean algebra

From Wikibooks, open books for an open world
Jump to: navigation, search

Boolean Algebra[edit]

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

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:

\bullet

Closure. The boolean system of 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.

\bullet

Commutativity. A binary operator "^o" is said to be commutative if A^o B = B^o A for all possible boolean values A and B.

\bullet

Associativity. A binary operator "^o" is said to be associative if
(A^o B)^o C = A^o (B^o C)

for all boolean values A, B, and C.

\bullet

Distribution. Two binary operators "^o" and "%" are distributive if
A^o(B % C) = (A^o B) % (A^o C)

for all boolean values A, B, and C.

\bullet

Identity. A boolean value I is said to be the identity element with respect to some binary operator "^o" if A^o I = A

\bullet

Inverse. A boolean value I is said to be the inverse element with respect to some binary operator "^o" if A ^o I = B and B /neq A (i.e., B is the opposite value of A in a boolean system).

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 "\cdot" represents the logical AND operation; e.q., A \cdot B is the result of logically ANDing the boolean values A and B. When using single letter variable names, this text will drop the "\cdot" symbol; Therefore, AB also represents the logical AND of the variables A and B (we will also call this the product<\i> of A and B).

The symbol "+" represents the logical OR operation; 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 (') 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. If two operators with the same precedence are adjacent, you must evaluate them from left to right. 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:
P1 Boolean algebra is closed under the AND, OR, and NOT operations.

P2 The identity element with respect to \cdot is one and + is zero. There is no identity element with respect to logical NOT.

P3 The \cdot and + operators are commutative.

P4 \cdot and + are distributive with respect to one another. That is, A \cdot (B + C) = (A \cdot B) + (A \cdot C) and A + (B \cdot C) = (A + B) \cdot (A + C).

P5 For every value A there exists a value A' such that A \cdot A^' = 0 and A + A^' = 1. This value is the logical complement (or NOT) of A.

P6 \cdot and + are both associative. That is, (A \cdot B) \cdot C = A \cdot (B \cdot 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:
Th1: A + A = A

Th2: A \cdot A = A

Th3: A + 0 = A

Th4: A \cdot 1 = A

Th5: A \cdot 0 = 0

Th6: A + 1 = 1

Th7: (A + B)^' = A^' \cdot B^'

Th8: (A \cdot B)^' = A^' + B^'

Th9: A + A \cdot B = A

Th10: A \cdot (A + B)=A

Th11: A + A^' B = A+B

Th12: A^' \cdot (A + B^') = A^' B^'

Th13: AB + AB^'=A

Th14: (A^' + B^') \cdot (A^' + B) = A^'

Th15: A + A^' = 1

Th16: A \cdot 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. Th1 & Th 2, Th3 & Th4, 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 \cdot 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]

A boolean expression is a sequence of zeros, ones, and literals separated by boolean operators. A literal is a primes (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 boolean:


F_0 = AB + C



This function computes the logical AND of A and B and then logically ORs this result with C. If A=1, B=O, and C=1, then F_0 returns the value one (1 \cdot 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:

Table 6: AND Truth Table

\begin{array}{|c|c c|} AND & 0 & 1 \\
\hline
0&0&0\\
1&0&1\\
\end{array}

Table 7: OR Truth Table

\begin{array}{|c|c c|} OR & 0 & 1 \\
\hline
0&0&1\\
1&1&1\\
\end{array}

For binary operators and twp 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 or four variables: