离散数学数理逻辑

1、离散数学数理逻辑第1页，共86页，2022年，5月20日，11点11分，星期五1教材与参考资料教材： 离散数学 （第2版），屈婉玲、耿素云、张立昂编，清华大学出版社参考资料：离散数学，刘玉珍、刘咏梅编，武汉大学出版社Discrete Mathematical Structures(Sixth Edition)， Bernard Kolman, Fobert C. Busby and Sharon Ross ，高等教育出版社有影印版、译本Discrete Mathematics and Its Applications(Sixth Edition)，美Kenneth H. Rosen，机械工业出

2、版社影印版、译本第2页，共86页，2022年，5月20日，11点11分，星期五2课程主要内容数理逻辑集合论图论代数系统* 第3页，共86页，2022年，5月20日，11点11分，星期五3目的、意义和要求研究内容：离散量的结构及其相互间的关系。意义：计算机科学的理论基础。目的：打基础必备的数学知识培养抽象思维能力、逻辑推理能力教学内容：第1-7 章重点第9、14章备选第8、11章自学第10、12、13章不要求 第4页，共86页，2022年，5月20日，11点11分，星期五4学习要求1、课堂要求： 按时上课 认真听讲2、课外要求： 复习(每次课后，安排半个小时) 认真、按时完成作业(每次课后，安排

3、1个小时)第5页，共86页，2022年，5月20日，11点11分，星期五5学习考查方法1、出勤率：10% 不定期检查出勤情况2、作业完成情况：10% 对作业完成情况进行登记3、课堂测验 + 期中考试：20% 共 5 次4、期末考试（闭卷）：60%第6页，共86页，2022年，5月20日，11点11分，星期五6第一篇 数理逻辑第1章 导 论数理逻辑的概念数理逻辑的发展简史数理逻辑的地位和作用第7页，共86页，2022年，5月20日，11点11分，星期五7（1）定义1.1 数理逻辑的概念 数理逻辑是采用数学方法研究抽象思维推理规律（形式推理）的一门科学。命题逻辑是数理逻辑的基本组成部分之一推理的基

4、本要素是命题把命题作为基本单位来分析符号化 研究公式间的关系 推导、演算 第8页，共86页，2022年，5月20日，11点11分，星期五8（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

5、 s3) 1 （3）(p2 s4) (p2 s4) 13.通过演算规则，得出结果第9页，共86页，2022年，5月20日，11点11分，星期五9（3）内容谓词逻辑命题逻辑第10页，共86页，2022年，5月20日，11点11分，星期五10（4）分支模型论证明论公理集合论递归论第11页，共86页，2022年，5月20日，11点11分，星期五111.2 数理逻辑的发展简史创立阶段起源阶段完善阶段 发展历史第12页，共86页，2022年，5月20日，11点11分，星期五12起源阶段 德国数学家、哲学家 G.Leibniz（16461716），提出建立一种普遍的符号语言，利用符号语言进行思维演算的设想

6、。第13页，共86页，2022年，5月20日，11点11分，星期五13创立阶段 英国数学家 G.Bool于1847年发表逻辑的数学分析，创建一套表示逻辑推理的基本符号以及符号的运算规律，建立了布尔代数。 德国数学家 G.Frege于1879年在概念的演算一书中引进谓词符号和量词符号，创建第一个比较严格的逻辑演算系统。第14页，共86页，2022年，5月20日，11点11分，星期五14完善阶段 英国逻辑学家 和B.Russel于1910将当时的数理逻辑写入了数学原理中，使数理逻辑成为了一门专门的学科。 20 世纪 30 年代，由于众多科学家的努力，衍生出许多新的分支，如：直觉主义逻辑、多值逻辑、

7、组合逻辑等。第15页，共86页，2022年，5月20日，11点11分，星期五151.3 数理逻辑的地位和作用1、计算机科学的重要的理论基础之一；2、对数学、计算机科学、人工智能、语言学、控制论等诸多学科产生深远的影响。3、在计算机科学中的应用：软件、硬件设计第16页，共86页，2022年，5月20日，11点11分，星期五16第2章 命题逻辑2.1 命题逻辑基本概念 2.2 命题逻辑等值演算 2.3 范式2.4 命题逻辑推理理论 第17页，共86页，2022年，5月20日，11点11分，星期五172.1 命题逻辑基本概念 2.1.1 命题与联结词命题与真值(简单命题, 复合命题)联结词(, ,

8、, , ) 命题公式及其分类命题公式及其赋值真值表命题公式的分类 第18页，共86页，2022年，5月20日，11点11分，星期五182.1.1 命题与联结词1、命题及相关概念（1）命题的定义两者必居其一且只居其一二值逻辑 命题定义的理解：从两个方面把握这个概念（1）陈述句；（2）真值唯一性（注意：真值可能目前还不知道答案）。命题：一个具有真假意义的陈述句。 什么是真值：只包含真/假两个值的量。 T/1真 F/0假第19页，共86页，2022年，5月20日，11点11分，星期五19 注意：（1） 感叹句、祈使句、疑问句都不是命题 （2）陈述句中的悖论以及判断结果不唯一确定的也不是命题第20页，

9、共86页，2022年，5月20日，11点11分，星期五20中国的首都在北京。1+1=10请开门！x+y=1明年10月1日是晴天。本命题是假的。李红既学英语又学日语。例1 判断下列个自然语言是否是命题第21页，共86页，2022年，5月20日，11点11分，星期五21（2）几个基本概念 真命题与假命题 命题变元与命题常元 真命题: 真值为真的命题 假命题: 真值为假的命题 若p即可以表示真命题，又可以表示假命题，则称p为命题变元。 T永远表示真命题，F表示假命题，称T和F为命题常元。第22页，共86页，2022年，5月20日，11点11分，星期五22例2真命题假命题真值不确定疑问句感叹句祈使句悖

10、论(1),(2),(5)是命题, (3),(4),(6)(8)都不是命题真值确定, 但未知 下列句子中哪些是命题？并指出命题的真值。 (1) 北京是中华人民共和国的首都.(2) 2 + 5 8.(3) x + 5 3.(4) 你会开车吗？(5) 2050年元旦北京是晴天.(6) 这只兔子跑得真快呀！(7) 请关上门！(8) 我正在说谎话.第23页，共86页，2022年，5月20日，11点11分，星期五23（1）简单命题与复合命题（2）联结词的定义（3）联结词的优先级2.联接词第24页，共86页，2022年，5月20日，11点11分，星期五24（1）简单命题与复合命题简单命题(原子命题):简单陈

11、述句构成的命题。简单命题的符号化:用p, q, r, ,pi,qi,ri (i1)表示 用“1”表示真，用“0”表示假复合命题:由简单命题通过联结词联结而成的陈述句。 例如 如果明天天气好, 我们就出去郊游 设p:明天天气好, q:我们出去郊游, 如果p, 则q 又如 张三一面喝茶一面看报 设p:张三喝茶, q:张三看报, p并且q第25页，共86页，2022年，5月20日，11点11分，星期五25（2）联结词的定义否定词（）定义2.1 设p为命题，复合命题 “非p”(或 “p的否定”)称为p的否定式，记作p，符号称作否定联结词, 并规定p为真当且仅当 p为假。例如 p:2是合数, p: 2不

12、是合数。p为假, p为真。第26页，共86页，2022年，5月20日，11点11分，星期五26合取词（ ）定义2.2 设p,q为二命题, 复合命题“p并且q”(或“p与q”)称为p与q的合取式, 记作pq, 称作合取联结词, 并规定 pq为真当且仅当 p与q同时为真.例如 p:2是偶数, q: 2是素数, pq: 表示的含义是2是偶素数。 因为p为真, q也为真，所以 pq为真。第27页，共86页，2022年，5月20日，11点11分，星期五27例3 将下列命题符号化. 解：记 p:王晓用功, q:王晓聪明(1) pq (2) pq(3) qp(4) 记 r: 张辉是三好生, s: 王丽是三好

13、生, rs(5) 简单命题, 记 t: 张辉与王丽是同学(1) 王晓既用功又聪明.(2) 王晓不仅聪明，而且用功.(3) 王晓虽然聪明，但不用功.(4) 张辉与王丽都是三好生.(5) 张辉与王丽是同学.第28页，共86页，2022年，5月20日，11点11分，星期五28析取词（）定义2.3 设 p、q为命题，复合命题“p或q”称作p与q的析取式，记作pq, 称作析取联结词, 并规定pq为假当且仅当p与q同时为假。例如 张三和李四至少有一人会英语设 p:张三会英语, q:李四会英语, 符号化为pq。第29页，共86页，2022年，5月20日，11点11分，星期五29相容或与排斥或 析取词表示的是

14、相容或，即 p 和 q 均为真时 (p q)亦为真，而与之对应的还有一个是排斥或，它表示的含义是p 和 q 不能同时为真。例如 这件事由张三和李四中的一人去做 设 p:张三做这件事, q:李四做这件事 应符号化为 (p q) (p q)第30页，共86页，2022年，5月20日，11点11分，星期五30例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:王晓红生于197

15、6年(vw)(vw)又可形式化为 vw(1) 2或4是素数.(2) 2或3是素数.(3) 4或6是素数.(4) 元元只能拿一个苹果或一个梨.(5) 王晓红生于1975年或1976年.第31页，共86页，2022年，5月20日，11点11分，星期五31蕴涵词（ ）定义2.4 设 p,q为二命题, 复合命题 “如果p,则q” 称作p与q的蕴涵式, 记作pq, 并称p是蕴涵式的前件, q为蕴涵式的后件. 称作蕴涵联结词, 并规定, pq为假当且仅当 p为真且q为假.例如 如果明天天气好, 我们就出去郊游 设p:明天天气好, q:我们出去郊游, 形式化为 pq第32页，共86页，2022年，5月20日

16、，11点11分，星期五32蕴涵词的其它表述方式pq 的逻辑关系: q为p的必要条件, p为q的充分条件。“如果p,则q” 的多种表述方式： 若p,就q 只要p,就q p仅当q 只有q 才p 除非q, 才p 除非q, 否则非p当p为假时，pq为真(不管q为真, 还是为假)第33页，共86页，2022年，5月20日，11点11分，星期五33例5 设p:天冷, q:小王穿羽绒服，将下列命题符号化 注意： pq 与 qp 等值（真值相同） pqpqqp 或 pqpqqp qppq 或 qpqp(1) 只要天冷，小王就穿羽绒服.(2) 因为天冷，所以小王穿羽绒服.(3) 若小王不穿羽绒服，则天不冷.(4

17、) 只有天冷，小王才穿羽绒服.(5) 除非天冷，小王才穿羽绒服.(6) 除非小王穿羽绒服，否则天不冷.(7) 如果天不冷，则小王不穿羽绒服.(8) 小王穿羽绒服仅当天冷的时候.第34页，共86页，2022年，5月20日，11点11分，星期五34等价词（ ）定义2.5 设p, q为命题, 复合命题 “p当且仅当q”称作p与q的等价式, 记作pq, 称作等价联结词. 并规定pq为真当且仅当 p与q同时为真或同时为假。 pq 的逻辑关系: p与q互为充分必要条件例如 这件事张三能做好, 且只有张三能做好 设p:张三做这件事, q:这件事做好了 形式化为: pq第35页，共86页，2022年，5月20

18、日，11点11分，星期五35例6 求下列复合命题的真值：1011(1) 2+24 当且仅当 3+36.(2) 2+24 当且仅当 3是偶数.(3) 2+24 当且仅当 太阳从东方升起.(4) 2+25 当且仅当 美国位于非洲.第36页，共86页，2022年，5月20日，11点11分，星期五36分析找出简单命题用字母表示简单命题用联接词联接命题符号命题符号化的一般规则第37页，共86页，2022年，5月20日，11点11分，星期五37分析找出简单命题用字母表示简单命题用联接词联接命题符号解 令 p: 我上街 q: 我累 r: 我去书店看看 则可符号化为：（pq)r例7 将下列命题符号化：如果我上

19、街并且我不累，我就去书店看看。简单命题：我上街。我累。我去书店看看。第38页，共86页，2022年，5月20日，11点11分，星期五38例8 试将下列命题符号化：如果你不看电影，那么我也不看电影小王一边吃饭，一边看书解:（1）设p：你看电影， q：我看电影，则： p q （2）设p：小王吃饭，q：小王看书，则： pq第39页，共86页，2022年，5月20日，11点11分，星期五39（3）联结词的优先级联结词优先级:( ), , , , 同级按从左到右的顺序进行第40页，共86页，2022年，5月20日，11点11分，星期五401、分析下列各命题的真值 （1） 2+2=4当且仅当3是奇数 （2

20、） 2+2=4当且仅当3不是奇数 （3） 2+24当且仅当3是奇数 （4） 2+24当且仅当3不是奇数2、将下列命题符号化 （1）小王是游泳冠军或者百米赛跑冠军 （2）小王现在在宿舍或者在图书馆 （3）选小王或者小李中的一人当班长 （4）如果我上街，我就去书店看看，除非我很累课堂练习（1）第41页，共86页，2022年，5月20日，11点11分，星期五41课堂练习（2）3、将下列命题符号化 （1）李平既聪明又用功 （2）李平虽然聪明，但不用功 （3）李平不但聪明，而且用功 （4）李平不是不聪明，而是不用功4、将下列命题符号化 （1）只要不下雨，我就骑自行车上班 （2）只有不下雨，我才骑自行车上

21、班 （3）若2+2=4，则太阳从东方升起 （4）若2+24,则太阳从东方升起第42页，共86页，2022年，5月20日，11点11分，星期五422.1.2 合式公式及其分类1.命题语言的字母表 ：2.合式公式的基本概念3.真值表4.合式公式的分类第43页，共86页，2022年，5月20日，11点11分，星期五431.命题语言的字母表命题语言的字母表 ：命题常元：T, F (或 1，0)命题变元：p1, p2, , pn联接词：，辅助符号：（ ）第44页，共86页，2022年，5月20日，11点11分，星期五44（1）合式公式(命题公式, 公式)的定义定义2.6 合式公式递归定义如下：(1) 单

22、个命题常项或变项是合式公式，并称作原子合式公式；(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第45页，共86页，2022年，5月20日，11点11分，星期五45（2）合式公式的层次定义2.7 (1) 单个命题变项或命题常项是0层公式(2) 称A是n+1(n0)层公式

23、是指下面情况之一：(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层第46页，共86页，2022年，5月20日，11点11分，星期五46（3）公式的赋值定义2.8 设 p1, p2, , pn是出现在公式A中全部的命题变项，给 p1, p2, , pn指定一组真值，称为对A的一个赋值或解释。使公式为真的赋值称作

24、成真赋值, 使公式为假的赋值称作成假赋值。说明: (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, 第47页，共86页，2022年，5月20日，11点11分，星期五47实例例8 公式A=( p1 p2 p3 )(p1 p2) 000是成真赋值, 001是成假赋值 公式B= (pq)r 000是成假赋值, 001是成真赋值第48页，共86页

25、，2022年，5月20日，11点11分，星期五483、真值表真值表: 命题公式在所有可能的赋值下的取值的列表。含n个变项的公式有2n个赋值 用0或1表示公式中命题变元的取值，并依据联结词的逻辑规则计算出复合命题（公式）的真值，用一个对应表表示的一种方法。第49页，共86页，2022年，5月20日，11点11分，星期五49基本复合命题真值表汇总 p q p pq pq pq pq 0 0 1 0 0 1 1 0 1 1 0 1 1 0 1 0 0 0 1 0 0 1 1 0 1 1 1 1第50页，共86页，2022年，5月20日，11点11分，星期五50 p q qp (qp) q (qp)

26、qp 0 00 11 01 1 1011 0001 1111例9 给出公式的真值表(1) (qp) qp；(2) (pq) q； (3) (pq) r.例9第51页，共86页，2022年，5月20日，11点11分，星期五51 p q ppq (pq) (pq) q0 00 11 01 1 1100110100100000(2) (pq) q第52页，共86页，2022年，5月20日，11点11分，星期五52 p q r pq r (pq)r 0 0 00 0 10 1 00 1 11 0 01 0 11 1 0 1 1 1 0011111 1 1010101 0 11101010(3) (pq

27、) r第53页，共86页，2022年，5月20日，11点11分，星期五534、命题公式的分类重言式(永真式): 无成假赋值的命题公式矛盾式(永假式): 无成真赋值的命题公式可满足式: 非矛盾式的命题公式注意: 重言式是可满足式，但反之不真.例如 上例中(1) (qp)qp为重言式(2) (pq)q为矛盾式(3) (pq)r为非重言式的可满足式第54页，共86页，2022年，5月20日，11点11分，星期五542、判断下列命题公式的类型（1）（2）课堂练习1、构造下列命题公式的真值表（1）（2）第55页，共86页，2022年，5月20日，11点11分，星期五552.2 命题逻辑等值演算2.2.1

28、 等值式与等值演算等值式基本等值式等值演算2.2.2 联结词完备集真值函数联结词完备集与非联结词和或非联结词第56页，共86页，2022年，5月20日，11点11分，星期五56 2.2.1 等值式与等值演算1、等值式的定义定义2.11 若等价式AB是永真式, 则称A与B等值, 记作AB, 并称AB是等值式。第57页，共86页，2022年，5月20日，11点11分，星期五57(1) 是元语言符号, 不要混同于和=。(2) A与B等值当且仅当A与B在所有可能赋值下的真值都相同, 即A与B有相同的真值表。(3) 可能有哑元出现. 在B中出现, 但不在A中出现的命题变项称作A的哑元. 同样,在A中出现

29、, 但不在B中出现的命题变项称作B的哑元. 哑元的值不影响命题公式的真值。说明第58页，共86页，2022年，5月20日，11点11分，星期五582、性质(1) A A(2) 若A B，则 B A(3) 若A B且B C，则 A C第59页，共86页，2022年，5月20日，11点11分，星期五593、真值表法判断公式是否等值结论: (pq) (pq) p q p q pq (pq) pq (pq)(pq) 0 0 1 1 0 1 1 1 0 1 1 0 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 0 1 0 0 1例1 判断 (pq) 与 pq 是否等值解第60页，共86页，

30、2022年，5月20日，11点11分，星期五60 p q r p(qr) (pq)r (pq)r 0 0 0 1 0 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 p(qr)与(pq)r等值, 但与(pq)r不等值 例2 判断下述3个公式之间的等值关系: p(qr), (pq)r, (pq)r解第61页，共86页，2022年，5月20日，11点11分，星期五614、基本等值式（1）双重否定律：（2）等幂律：第62页，共86页，2022年，5月20日，11点11分，星期五

31、62（3）交换律：（4）结合律：（5）分配律：（6）德 摩根定律：第63页，共86页，2022年，5月20日，11点11分，星期五63（7）吸收律：（8）蕴含等值式：（9）等价等值式：第64页，共86页，2022年，5月20日，11点11分，星期五64（10）零律：（11）同一律：（12）排中律：第65页，共86页，2022年，5月20日，11点11分，星期五65（13）矛盾律：（14）等价否定等值式：（15）归谬律：（16）假言易位：第66页，共86页，2022年，5月20日，11点11分，星期五66 (1) 代入规则 代入规则：对于重言式中的任一命题变元出现的每一处均用同一命题公式代入，得

32、到的仍是重言式。 例如 F=（pq）（qp）是重言式，若用公式rs代换命题变元p得公式 F1=（rs）q）（q（rs）， F1仍是重言式。注意：因为A B当且仅当A B是重言式。所以，若对于等值式中的任一命题变元出现的每一处均用同一命题公式代入，则得到的仍是等值式。5、等值演算第67页，共86页，2022年，5月20日，11点11分，星期五67(2) 置换规则 例如 设公式A=（PQ）（PQ）（RS）。 则PQ，PQ，（PQ）（RS）等均是A的子公式， 置换规则：设C是公式A的子公式，CD。如果将公式A中的子公式C置换成公式D之后，得到的公式是B，则AB。 子公式： 设C是命题公式A的一部分（

33、即C是公式A中连续的几个符号），且C本身也是一个命题公式，则称C为公式A的子公式。 第68页，共86页，2022年，5月20日，11点11分，星期五68(3) 等值演算 等值演算是指利用已知的一些等值式，根据置换规则、代入规则以及等值关系的可传递性推导出另外一些等值式的过程。 例3 证明 p(qr) (pq)r证 p(qr) p(qr) （蕴涵等值式） (pq)r （结合律） (pq)r （德摩根律） (pq) r （蕴涵等值式）第69页，共86页，2022年，5月20日，11点11分，星期五69 例4：证明（AB)(BA)是永真式。证明: (A B)(B A) 蕴涵等值式 (AB)(BA)

34、德摩根律、双重否定律 (AB)(BA) 分配律 (ABA)(BBA)交换律、结合律、补余律 T （AB)(BA)是永真式第70页，共86页，2022年，5月20日，11点11分，星期五70（同一律）（排中律）（分配律）证明 例5证：第71页，共86页，2022年，5月20日，11点11分，星期五71例6 用等值演算法判断下列公式的类型(1) q(pq) 解 q(pq) q(pq) （蕴涵等值式） q(pq) （德摩根律） p(qq) （交换律，结合律） p0 （矛盾律） 0 （零律）该式为矛盾式.第72页，共86页，2022年，5月20日，11点11分，星期五72例6(续)(2) (pq)(q

35、p) 解 (pq)(qp) (pq)(qp) （蕴涵等值式） (pq)(pq) （交换律） 1该式为重言式.第73页，共86页，2022年，5月20日，11点11分，星期五73例6(续)(3) (pq)(pq)r) 解 (pq)(pq)r) (p(qq)r （分配律） p1r （排中律） pr （同一律）非重言式的可满足式.如101是它的成真赋值,000是它的成假赋值.总结:A为矛盾式当且仅当A0; A为重言式当且仅当A1说明:演算步骤不惟一,应尽量使演算短些第74页，共86页，2022年，5月20日，11点11分，星期五74例7：应用题 某勘探队有3名队员，有一天取得一块矿样，3人的判断如下： 甲说：这不是铁，也不是铜 乙说：这不是铁，是锡 丙说：这不是锡，是铁 经过实验鉴定后发现，其中一人2个判断都是正确的，一人判断对了一半，另外一个人全错了。根据以上情况判断矿样的种类。第75页，共86页，2022年，5月20日，11点11分，星期五75解：设 p：矿样为铁，q：矿样为铜，r：矿样为锡，则可得：第76页，共86页，2022年，5月20日，11点11分，星期五76第77页，共86页，2022年，5月20日，11点11分，星期五7