Muroga, S.

"Basic Theory of Logic Functions"

The VLSI Handbook.
Ed. Wai-Kai Chen
Boca Raton: CRC Press LLC, 2000

2000 by CRC PRESS LLC

24
Basic Theory of Logic
Functions
24.1 Basic Theorems
Logic Expressions and Expansions

Saburo Muroga
University of Illinois
at Urbana-Champaign

24.2 Implication Relations and Prime Implicants

Consensus Derivation of All Prime Implicants from a
Disjunctive Form

24.1 Basic Theorems

Theory on logic functions where the values of variables and their functions are 0 or 1 only is called
switching theory. Here, let us discuss the basics of switching theory.
Let us denote the set of input variables by the vector expression (x1, x2, , xn). There are 2n different
input vectors when each of these n variables assume the value 1 or 0. An input vector (x1, x2, , xn) such
that f(x1, x2, , xn) = 1 or 0 is called a true (input) vector, or a false (input) vector of f, respectively.
Vectors with n components are often called n-dimensional vectors if we want to emphasize that there
are n components. When the value of a logic function f is specified for each of the 2n vectors (i.e., for
every combination of the values of x1, x2, , xn), f is said to be completely specified. Otherwise, f is
said to be incompletely specified; that is, the value of f is specified for fewer than 2n vectors. Input
vectors for which the value of f is not specified are called dont-care conditions usually denoted by d
or *, as described in Chapter 23. These input vectors are never applied to a network whose output
realizes f, or the values of f for these input vectors are not important. Thus, the corresponding values
of f need not be considered.
If there exists a pair of input vectors (x1, , xi-1, 0, xi+1, , xn) and (x1, , xi-1, 1, xi + 1, , xn) that
differ only in a particular variable xi, such that the values of f for these two vectors differ, the logic function
f(x1, x2, , xn) is said to be dependent on xi. Otherwise, it is said to be independent of xi. In this case,
f can be expressed without the xi in the logic expression of f. If f is independent of xi, xi is called a dummy
variable. If f(x1, x2, , xn) depends on all its variables, it is said to be non-degenerate; otherwise,
degenerate. For example, x1 x2x3 x 2 x 3 can be expressed as x1 x2 without dummy variable x3.

Logic Expressions and Expansions

Given variable xi, xi and x i are called literals of xi, as already explained.
Definition 24.1: (1) A conjunction (i.e., a logical product) of literals where a literal for each variable
appears at most once is called a term (or a product). A term may consist of a single literal. A
disjunction (i.e., logical sum) of terms is called a disjunctive form (or a sum of products). (2)
Similarly, a disjunction (i.e., a logical sum) of literals where a literal for each variable appears at most

2000 by CRC Press LLC

once is called an alterm. An alterm may consist of a single literal. A conjunction of alterms is called
a conjunctive form (or a product of sums).
For example, x 1 x 2 x 3 is a term, and x1 x2 x 3 is an alterm. Also, x1x2 x1 x2 and x1 x 1 x 2 are
disjunctive forms that are equivalent to the logic function x1 x2, but x1 x 2 ( x 1 x 2 ) is not a disjunctive
form, although it expresses the same function. A disjunctive form does not contain products of literals
that are identically 0 (e.g., x 1 x 2 x 2 ) from the first sentence of (1). Similarly, a conjunctive form does not
contain disjunctions of literals that are identically 1 (e.g., x1 x 2 x2 x3).
The following expressions of a logic function are important special cases of a disjunctive form and a
conjunctive form.
Definition 24.2: Assume that n variables, x1, x2, , xn, are under consideration. (1) A minterm is
defined as the conjunction of exactly n literals, where exactly one literal for each variable (xi and x i are
two literals of a variable xi) appears. When a logic function f of n variables is expressed as a disjunction
of minterms without repetition, it is called the minterm expansion of f. (2) A maxterm is defined as
a disjunction of exactly n literals, where exactly one literal for each variable appears. When f is expressed
as a conjunction of maxterms without repetition, it is called the maxterm expansion of f.
For example, when three variables, x1, x2, and x3, are considered, there exist 23 = 8 minterms: x 1 x 2 x 3 ,
x 1 x 2 x 3 , x 1 x 2 x 3 , x 1 x 2 x 3 , x 1 x 2 x 3 , x 1 x 2 x 3 , x 1 x 2 x 3 , and x1x2x3. For the given function x1 x2x3, the minterm
expansion is x 1 x 2 x 3 x 1 x 2 x 3 x 1 x 2 x 3 x 1 x 2 x 3 x1x2x3 and the maxterm expansion is (x1 x2 x3) (x1
x2 x 3 ) (x1 x 2 x3), as explained in the following.
Also notice that the row for each true vector in a truth table and also its corresponding 1-cell in the
Karnaugh map correspond to a minterm. If f = 1 for x1 = x2 = 1 and x3 = 0, then this row in the truth
table and its corresponding 1-cell in the Karnaugh map corresponds to a minterm x 1 x 2 x 3 . Also, as will
be described in a later section, the row for each false vector in a truth table and also its corresponding
0-cell in the Karnaugh map corresponds to a maxterm. For example, if f = 0 for x1 = x2 = 1 and x3 = 0,
then this row in the truth table and its corresponding 0-cell in the Karnaugh map corresponds to a
maxterm ( x 1 x 2 x 3 ) .
Theorem 24.1: Any logic function can be uniquely expanded with minterms and also with maxterms.
For example, f(x1, x2) = x1 x 2 x 3 can be uniquely expanded with the minterms as

x1 x2 x3 = x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x3
and also can be uniquely expressed with maxterms as

x1 x2 x3 = ( x1 x2 x3 ) ( x1 x2 x3 ) ( x1 x2 x3 ) .
These expansions have different expressions but both express the same function x 1 x 2 x 3 .
The following expansions, called Shannons expansions, are often useful.
Any function f(x1, x2, , xn) can be expanded into the following expression with respect x1:

f ( x 1, x 2, , x n ) = x 1 f ( 1, x 2, x 3, , x n ) x 1 f ( 0, x 2, x 3, , x n )
where f(1, x2, x3, , xn) and f(0, x2, x3, , xn), which are f(x1, x2, , xn) with x1 set to 1 and 0, respectively,
are called cofactors. By further expanding each of f(1, x2, x3, , xn) and f(0, x2, x3, , xn) with respect
to x2, we have

f ( x 1, x 2, , x n ) = x 1 x 2 f ( 1, x 2, x 3, , x n ) x 1 x 2 f ( 1, 0, x 3, , x n )
x 1 x 2 f ( 0, 1, x 3, , x n ) x 1 x 2 f ( 0, 0, x 3, , x n )

2000 by CRC Press LLC

Then we can further expand with respect to x3. And so on.

Also, similarly

f ( x 1, x 2, , x n ) = ( x 1 f ( 0, x 2, x 3, , x n ) ) ( x 1 f ( 1, x 2, x 3, , x n ) )
f ( x 1, x 2, , x n ) = ( x 1 x 2 f ( 0, 0, x 3, , x n ) ) ( x 1 x 2 f ( 0, 1, x 3, , x n ) )
( x 1 x 2 f ( 1, 0, x 3, , x n ) ) ( x 1 x 2 f ( 1, 1, x 3, , x n ) )
And so on.
These expansions can be extended to the case with m variables factored out, where m n, although
the only expansions for m = 1 (i.e., x1) and 2 (i.e., x1 and x2) are shown above. Of course, when m = n,
the expansions become the minterm and maxterm expansions.
Theorem 24.2: De Morgans Theorem
( x 1 x 2 x n ) = x 1 x 2 x n

and

( x 1 x 2 x n ) = x 1 x 2 x n

A logic function is realized by a logic network that consists of logic gates, where logic gates are realized
with hardware, such as transistor circuits.
De Morgans Theorem 24.2 has many applications. For example, it asserts that a NOR gate, i.e., a logic
gate whose output expresses the complement of the OR operation on its inputs, with noncomplemented
variable input x1, x2, , xn is interchangeable with an AND gate, i.e., a logic gate whose output expresses
the AND operation on its complemented variable inputs x1, x2, , xn, since the outputs of both gates
express the same function. This is illustrated in Figure 24.1 for n = 2.

FIGURE 24.1

Application of De Morgans theorem.

Definition 24.3: The dual of a logic function f(x1, x2, , xn) is defined as f ( x 1, x 2, , x n ) where f
denotes the complement of the entire function f(x1, x2, , xn) [in order to denote the complement
of a function f(x1, x2, , xn), the notation f ( x 1, x 2, , x n ) might be used instead of f ]. Let it be
denoted by f d(x1, x2, , xn). In particular, if f(x1, x2, , xn) = f d(x1, x2, , xn), then f(x1, x2, , xn)
is called a self-dual function.
For example, when f(x1, x2) = x1x2 is given, we have f d(x1, x2) = f ( x 1, x 2 ) = x 1 x 2 . This is equal
to x1x2 by the first identity of Theorem 24.2. In other words, f d(x1, x2) = x1x2. The function x1x2x2x3x1x3
is self-dual, as can be seen by applying the two identities of Theorem 24.2.
Notice that, if f d is the dual of f, the dual of f d is f.
The concept of a dual function has many important applications. For example, it is useful in the
conversion of networks with different types of gates, as in Fig. 24.2, where the replacement of the AND
and OR gates in Fig. 24.2(a) by OR and AND gates, respectively, yields the output function f d in Fig.
24.2(b), which is dual to the output f of Fig. 24.2(a).
As will be explained in a later chapter, a logic gate in CMOS is another important application example
of the concept of dual, where CMOS stands for complementary MOS and is a logic family, i.e., a type
of transistor circuit for realizing a logic gate. Duality is utilized for reducing the power consumption of
a logic gate in CMOS.
The following theorem shows a more convenient method of computing the dual of a function than
direct use of Definition 24.3.

2000 by CRC Press LLC

FIGURE 24.2

Duality relation between two networks.

Theorem 24.3: Generalized De Morgans Theorem Let f(x1, x2, , xn) be a function expressed by
and (and possibly also by parentheses and the constants 0 and 1). Let g(x1, x2, , xn) be a
function that is obtained by replacing every and by and , respectively, throughout the
logic expression of f(x1, x2, , xn) (and also, if 0 or 1 is contained in the original expression, by
replacing 0 and 1 by 1 and 0, respectively). Then,

fd(x 1, x2, , x n) = g(x 1, x 2, , x n)

For example, when f(x1, x2) = x1 x 2 x 3 is given, f d = x1 ( x 2 x 3 ) is obtained by this theorem.
Here, notice that in f, the calculation of precedes that of ; and in f d, the must correspondingly be
calculated first [thus, the parentheses are placed as ( x 2 x 3 ) ]. When f = x1 0 x2 x 3 is given, f d =
x1 (1 x2 x 3 ) results by this theorem. When f = x1 1 x2 x 3 is given, f d = x1 (0 x2 x3) results.
For example, the dual of x1 x2x3 is x 1 x 2 x 3 according to Definition 24.3, which is a somewhat
complicated expression. But by using the generalized De Morgans theorem, we can immediately obtain
the expression without bars, x1 (x2 x3) = x1x2 x1x3.

24.2 Implication Relations and Prime Implicants

In this section, we discuss the algebraic manipulation of logic expressions; that is, how to convert a given
logic expression into others. This is very useful for simplification of logic expression. Although simplification of a logic expression based on a Karnaugh map, which will be discussed in Chapter 25, is
convenient in many cases, algebraic manipulation is more convenient in many other situations.3
Definition 24.4: Let two logic functions be f(x1, x2, , xn) and g(x1, x2, , xn). If every vector (x1,
x2, , xn) satisfying f(x1, x2, , xn) = 1 satisfies also g(x1, x2, , xn) = 1 but the converse does not
necessarily hold, we write

f( x 1, x 2, , x n) g( x 1, x2, , x n)

(24.1)

and we say that f implies g. In addition, if there exists a certain vector (x1, x2, , xn) satisfying
simultaneously f(x1, x2, , xn) = 0 and g(x1, x2, , xn) = 1, we write

f( x1, x 2, , x n) g( x 1, x2, , x n)

(24.2)

and we say that f strictly implies g (some authors use different symbols instead of ). Therefore, Eq.
24.1 means f(x1, x2, , xn) g(x1, x2, , xn) or f(x1, x2, , xn) = g(x1, x2, , xn). These relations
are called implication relations. The left- and right-hand sides of Eq. (24.1) or (24.2) are called
antecedent and consequent, respectively. If an implication relation holds between f and g. That is, if
f g or f g holds, f and g are said to be comparable (more precisely, -comparable or implicationcomparable). Otherwise, they are incomparable.

2000 by CRC Press LLC

When two functions, f and g, are given, we can find by the following methods at least whether or not
there exists an implication relation between f and g; for example, using a truth table for f and g, directly
based on Definition 24.4. If and only if there is no row in which f = 1 and g = 0, the implication relation
f g holds. Furthermore, if there is at least one row in which f = 0 and g = 1, the relation is tightened
to f g. Table 24.1 shows the truth table for f = x 1 x 3 x 1 x 2 x 3 and g = x1x2. There is no row with f
= 1 and g = 0, so f g holds. Furthermore, there is a row with f = 0 and g = 1, so the relation is actually f g.
TABLE 24.1 Example for f g
x1
0
0
0
0
1
1
1
1

x2
0
0
1
1
0
0
1
1

x3
0
1
0
1
0
1
0
1

f
0
0
0
1
1
0
1
0

g
0
1
1
1
1
1
1
1

Although g implies f means if g = 1, then f = 1, it is to be noticed that g does not imply f does
not necessarily mean f implies g but does mean either f implies g or g and f are incomparable. In
other words, it does mean if g = 1, then f becomes a function other than the constant function which
is identically equal to 1. (As a special case, f could be identically equal to 0.) Notice that g does not
imply f does not necessarily mean if g = 0, then f = 0.
Definition 24.5: An implicant of a logic function f is a term that implies f.
For example, x1, x2, x1x2, , and x 1 x 3 x 2 are examples of implicants of the function x1x2. But x 1 x 2 is
not. Notice that x1x3 is an implicant of x1x2 even though x1x2 is independent of x3. (Notice that every
product of an implicant of f with any dummy variables is also an implicant of f. Thus, f has an infinite
number of implicants.) But x1x2 is not an implicant of f = x1x3 x 2 because x1x2 does not imply f. (When
x1x2 = 1, we have f = x3, which can be 0. Therefore, even if x1x2 = 1, f may become 0.) Some implicants
are not obvious from a given expression of a function. For example, x1x2 x 1 x 2 has implicants x2x3 and
x2x3x4. Also, x 1 x 2 x 2 x 3 x 1 x 3 has an implicant x3 because, if x3 = 1, x 1 x 2 x 2 x 3 x 1 x 3 becomes x 1 x 2
x2 x 1 = x1 x2 x 1 = (x1 x 1 ) x2 = 1 x2, which is equal to 1.
Definition 24.6: A term P is said to subsume another term Q if all the literals of Q are contained
among those of P. If a term P which subsumes another term Q contains literals that Q does not have,
P is said to strictly subsume Q.
For example, term x 1 x 2 x 3 x 4 subsumes x 1 x 3 x 4 and also itself. More precisely speaking, x 1 x 2 x 3 x 4
strictly subsumes x 1 x 3 x 4 . Notice that Definition 24.6 can be equivalently stated as follows: A term P is
said to subsume another term Q if P implies Q; that is, P Q. Term P strictly subsumes another term
Q if P Q.
Notice that when we have terms P and Q, we can say, P implies Q or, equivalently, P subsumes Q.
But the word subsume is ordinarily not used in other cases, except for comparing two alterms (as we
will see in Section 25.4). For example, when we have functions f and g that are not in single terms, we
usually do not say f subsumes g.
On a Karnaugh map, if the loop representing a term P (always a single rectangular loop consisting of
2i 1-cells because P is a product of literals) is part of the 1-cells representing function f, or is contained
in the loop representing a term Q, P implies f or subsumes Q, respectively. Figure 24.3 illustrates this.
Conversely, it is easy to see that, if a term P, which does not contain any dummy variables of f, implies
f, the loop for P must consist of some 1-cells of f, and if a term P, which does not contain any dummy
variables of another term Q, implies Q, the loop for P must be inside the loop for Q.

2000 by CRC Press LLC

(a) Term P implies a function f.

FIGURE 24.3

(b) Term P subsumes a term Q.

Comparison of imply and subsume.

The following concept of prime implicant is useful for deriving a simplest disjunctive form for a
given function f (recall that logic expressions for f are not unique) and consequently for deriving a
simplest logic network realizing f.
Definition 24.7: A prime implicant of a given function f is defined as an implicant of f such that no
other term subsumed by it is an implicant of f.
For example, when f = x1x2 x 1 x 3 x1x2x3 x 1 x 2 x 3 is given, x1x2, x 1 x 3 , and x2x3 are prime implicants.
But x1x2x3 and x 1 x 2 x 3 are not prime implicants, although they are implicants (i.e., if any of them is 1,
then f = 1). Prime implicants of a function f can be obtained from other implicants of f by stripping off
unnecessary literals until further stripping makes the remainder no longer imply f. Thus, x2x3 is a prime
implicant of x1x2 x 1 x 3 , and x2x3x4 is an implicant of this function but not a prime implicant. As seen
from this example, some implicants, such as x2x3, and accordingly some prime implicants are not obvious
from a given expression of a function. Notice that, unlike implicants, a prime implicant cannot contain
a literal of any dummy variable of a function.
On a Karnaugh map, all prime implicants of a given function f of at least up to four variables can be
easily found. As is readily seen from Definition 24.7, each rectangular loop that consists of 2i 1-cells,
with i chosen as large as possible, is a prime implicant of f. If we find all such loops, we will have found
all prime implicants of f. Suppose that a function f is given as shown in Fig. 24.4(a). Then, the prime
implicants are shown in Fig. 24.4(b). In this figure, we cannot make the size of the rectangular loops
any bigger. (If we increase the size of any one of these loops, the new rectangular loop will contain a
number of 1-cells that is not 2i for any i, or will include one or more 0-cells.)

FIGURE 24.4

Expression of prime implicants on Karnaugh maps.

2000 by CRC Press LLC

Consensus
Next, let us systematically find all prime implicants, including those not obvious, for a given logic function.
To facilitate our discussion, let us define a consensus.
Definition 24.8: Assume that two terms, P and Q, are given. If there is exactly one variable, say x,
appearing noncomplemented in one term and complemented in the other in other words, if P =
xP and Q = x Q (no other variables appear complemented in either P or Q, and noncomplemented
in the other) then the product of all literals except the literals of x, that is, PQ with duplicates of
literals deleted, is called the consensus of P and Q.
For example, if we have two terms, x 1 x 2 x 3 and x 1 x 2 x 4 x 5 , the consensus is x 2 x 3 x 4 x 5 . But x 1 x 2 x 3 and
x 1 x 2 x 4 x 5 do not have a consensus because two variables, x1 and x2, appear noncomplemented and
complemented in these two terms.
A consensus can easily be shown on a Karnaugh map. For example, Fig. 24.5 shows a function f =
x1x2 x 1 x 4 . In addition to the two loops shown in Fig. 24.5(a), which corresponds to the two prime
implicants, x1x2 and x 1 x 4 , of f, this f can have another rectangular loop, which consists of 2 1-cells with
i chosen as large as possible, as shown in Fig. 24.5(b). This third loop, which represents x2x4, the consensus
of x1x2 and x 1 x 4 , intersects the two loops in Fig. 24.5(a) and is contained within the 1-cells that represent
x1x2 and x 1 x 4 . This is an important characteristic of a loop representing a consensus. Notice that these
three terms, x2x4, x1x2, and x 1 x 4 , are prime implicants of f. When rectangular loops of 2i 1-cells are
adjacent (not necessarily exactly in the same row or column), the consensus is a rectangular loop of
2i 1-cells, with i chosen as large as possible, that intersects and is contained within these loops.
Therefore, if we obtain all largest possible rectangular loops of 2i 1-cells, we can obtain all prime
implicants, including consensuses, which intersect and are contained within other pairs of loops.
Sometimes, a consensus term can be obtained from a pair consisting of another consensus and a term,
or a pair of other consensuses that do not appear in a given expression. For example, x 1 x 2 and x2x3 of
x 1 x 2 x2x3 x 1 x 3 yield consensus x1x3, which in turn yields consensus x3 with x 1 x 3 . Each such consensus
is also obtained among the above largest possible rectangular loops.

FIGURE 24.5

Expression of a consensus on Karnaugh maps.

As we can easily prove, every consensus that is obtained from terms of a given function f implies f.
In other words, every consensus generated is an implicant of f, although not necessarily a prime implicant.

Derivation of All Prime Implicants from a Disjunctive Form

The derivation of all prime implicants of a given function f is easy, using a Karnaugh map. If, however,
the function has five or more variables, the derivation becomes increasingly complicated on a Karnaugh

2000 by CRC Press LLC

map. Therefore, let us discuss an algebraic method, which is convenient for implementation in a
computer program, although for functions of many variables even algebraic methods are too time
consuming and we need to resort to heuristic methods.
The following algebraic method to find all prime implicants of a given function, which Tison4,5 devised,
is more efficient than the previously known iterated-consensus method, which was proposed for the
first time by Blake in 1937.2
Definition 24.9: Suppose that p products, A1, , Ap, are given. A variable such that only one of its
literals appears throughout A1, , Ap is called a unate variable. A variable such that both of its literals
appear in A1, , Ap is called a binate variable.
For example, when x 1 x 2 , x 1 x 3 , x 3 x 4 , and x 2 x 4 are given, x1 and x4 are binate variables, since x1 and
x4 as well as their complements, x 1 and x 4 appear, and x2 and x3 are unate variables.
Procedure 24.1: The Tison Method Derivation of All Prime Implicants of a Given Function
Assume that a function f is given in a disjunctive from f = P Q T, where P, Q, , T are
terms, and that we want to find all prime implicants of f. Let S denote the set {P, Q, , T}.
1. Among P, Q, , T in set S, first delete every term subsuming any other term. Among all binate
variables, choose one of them.
For example, when f = x1x2x4 x 1 x 3 x 2 x 3 x2x4 x 3 x 4 is given, delete x1x2x4, which subsumes
x2x4. The binate variables are x3 and x4. Let us choose x3 first.
2. For each pair of terms, that is, one with the complemented literal of the chosen variable and the
other with the noncomplemented literal of that variable, generate the consensus. Then add the
generated consensus to S. From S, delete every term that subsumes another.
For our example, x3 is chosen as the first binate variable. Thus we get consensus x1x2 from pair x1x3
and x 2 x 3 , and consensus x 1 x 4 from pair x1x3 and x 3 x 4 . None subsumes another. Thus, S, the set of
prime implicants, becomes x1x3, x 2 x 3 , x2x4, x 3 x 4 , x1x2, and x 1 x 4 .

3. Choose another binate variable in the current S. Then go to Step 2. If all binate variables are
tried, go to Step 4.
For the above example, for the second iteration of Step 2, we choose x4 as the second binate variable
and generate two new consensuses as follows:

But when they are added to S, each one subsumes some term contained in S. Therefore, they are
eliminated.

2000 by CRC Press LLC

4. The procedure terminates because all binate variables are processed, and all the products in S are
desired prime implicants.
The last expression is called the complete sum or the all-prime-implicant disjunction. The complete
sum is the first important step in deriving the most concise expressions for a given function.

Generation of prime implicants for an incompletely specified function, which is more general than
the case of completely specified function described in Procedure 24.1, is significantly speeded up with
the use of BDD (described in Chapters 24.1 and 24.4) by Coudert and Madre.1

References
1. Coudert, O. and J. C. Madre, Implicit and incremental computation of primes and essential primes
of Boolean functions, Design Automation Conf., pp. 36-39, 1992.
2. Brown, F. M., The origin of the iterated consensus, IEEE Tr. Comput., p. 802, Aug. 1968.
3. Muroga, S., Logic Design and Switching Theory, John Wiley & Sons, 1979 (now available from
Krieger Publishing Co.).
4. Tison, P., Ph.D. dissertation, Faculty of Science, University of Grenoble, France, 1965.
5. Tison, P., Generalization of consensus theory and application to the minimization of Boolean
functions, IEEE Tr. Electron. Comput., pp. 446-456, Aug. 1967.

2000 by CRC Press LLC