LIB RA R Y Michigan State ' University ABSTRACT A UNIFIED TREATMENT OF HISTORY DEPENDENCY IN DIFFERENTIAL SYSTEMS BY Charles George Brockus The general method of Behavioral Diagrams is introduced briefly, then used as the basis for an investigation of the behavior of differential systems. The concept of short-term state variables is introduced in order to permit the size of the state space of an object to be viewed as an in- variant property of the object. Several practical benefits are realized for the analysis of differential systems as a result of the adoption of this concept. An entire set of representations is established for an arbitrary system. These representations are characterized by different parti- tions of the state space. Methods are developed for obtaining all such descriptions. The properties of the alternative descriptions are inves- tigated across the entire spectrum of system types in order to determine how solutions can be obtained from those descriptions. It is seen that a subset of those representations can be obtained with a minimal amount of work. The representations in that subset are characterized by a minimal complexity in their symbolic expressions. A preliminary investigation is proposed as a means to determine an optimal description to be used in the subsequent analysis of a partic- ular system. A determination cannot be made in all cases, but the new Charles George Brockus alternative descriptions are seen to be of value in a substantial number of cases. The results of the investigation are applied to a study of Bond Graphs, and some new techniques are developed for application in that method of analysis. Some special results are also provided: a new method for the simplification of truth functions; a new method for generating all trees of a linear graph, utilizing a technique developed to generate specific subsets of those trees; a new method for finding edge-incidence ma- trices from a out set matrix; and a new method for finding minimal edge-sets and minimal vertex-sets of a directed graph. A UNIFIED TREATMENT OF HISTORY DEPENDENCY IN DIFFERENTIAL SYSTEMS BY Charles George Brockus A THESIS Submitted to Michigan State University in partial fulfillment of the requirements for the degree of DOC TOR OF PHILOSOPHY Department of Electrical Engineering and Systems Science 1972 A /\ #4" 4 Q‘ AC KNOW LEDGMEN TS I wish to express my deep appreciation for the combined efforts Collectively, they furnished just the proper They of my guidance committee. blend of attitudes to affect the completion of this dissertation. were critical, tolerant, skeptical, encouraging and--in the end-- accepting. Dr. J. A. Resh, my major professor, furnished the inspiration for the work. Not only did his ideas serve as the source for this dis- sertation, but his inquisitive mind furnished a model for my behavior. He monitored my progress while leaving me essentially free to pursue whatever topics piqued my curiosity--a unique style of leadership which I found comfortable. Dr. R. O. Barr, Jr. had a strong influence on the style and clarity of my presentation. He furnished some needed encouragement on s everal occasions. Dr. J. S. Frame served as a sounding board for some of my ide a’8 in their formative stages, sometimes pointing out the forest While I was yet engrossed with the trees. He gave the final form 01' the dissertation his usual meticulous attention. Dr. H. E. Koenig brought to bear his extensive background in dl'fferential systems, furnishing constructive criticism along with a strong advocacy for bestowing credit where due. He 3180 furnished hi3 eIlcouragement on several occasions. ii Dr. R. C. Rosenberg brought to my committee an active interest in several of the problems studied here. Our many discussions were lively and highly stimulating--of great value to me. Every committee should have such a member. A special mention must be made of Dr. B. L. Weinberg of the Computer Science Department. While not a member of my committee, he took the time to engage in several discussions concerning the material of Appendix A. Support was furnished for the preparation of this dissertation through the auspices of the Division of Engineering Research, in the form of a Graduate Research As sistantship. Tangible support was provided by my working wife, Alice Marie, throughout my educational process. The intangible support she supplied has been the sine qua non for this document. Finally, my thanks to Linda Zimmerlee for an excellent job of typing the manuscript. iii TA BLE OF CONT EN TS ABSTRACT ACKNOWLEDGMENTS . . . . . . . . . . . . . . . . . . LIST OF TABLES . . . . . . . . . . . . . . . . . . . . LE T OF FIGURES O O O O O O O O O O O O O O C O O O I. INTRODUCTION ......... l. The Origins of this Dissertation . . . . . . Z. Behavioral Diagrams and Short- Term State Variables. . . . . . . . . . 3. Alternative Techniques for the Study of the Behavior of Differential Systems . . . . . 4. An Application of the Methodology of Behavioral Diagrams . . . . . . . . . . 5. The Development of Some Tools Needed for theStudyofBehavior . . . . . . . . . . . . . A GENERAL METHOD FOR DERIVING THE STATE-OUTPUT RELATIONS FOR A SYSTEM . . . 1. Introduction . . . . . . . . . . . The Task of an Experimentalist. . . . . . . . . . The Synthesis of Objects and Systems . . . . . . Behavioral Diagrams and System Orientations . . The Algebraic Reduction of Behavioral Diagrams . 01wa STATE-OUTPUT EQUATIONS FOR DIFFERENTIAL SYSTEMS--A SPECIALIZATION OF THE GENERAL METHOD................... 1. Introduction . . . . . . . . 2. Linear Graph Representations of Differential Systems . . 3. The Elements and Variables of the Behavioral Diagrams for Differential Systems . . . . . . . 4. Constructing Behavioral Diagrams for Differen- tialSystems . . . . . . . . . . . 5. Basic Orientations for Elements and Systems. . 6. A Procedure for Establishing an Initial Basic Orientation for a Behavioral Diagram , , , . iv Page ii vii ix 12 12 15 15 16 17 18 23 28 28 29 31 35 38 43 IV. VI. VII- VIII 7. The Algebraic Reduction of Behavioral Diagrams 8. The Attainable- Minimum Optimal-n for an n- Reducible Loop Structure . . . . . . . . . . THE CONCEPT OF SHORT- TERM STATE VARIABLES. O I O O O O O O O O O O O 1. Introduction . . . . . . . . . . 2. State Equations and Problematical Systems . 3. Short- Term State Variables in Differential Systems . . . . . . . . 4. Partitions of the State Space of Differential Objects . . . . . . . . . . . . . . . . 5. Efficient Analysis of Linear Systems . . . . . 6. Analytical Solutions for Full Short-State De- scriptions of Linear Differential Objects . . . MIXED-STATE REPRESENTATIONS OF LINEAR DIFFERENTIAL OBJECTS . . . . . . . . . . . 1. Introduction............. . The State- Output Matrix--S--and its Normal Form 2 3. Alternative Basic Orientations from the S Matrix 4 . The Existence of Full Short-State Descriptions of Linear Differential Systems . . . . . . . 5. Selection of Alternative Sets of Behavioral Features for Linear Differential Objects . . . ANALYTICAL SOLUTIONS FOR MIXED-STATE REPRESENTATIONS OF LINEAR DIFFERENTIAL SYSTEMS. I O O O O O I O O O O O O O O O l. The Propriety of a System . . . . . . 2. Strongly Proper Systems and Other Systems from which Solutions can be Obtained Directly . 3. Weakly Proper Systems . . . . . . . . . . . 4. Weakly Improper Systems . . . . . . . . . . 5. Strongly Improper Systems . . . . . . . . . THE A PRIORI EXISTENCE OF MIXED-STATE DESCRIPTIONS OF DIFFERENTIAL SYSTEMS . . 1. Introduction . . . . . . . . . . . . . 2. Determining the Existence of Alternative De- scriptions . . . . . . . 3. A Form for Listing the Mixed-State Descriptions 4. Mixed-State Representations of Non- Linear SYStems O O O I O O O O O O O O O O O 0 AN APPLICATION TO BOND GRAPHS--TOWARDS INTERDISCIPLINARY UNITY . . . . . . . . . . 1. Introduction . . . . . . . 2. The Details of Bond-Graph Diagrams. . . . . Page 50 59 70 70 71 73 75 77 79 83 83 84 87 9O 95 101 101 103 107 112 116 121 121 . 122 125 132 138 138 141 «JO‘U‘IFW Constructing Bond Graphs from Linear Graphs Orienting Bond Graphs . . . State- Output Equations from the Bond Graph Static Dependence and the Bond Graph Constructing Linear Graphs from Bond Graphs IX. CONCLUSIONS . . . . . . . . . 1. 2. 3. 4. The Method of Behavioral Diagrams The Concept of Short- Term State Variables Special Results from the Dissertation Recommendations for Future Investigations REFERENCES............ APPENDIX A. IprD-i CO. APPENDDC 1 . 0‘01»th APPENDIX FUNCTIONS . . . . . Introduction . . . . . The Axiomatic Duality of Boolean Algebra Some Semantics for Quantification . Terminology of Truth Functions and the Strong Role of Implication . . . . . Unate Truth Functions . . . Definitions for Some Operations . Two Theorems on the Simplification of Truth Functions . . THE SIMPLIFICATION OF TRUTH A New Method for the Simplification of Truth Functions......... B. TRUTH FUNCTIONS AND LINEAR GRAPHS Introduction . . . . . . Symmetry in Linear Graphs . Properties of the XSA. . . . A New Formulation of the XSA. Generating Trees of the Graph. Finding the Edge- Incidence Matrix by Truth Function......... C. OPTMAL N-REDUCIBILITY FOR BEHAVIORAL DIAGRAMS Introduction . . . . . The Method of Path Algebra . A Method for Determining the Optimal N- Reduci-o bility of a Behavioral Diagram Page 142 146 149 152 153 158 158 159 162 164 166 171 171 173 173 174 179 179 180 186 189 189 192 195 198 201 209 216 216 218 222 LIST OF TABLES Table Page 111- 1: The Fundamental Tie Sets for the Reduced Graph . . . . 64 III- 2: Rows from the Well- Ordered CSA . . . . . . . . . . 65 VII- 1: The Possible Orientations for the Object . . . . . . . 127 VII-2: The Fundamental Tie Sets for Partition (0, 0, O, 0) . . . 127 VII-3: The CSA for Partition (0, O, 0, 0) . . . . . . . . . . . 128 VII- 4: The Fundamental Tie Sets for Partition (0, 0, 0, l) . . . 128 VII-5: The CSA for Partition (0, 0, O, l) . . . . . . . . . . . 128 VII- 6: The Fundamental Tie Sets for Partition (0, 0, l, 0) . . . 129 VII- 7: The CSA for Partition (0, 0, l, 0) . . . . . . . . . . . 129 VII- 8: The Mixed-State Descriptions for the Object . . . . . . 130 VIII- 1: Fundamental Tie Sets for the Bond Graph . . . . . . . 151 VIII- 2: The Fundamental Tie Sets of the Graph . . . . . . . . 156 VIII-3: The Edge Incidence Matrix for the System . . . . . . . 156 B- 1 : All Possible Fundamental Y—Sets--(when nx = 4) . . . . 201 B- 2: All Possible Columns for the XSA-- (when nx = 4) . . , , 201 B" 3 = The Fundamental Tie Sets for the Initial Tree . . . . . 207 B“ 4: The Rows of the CSA for the First Iteration . . . . . . 203 B‘ 5 = The Fundamental Tie Sets for Iteration Two . . . . . . 203 B‘ 6: The Rows of the CSA for Iteration Two . . . . . . . . 208 B” 7: The Fundamental Tie Sets for Iteration Three . . . . . 209 B. 8' The Rows of the CSA for Iteration Three . . . . . . . 209 The Fundamental Tie Sets for the Two Cases , , , , , 212 Table B-lO: B-ll: B-12: B-13: Page The Well-Ordered CSA for Each Case . . . . . . . . 212 All Row-Cover Matrices for the Two Cases . . . . . 213 All Possible Columns for a CSA (when nc = 3) . . . . 214 All Possible Fundamental Tie Sets (when nc = 3) . . . 215 viii LIS T OF FIGURES Figure Page II- 1: The Behavioral Diagram of a Hypothetical Object . . . 20 11-2: A Basic Orientation of the Behavioral Diagram . . . . 22 121-3: A l-Reducible Loop Structure . . . . . . . . . . . . 27 III- 1: The Linear Graph of the System . . . . . . . . . . . 37 III- 2: A Behavioral Diagram for the System . . . . . . . . . 38 III-3: Basic Orientations for the Dissipator . . . . . . . . . 39 III- 4: Basic Orientations for the Sources . . . . . . . . . . 40 HI— 5: Basic Orientations for the Across-Type Memory Element...................... 41 III— 6: Basic Orientations for the Through— Type Memory Element O O O O O O O O O O O O O O O O O O O O O O 41 IJI- 7: A Basic Orientation of the Behavioral Diagram. . . . . 48 IH— 8: The Linear Graph for the System . . . . . . . . . . . 49 111- 9: An Oriented Behavioral Diagram for the System . . . . 51 III— 10: A Streamlined Behavioral Diagram for the System . . . 56 III— 1 1: A Streamlined Behavioral Diagram for the System . . . 58 In“ 12: Schematic Diagram of a System's Basic Orientation . . 6O 111‘ 13: The Linear Graphfor the System. . . . . . . . . . . 64 III“ 14: The Linear Graph of the System . . . . . . . . . . . 66 III” ' The Streamlined Behavioral Diagram from T1 . . . . . 67 III‘ 16: The Streamlined Behavioral Diagram from T2 . . . . . 68 V- 1 3 The Linear Graph for the Phase Shift System . . . . . 92 V‘ Z: The Linear Graph of the New System . . . . . . . . . 98 Figure V- 3: VI- 1: VI- 2: VI- 3 : VI- 4: VI- 5: VII-2: VII-3: VIII-l: VIII-2: VIII-3: VIII-4: B- 1: B-2: (3- 1: C— 2; C— 3 : 0-4: The Graph of the Superposed Trees . . . . . The Linear Graph for the Strongly Proper System The Linear Graph of a Strongly Improper System . The Linear Graph of a Weakly Proper System . The Linear Graph of a Weakly Improper System The Linear Graph of a Strongly Improper System . The Linear Graph for the System . . . . The Behavioral Diagram for Partition (1, l, l, 1) . The Behavioral Diagram for Partition (0, 0, 0, 0) . The Bond Graph with Complete, Consistent Causality . The Augmented Bond Graph for the System . A Bond Graph for the System . . . . . . . . The Linear Graph for the System . . . . . . The Linear Graph for the Example . . . . . Two LinearGraphs . . . . . . . . . . . . A Streamlined Behavioral Diagram . . . . . The Directed Flow Graph for the Example . . The Directed Flow Graph for the Example . . The Opened Flow Graph for the Example . . Page 99 104 106 109 114 117 126 133 134 148 151 155 157 207 211 221 221 225 225 CHAPTER I IN TRODUC TION Systems Science has developed during the past decade into a dis- cipline covering a broad spectrum of interests and techniques. Its foundations range from very abstract treatments, of which an important example is to be found in the work of Zadeh [64] --in which systems are viewed as functional mappings from one space to another--to the more practical treatments, of which an important example is to be found in Koenig et a1 [33] --in which the emphasis is placed on the development of techniques for obtaining quantitative descriptions of specific differential systems. This dissertation belongs in the latter category. The systems scientist can function as an experimentalist--one who observes behaviors of an actual system and develops models, per- haps heuristically, which simulate those behaviors. He can function as a modeler--one who guides the evolution of models by means of analysis and experimental verification, by means of synthesis and de- sign. He might be found dealing with the analysis of well developed models--in order to understand more fully the behavior of a system, to be able to predict its behaviors under interesting circumstances. He can be found in the attempt to control a system--by searching the set of all possible stimuli for the system to find the subset which will produce the desired responses. Sometimes he will be involved in the modification of a system--so that the system will be able to produce favorable responses to available stimuli. Finally, he often devotes his efforts to the design of an entirely new system--one which will possess a set of responses which are exactly right for his intended application. This dissertation is located in the analysis and modeling band of that spectrum. This dissertation can be viewed as the conceptual foundation for a systems analysis algorithm. It presents new techniques for the analysis of differential systems which nicely complement existing techniques. And, although a selection cannot be made in all cases, it presents methods for determining conditions under which an optimum selection can be made from the augmented set of alternative techniques. An entire class of quantitative models is developed to describe a sys- tem, along with the techniques necessary to obtain temporal solutions for the system's behavior from those alternative descriptions. Further- more, although the topic of system control is not broached, some new techniques are presented which will greatly facilitate the investigation of the set of all stimuli available for a system, or the set of all environ- ments in which the system can be immersed, which therefore will be of value to the system control theorist. Almost all systems of practical interest to the systems scientist exhibit history dependency, or memory. A system with memory is influenced in the determination of its responses not only by the im- mediate status of its stimuli but also by the history of those stimuli, the manner in which they have varied in the past. Systems science has included the development of the state space of a system as a for- mal acknowledgement of that history dependency. State equations appear as the conventional form in which quantitative descriptions are given to portray the system's behavior in the time domain. The current treatment of history dependency in the behavior of differential systems gives recognition only to long-term memory, to the influence of stimuli variations existing from the present into the indefinite past. That recognition is unanimous in the literature: it can be seen in the previous references ([ 64] , [33] ); in texts which are introductory to the topic (see, for example, Rohrer [53] ); and in technical journals (see, for example, Parkin and Silverberg [47] ). This dissertation advances the concept of short-term memory, a recognition of the strong influence exerted on some systems by stimuli variations occurring in the very immediate past. The adoption of short- term state variables to accommodate this concept provides some tangible benefits as it permits a rich variety of alternative techniques to be used in the analysis of systems. It also provides an intangible benefit as it provides the solution to a concep- tually troublesome phenomenon. Some systems, under the traditional treatment, seem to be represented by a state space which varies in size with varying environments. The unifying concept of short- term memory removes those variations and thus permits the size of the state space to be viewed as an invariant property of the system. 1. The Origins of this Dissertation Resh [52] has called Systems Science "The Study of Behavior". He has developed a viewpoint concerning the manner in which an ex- perimentalist deals with formal models which simulate behaviors ob- served in the phenomenological world. This dissertation presents an extension of that viewpoint; a refinement of selected facets of the c entral concept along with the development of the associated method- ology, in an application to systems for which the behavior can be represented by ordinary differential equations. Hopefully, the results obtained for differential systems will yield insight to the nature of the results which might be obtained through a similar approach to systems with much different characterizations. As the viewpoint is developed here it will be seen to provide in- sight to the behavior of differential systems. Moreover, it will be seen to provide a systematic, well organized approach to the investiga- tion of the behavioral relations of those systems. The approach can readily be utilized as the basis for a practical computer program for use in the analysis of differential systems. An underlying intention of this dissertation is to provide the conceptual foundation for such a program. All of the key methods to be found here can easily be de- veloped into efficient algorithms. 2. Behavioral Diagrlams and Short- Term State Variables This dissertation is organized around a method and a concept. The former, to be called 'The Method of Behavioral Diagrams', is the fulfillment of the viewpoint mentioned above. The latter, to be called 'The Concept of Short- Term State Variables', becomes a key requirement for the utilization of much of the new methodology de- veloped here for differential systems. E_.__1_. 'The Method of Behavioral Diagrarns' is not a sufficiently descriptive title to imply the diversity of the methodology grouped under that heading. The title is derived from the graphical techniques used to aid in the visualization of the important concepts as they are developed. The method was evolved through a detailed consideration of the procedures necessary to obtain the behavioral relations for a system. The result is a systematic procedure for obtaining those relations in any of several desired forms. Chapter 11 presents the refined version of the facets selected from the central concept of [52] , in the form in which they apply to general systems of unspecified characterizations. That presentation includes: a». The philosophy of the investigation: e. g. , the view- point that it is useful (as well as possible) to study the behavior of an object in all of its permissible environments; Definitions for terminology of the investigation: e. g. , the process of selecting dependent and independent behavioral features is termed the process of orient- ing the object; The framework of the method: e. g. , the specific rules which apply in obtaining behavioral relations for general systems, and which must be interpreted and followed while investigating differential systems. Chapter III presents, as a case study, the manner in which the general method of Behavioral Diagrams can be applied to the study of a particular type of system. One of the principal values of this dissertatation lies in this pilot application of Behavioral Diagrams to differential systems. The various steps to be taken are not merely outlined and described, they are carried out in a concrete and well known discipline. The value of this procedure comes from the insight afforded-~to the process of applying the method, and to the practical utility of the method in general. A bonus value accruing to this application is the visibility pro- vided for some fundamental results in differential systems. Several well-known results are obtained in this chapter; but the careful de- composition of the approach into simple, coherent steps yields clear and intuitively appealing derivations for these familiar results. In this chapter, and to a great extent in subsequent chapters, the examples presented deal with linear systems. Most of the develop- ment does not depend on that linearity, however, and the primary value of the method for differential systems will be found in its appli- cability to nonlinear systems. A result of considerable importance is developed in the final section of Chapter III. This result permits the behavioral relations for a differential system to be obtained in a manner requiring a mini- mum amount of work. This result was not previously available, and its accomplishment depends upon the experimentalist's acceptance of the short- term state variable concept. _§_._§. The concept of short-term state variables is of central importance throughout the dissertation. The adoption of that concept is promoted herein as the means of providing the titular unification for the treatment of the history-dependency of differential systems. The concept is bypassed in Chapter 111, although its presence is implicitly acknowledged by postulate. The dependence of the final result of that chapter on the postulate provides the initial motivation for the adoption of the concept itself. Due to the central importance of the concept, a separate chapter, Chapter IV, is devoted to its manifestation, to the problematical sys- tems which give rise to the need for a unifying concept, and to a dis- cus sion of the viewpoint which yields the name for the concept. Systems analysts have employed special techniques in the past to deal with those problematical systems. It is suggested in this chapter that other techniques may become available for that purpose through the adoption of short-term state variables; and subsequent chapters are devoted to the establishment of those methods. Adopting Zadeh's [64] adjective, "improper", for the proble- matical systems, subsequent chapters present examples to illustrate that this adoption can be of importance in three instances: a. The behavioral relations for 'proper' systems can sometimes be obtained in an alternative form which is more tractable for the purpose of obtaining solu- tions: e. g. , sparse matrices in the expressions for linear systems; b. 'lrnproper' systems often can be handled more conveniently with behavioral relations in an alter— native form: e. g. , a set of state variables directly associated with energy-storage components can be retained for certain systems, for which this would not have been possible previously; c. Systems containing certain types of nonlinearities require behavioral relations in an alternative form, through necessity or perhaps for computational convenience: e. g. , when functional inverses do not exist or are not computationally expedient. The final section of Chapter IV presents a derivation of the ana- lytical solutions for 'proper' linear differential systems when their behavioral relations are given in an alternative form in which all of the state variables are short- term state variables. The value of this solution form is made evident in the subsequent chapters as an example is given for a case a. , above; and when the techniques are developed to handle 'improper' systems by alternative methods as mentioned in b. , above. 3. Alternative Techniques for the Study of the Behavior of Differential Systems A question has been raised concerning the availability of alter- native techniques for the investigation of the behavior of differential systems--contingent upon the adoption of the short- term state variable concept. That question is answered in the affirmative by this disser— tation, as alternative techniques are developed for the stated purpose. L1. The framework for the investigation of linear differential. systems is presented in Chapter V. Section 2 of the chapter provides a normal form for the behavioral relations of such systems. That form is proposed because it is a very convenient form from which to obtain alternative sets of behavioral relations. A viewpoint in Chapter 11 holds that useful information concerning an object can be obtained by subjecting the object to all possible environ- ments. In order to do so, it is necessary to accommodate reorienta- tions of the object. The machinery required to accomplish those re- orientations is presented in section 3 of Chapter V. That machinery is utilized in section 4 of the chapter to establish the conditions which must exist in order for a 'proper' system to possess a set of behavioral relations in which only short- term state variables appear. An historically important network serves as an example of the case in which the description in that form is more tractable than a description in the conventional form. The example is expanded in a simple manner to include an active environment in order to emphasize the convenience of the alternative description. The final section of the chapter presents the techniques necessary to accomplish the selection of alternative sets of behavioral features for linear differential objects. This operation is another tool needed to investigate the behavior of the object in all possible environments. Use of the example from the previous section is extended to illustrate this procedure. The alternative description is again seen to be the more convenient form, as its simplicity permits the extension to be made easily. l._2_. Chapter VI presents techniques for obtaining solvable sets of equations from the behavioral relations, given in the normal form of Chapter V, for linear differential systems. When those relations are given in terms of mixed sets of state variables (both short- term state variables and conventional (or long- term) state variables) they do not yield solutions directly, in general. Five separate cases are considered, the cases being distinguish- able by the contents of certain sub-matrices of the relations in normal form. An example is provided with each case in order to illustrate the procedures . 10 The first two cases actually yield solutions from the relations in the mixed state- variable normal form. These systems are separ- able in the sense that solvable equations can be obtained for the short- term state variables which are independent of the long-term state variables, and vice versa. The case presented in section 4 illustrates a class of systems for which, when the conventional method is used for obtaining solu- tions, a new set of state variables must be defined as linear combina- tions of the original state variables and the system's inputs. The alternative method presented here permits the use of a reduced set of the original state variables in obtaining the solutions. The case presented in section 3 illustrates a class of systems for which the procedures are dual to those of case 4. The alternative form will yield solutions only in terms of redefined state variables, again linear combinations of the original state variables and the sys- tem's inputs. The conventional method yields solutions directly in terms of the original state variables. The case presented in section 5 illustrates a class of systems for which a more detailed investigation must be carried out in order to determine which of the available descriptions will be the most con- venient to use in obtaining the desired solutions. It is evident, however, that the use of short- term state variables will often provide a highly desirable alternative form for this purpose. 1._3. An investigation is undertaken in Chapter VII into the pos- sibility of performing an _a_ priori determination of the most convenient alternative form to be used for the behavioral relations of a differential 11 system. The extension of a well-known principle forms the basis of a method which permits that determination to be made in many cases. The question of whether or not a system is proper, as well as the general existence of alternative forms of the description of a sys- tem, depends on the system topology. The information which can be determined from investigation of the system graph is valid without regard for the linearity of the system components. Thus, the methods developed in this chapter pertain to nonlinear systems, while the two preceding chapters are restricted to linear systems. A convenient form is proposed for recording the information obtained from the system graph. This information can be gathered for all of the object‘s orientations at one time. The implications con- tained in this table of existing alternative descriptions are discussed in terms of the properties inherent to those descriptions. An example is given to illustrate the retrieval of information from the system graph. It is seen for one of the orientations of the object that a further investigation is required into the system equations. It is possible that in some cases, even under the more extensive in- vestigation, the results will not provide a basis for selecting a most convenient alternative description form. Finally, the object of the example is permitted to contain non- linear components of a practical nature. Both conventional and short- term state variable alternative descriptions are obtained for the System, and it is seen that the latter provides the favored way to treat this system. 12 4. An Application of the Methodology of Behavioral Diagrams The method of Bond Graphs is a technique recently developed for the analysis of differential systems. This method has been mech- anized for the computerized investigation of such systems, but the discipline is sufficiently new to retain several problem areas which have not been explored to a satisfactory extent. The method of Bond Graphs has many similarities to, and at the same time many differences from, the method of Behavioral Diagrams. The results which have been obtained for the latter method are applied in Chapter VIII to an investigation of the former method. As a result of this investigation, some refinements are suggested in the approach used in Bond Graphs; some of the results of this dissertation are seen to apply with a minimum of translation to one of the outstanding prob- lems in that discipline; and some other results are seen to provide the background for an approach to yet another outstanding problem in that discipline. 5. The Development of Some Tools Needed for the Study of Behavior In the course of developing the methodology of Behavioral Dia- grams as applied to the investigation of differential systems, it became necessary to apply certain techniques which were either not in exis- tence or not available in convenient form. These techniques have been generated to aid in accomplishing the central investigation. The tech- niques were developed with the goal that they would serve as the basis for efficient computer algorithms. They are described in the Appendices to the dissertation, and their appearance there is prerequisite to their use in the main body of the report. l3 §_._1_. Appendix A presents a general discussion of the termi- nology and manipulations of truth functions. Two theorems, one well known and the other not- so- well known, are given along with their duals. A technique is derived for the simplification of truth functions on the basis of those theorems. The technique is original, although similar to some results which have been published recently in the field. Almost all of the current simplification work is performed by the use of an iterative technique. The method derived here is direct. Current simplification work deals almost entirely with a set of clauses known as prime implicants. The method derived here permits the ready attainment of another set of clauses known as prime implicates as well, and that feature was very important to the development of the method contained in Appendix C. _5_._2_. Appendix B presents a truth-function approach to the study of linear graphs. Some new properties are established for the array of all cut-sets (tie-sets) of a graph which permit that array to be generated in a particularly nice way. One important problem, the generation of all trees of the graph, is solved in a manner which proves to be of great importance in this dissertation. The method permits the generation of specific subsets of trees. The method is important to the final result of Chapter III, and forms the basis for the technique used in Chapter VII for the 3 m determination of the most convenient alternative description tO be used in the analysis of a system. Another problem is solved, although the solution is not one Which would serve as a practical computer algorithm. That problem 14 is the realization of a graph from a tentative cut-set matrix. The solution of this problem is required in order to accomplish the method proposed in Chapter VIII for attacking an unsolved problem in Bond Graphs. 2. Appendix C presents the solution to a problem in the realm of directed graphs by means of a truth- function approach. The prob- lem is the determination of a minimum set of edges, and a minimum set of vertices, in order to open all feedback loops in a directed graph. The solution of this problem is applicable to problems in the areas of active systems analysis, finite state machines, and the analysis of analog computer programs, for example. The application of impor- tence in this dissertation is found in Chapter II, in the general method for establishing the behavioral relations in the study of system behavior. It serves there to permit those relations to be obtained with a minimum amount of work. CHAPTER II A GENERAL METHOD FOR DERIVING THE STATE-OUTPUT RELATIONS FOR A SYSTEM 1 . Introduction The material presented in this chapter forms the basis for the approach used to study systems in this dissertation. Based on the de- velopment by Resh [52] , the purpose of the material is to provide a systematic procedure for obtaining the behavioral relations for a system. Sections 2 and 3 of the chapter are devoted to a brief discussion of the philosophy of the investigation in order to place in perspective the role of this dissertation in systems science. Section 2 describes briefly the goals of an experimentalist, or observer, as he attempts to make efficient use of models in his study of actual behavior which has been observed in the phenomenological world. Section 3 deals briefly with the modeling procedure and the restricted manner in which it is to be used in the dissertation. The first step in the investigation of a system is to lay out in detail the various relational dependencies imposed by the structure of a system model. That is to be accomplished through the use of a be- havioral diagram. Section 4 establishes the terminology of behavioral diagrams and the rules which must be followed in the formal procedure 0f modeling a system by that means. 15 16 Section 5 presents the methods for obtaining the behavioral re- lations for the system from its behavioral diagram in an efficient manner. 2. The Task of an Experimentalist An experimentalist selects isolated articles (systems, groups, things, etc. ) from the phenomenological world around him and subjects them to an intensive scrutiny. His goal is to be able, ultimately, to describe to others the behaviors of such articles; to be able to predict the responses they will give to specific stimuli imposed under stated conditions; perhaps to alter their behavior patterns in some desired way by modifying their physical structure; in short, to understand them. In the study of articles there is a dichotomy of goals which must be attained in different ways. Behavior variations are studied in terms of: a. Modifications of the article's environment; b. Modifications of the article's structure. One necessary task to be performed in that study is the develop- ment of a model for the article. Such a model will be called an object. The object must be chosen to represent, in association with the cate- gories above, the article's: a. Behavior (Interactions between the article and its environment); b. Mechanism (Relation between the article's physical form and its behavior). The environment must be represented in compatible fashion. 17 The experimentalist can obtain valuable insight to an article's behavior by exposing the object to all of the possible environments which the model has been designed to accommodate. That can be accomplished by the expedient of maintaining the description of the en- vironment at a very general level. Although specific temporal behaviors can be observed only for an object interacting with a specific environment, properties of a general nature can be deduced for the object when it is studied in a general environment. For differential systems, whose investigation is undertaken in Chapter III, those properties take the form of con- trollability, obs ervability, stability, etc. The variation of an object through all of its alternative orienta- tions (orientations are discussed in section 4 of this chapter) becomes a valuable tool in accomplishing the investigation of an object in all possible environments. Many of the general properties of interest, including those listed above, are not invariants of the object but vary along with the object's orientation. Thus the experimentalist has hopes of finding orientations which will yield more efficient approxima- tions to the article's behavior than some of the alternative orientations. And efficiency is a highly desirable property which can make an experi- mentalist's task feasible when he is faced with the mechanized investi- gation of practical (and large) systems. 3. The Synthesis of Objects and Systems The object and its environment, when interconnected, will be termed a system. Alternatively an object will be viewed as a system 0f interconnected components, each component in turn being viewed as an object. This conceptual decomposition process can be continued through various hierarchical levels. At the lowest such level there 18 must exist a set of objects which will not be subjected to further de- composition; they will be termed elements. Objects can be developed in two basic ways. The first way in- volves a macro- analysis: The experimentalist observes the behavior of an article and postulates an object which characterizes that behavior. This procedure is associated with category a. of section 2 and is re- served for the development of elements. The second way involves a micro- analysis: The experimentalist synthesizes an object as a system of simpler objects through a physical knowledge of the article's inner construction. This procedure is associated with both categories of section 2. In this dissertation a set of elements will be assumed to exist (the set for differential systems will be represented by the R, L,C's and ideal sources of electrical networks). Modeling will be assumed to take place as in the latter procedure--by the construction of com- pound objects through hierarchical levels of interconnected components and elements. Modeling will not be studied directly, but a system modeler can conceivably gain indirect benefits through an increased insight to the behavior of differential objects. 4. Behavioral Diaggams and System Orientations The purpose underlying the use of behavioral diagrams is to pro- vide a graphical illustration of the constraints imposed on the behavior of an object by the nature of its component elements, as well as by the nature of their interconnections. Once these constraints are visible they can be taken into account more readily when deriving formal descriptions for the object's behavior. 19 These diagrams are widely applicable in the study of systems. Applications can be made to such well-known problems as the analysis of: finite state machines; computer programs (both analog and digital); electrical networks. That brief list indicates, but does not exhaust, the scope of the method. 11;]. In order to accomplish the stated purpose, the behavioral diagram must illustrate the constraints imposed by: a. The component elements, which represent the parts from which the object is constructed; in particular with regard to the relations these elements iInpose on their own behavioral features; b. The structural elements, which represent the media through which the parts communicate; i. e. , which specify the behavioral constraints imposed by the interconnections of the component elements within the object. As noted previously, the component elements in the case of dif- ferential systems will be taken as the set of R, L,C's plus the ideal sources. The structural elements will consist partially of the Kirchhoff Laws. A distinct structural element which appears in the behavioral diagrams for all types of systems is worthy of separate mention at this point. It is the behavioral direct connection (BDC) which repre- sents a formal recognition of the core of inter- object communications. A BDC lumps together several of the behavioral features of the separate elements and permits them to be assigned a common name. The BDC insists that all of these behavioral features have the identical instan- taneous value, thus the common name can logically be assigned. 20 Figure 1 shows the behavioral diagram for some hypothetical system. The vertices represent variables of the system which will be useful in determining behavioral relations for the object. The three shapes in the diagram represent elements of the object, their defining relations are given separately in equations (1). Two of the vertices represent BDC's in this diagram; they are the ones with variable names v3 and v4. 2 fl. 2vl - v2 + (v3-v4) = 0 f2: v3-v4+v5 : O (1) f3: V4- 4V6 1‘ 0 Figure 11- l: The Behavioral Diagram of a Hypothetical Object 4. 2. The orientation of an object is an important concept. The central purpose behind orienting an object is to impose a partition on the set of behavioral features of the object into inputs and outputsuto select the dependent and independent variables in the input- output re- lations of the object. The orientation of a behavioral diagram, however, has more to it than that. There is not, in general, a unique orientation of all of the components and elements contained in the behavioral diagram cor- responding to a particular input/output partition. It will be seen for differential systems that this lack of uniqueness gives rise to a second important feature; that a specific orientation of a behavioral diagram has the following two distinctive features: 21 a. The partition of behavioral features (into inputs and outputs); b. A partition iInposed on the state variables. The concept of orientation is indispensable to an understanding of the concepts of memory and causality, for example. The concept of memory, closely allied to item b. above, will come under discus- sion in section 5; and more extensively in Chapter IV. The concept of causality implies that objects having that property exhibit behavior which is both determinate and non- anticipatory. Objects having that property will be fundamental to this dissertation. iii. Graphically, then, an oriented behavioral diagram must give a sense of: a. m, which are behavioral features specified by the environment and imposed on the object (stimuli); b. Outputs, which are behavioral features specified by the object and iInposed on the environment (responses). M. A behavioral diagram presents a straightforward, if somewhat cumbersome, tool for the investigation of all of the alterna- tive orientations possible for a system. 11:333. An oriented behavioral diagram is a version of the familiar Mason-Coates [ l6] , [ 17] , [38] , [39] , [40] signal flow graphs. The flow, in this version, is one of functional dependency which illustrates graphically the dependencies among all of the variables. In a more streamlined version discussed in Appendix C, these diagrams become directed linear graphs. 11;}. It has been found that an orientation of a behavioral dia- gram must be imposed according to a set of rules in order that the 22 relations it implies among the object's behavioral features will be logic ally consistent. Any orientation which meets those criteria will be called a Basic Orientation. 4O 3O l. a. b. The orientation of an element is basic if: Its behavior is causal; Its behavior is not stimulus-constrained; i. e. , stimulus constraints do not embody element behavior; The orientation is minimal; 1. e. , no output can be redesignated as an input without violating a. or b. The orientation of an object is basic if: The orientation of each element in the object's behavioral diagram is basic; The behavioral diagram is consistent; i. e. , at each BDC there must be exactly one input, the remainder must be outputs. The orientation of a system is basic if: The orientation of the object is basic; The orientation of the environment is consistent with that of the object. Figure 2 shows a basic orientation of the behavioral diagram for the hypothetical system of section 4. 1. Figure 11-2: A Basic Orientation of the Behavioral Diagram 23 5. The Algebraic Reduction of Behavioral Diagrams Once a basic orientation has been obtained for a system‘s be- havioral diagram it can be processed into the form of an 'n- reducible loop structure'. The goal for the use of these loop structures is an optimum attainment of the state- output relations which describe the behavior of the object. 121. The first step to be applied in the algebraic reduction of oriented behavioral diagrams is to instantize all history- dependent elements of the diagram. An element, or an object, is said to be 'instantaneously deter- minate' if its responses can be determined at every instant solely from a knowledge of its stimuli at that instant. When such a deter- mination cannot be made for the reason that the responses depend at least in part on the past history of the stimuli, the object is said to exhibit history dependency--to have memory. The artifice which has been adopted in order to deal with such objects is the state variable. The experimentalist must adopt a sufficient set of state variables, whose instantaneous values depend on the history of the object's stimuli, in order that the object's responses become instantaneously determinate in terms of the values of the stimuli plus the values of the state variables. A history- dependent element is instantized by taking its sufficient set of state variables as free inputs (to be discussed in section 5. 2) in the modified behavioral diagram. At the same time a set of dynamic variables, which specify the manner in which the state variables are influenced by the stimuli and which are in l- l correspondence to the state variables, are taken as free outputs on that diagram. 24 The relations between these newly defined variables and the re- maining variables on the modified behavioral diagram are algebraic in nature and implicit in the diagram. The history- dependency has been removed by this technique, has become a meta-feature of the object not implicit in the loop structure. The history dependency will be re- incorporated only as the final step in obtaining the state- output relations. Examples of this instantization procedure can be seen in Chapter 111 when the state variables and dynamic variables are defined for the L,C elements of differential systems. _5_.__Z_. The streamlined behavioral diagram, the n- reducible loop structure, contains variables which can be classified into two types: free variables and bound variables. The free variables consist of the state variables and dynamic variables discussed in section 5. 1, along with the behavioral features of the object. When the behavioral diagram does not Show the environ- ment explicitly (the diagram of Figure 2 does not), those behavioral features can be recognized as the variables not requiring BDC's. BDC's will be required for these variables when the environment becomes explicit. The free variables are partitioned into inputs and outputsa- the behavioral features of the object as partitioned in the original basic orientation; and the remainder as discussed in 5. l. The bound variables consist of the behavioral features of the elements. They are all to be found on BDC'S since they enter into the relations of several elements. These variables will all be sup- pressed in the process of obtaining the desired relations and will not appear in the final results. 25 2:3. An n-reducible loop structure contains (at least n) 'feedback loops' of dependency in which bound variables can be found to depend on themselves. A streamlined behavioral diagram which is free from loops of that nature will be called a path structure. The oriented be- havioral diagram of Figure 2 is a path structure. It is shown in Appendix C that an optimal n can be determined for every loop structure, such that 11 variables can be found and used as discussed below in order to reduce the diagram to a path structure. A method is developed, also in the appendix, for finding the set of n vertices to be used for that reduction. The systematic procedure for obtaining the state- output relations for an object from the loop structure is given below in two phases. 5. 3. 1. Phase I of the solution procedure involves finding expres- sions for the bound variables in terms of the free input variables, a process which requires three steps when the degree (n) of the loop structure is non-zero. Step 1 entails reducing the loop structure to a path structure. Given an optimal set of n vertices, each vertex is split conceptually into a 'temporarily-free' input and a 'temporarily-free' output. In step 2, the path structure is analyzed by concatenation of the indicated operations along each path in order to obtain an expression for every bound variable, sequentially along the paths, in terms of the free and temporarily- free inputs. Finally the temporarily- free outputs are determined in terms of the free and temporarily- free inputs. All other bound variables have been suppressed during the course of this process. In step 3 the n temporarily- free outputs are equated to their cor- responding temporarily- free inputs. The resulting n simultaneous 26 algebraic equations can be solved to determine the final 11 bound var- iables as expressions in terms of the free inputs. 5. 3. 2. Phase II of the solution procedure involves finding ex- pressions for the free outputs in terms of the free inputs. Again the method involves concatenation of operations along paths of the behavioral diagrams, in this case making use of the expressions for the bound variables obtained in Phase I. Some of the expressions obtained in Phase II are the relations for the output behavioral features of the object. These expressions are given in terms of the state variables and stimuli, the desired form. The remainder of the expressions give dynamic variables in terms of the state variables and stimuli; once the state/state- change history- dependency information is incorporated in this set, they be- come the state- change equations in the desired form. 5. 3. 3. Since the behavioral diagram of Figure 2 is a path struc- ture, the results of Phase I for that object can be determined quite simply. Those results are given in equations (2). v3 = - v5 + 4V6 4v (2) V4 = 6 The results of Phase II for that example are given in (3). Notice that the object is instantaneously determinate, thus no state-change equations are involved. 2 v2 — 2vl -l-v5 (3) Figure 3 and equations (4) describe that system after a slight modification. The behavioral diagram of Figure 3 is now a l-reducible loop structure. 27 Figure 1.1-3: A l-Reducible Loop Structure Z+2v -v f1: (VI’Vz) 3 4 = 0 f2: v3 - v4 + v5 = 0 (4) f3: v4 - 4V6 = 0 Splitting vertex v4 into an input and an output (v4i, v40), the dia- gram yields the following relation. v =(v-v)2+2v.-Zv (5) 4o 1 2 41 5 After v40 and v4i are equated in (5), the results of Phase I for this system become: v v-(v 3 5 1 2v ( -v )2 v4 5 ' v1 2 -v2)2 (6) Using the results in (6), Phase 11 yields the final results for the be- havioral relations of this system as given in (7). v6 = v5/2- (VI-V2)2/4 (7) CHAPTER III STATE-OUTPUT EQUATIONS FOR DIFFERENTIAL SYSTEMS-- A SPECIALIZATION OF THE GENERAL METHOD 1. Introduction This chapter presents a specialization of the general method for obtaining the behavioral relations for a system, described in Chapter II, to the special case of differential systems. The treatment is limited to a restricted class of differential systems in the interests of keeping the dissertation reasonably compact. The methods of differential systems have a very broad range of application. Forrester [24] , for example, has applied such models to diverse problem areas. That his work is both topical and contro- versial can be seen in the IEEE Transactions on Systems, Man and Cybernetics; Volume SMC- 2; April 1972 issue which is devoted en- tirely to a set of papers which furnish critiques, and extensions, of the applications of his models. The terminology to be used in this dissertation is fairly standard for electrical network theory. Many results and techniques have been adopted from linear graph theory, the terminology of which is that of Seshu and Reed [57]; with some exceptions which are described in Appendix B of this dissertation, and which were adopted to yield a pleasing and useful symmetry of notation. 28 29 2. Linear Graph Representations of Differential Systems It will be assumed that the differential systems under investiga- tion are represented by oriented linear graphs as discussed in Chapter 5 of [57] . In this conventional representation every component ele- ment of the object will be represented by an edge of the system graph. If the object in question has n ports (n+1 'terminals') the environment also must have 11 ports. Every port of the environment is represented by an edge of the system graph. _Z_._l_. Let the graph of the object be understood to consist of: a. rne edges; b. mv vertices. Then n+1 of the mV vertices are junction points at which connections will be made to the object's environment. That subset of vertices will be known as terminals. The graph of the system, the interconnection of the object and its environment, has the following numerical properties: C. Edges: n = m + n e e d. Vertices: n = m v v (1) 60 Rank: I1 = m - 1 c v f. NullIty: nt = me - mv + n + 1 Notice that these numerical properties convey an underlying assumption. Consistent with the treatment in Appendix B, the graphs under consideration in this chapter are non-separable. _2;_2_. A complementary pair of variables is associated with each edge of the graph. For the jth edge they will be represented by: a. An across-type variable: vj; b. Athrough-type variable: ij. 30 In the terminology of Bond Graphs (see Chapter VIII herein), the variables are termed ”effort" and ”flow" , respectively. These vari- ables, for some of the differential systems of interest, are taken to represent respectively: a. Electrical Networks: Electric Potential, Current; b. Mechanical Rotation: Angular Velocity, Torque; c. Mechanical Translation: Linear Velocity, Force; (1. Fluid Transport: Pressure, Fluid Flow; e. Thermal Transport: Temperature, Heat Flow. _2_=_3_. The Kirchhoff Current Law (KCL) and Kirchhoff Voltage Law (KVL) are the relations which must be used to investigate the topological constraints on the system. Those laws can be related to the Cut-Set Array (CSA) and Tie Set Array (TSA) of Appendix B for the oriented graphs under consideration. In the appendix those arrays contained unsigned entries. Signs will be assigned to those entries in this section, and their subsequent use in this chapter will assume that assignment. £_3__1. Every row vector in the CSA (ignoring the rows which represent unions of edge-disjoint cut sets) can be used to represent one cut-set equation (one KCL equation) for the system. There exists a unique Gaussian surface which separates the vertices of the graph into two subsets. The edges represented by 1's in that row vector form the unique set which pierce the surface. The edges which are oriented inward through the surface will be assigned a positive sign; the outward oriented edges a negative Sign. The choice is arbitrary, and can be changed from row to row. 31 Then, if_i is the column vector consisting of the through variables associated with all of the edges of the graph, the set of all KCL equa- tions for the system can be written as: [CSA]: = 2 <2) _2._3._§. Every row vector in the TSA (ignoring unions of edge- disjoint tie sets) can be used to represent one tie- set equation (one KVL equation) for the system. The edges in each tie set (loop, circuit) form a path which is closed upon itself. As the path is traversed through one complete cycle, the edges which are oriented in the direc- tion of travel are assigned positive signs; the edges oriented opposing the direction of travel are assigned negative signs. Once again the choice is arbitrary and can be changed from row to row. With those assignments completed, and with X representing the column vector consisting of the across variables associated with all of the edges of the graph, the set of all KVL equations for the system can be written as: [TSA]: = 2 (3) 3. The Elements and Variables of the Behavioral Diagrams for Differential Systems The conventional background has now been outlined for differen- tial systems. As the nature of the elements to be used as the basis for the system models is established, further traditional techniques will be employed as needed. _3_.l. The objects to be considered will be constructed from two- terminal component elements. Those elements will be considered in two classes. _3_._1;_l_. Instantaneously determinate elements are those for which the constraining relations on the behavioral features do not 32 involve history dependency. Three of these elements will be con- sidered: a. The dissipator, R, so named since in power-flow sys- tems this element dissipates energy. Its behavioral features are constrained by: vj = inj(ij) (4) b. The across-type source, V, whose through variable is arbitrary but whose across variable is given by: vj = Vj (5) c. The through-type source, 1, whose across variable is arbitrary but whose through variable is given by: i. = I. (6) 3. l. 2. Memory elements are those for which the constraining relations on the behavioral features involve history dependency. There will be two elements in this class: a. The across-type memory element, C, whose instan- taneous behavior is constrained by a relation of the form: . d b. The through- type memory element, L, whose instan- taneous behavior is constrained by a relation of the form: d . . vj : EE{1ij(1j)} (8) 3. 2. The topological constraints imposed on system behavior by the interconnections of the component elements will be incorporated in the behavioral diagram through the use of three structural elements. 33 3. 2. l. A cut-set structure (CS) is an element which represents one KCL constraint on the system. This structure gives a graphical representation of one particular row of (2). iii. A tie-set structure (TS) is an element which represents one KVL constraint on the system. This structure gives a graphical representation of one particular row of (3). 1.3;}: The behavioral direct connection (BDC) is a vertex of the behavioral diagram, a junction of lines terminating on various of the other elements of the diagram. The BDC has the very interesting property that either: a. Exactly one of its lines represents the through vari- able of a system edge; each of the remaining lines terminates on a different CS; - or - b. Exactly one of its lines represents the across vari- able of a system edge; each of the remaining lines terminates on a different TS. Thus the BDC's can be partitioned into two sets, those which appear with the CS's and those which appear with the TS's. Moreover each BDC can be assigned the name of the single system variable associated with it. And all behavioral features to be discussed can be found on BDC's in the diagram. 2g. There are two levels of behavioral features associated with the behavioral diagram of a system. Each element has its own behavioral features; as does the object, and the environment. 3. 3. l. The behavioral features of a component element are the pair of complementary variables associated with the edge which repre— sents that element in the linear graph. The set of all such behavioral features can be found on a subset of the BDC's. 34 3. 3. 2. Due to the nature of the BDC's, there are no separately naIned behavioral features on the diagram for any of the structural elements. These elements merely embody the topological constraints of the system as they are imposed on the behavioral features of the component elements and the environment. 3. 3. 3. It has been implied that the environmental behavioral features will be Shown explicitly. Each of these features is connected, through a BDC, to either a CS or a TS element. These features can also be viewed, after a slight conceptual adjustment, as the behavioral features of the object. That adjustment will be made in Chapter V in connection with the selection of alternative sets of behavioral features for the object. Otherwise they will be treated as being associated with the environment in this dissertation. _3_._'_1_. The state variables and dynamic variables for the system will each be directly associated with an energy storage component of the system. When the jth edge of the graph represents such a memory element, one or the other of the following pairs of variables will be assigned to that element: a. A long- term state variable, xj, and a rate- of- change dynamic variable, rj; b. A short-term state variable, 3]., and an accumulation dynamic variable, aj. The assignment of these variables will be accomplished at the time the behavioral diagram is streamlined, to be discussed in section 7. The defining history- dependency relations between these variables are given by: 35 r - 51x j — dt 5 (9) a. 2 It 8. J J A more extensive discussion of these variables will be found in Chapter IV. 4. Constructing Behavioral Diagrams for Differential Systems Starting from the linear graph representation of the system, a form in which all of the topological information is readily available, it is the goal in this section to construct a representation specific to some subset of information sufficient to completely specify all con- straints. This is the first step of a process in which the ultimate purpose is to obtain expeditiously a quantitative description of the system's behavior. .441: It is a well-known fact that nC linearly independent KCL equations are required to specify the relations among all through variables of the system. Although any linearly independent set may be used, by representing their associated rows of (2) by CS's, the best procedure is to select the fundamental set, Fc' associated with some tree of the graph. When such a cut-set structural tree is used it will be denoted CST. The examples to be presented in this chapter will illustrate some of the problems which arise when non-fundamental sets are used. 4:2. It is also well known that nt linearly independent KVL equations are required to specify the relations among all across vari- ables of the system. When the fundamental set, Ft’ is used to select the rows of (3) which are to be represented by TS's, its associated tie-set structural tree will be denoted TST. 36 It is possible to select TST as the same tree used for CST. When this is done, the structural tree will be denoted ST. _’-1_._§_. It is usually desirable, when drawing a behavioral diagram, to split a BDC into several pieces in order to make the appearance of the diagram neater. Those several pieces taken together form the one conceptual BDC. The separate pieces can be recognized as part of the one BDC in that they all bear the designation of the single edge variable associ- ated with that BDC. That splitting process is implied in the following rules for constructing behavioral diagrams. 4. 3.1. Draw separate shapes (boxes, perhaps) for each system edge (component elements and environment edges) aligned down the center of the page. At each shape: bring out an across variable on the left, a through variable on the right, and label each. m. Draw a separate shape for each TS down the left side of the page. Bring out and label the nj across variables which are con- strained by that tie-set equation, indicating within the shape the Sign assigned to each variable in that equation. :1_3__§. Draw a separate shape for each CS down the right side of the page. Bring out and label the nj through variables which are constrained by that cut-set equation, indicating within the shape the sign assigned to each variable in that equation. 123:3. Connect each set of variables, those with the same labels, with a BDC. 3:123. Indicate within each shape the constraints imposed by that element; alternatively, label each shape to correspond with a separate list which states those constraints. 37 113.2- A behavioral diagram will be constructed for the system whose linear graph is shown in Figure l. The edge descriptions for the system are as follows: a. Edge 1 - an across-type source; b. Edge 2 - an across-type memory element; c. Edge 3 - a through-type memory element; d. Edge 4 - a dissipator; e. Edge 5 - the environment edge. Figure 111-1: The Linear Graph of the System Selecting the set of edges (2,4, 5) to be the branches of ST the subset of rows of (2) which can be written [Fc]_i_ = 2 become: 110 o o o 0110 _i.=_°. (10) 10 1 01 Also using ST in the determination of the fundamental tie sets, those rows of (3) which can be written [Ft]! = 2 become: 1-10 0 - [:0 o 1 -1 411:9 (11) Figure 2 shows the behavioral diagram for the system which in- corporates (10) and (11). It represents, of course, only one of the many behavioral diagrams which could be drawn for the system. 38 Figure III-2: A Behavioral Diagram for the System 5. Basic Orientations for Elements and Systems With the definitions of the elements having been established for differential systems in section 3, the set of all possible orientations of those elements must be investigated in order to establish the subset Which can qualify as~ basic orientations. The properties given in 11-4. 3 must be applied to establish that qualification. Those rules are listed here and will be referred to by letter designation in the ensuing. The orientation of an element is basic if: a. Its behavior is causal; b. Its behavior is not stimulus-constrained; c. The orientation is minimal- output. When an orientation is imposed on a system, the Zn behavioral features of the object are partitioned into a set of inputs and a set of 39 outputs. The set of inputs to the object will be grouped to form a column vector, u. The set of outputs from the object will form the column vector, y. A specific orientation of a behavioral diagram, in terms of the partition of the behavioral features, will be denoted by listing the ordered pair of transposed vectors; with inputs followed by outputs: i. e. , (uT; yT). For a component element oriented with its through variable as the input, that designation would be (ij; vj). Es}; The results for the component elements will include a behavioral diagram for each element in each basic orientation. The output equation will be given for that orientation, as well as the dynamic equation when applicable. (The dynamic equation gives the relation between the dynamic variable and the input variable for a memory element. ) 5. l. 1. For the dissipator: If both variables are taken as inputs, property b. is violated; if both variables are taken as outputs, proper- ties a. and c. are violated. Only two possible orientations remain. Both of these are 'complementary' in that one of the pair of comple- mentary variables is taken as an input and the other as an output. Behavioral diagrams are shown for both basic orientations of the dis- sipator in Figure 3. a. (v;i) Orientation b. (i;v) Orientation Figure III-3: Basic Orientations for the Dissipator The output equations which correspond respectively to the basic orientations of Figure 3 are given as: 40 If: f(i) :: iR(i) then a. i = I'l(v) (12) and b. v = f(i) §_,_1._2_. For the source: If the arbitrary variable is taken as an output, property a. is violated; if the 'specified' variable (the across- type variable for the across-type source, for example) is taken as an input, property b. is violated. Only one possible orientation remains for each source; in each case it is one of the possible complementary orientations. Figure 4 shows the sole basic orientation for each type source. 1. v. v. i. J J v3. 9—0 0% I). F>——o a. Across-type Source b. Through-type Source Figure 111-4: Basic Orientations for the Sources The respective output equations for the sources are: _5;1_._3_. For the memory element: If both behavioral features are taken as outputs, properties a. and c. are violated; if both be- havioral features are taken as inputs, property b. is violated. The remaining possibilities are the two complementary orientations. Figure 5 shows both basic orientations for an across- type memory element; Figure 6 the same for a through-type memory element. 41 . V. r>—-OJ (ij;vj) Orientation i. ‘ Cj jE 1 Cj [5' OJ ;ij) Orientation a. b. (v. J Figure III-5: Basic Orientations for the Across-Type Memory Element The output equations for these basic orientations become respec- tively: If: then and v. 1 L. 3-. f(v) = vC(v) _ -1 vj — fj (xi) 1. = S. J J i. J fj(vj) ,_._J__J, (vj;ij) Orientation L. (14) (15) V. >—<>J J b. (ij;vj) Orientation Figure III—6: Basic Orientations for the Through- Type Memory Element The output equations associated with Figure 6 become, for the respective basic orientations: If: then f(i) = iL(i) . -l lj fj (xj) v. = s. J J (16) 42 While the dynamic relations are given respectively by: a. r. = v. J J (17) and b. a. = f.(i.) J J J Notice that state variables and dynamic variables have been assigned to these memory elements in Figures 5 and 6. That assign- ment is not performed conceptually until the diagram is to be strearn- lined. That assignment constitutes the mechanization of the process of instantizing the memory elements, the discussion of which is de- ferred to section 7. Although the orientation of such an element does not require the assignment of these variables, they are shown here in the interest of economy. Separate diagrams will not be repeated in section 7. Notice also that part b. of both Figures 5 and 6 presents an orientation in which the respective memory element is not recognized as exhibiting history- dependent behavior in current systems analysis practice. The contention that it does exhibit such behavior is a prin- cipal theme in this dissertation. i2. Investigation of the nature of the structural elements for differential systems also yields a restricted set of basic orientations for those elements. 5_=_2_._1_. For the CS and TS: If all of the nj incident variables (the variables associated with the edges represented by non- zero en- tries in the particular row from (2) or (.3) under consideration) are taken as inputs, property b. is violated; if two or more of the variables are taken as outputs, properties a. and c. are violated. Thus each such element has exactly nj basic orientations. They are the ones which satisfy: 43 a. Exactly one variable is an output; b. The remaining (nj-l) variables are inputs. ELL—2. For the BDC: If all of the nj variables incident upon the BDC are taken as outputs, properties a. and c. are violated; if two or more of the variables are taken as inputs, property b. is violated. Thus each BDC has exactly nj basic orientations. They are the ones which satisfy: a. Exactly one variable is an input; b. The remaining (nj-l) variables are outputs. _5_.__3_. The orientation for the object and for the system is guaran- teed to be basic if, in the system's behavioral diagram, the orientation of every element is made basic according to the foregoing rules. That follows from the fact that, through the satisfaction of the requirements on the BDC in 5. 2. 2, the consistency requirement of 1.1-4. 3. 2 and II- 4. 3. 3 is automatically met. 6. _AfiProcedure for Establishing an Initial Basic Orientation for a Behavioral Diagram Constructing behavioral diagrams for differential systems has been seen to be a straightforward procedure. The next step to be taken in the quest to obtain a quantitative description of a system's be- havior is to impose a basic orientation on that diagram. This step will establish an input/output partition on the object's behavioral fea- tures--will select the dependent and independent variables to appear in the system's behavioral relations--but will establish a different partition as well. The orientation of a behavioral diagram requires the orientation of every element in that diagram. It was implied in section 5. 1. 3 that . VI: not iii in In L” 44 the orientation of a memory element imposes the selection of a particu- lar type of state variable to be associated with that element during the instantization step in the procedure for streamlining the behavioral diagram. Thus a particular orientation of a behavioral diagram also imposes a partition on the state variables for a system; into a set of short-term state variables and a set of long- term state variables. It is possible to derive a basic orientation of a behavioral dia- gram by orienting each element in the diagram one at a time, while ob- serving the rules established in section 5. Quite often, in following such a procedure, an impasse is reached and earlier work must be changed. Fortunately a more orderly procedure can be established for this purpose. This will be accomplished through an investigation of some very interesting properties of basic orientations of behavioral diagrams. _6_.__1. Structural elements impose some numerical necessary con- ditions on basic orientations for systems. §_.__1._l. Exactly nt system edges must be oriented with across variables as inputs, and the remaining nC with across variables as outputs, in order for the system's orientation to be basic. £3391: Clearly at least n must be inputs: each TS has one output which pro- 1: vides the one input for a particular BDC; all other connections to that BDC must be outputs, including the one which becomes the input to a unique system edge. Since that exhausts the supply of TS outputs, the remaining nc BDC's on the TS side of the behavioral diagram must receive their inputs from the remaining nC system edges. 6. 1. 2. Exactly nc system edges must be oriented with through variables as inputs, and the remaining nt with through variables as 45 outputs, in order for the system's orientation to be basic. m: The proof is similar to that of 6. l. 1 with attention focused on the CS side of the diagram. _(_>_._2_. The use of trees of the graph is sufficient for the satis- faction of the numerical restrictions of 6. 1. First observe that every tree of the system graph has nC branches, its companion cotree con- tains nt chords. 6L2. Select some tree of the system graph (to be called the tie-set orientation tree, TOT) in order to orient the TS side of the diagram. The system edges which are branches of that tree will be oriented with across variables as outputs; the remaining edges (the chords of the cotree) will be oriented with across variables as inputs. This procedure satisfies 6. l. 1, thus guarantees that the orientation of the TS's and the tie-set BDC's will be basic. _6_._Z__Z. Select some tree of the system graph (to be called the cut-set orientation tree, COT) in order to orient the CS side of the diagram. The system edges which are branches of that tree will be oriented with through variables as inputs; the remaining edges will be oriented with through variables as outputs. This procedure guarantees that the orientation of the CS's and the cut-set BDC's will be basic. _6__2_3. Under certain conditions (complementary partitions of the object's behavioral features) it is possible to select for COT the same tree selected for TOT. When this is done the tree will be re- ferred to as the orientation tree, OT. Its use will satisfy 6. l. 1 and 6. l. 2 simultaneously, and thus guarantee that the orientations of all structural elements will be basic. 46 é__2._4_. Although the procedures are conceptually separate, it is normally desirable to construct the behavioral diagram and orient it on the basis of the same tree (or same two trees). That procedure will prevent the appearance of certain problems which will be illustrated in the examples. 6:3. Component elements also impose restrictions which must be satisfied in order for the orientation of the behavioral diagram to be basic. 2L1. The available basic orientations for sources impose the following conditions for the selection of trees in 6. 2: a. Each across-type source must be selected as a branch of TOT, and as a branch of COT; b. Each through-type source must be selected as a chord in the companion cotree for TOT, and also for the COT. _6__3_£. For all of the component elements other than sources, it was seen in 5. l to be sufficient that their orientations be comple- mentary in order to be basic. To insure this, it is necessary that any such element chosen as a branch of TOT also be chosen as a branch of COT; and that any element chosen as a chord in the companion cotree for TOT be chosen similarly in the selection of COT. When OT is used this condition is satisfied automatically. 6:4. A final condition can be stated in terms of the environmental edges of a system. The condition is necessary in order for the orien- tation of the behavioral diagram to be basic. While it is sometimes convenient to suppress (ignore) certain output variables in the analysis of a particular system (for instance, 47 when those variables are the arbitrary variables for a set of sources and not of direct interest in the analysis), let it be agreed that those variables do exist. Then, define an 'even partition' of the behavioral features of an object as one in which the number of input variables is equal to the number of output variables. The property can be stated as: If the orientation of the behavioral diagram of a system is basic, then the partition iInposed on the be- havioral features of the object by that orientation is even. The M of that property is given in the following. 2:12.21: Notice that the basic orientations of all elements (both structural and component) can be considered to be 'even' in the sense that a redesignation of one variable of any such element from input to output (or vice- versa) requires the complementary redesignation of another variable of that element. Thus, given a basic orientation for a system, if a reorientation procedure be started by redesignating some one environmental edge variable from input to output (or vice- versa), that process cannot terminate on any element but must con- tinue until another enviromnental edge variable is redesignated. Furthermore, by the numerical necessary conditions of 6. 1, the nuIn- bers of inputs and outputs on both sides of the diagram must remain unaltered by that overall procedure. Therefore, if there exists a basic orientation of the system in which the partition is even, then all basic orientations of the system must have even partitions. _t_>_._:1_._2_. A basic orientation can be constructed by use of the OT as in 6. 3. 2 which, when the numerical restrictions in 6. l are considered, 48 can be seen to have the even partition of behavioral features as re- quired in 6. 4. 1. Thus the property must hold. 212. Notice that there is no explicit requirement in the fore- going that would require the orientation of environmental edges to be complementary. And the variables of the environmental edges are, of course, the port variables for the object. Therefore, as a con- sequence of this property, it is necessary only when n=l (when dealing with l-port, or two-terminal, objects) that the port variables be assigned complementary partitions, and not necessary when n > 1. This property has long been known to systems analysts who deal with the transmission parameters of n-port systems. _6_._§. A basic orientation will be derived for the example system of section 4. 4. The behavioral diagram was shown in Figure 2 for that system. Selecting the set of edges (1, 3, 5) to serve as the branches of OT, the resulting basic orientation is shown in Figure 7. .__J , CS v1 60v“ + TS - 7- e. v i I 90* 2 v L—zO->Cz .9. It - v i 4 4 flags..— F ' i . . CS v 1 1 Figure III-7: A Basic Orientation of the Behavioral Diagram 49 é__._6. The use of trees has been shown to be a sufficient pro- cedure in order to derive basic orientations for behavioral diagrams. An example will be given here to demonstrate that that procedure is not necessary; i. e. , there exist basic orientations which are not based on trees. The example will be continued in section 7 to illus- trate some problems which can arise in association with this alterna- tive method. _t_>__6__1_. Consider a system represented by the linear graph of Figure 8. Let the description of the system edges be as follows: a. Edges 1 and 6--Environment edges; b. Edges 2 and 3--Across-type memory elements; c. Edges 4 and 5--Through- type memory elements; (1. Edges 7 and 9--Dissipators; e. Edge 8--Through-type source. Figure 111-8: The Linear Graph for the System 6. 6. 2. A linearly independent set of tie-set equations can be selected from which to construct the TS elements. They are: —1 0 1 -l 0 0 -l 1 0 0 -1 0 0 -1 1 0 0 -1 0 l -l -1 _v_ = _O_ (18) OOOH OOI-IO OHOO 50 Those tie-sets do not constitute a fundamental set since they are not associated with any tree of the graph. Similarly, a non- fundamental set of linearly independent cut-set equations can be selected from which to construct the CS elements. Theyare: l 1 O l O O O 0 (J.-1 l 0 l O 0 -1 0 O 0 O l -1 0 -1 O O O O l :2 (19) O O 0 l O O -1 -l O O O O O 1 O O l - 1).. 1.1 é__6__3. Once the behavioral diagram has been constructed on the basis of (18) and (19), it can be oriented on the basis of a set of edges selected in such a way as to satisfy the numerical constraints of 6. 1. The set of nt edges (4, 5,6, 8) and the set of nc edges (1, 2,3, 7,9) were used to orient the diagram. The resulting basic orientation is shown in Figure 9. 7. The Algebraic Reduction of Behavioral Diagrams Oriented behavioral diagrams, in Chapter II, were seen to be flow diagrams in which the flow is one of functional dependence. These diagrams can be streamlined in order that the dependence will become more apparent. The streamlined diagrams can then be processed in order to obtain the desired behavioral relations. _7_._1. The two goals to be attained in streaInlining behavioral diagrams are as follows: a. To cause the behavior of the object to be instantane- ously determinate in terms of its inputs and some sufficient set of state variables; b. To isolate the inputs--variables which exhibit no in— stantaneous dependence on any other variables of the o a “ O OQ O m “ O O 51 Nwow 0% IVOMN W a w i w." H m> ¥ S em W03, _) w 1 mg m0 1 $9 + NW f . - Abdul k - wU + W3“ > + + A OHM T o> WM. + e. in] mo +.A..Ow.. + 52 system--and the outputs-~variables which impose no instantaneous dependence on any other system variables. _7__._1_.1. The first goal will be attained by the instantization of all memory elements contained in the system. This procedure is very important to the central concept of this dissertation, a unified treat- ment for the history dependency of differential systems. Since the concept comes under discussion in Chapter IV, it will be acknowledged here only through the following: Postulate: Every memory element in a differential system, irrespective of that element's orientation (sub- ject only to the restriction that the orientation must be basic), can be instantized to remove the element's history dependency as a feature of the oriented behavioral diagram in which it appears. The method by which instantization will be accomplished represents the extension of a known teclmique from systems analysis. Kuo [35] presents a method, which is useful only for 'proper' systems, in which all across (through)-type memory elements are re- placed by across (through)-type independent sources in the process of obtaining the behavioral relations for a system. Tapai [61] has sug- gested an extension of that technique, which is valid for 'improper' systems, in which certain of the across (through)- type memory ele- ments must be replaced by across (through)- type controlled sources. The method to be used here is equivalent to the replacement of a memory variable of either type by an independent source of either type; the choice can be made as a matter of convenience. This flex- ibility is possible upon adoption of the concept of short-term state variables . 53 An inspection of (7) and (8) reveals that there is no instantaneous relation between the behavioral features of a memory element. That is, given a value for the through variable at some instant in time, there is no means available for determining the value of the across variable at that same instant; it can assume arbitrary values. That same lack of a constraining relation between the behavioral features is a characteristic of the source. All of which explains the rationale behind replacing memory elements by sources in the process of instantizing a system. The procedure for instantizing a memory element will be mech- anized by appending a dynamic variable and a state variable to that element, as illustrated in Figures 5 and 6; the particular variables to be used will depend upon the element's orientation. The instantaneous relations among the variables are then given in (l4)-(l7). M. The second goal is easily attained. The nature of the sources is such that there are no constraints between their behavioral features; their specified variables serve as inputs to the relations for the system, their arbitrary variables are outputs. Under the general manner in which the environmental edges are used here, there are no constraints implied for their behavioral features. They have pre- viously been partitioned into inputs and outputs in the establishment of a basic orientation for the system. Thus the free variables on the streamlined diagram consist of: a. Inputs: State variables; specified source variables; and the set of inputs from the partition of the object's behavioral features; _.-._ 54 b. Outputs: Dynamic variables; arbitrary variables for sources; and the set of outputs from the partition of the object's behavioral features. 342. As part of the streamlining process, the linear constraints imposed by the oriented TS and CS elements will be represented by the traditional triangular symbol used to denote an adder. The BDC's will each be a single vertex point on the diagram. 7. 1. 4. An interesting observation can be made at this point. . _ A When the behavioral diagram is constructed and oriented on the basis of the same tree (or trees), there is a strict correspondence between the behavioral features of the memory elements and the dynamic and state variables of those elements. The state variables serve as direct inputs to one set of those features, and as the only such inputs; the complementary set of features serve as outputs only to the dynamic variables--they impose no dependence on any other system variables. Due to this direct correspondence with free variables, the memory element behavioral features themselves can be considered to be free variables. As a consequence of that observation, the set of all bound vari- ables on a streamlined behavioral diagram which was structured and oriented on the basis of the same tree (or trees) must consist solely of the set of behavioral features of the dissipators. 1L2. The computational procedure is to be accomplished as described in II-5. 3. The procedure consists of two phases. In Phase I, the bound variables are eliminated from the relations in terms of the free inputs. This procedure requires the solution of n simultaneous equations, when dealing with an n- reducible loop struc- ture, in order to eliminate n of the bound variables. 55 In Phase II, relations are developed for all of the free outputs in terms of the free inputs, utilizing the intermediate results from Phase I in that process. The general computational procedure to be used is the concaten- ation of functional operations along the various paths of the diagram. In the case of linear systems the entire procedure can be mechanized in terms of matrix operations. 1;. The expressions obtained in the computational procedure of 7. 2 can be grouped into three sets: a. Expressions which describe the behavior of the arbi- trary variables for the sources within the object; b. The relations which give the output variables, in the partition of the object's behavioral features, as expressions in terms of state variables, internal source elements, and the object's inputs. This set forms the actual output equations for the system; c. The remaining relations express the dynamic vari- ables in terms of the free inputs. When equations (9) are applied to these relations in order to re- incorporate the history dependency, these rela- tions become exactly the required set of state- change equations for the system. L4. A streamlined behavioral diagram will be produced from the oriented diagram of Figure 7, and a set of behavioral relations Will be obtained for the system described in section 4. 4. Figure 10 represents that streamlined diagram, with the arbitrary variable for the source having been suppressed as a free output. 56 Figure 111- 10: A Streamlined Behavioral Diagram for the System Under the assumption that the component elements of the system are linear, the State- Output equations can be obtained from Figure 10 and equations (9) as shown below. ftsz = C2(V1 - v5) (‘33 = L3(v5 - s3)/R4 (20) i5 = 82 + (83 - V5)/R4 This example does not meet the restrictions stated in the obser- Vation of 7. l. 4, in that the behavioral diagram was constructed and oriented on the basis of different trees. As a result the memory ele- ment behavioral feature 13 cannot be regarded as a free variable of the 8treamlined diagram. It imposes a constraint on the output variable is. in addition to its intended use in the determination of the dynamic variable a3 . 7. 5. The streamlined version of the oriented behavioral diagram, shown in Figure 9 for the system of section 6. 6, will illustrate 57 another problem which can be avoided by orienting behavioral diagrams on the basis of a tree. The construction of that behavioral diagram was performed on the basis of non-fundarnental sets of equations. The added flexibility, caused by the redundancy among the variables appearing in those equa- tions , permitted a basic orientation to be achieved through the use of a partition of the graph edges which, while numerically sufficient for the task, was not associated with a tree of the graph. Figure 11 presents the streamlined diagram, derived by the method of 7. 1. Inspection of that diagram reveals that the state- Output equations cannot be obtained directly from the diagram because 0f a. linear dependence which exists among the output variables (i1, i2, i3), and another among the output variables (v4, v5, v6). In order to Obtain results, it would be necessary to consider one of the variables in each set as being externally specified (i. e. , treat it as an input), in order to obtain expressions for the remaining variables in terms of the specified one. Those linear dependencies are present due to the existence of Certain well- known topological conditions which can be seen on the linear graph of Figure 8: 3 a. There is a tie- set containing only edges (1, 2, 3); b. There is a cut-set containing only edges (4, 5,6). Those topological dependencies prevent the existence of a tree which WOuld yield the orientation containing those combinations in the parti- tion of output variables. And thus, if a tree is used in the orienting °Peration, such linear dependencies will never arise in the relations ixnplied by the oriented behavioral diagram. 58 Ecumam 05. n3 gummwfl Wuoymgom podflfidouum < J a Ia unamah 59 8. The Attainable-Minimum Optimal-n for an n-Reducible Loop Structure This section presents an important result which has not been available previously. The result involves the ability to obtain a quan- titative description for the behavior of a differential system with a minimum amount of work. The description obtained in this manner also has the property that the relations consist of algebraic expressions of minimal complexity when compared with the alternative forms. Appendix C establishes a technique for determining the optimal n for an n- reducible loop structure, and a method for selecting a set of n vertices appropriate to the task of opening all feedback loops in a streamlined behavioral diagram. In this section the attainability of a minimum such optimal n for differential systems will be established, and a method proposed for the selection of an orientation which exhibits that property. The n- reducibility of a behavioral diagram is a property of the diagram and not of the system. That is, n- reducibility is a variable feature of the system under alternative orientations. The necessity for solving n simultaneous algebraic equations in obtaining the behavioral relations for the system provides the motivation for the search for a minimum n. _8_;_l. The observation made in 7. 1. 4, which depends on the pos- tlllate in 7. l. l and the subsequent instantization of 211 memory elements, Provides the first intimation that a minimum optimal-n can be attained. Figure 12 presents a schematic diagram of a basic orientation 0btained for a differential system on the basis of a tree of the system graph. If the behavioral diagram has been structured on the basis of that same tree, then there can be no dependency loops contained within 60 the structural element boxes. That follows since, under the stated conditions, no output of any CS (TS) can provide an input to another CS (TS). Environment Branches Memory Element Branches Across Source Tie- Set Environment Cut- Set Structural Ch (1 Structural Elements or 3 Elements and and Memo ry Element Through Source Chords Dis sipator Branches Dis sipator Chords Figure 111- 12: Schematic Diagram of a System's Basic Orientation Inspection of Figure 12 thus reveals that, when the diagram is Streamlined, all of the boxes representing particular sets of edges of the system will be opened-~split into the free inputs and free outputs 61 for the computational procedure--except for the two bottom boxes which represent dissipator edges. The behavioral features of the lat- ter two sets of edges become the bound variables of the streamlined diagram, all other variables having been seen to be free variables in section 7. l. .§.:_2.° It is apparent from 8. 1 that the only loops (of algebraic dependency) possible appear in the computation by virtue of paths through the dis sipator variables. Thus the set of vertices to be broken during Phase I of the computational procedure will consist of vertices representing behavioral features of the dissipators. Furthermore, opening the paths either through the branch- set dissipators or through the chord- set dissipators will destroy all de- pendency loops. The method for determining an orientation which will yield a minimum optiInal-n must involve a search for orientations for which either: a. As few dissipators as possible are branches; -or- b. As few dissipators as possible are chords. The smaller number of those two will provide the minimum optimal- n. §__2__1. Sometimes trivial conditions exist which can cause the minimum optimal-n to be smaller than that discussed here. These conditions can easily be taken into account, but will be ignored in this discussion. In order that attention can be concentrated on the central problem, it will be assumed that the systems under considera- tion do not contain any dissipators which appear in: a. all of the tie-sets in which some particular through source, or some other particular dissipator, also appears; - or- 62 b. all of the cut-sets in which some particular across source, or some other particular dissipator, also appears. An example of a system for which this happens can be seen in Chapter VII. M. Current systems analysis practice utilizes an 321515 tree selection procedure in which the goal is to find a "maximal tree" as defined in Koenig et al [33] . When obtaining a maximal tree, the emphasis is placed on the location of the memory elements. The mechanization of the search for a minimum-n orientation represents a break with that tradition as the emphasis is placed on the location of the dis sipators. At first it might appear that a search must be undertaken through the set of all trees of the graph in order to find a minimum-n configura- tion. However, the resulting orientation must be basic, thus the con- ditions of 6. 3 must be satisfied by the tree (or pair of trees) which defines the orientation. The particular constraints of iInportance here are the ones imposed by the internal sources of the object. Those re- strictions limit the search to a particular subset of trees of the graph, those for which: a. All across-type sources are branches; b. All through-type sources are chords. The method developed in Appendix B for the generation of trees is particularly well suited for the generation of special subsets of those trees. That method will be assumed here, and only the pro- cedures surrounding its use will be discussed. 63 §.__Z_.__3_. Starting with an initial tree which meets the restrictions imposed by the sources, trees can be generated: and only those trees need be gene rated which meet those restrictions. Two lists of trees will be kept as the trees are generated: one list will contain trees with a maximal dissipator- edge content; the other with a minimal dissipator- edge content. As each tree is gener- ated, its dissipator content is compared with those of the two existing lists. That tree is then: a. Discarded if its content is between the limits; b. Added to the particular list which its content equals; c. Kept in place of the particular list whose content it exceeds (high or low, as appropriate); i. e. , the old list is discarded, a new list started. The procedure can be terminated when a tree is located which contains either all or none of the dis sipator edges as branches. At that point a zero- reducible loop structure can be constructed on the basis of that tree. In general, however, the final tree of the subset of interest will have been examined with no tree having been found to have full (or empty) dissipator content. Let the following definitions be established: nmax' the index for the maximal list, is equal to the number of dissipators contained in the system minus the number which are branches of each tree in that list; and nmin’ the index for the minimal list, is equal to the number of dissipators which are branches of each tree in that list. The mini- mum n-reducibility of the system then becomes: n = min{n (21) max’ nmin} Every tree in the appropriate list will define an orientation with that property. 64 _8_:_3_. One of the Kuratowski networks discussed in [57] , the fully-connected 5 vertex network, will be used in an example illus- trating the determination of a system's minimum n-reducibility. The linear graph for the system is shown in Figure 13, and its edge de- scriptions are the following: a. Edges 1, 2, 8 and 9--Dissipators; b. Edges 3 and 5--Across-type sources; c. Edges 4 and 6--Through-type sources; d. Edges 7 and lO--Memory elements. Figure 111- 13: The Linear Graph for the System Since the through sources cannot be taken in any trees of interest, their edges are dropped from consideration--treated as being non- existent. An initial tree is selected which contains the across sources, (1, 3, 5, 7): and the fundamental tie-sets are generated for the reduced graph, as listed in Table 1. Edge: 2 8 9 10 1 3 5 7 1 o o o 1 o 1 1 o 1 o o 1 o 1 o o o 1 o 1 1 1 1 o o o 1 o 1 1 1 Table III- 1: The Fundamental Tie-Sets for the Reduced Graph 65 The row vectors of the well ordered CSA which contain zero en- tries for the across source edges are generated on the basis of the information contained in Table 1. They are listed in Table 2. Edge:3517 28910 0 0 0 1 l 0 l 1 0 0 1 0 l 1 1 0 0 0 1 1 0 l 0 1 Table III-2: Rows from the Well-Ordered CSA The edge truth function, which will yield all trees containing the across sources and none of the through sources, is derived from the rows of Table 2. It is presented in (22) as one equation. {T} = e365[e1e7 + el(ez +e9+elo) + e7(e2+e8+69) + . . . +(ez+e9+e10)(ez+e8+e9)(e8+elo)] (22) In this example, all of the trees generated happen to belong to either the maximal content list (with n = 4 - 2 = 2) or to the minimal max content list (with nmin = 1). Those lists are given here with the edges to be taken as branches indicated parenthetically. Edges 3 and 5 are omitted for brevity. a. Maximal-content list: (1,2), (1,9), (2,8), (8,9); b. Minimal-content list: (1,7), (l, 10), (2,7), (7,8), (7, 9), (2, 10), (8, 10), (9, 10). For this system, the minimum n-reducibility is unity; any tree from list b. will yield an oriented behavioral diagram with that property. _8_._f1_. An example will be provided to illustrate the savings in labor which can result when a system is oriented according to a mini- mum-n tree rather than a maximal tree. The example also provides an illustration of the process of 'opening the loops' during Phase I of the computational procedure. 66 Figure 14 shows the linear graph for the system. Its edge de- scriptions are as follows: a. Edge l—-An across-type source; b. Edges 2 and 3--Across-type memory elements; c. Edge 4--A through- type memory element; d. Edges 5 and 6--Dissipators. Figure III- 14: The Linear Graph of the System A maximal tree is selected from the graph: T1 = (l, 2, 3, 5). A miniInum-n tree is also selected from the graph: T2 = (1,4,5, 6). The fundamental tie-set equations, the same in this example for both trees, are listed in (23). 1-100- 1 [o 01 1-1 o]l’=9 (23) The fundamental cut-set equations for T are given in (24). 1 1 o o o o -1 o o o . o (l) 1 -1 g (l) 3— :9 (24) o o o 1 1 1 The fundamental cut—set equations for T2 are given in (25). i e 2 (25) OOOH 1 HHOH I OHl-IO OOHO OHOO H000 Figure 15 presents the streamlined behavioral diagram derived on the basis of T1' Investigation of that diagram reveals a l-reducible loop structure. 67 1 . 1 1 1‘2an V + TS V R, 6-1 v i r 5 R5 .5 O 1 r 4. 3 Figure 111- 15: The Streamlined Behavioral Diagram from T1 Choosing v5 as the vertex to be opened, the 'temporarily-free' variables are defined to be v50 (the output) and v5i (the input). The loop equation can then be written from the diagram. v50 = R5(-v5i/R6 - xZ/CZR6 - 114/1.4 + Vl/Rb) (26) v5 can be determined from (26) by equating v50 and VSi‘ The re- sult, expressed in terms of free inputs, is given in (27). v5 = R5(-xZ/C2- R6x4/L4 + Vl)/(R5 + R6) (27) The free output equations can be determined from the diagram with the aid of (27) and a little algebra. When (9) is applied to those equations, the State- Output equations have been obtained for the system as shown in (28). - (-x2/C2 + R5x4/L4 + Vl)/(R5 + R6) "4/1‘4 — -x3/C3 + R5(.x2/cz - R6x4/L4 + Vl)/(R5 + R6) 11 -_- (xZ/Cz - R5x4/L4 - Vl)/(R5 + R6) N N I (28) senese x w (I N .p. I 68 Figure 16 presents the streamlined behavioral diagram derived on the basis of T2. Investigation of that diagram reveals a path struc- ture, free of loops. V l + 8 1 v V 32 2 - cs R6 + TS 2 C2 90 + i v 3 CS 5 R5 5 + v3 a3 3 - ,4 TS <33 r—>O i a 4 + cs 4 L4 90 Figure III- 16: The Streamlined Behavioral Diagram from T2 The equations which give the free outputs in terms of the free inputs can be determined easily from that path structure. After the application of (9) to those equations has reincorporated history de- pendency, they become the State- Output equations of (29). t f 52 _ C2(-(R5 + R6)82 + R583 + V1) t _ f 83 — C3(R582 - R533 - 34) t (29) f 84 = L«133 11 = '92 This example illustrates the savings in work which can occur When a minimum-n tree is used in the process of obtaining the quantita- 1iive description for the system's behavior. A comparison of (28) and 69 (29) also reveals the greater algebraic simplicity of the latter descrip- tion. Several more examples will be presented in subsequent chapters to illustrate the benefits which can be gained from the use of alternative description forms. In those examples, as in this one just completed, the availability of the alternative forms is contingent upon the accep- tance of the concept of short- term memory. CHAPTER IV THE CONCEPT OF SHORT-TERM STATE VARIABLES 1. Introduction Let this chapter be opened with a viewpoint: the size of the state space of an object should be an invariant property of the object. It should not be subject to variations caused by such irrelevant conditions as the object's prevailing orientation. This viewpoint, founded on a strong intuitive sense of propriety, is not compatible with the current practice of differential systems analysis. Resh [52] has shown that for each basic orientation of any ob- ject there exists a state description of that object. It is also known that many aspects of the object's stimulus-response behavior, includ- ing properties of the state descriptions of that behavior, vary from one basic orientation to another. One of those properties is of par- ticular importance in the formulation of the short- term state variable concept. The size of the state space of an object should be a basic measure of the object's capacity to respond to its past experience as well as to present events. Clearly this capacity is a property of the object it- Self. Thus, since the choice of orientation is made at the whim of the Observer--assuming that the general notion of descriptions has been Properly framed-nit follows that the size of the object's state space Should not vary from one basic orientation to another. 70 71 The introduction of short-term state variables serves as a uni- fying concept in the treatment of history dependency in the behavior of differential systems. It permits the size of an object's state space to be viewed as an invariant property and, in so doing, provides relief to the outraged intuition. 2. State Efluations and Problematicaléystems It is frequently assumed that the most general form of the State- Output equations for a differential object is: dx —- f(x, u, t) Y gm. 11. t) in which u and y are the stimulus and response vectors for the given basic orientation and x is the state vector. It has long been known that this isn't strictly true. Zadeh and Desoer [64] , for example, pointed out that for "improper systems" it is necessary either to re- sort to "hybrid state equations" of the form: 3%: = fbt,U,t) (2) Y = ga‘susfisfis 0 0 0s t) or to decompose the system into a "proper part” and a ”differential operator part"; the state variables for the former being x, for the latter to be defined by: T .T T s =(u ,fi , . . . ) (3) Contrary to the grammar of Zadeh's definitions, the 'propriety of a System' is not a property of the system at all; it is determined by the observer's choice of orientation for the system. Thus Zadeh's 3d_ho_c_ approach amounts to dismissing an anomaly by naming it. 72 Other authors have paid implicit homage to this problem in the terminology which they employ. Some authors, Tapai [ 10] , for ex- ample, have referred to systems which require a description of the form (2) as ”Networks with Excess Elements". Rohrer [8] calls (2) the ”State Equations in Extended Form". In a private communication, Resh has suggested that resolution of the anomaly rests with the observation that the behavior of differen- tial objects admits interpretation in terms of two distinct types of history dependency, quite independently of the propriety of their orien- tations. One type deals with events experienced at any time from re- cently into the indefinite past; the other type reflects only events ex- perienced in the immediate past. The first type is describable in terms of 'long-term state variables', the familiar variables whose rate of change at any moment is determined by the object's state and and stimuli at that moment. The second type is describable by 'short- term state variables', variables whose accumulation is the dynamic property determined by the ob ject's state and stimuli at that moment. Consistent with that suggestion, the general form of the State- Output equations for a differential object will be taken as: ft 3 = e(s,x,u,t) EEK :: f(S,X,u't) (4) v = g(S.X.u.t) Zadeh's hybrid state equations, (2.), then represent a special case which can arise; for example, for a system with a scalar input, when the short- state transition equations are taken to be: ft 81 = u ft 82 = 81 (5) t _ f 8i ‘ 31-1 73 Proper systems are systems which can be described by expres- sions of the form (1). Those expressions have the property that the n11mber of state variables, the size of the state space of the object, is equal to the number of energy storage elements contained in the ob- ject. Conversely, improper systems must be described by expressions of the form (2) in the conventional treatment; and the number of state variables appearing in those expressions is smaller than the number of energy storage elements contained in the object. Notice, however, that the output equations of (Z) are not instan- taneously determinate expressions: knowledge of the values of the s tate variables and the stimuli at any instant is not sufficient for the Purpose of determining the response at that instant. Thus the appear- ance of the derivatives of the stimuli in the output equations indicates that the measure of the system's history dependency is not given adequately by the number of state variables appearing in the equations. The number of state variables appearing in (4), the totality of the constituents of s and x, is equal to the number of energy storage e1Earnents contained in an object--regardless of the object's propriety. It i s the contention of this dissertation that that number is an adequate lT1'$asure of history dependency; that it is the invariant size of the ob- Ject‘s state space. This contention is based on the fact that the output e<{nations in (4) are instantaneously determinate. 3 ~ Short- Term State Variables in Differential Systems When solutions are obtained for the conventional state equations of a differential system, the expressions for the state variables typi- Q a-lly include integrals of the stimuli. Those integrals form the basis for the nomenclature 'long-term state variables', to be used in ‘ 74 connection with those conventional variables. It is conceptually clear that such variables exhibit a dependence on events (stimulus variations) which occurred at any time from the present into the indefinite past. Conversely, when solutions are obtained from short- term state variable equations, the expressions for the state variables often show a. dependence on time derivatives of the stimuli. For example, upon differentiation of the first line of (S) to retrieve 81' it can be seen that 31 is determined solely by the derivative of the stimulus variable. The state variable solutions given in equations VI-(S) present a good illustration for the contrast in history dependency between the two types of state variables. If derivatives were to be defined on the basis of a limiting pro- cess from the left, the conceptual basis for the nomenclature 'short- te rm state variables' would become clear. Variables described by SuCh expressions would be seen to exhibit dependence only upon events which occurred in the very immediate past. The primary manifestation of short- term state variables in the 81:a.1:e equations for differential systems is the integral equation. That is obvious from (4), and from the exaznples which were presented in chapter III. Thus the adoption of the short- term state variable con- <2 erat must be accompanied by a willingness to deal with integral equa- t:i-CDIis, and with mixed sets of integral- differential equations. Some motivation has already been supplied for that adoption, however, when the minimum work method for obtaining the state descriptions was tie\reloped--the relative ease together with the accompanying algebraic 8il'nplicity of the expressions providing desirable results. .________‘ 75 All state variables in this dissertation will be taken as features directly associated with energy storage elements contained in the ob- ject. The specific forms to be used are as follows: nggil‘erm state Variables a. For across-type memory elements--vC(v); b. For through-type memory elements--iL(i); Short- Term State Variables a. For across-type memory elements--i; b. For through-type memory elements--v. In the terminology of electrical networks, long- term state vari- ables are, dimensionally, the charge on capacitors and the magnetic flux in inductors, respectively. The short-term state variables are, dilnensionally, the current through capacitors and the electric poten- tial difference across inductors, respectively. 4- Partitions of the State §pace of Differential ObJ'Lects The state variables, and their associated dynamic variables, are assigned to the memory elements at the time the behavioral dia- gram is streamlined. It was seen in III-5 that the particular assign- In~ent depends on the orientation of each memory element. Thus, the I33-:rtition of state variables into long-term/short- term sets is imposed by the basic orientation of the behavioral diagram, and is a property which varies from one basic orientation to another. The nature of this partition will be of importance in subsequent Qllapters during the development of alternative techniques for the eI‘llalysis of differential systems. The following terminology will be “8 eful to distinguish certain types of partitions: ”bf—1 76 a. A full long- state partition will be one associated with a description of the form (1), or with one of the form (4) in which the set of short- term state variables is empty. b. A full short- state partition will be one associated with a description of the form (4) in which the set of long- term state variables is empty. c. A mixed-state partition will be one associated with a general description of the form (4); normally its use will imply that neither set is empty. d. A maximal lonfltate partition will be a mixed-state partition developed on the basis of a maximal tree; i. e. , one in which the size of the set of long-term state variables has been maximized. e. A maximal short- state partition will be a mixed-state partition in which the size of the set of short-term state variables has been maximized. It should be apparent that a specification of the object's input/ °u1rput partition (its orientation) establishes a class of basic orienta- tions for the behavioral diagram. For a given input/output partition, the behavioral diagram can, in general, be oriented at least on the basis of several different trees (or pairs of trees). That class of orientations will contain many mixed-state partitions, a set (contain- ing at least one member) of maximal long- state partitions, a non- empty 8 e1; of maximal short- state partitions, plus possibly- empty sets of full long-state and full short- state partitions. If either of the latter two 8 ets is non- empty, its content is identical to its maximal counterpart (am to d., b. to e. ). 77 For a given object orientation, the size of the set of long- term state variables in the maximal long- state partition is fixed. However, as the orientation of the object is varied that number can also vary. It is that set size which is taken as the size of the state space of the object in the conventional treatment of history dependency. In this dissertation it will be considered to be only one of many interesting and variable properties of the state space; but certainly not its size. 5 - Efficient Analysis of Linear Systems Koenig et a1 [33] have specified conditions which guarantee the existence of unique solutions for linear differential systems. They have developed methods for obtaining State- Output equations in the conventional form for such systems, and solutions to those equations. However, much effort is still being devoted to the analysis of linear Systems in an attempt to devise ever more efficient procedures for Obtaining those results. That work is motivated by the desire to con- 3 truct tractable algorithms for the mechanization of systems analysis through the use of computers. Certain authors seem to feel that the best approach is to use a fiXed method of analysis for all systems. Pottle [50] and Silverberg [ 5 8] each opt for the nodal method of analysis as the basis for their 1) r ocedures. Other authors adopt the attitude that the use of mixed methods of E‘rlalysis can lead to optimum procedures to be used for different sys- tems. Bracchi and Somalvico [6] , [7] represent this viewpoint in a t1‘eatment which is based on frequency domain representations of 837’stems. 78 This dissertation supports the latter attitude, particularly in light of the variety of new techniques which promises to become available through adoption of short- term state variables. It is by no means clear that the extra effort required in order to find an optimal approach to the analysis of a specific system (as in the search for a minimum-n orientation) can be justified in terms of the labor to be s aved in the resulting analysis. But the alternative methods of analy- s is are at least worthy of investigation. And the question of the value of an optimizing procedure of analysis cannot be written off with an 3. Eriori negative attitude. Therefore the final section of this chapter, and the entire contents of Chapters V and VI, will be devoted to the analysis of linear systems through the use of alternative object orientations and alternative state S pace partitions. The approach by Silverberg [58] is of special interest to this dis sertation in that he used both integrals and derivatives of nodal Variables as "state variables”. Parkin [47] responded favorably to t1"1e procedures which Silverberg presented, but was highly critical of t1We use of the terminology ”state variables" in that context. He held that the usage violated the definitions laid down for state variables by Kuh and Rohrer [34]. Silverberg's break with tradition is similar to that proposed her e, but there are basic differences. This dissertation proposes th at both currents and potential differences be used as short- term State variables in particular situations, but always when associated Wit}, a memory element. Moreover, the reason for suggesting the break with convention is based on a viewpoint which is supported by 79 the argmnents already presented. It was not suggested merely as a matter of notational convenience in the use of a particular analysis procedure. Analytical Solutions for Full Short-State DescriLtions of Linear 6 . Diffirentiafojijects The first question which might be raised concerning alternative descriptions of differential systems is--What form do the analytical solutions take to full short- state equations? It will be established in this section that system responses can be determined in a straight- forward manner when that system's behavior is given in terms of a full short- state description. An example of such a description has already been presented in III-(Z9). Consider first a homogeneous equation of the form: 6. l. f;f(7)d'r + af(t) = o (6) in which f is a piecewise continuous function. Applying, for example, the techniques of "Generalized Functions" as given in Appendix 1 of Balabanian and Bickart [2], to derive a solution for (6), yields the Conclusion that the only such solution is fit) = 0. The next step is to consider ft f, which is to be understood to be an instantaneous function, e. g. , the antiderivative of f, evaluated at t, and which is defined by the relation of (7). ft: = fof+fgf(7)d'r (7) Then the homogeneous equation in which that function appears: f: + af = o (8) C an be found to give rise to the general solution: f = f0 exp (-t/a) ‘ (9) In which f0 = -f°f/a ‘ 80 Next, an investigation of the non- homogeneous equation: ftf+af+u=0 (10) yields the conclusion that the general solution is given by (11). f = (f0+uo/a) exp (-t/a) - u/a + (l/a)2f:) exp(-(t- 'r)/a)u(7)d‘T . . 0 1n which f0 = -(f f+uo)/a (11) and u0 = u(0) Notice in passing that step- discontinuities in the forcing function are reflected directly in the response. Such irregularities cause no problems in the evaluation of (11), however. ‘(_>_._§_. In presenting solutions to the vector equations of the full 8 hort- state description, a derivation will be followed which closely parallels that in Chapter 5 of Koenig et a1 [33] , in which solutions are given for the full long-state description. Consider the homogeneous vector equation: fts+As = g (12) The vector 3 can be represented by a Maclaurin expansion. 8 = s + s t + a tz/z' + + s‘n)tn/n' + (13) 0 0 O O O O O o o O o o The following relations can be derived from (12). -l 0 so = -A f s -l s = -A s 0 -2 0 (14) 80 = +A s0 98“) = (-1)nA'nso S‘lbstitution of (14) into (13) gives rise to the following general solution f01412): A I" -__- 81 s = (U- A‘lt+A'2t2/2: - A'3t3/3: +. . .)s 0 l (15) s = exp(-A' t)s0 Now assume that the full short-state descriptions, such as the one in III-(29), take the form of the non- homogeneous equation: fts+As+Bu = 0 t t o “6) where f s = [03(T)d7+f s In order to establish the general form of the solution to this equation, let the unknown vector of time functions, y, be related to the short- state vector by: (17) Where yo = s The following result is established from (17) through integration by parts. [Baffld'r = A(U - exp (-A-1t))v - Afgyd'r + Aft) exp (-A'l'r)yd'r (18) or fauna? = -As+Ay0+Af:) exp(-A‘17):,d7 The combination of (16) and (18) yields the following: J“; exp (~A'l'r)yd'r = -y0 - A'lfos - A"l Bu (19) Differentiating (l9), and premultiplying by exp (A- It), yields: . -l -1 Y : - GXP (A t)A Bil t -1 -1 (20) Or y = '10 exp(A T)A Bild'f +yo The combination of (17) and (20) yields the following: 8 = exp(-A'1t)so- ff) exp(-A-l(t- 7))A'1Bfid'r (21) The final result for the general solution to (16), which reduces to (11) in the scalar case, can be obtained from (21) by means of integration by parts. 82 l l s = exp(-A'lt)(so+A- Buo)- A- Bu+fg exp(-A-l(t-T))A-2Bud'r (22) The general form for the analytical solutions to the full short- state description of a system has been established. It is ap- parent that many properties, such as the concept of a transition matrix, can be carried over directly from the work done with full long-state descriptions by Koenig et a1 [33] . Subsequent chapters will present a standard form for the state I equations associated with mixed- state partitions, a form closely re- lated to (16), and investigate circumstances under which the solutions of (22) would represent a very attractive tool to have available. CHAPTER V MD(ED-STATE REPRESENTATIONS OF LINEAR DIFFERENTIAL OBJECTS 1. Introduction A convenient normal form for the matrix equations, of the gener- al form in III-(4), will be established in this chapter for linear differen- tial objects. This form will be very useful in the procedures for obtaining alternative mixed-state descriptions which are associated with the various basic orientations of the behavioral diagram. After the reorientation procedures have been established, an investigation will be made into the nature of objects for which the analytical solutions, given in IV-(ZZ), can be applied directly. The normal form representation will also be seen to be useful in the process of selecting alternative sets of behavioral features for the Object. Thus, from this representation, an investigation can be made into the nature of the object's behavior under all possible environments; and a control theorist would be equipped to undertake the search for the class of environments which would elicit the desired responses fI'Om the object. A standard convention which has been used in writing those matrix e(Nations is the A-matrix. Originating with Bashkow [3] , its form was made explicit by Bryant [ 12]. The matrix has been the center of several investigations. Dervisoglu [19] found it useful for RLC net- WOl'ks; Wilson and Massena [63] gave an extension from its original 83 84 form; Sandberg and So [56] gave a computerized application, in com- puting the critical frequencies of transfer functions. The use of the A matrix here will include full short-state, mixed- state, and full long-state descriptions of objects; its previous use has been restricted to the latter case. And there will be a reversal of the signs of the matrix entries from the standard usage. Therefore the A- matrix in the following should be recognized as a modification of the Bashkow-Bryant matrix. _- A- ‘UJ 1 L 2. The State- Output Equation Matrix-~S--and its Normal Form The state-output equations, as obtained from the streamlined behavioral diagram for a system in section III-7, will be the starting point for this discussion. The equations will be used in their algebraic form, prior to the substitution of III-(9) to replace the dynamic var- iables, as a matter of convenience. 5;]. Definitions must first be given for the numerical properties of the vectors appearing in the state-output equations. If the object contains m memory elements, and the basic orientation has partitioned the state variables into m8 short- term state variables and mx long- term state variables (where m = m8 + mx), then the particular column vectors: a. a--will consist of In8 accumulation variables; b. r--will consist of rnx rate variables; c. s--will consist of mS short-term state variables; d. x--will consist of mx long- term state variables. The sources internal to the object will be treated in a manner Similar to the behavioral features of the object, in writing the equations. Accordingly, the two sets will be grouped together for bookkeeping 85 purposes. Distinctive notation will be employed to accommodate those occasions in which it is important to distinguish between them. There will be 2n variables in this class. If the object has np ports and n8 internal sources (where n = 111) + us), then the vector of free inputs, u, and the vector of free outputs, y, will consist of the following partitions: a. ppm-which contains the np inputs to the object; b. 26-—which contains the nS specified variables for the E. sources internal to the object; c. yP--which contains the np outputs from the object; (1. y8--which contains the arbitrary variables for the n8 sources internal to the object. 53. The equations obtained from the streamlined behavioral diagram, in algebraic form, for the initial basic orientation are of the form: a = e(s,x,u) r = f(s,x,u) (1) y = g(s,x,u) Let them be rewritten in the form: 3‘1 .1 Y = o (2) :1 ‘ u...) The submatrices in (2) are of the following sizes, in terms of the numerical definitions in 2. l: a. Ull is the (m x m) identity matrix; b. 012 is the (m x n) zero matrix; c. A is an (m x m) coefficient matrix; 86 d. B is an (m x n) coefficient matrix; e. O is the (n x m) zero matrix; 21 f . U is the (n x n) identity matrix; 22 g. C is an (n x m) coefficient matrix; h. D is an (n x n) coefficient matrix. With dimensions established for the various submatrices, the sub- scripts will normally be dropped. Define the vector of free variables from the behavioral diagram: T T T T T T (3 =(a.r.y:8.x Then the S matrix will be defined by abbreviating (2) as: T .u ) (3) [S] B = 2 (4) Thus, in general, the 5 matrix associated with a basic orienta- tion is (m +n) x Z(m+n), and of full rank. Furthermore, when the free variables are ordered according to (3), and the first (m+n) columns of 5 form an identity matrix, S will be said to be in normal form. 12:5.- The following important observation can be made at this point: When linear dependencies exist among the set of free outputs on the streamlined behavioral diagram, as seen for example in Figure III-ll, an S matrix in normal form will not exist for that basic orien- tation. S matrices in normal form exist only for all basic orientations which are free from such dependencies. Furthermore, the set of all normal form 5 matrices can be ob- tained from an initial member of that set, whether or not their associ- ated basic orientations are based on trees of the graph. The following section will be devoted to the development of procedures to be used in that reorientation process. 87 3. Alternative Basic Orientations from the S Matrix One principal feature, of the procedure for obtaining valid al- ternative forms of the S matrix for an object, is the search for new sets of basis vectors for the column space of the matrix. The re- orientation process can be mechanized by simple row operations on the matrix, followed by a rearrangement of the columns (accompanied by a reordering of the vector (3) in order to retrieve a normal form for the result. [ The terminology ”pivoting" and "sweeping out the column" will be adopted from linear programming to describe the process of bring- ing a new column vector into the basis. The analogy does not go very deep, however. For, while the objective in linear programming is to optimize some objective function, the selection of pivotal entries in this procedure must be made to serve a much different purpose: to retain the basic nature of the resulting orientation. Thus, the second principal feature of the procedure is to insure that the conditions imposed in section 111-5, for basic orientations, will be satisfied. _3~_.__l_. Rules must be established, concerning what can and cannot be done while selecting new basis vectors for the S matrix, in order that the resulting orientation will be basic. For the sources internal to the object, the rules are very simple. The arbitrary source variables are basis vectors and must remain so. The specified variables are not in the basis and cannot be brought in. The rules concerning the behavioral features of the object are also simple to accommodate. Exactly half of these variables must be basis vectors. 88 The behavioral features of the dis sipators have been suppressed. Their behavioral constraints have been frozen into the relations im- plied by the S matrix, and nothing can be done to affect them. Thus, these elements impose no restrictions on the reorientating procedure. While the behavioral features of the memory elements have also been suppressed, they are closely associated with the state and dynamic variables which are quite visible in the array. All complications in the reorientation procedure can be traced to the fact that care must be taken to insure that the new orientation of each such element will be complementary. It is required that: a. If the (column associated with the) state variable xj is to become a basis vector, it will be renamed the accumulation variable aj; and the associated rate variable rj must be taken out of the basis to become the state variable sj. b. If the state variable sj is to become a basis vector, it will become the rate variable rj; and the asso- ciated accumulation variable aj must be taken out of the basis to become the state variable xj. Notice that the necessary renaming process implies that the state space is undergoing a repartitioning in this procedure. _3_;_Z_. One important class of reorientations can be performed on the S matrix which establishes alternative partitions on the object's state space without altering the object's orientation (the partition of its behavioral features). This might be undertaken for an object in a specific environment while searching for a maximal long- state parti- tion, for example. 89 Such procedures are accomplished entirely through the selection of pivotal elements within the A matrix. It is always possible to select a non- zero diagonal entry of A as pivotal, since that procedure cor- responds to the reorientation of a single memory element in a com- plementary manner. A technique can be used for the simultaneous complementary re- orientations of n memory elements, through the premultiplication of S by a matrix containing the inverse of some non-singular submatrix of A. The selection of the submatrix must be performed according to the following 5213: For all of the n columns of A represented in the sub- matrix; if the ith column is represented, the ith row must also be represented. The inductive extension of the latter technique leads to the fol- lowing property: If, in the normal form S matrix for any mixed- state representation of a system, the A matrix is of full rank; then there exists a normal form S matrix with the com- pletely complementary partition of state variables. The property, and the premultiplication technique, will be demon- strated constructively in section 4. _3_v_._3. Another important class of reorientations can be performed on the S matrix which establishes alternative orientations for the ob- ject without altering the partition of the state space. This might be undertaken, for example, in order to establish the set of all orienta- tions in which an object exhibits a full long—state description. 90 These procedures are accomplished entirely through the selection of pivotal entries within the D matrix, but the source variables must not be used. Let the final n rows of (2) be written in the following form: y s D D 11 ya x I’21 D22 “3 Any non-zero entry of D11 can be selected as pivotal, since that opera- tion replaces one behavioral feature in the basis by another. A technique can be used for the simultaneous replacements of n behavioral features by n others, through the premultiplication of S by a matrix containing the inverse of any non-singular submatrix of size n from D”. 2:.3' It may be desirable to perform reorientations which involve combinations of exchanges between state- and- dynamic variables and behavioral features of the object. The important concern is that the memory element orientation remain complementary. That can be in- sured through application of the following Luis: Whenever a pivotal entry is used from the ith row of B, one must also be used from the jth column of C; regardless of which is chosen first, they must always be utilized in such pairs. 4. The Existence of Full Short-State Descriptions of Linear Differen- tial Sgtems Sufficient conditions can be established for the existence of full short- state descriptions of the behavior of linear differential objects in particular orientations. These conditions will be both necessary and sufficient for the solutions of those equations to be given by IV-(ZZ). 91 Assume that a full long-state description exists for a linear sys- tem. Then (2) can be written for that system as: U 0 A B = 2 (7) O U C D cx~. This case constitutes an illustration of the reduction from the apparent n- reducibility noted in 111- 8. 2. Each loop structure is zero- reducible here because of the cut set involving only edges 5 and 7. 132 does not involve any other state variables; 1. e. , its sub-matrix A21 is zero. Thus the application of the transform of VI- (9) will be quite simple, in this case, if the maximal short- state description is chosen for the system analysis. 4. Mixed-State Representations of Non- Linear Systems The information contained in the table of mixed- state descrip- tions is valid, for systems of nonlinear component elements, since it depends solely on the system topology, the location of sources, and the location of memory elements. That these symbolic relations can be written for nonlinear systems is not as powerful a fact for nonlinear systems, however, due to the nature of the elements. It will be seen that there may be overpowering constraints imposed, by the elements, on the process of selecting orientations. Suppose that the elements, of the system of Figure l, are linear with the exception of elements 2 and 4. Let the relations of (4) govern those non-linear elements. f2(v2) = sz(v2) (4) f4(i4) = i4L(i4) Furthermore, suppose that the environment edges are fixed as: a. Edge 7--An across-type source; b. Edge 8--A through-type source. With that understanding, the orientation to be studied for this system is the one previously denoted as orientation 1. It was seen that both full long- state and full short- state partitions exist for this strongly proper orientation. If the expressions of (4) are chosen to be state variables, in writing the expressions for the system, then long- term state variables 133 will be associated with each of those memory elements; and the full long-state description may be used. The streamlined behavioral dia- gram of Figure 2 has been derived for the system, on the basis of the tree (1, 2, 7), in order to obtain that description. Figure VII-2: The Behavioral Diagram for Partition (1, l, l, 1) Since the functional inverse of the state variable for each of the non-linear elements is an input to the topological relations, the state- output equations are liberally sprinkled with those invers es. The relations derived from Figure 2 are given in (5). d _ — 1 3x1 _ -K1(G5+G6)xl + Géf.2 (x F3x3 + G 2)- V7-I d _ -1 dtxz ' K16631 ' Géfz (x2) + 13" 5 -f-l(x )+1 4 4 8 8 3 (5 a) d -1 ' 3x3 = lel ’ f2 (*2) d _ -1 37x4 ‘ f2 (*2) 134 17 : KIGSXl - GSV7 -1 v8 — lel - f2 (x2) (5-b) Alternatively, the expressions of (4) can be chosen as dynamic variables in writing expressions for the system, and short-term state variables will be associated with each of those memory elements. In that case, the full short- state description of the system can be used. The streamlined behavioral diagram of Figure 3 has been derived, on the basis of the tree (3, 4, 7), in order to obtain that description. Figure VII-3: The Behavioral Diagram for Partition (0, 0, 0, 0) It is clear from Figure 3 that the dynamic variables a and a4 2 will be given as explicit non-linear expressions, the arguments of which will be linear expressions in terms of the inputs and state 135 variables. This form should be more tractable for computational purposes than the full long- state form of (5). The relations derived from Figure 3 are given in (6). ft81=C3+Cs l 3 1 4 Itsz = f2(s4) fts3 = .1331 - 1.1,,(c3,_’+<36)s3 — L3G554 + L3G5V7 - L318 (6) fts4 = f4(-s1 - s2 - G533 - G534 + G5V7) i7 = C1563 + (3584 - G5V7 V8 = 83 i._l. In a standard viewpoint of ferroelectric ceramics, internal dipoles tend to become aligned in the direction of the applied electric field. These materials saturate as the field intensity becomes in- creasingly large. A capacitor, made with a dielectric material of this type, might be characterized by a relation such as (7- a); assum- ing that hysteresis effects can be ignored. Similarly, an inductor wound on a ferrite core (also assumed free from hysteretic effects) might be characterized by a relation such as (7-b). C2(vz) = C20 + C21 exp(-qv§) (7-a) L4(i4) = L40 + L41 exp (-112) (7-1)) If the nonlinear memory elements, in the example of this section, were of the nature specified by (7); then the nonlinear relations of (4), which appear in results (5) and (6), would be single valued functions; their invers es would therefore exist. However, they would not exist in explicit closed form; and, at every evaluation, an iterative approxi- mation technique would have to be used in order to obtain a numerical value. 136 The full short-state relations of (6) utilize these nonlinear func- tions in their explicit form. Each evaluation required would be simple and direct, thus (6) presents the more convenient form. g. In order to deal with (6), solution techniques must be established for vector integral equations of the following form: fts = 9(8,u) (8) Let the Jacobian of 6 be partitioned into a square array, con- taining the partial derivatives with respect to the components of 8, J80; and an array containing the partials with respect to u, Jue. Then differentiation of (8) yields the relation: 8 : [J89] S + [ Jue] 1.1 (9) This relation can be solved for s whenever J50 is nonsingular: _ -l s - [J89] [s- [JuGHi] (10) Equation (10) would serve as the basis for a first-order approximation in finding new values for the vector 8. Broyden [10] has investigated a class of methods, for the numerical solution of simultaneous non- linear equations, in which the inverse Jacobian is maintained in stor- age; its approximations are corrected directly, through the use of various techniques. Such methods are much faster than the direct one, which requires repeated inversions of the matrix. Other standard numerical techniques can be applied to the solu- tion of (8). If s were expanded in a Taylor series, the coefficients determined through the use of (8) would involve the derivatives of the nonlinear function. The Runge- Kutta formulas for approximating those time derivatives could be used to develop a recursion formula which, while it would be different in detail, would be similar in form to the A... 'L 137 formula commonly used for solving vector differential equations, as described in [33] . (f C HAPTER VIII AN APPLICATION TO BOND GRAPHS-- TOWARDS INTERDISCIPLINARY UNITY 1. Introduction The use of Bond Graphs, as a conceptual tool in the investigation of multiport differential systems, originated with Paynter [ 48] . It is not the purpose of this chapter to provide a substantial background for the use of that tool; rather, to apply some of the results of this dis- sertation to some problems which remain outstanding in that field. The reader interested in pursuing the technique more fully is directed to the work of Karnopp and Rosenberg [30], [31] . Bond Graphs have several features which recommend their use in the analysis of differential systems. Perhaps the principal one is that they present a graphical picture, an intuitively appealing one based on the physical sense of cause and effect, for power flow in a system. For this reason, they have proven to be of great tutorial value in the Department of Mechanical Engineering at Michigan State University. They provide an organization of a system's structure from which state- output equations can be obtained readily. This procedure has peen mechanized in a computer program called ENPORT [55] . This oal, for the use of Bond Graphs, is thus identical to that for the use E behavioral diagram, discussed in this dissertation. Oster et a1 [46] have developed a technique for analyzing ir- versible thermodynamic systems as differential systems. They 138 '— 139 favor the use of bond graphs, because ”this generalization of linear graphs treats all energetic flows on an equal footing". While their conclusion is valid--Bond Graphs present a very convenient tool for the analysis of differential systems--the reasoning used in support of that conclusion implies a two- fold misconception. In the first place, linear graphs show no preference for the dimensionality of the variables. There is a requirement that all vari- ables occur in complementary pairs, but all energetic flows are treated on an equal footing. In the second place, Bond Graphs--in exactly the same manner as behavioral diagrarns--represent a specialization of linear graphs rather than a generalization. In the use of bond graphs, some one set of topological information is selected, to be emphasized for the sys- tem, in order to facilitate the procedures for obtaining the system equations. The linear graph presents all of the topological information for the system, in its most convenient form. These representations should be fully exploited in order to render the use of bond graphs, or of behavioral diagrams, optimum in some sense. The use of bond graphs is a relatively new technique. As a result, its associated literature is fairly sparse. There are two problem areas which have not been given adequate treatment to date, and which will come under discussion here: a. One area deals with the interrelations between bond graphs. No method exists for obtaining all alterna- tive representations of a system. A method will be developed for that purpose. 140 b. There is a lack of a formal procedure for the investi- gation of the "static dependencies" among the state variables and their derivatives. This problem will benefit from previous results in this dissertation. Some other benefits will emerge as a foundation is established from which to attack those problems. Previous results can be carried over; minimum-n least work configurations, for exainpleuand the use of mixed-state representations. And a belief currently held by bond graph practitioners will be dispelled, by exposing a hazard inherent to the central method of constructing bond graphs. A viewpoint will be taken, in this chapter, which is embodied in the following: Postulate--A unique linear graph can be found, which corresponds to the set of all bond graphs which represent a given differential system. That viewpoint requires some serious consideration since, in the limited treatment of this dissertation, it is false in three respects. M: The linear graph for a system may be one of a Z-isomor- phic set (see [57] ), rather than unique. Nevertheless, such a graph will be termed 'the' linear graph. Second: The treatment in this dissertation is limited to non- separable graphs; a limitation which requires the exclusion of gyrators, transformers and active elements. Even if such elements are omitted from the bond graph treatment as well, a problem remains. The bond graph of a non-planar linear graph can be dualized easily--the result being a perfectly acceptable bond graph. It might be pertinent to in- quire, at this point, whether such a bond graph can represent an F:- 141 actual system; however, a linear graph cannot be obtained for it unless ideal transformers are introduced in the representation. _'I;h_i_rg: Bond graphs permit greater flexibility in the assignment of signs to the system variables. In order to attain agreement with the standard convention used with linear graphs, the power flow arrow must always be oriented toward each component element. If a linear graph has been obtained for a particular bond graph, the bond graph practitioner can, with the simple reversal of one arrow, destroy the validity of the linear graph--requiring the insertion of an ideal trans- former to accommodate the sign reversal for one variable from a complementary pair. The assignment of signs will not be discussed further in this chapter, although that assignment will be performed in an example. It will be tacitly assumed that the signs used are consistent between representations; that duals of non-planar graphs are not under con- sideration--in short, that ideal transformers are not required in the linear graph representations of the bond graphs under consideration. An extension of the treatment of this dissertation, to include gyrators, transformers and active elements, would not be difficult. For example, the rules for establishing basic orientations for these devices can be extracted from the very general theorems in Chapter 8 of [33] . Under such an extension, the postulate would hold for general bond graphs . 2. The Details of Bond-Graph Diagrams The appearance of bond-graph diagrams consists of lines, shapes, and sets of 1's and 0's. 1" 142 2:1. The lines on the diagram are called ”bonds". Each bond represents a complementary pair of variables. The across variables are termed "efforts"; the through variables are termed ”flows". The vectors v and i will continue to be associated with those system variables. 23.3- The shapes (circles, for example) on the diagram represent the component elements of the system. The set of elements used throughout this dissertation will be used here. Component elements are 1-ports--have one bond terminating on them. Each element im- poses behavioral constraints on the complementary variables associated with that bond. _2__._3. The 1's and 0's appearing on the diagram represent struc- tural elements for the system. They are called "junction structures". Each is an n-port--has n bonds terminating on it. Each embodies a Kirchhoff-Law constraint; but, at the same time, it embodies the constraint of a behavioral direct connection (BDC). a. The l-junction is called a "common- flow junction. " It imposes a tie-set constraint on its 11 across vari- ables, and a BDC constraint on its n through vari- ables. b. The O-junction is called a ”common- effort junction. " It imposes a cut- set constraint on its n through variables, and a BDC constraint on its n across variables. 3. ConstructixiBond Graphs from Linear Graphs There are two conceptually separate processes involved in the preparation of bond graphs, as was the case in the use of behavioral .1"..— I). 143 diagrams. The first of those, the construction of the graph, is the subject of this section. It will be seen that the construction can be accomplished in many ways from the linear graph of the system, re- sulting in many different bond graphs which can be used for the repre- sentation of the system. 3. l. The principal method us ed by bond graph practitioners corresponds to the use of node-pair equations in network analysis. The method consists of three steps: 91‘ ‘ ~‘c-7—1 I . a. One O-junction is drawn for each vertex of the graph; b. A 3-port l-juncu'on is drawn for each component ele- ment of the system (environment edges are included as component elements), then bonded to the element and to each vertex to which the element is connected; c. One of the O-junctions is deleted, as are the bonds terminating on it. There is a simplification procedure which can be applied to some graphs. Any two-port junction structure, which is bonded to one ele- ment and to another junction structure, can be deleted, along with its bond to the element; and the element can then be bonded directly to the other junction structure. This removal does not alter the topologi- cal equations implied by the bond graph, but it does lessen the flex- ibility in the subsequent assignment of signs to the variables. Conversely, an extra junction can be inserted between a junction and an element. One property of bond graphs must be maintained in that process, however. The junction-types always alternate. ii. A complete set of methods will be developed for generating bond graphs from linear graphs. Necessary conditions can be given, which will form the basis for constructing all possible bond graphs 144 which represent a system. Bond graphs must be constructed on the basis of either: a. nt linearly independent tie sets; -or- b. nc linearly independent cut sets. 3. 2.1. When alternative a. is chosen, two steps will be followed in the construction of a bond graph: a. One l-junction is drawn for each tie set; b. A O-junction is drawn for each component element; 7 2‘ ‘ r ‘75;- i ‘ L. then bonded to the element and to each of the l-junc- tions which represent tie sets in which the element appears. Since at least nC 0-junctions are used in this procedure, the combined requirements are sufficient for the bond graph to represent the sys- tem's behavior. _3_=_2_._2_. When alternative b. is chosen, two steps will be followed in the construction of a bond graph: a. One O-junction is drawn for each cut set; b. A l-junction is drawn for each component element; then bonded to the element and to each of the O-junc- tions which represent cut sets in which the element appears. Since at least nt l-junctions are used in this procedure, the combined requirements are sufficient for the bond graph to represent the system's behavior. It can be seen that the conventional method of 3. l constitutes a special case of alternative b. of this very general procedure. Simi- larly, the use of mesh equations, for a planar graph, would constitute a special case of alternative a. 145 _§_.__3_. Bond graphs constructed on the basis of the fundamental cut sets or tie sets associated with a tree are particularly nice. They can be simplified (expanded) to a specific form, through the deletion (insertion) of junction structures by use of the techniques mentioned in 3. 1. When in that 'normal' form, a bond graph constructed on the basis of a tree: a. Contains exactly ne junction structures--of which nt are 1-junctions and 11C are O-junctions; E. b. Contains one branch element bonded directly to each 1..., -_. 0- junction, and one chord element bonded directly to each l-junction. c. Is the identical graph, whether constructed from the set of fundamental cut sets or tie sets of the tree; thus it can logically be called 'the bond graph' ob- tained from the tree; (1. Enables the fundamental cut sets to be read directly from the graph, one from each O-junction; and the fundamental tie sets, one from each l-junction. Bond graphs will not appear in this normal form immediately, when constructed according to the general rules of 3. 2 which govern the construction of all bond graphs. These properties suggest a streaIn- lined technique for the construction of bond graphs on the basis of a tree; they can be constructed directly in normal form. On the other hand bond graphs can be simplified 'right on through' normal form for some systems. Such 'oversimplified' bond graphs will contain fewer than ne junction structures, and will have multiple elements bonded directly to at least one junction. For such graphs, it 146 must be true that either the CSA or the TSA (or both) contains repeated columns. 4. Orienting Bond Graphs The second conceptual process, involved in the preparation of a bond graph, is the one of establishing an orientation for the graph. This orientation necessarily imposes both the input/output partition of the behavioral features, and the partition. of the state variables. Bond graph practitioners call the assignment of orientations ”the assignment of causality". The assignment is accomplished on a local level by the placement of a "causal stroke" across the bond (and per- pendicular to it) at one end or the other. The element or junction near the stroke is defined to cause (as sign the value of) the flow, or through variable; the element or junction away from the stroke is defined to cause the effort, or across variable; in the bond they share. 4. 1. By the nature of the bonds, causality is assigned simul- taneously to both variables of the complementary pair. Thus all com- ponent elements, including environment edges, can only be given complementary orientations in this discipline. Source elements, of course, can only be assigned the one spe- cific causal relation, pertinent to the particular type of source. Dis sipators can take on either causality, as can memory elements. Memory elements which are oriented according to part a. of Fig- ures 111-5 and 6 are said to have "integral causality". This is the pre- ferred causality in the use of bond graphs; since, in this orientation, each memory element gives rise to a state variable (a long-term state variable--consistent with current systems analysis practice, bond graph practitioners recognize only the manifestation of long- term memory). 147 Causality must be assigned to the l-junction as; one stroke out, all others in; for the n bonds terminating on it. For the 0- junction, it must be; one stroke in, all others out. §_.__2_. Assigning a basic orientation for the entire bond graph is known as assigning a "complete, consistent causality". The procedure, by which this is accomplished, is to assign the required orientations to the sources, one at a time; extending the orientations, implied by those assignments, as far as possible through the junction structures. [ Then, again one at a time, the process is repeated for the memory elements; assigning the preferred orientation to each memory element, in turn, as long as possible, and extending the implications of those orientations. Finally, if necessary, orientations can be selected for other elements in order to complete the orientation. This procedure, when coupled with the construction procedure of section 3. 1, can cause unexpected problems. Section 5. 3 of [ 31] contains a statement concerning the state variables, "Because inte- gration causality has been assigned completely, we know that each such variable is statically independent of all the others. " The follow- ing example will refute that contention. The linear graph, for the system to be used, was given in Figure III-8. The system edges, with sources replacing the environ- ment edges in a manner consistent with the basic orientation of Figure III-9, are as follows: a. Edge 1--An across-type source; b. Edges 2 and 3--Across-type memory elements; c. Edges 4 and 5--Through—type memory elements; d. Edges 6 and 8--Through-type sources; e. Edges 7 and 9--Dissipators. 148 The bond graph of Figure 1 has been constructed according to the conventional method of section 3. l; and a complete, consistent causality has been assigned according to the method of this section. This orientation corresponds to the one us ed in Chapter III, and Figure III- 11 clearly reveals two separate linear dependencies which exist among the state variables and output variables. 0 \/ 69%] @Nl/0 < \/ @:/® / /\1 \T 1 Q \Q T 0 Figure VIII- 1: The Bond Graph with Complete, Consistent Causality 4. 3. Fortunately, a more direct method can be used to assign causality for a bond graph. If the causality is assigned on the basis of a tree, then the result is guaranteed to be free from linear dependen- cies among the state and output variables. Since that procedure is only sufficient; not all complete, consistent causalities can be obtained in this way. However, if the bond graph is constructed on the basis of the same tree, some problems can be avoided in obtaining equations from the graph, as seen in the examples of Chapter III. When the construc- tion is on the basis of a different tree--and particularly if not on the 1:. “EMT—m I. 149 basis of a tree at all--the process of obtaining equations for the sys- tem can be much more difficult, as will be seen in section 5. To assign the causality on the basis of a tree, it is necessary to: a. Select the branch elements to assign the value to the across variable of their bond; Select the chord elements to assign the value to the through variable of their bond. If that entire assignment is made initially, a complete, consistent causality will always be obtained through extension of the implications of the element assignments. It will be possible, of course, through the adoption of short- term state variables, to perform minimum-n orientations in order that the desired equations can be obtained with a minimum amount of work. 5. State-Outmit Equations from the Bond Graph The goal is to obtain from the bond graph an equation for each dynamic variable and each system output in terms of the state variables and system inputs. This can be accomplished by writing one output equation for each of the system elements and eliminating the dissipator variables from that set as 'bound variables'. Stromausality is particularly nice in this process. Under this property, the common variable of the junction is determined by the element bonded directly to the junction. Bond graphs which are constructed and oriented on the basis of the same tree are the only graphs which exhibit complete strong causality. Continggng paths result when graphs do not have complete strong causality. When writing an expression at a O-junction, for example, the through variable determined by (caused by) the junction 1.1- - . A...“ J 150 is computed as the algebraic sum of the through variables common to each adjacent l- junction. If there is no element bonded to one of those junctions, or if the element bonded there has weak causality, then a path must be followed through that junction until the cause of its through variable is located. That path must next encounter a 0- junction, indicating that the desired through variable must be computed as another summation; and new branches of the contingency path may appear in this process. Under the strong causality afforded a graph constructed and oriented on the basis of the same tree, the computation for an ele- ment variable is performed at a unique junction, and only the elements bonded directly to strictly adjacent junctions enter that computation. After the equations have been established for the elements, it will be necessary to solve n simultaneous equations, for this n- reduc- ible loop structure, in order to eliminate the dis sipator variables. After this elimination, the resulting equations form the desired set. Reinstatement of the history dependency relations, of III-(9), will yield the state- output equations for the system. An example will be given to illustrate this procedure, and to demonstrate the ease provided when strong causality is used. The linear graph of Figure III- 14 describes the system with the following edges: a. Edge l--An across-type source; b. Edges 2 and 3--Across-type memory elements; c. Edge 4--A through- type memory element; (1. Edges 5 and 6--Dissipators. ’h:‘-n_- l 151 The augmented bond graph of Figure 2 corresponds to the be- havioral diagram of Figure III- 16. Both were constructed and oriented on the basis of the tree T2 = (1,4,5, 6). The fundamental tie sets used to construct the bond graph are listed in Table 1. Edge: 2 3 1 4 5 6 1 o 1 o 1 1 o 1 o 1 1 0 Table VIII- 1: Fundamental Tie Sets for the Bond Graph 6) G) 63.4.. o AqTFLKf'm-Aftm o [._=-_@ @‘410 6) Figure VIII- 2: The Augmented Bond Graph for the System The arrows on the graph complete the augmentation of the bond graph. Used to determine the signs of the variables in the equations, they are consistent with the oriented linear graph of Figure III- 14. The following equations can be written for the graph; interpreting the free inputs and free outputs according to the conventions estab- lished previously. a2 : C2(V1-v +v 5 6) a3 = C3(-s4 + v5) (1) a4 2 L483 15 = 82- S3 16 = -82 152 Multiplication of the last two equations in (l) by RS and R6 accomplishes that which was called Phase I, in the computational pro- cedure for behavioral diagrams. There are no loop equations to be solved since the tree, used to prepare the bond graph, gave rise to a zero-reducible loop structure. Consequently, Phase 11 consists of inserting those bound variables into the first four equations of (1). Then, after the substitution of III-(9), the remaining four equations become the full short- state description of the system, as shown in 111- (29). 6. Static Dependence and the Bond Graph Bond graph practitioners are interested in the study of the static dependencies imposed, by the interconnections of the system's com- ponents, among the system's variables--not only among the state variables, but also among their derivatives. The interest is in the influence of these dependencies on such properties as: a. Available alternative forms of the bond graph; b. Available alternative forms for the state equations; c. The size of the state space of the system. These questions have, of course, been central to the investiga- tion and application of the concept of short-term state variables. A large portion of this dissertation has been devoted to a study of such dependencies. The methods of Chapter V represent, for linear systems, a way in which the implications of all linear dependencies can be inves- tigated. Rosenberg [54] has suggested the use of an array of functions, for non-linear systems, similar in form to the matrix equations in current use in systems analysis. An array of this type could be 153 formulated in the manner of the 8 matrix of V-(Z); and used in a similar inve stigation. Chapter VII presented a general method, valid for non- linear systems, for the determination of the principal manifestations of those dependencies as the first step in the analysis of a system. That method also provided the means for obtaining whichever description was deemed to have the most desirable set of properties, i. e. , the tree on which to base the analysis. Thus, once a method has been established for obtaining a linear graph from a bond graph--since the first representations available in that discipline are normally of the latter form--the results obtained in this dissertation will apply. And if not all questions, which might be asked, have been answered; at least the means to study the ques- tions have been supplied. 7. ConstructingyLinear Graphs from Bond Graphs This final section is important to the chapter in several re- spects. It will permit the study of static dependencies, as discussed in section 6; it will permit the generation of all alternative bond graphs which represent the system, through utilization of the method of section 3. 2; and it will fulfill the postulate which has been the foundation for the entire discussion. This important step will be taken in developing a method for obtaining a linear graph from a bond graph. .'_7_._l_. The first step to be taken is to obtain the CSA. That step can be accomplished in several ways, as discussed in Appendix B. In general, either a set of nt linearly independent tie sets, or a set of ne linearly independent cut sets, will suffice. 154 When the bond graph is in the normal form associated with a tree, the task is simple. The index columns of the CSA are repre- sented by the elements bonded to the 0- junctions, and the fundamental tie sets can be read off directly from the l-junctions. Thus the CSA can be generated by the special method developed in the appendix. When there are several elements bonded to one or more of the junctions, some simplifying procedures can be followed. The several elements bonded to a O-junction represent repeated columns of the CSA; thus all but one can be discarded, to be treated as discussed in Appendix B. And when n elements appear bonded to a single 1- junction, (n— l) linearly independent cut sets can be written immediately from that set of elements--by pairing a particular one with each of the others in turn. Each of those can be considered to be a fundamental out set; and all elements except the common one can be discarded, not to be us ed in writing subsequent cut sets. For graphs in which no junctions have multiple elements bonded to them, but in which 'free' junctions appear (junctions with no ele- ments bonded directly to them), the rank and nullity of the graph can be computed in order to determine how many cut sets, or tie sets, must be written in order to obtain the CSA. Let the following _dgfipi— E9119. be established: a. nOb--the number of O- junctions with elements bonded directly to them; b. nor-the number of O-junctions with no elements bonded to them; c. nlb--the number of l-junctions with elements bonded directly to them; (A4 1.: ”L 155 d. nlf--the number of l- junctions with no elements bonded to them. Then the rank and nullity of the graph can be computed as: n = n + n - n c 0b 0f If “t = n1b + ”11 ' “01 (2) Cut sets and tie sets can be obtained at the various junctions (0- junctions and l- junctions , respectively) on the graph, as discussed in section 5. Care must be taken to insure that the chosen set is linearly independent, as well as of the sufficient number computed in (Z). _7_.__Z_. The second step to be taken, once the CSA has been ob- tained, is to find an edge incidence matrix for the linear graph from among the rows of the CSA. This can be accomplished by the method developed in Appendix B. And the linear graph can be drawn by in- spection from that array. An example will be given to demonstrate the procedure just es- tablished. Let the system be represented by the bond graph of Figure 3. 6? *1/0\1____ @ |\0/ @ (2) l 6) Figure VIII-3: A Bond Graph for the System 156 If element 2 were extended through the insertion of a 0- junction, this bond graph would be in the normal form corresponding to a tree. The branches of that tree would be the edges (2, 3, 4). The rank of this graph is thus 3, nullity 2. The fundamental tie sets for that tree can be read at the l-junctions; they are listed in Table 2. Edge: 1 5 2 3 4 10111 01011 Table VIII-2: The Fundamental Tie Sets of the Graph Since the rank of this graph is 3, Table B- 13, of Appendix B, can be inspected to yield the desired edge incidence matrix. Let the following correspondence be established between the five edges of this graph and the columns of that array as follows: (e2,e3,e4;el,e5) = (cl,c2,c3;c7,c6) (3) The particular ordering of edges (2, 3, 4) with the first three columns is arbitrary; once established, however, the remaining two columns are associated with the other edges through the fundamental tie sets of Table 2. The two missing columns of the array establish the sets of rows which will furnish an incidence matrix. Therefore columns 4 and 5 will each yield one of the Z-isomorphic linear graphs for this system. Making the arbitrary selection of column 4, the edge incidence matrix is read, from Table B- 12, and listed in Table 3. Edge: 2 3 4 1 5 o 1 o 1 1 o 1 1 o o 1 o 0 1 o 1 o 1 o 1 Table VIII-3: The Edge Incidence Matrix for the System 157 Finally, the linear graph is drawn by inspection of Table 3. The graph is shown in Figure 4. Figure VIII-4: The Linear Graph for the System CHAPTER IX C ON C LUSIONS 1. The Method of Behavioral Diagrams The method of behavioral diagrams has served as the basis for the study of differential systems in this dissertation. The method has been 6 een to: a. C. Provide an excellent conceptual tool for organizing and discussing the ideas and methodology of differen- tial systems--thus to provide an excellent tutorial method; Provide a good pencil- and-paper method of analysis, particularly for obtaining system equations in sym- bolic form--thus to provide a basis for undertaking parametric studies and sensitivity analyses; Provide a good approach for the formulation of state equations for non-linear systems--thus to serve a very important function in systems analysis; Provide a good intuitive feeling for the process of re- orienting systems, the methodology for which was developed in Chapters V and VII--thus to furnish motivation for the control theorist to investigate some alternative characterizations of systems; Provide a good organizational structure upon which to build a computerized systems analysis program. 158 A A“! 159 The application of behavioral diagrams to bond graphs, in Chap- ter VIII, demonstrated that; in serving as a model for the process of obtaining descriptions of differential systems, they provide a useful means for studying other methods of analysis. Therefore, although the method of behavioral diagrams provided no improvements to existing matrix methods for obtaining and solving quantitative descriptions of linear systems, the method has substantial merit. And this dissertation has served a useful purpose in providing a formal application of the general method to a specific class of systems. The application its elf, in Chapter III, can serve as a guide as to the manner in which the method must be applied. And the specific methods which were developed in subsequent chapters, as a result of this application, can serve as beneficial tools of systems analysis re- gardless of the approach. The methods developed in Chapters IV through VII are equally applicable to the investigation of systems be- havior by means of the method of bond graphs, for example. 2. The Concept of Short- Term State Variables The most prominent theme of this dissertation has been the con- cept of short-term state variables. 'The adoption of this concept has been very satisfying in an academic sense. The concept has permitted a unification in the treatment of the history dependency of the behavior of differential systems; it permits the size of an object's state space to be an invariant property under alternative orientations, and it has expanded the pleasing duality in the characteristics of these systems. i A rich variety of practical alternative techniques, which were not previously available for systems analysis, has been developed as 7r —-.-- .__-:.. 160 a consequence of the adoption of this concept. The first result, in section III-8, demonstrated how any one of a set of minimum n- reduc- ible mixed- state representations of a system could be obtained with a minimum amount of work. Next, the analytical form for solutions to the full short- state representations of linear systems (in the case which came to be called 'strongly proper systems' ) was developed in Chapter IV. And--while such systems form a class which does not yield to an easy prior selec- tion of a best description--a practical system was used in Chapter V to demonstrate that the new alternative form could prove to be much simpler, hence more desirable for use, than the old form in which the system previously would have been treated. Chapter VI presented techniques for obtaining solvable equations from an entire spectrum of linear system types. It was seen: a. In section VI- 2, that solutions could be obtained directly from the mixed-state form for special cases of both strongly proper and strongly improper systems; b. In section VI—3, that weakly proper systems clearly yield most readily to treatment by means of the tra- ditional, full long-state description; c. In section VI- 4, that weakly improper systems, dual to those of b. above, would just as clearly yield best to treatment by means of a full short- state descrip- tion. And that this treatment obviates the need to define a new set of state variables-~a pleasing bene- fit at the expense of the technique previously avail- able; . -- _2__.___1 PL 161 d. In section VI-S, that strongly improper systems would best be handled by the maximal partition (long- state or short- state) with the greater size. Failing a choice on that basis, a prior selection would not be made easily--but again, the new alternative forms would be preferable under some circumstances. It was seen in Chapter VII that a preliminary investigation Could be undertaken to determine the set of alternative descriptions avail- able for an object-~in all of its orientations. The techniques used are original to this dissertation; they do not depend on basing the investi- gation on behavioral diagrams, nor do they depend on system linearity. That list of descriptions was seen to permit certain properties of the descriptions to be predicted; properties which would permit the prior selection of descriptions to be used for systems of the types dis- cussed in b. , c. , and (for a restricted set of such systems) d. above. An empirical investigation of equations, which could be limited to a small subset of the available descriptions, was suggested, in order to increase the number of systems for which a prior selection could be made, in cases a. and d. The foundations have thus been established for an optimum application, of one of the alternative descriptions, to a particular system. Another direct consequence of the adoption of this concept was the extension made in section III-7 to an existing method of systems analysis. As it became possible to replace every memory element by an independent source, the applicability of a previously very limited technique became completely general. #7). l k.—‘ 162 This dissertation has provided a strong case for the adoption of short- term state variables. The benefits to be gained consist of not only the aesthetically pleasing symmetry afforded the treatment of history dependency, but also an entire set of new techniques for sys- tems analysis. 3. Special Results from the Dissertation It became necessary, during the course of this investigation, to develop methods possessing particular properties in order to obtain some of the desired results of the dissertation. These problems and investigations were deemed sufficiently separate from the main theme of the dissertation to warrant incorporating them as appendices. 3. 1. Appendix A presents a new technique which was developed for the simplification of truth functions. The method is equally ap- plicable to obtaining the set of prime implicants or the set of prime implicates of a function; the latter proved especially valuable in the solution of the problem in Appendix C. Similarly, the inductive construction of this method proved to be of particular value in obtaining some results for linear graph theory in Appendix B. While the method in current widespread us e, for computerized applications, is iterative and requires several passes for completion, the new method is direct. Its justification as a competitor for the existing method would require an investigation of comparative execu- tion times; but it presents a very appealing pencil- and-paper technique. _3__._§_. Appendix B utilizes a truth- function approach to the study of linear graphs. A set of new properties is obtained for the arrays of all cut sets and all tie sets of a graph, then a method is developed to permit generation of those arrays in a new manner. __u ”h‘ _i 163 That method turns out to be of central importance in the develop- ment of a technique for obtaining all trees of the graph. And, while this technique has not been justified by means of a comparison of execution times with existing methods, for the generation of all trees, it has a property of great importance to this dissertation. It permits the generation of specific subsets of trees, a property which was re- quired in section 111-8 and in Chapter VII. A solution was proposed for the problem of locating an edge in- cidence matrix within a tentative CSA. This problem is of central importance to the discussion of bond graphs in Chapter VIII. The method of solution is not one to be given consideration as a practical algorithm. However, some clues were obtained which might suggest the direction to be taken to develop a practical solution; and an initial step in that direction was completed. 3. 3. Appendix C presents a solution to the problem of finding minimum edge-sets and vertex- sets needed to destroy _all feedback loops in a directed graph. This solution permits the optimal n- reduc- ibility to be determined for the oriented behavioral diagram of a sys- tem with a very general characterization. The solution was important to the material of section lI-S. It permits the behavioral relations to be obtained for a system in a manner requiring a minimum amount of work. The result has significance far beyond the confines of differential systems. 3.4. This dissertation has provided a set of interesting results which are represented by the discussion in this section. These results came in a wide variety of areas distinct from differential systems; but each area has been seen to furnish its own special impact on the methodology for the analysis of those systems. 164 4. Recommendations for Future Investigations The set of results reported in this dissertation has produced a generous supply of questions, remaining to be answered, and areas opened for further investigation. Some readily apparent ones are listed in this section. 4. l. The treatment should be extended to incorporate additional component elements: transformers, gyrators, and active elements. iii. A computerized systems analysis program should be de- [117‘ veloped, incorporating the new techniques provided here and demon- i (1... strating the feasibility of pre-selecting the best description for each particular system. E. An investigation should be undertaken to determine whether some more orderly procedure can be developed, to replace the empiri- cal investigation of system equations suggested in Chapters VI and VII. Such a method would be based on the CSA and TSA of the graph, coupled with a knowledge of the partition of free and bound variables of the be- havioral diagram. if, A method should be developed to utilize n—port objects as components in the hierarchical analysis of more complicated systems. Since component objects must be oriented in a manner consistent with their neighboring objects, the descriptions available for all orienta- tions of the object, as provided in Chapter VII, would be an important feature of this investigation. A simple example was provided in Chapter V for such an analysis, in the case of the phase- shift oscillator. £22. A control theorist would be interested in establishing the implications of particular mixed-state descriptions, and the availability of the various mixed-state descriptions, on certain features of the ob- ject's behavior: e. g. , controllability, observability, and stability. 165 fig. Perhaps an investigation would reveal that methods can be developed to obtain solutions directly from mixed sets of linear inte- gral and differential equations. It was assumed in Chapter VI that, except for the special cases of section VI- 2, a solvable set of equa- tions must be obtained in one form or the other. H. The Runge- Kutta method, for solving non-linear vector integral equations, should be developed as suggested in section VII- 4. And if the investigation of 4. 6 should yield an affirmative answer, a parallel investigation should be undertaken for non- linear equations. _4_._§. Execution-time studies should be undertaken to establish the significance of the simplification technique of Appendix A, and the tree generating technique of Appendix B, for more general applica- tions than those of the dissertation. £12. The problem of finding an edge-incidence matrix among the rows of a tentative CSA should be completed along the line of in- vestigation initiated in Appendix B. This problem is of general interest in several applications; but in particular, a practical method for ob- taining a linear graph from a bond graph would be of value to the practitioners of that discipline. REF ERENC ES REFERENCES M. T. Ardon and N. R. Malik, "An Intersection-Free Technique for Generating k- Trees", IEEE Trans. th. Thy., Vol. CT- 19, pp. 75-77, Jan. 1972. N. Balabanian and T. A. Bickart, Electrical Network Theoq, New York: Wiley, 1969. T. R. Bashkow, "The A-Matrix, New Network Description", IRE Trans. th. Thy., Vol. CT-4, pp. 117-119, Sept. 1957. C. Berge, The Ther of Graphs and its Applications, London: Methuen, 1962. I. Berger and A. Nathan, "The Algebra of Sets of Trees, k-Trees, and Other Configurations", IEEE Trans. th. Thy., Vol. CT- 15, pp. 221-228, Sept. 1968. G. Bracchi and M. Somalvico, "Topological Properties and Op- timum Application of the Mixed Method of Network Analysis", IEEE Trans. th. Thy., Vol. CT-18, pp. 228-232, March 1971. , "Theoretical Aspects of the Mixed Method in Com- puter- Aided Circuit Analysis", IEEE Trans. th. Thy. , Vol. CT- 18, pp. 305-308, March 1971. J. G. Bredeson and P. T. Hulina, "Generation of Prime Impli- cants by Direct Multiplication", IEEE Trans. Computers, Vol. C-20, pp. 475-476, April 1971. K. Brown, "Some Simple Methods for Generating Multitrees", IEEE Trans. th. Thy., Vol. CT-l8, pp. 179-181, Jan. 1971. C. G. Broyden, "A Class of Methods for Solving Nonlinear Simul- taneous Equations", Mathematics of Computation, Vol. 19, pp. 577-593, Oct. 1965. J. Bruno, K. Steiglitz, and L. Weinberg, "A New Planarity Test Based on 3-Connectivity", IEEE Trans. th. Thy., Vol. CT-l7, pp. 197-206, May 1970. P. R. Bryant, "The Explicit Form of Bashkow's A-Matrix", IRE Trans. th. Thy., Vol. CT-9, pp. 303—306, Sept. 1962. J. P. Char, "Generation of Trees, Two-Trees, and Storage of Master Forests”, IEEE Trans. th. Thy., Vol. CT-lS, pp. 228- 238, Sept. 1968. 166 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 167 W. K. Chen and S. K. Mark, "On the Algebraic Relationships of Trees, Co-Trees, Circuits, and Cutsets of a Graph", IEEE Trans. th. Thy., Vol. CT-16, pp. 176-184, May 1969. W. K. Chen, "Computer Generation of Trees and Co- Trees in a Cascade of Multiterminal Networks", IEEE Trans. th. Thy. , v01. CT‘ 16, pp. 518-526, NOV. 1969. C. L. Coates, "General Topological Formulas for Linear Net- work Functions", IRE Trans. th. Thy., Vol. CT-5, pp. 42-54, March 1958. , "Flow Graph Solutions of Linear Algebraic Equa- tions", IEEE Trans. th. Thy., Vol. CT- 6, pp. 170-187, June 1959. S. R. Das, "Comments on 'A New Algorithm for Generating Prime knplicants'", IEEE Trans. Computers, Vol. C-20, pp. 1614-1615, Dec. 1971. A. Dervisoglu, "The Realization of the A- Matrix of a Certain Class of RLC Networks", IEEE Trans. th. Thy. , Vol. CT-l3, pp. 164-170, June 1966. L. Divieti and A. Grasselli, "On the Determination of Minimum Feedback Arc and Vertex Sets", IEEE Trans. th. Thy. , Vol. CT- 15, pp. 86-88, March 1968. T. L. Dollhoff and B. L. Weinberg, "A Result on Set Extraction and Application to Covering-Closure Tables", IEEE Trans. Computers, Vol. C-21, pp. 603-606, June 1972. W. R. Dunn, Jr. and S. P. Chan, "An Algorithm for Testing the Planarity of a Graph", IEEE Trans. th. Thy., Vol. CT-lS, pp. 166-168, June 1968. G. J. Fisher and 0. Wing, "Computer Recognition and Extrac- tion of Planar Graphs from the Incidence Matrix", IEEE Trans. th. Thy., Vol. CT- 13, pp. 154-163, June 1966. J. W. Forrester, Urban Dflamics, Cambridge, Mass.: M.I. T. Press, 1969. J. S. Frame, "Similarity Reductions by Rational or Orthogonal Matrices", IEEE Spectrum, July 1964. Y. Fu, "Realization of Circuit Matrices", IEEE Trans. th. Thy., Vol. CT-lZ, pp. 604-607, Dec. 1965. D. D. Givone, Introduction to Switching Circuit Theory, New York: McGraw-Hill, 1970. G. Guardabassi, "A Note on Minimal Essential Sets", IEEE Trans. th. Thy., Vol. CT-18, pp. 557-560, Sept. 1971. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 168 E. A. Guillemin, Introductofl Circuit Theory, New York: Wiley, 1953. D. C. Karnopp and R. C. Rosenberg, Analysis and Simulation of Multiport Systems, Cambridge, Mass.: M. 1.3T? Press, 1968. , Systpm Dflamics: A Unified Approach, East Lansing, Mich. : M. S.U. Division of Engineering Research, 1971. G. Kishi and Y. Kajitani, "Maximally Distant Trees and Prin- cipal Partition of a Linear Graph", IEEE Trans. th. Thy. , Vol. CT- 16, pp. 323-330, Aug. 1969. H. E. Koenig, Y. Tokad, and H. K. Kesavan, Anal sis of Dis- n— crete Physical Systems, New York: McGraw-Hill, 1967. 1 i E. S. Kuh and R. A. Rohrer, "The State-Variable Approach to 3 Network Analysis", Proc. IEEE, Vol. 53, pp. 672-686, July L— 1965. B. C. Kuo, Linear Networks and Systems, New York: McGraw- Hill, 1967. A. Lempel and L Cederbaum, "Minimum Feedback Arc and Vertex Sets of a Directed Graph", IEEE Trans. th. Thy. , Vol. CT-13, pp. 399-403, Dec. 1966. N. R. Malik, "Compound Matrices Applied to the Tree- Generat- ing Problem", IEEE Trans. th. Thy., Vol. CT-l7, pp. 149- 151, Feb. 1970. S. J. Mason, "Feedback Theory--Some Properties of Signal Flow Graphs", Proc. IRE, Vol. 41, pp. 1144-1156, Sept. 1953. , "Feedback Theory--Further Properties of Signal Flow Graphs", Proc. IRE, Vol. 44, pp. 920-926, July 1956. , "Topological Analysis of Linear Non- Reciprocal Networks", Proc. IRE, Vol. 45, pp. 829-938, June 1957. W. Mayeda, "Necessary and Sufficient Conditions for Realiza- bility of Cut-Set Matrices", IRE Trans. th. Thy. , Vol. CT-7, pp. 79-81, March 1960. W. Mayeda and S. Seshu, "Generation of Trees without Duplica- tions", IEEE Trans. th. Thy., Vol. CT-lZ, pp. 181-185, June 1965. W. Mayeda, S. L. Hakimi, W. K. Chen and N. Deo, "Genera- tion of Complete Trees", IEEE Trans. th. Thy., Vol. CT- 15, pp. 101-105, June 1968. E- J. McCluskey, Jr., "Minimization of Boolean Functions", Bell System Tech. Jour., Vol. 35, No. 6, pp. 1417-1444, Nov. 1956. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 169 R. J. Nelson, "Simplest Normal Truth Functions", J. Symbolic Logic, Vol. 20, No. 2, pp. 105-108, June 1955. G. Oster, A. Perelson and A. Katchalsky, "Network Thermo- dynamics", Nature, Vol. 234, pp. 393-399, Dec. 1971. R. E. Parkin and M. Silverberg, "Comments on 'Efficient Time- Domain Solutions Using Nodal State Variables' ", IEEE Trans. th. Thy., Vol. CT-18, pp. 304-305, March 1971. H. M. Paynter, Analysis and Design of ErgineeringSystems, Cambridge, Mass.: M. I. T. Press, 1961. M. Piekarski, "On the Construction of a Pair of M-Submatrices of a Cut-Set Matrix", IEEE Trans. th. Thy. , Vol. CT-13, pp. ; 114-117, March 1966. C. Pottle, "A 'Textbook' Computerized State-Space Network Analysis Algorithm", IEEE Trans. th. Thy., Vol. CT-16, pp. 566-568, Nov. 1969. W. V. Quine, "A Way to Simplify Truth Functions", Amer. Math Monthly, Vol. 62, No. 9, pp. 627-631, Nov. 1955. J. A. Resh, Foundations of Systems Science, East Lansing, Mich. : M.S. U. Unpublished Lecture Notes for SYS 825, Spring 1970. R. A. Rohrer, Circuit Theory: An Introduction to the State Variable Approach, New York: McGraw- Hi1 , 1970. R. C. Rosenberg, "State-Space Formulation for Bond Graph Models of Multiport Systems", Trans. ASME J. Dynamic Sys- tems, Measurement, and Control, pp. 35-40, March 1971. , User'nguide for EN_I:ORT-4, East Lansing, Mich.: M.S.U. Diviaon of Engineering Research, June 1972. I. W. Sandberg and H. C. So, "A Two-Sets-of-Eigenvalues Approach to the Computer Analysis of Linear Systems", IEEE Trans. th. Thy., Vol. CT-l6, pp. 509-517, Nov. 1969. S. Seshu and M. B. Reed, Linear Eppphs and Electrical Net- works, Reading, Mass.: Addison-Wesley, 1961. M. Silverberg, "Efficient Tirne-Domain Solutions Using Nodal State Variables", IEEE Trans. th. Thy., Vol. CT-l7, pp. 82- 86, Feb. 1970. J. R. Slagle, C. L. Chang and R. C. T. Lee, "A New Algorithm for Generating Prime Implicants", IEEE Trans. Computers, Vol. C-19, pp. 304-310, April 1970. 60. 61. 62. 63. 64. 170 C. J. Stehxnan, J. H. Maenpaa and W. J. Stahl, "Complete Tree Generation--Some Practical Experience", IEEE Trans. th. Thy., Vol. CT-l6, pp. 548-550, Nov. 1969. M. A. Tapai, "Use of Superposition in Writing State Equations for Networks with Excess Elements", IEEE Trans. th. Thy. , Vol. CT- 17, pp. 624-626, Nov. 1970. M. Vidyasagar, "An Algebraic Method for Finding a Dual Graph of a Given Graph", IEEE Trans. th. Thy. , Vol. CT- 17, pp. 434-436, Aug. 1970. R. L. Wilson and W. A. Massena, "An Extension of Bryant- Bashkow A-Matrix", IEEE Trans. th. Thy., Vol. CT-lZ, pp. 120-122, March 1965. L. A. Zadeh and C. A. Desoer, Linearfiystem Theory, New York: McGraw-Hill, 1963. A PPENDIC ES 5 TWP—77‘) APPENDIX A THE SIMPLIFICATION OF TRUTH FUNCTIONS l . Introduction This appendix begins with a brief exposition of a few selected topics from Boolean Algebra. The material is presented, for the reader without previous experience in truth functions, as a prerequi- site to understanding the material in the appendices as well as some topics in the body of the dissertation. The material presented is es- sentially self-contained, although no claim of rigor or completeness is implied. The reader desiring a better foundation should consult the literature; for example, the introduction to switching theory given by Givone [ 27] . A well-known result for truth functions is presented in Theorem 7. l. A nice result by Nelson [45] is presented in Theorem 7. 3; a result which, while known (see the footnote on page 148 of [ 27] ), is seemingly esoteric (see [8] , [ 18] , and [59] ). The proof, presented for the latter result, is original to this dissertation. It is constructive, and is presented since it suggests a method for the practical application of the simplification technique developed here. The final section of this appendix presents a method for the sim- plification of truth functions. This new result is obtained on the basis of the two theorems of section 7. It provides a nice pencil- and-paper technique for obtaining both the set of all prime implicants and the set of all prime implicates of a truth function; and the latter set proves of 171 172 value in Appendix C. It is not immediately evident that it will provide a practical computer algorithm for the simplification of general truth functions, although its application to unate functions is easily accom- plished and proves to be of value in Appendices B and C. The simplification technique in common use today is the "Quine- McCluskey" algorithm (see [44] , [51] , and pp. 136- 161 of [27]), commonly known as 'Consensus'. Consensus is an iterative method which requires several passes to complete a sirnplification--the method proposed here is direct. Consensus, however, permits bit-packing and word operations in the performance of its function. The multipli- cation of terms, required in the new method, might seem to preclude those benefits because of the cross-product terms involved. However, a technique recently developed by Dollhoff and Weinberg [21] can be employed to permit those features to be used in the mechanization of the new method as well. Similarly, the constructive proof of 7. 3 suggests that the sim- plification can take place through the incorporation of a single term at a time; and in an application in Appendix B it will be seen that the great bulk of cross-product terms can be ignored when the intersec- tions of particular terms are non- empty. Thus, a careful mechaniza- tion of this method could make it a practical contender for general application. This method, while developed independently, is similar to one recently proposed by Slagle et al [59] . They were unaware of Nelson's results, and proved weaker forms of theorem 7. 3 and corollary 7. 4 in the justification of their method. Bredeson and Hulina [8] and Das [ 18] were quick to point out the existing theoretical basis for that 173 method. All authors seemed to feel that the general method shows potential for use in the development of a practical algorithm. 2. The Axiomatic Duality of Boolean Algebra The operators of interest in Boolean Algebra, the ones to be used in this appendix, are conjunction, disjunction, and negation. The axioms of Boolean Algebra form a completely dual set with re- spect to those operators. In addition to the axioms of the algebra of real numbers, Boolean Algebra has the axiom of the distributivity of disjunction over conjunction, left and right. This duality gives rise to the fact that, for every result in Boolean Algebra involving the operators disjunction and conjunction, there is an immediate dual result in which the roles of those operators are interchanged. (See Theorem 2. 1 of [27].) 3. Some Semantics for Quantification Special semantics will be in use in this appendix in order to facilitate an understanding of the specific intent of a given expression. Written quantifiers will be used in which: a. For all i--the key word 'all' will be used to imply a simultaneity of application over all members of the appropriate set; b. For each i--the key word 'each' will be used to im- ply a singularity of application, valid for every member of the appropriate set in turn; not prohibit- ing a multiple simultaneous application, but not requiring it. 174 4. Terminolopy of Truth Functions and the Strppg Role of Implication The truth table is a powerful tool available for use in the study of truth functions. This table presents an enumeration of the value of the function at every point in its domain. The tool is available be- cause the domain of each variable, as well as the range of the function, is the set (0, l). The domain of a truth function of 11 variables is a cross- product space which consists of Zn points. Although no specific use will be made here of truth tables, some of the terminology to be used will be explained with regard to them. A truth function can be expressed in many wally equivalent forms. Every equivalent expression for a function must give rise to the same truth table. Logical equivalence is implied by the use of the equals sign in Boolean formulas. The expressions for truth functions are made up of literals, where a literal is a variable appearing in either negated or non- negated form. A 313213 is a simple term formed by the conjunction (disjunction) of several literals in a restricted manner; no variable can be repre- sented by more than one literal in a clause. Thus, a clause can be regarded as the simplification of some more general term through’ application of rules (1). v. + v. = v. 1 1 1 vi + Vi = 1 (l) Vivi = Vi v.-;. = 0 11 175 Clauses can be of two types, depending upon the operation by which they are formed from the literals. Conjunctive clauses, formed by a 'product', will be denoted tp. Dis junctive clauses, formed by a 'sum', will be denoted t8. It is convenient to define subsuming clauses. When a clause tj contains all of the literals to be found in another clause of the same type, ti, plus (perhaps) some other literals; then tj subsmnes ti. 2:1. There are two special forms in which many of the equi- valent expressions for a truth function can be found. They are called normal forms for the expressions. 12L}, Conjunctive Normal Form (CNF) is an overall conjunc- tion of disjunctive clauses. The function can be written (as a 'product of sums'): F = gt“ (2) The clauses in (2) are termed imgicates, because it is clear from that expression that: F - tsi (for all i) (3) Whereas, by Contrapositive: t8i - F (for each i) (4) 4. l. 2. Disjunctive Normal Form (DNF) is an overall disjunc- tion of conjunctive clauses. The function can be written (as a 'sum of products'): F = f'tpi (5) The clauses in (5) are termed implicants, because it is clear from that expression that: tpi —- F (for each i) (6) 176 Whereas, by Contrapositive: F - tpi (for all 1) (7) .53.;- There are two unique canonical forms defined for a truth function. Each is a fully expanded normal form. 1122.1. The Fully Expanded CNF (FECNF) of a truth function of n variables, is the (unique) expression of the form (2), in which each clause is the disjunction of exactly 11 literals. Each such clause is called a 'max-term', because its truth table contains one 0 and (Zn-1) 1's. The function which is everywhere zero contains the entire set of Zn max-terms in its FECNF. 'Tautology', which is everywhere 1, has the empty set of max-terms as its FECNF. 5L2. The Fully Expanded DNF (FEDNF) of a truth function of n variables, is the (unique) expression of the form (5), in which each clause is the conjunction of exactly 11 literals. Each such clause is called a 'min-term', because its truth table contains one 1 and (Zn-l) 0's. The function which is everywhere zero has the empty set of min-terms as its FEDNF. Tautology contains the entire set of Zn min-terms in its FEDNF. 2:23.2- For every truth function, for which the FECNF contains m max-terms, its FEDNF contains (Zn-m) min-terms. General implicates are sometimes referred to as 'max-type terms'; general implicants as 'min-type terms'. That terminology derives from their fully expanded counterparts. 33. Two sets of 'prime' clauses can be defined for a truth function. Each set is unique. §_.__§_._1. From the set of all implicates of a truth function (the set of all clauses which satisfy (3) and (4) ), there can be found a unique 177 set of Prime Irnjlicates: in which a prime implicate is defined to be an implicate of F which subsumes no other implicate of F. Such a clause will be denoted si. Prime implicates may be thought of as dis junctions of minimal sets of literals--which have the following properties: a. A max- term may be a prime implicate; b. The set of all prime implicates is unique; c. The conjunction of the set of all prime implicates is logically equivalent to F; d. si is a prime implicate iff noj exists (jfi) such that E-t i sj' 4. 3. 2. From the set of all implicants of a truth function (the set of all clauses which satisfy (6) and (7) ), there can be found a unique set of Prime Implicants: in which a prime implicant is de- fined to be an implicant of F which subsumes no other implicant of F. Such a clause will be denoted Pi' Prime implicants may be thought of as conjunctions of minimal sets of literals--which have the following properties: a. A min- term may be a prime implicant; b. The set of all prime implicants is unique; c. The disjunction of the set of all prime implicants is logically equivalent to F; d. pi is a prime implicant iff no j exists (jfi) such that pi _. t131' 4. 4. Two forms for the truth function F are of particular interest. They are the 'simplest' normal forms. 178 3:12;. A simplest CNF of a truth function is a conjunction of a subset (perhaps the entire set) of the set of all prime implicates. A truth function need not have a unique simplest CNF, but it will have a least one. Suppose F is written in an equivalent form as in (2), with each clause a prime implicate. Let it be rewritten as: F = 8.f J where f = it s. . . 1 1141 andif 3:1"? (8) then f-b 8. J and f- F Therefore, f is logically equivalent to F, and sj need not be included-- is not required in the simplest CNF. 3.5112. A simplest DNF of a truth function is a disjunction of a subset (perhaps the entire set) of the set of all prime implicants. A truth function need not have a unique simplest DNF, but it will have at least one. Suppose F is written in an equivalent form as in (5), with each clause a prime implicant. Let it be rewritten as: F = . + f 1’1 where f = 23 pi #1 and if p. - f _’ _ (9) then f - pj and T - F or F - f Therefore, f is logically equivalent to F, and pj need not be included-- is not required in the simplest DNF. 179 5. Unate Truth Functions Unate functions are defined to be truth functions which are ex- pressible as a normal formula in which no variable appears in both negated and non-negated forms. Unate functions have the property that the simplest normal forms are unique. The simplest CNF of a unate function is the conjunction of the set of all prime implicates. No sj exists to satisfy (8). The simplest DNF of a unate function is the disjunction of all prime implicants. No pj exists to satisfy (9). 6. Definitions for Some Qperations The operations of this section are defined in order to permit an economical form of expression to be used in the dissertation. 6. 1. Variable complement is to be performed on an expression when signified by (F)c. Every literal in the expression is to be ne- gated: e. g. , vi is to be replaced by '17 , and 35 by vj. _§_.__Z_. Operation dualize is to be performed on an expression when signified by (F)d. Every operator in the expression is to be 1 replaced by its dual: i. e. , conjunction by disjunction, and vice-versa. De- Morgan's Theorems guarantee that those operations, taken as a pair, give logical equivalence to functional negation. ‘13 = ((F1d)° (10) Furthermore, the order of their application is irrelevant; they might be considered to be 'operationally commutative'. It can be seen that 'dualize' reverses implication: If f - g (1 1) then (11)" -» (ad 180 .6451. Operation expand is to be performed on an expression in CNF when signified by (F)E. The following rules are to be applied repeatedly until they are no longer applicable: a. Distributivity of conjunction over disjunction, left and right; b. The rules (1); c. Deletion of subsuming clauses. In order to accomplish c. , it is only necessary to apply (lZ-a) after applications of a. and b. H tpj _. tPi (12- a) then tpi + tpj : tpi However, less work will result in the later stages if an initial exhaus- tive application is made of (12-b). If t . -> t . 3’ 3’ (12-1)) then t .t . = t . 81 83 s1 Let an expansion procedure be defined which is the dual of E; E denote the dual procedure E is applicable to functions expressed l' l initially in DNF; distributivity of disjunction over conjunction, left and right, must be applied in place of a. above; and the roles of (12- a) and (lZ—b) are reversed. 7. Two Theorems on the Simplification of Truth Functions _Z_._l_. The set consisting of the duals of all prime impliCates of a truth function is the set of all prime implicants of the dual function. Consider the expression: m F = 11‘ 8. (13) i=1 1 181 If the m-member set {si} is the set of all prime implicates of F, then in the expression: m (P)(1 = 2: (4,)d (14) i=1 the m-member set {(si)d} is the set of all prime implicants of (F)d. Proof: Clearly, for each i, (si)d is an implicant of (F)d since if F -> s. 1 d (15) then (8i) * (F)d Assume lst: (si)d is not a prime implicant of (F)d. Then, by property 4. 3. 2. d, there exists a j (jfi) such that: d d (3.) -> (t -) therefore tsj -> si But the existence of a j to satisfy (16), together with property 4. 3. l. d, contradicts the original hypothesis that si is a prime implicate of F. Therefore it is established that every member of the set {(si)d} is a prime implicant of (F)d. Assume 2nd: There exists a prime implicant (sk)d, (k=m+l), not in the set {(si)d} . Therefore, 3k is not in the set {si} , and by the original hypothesis it is not a prime implicate of F. Then, by property 4. 3. l.d, there exists aj (jflc) such that: t . -v sk SJ d d (17) therefore (sk) -> (tsj) But the existence of a j to satisfy (17), together with property 4. 3. 2. d, implies that (sk)d is not a prime implicant of (F)d, a contradiction of the second assumption. Therefore, it has been established that the m-member set {(si )9} is the set of all prime implicants of (F)d. 182 _'_7_.__Z_. A corollary can be given for the theorem of section 7. 1. The set consisting of the duals of all prime implicants of a truth func- tion is the set of all prime implicates of the dual function. Consider the expression: m F = p. (18) 1:1 1 If the m-member set {pi} is the set of all prime implicants of F, then in the expression: d m (F) =11 i=1 (1 (pi) (19) d . . . . d the m-member set {(Pi) } 18 the set of all prime implicates of (F) . Proof: By duality. 7. 3. The theorem of this section, and its corollary of section 7. 4, are results published by Nelson [45] . For a truth function F of n variables, expressed in any equiva- lent CNF as in (2): k F = 11' t . i=1 81 k E m the expansion (1r t .) = E p. (20) . 81 . 1 i=1 1:1 m gives equivalence F = 2 pi i=1 in which the m-member set { pi} k is exactly the set of all prime irn- plicants of F. Proof: By induction over k: Take k = 2; and assume, without loss of generality, that tsZ 7‘ t8 1' 183 Case 1: t + t82--18 a tr1v1al case since tsl -> F, thus t81 31 is logically equivalent to F. Since tBl is the disjunction of m distinct m literals (m S 11 because t3i is a clause), then F = tBl = E 1i’ in which i=1 the m- member set { 1i} is the set of all prime implicants of F. Case 2: tsl /~ tsZ’ Let the Zn literals be subscripted in correspondence to the 11 variables as follows: The first 11 literals are in l- l correspondence to the variables as they appear non-negated (li = vi); the second n literals are in 1- l correspondence to the variables as they appear negated (In-ti = v.). 1 Let t8 be the disjunction of a set of literals {1i} 1, while ts 1 2 is the disjunction of a set of literals {li}2. Furthermore, let the following sets of subscripts be defined: J = {illic {1i}1} K : {1|1i€{1i}2} 1=JflK (21) 11 = 1-1 12 = K-I Then, with the aid of (21), F can be written in the following form: tsltsz = (21i+ 2 1.)(2: 1. + 2 11) (22) id ie'Il i€I i€I2 ‘ Then the expansion, (F)E, can be written: E (t t) =21.+(21.)(21.) (23) 81 “2 161 1 161 1 161 1 l 2 Quite clearly, as in Case 1, every member of the set {lili £1} is a prime implicant of F. That every non- zero member of the set of product terms is also a prime implicant follows from the observation 184 that, since the sets I, 11, and I2 term subsumes either a single term or another product term. The are pairwise disjoint, no product zero terms are recognizable as members of the set {liljli €11, jEIZ, 1 and I2 are denoted r, rl and r2, respectively, then it has been established that (t81 tsZ) i = j :t n} . And if the cardinality of the sets I, I E is comprised of the disjunction of m (m s r + r1 r2) prime implicants of F. Denote the set of prime implicants, just found for F, as {pi}? It must be established that no other prime implicants exist. Assume that there exists a prime implicant of F which is not a member of that set, denote it Pk’ Now (t81 t82 + pk) must be logically equivalent to F. Therefore: F = ’31 t::2 ”’1: from which F = (tel +?82)Ek thus, for example F8151, -> F but 1'81 - ‘1')" (24) therefore 1.31 -e 3k °" Pk " tsl Similarly pk -v t82 From the construction of the set {pi}2, and from the last two rows of (24), it is clear that pk must subsurne some member of that set. That results in a contradiction, through property 4. 3. 2. d, of the assumption that pk is a prime implicant of F. Therefore it has been established that (t81 t E is comprised of the disjunction of the 32) set of all prime implicants of F. Take k + l clauses in the general case. Assume, as the in- duction hypothesis, that (20) is valid for functions comprised of a conjunction of k implicates. Then write F as: 185 F f1<’::(1:+1) k where fk = i:l tsi (25) k E m and (11‘ t .) = 2 pi i=1 8’ i=1 in which, by the induction hypothesis, the m- member set {pi }k is the set of all prime implicants of fk. Each member of that set is the con- junction of n-or-fewer literals corresponding to distinct variables, since each is a clause. Case 1: fk - ts(k+l)"is again atrivial case. fk -> F, and {pi }k is the set of all prime implicants of F, {pi }k+l' Case 2: fk [v ts(k+l); Invoke distributivity and, selecting one member of {pi }k’ examine one term of (f.k ts(k+l))E at a time. Let pj be the conjunction of a set of literals {li}l, while ts(k+l) is the disjunction of a set of literals {li}z. Using the definitions (21) for sets of subscripts, and if I is not an empty set, then: pjt8(k+l) = (1r 1.)(1r 1.)(}: 1. + 2 11) C O 1 O O 161 1611 161 1612 . E from wh1ch (Pjts(k+l)) - pj + pj(i62; 1i) (26) 2 E °’ ‘Pj’s(k+1)’ ‘ P1 k F. In case I is an empty set, (26) becomes: In this case Pj’ a prime implicant of f , is also a prime implicant of E (Pitstl<+l)) = p,( z 11’ (27) 1€I2 Expression (27) yields a disjunction of rz terms (r2 is the cardinality of 12), each of which is a conjunction of literals. For each of those 186 terms there are three alternatives; lipj is: a. zero, and of no further concern; b. a prime implicant of F, the desired member of {pi }k+l’ c. an implicant of F which subsumes some clause from the particular expansion involving some other mem- ber of {pi }k' In that case, this term will be deleted upon application of rule (12- a). Therefore, it has been established that all of the members of the set {pi }k+l which result from (fkt8(k+1))E are prime implicants of F. Furthermore, by an argument paralleling that of the discussion of (24)--which will not be repeated--that set is the set of all prime im- plicants of F. 1.3. As a corollary to the theorem of section 7. 3: For a truth function F of n variables, expressed in any logically equivalent DNF as in (5): k F = Z t . 1=1 P1 E m k l the expansion (2 tpi) = 11.1181 (28) i=1 - m gives equivalence F = 11' Si i=1 in which the m-member set {si}k is exactly the set of all prime im- plicates of F. Proof: By duality. 8. A New Method for the Simplification of Truth Functions A method will be proposed for the simplification of truth func- tions based on the theorems given in section 7. The steps involved in 187 the inductive proof of section 7. 3 furnish clues as to the manner in which this method might be programmed as an efficient algorithm. Full use is made of the duality theorems for truth functions in the statement of the method, in order that the method can be per- formed easily with pencil and paper. Rather than make use of the dual expansion method suggested in (28), it will be suggested that a dual problem be worked, and its results dualized. That step is taken only because it is much easier to work with the form of distributivity carried over from the algebra of real nurn- bers, due to its familiarity. The method can be programmed in a manner in which the importance of CNF and DNF, of implicates and implicants, is lessened--their presence becomes a matter of the inter- pretation of the initial form and final result. _8_:_l. For a truth function F, expressed in any logically equiva- lent CNF: a. (ME yields the set of all prime implicants. b. ( ( ( (F)E)d)E)d yields the set of all prime implicates. _8_._§. For a truth function F, expressed in any logically equiva- lent DNF : a. (((F)d)E)d yields the set of all prime implicates. b. ( ( ( (1“)d)E)d)E yields the set of all prime implicants. As an example of the procedures involved, consider the truth function given in DNF as (29). F = aEe + acd + he'd + ab’ea’ +2663 (29) In the sequence of lines of (30), the prime implicants of (F)d are being computed by the progressive incorporation of clauses. The first term 188 in a line represents, in general, the result from the previous line. The second term represents the dual of a new clause from (29). £2 = (a+'B+e)(a+e+d) £3 = (a+c+hd)(b+c+d) f4 = (c+ab+a3)(a+b+'c"+'3) (30) 15 = (ab+ad+ac+be+ed)('a'+b+'6+‘d) (F)d = (ab+ad+be+ed+abe+aed) After deletion of the final two terms from (F)d as subsuming clauses-- the only subsuming terms which were developed at any point--that ex- pression becomes the set of all prime implicants of (F)d. Dualizing each clause in that result to obtain (31), the result is the set of all prime implicates of F. F = 1rsi = (a+b)(a+d)(b+c)(c+d) (31) i Since (31) is in CNF, expansion of that equation will yield the prime implicants of F. That procedure is shown in the sequential lines of (32). Again two subsuming terms develop, and are deleted to yield the final result. 1’ (a+bd)(b+c) 3 4 (bi + ab + ac)(c +3) (32) = (b3 + ac + abc + abd) f F F = Epi = ac+bd i APPENDIX B TRUTH FUNCTIONS AND LINEAR GRAPHS 1 . Introduction This appendix presents a truth- function approach to the study of non-oriented linear graphs. The results obtained are original to this dissertation, and are of importance to the methods in the main body in several instances. The second section of the appendix constitutes an introduction to the terminology to be used, and to the concepts and results from linear graph theory which are of importance to this investigation. The re- sults are taken from the primary reference for this appendix, Seshu and Reed [57] . The terminology stems mainly from that source, but has been altered in order to take full advantage of the dual nature of many results. _l_._l_. Section 3 provides a set of new properties for two important arrays associated with linear graphs. From that set of properties, a new method is developed in section 4 for generating those arrays. The method and the properties provide a more thorough understanding of the arrays, and permit than to be used in a manner of particular impor- tance to the subsequent work. That work consists of the investigation of the two principal prob- lems treated in this appendix. _1_.__§_. The first such problem is one which has received a sub- stantial amount of attention--the generation of all trees of a graph. 189 190 The most straightforward method for finding all trees is to in- spect all possible combinations of 11C edges, and to list those com- binations which qualify. But (2e) combinations must be inspected; and in the computerized analysis ofcsystems of practical size, that number becomes too large for computational feasibility. (The numbers ne and nc will be defined in section 2. ) Mayeda and Seshu [42] apparently solved this problem satis- factorily in 1965. Their method has the following properties: a. An initial tree is required, along with the associated set of fundamental cut sets. Satisfactory methods are available to obtain them; b. Trees were generated without duplication. Thus, large intermediate storage was not required, as it would be if a tentative list of trees were generated, a search through the list being required in order to eliminate duplications of specific trees; c. The computation of the sign associated with each tree, a step required when dealing with directed graphs, was easily accomplished since each new tree was generated by means of the replacement of a single branch. However, the problem has continued to attract attention--in a quest for ever more efficient computer utilization. Mayeda, working with others [43] , devoted further attention to the problem in 1968. They proposed a different method which had an interesting flaw; duplicate trees were generated. An inspection of the list of references [ l] , [9] , [ l3] , [15] , [37] , [60] will illustrate that the problem 191 remains of current interest. The method to be presented here is different than all of those results. The generation of trees is of interest in several applications: a. It is often desirable to compute system functions in symbolic form, in practical applications, in order to study the effects of parameter variations and to com- pute sensitivities. Topological formulas exist which provide a very convenient method for that computation. Those formulas require the listing of all trees of the graph. b. Vidyasagar [62] , in an investigation of the problem to be discussed in section 1. 3, utilized the matrix of all trees of the graph. c. Trees have been found to have significance in the solu- tion to a clustering problem in pattern recognition. d. If the transportation problem in linear programming is formulated properly, the set of all basic solutions can be represented by the set of trees of a graph. Other applications can be found in the work of references. [ 5] and [ l4] . The new method for generating trees of the graph, to be pre- sented in section 5 of this appendix, has the following properties: a. An initial tree is required, along with the associated set of fundamental tie sets (more commonly known as loops or circuits). b. Trees are generated without duplication. c. Particular subsets of trees can be generated as desired. 192 This method does not permit the ready computation of the sign associated with a tree, a feature of the method of [42] . That property is of importance only when dealing with directed graphs, however. It is property c, the ability to generate particular subsets of trees, that sets this method apart--and furnishes its primary importance for this dissertation. _l_._3_. The second problem to be treated deals with locating an edge- incidence matrix among the set of all cut sets of a graph--or realizing a graph from a tentative cut-set matrix. The theoretical solution was given for this problem in 1960 by Mayeda [41] . Sushu and Reed discuss the problem at length in section 5. 5 of [57], stating the results succinctly in their Theorem 5- 29. The problem remains of current interest (see [ l 1] , [ 22] , [ 23] , [26] , [32] , [49] , [62] ), for a valid reason. The necessary and suf- ficient conditions given in [41] for realizability do not lend themselves well to mechanized testing. The truth- function method presented in section 6 is not a prac- tical solution to the problem. It will not lead to a computationally efficient algorithm. However, a solution is found for graphs of rank 3, based on some results from section 3; and a general observation is made which hints that the potential is there for obtaining a practical solution to the general case. 2. Symmetiy in Linear Graphs All of the linear graphs, in the restricted set to be considered in this dissertation, have one important property; they are non-separable. Furthermore, this appendix will deal only with non- oriented graphs. 193 Due to the latter property, truth functions can be applied directly in the investigation. The usual operators, conjunction and disjunction, will be used extensively. But an additional operator, 'ring sum' ('addition modulo 2', 'exclusive or', 'equivalence'), will be used; its use will be denoted by the symbol ' G) '. The graphs will have the following well-known numerical proper- ties: a. neuthe number of edges of the graph; b. nv--the number of vertices of the graph; c. nc--the rank of the graph: (nc = n - l); d. ntuthe nullity of the graph: (nt = ne - nc). ‘24. There are two symmetrical sets of edge-combinations, associated with a linear graph, of central importance in graph theory; cut sets and tie sets. (The latter terminology, "tie sets", will be adopted from Guillemin [29] in place of the more common 'circuits' or 'loops'. ) A row vector will be used to denote a set of either type. It will consist of ne entries, ordered in correspondence to the edges of the graph. The entries will be 1's for the edges contained in the particular set, 0's for those omitted. When these row vectors are listed in arrays, the columns will be given a designation, (ci), which some- times will be us ed interchangeably with the designation of the corre- sponding edge, (ei). Two linear vector spaces (over the field mod 2), discussed in section 4. 7 of [57] , will be of central importance in this appendix. Their composition, and the terminology to be used for them, is dis- cussed below. 194 2. l. l. The set of all row vectors, which are either: a. cut sets of the graph; -or- b. unions of edge-disjoint cut sets of the graph; will be called the Cut Set Array (CSA). When the zero vector is appended to complete the linear vector space, the result will be called the Augmented CSA (ACSA). LL;. The set of all row vectors, which are either: a. tie sets of the graph; -or- b. unions of edge-disjoint tie sets of the graph; will be called the Tie Set Array (TSA). Similarly, the zero vector will be appended to this array to form the Augmented TSA (ATSA). _Z;;. There are some special members, in each of those arrays, which are given particular designations. They are called fundamental sets. 2. 2. l. A fundamental cut set bears a particular relation to some tree of the graph. It contains a single 1 among its entries in the set of columns associated with branches of that tree--its entries in the set of chord- columns can be mixed. There exists a unique set of nc row vectors: each one has the preceding property; and each has its l-entry appearing in a different branch-column. That set is known as the set of fundamental cut sets associated with the tree. It will be designated Fc' Fc is an (nc x ne) array. It is called Of in [57] . LL;. A fundamental tie set bears a particular relation to some tree of the graph. It contains a single 1 among its entries in the set of columns associated with chords of the cotree--its entries in the set of branch-columns can be mixed. There exists a unique set of 11, row vectors: each one has the preceding property; and each has its l-entry appearing in a different 195 chord-column. That set is known as the set of fundamental tie sets associated with the tree. It will be designated Ft' Ft is an (nt 1: ne) array. It is called Bf in [57]. L3. A certain symmetry is becoming apparent. That symmetry carries over into the discussion of the properties of the CSA and the TSA. In order to discuss both simultaneously, let the range of the symbol X be the set {C, T}. In a particular context, Y will represent the complementary member of that set. Using that coding, the following observations can be listed: a. The AXSA is an (201x) x ne) array. b. Every basis for the row- space of AXSA contains nx vec- tors. c. Fx is an (nx x ne) array; Fx spans the row- space of AXSA. d. The normal method employed to generate the XSA is to apply ring sum, in an exhaustive manner, to the row vectors of a basis for AXSA. e. A vegy important result, given in Theorem 4-14 of [57] , can be written: [XSA] [25A]T = [0] (mod 2) (1) 3. Prpperties of the XSA Two sets of properties will be established for the XSA in this section. The members of each set are similar; they represent se- quential members in a chain of properties. Then a final property will be given which represents, in an intuitive way, the junction of those two chains. 196 L;. Certain sets of columns of the XSA can be found to be re- lated in a particular manner. LL;. There may exist repeated columns in the XSA. The following 19.12 will be observed throughout this appendix: When sets of repeated columns are found in the XSA, delete all, except one, of the columns from each such set of repeated columns. That simplification is possible because, for both problems discussed in sections 1. 2 and l. 3, the results for repeated columns are quite simple to state. _3_._L;. The n members of a set {Ci} of columns of the XSA (which are associated with the set {ei} of edges of the graph), and whose subscripts form the index set, I; are related by: 2: ci = 9 (mod 2) (2) iEI if, and only if, the edges {eili 6 1} form an-x-set (or a union of edge- disjoint 'x-sets) of the graph. _P_1_'_9_q_f_: That set of edges represents the set of all 1's which appear in an annihilating vector of XSA. By (1), that vector must be a row in YSA. N333: Every pair of columns from a repeated set, as in 3. l. 1, presents an example for the case (n = 2) here. _IL;. This pair of properties, which deal with the contents of the columns of XSA, can be proved by induction over nx. That proof would also require an exact formulation of a procedure for generating XSA by ring sum over Fx. However, they can also be deduced from properties 3. l and 3. 3. No proof will be given. 197 3. 2. 1. In each column of the AXSA, exactly half of the entries are 1's. Interpretation: Each edge is a member of half of the cut sets (tie sets) and unions of edge- disjoint cut sets (fie sets) of the graph. _3_._Z_._;. Every pair of columns of the XSA (following application of rule 3. 1. l) is related in the following way: the set of rows which contains all of the 1- entries of one column (and none of the 0's) con- tains exactly half of the 1- entries of the second column (and an equal number of 0's). Interpretafion: Every pair of edges of a graph (bar- ring those for repeated columns) appear together in one-fourth of all of the cut sets (fie sets) and unions of edge-disjoint cut sets (tie sets) of the graph. Comment: This pair of properties is either very intuitive, or very counter-intuitive; but it remains for the reader to make the choice. _3._3. Every XSA, under a rearrangement of its rows and columns, can be well- ordered (indexed) in its first nx columns with binary representations of the numbers 1 through (2(nx) - l). 2593;: It is necessary and sufficient that the first nx columns be selected so that no subset (including the entire set) of those columns is related by (2). a. For the CSA, it is necessary and sufficient that the first nc columns correspond to a branch-set (tree) of the graph; by 3. l. 2 and Theorem 4- 10 of [57] . b. For the TSA, it is necessary and sufficient that the first 11 columns correspond to a chord-set (cotree) t of the graph; by 3. l. 2 and Theorem 4- ll of [57] . 198 4. A New Formulafion of the XSA Two new methods for generating the XSA will be discussed in this secfion. The first, a truth- function technique, will only be out- lined. It is quite interesfing, but would not serve as a practical method; the computafions required in order to generate the XSA are fairly extensive. Conversely, the second is a simple, feasible method. It will be important in the subsequent secfions. iii- The transpose of the XSA is the right-hand annihilator (RHA) of the ESA, by (1). It is also, of course, the RHA of Fx--or of any basis for the row space of YSA. Therefore, the set of all row vectors which safisfy: [F3211T = _9_ (mod 2) (3) must be the set of all rows of AXSA. Consider a truth function, F, of ne variables: x F = 1r fi (4) i=1 Let each fi in (4) be formulated from a different row of F1. If that row contains ni 1's, fi will be a truth funcfion of ni variables: f.=2t. 5 1 ij () Each clause in the set {tpj} will be formed by taking some unique _eye_n_ set of the ni variables in non-negated form, the remainder in negated form, and joining them all with conjuncfion. The complete set will be formed by exhausting all possible combinations of that nature. That function, fi, has some interesfing properties: a. fi is self-dual; i. e. , fi = (fi)d. b. {tpj} is the set of all prime implicants of fi' 199 c. {(tpj)d} is the set of all prime implicates of fi' d. Under a careful interpretation, {tpj} is the set of all annihilating vectors for the associated row of Fi' As a result of those properties, F can be expressed immediately in CNF. The expansion of that expression will yield the set of all prime implicates of F. (F)E = 2p (6) The prime implicants of F, the clauses of (6), have the following properties: a. Each clause is a min term of F; b. Each clause can easily be interpreted as an annihilating vector of FE; c. Under that interpretation, the set {pk} is the set of all rows of AXSA. _4_._;. Let the columns of the XSA and of F3: be ordered in the same manner. The ordering of the first nx columns is arbitrary, but the final 111. columns will be ordered so that they form an identity matrix in F371. Let the subscripts of the first nx columns form the index set, I; the subscripts of the last ILx. columns the set J. Consider the jth row, Fii , of F3. Column cj (j 6 J) contains the distinctive l for that fundamental i—set. Let the subscripts, of the columns which contain the remaining 1's of that row, form the index set, Ij’ (IjCI). Each F‘ij leads to an equation of the form (2) for the columns of the XSA; that equafion can be rewritten as: c. = E c. (mod 2) (7) J 1te 1 200 Inteijpretafion: Each of the final nx columns of the XSA can be formed as the ring sum of a particular subset of the first nx columns, in accordance with an equation of the form (7). The rows of FEE yield the required subsets for each of the specific columns. Method: The steps to be taken in the generation of the well- ordered XSA are as follows: a. Obtain F? from a tree of the graph; b. Generate the binary representations of the numbers 1 through (2(nx) - l) in the first nx columns; c. Generate the final n.)—K columns by ring sum on the in- dex set of columns as indicated by equations, in the form (7), obtained from F3?’ 4. 3. As an example of the applicability of the generation pro- cedure, an array will be generated which contains all possible columns of the: a. CSA for a graph with four branches per tree; b. TSA for a graph with four chords per cotree. That step can be taken by completing the linear vector space for the column vectors of the XSA. The set of index columns must span this column space; ring sum will be applied to them in the exhausfive manner indicated in Table l, the rows of which each yield an equation of the form (7). Column: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 l 0 0 l 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 l 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 l 0 0 0 0 l 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 l 0 0 0 0 0 l 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 l 0 0 0 0 201 Column: 1 2 3 4 5 6 7 8 9 10 ll 12 13 14 15 l l O l O 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 1 1 l 0 0 0 0 O 0 O 0 0 l O l l l l 0 0 0 O 0 O 0 0 0 0 1 Table B- 1: All Possible Fundamental Y-Sets-then nx = 4) The completion of Table 1 corresponds to step a. in the process of generating the XSA. The final result is obtained by completing steps b. and c. That result is listed in Table 2. Column: 1 2 3 4 5 6 7 8 9 10 ll 12 13 14 15 0 0 0 1 0 0 1 O 1 1 0 1 1 1 1 0 0 1 0 0 1 0 1 0 1 1 0 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 0 0 0 0 1 0 0 1 0 0 1 1 0 1 1 0 1 1 0 1 0 1 1 0 l l 0 1 1 0 1 0 0 O 1 l 0 1 1 0 0 l l 0 l l 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 l 0 1 1 0 0 l l 1 0 0 1 1 1 0 0 1 0 l 0 l 0 l O l l O l 0 l 0 l 0 l 0 l l l 0 O 1 l 0 0 O l 0 l 1 1 0 0 0 1 l 1 1 0 0 0 1 l 0 l l O l 0 l 0 l 0 l 0 1 0 0 l 1 1 1 0 0 0 1 0 1 l 1 0 0 0 1 l 1 l l O 0 0 0 0 0 1 l l l 0 Table B-2: All Possible Columns for the XSA--(when nx = 4) 5. Generating Trees of the Graph This section will present a new method for generating trees of a linear graph. A procedure will be developed by which specific subsets of trees can be generated. An overall procedure can then be formu- lated, using the previous result in a systemafic manner, for generating all trees of the graph, without duplication. A truth-function method will be proposed, as a first step, for generating all trees of the graph. This method, like the first method in secfion 4, will not be computationally efficient. 202 A detailed invesfigation into the simplificafion of the truth func- fion will be taken as the next step. The results of this invesfigation, when coupled with the method of secfion 4. 2, will permit the genera- fion of subsets of trees in a practical manner. Since trees and cotrees are complementary edge-sets for a graph, the problem can be worked in either of two ways. The rela- tive sizes of the rank and nullity might be used as a basis for making a choice between the two alternatives for a given graph. However, the discussion will be framed entirely in terms of the generafion of trees from the CSA. The dual method can be accomplished in a parallel manner, by means of the same sequence of steps. L;. Theorem 2- 14 of [57] , which states that each out set con- tains at least one branch of every tree, suggests a truth- funcfion technique for finding all trees of a graph. Let a set, {fi} , of unate truth funcfions be formed, one for each row of the CSA. The function, fi, will be the disjunction of all edges which appear in the out set represented by the ith row. Suppose, for example, that a particular row contains 1- entries only for the edges 3, 5 and 11. Then that fi can be interpreted as, "Either edge 3, or edge 5, or edge 11; or some combination of those edges (since disjunction is an 'inclusive or'); must appear in every tree of the graph. " Then F, a unate truth funcfion of the ne edges, can be formulated as: F = Trf. (8) F implies fi, for all i; that is, F 'true' indicates that the theorem has been satisfied for every row of the CSA. Furthermore, since each 203 clause in (8) is a disjuncfion of variables, F has been formulated directly in CNF. Thus, its expansion yields the set of prime impli- cants. The set of all prime implicants of F has the following properties: a. Each consists of the conjuncfion of nc edges; b. Each can be interpreted as a tree of the graph; c. Under that interpretation, the set of all prime im- plicants is the set of all trees of the graph. The method might seem impracfical since the entire CSA is re- quired. However, as suggested by the inductive proof in section A-7. 3, the rows of the CSA can be incorporated one at a fime into the simplificafion of F. And, by the method of secfion 4, the rows can easily be generated one at a time. There is another disadvantage, however. Large intermediate storage will be required, because the set of all trees will become available all at one fime. The enfire set becomes available at the incorporafion of the final row of the CSA. _5_.;. It is known, from property 3. 2. 1, that edge ej appears in half of the rows of the ACSA. Let the set of functions for those rows be denoted {fil ej _- fi}; let the subscripts of those functions form the index set, Ij. Each of those functions can be written as: fi = ej + gi (i E Ij) (9) in which gi is the dis juncfion of the remaining edges found in that cut set. As that set of rows is incorporated into the simplificafion of F, the following partial result will be obtained: 204 (1rf .)E 161. 1 J = e. +( 11 g.)E (10) J 161. 1 J The interpretation of (10) is very informafive. No tree con- taining ej is obtained from the cut sets in which ej appears. Rather, all trees containing ej will be obtained from the conjunction of ej with the set of fi corresponding to cut sets in which ej does not appear. It is known, from property 3. 2. 2, that one-fourth of the rows k funcfions for those rows by {filue-j ek —> fi}; let the subscripts of those of the ACSA do not contain ej but do contain e . Denote the set of funcfions form the index set, Ijk' Each of those funcfions can be written as: f1. = ek+gi (1 €Ijk) (11) It is apparent that: ( 1r fi)E = ek +( 11' gi)E (12) iEI. iel. Jk Jk All trees containing the pair of edges ejek are to obtained from the conjuncfion of that pair of edges with the set of funcfions for the cut sets in which neither of those edges appears. The general inducfive continuation of this process can be given. Select any set of n edges (11 5 nc) which all are branches of some tree of the graph. Let the subscripts of (n- l) of those edges form the index set, I; let the remaining edge be ek. This set of edges satisfies the conditions of secfion 3. 3. (n -n) It follows that there are 2 C rows of the CSA in which e k appears but no ej (j 6 1) appears. Denote the functions for those rows as {fil ek( 1r Ej)»fi}; let the subscripts of those funcfions form the .61 index set, Ijk' With those definitions in force, equafions (11) and (12) apply to this general case. 205 Inspection of those equations reveals that: a. For the special case, n = nc; the cardinality of Ijk is unity. The single equation of the form (11) yields the subset of all trees, which contain all of the edges in the set {ejlj 6 I}, as: {T}I = (ck + gi)-:Iej (13) J b. When n < nC; the trees containing all n edges of the set can be found as: E {T} = e (11' e.)( 11' g.) (14) I. k . . 1 Jk _ ~161 J 1€Ijk Notice that the truth function to be sim’ plified in (14), which (n -n) c represents (2 - 1) rows of the CSA, contains none of the n edges which specify the desired subset of trees. L3. The preceding development can be applied in many ways to formulate methods for generating all trees of the graph. One par- ficular method will be given here. Consider the well- ordered CSA of secfion 4. 2. If subsets of trees are generated which contain unique combinations of the branches of the initial tree, upon which the CSA was based, then the subsets will be mutually dis joint-~no duplicate trees will be generated. Not all trees of the graph will include branches of the initial tree, but the process will be extended in order to generate those trees also. P_e_fir_1_e_ the 'remaining' columns to mean those which are not serving, and which have not previously served, as index columns of the CSA. The truth funcfions to be simplified will have as variables only those edges associated with remaining columns. In the first iterafion of the process, the nt columns corresponding to chord-set edges will be the remaining ones. ‘III I 206 The first column of the CSA will be pivotal in this process. In the first iteration, any branch of the inifial tree will serve satisfac- torily as the first column. However, when a tree is selected to serve as the basis for the next iteration; some branch, which appears in at least one of the fundamental tie sets for the remaining columns, must be selected to serve as the first column of the new CSA. In each iterafion, the first branch will be taken together with all possible combinations of the other branches (including the combination in which none of the other branches appears); and specific subsets of trees will be generated according to (14) for each combination. The fundamental tie sets for the remaining columns will be used, according to (7), to generate the rows of the CSA in which zeroes occur for the branches appearing in the particular combination. These rows form the {gi} to be used in (14). To select a tree on which to base the next iteration, it is only necessary to select one of the remaining columns which represents a fundamental tie set in which the first column appears. The first column is then dropped from further consideration, and the newly selected column replaces it in the tree and becomes one of the index columns for the CSA of the next iteration. When only one column remains, ,the tree selected as above, to start the next iterafion, will be the final tree generated. L3. The simple results, menfioned in section 3. 1. 1, will now be given for repeated columns of the CSA. Consider any such pair of columns. Since they correspond to a tie set of the graph; either one, or the other, or neither, but_r_1_o_t both--can belong to a given tree (by Contraposifive on Theorem 2- 14 of [57] ). All trees have been found 207 which contain neither, as have all trees which contain the non- deleted member of the pair. Clearly each tree which contains one member of the pair will give rise to another tree. Direct edge- replacement will serve to accomplish that generation. Thus, as each tree is generated, it is inspected for edges which represent sets of repeated columns of the CSA. When such edges are detected, additional trees are generated for each member of the re- peated set. L5. The example given in [42] will be worked here by the method just presented. The linear graph is presented in Figure l. Figure B- l: The Linear Graph for the Example An inifial tree is selected, (1, 2, 3). The fundamental fie sets are derived from the graph, for that tree, and listed in Table 3. Edge: 1 2 3 4 5 6 7 1 o 1 1 o o o o 1 1 o 1 o o 1 1 o o o 1 o o 1 o o o o 1 Table B-3: The Fundamental Tie Sets for the Initial Tree Inspection of Table 3 reveals that Column 7 of the CSA will be a repeat of column 2. Therefore, edge 7 is deleted. Then the required rows of the CSA, for the first iterafion, are generated and presented in Table 4. 208 Edge: 1 2 3 4 5 6 o o 1 1 1 o o 1 o o 1 1 o 1 1 1 o 1 1 o o 1 o 1 Table B-4: The Rows of the CSA for the First Iteration The truth function generated from the first three rows of that array is shown in equation (15). The second line shows the trees generated from that equafion, plus the initial tree. The third line shows the trees generated by edge-replacement due to the repeated columns. F -.-. e1(e2(e4 + cs) + e3(e5 + e6) + (e4 + e5)(e5 + e6)(e4 + 86)) {T}1 = {(1.2.3). (1.2.4). (1.2.5). (1.3.5). (1,3,6), (1,4,5).... ---. (1.4.6). (1.5.6)} (15) mm = ((1.3.7). (1.4.7). (1.5.7)} From the last row of Table 4, it is apparent that edge 1 may be replaced either with edge 4 or edge 6. The tree (2, 3, 4) will be used for the second iterafion. The fundamental fie sets for the remaining columns, based on that tree, are shown in Table 5. Edge: 2 3 4 5 6 1 l 0 l 0 l l l O 1 Table B-5: The Fundamental Tie Sets for Iterafion Two The required rows of the CSA are shown in Table 6 for use in the second iteration. Edge: 2 3 4 5 6 0 0 1 0 1 0 l 0 l l 0 l l 1 0 1 0 0 1 1 Table B-6: The Rows of the CSA for Iteration Two 209 Equafions (16) show the truth function derived from the first three rows of Table 6, the trees, and the replacement trees. F -.- eZ(e3(e6) + e4(e5 +e6) + (e6)(e5 +86)(85)) {T12 = {(2. 3.4). (Z. 3. 6). (2. 4. 5). (Z. 4. 6). (Z. 5. 6)} (16) {T12R = {(33.4.7). (3.6.7). (4.5.7). (4.6.7). (5.6.7)} From the last row of Table 6, edge 2 can be replaced by either of the remaining edges. The tree (3,4, 5) will be used for the third iterafion. Its fundamental tie sets are shown in Table 7. Edge: 3 4 5 6 O l 1 1 Table B-7: The Fundamental Tie Sets for Iteration Three The required rows of the CSA are shown in Table 8. Edge: 4 3 5 6 0 0 l 1 0 1 0 0 0 l 1 1 1 0 0 1 Table B-8: The Rows of the CSA for Iteration Three Equafions (17) show the nearly vacuous truth funcfion, and the set of trees generated--including the final one, from the fourth row. F = e4(e3(e6) + e5(0) + (e6)(0)(66)) (l7) {T}4 = {(3,4,5), (3,4,6), (3,5,6)} 6. Findingthe Edge;lncidence Matrix by Truth Fu_nction A truth-funcfion method will be presented for finding an edge- incidence matrix within the CSA of a graph. This method has the property that the set of all 2-isomorphic graphs (see Definition 3-4 of [ 57] ) is contained in the result. The method is not a pracfical one because, although it does not (11 ) require the storage of the CSA, the (2 C - 1) rows of the CSA are the 210 variables of the funcfion. The solution procedure becomes overwhelm- ingly large for practical graphs. However, some properfies of the solution are invesfigated; and progress is made towards finding a more tractable method. _§_._1. The problem of finding an edge-incidence matrix in the CSA is one of locating a particular type of 'row cover' for that array. A set of nv rows must be selected in such a way that every column con- tains exactly two 1's. The rows of this matrix can be interpreted as verfices of the graph; the two l's indicate the vertices upon which the edge terminates. A set, {fi}, of truth funcfions will be formed; one for each column of the CSA. The variables appearing in the funcfion, fi, will be the half of the rows, of the ACSA, which contain l-entries for that column. Each fi will be a disjuncfion of 2(nc- Z)(ch. l) - l) clauses. Each clause will contain a unique pair of the row variables appearing in non- negated form, with the remainder appearing negated. The column functions have the following properties: a. The set of clauses, so constructed, forms the set of all prime implicants for the function; b. The funcfion, therefore, can be regarded as having been expanded from a CNF. A truth function, F, is formed as the conjuncfion of all ne mem- bers of the set {fi}: F = 1r fi (18) i (n ) The variables of F are all of the (2 c - 1) rows of the CSA. Comple- fion of the expansion of (18)--already parfially carried out, as indicated in b. , above--yields the set of all prime implicants for F. That set of 211 prime implicants has the following properties: a. All of the prime implicants are min- terms of F; b. The non-negated variables in each clause indicate the rows of the CSA which are to be included in that row- cover; c. All possible row- covers for the CSA, which meet the condifions stated for the columns, are contained in that set. However, the nv restricfion on the number of rows has not been incorporated into the procedure. Not only are all of the Z-isomorphic edge- incidence matrices included in that set, but sane simpler row- covers may also be included. Simpler covers can result, for example, when: a. Two (or more) edge-disjoint cut sets occur in an inci- dence matrix; b. The delefion of an edge of the graph, by collapsing its verfices into coincidence, leads to repeated columns in the new CSA. LL Two examples will be given here to illustrate the results of section 6. 1. Figure 2 shows the linear graphs for both cases. 6 (b) Figure B-Z: Two Linear Graphs The tree (1, 2, 3) is selected for each case. The fundamental tie sets are generated according to that tree, and listed in Table 9. Edge: 1 OH HO hug—a .1; OH (a) Table B-9: The Fundamental Tie Sets for the Two Cases U1 HQ 212 Edge: HOH D-i l 1 0 (b) OOH OHO HCO 0 The well- ordered CSA is generated, for each example, by the method of section 4. Edge: 1 HHHHOOO 2 HHOOHHO 3 HOHOHOH The results are listed in Table 10. 4 OHOHHOH (a) Table B- 10: The Well- Ordered CSA for Each Case 5 OHHOOHH Edge: 1 HO—‘I—IHOOO 2 HHOOHHO 3 HOHOHOH (b) 4 5 1 1 0 1 l 0 1 0 0 1 l 1 0 0 O ooHHHHO The truth funcfion is formulated and simplified for each case. The disjunction of the set of all prime implicants is shown in (19) for each case. F =rr?r a 123456 F r? b ‘: r1’21'3’4 r -i-r-1T 7 1 r-fr 567 +rrrrr 1 23 2r3r4r5r6r7 + r 4 5 6r? 1r2r3r4r5r6r7 + rlr 2’3 4r5r6r7 (19) The row-cover matrices are shown in Table 11, as selected from the CSA for the respecfive examples according to the prime implicants of the truth functions. Example a. has two 2-isomorphic edge-incidence matrices (re- presented in Table ll-(a) and (e) ), and two simpler row covers (Table l 1- (c) and (f) ). Example b. has a unique edge-incidence matrix, and a single simpler row-cover (Table ll-(b) and (d), respecfively). 213 Edge: 1 2 3 4 5 Edge: 1 2 3 4 5 6 0 0 1 1 1 0 0 1 1 1 0 0 l O 0 l O 1 O O l 1 l 0 0 1 O l 0 0 1 0 l 1 1 l 0 0 1 l 1 0 0 0 (a) - rows (1, 2,4,7) (b) - rows (l,2,4,7) 0 0 l l l 0 1 l l 0 l 1 1 0 1 1 1 0 1 0 1 1 l l 1 0 0 l l 0 l 1 0 (c) - rows (1,6,7) (d) - rows (3,5,6) 0 1 0 0 1 0 l l l 0 l 0 0 l 0 1 0 1 0 l (e) - rows (2,3,4,5) 0 l l 1 0 1 0 l 0 1 1 1 0 1 1 (f) - rows (3,5,6) Table B-ll: All Row-Cover Matrices for the Two Cases 2°23 The simple results, menfioned in secfion 3. 1, can be given now for repeated columns of the CSA. Since a row-cover can be found for the non- deleted member of a set of repeated columns, that same row-cover will obviously work as well for the repeated columns. Notice, as an example, that the linear graph of Figure l is the same as the one in Figure 2-b; except for the addition of an extra edge, in the former, which led to the existence of a pair of repeated columns in the CSA. Thus, for the graph of Figure l, the row- cover matrices can be derived from Table ll-(b) and (d); merely by adding a column, for edge 7, which duplicates that for edge 2. 214 p._4_. Consider the well-ordered CSA. Observe that, for a graph of rank nc; the truth function, formulated as the conjunction of the sub- set of {fi} associated with the first nC columns, will always be the same. That funcfion displays no dependence on any properfies of the graph, which the CSA represents, other than its rank. Therefore, since the results will never change (for a given nc), that function can be simplified once, the results will apply for all time. That function will contain, as variables, all of the rows of the CSA. Its prime implicants will all be min-terms. Moreover, all pos- sible row-covers will be contained in that list-- as each addifional column of a particular CSA is incorporated into the overall truth function, it can only serve to eliminate some of the possible candidates from the list. Since some simpler row- covers, for which the indicated number of rows is less than nv, are included in the list; they can be eliminated at once. Thus, if some tractable method can be found to indicate the available row-covers as a function of nc; and if the deletions from that list can be made easily, column by column, for the final nt columns of the CSA; then the truth- function method will have served well in pro- viding the conceptual foundation for a practical method. p:_5_. Consider, for example, the case (nc = 3). This case can be solved by inspection. Table 12 presents the array generated as the complefion of the column space of a CSA of rank 3. Column: 1 2 3 4 5 6 7 0 0 l 0 l 1 1 0 l 0 l 0 1 l 0 l l l 1 0 0 l 0 0 l l 0 l l O l l 0 1 O l l 0 0 1 l 0 1 1 l 0 0 0 1 Table B-12: All Possible Columns for a CSA (when nc = 3) v. : ' L 215 The final four columns of Table 12 happen to specify all possible edge-incidence matrices for graphs of rank 3. That is, the set of 1 entries in each of those columns indicates a set of rows which will serve as a row- cover matrix for the index columns--in fact will so serve for all columns other than itself. That this must be true follows as a direct consequence of properfies 3. 2. l and 3. 2. 2. Thus, in any case; the particular set of columns, missing from the set of all possible columns of the CSA, specifies the set of edge- ..." incidence matrices for the 2-isomorphic graphs. The set of all possible fundamental tie sets is listed in Table 13. Table 12 was generated, according to the method of section 4, from this information. An example is given in Chapter VIII to illustrate how the missing fundamental fie sets indicate the available edge-incidence matrices from a CSA. Column: 1 2 3 4 5 6 7 1 1 0 l 0 0 O l 0 l 0 l 0 0 0 l l 0 0 l 0 1 l 1 0 0 0 1 Table B- 13: All Possible Fundamental Tie Sets (when nC = 3) APPENDIX C OPTIMAL N-REDUCIBILITY FOR BEHAVIORAL DIAGRAMS It was seen, in Chapter II, that after obtaining a streamlined be- havioral diagram for an object--an n-reducible loop structure- -, an 7‘ optimal set of n vertices was needed in the process of obtaining the be- havioral relafions. This appendix will present a method for obtaining, simultaneously, the index (n) of the loop structure, and the set of ver- tices to be used. 1. Introducfion This appendix presents some familiar material, along with some original results. The directed-graph version of the loop structure represents an application of the familiar Mason- Coates signal flow graphs [l6] , [l7] , [38] , [39] , [40]; in this application, the flow is one of functional dependence. The central problem treated in this appendix is listed by Seshu and Reed as one of a set of "difficult research problems" (see page 299 of [57] ). Problem 11 of that set is the perfinent one. The problem has a wide variety of applications. For example, the material of secfion 2 of this appendix is very similar to the method of analysis of sequential machines us ed in secfion 9-2 of [57] . The 'path matrix', P of (3), is their "connection matrix", C, for example. The material of secfion 2 is included only to demon- strate that the set of all "feedback loops" can be listed in a systematic manner. 216 217 ;._1_. The doctoral dissertation of Lempel was addressed to this central problem, as reported in [36] . Divietti and Grasselli [20] pointed out that his solution was, in essence, one of finding prime im- plic ants of a truth funcfion. They missed the important point that the funcfions involved are unate; consequently, they were concerned in unnecessary detail with finding covers for tables of prime implicants. Moreover, they ignored the first portion of the problem--that of sec- fion 2, here. H The treatment in [36] uses the terminology of Berge [4] ; it deals 2 with an "edge- incidence matrix", whose "permanent expansion" cor- ) — responds to the idempotent path matrix of (6), in order to find the mini- mal sets of edges (2) to be cut in the process of destroying all feedback paths. The treatment in [36] then deals with a "vertex-incidence matrix", in order to find the minimal sets of verfices (15) to be opened for the same purpose. Another solution worthy of notice was given, for the central prob- lem, by Guardabassi [28] . His solufion does not require the listing of all feedback paths, of (7). His procedure is quite complex, being PT necessarily less direct than the other methods, and does not appear to require less work in obtaining the desired minimal sets of verfices. _li. The approach taken in this appendix; to obtain the minimal sets of both edges and verfices, from the listing of all feedback paths; is based entirely on truth funcfions. A major simplification occurs; due to the viewpoint that vertices are 'switches' which control trans- mission through the incident edges. This viewpoint, utilized in (14), permits both problems to be worked on the same basis--i. e. , the 218 minimal sets of vertices can be found from the trace path of the idem- potent path matrix. The material from Appendix A proves to be of importance. The set of prime implicates of the unate truth function becomes the desired result. 2. The Method of Path Aljebra This section describes how the listing of the set of all feedback paths, in the streamlined behavioral diagram, can be obtained. First, the diagram can be drawn in the form of a directed flow graph, which displays the systematic (cause- and- effect) dependence of every system variable on the others. The vertices of this digraph represent the variables (free and bound) of the behavioral diagram. Let them be numbered 1 through m. The edges of the digraph each show a direct dependence, by means of a path through some one element, of variable j on variable i. Let those edges be designated (given the 'value') eij’ accordingly. There will be a set, E0, of 'vacuous' edges: E0 = {eij'vj does not depend directly on vi} (1) Assign the value 0 to every member, eij 6 E0. There will be a set, E1, of 'self- edges': E1 = (en-Inn (2) Assign the value 1 to every member, e.. 6 E 13 1’ Construct the (m x m) path matrix, P: P = [eij] (3) This matrix can be interpreted as containing all directed paths of length one (passing along one edge) from vertex i to vertex j (for all i,j) in ‘1 r ‘ 219 the digraph. The diagonal 1's represent trivial 'self-paths'; the 0's represent 'no-paths'. ;.__1_. Some rules will be established for the manipulation of path matrices. There will be two operators in use; conjunction and dis- juncfion. Disjunction will be both commutafive and associative under all conditions. Conjunction will be an operator with restrictions similar to those for matrix multiplication. When either one (or both) of the quantities under its influence are members of the pair (0, l), conjunction will be both commutative and associative. However, when both quantities are paths; conjunction will be associative but not comrnutafive. The loss of commutativity is due to the directed nature of the digraph. Conjuncfion will be distribufive over disjunction, left and right. Paths will be defined recursively, as follows: a. Every edge (exclusive of members of E0 and E1) is a path; b. Every conjuncfion of two edges is a path, provided that the second subscript of the first edge is identical to the first subscript of the second edge; c. Every disjunction of two paths is a path; d. Every conjunction of two paths is a path, provided that the second subscript of the last edge in the first path is identical to the first subscript of the first edge in the second path. Some rules to be followed, in the simplification of path algebra expressions, are the following: 220 11 = 1 1-+1 = 1 oo = o o-+o = 0 10 = o 1-+o = 1 0p=0 (4) 0-+p = p 1p = p 1-+p = 9 pp = p P+P=P P1 + 13,102 = p1 p1 +pzpl = P1 The tenth rule in that list is an unusual one. It serves to eliminate the self-paths from further considerafion. ;._;. A sequence of matrices will now be developed. The final matrix of the sequence is of parficular interest in this application. Construct the matrix: Pk+l = PkP (5) In that construcfion, the rules of algebraic simplification in (4) are to be followed throughout. Pk has the property that pij is the disjunction of all paths of length k or less, from vertex i to verfix j, of the digraph. The first idempotent matrix, Pn, which has the property: Pp = pf+5 (i=1,2gg...) (6) .t. 221 has the additional property that its 'trace path', the path formed as the dis juncfion of all of its diagonal paths: m p = p T i=1 (7) ii is a 'sum-of-products' in which the conjunctive terms are exactly the collection of all 'feedback' paths (closed loops) for the n- reducible loop structure. _Z_.;. Consider an example of the application of the procedure of this secfion. Figure l, a streamlined behavioral diagram, shows three elements (a, b, c), one free (input) variable (v1), and three bound variables (vz,v3,v4) for the object. Free output variables are not of interest, in the Phase I procedure of secfion II-S. 3, and none are 3 hown. Figure C- l: A Streamlined Behavioral Diagram A directed graph is constructed for the same object. Figure 2 shows that digraph, with the corresponding vertices and the appropriate set of edges (e12, e23, e24, e32, e43). Figure C-Z: The Directed Flow Graph for the Example 222 The path matrix can be formulated from Figure 2, as follows: r- '1 1 e12 0 0 0 l e e P = 23 24 (8) 0 e32 l 0 _0 0 e43 1 _J The intermediate matrix, P2, can be computed from (8). P 1 e12 e12°23 e12624.) 0 e e e +e e e P2 = 23 32 23 24 43 24 (9) 0 832 632823 e32824 .0 e43‘332 843 1 .1 In the next step of the computafion, the idempotent matrix, P3, is obtained: 1 e12 e12623+612824e43 e12924 P; t: 0 e23632+ez4e43°32 e23"624343 624 (10) 0 e32 e32823+e32824e43 e32824 - 0 843°32 843 e43e32324.1 Finally, the trace path of the idempotent matrix yields the state- ment of all closed loops in the digraph. PT = e23"32 + e24"'«13"’32 + e32"'23 + e32824843 + e43332324 (11) 3. A Method for Determining the Optimal N- Reducibilitj of a Behavioral Diagram The preceding section has established a foundation; a method will be constructed, in this secfion, for finding optimal sets of verfices--to be opened in order to destroy all loops of dependency in the behavioral diagram. 223 Notice that the directed nature of the paths is no longer of impor- tance. In order to destroy all such loops, it is only necessary to know their composition. Therefore, full commutativity can be restored for the operator, conjunction. Notice, also, that an inlmediate simplificafion can be made. For every loop that passes through k verfices of the digraph; k cyclic per- mutations, of the edges in that loop, appear in the trace path, pT; one emanating from each of the k vertices. Under restored commutativity, these become idenfical clauses; and all but one of each set can be deleted. 24;. The path function, simplified according to the preceding ob- servation, becomes a unate truth function of the edges of the digraph. That function, FP(§_), is in DNF. Therefore, the expansion: (((FP(3))d)E)d = «r s, (12) i yields the simplest CNF for Fp(_e_), the conjunction of all prime im- plicates. And since: si -> Fp(3) (for each i) (13) {Si}e is the set of all minimal edge-sets which can be used to destroy all feedback loops in the digraph. The member of {si}e which contains the smallest number of edges, becomes the optimal edg-e-set for that purpose. The number of edges in the optimal edge-set is greater than or equal to the n- reducibility of the loop structure. The ultimate goal is to obtain a set of vertices to be 'opened', rather than a set of edges to be 'cut', in order to destroy all loops. Furthermore, as an investiga- tion of some simple examples can illustrate, not all optimal edge-sets yield optimal vertex-sets directly. 224 ;._;. Consider the vertices of the graph to be switches. Each one can control the transmission through all of the edges incident upon it. In order to maintain transmission (flow of dependence) through edge eij’ it is necessary that both vertex i and vertex j remain 'closed'. The substitufion of the conjunction of the particular pair of ver- tic es, associated with a parficular edge, can be made at every appear- ance of that edge in Fp(_e_). The result is a unate truth function, Fp(y), of the verfices of the graph. A Fp(_y) = FP(_§) (for all i,j) (14) l ij 1 j L‘- The terms in (14) will not immediately be clauses. However, the application of the relations A- (l)--those which apply to a unate funcfion--will simplify Fp(_v_) to the point at which it will be an expres- sion in DNF. And, once again, the expansion: dEd (((Fp(_\_r_))) ) = :81 (15) yields the set of all prime implicates of Fp(y). {81 }v is the set of all minimal vertex-sets which can be used to destroy alT feedback loops in the digraph. The member of {si }v which contains the smallest number of vertices becomes the optimal vzrtex-set needed in Chapter II. The number of vertices in that set is the index (n) for the n-reducible loop structure. 2.2.3.- Confinuing the example of secfion 2. 3, the loop structure can be seen to be 1-reducible. Equafion (16) shows the two unate truth - funcfions and their sets of prime implicates. The last line of (16) shows that either vertex 2, or vertex 3, can be used to destroy the loops in the digraph of Figure 2. 225 FPLE) = e23332 + e24643332 {8,12 = (632’(°23 + e24:”"23 + 643) (16) FPLY) = Vzvs + V2"3"4 {Bi}v = (VZHV3) As another example, Figure 3 shows the directed flow graph for another l-reducible loop structure. Figure C-3: The Directed Flow Graph for the Example The two truth functions, and their sets of prime implicates, are shown in (17) for this graph. Fp(3) z e12‘°’21 + e23’334342 + e13334342‘321 {SHE = (821“23’ (”21"834) (821“42) (812+e34’(812+e42’ (612+e13+ez3) Fp(y) = vlv‘2 + vzv3v4 + vzlv2v3v4 (17) {Si}v = (VZHVI + v3) (v1 + v4) For this example, there are four optimal edge-sets, each of which contains two edges. The optimal vertex- set is unique. The vertex v2 can be used to destroy all of the loops of the digraph. Figure 4 shows the graph opened at that vertex, as for Phase I. 1 e12 Figure C-4: The Opened Flow Graph for the Example