October 16, 2018
Introduction to Artificial Intelligence Lecture 13: Knowledge Representation & Reasoning II
1
Resolution
And yet Another Example:Resolving P Q R with P W Q Ron Q yields P R R W, which isTrue.on R yields P Q Q W, which is alsoTrue.You cannot resolve on Q and R simultaneously!Note:Anyset of wffscontaining and is unsatisfiable,i.e. if one wff is the negation of another wff in that set,it is impossible that all wffs in that set are true.Anyclausethat contains and has valueTrueregardless of the value of .
October 16, 2018
Introduction to Artificial Intelligence Lecture 13: Knowledge Representation & Reasoning II
2
Converting wffs to Conjunctions of Clauses
Resolution is a powerful tool for algorithmic inference, but we can only apply it toconjunctions of clauses(conjunctive normal form, CNF).So is there a way toconvertany wff into such a conjunction of clauses?Fortunately, there is such a way, allowing us to apply resolution toanywff.
October 16, 2018
Introduction to Artificial Intelligence Lecture 13: Knowledge Representation & Reasoning II
3
Converting wffs to Conjunctions of Clauses
Example:(P Q) (R P).Step 1:Eliminate implication operators:(P Q) (R P)Step 2:Reduce the scopes of operators by using DeMorgan’s laws and eliminating double operators:(P Q) (R P)Step 3:Convert to CNF by using the associative and distributive laws:(P R P) (Q R P), and then(P R) (Q R P)
October 16, 2018
Introduction to Artificial Intelligence Lecture 13: Knowledge Representation & Reasoning II
4
Resolution Refutations
Resolution is a sound rule of inference, but it isnot complete.For example, PR = PR, but the resolution rule does not allow us to infer PR from {P}, {R}.However, we can use resolution to show that thenegationof PR isinconsistentwith {P}, {R} and thereby showing that PR = PR.The negation of PR is P R.Conjunctively combining all clauses results inP R P R.This resolves to the empty set, so by contradiction we have indirectly shown that PR = PR.
October 16, 2018
Introduction to Artificial Intelligence Lecture 13: Knowledge Representation & Reasoning II
5
More Explanation ofResolutionRefutations
You have a set of hypotheses h1, h2, …,hn, and a conclusion c.Your argument is that whenever all of the h1, h2, …,hnare true, then c is true as well.In other words, whenever all of the h1, h2, …,hnare true, then c is false.If and only if the argument is valid, then the conjunction h1 h2 … hn c is false, because either (at least) one of the h1, h2, …,hnis false, or if they are all true, then c is false.Therefore, if this conjunction resolves to false, we have shown that the argument is valid.
October 16, 2018
Introduction to Artificial Intelligence Lecture 13: Knowledge Representation & Reasoning II
6
Resolution Refutations
The following statements about resolution refutation are true (see p. 234 for references to proof):Completenessof resolution refutation: For a set ofwffs and a wff , if = , then resolutionrefutation will produce the empty clause. Thismeans that propositional resolution isrefutationcomplete.Decidabilityof propositional calculus by resolutionrefutation: if is a finite set of clauses and if ,then resolution refutation willterminate withoutproducing theempty clause.
October 16, 2018
Introduction to Artificial Intelligence Lecture 13: Knowledge Representation & Reasoning II
7
Resolution Refutations
Example:“Gary is intelligent or a good actor.If Gary is intelligent, then he can countfrom 1 to 10.Gary can only count from 1 to 2.Therefore, Gary is a good actor.”Propositions:I: “Gary is intelligent.”A: “Gary is a good actor.”C: “Gary can count from 1 to 10.”
October 16, 2018
Introduction to Artificial Intelligence Lecture 13: Knowledge Representation & Reasoning II
8
Resolution Refutations
Hypotheses:I A, I C, CIn CNF: (I A)(I C)CConclusion:AConjunction of Clauses for Resolution Refutation:(I A)(I C)CA
October 16, 2018
Introduction to Artificial Intelligence Lecture 13: Knowledge Representation & Reasoning II
9
Resolution Refutations
(I A)(I C)CAResolution on A:I (I C)CResolution on I:CCResolution on C:FalseTherefore, the initial set of clauses is inconsistent, and the conclusion is correct:Gary is a good actor.
October 16, 2018
Introduction to Artificial Intelligence Lecture 13: Knowledge Representation & Reasoning II
10
Resolution Refutations
Another Example:“If Jim visits a pub on Thursday, he is late for work on Friday.If Jim is late for work on Friday, he has to work during the weekend.Jim had to work during the weekend.Therefore, Jim visited a pub on Thursday.”Propositions:T: “Jim visits a pub on Thursday.”F: “Jim is late for work on Friday.”W: “Jim has to work during the weekend.”
October 16, 2018
Introduction to Artificial Intelligence Lecture 13: Knowledge Representation & Reasoning II
11
Resolution Refutations
Hypotheses:T F, F W, WIn CNF: (T F)(F W)WConclusion:TConjunction of Clauses for Resolution Refutation:(T F)(F W)WT
October 16, 2018
Introduction to Artificial Intelligence Lecture 13: Knowledge Representation & Reasoning II
12
Resolution Refutations
(T F) (F W) W TResolution on F:(T W) W TSimplification:W TNo further resolution is possible.Therefore, the argument isinvalidand the conclusion that Jim went to a pub on Thursday isincorrect.(He could have been forced to work during the weekend for other reasons.)
October 16, 2018
Introduction to Artificial Intelligence Lecture 13: Knowledge Representation & Reasoning II
13
Propositional Calculus
You have seen that resolution, including resolution refutation, is a suitable tool forautomated reasoningin the propositional calculus.If we build a machine that represents its knowledge as propositions, we can use these mechanisms to enable the machine todeduce new knowledgefrom existing knowledge andverify hypothesesabout the world.However, propositional calculus has someserious restrictionsin its capability to represent knowledge.
October 16, 2018
Introduction to Artificial Intelligence Lecture 13: Knowledge Representation & Reasoning II
14
Propositional Calculus
In propositional calculus, atoms have no internal structure; wecannot reusethe same proposition for a different object, but each proposition always refers to the same object.For example, in the toy block world, the propositions ON_A_B and ON_A_C are completely different from each other.We could as well call them PETER and BOB instead.So if we want to express rules that apply to a wholeclassof objects, in propositional calculus we would have to define separate rules forevery single objectof that class.
October 16, 2018
Introduction to Artificial Intelligence Lecture 13: Knowledge Representation & Reasoning II
15
Predicate Calculus
So it is a better idea to usepredicatesinstead of propositions.This leads us topredicate calculus.Predicate calculus hassymbolscalledobject constants,relation constants, andfunction constantsThese symbols will be used to refer toobjectsin the world and topropositionsabout the word.
October 16, 2018
Introduction to Artificial Intelligence Lecture 13: Knowledge Representation & Reasoning II
16
Components
Object constants:Strings of alphanumeric characters beginning with either a capital letter or a numeral.Examples:XY, George, 154, H1BFunction constants:Strings of alphanumeric characters beginning with a lowercase letter and (sometimes) superscripted by their “arity”:Examples:fatherOf1, distanceBetween2
October 16, 2018
Introduction to Artificial Intelligence Lecture 13: Knowledge Representation & Reasoning II
17
Components
Relation constants:Strings of alphanumeric characters beginning with a capital letter and (sometimes) superscripted by their “arity”:Examples:BeatsUp2, Tired1Other symbols:Propositional connectives , , , and , delimiters(, ), [, ], and separator ,.
October 16, 2018
Introduction to Artificial Intelligence Lecture 13: Knowledge Representation & Reasoning II
18
Terms
An object constant is a term.A function constant of arity n, followed by n terms in parentheses and separated by commas, is a term.Examples:fatherOf(George), times(3, minus(5, 2))
October 16, 2018
Introduction to Artificial Intelligence Lecture 13: Knowledge Representation & Reasoning II
19
Wffs
Atoms:A relation constant of arity n followed by n terms in parentheses and separated by commas is an atom.An atom is a wff.Examples:Tired(John), OlderThan(Hans, Peter)Propositional wffs:Any expression formed out of predicate-calculus wffs in the same way that the propositional calculus forms wffs out of other wffs is a propositional wff.Example:OlderThan(John, Peter) OlderThan(Peter, Jennifer)
October 16, 2018
Introduction to Artificial Intelligence Lecture 13: Knowledge Representation & Reasoning II
20
Interpretations
Aninterpretationof an expression in the predicate calculus is an assignment that mapsobject constants into objects in the world,n-ary function constants into n-ary functions,n-ary relation constants into n-ary relations.These assignments are called thedenotationsof their corresponding predicate-calculus expressions.
October 16, 2018
Introduction to Artificial Intelligence Lecture 13: Knowledge Representation & Reasoning II
21
Interpretations
Example: Blocks world:
B
A
C
Predicate Calculus WorldA AB BC CFl FloorOn On = {<B,A>, <A,C>, <C, Floor>}Clear Clear = {<B>}
Floor
October 16, 2018
Introduction to Artificial Intelligence Lecture 13: Knowledge Representation & Reasoning II
22
Quantification
Introducing theuniversal quantifier and theexistential quantifier facilitates the translation of world knowledge into predicate calculus.Examples:All UMB Students are intelligent.x(UMBStudent(x) Intelligent(x))There is at least one intelligent UMB professor.x(UMBProf(x) Intelligent(x))
October 16, 2018
Introduction to Artificial Intelligence Lecture 13: Knowledge Representation & Reasoning II
23
Voluntary Homework!
a) There are no crazy UMB students.x (UMBStudent(x) Crazy(x))b) All computer scientists are either rich or crazy, but not both.c) All UMB students except one are intelligent.d) Jerry and Betty have the same friends.e) No mouse is bigger than an elephant.
0
Embed
Upload