Boolean Algebra

Boolean Functions
Introduction: Boolean algebra provides the operations and the rules for working with the set {0, 1}. Electronic and optical switches can be studied using this set and the rules of Boolean algebra. The three operations in Boolean algebra that we will use most are complementation, the Boolean sum, and the Boolean product. The complement of an element, denoted with a bar, is defined by 0 = 1 and 1 = 0. The Boolean sum, denoted by or by OR, has the following values:
1 1 = 1,  1 0 = 1,  0 1 = 1,  0 0 = 0.
The Boolean product, denoted by · or by AND, has the following values:
1 · 1 = 1,  1 · 0 = 0,  0 · 1 = 0,  0 · 0 = 0.

When there is no danger of confusion, the symbol · can be deleted, just as in writing algebraic products. Unless parentheses are used, the rules of precedence for Boolean operators are: first, all complements are computed, followed by all Boolean products, followed by all Boolean sums. This is illustrated in Example 1.

EXAMPLE 1 Find the value of 1 · 0 (0 1).
Solution: Using the definitions of complementation, the Boolean sum, and the Boolean product, it follows that

The complement, Boolean sum, and Boolean product correspond to the logical operators, ¬,∨, and ∧, respectively, where 0 corresponds to F (false) and 1 corresponds toT (true). Equalities in Boolean algebra can be directly translated into equivalences of compound propositions. Conversely, equivalences of compound propositions can be translated into equalities in Boolean algebra.We will see later in this section why these translations yield valid logical equivalences and identities in Boolean algebra. Example 2 illustrates the translation from Boolean algebra to propositional logic.

Boolean Expressions and Boolean Functions: Let B = {0, 1}. Then Bn = {(x1, x2, . . . , xn) | xi ∈ B for 1 ≤ i ≤ n} is the set of all possible n-tuples of 0s and 1s. The variable x is called a Boolean variable if it assumes values only from B, that is, if its only possible values are 0 and 1. A function from Bn to B is called a Boolean function of degree n.

The function F(x, y) = xy from the set of ordered pairs of Boolean variables to the set {0, 1} is a Boolean function of degree 2 with F(1, 1) = 0, F(1, 0) = 1, F(0, 1) = 0, and F(0, 0) = 0. We display these values of F in Table 1.

Boolean functions can be represented using expressions made up from variables and Boolean operations. The Boolean expressions in the variables x1, x2, . . . , xn are defined recursively as 0, 1, x1, x2, . . . , xn are Boolean expressions; if E1 and E2 are Boolean expressions, then E1, (E1E2), and (E1 E2) are Boolean expressions. Each Boolean expression represents a Boolean function. The values of this function are obtained by substituting 0 and 1 for the variables in the expression. In Section 12.2 we will show that every Boolean function can be represented by a Boolean expression.

EXAMPLE 5 Find the values of the Boolean function represented by F(x, y, z) = xy z.
Solution: The values of this function are displayed in Table 2.

Note that we can represent a Boolean function graphically by distinguishing the vertices of the n-cube that correspond to the n-tuples of bits where the function has value 1.