1.

     Convert the following to clausal form.

x [ Roman(x)   know(x,Marcus)]  [hate(x,Caesar)  (y(z
hate(y,z))  thinkcrazy(x,y))]

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

There are 9 simple steps to convert from Predicate logic to clause form.

We will use the following example :

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

The well formed formula for this statement is :

x [ Roman(x)   know(x,Marcus)]  [hate(x,Caesar)  (y(z
hate(y,z))  thinkcrazy(x,y))]

Lets see each of the covnersion steps in detail :

Well formed formula [ wff] : x [ Roman(x) and

know(x,Marcus)]  [hate(x,Caesar)  (y(z hate(y,z))  think crazy(x,y))]
1. Eliminate 

We will eliminate implication [ ] by substituting it with its equivalent.

for e.g. a  b  =  ~a v b .
Here 'a' and 'b' can be any predicate logic expression.

For the above statement we get :

x ~[Roman(x)  know(x,Marcus)]  [hate(x,Caesar) (y~(z
hate(y,z))  thinkcrazy(x,y))]
2. Reduce the scope of ~
To reduce the scope we can use 3 rules :
~(~p) = p           
DeMorgans Laws :    ~(ab) = ~a~b
                                    ~(ab) = ~a~b
Applying this reduction on our example yields :
x[~Roman(x)~know(x,Marcus)][hate(x,Caesar)(yz
~hate(y,z)thinkcrazy(x,y))]
[Link] variable names such that, each quantifier has a unique name.
We do this in preparation for the next step. As variables are just dummy names, changing
a variable name doesnot affect the truth value of the wff.
Suppose we have
xP(x)  xQ(x) will be converted to  x(P(x)  yQ(y) 
[Link] all the quantifiers to the left of the formula without changing their relative
order.
As we already have unique names for each quantifier in the previous step, this will not
cause a problem.
Performing this on our example we get :
xyz
[ ~Roman(x)  ~know(x,Marcus)]  [ hate(x,Caesar)(~hate(y,z)thinkcrazy(x,y))]
5. Eliminate existential quantifiers [  ]
We can eliminate the existential quantifier by simply replacing the variable with a
reference to a function that produces the desired value.
for eg.
y President(y) can be transformed into the formula President(S1)
If the existential quantifiers occur within the scope of a universal wuantifier, then the
value that satisfies the predicate may depend on the values of the unviersally quantified
variables.
For eg..   xy fatherof(y,x) will be converted to  x fatherof( S2(x),x )
6. Drop the Prefix
As we have eliminated all existential quantifiers, all the variables present in the wff are
unversally quantified, hence for simplicity we can just drop the prefix, and assume that
every variable is universally quantified.
We have form our example :
[ ~Roman(x)  ~know(x,Marcus)]  [ hate(x,Caesar)(~hate(y,z)thinkcrazy(x,y))]
7. Convert into conjunction of disjuncts
As we have no ANDs we will just have to use the associative property to get rid of the
brackets.
Incase of ANDs we will need to use the distributive property.
We have :
 ~Roman(x)  ~know(x,Marcus)   hate(x,Caesar)  ~hate(y,z)  thinkcrazy(x,y)
8. Separate each conjunct into a new clause.
As we did not have ANDs in out example, this step is avoided for our example and the
final output of the conversion is :
 ~Roman(x)  ~know(x,Marcus)   hate(x,Caesar)  ~hate(y,z)  thinkcrazy(x,y)
 [Link] CHAINING
Forward chaining is one of the two main methods of reasoning when using an inference engine and can
be described logically as repeated application of modus ponens. Forward chaining is a popular
implementation strategy for expert systems, business and production rule systems. Forward chaining is
also known as data driven approach. Forward chaining starts with the facts and see what rules apply.

Facts are held in the working memory (ie., contains the current state of the world). Rules represent the
action to be taken when specified facts occur in the working memory. The actions involve adding or
deleting facts from the working memory.
Algorithm: Forward chaining
i) Collect the rules whose conditions match facts in working memory.
ii) If more than one rule matches then
(a) Use conflict resolution strategy to select the rules.
iii) Do the actions indicated by the rules. ie add facts to working memory or delete facts from working
memory.
iv) Repeat these steps until the goal is reached or no condition match found.\

Example
Rule R1: IF hot and smoky THEN fire
Rule R2: IF alarm_beeps THEN smoky

Rule R3: IF fire THEN switch_on_sprinklers

Fact F1: alarm_beeps (Given)

Fact F2: hot (Given)

Inference
Rule R1: IF hot and smoky THEN fire
Rule R2: IF alarm_beeps THEN smoky

Rule R3: IF fire THEN switch_on_sprinklers

Fact F1: alarm_beeps (Given)

Fact F2: hot (Given)
Fact F3: smoky
(Added) Fact
F4: fire (Added)
Fact F5: switch_on_sprinklers (Added)

Suppose that we know the facts A, B, C, D, E and the rules shown in the knowledge base to the left
What facts can we infer from this?

After inferring facts X, L, Y and Z there are no more rules that can be fired.

Properties of forward chaining

 All rules which can fire do fire.
 Can be inefficient, which lead to spurious rule firing, unfocussed problem solving.
 Set of rules that can fire known as conflict set.
 Decision about which rule to fire is conflict resolution.

[Link] CHAINING
This is also called goal driven approach. A desired goal is placed in working memory, inference
cycle attempts to find evidence to prove it.
The knowledge base (rule base) is searched for rules that might lead to goal. If condition of such rule
matches fact in working memory then rule is fired and goal is proved.
Backward chaining means reasoning from goals to facts. Rules and facts are processed using
backward chaining interpreter.
Algorithm: Backward Chaining
i) Prove goal G.
ii) if G is the initial fact, it is proven.
iii) Otherwise, find a rule which can be used to conclude G, and try to prove each of the rules conditions.
Example 1
Rule R1: IF hot and smoky THEN fire
Rule R2: IF alarm_beeps THEN smoky

Rule R3: IF fire THEN switch_on_sprinklers

Fact F1: alarm_beeps (Given)

Fact F2: hot (Given)

Goal: Should I switch_on_sprinklers

Suppose that we know the facts A, B, C, D, E and the rules shown in the knowledge base to the
left. Can we infer the fact Z?

Backward chaining inferred Z from the facts and rules that were available.
Advantages
 Most efficient to infer one particular fact.
 User may be asked to input additional facts
[Link] Clausal Form Problem
1. All people who are graduating are happy.
2. All happy people smile.
3. Someone is graduating.
4. Conclusion: Is someone smiling?

Convert the sentences into predicate Logic

1. ∀x graduating(x)happy(x)
2. ∀x happy(x)smile(x)
3. ∃x graduating(x)
4. ∃x smile(x)

Convert to clausal form

(i) Eliminate the  sign
1. ∀xgraduating(x) happy(x)
2. ∀xhappy(x) smile(x)
3. ∃x graduating(x)
4. ∃x smile(x)
Reduce the scope of negation
(ii)
1. ∀xgraduating(x) happy(x)
2. smile(x)
3. ∃x graduating(x)
4. ∀x  smile(x)
Standardize variables apart
(iii)
1. ∀xgraduating(x) happy(x)
2. ∀yhappy(y) smile(y)
3. ∃x graduating(z)
4. ∀w  smile(w)
Move all quantifiers to the left
(iv)
1. ∀xgraduating(x) happy(x)
2. ∀yhappy(y) smile(y)
3. ∃x graduating(z)
4. ∀w  smile(w)
(v)Eliminate ∃
1. ∀xgraduating(x) happy(x)
2. ∀xhappy(y) smile(y)
3. graduating(name1)
4. ∀w  smile(w)
Eliminate ∀
(vi)
1. graduating(x) happy(x)
2. happy(y) smile(y)
3. graduating(name1)
4.  smile(w)
 (vii) Convert to conjunct of disjuncts form.
(viii) Make each conjunct a separate clause.
(ix) Standardize variables apart again.
happy(y) smile(y)  smile(w)

graduating(x) happy(x) happy(y)

. graduating(name1) graduating(x)

None Thus, we proved someone is smiling.

[Link]
Resolution is a procedure used in proving that arguments which are expressible in predicate logic are
correct. Resolution is a procedure that produces proofs by refutation or contradiction. Resolution leads to
refute a theorem-proving technique for sentences in propositional logic and first order logic. Resolution is
a rule of inference. Resolution is a computerized theorem prover
Algorithm: Propositional Resolution
Let F be a set of axioms and P the theorem to prove.
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 pair 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.
Example 1
Converting a compound proposition to the clausal form
Consider the sentence
(AB) (CA)
1. Eliminate implication sign
(AB) (CA)
2. Eliminate the double negation and reduce scope of “not sign” (De-Morgans Law) (A B)
(CA)
3. Convert to conjunctive normal form by using distributive and associative laws
(AC A)  (BCA)
4. Get the set clauses (AC) (BCA)

[Link] ALGORITHM
When attempting to match 2 literals, all substitutions must be made to the entire literal. There
may be many substitutions that unify 2 literals, the most general unifier is always desired

1. Initial predicate symbols must match.

2. For each pair of predicate arguments:
– different constants cannot match.
– a variable may be replaced by a constant.
– a variable may be replaced by another variable.
– a variable may be replaced by a function as long as the function does not contain an instance of the
variable

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 the return {FAIL}, else return (L2/L1).
(c) Else if L2 is a variable, then if L2 occurs in L1 the return {FAIL}, else return (L1/L2).
(d) Else return {FAIL}
2. If the initial predicate symbols in L1 and L2 are not identical, the return {FAIL}.
3. If L1 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 ith 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.

Example
P(x) and P(y) :substitution = (x/y)
• P(x,x) and P(y,z) : (z/y)(y/x)
• P(x,f(y)) and P(Joe,z) : (Joe/x, f(y)/z)
• P(f(x)) and P(x) : can’t do it!
• P(x) Ú Q(Jane) and P(Bill)  Q(y): (Bill/x, Jane/y)