人工智能推理优秀PPT.ppt
人工智能推理第1页，本讲稿共14页第三章 基于谓词逻辑的机器推理命题逻辑（复习）命题逻辑（复习）命题是具有真假意义的陈述句。命题是具有真假意义的陈述句。不能被分解成更简单的陈述句的命题称为简单命题不能被分解成更简单的陈述句的命题称为简单命题命题可用小写字母如命题可用小写字母如p,q,rp,q,r表示，称为命题变元。表示，称为命题变元。复合命题是由简单命题和联结词联结而成的命题。复合命题是由简单命题和联结词联结而成的命题。最最基本的基本的5 5种联结词是：种联结词是：，命题公式的定义：命题公式的定义：（1 1）单个命题变元是命题公式，称为原子公式；（）单个命题变元是命题公式，称为原子公式；（2 2）若）若A A、B B是命题公式，则是命题公式，则 A A，A A B B，A A B B，A A B B，A A B B也是命题公式；也是命题公式；（3 3）只有有限次地应用（）只有有限次地应用（1)1)、（、（2 2）形成的符号串才是命题公式。）形成的符号串才是命题公式。命题公式的一个指派（赋值）。命题公式的一个指派（赋值）。永真式（重言式）；永假式（矛盾式）；可满足式。永真式（重言式）；永假式（矛盾式）；可满足式。第2页，本讲稿共14页 基于谓词逻辑的机器推理-命题逻辑（复习）命题逻辑（复习）等价式等价式A AB B：A A B B为重言式。为重言式。永真蕴涵永真蕴涵A A B B：A A B B为重言式。为重言式。命题逻辑的一些重要等价式：命题逻辑的一些重要等价式：1 1、双重否定律：、双重否定律：A A A A2 2、幂等律：、幂等律：A AA A A,A A,A A A A A3 3、交换律：、交换律：A A B B B B A,A A,A B B B B A A4 4、结合律：、结合律：（A A B)B)C C A A(B(B C)C)(A (A B)B)C C A A (B (B C)C)5 5、分配律：、分配律：A A(B(B C)C)(A(A B)B)(A(A C)C)A A (B(B C)C)(A (A B)B)(A(A C)C)6 6、De Morgan De Morgan 律：律：(A(A B)B)A A B B (A(A B)B)A A B B第3页，本讲稿共14页7 7、吸收律：、吸收律：A A(A(A B)B)A,A,A A (A(A B)B)A A 8 8、零律：、零律：A A T T T,A T,A F F F F9 9、同一律：、同一律：A A F F A,A A,A T T A A1010、排中律：、排中律：A A A A T T1111、矛盾律：、矛盾律：A A A A F F1212、蕴含等值式、蕴含等值式:A:A B B A A B B1313、等价等值式：、等价等值式：A A B B (A (A B)B)(B(B A)A)基于谓词逻辑的机器推理-命题逻辑（复习）命题逻辑（复习）第4页，本讲稿共14页命题逻辑的一些重要的永真蕴涵式（即推理定律）命题逻辑的一些重要的永真蕴涵式（即推理定律）1 1、化简式：、化简式：A A B B A,A,A A B B B B2 2、附加式：、附加式：A A A A B,B,B B A A B B3 3、析取三段论：、析取三段论：A A (A(A B)B)B B4 4、假言推理（分离规则）：、假言推理（分离规则）：A A (A(A B)B)B B5 5、拒取式：、拒取式：B B (A(A B)B)A A6 6、假言三段论：、假言三段论：(A(A B)B)(B(BC)C)A A C C7 7、二难推论、二难推论:(A:(A B)B)(A(A C)C)(B(BC)C)C C 基于谓词逻辑的机器推理-命题逻辑（复习）命题逻辑（复习）第5页，本讲稿共14页命题公式的析取范式命题公式的析取范式命题变元或命题变元的否定的合取式称为简单合取式。命题变元或命题变元的否定的合取式称为简单合取式。简单合取式的析取式称为析取范式。简单合取式的析取式称为析取范式。命题公式的合取范式命题公式的合取范式命题变元或命题变元的否定的析取式称为简单析取式。命题变元或命题变元的否定的析取式称为简单析取式。简单析取式的合取式称为合取范式。简单析取式的合取式称为合取范式。任一命题公式都可化为与之等价的析取范式与合任一命题公式都可化为与之等价的析取范式与合取范式。取范式。基于谓词逻辑的机器推理-命题逻辑（复习）命题逻辑（复习）第6页，本讲稿共14页3.1.1 3.1.1 谓词、函词、量词谓词、函词、量词个体：研究对象中可以独立存在的具体的或抽象的客体。个体用个体常元或个个体：研究对象中可以独立存在的具体的或抽象的客体。个体用个体常元或个体变元表示，如体变元表示，如x,y,z,a,b,c,x,y,z,a,b,c,等。等。谓词：描述个体性质及个体之间相互关系的词。用谓词常元或谓词变元表谓词：描述个体性质及个体之间相互关系的词。用谓词常元或谓词变元表示，如示，如P P、Q Q、R R，等。等。例、命题例、命题“2 2是素数是素数”中，中，2 2是个体，是个体，“是素数是素数”是谓词。可表示为是谓词。可表示为P(2).P(2).函词（函数）：某些个体是其它个体的函数，描述这种关系的函词（函数）：某些个体是其它个体的函数，描述这种关系的称为函数。称为函数。例、命题例、命题“小李的父亲是医生小李的父亲是医生”可表示为可表示为Doctor(father(Li).Doctor(father(Li).基于谓词逻辑的机器推理-谓词（复习）谓词（复习）第7页，本讲稿共14页 基于谓词逻辑的机器推理-一阶谓词逻辑一阶谓词逻辑量词：存在量词量词：存在量词“”；全称量词；全称量词“”。例、例、“任何实数的平方都非负任何实数的平方都非负”可表示为可表示为 x(R(x)x(R(x)N(R(x)N(R(x)。“存在偶素数存在偶素数”可可表示为表示为 x(x(E(x)E(x)P(x)P(x)。3.1.2 3.1.2 谓词公式谓词公式项项的定义：的定义：1 1、个体常元和个体变元是项；、个体常元和个体变元是项；2 2、设、设f f是是n n元函词符号，元函词符号，t t1 1,t t2 2,t tn n是项，则是项，则f f(t t1 1,t t2 2,t tn n)是项。是项。3 3、只有有限次使用、只有有限次使用1 1，2 2得到的符得到的符号串才是项。号串才是项。原子公式：原子公式：P P是是n n元谓词，元谓词，t t1 1,t t2 2,t tn n是项，则是项，则P P(t t1 1,t t2 2,t tn n)称为原子公称为原子公式。式。谓词公式的定义：谓词公式的定义：1 1、原子公式是谓词公式；、原子公式是谓词公式；2 2、若、若A A、B B是谓词公式，是谓词公式，则则 A A，A A B B，A A B B，A A B B，A A B B，xAxA，xAxA也是谓词公式；也是谓词公式；3 3、只有有限次地应用步骤、只有有限次地应用步骤1 1，2 2形成的符号串才是谓词公式。形成的符号串才是谓词公式。第8页，本讲稿共14页辖域：辖域：xA xA 和和 xAxA中，中，x x称为指导变元，称为指导变元，A A称为称为x x的辖域。的辖域。A A中出现的中出现的x x称为约束出现。若称为约束出现。若x x的所有出现都是约束出现，则的所有出现都是约束出现，则x x称为约束变元，否称为约束变元，否则称为自由变元。则称为自由变元。例、例、xP(x)xP(x)；x(H(x)x(H(x)G(x,y)G(x,y)；xA(x)xA(x)B(x)/B(x)/加括号加括号(x)x)谓词公式的解释谓词公式的解释I I由下面由下面4 4部分构成：部分构成：(a)(a)、非空个体域、非空个体域D DI I。(b)(b)、D DI I中一些特定元素的集合中一些特定元素的集合(c)(c)、D DI I上特定函数的集合上特定函数的集合(d)(d)、D DI I上特定谓词的集合上特定谓词的集合例、给定解释例、给定解释I I如下：如下：P84P84 基于谓词逻辑的机器推理-一阶谓词逻辑第9页，本讲稿共14页谓词公式的永真性与可满足性:永真式（重言式）：在任何解释下均为真的谓词公永真式（重言式）：在任何解释下均为真的谓词公式称为永真式。式称为永真式。永假式（矛盾式）：在任何解释下均为假的谓词公式称为永假式。此时称谓词公式是不可满足的。可满足式：存在解释使谓词公式为真可满足式：存在解释使谓词公式为真。基于谓词逻辑的机器推理-一阶谓词逻辑第10页，本讲稿共14页常用谓词公式的等价式与推理定律常用谓词公式的等价式与推理定律命题逻辑的等价式和推理定律对谓词公式都成立，除此之外，还存命题逻辑的等价式和推理定律对谓词公式都成立，除此之外，还存在与量词有关的等价式和推理定律。参见教材在与量词有关的等价式和推理定律。参见教材p85,P86p85,P86。等价式：等价式：1 1、消去量词等价式、消去量词等价式设个体域为有限集设个体域为有限集D=aD=a1 1,a,a2 2,a,an n，则有，则有 xA(x)xA(x)A(A(a a1 1)A(A(a a2 2).A(A(a an n)xA(x)xA(x)A(A(a a1 1)A(A(a a2 2).A(A(a an n)2 2、量词转换律、量词转换律 xA(x)xA(x)x x A(x)A(x)，xA(x)xA(x)x x A(x)A(x)基于谓词逻辑的机器推理-一阶谓词逻辑第11页，本讲稿共14页3 3、量词分配律、量词分配律 x(A(x)x(A(x)B(x)B(x)xA(x)xA(x)x xB(x)B(x)x(A(x)x(A(x)B(x)B(x)xA(x)xA(x)x xB(x)B(x)4 4、量词辖域扩张及收缩律、量词辖域扩张及收缩律若若A(x)A(x)是任意的含自由出现个体变元是任意的含自由出现个体变元x x的谓词公式，的谓词公式，B B中不含中不含x x的出现，的出现，则则(a)(a)、x(A(x)x(A(x)B)B)xA(x)xA(x)B B x(A(x)x(A(x)B)B)xA(x)xA(x)B B x(A(x)x(A(x)B)B)xA(x)xA(x)B B x(Bx(B A(x)A(x)B B xA(x)xA(x)基于谓词逻辑的机器推理-一阶谓词逻辑第12页，本讲稿共14页(b)(b)、x(A(x)x(A(x)B)B)xA(x)xA(x)B B x(A(x)x(A(x)B)B)xA(x)xA(x)B B 推理定律：推理定律：全称指定规则全称指定规则US(Universal Specification)US(Universal Specification)：xA(x)xA(x)A(y)A(y)，y y是个体域中任一确定是个体域中任一确定元素。元素。存在指定规则存在指定规则ES(Existential Specification)ES(Existential Specification)：xA(x)xA(x)A(c)A(c)，c c是个体域中某是个体域中某一确定元素。一确定元素。全称推广规则全称推广规则UG(Universal Generalization)UG(Universal Generalization)：A(y)A(y)xA(x)xA(x)，y y是个体域中任一是个体域中任一确定元素。确定元素。存在推广规则存在推广规则 EG(Universal Generalization)EG(Universal Generalization)：A(c)A(c)xA(x)xA(x)，c c是个体域中某是个体域中某一确定元素。一确定元素。基于谓词逻辑的机器推理-一阶谓词逻辑第13页，本讲稿共14页以谓词公式的等价式及推理定律为基础进行的推理称为自然演以谓词公式的等价式及推理定律为基础进行的推理称为自然演绎推理。例见教材绎推理。例见教材p90p90。自然演绎推理在机器上实施比较困难，。自然演绎推理在机器上实施比较困难，因为推理规则太多。因为推理规则太多。基于谓词逻辑的机器推理-一阶谓词逻辑第14页，本讲稿共14页
