离散数学-数理逻辑.ppt

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,课程主要内容,数理逻辑 集合论 图论 代数系统*,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章 导 论,数理逻辑的概念 数理逻辑的发展简史 数理逻辑的地位和作用,8,（1）定义,1.1 数理逻辑的概念,数理逻辑是采用数学方法研究抽象思维推理规律（形式推理）的一门科学。 命题逻辑是数理逻辑的基本组成部分之一 推理的基本要素是命题 把命题作为基本单位来分析,符号化,研究公式间的关系,推导、演算,9,（2）方法,引入一套数学符号系统来进行研究，强调推理过程中前提和结论之间的形式关系。,例：A、B、C、D4人做百米竞赛，观众甲、乙、丙预报比赛结果的名次为： 甲：C第一，B第二 乙：C第二，D第三 丙：A第二，D第四 比赛结束后发现甲乙丙每人报告的情况都各对一半，试问实际名次如何？,1.引入pi,qi,ri,si分别表示“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) 1 3.通过演算规则，得出结果,10,（3）内容,谓词逻辑,命题逻辑,11,（4）分支,模型论,证明论,公理集合论,递归论,12,1.2 数理逻辑的发展简史,创立阶段,起源阶段,完善阶段,发展历史,13,起源阶段,德国数学家、哲学家 G.Leibniz（16461716），提出建立一种普遍的符号语言，利用符号语言进行思维演算的设想。,14,创立阶段,英国数学家 G.Bool于1847年发表逻辑的数学分析，创建一套表示逻辑推理的基本符号以及符号的运算规律，建立了布尔代数。,德国数学家 G.Frege于1879年在概念的演算一书中引进谓词符号和量词符号，创建第一个比较严格的逻辑演算系统。,15,完善阶段,英国逻辑学家 A.N.Witehead和B.Russel于1910将当时的数理逻辑写入了数学原理中，使数理逻辑成为了一门专门的学科。,20 世纪 30 年代，由于众多科学家的努力，衍生出许多新的分支，如：直觉主义逻辑、多值逻辑、组合逻辑等。,16,1.3 数理逻辑的地位和作用,1、计算机科学的重要的理论基础之一； 2、对数学、计算机科学、人工智能、语言学、控制论等诸多学科产生深远的影响。 3、在计算机科学中的应用：软件、硬件设计,17,第2章 命题逻辑,2.1 命题逻辑基本概念 2.2 命题逻辑等值演算 2.3 范式 2.4 命题逻辑推理理论,18,2.1 命题逻辑基本概念,2.1.1 命题与联结词 命题与真值(简单命题, 复合命题) 联结词(, , , , ) 2.2.2 命题公式及其分类 命题公式及其赋值 真值表 命题公式的分类,19,2.1.1 命题与联结词,1、命题及相关概念 （1）命题的定义,两者必居其一且只居其一 二值逻辑,命题定义的理解：从两个方面把握这个概念（1）陈述句； （2）真值唯一性（注意：真值可能目前还不知道答案）。,命题：一个具有真假意义的陈述句。,什么是真值：只包含真/假两个值的量。 T/1真 F/0假,20,注意：（1） 感叹句、祈使句、疑问句都不是命题 （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)都不是命题,真值确定, 但未知,下列句子中哪些是命题？并指出命题的真值。 (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 又如 张三一面喝茶一面看报 设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 将下列命题符号化.,解：记 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 和 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或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为真(不管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为真当且仅当 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,例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）小王现在在宿舍或者在图书馆 （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，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) 单个命题变项或命题常项是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) 赋值记作=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表示公式中命题变元的取值，并依据联结词的逻辑规则计算出复合命题（公式）的真值，用一个对应表表示的一种方法。,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 命题逻辑等值演算,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，则 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）归谬律：,（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之后，得到的公式是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)是永真式,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为矛盾式当且仅当A0; A为重言式当且仅当A1 说明:演算步骤不惟一,应尽量使演算短些,75,例7：应用题,某勘探队有3名队员，有一