2 Logic and Reasoning(逻辑及其推理)

1、Lecture 2 Logic and reasoning第2讲 逻辑及其推理2.1 Propositional Logic 命题逻辑2.2 Predicate Calculus 谓词逻辑2A/latombe/cs121/2003/home.htm补充读物：补充读物：Nils J. Nilsson著著, 郑扣根郑扣根 庄越挺译庄越挺译 Artificial Intelligence A New Synthesis 机械工业机械工业出版社出版社 2000 (中南大学图书馆中南大学图书馆 TP18 NES)3environmen

2、tagent?sensorsactuatorsKnowledge base4v Procedural(过程性的), e.g.: functions Such knowledge can only be used in one way - by executing itv Declarative(描述性的，说明性的), e.g.: constraints It can be used to perform many different sorts of inferences5Logic is a declarative language to:v Assert sentences represe

3、nting facts that hold in a world W (these sentences are given the value true)v Deduce the true/false values to sentences representing other aspects of W6 World WConceptualizationFacts about WholdholdSentencesrepresentFacts about WrepresentSentencesEntail 涵蕴71. 如果电池正常 且车灯正常， 那么车灯亮2. 如果电池正常，启动器正常且油箱不空

4、，那么引擎可以发动3. 如果引擎可以发动，且轮胎没有爆胎，那么汽车正常4. 车灯亮 5. 电池正常 6.启动器正常 7. 油箱不空 8. 汽车不正常World WConceptualization1 Battery-OK Bulbs-OK Headlights-Work2 Battery-OK Starter-OK Empty-Gas-Tank Engine-Starts3 Engine-Starts Flat-Tire Car-OK4 Headlights-Work5 Battery-OK6 Starter-OK 7 Empty-Gas-Tank 8 Car-OK 诊断结论：轮胎爆胎 Fla

5、t-Tire8Propositional logic: SyntaxvPropositional logic is the simplest logic illustrates basic ideasvThe proposition symbols P1, P2 etc are sentencesvIf S is a sentence, S is a sentence (negation)vIf S1 and S2 are sentences, S1 S2 is a sentence (conjunction)vIf S1 and S2 are sentences, S1 S2 is a se

6、ntence (disjunction)vIf S1 and S2 are sentences, S1 S2 is a sentence (implication)vIf S1 and S2 are sentences, S1 S2 is a sentence (biconditional)9Propositional logic: SemanticsEach model specifies true/false for each proposition symbolE.g. P1,2 P2,2 P3,1 falsetruefalseWith these symbols, 8 possible

7、 models, can be enumerated automatically.Rules for evaluating truth with respect to a model m:Sis true iff S is false S1 S2 is true iff S1 is true and S2 is trueS1 S2 is true iff S1is true or S2 is trueS1 S2 is true iffS1 is false orS2 is true i.e., is false iffS1 is true andS2 is falseS1 S2is true

8、iffS1S2 is true andS2S1 is true10vAssignment of a truth value true or false to every atomic sentencevExamples:vLet A, B, C, and D be the propositional symbolsvm = A=true, B=false, C=false, D=true is a modelvm = A=true, B=false, C=false is not a modelvWith n propositional symbols, one can define 2n m

9、odels11v Let KB be a set of sentencesv A model m is a model of KB iff it is a model of all sentences in KB, that is, all sentences in KB are true in mvGiven a vocabulary A, B, C and D, how many models for AB C are there? vfor AB B? 12AB C v AB C有多少模型vAB C， AB有多少模型13A KB is satisfiable iff it admits(

10、接纳) at least one model; otherwise it is unsatisfiableKB1 = P, Q R is satisfiableKB2 = P P is satisfiableKB3 = P, P is unsatisfiablevalid sentenceor tautology14v KB : set of sentences （知识库）v : arbitrary sentence v KB entails written KB iff every model of KB is also a model of v Alternatively, KB iff

11、vKB, is unsatisfiable (不可满足的)vKB is valid （永真的）15AB C v 令KB= AB C， ABv = Cv有KB 16Validity(永真性) and satisfiability(可满足性)A sentence is valid if it is true in all models,e.g., True,A A, A A, (A (A B) BValidity is connected to inference via the Deduction Theorem: （演绎定理）KB if and only if (KB ) is validA

12、sentence is satisfiable if it is true in some modele.g., A B, CA sentence is unsatisfiable if it is true in no modelse.g., AASatisfiability is connected to inference via the following:KB if and only if (KB ) is unsatisfiable17v I: Set of inference rulesv KB: Set of sentencesv Inference is the proces

13、s of applying successive inference rules from I to KB, each rule adding its conclusion to KB （推理 就是不断将I中的规则应用到KB，并将其结论加入到KB中的过程。）18 v Given:vKB: a set of sentencev: a sentencev Answer:vKB ?19v An inference rule , consists of 2 sentence patterns and called the conditions and one sentence pattern call

14、ed the conclusionv If and match two sentences of KB then the corresponding can be inferred according to the rule 20Example: Battery-OK Bulbs-OK Headlights-WorkBattery-OK Bulbs-OKHeadlights-Work , , 21Sound Inference Rules (deductive rules)vHere are some examples of sound rules of inference. vEach ca

15、n be shown to be sound using a truth table - a rule is sound if its conclusion is true whenever the premise is true.RULEPREMISECONCLUSIONModus Ponens（肯定前件） A, A = BBModus Tollens （否定后件） B, A = BAAnd IntroductionA, BA BAnd EliminationA BAOr Introduction A A v BDouble NegationAAChainingA = B, B = CA =

16、 C22 Connective symbol (implication 蕴含蕴含) Logical entailment（逻辑涵蕴）（逻辑涵蕴） Inference（推理）（推理） KB iff KB is valid23v An inference rule is sound if it generates only entailed sentences （如果一个推理规则只推出蕴含的句子，则为可靠的）v All inference rules previously given are sound, e.g.:modus ponens: , v The following rule: , i

17、s unsound, which does not mean it is useless （溯因推理，abduction） 24vA set of inference rules is complete if every entailed sentences can be obtained by applying some finite succession of these rules （所有的被蕴含的句子都可被推出，则该规则集为完备的）vModus ponens alone is not complete, e.g.:from A B and B, we cannot get A25vUs

18、e inference rules: generate new sentences X from a one or more existing sentences S. S is called the premise and X the conclusion of the rule.vProof procedure: a set of inference rules and a procedure of how to use these rulesvIf X can be generated from S by proof procedure i, we say X is derived fr

19、om S by i, denoted S |i X, or S | X.vSoundness. An inference procedure is sound if every sentence X it produces from a set of sentences S logically follows from S. (No contradiction is created).if S | X then S |= XvCompleteness. A inference procedure is complete, if it is able to produce every sente

20、nce that logically follows from any give S.if S |= X then S | X26Proof methodsvProof methods divide into (roughly) two kinds:vApplication of inference rulesvLegitimate (sound) generation of new sentences from oldvProof = a sequence of inference rule applicationsCan use inference rules as operators i

21、n a standard search algorithmvTypically require transformation of sentences into a normal formvModel checkingvtruth table enumeration (always exponential in n)vimproved backtracking, e.g., Davis-Putnam-Logemann-Loveland (DPLL)vheuristic search in model space (sound but incomplete)e.g., min-conflicts

22、-like hill-climbing algorithms27The proof of a sentence from a set of sentences KB is the derivation of by applying a series of sound inference rules 28The proof of a sentence from a set of sentences KB is the derivation of by applying a series of sound inference rules wBattery-OK Bulbs-OK Headlight

23、s-WorkwBattery-OK Starter-OK Empty-Gas-Tank Engine-StartswEngine-Starts Flat-Tire Car-OKwHeadlights-WorkwBattery-OKwStarter-OK wEmpty-Gas-Tank wCar-OK wBattery-OK Starter-OK (5+6)wBattery-OK Starter-OK Empty-Gas-Tank (9+7)wEngine-Starts (2+10)wEngine-Starts Flat-Tire (3+8)wFlat-Tire (11+12)2930vA li

24、teral is a either an atomic sentence or the negated atomic sentence, e.g.: P or PvTwo literals are complementary if one is the negation of the other, e.g.: P and P31Normal forms of PL sentencesvDisjunctive normal form (DNF)vAny sentence can be written as a disjunction of conjunctions of literals. vE

25、xamples: P Q R; AB v CD v PQR; PvWidely used in logical circuit design (simplification)vConjunctive normal form (CNF)vAny sentence can be written as a conjunction of disjunctions of literals.vExamples: P v Q v R; (A v B) (C v D) (P v Q v R); PvNormal forms can be obtained by applying equivalence law

26、s (A v B) = (C v D) = P (A v B) v (C v D) v P / law for implication (A v B) (C v D) v P / de Morgans law (A v B)(C D) v P / double negation and de Morgans law (A v B v P)(CD v P) / distribution law (A v B v P)(C v P)(D v P) / a CNF32vGiven two sentences: L1 Lp and M where Li, Lp and M are all litera

27、ls, and M and Li are complementary literalsvInfer: L1 Li-1 Li+1 Lp 33From: Engine-Starts Car-OKEngine-StartsInfer:Car-OKFrom: Engine-Starts Car-OK Car-OKInfer: Engine-StartsModus ponensModus tolensEngine-Starts Car-OK34From:wEngine-Starts Flat-Tire Car-OKwEngine-Starts Empty-Gas-Tankwe can infer not

28、hing!35vResolution ruleUnit Resolution A v B, ABResolution A v B, B v CA v C vOperates on two disjunctions of literalsvThe pair of two opposite literals cancel each other, all other literals from the two disjuncts are combined to form a new disjunct as the inferred sentencevResolution rule can repla

29、ce the following inference rules Modus PonensA, A v B B Modus Tollens B, A v B A Chaining A v B, B v C A v C) and (36vGiven two sentences: L1 Lp and M1 Mq where L1, Lp, M1, Mq are all literals, and Li and Mj are complementary literalsvInfer: L1 Li-1 Li+1 Lk M1 Mj-1 Mj+1 Mk in which only one copy of

30、each literal is retained (factoring) 37From:Engine-Starts Flat-Tire Car-OKEngine-Starts Empty-Gas-TankInfer:Empty-Gas-Tank Flat-Tire Car-OK38A A v B (利用消解规则推导不出)3940KB iff KB, is unsatisfiable Hence: Deciding whether a set of sentences entails another sentence, or not Testing whether a set of senten

31、ces is satisfiable, or not are closely related problems41Example: (A B) (C D)1. Eliminate (A B) (C D)2. Reduce scope of (A B) (C D)3. Distribute over (A (C D) (B (C D)(A C) (A D) (B C) (B D)Set of clauses:A C , A D , B C , B D42RESOLUTION-REFUTATION(KB, )clauses set of clauses obtained from KB and R

32、epeat: new For each C, C in clauses dores RESOLVE(C,C)If res contains the empty clause then return yesnew new U resIf new clauses then return noclauses clauses U new431 Battery-OK Bulbs-OK Headlights-Work2 Battery-OK Starter-OK Empty-Gas-Tank Engine-Starts3 Engine-Starts Flat-Tire Car-OK4 Headlights

33、-Work5 Battery-OK6 Starter-OK 7 Empty-Gas-Tank 8 Car-OK 445 2Starter-OK Empty-Gas-Tank Engine-Starts 6Empty-Gas-Tank Engine-StartsEngine-Starts 7 3Flat-Tire Car-OK 8Flat-TireFlat-TireNIL (矛盾)1 Battery-OK Bulbs-OK Headlights-Work2 Battery-OK Starter-OK Empty-Gas-Tank Engine-Starts3 Engine-Starts Flat

34、-Tire Car-OK4 Headlights-Work5 Battery-OK6 Starter-OK 7 Empty-Gas-Tank 8 Car-OK 45Summaryv命题逻辑：语法、语义命题逻辑：语法、语义v模型，可满足，逻辑涵蕴模型，可满足，逻辑涵蕴v推理，推理， 可靠性，可靠性， 完备性完备性v归结/消解v归结反驳/消解反演vNext lecture: 谓词逻辑46语法、语义、语用47PL is Too Weak a Representational LanguagevConsider the problem of representing the following inf

35、ormation: vEvery person is mortal. (S1)vConfucius is a person. (S2)vConfucius is mortal. (S3)vS3 is clearly a logical consequence of S1 and S2. But how can these sentences be represented using PL so that we can infer the third sentence from the first two? 48Weakness of PLvHard to identify individual

36、s. E.g., Mary, 3 vIndividuals cannot be PL sentences themselves.vDifficult to directly and clearly talk about properties of individuals or relations between individuals (hard to connect individuals to class properties). vE.g., property of being a human implies property of being mortalvGeneralization

37、s, patterns, regularities cant easily be represented. vAll members of a class have this propertyvSome member of a class have this propertyvA better representation is needed to capture the relationship (and distinction) between objects and classes, including properties belonging to classes and indivi

38、duals49vFirst-Order Logic ( abbreviated FOL or FOPC) is expressive enough to concisely represent this kind of situation by separating classes and individualsvExplicit representation of individuals and classes, x, Mary, 3, persons.vAdds relations, variables, and quantifiers, e.g.,v“Every person is mo

39、rtal” Forall X: person(X) = mortal(X)v“There is a white alligator” There exists some X: Alligator(X) white(X)5051Propositional Logic vs. Predicate CalculusvPropositional LogicvThe world consists of propositions (sentences) which can be true or false.vPredicate Calculus (First Order Logic)vThe world

40、consists of objects, functions and relations between the objects.52SyntaxvTerm: vconstant|variable|function(term, , term)vWar-and-Peacevauthor-of(War-and-Peace)vfather-of(author-of(War-and-Peace)vAtomic Sentencevpredicate(term, , term)vComplex Sentence53Universal quantificationv Everyone at CSU is s

41、mart:x At(x,CSU) Smart(x)vx P is true in a model m iff P is true with x being each possible object in the modelvRoughly speaking, equivalent to the conjunction of instantiations of PAt(KingJohn,CSU) Smart(KingJohn) At(Richard,CSU) Smart(Richard) At(NUS,CSU) Smart(NUS) .54A common mistake to avoidvTy

42、pically, is the main connective with vCommon mistake: using as the main connective with :x At(x,CSU) Smart(x)means “Everyone is at CSU and everyone is smart”55Existential quantificationv vSomeone at CSU is smart:vx At(x,CSU) Smart(x)vx P is true in a model m iff P is true with x being some possible

43、object in the modelvRoughly speaking, equivalent to the disjunction of instantiations of PAt(KingJohn,CSU) Smart(KingJohn) At(Richard,CSU) Smart(Richard) At(NUS,CSU) Smart(NUS) .56Another common mistake to avoidvTypically, is the main connective with vCommon mistake: using as the main connective wit

44、h :x At(x,CSU) Smart(x)is true if there is anyone who is not at CSU!57Properties of quantifiersvx y is the same as y xvx y is the same as y x vx y is not the same as y xvx y Loves(x,y)v“There is a person who loves everyone in the world”vy x Loves(x,y)v“Everyone in the world is loved by at least one

45、person”vQuantifier duality: each can be expressed using the othervx Likes(x,IceCream) x Likes(x,IceCream)vx Likes(x,Broccoli) x Likes(x,Broccoli)58Examples ( (用谓词逻辑表示以下命题用谓词逻辑表示以下命题) )vAll purple mushrooms are poisonousvNo purple mushroom is poisonousvEvery CS student knows a programming language.vA

46、 programming language is known by every CS student59Resolution Refutation in Predicate CalculusvAdd to KBvConversion to CNFvSubstitution/ UnificationvApply Resolution ProcedurevDerive : is provedvNo more possible application of resolution rules: is not a consequence of KB60v 例子: 将下列谓词演算公式化为一个子句集(x)P

47、(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y)开始：消去蕴涵符号 只应用和符号，以AB替换AB。(1) (x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y)子句集的求取v 步骤：共9步。61(2) 减少否定符号的辖域 每个否定符号最多只用到一个谓词符号上，并反复应用狄摩根定律。(3) 对变量标准化 对哑元（虚构变量）改名，以保证每个量词有其自己唯一的哑元。(2) (x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y)(3) (x)P(x)(y)P(y)P(f(x,y)(w)Q(x,w)P(w)(1) ( x)P(x)( y)P(y)P(f(x,

48、y)( y)Q(x,y)P(y)62(4) 消去存在量词 以Skolem函数代替存在量词内的约束变量，然后消去存在量词化为前束形 把所有全称量词移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分。 前束形=前缀 母式 全称量词串 无量词公式(4) (x)P(x)(y)P(y)P(f(x,y)Q(x,g(x)）P(g(x)式中，w=g(x)为一Skolem函数。(5) (x)(y)P(x)P(y)P(f(x,y)Q(x,g(x)P(g(x)(3) (x)P(x)(y)P(y)P(f(x,y)(w)Q(x,w)P(w)63把母式化为合取范式 任何母式都可写成由一些谓词公式和(或)谓词

49、公式的否定的析取的有限集组成的合取。(7) 消去全称量词 所有余下的量词均被全称量词量化了。消去前缀，即消去明显出现的全称量词。(6) (x)(y)P(x)P(y)P(f(x,y)P(x)Q(x,g(x)P(x)P(g(x)(7) P(x)P(y)P(f(x,y)P(x)Q(x,g(x)P(x)P(g(x)(5)( x)( y)P(x)P(y)P(f(x,y)Q(x,g(x)P(g(x)64(8) 消去连词符号 用A,B代替(AB)，消去符号。最后得到一个有限集，其中每个公式是文字的析取。(9) 更换变量名称 可以更换变量符号的名称，使一个变量符号不出现在一个以上的子句中。(8) P(x)P(

50、y)P(f(x,y)P(x)Q(x,g(x)P(x)P(g(x)(9) P(x1)P(y)Pf(x1,y)P(x2)Qx2,g(x2)P(x3)Pg(x3)(7)(7)P(x)P(y)P(f(x,y)P(x)Q(x,g(x)P(x)P(g(x)65SkolemizingvTo convert arbitrary FOL formula to CNF, one needs to eliminate . vSolution: just “name” it, vusing a new name vdifferent from any existing name . to avoid conflict

51、.vExamplevx rich(x) becomes rich(g7)vg7 is called a Skolem constant.66h16768SubstitutionvGiven sentence S and substitution , vS denotes result of plugging into S vP(c), Q(c), (x)(P(x) Q(x) = R(x)v = x/cv(x)(P(x) Q(x) = R(x) = P(c) Q(c) = R(c) 6970Applying Substitution7172Composition of Substitutions

52、73UnificationvTo apply the resolution rule, we need to find a pair of complementary literals.vUnification is a method for making two literals identical.vIf two literals can be made identical, they are unifiable.7475v 例子储蓄问题 前提：每个储蓄钱的人都获得利息。 结论：如果没有利息，那么就没有人去储蓄钱76(1）规定原子公式： S(x,y) S(x,y) 表示 “x储蓄y” M(

53、x) M(x) 表示 “x是钱” I(x) I(x) 表示 “x是利息” E(xE(x，y) y) 表示 “x获得y”(2）用谓词公式表示前提和结论：前提：前提：( (x)(y)(S(x,y)M(y)(y)(I(y)E(x,y)结论：结论：(x)I(x) (x)(y)(M(y)S(x,y)(3) 化为子句形证明证明：77把前提化为子句形：1) S(x,y)M(y)I(f(x)2) S(x,y)M(y)E(x,f(x)把结论化为子句形：3) I(z)4) S(a,b)5) M(b)(4) 消解反演求NIL储蓄问题反演树子句（1）子句（3）f (x)/zM(b)NIL子句（5）子句（7）子句（4）a/x,b/yS(x,y)M(y)子句子句（6）78SummaryvCNF及其转化方法，步骤及其转化方法，步骤v置换置换/合一合一v消解反演消解反演vSkolemizingvNext lecture: 谓词逻辑 + 不确