ENGINEERING RESEARCH INSTITUTE UNIVERSITY OF MICHIGAN ANN ARBOR TRUTH-FUNCTION EVALUATION USING THE POLISH NOTATION By Arthur W. Burks Don W. Warren Jesse B. Wright Project M828 BURROUGHS ADDING MACHINE CO. DETROIT, MICHIGAN July 8, 1952

s~~t he v ]-zitoUSo < < o b.i Es act,r;^it.,' >; A':,. 4.., A! f' * {hSqrS All c'; s'\,#..'S'>.

TABLE OF CONTENTS Page ABSTRACT iii ACKNOWLEDGMENT iv 1. INTRODUCTION 1 2. A TRUTH FUNCTION EVALUATOR 6 2.1 Block-Diagram Analysis 6 2.2 Detailed Analysis of Components 7 2.3 Operation 12 2.4 Modifications 14 3. THEORY OF TRUTH FUNCTION EVALUATION 17 3.1 Formal Languages 17 3.2 Concepts and Theorems Concerning the Process of Evaluation 19 3.3 Theorems Concerning Languages with only Dyadic Operators 21 4. CONCLUSION 25 BIBLIOGRAPHY 27 ii

ABSTRACT An inexpensive special-purpose relay machine is proposed (requiring some 40 standard relays, 90 crystal diodes, and a rotary selector switch) which will produce the complete truth-table for a formula 25 characters long containing 10 distinct variables in about 15 minutes machine time. Some theory is presented concerning the Polish notation, the type of language upon which the machine is based, e.g., theorems concerning the relation between structure and length of a formula and the amount of equipment required for its evaluation. It is pointed out that the proposed machine is not adaptable to extremely long formulas but that the theory could be embodied in an electronic machine which could handle such formulas and which would have some advantages over comparable versions of existing machines used for this purpose. iili

ACKNOWLEDGMENT The authors wish to express their gratitude to Carl H. Pollmar for his many helpful suggestions and constructive criticism throughout the writing of this report. iv

TRUTH-FUNCTION EVALUATION USING THE POLISH NOTATION 1. INTRODUCTION Two different methods for the mechanized evaluation of truthfunctions (i.e., expressions in the propositional calculus) have been proposed recently. The first is a parallel analogue method. To each occurrence of a logical connective in'the for-mula to be evalua-l;ed is assigned a physical element (rudimentary circuit of relays, vacuum tubes, etc. ) which realizes that connective. An input which has two stable states (one for each of the two truth-values "-true" and "false') is assigned to each variable occurring in the formula. The inputs and physical elements are then interconnected in accordance with th?.e arranl:eme,(t' of variables and connectives in the formula so that tbhe-re is a single output wire which, when the inputs represent a given assigrnment of values -o the variables, will represent the truth-value of the formula for that assignment. A counting or stepping device then causes the inputs to represent succesively all possible truth-value assignments to the variables and the output wire:rill then successively represent the corresponding truth-values of the formula. Two machines embodying this method have been built, one by Kalen and Burkhart (l)t and a second by engineers at Ferranti (2). Both machines used relays as their basic components, but it is obvious that special-purpose high-speed electronic machines embodying this same method could be readily designed. The second method employs a general-purpose computer, the evaluation being done by means of a special sequence of instructions (4). These instructions cause -the machine to first assign truth-values to all variables and second reduce down to a single truth-value the resultant formula. This is repeated until all possible assignments of values to variables have been exhausted. The reductions are generally accomplished by arithmetic operations (e.g., negation of a truth-value can be done by subtracting the given truthvalue from a constant) but in some instances logical operations might be used (eg., in some binary machines digit extraction is a form of bitwise logical. conjunction). VParenthesized numbers refer to the bibliography at the end of the volume.

It is difficult to compare computing methods per se, that is, independently of the physical means used to realize them, and yet comparisons which do not abstract from equipment are of little use. With this reservation in mind, consider formulas of great length (e.g., 250 characters) containing a large number of distinct variables (e.g., 25). Even assuming the- iUs:.e of hligh-speed electromie compQnents, neitherv. of these two methods seems practical for such formulas. The former method requires an excessive amount of equipment, especially if the machine is designed so-that setting it up for a particular problem is automatic (e.g., from a tape). The — latter method seems to require an excessive amount of computation time, presumably because this is not the type of problem which present general purpose machines were designed to handle efficiently. In the present report a new method for the evaluation of truthfunctions is proposed which does seem to be practical for formulas of great length and many variables and which has other features of interest. This new method is based on the Polish notation. We will first make a few remarks concerning this notation and our use of it. Following that (Section 2) a rather detailed design is presented for a special-purpose relay machine embodying the new method. This machine cannot handle formulas of the size referred to above, but it will serve to illustrate the principles involved. (The design work is further justified by the fact that there is some interest in Philadelphia in constructing it, mainly as a test for certain types of relay equipment. ) Section 3 contains some general theorems relevant to the proposed method of truthfunction evaluation. Finally, Section 4 considers briefly the use of this method for the evaluation of formulas of great length and many variables by means of high-speed electronic equipment. In the Polish notation a logical operator is followed by its arguments instead of being placed between them as is normally the case and no parentheses are needed. E.G.'(pfq) ~ r' is expressed as'KApqr', where'K' stands for conjunction and'A' for disjunction (alternation). The machine of section 2 evaluates formulas in a language containing the following primitive symbols: Ten propositional variables: pr., q,. 0o, y Six dyadic operators: defined by Table I below A "left-end-of-formula" symbol: * 2

TABLE I Name Symbol Truth Values First argument p 0 0 1 1 Second argument q 0 1 0 1 Conjunction Kpq 0 0 0 1 Alternation (Inclusive Disjunction) Apq 0 1 1 1 Conditional (Material Implication) Cpq 1 1 0 1 Negation Npq 1 0 1 0 Exclusive Disjunction (Material Inequivalence) Dpq 0 1 1 0 B icondit ional (Material Equivalence) Epq 1 0 0 1 The number of variables (10) was decided upon somewhat arbitrarily as providing reasonable capacity for handling an "interesting" range of problems and at the same time keeping the size of the machine within fairly modest bounds. Changing this number would require only the most obvious changes in the design of the machine. The six operators were chosen similarly on practical groundsobviously a single stroke-function operator would have been logically sufficient, but would have seriously restricted the practical application of the machine. The decision to make all operators dyadic, however, is in a somewhat different category. The possibility of changing this condition will be considered in section 3.4, but for the present it will be said merely that the restriction seems advisable for a "Mod I" experimental machine. tSee third paragraph following. 5

In connection with dyadic operators, Negation deserves special mention. Whereas the other five operators are "naturally" dy-adic, Negation is ordinarily monadic. The present definition requires that N take two well-formed formulas as arguments, the first of which is irrelevant —a "dummy". It has been found most efficient (as will be explained in section 3) to insist that 1) the first rather than the second argument be the dummy 2) the dummy be a single variable 3) the variable be- one that occurs elsewhere in the formula. Rigorous discussion of the properties of the language will be reserved for section 3. However, some concepts which are particularly relevant to the operation of the machine-namely those defining the class of formulas which the machine is capable of handling —will be mentioned briefly at this point. First the formation rules of the language must be given (section 3.1, p. 17). For the present, a formula may be recognized as well-formed on intuitive grounds if it contains no symbols other thnan those listed above and if it constitutes a translation from a well-formed formula in the more familiar propositional notation (V,',/, etc.). Second, it must be known that evaluation of a given well-formed formula will not exceed the capacity of the machine. This depends, obviously, on the formula's containing a number of symbols (tokens) which can be stored. But it depends, also, on a less obvious structural property called the Rank (section 3.1 Def. lB). For the present, it can be safely stated that any well-formed formula of less than 20 symbol-takens can be handled by the proposed machine+. Finally, before passing to a detailed consideration of the machine, the general procedure of evaluation will be outlined, since it is relevant to both section 2 and section 3. The entire operation is sequential. For a formula of n distinct variables, 2n Major Cycles are required. A Major Cycle consists of, first, making an assignment of a 0 or a 1 to each variable of the formula and, second, reducing this Evaluant (with binary digits properly substituted for the variables) to a single binary digit by successive application of the operators, proceeding from right to left (until the * is reached). If any Evaluant ~This fact is assured by Theorem 3, section 3.3, but does not by any means indicate the complete class of formulas which can be handled by the machine.

reduces to a 0, the formula is a non-tautology; if any evaluant reduces to a 1, the formula is a non-contradiction; and if all 2n evaluants reduce to 1 (0) the formula is a tautology (contradiction),

~~~~~~~~~~~~I I j ~~~~SFIG. I TRUTH -SLFUNCTION EVALUATOR SWITCHEMATIC DIAGRAM Sop HOME IIt -) *NpK, WZ I 1 Tifl Ld <0 Kil A I l E R AT ROR"kS'Nr 0 1 COUNT OPERATOR FUNCTION SW ITCH D Ti I L~i BUFFER E Al LS RS SIGNAL- I SHIFTING REGISTER FFI1, F2 3 cc cc FF

2. A TRUTH FUNCTION EVALUATOR The operation of the proposed machine will be described in three stages: first (section 2.1) at the block-diagram level, pointing out the purposes of the various components, second (section 2.2) a detailed discussion of the construction and operation of these components, and third (section 2.13) a description of the operation of the machine as a whole. Section 2.4 considers a few simple modifications which would make the machine somewhat more versatile. 2.1 Block-D iagram Analysis Figure 1 is a schematic representation of the complete machine. For the present, attention is directed primarily to the "block-diagram" aspect of this drawing: the five heavily-outlined boxes (Rotory Selector Switch, Gated Counter, Operator Function Switch, Buffer, Shifting Register) and their interconnections. The detailed discussion of the internal operation of these components, along with such overall problems as timing, is reserved for sections 2.2 and 2.3. The Rotary Selector Switch stores the original formula and establishes the timing cycle for the entire operation. The formula is set up manually, each of a sequence or arc of contacts being connected to the proper one of the 10 variable, 6 operator, or * outputs. As the wiper passes over these contacts, the outputs are activated, one at a time, in a sequence corresponding to the sequence of symbols in the formula reading from right to left. The Gated Counter produces Evaluants of the formula. It consists of a l0-stage binary counter. Each stage drives a gate (actually a double gate) which is fed by one of the variable (p through y) outputs of the Selector Switch. Each gate has twG outputs, the corresponding outputs of all gates being connected in parallel to produce the 0, 1 outputs at;the bottom of the box. The result is that when one of the variables is encountered by the Selector, the Counter will produce a 0 or a 1 output corresponding to the state of the stage of the Counter associated with that variable. Initially the counter is cleared to zero and is then advanced 1"lt by each occurrence of the:*,thus producing a new Evaluant for each complete "run" of the formula (Major Cycle). When all 2n Evaluants have been used, i.e., when the Counter returns to 0, Signals.2 will be operated indicating tautology and the machine stoppedt. VThis can occur only if none of the Evaluants reduces to 0.. Provision for handling formulas with less than 10 distinct variables is discussed in section 2.2, 6

The Ope-rator Function Switch is fed by the six operator outputs of the Selector and is controlled by the first two stages of the Shifting -Register (q.v. ) -as indicated in Figure 1 by the center lines-in such a way that whenever an operator is encountered by the Selector, the values Of its two arguments occur in the left end of the Register. These three signals are combined in the Operator Function Switch to produce an output which is 0 or 1 according to the truth-table for that operator and its arguments. The Shifting Register stores the successive portions of the Evaluant as they are produced and facilitates the reduction to a single value. It consists of 10 binary stages with provision for shifting its contents- one stage to the right or to the left upon command. Whenever a variable occurs and is assigned a 0 or 1 by the Counter, the Register is shifted right and this 0 or 1 stored in the leftmost stage. When an... operator is encountered it is applied to its two arguments from the Register (as in the preceding paragraph), the Register is shifted left to dispose of the arguments just used, and the new value from the Function Switch is stored in the leftmost stage of the Register. When a star occurs, the state of the leftmost stage of the Register represents the final reduction (to 0 or 1) of the current Evaluant. If this value is 0, the Stop box will operate Signal-1 representing non-tautalogy and stop the machine. The purpose of the Buffer is to combine for one purpose and to isolate for another its two pairs of0. 1 inputs. A signal on either of the input pairs (variable or operator but never both) must be sent to the Register. This is done by the outputs on the right of the diagram. In addition, a left shift of the Register is required for -an operator and a right shift for a variable. These are effected by the LS and RS outputs at the bottom of the box. 2.2 Detailed Analysis of Components The preceding subsection gives an idea of the operation of the machine "in the large". Now the details will be filled in. The operation of the proposed machine depends importantly on a special type of flip-flop. Such a flip-flop must have the ability to record the occurrence of a 0 or i input signal and at the same time remembers its previous state. This situation could be realized in many different wayssome of the most efficient requiring special-purpose equipment. One of the "ground rules" of the present design, however, is to make use of certain available equipment: in this case standard, 8-spring relays. The designing 7.

of the most practical and efficient circuits for the proposed machine is left to the- more specialized skills of the engineers and technicians who will be responsible for the actual construction. Nevertheless, in order to be sure-that the proposed design was workable, it seemed advisable in -several instances to work out — some rather detailed circuits. Such instances are to be taken primarily as proof that the proposed design can be.- carried out with a reasonable amount of equipment. If any of these circuits prove adequate for the actual construction of the machine, so much the better, but it is; fully expected that modifications may be necessary. In the case of the special flip-flop mentioned above, a circuit is presented in figure 2, which accomplishes the desired purpose by the use of two relays: A, the registering relay, and B, the auxiliary relay. Speaking generally, an input signal, throughout its duration will affect only the auxiliary relay, Be When the signal is removed, relay B will drive the registering relay, A, into the same state as B. Because of the memory embodied in this flip-flop, its state cannot be determined, in general, from a knowledge of the state of the inputs alone-it is necessary to know the previous state. The various possibilities are presented in Table II. The digit-pairs represent the state of the two relays, e.g.,'01' indicates that the A relay is unoperated and the B relay operated. The positions marked'X' represent conditions that can never occur in normal operation. Note that the states 00 and 11 are "permanent" in the sense that one or the other is produced whenever there is no input. Similarly, the states 01 and 10 might be termed "transient". TABLE II Previous state — > 00 11 01 10 _ Close 00 10 X X [Open 00 X X 00 Close 01 11 X X Open X 11 11 X...:l:,.,.. L~.,,...,.,. _,, -8

In detail, the operation of -the flip-flop is as follows: Figure 2 shows the flip-flop storing a 0 and with the input circuits open. (The notati6n'X','X' refers to the upper and lower terminals, respectively, in the orientation of the diagram, of relay coil X.) b I'| lmbm.411 P Ilc1 al, U 0 v3 B Flip-Flop Figure 2 The "tl" Input (from the "0" state) Closing this input grounds B and A shunting out A and closing bI which locks-up B.. Opening this input removes the ground from A. A remains grounded through bI and coil A (protected by the diode or "varistor", V ) is energized closing al, B remains locked-up to V2 and V (either one alone would be sufficient for this purpose). The state of the flip-flop is now "stable" for storing a 1. Closing the "l" input again has no effect because of V2 The "O" Input (from the "i" state) Closing. this input shunts out B at V1, opening bI if V1 is present. (V1 might not be required for this purpose if the forward resistance of V2 and V3 is small enough, but is necessary in the next step.) 9

Opening this input removes all ground and al opens. Closing the "0" input again has no effect because of V1. The equipment requirements -for this circuit are two standard relays with transfer contacts, 3 varistors, and 2 resistors. In the Schematic Diagram (Figure 1) the flip-flops are represented as small rectangles, labeled'FF', in the boxes for the Gated Counter and the Shifting Register. Each flip-flop has a "0" and a "1" input. The transfer contacts required on each (the- A and the B) relay for internal! operation of the flip-flop are not shown. Additional contacts required f-or external operations are shown and are connected to the proper flip-flop by means of center lines. Except in the case of the Stop box, all contacts are (and must be) controlled by the A relays. The detailed operation of circuits incorporating the flip-flop are most easily grasped by a careful study of figure 1. Some general remarks, however, may help to establish the proper orientation-particularly -with respect to the timing and overall organization of the operation. A Minor Cycle will be defined as the period between the instant the wiper touches -- a contact on the Rotary Selector Switch and the instant that it- touches the' next contact in its direction of travel. This Minor Cycle has - two, phases: the Contact phase, during which a contact is connected through the wiper to- ground, and the Open phase, during which no contact is grounded. The design is- such that in each phase at most one relay operation (either -an opening or a closing) is required. It is a fundamiental requirement of the proposed design that the Rotary Selector can be operated at a speed that will permit this. The evidence-admittedly incomplete —suggests that the Selector could be operated in the continuous or "running" mode and this mode of operation will be assumed. If the assumption proves to be unrealistic, the Switch could be advanced in discrete steps at the cost of a slight increase in equipment but a rather considerable loss of speed. An intermediate possibility is that, while the Minor Cycle is of sufficient duration to:;-alltow -two relay operations in sequence, the division into Open and Contact phases leaves the Open phase too short for one relay operation, In this ~event it might be possible to introduce a "slow-acting" relay —one whose.-operation time is invariably longer than the operation time for any other relay in the circuit —between the Selector and the flip-flops in order to artifically adjust the phase division. Another less efficient scheme would be to use only every other contact on the arc of the Selector Switch. 10

To proceed, then, the -above — indicates that s signal on an input of any box will consist of a grounding of that input, the input remaining grounded throughout the Contact phase of a Minor Cycle~ The signal will be preceded and followed by the Open phase in which the input is floating. The destination of such a signal will, in general, be a flip-flop input of the Shifting Register (the major exception being for the * which operates the Counter). From origin to destination the signal may be routed through contact networks and through the Buffer but with negligible- loss of time-i.e., there is no sequential operation of relays during the Contact phase (or, for that matter, during the Open phase) of a Minor Cycle. During this phase, the only relays which can change state are the B relays. During the second (Open) phase of this Cycle, the A relays are driven by the B relays, thus setting up the contact networks for the next Minor Cycle. The specific applications of the flip-flop can now be described. In the Gated Counter of Figure 1, note the two vertical banks of transfer contacts. These contacts are controlled by the A relays of corresponding flip-flops (FF's) as indicated by the center lines. The inner bank effects the counting operation. The binary number recorded by the counter is interpreted as having its least significant digit at the left. The FF inputs are connected to transfer contacts in such a way that a "count" signal will change the statet of every digit to the left of and including the first 0 As indicated in Figure 1, the Counter is connected to produce an output which will stop the machine when it has counted to 210 (returned to the all-O state). This corresponds to producing all evaluants of a formula of 10 distinct variables-.the maximum capacity of the machine. To handle efficiently formulas of fewer variables, two alternative modifications are suggested, both assuming that the variables omitted are those nearest the end of the alphabet. A. Connect the "stop output" directly to the 0 input of the nth FF from the left- n being the number of variables in the formula. This could be done easily as part of the manual set-up. B. Provide means (e.g., push buttons) for "clearing" the (10-n) rightmost FF's to 1 and leaving the "stop output" unchanged. The purpose of the outer bank of contacts is to route the variable signal from the Selector to the 0 or 1 output of the Counter in accordance with the state of the FF corresponding to that variable. ~The FF.- e., the A relay —of course does not change until the "count" signal is removed. 11

The second application of the flip-flop —the Shifting Register — depends again merely upon the proper interconnection between transfer contacts on the-: A relays and FF inputs. In the figure, the upper row of contacts controls the right shift-the springs being connected in parallel to the RS input. The make and break contacts controlled by FF. are then connected, respectively, to the 1 and 0 inputs of FFi+. The left shift is effected similarly by the lower bank, the connections being in this case from the contacts of FFi to the inputs of FFi_1 o The varistors connected to the transfer contacts are to prevent interaction between the LS and RS circuits. Note that three springs have been eliminated (FF12l10) since the corresponding shifts are never required. It was mentioned previously that the Operator Function Switch is controlled by the Shifting Register. This is shown in Figure 1 by the center lines connecting the two vertical columns of transfer contacts in the Switch to FF1 and FF2 (A relays) of the Register. When one of the operators, N. D, E, C, A, or K, occurs (no more than one can occur.at a time) the signal is fed through the contact network producing an output (O or 1) which is the result of that operator applied to its arguments (from FF1 and FF2). The purpose of the Buffer has been stated and the internal operation of this simple diode circuit hardly requires further discussion. 2.3 Operation Given a well-formed formula to be evaluated by the machine, the first step will be to set up the Rotary Selector Switch, In Figure 1, two arcs of contacts are indicated, one set up for the formula, *ANqqq, the other for *NpKqp. The use of two separate arcs in this manner permits the setting up of one formula while the machine is evaluating another. The switch just below the wiper selects the desired arc. Then the wiper is placed in the "home" position: on (or perhaps just ahead of) the first used contact. Clearing the machine consists merely of opening all relays and could be accomplished simply by removing all sources of power. It is worth noting that under normal operation very little clearing is required. Irrelevant information in the Shifting Register will never be able to move into FF1 or FF2 at a time when it -could affect the operation; hence the register need never be cleared. The counter will automatically clear to zero upon completing the evaluation of a tautology but in any case when the machine has not completed all evaluants it must be cleared. 12

Assuming then that the necessary clearinLg has been done, the next step is to set the maximum -to which the Counter is to countl-i.e, 2n for a formula of n' variables. This can be done by method A or B of section 2.2 and the operation is ready to start+. The first step of'the evaluation will be, invariably, the activation (grounding) of one of the variable outputs of the Selector. In the example of Figure 1, with the inner arc of the Selector in use, the p output is grounded. Due to the state of the Counter, its zero output becomes activated; this in turn activates the RS and 0 outputs of the Buffer. Simultaneously, a 0 is recorded in FF1 (B relay) and the Register shifts rilht. —i.e., puts the B relay of FFi+l in the same state as the A relay of FFi. This concludes the operations of the contact phase of the first Mianor Cycle. The open phase begins wh'en the wiper of the Selec-,-o: leave(s tlhc first contact. This removes the!round from all FF iipu-is in t-he Re ister~ thus allowing -the A relays -to be driven to the state of t-he B relays and changing, correspondingly, the state of the contact networks lDboi'.. ina the Reg,- is ter and in the Function Switch. The second Minor Cycle repeats the procedure of -ithe firs t for -the next contact of the arc which in the present example correspot:.nds to the variable, q, and' is assigned the value 0. At the conclusionl of`Uhis Cycle, the values (both 0 ) for p and q are stored in FF1 and FF2 The third Cycle begins when -the wiper reaches the third contact which, in this case, is connected to the K operator output of the Selector, By tracing the "K" path through the Function Switch it is seen that the 0 output is activated as is required since the value of KOO is 0 Passing through the Buffer it is seen that its 0 and LS outputs are activated thus storing a 0 in FF1 and simultaneously shifting: the Register, this time, to the left. The next two Cycles dispos. of p and N, leaving in FF1 the value NOKOO = 1. The next Cycle, which is the last Minor Cycle of the first Major Cycle, grounds the * output. This signal is transmitted simultaneously (1) to the Stop box, where i-t encounters an open circuit (since FF1 is storing a 1 ), (2) to the counter which it advances one step-i.e., changes the state of FFp from 0 to 1, and (3) to the "Home" tHere, as elsewhere, the simplest alternative is assumed: that all power can be applied and the Selector set in operation simultaneously. It is realized, however, that more selective control might be useful or possibly necessary and it is left to the engineers to make such modifications as seem advisable. 13

input of the Selector which will return the wiper to its initial position+ preparatory to — the. —next Ma-jor Cycle. The remaining three Major Cycles proceed quite analogously until the final Minor Cycle of the problem —that for *. At this point FF1 holds the value of NlKll which is 0. Hence the * signal can pass through the Stop box, turn on Signal-1 indicating non-tautology and stop the machine. Given the proper timing arrangement, the * signal could also effect a final "count" and "home" operation which might or might not be of: some slight advantage. The computation time for a formula of length (number of charactertokens), L, containing n distinct variables, on a machine whose Minor Cycle time is t, is given by the formula, T = tL2n This is the time required to test all evaluants. Of course in many cases it will not be necessary to test them all. Assuming that t = 1/30 second (30 steps per second of the Rotary Selector Switch under the mode of operation described above) the computation time would be, for example, for a "large" formula with n 10, L = 25, just under 15 minutes; for a "small" formula with n = 5, L = 10, T would be slightly over 10 seconds. 2. 4 Modif ications Depending upon the use to which the machine will be put, it might be advantageous to -provide. certain facilities not included in the basic design. Naturally, only a few of the many possible contingencies can be provided for the four suggestions below..are offered as examples. 1) Over-length Formulas. If the- number of character-tokenns in a formula is greater than the number of contacts on an arc of the Selector, it could be set up on two Or more arcs and a simple relay circuit added to "home" and to effect automatic switching of wiper contacts from one arc to the next. The formula for- -running time, T = tL2n applies to this case- without change. 2) Tests other than for Tautology. If the connections in the Stop box are reversed-closing the circuit through the "make" rather than the "break" contact-then Signal-l will be operated and the machine stopped upon the tIf a "non-homing" type of switch is used, certain modifications must be made at this point. 14

occurrence of a "1" or "true" evaluant indicating that the formula is not a contradiction. It might be required to determine the values of the variables for which the formula is true or for which it is false. For this purpose neon lights might be attached to the FF's of the: Counter for easy reading. The states of these lights would be recorded, manually, each time the machine stops. The "non-contradiction stop" of the preceding paragraph would be used to;. advantage in this test on formulas known to -have more false than true values. 3) Formulas of more. than Ten Variables. If it seemed advisable to use the Evaluator at all frequently for such formulas, it would of course.be a simple matter to add the necessary number of FF's to the Counter. However, given any fixed capacity, the following slight modification makes it possible to "program" the handling of formulas with an excess number of variables. Provide two additional Selector Switch outputs, connected directly to the 0 and 1 outputs of the Counter. This has the effect of adding the constants 0 and 1 to the formula language. The assignments of 0 and 1 to the "excess variables" can -then be made manually. This procedure requires 2n-10 complete "runs" to test all..possibilities where n-10 represents the number of excess variablest. The standard formula for running time gives a good approximation for this case, —but a more accurate time would be given by the formula- T tL2n + t 2n"-l0 when t is the time required for manually changing the conm mn nections to the 0, 1 outputs and 2n-lO is the number of possible combinations of the excess variables-i.e., the number of times the connections,must-. be. made.4) Formulas of Excess Rank. Though the formal definition of rank is reserved for: section 3, it can be informally characterized for present purposes as- that property of a formula which determines the capacity required in the Shifting Register. A.Formula:of "excess rank", therefore, is one whose evaluation would exceed the capacity of Register. Although it has been assumed that such formulas will not be- allowed on the machine, it might be desirable for the machine to detect excess rank, if only for the purpose of error preventionS This. facility can be pro.vided.as follows: a) Clear the Register before- each problem, b) Provide a signal to indicate a right shift of a 1 from.the rightmost FF (FF10) c) Provide for a 0 to be shifted into FF10 by every left shift. variations of the above procedure and, in fact, it seems probable that the general procedure might be: improved upon; but the possibilities have not been seriously investigated. 15

Though the fact appears to be -of little practical value, it is worth noting that this modification actually increases the "rank capacity" of the machine for certain rare formulas, due to the effect of shifting O's off the right end of the register and then shifting them back in again. This concludes the description of the machine, per se. The remainder of the report is concerned primarily with the theory underlying the method evaluation. 16

3. THEORY OF TRUTH FUNCTION EVALUATION The -present section serves two purposes: to provide a more rigorous, basis for the- design of the machine in section 2, and to express the- theory behind this machine in more generalized form so that it may be applied to a wider variety of problems in truth function evaluation. 3.1 Formal Languages-. The symbolism used throughout the remainder of the report will be as folltows-: Gn (n an integer.) will range over operators of degree n F:, A will range over formulas — usually well:-formed formulas. p, q... will range over propositional variables. ~a v Ir.,.. will range over the two truth-constants, 0 and 1 (Any of these- symtbols may have- subscripts or superscripts. ),All of the- above symbols are in the meta-language. In addition, the language of section 1 will be used, frequently, for examples. Note that the use of'p','q',... constitutes an ambiguity between the object language and the meta-language; this ambiguity will be resolved by the context in all cases, however. Several languages will now be defined: Def. 1A giving the set of symbols for -each, Def. lB giving the formation rules. which are common to all. Def. 1A. S contains a finite number of operators, which may be of different degrees, and a finite number of propositional variables. S contains the same operators as S, the two truth constants, 0 and 1, but no propositional variables. Sn (Sn) contains the same symbols as S (S) except that all operators are of degree n -i.e., "n-adic"' 17

Def. lB. Any propositional variable or truth constant is a Well-formed Formula (henceforth, wff) with Rank, R 1 If A1,.., An are wf (Well-formed), then Gn An...An is wf with n R = Max (R(A1) + i - 1) i=l The Length, L(A) of a wff, A, is the number of characters (tokens of operators, variables, truth constants) in A Note the assymetrical role played by the various arguments of an operator in the determination. of the rank of the operator-plus —its-arguments. This can.be taken advantage of in minimizing the rank of formulas under various circumstances. E.g., suppose we need the alternation of p and Kqr ApKqr has a rank of 2, AKqrp has a rank of 3, while the lengths of both formulas are the same. A further example concerns the conditional operator, C. It is often the case that the antecedent of a conditional has a greater rank thanthe consequent; this is especially true with the hypothetical corresponding to a given argument. Suppose R(r ) >R(A) > 1. Then R(C 7 A) = R( ) + 1 and L(C7 A) - L(7 ) + (L(A) + 1. The rank could be reduced by 1 if C were replaced by a "reversed conditional" operator, Cr CrA = def. C rA. Then R(CrA7 ) = R(7 ). However, the same saving in rank can be obtained without the introduction of a new operator by using the equivalent expression, AANp r whose rank is also R(7 ) although its length is L(7 ) + L(A) + 3, an increase of 2 It is not adbvibOus that the decomposition of a wff into its arguments is unique; iLe., that, given a wff A of the form GJ AJ... Al A cannot also be expressed as GJ A'...Ai unless it is true that all Ai = A!. Since the uniqueness of Rank and of truth values depend upon this uni-queness. of decomposition. it wil now be formally established. Lemma. Given a wff, A =.J.., and a wf initial segment of A = GJ... (having its sequence of m characters identical to. the sequence of the first m characters of A), then A = r Proof (by induction on L(A) ). The Lemma is true, obviously, for L(A) 1. Assume that it is true for all,. A having L(A) _ n; then it can be shown to hold for L(A) = n.+ 1 by the following: By the formation rules, A can be written as t iAJ... A1,and r as with L() an L(r Therefore, since either AJ is an lThe order of the Ai is significant only in relation to the Rank formula which follows. For an informal discussion of Rank see section 2.4, modification 4. 18

initial segment of rJ or vice versa, the two formulas satisfy the induction hypothesis and A =. Suppose it has been shown that A., = ~ for all j' satisfying j j' J. Then the argument above (for subscrip~ J) applies and it follows that for all j such that 1 - j' J, A. = Cj; and therefore- A = 7. Q.E.D. Theorem 0. The decomposition of a wff into an operator followed by a sequence of wff's is unique; i.e., if A = 8K A.A1 -= 6K.. 1 A, then K J and Ai = for 1i K Proof. Each of the pairs of formulas (AJ, a~), (AJ_1, A 1) *. in turn satisfies the hypothesis of the Lemma and consequently the conclusion. Continuation of the process until A is exhausted will establish simultaneously the identity of the paired formulas and the relation J = K Q.E.D. On the strength of Theorem 0, it can be assumed henceforth, that the Rank of any wff is unique, and that the truth value of a wff in S (or Sn) is independent of the order of evaluation. 3.2 Concepts and Theorems Concerning the Process of Evaluation. Let us call any wff, AX of S an evaluant. A is, of course, an evaluant of some wff, r of S, i.e., A is obtainable from some r of- S by substituting 0 for all occurrences of some (possibly none) of the variables of r and substituting 1 for all occurrences of the remaining variables. Hereafter, section 3.2 will be concerned with the language', S, exclusively, The Length of the Uninterrupted Sequence of bits (occurrences of truth constants( counting from the right of an evaluant A is call-ed Lus (A); e.g., Lus (92 C 92 pC) 2=, Lus (a) = 1 Theorem 1. Lus (A) -the degree of the rightmost operator of A or 1 if there is no operator in A. (I.e., the rightmost operator An of an evaluant A is followed by at least n bits..) Proof. Else A would not be wf. Q.E.D. ( 7 is the immediate reductum of an evaluant, A) = def. (7 is formed from A by substituting for the rightmost operator Gn of A and the following n bits its value). E.g., KO1 is the immediate t- i. r mI-. ie.. A, TN VThe't= means that the sequences of symbols are identical, 19

reductu of KOAO1 i Note that the immediate reductum of the evaluant is itself.- an e-valuant (A1,*.., Al. is the complete sequence of reducta of an evaluant A1) def. (Ai+1 is the immediate reductum of Ai, and AM is 0 or 1.) E.g., KOAO1, KO1, 0 is the complete sequence of reducta of KOA01 The main theortm on evalluation is: Theoem 2. If A1 A,.., AM is the complete sequence of reducta of the evaluant A((A A1) then M Max (Lus (Am) ) = R(A). m=l Proof. (by induction on L(A) ). (I) It is obvious that it holds for L(A) = 1 (II) Asslue it holds for all wff of L - n. It will be proved that it holds for any formula A of L = n + 1. Note that A is of the form @J r J. J rl 7 where L( j) n (1 - j ~J), and each rj is an evaluant. Let the complete sequence of reducta -of A be A1,., Am,... @ (-as before) and the complete sequence of reducta of r. be' -''i -(where l is F j n m j-at1I J. I F. ( = p + Pi) is of the form i=l rJ'' rj+l j-1 where Max (Lus (F p) ) R( r ) by the inductive hypothesis. It follows that Max (Lus (J rJ.. rj+l ajI"! KL) ) R( + j -1 p=l since there are j - 1 ats in the sequence aC-1''', a~ Hence, M J MaX (Lus (Am)) = Max (R(r ) + j 1) But,. by definition, j=l1

Therefore, M Max (Lus (Am) ) = R(A) Q.E.D. m=l 3.3 Theorems Concerning Languages with only Dyadic Operators. With the machine of section 2 specifically in mind, the present subsection will establish some theorems concerning the language, S2, in which all operators are dyadic. Theorems 3 and 4 establish connections between L(A) and R(A). Theorem 3. If A is in S2 then L(A) - 2R(A) - 1. Proof. (by induction on L(A) (I) The theorem clearly holds for L(A) - 1. (II) Assume it holds for all wff of L n. It will be proved that it holds for any formula A of L = n + 1. Note that A is of the form e2 A2 A1 where L(A1), L(A2) < n.$ Obviously, L(A) = L(A2) + L(A1) + 1. By the inductive hypothesis L(A2) _ 2R(A2) - 1 and L(A1) X 2R(A1) - 1. Hence, L(A) 1 2R(A2) + 2R(Al) - 1 Depending upon the relative Ranks of A1, and A2, there are two cases to consider: (A) (B) R(A2) + 1 - R(A1) R(A2) + 1< R(A1) Then R(A) = R(A2)+ 1 Then R(A) = R(A1) and L(A) - 2R(A:) +2R(A1)' -3 - and L(A)' 2R(A2) + 2R(A) - 1 But R(A1) 1 But R(A2)' 1 so L(A) - 2R(A) - 1. so L(A)' 2R(A) - 1 Hence, L(A)' 2R(A) - 1. Q.E.D. Remark: For each rank there exists a formula A of that rank such that L(A) = 2R(A) - 1, i.e,, a minimurm length Note that' for even values of L no formulas exist in S2 and the Theorem holds vacuously. 21

formula of that rank-. S-uch a formula can be obtained by starting with an ac and simultaneously prefixing a 42 and suffixing an a as many times as required, e.g., G2&2 2c is of rank 4 and length 7 Theorem 4. For any R - 2 there is no upper limit to the length (L) of formulas of S2 of this rankt. Proof. Consider any formula A of R t 2. An indefinitely long formula of the same rank may be constructed from it by repeatedly preceding it by 92 p. Q.E.D. Note that Theorem 3, the remark following it, and Theorem 4 establish the following concerning the formula of any given rank - 2: there is a lower bound to the length of these formulas but no upper bound. In the absence of an upper bound it would be of interest (in determining the relative capacity of the memory and the shifting register) to have more information concerning the relation between the length and rank of the formulas that would actually be tested on such a machine as has been proposed. Note in this connection that for all formulas A with the property that for every operator the arguments of that operator are of equal length (e.g., 9 aG2, 2_xG2G2 U2aG2 aa) it is the case that L() 2R(A) -1. For any formula r let' denote the formula derived from r by replacing each occurrence of N1 (if any) by N2p (where p is a dummy argument ) 4. Theorem 5. Let A be a wff in S. Then R(A) - R(A') R(A) + 1. Proof. (by induction on L(A) ) (I) The theorem holds for L(A) 1 i (trivially). (II) Assume it holds for all wff, A, such that L(A) - n. It will be proved that it holds for any formula, A, such that L(A) = n + 1 This proof involves two cases according to whether or not the first operator "of A is N1 Case 1. The first operator in A is not N1; A is of the form 9J Aj..A1. tThis theorem applies, more generally to any language, S 4Note that the "prime" symbol in the expression l' here denotes an operation on r 22

1. Thea A' - GJ A,..A' J 1 2. By the inductive hypothesis: R(A.) - R(A )' R(A ) + 1 3. But, by definition, R(A") = Max (R(A'.) + j - 1) j=l 4. Therefore, J J Max (R (A) + j 1) - R(A') Max (R (A.) + j - 1 + 1) j=1 j=l 5. R(A) -( R(A') A- R() + 1 Case 2. The first operator in A = N1; A is of the form A = N1 A1 1. By definition of the substitution operation, A' = N2 pA1 2. R(A1)' R(Ai)'- R(A1) + 1 by hypothesis. 31 Two sub-cases must be considered according to whether R(A1) 1 2 or R(AI) = 1 (a) Suppose R-(A1) 2, then R(A') =R(A) Now, since R(A) = R(A ), Step 2 yields R(A)'- R(A') c R((A)+: (b) Suppose R(A1) = 1, then R(A) = 1 R(A') = 2, satisfying the theorem. QE.D. Note that any of the -alterna-tive ways of constructing the N2 operator..would in general, increase both R and L. If the second rather than the first argument is the dummy, there is no upper limit to R(7 ) R(A) as shown by...N2N2N2pq12q3"' (= r ).. NiNlNl ((= A ) Hence L( r ) - L(A) is equal to the number of occurrences of N2 in r (or of N1 in A) If neither argument is a dummy, then in order to satisfy N1 23

formula (tautology or contruadiction)m. In either case extra computin time and perhaps extra equipment would be required. Using identity - N1 / -- N2F CC which is probably as simple a function as any, each occurrence of negation has its Rank increased by 1 and its Length increased by L - 1 as compared to the N2 proposed in this report4+. Using for A a simple constant formula, the contradiction Dpp, a negation has its L increased by 2 (as compared to the standard N2); its Rank is not increased except fo? the case of R(7 ) _ 2 tIf the symbols for 0 and 1 are included in the formula language (as suggested in section 2.4) the use of one of these constants as dummy, rather than a constant formula, would be a satisfactory alternative. 44This is true for all instances except L = 3 - the shortest possible expression. 24

In. CONCLUSION In conclusion a few remarks will be made concerning the use of the proposed- method., of evaluating truth-functions in connection with formulas of great length and many variables. This method, which was illustrated in section 2, may be summarized-as follows: For each Evaluant of the given formula., the: formula is scanned -from right to left, each variable being -replaced by its value in the Evaluant and each operator together with its arguments being replaced by its functional value until a single truth-value is Obtained. - Onee of the- advantages this method has is that the capacity of a machine embodying it may be increased with regard t-o the length, rank, or number of variables -independently, merely by enlarging the memory, the shifing register, or the counter respectively. The- speed -of operation required for extremely long formulas- may be shown by- reference- to an -example. Consider a formula containing 25 distinct variables and 250 characters. There are 225 Evaluants of this formula, and if these -are all reduced the machine must scan 250 x 225 or roughly 1010 characters-.- For this to be feasible the time per character must be of the order of microseconds; for example, 250 x 225 microseconds equals approximately 140 minutes. It is clear from the preceding sections that a serial, circulating memory is naturally adapted to the present method of evaluating truth-functions. Mercury delay lines would be especially suitable; a magnetic drum would be satisfactory but somewhat slower. A brief "design-sketch" will be presented for an evaluator using mercury delay lines of 1000 bit capacity and 1 microsecond pulse period. The design of an evaluator employing a magnetic drum would be very similar. We assume that the formula will be read into the machine from a magnetic or paper tape so that set-up time will be small. Consider a language containing the six dyadic operators K, A, C, E, D, N, the marker symbol *, and 25 distinct propositional variable-s. Express these 32 characters in a five-bit code and store them in parallel in a bank of five delay lines. Store the formula to be evaluated in this memory as many times as it will go, placing a * after each occurrence of it and filling every unused memory position with a *. There will be a certain waste of memory capacity (and hence of time) whenever the formula is not an integral factor of 1000 Characters in length; e.g., a formula of 251 characters (including a * ) would be stored three times with a waste factor of 247/1000 or about 25%. This waste factor could be decreased by the use of 2 or more banks of delay lines and some switching equipment. The above-described memory would feed a decoding function switch with five inputs and 32 outputs. These outputs would in turn feed a gated counter, operator function switch, buffer, shifting register, and stop box, 25

all of which would be the electronic analogues of the circuits shown in Figure 1. Certain minor variations in the design are necessary, e.g., one due to the fact that stars are used to- fill otherwise empty memory positions. It is- possible, using available electronic techniques, to construct these circuits so that they would keep up with the megacycle pulse rate of the circulating memory. Such a machine would completely evaluate a formula containing 25 variables and slightly over 250 characters in length in about three hours. 26

BIBLIOGRAPHY 1. Edmund C. Berkeley, Giant Brains, John Wiley and Sons, Inc., New York, 1949, Chapt. 9. 2* D. M. McCallum and J. B. Smith, "Mechanized Reasoning," Electronic Engineering,- April, 1951. 3. D. M. McCullum and J. B. Smith, "Feedback Logical Computers," Electronic Engineering, December, 1951. 4. W. R. Abbott, "Computing Logical Truth with the California Digital Computer," Mathematical Tables and Other Aids to Computation, 5(1951) 120-128. 27

UNIVERSITY OF MICHIGAN 3 9015 02653 5867 3 0502653 5867