GB2160684A - Expert system - Google Patents

Abstract

A computer method and system is provided in which an inference engine (11) forms inferences based upon rule data stored in flat files (10). The data represents expert knowledge. The flat files are multi- dimensional association tables for use in problem solving. An inference occurs when information observed is used with the flat files. The flat file structure provides, in the simplest case, a representation of results (consequences) in terms of observable characteristics (antecedents). Each such association is treated as a rule. The inference engine functions by backward or forward chaining rule- based deduction that amounts to proof of a goal statement on the basis of any initial state (a set of previously verified primitive statements) by application of production rules (P-rules). In accordance with one embodiment, in order to prove a goal, backward chaining occurs so that rules applied derive intermediate goals until every new intermediate goal is confined by the initial state. An explanation system (13) is incorporated which consists of displaying affirmative or negative English sentences as reports of each step pieced together during the proofs carried out by the inference engine. The report replicates the expert's line of reasoning in arriving at the conclusion of a proof. The invention thus achieves a portable expert system which is not dependent on any particular host computer system or any particular programming language and which can be utilized in any general purpose computer system (14) or in a particular computer hardware apparatus which offers the advantages of faster run times, less power and less volume. <IMAGE>

Description

SPECIFICATION Global expert system Background of the Invention The present invention relates to an expert system and specifically to data processing systems and methods for making inferences using rules.

As a general background to rule based systems, reference is made to the books Principles of Artificial Intelligence by N. J. Nilsson, Tioga Publishing Company, Palo Alto, 1980; Logic for Problem Solving by R. Kowalski, North Holland, New York, 1979; Introduction to Mathematical Logic, E. Mendelson, Van Nostrand, New York, 1963.

In the prior art, there are a number of traditional approaches to rule based deduction systems.

In general, such rule based systems have undesirable dependencies upon given languages or operating systems that require specific computing hardware environments.

Since existing rule based systems use an embedded language that recognizes and interprets rules, existing designs do not always include a rule syntax rich enough to provide easy expression of rules of expertise. Also, these designs do not provide sufficient quality in the explanations for conclusions drawn. Some rule based system designs do not embody traditional concepts of mathematical logic even though these have already been applied successfully in artificial intelligence research.

Although much research has been performed, there is a need for a system that separates the design from its expression in any given programming language and from its dependence on the peculiarities of any given operating system. Many rule based system designs are limited by their dependence on LISP source code. Such systems do not apply generally to the expert-intensive operations in a variety of environments for example, Digital Equipment Corporation's VAX/VMS system.

FORTRAN and PASCAL are two languages that run under most systems. PASCAL has two major advantages over FORTRAN as a choice for implementing rule based systems although FORTRAN could serve that purpose too. First, PASCAL supports recursive procedure calls-a clear and concise procedure execution scheme for the sort of complex searches required by deductive proof techniques. Second, PASCAL supports the dynamic run time allocation of linked list structures-a memory management scheme that is difficult to rival for clarity with array structures whose sizes must be determined statically at compile time.

When implementing an embedded language for a rule based system-viz., the language of rules recognized by the deductive proof procedure to be employed-PASCAL is a more attractive choice than FORTRAN. Recursion and linked lists are two principal programming tools used in compiler and interpreter technology and their availability in the programming language is a key consideration in selecting a language.

If, for example, PASCAL is selected as an implementation language and VMS as a host operating environment for a rule based system, it still remains to translate the quasi-formal procedural documentation of the rules of expertise into the embedded language of rules recognized by the rule based system. There is a need to develop methods for giving formal rule based expression to the order dependence of steps involved in the expert's procedural decomposition of the problem. Definitions for terms used by the expert in the expression of his rules need to be supported directly by the formal syntax.

In order to represent expertise, a system is needed to construct and maintain documentation of the expert analyst's strategies (rules of expertise). The documentation of expertise is initially developed through controlled query exercises with system experts. Cognitive strategies are explicitly documented in procedural form during these exercises.

The documentation of expertise is intended to explicitly retain expert judgement. For example, an expert may use terminology such as "low", "medium", "high", "out of bounds", and "disabled". Parameters are most usefully quantified into such 'heuristic' ranges since expert knowledge for many applications is not precise in the first place. The semantics of a formal rule syntax desirably preserves this heuristic information and preserves the expert's judgements as he stated them, for example, 'If the tolerance X is not low.

In view of the above background, there is a need for improved expert systems and methods which are independent of any particular host system and language and which are transportable among many different software and hardware systems.

Summary of the Invention The present invention is computer method and apparatus in which a universal data files are implemented as flat files and in which an inference engine forms inferences based upon data stored in the flat files. The data in the flat files represents expert knowledge and is separated from the inference engine.

The flat files are multi-dimensional association tables which function as a knowledge representation structure for use in a problem solving method or paradigm. An inference occurs when information observed is used with the flat files. The flat file structure provides, in the simplest case, a convenient two-dimensional tabular representation of results (consequences) in terms of observable characteristics (antecedents). Each such association is treated as a rule and each rule codifies the associative knowledge as data to which inferencing procedures are applied to solve the particular problem of interest.

The inference engine of the present system functions by backward or forward chaining rulebased deduction. The system operates with a computation that amounts to proof of a goal statement on the basis of any initial state (a set of previously verified primitive statements) by application of production rules (P-rules).

In accordance with one embodiment, in order to prove a goal, backward chaining occurs so that rules applied derive intermediate goals until every new intermediate goal is confined by the initial state. In this way, the goal statement is established by producing a proof of it through the backward piecing together of proof steps until steps already known to be true are the only ones that remain.

In the present invention, the explanation system consists of forming simple reports of each step pieced together during the proofs carried out by the inference engine. The report replicates the expert's line of reasoning in arriving at the conclusion of a proof. The explanation facility therefore merely traces and reports the steps of the inference engine. The reporting is a textoriented display written at the time that the rule set is developed. For each atom involved in any rule of the set, an affirmative English sentence and an opposite English negation sentence is established. The explanation procedure receives an index of an atom whose mnemonic identifier occurs in the expression of a rule cited in any given proof step.The atoms index is used to recover the affirmative or negative sentence for display according to whether the mnemonic for the atom was affirmed or negated in the rule.

In accordance with the summary, the present invention achieves an improved expert system which is not dependent on any particular host computer system or any particular programming language. The present invention achieves a portable expert system which can be utilized in any general purpose computer system and can be implemented as a particular computer hardware apparatus. The hardware apparatus offers the advantages of faster run times over that of a general purpose computer and can draw less power and occupy less volume.

Additional objects and features of the invention will appear from the following description in which the preferred embodiments of the invention have been set forth in detail in conjunction with the drawings.

Brief Description of the Drawings Figure 1 depicts a block diagram of an expert system in accordance with the present invention.

Figure 2 depicts a block diagram of one entry of a flat file in accordance with the present invention.

Figure 3 depicts a compressed data record representation of a flat file.

Figure 4 depicts a block diagram of an inference engine for forward chaining in accordance with the present invention.

Figure 5 depicts a block diagram of an inference engine for backward chaining in accordance with the present invention.

GENERAL SYSTEM In Fig. 1, a block diagram of a system in accordance with the present invention is shown. In Fig. 1, the knowledge base store 10 stores N-dimensional arrays which are called flat files. Store 10 is typically a random-access memory having addressable locations where each address location stores a flat file in the form of logical ones and zeros. Entries in the store 10 consist of atoms, and there are atoms of several types. Relationships between atoms are defined as rules.

Each rule has a combination of antecedent atoms and consequent atoms. For example, a boolean combination of one or more antecedent atoms defines a boolean combination of one or more consequent atoms. Antecedent atoms which are a result of observation, for example human observation, are defined as primitives. For purposes of explanation, antecedent atoms are defined to be on the left side of an expression separated by a symbol ": =" and consequent atoms are defined to be on the right of the symbol. The term "left" and "right" however have no meaning except to separate the antecedent and consequent. Antecedents appear only to the left of the rule symbol (:=) and goals are consequences which appear only to the right of the rule symbol (:=) A consequent which appears on the right of one rule may appear on the left of another rule. In general, therefore, a consequent is merely an intermediate result between a primitive and a goal.

A flat file consists of one or more rules having common attribute types (that is,common types of atoms) but different attribute values (that is, the atoms can have different logical one or logical zero values). Because the consequents in one flat file may serve as antecedents for another flat file, flat files are indirectly linked by the fact that consequence atoms among several files may appear either to the right or to the left of the rule symbol (: = ). The information in flat files is inherently linked through consequent atoms, but, there is no linking pointer which interconnects one flat file to another.

The rules stored in store 10 are identified by an address or name called the rule ID. Each rule includes a field for identifying the type of rule, inclusive or exclusive, and one or more fields indentifying each of the atoms of the rule together with the relationship between the antecedent and consequent atoms.

For inclusive rules, backward chaining must be employed, but for exclusive rules either forward or backward chaining may be employed. An example of a rule is as follows: P1#P2:= P3.

In that rule, P,SP2 is the antecedent and P3 is the consequent. The rule states that the logical AND of the atoms P, and P2 implies the atom P3.

In addition to the rules, store 10 stores an atom table. The atom table is a directory of all atoms within the knowledge base and is in three sections. The first section is a primitive store which includes address locations, addressed by primitive atom names or IDs. All possible primitives in the system are stored in the primitive store. Each location includes a field storing the rule ID for each rule within which the primitive atom appears together with explanatory text field which is used whenever the atom is proved.

The atom table additionally includes a consequent store addressed by consequent atom names or IDs. All possible consequent atoms in the knowledge base are stored in the consequent store.

Each address location for each consequent atom includes a field storing the rule ID for each rule within which the consequent atom appears. The consequent store additionally includes an explanation text field, which is used whenever the consequent is proved.

The atom table additionally includes a goal store addressed by goal atom names or IDs. All possible goal atoms within the knowledge base appear in the goal store. Each location for a goal atom includes a field storing the rule ID for each rule within which the goal appears and includes an explanation text field to be used whenever a goal is proved.

In Fig. 1, the inference engine 11 is an apparatus which uses the information from the knowledge-base store 10 to determine whether certain goals are true given a set of selected input primitives (that is, input observations). The input primitives are tested by either forward or backward chaining to determine whether or not they satisfy the rules in the rule table. The inference engine tests the primitives and the rules to determine if the goals are satisfied. The sequence followed by the inference engine and by which individual atoms are proved to be true is recorded in the explanation store 13. Thereafter, an interrogation of store 13 to sequentially access each atom, together with the explanatory text from the atom table corresponding to that atom, provides an expert text in a sequence which explains how the goals are proved to be true.

In Fig. 1, the user interface 12 is a mechanism which initiates a requests to the system of Fig.

1. When the user interface 12 is an application program, then the application program is resident in the host computer system 14. The host computer system 14 typically includes hardware 16 and an operating system 15. User interface 12 typically includes a terminal or other input/output device associated with a host computer 14. The function of the user interface 12 is to provide the input primitives on which the inference engine operates to determine whether or not goals are satisfied by the rules in the expert system.

Further details of preferred embodiments of the invention will be described after the following description of certain features of the present invention.

Flat Files-Figure 2 A multi-dimensional association table is used as a knowledge representation structure in a problem solving method or paradigm. Such multi-dimensional association tables are called 'flat files'. The flat file structure provides a convenient two-dimensional tabular representation of results (consequences) in terms of observable characteristics (antecedents). Each such association is treated as a rule and each rule codifies the associative knowledge as data to which inferencing procedures are applied to solve the particular problem of interest.

An example of a flat file is shown in Fig. 2 for the rule P1VP2V( - P3): = P4#i#P5. The rule states that the logical OR of P1, P3 and (- P3) implies the logical AND of P4 and P5. The antecedent is P1VP2V( - P3) and the consequent is P4 & 5.

The main idea behind the paradigm is that observations are used to reduce a candidate set of results by retaining only those candidates whose associated characteristics include those observed. From an initial set of candidates, typically consisting of all possible outcomes defined, only those with characteristics presented in the current set of observations are selected. In this way, a new set of candidates are inferred from a previous set of candidates on the basis of new observations.

The flat file representation solves two engineering problems. First, flat files provide a computer-language independent representation of the rule base to be used in applying the paradigm (problem solving technique) to the problem of interest. This language independence postpones the choice of computing hardware and language until the implementation phase.

Most often, some dialect of LISP is used for implementation. However, use of flat files permits designs for many different environments at once, for example. ROSIE under INTERSLIP/20 and PASCAL under DEC VAX 3.0.

The second engineering problem solved by flat files is the need for a data abstraction method in representing the rule base for expert system applications. The tabular representation of the rule base with a flat file enables an orderly and comprehensive understanding of the rules.

Conceptual errors and deficiencies in the rule base are easily detected given a clear understanding of the particulars involved in the problem of interest.

Given the flat file of rules associating results types with observable characteristics, the main task during the implementation phase is the judicious choice of data structure implementation techniques for the flat file of rule data. It is desirable to choose data structures that are comparatively efficient for different languages, for example, ROSIE and PASCAL.

In the case of the ROSIE, the associations codified in the flat file are represented with relational assertions of the form 'x is a characteristic of object y'. In the case of PASCAL, the flat file tends to be sparsely populated since it selects comparatively few of the possible associations it could represent. Since it is wasteful of memory to implement the flat file with a twodimensional boolean array (most elements would have the value 'false'), the flat file is implemented instead with a pair of association list arrays, the first listing all characteristics of each result type, and the second listing all result types having each characteristic. In both cases, the flat file is sufficiently abstract and language independent of the rule base to allow for the advantages and data structuring strengths of each language.Moreover, it is a simple matter to assure that the two implementations are semantically equivalent.

A Standard Paradigm for Flat Files The design of a standard paradigm requires operation without reference to a particular language or operating environment. The flat file representation is of particular utility in combination with standard paradigms.

Backward chaining rule based deduction The Al paradigm used for the parameter selection problem is called a backward chaining rule based deductive inferencing system. In such a system, a computation is the "proof of a goal" statement on the basis of an initial state (a set of previously verified primitive statements) by application of "production rules" called "P-rules." P-rules are "if-then" conditional assertions expressing laws about given problem domain.

Syntactic structure of production rules in P-rule form In a backward chaining deduction system, a production rule is composed of an "if-then" conditional implication sign, ': =', with left and right hand sides (called respectively the antecedent and consequent of the rule) composed as certain boolean combinations of simple statements (called atoms). We define a literal to be any simple statement (atom), for example, 'PlusFouled', or its negation, for example, '- PlusFouled'. The antecedent of a production rule can be an arbitrary conjunction (boolean product) of literals and the consequent can be an arbitrary disjunction (boolean sum) of literals.

The symbols for conjunction are the ampersand and the inverted wedge, while those for disjunction are the vertical stroke and the wedge. The symbol for negation is the hyphen. Atoms are to be represented by mnemonic identifiers in either upper or lower case alpha-numeric characters together with the underscore, subject only to the requirement that the first character of the mnemonic be alphabetic.

Obtaining proofs by backward chaining During the course of a goal's proof, the rules are applied to derive intermediate goals until every new intermediate goal is confirmed by the intial state (truth assignment). In this way, the goal statement is established by producing a proof of it through the backward piecing together of proof steps until steps already known to be true remain. To illustrate the idea, the set: 1. A:=B 2. -C & D:=E 3. b & & :=G 4. TO:= F 5. T18r-h:=F 6. T28-j:= F of production rules (1-6) can be used to confirm (that is, 'produce' a proof of) the goal 'G' by application of rules 3, 1, 4, and 2 respectively, to arrive at the literals 'A', 'TO', '-C', and 'D' confirmed by some initial state (truth assignment).

The flat file representation of P-rules The P-rule form of production rules requires the explicit representation of the negations of atoms within the rule structure. The flat file representation of P-rules is exhibited in Fig. 2. Note that for any production rule in P-rule form, there is a flat file of the form exhibited in Fig. 2.

This result provides a method for constructing a flat file corresponding to any given production rule in P-rule form and there is an abstract data type for P-rules. For a PASCAL implementation of the inference system, a more space efficient data structure, equivalent to the Fig. 2 flat file representation, results from the observation that the columns of any flat file of the Fig. 2 type are either empty or they select exactly the same rows. Thus, for a vocabulary of n atoms, the space complexity for the implementation of a P-rule from 4n2 elements in the corresponding flat file is reduced to 4n elements in the PASCAL data structure used utimately to represent that P-rule. Fig. 3 shows the reduction in storage space for P-rules for the Fig. 2 flat file when represented in a PASCAL flat file form.

System Syntax A rule consists of a boolean product of literals and a consequent consisting of a single literal.

The system allows a boolean sum of literals as the consequent of a rule.

The system does not allow the assertion of atomic statements composed of relational predicates followed by terms (individuals standing in the relations denoted by relational predicates, e.g., 'FATHER (Mary, John)', "COUSIN(Mary,x)'). Furthermore, the backward deduction system does not support the expression of non-atomic statements composed as "qu antificational" sentences in which individual variables are bound to occurrences of symbols for the quantifiers 'every' and 'some' (e.g., '(Some x)COUSIN(Mary,x)' which asserts that Mary has at least one cousin).

In the case of production rules in the system there are no relational predicates, terms, or quantifiers. Instead, atomic formula are simple sentences with no further distinguished syntactic structure. This difference in syntactic structure carries over to the mathematics of the underlying deductive logics used. The system does not support "first-order predicate calculus" which provides for inferences involving the quantifiers and relationally composed statements described but the system does support "sentential calculus" which provides for inferences involving only simple statements in which no syntactic structure below the level of the boolean operators is distinguished.

Logical validity and provability within the system A boolean combination of simple sentences is traditionally said to be "logically valid" if and only if it is verified by every assignment of truth values to its atomic constituents, that is, its truth table column yields the value 'true' for every atomic assignment row. Logical validity is a semantical property since it has to do with the value of a sentence under all assignments of truth values to its atomic constituents.

On the other hand, a sentence is traditionally said to be "provable" in a given system of deductive logic if and only if a sequence of sentences ending with the sentence in question can be generated by the application of proof procedure rules. Extensions of this notion of provability to the notion of the provability of one sentence on the basis of another in a given system are certified as a matter of course in most formal presentations of deductive logic.

Soundness and completeness of deductive systems These two notions of "logical validity" and "provability" are traditionally used to define two important properties of a formal system of deductive logic. First, a system is said to be "logically sound" if only logically valid sentences can be proven within it. Secondly, a system is said to be "semantically complete" if every logically valid sentence can be proven within it.

The system is logically sound but not semantically complete. This incompleteness results because the only deduction rule employed in the backward piecing together of proofs is "modus pones" (if you can prove 'A: = B' and 'A', then you may infer 'B') which is demonstrably sound. In order to make the system semantically complete, several other sound deductions rules are added, specifically 'indirect proof'' (if you can infer both 'B' and '-B' on the assumption of a 'A', then you may infer '-A') and "conditional proof" (if you can infer 'B' on the assumption of 'A', then you may infer 'A: = B'). The principal aim in implementating a backward deduction system is not, however, to achieve "semantical completeness" at the expense of other important properties for example the recovery of proofs in a form that an expert would give them.

Logic programming systems can achieve "semantical completeness" by sacrificing the threads of reasoning implicit in the order of negation and consequence in the expert's rule set. Proofs thus obtained reproduce only chains of consequence expressed in restricted syntax for rules.

The backward chaining inferencing paradigm provides naturally for explanations of its conclusions. Explanations are obtained as simple reports of each step pieced together in the proofs. By its very nature, such a report will replicate the expert's line of reasoning in arriving at the conclusion of a proof. An explanation facility for the inferencing system is thus achieved as a simple addition (tracing and reporting) to the inference engine.

The explanation facility converts a trace of the steps involved in the proof of its latest result into a text-oriented display. The text used in the display is introduced by the knowledge engineer in the development of a rule set.

For each atom involved in any rule of the set, the knowledge engineer supplies an affirmative English sentence and an opposite English negation sentence. The explanation procedure needs only to be passed the index of an atom whose mnemonic identifier occurs in the expression of a rule cited at any given proof step. The atom's index can then be used to recover the affirmative or negative sentence for display according to whether the mnemonic for that atom was affirmed or negated in the rule. Again, this simple approach to providing the user with explanations of the system results is made possible by the nature of backward chaining deduction.

The form of explanations displayed to an analyst have the text for a literal displayed at a given level of identation while the text for every literal to be established for its proof is displayed below it at the next level of indentation. The first line of text presents a global diagnosis of the latest run's results. Goals reporting parameter specific results are embedded deeper in the explanation in accordance with the system expert's way of decomposing the problem.

A compiler for high level rules in the system The PASCAL data records representing production rules in P-rule form reside in a file within the system's file directory. The P-rule data file is generated by a compiler that creates one or more P-rules from any of a number of higher level rules contained in a editable ascii file.

The higher level rules, called H-rules, extend the content of the P-Rule form of production rules but are, at the same time, reducible to them by certain well known laws of sentential logic.

The many-one relation between P-rules and H-rules described below provides the knowledge engineer with a useful method of reducing the risk of error at rule entry time since it potentially reduces the number of rules per rule set. For instance, one rule set generated 77 P-rules in the internal PASCAL form from 43 H-rules.

H-rules extend the content of P-rules H-rules allow for the expression of equivalences ("if and only if" biconditionals) as well as the canonical implications ("if then" conditionals). Thus, the knowledge engineer may express two separate P-rules of the forms 'A = :B' and 'B = :A' with a single H-rule of the form 'A = = B'.

Moreover, an H-rule may have a boolean sum of products (disjunction of conjunctions) of literals (atoms or their negations) as its antecedent ("if" or left-hand side) instead of just a single boolean product as specified by the syntax for the P-rule form. This allows a further compression of the rule set since the knowledge engineer may represent two rules of forms such as = = =C' and 'D & : = C' with a single rule of the form 'AbBvDbE: = C'. Similarly, the consequent ("then" or right-hand side) of an H-rule may be a boolean product of sums instead of just a single boolean sum. This allows the reduction of two such forms as, for example, 'A: = (BvC)8(DvE)'.

The compiler exploits some properties of sentential logic The system's H-rule compiler allows for a more concise form of user definable rule, and also eliminates uninformative and redundant P-rules. The uniformative P-rules are those which would be true no matter what, that is, those with contradictory antecedents (e.g., 'AHA: = B') and those with trivial or necessarily true consequents (e.g., A: = (Bv-B'). Such P-rules are eliminated from the P-rule set generated by the compiler along with a message that such action is being taken.

The elimination of redundant P-rules is achieved by an optimization pass of sorts over the file of initially generated P-rules. The idea is that if the consequent of a given P-rule can be derived on the basis of an initial state consisting of its antecedent from the rest of the P-rule set, then the rule can be eliminated on the grounds that it adds no information to the P-rule set. The formal justification for this optimization procedure is the "deduction theorem" for sentential logic which provides that if B can be proven on the assumption of A then 'A: = B' is provable.

A final logical property of the system that can be exploited stems from its reliance on sentential logic. Since there are decision procedures for the logical consistency of rule sets in sentential form (though not for rule sets in full first-order predicate form), the rule compiler tests a given rule set's logical consistency.

This test is an advantage of the system's backward chaining deduction which becomes more significant the larger the rule set selected. The detection of logical inconsistencies by human inspection becomes increasingly difficult as the complexity of the set of rules increases. A rule set that grows large is one for which we would want most to ensure consistency.

While a compiler is desirable for the reasons described, the present invention is applicable to any flat file system regardless of how the P-rules are formed.

Generalizing The System Inference Initialization The flat file and inference engine system can be implemented using a standard subset of PASCAL. When so implemented, the system is portable across a wide range of operating systems. One example of a program for use in a system which runs PASCAL under Digital Equipment Corporation VMS in accordance with the present invention appears in the APPENDIX attached to this specification.

Although a rule compiler can recognize only boolean ("if-then", "and", "or", "not") structures in admissible rules, there are advantages when the compiler recognizes syntactic structure below the level of the simple sentence including relational and functional expressions with free variables (the formal counterparts of pronouns).

FORTRAN namelist input is a good example of a standard data representation. Note that in a namelist, an identifier is given together with associated values at each list component. This identifier in effect makes each namelist a binary relation (a set of ordered pairs of values) in the simplest case. For example, the namelist: idl 123 id2 456 id3 789 can be construed as a set of tuples satisfying a binary relation such as "ValueOf(X,Y)", "LowerBound(X,Y)" or perhaps ''Coefficient(X,Y)'', depending on the application. Higher degree relations are also obtainable from FORTRAN namelists. An extended inference engine makes the use of FORTRAN namelist representations of relations transparent to the user in the sense that no special purpose interface to these data representations would have to be developed for each application.

The system uses data representation (viz., tuples) that are structurally identical to those used in relational database management systems. That is, relational database systems and predicate logic rule based systems are founded on the same notion of a relation.

The relational expression evaluation mechanisms within the inference engine is also extended to include user transparent access to FORTRAN namelists and relational data base systems such as INGRES. This extension eliminates the need to develop special purpose interfaces to problem domain data.

System Performance The performance of the inference engine is, in part, a result of reducing the execution time needed to construct proofs of goals by backward chaining. The traditional method of searching the rule base uses an order(n) linear scan for the next of n rules to apply in an attempt to prove a given (sub)goal. This computation is eliminated by having the rule compiler compute for each literal (simple sentence or its negation) a list of rules to apply in searching for a proof having that literal (atom) as a conclusion. This list of rules, indexed by atom name or ID is stored in an atom table. This atom table reduces one component of the proof construction overhead from order(n) to order(1).

Another high performance factor is in the time used to execute SETATOMS in order to construct an initial state description against which the inference engine terminates its backward chaining search for goal proofs. The systems run time parameter and atom table construction procedures minimize disk service requests. The observed delays due to initial run time input/output activity is thus attributed to the order (2M) time bound on the proof search algorithm itself, where M is the number of simple atomic sentences used in the rule base.

Predicate Logic An extended rule language partly implemented in software in the system includes atoms expressed as relational expressions with individual constants (names, numbers), individual variables (pronouns), and functions of individuals serving as admissible argument types. The extensions bring the rule language up from the level of simple boolean sentential logic to the level of first order predicate logic. Rules expressed in unextended syntax are defined as rules in sentential form and rules expressed in the extended syntax are defined as rules in first-order or predicate form.

The inference engine provides for inferences warranted by the predicate logic form of rules but not accounted for by the inference engine using the sentential form of rules. In addition to the procedures used to handle inferences involving rules in sentential form, the rule of unification (finding appropriate term substitutions for free variables) is implemented to handle predicate logic inference rules such as: Formal Expression English FROM: OutOfBounds (x) Everything is out of bounds.

INFER: OutOfBounds (min(lNT1)) The minimum INT1 is out of bounds.

A disadvantage of the predicate logic form is that the consistency of a set of rules cannot be effectively tested since consistency for sets of formulas of first order logic is an undecidable problem (a problem for which there is not an algorithm that halts in a finite number of steps with a definite answer).

However, an important practical advantage of the extended language is that complex logical relations and conditions can be expressed more concisely. The introduction of atoms composed in relational and functional form provides for a compression in the size of rule sets. Instead of the indefinitely long list of rules: :Parm10utOfBounds: = BadParml :Parm20ut0fBounds: = BadParm2 expressed without the aid of relational expressions and free variables, we may assert instead the single rule: :Parm(x) & r(Val(x),UpperBound(x)) := BadValue(x) The rule is interpreted as stating that "Anything that is a parameter and has a value greater than its specified upper bound has a bad value." or, less cryptically, "Any parameter value that is greater than its upper bound is bad." Rule Syntax The system's language of rules is based on a formal language for symbolic logic. The syntactic specification of this language is presented by discussing the lexical (word) structure and then the grammatical (phrase) structure of expressions recognized by the rule compiler.

The Lexical Structure of Expressions: The symbol types used to construct assertions, rules and other expressions recognized by the system's syntax are: (1) Predicate Constants.

(2) Individual Constants.

(3) Individual Variables.

(4) Function Symbols.

(5) Punctuation Symbols.

(6) Logical Constants.

We discuss each of these types in turn below.

(1) Predicate Constants: Predicate constants are identifiers that may be interpreted to express finitary m-place relations among individual objects. Predicate constant identifiers are composed as strings of the alphabetic and numeric character sets together with the underscore character, '~', subject to the provision that such strings begin with a "capital" alphaetic character.Thus, for example, GreaterThan, LESSTHAN, Equal-To, and Brushes-Too-Warn are predicate constants while the following strings are not for the reasons indicated: greaterthan -no initial capital alphabetical character 2nd Spark~Plus--no initial capital alphabetic character Power~1/2 ~illegal character '/' (2) Individual Constants The class of individual constants includes strings that conform to the rule for predicate constants as well as strings that represent real (fixed point) numbers. Individual constants may be interpreted as names of unique individuals (objects, numbers, etc.).Thus, the following strings Battery Ignition System~2000 3706 - 123.4546 are legal individual constants while the following are not for the reasons indicated: battery -no initial capital alphabetic character 2nd Staff -no initial capital alphabetic character .1 23e4546-not a fixed point number representation (3) Individual Variables Individual variables are composed as strings from the same character sets as the predicate constants and the alphanumeric individual constants subject to the different provision that they begin with an initial lower case alphabetic character.Individual variables are interpreted as the formal counterparts of pronouns in ordinary English in that they designate individuals only relative to a context that binds them to unique references. Note that typical variables are selected from the end of the alphabet but that the specification is much broader. Thus the following strings x y xl y234 object 1 plus 2 are legal individual variables while the following are not the reasons indicated: xl -no initial lower case alphabetic character 2nd object-no initial lower case alphabetic character x.1 1 ~illegal character, (4) Function Symbols: Function symbols are compassed in the same way as individual variables and are distinguished grammatically by context.Function symbols may be interpreted as finitary m-place functions that pickout a unique individual given a sequence of individuals as arguments.

Function symbols usually do not begin with letters toward the end of the alphabet, but, here too, such function symbols are not illegal. Thus the following strings sort xml bin-width are legal function symbols while the folowing are not for the reasons indicated.

SQUARE -no initial lower case alphabetic character.

2s complement-no initial lower case alphabetic character.

int#min ~illegal character, '#'.

(5) Punctuation Symbols: The punctuation symbols are used to group expressions recognized by syntax. The punctuation symbols are the parentheses, '(' and ')', and the square brackets, ' [ ' and ' ] '. Expression groupings such as function or predicate argument lists or boolean combinations of sentences that are initiated with '(' must be terminated with ')' and those beginning with '[' must be terminated with ' ] '.

(6) Logical Constants: The logical constants are the boolean sentence operators symbolized as follows: SYMBOL OPERATOR CONNECTIVE 8 conjunction (and) V disjunction (or) - negation (not) := conditional (if-then) biconditional (if and only if) The Syntactic Structure of System Expressions The syntax distinguishes several types of syntactic structure. These are: (1) Individual Terms.

(2) Atomic Formulas.

(3) Well-formed formulas.

(4) P-rules.

(5) H-rules.

(1) Individual Terms Individual terms are the class of expressions that can serve as arguments to functions or predicates. They are defined recursively as follows: (a) Every individual constant is an individual term.

(b) Every individual variable is an individual term.

(c) If f is an n-place function symbol and T1. . ., Tn are individual terms than f(Tl . . ., Tn) and f [ T1 . . ., Tn ] are individual terms.

(d) Only expressions satisfying rule (a), (b) or (c) are individual terms.

(2) Atomic Formulas Atomic formulas represent the lowest level of complete phrase structure within the syntax.

Atomic formulas are defined recursively as follows: If P is an m-place predicate constant and T1,. ., Tm are individual terms, then P(T1 . . ., TM) and P [ T1 . . ., Tm ] are atomic formulas. Nothing else is an atomic formula.

(3) Well-formed formulas The highest level of phrase structure recognized by the system syntax is the class of wellformed formulas. Members of this class are arbitrary boolean combinations of atomic formulas.

The class is designed recursively as follows: (a) Every atomic formula is a well-formed formula.

(b) If P and 0 are well-formed formulas, then so are -P, (P8Q), (PVQ), (P: = Q), and (P= =a) (c) Only expressions formed by a finite number of aplications of rules (a) and (b) are well formed formulas.

We also distinguish a class of well-formed formulas called literals.

(d) If A is an atomic formula then both A and -A are literals.

(4) P-rules P-rules are the simplest kind of rule recognized by the syntax. P-rules are defined recursively as folows: (a) Any single literal or finite conjunction of literals is a LITPROD.

(b) Any single literal or finite disjunction of literals is a LITSUM.

(c) If P is a LITPROD and S is a LITSUM then (P: = S) is a P-rule.

(d) Only expressions formed in accordance with rules (a), (b) and (c) are P-rules.

Note that a single literal, for example, '-OutOfBounds (Int(x))', may be regarded as either a boolean sum or boolean product of literals according to the Laws 'S = = (SVS)' and 'S = = (S & )'. There is a one-to-one correspondence between P-rules and the data structures generated by the rule compiler.

(5) H-rules H-rules are the most general kind of rule recognized by the syntax. H-rules are defined recursively as follows: (a) Any single LITPROD or finite disjunction of LlTPRODs is a PRODSUM.

(b) Any single LITSUM or finite conjunction of LlTSUMs is a SUMPROD.

(c) If P is a PRODSUM and S is a SUMPROD then (P: = S) and (P = = S) are H-rules.

(d) Only expressions formed in acord with rules (a), (b) and (c) are H-rules.

There is a one-to-many correspondence between H-rules and the P-rule preserving data structures generated by the rule compiler. The reason is that H-rules are really abbreviations of conjunctions of P-rules and are therefore equivalent to sets of P-rules by the following reduction schemas: H-rule Equivalent P-rule set ((P & )V(R & )): = T ((P8Q): = T, (R & ): = T) P: = ((QVR) & SVT)) (P: = (QVR), P: = (SVT)) P==Q (P: = O, Q: = P) Constructing H-rule Sets The rule sets are constructed as ascii text files by the knowledge engineer in the host computing environment. There are four sections in a rule set that declare expressions used to represent expert knowledge: (1) The NAMES section.

(2) The PREDICATES section.

(3) The FUNCTIONS section.

(4) The RULES section.

We present a representative piece of each section of the H-rule set under construction for one application and then comment on its form.

(1) The NAMES Section In order to enumerate the non-numeric individual constants used in an application, the knowledge engineer declares them in in the initial section of the application H-rule set as follows: NAMES Prange 1 Prange2 Prange3 Farther along in the H-rule set, the knowledge engineer uses these declared names to provide arguments of interest to predicates and functions of interest.

(2) The PREDICATES Section Following the NAMES section, the knowledge engineer declares the predicate constants to be used in the expression of rules of expert knowledge as follows: ~PREDICATES~ Sane(x) x is acceptable.

OutOfBounds(x) x is out of bounds.

Minimum(x,y) x is the minimum of y.

Maximum(x,y) x is the maximum of y.

DeltaThresh(x,y) y is the threshold for acceptable changes in x.

Note that for each predicate constant introduced in the PREDICATES section, a dummy argument list is given. The dummy argument list serves two purposes. First, the length of the list is taken as the degree (or "arity") of the relation so that, for example, 'OutOfBounds' is A unary or first-degree relation while 'Minimum', 'Maximum', and 'DeltaThresh' are binary or second-degree relations. Secondly, the dummy argument list serves to mark the relative positions in the succeeding line of text where the test for each substituted individual term is to be placed in retracing proofs during explanation.

(1) The FUNCTIONS Section After the knowledge engineer presents the PREDICATES to be used in the rule set, the FUNCTIONS section is presented as folows: -FUNCTIONS- squareroot (x) ATTACH ufool the square root of x.

min(x) PROJECT Min (x,y) the minimum of x.

max(x) PROJECT Max(x,y) the maximum of x.

Note that in the declaration of function symbols, we are not only given an argument list that serves the same two purposes as the argument list provided in a predicate constant declaration but we are also given an attribute specifying a method of evaluation.

Functions that are declared with the ATTACH attribute are evaluated at run time during proof construction by calling a PASCAL function named by the string given as argument to the ATTACH attribute, for example, in this case, a function named 'ufool'. Our terminology derives from the concepts of "procedural attachment" for (sub)goal verification within rule-based systems technology.

module USER FUNCTIONS (input/output) function ufool (x : real): real; begin ufool:= sqrt(x); end.

Functions that are declared with the PROJECT attribute are evaluated by projecting a term from a tuple in the table attribute. In the example above for the declaration of 'min', the relation table for a previously declared predicate constant, 'Min', is examined during proof construction and the function evaluates to the appropriate projection of any satisfying tuple. Thus, if 'min (Prangel)' is being evaluated during proof construction as a substitution instance of 'min(x)', the second element of the fourth tuple presented below in CHART 1 is its resulting value.

CHART 1 < Range, 123.456 > < Range2, 234.567 > < Range3, 345.678 > < Range9, 456.789 > The functional, 'min(Range3)', is evaluated by PROJECTING 345.678 from the tuple Range3,345,673- in the relation table for 'Min'.

(4) The RULES Section The last section of an application rule set is the section in which the knowledge engineer expresses the rules of problem domain expertise in terms of the declarations occurring the the previous three sections. For example: ~RULES~ Range(Range9).

Range(Range8).

:Range(Rangel).

:Range(Range2).

:Range(x)8G4diff(max [ x ] ,min [ x ] , deltathres(x) ] : = Sane(x).

This piece of the rule section leads to a rule that captures the idea that "any range whose maximum differs from its minimum by more than a known threshold is acceptable".

Forward Chaining System-Fig. 4 In Fig. 4, a forward chaining expert system is shown. The system includes a given store 25 which receives the input primitives from the user interface 12 of Fig. 1. The given store 25 is typically a push-down stack which stores a subset of all of the primitives which appear in the knowledge base store 10. This subset of primitives in store 25 represents observed data from particular observations which are to be tested against the knowledge base. A sequencer 26 causes each primitive, one at a time, to be pushed down in the store 25 to the address register 27. Address register 27 addresses the primitive store 28 which forms a part of the knowledge base store 10 of Fig. 1. The primitive store 28 stores a rule ID (an address) for every rule in which the primitive in register 27 appears.Table 28 is accessed and stores each rule ID in the rule ID registers 29. Sequencer 26 causes each rule ID in registers 29, one at a time, to address the rule store 30. Register 29 typically includes a number of fields, one for each rule ID. Rule ID's in register 29 are shifted, under control of the CIDS signal from sequencer 26, one at a time to the output field location 37 which addresses rule store 30.

The rule store 30 is part of the knowledge base store 10 of Fig. 1. The rule addressed in the rule store 30 has its consequence field accessed and latched by the CCR signal into the output consequence register 31. Consequence register 31 connnects as one input to the AND gates 32. The other input to the AND gates 32 is from the result register 33. For the initial operation of gates 32, the sequencer 26 sets the result register 33 to the all 1 's condition. The output from the AND gates 32 is then latched by the CRR signal into the result register 33. Thereafter, sequencer 26 causes the next rule from the rule ID registers 29 to access the rule store 30 and the consequence field from the corresponding field is stored into the consequence register 31.

The contents of the consequence register 31 are then AND'ed with the contents of the result register 33 and the result is again stored into result register 33.

This process of accessing rules from store 30 continues until all of the rules associated with the first primitive in register 27 have been accessed. Sequencer 26 detects when the register 29 is empty by operation of the tester 36.

Tester 36 detects an empty condition in the register 37. Tester 36, upon detecting an empty condition, provides an empty signal to sequencer 26 which in turn asserts the CGS signal which causes the next primitive from the given stack 25 to be pushed into register 27 to address the primitive store 28. Again the process is repeated for the rule ID from the primitive store 28 which is stored into the rule ID register 29. Again the rules for the second primitive are accessed one at a time from the rule store 30 and the consequences are latched into the consequence register 31. Each consequence in register 31 is AND'ed with the previous result in the result register 33.

This process of accessing rule consequences corresponding to each of the primitives continues until all primitives and all rules have been accessed and the corresponding consequences have been AND'ed together. At this time, when tester 34 indicates that there are no primitives and tester 36 indicates that there are no more rules, sequensor 26 senses the decoder 35 to test the contents of the result register 33. If decoder 35 finds all O's in register 33 and asserts line 64, then it indicates that the given primitives do not satisfy the rules within the expert system. More information is necessary before a result can be proved.

If decoder 35 detects one and only one 1 in the result register 33 and asserts line 65, then a unique proof based upon the input primitives has been determined by the expert system.

When decoder 35 detects more than a single one in the result register 33 and asserts line 66, it indicates that more than one unique proof exists from the given set of primitives and that therefore a single unique proof has not been determined.

During the operation of the Fig. 4 system, each rule ID used to address the rule store 30 is stored into the explanation stack 38. Stack 38, accordingly, provides a trace of the sequence by which the expert decision is arrived. When the rule stack 38, and the corresponding rule text from rule store 30 is accessed, an explanation of the expert determination is obtained. The sequencer 26 sequentially accesses the rule ID's from the explanation stack 38 by generating the CES signal which steps the rule ID's into the bottom-most register location 92 of stack 38.

Each rule ID in register 92 addresses rule store 30. The addressed location in store 30 has the text field portion 88 readout to the output device 89. Output device 89 is typically a display or printer.

Backward Chaining Expert System-Fig. 5 In Fig. 5, a backward chaining expert system is shown. In Fig. 5, a goal stack 50 is part of the knowledge base store 10 pf Fig. 1. The goal stack 50 stores all of the goals of the knowledge based system. As previously defined, the goals are single atom consequences. The goal stack 50 is, for example, a random access memory organized as a push-down stack. The bottom register in this stack is the register 78. The contents of store 50 are pushed down in sequence, one at a time, to register 78 under control of the stack increment signal CGOS from the sequencer 69 whenever a new goal is to be processed.

The sequencer 69 is a conventional sequencing device, such as a microprogramed processor or such as hardwired or programable logic. Sequencer 69 generates the control signals which all have a prefix "C" in Fig. 5. The timing and sequence of these control signals will be clear from the following description.

In Fig. 5, the given stack 72 stores a subset of primatives which are to be tested against goals in the goal stack 50 in accordance with P-rules stored in a rule store 74. The given stack 72 typically is a random access memory organized as a push-down stack, and represents the current state description.

The goal address store 51 is part of the rule address store 91 which is part of the knowledge base store 10 of Fig. 1. The rule address store 91 is sometimes called an atom table since it is addressed by atoms. Each location in store 68 includes one or more text fields which are accessed when a test is complete to provide a textual explanation of the sequence by which the test was completed.

Store 51 is organized to identify each rule in which a goal appears as a consequence. Store 51 is loaded by a rule compiler as previously described or by any other convenient means. The goal address store 51 is a random access memory which is addressed by the contents of the bottom-most register 78 in the goal stack 50. When addressed by the contents of register 78, the output from the goal address store 51 includes all of the rule ID's in which the goal in register 78 appears as a consequent.

Selection gate 53, when the CGOT signal from sequencer 69 is asserted, provides the rule ID's from the addressed location in address store 51 to the rule ID register 75. When CGOT is not asserted, gates 53 select the output from address store 68. Register 75 is clocked by the CRID signal from the sequencer 69 to store the parallel output from the selection gates 53.

Register 75 is organized with a plurality of fields with one location for each rule ID selected from the goal address store 51 or from the consequence address store 68. Rule ID's are unloaded, by shifting left to right for example by CSID signals from sequencer 69 into the rightmost field location 39.

The consequence address store 68 is part of the knowledge base store 10 of Fig. 1.

Consequence address store 68 when addressed by an atom from the atom stack 60, provides the rule ID's for each of the rules associated with the addressing atom as a consequence. The output in location 39 from the selected one of the stores 51 or 68 has its contents selected by the rule stack control 54 whenever the CRS signal from the sequencer 69 is asserted. The rule stack control 54 is a push/pop control for sequencially gating each rule ID from register 75 location 39 into the stack 56. Whenever the CRS signal from the sequencer 69 is asserted, the rule stack control 54 pushes the rule ID's into the stack 56. Whenever the CRS signal from sequencer 69 is not asserted, rule ID's are popped from the stack 56.

The control 54 includes a node-bit field 55. The node-bit field 55 is forced to 1 or a 0 under control of the CRSN signal from the sequencer 69. The node-bit 55 is stored as a 0 for all rule ID's except for the first rule ID from the register 75 for all rule ID's loaded from the address store 52 or from the address store 68. Whenever the rule store control 54 is loading rule ID's into the stack 57, the test RS unit 66 senses whenever the last field location 39 (and hence all fields) in register 75 is empty and causes sequencer 69 to stop pushing rule ID's into the stack 57. Whenever the control 54 is popping rule ID's from stack 57, the test unit 66 senses the rule ID bits and the node-bit in the top-most register 78 of stack 56 to permit control of the system based upon the 1 or 0 conditions of the bits in the top-most register 78 of the stack 56.

Rule Stack Node Control For pushes into stack 56, the node bit for the first rule ID pushed onto the stack is set to 1 and each subsequent rule ID from register 75 has the node bit set to 0. For pops, each rule ID is examined for an empty condition (all O's) and for the 1 or 0 state of the node bit.

For a purge of the rule stack, when required, the rule ID's with node bits 0 are purged until a rule ID with node bit 1 is found and thereafter all rule ID's with node bits 1 are purged until a rule ID with a node bit 0 is found. That rule ID with node bit 0 is not purged, but is left at the top of the stack in register 78. In summary, a purge occurs until a first 0 after a 1 is found, that is, until the first non-leading 0 is found.

When rule ID's are popped from stack 56, the control 54 connects the popped rule ID as an input to address the rule store 74. Rule store 74 is part of the knowledge base store 10 of Fig.

1.

Rule store 74 under control of the rule stack control 54 is addressed by the contents of the top-most register 78 in the stack 57. The rule ID from register 78 addresses the store 74 and causes all of the antecedent atoms from the rule store 74 addressed location to be stored into register 76. The antecedent atoms are latched in parallel into register 76 under control of the CATR signal from the sequencer 69. Each atom in register 76 is latched into a different field under the control of the CATR signal. The antecedent atoms for a rule latched into register 76, under control of the atom stack control 58 are shifted, left to right, out of register 76 through location 24, under control of the CSAT signal from sequencer 69 and pushed down into the atom stack 60.The atom stack control 58 is operated to push atoms from register 76 into stack 60 or to pop atoms from stack 60 under control of the CAS signal from the sequencer 69.

When the CAS signal is asserted, control 58 pushes atoms into the stack 60 and when nonasserted it pops atoms from the stack 60.

The atom stack control 58 includes a node control field 59 which is actuated under control of the CASN signal from the sequencer 59. Whenever atoms, other than the first atom from regist'er 76, are loaded into the atom stack 60 from register 76, the node control 59 causes a logical 0 to be loaded into the corresponding node field 61. The first atom from register 76 for a particular rule is set to a logical 1 to signify a node point. The test atom stack unit 70 senses the full or empty condition of register 76 and the register 79 to enable sequencer 69 to control the CASN signal.

Atom Stack Node Control For pushes, the node bit for the first atom of a rule is set to 1 and the node bit for each subsequent atom of a rule is set to 0.

Whenever an atom is proved, the atom is popped from the atom stack register 79, latched into explanation register 77 and pushed into the explanation stack 80. When an atom having a node bit set to 1 is proved, the rule stack 56 is purged and the next atom in the atom stack 66 is also thereby deemed to be proved. If that next atom also has a node bit 1, then by that fact the next atom is also deemed to be proved, the rule stack is again purged, and so on until the top-most atom in register 79 in the atom stack has a node bit equal to O or the atom stack is empty.

Whenever the CAS signal is not asserted and atoms are being popped from stack 60, the node control 59 together with the test atom stack unit 70 senses the 0 or 1 condition of the node-bit from the top-most register location 79 of the stack 60. In this way, operation of the system of Fig. 5 is conditioned upon the value of the bits accessed from the atom stack 60.

The atom stack control 58 connects the atom in the top-most register 79 as one input to the comparator 73 and as an input to address the consequence address store 68. The consequence address store 68 is typically a random access memory which forms part of the rule address story 91. The consequent address store 68 is addressed by atoms in the register 79 of atom stack 60.

Comparator 73 compares the atom in the top-most stack register 79 with the contents of the register 81 which is the bottom-most register in the given stack 72. The stack 72 functions as a shift register where the output from the bottom-most stack register 81 connects around as an input to the top of the stack 72. In this way, the contents of the stack 72 are circulated and every entry in stack 72 can be compared with the contents of the register 79 from stack 60.

The given stack 72 stores primitive atoms which are given as initial conditions to be used in proving that goals, specified by the goal atoms in goal stack 50, satisfy rules stored in rule sore 74. The given stack 72 is, therefore, sometimes referred to as a primitive stack.

Whenever comparator 73 detects identity, sequencer 69 causes the atom from register 79 to be latached into register 77 and pushed into the stack 64. The contents of register 79 are pushed into the stack 64 under control of the explanation stack control 62. Control 62 pushes atoms into stack 64 when the CES signal from sequencer 69 is asserted and pops atoms from stack 64 whenever CES is not asserted. Control 62 includes a node control field 63 which, in conjuntion with the tester 67 operates to detect and control the node-bits stored into the node field 65 of the stack 64. Each atom, except the first, associated with the most recent rule popped from the stack 56 is stored with a logical 0. The first atom is stored with a logical 1.If the rule popped from stack 56 represented by a sequence of atoms in the stack 60 is not proved, that is comparator 73 fails to have a comparison, then all of the atoms associated with that rule previously stacked into the explanation stack 64 are popped from the stack. That is, all atoms having a 0 prior to a 1 are popped from the stack 64. The 1 or 0 node state of the atoms popped from stack 64 are detected by the test ES unit 67 which in turn signals the sequencer 69.

The operation of the backward chaining system of Fig. 5 continues until all of the goals in stack 50 have been processed. Sequencer 69, whenever the rule stack 56 has an empty location in the top-most register 78, as detected by the test unit 66, asserts the CGOS signal to provide a new goal into the bottom-most register 78 of the stack 50. Thereafter, processing continues for the new goal as previously described in connection with the first goal. After all of the goals in stack 50 have been processed, as detected by the test unit 52, the sequencer 69 signals that the backward chaining analysis is complete.

Explanation Stack Node Control For a push, the first atom proved for a goal has its node bit set to 1, and therafter the node bit for each subsequent atom is set to 0. If a goal is not proved, all atoms in stack 64 with a node bit 0 are purged until the first node bit 1 is detected and it is also purged. The node bit field 65 in stack 54 can include more than one bit. For example, the node bit values from field 61 of stack 60, for each atom, are also stored in stack 64 for use in outputting text to output device 91. Each such asserted node bit is used to control a different level of indentation for textual explanations.

In Fig. 5, the bottom-most register 90 in the stack 64 provides an output to address the consequent store 68 each atom in register 90 addresses a location in the consequent address store 68. One or more of the fields in the store 68 stores a text field which is gated to the output device 89. Each atom in the output register 90 causes a text field to be output to the output device 89. The atoms in the stack 64 are pushed down by the CES signal from the sequencer 69 the process of outputting atoms to the output device 89 typically occurs after the sequencer 69 has detected that the goal proof is completed. The output device 89 is typically a CRT display, a printer, or other output device. Typically, the output device 89 is part of the user interface 12 of Fig. 1.

Operation of Backward Chaining System The operation of the backward chaining system will be described in connection with the example of rules in the following CHART 2 for a test using the primitives in Test 1 of CHART 3.

In CHART 2, the three goals G1, G2, and G3 are defined by rules R,3,R14 and R15, respectively.

In CHART 3, five different tests, Test 1, Test 2, Test 3, Test 4 and Test 5 are defined each with a different set of primitives. For example, the given primitives of Test 1 are A1, A2 and A3.

The step by step processing of Test 1 is depicted in CHART 4 for the first goal.

In CHART 4, and referring to Fig. 4, the column GS denotes the contents of the goal stack 50, the column RS denotes the contents of the rule stack 56, the column AS denotes the contents of the atom stack 60, the column ES denotes the contents of the explanation stack 64 and the column GIS denotes the contents on the given stack 72. The 1 or 0 value in parenthesis () denotes the node bit.

CHART 2 Rule Antecedent Consequent R1 A1 & A2 & 3 := B1 R2 A1 & A2 & A3 B2 R3 A3 & 4 & A5 B1 R4 A3 & A4 & A5 := B4 5 6 7 B3 A & A A R6 A5 & A6 & A7 := B4 R7 B1 & B2 := C1 R8 B1 & B2 := C2 R9 B1 & B4 := C2 R10 B1 & 4 := C3 R11 B3 & B4 := C4 R12 B3 & 4 := C5 R13 C1 & C2 ~ G1 C2 - G R14 C2 & := 2 R15 C4 & C5 ::= G3 CHART 3 Test Given Test 1 A1, A2, A3 Test 2 A3, A4, A5 Test 3 A5, A6, A7 Test 4 A1, A2 Test 5 A1, A2, A3, A4, A5 CHART 4 STATE GS RS(Node) AS(Node) ES(Node) GIS 1.1 G3 0(0) 0(0) (o) A3 G2 A2 G1 A1 0 1.2 G3 R13 (1) 0(0) 0(0) [COPY] G2 1.3 G3 0(0) C1 (0) ( ) [ COPy ] G2 C2(1) 1.4 G3 C2(l) 0(0) [COPY] G2 1.5 G3 0(0) B1 (0) 0(0) [COPY] G2 B2(1) C1 (o) C2(1) 1.6 G3 R1(O) ) Bl(0) 0(0) [COPY] G2 R3(1) B2(l) C1 (0) C2(1) CHART 4 (cont'd) STATE GS RS(Node) AS(Node) ES(Node) GIS 1.7 G3 R3(1) ) Al(O) 0(0) [COPY] G2 A2(0) A3 (1) B1 (0) B2 (1) C1 (0) C2 (1) 1.8 G3 0,0 B2 (1) Bl(O) [COPY] G2 C1 (0) A3(0) C2 (1) A2(0) A1(1) 1.9 G3 R2(1) B2 (1) Bl(0) [COPY] G2 G1(0) A3(0) C2 (1) A2(0) A1(1) 1.10 G3 0,0 A1(0) Bl(O) [COPY] G2 A2 (0) A3(0) A3 (1) A2(0) B2(1) A1(1) C1 (o) C2(1) CHART 4 (cont'd) STATE GS RS(Node) AS(Node) ES(Node) GIS 1.11 G3 0,0 C2(1) C1(0) [COPY] G2 B2(0) A3 (0) A2(0) A1 (o) [ COPY ] 1.12 G3 R8(0) C2(1) [COPY] [ COPY ] G2 R9(1) 1.13 G3 Rg(l) B1(0) [COPY] [ COPY ] G2 B2(1) C2(1) 1.14 G3 R1(0) B1(0) [COPY] [ COPY ] G2 R3(1) B2(1) R9(1) C2(1) 1.15 G3 R3(1) A1(0) [COPY] [COPY] G2 R9(1) A2(0) A3(1) B,(0) B2(1) C2(1) CHART 4 (cont'd) STATE GS RS(Node) AS (Node) ES(Node) GIS 1.16 G3 0,(0) B2(1) B1(0) [ COPY ] G2 C2 (1) A3(0) A2 ( ) A1(0) [ COPY ] 1.17 G3 R2(1) B2(1) [COPY] [COPY] G2 C2(1) 1.18 G3 0,(0) A1(0) [ COPY ] [ COPY ] G2 A2 (o) A3 (1) B2(1) C2(1) CHART 4 (cont'd) STATE GS RS(Node) AS(Node) ES(Node) GIS 1.19 G3 0,(0) 0,0 C2(0) A3 G2 B2(0) A2 A3 (0) A A2(0) o A1(0) B1 (0) A3(0) A2(0) A1 (O) C1 (o) E2 (0) A3 (0) A2 (0) A1 (O) B1 (0) A3 (0) A2(0) A1(1) 1.20 G3 R14(1) 0,0 [ COPY ] [ COPY ] 1.21 G3 0,(0) C2(0) [COPY] [COPY] C3(1) In CHART 4, in state 1.1, the goal stack 50 has been loaded with the goals G3, G2, and G,.

The given stack 72 is loaded with the primatives A3, A2, and A,. At this time, the sequencer 69 has issued a clear signal which clears all of the other registers and stacks to a 0 condition in preparation of commencing a test. After having been cleared, the test units 66 and 70 test the empty (all O's) condition of the rule stack 56 and the atom stack 60, respectively. At the same time, the test unit 52 detects that goal G, has not been stepped down to the register 78 so that register 78 is detected as not being empty. Sequencer 69 recognizes this condition and continues to assert the CGOS signal which causes the goal G, to be stepped down to the stack register 78. The goal G, addresses the goal address store 51. Sequencer 69 asserts the CGOT signal to select the rule ID's from the address location of goal G, in the goal address store 51.

The goal address store 51 is selected by selector 53 rather than the consequent address store 68 because the test units 66 and 70 detect the all 0 condition of the rule stack 56 and the atom stack 61.

The rule R13 ID is the one accessed from address store 51 for goal G, and is stored into the register 75. The CRID signal latches the rule R13 ID into register 75. The sequencer 69 then generates CSID signals to shift the R13 ID into the right-hand field location 39. At that time, the test unit 66 detects the non-zero condition of field 39 and hence presents R13 as an input to the rule stack control 54. Rule stack 54 is controlled by the CRS signal to push R13 into the rule stack 56 in the top-most location 78. The CRSN signal is asserted causing the node bit to be a 1. The state of the Fig. 5 system at this point in time is shown as state 1.2 in CHART 4.The term [ COPY ] in the column GIS indicates that the state of the given stack in state 1.2 includes all of the entries in the privious state 1.1.

At state 1.2 of CHART 4, the test unit 66 detects the presence of the rule ID R13 in the rule stack 78 and pops the R13 rule ID from register 78 to address the rule store 74. Rule store 74 is then accessed and loads all of the antecedent atoms for rule R13 into the register 76 by assertion of the CATR signal from sequencer 69. Thereafter, the CSAT signal is asserted by sequencer 69 until all of the atoms, C1 and C2 in this case, are unloaded through location 24 through the atom stack control 58 into the atom stack 60. The first atom loaded is C2 which has its node bit set to 1. The second and final atom C, is pushed into the stack with its node bit set to 0.At this point, the test unit 70 detects the empty condition of location 24 and signals sequencer 69 to stop pushing atoms through the control 58 into the atom stack. 60. At this point in time, the state of the Fig. 5 system is shown in state 1.3 of CHART 4.

In state 1.3, the test unit 70 detects that the atom stack 60 has a non-empty top-most register 79 and causes atom stack control 58 to provide the contents of register 79 as an input to the comparator 73. With the contents of register 79 connected as an input to comparator 73, sequencer 69 senses that the bottom-most register 81 of the stack 72 has a 0 condition by operation of the test unit 71. Sequencer 69 then asserts the CGIS signal gating the 0 out from register 81 and pushing it back into the top of the stack presenting the A1 atom into register 81.

The comparator 73 compares the contents of register 81 with the contents of the atom stack register 79. If a comparison is detected by comparator 73, then the contents of register 79 are latched into the register 77 by the CEXR signal and pushed into the explanation stack 64. In the case of state 1.3, however, C, does not compare with A, in register 81 and hence no comparison occurs. Sequencer 69 again aserts the CGIS signal causing A, to be gated from the stack and pushed back into the top leaving A2 in register 81. This process of comparing each entry in the given stack 72 continues until A2 and A3 have been again pushed back into the stack. The sequencer 69 asserts the CGIS signal until tester 71 again detects all O's in register 81 whether or not comparator 73 finds a comparison. Since no comparison results, the C, atom in register 79 is not popped from stack 60 but remains there.

The contents of register 79 remain output through the control 58 and as an input to the consequent address store 68. Since the rule stack 56 and the atom stack 60 are not both empty, sequencer 69 does not assert the CGOT signal and hence selects the output from the consequent address store 68. The antecedent of the rule addressed by C, in the consequent address store 68 is latched into the register 75. As before, the contents are shifted left to right through the location 39 and into the rule stack 56. In the present example, the rule ID accessed is R7 which appears in the register 78 with the node bit set to a logical 1. The state of the Fig.

5 system at this point in time is shown in state 1.4 of CHART 4.

With the state 1.4, and rule stack 56 not empty, and register 77 empty as detected by test unit 67, meaning that nothing was pushed into the explanation stack 64, the control 54 connects the contents of register 78 to address the rule store 74. The rule ID R7 addresses store 74 and causes the antecedent for that rule to be latched into the register 76 by assertion of the CATR signal. Thereafter, as before, the CSAT signal loads the contents of register 76 through the location 24 to push through control 58 onto the top of the atom stack 60. The state of the Fig. 5 system as this point in time is as shown in state 1.5 of CHART 4.

In state 1.5, after loading the atom stack 60, the control 58 is controlled by sequencer 69 to provide the contents of register 79 to comparator 73. Comparator 73 then compares the contents of the given stack 72 with the B, contents of register 79. Since B, does not compare with any of the contents in the given stack 72, no compare signal is given to the sequencer 69.

Accordingly, the entry in register 79 remains connected through control 58 to address the consequent address store 68. The consequent address store 68 provides the rule ID's for all rules having B, as a consequent into the register 75. Register 75 is then unloaded through location 39 and control 54 onto the rule stack 56. The first rule ID loaded is R3 and it has its node bit set to 1 and the second rule loaded is R, with its node bit set to 0. At this point in time, the state of the Fig. 5 system is shown in state 1.6 of CHART 4.

In state 1.6, the R, contents of rule stack register 78 addresses the rule store 74 and is popped. The antecedent field for the rule R, is loaded into the register 76 and then is unloaded through control 58 and pushed on top of the stack 60. At this point in time, the state of the Fig. 5 system is shown in state 1.7 of CHART 4.

At state 1.7, control 58 presents the A, entry in register 79 as an input to comparator 73.

Comparator 73 compares the A, value from register 79 with the contents of stack 72. Stack 72 contains A, as an entry so that comparator 73 detects the comparison and signals sequencer 79. Upon detection of the comparison of A, atom, the CEXR signal is asserted to latch the A1 atom into the register 77. The contents of register 77 at the same time are selected by control 62 to push the A, atom into the stack 64. Because the A, atom is the first one pushed into the stack for a goal, the node bit is set to 1. With register 77 containing an entry as detected by test unit 67, the control 58 connects the top entry in register 79, which at this time is the A2 atom since the A, atom has been popped into register 77. The A2 atom is compared in comparator 73 with the contents of stack 72. Stack 72 again finds a comparison and causes the A2 atom to be popped from register 79 into the register 77.Control 62 in turn causes the A2 atom to be pushed into the stack 64 with the node bit set to 0.

Again, the A3 atom appearing in register 79 is compared in comparator 73 to find a comparison with the A3 entry in stack 72. The A3 atom from register 79 is latched into register 77 and pushed into the stack 64 with a 0 for the node bit. The tester 67 detects that the node bit in register 77 from the A3 atom from register 79 has a logical 1. Sequencer 69 therefore automatically pops the next atom in register 79, the B, atom, into register 77 and pushed into the stack 64. Also, the sequencer 69 causes the rule stack to be purged so that R3(1) is popped and not used and register 77 is cleared by loading all 0's from location 24 through control 58.

At this point, the tester 67 detects a 0 in the node bit position for the B, in register 77 so that further popping of atoms from stack 60 does not occur without further proof. At this point in time, the state of the system of Fig. 5 is shown in state 1.8 of CHART 4.

At state 1.8, the B2 atom from the register 79 is gated by control 58 as an input from comparator 73 and is compared with the contents of stack 72. Because B2 is not a primitive in stack 72, the B2 rule ID addresses the consequent address store 68 and causes all rules of which B2 is a consequent to be gated into register 75. The rule ID in register 75 is R2 which is pushed onto the rule stack 56. At this time, the state of the Fig. 5 system is as shown in state 1.9 of CHART 4.

At state 1.9, the R2 rule ID through control 54 addresses the rule store 74 and place the atoms associated with R2 into the register 76 and R2 is popped from register 78. These atoms associated with R2 are pushed into the stack 60 and the state of the Fig. 5 system at this time is shown in state 1.10 in CHART 4.

At state 1.10, the atoms in stack 60 are compared with the contents of the given stack 72 in order as they are pushed up to the top-most register 79. A comparison occurs in order for A1, A2, and As and each of these atoms is therefore pushed into the explanation stack 64 on top of the information already in the stack 64. The information already in the stack 64 is shown in state 1.9 and for simplicity is indicated in state 1.10 by the word [COPY]. Accordingly, at this point in time, A1, A2, and A3 have been popped from the atom stack 60 and pushed into the explanation stack 64. When the A3 atom appears in register 77, the node bit 1 is detected by test unit 67 so that the next atom B2 which appears in the register 79 is also popped from stack 60 and pushed into stack 64.When the B2 atom appears in register 77, it also has a node bit 1 which is detected by unit 67 so that the next entry in the atom stack register 79 is also popped and pushed into the stack 64. That entry is the C, atom. At this point in time, the state of the Fig. 5 system is shown in state 1.11 in CHART 4. Note that the C1, B2, A3, A2, and A, atoms have been pushed onto the stack on top of the data previously in the stack (indicated by the word [COPY] and as explicitly shown in state 1.9).

At state 1.11, C, with its node bit 0 is in register 77. Therefore, sequencer 69 causes control 58 to connect the C2 atom in register 79 as an input to comparator 73. Since C2 after comparison with the primatives in stack 72 finds no comparison, C2 is used to address the consequent address store 68. The rule ID's for C2 are latched into the register 75 and pushed down into the rule stack 56. These rule ID's are R8 and Rg. The state of the sequencer at this point appears as state 1.12 in CHART 4.

At state 1.12, the R8 rule ID from register 78 addresses a rule store 74 and causes the B, and B2 atoms to be pushed down onto the atom stack 60. The state of the system is shown as state 1.13 in CHART 4.

At state 1.14, the B, atom in the atom stack 60 addresses the consequent address store 68 and pushes R3 and R, onto the rule stack.

Thereafter, R1 addresses the rule store 74 and pushes the atoms A3, A2, and A, onto the atom stack 60.

At 1.15, the A1, A2, A3 atoms each in turn find a comparison and are pushed into the explanation stack. Since the A3 atom has a node bit 1, the B, atom is also pushed onto the stack. Because the stack is loaded at a node point, the rule stack is purged in accordance with the purging rules. Since in state 1.15, all rules have node bit 1, all rules in the stack are purged. The state of the Fig. 5 system at this point in time is shown in state 1.16 of CHART 4.

In state 1.16, the B2 atom in the atom stack finds no comparison and hence accesses the R2 rule ID into the rule stack 56. At this point in time, the state is shown in state 1.17 of CHART 4.

At state 1.17, the R2 rule ID addresses the rule store 74 and causes the atoms from R2 to be pushed onto the atom stack 60 as shown in state 1.18.

At state 1.18, the A1, A2, A3 atoms find a comparison and are popped from the atom stack and pushed onto the explanation stack. Because the A3 atom has a node bit 1, the B2 top-most entry in stack 60 is also popped from the atom stack and pushed onto the explanation stack.

Because B2 also has a 1 in the node bit, the next entry C2 in the register 79 is also popped from the atom stack and pushed onto the explanation stack. At this point in time, the state of the Fig.

5 system is shown as state 1.19 in CHART 4.

At state 1.1 9, the rule stack 56 and the atom stack 60 have their top-most register 78 and 79 detected as empty. Accordingly, the sequencer 69 again asserts the CGOS signal stepping down the next goal into register 78. The goal G2 at that time addresses the goal address store 51 and selector 53 causes the rule ID for G2 to be latched into register 75. That rule ID is R14 and is pushed onto the rule stack 56. At this point in time, the processing of the second goal continues and the state of the Fig. 5 system is shown as state 1.20 in CHART 4.

At state 1.20, rule ID R14 from the stack 56 addresses the rule store 74 and is popped from the stack and in turn causes the atoms C3 and C2 to be pushed onto the stack 60. The state of the Fig. 5 system is shown as state 1.21 in CHART 4.

Processing of the goal G2 continues from state 1.21 in a manner analogous to that previously described in states 1.1 through 1.19 for goal G,. When processing of the goal G2 is complete, then the CGOS signal is again asserted to cause the G3 goal to be processed in the manner analogous to G, and G2.

When register 78 in the goal stack 50 and the top-most register 78 and 79 of the rule stack 56 and the atom stack 60 are all empty, sequencer 69 will detect this condition and Test 1 of CHART 3 wil be completed.

Thereafter, additional tests for example like those of Test 2 through Test 5 of CHART 3 can be commenced with processing carried out in the manner previously described in connection with CHART 4.

After a test is completed, sequencer 69 typically communications to, or in response to, the user interface 12 of Fig. 1 to output the textual description in the sequence determined by the atoms in the explanation stack 64. In order to output the textual information, the sequencer 69 repeatedly asserts the CES signal to push down the atoms in stack 64 one at a time on a first-in, first-out basis. Each atom as it appears in the bottom-most register 90 addresses the consequent address store 68 which in turn provides a text field to the output device 91. When output device 91 is a printer, a textual description of the manner in which the expert decision was reached is printed for human evaluation.

While the invention has been particularly shown and described with reference to preferred embodiments thereof, it will be understood by those skilled in the art that the foregoing and other changes in form and detail may be made therein without departing from the spirit and scope of the invention.

Claims (23)

1. A data processing system for processing data comprising, means for storing rules in flat files where each rule includes a plurality of atoms related in a manner specified in a corresponding flat file, means for storing one or more primitive atoms.

means for storing one or more goal atoms, inference engine means for processing primitive atoms and goal atoms to determine if said primitive atoms prove said goal atoms in accordance with said rules.

2. A data processing system for processing data to prove that goals satisfy rules using backward chaining when one or more primitives are given as initial conditions comprising, rule store means for storing rules in flat files where each rule includes an antecedent and a consequent formed by one or more atoms related in a manner specified in a corresponding flat file, primitive stack means for storing one or more primitive atoms, goal stack means for storing one or more goal atoms where each goal atom is a consequent of a rule in said rule store means, rule address store means having rule address locations where each rule address location is addressed by an addressing atom and where each rule address location stores rule addresses of rules having the addressing atom as a consequent, rule stack means for storing rule addresses accessed from said rule address store means, atom stack means for storing atoms forming the antecedents of rules accessed from said rule store means, comparator means connected for comparing primitive atoms from said primitive stack means with atom stack atoms from said atom stack means and for providing a compare signal when an atom stack atom compares with a primitive atom, sequencer means for processing primitive atoms and goal atoms to determine if said primitive atoms prove said goal atoms in accordance with said rules, said sequencer means operative for connecting a goal atom from said goal store means to address said rule address store means, for connecting rule addresses at the addressed location in said rule address store means to said rule stack means, for connecting rule addresses from said rule address stack means to address said rule store means, for connecting antecedent atoms from said rule store means to said atom stack means, for connecting atoms from said atom stack means to said comparator for comparing with primitive atoms from said primitive store means.

3. The system of Claim 2 further including an explanation stack having explanation stack locations and including explanation stack control means, responsive to said sequencer means, for pushing atoms into said explanation stack whenever said comparator detects a comparison between an atom in the primitive stack with an atom in the atom stack.

4. The system of Claim 2 wherein said rule stack means includes a push-pop rule stack having rule stack locations and includes a rule stack control means wherein each rule stack location includes a rule address node bit field used to control the pushing of atoms into said stack and the popping of atoms from said stack.

5. The-system of Claim 4 wherein said rule stack means includes rule stack node bit control means for setting the first rule address node bit to one state and each subsequent rule address node bit to the opposite state for all rule addresses resulting from said addressing atom.

6. The system of Claim 2 wherein said atom stack means includes a push-pop atom stack having atom stack locations and atom stack control means for pushing atoms into said atom stack from said rule store means and means for popping atoms from said atom stack.

7. The system of Claim 6 wherein said atom stack includes an atom stack node bit field for each atom stack location and wherein said atom stack control means includes means for setting an atom stack node bit to one state for the first atom of a rule and for thereafter setting the node bit for each subsequent atom for a rule to the opposite state.

8. The system of Claim 2 further including means for connecting an atom stack atom to address said rule address store in the absence of a compare signal to responsively push atoms onto said rule stack means.

9. The apparatus of Claim 2 including, rule stack test means for testing for rule addresses in said rule stack to determine if said rule stack is empty, atom stack test means for testing atoms in said atom stack to determine if said atom stack is empty, said rule stack test means and said atom stack test means connected to said sequencer means for signaling said sequencer means to select a goal atom from said goal stack means whenever the rule stack and atom stack are both empty.

10. The system of Claim 3 wherein said explanation stack means includes a push-pop explanation stack and explanation stack control means and wherein each explanation stack location includes an explanation stack node bit field and wherein said explanation stack control means includes means for pushing atoms into said explanation stack and popping atoms from said explanation stack under control of said sequencer.

11. The system of Claim 10, further including an output device connected tosaid rule address means and operative to output textual explanations from said rule address means sequentially in response to addressing of said rule address means by atoms stored in said explanation stack.

12. A data processing system for processing data to prove that goals satisfy rules using forward chaining when one or more primitives are given as initial conditions comprising, rule store means for storing rules in flat files where each rule includes an antecedent and a consequent each formed by one or more atoms related in a manner specified in a corresponding flat file, primitive stack means for storing one or more primitive atoms, rule address store means having rule address locations where each rule address location is addressed by a primitive atom accessed from said primitive stack means, and where each rule address location stores rule addresses of rules having the addressing primitive atom as a consequent, rule address register means for storing rule addresses accessed from said rule address store means, and connected for addressing said rule store means, consequent register means for storing atoms forming the consequents of rules accessed from said rule store means, combining means connected for combining consequent atoms from said consequent register means with the contents of said result register means to form a new result and connected for storing said new result into said result register means, decoder means connected to said result register means for detecting the state of said result register and thereby to determine if said primitive atoms satisfy said rules.

13. The system of Claim 12 wherein said combining means includes a logical AND for ANDing the content of said consequent register with the contents of said result register.

14. The system of Claim 12 further including an explanation stack connected to said rule address register means for storing each rule address accessed from said primitive stack means.

15. The system of Claim 14, further including an output device connected to said rule store means and operative to output textual explanations from said rule store means sequentially in response to addressing of said rule store means by rule addresses stored in said explanation stack.

16. In a data processing system having rule store means for storing rules in flat files where each rule includes an antecedent and a consequent formed by one or more atoms related in a manner specified in a corresponding flat file, having primitive store means for storing one or more primitive atoms, and having goal store means for storing one or more goal atoms, the method comprising, sequentially accessing each of said primitive atoms, sequentially accessing each of said goal atoms, processing each accessed primitive atom and each accessed goal atom to determine if said rules are satisfied.

17. The method of Claim 16 wherein said data processing system includes a rule address store means, rule address stack means, and atom stack means, and wherein said method is performed by backward chaining and wherein for each accessed goal atom, said processing step includes connecting a goal atom from said goal store means to address a rule address store means, connecting rule addresses at the addressed location in said rule address store means to said rule stack means, connecting rule addresses from said rule address stack means to address said rule store means, connecting antecedent atoms from said rule store means to said atom stack means, connecting atoms from said atom stack means to said comparator for comparing with primitive atoms from said primitive store means.

18. The method of Claim 17 wherein said rule address stack means includes a rule address node bit field and wherein said atom stack means includes an atom stack node bit field and wherein said method includes the steps of pushing and popping rule addresses into and from said rule address stack means under control of said rule address node bit field and pushing and popping atoms into and from said atom stack means under control of said atom stack node bit field.

19. A data processing system for processing data comprising, means for storing rules in flat files where each rule includes a plurality of atoms related in a manner specified in a corresponding flat file, means for storing one or more primitive atoms, inference engine means for processing primitive atoms to determine if said primitive atoms satisfy said rules.

20. The system of Claim 19 further including a goal stack for storing one or more goal atoms where each goal atom is a consequent of a rule in said rule store means and wherein said inference engine further includes one or more push/pop stacks each having a node bit field for controlling the pushing and popping of atoms into and from one of said push/pop stacks.

21. The system of Claim 20 wherein said inference engine includes a comparator for comparing primitive atoms with atoms from one of said push/pop stacks for providing a comparison signal whenever said atoms compare.

22. The system of Claim 20 wherein said inference engine includes an explanation stack for storing atoms from one of said push/pop stacks in response to a comparison signal.

23. Either of the data processing systems substantially as herein described with reference to the accompanying drawings.