1、中北大学离散数学课程组中北大学离散数学课程组1离离 散散 数数 学学 中北大学中北大学16 February 202316 February 2023中北大学离散数学课程组中北大学离散数学课程组2引言n1.1.计算机专业的学生为什么要学计算机专业的学生为什么要学习离散数学？习离散数学？n2.2.离散数学包含的内容离散数学包含的内容?n3.3.怎样学习离散数学？怎样学习离散数学？中北大学离散数学课程组中北大学离散数学课程组31 1 什么是离散数学？什么是离散数学？离散数学是现代数学的一个重离散数学是现代数学的一个重要分支，是计算机类专业的重要课程要分支，是计算机类专业的重要课程。它以。它以研究离
2、散量的结构及其相互间研究离散量的结构及其相互间的关系的关系为主要目标，其研究对象一般为主要目标，其研究对象一般是有限个或可数个元素。是有限个或可数个元素。中北大学离散数学课程组中北大学离散数学课程组42 2 离散数学与计算机科学离散数学与计算机科学n计算机学科的一个重要特点计算机学科的一个重要特点离散性离散性硬件硬件软件软件（系统软件、应用软件）模 型算法（程序运行逻辑）算法（程序运行逻辑）数据表示、存储数据表示、存储程序编写、执行程序编写、执行离离散散数数学学中北大学离散数学课程组中北大学离散数学课程组52 2 离散数学与计算机科学离散数学与计算机科学n 离散数学的思维方法能够为计算机离散数
3、学的思维方法能够为计算机科学所用，科学所用，“离散数学能够使我们在更高的离散数学能够使我们在更高的高度去了解和学习计算机科学高度去了解和学习计算机科学”！n 计算机科学知识掌握的过程：计算机科学知识掌握的过程：“硬件硬件跟着软件走，软件跟着模型走，模型跟着学跟着软件走，软件跟着模型走，模型跟着学科实际应用走；学科实际应用跟着自然走科实际应用走；学科实际应用跟着自然走”！n需要如下三个方面的能力：需要如下三个方面的能力：构造模构造模型、算法设计、程序设计的能力。型、算法设计、程序设计的能力。n 思维训练：思维训练：构造性思维构造性思维中北大学离散数学课程组中北大学离散数学课程组63 3 关于课程
4、学习关于课程学习n课程特点课程特点l知识点集中，概念和定理多l方法性强n 阅读，思考，练习，阅读，总结阅读，思考，练习，阅读，总结，n学习内容学习内容n数理逻辑、集合论、抽象代数、图论数理逻辑、集合论、抽象代数、图论中北大学离散数学课程组中北大学离散数学课程组74.4.计算科学与数学的关系计算科学与数学的关系n 至于计算机技术专业的学生为何要学习至于计算机技术专业的学生为何要学习数学这个问题的答案：数学这个问题的答案：计算机科学植根于数计算机科学植根于数学，从而数学是必须掌握的基础知识学，从而数学是必须掌握的基础知识；另外；另外如果我们已经拥有牢固的数学基础，则能大如果我们已经拥有牢固的数学基
5、础，则能大大提高我们本身的大提高我们本身的逻辑推理能力逻辑推理能力、抽象思维抽象思维能力能力和和形式化思维能力形式化思维能力，从而今后在学习任从而今后在学习任何一门计算机科学的专业主干课程时，都不何一门计算机科学的专业主干课程时，都不会遇上任何思维理解上的困难。会遇上任何思维理解上的困难。中北大学离散数学课程组中北大学离散数学课程组84 4计算学科与离散数学的关系计算学科与离散数学的关系n 在计算机科学知识掌握的过程中应是在计算机科学知识掌握的过程中应是“硬件跟着软件走，软件跟着模型走，模型硬件跟着软件走，软件跟着模型走，模型跟着学科实际应用走；学科实际应用跟着自跟着学科实际应用走；学科实际应
6、用跟着自然走然走”。关于学生的培养目标就是要培养自关于学生的培养目标就是要培养自己的学生能够根据实际应用问题提出计算机己的学生能够根据实际应用问题提出计算机应用的模型，并用硬件和软件资源去构造计应用的模型，并用硬件和软件资源去构造计算机系统去完成模型中所提出来的工作。算机系统去完成模型中所提出来的工作。n 构造模型的能力；算法设计的能力；构造模型的能力；算法设计的能力；程序设计的能力。程序设计的能力。中北大学离散数学课程组中北大学离散数学课程组96.6.离散数学在国外的状况离散数学在国外的状况n 纵观全世界软件产业的情况，易见一个纵观全世界软件产业的情况，易见一个奇特的现象：美国处于绝对的垄断
7、地位。造奇特的现象：美国处于绝对的垄断地位。造成这种现象的一个根本的原因就是成这种现象的一个根本的原因就是计算机科计算机科学学在美国的飞速发展。当今计算机科学界的在美国的飞速发展。当今计算机科学界的最权威人士很多都是研究离散数学出身的。最权威人士很多都是研究离散数学出身的。n 美国最重要的计算机科学系（美国最重要的计算机科学系（MITMIT，PrincetonPrinceton，StanfordStanford，HarvardHarvard，YaleYale，.）都有第一流的）都有第一流的离散数学家离散数学家。计算机科。计算机科学通过对软件产业的促进，带来了巨大的效学通过对软件产业的促进，带来
8、了巨大的效益，这已是不争之事实。益，这已是不争之事实。中北大学离散数学课程组中北大学离散数学课程组106.6.离散数学在国外的状况离散数学在国外的状况n 美国政府也成立了离散数学及理论计算美国政府也成立了离散数学及理论计算机科学中心机科学中心DIMACSDIMACS（与（与PrincetonPrinceton大学，大学，RutgersRutgers大学，大学，AT&T AT&T 联合创办的，设在联合创办的，设在RutgersRutgers大学），该中心已是离散数学理论大学），该中心已是离散数学理论计算机科学的重要研究阵地。美国国家数学计算机科学的重要研究阵地。美国国家数学科学研究所（科学研究所
9、（Mathematical Sciences Mathematical Sciences Research InstituteResearch Institute，由，由陈省身陈省身先生创立）先生创立）在在19971997年选择了离散数学作为研究专题，组年选择了离散数学作为研究专题，组织了为期一年的研究活动。织了为期一年的研究活动。中北大学离散数学课程组中北大学离散数学课程组116.6.离散数学在国外的状况离散数学在国外的状况n 值得一提的是亚洲的发达国家也十分重视离散值得一提的是亚洲的发达国家也十分重视离散数学的研究。数学的研究。日本日本有离散数学研究中心，并且从美有离散数学研究中心，并且从
10、美国引进人才，不仅支持日本国内的研究，还出资支国引进人才，不仅支持日本国内的研究，还出资支持美国的有关课题的研究，这样使日本的离散数学持美国的有关课题的研究，这样使日本的离散数学这几年的发展极为迅速。这几年的发展极为迅速。台湾、香港台湾、香港两地也从美国两地也从美国引进人才，大力发展离散数学。引进人才，大力发展离散数学。新加坡，韩国，马新加坡，韩国，马来西亚来西亚也在积极推动离散数学的研究和人才培养。也在积极推动离散数学的研究和人才培养。n 世界各地对离散数学的如此钟爱显然是有原因世界各地对离散数学的如此钟爱显然是有原因的，那就是没有的，那就是没有离散数学离散数学就没有就没有计算机科学计算机科
11、学，没有，没有计算机软件计算机软件。中北大学离散数学课程组中北大学离散数学课程组125.5.离散数学在国外的状况离散数学在国外的状况n 2020世纪公认的伟大数学家世纪公认的伟大数学家盖尔芳德盖尔芳德预言离散数预言离散数学和几何学将是学和几何学将是2121世纪数学研究的前沿阵地。这一世纪数学研究的前沿阵地。这一观点不仅得到国际数学界的赞同，也得到了中国数观点不仅得到国际数学界的赞同，也得到了中国数学界的赞同和响应。学界的赞同和响应。n 除上述以外，欧洲也在积极发展离散数学，英除上述以外，欧洲也在积极发展离散数学，英国、法国、德国、荷兰、丹麦、奥地利、瑞典、意国、法国、德国、荷兰、丹麦、奥地利、
12、瑞典、意大利、西班牙等国家都建立了各种形式的离散数学大利、西班牙等国家都建立了各种形式的离散数学研究中心。近几年，南美国家也在积极推动离散数研究中心。近几年，南美国家也在积极推动离散数学的研究。澳大利亚，新西兰也组建了很强的离散学的研究。澳大利亚，新西兰也组建了很强的离散数学研究机构。数学研究机构。中北大学离散数学课程组中北大学离散数学课程组136.6.关于离散数学的一些应用关于离散数学的一些应用n 例例1:1:在日常生活中我们常常遇到离散数学在日常生活中我们常常遇到离散数学的问题。如果你仔细留心一张世界地图，你的问题。如果你仔细留心一张世界地图，你会发现用会发现用一种颜色一种颜色对对一个国家
13、一个国家着色，那么一着色，那么一共只需要共只需要四种颜色四种颜色就能保证每两个相邻的国就能保证每两个相邻的国家的颜色不同。这样的着色效果能使每一个家的颜色不同。这样的着色效果能使每一个国家都能清楚地显示出来。但要证明这个结国家都能清楚地显示出来。但要证明这个结论确是一个著名的世界难题，最终借助计算论确是一个著名的世界难题，最终借助计算机才得以解决，最近人们才发现了一个更简机才得以解决，最近人们才发现了一个更简单的证明。单的证明。中北大学离散数学课程组中北大学离散数学课程组146.6.关于离散数学的一些应用关于离散数学的一些应用n 例例2:2:一个邮递员从邮局出发，要走一个邮递员从邮局出发，要走
14、完他所管辖的街道，他应该怎样选择什完他所管辖的街道，他应该怎样选择什么样的路径，这就是著名的么样的路径，这就是著名的 中国邮递中国邮递员问题员问题，由中国离散数学家管，由中国离散数学家管梅谷梅谷教教授提出，著名离散数学家授提出，著名离散数学家J.EdmondsJ.Edmonds和和他的合作者给出了一个解答。他的合作者给出了一个解答。中北大学离散数学课程组中北大学离散数学课程组156.6.关于离散数学的一些应用关于离散数学的一些应用n 例3:一个班级的学生共计选修一个班级的学生共计选修A A、B B、C C、D D、E E、F F六门课程，其中一部分人同六门课程，其中一部分人同时选修时选修D D
15、、C C、A A，一部分人同时选修，一部分人同时选修B B、C C、F F，一部分人同时选修，一部分人同时选修B B、E E，还有一，还有一部分人同时选修部分人同时选修A A、B B，期终考试要求，期终考试要求每每天考一门课，六天内考完天考一门课，六天内考完，为了减轻学，为了减轻学生负担，要求生负担，要求每人都不会连续参加考试每人都不会连续参加考试，试设计一个考试日程表。，试设计一个考试日程表。中北大学离散数学课程组中北大学离散数学课程组166.6.关于离散数学的一些应用关于离散数学的一些应用n 例例4:4:一个人带着一只狼、一只羊和一一个人带着一只狼、一只羊和一捆草要渡河，由于船太小，人做摆
16、渡者捆草要渡河，由于船太小，人做摆渡者一次只能运送一个一次只能运送一个“乘客乘客”，很显然，很显然，如果人不在，狼要吃羊，羊要吃草，问如果人不在，狼要吃羊，羊要吃草，问人怎样才能把它们平安地渡过河去？人怎样才能把它们平安地渡过河去？中北大学离散数学课程组中北大学离散数学课程组176.6.关于离散数学的一些应用关于离散数学的一些应用n 例例5 5 网络计划技术网络计划技术n 在生产原子弹的曼哈顿计划中，在生产原子弹的曼哈顿计划中，涉及到很多工序，许多人员的安排，很涉及到很多工序，许多人员的安排，很多元件的生产，怎样安排各种人员的工多元件的生产，怎样安排各种人员的工作，以及各种工序间的衔接，从而使
17、整作，以及各种工序间的衔接，从而使整个工期的时间尽可能短？这些都是离散个工期的时间尽可能短？这些都是离散数学典型例子。数学典型例子。中北大学离散数学课程组中北大学离散数学课程组186.6.关于离散数学的一些应用关于离散数学的一些应用n 总之，离散数学无处不在，它的主要应总之，离散数学无处不在，它的主要应用就是在各种复杂关系中找出最优的方案。用就是在各种复杂关系中找出最优的方案。所以离散数学完全可以看成是所以离散数学完全可以看成是一门量化的关一门量化的关系学系学，一门量化了的运筹学一门量化了的运筹学，一门量化了的一门量化了的管理学管理学。n 胡锦涛同志在胡锦涛同志在19981998年接见年接见“
18、五四五四”青年青年奖章时发表的讲话中指出，离散数学不同于奖章时发表的讲话中指出，离散数学不同于传统的纯数学的一个分支，它还是一门应用传统的纯数学的一个分支，它还是一门应用学科，一门交叉学科。他希望中国的离散数学科，一门交叉学科。他希望中国的离散数学研究能够为国家的经济建设服务。学研究能够为国家的经济建设服务。中北大学离散数学课程组中北大学离散数学课程组192/16/20232/16/2023数理逻辑（数理逻辑（Mathematical LogicMathematical Logic）是研究演绎推理的一门学科，用是研究演绎推理的一门学科，用数学的数学的方法方法来研究来研究推理的规律推理的规律统称
19、为数理逻辑。统称为数理逻辑。第一篇第一篇 数理逻辑数理逻辑中北大学离散数学课程组中北大学离散数学课程组202/16/20232/16/2023主要研究内容：主要研究内容：推理推理 着重于着重于推理过程是否正确推理过程是否正确 着重于着重于语句之间的关系语句之间的关系 主要研究方法：主要研究方法：数学的方法数学的方法 就是引进一套符号体系的方法，所以数就是引进一套符号体系的方法，所以数理逻辑又叫符号逻辑（理逻辑又叫符号逻辑（Symbolic LogicSymbolic Logic）。）。第一篇第一篇 数理逻辑数理逻辑中北大学离散数学课程组中北大学离散数学课程组212/16/20232/16/20
20、23什么是数理逻辑什么是数理逻辑？用数学的方法来研究推理的规律统称为数理逻辑。用数学的方法来研究推理的规律统称为数理逻辑。为什么要研究数理逻辑？为什么要研究数理逻辑？程序算法数据程序算法数据 算法逻辑控制算法逻辑控制中北大学离散数学课程组中北大学离散数学课程组222/16/20232/16/2023第一章第一章 命题逻辑命题逻辑 命题逻辑也称命题演算，或语句逻辑。命题逻辑也称命题演算，或语句逻辑。研究内容：研究内容：（1 1）研究以）研究以命题为基本单位命题为基本单位构成的构成的前提和结论前提和结论之间的可推导关系之间的可推导关系?（2 2）研究）研究什么是命题什么是命题？（3 3）研究）研究
21、如何表示命题如何表示命题？（4 4）研究）研究如何由一组前提推导一些结论如何由一组前提推导一些结论？中北大学离散数学课程组中北大学离散数学课程组232/16/20232/16/2023第一章第一章 命题逻辑命题逻辑 命题逻辑的命题逻辑的特征：特征：在研究逻辑的形式时，我们在研究逻辑的形式时，我们把一个命题只把一个命题只分析到其中所含的命题成份为止，不再分析下分析到其中所含的命题成份为止，不再分析下去去。不把一个简单命题再分析为非命题的集合，。不把一个简单命题再分析为非命题的集合，不把不把谓词谓词和和量词量词等非命题成份分析出来。等非命题成份分析出来。中北大学离散数学课程组中北大学离散数学课程组
22、242/16/20232/16/20231.1.1 1.1.1 命题命题定义定义1.1.11.1.1具有具有确切真值确切真值的陈述句称为的陈述句称为命题命题,该命题只取一个该命题只取一个“值值”，称为，称为真值真值。真值只有真值只有“真真”和和“假假”两种，两种，分别用分别用“”(或或“”)和和“”(或或“”)表示。表示。1.1 1.1 命题与命题联结词命题与命题联结词中北大学离散数学课程组中北大学离散数学课程组252/16/20232/16/2023（1 1）太阳是圆的；）太阳是圆的；（2 2）成都是一个旅游城市；）成都是一个旅游城市；（3 3）北京是中国的首都；）北京是中国的首都；（5 5
23、）1 11 11010；（6 6）+y+y；（7 7）我喜欢踢足球；）我喜欢踢足球；（8 8）3 3能被能被2 2整除；整除；（9 9）地球外的星球上也有人；）地球外的星球上也有人；（1010）中国是世界上人口最多的国家；）中国是世界上人口最多的国家；（1111）我正在说谎；）我正在说谎；例例1.1.11.1.1TTT/F非命题非命题T/FFT/FT悖论悖论T中北大学离散数学课程组中北大学离散数学课程组26悖悖 论论 首先要知道悖论是一个逻辑学的名词。其定首先要知道悖论是一个逻辑学的名词。其定义的表述为：由一个被承认是真的命题为前提，义的表述为：由一个被承认是真的命题为前提，设为设为B B，进
24、行正确的逻辑推理后，得出一个与前提，进行正确的逻辑推理后，得出一个与前提互为矛盾命题的结论非互为矛盾命题的结论非B B；反之，以非；反之，以非B B为前提，为前提，亦可推得亦可推得B B。那么命题。那么命题B B就是一个悖论。当然非就是一个悖论。当然非B B也也是一个悖论。是一个悖论。中北大学离散数学课程组中北大学离散数学课程组272/16/20232/16/2023例例1.1.11.1.1（续）（续）（1212）把门关上；）把门关上；（1313）滚出去！）滚出去！（1414）你要出去吗？）你要出去吗？（1515）今天天气真好啊！）今天天气真好啊！非命题非命题非命题非命题非命题非命题非命题非命
25、题注意：注意：一切没有判断内容的句子都不能作为命题一切没有判断内容的句子都不能作为命题，如命令，如命令句、感叹句、疑问句、祈使句、二义性的陈述句等。句、感叹句、疑问句、祈使句、二义性的陈述句等。中北大学离散数学课程组中北大学离散数学课程组282/16/20232/16/2023n命题一定是陈述句，但并非一切陈述句都是命题。命题一定是陈述句，但并非一切陈述句都是命题。n命题的真值有时可明确给出，有时还需要依靠命题的真值有时可明确给出，有时还需要依靠环境、环境、条件、实际情况时间条件、实际情况时间才能确定其真值。才能确定其真值。结论：结论：中北大学离散数学课程组中北大学离散数学课程组29简单命题符
26、号化简单命题符号化 用小写英文字母用小写英文字母 p,q,r,pi,qi,ri(i 1)或大写英文字母或大写英文字母P，Q，R等表示简单命题等表示简单命题 用用“1”表示真，用表示真，用“0”表示假表示假 例如，令例如，令 p：是有理数，则是有理数，则 p 的真值为的真值为0，q：2+5=7，则，则 q 的真值为的真值为1 2命题的符号化命题的符号化中北大学离散数学课程组中北大学离散数学课程组302/16/20232/16/2023一般来说，命题可分两种类型：一般来说，命题可分两种类型：1)1)原子命题原子命题(简单命题简单命题)：不能再：不能再分解分解为更为简单为更为简单命题的命题。命题的命
27、题。2)2)复合命题复合命题：可以：可以分解分解为更为简单命题的命题。为更为简单命题的命题。而且这些简单命题之间是通过如而且这些简单命题之间是通过如“或者或者”、“并且并且”、“不不”、“如果如果.则则.”、“当当且仅当且仅当”等这样的关联词和标点符号复合而构等这样的关联词和标点符号复合而构成一个复合命题。成一个复合命题。命题的分类命题的分类中北大学离散数学课程组中北大学离散数学课程组312/16/20232/16/20231.2.1 1.2.1 命题联结词命题联结词设命题设命题P,QP,Q表示任意两个命题表示任意两个命题,则则最常见的命题联结词有：最常见的命题联结词有：联接词联接词记号记号
28、复合命题复合命题读法读法 记法记法真值结果真值结果 3.3.析取析取 P P或者或者Q QP P与与Q Q的析取的析取P P Q QPQ=1PQ=1P=1P=1或或Q=1Q=12.2.合取合取 P P并且并且Q QP P与与Q Q的合取的合取PQPQPQ=1PQ=1P=1P=1且且Q=1Q=11.1.否定否定 非非P PP P的否定的否定PPP=1P=1P=0P=04.4.条件条件若若P,P,则则Q QP P条件条件Q QP PQQPQ=0PQ=0P=1,Q=0P=1,Q=05.5.等价等价 P P当且仅当当且仅当Q QP P等价于等价于Q QP PQ QP PQ=1Q=1P P=1,Q=1=
29、1,Q=1或或P P=0,Q=0=0,Q=0中北大学离散数学课程组中北大学离散数学课程组32n 命题联结词及真值表命题联结词及真值表否定词否定词“”（或（或“”）否定词否定词（NegationNegation）是一元联结词。相当于自是一元联结词。相当于自然语言中的然语言中的“非非”、“不不”等，等，真值表如右图。真值表如右图。1.2.2 命题联结词的真值表命题联结词的真值表 P P P P 0 0 1 1 1 1 0 0中北大学离散数学课程组中北大学离散数学课程组33合取词合取词“”合取词合取词（ConjunctionConjunction）是二元联结词。相当于自然是二元联结词。相当于自然语言
30、中的语言中的“与与”、“并且并且”“而且而且”、“也也”等，等，真值表如右图。真值表如右图。P Q P Q P P Q Q 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 1 1 1 1 1 11.2.2 1.2.2 命题联结词的真值表命题联结词的真值表中北大学离散数学课程组中北大学离散数学课程组34析取词析取词“”析取词（析取词（DisjunctionDisjunction）是二元联结词。相当于自然是二元联结词。相当于自然语言中的语言中的“或或”、“要么要么要么要么”等，真值表如右图。等，真值表如右图。P Q P Q P PQ Q 0 0 0 0 0 0 0 1 0
31、1 1 1 1 0 1 0 1 1 1 1 1 1 1 11.2.2 1.2.2 命题联结词的真值表命题联结词的真值表中北大学离散数学课程组中北大学离散数学课程组35例例1.2.11.2.1：P P：今晚我写字，：今晚我写字，Q Q：今晚我看书。：今晚我看书。P P Q Q：今晚我写字或看书。：今晚我写字或看书。或字常见的含义有两种：一种是或字常见的含义有两种：一种是“可兼或可兼或”，如上，如上例：它不排除今晚既看书又写字这种情况；一种例：它不排除今晚既看书又写字这种情况；一种是是“排斥或排斥或”，如：，如：“人固有一死，或重于泰山人固有一死，或重于泰山，或轻于鸿毛，或轻于鸿毛”中的或就表示非
32、此即彼，不可兼中的或就表示非此即彼，不可兼得。得。运算运算：表示可兼或：表示可兼或注：排斥或用注：排斥或用表示。表示。1.2.2 1.2.2 命题联结词的真值表命题联结词的真值表中北大学离散数学课程组中北大学离散数学课程组36蕴含词蕴含词“”蕴含词（蕴含词（ImplicationImplication）是二元联结词。相当于自然是二元联结词。相当于自然语言中的语言中的“若若则则”、“如果如果就就”、“只有只有才才”，真值表如右图。真值表如右图。P Q P QP P Q Q 0 0 0 0 1 1 0 1 0 1 1 1 1 0 1 0 0 0 1 1 1 1 1 11.2.2 1.2.2 命题联
33、结词的真值表命题联结词的真值表中北大学离散数学课程组中北大学离散数学课程组37等价词等价词“”等价词（等价词（EquivalenceEquivalence）是二元联结词。相当于自然语是二元联结词。相当于自然语言中的言中的“等价等价”“”“当且仅当当且仅当”“充要条件充要条件”等，等，真值表如右图。真值表如右图。P Q PQ 0 0 1 0 1 0 1 0 0 1 1 11.2.2 1.2.2 命题联结词的真值表命题联结词的真值表中北大学离散数学课程组中北大学离散数学课程组382/16/20232/16/2023例题例题1.2.21.2.2：P QP QP PPQPQPQPQPQPQP PQ Q
34、0 00 01 10 00 01 11 10 10 11 10 01 11 10 01 01 00 00 01 10 00 01 11 10 01 11 11 11 1例如：命题例如：命题P P：2 2是素数；是素数；Q Q：北京是中国的首都：北京是中国的首都中北大学离散数学课程组中北大学离散数学课程组392/16/20232/16/2023说明说明1 1、联结词是句子与句子之间的联结，而非单纯的、联结词是句子与句子之间的联结，而非单纯的名词、形容词、数词等地联结；名词、形容词、数词等地联结；2 2、联结词是两个句子真值之间的联结，而非句子、联结词是两个句子真值之间的联结，而非句子的具体含义的
35、联结，两个句子之间可以无任何的具体含义的联结，两个句子之间可以无任何地内在联系；地内在联系；中北大学离散数学课程组中北大学离散数学课程组402/16/20232/16/2023说明说明3 3、联结词与自然语言之间的对应、联结词与自然语言之间的对应并非一一对应并非一一对应；联结词联结词自然语言自然语言既既又又、不仅、不仅而且而且、虽然、虽然但但是是、并且、和、与，等等；、并且、和、与，等等；如如P P则则Q Q、只要、只要P P就就Q Q、P P仅当仅当Q Q、只有、只有Q Q才才P P、除非除非Q Q否则否则 P P，等等，等等等价、当且仅当、充分必要、等等；等价、当且仅当、充分必要、等等；相
36、容（可兼）的或相容（可兼）的或中北大学离散数学课程组中北大学离散数学课程组412/16/20232/16/2023符号化下列命题符号化下列命题（1 1）四川）四川不不是人口最多的省份；是人口最多的省份；（2 2）王超是一个）王超是一个德智体德智体全面发展的好学生；全面发展的好学生；（3 3）教室的灯不亮可能是灯管坏了）教室的灯不亮可能是灯管坏了或者或者是停电了；是停电了；（4 4）如果如果周末天气晴朗，周末天气晴朗，那么那么学院将组织我们到学院将组织我们到石像湖春游；石像湖春游；（5 5）两个三角形全等）两个三角形全等当且仅当当且仅当三角形的三条边全三角形的三条边全部相等。部相等。(6)张辉与
37、张辉与王丽是同学。王丽是同学。例例1.2.31.2.3中北大学离散数学课程组中北大学离散数学课程组422/16/20232/16/2023例例1.2.3 1.2.3 解解（1 1）设：四川是人口最多的省份。）设：四川是人口最多的省份。则命题（则命题（1 1）可表示为）可表示为。（2 2）设：王超是一个思想品德好的学生；）设：王超是一个思想品德好的学生；：王超是一个学习成绩好的学生；：王超是一个学习成绩好的学生；R R：王超是一个体育成绩好的学生。：王超是一个体育成绩好的学生。则命题（则命题（2 2）可表示为）可表示为RR。（3 3）设：教室的灯不亮可能是灯管坏了）设：教室的灯不亮可能是灯管坏了
38、 ：教室的灯不亮可能是停电了：教室的灯不亮可能是停电了 则命题（则命题（3 3）可表示为）可表示为。中北大学离散数学课程组中北大学离散数学课程组432/16/20232/16/2023（4 4）设：周末天气晴朗；）设：周末天气晴朗；：学院将组织我们到石像湖春游。：学院将组织我们到石像湖春游。则命题（则命题（4 4）可表示为）可表示为。（5 5）设：两个三角形全等；）设：两个三角形全等；：三角形的三条边全部相等。：三角形的三条边全部相等。则命题（则命题（5 5）可表示为）可表示为。(6)P:张辉与张辉与王丽是同学王丽是同学例例1.2.3 1.2.3 解解(续续)中北大学离散数学课程组中北大学离散
39、数学课程组442/16/20232/16/2023 为了不使句子产生混淆，作如下约定，为了不使句子产生混淆，作如下约定，命题联结命题联结词之优先级词之优先级如下：如下：1.1.否定否定合取合取析取析取条件条件等价等价2.2.同级的联结词，按其出现的先后次序同级的联结词，按其出现的先后次序(从左从左到右到右)3.3.若运算要求与优先次序不一致时，可使用若运算要求与优先次序不一致时，可使用括号括号；同级符号相邻时，也可使用括号。；同级符号相邻时，也可使用括号。括号中的运算为最优先级括号中的运算为最优先级。约约 定定中北大学离散数学课程组中北大学离散数学课程组452/16/20232/16/2023
40、设命题设命题P P：明天上午七点下雨；：明天上午七点下雨；Q Q：明天上午七点下雪；：明天上午七点下雪；R R：我将去学校。：我将去学校。符号化下述语句：符号化下述语句：1)1)如果如果明天上午七点明天上午七点不不是雨是雨夹夹雪，雪，则则我将去学校我将去学校2)2)如果如果明天上午七点明天上午七点不不下雨下雨并且并且不不下雪，下雪，则则我将去我将去学校学校3)3)如果如果明天上午七点下雨明天上午七点下雨或或下雪，下雪，则则我将我将不不去学校去学校4)4)明天上午我将明天上午我将雨雪无阻雨雪无阻一定去学校一定去学校可符号化为：可符号化为：(PQR)(PQR)(PQR)(PQR)(PQR)(PQR
41、)(PQR)(PQR)。或或 (PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)R(PQ)R。例题例题4 4可符号化为：可符号化为：(PQ)R(PQ)R。可符号化为可符号化为:(PQ)R:(PQ)R。可符号化为可符号化为:(PQ)R:(PQ)R。中北大学离散数学课程组中北大学离散数学课程组462/16/20232/16/20231.3 1.3 命题公式与真值表命题公式与真值表定义定义1.3.11.3.1 一个特定的命题是一个一个特定的命题是一个常值命题常值命题，它不是，它不是具有值具有值“T T”(“1 1”)，就是具有值，就是具有值“F F”(“0 0”)。而一个任意的没有赋予具体内容
42、的原子命题是一个变而一个任意的没有赋予具体内容的原子命题是一个变量命题，常称它为量命题，常称它为命题变量命题变量(或或命题变元命题变元)，该命题变，该命题变量无具体的真值，它的变域是集合量无具体的真值，它的变域是集合TT，F(F(或或00，1)1)注意注意(1)(1)复合命题为命题变元的复合命题为命题变元的“函数函数”,其函数值仍为其函数值仍为 真真 或或“假假”值。值。(2)(2)真值函数或命题公式，没有确切真值。真值函数或命题公式，没有确切真值。真值函数真值函数中北大学离散数学课程组中北大学离散数学课程组472/16/20232/16/20231.3.11.3.1命题公式命题公式定义定义1
43、.3.2(1.3.2(命题公式命题公式)1.1.命题变元本身是一个公式；命题变元本身是一个公式；2.2.如如G G是公式，则是公式，则(G)(G)也是公式；也是公式；3.3.如如G G，H H是公式，则是公式，则(GH)(GH)、(GH)(GH)、(GH)(GH)、(G(GH)H)也是公式；也是公式；4.4.仅由有限步使用规则仅由有限步使用规则1-31-3后产生的结果。该公式后产生的结果。该公式常用符号常用符号G G、H H、等表示。等表示。中北大学离散数学课程组中北大学离散数学课程组482/16/20232/16/2023符号串：符号串：P(QR)(Q(SR)P(QR)(Q(SR)；PQPQ
44、；P(PQ)P(PQ)；(PQ)(RQ)(PQ)(RQ)(PR)(PR)。等都是命题公式。等都是命题公式。例例1.3.11.3.1例例1.3.21.3.2符号串：符号串：(PQ)Q)(PQ)Q)；(PQ(R(PQ(R；PQPQ。等都不是合法的命题公式。等都不是合法的命题公式。中北大学离散数学课程组中北大学离散数学课程组492/16/20232/16/20231.3.2 1.3.2 公式的解释与真值表公式的解释与真值表定义定义1.3.3 1.3.3 设设P P1 1、P P2 2、P Pn n是出现在公式是出现在公式G G中的所中的所有命题变元，指定有命题变元，指定P P1 1、P P2 2、P
45、 Pn n一组真值，则这组一组真值，则这组真值称为真值称为G G的一个的一个解释或指派解释或指派,常记为常记为。一般来说，若有个命题变元，则应有一般来说，若有个命题变元，则应有2 2n n个不个不同的解释。同的解释。如果公式如果公式G G在解释下是真的，则称在解释下是真的，则称满足满足G G；如；如果果G G在解释下是假的，则称在解释下是假的，则称不满足不满足G G。定义定义1.3.41.3.4 将公式将公式G G在其在其所有所有可能解释下的真值情况可能解释下的真值情况列成表，称为列成表，称为G G的的真值表真值表。中北大学离散数学课程组中北大学离散数学课程组50构造真值表的步骤构造真值表的步
46、骤:(1)找出公式中所含的全部命题变元找出公式中所含的全部命题变元p1,p2,pn(若若无下角标则按字母顺序排列无下角标则按字母顺序排列),列出列出2n个全部赋值个全部赋值,从从000开始开始,按二进制加法按二进制加法,每次加每次加1,直至直至111为止。为止。(2)按从低到高的顺序写出公式的各个层次。按从低到高的顺序写出公式的各个层次。(3)对每个赋值依次计算各层次的真值对每个赋值依次计算各层次的真值,直到最后计直到最后计算出公式的真值为止。算出公式的真值为止。1.3.2 1.3.2 公式的解释与真值表公式的解释与真值表中北大学离散数学课程组中北大学离散数学课程组512/16/20232/1
47、6/2023例例1.3.21.3.2求下面公式的真值表：求下面公式的真值表：(P(P(P PQ)R)QQ)R)Q 其中，、是的所有命题变元。其中，、是的所有命题变元。P Q R P PQ(PQ)RP(PQ)R)G0 0 0 10 0 110 0 1 10 0 110 1 0 1 1 0 1 10 1 1 1 1 1 111 0 0 0 1 0 001 0 1 0 1 1 111 1 0 0 0 0 011 1 1 0 0 0 01中北大学离散数学课程组中北大学离散数学课程组522/16/20232/16/2023例例1.3.21.3.2（续）（续）P Q R(P(PQ)R)Q0 0 010 0
48、 110 1 010 1 111 0 001 0 111 1 011 1 1 1进一步化简为：进一步化简为：中北大学离散数学课程组中北大学离散数学课程组532/16/20232/16/2023例例1.3.31.3.3 P Q()()()(Q)0 0 1 00 0 1 1 00 1 01 00 1 11 10 求下面这组公式的真值表：求下面这组公式的真值表：1 1 ()；2 2()；3 3 ()(Q)Q)。中北大学离散数学课程组中北大学离散数学课程组542/16/20232/16/2023从这三个真值表可以看到一个非常有趣的事实：从这三个真值表可以看到一个非常有趣的事实：公式公式G G1 1对所
49、有可能的解释具有对所有可能的解释具有“真真”值值 公式公式G G3 3对所有可能的解释均具有对所有可能的解释均具有“假假”值值 公式公式G G2 2则具有则具有“真真”和和“假假”值值结论结论中北大学离散数学课程组中北大学离散数学课程组552/16/20232/16/2023定义定义1.3.51.3.51.1.公式公式G G称为称为永真公式永真公式(重言式重言式)，如果在它的所有，如果在它的所有解释之下都为解释之下都为“真真”。2.2.公式公式G G称为称为永假公式永假公式(矛盾式矛盾式),),如果在它的所有如果在它的所有解释之下都为解释之下都为“假假”。3.3.公式公式G G称为称为可满足的
50、可满足的，如果它不是永假的。，如果它不是永假的。中北大学离散数学课程组中北大学离散数学课程组562/16/20232/16/2023从上述定义可知三种特殊公式之间的关系：从上述定义可知三种特殊公式之间的关系：1)1)永真式永真式G G的否定的否定 G G是矛盾式；矛盾式是矛盾式；矛盾式G G的否定的否定 G G是是永真式。永真式。2)2)永真式一定是可满足式永真式一定是可满足式,可满足式不一定是永真式可满足式不一定是永真式3)3)可满足式的否定不一定为不可满足式可满足式的否定不一定为不可满足式(即为矛盾式即为矛盾式)结论结论中北大学离散数学课程组中北大学离散数学课程组572/16/20232/
