## Session 11

### Inference in Predicate Logic

#### Artificial Intelligence

today's slides in PDF

### A Refresher Exercise, Part 1

Write predicate logic sentences for each of these facts:

• Joe, Sally, Bill, and Ellen are members of the Elm St. Bridge Club.

• Sally is married to Joe.

• Bill is Ellen's brother.

• The spouse of every married person in the club is also in the club.

• The last meeting of the club was at Joe's house.

Let's build a possible solution. What objects do we need? I figure at least Joe, Sally, Bill, Ellen, ElmStBridgeClub, and JoesHouse. These are the objects in the world that we need to represent if we are to represent the facts given. In logic terms, the symbols that refer to objects are often called atoms.

Okay, what predicates do we need? I found these:

• member( member, organization )
• married( spouse1, spouse2 )
• brother( person, theBrother )
• lastMeetingAt( organization, location )

These are the relationships in the world that we need to represent if we are to represent the facts given. In logic terms, the predicates are often called relations, which recognizes that they define relationships.

I also decided to use a new kind of object, one computed by a function. If I represent JoesHouse as an atom, then I may have to create many, many atoms for peoples' houses. Given that each person typically has one house, at least one primary residence, I can imagine have a function named houseOf(x) that gives me the house of x. houseOf( Joe ) is different from the relation house( Joe, JoesHouse ) in at least two ways: (1) in the latter, I still need a symbol for Joe's house, and (2), because houseOf( Joe ) is an object, I can use it as a part of other predicates.

Now, I think I am ready to write my sentences:

1. memberOf( Joe, ElmStBridgeClub )
memberOf( Sally, ElmStBridgeClub )
memberOf( Bill, ElmStBridgeClub )
memberOf( Ellen, ElmStBridgeClub )

2. married( Sally, Joe )

3. brother( Ellen, Bill )

4. forall m, s [ married( s, m ) and memberOf( m, ElmStBridgeClub ) ] implies ( s, ElmStBridgeClub )

5. lastMeetingAt( ElmStBridgeClub, houseOf(Joe) )

### A Refresher Exercise, Part 2

Given the facts above, derive the following statements:

• The last meeting of the club was at Sally's house.

• Ellen is not married.

Feel free to define any commonsense axioms that you need in order to do your derivations.

Okay, what commonsense knowledge do we need? I found the following:

• forall x, y, married( x, y ) implies married( y, x )
• forall x, y, married( x, y ) implies houseOf( x ) = houseOf( y )
• forall x, y, married( x, y ) implies not brother( x, y )
forall x, y, married( x, y ) implies not brother( y, x )
• forall x, y, z, married( x, y ) implies not married( y, z )

There are, of course, many other facts that we could write down about married couples and homes and siblings and ..., but these are the ones that came to mind as I tried to solve the problem.

Now, I think I am ready to do my derivations:

1. ...

2. ...

### Where Are We?

We are exploring predicate logic with modus ponens as an inference rule.

• As a representation, logic gives a nice formal language in which to encode facts we believe to be true. Predicate logic allows us to represent a wide variety of facts about the world.

• As a reasoning mechanism, modus ponens lets us derive new facts in a straightforward, if cumbersome, way.

Using an inference rule to derive facts is a lot like using an operator to generate possible future states from some state of the world.

In such a formulation, states are sets of sentences that describe a world, and an inference rule is an operator that allows you to generate possible future states consisting of one more fact each.

So, we can evaluate an inference rule in much the same way as we would a search strategy.

Modus ponens is:

• ... complete? Yes.
• ... optimal? It depends.
• ... time-efficient? It depends, but ....
• ... space-efficient? It depends, but ....

Another interesting feature of logic is soundness. A sound inference rule derives only sentences that follow from the facts in the database. That is, if all sentences in a knowledge base are true, then it generates only true sentences.

Modus ponens is sound.

### Wrap Up

• Homework -- Homework 2 is available now and is due on Friday.

• Paper -- Don't forget the next milestone for your paper...

• Exam -- Our first midterm exam is a week from next Tuesday, October 16. You will have the Thursday of that week, October 18, off. Use that time to work on your paper.

Eugene Wallingford ==== wallingf@cs.uni.edu ==== October 9, 2001