Module 2:

Using Predicate Logics

Representing Simple Facts in Logic:

Representing the propositional logic is easy because it is simple to deal with and a decision
procedure for it exists.

A Predicate Logic Example

1. Marcus was a man.

2. Marcus was a Pompeian.
3. All Pompeian were Romans.
4. Caesar was a ruler.
5. All Romans were either loyal to Caesar or hated him.
6. Everyone is loyal to someone.
7. People only try to assassinate rulers they are not loyal to.
8. Marcus tried to assassinate Caesar.
An Attempt to Prove
Representing Instance and ISA relationships

Computable Functions and Predicates:

1. Marcus was a man.

2. Marcus was a Pompeian.
3. Marcus was born in 40 A.D.
4. All men are mortal.
5. All Pompeians died when the volcano erupted in 79 A.D.
6. No mortal lives longer than 150 years.
7. It is now 1991.
8. Alive means not dead.
 9. If someone dies, then he is dead at all later times.

One Way of Proving That Marcus Is Dead

Resolution:

Conversion to Clause Form

Problem :

All Romans who know Marcus either hate Caesar or think that anyone who hates anyone is
crazy.

This can be represented as:

Solution:

 Flatter: There are less embedding of components.

 The quantifiers are separated from the rest of the formula so that they need not to
be considered.

Conjunctive Normal Form: Has both of these properties.

The above formula can be represented as follows:

Algorithm: Convert to Clause Form

Examples of Conversion to Clause Form

Example:

1. Eliminate "

2. Reduce scope of
3. Standardize Variables.

4. Move quantifiers.

5. Eliminate existential quantifiers.

6. Drop the prefix.

7. Convert to a conjunction of disjuncts.

Examples of Conversion to Clause Form

The Formula

becomes

and then becomes

The Basis of Resolution:

Resolution procedure is a simple iterative process: at each step, two clauses, called the parent clauses,
are compared (resolved), yielding a new clause that has been inferred from them.

Suppose there are two clauses in the system:

This means that both clauses must be true. One of winter and winter will be true at any point. If
winter is true, then cold must be true to guarantee the truth of the second clause. If winter is true,
then summer must be true to guarantee the truth of the first clause. From these two clauses we can
deduce

Herbrand’s Theorem
  To show that a set of clauses S is unsatisfiable, it is necessary to consider only
interpretations over a particular set, called the Herbrand universe of S.
 A set of clauses S is unsatisfiable if and only if a finite subset of ground instances (in
which all bound variables have had a value substituted for them) of S is unsatisfiable.

Resolution in Propositional Logic

In propositional logic, the procedure for producing a proof by resolution of proposition P with respect to
a set of axioms F in the following:

Algorithm: Propositional Resolution

1. Convert all the propositions of F to clause form.

2. Negate P and convert the result to clause form. Add it to the set of clauses obtained in step 1.

3. Repeat until either a contradiction is found or no progress can be made:

(a) Select two clauses. Call these the parent clauses.

(b) Resolve them together. The resulting clause, called the resolvent, will be the disjunction of all of the
literals of both of the parent clauses with the following exception: If there are any pairs of literals L and
¬L such that one of the parent clauses contains L and the other contains ¬L, then select one such pair
and eliminate both L and ¬L from the resolvent.

(c) If the resolvent is the empty clause, then a contradiction has been found. If it is not, then add it to
the set of clauses available to the procedure.

A Few Facts in Propositional Logic

Unification:

In propositional logic, it is easy to determine that two literals cannot be true at the same time.
Finding General Substitutions

Given :

We could produce:

Algorithm : Unify (L1, L2)

1. If L1 or L2 are both variables or constants, then:

(a) If L1 and L2 are identical, then return NIL.

(b) Else if L1 is a variable, then if L1 occurs in L2 then return {FAIL}, else return (L2/L1).

(c) Else if L2 is a variable then if L2 occurs in L1 then return {FAIL}, else return (L1/L2).

(d) Else return {FAIL}.

2. If the initial predicate symbols in L1 and L2 are not identical, then return {FAIL).

3. If LI and L2 have a different number of arguments, then return {FAIL}.

4. Set SUBST to NIL.

5. For i ← 1 to number of arguments in L1:

(a) Call Unify with the /th argument of L1 and the ith argument of L2, putting result in S.

(b) If S contains FAIL then return {FAIL}.

(c) If S is not equal to NIL then:

(i) Apply S to the remainder of both L1 and L2.

(ii) SUBST : = APPEND(S, SUBST).

6. Return SUBST.

Resolution in Predicate Logic

Algorithm : Resolution

1. Convert all the statements of F to clause form.

2. Negate P and convert the result to clause form. Add it to the set of clauses obtained in 1.

3. Repeat until either a contradiction is found, no progress can be made, or a predetermined amount of
effort has been expended.

(a) Select two clauses. Call these the parent clauses.

(b) Resolve them together. The resolvent will be the disjunction of all the literals of both parent
clauses with appropriate substitutions performed and with the following exception: If there is
one pair of literals T1 and ¬T2 such that one of the parent clauses contains T2 and the other
contains T1 and if T1 and T2 are unifiable, then neither T1 nor T2 should appear in the resolvent.
If there is more than one pair of complimentary literals, only one pair should be omitted from
the resolvent.

(c) If the resolvent is the empty clause, then a contradiction has been found. If it is not, then add it
to the set of clauses available to the procedure.

A Resolution Proof
MODULE 2: Chapter 6: Representing Knowledge using Rules.
Procedural versus Declarative Knowledge

A declarative representation is one in which knowledge is specified, but the use to which that
knowledge is to be put is not given. To use declarative representation, the program should be
specified with what is to be done with the knowledge and how.

A procedural representation is one in which the control information that is necessary to use the
knowledge is considered to be embedded in the knowledge itself.

To use a procedural representation, we need to augment it with aninterpreter that follows the
instructions given in the knowledge.

The difference between the declarative and the procedural views of knowledge lies in where
control information resides.

Consider the knowledge base :

Suppose we want to answer the question

We could answer with any one of :

Now consider an alternative KB :

Logic Programming:
Logic programming is a programming language paradigm in whichlogical assertions are viewed
as programs, e.g : PROLOG

A PROLOG program is described as a series of logical assertions, eachof which is a

Horn Clause.

A Horn Clause is a clause that has at most one positive literal.

Eg p, ¬ p V q etc are also Horn Clauses.

The fact that PROLOG programs are composed only of Horn Clauses and not of arbitrary logical
expressions has two important consequences.

Because of uniform representation a simple & effective interpreter can be written.

The logic of Horn Clause systems is decidable.

A PROLOG program is composed of a set of Horn clauses. A Horn Clause is a clause that has at
most one positive literal.

Examples :

A Declarative and a Procedural Representation:

There are several superficial, syntactic differences between the logic and the PROLOG
representations, including:
 1. In logic, variables are explicitly quantifies. In PROLOG, quantification is provided
implicitly by the way the variables are interpreted.
2. In logic, there are explicit symbols for and (^) and or (V). In PROLOG, there is explicit
symbol for and (,), but there is none for or.
3. In logic, implications of the form “p implies q” are written as p -> q. In PROLOG, the
same implication is written “backward ”, as q: - p.

Forward v/s Backward Reasoning

 The objective of any search is to find a path through a problem spacefrom the initial to
the final one.
A Sample of the Rules for Solving the 8-Puzzle

An Examples :

Start Goal

 There are 2 directions to go and find the answer

Forward

Backward

 8-square problem

 Reason forward from the initial states: Begin building a tree of

movesequences that might be solution by starting with the initialconfiguration(s) at the
 root of the tree. Generate the next level of tree by finding all the rules whose left sides
match the root node and use the right sides to create the new configurations. Generate
each node by taking each node generated at the previous level and applying to it all of the
rules whose left sides match it.

 Reason backward from the goal states:

Begin building a tree of move sequences that might be solution by starting with the goal
configuration(s) at the root of the tree. Generate the next level of tree by finding all the
rules whose right sides match the root node and use the left sides to create the new
configurations. Generate each node by taking each node generated at the previous level
and applying to it all of the rules whose right sides match it.
This is also called Goal-Directed Reasoning.
 To summarize, to reason forward, the left sides (pre conditions) are matched against the
current state and the right sides (the results) are used to generate new nodes until the goal
is reached.

 To reason backwards, the right sides are matched against the current node and the left
sides are used to generate new nodes.
.

Factors that influence whether to choose forward or backward reasoning :

 Are there more possible start states or goal states? We would like to go from smaller set
of states to larger set of states.

 In which direction is the branching factor (the average number of nodes that can be
reached directly from a single node) greater? We would like to proceed in the direction
with the lower branching factor.

 Will the program be asked to justify its reasoning process to the user? It so, it is important
to proceed in the direction that corresponds more closely with the way user will think.

 What kind of event is going to trigger a problem-solving episode? If it is the arrival of a

new fact, forward reasoning should be used. If it a query to which response is desired, use
backward reasoning.

Forward Rules: which encode knowledge about how to respond tocertain input configurations.

Backward Rules: which encode knowledge about how to achieveparticular goals.

Backward- Chaining Rule Systems

 PROLOG is an example of this.

 These are good for goal-directed problem solving.
 Hence Prolog & MYCIN are examples of the same.
Forward - Chaining Rule Systems
 The left sides of rules are matched with against the state description.
 The rules that match the state dump their right side assertions into the state.
 Matching is more complex for forward chaining systems.
 OPS5, Brownston etc. are the examples of the same.

Matching

 Till now we have used search to solve the problems as the application of appropriate
rules.

 We applied them to individual problem states to generate new states to which the rules
can then be applied, until a solution is found.

 We suggest that a clever search involves choosing from among the rules that can be
applied at a particular point, but we do not talk about how to extract from the entire
collection of rules those that can be applied at a given point.

To do this we need matching.

Indexing

Do a simple search through all the rules, comparing eachone’s precondition to the current state
and extracting all the ones that match. But this has two problems

In order to solve very interesting problems , it will be necessary to use a large number of rules,
scanning through all of them at every step of the search would be hopelessly inefficient.

It is not always immediately obvious whether a rule’s preconditions are satisfied by a particular
state.

To solve the first problem, use simple indexing. Eg. In Chess, combine all moves at a particular
board state together.
Matching with Variables

 The problem of selecting applicable rules is made more difficult when preconditions are
not stated as exact descriptions of particular situations but rather describe properties that
the situations must have.

 Then we need to match a particular situation and the preconditions of a given situation.

 In many rules based systems, we need to compute the whole set of rules
that match the current state description. Backward Chaining Systems usually use depth-
first backtracking to select individual rules, but forward chaining systems use Conflict
Resolution Strategies.

 One efficient many to many match algorithm is RETE

Complex &Approximate Matching

 A more complex matching process is required when the preconditions
of a rule specify required properties that are not stated explicitly in thedescription of the
current state. In this case, a separate set of rules must be used to describe how some
properties can be inferred from others.

 An even more complex matching process is required if rules should be applied if their
preconditions approximately match the current situation. Example of listening to a
recording of a telephonic conversation.
 For some problems, almost all the action is in the matching of the
rulesto the problem state. Once that is done, so few rules apply that theremaining search
is trivial. Example ELIZA
Conflict Resolution

The result of the matching process is a list of rules whose antecedents have matched the current
state description along with whatever variable binding were generated by the matching process.

It is the job of the search method to decide on the order in which the rules will be applied. But
sometimes it is useful to incorporate some of the decision making into the matching process.
This phase is called conflict resolution.

There are three basic approaches to the problem of conflict resolution in the production system

Assign a preference based on the rule that matched.

Assign a preference based on the objects that matched.

Assign a preference based on the action that the matched rule would perform.