THE UNIVERSITY OF MICHIGAN COLLEGE OF LITERATURE, SCIENCE, AND THE ARTS Logic of Computers Group Technical Report LECTURES ON SITITCHING AND AUTOMATA THEORY ~ Calvin C. ElgQt. Research As s6otate, Wiliopw Run Laboratories. I..ro je.t 2755 under contract with: ORDNANCE CORPS, DETROIT ORDNANCE DISTRICT CONTRACT NO. DA-20-018-ORD-16971, PROJECT NO. ORD R AND D (TB 2-001) DETROIT, MICHIGAN administered by: THE UNIVERSITY OF MICHIGAN RESEARCH INSTITUTE ANN ARBOR January 1959

t- X - 1 I i - J-i -.. ifoI'~l~~~~~ I- 111'.

F OREWORD At the time these lectures were being prepared and presented, the author was engaged in research supported by the Office of Naval Research Contract No. Nonr 1224(21), and by the Office of Ordnance Research (Contract No. DA-20-018-0RD-16971). The lectures employ many concepts and theorems developed in the course of this research. 111

TABLE OF CONTENTS Page 1. Introduction 1 2. Operations on Sets 2 3. Operations and Associated Relations 3 4. Lattices 6 5. Propositional Calculus and an Application 14 6, Multi-Terminal Networks 28 7. Automata and Sequential Circuits 35 8. Realization of Events 61 9. Bibliography 75 iv

1. INTRODUCTION These lectures include a study of two-terminal series-parallel relay contact networks, multi-terminal relay contact networks, and sequential networks. General, systematic techniques for the study of series-parallel networks have employed Boolean algebra or propositional calculus53 A basic paper on multiterminal relay contact nets makes use of matrices whose entries are elements of a Boolean algebra.39 More recent work49'3~'34y17 makes use of the algebraic concepts: lattice, semi-group, group, The concept of ring when suitable specialized is intimately connected with Boolean algebras,,6 This indicates the extent to which algebra is invading the mathematical theory of switching. Much recent workl8 26)31v32 has employed more advanced aspects of logic than the propositional calculus. Indeed, the use of logic and its techniques has already produced significant results and promises still more fruitful ones. We begin with some preliminary, simple, algebraic and logical concepts which will lead to a discussion of finite Boolean algebras, propositional calculus, and their application to switching theory. The work of Lunts39 (which lists results only) is discussed in Section 6. The arguments make use of an important correlation between matrices of zeros and ones and finite binary relations. This correlation is useful in other work on switching.19, 2335 Automata and sequential circuits are introduced in Section 7 and the connection with Burks-Wright logical nets25 is pointed out. Moore s theory and related work of Mealy and Ginsburg33,34,45 is expounded. The equivalence, in a certain reasonable sense, of finite automaton as defined here and as defined in Moore is indicated. Finite semi-groups are associated with automata in section 7.9. In the case of a permutation automaton33 (backwards deterministic)23 the associated semi-group is a group. An application is made of this association. Kleene's theory37 of regularity as modified in item 28 of the bibliography is explained. An alternative notion of regularity is defined and its relation to the primary concept is established, The discussion terminates with an example illustrating several of the main results of the sections on automata theory. These notes were the basis for the bulk of a course given by the author at T'.e University of Michigan (1957, 1958) in the Department of Electrical En7gi.eering.

2. OPERATIONS ON SETS Let A be a set (class, collection, aggregate) of objects called elements (or points) of the set. "x is an element in A" is written "x c A." For example, ifJ is the set of positive integers, 1 c J, 2 e 9, etc. If A and B are sets, then A = B (i.e., "A" and "B" denote the same set) if and only if (x C A <-> x c B). If A and B are sets, the union of A and B, AUB, is defined as the set of all elements x such that x c A or x C B (i.e., in one or both); the intersection of A and B, An B, is the set of all x such that x c A and x c B. ACB meails "if x c A, then x E B"; so does BDA. ACB (BDA) means ACB but A f B. Exercises. Prove that for all sets A,B,C 2.1. AUA = A 2.2. (AU B) UC = A U (BU C), 2.3, AnA = A, 2.4. (AnB)n C = An (B nc), 2.5 A n(AUB) = A [Proofo x c (A n(A UB)) if and only if x c A and if x e A UB if and only if x C A and (x c A or x c B) if and only if x C A or (x C A and x c B) if and only if x c A.] 2,6: A U(A nB) = A, 2.7 ifACB, then AUB = B. 2.8., if A UB = B, then AB., 2.9. if ACB, then AnB = A, 2,10. if A NB = A, then ACB, 2.11. AUB = BUA, 2.12. AnfB = BOA, 2.13. ANf(BUC) = (AnB) U(AnC), 2.14. AU(BfnC) = (AUB) n(AUC). 2.15. Example. If A = (1,2}, i.e., A consists of two (distinct) elements 1,2, and B = (2,3}f then AUB = (1,2,3) and A nB = ([2] 2.16. If A and B are sets with no elements in common, then An B is undefined. In order to avoid this situation, it is customary to introduce the empty set, denoted by "," which is defined to be a set with no elements, i.e., x i ~ for all x. It follows A nB = X if A and B have no elements in common. 0 is the only set with no elements. Objects which are not sets also have no elements. 2.17. For all sets A, (1) An O = 0, (2) AU ( = A.

3. OPERATIONS AND ASSOCIATED RELATIONS Let S be an arbitrary set and * a binary operation defined over the set, 3. 1. Let R. be a binary relation on S defined as follows: xR*y if and only if x = x * y. ["xR*y" is read "x is in the relation R* to y."] Similarly define xR*y if and only if y = x * y. 3.2. A relation R is reflexive over S if and only if xRx for every x C S; anti-symmetric if and only if xRy and yRx implies x = y; and transitive if and only if xRy and yRz implies xRz. 3.3. Theorem, Let * be a binary operation on S. Then (a) if x * x = x for all x e S i.e., * is idempotent, then R* is reflexive over S; (b) if x * y = y * x for all x,y C S, i.e., * is commutative, then R* is anti-symmetric; (c) if (x * y) * z = x * (y * z) for all x,y,z C S, i.e., * is associative, then Rp is transitive. Proof. (a) xR*x if and only if x = x * xo (b) If xR*y, then x = x * y; if yR*x, then y = y * xo Since x * y = y * x. it follows xR*y and yR*x implys x = y. (c) Suppose xR*y and yR*z. To prove: xR.*zo Then (1) x = (x*y), (2) y = (y * z). From (1) it follows (3) x * z = (x * y) * z while from (2) follows (4) x * y = x * (y * z). Since the operation is associative, (3) and (4) yield x * z = x * y, but x * y = x from (1) so that x * z = x, i.e,, xR*z. 3.4, Statement 3.3 with R in place of R. also holds, 3 55 Example. (1) Let min be a binary operation on numbers (reals or integers or positive integers) defined as follows: min(a,b) = a if and only if a < b; min(a,b) = b if and only if b < a. Then min is idempotent, anti-symmetric, and transitive, aRminb if and only if a = min (a,b) if and only if < b; aRminb if and only if b = min(a,b) if and only if b < a. Thus Rmin is the relation < while Rmin is the relation > (2) Let S be the set of rational numbers (fractions; let * be ordinary multiplication. Then: xRBy if and only if x = x * y if and only if

x = 0 or y = Io Therefore, OR*x and xR*l for all rational numbers x. Notice that multiplication of rational numbers is commutative and associative but not idempotent. Theorem 3.3 tells us that in this case R* is anti-symmetric and transitive. Note, too, xR 0 and 1R*x for all rational numbers x. (3) Let S be the set of non-zero rational numbers and let x * y. Then xR*y if and only if x =x + y if and only if xy = x if and only if y = while xR*y if and only if y = x - y if and only if y2 = x so that 9R 3, 16R 4, etc. 3.6. Exercises~ (a) What is Ru, RU R, Rn in terms of previously defined relations? [Note 2.1, 2.2, 2.11; 253, 2.4, 2.12.1 (b) Show the greatest common divisor (gcd) and the least common multiple (lcm) of positive integers are idempotent, commutative, associative operations. What is RX if x * y means gcd of x,y; if x * y means lcm of x,y? (c) If * is commutative, then xR*y if and only yR*x, and conversely. (d) Show subtraction of integers is not an associative nor a commutative operation. (e) If + is an associative binary operation on a set S, then: if xR+m and yR+m, then (x+y)R+m(cf.3.1). If, furthermore, + is commutative and idempotent, then xR+x+y and yR+x+y. Under these conditions (S,+) is a semi-lattice and R+ a semi-lattice ordering relation (cf. 353). 3.7. A partial ordering relation R over a set S is a reflexive, anti-symmetric and transitive relation over S. Examples. (a) C, D. (b) Define R over ordered pairs [ioeo, (x,y) is to be distinguished from (y,x)] of numbers (real, integers, etc.) (a,b) as follows: (a,b) R (cd) if and only if a < c and b < d. Thus (2,3) R (2,4) but not (2,3) R (3,2) nor (3,2) R (2,3)} (c) d e a b

xRy if and only if (1) y is above x or (2) y = x. (d) R*, R where * is idempotent, commutative, and associative. 3.8. Exercise. (a) If R is a partial ordering relation over S and R is defined as follows: U u xRy if and only if yRx, then R is a partial ordering relation. (b) xRy if and only if xRy.

9,10 4. LATTICES 4.1. A lattice L = (Av, A) consists of a set A and two binary operations v A such that (a) each operation is idempotent, commutative, and associative and (b) aA(avb) = a, av (a Ab) = a, for all a,b in A. The first of the two operations is the join operation, while the second is the meet operation. 4.2. Exercise. If (A,/,A) is a lattice, then so is (A,A,V). 4.3. Examples of lattices. (a) If A is the collection of all subsets of a set S(T is a subset of S ff T C S), then (A, U, n) is a lattice. More generally, if A is a collection of sets such that A is "closed"unier U(i.e., S1 c A and S2 c A imply S1U S2 e A) and n, then (A,U, n) is a lattice. (b) Let A be the set of ordered pairs of integers. Define: (ab)V(c,d) (max)a,c), max(b,d)), (a,b)A (c,d) = (min(a,c), min(b,d)). Then (A, V, A) is a lattice. 4.4. Exercises. (1) Give 4.)(b) a geometric interpretation by introducing rectangular coordinates in a plane and correlating with an ordered pair of integers, the point which has this ordered pair as it-,coordinates. (2) If A is the set of positive integers, and if aVb means the least common multiple of a,b, and if aAb means the greatest common divisor of a,b, then (AV,a) is a lattice. 145. A relation < is a lattice ordering relation over a set S ff*< is a partial ordering relation and every pair of elements in S has a (unique) least upper bound and greatestlower bound, with respect to this ordering. (b is an upper bound of x,y means x < b and y < b. m is a least upper bound of x,y means that m is an upper bound and further if b is any upper bound of x,y then m < b.) 4.6. Theorem. (a) If (A,V,A) is a lattice, then RA is a lattice ordering relation withVthe least upper bound andA the greatest lower bound with respect to this ordering. *Note: ff means "if and only if."

(b) If < is any lattice ordering relation over a set A, let j(< ) be the binary operation on A of least upper bound and let m(<) be the binary operation on A of greatest lower bound both with respect to <, then (Aj(<), m(<)) is a lattice. Proof. (a) Since/Ais idempotent, commutative, and associative (4.1), it follows (3.3) that RA is a partial ordering relation. We note xRAy if and only if x = x/\y, while xRVy if and only if y = xVy (3,1)o If xR\y, then xVy = (xAy)V y = y so that xRVy. If xRVy, then xAy = x A (xVy) = x so that xRAy (4,1(b)), which establishes RV = RA. (To say R1 = R2, where RB and R2 are binary relations, means that xRly if and only if xR2y.) We now write "<" instead of "R." Let x,y C A. We note x < xVy if and only if xVy = xV(xVy). But xV(xvy) = (xV(xVy). But xV(xVy) = (xVx)Vy = xVy. Similarly, since xvy = Yv(xvy) = yv(yVx) = (yVx) = Yvy)Vx = yVx, it follows y < xVy. Suppose now x,y < m. It is required to show that xvy < m, i.e., m = (xvy)vm. Note that (xVy)Vm = xV(yvm) = xVm (since y < m) and xVm = m (since x < m) so that xVy < m. 4,7. Exercise. (a) Prove 4.6(b) (b) Define aRb, where a,b are positive integers as follows: aRb if and only if there exists an (integer) x such that a. x = b, where "o" indicates ordinary multiplication, i.e., aRb if and only if a divides b. Verify that R is a lattice ordering relation and determine the arithmetic meaning of join and meet in the associated lattice, [Cf, 4.1, 4.51 4.6 ] (c) Every finite lattice has a (unique) maximum and a unique minimum element, with respect to the lattice ordering. (d) If < is a partial ordering relation over a set S such that for any a,b e S either a < b or b < a, then < is a lattice ordering, (A relation satisfying these properties is called a complete, simple, or linear ordering relation ) 4.8, The meaning of series-parallel network is now indicated in a semiformal way. If a - - b c d a*_ __ anrld - are two-terminal networks, their connection in series is

a b d their connection in parallel is a I I- b a b A network. a, consisting of two nodes (vertices, points) and one branch (edge) is called a unit network, The two terminals of each of the networks above are the displayed ones, the first one being on the left. The class of series-parallel networks is the smallest class of two-terminal networks containing the unit networks and such that the series and parallel connections of any two networks in the class is again in the class. Equivalently, a two-terminal network is series-parallel if and only if it is a unit network or is obtainable from unit networks by a finite number of series and parallel connections. 4.9. Exercise. Verify, using the definition, that the following networks, where the two terminals are indicated by "'*," are series-parallel. (a) (b) 4.10. By a chain in a two-terminal network we shall mean a sequence of distinct nodes beginning with the first terminal and ending with the second having the further property that consecutive nodes have an edge in common. A relation < may now be defined on the nodes of the network as follows: x < y if and only if x is a node which precedes y in some chain containing both. It turns out that: if the network is series-parallel, then < (where < is the relation just defined) is a lattice ordering of the nodes of the network. In accordance with 4.6(b), a lattice may be associated with a series-parallel network. For example, if the network is 8

then b < c, b < e, b a, c a 4.11. Two elements x,y in a lattice with 0,1 (O is the minimum and 1 is the maximum element with respect to <) are called complementary if and only if xVy = 1 and xAy = 0. In the example above (4.10) the following pairs are complementary-: a,c], (a,b], [a,d], (a,e), (0,1.o On the other hand, if the network above is series-connected with a unit network, then none of the elements in the associated lattice, except 0,1 has complements. 4,12. Exercises. Construct a table forVand one for A(analogous to addition and multiplication tables) for the lattice associated with the networks below. List the complementary pairs of elements, b a c (b) 0 1 b d 4.13. A two-terminal network is admissible if and only if each node occurs in some chain (cf. 4.10). The following can be proved:30 an admissible network is series-parallel if and only if < (the relation defined in 4.10) is asymmetric, that is, for no nodes x,y does x < y and y < x hold. It seems reasonable to call an admissible two-terminal network a bridge network if and only if < is not asymmetric. It follows from the theorem and definitions that every two-terminal network falls into one and only one of the following categories: 1. series-parallel, 2. bridge, 3 nonadmissible. Exercise. Give two examples of each of these categories of networks. 4.14. A lattice (A.,A, V) is called distributive if and only if for all x,y,z C A the following hold: xA(yVz) = xAy.)V(xAz), and xV(yAz) = (xVy) A(xV z). 4.15o In a distributive lattice every element has at most one (possibly no) complement. This assertion is an immediate consequence of the following theorem.

4.16. Theorem. In a distributive lattice, if aV x = aVy, and aAx = a Ay, then x = y. Proof. Note that: x = xA(aVx) = xA(aVy) = (xAa)V(xAy) = ((xAa)Vx)A((xAa)vy) = xA((yAa)vy) = xAy, so that x = xAy. If x and y are interchanged throughout the above argument, it remains valid so that y = yAx. This together with x = xAy yields x = y. 4.17. In the diagram of 4.10, b,c,d,e are each complements of a. It follows from 4.15 that the lattice associated with diagram 4.10 is not distributive. 4.18. A distributive lattice with 0,1 in which each element has a complement (by 4.15 unique) is a Boolean algebra. Examples. (1) The set of all subsets of a set (finite or infinite) under union and intersection. Given the set (a,b,c) with three elements, the set of all subsets is (, Ca)},(b), c),a,b}, (a,c), (h,c),(a,b,c}}. Notice that the given set has three elements while the set of all subsets has eight elements. In general, if a set has n elements, the set of all subsets has 2n elements, This may be proved by putting subsets of an n-element set into one-to-one correspondence with all the sequences of zeros and ones of length n. In case n = 3 and the given set is (a,b,c), a correspondence is: 000 X 100 (a) 010 (b) 001 (C) 110 [a,b} 101 (a,c) 011 (b,c) 111 (a,b,c). Another count of the number of subsets of a given set is obtainable as follows. According to the binomial theorem (a + b)n = an-r br r=0 where nr) is the number of n things taken r at a time, i.e., (nr is the number of r-element subsets of an n-element set. Substituting in the ormula a = 1, b = 1 yields ~2n rC0( 10

(2) Let n be a positive integer which is not divisible by the square of any number except 1,o Let A be the set of all positive integral divisors of n, and let xVy be the least common multiple of x,y and let xAy be the greatest common divisor of xy. Then (A, VA) is a Boolean algebra. We indicate the proof in the case that n = 30. In this case, A = [1,2,315,6,10,15,305} Let f be a function defined as follows: f(() 1= ff({2,3) = 6 f({2}) = 2 f(C2,15) = 10 f((33) = 3 f({,35}) = 15 f(C5)) = 5 f((2,3,95) = 30. Then (a) f(xU)y) = f(x)vf(y), (b) f(x ly) = f(x)Af(y), and (c) for every v c A, there is a subset u of (x,y,z) such that v = f(u). Because of (a), (b), (c) and the fact that all the subsets of a set underU, n form a Boolean algebra, it follows that (A,V, A) is a Boolean algebra, 4.19. If f is a function defined on a set A with values in a set A and if a = (A,V, A), a? = (A, VT, A 8) whereyV,A,VV A' are binary operations such that (1) f(aVb) = f(a)V' f(b), (2) f(aAb) = f(a) AI f(b), then f is a homomorphism of al,'into aI'. If, furthermore, (3) for every x' e AI, there is an x c A such that f(x) = x' then f is a homomorphism of a onto aQ, If, in addition, (4) x t y implies f(x) f f(y), then f is an isomorphism of a onto a'. The function f of 4.18 (2) is an isomorphism. 4.20, Exercises. (1) If f is a homomorphism from a lattice a, = (A,V, ^) onto a = (AX, Vt,A t) (whereVt, A' are binary operations), then (A'V, A') is a lattice. If 6L is a Boolean algebra, then Q,' is a Boolean al11

gebra, and if a c A and b is the (unique) complement of a, then f(b) is the complement of f(a). (2) Define operations V, A on the ordered triples of 4.18 (1) in such a way that the correspondence indicated between these triples and the subsets of [a,bc} is an isomorphism, (3) Let S be any set (finite or infinite). Let A be the class of all subsets x such that either x is a finite subset of S or x = S-y and y is a finite subset of S; here S-y is the set of all elements in S which are not in y. Show that (A, U, n) is a Boolean algebra. 4.21. We now establish some identities for Boolean algebras. The (unique) complement of an element x in a Boolean algebra will be denoted by "x." (1) xVy = xAy. Proof: Using the left distributive law for VoverA\: (xVy) V(x (A) = [(xVy)V1] A[(xVy)V*] = lAl = 1. Similarly using the right distributive law for A over V':'(xVy) V(A:) = [xA(2A:y)]V[yA(EA7~)] = OVO = 0. (2) XY = A- Proof: InterchangeV, Aand 0,1 in the argument for (1). (3) = x. Proof: x is, by definition, the unique complement of x. But x and x are complementary, i.e., x is the unique complement of x. Therefore x = X. (4) If x < y then y < S. Proof: We note that x < y if and only if xVy = y if and only if xAy = x and that y < x if and only if yUxV = ~ if and only if yAx = y. Since by hypothesis x < y, it follows that y = xVy and, by (1), 7 = xAy, so that y < xo (5) If K < x then x < yo Proof: By (4), x < y and, by (3), x <y. 4.22. Exercises. (1) Let A be the set of positive integers augmented by a new element co (infinity). If x,y c A, define xvy and xAy as in 4.4 (2) if x,y are both integers; define xVoo = oo, xAO = x for all x c A. (a) Determine whether (A,V, A) is a lattice. (b) Which elements, if any, have complements? (c) Is (A,VA) a Boolean algebra? 12

(2) Show, by mathematical induction, that xl.'x2V.. VXn = xlAx2..^ Al,, for any n > 1. (3) In a Boolean algebra (A,V, A) define x + y = (xA )V(xAy). Show: (a) (x + y) + z = x + (y + z); (b) x + x = O; (c) xA(y + z) = xAy) + (xAz); (d) 1 + x =; (e) xvy = x + y + (xAy); (f) let A be a class of subsets of S closed under union and intersection, and interpretV,Aas union, intersection, respectively; interpret x and x + y where x,y c A. (4) Let A be the set [0,1l; OV1 = 1VO = lVl = 1, OVO = 0; Al = lAO = OAo = 0, 11 = 1. Show (A, VA) is a Boolean algebra. (5) Let B be the set of all functions f defined on n-tuples of O's and l's with values which are 0 or 1. Define f Vg = h if and only if f(xl,x2.*.. Xn)Vg(xlx2,..., xn) = h(xl, x2,.., xn) where each xi varies independently over 0,1 and the "V" operation on O,1 is defined as in (4). Define fAg analogously. Show (B, V,A) is a Boolean algebra. How many elements does B have? 13

5o PROPOSITIONAL CALCULUS AND AN APPLICATIONu 5 955 501 A formula is a finite (nonzero) concatenation of symbols of the following four types propositional variables: PI, P2, oeo, Pn [n > 1] propositional constants: f, t propositional connectives: v, A, punctuation symbols: (, ) For example, P1P2 v (., ~P1P2 are formulas. Such formulas will not be interesting to us nor will they be given interpretationso The formulas with which we shall be concerned and to which interpretations will be given are the well-formed formulas We define inductively on the length (number of occurrences of symbols) of a formula, a well-formed formula. A formula F is a well-formed formula if and only if (a) F is a propositional variable or constant; (b) F is (F1 V F2) or (F1 A F2) or (AF1) where F1 and F2 are well-formed formulas. The symbols, A,, f, t will be read "or," "and" "not," "falsehood," "truth," respectively. 5o2. (a) We may allow an infinite number of propositional variables in 5.1 but for greater perspicuity in the applications to switching theory the finite cases will be usedo (b) The punctuation symbols of 5o1 are dispensable. We may, for example, write v PiP2 instead of (pI v P2), A PP2 instead of (pl A P2), ~Pi instead of (-P1), so that (pl v (~(pI A P2))) may be written vpl A P1P2o We shall, however, adhere to the scheme of 5J1 with the modification, however, that parentheses will sometimes be dropped when it is believed that this will not cause confusiono The syntax as well as some applications of parenthesis-free notation are discussed in items 24 and 29 of the bibliography~ 5~30 Define t U t = t U f = f u t = t, f u f = f; t n t = t and t n f = f n t = f n f = f [cfo 4.22 (4)1; Ot = f, [Df = to We will now associate with each well-formed formula F a function g(n) from n-tuples of t's and f's and with values which are t or f as follows (the xi's below vary independently through (t,f)oI 14

(1) gin) (X1,X2,..,xn) = Xi if F is Pi; gn)(x1,x2,..oXn) = t if F is t; g(n) (XiX2,.,xn) = f if F is f; (2) g (n)(XIX2,,.,xn) = g,(n)(xi,x2,,.,xn) U g(n) (x1,x2,Xn)) if F is (F1 V F2); (3) g )(xl,x1,...,xn) = 4n)(xn,x2,..*,xn) n g()(xn,x2,X..,xn) if F is (F1 A F2); (4) 4 n)(XIX2...X)= Eln )(xIx2,..,xn) if F is (F1). n (n) (n) Now define two formulas F,G to be equivalent, F eq G, ff g = gG 5.40 Theorem. F eq G, where at most the variables pl,. oPn occur in F,G, if and only if F 9q G where m > n. Proof. It is obvious by induction on the number of occurrences of operation symbols (V, A,-) in F that gpm)(xlx2.ooXn, o.O,xm) = g(n)(xl,x2,...,xn) from which the result follows. Because of this theorem we write "F eq G" if F eq G for some no 5.5(a). A binary relation R which over a set S satisfies: (1) aRa for every a c S (reflexivity) (2) aRb implies bRa (symmetry) (3) aRb and bRc imply aRc (transitivity) is called an equivalence relation. Show that if l(a) is the set of all x such that xRa, then (4) a c S, b E S, and aRb imply R(a) = R(b) (5) a e S, b e S, and aWb imply I~(a) nR(b) = (6) S is the union of all classes E(ka) where a runs throughi S. n 5.5(b) Show - is an equivalence relation over the integers for each positive integer n, where a n b means a-b is devisible by n Conversely, if S is the union of disjoint subclasses (i.e., if U,V are subclasses either U = V or U (f V = 0), and if aRb is interpreted as meaning that a,b are both in the same subclass, then R satisfies (1), (2), (3)o 5.6. The class of all well-formed formulas W may be partitioned into subclasses W1,.oWr (cf. 505) such that any two formulas in the same subclass are eq-related, Wi nfWj = 0 for i ~ j and W = W1i Uo~o U Wr. Note that if F eq F' 15

and G eq G', then (F v G) eq (F' v G') and (F A G) eq (F'A G')o Hence we may define Wk = Wi v Wj if H is F v G) and H C Wk, F E Wi, G e Wj. Wi A Wj is defined analogously. Theorem. If C = ([W1,o.oWr), then (C, v, A) is a Boolean algebra where V,A are the operations defined immediately above. Indeed (a, V, A ) is isomorphic to (B, v, A) of 4.22 (5). Proof By virtue of 5.3 and the definition of eq, with each Wi is associated a unique function from n-tuples of t's and f's with values which are t or f o Moreover, with each function g of this kind there is a formula F such that gn) = g. The formula F may be chosen as a disjunction of conjunctions of the form ql A q2 Aoo. A qn where each qi is Pi or (-pi); for each n-tuple xl,x2,, O, Xn such that f(xi,x2, oo,xn) = t construct the "corresponding" conjunction of qi's where qi = Pi if and only if xi = t; the disjunction of all conjunctions of this kind "corresponding" to n-tuples xlxc2,o.,x n such that f(xlx2,.ooXn) =t is chosen as F. For this F, g n) = go Hence, for each function g from n-tuples of t's and f's with values which are t or f, there is a Wi such that for each F c Wi, gn) = g. The correspondence indicated between C and these functions g yields a correspondence between C and B of 4.22 (5) if t is correlated with 1 and f with 0. The correspondence between C and B is an isomorphism between (C, v, A) and (B, v, A) of 4.22 (5). Since the latter system is a Boolean algebra, the former is. Note, too, this implies r = 22no 5.7. By virtue of the theorem of 5.6, the identities which hold for Boolean algebras carry over to formulas of any propositional calculus with "=" replaced by "eq.o" For example, x A(y V z) = (x A y) V (x A z) implies F A(G v H) eq (FA G)V (F A H), and xVy = x A y implies -(F v G) eq (-F) A ( —G) where F,G,H are arbitrary well-formed formulas of a propositional calculus. 5.8. If G is a well-formed part of a well-formed formula F and G eq G', then F eq F' where F' is obtained from F by replacing an occurrence of G by G'. This may be proved by induction on the number of operation symbols which occur in Fo For example, if F is (Pa V (P2 A ("P2))) A P3, then G may be taken as P2 A (~P2), G= as 0, so that F' is (Pi v 0) A p3o Repeating the process with "G" the formula (Pl V 0) and "G'" the formula Pl, we obtain Pi A P3 eq (piV 0) A P3. Thus (Pi V (P2 A (~P2))) A P3 eq pi A P3 5.9. Exercises. Let A, B, C be well-formed formulas of a propositional calculus. Define: (A - B) to be (A A B) V ((~A) \ (B)); (A + B) to be (A A(~B)) V ((HA) A B); 16

(A + B) to be (-A V B) (A tB) to be (-(A A B)) (A 8B) to be (-(A V B)) Show that (1) (t + A) eq (-A); (2) ((A + B) + C) eq (A + (B + C)); (3) ((A - B) = C) eq (A a (B a C)); (4) (A + B) eq (B + A) and (A -B) eq (B — A) (5) (t + A + B) eq (A - B); (6) ((A -+ B) A (B -+ A)) eq (A = B); (7) (A + (B + A)) eq t; (8) A eq B if and only if (A -B) eq t; (9) Eq(A) < Eq(B) if and only if (A + B) eq t, where Eq(A) is the class of formulas X such that X eq A and < is the lattice ordering of the Boolean algebra (cf. Theorem of 5.6); (10) there is a formula in A, B, +, A, t which is eq-related to (a) AVB (b) A B (c) -A; ( 11) same as (10) but replace "+) A, t" by't, f"; (12) same as (10) but replace T+, A, t" by l"l\"; (13) same as (10) but replace +, A, t by "G"; (14) A V (A A B) eq A; (15) A v (A A B) eq A v B [of. 5.103; (16) (A A B) V (A A C) eq (AA B) V ( A C) V (B A C). 5.10. Notice that A - B - C (i.e., ((A -B) - C)) is not eq-related to ((A - B) A (B - C)). Note, too, that -, + are operations while eq, < are relations (cf. (8), (9) of 5~9). Furthermnore (A- B) is (an abbreviation for) a well-formed formula of the propositional calculus but (A eq B) is not. In what follows we will often regard a formula as denoting its equivalence class, so that the formula will denote an element of the Boolean algebra of 5.6. Under these circumstances we may write "A = B" instead of "A eq B" and "A" instead of "(~A) " 5.11. Application to series-parallel relay contact circuits. We shall restrict the meaning of relay contact to a device with two terminal posts which is capable of two states, in one of which there is a closed path between the two posts and in the other of which there is no closed path between the two posts. A contact is normally open if and only if there is no closed path between its posts when its controlling coil is not energized and there is a closed path between its posts in the contrary case. A contact is normally closed if and only if there is a closed path between its posts when its controlling coil is not energized and there is no closed path between its posts in the contrary case. 17

With a two-terminal series-parallel circuit constructed of relay contacts, but not their coils, we associate a diagram of the type indicated in 4.8 which indicates the structure of the circuit with the modification that each branch will be labeled by exactly one of the following: pl, Pi, P2, P2,'', Pn Pn and in such a way that (a) a letter without a bar is correlated with a normally open contact; a letter with a bar is correlated with a normally closed contact; (b) if one branch is labeled qi (qi is Pi or pi) and another qj, then i= j if and only if the coils controlling the contacts associated with qi, qj are the same. We now associate with each 4.8 diagram (but with branches labeled) a formula as follows. With the diagram Pi -P is associated the formula Pi which will be interpreted as "coil Pi is energized." (By coil Pi we mean the coil which controls the contact associated with the branch labeled "Pi.") With the diagram Pi is associated the formula Pi which will be interpreted as "coil Pi is not energized." Labels "t",("f") on such a diagram are interpreted as "there is a closed (open) path between the terminals." If with the diagrams the formulas A, B are respectively associated, then with their series connection the formula (A A B) is associated, and with their parallel connection — _ — the formula (A V B) is associated. The interpretation of (A A B) is obtained by following the interpretation of A by "and" and then the interpretation of Bo The interpretation of (A V B) is obtained similarly but writing "or" instead of "and." Here "or" is understood in the inclusive sense, i.e., (A V B) is false if and only if both A and B are false. For example, with the diagram P2 18

is associated the formula P! A (pl V P2) which is interpreted as: coil Pi is energized and (either) coil P1 is not energized or coil P2 is energized. Conversely, given any well-formed formula constructed out of Ply Pi, P2, P2,.ec by means of V, A, there is a two terminal series-parallel network (essentially unique) which has the given formula as its associated formula. Notice that there is a closed path between the terminals of a two-terminal network when and only when the associated formula (under the given interpretation) is true. Two networks are equivalent if and only if there is a closed path between the terminals of one when and only when there is a closed path between the terminals of the other. If this statement is properly understood, it follows that two networks C1, C2 are equivalent if and only if their associated formulas F1, F2 are eq-related, i.e., F1 eq F2. Thus the network indicated above is equivalent to the network. Pi P2 since (Pi A (`p V p2)) eq (pI A P2). The former network contains three relay contacts while the latter network contains only two. 5,12. Exercises. (1) Let P = a v (a/ A b A c) v (A F A c) v (aA A c). (a) Write P in expanded disjunctive normal form (i.e., as a disjunction of conjunctions, each conjunction of which involves all three letters). (b) Put the negation (complement) of P in the same form. [This may be done by inspection from (a).] (c) Simplify P and indicate with a diagram the two-terminal seriesparallel network associated with the simplified formula. (2) The formula (a A b) v (a A c) v (a A b) V (b A c) is a disjunction of four conjunctions. Which, if any, of the conjunctions, when deleted, yields a formula equivalent to the given one? (3) Find a relay contact network equivalent to the one given below but using at most five relay contacts. Hint: The result of (2) may be useful. (4) Construct a relay contact network (if one exists) controlled by three coils and such that whenever the state of exactly one of the coils changes, the state of the network changes. (5) Same as (4) but change "exactly one" to "exactly two." 19

a b d a a b b a a C ) a - d b a b.. Diagram for exercise 5.12 (3). 5.13. Quine's method.53 This subsection is concerned with those and only those formulas which are disjunctions of conjunctions. Each conjunction is a conjunction of literals, a literal being a propositional variable with or without a bar over it (i.e., negated or affirmed). It is assumed that a conjunction contains at most one occurrence of a letter. Conjunction will be denoted by concatenation. A conjunction which is part of a formula is called a clause of that formula. An example of such a formula is: P1P2P3 V P2P3- Its clauses are P1P2P3 and P2P3An implicant of a formula F is a (nonempty) conjunction A such that (A + F) is a tautology. Given two conjunctions A and B., A is said to subsume B if A (possibly rearranging its constituent literals) may be written BC (C is a, possibly empty, conjunction) where "BC" denotes the concatenation of B and C. An implicant of a formula is prime if it subsumes no implicant other than itself. The prime implicants of the formula above are: P1P2, P2P35.13.1. Theorem. Given a formula F (not a tautology), there is a formula F' such that F eq F' and F' is a disjunction of all and only the prime implicants of F. Rules (1), (2), (3) below may be applied (in any order) only a finite number of times to the formula F at the end of which time the formula F' is obtained. (If one conjunction is obtainable from another by rearranging its constituent literals, the two conjunctions will be identified.) 20

Rules: (1) If A,B are clauses of a formula and A subsumes B, then delete A from the formula. (2) If pi and piA (for some i) are clauses of a formula, replace piA by A; similarly if pi and pi are interchanged. (3) If piA and piB are clauses of a formula G and A and B are both nonempty, then replace G by G V C, where C is obtainable from AB by deleting duplications of literals; this rule is applicable provided that (a) no letter both with and without a bar occurs in AB and (b) C subsumes no conjunction which is part of G. Proof. Note that a clause of a formula is an implicant of that formula. To show the rules can be applied only a finite number of times, note that, if A is a clause of a formula, then applications of any of the rules yields a formula which contains the clause B (possibly A itself) which is subsumed by A. It follows, because of proviso (b), that rule (3) cannot "yield" the same clause C twice. Since there are only a finite number of (distinct) clauses which are implicants of a given formula, it follows that rule (3) can be applied only a finite number of times. Since applications of rules (1) and (2) reduce the number of occurrences of literals in the formula and since rule (3) can be applied only a finite number of times, it follows that rules (1) and (2) can be applied only a finite number of times. It will now be shown that if the prime implicant A of a formula G (not a tautology) is not among the clauses of G, then either rule (2) or (3) is applicable to Go Since G is not a tautology, there is an assignment of truth values to the letters occurring in G which will make G false. Since (A + G) is a tautology, it cannot be that no letter in A occurs in G, for if that were the case, an assignment of truth values to the letters of A could be made (independent of the assignment to the letters of G) which would make A true. If A is of the form qiB (where qi is pi or pi) and pi does not occur in G, then (tB + G) is a tautology so that (B + G) is a tautology, which contradicts the assumption that A is prime. Hence each letter which occurs in A occurs in G. Furthermore A subsumes no clause of G, for each such clause is an implicant of G while A is a prime implicant. Thus A has the properties: (a) it subsumes A; (b) it subsumes no clause of G; (c) every letter which occurs in A occurs in G. There is a longest conjunction L (with no duplications of letters) which satisfies (a), (b), and (c)o Note that, since L subsumes A, L is an implicant of A, and since A is an implicant of G, it follows that L is an implicant of G. It cannot be that every letter in G occurs in L, for if this were the case, then for every clause C of G. every letter in C occurs in L but since L does not subsume C, by (b), the truth assignment to the letters of L which makes L true will make C false. From this follows (L + G) is not a tautology, which contradicts the fact that L is an implicant of G. Thus some letter, say pi, occurs in G but not in L. Consider piL and PiL. These conjunctions satisfy (a) and (c), Since L is a longest formula satisfying (a), (b), and (c), it follows that piL subsumes a clause of G; pi must occur in this conjunction since L does not subsume it; call this conjunction piD (D possibly empty), Similarly piL subsumes piEo (The con

junctions piD and piE are distinct since both Pi and pi cannot occur in the same formula.) Not both D and E can be empty for this would mean G is a tautology. If exactly one of D,E is empty, then rule (2) is applicable; if neither is empty, then rule (3) is applicable. Thus, if rules (2) and (3) are not applicable to a formula G, then every prime implicant of G is a clause of Go If rule (1) is not applicable to a formula G, as well as rules (2) and (3), then every clause of G is a prime implicant of Go For suppose the clause A, of G, is not a prime implicant. Then since A is an implicant of G, it subsumes a prime implicant B of G. Since rules (2) and (3) are not applicable (by the argument of the preceding paragraph), B is a clause of G, so that rule (1) would be applicable. To complete the proof of the theorem, it is necessary only to observe that application of any of the rules yields a formula equivalent to the given one [cf. 5.9 (14), (15), (16)]. 5.13.2. To recapitulate, suppose a formula F is given. Applying any of the three rules to F yields a formula F1 yields F2, etc. The formulas Fa, F2, -.. are obtained such that Fl eq F2 eq F3 eq.... The first paragraph of the proof shows that this sequence of formulas must terminate, i.eo,, there is a formula Fm in the sequence such that none of the rules is applicable to Fmo The second paragraph establishes that, if rules (2) and (3) are not applicable to Fi, then every prime implicant of Fi (the prime implicants of F and Fi are the same since F eq Fi) is a clause of Fi. In particular, every prime implicant of Fm(F) is a clause of Fm. In addition, by the third paragraph, every clause of Fm is a prime implicant of Fm(F). 5.13.3. Exerciseso (1) Prove the following corollary to 5.13.1: if F is a disjunction of conjunctions of propositional variables, then every prime implicant of F is a clause of F. Hence applications of rule (1) above are enough to produce the F' of the theorem. (2) Let rule (3') be the same as rule (3) except that the restriction "A and B are both nonempty" is removed. Then the statement obtained from theorem 5.13.1 by replacing rules (2) and (3) by rule (35') is a theorem. If one applies rule (3') successively, without intervening applications of rule (1), one obtains a formula such that every prime implicant of the formula is a clause of the formula. Having obtained such a formula rule (3') is no longer applicable [even after one or more applications of rule (1)] so that F' (of the theorem) may be obtained from F by repeated applications of (3') followed by repeated applications of rule (1). (3) Show that, if A is an implicant of B and B an implicant of C, then A is an implicant of C. [Cf. 5.9 (9) ] (4) Determine whether ((A +- B) + C) eq (A + (B + C)).

5.1354. The significance of prime implicants for the simplification of formulas (which are disjunctions of conjunctions of literals) is this: if a clause of a formula is not a prime implicant, then it may be replaced by a prime implicant which is subsumes, yielding an equivalent formula which is "simpler," e.g., from the point of view of number of occurrences of propositional variables. (Recall that the number of relay contacts in the associated relay contact network is equal to the number of occurrences of propositional variables.) 5.13.5o If one makes use of 5.13.1 to simplify a formula, it is better strategy to apply rules (1) and (2) as often as possible [rather than to proceed as in 5.13.3 (2), for example]; that is, at any particular time, if (1) or (2) is applicable, one applies either independent of whether (3) is applicable or not, so that (3) is applied only when rules (1) and (2) are not applicable. The method will be illustrated by the following example: (1) PIP2P3 V P2P3 V P1P4P5 V P2P4 V P3P4 s PlP3P4 Rule (2) yields: P1P2P3 v P2P3 v PlP4 V P2P4 v P3P4 V P5 v PIP3P4 The last clause subsumes the third and may therefore [rule (1)] be deleted. Applying rule (3) to the third and fourth clauses yields the clause P1P2 which is subsumed by the first clause, Thus, the following formula is obtained: (2) P2P3 V P lP4 V P2P4 V P1P2 V P3P4 V s Applying now rule (3) to first and third clauses, to first and fourth clauses, to first and fifth clauses, and to third and fifth clauses yields: (3) P2P3 v P1P4 V P2P4 v PIP2 V P3P4 V P5 V [P34 V PIP3 V P2P4 V P2P3] None of the rules is now applicable, so that all prime implicants of the given formula have been obtained. The clauses in brackets are clearly jointly dispensable. Other clauses may be dispensable possibly conditional upon the presence of some or all of the bracketed clauses. If A is the formula obtained from (3) by deleting the first clause, then one may check that (P2p3 + A) is a tautology, so that A eq B where B is the given formula; however, P2P3 is not dispensable from (2). Notice that PIP2 is dispensable from (2) since it was obtained by rule (3) applied to P1P2 is dispensable from (2) since it was obtained by rule (3) applied to PIP4 and P2P4, which are present in (2). Another way of seeing that PEp2 is dispensable is to note that (pfp2 + C) is a tautology where C is (2) with PiP2 deleted. Thus the given formula is equivalent to (4) P2p_ V P1P4 V p2p4 v p3p4 v pS v [P1P2 V p3p4 V P1P3 V P2P4 V P2P3] where the clauses in brackets are simultaneously dispensable. To check whether this formula is "simplest"t would require much tedious labor. We will not carry the argument further. As the argument has, perhaps, already demonstrated, the simplification pro23

cedure is straightforward and reasonably quick up to the point where one obtains all prime implicants. From that point on the procedure is in complicated cases quite tedious and lengthy if one wants to be sure he has a simplest equivalent of the given formula. Notice, however, that the given formula has sixteen occurrences of literals while our simplest equivalent has only nine. For further examples and simplification suggestions the reader is referred to item 2 of the bibliography, page 1. 5.14. A law of duality. The dual AD of a well-formed formula A is now defined inductively on the length of a formula. (1) If A is t (f), then AD is f (t); if A is Pi, then AD is pi. (2) If A is (B V C), then AD is BDA CD; if A is (B A C), then AD is BDV CD (3) If A is ~B, then AD is (BD) Thus, for example, if A is p V (-(P2 A p3)), then B is p1 A (-(P2 V P3)) Lemma. If g is the function (of n variables) associated with the formula A (cf. 5 3) and gD is the function associated with AD, then gD(xl,x2,..,xn) = g(l,x2,-o,x —n), where the bar over g indicates the complement of g(l,x-2,- ~xn)" t is f, and f is to The proof is by induction on the length of the well-formed formula. Proof. If A is t, then AD is f, g(x1,x2,,xn) = t, gD(xl,x2,..oxn) = f, g(XlX — ee —,Xn) = t, and g(x1,2 —.,xn) = f, so that the conclusion of the lemma is satisfied. If A is f, the argument is analogous. If A is Pi, then AD is Pi, g(X1,x2,= g-n-xn) = Xi gD(X1iX2,, Xxn) = Xi, n) = i, and g(Xl1,2 oooxn) = xi, so that the conclusion of the lemma is satisfied in this case. Now suppose A is B v C, gD(xlx2,-loxn) = gB(xlX,o.,xn) and g(xx2,o,xn) = gc(XlX —. -,Xn) o Then gA(xl,x2, oxn) = gB(x1,x2,... i n) gC(xl,x2,Xn), so that gA(xX2,,-eixn) = g(X1,X2,. *,Xn) L gC(X1,3X2,'~nn) - gB(x1,x2,,xn) n gC(x1 X2,~~ n) - gED(x1,X2... *,Xn) fl gD(XlX2.,O~xn) Since AD is BD A CD, it follows that gA(xlx2,..(x.,n) = g~(xl,x2,' O-xn), so that gA(xix2, -,Xn) = gA(xl,x2,,X-n). The argument in the case A is B A C is analogous. Now suppose A is ~B and g (x1,x2, ~,xn) = gB(Xz,X2',Xn)o Then gA(xIx2, ~,xn) = gB(x1,x2,,Xn), so that gA(X1,X2r,o-,Xn) = gB(X1,X2, o,Xn)o Since

AD is -BD, it follows that gD(xl,x2, -.,xn) = g3(xl,x2,'i,xn), so that (using inductive assumption) gd(x1,x2,.,Xn) =.B.(XiX2,x-n) = gBlX,X2,' X —n) = gA(xiX2,~~.,xn)o Theorem. If A eq B, then AD eq BD, Proof. The result is immediate from the lemma: gA(x1,.,Xn) = gA(x., x x~n) -- g(x n) = gD(xl, * Xn) Corollary 1. If A is a tautology, then -(AD) is a tautology. Proof. Since A eq t, it follows that AD eq tD, AD eq f, and ~(AD) eq t. Corollary 2. If (A. B) is a tautology (cf. 5-9), then (AD - BD) is a tautology. Proof. By previous corollary -((A -B)D) is a tautology. On the other hand (A - B)D eq -(AD - BD) (see exercise 1 below), so that (AD - BD) is a tautology. Exercises. Show (cf. 5.9) that (1) (A - B)D eq,(AD - BD); (2) -(A - B) eq (-A) - B eq A - (-B) eq A + B; (3) (A 4 B)D eq (AD' BD); (4) (A B)D eq (BD -+ AD); (5) if A -+ B is a tautology then (BD + AD) is a tautology; (6) if Eq(A) < Eq(B), then Eq(BD) < Eq(AD), (7) A - B C eq A + B + C. (8) Every formula is equivalent to one in "expanded conjunctive normal form." Define this form by analogy with 5.12 (a). Use the result of 5.12 (a) and a duality law to obtain the desired result. 5.15. Preliminary to establishing a representation theorem for finite Boolean algebras, we note some further properties of Boolean algebras. 5.15.1. (1) x < x V y; x > x A y; (2) if x < y and x' < y?, then x V x' < y V yT and x A x' < y A y'; (3) if x < y and x < y, then x < y A y', and if x > y and x > y' then x > y V yl [these statements are immediate consequences of (2)1]; (4) x < y if and only if x A y = 0 if and only if x V y = 1. Proof. Suppose x < y. Then x A y = x and O = (x A y) A y = x A y. Suppose x A y = 0. Then x V y = (x A y) V y = y, so that x < y. (5) An element a in a Boolean algebra is minimal if and only if a f 0, and for all x if x < a, then x = a or x = O0 In a finite Boolean algebra, given any element y f 0, there exists a minimal element less than or equal to y. 25

(6) An element a in a Boolean algebra is an atom if and only if a # 0 and for all x either x A a = a or x A a = O. An element is minimal if and only if it is an atom. (7) If a,b are atoms and ab f 0 then a = b. (8) Let a, al, a2,..* an be atoms of an arbitrary Boolean algebra. (a) If x -= a V a2 V.. V an and a < x, then a = ai for some i. (b) a < yV z if and only if a < y or a < z. (c) a < y A z if and only if a < y and a < z. Exercise. Prove (1), (2), (3), (5), (6), (7), and (8) above. 5.15.2. Lemma. In a finite Boolean algebra, every element x is the join (least upper bound) of all atoms a in the algebra such that a < x. Proof. Suppose al, a2,'*o, an are all the atoms less than or equal to X. Then the element y = (al v a2 v... V an) < x [cf. 5.15.1 (3)]. It is sufficient then to show that x < y which is equivalent [cf. 5.15.1 (4)] to showing xy = 0O We shall show that the assumption that xy t 0 leads to a contradiction from which the desired result follows. If xy / 0, then there is an atom [5.15.1 (5)] a < xy so that a K x and a < y. From a < x and the choice of the ai's it follows that a = ai for some i. Hence a < y. Thus a < y A y = 0 [cfo 5.15.1 (3)], so that a = 0, contradicting the choice of a. 5.15.3. Theorem. If (A,v, A) is a Boolean algebra, it is isomorphic to (C, u, n) where C is the class of all sets of atoms.of A. Indeed, the function h which associates with each x E A the set h(x) of atoms a in A such that a < x is an isomorphism of (A, V, A) onto (C, U, n). Proof. Immediate from 5.15.2 and 5.15.1 (8). (Cf. 4.19.) Corollary. If r is the number of elements in a finite Boolean algebra, then r = 2m for some mo Two finite Bollean algebras are isomorphic if and only if they have the sane number of elements. 5o15.4. Example. Below is a lattice diagram of the Boolean algebra associated with the formulas of the propositional calculus in the case n = 2. (Cf. t PiM \ P PM pPi \/ P2 P P PLPP- -~rIP2 ~ P1Pf

501land 56,) Recall that is an abbreviation for PP2 V PP2 and - P2 is an abbreviation for P1P2 V PSP2. The atoms of this algebra are: PiP2, P1P2, PiP2, P1P2t The isomorphism which the theorem establishes applied to this case is: h(f) = 0 h(Pl1-P2) = [PLP2,PlP2) h(P1p2) = (PIP2} h(p2) = {(pP2, Pp2}I h(pPP2) (P2J h(r1) = ClPP2 P1iP2} h(pP2) = (P1P2} h(p1V P2)= IPIP2, PIP2, P1P2) h(P}P2) = {P1P2} h(PlVps) = {P1P2, Pl72, l1P2} h(pl) = (PIP2, P1P2} h(pzVr2) = PP2, PIP2, P1P2} h(p2) = (PIP2,9 P1P2) h(i1Vp2) = (P1P2Y PiP2, PIP2) h(p~+p2) = (PIP2, P1P2} h(t) = [PIP2, PP2,, P P2, PIP2} Notice that 5.15.2 provides the information that x is the join of the elements in h(x), e.g., Pi V P1P2 vPLp2; the right-hand member of the equality is the expanded disjunctive normal form of Pm V P25.15.5. Exercises. (1) In a manner analogous to the correspondence established on page 10, establish a correspondence between 4-tuples of O's and l's and the set of all subsets of P1P2, P1P2Y 1P2, P zP2o This correspondence together with the correspondence h in the example immediately above yield a correspondence between the elements of the Boolean algebra depicted in the lattice diagram and 4-tuples of O's and l's. This correspondence is an isomorphism. Relabel the lattice diagram of the example above in a way indicated by this correspondence and check that join and meet are preserved under this correspondence. Note that such a correspondence may also be obtained by associating with a formula the sequence of values of its associated function, for a fixed ordering of its arguments. (Cfo 5.3o) (2) A set S of elements is closed with respect to a binary (n-ary) operation o if and only if xl o x2 [o xlx2m- xn] is in S whenever xl,x2 [xl,x2,*..9 xn] is in S. What is the smallest class of elements in the 16-element algebra depicted above containing (a) Pi, P1+P2, and closed under join and meet? (b) pi, P1+P2, and closed under join, meet, and complement? (c) Pi -P2, P1+P2. and closed under join, meet, and complement? (3) An isomorphism of an algebra onto itself is called an automorphism. Show that a Boolean algebra with 2n elements has exactly n!' automorphisms. Hint: In any automorphism, atoms will go into (be associated with) atoms. 27

6. MULTI -TERMNAL NETWORKS 6.1. An example. P1P2 v PlP2 P2 P1 P3 v P1P3 p2A3 Consider a particular truth assignment, say 1, 0, 0 (i.e., t, f, f) to P1, P2, p3, respectively. Then the following matrix 1 2 3 4 1: l1 0 0 0 \ 2 1 1 1 1 3 O 1 1 0 2( 01 4 1 0 1 has a "1" in the i,j position (i.e., the ith row and jth column counting from top to bottom and left to right, respectively) if there is a closed path between node i and node j (for this truth assignment); otherwise the ijth entry is "0." The convention that there is a closed path between a node and itself is adopted. Let the i,jth entry be aij. Then the matrix can also be described as follows: aii = a.. = aj1. a23 = a24 = 1, and a12 = a,3 = a14 = a34 = 0. 6o2, Pierce and matrix product. With each binary relation R defined over a finite set S of n elements, n > 1, a matrix M(R) of O0s and l's is associated as follows. We assume S = [1,2,.X0o nh. The ijth entry of M(R) is 1 if iRj, otherwise 0. Every n x n matrix (n rows and n columns) of 0gs and l's is M(R) for some R. For example, the matrix of 6.1 is M(R) if R is reflexive over 1,2,3,4, symmetric, and 2R3, 2R4, 1J42, 1~35 1i4, 3~4, 28

The (Pierce) product R1 x R2 of two binary relations is defined as follows: x(R! x R2)y if and only if there exists an element z such that xRlz and zR2y. The (matrix) product C = A x B of two n x n matrices A = (Aij) and B = (bij) is defined as follows: cij = a=l -ik O bkj. (It is convenient to use the same symbol "x" for both Pierce and matrix product.) This makes sense if an operation "+" and an operation "." are defined over the elements denoted by the entries of the matrix. (It is also assumed here that "+" is associative.) We shall be interested in the case where the matrix entries denote elements of a Boolean algebra (more generally, a lattice) and will, therefore, write Cij Vl aikAbkj and "A" will sometimes be omitted (but understood). This matrix product will sometimes be referred to as "the Boolean matrix product." Notice that, if A and B have l's along the main diagonal then so will C, since cii = Vkn=1 aikbki 1 since among these disjuncts is aiibii = 1o 6o2o1. Theorem. If R1, R2 are binary relations defined over the same set S of ii elements (assumed without loss of generality to be the first n positive integers), then M(R1 x R2) = M(R1) x M(R2) Proof. Let cipj aij, bij be the i,jth element of the respective matrices M(RL x R2), M(R1), M(R2)o Then ij = (aik A b kj) so that c.. 1 if and only if there exists an integer k, 1 < k < n, such that aik = 1 kj if and only if there exists k c S such that iRlk and kR2j if and only if i(RB x R2)j. 6.2.2. Corollary. The function M is an isomorphism between the system of all binary relations (defined over a fixed set of n elements) under Pierce product,V,Aand the system consisting of the set of all n x n matrices with 0, 1 entries, under Boolean matrix product and V, A, Let A = (aij), B = bij) be n x n matrices with all the ai} bij elements of some lattice. The ij element of AVB is by definition aijVbij. AAB is defined analogously. For binary relations x(RBVR2)y if and only if xRBy or xR2y, R1/AR2 is defined similarly. 29

6.2.3. Theorem. (a) The set of n x n matrices of 6.2.2 form a lattice under V,A, and if L is a Boolean algebra, then this lattice is a Boolean algebra. (b) The subset of matrices of (a) with l's along the main diagonal (i.e., aii = 1 for 1 < i < n) is a Boolean algebra, if L is a Boolean algebra. (c) A x (BVC) = (A x B)V(A x C). (d) (A x B) x C = A x (B x C). Proof. (a) It is obvious that this system of matrices forms a lattice, say oo oZhas a zero (one) element, namely, the matrix all of whose entries are "0" ("1"). If A = (aij), it is easily seen that A = (aij)o (b) It is obvious that this system of matrices forms a lattice, say c'. Z I has a zero element, namely, the matrix all of whose entries are "O" except the elements along the main diagonal which are all "1." X' has a one element, namely, the matrix all of whose entries are "1." If A = (aij), B = (bij), and bij = aij for i f j and bii = 1, then B = A. (c) The i,jth element of A x (B VC) is n n k=l ik(bkj kj j) = (aikbkjVikck) = k1 aikbk V(k-l aikCk which is the join of the ijth element of A x B and A x C. (d) The i,jth element of (A x B) x C is k/1 a~bk Ckj aiiblkCkj = N ail b~kck k=l which is the iAjth element of A x (B x C). 6.3. Connection matrix, An n x n symmetric matrix with l's along the main diagonal and with entries which are formulas of the propositional calculus may be associated with those relay contact networks constructed as follows: With each ij, i < j, a two-terminal network with terminals ij is constructed whose behavior is given by the propositional formula which is the i,jth entry of the given matrix. The two-terminal networks are then connected" together by con3o

necting (identifying) those terminals with the same name. If each two-terminal network with terminals i,j is so chosen to be the series-parallel network whose "structure" (cf. 5.11) as well as "behavior" is given by the ijth entry of the matrix, then the (labeled) network associated with the matrix is "essentially" unique. Conversely, given a network, if one "labels" enough of its nodes, 1,2,.a, n, there is an n x n matrix (of the kind mentioned above) which has the given network as an associated (in the above-mentioned way) network. B choosing enough nodes, the two-terminal network associated with the i,j entry of the correlated matrix will be series-parallel. A matrix correlated with a network in this way is called a connection matrix of the network. Any symmetrnc matrix with ls on the main diagonal and propositional formulas as entries is a connection matrix of some labeled network. A labeled network corresponding to the diagram of 601 has as its connection matrix the symmetric matrix A = (aij) with l's along the main diagonal and al2 = PlP2V~lP2, als = P2P3, a14 = P1, a23 = Pmp3VP1P3 9 a24 = P2, a34 = PlP2P3 6.4. Characteristic matrix. The characteristic matrix x(A) of a labeled network with connection matrix A is a matrix with the property: the ijth entry is a propositional formula which takes on the value 1 for those and only those truth assignments which correspond (cf. 5.11) to states of the relay coils which result in there being some closed path between nodes i and j. In example 6 1 the characteristic matrix X(A) = (bij) where b12 = P1P2VPlf2, b13 - p2P3V Pl2P3, b14 = PP b b23 = PIP3V PIP3, b24 = P2, b34 = PmP3V Pp2P3VPLP2P3 We indicate the calculation for b13. The condition under which there is a closed path from node 1 to node 3 and not passing through any labeled nodes is given by P2P3. The conditions under which there is a closed path from node 1 to node 2 and from node 2 to node 3 and not passing through any labeled nodes (except 2) is given by (P1P2 VplP2) (Pf3V 1P3). Similarly "corresponding" to 143 is PI(P1P2P3), to 1243 is (P1P2VPLP2)P2(P1P2P3), and to 1423 is Pl(P2)(PlP3VPlP 3). Thus the condition under which there is any closed path from node 1 to node 3 is given by (p2p3) V(plp2 VP12)(P153 VPP3)V 1(P1P2P3)V(PlP2V 5P2)P2(PlP2P3)V PlP2(P1P3VP1P3) which simplifies to P2P33VPP2P36~5 Analysis theorem. 6b.1. Theorem, if A is the n x n connection matrix of a labeled network,

then A < A2 < A3 <... < Ar r+l n-~ thenA<A2<A3<... <Ar = Ar+l... = A.l = x(A), where r < n. Proof. Consider a fixed truth assignment T to the propositional variables occurring in the entries of A yielding a matrix AT of 0~s and ls. Let RT be the associated relation, i.e., M(RT) = AT (cf. 6.2) Then i j, m > 1, means there is a closed path (under this truth assignment) from node i to node j passing through at most m-i labeled nodes of the network other than i,j. Since there are only n-2 such nodes, it follows that RT RT = RT = Hence, 2n-l n ^n+l by 6.2.1, A = AT = AT =... Since RT < R2 < R3 <... (i.e., xRTy implies xRBy, etc., or still otherwise stated, ~RT RT =, etc.), it follows (6,2.2) that AT A< AT _< A < Inasmuch as these relations hold for each truth assignment T and (A x B)T AT x BT (by 5.3 and the definition of matrix product), the results follows. 6.5.2. Corollary. A = A2 if and only if A = X(A). Proof. If A = A2, then A x A = A2 x A so that A = A2 = A3. Similarly A = An-1 = X(A). If A = x(A) then A = An-l and A2 = An = X(A) = A. 6.6. Synthesis theorem. 6.6.1. Lemma. If AB,CD and n x n matrices whose entries denote elements of a lattice and if A < C and B < D, then A x B < C x D. Proof. The ijth elements of A x B and C x D are, respectively, k=l aikbkj' kl cikdkj Since A < C, it follows aik < ciko Similarly bkj < dkj. Hence aikbkj < cikdkj. It follows that Vakbk < V Z dkj k a ikbkj <- Cik dkj 6.6.2. Corollary. If A, B are connection iatrices then (a) A < X(B) if and only if X(A) < X(B); if A < B, then X(A) < X(B) Proof. (a) If X(A) $ X(B), then A < x(B) since A < X(A). If A < x(B), then A x A $ X(B) x X(B) = X(B). Similarly A4 < x(B), etc. Hence x(A) < x(B) (b) If A < B, then A < X(B) and (a) gives the result. 6.6,3~ Theorem, If x(X) < X(Y) < X(A), then x(A) = X((AA^)VY), where X is understood in the sense of 6.2.3 (b) (i.e., X is obtained from X by comple32

menting each element of the main diagonal). Proof. It will be shown that (a) X(A) < X(AXVY) and (b) x(AXVY) < x(A). There will be several applications of 6,6.2 (a)., Note that since X < X(Y), it follows [5.15,1 (4)] that XVX(Y) = 1 (the all 1 matrix). Hence A = A(X Vx(Y)) = A(AX VX(Y)) so that A < AXVx(Y), Now AXVx(Y) < (AXVY)n =- X(AXVY) since among the disjuncts of (AXVY)n'l, (AX)n- and n appear. Thus, A < X(AXVY) and (a) follows. To obtain (b), note that AX < A < x(A) and Y < x(A) so that AXVY < x(A) and (b) follows. 6.6.5. Theorem. If X(A) = X(B) and if A < C < B, then (a) X(A) = x(C), (b) X(A) = X(AVB), (c) X(A) = x(A x 3). Proof (a) Immediate from 6.6.2 (b) and hypothesis. (b) A < AVB so that x(A) < X(AVB). A VB < x(A)V x(B) = x(A) so that x(AVB) < X(A)o (c) Analogous to (b). 6,6.5. The results of 6.6.3 and 6.6.4 are now applied to 6.1 (cf. 6.3, 6.4). I PiP2V P1P2 P2P3 P A = 1 PiP3 V P1P3 P 1 P1P2P3 /1 PiP2 V PIP2 P2P3 V PlP2P3 PI X(A) - - 1 P173 V P1P3 P2 1 b34 where b34 = PLP3VPP2eP3 V PlP0P3 Let Y12 = PLP2, Y13 = P2P31 Y14 = P1, Y23 - PiP3a Y24 = P2, Y34 P1P2P3o Then Y < x(A), Choose X = y2 so that X(X) X= (Y). A calculation yields: x12 - pIP2V Pp2, xl3 = TP2P3 x14 = pL, x23 = (IVP2)p3Vp1p2P3, x24 = P2, x34 = PzP2P3VP1P2P3VP-LP2P3. If Z = AXVY, then a calculation yields: zl2 = P1P2 z3 z3 P2PaP39 Z4 = P1 z23 = PP —2P3V PlP3a z24 = r2, and z4 = PIP3s Thus X(Z) - X(A)o Let uz P1P29 uz3 = P2P3 u14 = [1 u23 = P1s3V1lP3, U24 = P2u34 = P1P3- Then Z < U < x(A). Hence X(U) = X(A) 33

6.7. Exercises. (1) Prove: If A is an n x n matrix, with elements in some lattice, then AVA2 V V An = AVA2 V... V An+r r > 0. (2) (a) Show that the n x n matrices with elements in some lattice with zero element and which have zeros along the main diagonal are closed under the operation (dual to "Boolean" matrix product). n cij = /\ (a ikV bkJ) - k=l ik~ bkj (b) Define a (binary) operation on binary relations (dual to Pierce produce) which "corresponds" to the matrix operation defined above, in the case where the elements are drawn from the two-element Boolean algebra. (c) Determine whether the set of connection matrices modified so as to have Ogs along the main diagonal is closed under matrix product. (3) A permutation of a set S is a 1-1 function from S onto itself. If A is an n x n matrix with elements in some lattice, the determinant IAI of A is defined as follows: IAI = V a.t(1) a2X(2).. ani(n) where it runs through all permutations of S = {1,2,,oo nj. Show: (a) IAl ABI < XA x BI; n-l (b) A = M where A is a connection matrix and mi. is the determinant of the matrix obtained from A by deleting the dth row and ith column. Is the assumption that A is symmetric essential? (4) If connection matrices are called equivalent if their characteristic matrices are equal, then it has already been shown that each equivalence class is closed under V, x. Does the same hold forA? (5) Let matrix B be the same as matrix A except that b14 = b4l = Tl V P2VP3 and b24 = b42 = plV-P2V 3. "Simplify" B.

7. AUTOMATA AND SEQUENTIAL CIRCUITS2p28~33145p48y~ 7.1. Definition. An automaton A is a quintuple (I, V, Q, f, g) where I is a nonempty finite set of objects called input states, V is a nonempty finite set of objects called output states, Q is a nonempty finite set of objects called internal states, f is a function (called the direct transition function) from I x Q to Q. i.e., a function which associates with each i c I and q e Q an element f(i,q) E Q, and g is a function from I x Q to V (called the direct output function). With each automaton A and internal state q of A are associated functions T TA q (respectively called transition and output functions) from finite sequences of elements of I to elements of V as follows: TX q(i) = f(i,q), TA,q(i) T.Zgq1)= g(i,q), T,q(Si) = f(i,T q(S)), TX,q(Si) = g(iTA7q(S)), where i is an arbitrary element of I, and S is an arbitrary (nonempty) finite sequence of elements of I. The subscript "A" will be dropped in discussions concerning a single automaton. 7.2. An example. Let I = [0,1) = V, Q = [ql, q2, q3) and f,g be given by the following table: f g O, q1 ql 0 O q2 q3 1 O, q3 q2 1 l, ql q3 1 1, q2 q3 0 l, q3 q1 1 Notice that the table specifies the automaton completely. The information in the table may also be presented by a direct transition-output diagram. 35

0-0 1-1 0-1 1-0 The label "a-b" refers to input state a and output state b. The transition and output functions associated with each of the internal states is now indicated: Sequences of input T1 T2 T1 T2 T1 T2 states 0 q! 0 q3 1 q2 1 1 q3 1 q3 0 ql 1 00 q 0 q2 1 q3 1 01 q3 1 qq 1 q3 0 1 0 q2 1 q2 1 ql 0 11 41 1 q1 1 q3 1 0 1 q1 1 1 1 q 1 10 0 0 3 1 q3 1 4l 0 7 3. It is often convenient to interpret the transition and output functions of an automaton, relative to an internal state q, in the following way. The automaton A is regarded as being in state q at "initial" time, say time t = O. If TA,q(S) = q*, T2,q(S) = v where S = ioil...in, ik C I, q,q* C Q, v C V, this is interpreted as meaning: if the input state of the automaton at time t = k, O _ k < n, is ik, then the internal state of the automaton at time t = n+l is q* while the output state of the automaton at time t = n is v. The corresponding interpretation for the direct transition and direct output functions of an automaton is this: if at a particular time t the internal state of the automaton is q while its input state is i, then f(i,q) is the internal state of the automaton at time t+l while g(i,q) is the output state of the automaton at time t. With this interpretation in mind, note that associated with each sequence io, il,..., in of input states and internal state q is the sequence q, T~,q(io),o

T q(ioil... in1 ) of internal states and TA,q(io), Tq(ioi.., (oilin of output states. The kth member of each of the three sequences is, respectively, the input state, the internal state, and the output state of the automaton at time k-l. For the automaton in 7.2 above we indicate some sequences of input states and the associated sequences of internal and output states, assuming the automaton at time t = 0 is in internal state ql. Input state: 1 0 1 0 1 0 1 0 Internal state: ql qn q2 q3 q2 q3 q2 q3 Output state: 1 1 0 1 0 1 0 1 Input states: 0 0 1 0 0 1 0 0 1 0 0 1 Internal states: q! ql q1 q3 q2 q3 q ql ql q3 q2 q3 Output states: 0 0 1 1 1 1 0 0 1 1 1 1 Input states: 1 1 0 1 0 0 0 1 1 Internal states: ql q3 q3 ql q3 q2 q3 q2 q3 Output states: 1 1 0 1 1 1 1 0 1 In the same way in which finite sequences of internal states and output states are associated with finite sequences of input states, one may associate infinite sequences (corresponding to times t = 0,1,2,...) of internal and output states with infinite sequences of input states. 7.4. We now indicate how a logical net23'25 may be constructed to "behave" as does a given automaton by applying the process to the example of 7.2. The first step is to "code" the input, internal, and output states. In our case, it is necessary only to "code" the set of internal states. By this is meant: associate with each internal state an ordered pair (or triple or quadruple, etc.) of zeros and ones. The ordered pairs associated with distinct internal states are required to be distinct. For example, the association l1 00 q2 0 1 q3 1 is permissible. Corresponding to the table in 7.2 for f,g is the table x a b a* b* y 0, 0 0 0 0 0 0, 01 1 1 1 0,1 1 0 1 1 1,0 0 1 1 1 1,0 1 1 1 0 1 1 1 0 0 1 37

a*, b*, y may be expressed as propositional formulas in x, a, b as follows. [Note that, since, not all arguments x, a, b are specified in the table, more than one Boolean function (say for y) will satisfy the conditions expressed by the table ] a* = xabVxabv xab = xabv xa *= a(bv x) or b* = a b x a b* = xbv 7a bv x 9 V x a b = a bv x a b x a bv x a b v x a ab vf x b v x a = xb v x a b* = x bvxa y = x a b x a b v xabv x a b = x b x abv a b =b (av,x)v a b x We now construct a switch(es) with inputs x, a, b satisfying a* = a(b v x). or a a* In a similar way, switches may be constructed for b*, yo It is assumed that these switches act "instantaneously~" In addition the net will require delay elements 38

whose input and output are related as follows: c*(t) = c(t+l). It is further assumed, here, that c(O) = 0. We may now schematically indicate a net whose behavior corresponds (via the coding chos:en) to the automaton. The states (i.e., 0 or 1, active or inactive) of junctions a, b correspond to the internal states of the automaton. a* — a Y b b* b The "behavior" of this net is indicated by the following equations: a(t+l) = a(t)(b(t) v x(t)) b(t+l) = x(t)b(t) v x(t)a(t) y(t) = b(t)(a(t) v x(t)) V a(t)b(t) x(t) a(o) = o b(o) 00 The "tbehavior" of this net may also be expressed by the following equations: a*(t+l) = a*(t)[b*(t) v x(t+l)] b*(t+l) = x(t+l) b*(t) V x(t+l) a*(t) y(t+l) = b*(t)[a*(t) V x(t+l)] V a*(t) b*(t) x(t+l) a*(O) = x(O) b*(O) = x(O) y(0) = x(O). [Note that, if the internal state q and the output v of an automaton at time t+l are regarded as functionally dependent on q(t), and the input i at t+l and further q(O) and v(O) are dependent on q(O) and i(O), then (a*, b*) would correspond to the internal state of the associated automaton. ] 39

The "input junction" labeled t "x" assumes one of two (input) states. The "internal junctions" (a,b) assume one of three (internal) states, viz., 0 0, 0 1, 1 1o The "output junction" y assumes one of two (output) states. If x x(O) = 1, x(l) = 0, x(2) = 1, x(3) = 0, x(4) = 1, etc., the corresponding sequences for a, b, y are as follows: time 0 1 2 3 4 5 6 7 x 1 0 1 0 1 0 1 0 1 0 a 0 1 0 1 0 1 o b 0 1 1 1 1 1 1 1 y 1 1 0 1 0 1 0 1 7.5 The previous section indicates how our notion of automaton is associated with synchronous sequential circuitry. We now indicate a connection with asynchronous circuitry as typified by (sequential) relay circuits. This will be done by constructing a relay circuit associated with the logical net above as follows: t"x" sill indicate the state of a relay contact whose coil is outside the circuit; "a%" "'b*" will indicate the state of coils in the circuit and "ta,1" "b" will indicate the state of the contacts which relays a*, b* operate; "y" will indicate the state of a certain point in the circuit (high potential or low potential) a(t) b(t)' | a(t) b(t) x(t) b(t) x(t) x(t) a(t) b(t) a(t) {' _ a* (t) b*(t) 40

There are certain difficulties with this circuit, however. These difficulties can be appreciated by reference to the direct transition-output diagram of 7.2. Let us suppose the initial input of relay contact x is 1, i.e., x(O) = 1 and the coil controlling x remains energized. Then (a,b) starts in state (0, 0), then passes to (1, 1), then back to (0, 0), and back to (1, 1), etc. Coils a*, b* would oscillate back and forth between being energized and not, and the state of y would be constantly low potential. If the coil controlling x is now de-energized, the output would depend on the states of a,b at that time which, in general, could not be predicted in advance. A relay circuit associated with the automaton below does not suffer the same difficulty, If the coding of the internal states is such that at most one relay coil changes state at any instant, then if we assume the contacts on any relay operate "simultaneouslyt," the "behavior" of the relay circuit would correspond to the "behavior" of the automaton. 11-1 00-1 01-_,1~~ At 01-1 10-0 00-0 01-0 10-0 11-0 010-1 10-1 11-1 01-0 7.6. Exercises. 1. Construct the logical net associated with the automaton indicated above where qL, q2, qs3 q4 correspond, respectively, to 00, 01, 11, 10. 2. As 1 but construct a diagram of a relay circuit instead of a logical net. 35 If an automaton A has one input state, then for any internal state q there are integers m _ 0, p > 0 such that T,q(t) = TA q(t+p) for all t ~ m (cf. 7o1). The argument t represents an input sequence of length t. Further p is less than the number of internal states of the automaton. 4o Let f be any function on the non-negative integers with values in a finite set V and such that, for some m 0 ~, p >0, f(t) = f(t+p) for all t ~ m.

Construct an automaton A with one input state, whose set of output states is V and such that TA q(t) = f(t) for all t, for some internal state q of the automaton A. Here, again, the argument t of the function TAq is to be correlated with an input sequence of length t. 7.7o Behavioral equivalence. 7.7.1. Two automata A,B with the same set of input and output states are behaviorally equivalent with respect to (nonempty) subsets QA, QB of the internal states of A,B [written (A, QA)~(B, QB)l if and only if for each qA c QA there exists qB c QB such that (cf. 7.1) TA TB and similarly for A and B reversed. Two such automata are isomorphic if ang only if there exists a 1-1 function ~ from the internal states of A onto the internal states of B such that OfA(i,q) = fB(i,,(q)) and gA(i,q) = gB(i,,(q))s An internal state q' of an automaton A is accessible from an internal state q of A if and only if q' is q or there exists a finite sequence S of input states of A such that TqI(S) = q'. An automaton A is minimal with respect to a subset Q of its internal states [briefly, (A,Q) is minimal] if and only if (1) for every internal state q' of A there exists an internal state q c Q such that q? is accessible from q and (2) if q,q' are distinct internal states of A, then Tq / T2. An automaton is reduced if and only if (2) holds. 7.7.2. Theorem. (a) Given any automaton A and (nonempty) subset QA of its internal states, there is an automaton B (whose internal states are a subset of the internal states of A) and a (nonempty) subset QB of its internal states such that (A, QA)~(B, QB) and (B, QB) is minimal. (b) If (A, QA)~(B, QB) and (A, QA), (B, QB) are minimal, then A and B are isomorphic. Proof. (a) Let Q be the set of internal states of A which are accessible from (elements of) QA' Call two elements q, q: of Q equivalent if and only if T = T2. This binary relation is indeed an equivalence relation (cf. 5.5) and so partitions Q into equivalence classes. Call this relation R and let R*(q) be the set of all elements qs E Q such that qRq1, i.e., the set of all elements 2 2 co such that TA,q = TAq,. Let c be any function defined over the R-equivalence classes o with the property c(c) c a. The function c "chooses" from each equivalence class exactly one element from that class. We will now "construct" an automaton B to satisfy the theorem. Let the set of all internal states of B be the set of values of c, i.e., the set of all c(R*(q)) where q C Q. Notice that c(R*(q)) is equivalent to q and, for q C B, c(R*(q)) = q and c(R*(q)) and c(R*(q')) are either equal or not equivalent. Let QB be the set of all c(R*(q)) where q C QA. Let (fA, gA), (fB, fB) be the direct transition and output functions of A and B, respectively. Define: fB(iq') = c(R*(fA(i,q ))) and gB(i,q') = gA(iql) where q' is an internal state of B. The desired result will follow from the following lemma. 42

Lemma I. If qI = c(R*(q)), then TAq = TB,q and c(R*(TA,q(S))) = TBqt(S) for all finite sequences S of input states. Proof. Note that TA qt(i) = gA(iqq') = Tg(i) and TB qV(i) = fB(i,q) = c(R*(fA(iq'))) = c(R*(T4,q?(i))) = c(R*(TA,(i))). Inductively assuming that the lemma holds for a finite sequence S, it is required to show that it holds for Si, Recall that TX,q(S) is equivalent to c(R*(T~ q(S))), so that TB q g(iT(Si) =) g= gB(i,c(R*(Tq(S)))) gA(i,T,q(S)) TA,q(Si) and TB, qt(Si) = fB(iTB,q q(S)) = c(R*(fA iTBq(S)))) = c(R*(fA(iic(*(TI q(S)))))) = c(R*(fA(i,TA q(S)))) = c(R*(T",q(Si))), and the lemma is proved, Thus, given any q c QA, there exists a' c QB, namely, q' = c(R*(q)), such that T = TB q Given any qt E QB there exists q C QA, namely q = q' c(R*(qt'l, sucA that T = TB q so that (A, QA)~(B,QB). Furthermore, (B,QB) is minimal because: (15 Suppose q" is any internal state of B. There is an internal state q c QA such that q" is accessible (in A) from q since q" e Q. Let q = c(R*(q)). Then q' c QBo By the lemma, c(R*(TA q(S))) = TB q,(S). Now S may be chosen in such a way that T iq(S) = q". Since c(R*(q")) = q", it follows that zTB,(S) = q" so that q" is accessible from an element of Q (2) Let T B=q i Q Le q,qt be any two internal states of B. Then q,q' e Q and TA q TA But q = c(R*(q)), qI = c(R*(q')) so that, applying the lemma T2 / T' B;q Bq' We shall need the following lemma. Lemma 2. For any automaton A and internal state q of that automaton, if TA (So0 q0o then, for all S, T q(SS = T' () and T = Proof. If S is i, a sequence of input states of length one, the result follows from 7.l Now suppose the result holds for S', S is S'i, and Tq (SoSt) = qK. By inductive assumption qt = TXqA(SoSI) = T qSo (5) and T2 (A S) = T2 (Si). By 7.1, f(i,q') T q(SoSi) = Tiqo(S'i) and A,q A, q Aq g(i qt) = Taq(So0Si) Tqo O(S'i) and the lemma is proved. Proof of (b)o Since (A,QA)~(B,QB), for q c QA there exists q1 c QB such that TA q = TB. Because of the minimal character (second defining property) of (B QB) if TA = Tq q also, then q = q". Similarly, for each q' c QB, there is exactly one q E QA such that Ti,q = TB,qt Thus, there is a 1-1 function d from QA onto QB such that Ta = Td(q) for all q E QA We not extend the domain of d to all the internal states of A and its range to all the internal states of QBO Let q be any internal state of A. Then, because of the minimal character (first defining property) of (A,QA), there exists S', q' such that TA, q(ST) = q. We would like to define d(q) = T, d(q, )(S' ). In order for this requirement to well-define d(q), it must be shown that: if T~ q(S") = q also, then T~,d(q,)(S") = Tg d(q,)(Sv). Observe that TA,q(SS) =,d(qt)(S'S) 43

for all finite sequences of S of input states. By lemma 2 T,q(S) = Tqf(S'S) and TBq*(S) = TB d(q)(S'S) where q* = T d(qf)(S'), so that T = T2 ta Similarly, if q** = T d ("(S") then T2 T2 HenceT2 - T2 so that ~B d1q) A q Bq** Bq* B,q q* = q** by the minimal nature of B. Therefore, d(q) = T d(qt)(S?) well-defines d(q). If d(q) = d(q') then T2 = T d(q) = T d(ql) = TA and so, because A is A,,~ Bd d(q) Bjd1 -, 1q' minimal, q = q1. Thus the domain of a has been extended to the set of all internal states of A and it has been shown that d is 1-1. If q* is any internal state of B, then for some S and d(q') c QB' q* = T d()(S'). Let q = T _qt(S'). Then d(q) = T,d(q,)(S') and by what has been shown above,Tiq = TB,d(q). But, because of the symmetric roles of A,B, Tq = Tq* and so d(q) = q*. Thus the range of d is the set of all internal states of B. Corollary. If (A,QA)-(B,QB) and (B,QB) is minimal, then A has at least as many internal states as B (which indicates why the word "minimal" is used). Proof~ By (a) of the theorem, there is an automaton A' and a subset of its internal states QA' such that (AQA)~(A',QA ) and (A,QA ) is minimal. Furthermore, the internal states of A' are a subset of those of A. Moreover, since (A',QA )-(B,QB), by (b) of the theorem, the number of internal states of A' and B are the same. 7.7~3~ Exercises. o. Show that if q is an isomorphism between automata A and B and if QA is any subset of the internal states of A and QB is the set of 0(q) where q E QAA then (A,QA)~(B,QB). 2. Let K be the class of all automata which have the same set of two input states, two internal states, and two output states. (a) How many elements are there in K? (b) How many (A,QA) are there where A c K, (A,QA) is minimal, and (1) QA contains exactly one element, (2) QA contains two elements? (c) The relation of isomorphism between automata in K is an equivalence relation. How many equivalence classes are there? (d) Call two automata A = (I,V,Q,f g) and B = (I'gVt,,fgc ) isomorphic in the wider sense if and only if there exists 1-1 functions 0, 02 from I, V,Q, respectively, onto I2, V', Q', respectively, such that f'(0l(i), 03(f(i,q)) and g'(01(i), $3(q)) = 02(g(i,q)) for all i c I and q c Q. The relation of isomorphism in the wider sense is an equivalence relation on the elements of Ko How many equivalence classes are there? Show that, if A,B are isomorphic, then they are isomorphic in the wider sense. 7~7~4~ Define a family of equivalence relations over the set of all internal states of a given automaton as follows. For each positive integer k, q Rk q' if and only if Tq(Sk) = TqT (Sk) where Sk varies through all finite sequences of input states of length k or less. Notice that, if q Rk+l qi, then q Rkq' Let q R qt if and only if T2(S) = T, (S) for all sequences S of input states (of any length)~ If q R q', then q Rk q' for every ko, o~~~~~~4

We now define a family Rk of equivalence relations over the same set of internal states of the given automaton. Let Rj = R,. Assuming Rk has been defined, define R+i- as follows: q RkB+ q' if and only if (1) q RB q' and (2) for all input states i, f(iq) Rk f(i,q ) where f is the direct transition function of the given automaton. Lemma 1. For all n, Rn = RB. Proof. By definition R1 = RB. Assume Rk = Rk, k > 1. To prove Rk+l = Rk+li q Rk+l q' if and only if f(iq) Rk f(i,q') for all i if and only if f(i,q) Rk f(i,q') for all i if and only if Ta(i )(Sk) = for all i and if and only if for all i if and only if T, Sk [uifnd f if Tq(iSk) = T f(iSk) for all 1, ok [using f iq) = Tq(i) and 7.7.2 lemma 2] if and onrly if q Rk+l qt' Remark. By virtue of lemma 1 and the definition of Rk, it follows: q, q' are in the same Rk+l-equivalence class if and only if they are in the same Rkequivalence class and f(i,q) = f(i,q') for all i, where i is the direct transition function. Lemma 2. In any automaton, if q R1 q R1 q' for all q, qt, then q R q' for all q, qg Proof. By hypothesis Tq(i) = T2q(i) for all i. Assume T2(S) = T2,(S) where S is any sequence of input states,and let q T= (S) q't - Tt (S Then applying 7.7.2 lemma 2 T2(Si) = ~i(i) and T2,(Si) = T2tt(i). iy hypothesis TT(i) = Tqtvt(i) so that Tq(Si) = Tq (Si) and the conclusion follows. Lemma 3, For every positive integer k, R = Rk if and only if Rk+l = Rk. Proof. If R = Rk, it is obvious that Rk+l = Rk. If R f Rk, then there exist q, qt such that q Rk qt but not q R qt' Let S be a sequence of minimum length, say m, such that T2(S) / Ta (S), Then m > k. Assume m > k+l, for if m = k+l the result is immediate. Let S = LmklMk+l, where the subscripts indicate the length of the sequence. Then using 7.7~2 lemma 2, T2,,(Mk+l) / Tq (Mk+l) so that q" k+l qt'. On the other hand, let U be any sequence of input states of length k or less. Then T(Lmk_ U) = T, (Lmq.kiU) because Lm k'lU has length less than m. Again applying 7.7.2 lemma 2, T%1,(U) = Tt,, (U) q q so that q" Rk qsV o Lemma 4. If Rk / R, then there are at least k+l Rk-equivalence classes. Proof. Suppose k = 1 and R1 f R. If there is exactly one Rl-equivalence class, ie,, q R1 q' for all q, qI, then by lemma 2, R1 = R. contradicting the hypothesis~ Now assume inductively Rm / R implies there are at least m+l equivalence classes. Suppose, now, that Rm+1l R. Then Rm f R and by the inductive assumption there are at least m+l Rm-equivalence classes. But Bm+1 f Rm because by lemma 3, if equality held, then Rm = R. Hence there are more Rm+l1-equivalence classes than Rm-equivalenceo Thus, there are at least m+2 RmBl-equivaience classes. q.e.d.

Theorem. Given an automaton with n > 1 internal states. Then for some k, k < n-l, Rk = Ro In particular, Rnl = R. Proof. Applying lemma 4, there exists j such that Rj = R. Let k be the minimum of all such j's. If k = 1, the result is immediate. Suppose k > 1. Then Rkl f R and there are at least k Rk_l-equivalence classes (lemma 4). If k > n-l, i,e,, k-l > n-l, then there are at least n RkBl-equivalence classes. But there are all together only n internal states and the R-equivalence classes are obtained by partitioning each RkBl-equivalence class into one or more classes. Hence R = Rkl,' which contradicts the choice of k. The assumption that k > n-l has led to a contradiction. Therefore, k < n-1. Corollary. Given an automaton with n internal states, Suppose for some q,q' that T2 T2,7 Then for some sequence S of input states of length at most n-l T2(S) T2 S). Proof. Since T,2 T2t, q f q' and n > 1 so that the theorem applies. q q 7.7.5. Let q, q1 be distinct internal states of an automaton. To determine whether T2 = T2t "directly" would require checking for each finite sequence S of input states whether Tq2S) = Tq (S). Since there are an infinite number of such sequences, this checking cannot be carried outo The theorem 7.7.4, however, provides a finite checking procedure, ioe., an algorithm, for determining whether T2 = T2qt Exercise. Provide an algorithm for determining whether q' is accessible from q, for any internal states q, q' of an automaton. [Cfo 6.7 (1)o] 7.7.6. If A = (I,V,Q,f,g) and A' = (I,V,Q',fIg ) are two automata, their direct sum B = A + A? is the automaton (I,V,QB,fB,gB) where QB is the union of Q x [0] and Q? x (13, fB(i,(q,O)) = f(i,q), fB(i, (q',l)) = f'(i,q'), g(i,(q,0))= g(i,q), gB(i, (q 1,)) = g(i,q'), and i c I, q c Q, q' E Q' [Recall that if M, N are sets, then M x N is the set of ordered pairs m, n where m c M, n c N and (03 is the set whose only element is 0. If we considered only those automata A,At such that Q rnQ = A, then the internal states of the direct sum automaton could be taken simply as Q kUQ. Notice that even if Q nQ' f ~, it is nevertheless the case that Q x o3 nQ' x (13 = 0.] To obtain the direct transition-output diagram for B from the diagrams for A, A one merely changes the label q in the diagram for A to (q,O) and the label q1 in the diagram for B to (q,l) and the two diagrams taken together constitute the diagram for B. The following lemma is obvious. Lemma. (a) TA q = TB (q,O) and TA t = TB (q' 1)' Moreover, (b) (Tkq(S) 01 = Ti(qo)(S) and (TAi q(S, 1 = T,(q1l)(S) for any sequence S of input states. 46

Theorem. If A,A' are automata with n, n' internal states, respectively, if q, q' are, respectively, internal states of A, A'. and if T,q Ti, q,' then for some finite sequence S of length n+n?-l or less, T,(S) Tt q(S) Proof. Immediate from lemma (a) immediately above and theorem 7.7~4. Corollary. If A, A' are automata with n, n' internal states, respectively, and QA2 QuA are subsets, respectively, of the internal states of A, A', then whether or not (A,QAA)(A!,QAt) can be effectively determined. More explicitly, whether or not (A, QA)~(A, QA_ ) can be determined by examining TR,q(S), Tt,q (S) for all q C QA, qt c QAt and for all sequences S of length at most n + n'-i and applying the theorem, 7.7o7. Exercises. (1) Given automata A,Bo Let P = p(qq') be a binary relation such that, ql P q2 if and only if (1) there exists S such that Tijq(S) = ql and Thq,(S) = q2 or (2) q = q, and qt = q2. Prove: (a) If TA,q = TBq, then q1 P q2 implies T,ql = TB,q2. (b) If ql B q2 implies T ql (i) = T,q2(i) for all input states i, then T22q 2 Tangq = TBaqua (c) From (a), (b) it follows: TA,q = TB,q' if and only if for all ql, q2, q1 5 q2 implies gA(iql) = gB(i,q2) for all i. (d) It is possible to decide effectively whether ql 5 q2 or not. (2) Apply theorems 7.7.4 and 7.7.2 to the following problem. Given the logical net indicated below with two delay elements. x Y a(O) = O, b(O) = 0 a(t+l) = x(t)[a(t) b(t) v a(t) E(t)] b(t+l) = 7(t) a(t) U(t) y(t) = a(t) (t) V x(t)[a(t) b(t)V lo | |a(t) b(t)] a, Find another (equivalent) net (of the form) x Y with one delay element with the property: for any sequence x(O), x(l),.., x(t) of (input states) of "wire" x in both nets, the determined (output) state y(t) is the saie for'csth nets ~o ca nets.~4

708 Strongly connected automata>48 7.8.1. Given any automaton A. Define TAIq(ili2. in) to be the sequence of output states TA q(il ), TA q(ilis), o, TA q(ili2o -in) o As usual the subscript A will sometimes be dropped in discussions concerning only one automaton. Lemma. For any automaton, Tq= tr if ahd only if T2 = Tqto Further: q Rk q' if and only if Tq(S) = Tqt(S) for all sequences S of length k. Making use of 7a7,2 lemma 2, the proof follows readily. 7.8.25 An automaton is strongly connected if and only if for every ordered pair (q,q') of internal states of the automaton, q' is accessible from q. Note that, given an automaton, one can effectively determine whether it is strongly connected or not [cf. 7,7-5], Theorem~ Let A be a strongly connected automaton. Let B be any automaton. Suppose that for each internal state q of A and for each finite sequence S of input states there exists an internal state qT of B such that TA,q(S) = TB,q (S). Then for each internal state q of A, there exists an internal state q" of B such that for all finite sequences S of input states TAq(S) = TB, qt(S). Proof. Define eq(S) as the set of q" = TB,q (S) where q' is an internal state of B satisfying TA q(S) = TB,q (S). Let ceq(S) be the number of elements in eq(S)o Notice that ceq(S) is at most equal to the number of states q' such that TA q(S) = TB qt(S). Hence, for any sequences S, S', ce (SS') < ceq(S) because if TAq(SST = TB,q (SS'), then also TA,q(S) = TB,ql(S Indeed, the following holds: Lemmao eq(S'S) is the set of q" = TBq, (S) where q' c eq(S' ) satisfies TA,(S) = TBq =(S), where q = T1 (Sw)o Aq Let SL be an arbitrary finite sequence of input states. Suppose there is some S such that ceq(SIS) < ceq(S1)> Pick one and call it S2o Suppose there is some S such that ceq(S1S2S) < ceq(SlS2). Then pick one and call it S3.-~~ This processcannot go on indefinitely since ceq(S) is a non-negative integer for all So Thus, there is a k such that for all S, ceq(SlS200Sk) = ceq(S1S2oo.SkS)o Let S~ O SS2o. oSko Then ceq(S~) = ceq(S~S) for all S. Let the set of internal states of A be (ql,q2, ooo qno}. Since A is strongly connected, there exists a sequence, say S1, of input states, possibly of length zero, such that ql is accessible from TX,q(S~). Then T, q(S~Sl) = ql. In general, there are sequences. SJ (some of which may have length zero), j = 1,2,.o.,n, such that TIq(S~S'S2oSj) = qj5 Moreover, ceq(SS5S22ooSJS) > 0, for each j~ since it follows from the hypothesis that for any S, ceq(S) > 0. 48

Let q1 C eq(SOS1.Sj), We shall show TA q = TBq by supposing the contrary and deriving a contradiction. Suppose taeg for some S, TA q.(S) f TB qI(S) Then ceq(SOSi..SJS) < ceq(SO) since not all q1 c e (501O.SJ) satisfies (cf. the the lemma) TA q(S) =TB q(S) and ceq(SO)> ceq(SOSKo.Sj) ceq(S0S'.SJS), and this contradicts the choice of So. 7.8.3o Lemma. In a reduced automaton k < n implies there are at least k+l Rk-equivalence classes. Proof. It follows from the hypothesis that there are exactly n R-equivalence classes. If Rk = RB then there are at least k+l Rk-equivalence classes since k+l < no If Rk f R, then the conclusion follows from 7.7o4 lemma 4. 7a.84. Theorem. Given a reduced automaton with n internal states, Let eq(S)'be the set of q'" = T~(S) where qj is such that T (S) = Tq (S). Then for every q, there exists S of length n(n-1)/2 such that eq(S) has exactly one element. Proof, Let ceq(S) be the number of elements in eq(S). Let i(S) be the length of So It is to be proved that, for each q, there exists S such that ~(S) = n(n-1)/2 and ceq(S) = I, The theorem is obvious in case n = 1. Assume, therefore, n> 1. Claim. If (S) < k(k+l)/2, 1 < k < n-2 and ceq(S) = n-k, then for some kl > k there exists SE, an extension of S, such that ~(S') < k'(k'+l)/2 and ceq(S') = n-k' To justify the claim, note that there are at least k+2 Rk+l-equivalence classes (7~8.3). Not all n-k members of eq(S) can be in the same Rk+1-equivalence class, for if this were so then the automaton would have at least (n-k)+(k+l) internal states (since each equivalence class is nonempty). It follows that there exist qn, q2 such that q1 e eq(S), q2 cq(S) and ql $hk+l q2. For some Sk+l, (Sk+l) = k+l and Tq (Sk+l) TqI(Sk+l). If = Tj(S), then q c eq(S) and either Tq(Sk+l) i Tql(Sk+l) or Tq(Sk+l) i Tq2(Sk+1) Hence, by lemma 7.8.2 (applied in the case A = B), ceq(SSk+1l) < ceq(S). Let S' = SSk+l and choose k' such that ceq(S') = n-kKo Then k' > k. Furthermore, ~(St) < k(k+l)/2 + k+l = (k+l)(k+2)/2 < k'(k'+l)/2 and the claim is justified. Since the automaton is reduced, there are at least 2 R1-equivalence classes. Suppose n = 2 ant Tq(i) t Tq (i)o Then n(n-1)/2 = 1, eq(i) = (T1(i)) so that ceq(i) = 1 and the theorem is verified in this case. Suppose, now, n > 2. For some S, q', e(S) = 1, Tq(S) Tkq(S). Therefore, ceq(S) < n-lo Let k be such that ceq(S) = n-k. Then 1 < n-k < n-l so that 1 < k < n-lo If k = n-l, then ceq(S) = 1 and the conclusion of the theorem is satisfied. If 1 < k < n-l, i.e., 1 < k < n-2, then the hypothesis of the claim is satisfied, Hence there is a k' > k and an extension S' of S such that ~(S') < k'(k9+l)/2 and ceq(S') = n-kl. Now kT f n because Tq(S') E eq(S'). Therefore either kT = n-l, in which case the conclusion of the theorem is satisfied, or else k' < n2, in which case the hypothesis of the claim is satisfied and the procedure is iterated, thereby obtaining a k" > kT > k and a S" such that 49

~(S") < k"(k"+l)/2, Thus, for some n, k(n) = n-l, ~(S(n)) < (n-l)n/2 and ceq(S(f)) = 1o If S(n) is extended in an arbitrary manner to a sequence of length (n-l)n/2, then this latter sequence satisfies the conclusion of the theorem. qo.e.d Exercise. (1) Construct a reduced automaton A with I = (0,11 = V such that, for some q, T,q(S) = 1 for those and only those sequences S which do not consist solely of Os.o For each q, answer the question: Is A, [q)) minimal? Is there an automaton with exactly one internal state (and the same input, output states as A) which "behaves" in the same way? Construct an automaton B with (0,11 as its set of input and output states and such that, for some q, T,q(S) = 1 for those and only those sequences S which consist solely of l's. (2) Find a sequence S such that for all internal states q of A [exercise (1)] ceq(S) = 1. (3) The theorem fails if the automaton is not reduced. Indeed, one can find an automaton such that, for all q,S, ceq(S) > 1. Construct such an automaton. 7.8.'5 The following is an alternative, more perspicuous, formulation of 7.8.4. Te-remr. Given a reduced automaton with n internal states. Then /~_ / [ 1T (S) / l(S) Tq'(S) / Tq(S)]^Q(S) = n(n-1) (i.e., for all q, there exists S such that for all q'.,.)o Proof. It will be shown that ceq(S) = 1 if and only if 4 [Tq (S) = Tq(S) _= (S)= TI) q Tqm Tq(S)] (1) Suppose ceq(S) = 1 and Tq(S) = Tq(S). Then Tbl(S) c eq(S). Since T1(S) c eq(S) and ceq(S) = 1, it follows that Tq (S) = TI(S). q (2) Suppose q [Tl~ (S) = T(S= Tq(S) and suppose q" E eq(S)o Then for some ql, Tq(S( = q' and Tq (S) = Tq(S)o It follows that q" = Tqi (S) = Tq(S) so that eq(S) has exactly one element, viz. T(S),o The theorem is now immediate from 7.8.4. 7.8.6. The use of quantifiers permits a more perspicuous formulation of theorem 7.8.2: Let A be a strongly connected automaton and B any automaton. Then if t fo lows) Ttq (S)]

/\// / [TAq(S) TB q(S)] q qr S 7y.8o7 Corollary. Given a reduced automaton such that AQ$/\ [q q' —q ) Tq(S) Tq (S)] then [(q f q1 - Tq (S) f Tq(S))A 2(S) = n(n-l)/2 ] Proof. Immediate from 7.8o5. 7.8.8. Corollary. If the direct sum of two automaton A and A' is reduced, then >V4 > [TA,q(S) f TA, q(S)^ ~(S) = n(n-1)/2] where q,q' are internal states of A, A', respectively, and n is the number of internal states of A + A'. Proof, [Cf. 7.7.61] TtqO)(S) f T1q, l)(S) and the result follows from 7.o85. 7.8.9. Theorem. In a reduced automaton: \A, qA [Tq(S) ~ Tl (S) T (S) / Tq(S)] ~(S) = n(n-1)] I q' qqt'S^ = 2 where n is the number of internal states of the automaton. (Cf. Reference 33 for an S of shorter length than is given here. Note that in both References 33 and 48 the output state of a machine is a function only of the internal.state. The notion of automaton adopted here has the output state a function of both input and internal states. One must be on guard in interpreting results established by different authors because of differences in basic concepts.) Proof. Let qj, q2o,..qn be the set of all internal states of the automaton. Let ql = ql and let S1 be such that 1'(SI) (3)T n(n-1),/\ [T(S1) / Tl1(SI) =Tq(SI) / Tqa(Sl)] and =(S) = 2 Suppose 1 < j < n-l and qj and Sj have been chosen such that A [Tq(Sj) Tq(Sj)- -, Tq(Sj) Tq(S j)] and (Sj) = n(n-1)

Then let %q+l Tqj(SlS2o.S ) and choose Sj+1 such that n(n-l) A ETj(Sj+1) ~ Tq (Sj+) = Tq(Sj+l) ~ TqO+1(Sj+l)] and Q(Sj+l) 2 q Let S = SiS2o'Sn=1' It is claimed that this S satisfies the requirements of the theorem. Let 1 < j < k < n and suppose Tq.(S) 1 Tn (S). Then Tn.(S S2).o.S) Tqk (S1S2 ) If j = 1, then Tqk(Sl) 4 ~q (Sl) so that Tqk(S) T (S). Now suppose that j > lo Then Tqj(S1S2..oSj) = T q(Sj) and T (S,, = T(Sj) where q = Tqk(S1S2.. Sjl) so that Tq(Sj) o Tq (Sj)o Hence Tq.(~j) j Tq(Sj)o Note that Tqj(SIS2o oSj) = Tq (S1S2.o Sj-l)Tq3 (Sj)0and Tqk(SlS2o oj) = Tqk(S1S2. o Sj-l)Tq(Sj) so that Tqj(S1S2...Sj) / Tqk(SLS2.o oSj) It follows that Tqj(S) i Tqk(S) q.e.d. 7.8.10. The direct sum of two automata has been defined (7.7~6). In an analogous way one can define the direct sum A = A1 + A2 +... + An of automata, A1 = (I, V, Q1, f1, gl), A2 = (I, V, Q2, f2, g2), oo, An = (I, V, Qn, fn, gn)o The direct sum automaton A = (I, V, Q, f,g) has as its set of internal states Q =Jj=l(Qj x j) and f(i, (q,j)) =(fj(i,q), j), g(i, (q,j)) = gj(i,q) where i c I, q ~ Qjo It is easy to see that A1 + A2 +..o An is isomorphic to.ooo((A1 + A2) + A3) +..o + An]. Indeed, A is isomorphic to the direct sum of the automaton Al, A2,..., An taken in any order and any groupings. For example, A1 + A2 + A3 + A4, (A3 + A1 + A4) + A2, (A2 + A3) + (A4 + A1) are all isomorphic. Lemma. If Aj, 1 < j < n, are strongly connected reduced automata nonisomorphic in pairs, then their direct sum is reduced. Proof, Note that (Aj, Qj) is minimal, where Qj is any nonempty subset of the internal states of Ajo It follows from 7o7.2 (b) that Aj, Ak, j j k, are isomorphic if and only if V t [TAj q- TAk ql]e (Indeed if Aj, Ak are isomorphic,? [TAj = TAk q,1] Since Aj, Ak are not isomorphic, A q [TAjq TAkyql It follows jhat the direct sum of the Aj s is reduced. 7.8.11. We now note some corollaries of 7.8~9. (a) Given a reduced automaton such that A A /\ [q q -- Tq(S) / Tq,(S)], q q' S VA (q f TgS) i Tq(S)) I(S) = n Sqg qC 2 J

(b) If the direct sum A of A1, A2,..., Ar is (1) reduced or (2) Aj, 1 < j < r, is strongly connected and redu6ed and nonisomorphic in pairs, then VA A [(j k A TAj q (S) A TAk,q(S))/r\(S) = n(n-1)2/2] S q q' where q', q are internal states of Aj, Ak, respectively, and n is the number of internal states of A. Proof. If j ~ k, then TjA (q' j)(S) A Tl,(q k)(S) for any S and any q', q internal states of Aj, Ak, respectively. If A is reduced, the result follows from 7.8.9. If (2) holds, the result follows from the lemma and what has just been proved. q.e.d. 7.8.12. Theorem. Given any function h from finite sequences of elements of I of length at most n, which has values which are elements of a set V. Then there is an automaton with input states I and output states V such that for all sequences S of input states of length at most n Tq(S) = h(S) for some internal state q of the automaton. We illustrate a general method for constructing such an automaton, in the case n = 3, I = [0,11 = V and h as indicated below. h: 0 0 1 1 00 1 01 0 10 1 11 0 000 1 001 0 010 0 011 1 100 1 101 0 110 0 111 1 The desired automaton is indicated by the diagram below (a modification of a transition-output diagram) where the heavy dots represent internal states. The leftmost dot plays the role of the q of the theorem, It is obvious that the indicated automaton satisfies the requirements of the theorem.

0-1 0-1/ 1-0 1-0o 1 0-0 0-0 s / 1-1 0-I 1-0 0-0 1-1 7.o813a Exercises. (1) Knowing that the table in 7o812 was obtained from an automaton with two internal states, find the automaton (but do not enumerate all the two internal state automata')0o Cfo 7o704, corollary. (2) Call the 7 internal state automaton indicated in 7.8o12, A. Construct the minimal automaton B such that TBq, = TA q for some q' of Bo Modify A by altering the transitions from the "rightmost" four internal states in such a way that the minimal "B" has two internal states. (3) In the automata indicated below, determine whether 78.1ll (b) (2) holds, and if so, find an S satisfying the conclusion of 7o8oll (b)0 1-1 0-0 A:.- q 02 1-0 0-1 A2 j 20-1.1-0.

7.9. An application of group theory. We digress to introduce some further concepts and establish some elementary mathematical results, An application is then made to automata theory. 7.9.1. The notion of "finite set" has, up to now, been presumed understood. It will be worthwhile at this point to give a precise characterization of "finite." A set M is finite if and only if every 1-1 function which takes M into itself takes M onto itself, i.e., for every function f from M into M, [ (X y ==- f(x) f f(y)) / =M /f\ (v = f(u))] A set of M is infinite if it is not finite, i.e., a set is infinite if and only if there exists a function f from M into M (such that) xyM(X y f(x) f (y)) VM u (v f(u)).YYCM vcM uEM In the case of the non-negative integers, for example, f may be chosen so that f(x) = x + 1. Alternatively, f may be chosen so that f(x) = 2x. If M is finite and m is the number of elements in M, then there are mm functions from M into M, of which mi are 1-1 functions (and, therefore, onto). A permutation of a set M is a 1-1 function from M onto M. If M has exactly m elements, then there are mt permutations of M. Exercise. If f is a function from a finite set onto itself, then f is a permutation. Give a counter-example in the case of an infinite set. 7,9.2. The set of all functions from a set A into a set B will be denoted by BA. If f,g C MM [f,g are also called unary (singulary) operations on M], then by f o g is meant a function from M into M such that f o g(x) = f(g(X))o The binary operation "o" is called "composition" and f o g is the result of composing f and g (in that order). In general, f o g t g o f. Composition is, however, associative: (fog)oh(x) = fog(h(x)) = f(g(h(x))) = f(goh(x)) = fo(goh)(x). Often "fg" will be written instead of "fog." There is a unique element, call it I, [more explicitly, I = I(M)], satisfying I E MM and I(x) = x for all x c M. For all f c MM, fI = f = If.

Theorem. If M is finite, f,g E MM, and fg = I, then f and g are permutations and gf = I. Proof. By hypothesis fg(x) = x for all x c M. Suppose g(x) = g(y)o Then x = fg(x) = fg(y) = y, so that g is 1-1. Since M is finite, g is onto, i.e., g is a permutation. For every x c M, there exists y c M such that f(y) = x, namely, y = g(x)o By the exercise above, f is a permutation. For every y c M, if f(y) = x, then y = g(x), since f(g(x)) = x and f is 1-1, It follows that gf(y) = g(x) = y for all y c M, that is, gf = I. Exercise. If the requirement "M is infinite" is deleted from the theorem above, show the resulting statement becomes false. The following statement holds, however: If f,g e MM and fg = I = gf, then f and g are permutations. 7.9.3o The ordered triple (M, ~, 1) is called a semi-group (with identity) if and only if (1) x-y c M, for all x,y c M, (2) (xoy).z = xo(yoz), for all x,y,z c M, (3) 1 E M and lox = x = xol, for all x c M. If (Av ^ ) is a lattice with 0, 1 (e.g., a finite lattice), then (A, ^, 1) and (A v, 0) are semi-groups. If M is an arbitrary set, then (MM, o, I) is a semigroup. If PM~MM is the set of all permutations of M, then (PM, o, I) is a semigroup. To justify this latter statement, it is necessary only to establish that the composition of two permutation is a permutation, Let fig C PM and x c M. Then f(y) = x and g(z) = y for some y and z. Hence fog(z) = xo Suppose fg(x) = fg(y)o Then g(x) = g(y), since f is 1-1, and x = y since g is 1-1. Thus fg is a permutation. Lemma 1o If (M, o, 1) is a semirgroup, a c M, and, for all x, ax = x, then a = 1. Proof. Since ax = x, in particular, aol = 1. On the other hand, aol = ao Hence a = 1. Lemma 2. If (M, ~, 1) is a semi-group, then the function L taking a c M into La is an isomorphism of (M, o, 1) and (\, o, I) where MM is the set of all La where a e M and La(x) = aox for every x c M. Proof. L o= ao(b-x)= (a b)-x = L (x). Thus L o Lb = L a Lb(x) ='xb(x) a a -b~ If La = Lb, then a = La(l) = Lb(l) = b. Hence L is 1-1. By definition, L is onto, Thus L is an isomorphism. 7.94o. A semi-group (M, -, 1) is a group if and only if xcM yM xy = Suppose xy = 1 = yzo Then z = loz = (xy)z = x(yz) = xl = x Thus, if xy = 1, then yx = 1. Suppose xy = 1 = xy', Then yx = 1 = xy', so that y = y'T Hence, o o, o~~~~5

in a group, for each x, there exists a unique y such that xy = 1. This y satisfies yx = 1 also and is denoted by "x-1." In a group, ax = b has a (unique) solution for x, namely, x = a-lb. It has already been observed that (PM, o, I) is a semi-group. It is also a group because if g is any permutation of M, the requirement fg(x) = x for all x c M defines an element f c PM. If (M,, 1) is a group, then (g, o) I) is a group of permutations (cf. lemma 2, 79.-3) and La-1 -= La - Theorem. If (M, *, 1) is a group, E~ M is finite, and x,y, c E- x'y c E, then (EB,, 1) is a group. Proof. If a c E, then La is a 1-1 mapping of E into E. Since E is finite, La is onto. Hence ax = a has a solution for x in E; it follows 1 c E. Thus, (E,., 1) is a semi-group, Since La is an onto function, ax = 1 has a solution in E and (E, -, 1) is a group. Corollary. If E is a finite set of permutations closed under composition (i.e., f,g c E -if fog c E), then (E, o,I) is a group. Proof. If the elements of E are permutations of S, say, then E is a subset of the set PS of all permutations of S, (Ps, o~ I) is a group and the theorem applies. 7.9.5. Theorem. If (E, o, I) is a group of permutations of S, then the relation p defined as: apb if and only if a b C S and there exists E c E such that <(a) = b is an equivalence relation. Proof. Since I e E, it follows apa for all a c S. If apb, then t(a) = b for some ir E E and a = t-l(b), a-1 C E, so that bpa. Finally, if apb and bpc, then <(a) = b and r'(b) = c for some,dt' c E so that v'v(a) = c and apc. 7.9.6. A semi-group8 (A) is associated with every automaton A = (I, V, Q, f,g) in the following way, With each finite sequence S of input states, define LS C QQ as follows: Ls(Q) = Tj(S). If ~ is the sequence of length 0, then L~ = I c QQ. It is easy to verify that LSS, = LsoLS, Thus, if~ is the set of all LS, (i, o, I) is a semi-group. Notice that J(A) depends only on the direct transition function f (and not on the direct output function). If J(A) is a group, then A is called a permutation automaton. (Cf. Refl 33, p. 277. In Ref. 23, p. 286, def. 5, an equivalent concept "backwards deterministic" is defined.) Lemma. 2S(A) is a group if and only if Li is a permutation for each input state i of A.

Proof. The composition of two permutations is a permutation (7.9.3). The result follows, then, from 7,9.4 corollary. Theorem. Every permutation automaton A is isomorphic to a direct sum of strongly connected permutation automata. Proof. The relation p, defined relative to Y(A), partitions (7-9.5 theorem) Q, the internal states of A, into equivalence classes Qj. Corresponding to each Q. is an automaton Aj = (I, V, Qj, fj, gj) where fj(i,q) = f(i,q) and gj(i,q) = g i,q) for each i c I, q c Qio. The isomorphism may readily be verified. 7-9d7. It has been remarked earlier that some authors use a notion of (finite) automaton in which the output at time t depends only on the internal state at time t. Let us refer to such an automaton as a Moore-machine. Let us suppose a Moore-machine given. Let the machine initially be in state q and suppose an arbitrary sequence of input states il, i2o,.., in given. Then the corresponding sequences of internal states and output states are given by: q, T1(ij), T1(ili2),..0, T(ili2,in) q q q and g(q), gT (i1), gT (i1i2), 0.o, gT (i1i2..in) where g is the direct output function of the automaton. Notice that the latter two sequences are of length n+l while the former is of length n and that the initial output state is independent of the input sequences. It is natural to associate with a Moore-machine and an internal state of the machine the function Tq, from finite sequences S of input states to output states, defined as follows: Tq(S) = gTq(S), where g is the direct output function of the machine. Theorem 1. Suppose an automaton A and one of its internal states ql given. Then there is a Moore-machine M with an internal state ql such that, for all nonnull S, TM (S) = Proof. Let A = (I, V, Q, fA, gA). Let M = (I, V,', fM gM) where Q' (I x Q)v (ql) and fM(i,(i',q)) = (i, fA(iq)), fM(iyql) = (i,ql), gM(i,q) = gA(i,q), gM(ql) may be defined arbitrarily. We list the sequence of internal states for both automata A,M corresponding to an arbitrary sequence of input states: il i2 13 14 in A ql q2 q3 q4 qn qn+l M qg (il q) (i2,q2) (i3,q3) (inl-, qn-1) (inqn) which makes the result rather clear, Proceeding more formally, we claim that TM (Si) = (i, TX (S)) for all input states i and sequences S thereof including 58

the null sequence (which has length 0). For S null, we obtain TMIqi) = fM(i,q-) = (i,qi) = (iTql()) ) Suppose T, (Si) = (i T' (S)) Then M T ql(Siit) = fM(ilTT ql(Si)) = fM(i (i,TA q(S))) = (i,f(iTA,q())) = ( iS)' r A,l Si) )a which establishes the claim. It remains only to recall that TAql(Si) = gA(i,TA1ql(S)) and Tl(Si) = gM(T q(Si)) = g(i,TA,(S))= gA(iTA,q((s)), q.e.d. Theorem 1 states, roughly speaking, that every behavior which is realizable by a finite automaton in our sense is realizable by a Moore-machine provided, of course, "behavior," particularly of the Moore-machine, is properly understood. We now show the converse also holds. More precisely: Theorem 2, Suppose that a Moore-machine M = (I, V, Q. f, gM) with an internal state ql given. Then if A = (I, V, Q, f, gA), where gA(i,q) = gMf(i,q), TMl'(S) = Tql(S) for all non-null S. Proof. 2.,sl(Si)=,1~i,%~~i~(S))= ql TiA q(Si) = gA(i,TXAql(S)) = gMf(i, TAq(S)) = gMTMq1(Si) = TM (Si). q.e.d. The following two diagrams illustrate theorem 1. O-a Automaton AO-c

f, qj 0 (0,q2) 0 b ~1 c! Moore -machine M 7.9.8. Exercises 1. Given an automaton A and an internal state q of that automaton. Define a binary relation aq as follows: S1 Uq S2 if and only if Tq(Sl) = Tq(S2)Assume ea:.:h internal state of A is accessible from q. Show that: aq is an equivalence relation over the finite (including the null) sequences of input stateso There is a 1-1 correspondence between internal states of the automaton and aq-equivalence classes. Treat the equivalence classes as internal states of a new automaton A' with the same input, output states as the given automaton. Define a direct transition and a direct output function for A' in such a way that A, A' are isomorphic. If the assumption concerning accessibility is dropped, what is the relationship between A, A'? 2. Define a binary relation Pq as follows: S1 Pq S2 if and only if Tql T2 where ql = Tq(S1) and q2 = Tq(S2) Treat the q-equivalence classes as internal states of an automaton B and define a direct transition function and a direct output function of B (as for Al) in such a way that (A, (q} is equivalent to (B, 7), where q is the Pq-equivalence class containing the null sequence. If these functions are defined in a certain "natural" way, B will be minimal, 60

8. REALIZATION OF EVENTS 2837 8o1. By an I-event is meant a set (possibly infinite) of finite sequences of elements of a finite set I. An automaton (or a logical net) with two output states 02 1 and input states I is said to realize the I-event E (relative to one of its internal states q) if and only if (1) if S ~ E, then T2(S) = 1 and (2) if T2q(S) = 1, then S C Eo The notion of "realization of an event" is another way of expressing behavior of an automaton. Certain I-events are called regular. The significance of regular events is this: every (two-output) automaton realizes a regular event and conversely, every regular event can be realized by a (two-output automaton) (cf. Refs. 7, 16). 8.2. If a, 5 are I-events, then Se (a v 5) if and only if Secx or Set Se(cz ~ 5) if and only if for some Sl_ S2, S1Ca, S2e5 and S = S1S2 Se a* if and only if for some n > 1, S> S~,.o o Sn, Siec and S = S1S2.. Sn. The class of regular I-eveints is the smallest class containing the empty set and the unit sets of length one sequences of elements of I, which is closed under v,., * o Regular I-events may be denoted by regular I-expressions; these are well-formed formulas constructed out of symbols denoting the empty set, the unit sets of length one sequences of elements of'I and v., *. (Different regular expressions may denote the same event.) For example, letting I = (0,1) and letting "O." "1" denote, respectively, the unit sets ([O, [1), then (O v 1)* is the set of all [0,1) - sequences; (O - 1) is the set of all [0,1) - sequences, beginning with 0, terminating with 1 and alternating between 0,1; (0.1 v 0.0o.) is the set consisting of the two sequences, 01, 000; l.(Ovl)* is the set of all sequences of length two or more which begin with a 1; (0*l-.O*vl.O*vO*.lvl) is the set of all sequences containing exactly one 1. If a is an I-event, then let [a] be the I x [0,1) event defined as follows: ili2. oin e[a] if and only if for some k, Pk = 1 and ikik+l... in C; PlP2 ~ ~Pn

here we have written "pj" for the ordered pair (ij, pj) where i cI and j.e(O,l]. Theorem. There is a logical net (and hence an automaton) realizing [a] for every regular I-event CZ. Proof. The proof is by induction on the number of operation symbols occurring in a regular expression A. (a) If A is i, denoting ca = [i), then a net realizing [a] is c The set I is the set of all input states which "cable" a may assume, while the "wires" b, c are capable of assuming the states 0, 1. The switch indicated is such that for all t, c(t) = 1 if and only if a(t) = i Ab(t) = 1. Hence this net realizes [Ca]o Let the expression A, Al, A2 denote the events a, al, 0c. Suppose the following nets realize [c1l], [c], respectively, c c ] L1 i _ C0 and 4\ [cj(t) = 1 => Vt [t' < t bj(t') = lAaj(t')aj(t'+l)...j(t) (b) Let A = (A1VA2); then the net al =a=a2 c b1 =b=b2 by~~~~~~~6

realizes [x1 C'] because c(t) = 1 <= —> cl(t) = 1Vc2(t) = 1 so that [c(t) =1 < —> V [t < tAb (t) 1Aa hj(t)aj(t+l)... aj(t) c aj] and since K [al(t) =a(t a2(t)Abl(t) = b(t) = b2(t), it follows4\ [c(t) = 1 > t < tAb(t') = lAa(t')a(t'+l) a(t) e ] (c) Let A = (A1, A2), Then the net al=a a2=a [ll C delay Lce2II bl=b b2 realizes [a] = [ca~-],. We proceed to justify this assertion, Suppose V tt < tAb(t) A= a(tl)a(t+l).. a(t) c];c tv then there exists t", tB < t" < t" such that a(tt).o. a(t"). a(t) = a(tt)a(t'+l)... a(t) a(t$)..o a(t") e a, and a(t"+l)... a(t) c 2~ Hence al(t')... al(t") E al and bl(t') = 1 so that cl(tt") = 1. It follows that b2(tt"+l) and a2(t"+l)... a2(t) c a2 so that c(t) = 1.

Suppose now c(t) = 10 Then for some tt, t' < t, b2(tW) = 1 and a2(tt'),.. a2(t) E ac. Since b2(t') = 1, t / O. It follows cl(t-l) = 1. Hence there exists t" < t - 1 such that bl(t") = 1 and al(t")... a1(t'-l)e Cl. It follows that b(t") = 1 and a(t")... a(tl-l)a(tv) o.. a(t) c a = aC C k and the assertion has been justified. (d) Let A = Ag. Then the net a1=a lcl] delarealizes [a] = [Ct]. We proceed to justify this assertion. Suppose for some t, < t, b(tt) = 1 and a(tt)... a(t) c a, Then, for some n, t-, t2,..o tn, n > 1, tl = t tl < t2 <. < tn < t, a(tl)Sla(t2)S2a(tn)Sna t) = a(t) a(t) and a(tl)S1 E a, a(t2)S2 c aa(tn)Sna(t) e a. Since b(t1) = 1, we have bl(tl) = 1 and a(t1)Sl e Ua Hence d(t2) = 1 and b(t2) = 1. It follows d(t3) = 1. Similarly, d(tn) = 1 and bi(tn) = 1. Since also a(tn)Sna(t) c a, it follows c(t) = 1. Suppose c(t) = 1. Then for some t <K t, al(t') *.. al(t) c ac and bl(t) = 1i Hence eit'her (); b(t') = 1 and a(t')... a(t) e ac or (2) b(t') ~ 1 and d(t') = 1 so that tt f 0. Assuming the latter alternative holds, it follows c(t' - 1) = 1 so that for some t, < tV, al(tl)... al(t-l) C ac and bl(tl) = 1. Hence either (1) b(t1) = 1 or (2) b(t1) / 1 and d(tl) = 1 so that tl 0 In case (2), it follows c(tl-l) = 1 so that for some t2 < tl, al(t).o.. al(tl-l) c ac and b1(t2) = 1o Since there is no infinite sequence of nonnegative integers t > t' > tl > t2 > 0 o, it follows for some n, the first alternative will holdo For such an n, then, we have b(tn) = 1 and al(tn)..o al(tnl - 1) C ac so that a(tn)..0 a(t) C a. q.eodo If the net b [.al i, M 4

realizes [a], then the net C, delay [' realizes a because b(o) = 1 and b(t+l) = 0 so that (1) if a(o) a(1l).o. a(t) c a, then, since b(o) = 1, c(t) = 1; (2) if c(t) = 1, then for some t' < t, a(t')... a(t) c a and b(t') = 1. Hence t' = 0 and a(o) a(l)... a(t) c a. Corollary. There is an effective procedure for constructing a net which realizes a regular event given by a regular expression. It is to be emphasized that the theorem gives a purely rote procedure for constructing a net (and hence automaton) which manifests any desired automaton behavior. We leave the converse theorem to the bibliographical references. 8.3. We digress in this section to indicate a variant of the point of view adopted, 8.3.1. A brief demonstration is given of the theorem of the previous section in terms of Moore-machines. To motivate the construction, constructions are given first in terms of nets. (a) b ~ - delay N_ The switch is such that c(t+l) = 1 if and only if a(t) = iAb(t) = 1.

Furthermore, c(O) = O. Suppose the following nets given: b= Eal I (Y2] and ci(t+l) = 1 if and only if ai(tO)ai(tO+l).o. ai(t) e ciAbi(to) = 1, and ci(O) = 0o (b) Then the net below with output c realizes [am U 2]. al=a a2=a [di] Ic1 =b2 CI bi=b If b(to) = 1Aa(tO) a(tO+l)... a(t) e c. = a,' c2, then bl(to) = 1 and for some tl, tO < t1 < t, a(to) AO a(tj) A1 a(t) a(t0) a(tO+l)..o a(t)Aal(to)AO e Cl Aa2(tl) A1 a2(t) c a2, so that cl(tl) 1 = b2(tl). Hence c(t+l) = 1. If c(t+l) = 1, then for some tl, t a t, a(t) a2a(t). a2(t) E Ab2(tl) = 1. Since cl(O) = O = b2(0), it follows t1 > O. Thus, for some t0 < tl, al(tO).. al(tl-1) E caAbl(tO) = 0. It follows a(to)... a(tl-l) a(tl)... a(t) c aCA b(tO) = 1. Note, toD, that c(O) = 0. (c) The following net realizes [O] = [ao], i.e,, has the property c(t+l) = 1 if and only if b(to) = lAa(to)... a(t) c cx -=' for some t0 < t. al =a 6

Suppose b(t0) = lAa(t0)... a(t) E a for some to < to Then a(t0)... a(t) = a(t0) Ao a(tl) A1... a(tn) An a(t) for some n,tj and a(t0)A0, a(tl) A1,... a(tn) An a(t) c a1. Since al(t) = a(t) and since bl(t0) = 1, it follows c(tl) = 1 so that bl(tl) =1 also. Similarly, c(t2) 1, bl(t2) = 1,.., and c(tn) = 1, bl(tn) = 1. Since al(tn) An a(t) c al, it follows c(t+l) = 1. Suppose c(t+l) = 1. Then for some tl < t, a(tl)... a(t) c a1 and bl(tl) = 1. Then either (1) b(tl) = 1 or (2) c(tl) = 1. If (1) holds, the argument is completed. If (1) fails to hold but (2) holds, then tl > 0 and for some t2 < tl, a(t2)... a(tl-l) e 1l and bl(t2) = 1. Again one of two alternatives holds and the argument proceeds as before. We now give the "corresponding" constructions for Moore-machines. (a) Suppose a = [i). Let Q[a] = [0,1). Define f[a] (i",a), q = 1 if and only if i' = i and a = 1, g[a] (q) = q. We take q = 0 as initial state. (b) Suppose a = 15 y. Let Q[C] = x Q[]]. Define fia](i, x, q, q') = ([~](i, x, q), f[7](i, g[]i(q), q') [aO](qg qj) g[=] (q ) where i E I. x E [0,1], q e q E Q[] If q[p] is the initial state ior the automaton realizing []1 and similarly for q[7]1 then we take as initial state q[] = (q[,], q[(]). (c) Suppose a = 5*~ Let Q[] = [,]' Define f[a](i, x, q) = f[,] (i, g[,](q)Vx, q), g[p](q) = g[](q). The initial state of the machine "for [a]" is taken as the intial state of the machine for [n]. (d) Suppose a = yV7. Let Q[a] = [ x] x Q[ ]' fia](i x, q, al) = f[,](i, x, q), f[7](i, x, q') gin](q,' = g[=](q) g[y]('q).

This initial state is chosen as in (b). (e) Given a machine "for [cY]," we now construct one for a. Let Qa = Q[] x [0,1). Define fc(i, q, x) = M[c](i, x, q), o), g0(q, 1) = 0, ga(q, 0) = g[jl](q). The initial state q, is chosen to be (q[a], 1). 8.532. Let a (A,I)-event be any set of I-sequences, possibly including the null sequence A. The class of ( A,I)-regular events is the smallest class of (A,I)-events containing O., (A), (i) for each i c I and closed under V, 9, t where S at if and only if S = A or, for some n, S C an. Then, since a at = * (= ct CUa), it follows if an I-event is regular, it is (A,I)-regular. If Oc,: are sets, a-5 = cznf5 is a set of elements in a but not in 5. If a is a (A,I)-event, let aO = a - A). We wish to show the class of (A,I)-regular events consists of exactly those (A,I)-events U0 is I-regularo If a is Iregular, cV A) is (A,I)-regular. We now show if ac is (A,I)-regular, then o0 is I-regular. This follows from the following equalities: (avp)O =acOv PO (U.)O = c.O 0V(c 0)0o VO.(5-BO) [note ac. = 0 =.ca] (at)o = (Uo)* The (A,I) event realized by a (two-output) Moore-machine is the I-event realized by the machine augmented by Aif and only if the machine has output 1 at initial time. It follows from the underlined statement above and 8.3.1 that every (A,I) event is realizable by a Moore-machine. It follows, too, that every (A,I)-event realized by a Moore-machine is (A,I)-regular 8.4. An example. We illustrate the theorem of 8.2. Let the given (0,1l - regular set be (u.uVv)* where "u" denotes (0) and "v" denotes (1). The diagrams below indicate the application of the algorithm. 1. 6U]

de lay 3. CCE 4e - >~ b*9~ -_~ v (o~b)b* x(c Vb) c _) I The behavior of the output b* of this net may be described as follows: (1) a* - x(cVb), b* = aVx(cVb) [Here, the argument "t" is to be understood throughout. ] (2) b(t+1) = b*(t), b(O) = O, a(t~l) = a*(t), a(O) = 0o. 69

Assume now wire c of the net below connected to wire c of the net above. d _ c Call the resultant net N. N may be regarded as an automaton with 8 internal states (viz., the states associated with wires a, b, d), 2 outputs states (viz., the states of wire b*), 2 input states (viz., the states of "cable" x), and direct transition and output functions given by the table below. To facilitate construction of the table, we set down the appropriate equations. 1. Equations for direct transition functions: (i) a(t+l) = x(t) ((t)Vb(t ), (ii) b(t+l) = x(t) a(t) x(t) d(t) b(t) (iii) d(t+l) = 1. 2. Equation for direct output function: b*(t) = x(t) a(t)Vx(t) ((t)Vb(t) 3. Equations for initial internal state: a(O) = b(O) = d(O) = 0 It is clear that the states (a, b, d) = (1, 1, 0), (1, 0, 0), (0, 1, 0) are not accessible from (0, 0, 0) and so these states are omitted from the tablebelow., I Q Q V x a b d a b d b* O 0 0 0 101 0 0 0 0 I 0 0 1 0 0 0 1 1 1 1 0 0 1 0 1 0 1 1 0 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 0 0 1 0 0 1 0 1 011 0 11 1 1 11 0 1 0 0 1 0 1 1 1 1 0 1 1 1 70

Below is a direct transition-output diagram corresponding to the table above. 1-0 0-0 1-0 0-1 111 Notice that internal state 111 is not accessible from state 000. We therefore delete 111 from the set of internal states. We now partition the four internal states into equivalence classes. Rio: (000, 011)}, 101), (001) R2' (000, 011), (101), (001) Thus the minimal automaton equivalent (relative to [000)) to the given automaton is given by the diagram below. 1-1 1-0 0-0 0-1 One may check at this stage that this automaton realizes the event in question. We now rename the internal states and then construct a net with an output which behaves like b* above. 71

1- 0-0 110 1-0 0-0 0-1 x e f e f y O 0 0 0 1 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 0 0 0 1 1 0 1 1 0 0 1 1 0 1 0 0 f =x - x e f, = x e f Vx e f Vx e f = efVx e f. To simplify e*, we may require that e* be 1 when x = e = f = 1. That is e* e fVx e f Vx e f= e fVx f. y = x e fVx e e f e f = x fVx e fo x Y e*iJ' c-t~e-I a,;- I-e II de lay _ We terminate this discussion with the schematic diagram above. It should be clear however, how to proceed to construct a detailed net, 72

9. BIBLIOGRAPHY Books on Switching and Automata Theory 1. Shannon, C., and McCarthy, J., eds. Automata Studies, Princeton Univ. Press, 1956. 2. Caldwell, S. H., Switching Circuits and Logical Design, John Wiley and Sons, Inc., New York, 1958. 3. Keister, W., Ritchie, A. E., and Washburn, S. H., The Design of Switching Circuits, D. Van Nostrand Co., New York, 1951. 4. Phister, M., Jr., Logical Design of Digital Computers, John Wiley and Sons, Inc., New York, 1958. 5. Richards, R. K., Arithmetic Operations in Digital Computers, D. Van Nostrand, Co., New York, 1955. 6. Richards, R. K., Digital Computer Components and Circuits, D. Van Nostrand, Co., New York, 1957. 7. Seshu, S., Theory of Linear Graphs with Application to Electrical Engineering, Electrical Engineering Department, Syracuse Univ., Syracuse, New York. 8. Staff of Harvard Computation Laboratory, Synthesis of Electronic Computing and Control Circuits, Harvard Univ. Press, Cambridge, 1951. Books on Related Mathematical Topics 9, Birkhoff, G., Lattice Theory, American Mathematical Society Colloquium Publications, Vol. XXV, (1948). 10. Birkhoff, G., and Mac Lane, S., A Survey of Modern Algebra, The Macmillan Co., New York, (Chapter XI). 11. Church, A., Introduction to Mathematical Logic, Vol. I, Princeton Univ. Press, Princeton, 1956. 12. Davis, M., Computability and Unsolvability, McGraw-Hill, New York, 1958. 13. Hilbert, D., and Ackermann, W., Principles of Mathematical Logic, Chelsea, New York, 1950 (translation of the 2nd edition, 1928). 14. Kleene, S. C., Introduction to Metamathematics, D. Van Nostrand Co., Princeton, New Jersey, 1952. 73

15. Rosenbloom, P. C., The Elements of Mathematical Logic, Dover Publications, New York, 1950. 16. van der Waerden, B. L., Modern Algebra, Vols. I, II, Ungar, New York, 1949-50 (translation of the 2nd edition, 1937, 1940). Papers and Articles 17. Bratton, D., "A Theorem on Factorization in Semi-groups that Results from a Theorem of Kleene's in the Theory of Automata," Abstract in Notices of the American Mathematical Society, Vol. 6, No. 3 (June, 1958). 18. Buchi, J. R., Elgot, C. C., and Wright, J. B., "The Non-existence of Certain Algorithms of Finite Automata Theory," Abstract in Notices of the American Mathematical Society, Vol. 5, No. 1, 98 (February, 1958). 19, Burks, A. W., "The Logic of Fixed and Growing Automata," to appear in Proceedings of the 1957 International Symposium on Switching Theory, Harvard University Press. 20. Burks, A. W., and Copi, I. M., "The Logical Design of an Idealized GeneralPurpose Computer," J. Franklin Institute, 261, No. 3, 299-314 (1956). 21. Burks, A. W., McNaughton, R., Pollmar, C. H., Warren, D. W., and Wright, J. B., "Complete Decoding Nets: General Theory and Minimality," J. Soc. Ind. Appl. Math., 2, 201-243 (1954). 22. Burks, A. W., McNaughton, R., Pollmar, C. H., Warren, D. W., and Wright, J. B., "The Folded Tree," J. of the Franklin Institute, 260, Nos. 1 and 2, 7-24 and 115-126 (1955. 23, Burks, A. W., and Wang, H., "The Logic of Automata," J. of the Assoc. for Computing Machinery, Part I, 4, 193-218, Part II, 4, 279-297 (1957). 24. Burks, A. W., Warren, D. W., and Wright, J. B., "An Analysis of a Logical Machine Using Parenthesis-Free Notation," Mathematical Tables and Other Aids to Computation (April, 1954). 25. Burks, A. W., and Wright, J. B., "Theory of Logical Nets," Proc. IRE, 41, 13571365 (1953). 26. Church, A., "Application of Recursive Arithmetic in the Theory of Computers and Automata, " Notes from'Advanced Theory of the Logical Design of Digital Computers," Summer Session Course, U. of Michigan, June, 1958. 27, Copi, I. M., "Matric Development of the Calculus of Relations," J. of Symbolic Logic, 13, 193-203. 74

28. Copi, I. M., Elgot, C. C., and Wright, J. B., "Realization of Events by Logical Nets," J. of the Assoco for Computing Machinery, 5, 181-196 (1958). 29. Elgot, C., "On Single vs. Triple Address Computing Machines," J. of the Assoc. for Computing Machinery, 1, 119-123 (1954). 30, Elgot, C., and Wright, J., "Series-Parallel Graphs and Lattices," to appear in the Duke Mathematical Journal, 1958. 31. Elgot, C., and Wright, J., "Quantifier Elimination in a Problem of Logical Design," to appear in the Michigan Mathematical Journal. 32. Friedman, J., "Some Results in Church's Restricted Recursive Arithmetic," J. of Symbolic Logic, 22, 337-342 (1957). 33. Ginsberg, S., "On the Length of the Smallest Uniform Experiment which Distinguishes the Terminal States of a Machine," J. of the Assoc. for Computing Machinery, 5, 266-280 (1958). 34. Ginsberg, S., "Some Remarks on Abstract Machines," I, January, 1958, II, May, 1958, National Cash Register Co., Electronics, Div., 1401 El Segundo Blvd., Hawthorne, Calif. 35. Hohn, F. E., Seshu, S., and Aufenkamp, D. D., "The Theory of Nets," IRE Transactions on Electronic Computers (September, 1957). 36. Huffman, D. A., "The Synthesis of Sequential Switching Circuits," J. of the Franklin Institute, 257, 161-190, 275-303 (1954). 37. Kleene, S. C., "Representation of Events in Nerve Nets and Finite Automata," Automata Studies, Princeton Univ. Press, 1956, 3-41. 38. DeLeeuw, K., Moore, E. F., Shannon, C. E., and Shapiro, N., "Computability by Probabilistic Machines," Automata Studies, Princeton Univ. Press, 1956, 183-212. 39. Lunts, A. G., "The Application of Boolean Matrix Algebra to the Analysis and Synthesis of Relay Contact Networks," Doklady Akademii Nauk SSSR, 70, No. 3 40. McCluskey, E. J., "Iterative Combinational Switching Networks," Notes from "Advanced Theory of The Logical Design of Digital Computers," Summer Session Course, U. of Michigan, June, 1958. 41. McCluskey, E. J., Jr., "Minimization of Boolean Functions," Bell System Technical Journal, 35, 1417-1444 (1956). 42. McNaughton, R., "A Proof that Addition is Not Arithmetically Definable in Terms of a Single Unary Operator," Technical Report No. 3, Applied Mathematics and Statistics Laboratory, Stanford University, May 1, 1957.

43. McNaughton, R., "Unate Truth Functions," Technical Report No. 4, Stanford University, October 21, 1957. 44. McNaughton, R., and Mitchess, B., "The Minimality of Rectifier Nets with Multiple Outputs Incompletely Specified," Technical Report No. 2, Applied Mathematics and Statistics Laboratory, Stanford University, April 18, 1957. 45. Mealy, G. H., "A Method for Synthesizing Sequential Circuits," Bell System Technical Journal, 34, 1045-1079 (1955). 46. Medvedev, I. T., "On a Class of Events Representable in a Finite Automaton," MIT Lincoln Lab Group Report, 34-73, translated from the Russian by J. SchorrKon, June 30, 1958. 47. Moore, E. F., "A Simplified University Turing Machine," Proc. of the Toronto Meeting of the ACM, Toronto, 1952 (Bell Telephone Lab. monograph 2098). 48. Moore, E. F., "Gedanken-Experiments on Sequential Machines," Automata Studies, Princeton, 1956, 129-153. 49. Muller, D. E., "A Theory of Asynchronous Circuits," to appear in Proceedings of the 1957 International Symposium on Switching Theory, Harvard Univ. Press. 50. Murray, F. J., "Mechanisms and Robots," J. of the Assoc. for Computing Machinery, 2, 61-82 (1955). 51. Polya, G., "Kombinatorische Anzahlbestimmungen f{ur Gruppen, Graphen und Chemische Verbindungen," Acta Mathematica, 68, 145-254 (1937). 52. Post, E, L., "Revursively Enumerable Sets of Positive Integers and Their Decision Problems," Bull. Amer. Math. Soc., 50, 284-316 (1944). 53. Quine, W. V., "A Way to Simplify Truth Functions," American Mathematical Monthly, 62, 627-631 (1955). 54. Rabin, M., and Scott, D., "Finite Automata and their Decision Problems," IBM Research Center, Lamb Estate, Yorktown, New York,1958). 55. Raney, G. N., "Sequential Functions," J. of the Association for Computing Machinery, 5, 177-180 (1958). 56. Riordan, Jo, and Shannon, C. E., "The Number of 2-Terminal Series-Parallel Networks," J. of Mathematics and Physics, 21, 83 ff. (1942). 57. Shannon, C. E., "A Universal Turing Machine with Two Internal States," Automata Studies, Princeton Univo Press, 1956, 157-165. 76

58. Shannon, CO Eo,, "Symbolic Analysis of Relay and Switching Circuits," AIEE Trans., 57, 713-723 (1938). 59. Shannon, C. E,, "The Synthesis of Two-Terminal Switching Circuits," Bell System Technical Journal, 28, No. 1, 59-98 (January, 1949). 600 Turing, A. M., "On Computable Numbers, with an Application to the Entscheidungesproblem," Proc. London Math. Soc. ser. 2, 42, 230-265 (1936-7), with a correction, ibid., 43, 544-546 (1937). 61. Wang, Ho, "A Variant to Turing's Theory of Computing Machines," J. of the Assoc. for Computing Machinery, 4, 63-92 (1957). 62. Wang, Ho, "University Turing Machines~ An Exercise in Coding," Zeitschrift fur Mathematische Logik und Grundlagen der Mathematik, 3, 69-80 (1957). 77

UNIVERSITY OF MICHIGAN 3 I111 11 1115086711 8ll lii f I 3 9015 02826 7618