A set is a collection of distinct objects, and the objects, called the members of the set, are enclosed in a pair of curly braces. Set S, consisting of alphanumeric symbols x, 2, $, 3, %, and L2, can be written as S = {x, 2, $, 3, %, L2}. Inside the braces can be a qualification expression for the set members. For example, F = {p : p is a prime and p = 2ⁱ-1} represents the set of all prime numbers that can be expressed in the form 2ⁱ-1 for some integer i. The expression after the colon is the qualification expression. Sometimes a vertical bar is used in place of the colon: F = {pp is a prime and p = 2ⁱ-1}. Set U is often denoted as the universal set that consists of everything in the context. For example, in the context of integers, U consists of all integers. Set Z usually denotes the set of all nonnegative integers, whereas R represents the set of all real numbers. Z⁺ and R⁺ are positive integers and positive real numbers respectively. The number of elements in set S, called the cardinality of S, is denoted by |S|.

Membership in a set, such as x is a member of S, is denoted by x∉S. Similarly, y is not a member of S is denoted by y ∉ S. Using the previous definition of set F, we have 7 ∊ F and 11 ∉ F. Symbols ∀s and ∃s mean “for all variable s” and “for some variable s” respectively. Set V is a subset of set W, denoted as V⊆W, if ∀ s ∊ V⇒s ∊ W, which says, for every element s in set V, s is also in W. Symbol x ⇒ y means “x implies y”. If there is at least one element in W that is not in V,V is said to be a proper subset of W and is denoted as V ⊂ W. The equality sign is removed.

Compositions of sets can be defined in terms of the previous notations. If sets A and B are sets, then

This is called the intersection of A and B, which is the set of all elements common to A and B. Using sets S and F, we see that S ∩ F = {3}. If A and B do not have common element, the intersection is empty: A∩B = Ø. Two sets with an empty intersection are said to be disjoint.

The union of A and B is defined as

which is the set of all elements in A or B. Obviously, A⊆(A∪B), (A∩B)⊆A, and (A∩B)⊆(A∪B).

The Cartesian product A×B is defined as

The Cartesian product is a common method used to construct higher dimensional space from lower dimensional spaces. For example, the set of all positive rational numbers, K, can be constructed from positive integers and can be represented as K = {(a, b) | a and b are positive integers}, where a can be treated as the numerator and b, the denominator.

These set operations can be extended to a finite number of operands:

An element in a Cartesian product of k sets, denoted as (n_l,...,n_k), is called a k-tuple. It can be regarded as a point in the k-dimensional space.

The exclusion of B from A, or subtraction of B from A, is defined as

which is the set of all elements in A but not in B. As an example, the set of all positive integers Z⁺ is Z-{0}, and the set of all positive irrational numbers is R⁺–K. If U is the universal set, then U-B is called the complement of B, denoted by .

Mapping μ between two sets S₁ and S₂, denoted by μ(S₁,S₂), associates each element in S₁ with an element or a subset in S₂. An example of a mapping is the procedure that takes in a photograph and outputs all colors in the photograph. In this example, S₁ is a set of photographs and S₂ is a set of colors.

A mapping that associates an element in S₁ with only one element in S₂ is called a function. That is, a function maps one element S₁ to exactly one element S₂. However, a function can map several elements in S₁ to the same element in S₂. Set S₁ is called the domain, and S₂ is called the image or range of the function. A function or mapping that maps distinct elements in S₁ to distinct elements in S₂ is called a one-to-one function or one-to-one mapping.

The relation γ between S₁ and S₂ is the function γ(S₁×S₂, {0,1}). For x ∊ S₁ and y ∊ S₂, we say a relation exists between x and y if γ(x,y) = 1. An example of a relation is the less than relation, <, on real numbers. Relation < maps (2,3) to 1 because 2<3 exists. But it maps (5,1) to 0. For simplicity, we denote x related to y by γ(x,y). Furthermore, for γ(S×S, {0,1}), we say γ is a relation on S.

A partition of set S, λ = {A_l,...,A_n}, is a collection of subsets of S, A_l,...,A_n, such that

and

In words, a partition of set S is a division of S into disjoint subsets, which together make up S. Subsets A₁,...,A_n are called the elements of the partition.

For notational convenience, let’s use overlines and semicolons to denote a partition. For the partition in the previous example, we have

A relation γ on S is an equivalence relation if it satisfies the following conditions:

An equivalence relation is denoted by ~; for example, x ~ y if x is equivalent to y. As an example, a nonequivalent relation is relation <, because it is not reflexive. For example, 2<2 does not exist. An example of an equivalence relation is the equality on real numbers, =. The main use of an equivalence relation is to partition a set to find all equivalent elements. When all equivalent elements are combined as a single element, the resulting set, called the quotient set, becomes smaller and easier to manipulate.

Given an equivalence relation ~, we would like to find a procedure to reduce a set based on the equivalence relation ~. Define S_x as the set {s : s ~ x where x ∊ S}. That is, S_x is a subset of S, whose elements are equivalent to x. Element x can be regarded as a representative element of S_x and S_x, as the equivalence neighborhood of x. If we find all representative elements in S, then S can be reduced to a set made of only representative elements. Theorem 7.1 guarantees this possibility.

Part 1 of this theorem says that any two equivalent elements must belong to the same subset. Part 2 says that any two nonequivalent elements must be in two different subsets. In other words, S is broken into equivalent subsets, each of which is the maximal equivalent subset. The subsets are maximal because of the definition of S_x. The pairwise nonequivalent elements in part 3 can be regarded as the representatives of the equivalent subsets, each representing all the elements to which it is equivalent. Therefore, λ is the equivalent partition with the minimum |λ|. That is, any other partition of S based on ~ has a greater or equal cardinality. λ is the coarsest partition.

This theorem states a method of maximally partitioning a set such that all elements of any subset are equivalent. To create the partition, take any element x, find all its equivalent elements, and make them into a subset S_x. Any elements not included in S_x must be not equivalent to x. Take any remaining elements and repeat this process. The partition ends when all elements have been included in a subset. This is summarized in the following list. Given an equivalence relation γ on set S, partition S according to γ.

Note that the relation must be an equivalence relation; otherwise, the subsets formed are not a partition, as seen in Example 7.2.

Of the three conditions for equivalent relation, if we replace the symmetric property with the asymmetric property, we have an ordering relation. An ordering relation is a generalization of the usual ≥ operator on real numbers. The meaning of an ordering relation extends beyond mere magnitude comparison; it is a more abstract concept of comparison. An ordering relation, x≥y, satisfies the following three conditions:

The mathematical structure made of a set and an ordering relation is called a partially ordered set, or poset. The ordering relation operates on the elements of the set and arranges them according to the relation. It is called “partially ordered” because not all pairs of elements have a relation. Using the β(s, r) relation from Example 7.3, s ≥ r if r is a substring of s. In other words, s contains or subsumes r. However, no order exists for these two strings s = abc and r = xy, because we can write neither s ≥ r nor r ≥ s. That is, β cannot order s and r.

One way to visualize ordering of a poset is to use a Hasse diagram. For two elements, x and y, we say x covers minimally y if x≥y, and for all z ≥ y, z ≥ x. That is, x is the smaller element that is greater than y. If x covers minimally y, we draw a downward line from node x to node y. It may be clearer to draw an arrow from x to y, but a Hasse diagram traditionally does not rely on arrows but north-south direction.

Example 7.4

Draw a Hasse diagram for the following partially ordered set

with at least two entries equal to 1, where a_ij ∊ {0, 1}.

We define s₁ ≥ s₂ if a_ij in s₁ is 1, then a_ij in s₂ is also 1. For example,

also covers

There are eleven such matrices and their relations are shown in Figure 7.1.

Because of the transitive property, we see that if there is a descending path from p to q, then p ≥ q. If there is no descending path between the two nodes, no relation exists between them.

Figure 7.1. Hasse diagram for 2 × 2 Boolean matrices

Between two elements in a partially ordered set, we can define meet and join. A meet z between elements x and y is the greatest lower bound of x and y. That is, x ≥ z and y ≥ z. If there is an element w, such that x ≥ w and y ≥ w, then z ≥ w. We denote a meet between x and y by x · y. In Figure 7.1, the meet of

and is

Note that there may not be a meet between any two elements. For instance,

and do not have a meet.

Similarly, a join between two elements x and y, denoted as x + y, is the least upper bound of x and y. That is, join z of x and y is the smallest element such that z ≥ x and z ≥ y. In Figure 7.1, the join between and is . Note that is not a join because is smaller than and is greater than both and .

Understanding meet and join as the greatest low bound and the least upper bound, it is easy to see that Theorem 7.2 is intuitively reasonable.

As we have seen, not all pairs of elements have a meet or a join. However, when every pair of elements in a partially ordered set have a meet and a join, we call this mathematical structure (the set together with the meet and join operator) a lattice.

The set of partitions form a lattice if the meet and join are defined carefully. We define the meet of two partitions π₁ · π₂ to be a partition formed by the intersection of the elements in π₁ and π₂. That is, an element in the meet partition is an intersection of an element in π₁ and an element in π₂. We define the join, π₁ + π₂, to be a partition formed by the union of all chain-connected elements in π₁ and π₂. Two sets, S₁ and S_n, are chain connected if there exists a sequence of sets, S₂, ..., S_{n - 1}, such that S_i and S_{i + 1} have a nonempty intersection for i = 1, ..., n - 1. It can be proved that with this definition of meet and join, the set of partitions constitutes a lattice.

Example 7.5

Find the meet and join of the following partitions

The meet partition is obtained by intersecting the subsets of the two partitions. For example, subset {a,b,c} of π₁ intersects {a,b} of π₂ to give subset {a,b} in π₁ · π₂. Performing intersections between the subsets, we get

To obtain the join partition, we grow its elements gradually, starting with two overlapping subsets, one from π₁ and another from π₂. For example, subset {a,b,c} of π₁ and subset {a,b} of π₂ have a nonempty intersection; thus, they are chain connected. Now element c connects to other subsets. Specifically, subset {a,b,c} of π₁ and subset {c,g,h} of π₂ have a nonempty intersection, so they are chain connected. So far these subsets {a,b}, {a,b,c}, and {c,g,h} are chain connected. Then elements g and h connect more elements from π₁ (namely i) which connects j and k in π₂. So, subsets {a,b}, {a,b,c}, {c,g,h}, {g,h,i}, and {i,j,k} are chain connected. This chain connection stops at subset {j,k} of π₁ because it does not connect any more new elements. Therefore, the first subset in the join partition is the union of previous chain-connected subsets, giving {a,b,c,g,h,i,j,k}. The second subset starts with a subset not yet included, say {d,e} of π₁. {d,e} connects with {d,e,f} of π₂ and f is a subset by itself. Thus, the second subset of the join is {d,e,f}. The result is

Let B denote the set {0, 1}. A Boolean function of n variables is a mapping from Bⁿ to B, written as . An example is .

The set of variables in a Boolean function is called the support, denoted by supp(f). Thus, for the previous example function, supp(f) = {a,b,c}. Even when a variable is redundant in a function (that is, it does not affect the result of the function), the variable is still included in the support. For instance, variable r in is redundant, but supp(g) = {a, b, r}. If only nonredundant variables are required, the term minimum support is used to include only the nonredundant variables.

A Boolean function can be represented in many ways. Let’s briefly review some common forms of representation. A sum of products representation is the ORing of all AND terms. An AND term, a product term, is also called a cube. A sum of products is written as

where x_i, x_j, ..., x_n are literals. A literal is either a variable or the complement of the variable. Each product term or cube x_ix_j...x_n need not have all variables present. If a product term has all variables, it is called a minterm or vertex. The sum of products representation is also called disjunctive normal form (DNF).

For example, consider function . It is a sum of products representation. It has three cubes. There are six literals—namely, a, , , c, b, and . The last cube, , is a minterm.

Similarly, a Boolean function can be represented as a product of sums, or conjunctive normal form (CNF), as written here:

where x_i, x_j, ..., x_n are literals. Each sum term need not have all variables present. A sum term, the counterpart of a cube, is called a clause. If all variables are present in a clause, the term is called a maxterm.

Finally, a Boolean function can be written in a form mixed with sums of products and products of sums. This form is generically called multilevel representation. A sum of products can be implemented as a two-level circuit, with the first level being AND gates and the second, an OR gate. Similarly, a product of sums can be implemented as a circuit with a layer of ORs followed by an AND gate. Therefore, a mixed representation calls for multiple levels of gates to implement, hence the name. An example is .

Example 7.6

Convert the following CNF to DNF and vice versa:

First, we convert f to DNF. This can be done by simply multiplying the terms. After multiplying the four clauses and simplifying, we get

To convert g from DNF to CNF, we first use De Morgan’s law to obtain in CNF and to multiply the clauses to get the CNF of . Finally, we obtain the CNF of g by complementing using De Morgan’s law:

Multiplying the clauses, we have

Now, complement g and use De Morgan’s law to obtain DNF:

Another way of obtaining DNF from CNF is to use the second form of the distributive laws of Boolean algebra stated here:

To many people, the first form is probably more familiar than the second. However, they are related through the duality principle of Boolean. The duality principle of Boolean Algebra states that by replacing AND with OR, OR with AND, 1 with 0, and 0 with 1 in a Boolean identity, we arrive at another Boolean identity. Suppose we start with identity

and apply the exchange operations of duality. We get

which is the second form of the distributive law.

Example 7.7

Let us use the second form of distributive law to convert to CNF.

To verify that our conversion is correct

As far as representation size is concerned, it is difficult to know when CNF or DNF is more compact. It is known that there are functions with a CNF that is of polynomial size in number of variables expands to a DNF of exponential size, and vice versa. A research result relating the size of CNF to DNF has the following bounds^[1] . If function f has n variables and its CNF size is less than m, then its DNF size, ||f(n,m)||_dnf, is bound by the following expression, where c₁ and c₂ are constants:

Given a function f in DNF, the problem of satisfying f is to determine whether there is an assignment of variables for which f evaluates to 0 (that is, whether f has a nonempty offset). Similarly, if f is in CNF, the satisfiability problem is to determine whether f can evaluate to 1 (in other words, f has a nonempty on set).

A brute-force method to solve the satisfiability problem is to expand the function into minterms or maxterms. This approach, in the worst case, encounters exponential numbers of terms and is practically infeasible, because the satisfiability problem is NP complete. We return to this topic in a later chapter.

Symmetric Boolean Functions

Symmetric Boolean functions have some interesting properties and lend themselves to computational efficiency. A Boolean function can be regarded as a function of literals. For instance, is a function of literals a, , and c, as opposed to a function of variables a, b, and c. With this clarification, we say that a Boolean function f(x₁,...,x_n) is symmetric with respect to a set of literals, x₁,...,x_n, if the function remains unchanged by any permutation of the literals. That is, f(x₁,...,x_n) = f(x_σ(1),...,x_σ(n)), where σ is a permutation map, which is a one-to-one mapping from {1,...,n} to {1,...,n}. An example of σ is the following: 1 maps to 2, 2 to 3, n to 1. In this case, f(x_σ(1),...,x_σ(n)) = f(x₂,x₃,...,x_n,x₁). It should be emphasized that x_i is a literal, not a variable. In the previous example function, x₁ =a, , and x₃ =c.

It can be cumbersome to use this intuitive definition to determine whether a function is symmetric. Theorem 7.3 alleviates this task.

Theorem 7.3

Function f(x₁,...,x_n) is symmetric if and only if there exists a set of integers I = {a_i: i = 0, ...,m ≤ n}, such that f(x₁,...,x_n) is 1 when exactly a_i literals of symmetry are 1.

For example, takes the value of 1 if and only if zero or two of the literals a, , or c have the value of 1, no matter which two. Therefore, this function is symmetric and I = {0, 2}. Consider function . When a = 0, b = 1, and c = 1, the function evaluates to 1. However, when a = 1, b = 1, and c = 0, which also has two literals being 1, the function fails to evaluate to 1. Therefore, evaluation of this function does depend on which literals have the value of 1. Thus, we conclude, according to Theorem 7.3, that this function is not symmetric with respect to literals a, b, and c.

Interestingly, if we rewrite the function as a function of literals a, b, and , and replace with d, we have , which is symmetric with respect to a, b, and d. That is, the function is symmetric with respect to a, b, , but not with respect to a, b, c. This example shows why we need to treat symmetric functions with respect to literals, instead of variables.

Theorem 7.3 makes sense in that if a function is symmetric, then only the number of literals, not the specific literals, matters in determining the function’s output value, because a symmetric function cannot distinguish literals. Because the number of literals being 1 uniquely determines the function’s value, symmetric functions can be represented succinctly by the set I—in other words, Sⁿ_I(x₁,...,s_n), where n denotes the number of variables in the function. For example, symmetric function is represented as S³_0.2(a,b,c), and , by S³₁ .

With these notations for symmetric functions, manipulation of symmetric functions becomes easy with Theorem 7.4. Logical operations become set operations on the indices.

Theorem 7.4

Given symmetric functions and , the following holds:

Parts 1 and 2 state that ORing and ANDing of two symmetric functions amount to union and intersection of their respective index sets. The ORed result is 1 when at least one of its operands evaluates to 1. This means that the number of literals being 1 in the ORed result is in either or both index sets, giving rise to the union of the index sets. Similar reasoning applies to ANDing. In part 3, ⌝I denotes the complement of the index set I: ⌝I = {1,...,n}-I So, complementing a function amounts to complementing the index set. The complement of a function being 1 means the function itself is 0, meaning the number of literals being 1 is not in the index set. In part 4, n - I = {j : j = n - i, i ∊ I}, and it states that complementing the literals translates to complementing the individual indices.

Example 7.8

Determine whether the following function is symmetric. Also, compute the complement of the function:

We need to know whether the number of literals being 1 uniquely determines the function’s value. To start, we represent the function in a truth table (Table 7.1). Only the values giving the function a value of 1 are shown.

From Table 7.1 we see that the function’s value is not solely determined by the number of 1 in literals a, b, c, and d. For example, 0100 gives output 1 but not 1000. Therefore, the function is not symmetric with respect to literals a, b, c, and d.

However, it is possible that for other literals, the function is symmetric. We can invert some of the literals, change the values in the table, and determine whether the function becomes symmetric. By complementing variables a and c, we get the symmetric functions seen in Table 7.2.

From Table 7.2 we see that as long as three or four literals are 1, the function is 1. Therefore, the function is symmetric with respect to literals , b, , and d. In terms of these literals,

The function can be represented as . Once the function is symmetric, its complement can be computed readily, using Theorem 7.4. . Expanding this to the sum of products, we have

Table 7.1. Determining Functional Symmetry

(a,b,c,d)
0100
1101
0001
0111
0101

Table 7.2. Symmetric Function

1110
0111
1011
1101
1111

Incompletely Specified Boolean Functions

A Boolean function can also be characterized by its on set, off set, and don’t-care set. An on set is the set of vertices that make the function 1; and an off set, 0. A don’t-care set is the set of vertices on which the function is not specified or a don’t-care. The union of on set, off set, and don’t-care set makes up the universe. If a Boolean function is completely specified, then the don’t-care set is empty; otherwise, the function is incompletely specified.

Example 7.9

The on set, off set, and don’t-care set representation can be displayed spatially for functions with a smaller number of variables. Consider function

Refer to Figure 7.2. Three axes represent variables a, b, and c respectively. Each axis has only two values: 0 at the original and 1 at the far end. The coordinates are the values of the variables. For instance, 101 means a = 1, b = 0, and c = 1, and hence represents minterm .

The function is completely specified and its on set is all vertices in the expression. To see the vertices in the on set, we expand the three cubes into minterms. Cube is equal to . Therefore, .

Each minterm is a vertex in the on set. Mark the vertices on the cube as small solid circles. Because the function is completely specified, the remaining vertices are in the off set, marked as small squares.

The vertices, if grouped as shown, and each group of two vertices corresponds to a cube, produce the three cubes , , and . Therefore, the function is also equal to

which is obvious from the spatial representation but not so in the sum-of-products form.

Figure 7.2. A spatial representation of a Boolean function

Characteristic Functions

Representing incompletely specified Boolean functions becomes more complicated because a single incompletely specified Boolean function requires at least two Boolean expressions to represent: one for the on set and the other for the off set or don’t-care set. The matter becomes more so in multiple-output Boolean functions. An example of a multiple-output Boolean function is the next-state function of a finite-state machine with two D-type FFs. The next-state function has two components: f(v) = (f₁(v), f₂(v)), f₁ for the first FF and f₂ for the second. A multiple-output Boolean function is also called a vector Boolean function.

To deal with multiple-output Boolean functions, one may suggest treating each component as a function and representing each output function with its on set, off set, and don’t-care set. A difficulty arises when the output of a multiple-output Boolean function takes on more than one value at a given input value. For example, when v = 1011, f(v) can be either 11 or 00. It may be tempting to deduce that 1011 represents a don’t-care point in each of the output functions. The erroneous reasoning is that f₁(1011) is either 1 or 0; thus, f₁(1011) is a don’t-care. The same reasoning applies to f₂(1011). Therefore, f(1011) = (*,*), where * represents a don’t-care. The fallacy is that by assuming that f₁(1011) and f₂(1011) are don’t-cares, the output don’t-care points include not just 11 and 00, but also 10 and 01, because (*,*) means either component can be any value. However, the problem states that for 1011, the output can be only 11 or 00. The root cause of this difficult is that in this case the multiple-output Boolean function is no longer a function but a relation, because it maps an input value to more than one output value. In the single-output situation, we simply use a don’t-care set to solve this multivalue output problem, but this technique no longer works for the multioutput situation.

To represent a Boolean relation, characteristic function plays a vital role. A characteristic function λ(S) representing set S is defined as follows:

For a Boolean relation with input vector v and output vector w, the characteristic function is λ(v, w) and the set S is all I/O pairs describing the Boolean relation. In other words, λ(v, w) is 1 if w is an output for input v, and it is 0 otherwise.

Example 7.10

Use characteristic functions to represent the following Boolean relations.

1. A completely specified Boolean function,

2. An incompletely specified Boolean function f(a,b,c), with on set equal to {110, 010, 001} and don’t-care set, {111, 000}.

3. An incompletely specified Boolean relation f(v) = (f1(v),f2(v)),v = (a,b,c), described by Table 7.3 on page 353.

   1. Let λ(y,a,b,c) be the characteristic function, where variable y is the output value. The input-output pairs are {(y,a,b,c):y = 1 if f(a,b,c) = 1 and y = 0 if f(a,b,c) = 0}. Therefore, the characteristic function is defined as follows: λ(y,a,b,c) = 1 if . Substituting the equation for f, we get:

      

      As check, we know that f(101) = 1. Substitute y = 1, a = 1, b = 0, and c = 1 into λ(y,a,b,c), and we get 1, as expected. Suppose we substitute y = 0, a = 1, b = 0, and c = 1 into λ(y,a,b,c). We should get 0, because this output value is not produced by the input vector. A little calculation shows that λ(1,1,0,1) = 0.

   2. The only difference from (a) is the don’t-care points. A don’t-care point simply implies that variable y can be either 1 or 0. Therefore, the characteristic function λ(y,a,b,c) is

      

      The first group of terms represents the on set; the second, the off set; and the third, the don’t-care set. We obtained the off set by subtracting the on set and the don’t-care set from the universe.

   3. Let y and z be the variables for output f₁ and f₂ respectively. Let’s go through Table 7.3 one row at a time. At each row we add a term to the characteristic function. The term describes, in Boolean form, the relation between the I/O values. For example, the first row gives because output is 10 when input is 001. Then the characteristic function is

      

      The first two cubes come from the first two entries of the table. The next two groups of terms are from the third and the fourth entries, each of which have two output values. The two output values are ORed because either output value is possible. The last group of terms comes from the last entry of the table, which consists of all remaining minterms.

Table 7.3. Specification of a Vector Boolean Relation

v = (a,b,c)	f = (f1,f2)
001	(1,0)
011	(0,1)
101	(1,1) or (0,0)
110	(1,0) or (1,1)
all other values	(0,0)

In this section, we will study some common operators encountered in formal verification. Cofactor operation on function f with respect to a variable x has two phases—a positive and negative phase—denoted by f_x and respectively. Cofactor f_x is computed by setting variable x to 1, whereas is computed by setting x to 0. Therefore, f_x and are functions without variable x. Functions f_x and can be further cofactored with respect to other variables. For example, cofactoring with respect to variable y gives (f_x)_y, which is written as f_xy. It can be shown that f_xy = f_yx. Function f is related to its cofactors through the following Shannon theorem (Theorem 7.5).

Theorem 7.5 Shannon Expansion Theorem

Any Boolean function f can be expressed in the following forms, where x is a variable of f:

The Shannon cofactor can be applied successively to all variables in a function. For example, a function with two variables, x and y, can be expressed as

This last equation is a minterm expansion of the function. Because the function has only two variables, the cofactors, , and , are either 1 or 0. Therefore, Shannon expansion can be regarded as a partial evaluation.

This cofactor definition, sometimes called the classic cofactor, is based on a cube; that is, the c in cofactor f_c is cube. The generalized cofactor function of a vector Boolean function f, f_g, allows g to be any Boolean function and is defined as

where * denotes a don’t-care value. It is tempting to assume that f_g is equal to fg, which gives f when g = 1. The following exercise shows that they are not the same.

Example 7.12

Express the generalized cofactor function using a characteristic function. From the definition, the characteristic function is

where variable y is the value of the cofactor, and x₁ through x_n are the variables in f and g. The function is 1 if y has the same value as f when g is 1 or y can be any value (such as don’t-care), when g is 0, which is exactly the definition of generalized cofactor.

Let’s apply this technique to computing the generalized cofactor and . Using a characteristic function to represent f_g, we have

To check, let a = b = c = d = 0. Then, g = 1 and , which means the value of the cofactor is 0, consistent with the value of f because g = 1. Let a = 1 and c = 0. Then g = 0. So the cofactor is a don’t-care, meaning the characteristic function should be 1 independent of y. λ(y, 1, b, 0, d) = 1, as expected.

The Boolean difference of function f with respect to variable x, , is defined to be

If the Boolean difference of a function with respect to variable x is identically equal to 0, then the function is independent of x, because the cofactors with respect to x are equal, meaning the function remains the same whether x takes on the value of 1 or 0. Therefore, x is in the minimum support of a function if and only if its Boolean difference is not identically equal to 0.

The concept of Boolean difference is used widely in practice. For example, to determine whether a circuit can detect a stuck-at fault at node x, the decision procedure is equivalent to determining whether there is an input vector v such that

where f is the function of the circuit with the fault site x made as a primary input.

The problem of deciding whether a value v exists such that function f(v, w) evaluates to a specific function g(w) is called the existential problem, and is often denoted by the existential operation as ∃vf(v,w)≡g(w), To compute an existential problem, we simply enumerate all possible values of input v, evaluate the function on each of them, and OR together all outputs. If the result is equal to g(w), then such an input value exists. This procedure of computing existential operation in mathematical form is

where f_m(v, w) is a cofactor with respect to minterm m. For instance, if the existential operator is on two variables, x and y, then all minterms are . This summation can be regarded as a Boolean operation for evaluating the existential operation. This operator, called the smooth operator, is

A special case is when the existential operator is on a single variable, say x. Then the equation becomes

The counteroperator of the existential operator is the universal operator. An example of an application of a universal operator is deciding whether function f(v, w) is always equal to some specific function g(w) for all values of v. This is denoted by ∀vf(v,w)≡g(w). To compute this universal operation, we can evaluate f(v, w) for each of possible values of v and AND the outputs. If the result is g(w), the answer is yes. Mathematically, the computation is

If the function has a single variable x,

In computer science literature, finite-state automata are used in the place of finite-state machines, with minor differences. A finite-state automaton accepts input symbols and transits just like a finite-state machine, but it does not produce any output as in a finite-state machine. By adding an output function to an automaton, we have a finite-state machine or a transducer. Furthermore, a finite-state automaton has a set of states designated as acceptance states that do not have a counterpart in finite-state machines.

A finite-state automaton is a mathematical object with five components, or a quintuple, (Q, Σ, δ, q₀, F), where Q is the set of states, Σ is the set of input symbols, δ is the transition function with δ: Q×Σ → Q, q₀ is an initial state, and F is a set of states designated as acceptance or final states. The transition function δ is based on the current state and an input symbol, and it produces the next state. Another way to represent δ is qⁱ⁺¹ = δ(qⁱ, a), where qⁱ is the present state at cycle i, qⁱ⁺¹ is the next state, and a ∊ Σ is an input symbol.

A transducer or finite-state machine is a 6-tupe (Q, Σ, Λ, δ, μ, q₀), where Λ is the set of output symbols and μ is the output function with μ : Q×Σ → Λ. The output function here assumes the Mealy machine model in that the output is a function of both the current state and the input symbol. For a Moore machine, the output function is simply μ : Q → Λ.

A finite-state automaton can be depicted with a state diagram. A state diagram is a directed graph with nodes and directed edges connecting the nodes. A node is a state, and an edge is a transition. An input symbol that activates a transition is placed on an edge. An initial state is marked with a wedge, and an acceptance state is twice-circled node. In a finite-state machine, the output symbol is placed on a node if it depends only on the state (Moore machine); otherwise, it is placed over an edge (a Mealy machine).

Figure 7.3. (A) A finite-state automaton (B) A finite-state machine

So far, the automata and state machines discussed are deterministic, because their states over time can be predicted or determined. A nondeterministic finite-state automaton or finite-state machine, as an extension of the previous definitions, can have more than one initial state, or more than one next state on an input symbol, or a transition on no input symbol. It can be shown that nondeterministic finite-state automata can be transformed into a deterministic finite-state automaton with enlarged state spaces.

A finite-state automaton is completely specified if the next state is specified for every input symbol and every present state. Otherwise, it is incompletely specified. For finite-state machines, the additional requirement is that the output symbol is specified for every state in a Moore machine and for every state and input symbol in a Mealy machine.

Figure 7.4 shows a nondeterministic finite-state automaton and an incompletely specified finite-state machine. In Figure 7.4A, the automaton has two initial states: q₀ and q₁. Furthermore, state q₁ transits to states q₀ and q₂ on input symbol b. State q₂ can nondeterministically transit to q₃, even though no input symbol is present. In Figure 7.4B, ? denotes unspecified output. Furthermore, state q₀ does not specify the next state on input symbol c.

Figure 7.4. (A) A nondeterministic finite-state automaton. (B) An incompletely specified finite-state machine.

An input symbol makes an automaton transit from one state to another. Thus, a string of input symbols causes an automaton or a state machine to make a sequence of state transitions. A string of finite length is accepted if the automaton terminates at a final or acceptance state q_f (in other words, q_f ∊ F). The set of all accepted strings of an automaton is the language of the automaton.

Using ending states as a condition for acceptance is just one of many possible ways of defining string acceptance and hence the language of an automaton. In fact, different kinds of acceptance conditions give rise to different types of automata. The previous definition of acceptance will not work for defining acceptance of strings of infinite length. As an example of a different kind of acceptance condition, consider the following acceptance condition of infinite strings. An infinite string is accepted if the set of states visited infinitely often is a subset of the final state set F. A state is visited infinitely often if for every N, there is M > N such that the state is visited at cycle M. Automata with this acceptance condition are called Buchi automata. Symbolically, a Buchi automaton is a quintuple, (Q, Σ, δ, q₀, F), with the acceptance condition that {q| q is visited infinitely often}⊆F.

Sometimes, one may be curious about situations when infinite strings may arise in practice. Indeed, all hardware machines are designed to function continuously over time, and therefore it is only realistic, although a bit counterintuitive, to assume that all input strings are of infinite length.

Product Automata and Machines

A system can consist of more than one finite-state machine that interact with each other. An example is a traffic light controller at a street intersection. There are four controllers required, one for each direction. These four controllers do not operate independently but take into consideration inputs from other controllers. Cars sensed waiting on the north–south-bound intersection prompt the east–west controller to move to red in the next cycle. Sometimes one must model a system of multiple interacting finite-state machines as one single finite-state machine. The resulting overall finite-state machine is called the product finite-state machine.

Given two finite-state machines, M₁ = (Q₁, Σ₁, Λ₁, δ₁, μ₁, q¹₀) and M₂ = (Q₂, Σ₂, Λ₂, δ₂, μ₂, q²₀), the product machine M = M₁×M₂ is defined as (Q, Σ, Λ, δ, μ, q₀), where

M₁ and M₂ are called the component machines of M. If Σ₁ and Σ₂ are identical, then Σ is either Σ₁ or Σ₂ instead of a Cartesian product of the two.

Example 7.15

Let’s compute the product machine of the following two finite-state machines shown in Figure 7.5. Symbolically,

M₁ = ({s₀, s₁, s₂,} {a, b}, {0,1}, δ₁, μ₁, s₀)

M₂ = ({r₀, r₁, r₂, r₃,} {a, b}, {0,1}, δ₂, μ₂, r₀)

The product machine is

Q = {(s₀, r₀), (s₀, r₁), (s₀, r₂), (s₀, r₃), (s₁, r₀), (s₁, r₁), (s₁, r₂), (s₁, r₃), (s₂, r₀), (s₂, r₁), (s₂, r₂), (s₂, r₃)}

= {q₀₀, q₀₁, q₀₂, q₀₃, q₁₀, q₁₁, q₁₂, q₁₃, q₂₀, q₂₁, q₂₂, q₂₃}

Σ = {a,b}

Λ = {0,1}

q₀ = {(s₀, r₀)}

The transition and output function for the product machine are computed component-wise as follows. For present state (s_i, r_j), the next state on symbol x is (δ₁(s_i, x), δ₂(r_j, x)). For instance, (s₀, r₂) on input b transits to (s₁, r₁), and the output for the transition is 01. State q₁₃ and q₂₀ are unreachable states. The state diagram of the product machine is shown in Figure 7.6.

Figure 7.5. Component finite-state machines

Figure 7.6. Product finite-state machine

In a product machine, the size of the state space is the product of the component machines’ state spaces. If M = M₁×...×M_n, then

If the component machines have approximately the same state space size, say |Q₁|, then |Q| = |Q₁|ⁿ, which grows rather rapidly. This phenomenon is called state explosion.

State Equivalence and Machine Minimization

In designing a finite-state machine, it is possible that there are equivalent states (in other words, that states are indistinguishable by an external observer who examines only the input strings fed to the machine and the output strings produced by it). These equivalent states can be combined to give a smaller, reachable state space. In this section we will study a method to identify all equivalent states and to produce minimal finite-state machines.

Two states in a finite-state machine are equivalent if for any input string the output strings produced starting from each of the two states are identical. If two states are not equivalent, there must be an input string that drives the machine to produce different output strings starting from either of the two states. For brevity, we say that the input string causes the two states to produce different output strings. Let’s look at an equivalent-state identification algorithm on Mealy machines. With minor modification, the algorithm can be applied to Moore machines.

The algorithm starts out by assuming all states are in one equivalent class, and then successively refines the equivalence class. Let’s use the state machine in Table 7.6 to illustrate the algorithm. The first column is the present state, and the second and third columns are the next states for input x equal to a and b respectively. The outputs are either 0 or 1 and are given after the next states. Initially, all states are assumed to be equivalent. Let’s group them into an equivalent class:

Table 7.6. State Machine for Equivalent-State Identification

PS	NS, x = a	NS, x = b
S1	S5/1	S4/1
S2	S5/0	S4/0
S3	S5/1	S2/0
S4	S5/0	S2/0
S5	S3/1	S5/1

From the definition of state equivalence, two states that produce different outputs on the same input are not equivalent. From Table 7.6, we see that on input x = a, S₁ and S₂ produce different outputs, S₁, giving and S₂ giving 0. They must not be equivalent. Examining all states for x = a, states S₁, S₃, and S₅ could still belong to the same group because they produce the same output. Similarly, S₂ and S₄ belong to the same group. Therefore, we can split the initial single group into two groups such that the states within the same group produce the same outputs. We then have

Now we examine the other input value, x = b. States S₂, S₃, and S₄ produce output 0 whereas S₁ and S₅ produce 1. Thus, S₃ and S₁ are not equivalent. So, we can split the first group again:

If two states S_i and S_j in the same group, on the same input symbol (say, y) transit to two states R_i and R_j that are in two different groups, then S_i and S_j cannot be equivalent. The reasoning is as follows. Because R_i and R_j are not equivalent, there is an input string (say, z) that causes R_i and R_j to produce different output strings. The string yz (symbol y followed by string z) will cause S_i and S_j to produce different output strings.

Examine the state transition table for the first group, (S₁, S₅). On input x = a, S₁ goes to S₅ and S₅ goes to S₃. Because S₅ and S₃ are in different groups, based on our reasoning we can conclude that S₁ and S₅ are not equivalent. So we can split the first group again:

The only group with more than one state is (S₂, S₄). On x = a, S₂ and S₄ both go to S₅. On x = b, S₂ goes to S₄ whereas S₄ goes to S₂. The next states, S₄ and S₂, are in the same group; thus, no splitting is needed. Up to this point, all groups have been examined and we stop. Because S₂ and S₄ are in the same group, they are equivalent. Because there are no input strings that can distinguish between S₂ and S₄, we might as well represent both states with a single state, say S₂. Therefore, we simplify the state transition table by replacing S₄ with S₂. The minimal-state machine is presented in Table 7.7.

Table 7.7. Minimized Finite-State Machine

PS	NS, x = a	NS, x = b
S1	S5/1	S2/1
S2	S5/0	S2/0
S3	S5/1	S2/0
S5	S3/1	S5/1

The state equivalence identification and state minimization algorithm is summarized here:

State Equivalence and Minimization Algorithm

1. For each input symbol, create groups of states such that states within the same group produce the same output.

2. For each group, examine the states on each input symbol. Two states whose next states are in different groups of the partition from the previous step must be split.

3. Repeat step 2 until there is no more group splitting.

We need to understand why states in the same group at the termination of the algorithm are equivalent. Suppose that states S and R are in the same group but are not equivalent. Then there must be an input string that causes S and R to produce different output strings. Let T be the first time the two output strings differ. Let S_T be the present state at time T for the run of the machine starting from S. Similarly, let R_T be the present state at time T for the run starting from R. Because S_T and R_T produce different outputs, the algorithm guarantees that they be in different groups. Step 2 of the algorithm also guarantees that the state pair one cycle before S_T and R_T belongs to different groups. Again, the state pair two cycles before S_T and R_T also belongs to different groups. Going backward, we will eventually arrive at S and R, and will conclude that S and R must belong to different groups, which is a contradiction.

A rigorous proof is based on mathematical induction on the length of the input string. When the length is 1, step 1 of the algorithm guarantees equivalence of states. Assume that the states produced by the algorithm are equivalent for any string of length less than n. For a string of length n, feed the first symbol to the machine. Two states in the same group will transit to the same group, as ensured by step 2 of the algorithm. Now we have an input string of length less than n. The induction hypothesis guarantees the two states be equivalent. I’ll leave the details of a proof based on mathematical induction to you to determine.

Furthermore, the algorithm finds all equivalent states. If two states are equivalent, then they must belong to the same group at the end of the algorithm. To see why this is so, we notice that initially all states are grouped by their outputs. So these two states must be grouped together in step 1. Because they are equivalent, they will not transit to two different groups; hence, step 2 will not split them. Therefore, they must remain in the same group at the termination of the algorithm.

This grouping of equivalent states can be regarded as a state partition. The state partition produced by the algorithm is unique. That is, if there is another partition of the states, then that partition must be identical to the one produced by the algorithm. Suppose this were not true. There must be two states, S and R, that belong to one group in one partition and belong to two different groups in the other partition. Belonging to two different groups means that they are not equivalent. However, on the other hand, they belong to the same group, meaning they are equivalent—a contradiction. Therefore, the state partition given by the algorithm is unique.

So far, the machine minimization algorithm has been applied only to finite-state machines. It can also be applied to finite-state automata. Because automata do not produce output, the meaning of state equivalence must be redefined. We define two states to be equivalent if the following condition is satisfied: whether the automaton accepts or rejects an input string is independent of which of the two states it starts at. In other words, an accepted (rejected) string by the machine starting at one state is also accepted (rejected) by the machine starting at the other state.

With this definition of state equivalence, the first step of the algorithm is to group final states as one group and the remaining states as another, because states in one group are accepted whereas the others are not. Thus, states in these two groups are not equivalent. Then we examine the next state of the states in each group, on each of the input symbols. Two states transiting to two different groups on the same input symbol are not equivalent, and thus the group must be split. This process continues until no group splitting exists. Just like the algorithm for finite-state machines, the reduced automata produced by combining the equivalent states indicated by this algorithm are minimal and unique.

Example 7.16

Consider the finite-state automaton described by the state diagram in Figure 7.7. The first partition of states is to group final states as a group: states a and g, and the remaining states as another group. We have (a, g) (b, c, d, e, f).

Examine the states in each group for each input symbol. On input 0, a and g go to b and e respectively. Both are in the same group, so no splitting is required. In the second group, b goes to c, and c goes to a. Because these next states are in different groups, b and c belong to different groups. A similar analysis produces the following: (b, c, d, e, f) goes to (c, a, c, f, g). Therefore, (b, c, d, e, f) splits to (c, f) (b, d, e). States c and f belong to the same group because their next states on input 0 are a and g, which are in the same group. At this point we have (a, g) (c, f) (b, d, e).

On input 1, a and g go to d and e respectively, which are in the same group. States c and f go to f and c respectively, which are in the same group. States b, d, and e go to a, g, and g respectively, which are in the same group. At this point, there is no splitting. Now on input 0, (a, g) goes to (b, e), (c, f) goes to (a, g), and (b, d, e) goes to (c, c, f). There is no splitting on input 0. Therefore the process terminates. The final partition is (a, g) (c, f) (b, d, e). States a and g are equivalent, as are c and f, and b, d, and e. By combining the equivalent states, we have the reduced automaton shown in Figure 7.7B.

Figure 7.7. Finding equivalent states and minimizing a finite-state automaton. (A) An automaton with equivalent states (B) A reduced automaton

Finite-State Machine Equivalence

During the course of a design project, it is sometimes required to determine whether two state machines are equivalent. Two finite-state machines are equivalent if their input and output behavior is identical. Comparing state machines ensures that a state machine, after undergoing a timing enhancement, is functionally equivalent to the original machine. For smaller, deterministic state machines, the following procedure can be used. First, minimize both machines using the previous algorithm. If these two reduced machines are indeed equivalent, there is a one-to-one correspondence between the states in the machines. That is, for every state in the first machine, there is a corresponding state in the second machine such that they play the same role in the machines except for possibly their names (in other words, they are isomorphic). To determine this one-to-one correspondence, assume their initial states correspond to each other. Then for each input symbol, make the next states from the respective initial state correspond to each other if they produce the same output.

When all next states of the initial state have been mapped, continue the same process on the next states of the respective mapped states. If, at the end, all states have been mapped, the two machines are equivalent; otherwise, they are not.

The state mapping step is difficult if the machines are nondeterministic, because there could be more than one initial state or next state, so that the correspondence between states is difficult to determine.

Example 7.17

Consider the two minimal state machines in Figure 7.8. The first machine, in Figure 7.8A, has initial state a, and the second machine has initial state z. Map state a to z. On input 0, the next state of the first machine is c with output 1, and that of the second machine is s with output 1. Because the outputs are identical, map state c to s. On input 1, the next states of the first and the second machine are b and y respectively, with identical output. So map state b to state y. Choose mapped states c and s for the next iteration of the mapping process. On input 0, the next states are b and y with identical output, which is consistent with the existing mapping. On input 1, the next states are e and x respectively. Because the outputs are equal, map state e to state x. Repeat until all states and transitions have been visited. At the end, we find that all states have been mapped, and we therefore conclude that the two machines are equivalent. The final state mapping is

Note the increased difficulty if there is more than one initial state or next state.

Figure 7.8. Determine state machine equivalence between the machines in A and B.

Graph Algorithms

Because finite-state automata or machines can be represented by state diagrams, algorithms on automata and state machines often take the form of graph algorithms. For example, to inquire whether a state can be reached from the initial state, it is a question of whether the state vertex in the state diagram can be reached from the initial state vertex. In this section we will study several graph algorithms commonly encountered during formal verification procedures.

A directed graph or digraph consists of a set of vertices V and a set of directed edges E—in other words, G(V,E). An edge from vertex n to vertex m is represented by (n,m). In the context of a state diagram, the vertices represent states and the edges represent transitions. A vertex has a fanout if there is an edge from the vertex to another vertex, which is called the fanout vertex. A path from vertex n to vertex m is a sequence of alternating vertices and edges, with the first vertex being n and the last vertex m such that the ith edge goes from the ith node to the i + 1st node. Vertex n can be reached from vertex m if there is a path from m to n. Given a node n, the set of all nodes that can be reached from n is called the transitive closure of n.

Example 7.18

In this example we look at representing a graph as a Boolean relation. Representing a graph in a Boolean domain translates graphical manipulations into Boolean operations. Consider the graph in Figure 7.9. Two things need to be represented: vertices and edges. We first encode the vertices. There are four vertices; thus, 2 bits are required to encode the vertices. Vertices a, b, c, and d are encoded as 00, 01, 10, and 11.

An edge is identified by its head and its tail, which are vertices; therefore, 4 bits are required to encode an edge. Let us choose variables r, s, v, and w. For example, edge (a,c) is encoded as 0010. The first 2 bits are the code of the edge’s head, vertex a, and the last 2 bits are the code of the tail, vertex c.

We can define a relation on vertex pairs (e₁, e₂). The relation is true, if edge (e₁, e₂) exists in the graph. For instance, (b, d) is true but (c, a) is false. This relation is represented by a characteristic function. Therefore, the characteristic function λ(r, s, v, w) is 1 for the vertex pairs: (a, b), (a, c), (b, b), (b, d), (b, c), (c, d), (c, c), and (d, a). Replacing the edges by their code, we have:

To check, for edge (b, c), the code for the edge is 0110 (in other words, r = 0, s = 1, v = 1, and w = 0). We can see that λ(0, 1, 1, 0) = 1 because the fifth term becomes 1, as expected. Consider edge (c, a), which is not in the graph. The code is 1000. We calculate λ(1, 0, 0, 0) = 0, as expected.

Figure 7.9. A graph for Boolean representation

Depth-First Search

A basic procedure on a graph is to visit, or traverse, the vertices in a systematic way so that all vertices are visited only once. Two popular traversal algorithms are DFS and breadth-first search (BFS). Let us study DFS first.

DFS starts from an arbitrary vertex, called the root of DFS, selects a fanout vertex, and visits all vertices that can be reached from the fanout vertex before repeating the traversal on the other fanout vertices. A DFS algorithm is shown here. The number N records when a vertex is visited. When a vertex is visited, N is stored in the entry time attribute of the vertex. When a vertex is done visiting, N is stored in the exit time attribute of the vertex. N is included for the sole purpose of showing the order in which the vertices are visited, and hence is not necessarily a part of the algorithm. In a DFS operation, unlike vertices, which are all traversed, not all edges have to be traversed. We will see that all traversed edges form a set of trees, or a forest. A tree is a graph with no loops. The set of traversed edges is called the DFS tree.

DFS Algorithm

Input: G(V, E)
Output: a systematic traversal of vertices.
Initialization: N = 1 // used to record entry and exit time of a node


DFS (G) {
   while (vertex v in V is not marked visited) VISIT(v);
}


VISIT(v) {
   mark v visited;
   v.entry = N;
   N = N + 1; // record node entry time
   for_each (u = fanout of v)
      if ( u is not marked visited) VISIT(u);
   v.exit = N;
   N = N + 1;
}

Example 7.19

Let us perform a DFS on the graph in Figure 7.10. We start the DFS from vertex G, which we mark visited and tag with N = 1. In Figure 7.10, the first number is entry time and the second number is exit time. Following the arrow, we arrive at B, which has two fanouts. We mark B visited and tag B with N = 2, and follow a fanout to D, which is then marked visited and is tagged with N = 3. Because D has no fanout, D is done visiting and we return from D. On exiting from D, we tag D with exit time 4. Following the other fanout of B, we arrive at C, which is marked and tagged with N = 5. Because C has no fanout, we return from C and tag it with exit time N = 6. On returning to B, we find that all of its fanouts have been visited, so we exit from B and tag its exit time with 7. Finally, we return to node G and tag its exit time with 8. This completes the first traversal. However, there are still unvisited vertices, such as A. So, we start from another vertex, say, E. We tag E with entry time 9 and follow its sole fanout to A. On arriving at A, we tag its entry time with 10. Because both fanouts of A have already been marked visited, we return from A and tag its exit time with N = 11. On returning to E, we tag its exit time with 12. The remaining unvisited nodes, F and H, having no unvisited fanouts, are marked and tagged. The edges that were traversed in the DFS are in bold and form the DFS trees.

Figure 7.10. A graph with entry and exit times from a DFS

In a DFS tree, a vertex is called a parent of another vertex if there is an edge in the DFS tree that starts from the former and goes to the latter. The second vertex is called the child vertex. A vertex A is called a descendant of vertex B if A can be reached from B, following directed edges of the DFS tree. Vertex B is called an ancestor of A. Once a DFS tree or forest is determined, edges in the graph can be classified into the following four types: tree edges, back edges, forward edges, and cross edges. Tree edges are just edges of the DFS tree. Back edges connect descendants to ancestors. Forward edges connect ancestors to descendants. The remaining edges are cross edges.

One application of DFS is to find cycles or loops in a directed graph. Theorem 7.6 provides the necessary and sufficient condition.

Theorem 7.6

Main property of DFS trees and cycle detection

1. If edge (n,m) is such that the entry time of n is less than that of m, then m is a descendant of n.

2. Graph G(V,E) has a directed cycle, or loop, if and only if G contains a back edge with respect to the DFS tree of G.

Example 7.20

Let’s apply DFS to the graph in Figure 7.11 to illustrate the previous definitions and theorem. The numbers shown are entry times. The bold edges form the DFS tree. Edges (b, f), (f, c), (c, d), (c, e), (e, a), and (a, g) are tree edges. According to part 1 of Theorem 7.6, g is a descendant of b. So, edge (b, g) is a forward edge. Vertex a is a descendant of vertices c and b because there is a path from c or b to a along the DFS tree. Therefore, edges (a, b) and (a, c) are back edges. Finally, vertex g and vertex d are not related (neither is a descendant of the other); therefore, edge (g, d) is a cross edge. So is edge (e, d). According to part 2 of Theorem 7.6, there are directed cycles or loops because of the back edges (a, b) and (a, c). Indeed, the loops are (a,b,f,c,e,a) and (a,c,e,a).

Figure 7.11. Detect loops using DFS

Directed cycles are special instances of SCCs. An SCC of a directed graph is a maximal sub-graph such that every vertex can be reached from any other of its vertices. SCCs are an expanded notion of loop. A DAC is a tree or forest, and hence is free of SCCs. It is known that any directed graph can be decomposed into a DAC and SCCs. In other words, this decomposition breaks any directed graph into looping components and straight components. Once a graph is decomposed in such a way and the SCCs are encapsulated, the resulting graph is a DAC and is loop free. SCCs can be determined by applying DFS, as follows:

Algorithm for Finding SCCs

Input: graph G

output: a collection of SCCs in G

1. Perform DFS on G and record the exit time for the nodes.

2. Reverse the edges of G and apply DFS to this graph, selecting the nodes in order of decreasing exit number in the while loop step.

3. The vertices of a DFS tree from step 2 are SCCs.

In step 2 of the algorithm, reversing an edge means making the head of the edge its tail, and vice versa. When applying DFS to this graph, in the while loop of the DFS algorithm, select the unvisited nodes in the order of decreasing exit numbers that were derived in step 1.

Example 7.21

Identify strongly connected components.

Apply the SCC-finding algorithm to the graph in Figure 7.12. In Figure 7.12A, the numbers underlined are the exit times of the nodes from the DFS in step 1. Figure 7.12B is obtained from A with edges reversed. To apply DFS to this derived graph, the first unvisited vertex is vertex d because it has the largest exit number. This search ends after it has visited vertices a, b, d, and h. The next unvisited vertex is f, because it has the largest exit number in the remaining unvisited vertices. This search concludes the DFS after it has visited g and e. The bold edges in Figure 7.12B are the DFS trees from this DFS. The vertices of a DFS tree form an SCC. Therefore, {a,b,d,h} is an SCC, as is {e,f,g}. Making an SCC into a composite vertex, the resulting graph is a DAC, which is shown in Figure 7.12C.

Figure 7.12. Finding SCCs. (A) Result of a DFS. The underlined numbers are exit times. (B) DFS on a graph derived by reversing the edges. (C) Resulting DAC by treating SCCs as composite nodes.

Breadth-First Search

A BFS visits vertices level by level. First it selects a vertex, the root of the DFS, as the starting point of the search and visits all its fanout vertices before visiting other vertices. Then the fanout vertices of the recently visited fanout vertices are visited, and so on, until all vertices are visited. If we define the level number of a vertex with respect to the root to be the minimum number of edges from the root to the vertex, then vertices in a BFS are visited according to their level numbers from the root in increasing order, because the level numbers of fanout vertices of a vertex are one more than that of the vertex itself. Similar to DFS, all traversed edges form a BFS tree or forest. A BFS algorithm is as follows:

Input: G(V, E)
Output: a systematic traversal of vertices.
Initialization: N=1 // used to record entry time of a node


BFS (G) {
   while (vertex v in V is not marked visited) VISIT(v);
}


VISIT(v) {
   mark v visited;
   place v in a queue Q.
   while (Q is not empty) {
      remove head of Q and call it u.
      u.entry = N; N = N + 1; // record node entry time
      for_each edge (u, r) where r is not yet marked {
         mark r;
         add (u, r) to the BFS tree;
         place r in Q;
      } // end of for_each
   } // end of while
}

Theorem 7.7 shows two properties about BFS. Because BFS visits vertices in increasing order of level numbers, the first property, a direct result of the search procedure, says that for all edges (n, y) leading to y, the one closest to the root is selected first and thus belongs to a BFS tree. The second property is a consequence of successive manifestations of the first property. A path is made of a sequence of connecting edges. According to property 1, the edges on a BFS tree are the ones closest to the root; therefore, the shortest path from a root to a vertex is the one made of only tree edges in a BFS tree.

Theorem 7.7

Properties of BFS

1. Suppose edge (x,y) is a tree edge of a BFS tree and (z,y) is any edge leading to y. Then the entry number of x is less than that of z.

2. The shortest path from a root of a BFS to a vertex x is the path from the root to x, which lies in the BFS tree.

Example 7.22

Let’s apply BFS to the graph in Figure 7.13, for which we performed a DFS. You may want to compare the two search methods. Let’s select vertex b as the starting point. In routine VISIT, vertex b is marked and placed into the queue. It is then removed from the queue and tagged with an entry time of 1. Then its fanout vertices f and g are enumerated, marked, and placed in the queue. Now the queue contains f and g. Vertex f is removed. Vertex f is tagged with entry time 2 and its fanout is c, which is then marked and placed in the queue. Now the queue has g and c. Next, g is removed from the queue and is tagged with an entry time of 3. Its fanout is d, which is then marked and placed in the queue. The queue has c and d. Vertex c is taken off the queue and is tagged with an entry time of 4. Its fanouts are e and d, but d has already been marked. Thus, only e is marked and is placed in the queue. The queue has d and e. Vertex d is removed from the queue and is assigned an entry time of 5. It has no fanout. The queue has e. Next, vertex e is taken off the queue and is given an entry time of 6. Its sole fanout is vertex a, which is then marked and placed in the queue. The queue has a. Vertex a is removed from the queue and is assigned an entry time of 7. Its three fanouts—b,g, and c—are all marked, and the BFS terminates. The graph with entry times and the BFS tree in bold are shown in Figure 7.13A. In Figure 7.13B, the vertices are rearranged according to the BFS tree. In this rearrangement, it is easy to see that BFS levels the vertices, and the shortest distance from the root (vertex b) to any vertex is the path that lies in the BFS tree, as stated in part 2 of Theorem 7.7. Furthermore, the nontree edges also obey the rule stated in part 1 of Theorem 7.7. For example, edges (c,d) and (e,d) are not tree edges, whereas (g,d) is. Hence, the entry times of c and e are greater than that of g.

Figure 7.13. Graph for BFS. (A) Result of a BFS run shows a BFS tree with entry numbers. (B) Rearrange vertices according to their levels.

In this chapter we reviewed some of the basic mathematics encountered in formal verification. We started with set operations and then defined relations among sets. An especially interesting relation is the equivalence relation, based on which sets can be partitioned. Next we studied partially ordered sets along with meet and join, and introduced lattices.

We then moved to Boolean functions and their representations. We examined CNF, DNF, and multilevel representation. Symmetric Boolean functions have a concise way of representation, and we showed how operations on symmetric functions could be performed easily. For incompletely specified functions, we introduced representation using on set, off set, and don’t-care set. To represent Boolean relations, we used characteristic functions.

We went over several Boolean operators—namely, cofactor, which gives rise to Shannon expansion, generalized cofactor, Boolean difference, and existential and universal operators. In passing, we mentioned the generalized Reed–Muller form.

From the discussion of combinational domain we continued to sequential domain. First we defined finite-state automata, finite-state machines, completely specified, incompletely specified, deterministic, and nondeterministic. A language of an automaton is defined in terms of its acceptance condition. There are various forms of acceptance conditions, some for finite strings and some for infinite strings. Finally, we considered product machines and the state explosion phenomenon.

States may be equivalent in the sense that an external observer would not be able to distinguish the states. We provided an algorithm to determine all equivalent states and to reduce automata and machines to their minimal forms. We also looked at a procedure to determine the isomorphism of deterministic finite-state machines.

Lastly we studied some graph algorithms. We defined common graph terms, then looked at DFS and BFS in detail. We defined a DFS and BFS tree, applied DFS to finding directed cycles and SCCs, and showed how BFS levels nodes and produces the shortest path.