上堂章节内容重点与难点.ppt

《上堂章节内容重点与难点.ppt》由会员分享，可在线阅读，更多相关《上堂章节内容重点与难点.ppt（44页珍藏版）》请在三一文库上搜索。

1、1/44,上堂课的内容、重点与难点,公理推理过程 假设推理过程,只按分离规则代入规则组织公理推理过程 了解导出规则，灵活组织假设推理过程,公理推理定理 公理 分离规则、代入规则 假设推理系统,2/44,2.4 命题演算的归结推理法,机器证明的一个重要方法， 仅有一条推理规则(称为归结规则)的机械推理法， 便于计算机程序实现。,3/44,2.4.1 归结证明过程,证明AB永真,证明AB永假,AB= (AB),证明B永真,证明B永假,B= (B),4/44,一、建立子句集,要证明公式AB，将 (AB)= A B 化为合取范式； (2) 把合取范式的所有析取式构成一个集合即子句集。,A化为合取范式、

2、 B化为合取范式,5/44,例 建立子句集,如要证明公式 (PQ)P)Q， 只要考察 (PQ)PQ (1) 根据(1)得合取范式： (PQ)PQ (2) 根据(2)建立子句集： S =PQ，P，Q,6/44,二、对子句集S的归结,设有两个子句 P1 P2 Pn 和 P1 Q2 Qm， 注意到这两个子句，其中一个含有命题变元的肯定形式，另一个含有该变元的否定，由这两个子句就可推出一个新子句： P2 Pn Q2 Qm 称之为这两个子句的归结式。,7/44,若干重要的归结规则,父辈子句 归结式 说明 P和PQ Q 三段论 PQ和PQ Q 子句合并成Q PQ和PQ PP或QQ 两个可能的子句 均为重言

3、式 P和P 空子句， 归结结束 PQ和QR PR 一般归结,8/44,三、归结证明,依归结规则进行归结，直至归结出空子句(用“”表示)， 则证明原公式为定理，否则不为定理。,子句可以 多次使用,9/44,2.4.2 归结证明举例,证明： (PP) = P P,归结过程为 (1) P (2) P (3) (1)(2)归结 故原式为定理,例 用归结原理证明 PP,10/44,例 (PQ)(PQ)P),证明： (PQ)(P Q ) P ) = (P Q) (P Q) P ) =(P Q) (P Q) P ) =(P Q) (P Q) P ),归结过程为 (1) P Q (2) P Q (3) P,(

4、4) P (1)(2)归结 (5) (3)(4)归结 故原式为定理,11/44,例 (PQ) R)(SP)Q) (SR),证明：考察(PQ) R)(SP)Q (SR) 合取范式为 (PR)(QR)(SP)QSR 建立子句集 PR，QR，SP，Q，S，R 归结过程为 (1) PR (2) QR (3) SP (4) Q (5) S (6) R (7) R (4)(2)归结 (8) (7)(6)归结,12/44,例 (SQ)(PQ)(RS)(RQ)P,证明： 建立子句集 SQ, P Q, RS, RQ, P 归结过程为:,(1) SQ (2) P Q (3) RS (4) RQ (5) P,(6)

5、 PS (1)(2)归结 (7) S (5)(6)归结 (8) PR (2)(4)归结 (9) R (5)(8)归结 (10) S (3)(9)归结 (11) (7)(10)归结 故原式为定理。,13/44,例 构造下面的归结推理证明：,若数a是实数，则它不是有理数就是无理数；若a不能表示成分数，则它不是有理数；a是实数且它不能表示成分数。所以a是无理数。,解 设 p：a是实数。 q：a是有理数。 r：a是无理数。 s：a能表示成分数。,首先将简单命题符号化：,前提：p(qr), sq, ps 结论：r,将前提与结论的否定化为子句。 归结证明过程： (1) pqr (2) sq (3) p (

6、4) s (5) r (6) prs (1)(2)归结 (7) rs (3)(6)归结 (8) r (4)(7)归结 (9) (5)(8)归结,14,前提：p(qr), sq, ps 结论：r,讨论,如果将“若数a是实数，则它不是有理数就是无理数”翻译如下： p(qr)(qr) = p(qr)(qr) = p(qr)(qr) =(pqr)(pqr) 则有2个子句： p q r p q r 如果只用到第1个子句，就能够归结出矛盾，当然更好了。,16/44,苏格拉底三段论,P：凡人要死 Q：苏格拉底是人 R：苏格拉底要死 此三段论表示为: (PQ)R 局限性: 此三段论是正确的，但却不是重言式。,

7、第三章 谓词演算基础,17/44,谓词演算,在命题演算中，把不可剖开或分解为更简单命题的原子命题作为基本单元。 对原子命题内部结构进一步剖析，分解为,个体,谓词,18/44,3.1 谓词与个体,个体 个体域 全总个体域 个体变元 项,3.1.1 个体,个体是指具有独立意义、独立存在的东西。 也称为常个体或实体。 用a、b、c等表示。,19/44,个体域、全总个体域,(2) 个体域：由个体组成的集合。 个体域常用I、J、K等表示。 (3) 全总个体域： 所有个体不管是何种类型的个体综合在一起组成的个体域称为全总个体域。 用U表示。,20/44,个体变元、项,(4)个体变元：以个体域I为变域的变元

8、称为个体域I上的个体变元。 用x、y、z、等表示。 (5)项：包括实体、变量符号和函数符号等。,常个体a、泛指个体x、 个体的函数 f(x),21/44,3.1.2 谓词,一、有关概念 1. 谓词的定义 2. 谓词填式 3. 谓词命名式 4. 谓词变元,把语句中表示 个体性质和关系的语言成分 称为谓词（predicate）,谓词指个体所具有的性质或若干个体之间的关系,22/44,例 (谓词：表示个体性质或个体间关系),“苏格拉底是人”中的 “是人”。 “苏格拉底是要死的”中的“是要死的”。 “张三生于北京”中的“生于”。 “3+2=5”中的“+=”。,23/44,一元谓词、二元谓词、三元谓词,

9、“苏格拉底是人”中的 “是人”。 “苏格拉底是要死的”中的“是要死的”。 “张三生于北京”中的“生于”。 “3+2=5”中的“+=”。,谓词所携空位的数目,谓词的元数,24/44,谓词命名式: 携有空位的大写字母,M（ ）表示“是人”。 D（ ）表示“是要死的”。 B（ ， ）表示“生于”。 ADD（ ， ， ）表示“+=”。 可读性差！ 可用变元来代替空位: M(x)，D(x)，B(x,y)，ADD(x, y, z),25/44,谓词填式,M（苏格拉底） “苏格拉底是人”。 D（苏格拉底） “苏格拉底是要死的”。 B（张三，北京） “张三生于北京”。 ADD（3，2，5） “3+2=5”。,

10、单个谓词不构成完整的意思，只有当谓词填以个体后才能够构成完整的意义。,谓词的空位上填入个体后所产生的语句。,26/44,谓词命名式与谓词填式,例如：,同形，但它们表示不同的意义。,M(x),作为命名式时，它只是M()的另一写法，x是个体变元， M(x)未必是命题,作为填式时，x是常个体，M(x)是命题,27/44,谓词：从个体域到真值集的映射,当谓词填式中所填个体都是常元时，它是一个命题，因而有确定的真值。 例如： M（x）“x是人” M（苏格拉底）为真， M（孔子）为真， M（孙悟空）为假， M（北京）为假。,28/44,个体域a上的一元谓词,A(e)如下图所示:,e A1 A2 a T F

11、,谓词数目：2,29/44,个体域a，b上的一元谓词,A(e)如下图所示:,e A1 A2 A3 A4 a T F T F b T T F F,谓词数目： 22,30/44,个体域a，b，c上的一元谓词,A(e)如下图所示:,e A1 A2 A3 A4 A5 A6 A7 A8 a T F T T F T F F b T T F T F F T F c T T T F T F F F,一元谓词数目：23,31/44,个体域a，b ，c ，d上的一元元谓词,A(e)如下图所示:,E A0 A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12 A13 A14 A15,a T

12、F T T T F F F T T T T F F F F b T T F T T F T T F F T F T F F F c T T T F T T F T F T F F F T F F d T T T T F T T F T F F F F F T F,谓词数目：24,32/44,个体域a上的二元谓词,A(e1，e2)如下图所示:,e1 e2 A1 A2 a a T F,谓词数目：2,33/44,个体域a，b上的二元谓词,A(e1，e2)如下图所示:,e1 e2 A0 A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12 A13 A14 A15,a a T F

13、 T T T F F F T T T T F F F F a b T T F T T F T T F F T F T F F F b a T T T F T T F T F T F F F T F F b b T T T T F T T F T F F F F F T F,34/44,谓词数目,h个体域的大小 m个体变元数,35/44,谓词变元,约定: 大写字母A、B、C等特定的谓词 小写字母a、b、c等特定的个体或实体 大写字母X、Y、Z等谓词变元 小写字母x、y、z等个体变元,以谓词组成的集合为变域的变元,36/44,一元谓词变元,其中x为变量符号项、A为谓词变元。 此式表示x具有性质A。

14、 注意：x，A分别在两个域上变化。,A(x),37/44,二元谓词变元,其中x, y为变量符号项、A为谓词变元。 此式表示x和y具有关系A。 注意：x，y，A分别在三个域上变化。,A(x，y),38/44,二、谓词语句的符号化,动词 系动词 形容词 集合名词 ,谓词,39/44,例1 符号化：我送他这本书。,解：令 A(e1，e2，e3)表示“e1送e3给e2”； B(e)表示“e为书”； a表示“我”； b表示“他”； c表示“这”； 则原句译为： A(a，b，c) B(c),40/44,例2 符号化：这只大红书柜摆满了那些古书。,解：令,A(e1，e2)表示“e1摆满了e2； B(e)表示

15、“e为大的”； C(e)表示“e为红的”； D(e)表示“e为书柜”； E(e)表示“e为古书”； a表示“这只”； b表示“那些”； 则原句译为： A(a，b) B(a) C(a) D(a) E(b),41/44,例 将下列命题符号化，并讨论它们的真值: (1)只有2是素数，4才是素数； (2)如果5大于4，则4大于6。,解(1) 记 P(e)表示e为素数。 可以翻译为： P(4) P(2) 其真值为T。 (2) 记 G(e1, e2)表示e1大于e2。 可以翻译为： G(5,4) G(4, 6) 其真值为F。,42/44,例 如果我知道你不在家，我就不去找你了 。,解：令,F(e1,e2)

16、表示“e1去找e2”, a表示“我”， b表示“你”， K(e1,e2)表示“e1知道e2不在家” 则原句译为 K(a, b) F(a,b),另解： A(e1,e2)表示“e1知道e2”, H(e) 表示 “e在家”, 则原句译为 A(a, H(b) F(a,b),非一阶谓词,43/44,本堂课的内容、重点与难点,归结推理过程 运用谓词将知识符号化,提取子句（将哪个公式化为合取范式？） 个体与个体变元 谓词与谓词变元,归结推理法 子句 归结规则 个体 谓词,44/44,作业04,2.7（3）（6） 2.8 3.1（2）（4） 补1 将下列命题符号化，并讨论它们的真值:,(1) 只有2是偶数，3才不是偶数； (2) 如果3能够除尽6，则3能够除尽8； (3) 5是偶数的充分必要条件是2能够除尽5。,