(1.2)--离散数学离散数学.ppt

《(1.2)--离散数学离散数学.ppt》由会员分享，可在线阅读，更多相关《(1.2)--离散数学离散数学.ppt（205页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2024/1/202024/1/20离散数学离散数学1 1离 散 数 学2024/1/202024/1/20离散数学离散数学2 2问题：为什么要开设问题：为什么要开设离散数学离散数学课程？课程？离散数学离散数学是什么？是什么？是数学课程吗？是数学课程吗？有什么作用？有什么作用？为什么要学数学课程？为什么要学数学课程？2024/1/202024/1/20离散数学离散数学3 3客观世客观世界界现象现象的两种分类？的两种分类？u确定性现象与随机性现象确定性现象与随机性现象u连续性现象与连续性现象与离散性现象离散性现象2024/1/202024/1/20离散数学离散数学4 4离散数学离散数学l现代数学

2、的一个重要分支现代数学的一个重要分支l计算机类专业的一门重要基础课（核心课计算机类专业的一门重要基础课（核心课程）程）l研究的对象是研究的对象是离散数离散数量量和和离散结离散结构构的数的数学学模型。模型。2024/1/202024/1/20离散数学离散数学5 5为什么要研究和学习它？为什么要研究和学习它？（计算机）（计算机）由于数字电子计算机是一个离散结构，它只能由于数字电子计算机是一个离散结构，它只能处理离散的或离散化了的数量关系。处理离散的或离散化了的数量关系。面临着面临着p如何对离散结构建立相应的数学模型；如何对离散结构建立相应的数学模型；p如何将已用连续数量关系建立起来的数学模如何将已

3、用连续数量关系建立起来的数学模型离散化，从而可由计算机加以处理。型离散化，从而可由计算机加以处理。2024/1/202024/1/20离散数学离散数学6 6离散数学离散数学l工具作用：工具作用：计算机与信息科学的基础计算机与信息科学的基础如应用在如应用在数字电路、编译原理、数据结构、操作数字电路、编译原理、数据结构、操作系统、数据库系统、算法设计与分析、人工智能、计系统、数据库系统、算法设计与分析、人工智能、计算机网络算机网络等专业课程等专业课程中。中。l思维训练：思维训练：数学是思维的体操数学是思维的体操n概括抽象能力、逻辑思维能力、归纳构造能力的概括抽象能力、逻辑思维能力、归纳构造能力的提

4、高提高“一个数学的抽象，包含无穷个现实。一个数学的抽象，包含无穷个现实。”n严谨、完整、规范严谨、完整、规范的科学态度的培养。的科学态度的培养。2024/1/202024/1/20离散数学离散数学7 7离散数学离散数学的内容十分丰富，最重要，最核的内容十分丰富，最重要，最核心的是：心的是：数理逻辑、集合论、代数系统数理逻辑、集合论、代数系统和和图论图论，本，本课程主要讲授以上四个方面的内容。课程主要讲授以上四个方面的内容。本课程主要介绍本课程主要介绍离散数学离散数学的各个分支的基的各个分支的基本概念、基本理论和基本方法，本概念、基本理论和基本方法，共共48学时学时。2024/1/202024/

5、1/20离散数学离散数学8 8二、集合论二、集合论二、集合论二、集合论四、图论四、图论四、图论四、图论三、代数结构三、代数结构三、代数结构三、代数结构命题逻辑命题逻辑命题逻辑命题逻辑一阶逻辑一阶逻辑一阶逻辑一阶逻辑集合的基本概念和运算集合的基本概念和运算集合的基本概念和运算集合的基本概念和运算二元函数和关系二元函数和关系二元函数和关系二元函数和关系代数系统的一般性质代数系统的一般性质代数系统的一般性质代数系统的一般性质典型的代数系统典型的代数系统典型的代数系统典型的代数系统图的基本概念图的基本概念图的基本概念图的基本概念特殊的图特殊的图特殊的图特殊的图树树树树一、数理逻辑一、数理逻辑一、数理逻

6、辑一、数理逻辑本课程的学习内容本课程的学习内容独立性独立性2024/1/202024/1/20离散数学离散数学9 9教材与教学参考书教材：教材：邓毅雄主编，邓毅雄主编，离散数学离散数学（修订版）（修订版），江西高校出版社，江西高校出版社，2013.1参考书参考书：耿素云、屈婉玲、张立昂，离散数学（第三版），耿素云、屈婉玲、张立昂，离散数学（第三版），清华大学出版社清华大学出版社,2004.屈婉玲、耿素云、张立昂，离散数学题解（修订版）屈婉玲、耿素云、张立昂，离散数学题解（修订版），清华大学出版社，清华大学出版社，2004.等等等等.2024/1/202024/1/20离散数学离散数学1010本

7、课程成绩评定本课程成绩评定（考试）（考试）总成绩=作业16分 课堂测验、提问16分 平时表现（含期中考试）8分 +期末考试60分2024/1/202024/1/20离散数学离散数学1111我的联系方式：我的联系方式：学习群：2021春邓老师离散学习交流群283379560个人QQ：风中求静 244946824个人微信公众号：老青年凳子手机号：13970827183欢迎联系！2024/1/202024/1/20离散数学离散数学1212老青年凳子老青年凳子个人微信公众号个人微信公众号2024/1/202024/1/20离散数学离散数学1313 逻辑学逻辑学逻辑学逻辑学:研究思维研究思维研究思维研究

8、思维(或推理或推理或推理或推理)的形式结构和规的形式结构和规的形式结构和规的形式结构和规律的学科。律的学科。律的学科。律的学科。数理逻辑数理逻辑这里所指的这里所指的数学方法数学方法就是引进一套符号体系的方法。就是引进一套符号体系的方法。所以数理逻辑又称所以数理逻辑又称符号逻辑符号逻辑，它是从量的侧面来研，它是从量的侧面来研究思维规律的。究思维规律的。数理逻辑数理逻辑数理逻辑数理逻辑：是用数学方法来研究推理的形式：是用数学方法来研究推理的形式：是用数学方法来研究推理的形式：是用数学方法来研究推理的形式结构和推理规律的数学学科。结构和推理规律的数学学科。结构和推理规律的数学学科。结构和推理规律的数

9、学学科。2024/1/202024/1/20离散数学离散数学1414 计计计计算算算算机机机机及及及及计计计计算算算算机机机机科科科科学学学学与与与与数数数数理理理理逻逻逻逻辑辑辑辑有有有有着着着着十十十十分分分分密密密密切切切切的的的的关关关关系系系系。人人人人们们们们说说说说数数数数字字字字电电电电子子子子计计计计算算算算机机机机是是是是数数数数理理理理逻逻逻逻辑辑辑辑与与与与电电电电子子子子学学学学结结结结合合合合的的的的产物产物产物产物。数理逻辑与计算机数理逻辑与计算机使用计算机必须首先学会编使用计算机必须首先学会编“程序程序”，那么什么，那么什么是程序？是程序？程序算法数据程序算法数

10、据算法逻辑控制算法逻辑控制2024/1/202024/1/20离散数学离散数学1515数理逻辑数理逻辑 本本本本课课课课程程程程介介介介绍绍绍绍的的的的是是是是数数数数理理理理逻逻逻逻辑辑辑辑最最最最基基基基本本本本的的的的内内内内容容容容，也也也也是是是是与与与与计计计计算算算算机机机机科科科科学学学学关关关关系系系系最最最最为为为为密密密密切切切切的的的的：命命命命题题题题逻逻逻逻辑辑辑辑和和和和谓谓谓谓词词词词逻逻逻逻辑辑辑辑（一阶逻辑）（一阶逻辑）（一阶逻辑）（一阶逻辑）现代数理逻辑可分为现代数理逻辑可分为现代数理逻辑可分为现代数理逻辑可分为逻辑演算逻辑演算逻辑演算逻辑演算、证明论证明

11、论证明论证明论、公公公公理集合论理集合论理集合论理集合论、递归论递归论递归论递归论和和和和模型论模型论模型论模型论。2024/1/202024/1/20离散数学离散数学1616第一章第一章 命题逻辑命题逻辑 1.11.1 命题符号化及联结词命题符号化及联结词命题符号化及联结词命题符号化及联结词 1.21.2 命题公式及分类命题公式及分类命题公式及分类命题公式及分类 1.31.3 等值演算等值演算等值演算等值演算 1.41.4 联结词全功能集联结词全功能集联结词全功能集联结词全功能集 1.51.5 对偶与范式对偶与范式对偶与范式对偶与范式 1.61.6 推理理论推理理论推理理论推理理论 重点重点

12、：命题概念及其：命题概念及其符号化、命题公式化简、符号化、命题公式化简、范式、推理规则。范式、推理规则。难点难点：推理理论及应：推理理论及应用。用。2024/1/202024/1/20离散数学离散数学1717内容：命题，逻辑联结词，命题符号化内容：命题，逻辑联结词，命题符号化重点：重点：(1)掌握命题概念掌握命题概念(2)掌握联结词含义及真值表掌握联结词含义及真值表(3)掌握命题符号化方法掌握命题符号化方法1.1 1.1 命题符号化及联结词命题符号化及联结词2024/1/202024/1/20离散数学离散数学1818思考：思考：我们是怎么思考问题，是怎么进行判断的？我们是怎么思考问题，是怎么进

13、行判断的？一个简单的推理问题一个简单的推理问题前提前提1：今天上数学课或英语课：今天上数学课或英语课前提前提2：今天不上英语课：今天不上英语课结论：今天上数学课结论：今天上数学课数理逻辑研究的中心问题是数理逻辑研究的中心问题是数理逻辑研究的中心问题是数理逻辑研究的中心问题是推理推理推理推理，而推理的前提和结论都，而推理的前提和结论都，而推理的前提和结论都，而推理的前提和结论都是表达判断的陈述句，因而表达判断的陈述句构成了推理的基是表达判断的陈述句，因而表达判断的陈述句构成了推理的基是表达判断的陈述句，因而表达判断的陈述句构成了推理的基是表达判断的陈述句，因而表达判断的陈述句构成了推理的基本单位

14、。本单位。本单位。本单位。2024/1/202024/1/20离散数学离散数学1919一、命题的概念命题：命题：命题：命题：能判断真假的陈述句能判断真假的陈述句能判断真假的陈述句能判断真假的陈述句。这种判断的结果只两种这种判断的结果只两种这种判断的结果只两种这种判断的结果只两种 正确正确正确正确 orororor 错误错误错误错误命题真值：命题真值：命题真值：命题真值：判断为正确的命题称其命题真值为判断为正确的命题称其命题真值为判断为正确的命题称其命题真值为判断为正确的命题称其命题真值为真真真真或或或或T T(Ture)(Ture)或或或或1 1；判断为错误的命题称其命题真值为判断为错误的命题

15、称其命题真值为判断为错误的命题称其命题真值为判断为错误的命题称其命题真值为假假假假或或或或F F(False)(False)或或或或0 0；命题是具有唯一真值的陈述句。命题是具有唯一真值的陈述句。命题是具有唯一真值的陈述句。命题是具有唯一真值的陈述句。真值不是说该命题的值必为真。真值不是说该命题的值必为真。2024/1/202024/1/20离散数学离散数学2020例1 判断下列句子中那些是命题。(1)(1)2 2是素数。是素数。是素数。是素数。(2)(2)2+3=52+3=5。(3)(3)雪是黑色的。雪是黑色的。雪是黑色的。雪是黑色的。(4)(4)3 3能被能被能被能被2 2整除。整除。整除

16、。整除。(是是是是)(是是是是)(是是是是)(是是是是)真值确定的陈述句是命题真值确定的陈述句是命题1100真值真值2024/1/202024/1/20离散数学离散数学2121例1 判断下列句子中那些是命题。(5)(5)5 5x x+111+111.(6)xy.(6)xy.(否否否否)(否否否否)真值不唯一陈述句真值不唯一陈述句不是命题不是命题2024/1/202024/1/20离散数学离散数学2222例1 判断下列句子中那些是命题。(7)(7)明年十月一号是晴天。明年十月一号是晴天。明年十月一号是晴天。明年十月一号是晴天。(8)(8)火星上存在生命。火星上存在生命。火星上存在生命。火星上存在

17、生命。(是是是是)(是是是是)真值目前不确定，但未来将确定的陈述句是命题真值目前不确定，但未来将确定的陈述句是命题真值？真值？2024/1/202024/1/20离散数学离散数学2323例1 判断下列句子中那些是命题。(9)(9)你需要帮助吗？你需要帮助吗？(10)(10)软件学院的男生真帅！软件学院的男生真帅！(11)请勿闯红灯！请勿闯红灯！(否否否否)(否否否否)疑问句、感叹句、祈使句疑问句、感叹句、祈使句不不是命题是命题(否否否否)吸烟有害健康。吸烟有害健康吗？吸烟有害健康呀！不准吸烟！2024/1/202024/1/20离散数学离散数学24242024/1/202024/1/20离散数

18、学离散数学2525孤岛历险记孤岛历险记2024/1/202024/1/20离散数学离散数学2626例1 判断下列句子中那些是命题。(12)(12)我说的是假话我说的是假话.(13)(13)我专门给不给自己理发的人理发我专门给不给自己理发的人理发我专门给不给自己理发的人理发我专门给不给自己理发的人理发.(否否否否)(否否否否)悖论悖论不是命题不是命题解题思想：判断一个句子是否为命题，一看它是解题思想：判断一个句子是否为命题，一看它是解题思想：判断一个句子是否为命题，一看它是解题思想：判断一个句子是否为命题，一看它是否为陈述句，否为陈述句，否为陈述句，否为陈述句，二看它的真值是否唯一。二看它的真值

19、是否唯一。二看它的真值是否唯一。二看它的真值是否唯一。命题有命题有两个条件两个条件，首先它是一个陈述句，首先它是一个陈述句，其次，它具有唯一的一个真值。其次，它具有唯一的一个真值。2024/1/202024/1/20离散数学离散数学2727下列句子哪些是命题：下列句子哪些是命题：下列句子哪些是命题：下列句子哪些是命题：（学生答）（学生答）（学生答）（学生答）（1 1 1 1）8 8 8 8小于小于小于小于12121212。（2 2 2 2）8 8 8 8大于大于大于大于12121212。（3 3 3 3）8 8 8 8大于大于大于大于12121212吗？吗？吗？吗？（4 4 4 4）请勿沉迷网

20、络。）请勿沉迷网络。）请勿沉迷网络。）请勿沉迷网络。（5 5 5 5）任何一个大于）任何一个大于）任何一个大于）任何一个大于5 5 5 5的偶数可表成两个素数的和。的偶数可表成两个素数的和。的偶数可表成两个素数的和。的偶数可表成两个素数的和。（6 6 6 6）未来，人类将住在月球。未来，人类将住在月球。未来，人类将住在月球。未来，人类将住在月球。（7 7 7 7）X=YX=YX=YX=Y。（当（当（当（当X X X X、Y Y Y Y给定值时？）给定值时？）给定值时？）给定值时？）（8 8 8 8）我说的这句话是假的。我说的这句话是假的。我说的这句话是假的。我说的这句话是假的。2024/1/2

21、02024/1/20离散数学离散数学2828二、与命题相关的几个概念1 1、简单命题或原子命题：简单命题或原子命题：简单命题或原子命题：简单命题或原子命题：简单的陈述句，不能再分解成更简单的句子。简单的陈述句，不能再分解成更简单的句子。简单的陈述句，不能再分解成更简单的句子。简单的陈述句，不能再分解成更简单的句子。一般用英文字母一般用英文字母一般用英文字母一般用英文字母p p,q q,r r,表示。表示。表示。表示。这样的命题是不可再分割了，如再分割就不是命题了。这样的命题是不可再分割了，如再分割就不是命题了。在简单命题中，尽管常有主语和谓语，但我们暂时不去加以在简单命题中，尽管常有主语和谓语

22、，但我们暂时不去加以分割，将简单命题作为一个不可分的整体看待，进而作命题演分割，将简单命题作为一个不可分的整体看待，进而作命题演算。在谓词逻辑里，才对命题中的主谓结构进行深入分析。算。在谓词逻辑里，才对命题中的主谓结构进行深入分析。2024/1/202024/1/20离散数学离散数学2929二、与命题相关的几个概念（续）2 2、命题常项或命题常元：命题常项或命题常元：命题常项或命题常元：命题常项或命题常元：由于简单命题的真值确定，故又称之为命题常项由于简单命题的真值确定，故又称之为命题常项由于简单命题的真值确定，故又称之为命题常项由于简单命题的真值确定，故又称之为命题常项 或命题常元。或命题常

23、元。或命题常元。或命题常元。3 3、命题变项或命题变元：命题变项或命题变元：命题变项或命题变元：命题变项或命题变元：真值可以变化的简单陈述句，但它不是命题。真值可以变化的简单陈述句，但它不是命题。真值可以变化的简单陈述句，但它不是命题。真值可以变化的简单陈述句，但它不是命题。2024/1/202024/1/20离散数学离散数学3030二、与命题相关的几个概念（续）4 4、复合命题：复合命题：复合命题：复合命题：由简单命题用由简单命题用由简单命题用由简单命题用联结词联结词联结词联结词联结而成的命题。联结而成的命题。联结而成的命题。联结而成的命题。命题逻辑主要就是研究复合命题。即命题逻辑主要就是研

24、究复合命题。即命题逻辑主要就是研究复合命题。即命题逻辑主要就是研究复合命题。即命题逻辑所讨论命题逻辑所讨论的正是多个命题联结而成的复合命题的规律性。的正是多个命题联结而成的复合命题的规律性。5 5、命题的符号化：命题的符号化：命题的符号化：命题的符号化：将表示命题的符号放在该命题的前面。将表示命题的符号放在该命题的前面。将表示命题的符号放在该命题的前面。将表示命题的符号放在该命题的前面。如如如如 p p：我是中国人；：我是中国人；：我是中国人；：我是中国人；q q：2 2 2 22 2 2 27 7 7 7p的真值为的真值为1，q的真值为的真值为0。2024/1/202024/1/20离散数学

25、离散数学3131三、联结词先看一个例子：先看一个例子：先看一个例子：先看一个例子：例例例例2 2：判断下列命题是否为复合命题，说出其联结词。：判断下列命题是否为复合命题，说出其联结词。：判断下列命题是否为复合命题，说出其联结词。：判断下列命题是否为复合命题，说出其联结词。(1)(1)3 3不是偶数。不是偶数。不是偶数。不是偶数。(2)(2)2 2是素数和偶数。是素数和偶数。是素数和偶数。是素数和偶数。(3)(3)林芳学过英语或日语。林芳学过英语或日语。林芳学过英语或日语。林芳学过英语或日语。(4)(4)如果角如果角如果角如果角A A和角和角和角和角B B是对顶角，则角是对顶角，则角是对顶角，则

26、角是对顶角，则角A A等于角等于角等于角等于角B B。(5)(5)我去上街我去上街我去上街我去上街当且仅当我有时间。当且仅当我有时间。当且仅当我有时间。当且仅当我有时间。(非非非非)(且且且且)(或或或或)(如果如果如果如果,则则则则)(当且仅当当且仅当当且仅当当且仅当)2024/1/202024/1/20离散数学离散数学3232三、联结词（续）常见的基本联结词：常见的基本联结词：常见的基本联结词：常见的基本联结词：1 1、否定联结词、否定联结词、否定联结词、否定联结词“”，读作，读作，读作，读作“非非非非”。复合命题复合命题复合命题复合命题“非非非非p p”称作称作称作称作p p 的否定式，

27、记作的否定式，记作的否定式，记作的否定式，记作“p p”。p p 为真当且仅当为真当且仅当为真当且仅当为真当且仅当p p 为假。为假。为假。为假。在例在例在例在例2(1)2(1)中，设中，设中，设中，设p p 表示表示表示表示“3 3是偶数是偶数是偶数是偶数”，则则则则 p p 表示表示表示表示p p p p1 10 00 01 1真值表真值表真假对换真假对换“3“3不是偶数不是偶数不是偶数不是偶数”。p p 真值为真值为真值为真值为0 0，p p 真值为真值为真值为真值为1 1。2024/1/202024/1/20离散数学离散数学3333 又如：又如：又如：又如：“昨天张三去看球赛了昨天张三

28、去看球赛了昨天张三去看球赛了昨天张三去看球赛了”。这命题以。这命题以。这命题以。这命题以P P P P表示，于是表示，于是表示，于是表示，于是“昨天张三没有去看球赛昨天张三没有去看球赛昨天张三没有去看球赛昨天张三没有去看球赛”，这新命题便可用，这新命题便可用，这新命题便可用，这新命题便可用 表示了。表示了。表示了。表示了。若昨天张三去看球赛了，命题若昨天张三去看球赛了，命题若昨天张三去看球赛了，命题若昨天张三去看球赛了，命题P P P P是真的，那么新命题是真的，那么新命题是真的，那么新命题是真的，那么新命题 P P P P必然必然必然必然是是是是 。反之，若命题。反之，若命题。反之，若命题。

29、反之，若命题P P P P是假的，那么是假的，那么是假的，那么是假的，那么 P P P P就是就是就是就是 。如如如如:Q:Q:Q:Q:今天是星期三。今天是星期三。今天是星期三。今天是星期三。Q:Q:Q:Q:如：（如：（如：（如：（1 1 1 1）p:p:p:p:塑料不是金属。塑料不是金属。塑料不是金属。塑料不是金属。（2 2 2 2）p p:P P假的假的假的假的真的真的真的真的今天不是星期三。今天不是星期三。今天不是星期三。今天不是星期三。塑料是金属。塑料是金属。塑料是金属。塑料是金属。2024/1/202024/1/20离散数学离散数学3434三、联结词（续）2 2、合取联结词、合取联结

30、词、合取联结词、合取联结词“”，读作，读作，读作，读作“合取合取合取合取”。复合命题复合命题复合命题复合命题“p p并并并并且且且且q q”称作称作称作称作p p 与与与与q q 的合取式，记的合取式，记的合取式，记的合取式，记“p p q q”。p p q q 为真当且仅当为真当且仅当为真当且仅当为真当且仅当p p 与与与与q q 同时为真。同时为真。同时为真。同时为真。联结词联结词联结词联结词“既既既既又又又又”，“不不不不但但但但而且而且而且而且”，“虽然虽然虽然虽然但是但是但是但是”等，都可符号化为等，都可符号化为等，都可符号化为等，都可符号化为 。p p q qp p q q0 00

31、 00 00 01 10 01 10 00 01 11 11 1真值表真值表真值表真值表同真则真同真则真同真则真同真则真2024/1/202024/1/20离散数学离散数学3535三、联结词（续）在例在例在例在例2 2(2 2)中，设中，设中，设中，设 p p：“2 2是素数是素数是素数是素数”，q q：“2 2是偶数是偶数是偶数是偶数”，则则则则 p p q q：因为因为因为因为 p p和和和和q q 的的的的真值均为真值均为真值均为真值均为1 1，所以所以所以所以 p p q q 的的的的真值真值真值真值“2“2是素数和偶数是素数和偶数是素数和偶数是素数和偶数”。为为为为1 1。设设设设

32、p:p:p:p:教室里有教室里有教室里有教室里有10101010名女同学。名女同学。名女同学。名女同学。q:q:q:q:教室里有教室里有教室里有教室里有15151515名男同学。名男同学。名男同学。名男同学。p p p pq:q:q:q:教室里有教室里有教室里有教室里有10101010名女同学与名女同学与名女同学与名女同学与15151515名男同学。名男同学。名男同学。名男同学。2024/1/202024/1/20离散数学离散数学3636三、联结词（续）设设设设 p:p:p:p:今天下雨了。今天下雨了。今天下雨了。今天下雨了。q:q:q:q:教室里有教室里有教室里有教室里有1001001001

33、00张桌子。张桌子。张桌子。张桌子。pq:pq:pq:pq:今天下雨了并且教室里有今天下雨了并且教室里有今天下雨了并且教室里有今天下雨了并且教室里有100100100100张桌子张桌子张桌子张桌子.复合命题通过复合命题通过复合命题通过复合命题通过还可得到复合命题的复合命题。还可得到复合命题的复合命题。还可得到复合命题的复合命题。还可得到复合命题的复合命题。复合命题的真值，不能根据参与复合的命题之复合命题的真值，不能根据参与复合的命题之间是否存在联系来判断。间是否存在联系来判断。2024/1/202024/1/20离散数学离散数学3737三、联结词（续）“和”之“不和”日常自然用语里的联结词日常

34、自然用语里的联结词日常自然用语里的联结词日常自然用语里的联结词“和和和和”、“与与与与”、“并且并且并且并且”，一般，一般，一般，一般是表示两种同类有关事物的并列关系的。是表示两种同类有关事物的并列关系的。是表示两种同类有关事物的并列关系的。是表示两种同类有关事物的并列关系的。但但但但“”同同同同“与与与与”、“并且并且并且并且”又不能等同视之。又不能等同视之。又不能等同视之。又不能等同视之。在进行命题的形式化时，不能见到在进行命题的形式化时，不能见到在进行命题的形式化时，不能见到在进行命题的形式化时，不能见到“和和和和”，“与与与与”就用就用就用就用“”。例如，例如，例如，例如，“李文与李武

35、是兄弟李文与李武是兄弟李文与李武是兄弟李文与李武是兄弟”，“王芳和陈兰是好朋友王芳和陈兰是好朋友王芳和陈兰是好朋友王芳和陈兰是好朋友”，这两个命题中分别有这两个命题中分别有这两个命题中分别有这两个命题中分别有 和和和和 及及及及 与与与与 字，可是它们都是字，可是它们都是字，可是它们都是字，可是它们都是简单命题而不是复合命题。简单命题而不是复合命题。简单命题而不是复合命题。简单命题而不是复合命题。2024/1/202024/1/20离散数学离散数学3838三、联结词（续）3 3、析取联结词、析取联结词、析取联结词、析取联结词“”，读作，读作，读作，读作“析取析取析取析取”。复合命题复合命题复合

36、命题复合命题“p p或或或或q q”称作称作称作称作 p p与与与与q q 的析取式，记作的析取式，记作的析取式，记作的析取式，记作“p p q q”。p p q q 为真当且仅当为真当且仅当为真当且仅当为真当且仅当 p p 与与与与 q q 中至少一个为真。中至少一个为真。中至少一个为真。中至少一个为真。当当当当p p p p、q q q q有一取值为有一取值为有一取值为有一取值为1 1 1 1时时时时,p,p,p,pq q q q便便便便为为为为1 1 1 1。仅当。仅当。仅当。仅当p p p p、q q q q均取均取均取均取0 0 0 0值时值时值时值时,pqpqpqpq方为方为方为方

37、为0 0 0 0。这就是析取词的定义这就是析取词的定义这就是析取词的定义这就是析取词的定义,p,p,p,pq q q q可可可可用来表示自然用语用来表示自然用语用来表示自然用语用来表示自然用语p p p p或或或或q q q q。p p q qp p q q0 00 00 00 01 11 11 10 01 11 11 11 1真值表真值表真值表真值表同假则假同假则假同假则假同假则假2024/1/202024/1/20离散数学离散数学3939三、联结词（续）例例:（1 1）p:p:今天刮风。今天刮风。q:q:今天下雨。今天下雨。(2)(2)p p:“:“林芳学过英语林芳学过英语林芳学过英语林芳

38、学过英语”，q q:“:“林芳学过日语林芳学过日语林芳学过日语林芳学过日语”。(3)(3)p p:2:2小于小于3 3。q:q:雪是黑的。雪是黑的。pqpq：p p q q:2 2小于小于3 3或者或者雪是黑的。雪是黑的。今天刮风今天刮风或者或者下雨。下雨。林芳学过英语林芳学过英语林芳学过英语林芳学过英语或或或或日语日语日语日语”。pq:pq:pq:pq:由于由于2 2小于小于3 3是真的是真的,所以所以pqpq的取值为真的取值为真,尽尽管管 雪是黑的雪是黑的 这命题取假。这命题取假。2024/1/202024/1/20离散数学离散数学4040三、联结词（续）“或”之有异在自然语言中的在自然语

39、言中的“或或”具有二义性，具有二义性，有时表示的是有时表示的是相容性或，有时表示的是不相容性或（即排斥或）相容性或，有时表示的是不相容性或（即排斥或）。例如：例如：（1 1）张三或者李四考了张三或者李四考了张三或者李四考了张三或者李四考了9090分。分。分。分。（2 2）第一节课上数学课或者上英语课。第一节课上数学课或者上英语课。第一节课上数学课或者上英语课。第一节课上数学课或者上英语课。（3 3）小张出生）小张出生）小张出生）小张出生于于于于20002000年或年或年或年或20012001年年年年。（4 4）派小王或小李中的一人去开会。）派小王或小李中的一人去开会。）派小王或小李中的一人去开

40、会。）派小王或小李中的一人去开会。（1）是相容或，（）是相容或，（2）（）（3）（）（4）是排斥或。）是排斥或。2024/1/202024/1/20离散数学离散数学4141三、联结词（续）请同学们再举几个排斥或的例子！请同学们再举几个排斥或的例子！这类这类这类这类“或或或或”称为称为称为称为 排斥或排斥或排斥或排斥或。符号化：符号化：符号化：符号化：(p p q q)(p p q q)符号化？符号化？（2）（3）可以用两种方式表示，但（）可以用两种方式表示，但（4）只）只能用一种方式表示。能用一种方式表示。2024/1/202024/1/20离散数学离散数学4242三、联结词（续）4 4、蕴涵

41、联结词、蕴涵联结词、蕴涵联结词、蕴涵联结词“”，读作，读作，读作，读作“蕴蕴蕴蕴涵涵涵涵”。复合命题复合命题复合命题复合命题“如果如果如果如果 p p，则，则，则，则 q q”称作称作称作称作p p 与与与与q q 的的的的蕴蕴蕴蕴涵涵涵涵式式式式，记作，记作，记作，记作“p p q q”。其中其中其中其中 p p 称为蕴称为蕴称为蕴称为蕴涵涵涵涵式的式的式的式的前件前件前件前件，q q 称为蕴称为蕴称为蕴称为蕴涵涵涵涵式的式的式的式的后件后件后件后件。p p q q 为假当且仅当为假当且仅当为假当且仅当为假当且仅当 p p 为真且为真且为真且为真且 q q 为假。为假。为假。为假。p p q

42、 q:p p为为为为q q的充分条件，的充分条件，的充分条件，的充分条件，q q为为为为p p的必要条件。的必要条件。的必要条件。的必要条件。p p q qp p q q0 00 01 10 01 11 11 10 00 01 11 11 1真值表真值表真值表真值表前真后假则假前真后假则假2024/1/202024/1/20离散数学离散数学4343三、联结词（续）例如：一位父亲对儿子说：例如：一位父亲对儿子说：例如：一位父亲对儿子说：例如：一位父亲对儿子说：“如果我去书店，就一定给如果我去书店，就一定给如果我去书店，就一定给如果我去书店，就一定给你买本你买本你买本你买本儿童画报儿童画报儿童画报

43、儿童画报。”问：什么情况下父亲食言？问：什么情况下父亲食言？问：什么情况下父亲食言？问：什么情况下父亲食言？解：可能情况有四种：解：可能情况有四种：解：可能情况有四种：解：可能情况有四种：(1)(1)(1)(1)父亲去了书店，给儿子买了父亲去了书店，给儿子买了父亲去了书店，给儿子买了父亲去了书店，给儿子买了儿童画报儿童画报儿童画报儿童画报。(2)(2)(2)(2)父亲去了书店，却没给儿子买父亲去了书店，却没给儿子买父亲去了书店，却没给儿子买父亲去了书店，却没给儿子买儿童画报儿童画报儿童画报儿童画报。(3)(3)(3)(3)父亲没去书店，却给儿子买了父亲没去书店，却给儿子买了父亲没去书店，却给儿

44、子买了父亲没去书店，却给儿子买了儿童画报儿童画报儿童画报儿童画报。(4)(4)(4)(4)父亲没去书店，也没给儿子买父亲没去书店，也没给儿子买父亲没去书店，也没给儿子买父亲没去书店，也没给儿子买儿童画报儿童画报儿童画报儿童画报。显然，显然，显然，显然，(1)(1)(1)(1)、(4)(4)(4)(4)父亲没有食言，父亲没有食言，父亲没有食言，父亲没有食言，(3)(3)(3)(3)与父亲的许诺没有与父亲的许诺没有与父亲的许诺没有与父亲的许诺没有抵触，当然也没有食言，只有抵触，当然也没有食言，只有抵触，当然也没有食言，只有抵触，当然也没有食言，只有(2)(2)(2)(2)算食言，而这种情况算食言，

45、而这种情况算食言，而这种情况算食言，而这种情况正好对应蕴涵式为假的正好对应蕴涵式为假的正好对应蕴涵式为假的正好对应蕴涵式为假的“前件真后件假前件真后件假前件真后件假前件真后件假”的条件。的条件。的条件。的条件。前真后假则假？前真后假则假？452024/1/202024/1/20离散数学离散数学4444三、联结词（续）根据根据根据根据p p p pq q q q真假值取法的定义可以看出，真假值取法的定义可以看出，真假值取法的定义可以看出，真假值取法的定义可以看出，若若若若p p p p为假，不论为假，不论为假，不论为假，不论q q q q是否为真，则是否为真，则是否为真，则是否为真，则p p p

46、 pq q q q为真。为真。为真。为真。我们来看命题：我们来看命题：我们来看命题：我们来看命题：如果月亮从西边出来，则太阳也从西边出来。如果月亮从西边出来，则太阳也从西边出来。如果月亮从西边出来，则太阳也从西边出来。如果月亮从西边出来，则太阳也从西边出来。由定义这是一个真命题，但完全可以认为这个命题由定义这是一个真命题，但完全可以认为这个命题由定义这是一个真命题，但完全可以认为这个命题由定义这是一个真命题，但完全可以认为这个命题毫无意义。然而我们感兴趣的主要是（数学）推理和证毫无意义。然而我们感兴趣的主要是（数学）推理和证毫无意义。然而我们感兴趣的主要是（数学）推理和证毫无意义。然而我们感兴

47、趣的主要是（数学）推理和证明的方法。明的方法。明的方法。明的方法。又又又又例如：例如：例如：例如：如果地球停止了转动，则大熊猫产在中国。如果地球停止了转动，则大熊猫产在中国。如果地球停止了转动，则大熊猫产在中国。如果地球停止了转动，则大熊猫产在中国。另外一个看上去有点困顿的例子：另外一个看上去有点困顿的例子：如果我认真学习，那么我离散通过。如果我认真学习，那么我离散通过。与与我不认真学习，或者我离散通过。我不认真学习，或者我离散通过。在意思上，相同吗？在意思上，相同吗？2024/1/202024/1/20离散数学离散数学45452024/1/202024/1/20离散数学离散数学4646三、联

48、结词（续）由由由由 p p p p q q q q的真值表的真值表的真值表的真值表,在在在在p p p p、q q q q的所有取值下的所有取值下的所有取值下的所有取值下,p,p,p,pq q q q同同同同 p p p p q q q q都有相同的真值都有相同的真值都有相同的真值都有相同的真值,于是可记作于是可记作于是可记作于是可记作 p p p pq q q q p p p p q q q q (真值相同的等值命题以真值相同的等值命题以真值相同的等值命题以真值相同的等值命题以联结联结联结联结)。这也说明。这也说明。这也说明。这也说明可由可由可由可由 、来表示来表示来表示来表示,从逻辑上看从

49、逻辑上看从逻辑上看从逻辑上看 如果如果如果如果p p p p则则则则qqqq同同同同 非非非非p p p p或或或或qqqq是等同的是等同的是等同的是等同的两个命题。两个命题。两个命题。两个命题。p p q q p p p p p p p p q q q qp pq q0 00 01 10 01 11 11 10 00 01 11 10 0真值表真值表真值表真值表11011101你能举个例吗？你能举个例吗？2024/1/202024/1/20离散数学离散数学4747q q为为为为p p的必要条件的必要条件的必要条件的必要条件“如果如果如果如果p p，那么，那么，那么，那么q q”的不同表述：的

50、不同表述：的不同表述：的不同表述：（1 1）“p p仅当仅当仅当仅当q q”；（2 2）“q q每当每当每当每当p p”；（3 3）“只要只要只要只要p,p,就就就就 q q”；（4 4）“若若若若p p，就，就，就，就q q”；（5 5）“只有只有只有只有q q,才才才才 p p”；（6 6）“除非除非除非除非q q，才，才，才，才p p”；（7 7）“除非除非除非除非q q，否则非，否则非，否则非，否则非p p”等。等。等。等。2024/1/202024/1/20离散数学离散数学4848例例设设p：天冷，天冷，q：小王穿羽绒服，将下列命题符号化小王穿羽绒服，将下列命题符号化（1）只要天冷，