FOPL and Prolog In AI part 04

Introduction

First Order Predicate Logic (FOPL) is a generalisation of Propositional Logic. Logic Programs are written in a sub-language of FOPL and therefore derive their meaning and formal properties from it.

FOPL has two major extensions over Propositional Logic:

1. Propositions are renamed "predicates" and may possess an internal structure. In fact the predicates of FOPL have precisely the same syntactic structure as they have in Prolog - i.e. a predicate name with terms as arguments, each term being aa

-constant,

-variable, or

-funcion with term(s) as argument(s).

2. Variables must be quantified by either

A meaning "for all" or

E " "there exists"

e.g Ex P(x) means "some unspecified constant has property P". Each quantifier has a SCOPE which is defined as the textual area in which it binds occurrences of its variable. This scope is usually delimited by brackets, unless it is obvious as in the example above.

These extensions critically extend the expressive power of logic. Consider the following sentences which are given a natural corresponding syntax in predicate calculus:

"John is the brother of Jim." brother_of(john,jim).

"Socrates is dead and buried." dead(socrates)&buried(socrates).

"All men are mortal." Ax (man(x) -> mortal(x)).

As an exercise try to express these in propositional logic!

Conversion of Prolog into FOPL:

Prolog clauses can be directly translated into FOPL, except for a few exceptions like write, !, is, assert, retract, ...

The three simple rules for conversion are:

- "," corresponds to "&"

- ":-" corresponds to "<-"

- All variables are universally quantified.

Examples

1. grandfather(X,Y) :- father(X,Z),parent(Z,Y).

In FOPL:

Ax,Ax,Az (grandfather(x,y) <- (father(x,z)&parent(z,y)))

2. uncle(X,Y) :- parent(Z,Y),brother(X,Z).

In FOPL:

Ax,Ay,Az ( uncle(x,y) <- (parent(z,y)&brother(x,z)))

3. member(X,[X|T]).

In FOPL:

Ax,Ay,At (member(x,[x|t]))

4. member(X,[Y|T]) :- member(X,T).

In FOPL:

Ax,Ay,At (member(x,[y|t]) <- member(x,t))

5. a :- b,c,d,e.

In FOPL:

a <- (b & c & d & e)

If we use the laws derived from the meaning of the logical connectives, we can simplify the expressions in 1, 2, 4, and 5:

1. AX,AY,AZ (grandfather(X,Y) <- (father(X,Z) & parent(Z,Y)) )

by "<-" simplification this becomes

= AX,AY,AZ (grandfather(X,Y) V ~(father(X,Z) & parent(Z,Y)) )

using "not" simplification this becomes

= AX,AY,AZ ( grandfather(X,Y) V ~father(X,Z) V ~parent(Z,Y) )

3. AX,AY,AT (member(X,[Y|T]) <- member(X,T))

by "<-" simplification this becomes

= AX,AY,AT (member(X,[Y|T]) V ~member(X,T))

4. AX,AY,AZ ( uncle(X,Y) <- (parent(Z,Y) & brother(X,Y)) )

by "<-" simplification this becomes

= AX,AY,AZ ( uncle(X,Y) V ~(parent(Z,Y) & brother(X,Y)) )

using "not" simplification this becomes

= AX,AY,AZ ( uncle(X,Y) V ~parent(Z,Y) V ~brother(X,Y) )

5. a <- (b & c & d & e)

by "<-" simplification and "not" simplification this becomes

= a V ~b V ~c V ~d V ~e

The following should be obvious from the examples:

Any Prolog clause which is translated into FOPL has exactly one positive (i.e. non-negated) predicate - originally the head of the Prolog clause.

Assignments

PREMISES 1

1. Horses, cows, pigs are mammals.

2. An offspring of a horse is a horse.

3. Bluebeard is a horse.

4. Bluebeard is Charlie’s parent.

5. Offspring and parent are inverse relations.

6. Every mammal has a parent.

QUERY

1. Is Charlie a horse?

PREMISES 2

2. every American who sells weapons to hostile nations is a criminal.

3. every enemy of America is a hostile.

4. iraq has some missiles.

5. all missiles of iraq were sold by george.

6. george is an American

7. iraq is a country.

8. iraq is the enemy of America.

9. missiles are weapons.

QUESTION

1. Is George a criminal ?

PREMISES 3

1. All pompeians are romans.

2. all romans were either loyal to Caesar or hated him.

3. everyone is loyal to someone.

4. people only try to assassinate rulers they are not loyal to.

5. marcus tried to assassinate Caesar.

6. marcus was Pompeian.

QUESTION

1. did marcus hate Caesar?

PREMISES 4

Bhogendra likes all kinds of food. Oranges are food. Chicken is food. Anything anyone eats and isn’t killed by is food. If a person likes a food means that person has eaten it. Jogendra eats peanuts and is still alive. Shailendra eats everything Bhogendra eats.

QUESTION

Does Shailendra like chicken.

PREMISES 5

Dave and Fred are members of a dancing club in which no member can both waltz and jive. Fred"s dad can"t waltz and Dave can do whatever fred can"t do. If a child can do something, then their parents can do it also.

PROVE that there is a member of the dancing club who can"t jive.