人工智能中的离散数学.ppt

1、数理逻辑,逻辑学: 研究人的思维形式和规律的科学由于研究的对象和方法各有侧重而又分为形式逻辑、辩证逻辑和数理逻辑 数理逻辑: 用数学方法研究推理，是研究推理中前题和结论之间的形式关系的科学所谓推理就是由一个或几个判断推出一个新判断的思维形式. 这里所说的数学方法就是建立一套表意符号体系，对具体事物进行抽象的形式研究的方法因此，数理逻辑又称符号逻辑这种方法的优点是表达简洁、推理方便、概括性好、易于分析等,数理逻辑,一般认为，数理逻辑是由德国数学家兼哲学家莱布尼兹(G.W.Leibnitz)在17世纪中叶创立的其后由英国数学家布尔(G.Bool)于1847年出版的逻辑的数学分析一书发展了逻辑代数，

2、即通常称为布尔代数还有德国数学家弗雷树(F.L.G.Frege)于1879年出版了表意符号,引入了量词、约束变元，使逻辑演算趋于完备1930年出生于奥地利的美藉数学家哥德尔(K.Gdel)的完全性定理证明，使数理逻辑的基础得到完善意大利数学家皮亚诺(G.Peano)，英国数学家德摩根(A.DeMorgen)、罗素(B.A.W.Russell)等人都做了很大贡献，丰富和发展了数理逻辑,数理逻辑,数理逻辑主要包括五部分：逻辑演算、证明论、公理化集合论、模型论和递归函数论本篇仅介绍计算机科学领域中所必需的数理逻辑基础知识： 命题逻辑 谓词逻辑,1.1命题逻辑,能判断真假的陈述语句称为命题。一个语句如

3、果不能再进一步分解成更为简单的语句,而且又是一个命题则称此命题为原始命题 作为命题的陈述句所表达的判断结果称为命题的真值，真值只取两个值：真或假。真值为真的命题称为真命题，真值为假的命题称为假命题。真命题表达的判断正确，假命题表达的判断错误。任何命题的真值都是唯一的。,命题逻辑,判断给定句子是否为命题，应该分两步： 首先判定它是否为陈述句 其次判断它是否有唯一的真值。,例1 判断是否为命题?,(1) 雪是黑色的。 (2) x大于y。 (3) 月球上有冰。 (4) 2100年元旦是晴天。 (5)大于3.14 吗？ (6) 请不要吸烟！ (7) 这朵花真美丽啊！ (8) 我正在说假话。,本例中的8

4、个句子中，(5)是疑问句，(6)是祈使句，(7)是感叹句，因而这3个句子都不是命题。 剩下的5个句子都是陈述句，但(2)无确定的真值，根据x,y的不同取值情况它可真可假，即无唯一的真值，因而不是命题。 虽然今天我们不知道(3)，(4)的真值，但它们的真值客观存在，而且是唯一的，将来总会知道(3)的真值，到2100年元旦(4)的真值就真相大白了。,若(8)的真值为真，即“我正在说假话”为真，也就是“我正在说真话”，则又推出(9)的真值应为假；反之，若(9)的真值为假，即“我正在说假话”为假，也就是“我正在说假话”，则又推出(9)的真值应为真。于是(9)既不为真又不为假，因此它不是命题。像(9)这

5、样由真推出假，又由假推出真的陈述句称为悖论。凡是悖论都不是命题。,例2,2是偶素数； 2或4是素数； 如果2是素数，则3也是素数； 2是素数当且仅当3也是素数。 全是命题。 上述命题都是通过诸如“或”，“如果，则”等连词联结而成，这样命题，称为复合命题。相对地，构成复合命题的命题称为简单命题。,1.2 逻辑联词,联结词是逻辑联结词或命题联结词的简称，它是自然语言中连词的逻辑抽象. 有了联结词，便可以用它和原子命题构成复合命题常用联结词有以下5种,1.2 逻辑联词,(1) 否定(Negation)， 命题P的否定是命题P,读作非P。从真值表易见P与P的取值关系：P真，当且仅当P假。,(2) 合取

6、(Conjunction)， 命题P与Q的合取是命题PQ,读作P与Q。PQ取值“真”，当且仅当P与Q都取真值“真”。 PP 是一永假式。,1.2 逻辑联词,1.2 逻辑联词,(3) 析取(Disjunction)， 命题P与Q的析取是命题PQ,读作P或Q。PQ假，当且仅当P与Q都假。,1.2 逻辑联词,(4) 条件联结词(Implication)， 命题PQ,读作“P条件Q”或“如果P,则Q”。当P为F, PQ为T,称为“善意推定”. PQ假，当且仅当P真而Q假。,1.2 逻辑联词,(5) 双条件(Bicondition)， 命题P与Q组成双条件命题PQ,读作P当且仅当Q。PQ 取真，当且仅当

7、P与Q取相同的真值(同真或同假)。这里称P为双条件命题的左支,称Q为右支。,1.2逻辑联词,以上定义了五种最基本、最常用、也是最重要的联结词， ，将它们组成一个集合， ，称为一个联结词集。其中为一元联结词，其余的都是二元联结词。 使用这些联结词的好处就是： 可以将复杂命题表示成简单的符号公式。 连接词的优先级: ，,1.3 命题形式与真值函数,从上可知，命题分两类：一类是原子命题；另一类是复合命题，它是由原子命题和联结词复合而成判断一个命题是否为复合命题，其关键是联结词出现否？出现，则是复合命题；不出现，则是原子命题,1.3 命题形式与真值函数,1.命题公式 前面讲了联结词、原子命题变元再加上

8、圆括号“(”、“)”，便可以进行有限次的连接，得到许多字符串，这些字符串是否都有意义呢？即对其中命题变元作指派后，它们是否都有确定的真值？答案为否那些有意义的字符串，称为约中的合式公式，简称命题公式或公式如何连接才能得到合式公式，这就需要给出一定的规则 下面，使用归纳法定义合式公式,1.3命题公式,(1)单个命题变项称为原子命题公式。单个命题变项是合式公式，并称为原子命题公式。 (2)若A是合式公式，则(A)也是合式公式。 (3)若A，B是合式公式，则(AB)，(AB)，(AB)，(A B)也是合式公式。 (4)只有有限次地应用(1)(3)形式的符号串才是合式公式。 如：(pq)(q r)，(

9、pq)r，p(qr)等都是合式公式，而pqr，（p(rq)等不是合式公式。,1.3 真值表与等值公式,定理1.3.1 AB当且仅当AB是永真式 显然，根据有关定义，不难证明此定理所以，又称AB是永真双条件式 等价式有下列性质： 自反性，即对任意公式A，有AA 对称性，即对任意公式A和B，若AB，则BA 传递性，即对任意公式A,B和C，若AB、BC，则AC 4基本等价式命题定律 在判定公式间是否等价，有一些简单而又经常使用的等价式，称为基本等价式或称命题定律牢固地记住它并能熟练运用，是学好数理逻辑的关键之一，,1.3 真值表与等值公式,应该注意到这一点现将这些命题定律列出如下： (1)双否定:

10、AA (2)交换律: ABBA, AB BA, AB BA (3)结合律: (AB)CA(BC), (AB)CA(BC)， (AB)CA(BC) (4)分配律： A(BC)(AB)(AC)， A(BC)(AB)(AC)， (5)德摩根律: (AB) A B, (AB)A B,1.3 真值表与等值公式,(6)等幂律: AAA，AAA (7)同一律: ATA，AFA (8)零律: AFF， ATT (9)吸收律: A(AB)A, A(AB)A (10)互补律: AAF (矛盾律) AAT (排中律) (11)条件式转化律：AB AB, AB B A (12)双条件式转化律：AB (AB)(BA)

11、, AB(AB)(A B), AB (AB) (13)输出律: (AB)CA(BC) (14)归谬律: (AB)(A B) A,1.3 真值表与等值公式,上面这些定律，即是通常所说的布尔代数或逻辑代数的重要组成部分它们的正确性利用真值表是不难给出证明的 5. 代入规则和替换规则 在定义合成公式时，我们已看到逻辑联结词能够把已知公式合并成新的公式，从这个意义上可把逻辑联结词看成运算除逻辑联结词外，还要介绍“代入和“替换”，它们也有从已知公式得到新的公式的作用，因此也可将它们看成运算，这不无道理，而且在今后讨论中，它们的作用也是不容忽视的,1.3 真值表与等值公式,(1)代入规则 定理1.3.2

12、在一个永真式A中，任何一个原子命题变元R出现的每一处，用另一个公式代入，所得公式B仍是永真式本定理称为代入规则 证明: 因为永真式对任意解释，其值都是真，与所给的某个命题变元指派的真值是真还是假无关，因此，用一个命题公式代入到原子命题变元R出现的每一处后，所得命题公式的真值仍为真，证毕,1.3 真值表与等值公式,例. 求证 (PQ) (PQ)为永真式 证明 由排中律可知，RRT，即R R为永真式今用公式(PQ)代人前面公式中的命题变元R，则得(PQ)(PQ) 根据代人规则可知，给定公式是永真式注意，若仅仅把(PQ)代入到一个析取项R，得到(PQ)R，显然它不是永真式，因为这不符合代入规则所要求

13、的处处代入,1.3 真值表与等值公式,(2)替换规则 定理1.3.3 设A1是合式公式A的子公式，若A1B；并且将A中的A1用B1替换，得到公式B理，则AB. 本定理称为替换规则 证明 因为A1B, 即对于它们的命题变元做任何真值的指派；A1与B1的真值相同. 故以B1替换A1后,公式B与A在对其命题变元做相应的任何真值指派,它们的真值也相同, 因此AB成立 满足定理1.3.3条件的替换，称为等价替换,1.3 真值表与等值公式,利用命题定律和定理1.3.3，可以推演出一些更为复杂的等价式从定理及例题，可看到，代入和替换有两点区别： 代入是对原子命题变元而言的，而替换可对命题公式实行 代入必须是

14、处处代入，替换则可部分替换，亦可全部替换,1.3命题公式的真值判定方法,1、真值表法 真值表，就是能显示一个真值形式在它的命题变项的各种真值组合下所取真值的图表。 其作用是判定一个真值形式是重言式、可满足式或者是矛盾式。,构造真值表的一般方法,（1）找出给定真值形式中的所有命题变项，列举出它们的各种真值组合。 （2）根据真值形式的构成过程，由简到繁列举出该真值形式的构成部分，真值表的最后一列就是说要判定的真值形式。 （3）根据所涉五个基本真值联结词的逻辑特性，分别计算出每一行中各构成部分的真值，最后得出该真值形式的真值。,用真值表判定(p q) r) (p (q r)是否为重言式。,用真值表判

15、定下述推理,或者逻辑学难学，或者没有多少学生喜欢它。如果数学容易学，那么逻辑不难学。因此，如果许多学生喜欢逻辑，那么数学不容易学。 前提：(1) p q; (2) r p 结论：q r 真值形式： (p q) (r p) (q r),真值表方法,真值表方法还可以用来判定不同真值形式之间的逻辑关系,1.4 范式,2. 析取范式与合取范式 定义1.5.3 一个命题公式A称为析取范式, 当且仅当A可表示为简单合取式的析取, 即AA1A2 An;其中Ai为简单合取式, i=1, 2,n. 定义1.5.4 一个命题公式A称为合取范式, 当且仅当A可表示为简单析取式的合取, 即A A1A2 An;其中Ai

16、为简单析取式, i=1, 2,n.,1.4 范式,例. 求(PQ)P的析取范式和合取范式 解: (PQ)P(PQ)P) (PQ)P 析取范式 P 析取范式 (PQ)P(PQ)P 合取范式 P(QP) 合取范式 P 合取范式,1.4 范式,范式基本上解决了公式的判定问题. 但由于范式的不唯一性, 对识别公式间是否等价带来了一定困难, 而公式的主范式解决了这个问题. 下面分别讨论主范式中的主析取范式和主合取范式. 1.主析取范式 小项的概念和性质 定义1.5.5 在含有n个命题变元的简单合取式中, 若每个命题变元与其否定不同时存在, 或二者之一出现一次且仅出现一次, 则称该简单合取式为小项, 或布

17、尔积. 可以证明，n个命题变元共形成2n个小项,1.4 范式,主析取范式的求法 主析取范式求法有两种：真值表法和公式化归法定理1.7.1的证明已给出了用真值表求主析取范式的方法，公式化归法给出如下： 把给定公式化成析取范式； 删除析取范式中所有为永假的简单合取式； 用等幂律把简单合取式中重复出现的同一命题变元的化简为一次出现. 用同一律补进简单合取式中未出现的所有命题变元, 并用分配律展开,将相同的简单合取式的多次出现化为一次出现, 这样就得到给定公式的主析取范式.,1.5常用的蕴涵式,下面给出常用的蕴涵式，称为基本蕴涵式，它们可以用真值表法、前件真推导后件真法和后件假推导前件假法去证明 (1

18、) PQP 化简式 (2) PQQ 化简式 (3) PPQ 附加式 (4) PPQ 附加式变形 (5) QPQ 附加式变形 (6) (PQ)P 化简式变形,1.5常用的蕴涵式,(7) (PQ)Q 化简式变形 (8) P(PQ)Q 假言推论 (9) Q(PQ) P 拒取式 (10) P(PQ)Q 析取三段论 (11) (PQ)(QR)PR 条件三段论 (12) (PQ)(QR)PR 双条件三段论,1.5常用的蕴涵式,(13) (PQ)(RS)(PR)QS 合取构造二难 (14) (PQ)(RS)(PR)QS 析取构造二难 特别当QS时，有 (PQ)(RQ)(PR)Q (15) PQ(PR)(QR

19、) 前后件附加,1.6推理规则,定义 若H1H2 Hn C, 则称C是H1, H2, , Hn的有效结论。 特别若A B, 则称B是A的有效结论。 定义说明: 若H1H 2 Hn C, 则从H1H2Hn推出C, 这样的推理是正确的。 但注意推理正确不等于结论为真, 结论的真假还取决于前提H1H2Hn的真假, 前提为真时, 结论C为真; 前提为假时, C可能真也可能假, 这就是定义中只说C是H1H2 Hn的有效结论而不说是正确结论的原因。有效”是指结论的推出是合乎推理规则的。,1.6推理规则,推理方法主要有: 真值表法 等值演算方法 “形式证明”方法 间接证明(或反证法),1.6推理规则,根据上

20、述的推理定律得到，在证明中可使用以下一些推理规则： 1.假言推理规则（分离规则）：若有AB和A，则可得到B。（注意证明是命题公式的序列，因此这里的意思是，如果序列中出现AB和A，则可在该序列中添加公式B，或换句话，按照证明的意思就是，如果有前提AB和A，则可得到结论B） 解释：假言推理规则就是最常用的推理方法，例如，如果天下雨(A)，地就是湿的(B)，现在天下雨，所以地是湿的。,1.6推理规则,2.附加规则：若有A，则可得到AB。 3.化简规则：若有AB，则可得到A，也可得到B。,1.6推理规则,4合取引入规则：若有A和B，则可得到AB。 解释：附加规则、化简规则及合取引入规则的直观含义很简单

21、。,1.6推理规则,5拒取式规则：若有AB和B，则可得到A。 解释：拒取式规则就是通常所使用的反证法，即从A可推出B，但如果我们已经有了B的否定(B)作为前提，那么我们就有理由相信A是成立的。 例如，如果天下雨地就是湿的(AB)，但现在地没有湿(B)，所以天没有下雨(A)。,1.6推理规则,6假言三段论（传递规则）：若有AB及BC，则可得到AC 解释：假言三段论表明推理的传递性，也是常用的一种三段论（亚里斯多德的工具论中共总结出24种三段论的形式）。 例如，如果天下雨(A)，路就会很难走(B)，路很难走，我上学就会迟到(C)，所以如果天下雨我上学就会迟到。,1.6推理规则,7析取三段论规则：若

22、有AB和B，则可得到A。 解释：析取三段论本质上与拒取式一致，但在逻辑上通常称为选言推理，或者更通俗地称为排除法。 例如，今天我要么去开会(A)要么去上课(B)，我不去上课(B)，所以我去开会(A)。实际上这里假定前提AB已罗列了所有可能情况，因为这只是一种推理模式，因此这种假定是合理的，具有一般性。,1.6推理规则,1.6推理规则,8构造性二难规则：若有AB，CD和AC，则可得到BD。 解释：构造性二难推理是析取三段论的推广。 例如如果派小王参加比赛(A)我们就可得到第一名(B)，如果派小张参加比赛(C)就可得到第三名(D)，我们要么派小王去比赛，要么派小张去比赛，所以我们不是得到第一名就是

23、得到第三名。一种极端的二难推理形式是，有AB和AB，那么就可得到B，因为AA是永真的。,1.6老婆定律,构造性二难规则之极端例子：老婆定律 老婆做的饭好吃，先生要赞美（AB） 老婆做的不好吃，先生要赞美（AB） 结论：先生要赞美（B） 数学描述：有AB和AB，那么就可得到B，因为AA是永真的。,1.6推理规则,1.6推理规则总结,P, Q P P, Q Q P,Q P Q P PQ P, (PQ) Q P PQ Q PQ (PQ) P (PQ) Q,1.6推理规则总结,Q, (PQ) P P, (PQ) Q (PQ), (QR) PR (PQ), (QR) PR (PQ), (RS), (PR

24、) QS (PQ), (RQ), (PR) Q PQ (PR)(QR),1.7推理大的基本规则,在证明中常用的推理规则有3条： 1.7.1前提引入规则（规则P） ：在证明的任何步骤都可以引入已知的前提； 1.7.2结论引入规则（规则T） ：在证明的任何步骤都可以引入这次已经得到的结论作为后续证明的前提； 1.7.3置换规则：在证明的任何步骤上，命题公式中的任何子公式都可用与之等值的公式置换，得到证明的公式序列的另一公式。 使用命题逻辑公式进行推理还有其他一些推理规则，这些规则建立在上面一些推理定律上：,1.7CP规则：,P1P2Pn(PQ)形式命题的证明 等价于 P1P2PnPQ, 所以, 只

25、须证明 P1P2PnPQ 这个方法叫CP规则, 也叫演译定理, 因P移作前提, 常使证明简化, 所以经常应用。 这种方法也称为附加前提法,回顾证明:,例题,例 构造下列推理的证明 前提：AB, BC, AD, D，结论：C(AB) 【解答】根据合取引入规则，因为已经有前提AB，所以只要推出结论C即可： (1).AD/ 已知的前提 (2).D / 已知的前提 (3).A / 拒取式 (4).AB / 已知的前提 (5).B / 析取三段论 (6).BC / 已知的前提 (7).C / 分离规则,例题 验证下述推理是否正确：,例 或者逻辑学难学，或者有少数学生不喜欢它；如果数学容易学，那么逻辑学并

26、不难学。因此如果许多学生喜欢逻辑，那么数学并不难学。 【解答】先将命题符号化，首先抽取的基本命题包括： A: 逻辑学难学 B: 有少数学生不喜欢逻辑学 C: 数学容易学 则前提是AB，CA，要证明的结论是BC，可进行如下的验证：,例题,(1).B / 按照演绎定理，引入结论的前件B作为前提 (2).AB / 已知的前提 (3) A / (1)和(2)及析取三段论 (4).CA / 已知的前提 (5).C / (3)和(4)及拒取式 得到结论的后件，因此从前提可有效地推出结论，因此整个推理正确。,1.7推理实例,例. 证明从前提PQ，(QR)可演绎出P 证明 1(1)PP(附加前提) 2(2)P

27、QP 1,2(3)QT,(1)(2)I8 4(4)(QR)T,(4)E5 4(5)QRT,(5)I2 1,2,4(6)QT,(3)(6),1.7推理实例,证明(PQ)，(PR)，(QS)SR PQ 规则1 PQ 规则2，根据1 QS 规则1 PS 规则2，根据2，3 SP 规则2，根据4 PR 规则1 SR 规则2，根据5，6 SR 规则2，根据7。,1.7推理实例,例. 证明RS可从前提P(QS)，RP和Q推导出. 证明 因为RS是条件式, 所以在推理中可用CP规则. 1(1)RPP (附加前提) 2(2)RP 1,2(3)PT,(1)(2)I8 4(4)P(QS)P 1,2,4(5)QST

28、,(3)(4)I8 6(6)QP 1,2,4,6(7)ST,(5)(6)I8 1,2,6(8)RSCP,(2)(7),1.7推理实例,例. 设有下列情况，结论是否有效 （1）或者是天晴，或者是下雨； （2）如果是天晴，我去看电影； （3）如果我去看电影，我就不看书 结论：如果我在看书，则天在下雨 解 令W: 天晴, Q: 下雨, S: 我去看电影, R: 我看书. 本例可符号化为： 前提为W Q，WS，SR, 结论为RQ,1.7推理实例,1(1)RP 2(2)SRP (附加前提) 1,2(3)ST,(1)(2)I8 4(4)WSP 1,2,4(5)W T,(3)(4) I8 6(6) W Q

29、P 6(7)Q 析取三段论 2,4,6(10)RQCP,(1)(9) 结论有效,例 符号化下面语句的推理过程，并指出推理是否正确。“如果甲是冠军，则乙或丙将得亚军；如果乙得亚军，则甲不能得冠军；如果丁得亚军，丙不能得亚军；事实是甲已得冠军，可知丁不能得亚军”。,解 设 A：甲得冠军；B：乙得亚军； C：丙得亚军；D：丁得亚军。,推理过程符号化为 A（BC），B A，DC，A D,1.7推理实例,1.7推理实例,1.7 CP规则应用实例1,例1 证明 ：如果小张和小王去看电影，则小李也去看电影；小赵不去看电影或小张去看电影；小王去看电影。所以，当小赵去看电影时，小李也去看电影。 解：将简单命题符

30、号化： 设 p:小张去看电影。 q:小王去看电影。 r:小李去看电影。 s:小赵去看电影。 前提：(pq)r , sp, q 结论：sr 证明：用附加前提证明法。,1.7 CP规则应用实例1, s 附加前提引入 sp 前提引入 p 析取三段论 (pq)r 前提引入 q 前提引入 pq 合取 r 假言推理,1.7 CP规则应用实例2,例:用附加前提证明法证明下面推理。 前提：P（QR），SP，Q 结论：SR 证明： （1）SP前提引入规则 （2）S附加前提引入规则 （3）P（1）（2）析取三段论规则 （4）P（QR）前提引入规则 （5）QR（3）（4）假言推理规则 （6）Q前提引入规则 （7）R

31、（5）（6）假言推理规则,1.7 CP规则应用实例3,证明: (1) S CP (2) R S P (3) S R (2),E (4) R (1),(3),I (5) P R P (6) R P (5),E (7) P (4),(6),I (8) P Q P (9) P Q (8),E (10) Q (7),(9),I (11) S Q (1),(10),CP,例：前提：P Q, PR,R S;结论：S Q,1.8用推理判定下列推理是否有效,如果下雨，地面就会潮湿，地面没潮湿，所以没下雨。 前提： p q; q. 结论：p (1) p q 前提 (2) p 假设 (3) q (1)(2)蕴涵消

32、去 (4) q 前提 (5) q q (3)(4) 合取引入 (6) p (1)(5) 否定引入(消去假设(2),1.8判定下列推理是否有效,甲、乙、丙、丁四人参加拳击比赛， 若甲获胜，则乙失败；若丙获胜， 则乙也获胜；若甲不获胜，则丁不 失败。所以若丙获胜，则丁不失败。 解：设A：甲获胜， B：乙获胜， C：丙获胜， D：丁获胜。 则命题化为论证：,1.8判定下列推理是否有效,A B，C B， A D C D 证明：1）A B （P） 2）B A （T1),E) (假言易位基本等值式） 3）A D （P） 4）B D (T 2)3),I)(假言三段论规则) 5）C B （P） 6）C D (

33、T4)5),I)(假言三段论规则),1.8判定下列推理是否有效证明：,(p q) (q r) (p r) （1） p q 假设 （2） q r 假设 （3） p 假设 （4） q (1) (3) 蕴涵消去规则 （5） r (2) (4) 蕴涵消去规则 （6） p r (3) (5)蕴涵引入规则(消去了假设(3) ) （7）(q r) (p r ) (2)(6)蕴涵引入规则(消去了假设(2) ) （8）(p q ) ( (q r) (p r ) (1)(7)蕴涵引入规则(消去 了假设(1) ),1.8证明: (p q) (q p),(1) p q 假设 (2) p 假设 (3) q p (2),

34、 析取引入 (4) q 假设 (5) q p (4), 析取引入 (6) q p (1) (2) (3) (4) (5)析取消去规则（消去假设(2) (4)） (7) (p q ) (q p ) (1) (6)蕴涵引入（消去假设(1) ）,判定下列推理是否有效证明：,1.9反证法（归缪法）：,上面的反证法如果推广的话，则有如下定理：,反证法,反证法公式 证明,(P1P2Pk)Q (P1P2Pk) Q (P1P2Pk Q) 若(P1P2Pk Q)为矛盾式，正说明(P1P2Pk) Q为重言式，即 (P1P2Pk) Q, 故推理正确。,反证法举例1,如果小张守第一垒并且小李向B队投球，则A队将取胜；

35、或者A队未取胜，或者A队获得联赛第一名；A队没有获得联赛的第一名；小张守第一垒。因此，小李没有向B队投球。 解 先将简单命题符号化。 设 p:小张守第一垒。 q:小李向B队投球。 r:A队取胜。 s:A队获得联赛第一名。 前提：(pq)r,rs,s ,p 结论：q 证明：用归谬法,反证法举例1, q 结论的否定引入 rs 前提引入 s 前提引入 r 析取三段论 (pq)r 前提引人 (pq) 拒取式 pq 置换 p 前提引入 q 析取三段论 qq 合取 由于最后一步qq F，即(pq)r)(rs)sp)q F，所以推理正确。,反证法举例,例 用反证法证明。 前提：PQ，PR，QS 结论：SR

36、证明 （1）（SR） 附加前提引入规则 （2）SR（1）置换规则 （3）S（2）化简规则 （4）R（2）化简规则 （5）QS 前提引入规则 （6）QS（5）置换规则 （7）Q（3）（6）析取三段论规则,（8）PQ 前提引入规则 （9）P（7）（8）析取三段论规则 （10）PR前提引入规则 （11）PR（10）置换规则 （12）R（9）（11）析取三段论规则 （13）RR（4）（12）合取引入规则,反证法举例,例：证明下列前提是不相容的,若A因病缺了许多课，那么他中学考试失败。 若A中学考试失败，则他没有知识。 若A读了许多书，则他有知识。 A因病缺了许多课，而且读了许多书。,证明：P:”因病缺

37、了许多课”，Q:”中学考试失败”，R:”有知识”，S:”读了许多书” 要证明：PQ,Q R,S R,PS不相容。 编号 公式 依据 P S P P (1);I1 S (1);I2 PQ P Q (2),(4);I9 S R P R (3),(6);I9 Q R P R (5),(8);I9 R R (7),(9),例：张三说李四在说谎，李四说王五在说谎，王五说张三、 李四都在说谎。问张三、李四、王五三人，到底谁说真话，谁说假话？,解 先将简单命题符号化。 令P：张三说真话；Q：李四说真话； R：王五说真话， 由题意知推理的前提为： P Q，PQ，QR， QR， R（P Q）， R（PQ）。 下

38、面根据已知前提进行形式推理。,因此，由上述推理知张三说假话，王五说假话，只有李四说真话。,谓词逻辑的引入,逻辑三段论：凡人要死，苏格拉底是人，所以苏格拉底要死。P：凡人要死Q：苏格拉底是人R：苏格拉底要死此三段论表示为（P Q） R 苏格拉底三段论是正确的，但（P Q） R 却不是重言式，这就是命题逻辑的局限性。,谓词逻辑的引入,命题逻辑虽然可以用来描述一些确定性的事实知识,但它有较大的局限性,它无法把所描述的客观事物的结构及逻辑特征以及关系反映出来,不能把不同事物的共同特征描述出来.,谓词逻辑的引入,例如,对于“张三是李四的老师”,若用英文字母P表示,P只能表达一个或“真”或“假”的值外,无

39、论如何也看不出张三李四之间的师生关系. 又如,对于“贝多芬是作曲家”和“柴可夫斯基是作曲家”这两个命题,用命题逻辑表示时,也无法把两者的共同特征(是作曲家)表示形式的出来.为了消除命题逻辑的局限性,在命题逻辑的基础上发展了谓词逻辑.,一阶逻辑,个体词，谓词和量词是一阶逻辑命题符号化的三个基本要素。 下面讨论这三个要素。,一、个体词,个体词是指所研究对象中可以独立存在的具体的或抽象的客体。例如，小王，小李，中国，鲜花 ，李白,电视机,3等都可以作为个体词。 将表示具体或特定的客体的个体词称作个体常项，一般用小写英文字母a，b，c表示；而将表示抽象或泛指的个体词称为个体变项，常用x，y，z表示。,

40、一、个体词,称个体变项的取值范围为个体域(或称论域)。个体域可以是有穷集合，例如1，2，3，a，b，c，d，a，b，c，x，y，z，；也可以是无穷集合，例如，自然数集合N=0，1，2，实数集合R=x|x是实数。 有一个特殊的个体域，它是由宇宙间一切事物组成的，称它为全总个体域。通常在论述或推理中如没有指明所采用的个体域，都是使用全总个体域。,二、谓词,谓词是用来刻画个体词性质及个体词之间相互关系的词。 考虑下面四个 语句(或命题公式): (1)3是有理数。 (2)x是有理数。 (3)小王与小李同岁。 (4)x与y具有关系L.,二、谓词（续）,在(1)中， 3是个体常项，“是有理数”是谓词，记为

41、F，并用F(3)表示(1)中命题。 在(2)中，x是个体变项，“是有理数”是谓词，记为G，用G(x)表示(2)中语句。 在(3)中，小王，小李都是个体常项，“与同岁”是谓词，记为H，则(3)中命题符号化形式为H(a,b)，其中，a:小王，b:小李。 在(4)中，x，y为两个个体变项，谓词为L，(4)的符号化形式为L(x,y).,二、谓词（续）,同个体词一样，谓词也有常项和变项之分。表示具体性质或关系的谓词称为谓词常项，表示抽象的、泛指的性质或关系的谓词称为谓词变项。 无论是谓词常项或变项都用大写英文字母F，G，H，表示，可根据上下文区分。在上面四个命题中，(1)，(2)，(3)中谓词F，G，H

42、是常项，而(4)中谓词L是变项。,二、谓词（续）,一般的，用F(a)表示个体常项a具有性质F(F是谓词常项或谓词变项)，用F(x)表示个体变项x具有性质F. 而用F(a，b)表示个体常项a，b具有关系F，用F(x,y)表示个体变项x，y具有关系F. 更一般的，用P(x1,x2,xn)表示含n(n1)个命题变项的n元谓词。 n=1时，P(x1)表示x1具有性质P； n2时，P(x1,x2,xn)表示x1,x2,xn具有关系P.,二、谓词（续）,实质上，n元谓词P(x1,x2,xn)可以看成以个体域为定义域，以0,1为值域的n元函数或关系。 需要特别注意的是： n元谓词P(x1,x2,xn)不是命

43、题。 要想使它成为命题，必须用谓词常项取代P，用个体常项a1,a2,an取代x1,x2,xn，得P(a1,a2,an)是命题。,二、谓词（续）,有时候将不带个体变项的谓词称为0元谓词。 例如，F(a)，G(a,b)，P(a1,a2,an)等都是0元谓词。当F，G，P为谓词常项时，0元谓词为命题。 这样一来，命题逻辑中的命题均可以表示成0元谓词，因而可以将命题看成特殊的谓词。,三、量词,有了个体词和谓词之后，有些命题还是不能准确的符号化，原因是还缺少表示个体常项或变项之间数量关系的词。 称表示个体常项或变项之间数量关系的词为量词。,(1) 全称量词,日常生活和数学中所用的“一切的”，“所有的”，

44、“每一个”，“任意的”，“凡”，“都”等词可统称为全称量词，将它们符号化为“ ”。并用 x， y等表示个体域里的所有个体，而用 xF(x)， yG(y)等分别表示个体域里所有个体都有性质F和都有性质G。,(2) 存在量词,日常生活和数学中所用的“存在”，“有一个”，“有的”，“至少有一个”等词统称为存在量词，将它们都符号化为“ ”。 并用 x， y等表示个体域里有的个体，而用 xF(x)， yG(y)等分别表示个体域里存在个体具有性质F和存在个体具有性质G等。,一阶逻辑命题符号化,例 在个体域分别限制为(a)和(b)条件时，将下面两个命题符号化: (1) 凡人都呼吸。 (2) 有的人用左手写字

45、。 其中:(a)个体域D1为人类集合； (b)个体域D2为人类集合。,例题4,解 令F(x):x呼吸。G(x):x用左手写字。 (1) 在D1中除了人外，再无别的东西，因而“凡人都呼吸”应符号化为 xF(x) (2) 在D1中的有些个体(人)用左手写字，因而“有的人用左手写字”符号化为 xG(x),例题5,将下列命题符号化，并讨论真值。 (1)所有的人都长着黑头发。(2)有的人登上过月球。 (3)没有人登上过木星。(4)在美国留学的学生未必都是亚洲人。,例题5（续）,解 由于本题没有提出个体域，因而应该采用全总个体域，并令M(x):x为人。(1)令F(x):x长着黑头发。命题(1)符号化为 x

46、(M(x)F(x)设a为某个金发姑娘，则M(a)为真，而F(a)为假，所以M(a)F(a)为假，故(4.9)所表示的命题为假。,例题5（续）,(2)令G(x):x登上过月球。命题(2)的符号化形式为 $ x(M(x)G(x) 设a是1969年登上月球完成阿波罗计划的一个美国人，则M(a)G(a)为真，所以上式表示的命题为真。,例题5（续）,(3)令H(x):x登上过木星。命题(3)符号化形式为 $ x(M(x)H(x) 到目前为止，对于任何一个人(含已经去世的人)都还没有登上过木星，所以对任何人a，M(a)H(a)均为假，因而$x(M(x)H(x)为假，所以表示的命题为真。,例题5（续）,(4

47、)令F(x):x是在美国留学的学生，G(x):x是亚洲人。命题(4)符号化形式为 x(F(x)G(x)这个命题也为真。,例题6,将下列命题符号化: (1) 兔子比乌龟跑得快。 (2) 有的兔子比所有的乌龟跑得快。 (3) 并不是所有的兔子都比乌龟跑得快。 (4) 不存在跑得同样快的两只兔子。,例题6（续）,本题没有指明个体域，因而采用全总个体域。因为本例中出现二元谓词，因而引入两个个体变项x与y.令F(x):x是兔子，G(y):y是乌龟，H(x,y):x比y跑得快，L(x,y):x与y跑得一样快。 这4个命题分别符号化为：,自由与约束,定义 在公式 xA和 $ xA中，称x为指导变元，A为相应

48、量词的辖域。在 x和 $ x的辖域中，x的所有出现都称为约束出现。A中不是约束出现的其他变项均称为是自由出现的。,例题7,指出下列各公式中的指导变元，各量词的辖域，自由出现以及约束出现的个体变项: (1)x是指导变元。量词 的辖域A=(F(x,y)G(x,z)，在A中， x是约束出现的。而且约束出现两次，y和z均为自由出现的，而且各自由出现一次。,例题7,(2)公式中含有两个量词，前件上的量词 的指导变元为x， 的辖域A=(F(x)G(y)，其中x是约束出现的，y是自由出现的。后件中的量词$ 的指导变元为y， 的辖域为(H(x)L(x,y,z)，其中y是约束出现的，x，z均为自由出现的。在整个

49、公式中，x约束出现一次，自由出现2次，y自由出现一次，约束出现一次，z只自由出现一次。,例：指出各公式的指导变元，辖域、约束变元和自由变元,x(p(x)yQ(x,y) x(x=yx2+x5xz)x=5y2,换名规则,换名规则：对约束变元进行换名。 将量词辖域内出现的某个约束变元及其相应量词中的指导变元,可以换成一个其他变元,改变元不能与本辖域内的其他变元同名,公式中的其他部分不改变。,例:,对于x(P(x，y)Q(x，z)，改名为u(P(u,y)Q(u，z)。但下面的改名都是不对的： a. u(P(u，y)Q(x，z) b. x(P(u，y)Q(u，z) c. u(P(x，y)Q(x，z) d

50、. y(P(y，y)Q(y，z) e. z(P(z，y)Q(z，z),解需对x，y换名,错误法：,例对公式 进行换名，使各变元只呈一种形式出现。,说明：,(1)当多个量词连续出现，它们之间无括号分隔时，约定从左到右的次序读出，后面的量词在前面量词的辖域之中。 yx(x(y-2),x,y的个体域为实数集。,说明：,(2)如果D是有限集,谓词公式中的量词可以用逻辑联结词来解释。 例D=a,b,c xP(x) P(a) P(b) P(c) x P(x) P(a) P(b) P(c),说明：,(3)量词不能随便换顺序。对于和这两个量词交换位置,其意义不同了,相应真值也可能改变。 例：D：自然数全体,G

51、(x,y)：x小于y。 xyG(x,y)表示任意一个自然数x,总存在自然数y,使得x小于y,该命题是真的。 yxG(x,y)表示存在一个自然数y,使得对一切自然数x,使x小于y,即y是最大的自然数。该命题是假的。,代入规则 对于公式中自由变元的更改叫做代入。,谓词公式,项：（1）个体变元和个体常元是项。 （2）对任意正整数n，如果f (n)为一n元函数符，t1 , ,tn为项，那么f (n)(t1,tn)也是项。 （3）除有限次使用（1），（2）条款所确定的符号串外，没有别的东西是个体项。,原子公式的定义 原子公式是公式的最小单位，最小的句子单位。项不是公式。 定义：若P(x1,.,xn)是n

52、元谓词，t1,.，tn是项，则P(t1,.，tn)为原子公式。 （1）从中可以看出，项也可以出现在谓词的变量位置，相当于名词，可以做句子的主语或宾语。 （2）函数f(t1,.，tn)不是句子，仅是词，因而不是公式仅是项。项的结果仍是个体名称集中的名词，而公式的结果（真值）是成立或不成立（是1或0）。,谓词公式的定义,定义：谓词公式的递归定义如下： （1）原子公式是合式公式； (2)如A，B是公式，则A, AB, AB, AB, AB也是公式； （3）如A是谓词公式，x是A中出现的任意有关个体变元，则xA,xA也是谓词公式。 （4）只有有限次使用（1）（2）（3）生成的符号串才是合式公式（也称谓

53、词公式） 例：H(a,b), C(x)B(x), x(M(x)H(x), x(M(x)C(x)B(x), 等均是合式公式。,谓词公式的解释,定义 谓词逻辑中公式G的一个解释I，是由非空区域D和对G中常量符号，函数符号，谓词符号以下列规则进行的一组指定组成： 1. 对每个常量符号，指定D中一个元素； 2. 对每个n元函数符号，指定一个函数，即指定Dn到D的一个映射； 3. 对每个n元谓词符号，指定一个谓词，即指定Dn到0，1的一个映射。,谓词公式的解释,在谓词逻辑中，由于涉及变量和函数，不可能直接给原子公式指派真值，必须先定义一个拟观察个体的可能论域，并确定原子公式中变量项和函数项在论域中的取值

54、，然后才能给原子公式指派真值。,例:,给出如下两个公式：1) G=x(P(f(x) Q(x，f(a)2) H=x(P(x)Q(x，a) 给出如下的解释I：D=2，3 a 2 f(2) f(3) 3 2 P(2) P(3) Q(2, 2) Q(2, 3) Q(3, 2) Q(3, 3) 0 1 1 1 0 1,例:,TI(G)= TI(P(f(2)Q(2，f(2) (P(f(3)Q(3，f(2)= TI(P(3)Q(2，3)(P(2)Q(3，3)=(11)(00)=1 TI(H)= TI(P(2)Q(2，2)P(3)Q(3，2)=0110=0,一阶公式的解释,一般情况下，谓词公式的真值都是针对某

55、一个解释而言的。同一个公式可能一种解释下为T，而在另一种解释下为F。,谓词公式的永真性和可满足性,1） 谓词公式的永真性 若某合适公式P对于某论域D上的所有可能的解释都有真值T，则称P在D上是永真的；若P在每个可能的非空论域上均永真，则称P是永真的。 2） 谓词公式的可满足性对于合适公式P，若在论域D上至少可以建立一个解释，使P有真值T，则称P在D上是可满足的；若至少有一个论域使P可满足，则称P是可满足的。,谓词公式的永真性和可满足性,3） 合适公式的永假性若某合适公式P对于论域D上的所有可能的解释都有真值F，则称P在D上是永假的(即不可满足的)；若P在每个可能的非空论域上均永假，则称P是永假

56、的。,谓词公式的永真性和可满足性,显然，在可能的论域个数较少，每个论域自身又较小（包含个体对象较少）的情况下，易于判断合适公式的永真性和可满足性； 即使论域个数较多，每个论域较大，只要解释的个数有限，永真性和可满足性总是可判定的。 但若解释的个数无限时，就不能确保可以判定，或者不能确保在有限的时间内判定。,谓词等价公式和蕴涵公式,定义 设A,B是个体域D上的两个公式，若对于A和B的任意一组指派，两公式都具有相同的真值，则称公式A和B在D上等值，记作AB。 定义 对于公式A和B，若AB1,则称公式A蕴涵公式B，记作AB。,命题逻辑中结论的推广,在命题逻辑中成立的基本等值式和基本重言蕴含式及其代换

57、实例都是谓词逻辑的等值式和重言蕴含式。 例：幂等律 xA(x)xA(x) xA(x) 蕴含律 x(A(x)B)x(A(x)B),量词转换律,(1)(xA(x) x(A(x) (2)(xA(x) ) x(A(x) 在D=a，b，c时 (1)式左边xA(x) (A(a) A(b) A(c) (1)式右边xA(x) A(a) A(b) A(c) 比较两公式可得(1)在命题逻辑中相当于德.摩根律,量词否定公式的推导,说明：,(1)在谓词演算中只要有一个量词就够了； (2)量词前面的否定符号可深入至量词辖域内，但与此同时必须将存在量词和全称量词作对换。,量词辖域的扩张和收缩,(1) x ( A(x) B) x A(x) B (2) x ( A(x) B) x A(x) B (3) x ( A(x) B) x A(x) B (4) x ( A(x) B) x A(x) B 说明：1、，在，逻辑词下，辖域可以扩充到一切不含该指导变元的任意原子公式上，推广的有 x A(x) B(y)x (A(x) B(y)。两个条件：1、B中不含指导变元x 2、只能与，,(5)x(A(x) B) xA(x) B (6)x(B A(