Incomputer science, arule-based system is a computer system in which domain-specificknowledge is represented in the form of rules and general-purposereasoning is used to solve problems in the domain.
Two different kinds of rule-based systems emerged within the field ofartificial intelligence in the 1970s:
The differences and relationships between these two kinds of rule-based system has been a major source of misunderstanding and confusion.
Both kinds of rule-based systems use eitherforward orbackward chaining, in contrast withimperative programs, which execute commands listed sequentially. However, logic programming systems have a logical interpretation, whereas production systems do not.
A classic example of a production rule-based system is the domain-specificexpert system that uses rules to make deductions or choices.[1] For example, an expert system might help a doctor choose the correct diagnosis based on a cluster of symptoms, or select tactical moves to play a game.
Rule-based systems can be used to performlexical analysis tocompile orinterpret computer programs, or innatural language processing.[2]
Rule-based programming attempts to derive execution instructions from a starting set of data and rules. This is a more indirect method than that employed by animperative programming language, which lists execution steps sequentially.
A typical rule-based system has four basic components:[3]
Whereas the matching phase of the inference engine has a logical interpretation, the conflict resolution and action phases do not. Instead, "their semantics is usually described as a series of applications of various state-changing operators, which often gets quite involved (depending on the choices made in deciding which ECA rules fire, when, and so forth), and they can hardly be regarded as declarative".[5]
The logic programming family of computer systems includes the programming languageProlog, the database languageDatalog and the knowledge representation and problem-solving languageAnswer Set Programming (ASP). In all of these languages, rules are written in the form ofclauses:
A :- B1, ..., Bn.and are read as declarative sentences in logical form:
A if B1 and ... and Bn.In the simplest case ofHorn clauses (or "definite" clauses), which are a subset offirst-order logic, all of the A, B1, ..., Bn areatomic formulae.
Although Horn clause logic programs are Turing complete,[6][7] for many practical applications, it is useful to extend Horn clause programs by allowing negative conditions, implemented bynegation as failure. Such extended logic programs have the knowledge representation capabilities of anon-monotonic logic.
The most obvious difference between the two kinds of systems is that production rules are typically written in the forward direction,if A then B, and logic programming rules are typically written in the backward direction,B if A. In the case of logic programming rules, this difference is superficial and purely syntactic. It does not affect the semantics of the rules. Nor does it affect whether the rules are used to reason backwards, Prolog style, to reduce the goalB to the subgoalsA, or whether they are used, Datalog style, to deriveB fromA.
In the case of production rules, the forward direction of the syntax reflects the stimulus-response character of most production rules, with the stimulusA coming before the responseB. Moreover, even in cases when the response is simply to draw a conclusionB from an assumptionA, as inmodus ponens, the match-resolve-act cycle is restricted to reasoning forwards fromA toB. Reasoning backwards in a production system would require the use of an entirely different kind of inference engine.
In his Introduction to Cognitive Science,[8]Paul Thagard includes logic and rules as alternative approaches to modelling human thinking. He does not consider logic programs in general, but he considers Prolog to be, not a rule-based system, but "a programming language that uses logic representations and deductive techniques" (page 40).
He argues that rules, which have the formIF condition THEN action, are "very similar" to logical conditionals, but they are simpler and have greater psychological plausibility (page 51). Among other differences between logic and rules, he argues that logic uses deduction, but rules use search (page 45) and can be used to reason either forward or backward (page 47). Sentences in logic "have to be interpreted asuniversally true", but rules can bedefaults, which admit exceptions (page 44). He does not observe that all of these features of rules apply to logic programming systems.