人工智能(推理1).ppt

1、人工智能(推理部分),内蒙古工业大学计算机系 2007年6月,第三章 基于谓词逻辑的机器推理,命题逻辑（复习） 命题是具有真假意义的陈述句。 不能被分解成更简单的陈述句的命题称为简单命题 命题可用小写字母如p,q,r表示，称为命题变元。 复合命题是由简单命题和联结词联结而成的命题。 最基本的5种联结词是：， 命题公式的定义：（1）单个命题变元是命题公式，称为原子公式；（2）若A、B是命题公式，则 A，A B，A B，A B，A B也是命题公式；（3）只有有限次地应用（1)、（2）形成的符号串才是命题公式。 命题公式的一个指派（赋值）。 永真式（重言式）；永假式（矛盾式）；可满足式。,基于谓词逻

2、辑的机器推理-命题逻辑（复习）,等价式AB： A B为重言式。 永真蕴涵A B： A B为重言式。 命题逻辑的一些重要等价式： 1、双重否定律：A A 2、幂等律： AA A, A A A 3、交换律： AB BA, A B B A 4、结合律： （A B) C A(B C) (A B) C A (B C) 5、分配律： A(B C) (AB) (A C) A (B C) (A B) (A C) 6、De Morgan 律： (AB) A B (A B) A B,7、吸收律： A(A B) A, A (A B) A 8、零律： AT T, A F F 9、同一律： AF A, A T A 10

3、、排中律： A A T 11、矛盾律： A A F 12、蕴含等值式: A B A B 13、等价等值式： A B (A B) (B A),基于谓词逻辑的机器推理-命题逻辑（复习）,命题逻辑的一些重要的永真蕴涵式（即推理定律） 1、化简式： A B A, A B B 2、附加式： A A B, B A B 3、析取三段论： A (A B) B 4、假言推理（分离规则）： A (A B) B 5、拒取式： B (A B) A 6、假言三段论： (A B) (BC) A C 7、二难推论: (A B) (A C) (BC) C,基于谓词逻辑的机器推理-命题逻辑（复习）,命题公式的析取范式 命题变元

4、或命题变元的否定的合取式称为简单合取式。简单合取式的析取式称为析取范式。 命题公式的合取范式 命题变元或命题变元的否定的析取式称为简单析取式。简单析取式的合取式称为合取范式。 任一命题公式都可化为与之等价的析取范式与合取范式。,基于谓词逻辑的机器推理-命题逻辑（复习）,3.1.1 谓词、函词、量词 个体：研究对象中可以独立存在的具体的或抽象的客体。个体用个体常元或个体变元表示，如x,y,z,a,b,c,等。 谓词：描述个体性质及个体之间相互关系的词。用谓词常元或谓词变元表示，如P、Q、R，等。 例、命题“2是素数”中，2是个体，“是素数”是谓词。可表示为P(2). 函词（函数）：某些个体是其它

5、个体的函数，描述这种关系的 称为函数。 例、命题“小李的父亲是医生”可表示为Doctor(father(Li).,基于谓词逻辑的机器推理-谓词（复习）,基于谓词逻辑的机器推理- 一阶谓词逻辑,量词：存在量词“ ”；全称量词“ ”。 例、“任何实数的平方都非负”可表示为 x(R(x) N(R(x)。 “存在偶素数”可表示为 x(E(x) P(x)。 3.1.2 谓词公式 项的定义：1、个体常元和个体变元是项；2、设f是n元函词符号， t1, t2 , , tn是项，则f(t1, t2 , , tn)是项。3、只有有限次使用1，2得到的符号串才是项。 原子公式：P是n元谓词， t1, t2 , ,

6、 tn是项，则P(t1, t2 , , tn)称为原子公式。 谓词公式的定义：1、原子公式是谓词公式；2、若A、B是谓词公式，则 A，A B，A B，A B，A B， xA， xA也是谓词公式；3、只有有限次地应用步骤1，2形成的符号串才是谓词公式。,辖域： xA 和 xA中，x称为指导变元，A称为x的辖域。A中出现的x称为约束出现。若x的所有出现都是约束出现，则x称为约束变元，否则称为自由变元。 例、xP(x)； x(H(x) G(x,y)； xA(x) B(x) /加括号(x) 谓词公式的解释I由下面4部分构成： (a)、非空个体域DI。 (b)、 DI中一些特定元素的集合 ( c)、 D

7、I上特定函数的集合 (d)、 DI上特定谓词的集合 例、给定解释I如下：P84,基于谓词逻辑的机器推理- 一阶谓词逻辑,谓词公式的永真性与可满足性: 永真式（重言式）：在任何解释下均为真的谓词公式称为永真式。 永假式（矛盾式）：在任何解释下均为假的谓词公式称为永假式。此时称谓词公式是不可满足的。 可满足式：存在解释使谓词公式为真。,基于谓词逻辑的机器推理- 一阶谓词逻辑,常用谓词公式的等价式与推理定律 命题逻辑的等价式和推理定律对谓词公式都成立，除此之外，还存在与量词有关的等价式和推理定律。参见教材p85, P86。 等价式： 1、消去量词等价式 设个体域为有限集D=a1,a2, an，则有

8、xA(x) A(a1) A(a2) . A(an) xA(x) A(a1) A(a2) . A(an) 2、量词转换律 xA(x) x A(x)， xA(x) x A(x),基于谓词逻辑的机器推理- 一阶谓词逻辑,3、量词分配律 x(A(x) B(x) xA(x) xB(x) x(A(x) B(x) xA(x) xB(x) 4、量词辖域扩张及收缩律 若A(x)是任意的含自由出现个体变元x的谓词公式，B中不含x的出现，则 (a)、 x(A(x) B) xA(x) B x(A(x) B) xA(x) B x(A(x) B) xA(x) B x(B A(x) B xA(x),基于谓词逻辑的机器推理- 一阶谓词逻辑,(b)、 x(A(x) B) xA(x) B x(A(x) B) xA(x) B 推理定律： 全称指定规则US(Universal Specification) ： xA(x) A(y)，y是个体域中任一确定元素。 存在指定规则ES(Existential Specification)： xA(x) A(c)，c是个体域中某一确定元素。 全称推广规则UG(Universal Generalization) ：A(y) xA(x)，y是个体域中任一确定元素。 存在推广规则 EG(Universal Generali