《离散数学-数理逻辑.ppt》由会员分享，可在线阅读，更多相关《离散数学-数理逻辑.ppt（86页珍藏版）》请在三一办公上搜索。
1、1,离 散 数 学,杨 敏 武汉大学国际软件学院,2,教材与参考资料,教材：离散数学（第2版），屈婉玲、耿素云、张立昂编，清华大学出版社参考资料：离散数学，刘玉珍、刘咏梅编，武汉大学出版社Discrete Mathematical Structures(Sixth Edition)，Bernard Kolman,Fobert C.Busby and Sharon Ross，高等教育出版社有影印版、译本Discrete Mathematics and Its Applications(Sixth Edition)，美Kenneth H.Rosen，机械工业出版社影印版、译本,3,课程主要内容,数
2、理逻辑集合论图论代数系统*,4,目的、意义和要求,研究内容：离散量的结构及其相互间的关系。意义：计算机科学的理论基础。目的：打基础必备的数学知识培养抽象思维能力、逻辑推理能力教学内容：第1-7 章重点第9、14章备选第8、11章自学第10、12、13章不要求,5,学习要求,1、课堂要求：按时上课 认真听讲2、课外要求：复习(每次课后，安排半个小时)认真、按时完成作业(每次课后，安排1个小时),6,学习考查方法,1、出勤率：10%不定期检查出勤情况2、作业完成情况：10%对作业完成情况进行登记3、课堂测验+期中考试：20%共 5 次4、期末考试（闭卷）：60%,7,第一篇 数理逻辑第1章 导 论
3、,数理逻辑的概念数理逻辑的发展简史数理逻辑的地位和作用,8,（1）定义,1.1 数理逻辑的概念,数理逻辑是采用数学方法研究抽象思维推理规律（形式推理）的一门科学。命题逻辑是数理逻辑的基本组成部分之一推理的基本要素是命题把命题作为基本单位来分析,符号化,研究公式间的关系,推导、演算,9,（2）方法,引入一套数学符号系统来进行研究，强调推理过程中前提和结论之间的形式关系。,例：A、B、C、D4人做百米竞赛，观众甲、乙、丙预报比赛结果的名次为：甲：C第一，B第二乙：C第二，D第三丙：A第二，D第四比赛结束后发现甲乙丙每人报告的情况都各对一半，试问实际名次如何？,1.引入pi,qi,ri,si分别表示
4、“A排名第i，B排名第i，C排名第i，D排名第i”2.给出个命题之间的关系（1）(r1 q2)(r1 q2)1（2）(r2 s3)(r2 s3)1（3）(p2 s4)(p2 s4)13.通过演算规则，得出结果,10,（3）内容,谓词逻辑,命题逻辑,11,（4）分支,模型论,证明论,公理集合论,递归论,12,1.2 数理逻辑的发展简史,创立阶段,起源阶段,完善阶段,发展历史,13,起源阶段,德国数学家、哲学家 G.Leibniz（16461716），提出建立一种普遍的符号语言，利用符号语言进行思维演算的设想。,14,创立阶段,英国数学家 G.Bool于1847年发表逻辑的数学分析，创建一套表示逻
5、辑推理的基本符号以及符号的运算规律，建立了布尔代数。,德国数学家 G.Frege于1879年在概念的演算一书中引进谓词符号和量词符号，创建第一个比较严格的逻辑演算系统。,15,完善阶段,英国逻辑学家 和B.Russel于1910将当时的数理逻辑写入了数学原理中，使数理逻辑成为了一门专门的学科。,20 世纪 30 年代，由于众多科学家的努力，衍生出许多新的分支，如：直觉主义逻辑、多值逻辑、组合逻辑等。,16,1.3 数理逻辑的地位和作用,1、计算机科学的重要的理论基础之一；2、对数学、计算机科学、人工智能、语言学、控制论等诸多学科产生深远的影响。3、在计算机科学中的应用：软件、硬件设计,17,第
6、2章 命题逻辑,2.1 命题逻辑基本概念 2.2 命题逻辑等值演算 2.3 范式2.4 命题逻辑推理理论,18,2.1 命题逻辑基本概念,2.1.1 命题与联结词命题与真值(简单命题,复合命题)联结词(,)命题公式及其分类命题公式及其赋值真值表命题公式的分类,19,2.1.1 命题与联结词,1、命题及相关概念（1）命题的定义,两者必居其一且只居其一二值逻辑,命题定义的理解：从两个方面把握这个概念（1）陈述句；（2）真值唯一性（注意：真值可能目前还不知道答案）。,命题：一个具有真假意义的陈述句。,什么是真值：只包含真/假两个值的量。T/1真 F/0假,20,注意：（1）感叹句、祈使句、疑问句都不
7、是命题（2）陈述句中的悖论以及判断结果不唯一确定的也不是命题,21,中国的首都在北京。1+1=10请开门！x+y=1明年10月1日是晴天。本命题是假的。李红既学英语又学日语。,例1 判断下列个自然语言是否是命题,22,（2）几个基本概念 真命题与假命题 命题变元与命题常元,真命题:真值为真的命题 假命题:真值为假的命题,若p即可以表示真命题，又可以表示假命题，则称p为命题变元。T永远表示真命题，F表示假命题，称T和F为命题常元。,23,例2,真命题,假命题,真值不确定,疑问句,感叹句,祈使句,悖论,(1),(2),(5)是命题,(3),(4),(6)(8)都不是命题,真值确定,但未知,下列句子
8、中哪些是命题？并指出命题的真值。(1)北京是中华人民共和国的首都.(2)2+5 8.(3)x+5 3.(4)你会开车吗？(5)2050年元旦北京是晴天.(6)这只兔子跑得真快呀！(7)请关上门！(8)我正在说谎话.,24,（1）简单命题与复合命题（2）联结词的定义（3）联结词的优先级,2.联接词,25,（1）简单命题与复合命题,简单命题(原子命题):简单陈述句构成的命题。简单命题的符号化:用p,q,r,pi,qi,ri(i1)表示 用“1”表示真，用“0”表示假复合命题:由简单命题通过联结词联结而成的陈述句。例如 如果明天天气好,我们就出去郊游 设p:明天天气好,q:我们出去郊游,如果p,则q
9、 又如 张三一面喝茶一面看报 设p:张三喝茶,q:张三看报,p并且q,26,（2）联结词的定义,否定词（）,定义2.1 设p为命题，复合命题“非p”(或“p的否定”)称为p的否定式，记作p，符号称作否定联结词,并规定p为真当且仅当 p为假。,例如 p:2是合数,p:2不是合数。p为假,p为真。,27,合取词（）,定义2.2 设p,q为二命题,复合命题“p并且q”(或“p与q”)称为p与q的合取式,记作pq,称作合取联结词,并规定 pq为真当且仅当 p与q同时为真.,例如 p:2是偶数,q:2是素数,pq:表示的含义是2是偶素数。因为p为真,q也为真，所以 pq为真。,28,例3 将下列命题符号
10、化.,解：记 p:王晓用功,q:王晓聪明,(1)pq,(2)pq,(3)qp,(4)记 r:张辉是三好生,s:王丽是三好生,rs,(5)简单命题,记 t:张辉与王丽是同学,(1)王晓既用功又聪明.(2)王晓不仅聪明，而且用功.(3)王晓虽然聪明，但不用功.(4)张辉与王丽都是三好生.(5)张辉与王丽是同学.,29,析取词（）,定义2.3 设 p、q为命题，复合命题“p或q”称作p与q的析取式，记作pq,称作析取联结词,并规定pq为假当且仅当p与q同时为假。,例如 张三和李四至少有一人会英语设 p:张三会英语,q:李四会英语,符号化为pq。,30,相容或与排斥或,析取词表示的是相容或，即 p 和
11、 q 均为真时(p q)亦为真，而与之对应的还有一个是排斥或，它表示的含义是p 和 q 不能同时为真。,例如 这件事由张三和李四中的一人去做 设 p:张三做这件事,q:李四做这件事 应符号化为(p q)(p q),31,例4 将下列命题符号化，并指出其真值,解：记 p:2是素数,q:3是素数,r:4是素数,s:6是素数,(1)pr,(2)pq,(3)rs,(4)记t:元元拿一个苹果,u:元元拿一个梨,真值:1,真值:1,真值:0,(tu)(tu),(5)记v:王晓红生于1975年,w:王晓红生于1976年,(vw)(vw),又可形式化为 vw,(1)2或4是素数.(2)2或3是素数.(3)4或
12、6是素数.(4)元元只能拿一个苹果或一个梨.(5)王晓红生于1975年或1976年.,32,蕴涵词（）,定义2.4 设 p,q为二命题,复合命题“如果p,则q”称作p与q的蕴涵式,记作pq,并称p是蕴涵式的前件,q为蕴涵式的后件.称作蕴涵联结词,并规定,pq为假当且仅当 p为真且q为假.,例如 如果明天天气好,我们就出去郊游 设p:明天天气好,q:我们出去郊游,形式化为 pq,33,蕴涵词的其它表述方式,pq 的逻辑关系:q为p的必要条件,p为q的充分条件。“如果p,则q”的多种表述方式：若p,就q 只要p,就q p仅当q 只有q 才p 除非q,才p 除非q,否则非p当p为假时，pq为真(不管
13、q为真,还是为假),34,例5 设p:天冷,q:小王穿羽绒服，将下列命题符号化,注意：pq 与 qp 等值（真值相同）,pq,pq,qp 或 pq,pq,qp,qp,pq 或 qp,qp,(1)只要天冷，小王就穿羽绒服.(2)因为天冷，所以小王穿羽绒服.(3)若小王不穿羽绒服，则天不冷.(4)只有天冷，小王才穿羽绒服.(5)除非天冷，小王才穿羽绒服.(6)除非小王穿羽绒服，否则天不冷.(7)如果天不冷，则小王不穿羽绒服.(8)小王穿羽绒服仅当天冷的时候.,35,等价词（）,定义2.5 设p,q为命题,复合命题“p当且仅当q”称作p与q的等价式,记作pq,称作等价联结词.并规定pq为真当且仅当
14、p与q同时为真或同时为假。,pq 的逻辑关系:p与q互为充分必要条件例如 这件事张三能做好,且只有张三能做好 设p:张三做这件事,q:这件事做好了 形式化为:pq,36,例6 求下列复合命题的真值：,1,0,1,1,(1)2+24 当且仅当 3+36.(2)2+24 当且仅当 3是偶数.(3)2+24 当且仅当 太阳从东方升起.(4)2+25 当且仅当 美国位于非洲.,37,分析找出简单命题,用字母表示简单命题,用联接词联接命题符号,命题符号化的一般规则,38,分析找出简单命题,用字母表示简单命题,用联接词联接命题符号,解 令 p:我上街 q:我累 r:我去书店看看 则可符号化为：（pq)r,
15、例7 将下列命题符号化：如果我上街并且我不累，我就去书店看看。,简单命题：我上街。我累。我去书店看看。,39,例8 试将下列命题符号化：如果你不看电影，那么我也不看电影小王一边吃饭，一边看书,解:（1）设p：你看电影，q：我看电影，则：p q（2）设p：小王吃饭，q：小王看书，则：pq,40,（3）联结词的优先级,联结词优先级:(),同级按从左到右的顺序进行,41,1、分析下列各命题的真值（1）2+2=4当且仅当3是奇数（2）2+2=4当且仅当3不是奇数（3）2+24当且仅当3是奇数（4）2+24当且仅当3不是奇数,2、将下列命题符号化（1）小王是游泳冠军或者百米赛跑冠军（2）小王现在在宿舍或
16、者在图书馆（3）选小王或者小李中的一人当班长（4）如果我上街，我就去书店看看，除非我很累,课堂练习（1）,42,课堂练习（2）,3、将下列命题符号化（1）李平既聪明又用功（2）李平虽然聪明，但不用功（3）李平不但聪明，而且用功（4）李平不是不聪明，而是不用功,4、将下列命题符号化（1）只要不下雨，我就骑自行车上班（2）只有不下雨，我才骑自行车上班（3）若2+2=4，则太阳从东方升起（4）若2+24,则太阳从东方升起,43,2.1.2 合式公式及其分类,1.命题语言的字母表：2.合式公式的基本概念3.真值表4.合式公式的分类,44,1.命题语言的字母表,命题语言的字母表：命题常元：T,F(或 1
17、，0)命题变元：p1,p2,pn联接词：，辅助符号：（）,45,（1）合式公式(命题公式,公式)的定义,定义2.6 合式公式递归定义如下：(1)单个命题常项或变项是合式公式，并称作原子合式公式；(2)若A是合式公式,则(A)也是合式公式；(3)若A,B是合式公式,则(AB),(AB),(AB),(AB)也是合式公式；(4)只有有限次地应用(1)(3)形成的符号串才是合式公式。,2、合式公式的基本概念,说明:(1)元语言符号与对象语言符号(2)在不影响运算顺序时,括号可以省去 例如 0,p,pq,(pq)(pr),pq r,(pq)r,46,（2）合式公式的层次,定义2.7(1)单个命题变项或命
18、题常项是0层公式(2)称A是n+1(n0)层公式是指下面情况之一：(a)A=B,B是n层公式(b)A=BC,其中B,C分别为i层和j层公式,且 n=max(i,j)(c)A=BC,其中B,C的层次及n同(b)(d)A=BC,其中B,C的层次及n同(b)(e)A=BC,其中B,C的层次及n同(b),例如 p 0层 p 1层 pq 2层(pq)r 3层(pq)r)(rs)4层,47,（3）公式的赋值,定义2.8 设 p1,p2,pn是出现在公式A中全部的命题变项，给 p1,p2,pn指定一组真值，称为对A的一个赋值或解释。使公式为真的赋值称作成真赋值,使公式为假的赋值称作成假赋值。,说明:(1)赋
19、值记作=12n，其中i=0或1，诸i之间不加标点符号；(2)通常赋值与命题变项之间按下标或字母顺序对应,即：当A的全部命题变项为p1,p2,pn时,给A赋值12n是指 p1=1,p2=2,pn=n;当A的全部命题变项为p,q,r,时,给A赋值123是指p=1,q=2,r=3,48,实例,例8 公式A=(p1 p2 p3)(p1 p2)000是成真赋值,001是成假赋值 公式B=(pq)r 000是成假赋值,001是成真赋值,49,3、真值表,真值表:命题公式在所有可能的赋值下的取值的列表。含n个变项的公式有2n个赋值,用0或1表示公式中命题变元的取值，并依据联结词的逻辑规则计算出复合命题（公式
20、）的真值，用一个对应表表示的一种方法。,50,基本复合命题真值表汇总,51,例9 给出公式的真值表(1)(qp)qp；(2)(pq)q；(3)(pq)r.,例9,52,(2)(pq)q,53,(3)(pq)r,54,4、命题公式的分类,重言式(永真式):无成假赋值的命题公式矛盾式(永假式):无成真赋值的命题公式可满足式:非矛盾式的命题公式注意:重言式是可满足式，但反之不真.例如 上例中(1)(qp)qp为重言式(2)(pq)q为矛盾式(3)(pq)r为非重言式的可满足式,55,2、判断下列命题公式的类型（1）（2）,课堂练习,1、构造下列命题公式的真值表（1）（2）,56,2.2 命题逻辑等值
21、演算,2.2.1 等值式与等值演算等值式基本等值式等值演算2.2.2 联结词完备集真值函数联结词完备集与非联结词和或非联结词,57,2.2.1 等值式与等值演算,1、等值式的定义,定义2.11 若等价式AB是永真式,则称A与B等值,记作AB,并称AB是等值式。,58,(1)是元语言符号,不要混同于和=。(2)A与B等值当且仅当A与B在所有可能赋值下的真值都相同,即A与B有相同的真值表。(3)可能有哑元出现.在B中出现,但不在A中出现的命题变项称作A的哑元.同样,在A中出现,但不在B中出现的命题变项称作B的哑元.哑元的值不影响命题公式的真值。,说明,59,2、性质,(1)A A(2)若A B，则
22、 B A(3)若A B且B C，则 A C,60,3、真值表法判断公式是否等值,结论:(pq)(pq),例1 判断(pq)与 pq 是否等值解,61,p(qr)与(pq)r等值,但与(pq)r不等值,例2 判断下述3个公式之间的等值关系:p(qr),(pq)r,(pq)r解,62,4、基本等值式,（1）双重否定律：,（2）等幂律：,63,（3）交换律：,（4）结合律：,（5）分配律：,（6）德 摩根定律：,64,（7）吸收律：,（8）蕴含等值式：,（9）等价等值式：,65,（10）零律：,（11）同一律：,（12）排中律：,66,（13）矛盾律：,（14）等价否定等值式：,（15）归谬律：,（
23、16）假言易位：,67,(1)代入规则 代入规则：对于重言式中的任一命题变元出现的每一处均用同一命题公式代入，得到的仍是重言式。,例如 F=（pq）（qp）是重言式，若用公式rs代换命题变元p得公式 F1=（rs）q）（q（rs），F1仍是重言式。,注意：因为A B当且仅当A B是重言式。所以，若对于等值式中的任一命题变元出现的每一处均用同一命题公式代入，则得到的仍是等值式。,5、等值演算,68,(2)置换规则,例如 设公式A=（PQ）（PQ）（RS）。,则PQ，PQ，（PQ）（RS）等均是A的子公式，,置换规则：设C是公式A的子公式，CD。如果将公式A中的子公式C置换成公式D之后，得到的公式
24、是B，则AB。,子公式：设C是命题公式A的一部分（即C是公式A中连续的几个符号），且C本身也是一个命题公式，则称C为公式A的子公式。,69,(3)等值演算 等值演算是指利用已知的一些等值式，根据置换规则、代入规则以及等值关系的可传递性推导出另外一些等值式的过程。,例3 证明 p(qr)(pq)r证 p(qr)p(qr)（蕴涵等值式）(pq)r（结合律）(pq)r（德摩根律）(pq)r（蕴涵等值式）,70,例4：证明（AB)(BA)是永真式。证明:(A B)(B A)蕴涵等值式(AB)(BA)德摩根律、双重否定律(AB)(BA)分配律(ABA)(BBA)交换律、结合律、补余律 T（AB)(BA)
25、是永真式,71,（同一律）,（排中律）,（分配律）,证明,例5,证：,72,例6 用等值演算法判断下列公式的类型(1)q(pq)解 q(pq)q(pq)（蕴涵等值式）q(pq)（德摩根律）p(qq)（交换律，结合律）p0（矛盾律）0（零律）该式为矛盾式.,73,例6(续),(2)(pq)(qp)解(pq)(qp)(pq)(qp)（蕴涵等值式）(pq)(pq)（交换律）1该式为重言式.,74,例6(续),(3)(pq)(pq)r)解(pq)(pq)r)(p(qq)r（分配律）p1r（排中律）pr（同一律）非重言式的可满足式.如101是它的成真赋值,000是它的成假赋值.,总结:A为矛盾式当且仅当
26、A0;A为重言式当且仅当A1说明:演算步骤不惟一,应尽量使演算短些,75,例7：应用题,某勘探队有3名队员，有一天取得一块矿样，3人的判断如下：甲说：这不是铁，也不是铜 乙说：这不是铁，是锡 丙说：这不是锡，是铁 经过实验鉴定后发现，其中一人2个判断都是正确的，一人判断对了一半，另外一个人全错了。根据以上情况判断矿样的种类。,76,解：设 p：矿样为铁，q：矿样为铜，r：矿样为锡，则可得：,77,78,79,等值演算不能直接证明两个公式不等值.证明两个公式不等值的基本思想是找到一个赋值使一个成真,另一个成假.例8 证明:p(qr)(pq)r方法一 真值表法方法二 观察法.容易看出000使左边成
27、真,使右边成假.方法三 先用等值演算化简公式,再观察.,80,2、证明,3、证明 是永真式。,课堂练习,1、证明,用等值演算证明：,81,2.2.2 联结词完备集,1、真值函数,n元真值函数共有 个每一个命题公式对应于一个真值函数每一个真值函数对应无穷多个命题公式,定义2.12 称F:0,1n0,1为n元真值函数,82,2元真值函数,83,定义2.13 设S是一个联结词集合,如果任何n(n1)元真值函数都可以由仅含S中的联结词构成的公式表示,则称S是联结词完备集定理2.1 下述联结词集合都是完备集:(1)S1=,(2)S2=,(3)S3=,(4)S4=,(5)S5=,(6)S6=,2、联结词完备集,84,举例,AB(AB)(BA),AB AB,AB(AB)(AB),AB(AB),AB(A)B AB,85,与非、或非,与非式:pq(pq),称作与非联结词或非式:pq(pq),称作或非联结词pq为真当且仅当p,q不同时为真pq为真当且仅当p,q同时为假定理2.2,是联结词完备集证 p(pp)pp pq(pq)(pq)(pq)(pq)得证是联结词完备集.对于可类似证明.,86,P80-81：2.10，2.12，2.13（2），2.15（1），2.16，2.18（1），2.19（2），2.20，2.21（1），2.22（2），2.23（1）（3）,本节习题,
