Free Trial

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

  • Create BookmarkCreate Bookmark
  • Create Note or TagCreate Note or Tag
  • PrintPrint

2.1. Boolean Algebra

2.1.1. Values

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.

2.1.2. Operators

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:

  1. NOT

  2. AND

  3. OR

  4. IMPLIES

  5. 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.”

2.1.3. Truth Tables

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.

Table 2.1. NOT Operation
ANOT A ()
01
10


Table 2.2. AND Operation
ABA AND B (A · B)
000
010
100
111


Table 2.3. OR Operation
ABA OR B (A + B)
000
011
101
111


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.

Table 2.4. NAND Operation
ABA NAND B
001
011
101
110


Table 2.5. NOR Operation
ABA NOR B
001
010
100
110


Table 2.6. XOR Operation
ABA XOR B (AB)
000
011
101
110


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

2.1.4. Rules of Boolean Algebra

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

  1. Commutativity

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


  2. Associativity

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


  3. 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.

2.1.5. De Morgan’s Law

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

2.1.6. Shannon’s Expansion Theorem

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.

  • Safari Books Online
  • Create BookmarkCreate Bookmark
  • Create Note or TagCreate Note or Tag
  • PrintPrint