Logical Implication and Unification

Logical deduction and inference procedures are important to artificial intelligence because they allow the derivation of new knowledge from old knowledge. In fact, one can obtain an infinite number of facts from a relatively small data base of knowledge. The rules of inference define which rules can be added to the database. The following four rules are available for our disposal [Genesereth & Nilsson 1987]:

• Modus Ponens (MP) or "Law of Detachment"

• Modus Tollens (MT)

• AND Elimination (AE) or "Law of Simplification"

• AND Introduction (AI) or "Law of Conjunction"

In addition there are two rules for working with quantifiers:

• Universal Instantiation (UI)

• Existential Instantiation (EI)

The rules of inference will be written with the following notation:

<description of the initially known facts - conditions >

____________________________

<facts that can be inferred - conclusions >

1.1 Modus Ponens (MP)

(IF A B)

A

______

B

If A is true, and if A implies B, then B is true and can be added to the database. Roughly speaking, the Latin expression "modus ponens" means to add. Modus Ponens is sometimes called the Law of Detachment.

If B is not true, and if A implies B, then A is not true and (NOT A) can be added to the database. Roughly speaking, the Latin expression "modus tollens" means to take apart, in this case meaning A is deleted from the data base. It is the reverse of modus ponens.

1.3 And Elimination (AE) or Law of Simplification

(AND A1, A2, . . . An)

_______________

A1

A2

•

•

An

If all expressions in a conjunction are true, then any one is true. In this case, there are as many conclusions as there are expressions in the conjunction.

1.4 AND Introduction (AI) or Law of Conjunction

AI states that whenever a set of logical expressions is in the data base, their conjunction can also be included.

A1

A2

•

•

•

An

_______

(AND A1, A2, . . . An)

1.5 Universal Instantiation (UI)

allows us to reason from the general case to the specific.

(ALL x1, x2, . . . xn , P)

________________ where ß is free for x in P

P [ x1, x2, . . . xn/ ß]

UI states that whenever the data base contains a universally quantified logical sentence (ALL x P), it is acceptable to add a copy of P to the database with all occurrences of x replaced by an appropriate term or instantiation. Roughly speaking this says that if something is true for everything, then it is true for any particular thing. For example, if (ALL x (FRIEND JANE x) is true, then one can conclude that (FRIEND JANE GAIL) is also true. One interpretation might be that if everyone in the world is a friend of Jane, we can safely say that GAIL is a friend of Jane. A term or instantiation ß is free for a variable xi in P if and only if ß does not occur within the scope of any quantifier of the variable xi contained in P. The purpose of adding this condition is to avoid inappropriate substitutions. For example, it would be incorrect to substitute y for x in the following logical sentence: (ALL x (EXIST y (FRIEND x y))). However, this substitution is not allowed because y is not free for x [Genesereth & Nilsson 1987].

1.6 Existential Instantiation (EI)

(EXIST x P)

__________________ where F is a new function symbol and

P [ x/ (F (y1, y2, . . . yk))] y1, y2, . . . yk are free variables in P

EI states that whenever the data base contains a logical sentence of the form (EXIST x P), it is acceptable to add a copy of P in which all occurrences of x have been replaced by a term consisting of a new function F applied to the free variables in P. For example, if (EXISTS x (FRIEND x y)) is true, then one can conclude that there is a function (F y) such that (FRIEND (F y) y) is true. In this case, the function BESTFRIEND might be such a function F. Such functions are sometimes called skolem functions . Where there are no free variables, the variables can be replaced by a function with no arguments, i.e., by a constant that has not been used before in the system (called a skolem constant ) [Genesereth & Nilsson 1987].

2 Pattern Matching and Unification

In predicate logic, the matching process can be quite complicated because the binding of variables must be carefully considered. For example, it is clear that (ALL x (DENSER LEAD x)) and (ALL x (NOT (DENSER LEAD x))) together form a contradiction. However, (DENSER LEAD WATER) and (NOT (DENSER LEAD URANIUM)) do not form a contradiction. In order to determine contradictions, a pattern matching procedure is needed. A substitution is any finite set of mappings between variables and expressions such that (1) each variable is mapped to at most one expression and (2) no variable in one mapping expression occurs within any other mapping. For example in the following substitution, the variable 'x' is mapped to the constant 'A' and the variable 'y' to the term: (F z).

s = [x/A , y|(F z)]

Terms associated with the variables in a substitution (bound variables) are called bindings for those variables and the substitution the binding list. A substitution can be performed on a logical sentence to produce a new logical sentence by replacing all bound variables in the expression by their bindings. Variables without bindings remain unchanged. The new logical sentence is called a substitution instance.

Unification is such a procedure based on the incorporation of universal instantiation into the other rules of inference. The unification procedure compares two logical sentences and determines whether there exists a set of substitutions that can make them identical. If such a substitution exists, the two logical sentences are said to unify with each other. Consider the following unification procedure (with no recursion allowed) to be applied to two logical sentences:

STEP 1: If the first objects are the same ( i.e., if they consist of exactly the same lists of characters) and have the same number of arguments go to STEP 2, otherwise the logical sentences can not be unified.

STEP 2: Compare the next pair of objects. If they are constants and are identical ( i.e., if they consist of exactly the same lists of characters) then there is a pattern match and go to the next pair of objects and repeat STEP 2. If the pair of objects are constants and are not identical there is no pattern match and the logical sentences can not be unified. If the pair of objects are not both constants, go to STEP 3.

STEP 3: Find a substitution that will make the two objects unify after substitution. The substitution can replace any variable with a variable, term, or constant provided the following rules are satisfied:

The first step in the unification procedure is to guarantee that the logical sentences are parallel in meaning. For example, the following two logical sentences are not unifiable because they could express entirely different relationships:

(HEAVIER LEAD WATER)

(LIGHTER LEAD X)

The second step allows one to skip over object constants that are identical and are thus already unified.

The third step can be somewhat of an art. It helps to look at the entire set of necessary substitutions in order to be successful at picking one that will be consistent for the entire set. For example, consider the following two logical sentences:

(P (F y) x)

(P x (F A))

The resulting unified statement would read: (P (F A) (F A)).

More often than not, there will be many substitutions that will unify a set of logical sentences. Although the object of unification is to find any substitution that causes the two logical sentences to match, it is usually best to find the most general unifier (mgu) possible. Any most general unifier is unique up to variable renaming [Genesereth & Nilsson 1987]. Consider the following set of logical sentences:

P1: (P (F x) (G z))

P2: (P y x)

The following substitutions will all unify the logical sentences P1 and P2. However, the second substitution is more general than the other two and is, in fact, the most general unifier possible. The advantage of staying as general as possible in unification will become more obvious when we discuss search techniques and control strategies. However, it should be intuitive for theorem proving applications that the second unifier will be more powerful than the other two.

3 Exercises

1) Pattern Matching: Determine whether the second member of each of the following logical sentences matches the first. If so, give the appropriate substitution. If not, give the reason.

1. (BEARING RADIAL THRUST). (SUBSET x y)
2. (= (TIMES 4 4)) (= (TIMES 4 4) x)
3. (= (TIMES 4 4) x)(= (TIMES 2 2) x)
4. (SUBSET BEARING RADIAL)(SUBSET x y)

2) Unification Attempt to unify the following logical sentences. If unification is possible, what unifier was used? Is this the most general unifier for the set?

1. (P x) (P (R a))
2. (P r s r) (P (R b) s (R m))
3. (P (F x) y (G y)) (P (F x) z (G x))
4. (P w x w) (P A x x)
5. (NOT (P x y)) (P a b)
6. (FRIEND x y) (FRIEND y x)<
7. (P x y z) (P w u w)
8. (STRESS RADIAL x) (STRESS y TANGENTIAL)
9. (P a b) (R x y)
10. (STRESS RADIAL z) (STRESS x y)

3) Most General Unifier: Write a recursive procedure for computing the most general unifier of two expressions. If the expressions are unifiable, the procedure should return the most general unifier. Otherwise, it should return "nil".

4) Validity: Show that the following logical sentences are always valid (tautological) by using the truth tables introduced in Chapter 4. A sentence is valid if it has a truth value of "T" (true) under all possible combinations of truth and falsity of its component propositions.

5) Inconsistency: A logical sentence is inconsistent if it is false under all interpretations. Use truth tables to show which of the following are inconsistent.

6) Give a reasonable English interpretation for the logical sentence:

(ALL x (EXIST y (CONNECTED x y)))

7) Given the following rules concerning coyotes and roadrunners, prove that BEEP-BEEP (or BB for short) is faster than WILEY. First express each rule in prefix predicate calculus form and apply the rules of inference presented in this chapter. So that the class is consistent on the relation terms, use (HRR A) to mean A is a healthy roadrunner, (FASTER x y) to mean x is faster than y, (PDOG B) to mean B is a pedigree dog, (COYOTE C) means that C is a coyote, and (GH D) means that D is a greyhound dog. Solution.

1. Every healthy roadrunner can outrun any pedigree dog.

2. There are some greyhounds that can outrun any coyote.

3. BEEP-BEEP is a healthy roadrunner.

4. WILEY is a coyote.

5. A greyhound is a pedigree dog.

6. Transitivity of faster. (If A is faster than B, and B is faster than C, then A is faster than C.)

   ---

   [ Home | Info | Syllabus | Readings | Students | Homework | Resources | News | Chat]

   ---

   Last updated: 16 February 99
   Send Comments to: Alice Agogino, aagogino@me.berkeley.edu
   Copyright © 1999 Alice Agogino; All Rights Reserved.