1-1-aolm-离散数学

《1-1-aolm-离散数学》由会员分享，可在线阅读，更多相关《1-1-aolm-离散数学（27页珍藏版）》请在装配图网上搜索。

1、离散数学离散数学 人民邮电出版社编著：杨炳儒编著：杨炳儒编著：杨炳儒编著：杨炳儒n第1篇 数理逻辑 n第2篇 集合论 n第3篇 代数结构 n第4篇 图论第1篇 数理逻辑 我们知道，数学家对于逻辑不如逻辑我们知道，数学家对于逻辑不如逻辑学家对于数学那样关心。数学和逻辑是精学家对于数学那样关心。数学和逻辑是精确科学的两双眼睛：数学派闭上逻辑眼睛，确科学的两双眼睛：数学派闭上逻辑眼睛，逻辑派闭上数学眼睛，各自相信一双眼睛逻辑派闭上数学眼睛，各自相信一双眼睛能比两双看得更好。能比两双看得更好。奥古斯塔斯奥古斯塔斯.德德.摩摩根根第2篇 集合论 当我们已经直观地弄懂了几个简单的定理的时当我们已经直观地弄

2、懂了几个简单的定理的时当我们已经直观地弄懂了几个简单的定理的时当我们已经直观地弄懂了几个简单的定理的时候候候候如果能通过连续的不间断的思考活如果能通过连续的不间断的思考活如果能通过连续的不间断的思考活如果能通过连续的不间断的思考活动，把几个定理贯穿起来，悟出它们之间的相互关动，把几个定理贯穿起来，悟出它们之间的相互关动，把几个定理贯穿起来，悟出它们之间的相互关动，把几个定理贯穿起来，悟出它们之间的相互关系，并能同时尽可能多地、明确地想象出其中的几系，并能同时尽可能多地、明确地想象出其中的几系，并能同时尽可能多地、明确地想象出其中的几系，并能同时尽可能多地、明确地想象出其中的几个，那将是很有益的

3、。照这样我们的知识无疑会增个，那将是很有益的。照这样我们的知识无疑会增个，那将是很有益的。照这样我们的知识无疑会增个，那将是很有益的。照这样我们的知识无疑会增加，理解能力会有显著的提高。加，理解能力会有显著的提高。加，理解能力会有显著的提高。加，理解能力会有显著的提高。笛卡尔笛卡尔笛卡尔笛卡尔第3篇 代数结构 数学的本质就在于一切能证明的都要证明。数学的本质就在于一切能证明的都要证明。数学的本质就在于一切能证明的都要证明。数学的本质就在于一切能证明的都要证明。G.Frege第4篇 图论 模型化是数学中的一个基本概念，它处于所模型化是数学中的一个基本概念，它处于所模型化是数学中的一个基本概念，它

4、处于所模型化是数学中的一个基本概念，它处于所有的数学应用之心脏，也处于某些最抽象的纯数有的数学应用之心脏，也处于某些最抽象的纯数有的数学应用之心脏，也处于某些最抽象的纯数有的数学应用之心脏，也处于某些最抽象的纯数学核心之中。学核心之中。学核心之中。学核心之中。R.C.Buck第1篇 数理逻辑n n第第1 1章章 命题逻辑命题逻辑n n第第2 2章章 谓词逻辑谓词逻辑命题逻辑和谓词逻辑是数理逻辑的基础部分命题逻辑和谓词逻辑是数理逻辑的基础部分第1篇 数理逻辑n n第1章 命题逻辑 1.1 1.1 命题命题1.2 1.2 联结词联结词 1.3 1.3 命题公式与翻译命题公式与翻译 1.4 1.4

5、命题公式的等价、蕴涵命题公式的等价、蕴涵 1.5 1.5 对偶与范式对偶与范式 1.6 1.6 其他联结词其他联结词 1.7 1.7 命题演算推理命题演算推理 1.8 1.8 应用应用1.9 1.9 典型例题解析典型例题解析 第1篇 数理逻辑n n第2章 谓词逻辑2.1 2.1 谓词和量词谓词和量词 2.2 2.2 谓词公式与翻译谓词公式与翻译 2.3 2.3 约束变元与自由变元约束变元与自由变元 2.4 2.4 谓词公式的等价、蕴涵谓词公式的等价、蕴涵 2.5 2.5 前缀范式前缀范式 2.6 2.6 谓词演算推理谓词演算推理2.7 2.7 应用应用 2.8 2.8 典型例题解析典型例题解析

6、 第1章 命题逻辑 有人问有人问有人问有人问 SophusSophus Lie Lie，什么是数学家所特有，什么是数学家所特有，什么是数学家所特有，什么是数学家所特有的天赋，他回答说是下面这个四元组：想象力，的天赋，他回答说是下面这个四元组：想象力，的天赋，他回答说是下面这个四元组：想象力，的天赋，他回答说是下面这个四元组：想象力，干劲，自信心和自我批评。干劲，自信心和自我批评。干劲，自信心和自我批评。干劲，自信心和自我批评。A德摩根德摩根第1章 命题逻辑本章的主要内容:简单命题，命题联结词，复合命题。复合命题的真假值问题，对偶定理，主析取范式，主合取范式。命题逻辑的三类推理方法：真值表法、直

7、接证法和间接证法。n n逻辑学主要分为：逻辑学主要分为：辩证逻辑辩证逻辑辩证逻辑辩证逻辑、形式逻辑形式逻辑形式逻辑形式逻辑和和数理逻辑数理逻辑数理逻辑数理逻辑n n数理逻辑：用数学的方法来研究推理规律的学科。数理逻辑：用数学的方法来研究推理规律的学科。n n学科形式：引进一套符号系统来描述和处理思维的学科形式：引进一套符号系统来描述和处理思维的形式及其规律性；形式及其规律性；总之：总之：总之：总之：数理逻辑：用形式符号语言的方法来研究逻辑问数理逻辑：用形式符号语言的方法来研究逻辑问题的一门学科题的一门学科 1.1 1.1 命题命题命题命题 1.1.1 1.1.1 命题的概念命题的概念命题的概念

8、命题的概念 一个命题，是具有真假意义的陈述句。一个命题，是具有真假意义的陈述句。一个命题，是具有真假意义的陈述句。一个命题，是具有真假意义的陈述句。命题具有一个确定的值，称为真值命题具有一个确定的值，称为真值命题具有一个确定的值，称为真值命题具有一个确定的值，称为真值 ：判断的结果。：判断的结果。：判断的结果。：判断的结果。真值：真值：真值：真值：“真真真真”和和和和“假假假假”，记为，记为，记为，记为 TrueTrue（真）和（真）和（真）和（真）和 FalseFalse（假），（假），（假），（假），用符号用符号用符号用符号 T T 和和和和 F F 表示。表示。表示。表示。注意：不能作为

9、命题的句子：注意：不能作为命题的句子：注意：不能作为命题的句子：注意：不能作为命题的句子：一切没有判断内容的句子，无所谓是非的句子。一切没有判断内容的句子，无所谓是非的句子。一切没有判断内容的句子，无所谓是非的句子。一切没有判断内容的句子，无所谓是非的句子。如感叹句，疑问句，祈使句，陈述句中的悖论等。如感叹句，疑问句，祈使句，陈述句中的悖论等。如感叹句，疑问句，祈使句，陈述句中的悖论等。如感叹句，疑问句，祈使句，陈述句中的悖论等。不是命题的例句：1.1.该吃早饭了！该吃早饭了！2.2.多漂亮的花呀！多漂亮的花呀！3.3.明天你有什么安排吗？明天你有什么安排吗？4.4.我正在说谎。我正在说谎。5

10、.5.x x y y2 2。(1),(2),(3)(1),(2),(3)这些句子都无所谓是非，这些句子都无所谓是非，(4)(4)无法无法判定其真假值（判定其真假值（语义上的悖论），），(5)(5)中的中的x,x,y y的值不确定的值不确定 。命题的例句：命题的例句：命题的例句：命题的例句：6.6.不在同一直线上的三点确定一个平面。不在同一直线上的三点确定一个平面。不在同一直线上的三点确定一个平面。不在同一直线上的三点确定一个平面。7.7.郑州是河南省的省会。郑州是河南省的省会。郑州是河南省的省会。郑州是河南省的省会。8.8.今年的冬天将是一个暖冬。今年的冬天将是一个暖冬。今年的冬天将是一个暖冬

11、。今年的冬天将是一个暖冬。9.9.这碗汤味太淡了。这碗汤味太淡了。这碗汤味太淡了。这碗汤味太淡了。10.101110.1011 100010001001110011。(6),(7)(6),(7)的真值为的真值为的真值为的真值为T T，(8)(8)的真值虽然目前无法确定，但它的真值虽然目前无法确定，但它的真值虽然目前无法确定，但它的真值虽然目前无法确定，但它是有真假可言的，是有真假可言的，是有真假可言的，是有真假可言的，(9)(9)的真假取决于说话人的主观判的真假取决于说话人的主观判的真假取决于说话人的主观判的真假取决于说话人的主观判断（即可以认为此语句是断（即可以认为此语句是断（即可以认为此语

12、句是断（即可以认为此语句是“我认为这碗汤味太淡了我认为这碗汤味太淡了我认为这碗汤味太淡了我认为这碗汤味太淡了”的缩写）。的缩写）。的缩写）。的缩写）。(10)(10)也是命题。也是命题。也是命题。也是命题。1.1.2 1.1.2 命题的分类命题的分类命题的分类命题的分类命题有两种类型：命题有两种类型：命题有两种类型：命题有两种类型：1.1.原子命题原子命题原子命题原子命题:不能分解为更简单的陈述语句的命题；不能分解为更简单的陈述语句的命题；不能分解为更简单的陈述语句的命题；不能分解为更简单的陈述语句的命题；2.2.复合命题复合命题复合命题复合命题:由联结词、标点符号和原子命题复合构成由联结词、

13、标点符号和原子命题复合构成由联结词、标点符号和原子命题复合构成由联结词、标点符号和原子命题复合构成的命题。的命题。的命题。的命题。例如：例如：例如：例如：玫瑰是红的玫瑰是红的玫瑰是红的玫瑰是红的并且并且并且并且紫罗兰是蓝的紫罗兰是蓝的紫罗兰是蓝的紫罗兰是蓝的。如果如果如果如果明天是个好天气明天是个好天气明天是个好天气明天是个好天气，那么，那么，那么，那么我们就去野炊我们就去野炊我们就去野炊我们就去野炊。(如果如果那么那么)命题的表示命题的表示命题的表示命题的表示:使用大写字母使用大写字母使用大写字母使用大写字母 AA,BB,P P,QQ,或用带下标的大写字母或用数字，如，或用带下标的大写字母或

14、用数字，如，或用带下标的大写字母或用数字，如，或用带下标的大写字母或用数字，如，AiAi,12,12等等等等 P P：今天下雨。：今天下雨。：今天下雨。：今天下雨。1212：今天下雨：今天下雨命题标识符命题标识符命题标识符命题标识符:表示命题的符号称为，表示命题的符号称为，P P和和1212就是命题标识符。就是命题标识符。命题常量：命题常量：命题常量：命题常量：一个命题标识符如果表示确定的命题。一个命题标识符如果表示确定的命题。命题变元：命题变元：命题变元：命题变元：如果一个命题标识符只表示任意命题的位置标志。如果一个命题标识符只表示任意命题的位置标志。原子变元：原子变元：原子变元：原子变元：

15、当命题变元表示原子命题时。当命题变元表示原子命题时。1.2 1.2 联结词联结词联结词联结词在自然语言中，常常使用的联结词有在自然语言中，常常使用的联结词有:“如果如果那么那么”、“不不”、“并且并且”、“或者或者”、“当且仅当当且仅当”。1.2.1 1.2.1 否定联结词否定联结词否定联结词否定联结词定义定义定义定义1.11.1 与命题与命题P P的真值相反的命题称为的真值相反的命题称为P P的的否定命题否定命题否定命题否定命题，记，记作作P P，读作，读作“非非P P”。【例例例例1.11.1】P P：这是一个三角形：这是一个三角形 P P：这不是一个三角形。：这不是一个三角形。【例例例例

16、1.21.2】P P：雪是白色的：雪是白色的 P P：雪不是白色的：雪不是白色的 P PTFFT1.2.2 1.2.2 合取联结词合取联结词合取联结词合取联结词定义定义定义定义1.2 1.2 只有命题只有命题只有命题只有命题P P与命题与命题与命题与命题QQ的真值均为的真值均为的真值均为的真值均为T T时其真值才为时其真值才为时其真值才为时其真值才为T T的的的的命题，称为命题命题，称为命题命题，称为命题命题，称为命题P P与命题与命题与命题与命题QQ的合取命题，记作的合取命题，记作的合取命题，记作的合取命题，记作P PQQ，读作，读作，读作，读作“P P与与与与QQ”。在自然语言中，还可用在

17、自然语言中，还可用“并且并且”、“同时同时”、“以及以及”、“既既又又”、“不但不但而且而且”等多种方式表达合取。等多种方式表达合取。PQPQTTTTFFFTFFFF【例例例例1.31.3】设各命题变元为：设各命题变元为：P P：今天打雷：今天打雷 QQ：今天下雨：今天下雨 则则P PQQ：今天打雷且下雨。：今天打雷且下雨。【例例例例1.41.4】设各命题变元为：设各命题变元为：P P：小李在看书：小李在看书 QQ：小李在听音乐：小李在听音乐 则则P PQQ：小李一边在看书，一边在：小李一边在看书，一边在听音乐。听音乐。1.2.3 1.2.3 析取联结词析取联结词析取联结词析取联结词定义定义定

18、义定义1.3 1.3 只有当命题只有当命题只有当命题只有当命题 P P 和命题和命题和命题和命题 Q Q 的真值同时为的真值同时为的真值同时为的真值同时为 F F 时，时，时，时，其真值才为其真值才为其真值才为其真值才为 F F 的命题称为命题的命题称为命题的命题称为命题的命题称为命题 P P 和命题和命题和命题和命题 Q Q 的析取的析取的析取的析取命题，记作命题，记作命题，记作命题，记作 P PQQ，读作，读作，读作，读作“P P或或或或QQ”。PQP QTTTTFTFTTFFF【例例例例1.51.5】晚上我们去教室学习或晚上我们去教室学习或去电影院看电影。去电影院看电影。(是是“排斥或排

19、斥或”)【例例例例1.61.6】他可能数学考了他可能数学考了100100分分或英语考了或英语考了100100分。分。(“(“可兼或可兼或”)【例例例例1.71.7】刘静今天跑了刘静今天跑了200200米或米或300300米远。米远。(大概路程大概路程 ,不是命题不是命题联结词联结词 )【例例例例1.81.8】设各命题变元为：设各命题变元为：设各命题变元为：设各命题变元为：P P：今天打雷：今天打雷：今天打雷：今天打雷 QQ：今天打闪：今天打闪：今天打闪：今天打闪 则则则则P PQQ：今天打雷或今天打闪。：今天打雷或今天打闪。：今天打雷或今天打闪。：今天打雷或今天打闪。【例例例例1.91.9】设

20、各命题变元为：设各命题变元为：设各命题变元为：设各命题变元为：P P：今天是星期一：今天是星期一：今天是星期一：今天是星期一 QQ：今天天气很好：今天天气很好：今天天气很好：今天天气很好 则则则则P PQQ：今天是星期一或天气很好。：今天是星期一或天气很好。：今天是星期一或天气很好。：今天是星期一或天气很好。1.2.4 1.2.4 条件联结词条件联结词条件联结词条件联结词定义定义定义定义1.4 1.4 只有当命题只有当命题只有当命题只有当命题 P P 的真值为的真值为的真值为的真值为 T T 且且且且 Q Q 的真值为的真值为的真值为的真值为 F F 时，时，时，时，其真值才为其真值才为其真值

21、才为其真值才为 F F 的命题称为命题的命题称为命题的命题称为命题的命题称为命题 P P 和命题和命题和命题和命题 Q Q 的条件命题。的条件命题。的条件命题。的条件命题。记为记为记为记为 P P QQ，读作，读作，读作，读作“若若若若P P则则则则QQ”。称。称。称。称 P P 为前件或者前提，为前件或者前提，为前件或者前提，为前件或者前提，Q Q 为后件或者结论。为后件或者结论。为后件或者结论。为后件或者结论。PQP QTTTTFFFTTFFT对于对于对于对于“若若若若则则则则”在日常语言在日常语言在日常语言在日常语言中有多种表达方式，诸如中有多种表达方式，诸如中有多种表达方式，诸如中有多

22、种表达方式，诸如“只只只只要要要要就就就就”，“当当当当则则则则”，“若若若若那么那么那么那么”，“必须必须必须必须以以以以便便便便”等。等。等。等。【例例例例1.101.10】甲对乙说：甲对乙说：甲对乙说：甲对乙说：“如果今晚我们班上不开会，则我就和如果今晚我们班上不开会，则我就和如果今晚我们班上不开会，则我就和如果今晚我们班上不开会，则我就和你一起去玩。你一起去玩。你一起去玩。你一起去玩。”请问：在什么情形下，乙认为甲的这句话是假请问：在什么情形下，乙认为甲的这句话是假请问：在什么情形下，乙认为甲的这句话是假请问：在什么情形下，乙认为甲的这句话是假？如果班上没有开会如果班上没有开会如果班上

23、没有开会如果班上没有开会(T)(T)，甲与乙一起去玩，甲与乙一起去玩，甲与乙一起去玩，甲与乙一起去玩(T)(T)，则自然认为甲说的话为真则自然认为甲说的话为真则自然认为甲说的话为真则自然认为甲说的话为真(T)(T)；如果班上开会了如果班上开会了如果班上开会了如果班上开会了(F)(F)，甲没有与乙一起去玩，甲没有与乙一起去玩，甲没有与乙一起去玩，甲没有与乙一起去玩(F)(F)，则没有理由认为甲的话为假则没有理由认为甲的话为假则没有理由认为甲的话为假则没有理由认为甲的话为假(T)(T)；如果班上没有开会如果班上没有开会如果班上没有开会如果班上没有开会(T)(T)，甲没有与乙一起去玩，甲没有与乙一起

24、去玩，甲没有与乙一起去玩，甲没有与乙一起去玩(F)(F)，则显然认为甲的话为假则显然认为甲的话为假则显然认为甲的话为假则显然认为甲的话为假(F)(F)；如果班上开会了如果班上开会了如果班上开会了如果班上开会了(F)(F)，但甲未参加而与乙一起去玩了，但甲未参加而与乙一起去玩了，但甲未参加而与乙一起去玩了，但甲未参加而与乙一起去玩了(T)(T)，则也不能认为甲的话为假则也不能认为甲的话为假则也不能认为甲的话为假则也不能认为甲的话为假(T)(T)。【例例例例1.111.11】设各命题变元为：设各命题变元为：P P：明天天气晴朗：明天天气晴朗 QQ：我们就去郊游：我们就去郊游 则则 P P QQ：如

25、果明天天气晴朗，我们就去郊游。：如果明天天气晴朗，我们就去郊游。【例例例例1.121.12】设各命题变元为：设各命题变元为：P P：x x 4 4 QQ：x x2 2 1616 则则 P P QQ：如果：如果x x 4 4，则，则x x2 2 1616。n n注：注：注：注：n n命题命题命题命题“P PQQ”也可读作也可读作也可读作也可读作“P P蕴涵蕴涵蕴涵蕴涵QQ”，条件联结词又可称，条件联结词又可称，条件联结词又可称，条件联结词又可称为为为为“蕴涵联结词蕴涵联结词蕴涵联结词蕴涵联结词”。条件命题的真值表不太符合自然语言。条件命题的真值表不太符合自然语言。条件命题的真值表不太符合自然语言

26、。条件命题的真值表不太符合自然语言中的习惯，这一点请读者务必注意。中的习惯，这一点请读者务必注意。中的习惯，这一点请读者务必注意。中的习惯，这一点请读者务必注意。n n给定命题公式给定命题公式给定命题公式给定命题公式 P PQQ，命题公式命题公式命题公式命题公式 QQP P 称为称为称为称为 P PQ Q 的逆换式；的逆换式；的逆换式；的逆换式；P PQ Q 称为称为称为称为 P PQ Q 的反换式；的反换式；的反换式；的反换式；QQP P 称为它的逆反式。称为它的逆反式。称为它的逆反式。称为它的逆反式。逆换式类似于中学数学里所学的命题的逆命题；反换逆换式类似于中学数学里所学的命题的逆命题；反

27、换逆换式类似于中学数学里所学的命题的逆命题；反换逆换式类似于中学数学里所学的命题的逆命题；反换式类似于否命题；逆反式类似于逆否命题。式类似于否命题；逆反式类似于逆否命题。式类似于否命题；逆反式类似于逆否命题。式类似于否命题；逆反式类似于逆否命题。1.2.5 1.2.5 双条件联结词双条件联结词双条件联结词双条件联结词定义定义定义定义1.51.5 只有当命题只有当命题只有当命题只有当命题 P P 和命题和命题和命题和命题 Q Q 的真值同时为的真值同时为的真值同时为的真值同时为 T T 或同时为或同时为或同时为或同时为 F F 时其真值方为时其真值方为时其真值方为时其真值方为 T T 的命题称为

28、命题的命题称为命题的命题称为命题的命题称为命题 P P 与与与与 Q Q 的双重条件的双重条件的双重条件的双重条件命题，记作命题，记作命题，记作命题，记作 P P QQ，读作，读作，读作，读作“P P当且仅当当且仅当当且仅当当且仅当Q”Q”。PQP QTTTTFFFTFFFT“P P 当且仅当当且仅当 Q Q”的含义与的含义与“若若 P P 则则 QQ，并且若，并且若 Q Q 则则 P P”的的含义相同，同时其含义与数学上含义相同，同时其含义与数学上“P P 是是 Q Q 的充要条件的充要条件”的含义的含义也一致。也一致。【例例例例1.131.13】设各命题变元为：设各命题变元为：P P：四边

29、形：四边形ABCDABCD是平行四边形是平行四边形 QQ：四边形：四边形ABCDABCD的对边平行的对边平行 则则 P P QQ：四边形：四边形ABCDABCD是平行四边形，是平行四边形，当且仅当它的对边平行。当且仅当它的对边平行。【例例例例1.141.14】设各命题变元为：设各命题变元为：P P：5 53 3 QQ：5 5 3 30 0 则则 P P QQ：3 3当且仅当当且仅当5 5 3 30 0。与联结词与联结词“”、“”、“”一样，双重条件命题一样，双重条件命题“P P QQ”的构成也不要求命题的构成也不要求命题 P P 和命题和命题 Q Q 之间存在任何联之间存在任何联系，它的真值仅仅与系，它的真值仅仅与 P P 和和 Q Q 的真值有关。的真值有关。