Table of Contents#### Download Safari Books Online apps: Apple iOS | Android | BlackBerry

### 2.1. Boolean Algebra

#### 2.1.1. Values

#### 2.1.2. Operators

#### 2.1.3. Truth Tables

#### 2.1.4. Rules of Boolean Algebra

#### 2.1.5. De Morgan’s Law

#### 2.1.6. Shannon’s Expansion Theorem

Entire Site

Free Trial

Safari Books Online is a digital library providing on-demand subscription access to thousands of learning resources.

Digital design uses a two-value algebra. Variables can take one of two values that can be represented by

ON and OFF,

TRUE and FALSE,

1 and 0.

The algebra of two values, known as Boolean algebra, after George Boole (1815–1864), has five basic operators. In decreasing order of precedence (i.e., in the absence of parentheses, operations at the top of the list should be evaluated first) these are:

NOT

AND

OR

IMPLIES

EQUIVALENCE

The last two operators are not widely used in digital design. These operators can be used to form expressions. For example:

The symbol “+” means “OR,” “.” means “AND,” and the overbar, for example, “,” means “NOT A.”

The meaning of an operator or expression can be described by listing all the possible values of the variables in that expression, together with the value of the expression in a truth table. The truth tables for the three basic operators are given in Tables 2.1, 2.2, and 2.3.

A | NOT A () |
---|---|

0 | 1 |

1 | 0 |

A | B | A AND B (A · B) |
---|---|---|

0 | 0 | 0 |

0 | 1 | 0 |

1 | 0 | 0 |

1 | 1 | 1 |

A | B | A OR B (A + B) |
---|---|---|

0 | 0 | 0 |

0 | 1 | 1 |

1 | 0 | 1 |

1 | 1 | 1 |

In digital design, three further operators are commonly used: NAND (Not AND), NOR (Not OR), and XOR (eXclusive OR); see Tables 2.4, 2.5, and 2.6.

A | B | A NAND B |
---|---|---|

0 | 0 | 1 |

0 | 1 | 1 |

1 | 0 | 1 |

1 | 1 | 0 |

A | B | A NOR B |
---|---|---|

0 | 0 | 1 |

0 | 1 | 0 |

1 | 0 | 0 |

1 | 1 | 0 |

A | B | A XOR B (A ⊕ B) |
---|---|---|

0 | 0 | 0 |

0 | 1 | 1 |

1 | 0 | 1 |

1 | 1 | 0 |

The XNOR operator is also used occasionally. XNOR is the same as EQUIVALENCE.

There are a number of basic rules of Boolean algebra that follow from the precedence of the operators.

Commutativity

A + B = B + A A · B = B · A Associativity

A + (B + C) = (A + B) + C A · (B · C) = (A · B) · C Distributivity

A · (B + C) = A · B + A · C

In addition, some basic relationships can be observed from the previous truth tables.

The right-hand column can be derived from the left-hand column by applying the principle of duality. The principle of duality states that if each AND is changed to an OR, each OR to an AND, each 1 to 0, and each 0 to 1, the value of the expression remains the same.

There is a very important relationship that can be used to rewrite Boolean expressions in terms of NAND or NOR operations: de Morgan’s Law. This is expressed as

Shannon’s expansion theorem can be used to manipulate Boolean expressions.

F(1, B, C, D, ...) means that all instances of A in F are replaced by a logic 1.