ME290M, Spring 1999, Week 4a

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

Week 4b

Semantic Interpretation and Truth

The syntax of prefix predicate calculus was presented in the previous lecture. This syntax, however, merely provides the structure, not the meaning, interpretation, or truthfulness of a sentence. In structuring a knowledge base in predicate calculus, it is important to assign meaning to the symbols (object, relation, and function) in the model of the system being described. The semantic interpretation provides the mapping between the symbols in the predicate calculus representation and the world that it models.

Semantics Provide the Interpretation of Symbols in predicate calculus

1 Semantic Interpretation

An interpretation is defined from the human modeler’s perspective over a set of objects W (world) and a function I (interpretation) acting on the symbols S for the objects in predicate calculus language, where the function I has the following properties [Genesereth and Nilsson 1987]:

1) The interpretation function I maps every object constant in predicate calculus representation into an element or class of elements of the set W.

I(x) Œ W {for x Œ S defined as an object constant}

2) The function I maps every function constant into an n-ary function from elements of Wn into elements of W.

I(F):Wn Æ W {for F defined as a n-ary function constant}

3) The function I maps every n-ary relation constant into an n-ary relation on the elements of W.

Wn … I(R) {for R defined as an n-ary relation}

For example, an interpretation for the object constant COYOTE might refer to an independent and clever animal found in western North America. The interpretation of the function constant PRESSURE might refer to the distribution of force over a surface area, expressed in pounds per square-inch. The interpretation of the relation constant FRIENDS might be the set of pairs of beings that have a close friendly relationship with each other.

2 Truth and Satisfaction of Logical Sentences

The truthfulness or satisfaction of a logical sentence depends on the logical operator involved and the interpretation of the objects. A rigorous mathematical representation for meaning and truth will not be discussed here. It will be assumed that the system modeler includes this in the assignment of symbols. If a sentence is satisfied then it evaluates to true. Given a set of assignments of variables and interpretations I, the satisfiability of logical sentences will depend on the logical operator involved:

NOT: 1) The negation of a sentence is satisfied if and only if the sentence itself is not satisfied. Thus given that sentence P1: (COLOR APPLE RED) is satisfied, then sentence P2: (NOT(COLOR APPLE RED)) is not satisfied.

IF: 2) An implication is satisfied if the consequent is satisfied whenever the antecedent is satisfied. Thus sentence P3: (IF P1 P2) is satisfied only if P2 is satisfied whenever P1 is satisfied. Or equivalently, if P2 is not satisfied, then P1 must not be satisfied. Thus an equivalent way of writing P3 is the disjunction: (OR (NOT P1) P2). An implication is considered to be true if the antecedent is always false as a matter of convention.

AND: 3) A conjunction of sentences is satisfied if and only if every conjunct is satisfied. For example, sentence P4: (AND P1 P2) is satisfied if and only if P1 and P2 are satisfied.

OR: 4) This is an "inclusive OR". A disjunction of sentences is satisfied if and only if at least one of the disjunctions is satisfied. Thus sentence p5: (OR P1 P2) is satisfied if either P1 or P2 (or both) are satisfied.

ALL: 5) A universally quantified sentence is satisfied if and only if the sentence is satisfied for every assignment of the variables in the argument list.

EXIST: 6) An existentially quantified sentence is satisfied if and only if the sentence is satisfied for at least one of the variables in the argument list.

2.1 Truth Tables

Boolean truth tables are useful in evaluating complex predicates made up of atoms and connectives.

2.2 Validity

A predicate is valid if and only if it is satisfied by every interpretation and variable assignment. Because a valid predicate is satisfied for every interpretation, it gives no information about the domain being described -- it is a tautology. For example the predicate (OR (NOT P) P) is valid but doesn't tell us anything about P. A set of predicate is valid if and only if every element is valid.

2.3 Satisfiability

The satisfiability of a predicate depends on the interpretation. A sentence is said to be satisfiable or consistent if and only if there is some interpretation and variable assignment that satisfy it. Otherwise it is unsatisfiable. or inconsistent. A set of sentences is satisfiable if and only if there is some interpretation and variable assignment that satisfies every element of the set. Otherwise the set is said to be inconsistent.

3 Exercises on Interpretation (Week4b Solutions)

For each of the following sentences, give interpretations to the symbols so that the sentence makes sense and represents the world accurately (i.e., so that you believe the sentence to be true).

(> 3 7)

(SHORTER ALICE (ETCHEVERRY-HALL))

(Ductile+ COPPER BRASS)

(EXIST something (AND (GOLD something) (NOT (GLITTER something))))

(EXIST something (AND (WANDER something) (NOT (LOST something))))

(IF (REPTILE x)(ANIMAL x))

(IF (R a b c) (R b c a))

(IF (NOT (P)) (NOT (Q)))

4 Exercises on Satisfaction and Validity (Week4b Solutions)

Say whether each of the following sentences is valid, satisfiable or unsatisfiable.

(IF P (NOT P))

(IF (NOT P) P)

(IF P P)

(AND (IF P (NOT P)) (IF (NOT P) P))

(AND (NOT P) P)

(OR (NOT P) P)

(IF P (IF Q P))

(OR (NOT P) (IF Q P))

5 Venn Diagrams as Graphical Representations of Predicate Calculus

Venn diagrams are graphical representations of objects in a world (or universe depending on your perspective) W. They can be used to represent portions of the space which are empty, unknown, or where at least one instance occurs. For example, consider the expression:

No A are B: In predicate calculus --> (IF (A x) (NOT (B x)))

This means that the space representing the occurrence of both A and B is empty (signified by black).

Venn diagrams can also be used to show existence. For example, consider the expression "Some B are C" or in predicate calculus:

(EXIST x (AND (B x) (C x)))

The existence of something is shown in the Venn diagram above by the dotted region.

6 Implication:

The diagram that represents the conjunction of two sentences can be used to test the consistency or truthfulness of a third. For example, given the previous two sentences, is this one consistent?

Some C are not A: (EXIST x (AND (C x) (NOT (A x))))

Is it implied?

7 Meaning and the Correct Use of AND and IF

Heuristic

More often than not, if a sentence is universally quantified (ALL) then you should begin the sentence with an IF, while if it is existentially quantified (EXIST) you should begin with an AND. For example:

All elements are isotopes: (IF (ELEMENT x) (ISOTOPE x))

Some Elements are Isotopes: (EXIST x (AND (ELEMENT x) (ISOTOPE x))))

Exception:

The major exception to this rule is the case where your sentence applies to everything. For example, the sentence "Everything is meaningless and pointless" refers to everything in the universe. This can be expressed in predicate calculus as:

(ALL x (AND (MEANINGLESS x) (POINTLESS x))).

8 References

S. Russell, The Compleat Guide to MRS, Report No. STAN-CS-85-1080, June 1985, Department of Computer Science, Stanford University, Stanford, CA 94305.

M.R. Genesereth and N.J. Nilsson, Logical Foundations of Artificial Intelligence, Morgan Kaufmann, 1987, pp. 22-28.

ME290MExpert Systems in Mechanical Engineering