Chapter 10 - Boolean Algebra

Boolean Algebra

Claude Shannon showed how the basic rules of logic, first given by George Boole in 1854 in his “The Laws of Thought”, could be used to design circuits. These rules form the basis for Boolean algebra. In this chapter we develop the basic properties of Boolean algebra.

Boolean Functions

Boolean algebra provides the operations and the rules for working with the set . Electronic 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 the Boolean sum, the Boolean product, and complementation. The complement of an element, denoted with a bar, is defined by and . The Boolean sum, denoted by or by has the same values as standard logical ‘or’ () function if we treat as True and as False. Similar results can be obtained for the Boolean product () which is identical to logical ‘and’ ().

Boolean Expressions and Boolean Functions

Let . Then for is the set of all possible -tuples of s and s. The variable is called a Boolean variable if it assumes values only from that is, if its only possible values are and . A function from to is called a Boolean function of degree .

Boolean functions can be represented using expressions made up from variables and Boolean operations. The Boolean expressions in the variables are defined recursively as are Boolean expressions; if and are Boolean expressions, then and are Boolean expressions.

Boolean functions and of variables are equal if and only if whenever belong to . Two different Boolean expressions that represent the same function are called equivalent. For instance, the Boolean expressions and are equivalent.

The complement of the Boolean function is the function where . Let and be Boolean functions of degree . The Boolean sum and the Boolean product are defined by

• Definition: A Boolean algebra is a set with two binary operations and elements and and a unary operation such that these properties hold for all and in :

  • Identity laws

  • Complement laws

  • Associative laws

  • Commutative laws

  • Distributive laws

Representing Boolean Functions

Two important problems of Boolean algebra will be studied in this section. The first problem is: Given the values of a Boolean function, how can a Boolean expression that represents this function be found? The second problem is: Is there a smaller set of operators that can be used to represent all Boolean functions?

Sum-of-Products Expansions

• Definition: A literal is a Boolean variable or its complement. A minterm of the Boolean variables is a Boolean product where or . Hence, a minterm is a product of literals, with one literal for each variable.

By taking Boolean sums of distinct minterms we can build up a Boolean expression with a specified set of values. In particular, a Boolean sum of minterms has the value when exactly one of the minterms in the sum has the value . It has the value for all other combinations of values of the variables. Consequently, given a Boolean function, a Boolean sum of minterms can be formed that has the value 1 when this Boolean function has the value and has the value when the function has the value . The minterms in this Boolean sum correspond to those combinations of values for which the function has the value . The sum of minterms that represents the function is called the sum-of-products expansion or the disjunctive normal form of the Boolean function.

It is also possible to find a Boolean expression that represents a Boolean function by taking a Boolean product of Boolean sums. The resulting expansion is called the conjunctive normal form or product-of-sums expansion of the function. These expansions can be found from sum-of-products expansions by taking duals.