ME290M
Expert Systems in Mechanical Engineering
Spring 1999, T-Th 12:30-2:00 pm
1165 Etcheverry Hall, Course Control No. 56369 http://best.me.berkeley.edu/~aagogino/me290m/s99
|
| ME290M
Spring 1999, T-Th 12:30-2:00 pm
|
| [ Home | Info | Syllabus | Readings | Students | Homework | Resources | News | Chat] |
A variety of methods have been used to develop "expert systems". One approach is to use conventional programming techniques. Such systems are typically implemented with contemporary procedural languages, and thus the knowledge of the system is represented by the statements of the underlying program. Inferences are generated by executing the statements in the program. In these systems, there is no clear-cut separation between the knowledge base and the inference mechanism: the two parts are inseparably interwoven.
Partially because of the limitation of these procedural approaches in modeling human thought processes, researchers in artificial intelligence have become interested in developing systems that describe the world in a declarative rather than a procedural manner. One widely accepted approach has been the use of predicate calculus in representing knowledge and making inferences. Although many would argue that classical logic does not accurately model human cognitive processes, most agree that logic programming languages are at least closer to this goal than procedural languages like FORTRAN or PASCAL.
Knowledge representation is one of the most critical considerations in designing expert systems. The representation can enhance or limit the knowledge engineer's ability to encode expert knowledge and will greatly affect the effectiveness and understandability of the final system. A variety of knowledge representations and inference procedures have been used to reason about declarative (as opposed to procedural) knowledge in the development of expert systems. Classical logic is attractive because it is a precise mathematical language that benefits from hundreds of years of development. The logical power of deduction has proved beneficial in virtually all realms of knowledge. It also provides a method of deriving new knowledge from old knowledge. Propositional logic and predicate calculus (PC) will be reviewed in this chapter. Other representational formalisms will be discussed in other chapters.
The foundations of classical logic are attributed to Aristotle in his approach to constructing rigorous arguments for validation or refutation as part of a public debate process in Classic Greece. He developed a set of syllogisms to demonstrate these principles and show examples of fallacious reasoning to be avoided. Although often termed Aristotelian logic, the development of propositional logic, in which the fundamental elements are whole sentences to be evaluated as true or false, was developed a century later by another Greek named Chryssipus.
Substantial extensions to classical logic did not occur until over a thousand years later in the works of medieval philosophers such as William of Occam, who developed modal logic in the fourteenth century. Model logic developed concepts of possibility, necessity, belief and doubt and is closely related to multivalued logics like probability theory and possibility . These alternative logics will be discussed in Weeks 7-11.
Leibnitz, in the seventeenth century, outlined a scheme for machine reasoning that was even more ambitious than his mechanical calculator (described in Week 1) or the mathematical machinery of "calculus" that he shared with Newton. He called this scheme "Characteristica Universalis," representing a calculus that would cover all thought, not just mathematical, by calculus type constructs. The system would contain all knowledge of the world so far and use logical constructs to derive new knowledge from established knowledge. Gardner [Gardner 1982] likens this system to "a universal algebra by which all knowledge, including moral and metaphysical truths, can some day be brought within a single deductive system." Needless to say, Leibnitz did not have the tools to implement these ideas, and the Characteristica Universalis was never realized.
Boolean Logic forms the foundation of modern logic today as initially outlined in Boole’s 1854 publication titled: An Investigation of the Laws of Thought on Which are Founded the Mathematical Theories of Logic and Probabilities. Boole applied the tools of modern algebra, such as the arithmetic operations of addition, multiplication, and subtraction, to create logical equivalents called union, intersection, and the connective "not". Boole invented the truth table to test the truth and validity of compound propositions. Boole also extended Aristotelian logic with the concept of existence. Giarratano & Riley (1998, p. 82-83) give the proposition "all mermaids swim well" as an example. Aristotelian logic would not allow the premise or the condition as mermaid don’t exist. But Boole’s logic relaxed this restriction allowing one to reason about empty classes.
Frege is credited with first developing a complete theory of first-order logic and a notational system for mechanical reasoning with it [Frege 1879]. This provided the theoretical foundation for the symbolic logic described by Whitehead and Russell (1910) in their seminal book Principia Mathematica. Although Whitehead and Russell stressed the virtues of formal logic to settle differences and counterweight human biases and irrationality in structuring formal arguments in mathematical theory, this practice was not realized in dealing with their personal disagreements. Russell’s position as a staunch pacifist made it very difficult for Whitehead to reconcile with the death of his own son in World War I. Though the book initially started as a joint effort, much of the bulk of the book was completed by Russell.
Propositional logic is represented by a set of propositions or complete English-like sentences concerning specific instances of objects. These propositions evaluate to true (T) or false (F).
(FILTER-1 IS CLOGGED)
(PUMP DISCHARGE IS ZERO)
(PUMP IS BROKEN)
There are established conventions for formalizing these propositions into what are sometimes called well-formulated formulas (or "WFFs" for short). These propositions contain no variables, only specific instances of an object or class of objects. As a matter of notation, I will enclose all WFFs in parentheses. Complex WFFs can be derived by using a small set of logical connectives on simple WFFs. These connectives are the Boolean operators termed: "NOT" (negation), "AND" (conjunction), an "OR" (disjunction). An example of a disjuction is given below in which the operator OR is at the beginning of the WFF. The proposition will evaluate to true if either simple WFF is true, in other words, if either the filter is clogged or the pump is broken.
( (FILTER-1 IS CLOGGED) OR (PUMP IS BROKEN))
Implications are defined as conditional statements such as the one below:
(IF (PUMP DISCHARGE IS ZERO)
THEN (OR (FILTER-1 IS CLOGGED) (PUMP IS BROKEN)))
There is also a set of inference rules for deducing new expressions from existing ones. So for example, we could infer from the previous implication-type proposition and the fact that the pump discharge is indeed zero, that either the filter is clogged or the pump is broken. We will cover these rules of inference in the next chapter for the more general case of predicate logic.
A predicate (as with a logical proposition) is a symbolic expression that evaluates to true or false. Informally, predicate calculus is distinguished from propositional logic in that the former allows the use of variables and a more complex grammar of quantification and logical implication concerning these variables. The "calculus" in predicate calculus refers to a methodology for calculating the truth of propositions.
In Prefix Predicate Calculus (PPC), the operator of the symbolic expression is written first, followed by operands from left to right. In contrast, in every day English we use the infix notation for active, transitive verbs, such as in the proposition above: (FILTER-1 IS CLOGGED). We also tend to use infix conventions with mathematical operators and some logical operators such as AND or OR. Examples of infix notation are shown below:
(1+ 2), meaning that the sum of the number "1" and the number "2").
(A OR B), meaning that A is true or B is true.
(A Æ B), meaning that A implies B or "If A is true then B is true."
The corresponding prefix notation might be:
(+ 1 2)
(OR A B)
(IF A B)
In this book both infix and prefix notation will be used. Infix notation, in which the predicate operator are embedded in each expression, reads more like natural language. The main advantage of prefix notation is that it is closer to the form that is implemented in most AI languages on the computer and it is subject to less ambiguity than the infix notation. So its useful to be able to convert back and forth between notations.
It is important to remember that correct syntax does not imply that the meaning is correct. We will concentrate on syntax in this chapter. Meaning, truth, and implications will be discussed in the next chapter.
The basic components of PC are:
• object symbols
- object variables
- object constants
- relation constant
- function constant
• terms
• logical operators
• quantifiers
• sentences
- atomic sentences
- complex sentences
All of the sentences in the PC language are composed of these components along with appropriate spaces and parentheses. The expression of a fact in this formal language is called a logical sentence. Predicate calculus provides a methodology for expressing complex facts as combinations of simple facts and to reason with variables in addition to specific objects.
In PC the universe consists of a fixed set of objects (which need not be finite) called the universe of discourse. An object constant is a connected sequence of alphabetic characters, numerals, and symbol characters (except parentheses). The object constant is the name used to represent objects in the system being described. These objects can be almost anything including, physical objects, abstractions, concepts, and sets. Examples are:
PUMP#1
WOMAN
COYOTE
ENGINEER
SENSOR#2
PEACE
7
HEAVY
WEIGHT
Alice.M.Agogino
x
The simplest kinds of objects are object constants which refer to specific instances of objects in the universe of discourse. For purposes of clarity, the convention in this book will be to represent object constants by a sequence of alphabetic characters or digits, in which the first character is either uppercase alphabetic or numeric. "Alice.M.Agogino" is a very specific object, which might be called in PC an object constant. Other object constants in the above list might be: the number 7, PUMP#1, and SENSOR#2. If the object can take on a number of different instances, it is called a variable . By convention in this book, a variable will be represented in lowercase, never beginning with a number. More restrictions on variables will be given in later sections.
A relation is used to describe objects and their properties. A relation constant will be represented by a connected sequence of characters, numerals, and non-contiguous characters (except parentheses). Relation symbols must begin with either a mathematical operator (e.g., =,<,>Œ, … ) or an uppercase alphabetic character. In this book, relations symbols will never begin with a numeral. Relation symbols are a subset of object symbols and are used to define relations between objects in the system being described. A relation has an associated arity, which indicates the number of arguments the relation can operate on. Examples are:
SUBSET
INFLUENCE
³
MOTHER
FRIEND
A function constant is a also a connected sequence of alphabetic characters, numerals, and non-contiguous characters (except parentheses). Like the relation constant, in this book the function constant will never begin with a numeral and will always begin with either a mathematical operator or an uppercase alphabetic character. Function symbols are used to name functions on the objects in the system being considered, and map an n-ary list to a single value f: U**N-->U. Examples are:
COLOR
Height
+1
SUM
Difference
LENGTH
TEMPERATURE
For each function is an associated "arity". For example the "Difference" function might map two arguments to the difference between the first and the second. The "LENGTH" function might take on only one argument and map to the argument to its length expressed in meters. Associative functions may take on any number of arguments, such as "SUM" which might evaluate to the arithmetic sum of a list of real numbers of an arbitrary number of elements.
A function maps N terms to a single value,
f: U**N-->UThe difference between a function constant and relation constant is how it is used in a logical sentence and the associated interpretation. A logical sentence starting with a relation constant forms a predicate which evaluates to either true or false, nothing else. A logical sentence starting to a function constant maps to the object which represents the "function" of the arguments and thus not to true or to false. This distinction will be made clearer with a formal definition of a "term" and a "predicate."
A term is a list of objects and is used to define more complex expressions for objects in the system being described. All object constants and variables are terms. In addition, any n-ary function constant "F" of n arguments, (T1, T2, . . . Tn) enclosed by parentheses is also a term:
(F (T1, T2, . . . Tn)).
Thus, unlike logical sentences that are always enclosed by parentheses, terms do not evaluate to True or False. For example, the following expressions are all legal terms:
COYOTE
JOHN
x
(SUM (x1 x2 x3 x4))
(HEIGHT JOHN)
Facts are stated in the form of declarative sentences called predicates, logical sentences or well-formulated formulas (wffs). There are three kinds of predicates:
• atomic
• logical
• quantified
An atomic sentence or atom is an expression consisting of an n-ary relation constant "R" and n terms, T1, T2, . . . Tn, enclosed within parentheses: (R T1, T2, . . . Tn). An atomic predicate should consist of at least 2 terms (one of which can be the relation constant). Predicates evaluate to either true or false.
Logical Sentences Are Either True or False
Examples in prefix notation are:
(R T1 T2 . . . TN)
(FRIEND ALICE DALE)
(SUBSET ANIMALS COYOTE)
Or in infix notation:
(T1 IS.RELATED.BY.R.TO T2 . . . IS.RELATED.BY.R.TO TN)
(ALICE IS.A.FRIEND.OF DALE)
(ANIMALS IS.A.SUBSET.OF COYOTE)
Logical operators are used to express negations, conjunctions, disjunctions and conditional statements involving objects. The only legitimate operators in PC are:
• AND
• OR
• NOT
• IF
Examples of proper use of these operators in prefix notation are as follows:
(NOT P1)
(NOT (SUBSET ANIMALS PLANTS))
(IF A B)
(OR (TEMP WATER 95ºF) (TEMP WATER 105ºF))
(AND (FRIEND MARY JANE) (FRIEND TOM ISHMAEL))
A predicate that begins with an AND or an OR operator can have any number of arguments.
(AND P1 P2 P3 . . . Pn) is true when all conjoined predicate are true. By convention a conjunction of no predicates is true.
(OR P1 P2 P3 . . . Pn) is true when any of the disjoined predicates are true. Note that more than one of the disjunctives may be true. By convention a disjunction of no predicates is false.
An expression that begins with the NOT operator can have only one argument. (NOT P1) means that the predicate P1 is false.
An expression that begins with the IF operator can have two and only two arguments: (IF P Q) meaning that P implies Q. By convention, this is true if the consequence Q is true when the antecedent P is true, or if the antecedent P is false.
With the syntax introduced so far, predicates can only reason about object constants, but not variables. Quantifiers allow us to introduce and quantify variables of interest. Two quantifiers are allowed:
• ALL (universal quantifier)
• EXIST (existential quantifier)
A universally quantified predicate of the form (ALL x1, x2, . . . Xn P) states that the predicate P is true for all possible values of the variables x1, x2, . . . Xn . By convention, if the ALL quantifier applies to all variables and is in the front of an outer predicate, it is implied and can be dropped. For example, the expression (ALL x P) can be replaced by (P).
The existentially quantified predicate of the form (EXIST x1, x2, . . . Xn P) states that the proposition P is true for some value of the variables x1, x2, . . . Xn . Examples are:
(EXIST x (AND (WOMAN x) (ENGINEER x))
(ALL x (IF (HUMAN x) (ANIMAL x)))
The scope of the quantifier in a quantified expression are the logical sentences embedded within the quantified expression. A variable that occurs within the scope of a quantified expression is said to be a bound variable. A variable that occurs as a term in a sentence without an enclosing quantifier (i.e., not within the scope of a quantified expression) is said to be a free variable relative to that quantifier). For example, all occurrences of the variable x are bound in both of the previous sentences within the scope of a quantified expressions.
As with atomic and logical expressions, quantified sentences can be combined to form complex sentences. Because quantified sentences can be used as terms in other sentences, a variable could be free in one occurrence of a large sentence and bound in another occurrence. For example, the variable x is free in the first term in the following sentence but bound in the second. Note that even though universal quantification is implied in the first expression, x is not considered bound unless the quantifier is explicit. Thus if the quantifier can be legally removed, the variables in such quantified expressions are also not bound. The rules for doing this, however, can be quite complex as will be discussed in the following chapters.
(OR (MAMMALS x) (EXIST x (REPTILE x)))
In complex sentences, the order of occurrence and nesting is extremely important. For example, consider the following two complex sentences P and Q involving component variables x and y. The relation CONNECTED evaluates to "true" if the two arguments in the sentence are connected together in a kinematic system.
P: (EXIST x (ALL y (CONNECTED x y)))
Q: (ALL y (EXIST x (CONNECTED x y)))
The sentence P states that there exists a component x such that it is connected to every component y in the system, including itself. The sentence Q, on the other hand, states that every component y is connected to at least one component in the system, but that this component could be itself. Sentence P is a very strong statement concerning the system: at least one component is connected to every other component in the system. Sentence Q is a much different statement and gives us little information concerning the system.
Only variables can be quantified in first-order predicate logic. In second-order logic, functions and relations can also be quantified. As the majority of AI systems rely on first-order predicate logic, or some subset thereof, this book will not cover second-order predicate logic.
1). If COLOR is a function (COLOR STRAWBERRY) is a legal term, but is not a predicate. However, the expression (COLOR STRAWBERRY RED) is an atomic predicate if COLOR is a relation.
2). Suppose you want to say that some apples are red and some are green. Is the following expression a legal predicate, where RED and GREEN are object constants standing for the color red and green, respectively?
(COLOR APPLE (OR RED GREEN))
The answer is no! Logical operators, AND, OR, IF, can only be used with predicates to form a new predicate. The intended meaning could legally expressed by the following expression:
(AND( EXISTS x (AND (APPLE x) (RED x)) (EXISTS x (AND (APPLE x) (GREEN x)))
1). Which of the following are legal terms or predicates. Justify your answer.
a). (IF APPLE RED)
b). (IF (APPLE x) (RED x))
c). (IF (TALL JOHN) (HEAVY JOHN))
d). (IF (TALL JOHN) (> (WEIGHT JOHN) 200))
e). (AND (Connected Bolt Plate) (Connected Bolt Plate Washer))
2). Represent each of the following sentences as prefix predicates:
a). Coyote is an Animal.
b). All classes are long and boring.
c). Some classes are long and boring.
d). This class is long but not boring.
f). This class is neither dull nor boring.
3). Represent the following "influence diagram" in the drawing below as prefix predicates. In influence diagrams, nodes represent states and arrows represent influences. Use the following relation: (INFLUENCE x y) states that x influences y.
APPENDIX
: Logic Symbol ConventionsIn reading reference textbooks in symbolic logic, you may be confused by the notation. The following is a translation from prefix to classical notation. In prefix PC these symbols are all used at the beginning of a sentence. In classical (or infix) notation, the
-->, OR, AND and NOT are often used between the relevant terms. The syntax of the other symbols is the same except, of course, for all the parentheses used in prefix PC which are not used in classical notation.
|
English |
Classical Notation |
Word Notation |
|
implication |
--> |
IF |
|
or |
OR |
OR |
|
and |
AND |
AND |
|
negation |
¬ or ~ |
NOT |
|
existence |
$ |
EXIST |
|
All |
" |
ALL |
For example:
|
Prefix Word Notation |
Infix Symbol Notation |
|
|
(IF A B) |
is equivalent to |
A --> B |
|
(OR A B) |
is equivalent to |
A OR B |
|
(AND A B) |
is equivalent to |
A AND B |
|
(NOT A) |
is equivalent to |
¬ A |
|
(EXIST x (A x)) |
is equivalent to |
$ x A(x) |
|
(ALL x (B x)) |
is equivalent to |
" x B(x) |
| [ Home | Info | Syllabus | Readings | Students | Homework | Resources | News | Chat] |
Last updated: 8 February 99