命题及联结词

1、请各位同学认真选择好座位，以后便对号入座， 以后点名，只对座位不对人。靠门的最后一排不坐人。任课老师:邓炳茂课程名称：离散数学课程名称：离散数学课程代码：课程代码：GE1032 GE1032 课程学时：课程学时：每周每周4 4学时学时 学学 分分 ：4 4学分学分课程性质：课程性质：必修考试必修考试课程介绍课程介绍 绪论绪论1.何谓离散数学何谓离散数学 离散数学是随着计算机科学的发展而形成的离散数学是随着计算机科学的发展而形成的一门工具性课程。它主要是研究一门工具性课程。它主要是研究离散量离散量的结构及的结构及相互之间的关系，同时离散数学不仅重视存在性相互之间的关系，同时离散数学不仅重视存在性

2、问题的研究，更重视可行性问题的研究。问题的研究，更重视可行性问题的研究。2.开设离散数学的目的开设离散数学的目的 奠定计算机科学必备的数学知识，提高学生奠定计算机科学必备的数学知识，提高学生逻辑思维逻辑思维的能力。的能力。3.离散数学所包含的内容离散数学所包含的内容目目 录录第一篇第一篇 数理逻辑数理逻辑 第第1章章 命题逻辑命题逻辑 第第2章章 一阶逻辑一阶逻辑 第二篇第二篇 集合论集合论 第第3章章 集合集合 第第4章章 关系关系第三篇第三篇 代数结构代数结构( (不讲不讲) )第四篇第四篇 图论图论 第第7 7，8 8，9 9章章学习本课程的具体要求学习本课程的具体要求一、课前预习，一、

3、课前预习， 按时上课；按时上课；二、集中精力，二、集中精力， 手脑并用；手脑并用；三、课后复习，三、课后复习， 完成作业。完成作业。考核内容考核内容要求要求分数分数百分比百分比考勤考勤准时到课堂，不影响其他准时到课堂，不影响其他人，准时离开课堂。人，准时离开课堂。101010%10%课堂表现课堂表现课堂上能认真听讲，不影课堂上能认真听讲，不影响他人听课，积极回答教响他人听课，积极回答教师提问。师提问。 5 55%5%作业作业独立、认真、按时完成。独立、认真、按时完成。151515%15%期末考试期末考试采取闭卷形式考试，主要采取闭卷形式考试，主要考查学生对本课程知识的考查学生对本课程知识的掌握

4、情况。掌握情况。10010070%70%期末总评期末总评: : 平时平时30%(30%(考勤考勤10%+10%+作业作业15%+15%+课堂表现课堂表现5%)+)+期末考试期末考试70%70%凡主动找老师问问题和认真订正作业凡主动找老师问问题和认真订正作业中的错误者都适当加分。中的错误者都适当加分。对抄袭和作弊行为的管理高等院校和任何学术交流都严禁任何方式的高等院校和任何学术交流都严禁任何方式的抄袭和作弊行为。学生在考试中有任何作弊行抄袭和作弊行为。学生在考试中有任何作弊行为，将根据学院为，将根据学院学生考试作弊行为处理规定学生考试作弊行为处理规定（修订）（修订）条例由教务处给予处罚。条例由教

5、务处给予处罚。学生作业中，需要引用他人的，必须有明确学生作业中，需要引用他人的，必须有明确的标示。有明确标示的不视为抄袭。如果不同的标示。有明确标示的不视为抄袭。如果不同学生的作业有学生的作业有70%70%以上的内容雷同，或同一段里以上的内容雷同，或同一段里有有70%70%相类似，或连续相类似，或连续3030个中文字词是一样的，个中文字词是一样的，视为抄袭。抄袭和被抄袭的作业或考试被评为视为抄袭。抄袭和被抄袭的作业或考试被评为零分。零分。授课人： 邓炳茂答疑时间：星期一 10:30am12：00am 星期二 10:00am12：00am 办公地点：基础部（综合楼办公地点：基础部（综合楼4144

6、14）电电 话：话：0200208781799887817998684322Q Q: 190687208E-MAILE-MAIL： 课件下载地址：课件下载地址：4040 基础部基础部第一篇第一篇 数理逻辑数理逻辑 逻辑学是一门研究思维形式及思维规律的学科逻辑学是一门研究思维形式及思维规律的学科, ,可可分为分为: :辨证逻辑：以辨证法认识论的世界观为基础的逻辨证逻辑：以辨证法认识论的世界观为基础的逻辑学。辑学。形式逻辑：研究思维形式结构和规律的学科，是形式逻辑：研究思维形式结构和规律的学科，是一门工具性学科。

7、一门工具性学科。用用数学的方法数学的方法研究形式逻辑中研究形式逻辑中推理规则推理规则的理论称为的理论称为数理逻辑。即以量的形式来研究思维规律。它引入数理逻辑。即以量的形式来研究思维规律。它引入一套一套符号符号体系来表示逻辑关系，故此也称符号逻辑。体系来表示逻辑关系，故此也称符号逻辑。 辩证逻辑辩证逻辑 传统演绎逻辑传统演绎逻辑逻辑学传统形式逻辑传统归纳逻辑逻辑学传统形式逻辑传统归纳逻辑简单逻辑方法简单逻辑方法形式逻辑形式逻辑现代演绎逻辑现代演绎逻辑（数理逻辑数理逻辑）现代归纳逻辑现代归纳逻辑现代形式逻辑（概率逻辑等）现代形式逻辑（概率逻辑等）非标准逻辑非标准逻辑（模态逻辑等）（模态逻辑等） 在

8、数理逻辑中，它撇开研究对象的实质在数理逻辑中，它撇开研究对象的实质含义，把直观的内容抽象为含义，把直观的内容抽象为形式化形式化，而且仅，而且仅仅研究其形式关系，这些仅研究其形式关系，这些形式关系形式关系是数理逻是数理逻辑研究的关键。辑研究的关键。 数理逻辑在计算机科学中的作用数理逻辑在计算机科学中的作用: （1）在程序设计中的应用。）在程序设计中的应用。 （2）在逻辑电路设计中的应用。）在逻辑电路设计中的应用。 （3）在程序正确性证明中的应用。）在程序正确性证明中的应用。第一章第一章 命题逻辑命题逻辑1.1 命题与联结词命题与联结词1.2 命题公式命题公式1.3 等价公式等价公式1.4 其他联

9、结词及联结词的完备性其他联结词及联结词的完备性1.5 对偶式与范式对偶式与范式1.6 蕴含公式蕴含公式1.7 推理理论推理理论1.8 应用应用第一章第一章 命题逻辑命题逻辑1.1 命题符号化及联结词命题符号化及联结词主要内容主要内容(1)(1)命题的基本概念及符号化命题的基本概念及符号化; ;(2)(2)联结词联结词 .重点内容重点内容理解命题、联接词的概念；掌握命题理解命题、联接词的概念；掌握命题的符号化的符号化.1.1命题与联结词命题与联结词1.1.1 命题及其表示命题及其表示 人们的思维活动是靠自然语言来表达的。人们的思维活动是靠自然语言来表达的。 然而然而, 由于自然语言易产生由于自然

10、语言易产生二义性二义性, 用它来表示严格的推用它来表示严格的推理就不合适了。理就不合适了。 为了解决这个问题为了解决这个问题, 在数理逻辑中在数理逻辑中引进了一种引进了一种形式化的语言形式化的语言。 自然语言的基本单位是句子。自然语言的基本单位是句子。 句子分为陈述句子分为陈述句、句、 祈使句、祈使句、 疑问句和感叹句等疑问句和感叹句等, 其中能判断对错其中能判断对错的只有陈述句的只有陈述句 。 因为只有陈述句才能够表达对事物有因为只有陈述句才能够表达对事物有“肯定肯定”或或“否定否定”的思维方式，我们把这种的思维方式，我们把这种“肯定肯定”和和“否定否定”称为真值（称为真值（Truth）。例

11、如陈述句）。例如陈述句“今今天下雨天下雨”，这是一个判断。如果今天真的下雨，这是一个判断。如果今天真的下雨，则这个判断的值为真则这个判断的值为真(true)；如果今天没有下雨，；如果今天没有下雨，则这个判断的值为假（则这个判断的值为假（false）。）。 我们把具有这种特点的句子叫命题，它是形我们把具有这种特点的句子叫命题，它是形式语言中的基本单位。式语言中的基本单位。 定义定义1-1 在数理逻辑中，把能在数理逻辑中，把能惟一惟一判断真假的判断真假的陈陈述句述句称为命题称为命题(proposition)，以命题作为研究对，以命题作为研究对象的逻辑称为命题逻辑象的逻辑称为命题逻辑(proposi

12、tion logic)。 命题可能为真，也可能为假。命题的真命题可能为真，也可能为假。命题的真(ture)、假、假(false)统称为命题的真值。统称为命题的真值。 真值为真的命题称为真值为真的命题称为真命题真命题，记作，记作“1”（也可记作（也可记作“T”） 真值为假的命题称为真值为假的命题称为假命题假命题，记作，记作“0”（也可记作（也可记作“F”） 判断命题的两个步骤：判断命题的两个步骤： 首先判断它是否为陈述句，首先判断它是否为陈述句， 再判断它是否有确定的、惟一的真值再判断它是否有确定的、惟一的真值.例例1-1判断下列句子哪些是命题：判断下列句子哪些是命题： (1) 广州是广东省的省

13、会。广州是广东省的省会。 (2) 雪是黑色的。雪是黑色的。 (3) 2100年人类将在月亮上生活。年人类将在月亮上生活。 (4) 11+1=100 (5) 如果天气炎热，小梅就去游泳。如果天气炎热，小梅就去游泳。 (6) 我正在撒谎。我正在撒谎。 (7) 请把门关好。请把门关好。 (8) 这里可以坐吗？这里可以坐吗？ (9) 这幅画真好看。这幅画真好看。 解：这解：这9个句子中，（个句子中，（7）（）（9）都不是陈述句，）都不是陈述句，因而都不是命题。因而都不是命题。（1）是真命题，（）是真命题，（2）是假命题。）是假命题。（3）的真值虽然现在还不能判断，到）的真值虽然现在还不能判断，到210

14、0年就能年就能判断了，因而是命题。判断了，因而是命题。（4）在十进制中为假，在二进制中为真，当确定）在十进制中为假，在二进制中为真，当确定了进位制时其真值就确定了，因而是命题。了进位制时其真值就确定了，因而是命题。（5）是命题，真值视具体情况惟一确定（不是真）是命题，真值视具体情况惟一确定（不是真就是假）。就是假）。（6）是陈述句，但无法给出真假值。这种自相矛）是陈述句，但无法给出真假值。这种自相矛盾的判断称为盾的判断称为悖论悖论，以后再讲。，以后再讲。从以上分析解答可以看出：从以上分析解答可以看出： 命题一定是陈述句，但并非所有陈述句都是命题。命题一定是陈述句，但并非所有陈述句都是命题。如例

15、如例1-1（6）命题必须有惟一确定的真值，但其真值可能受到命题必须有惟一确定的真值，但其真值可能受到环境、判断的标准及认识程度的限制，一时无法环境、判断的标准及认识程度的限制，一时无法确定，只要能分辨真假值的判断均为命题。确定，只要能分辨真假值的判断均为命题。1.1.2 命题的分类命题的分类命题可分为原子命题和复合命题。命题可分为原子命题和复合命题。定义定义1-2 凡不能再分解的命题称为凡不能再分解的命题称为原子命题原子命题(简单命题简单命题) 由原子命题和联结词联结而成的命题称为由原子命题和联结词联结而成的命题称为复合命题复合命题.例例1-1中，（中，（1）（）（4）是原子命题。）是原子命题

16、。例例1-1中，（中，（5）是复合命题。）是复合命题。 数理逻辑也称符号逻辑，它引入一套符号体数理逻辑也称符号逻辑，它引入一套符号体系来表示命题和命题之间的联系，这个过程称为系来表示命题和命题之间的联系，这个过程称为命题形式化命题形式化。 命题形式化可分为命题形式化可分为原子命题形式化原子命题形式化和和命题之命题之间联系间联系的形式化。在数理逻辑中，通常用大写英的形式化。在数理逻辑中，通常用大写英文字母或带下标的大写英文字母文字母或带下标的大写英文字母P，Q，R，Pi，Qj，来表示命题。来表示命题。 用来表示命题的符号称为命题标识符。用来表示命题的符号称为命题标识符。 例如例如: P：广州是广

17、东省的省会。：广州是广东省的省会。 Q: 今天天下雨。今天天下雨。1.1.3 命题的表示方法命题的表示方法 命题分类：简单命题（也称原子命题）与复合命题 简单命题符号化 用小写英文字母 p, q, r, , pi, qi, ri (i1)表示简单命题 用“1”表示真，用“0”表示假 例如，令 p： 是有理数，则 p 的真值为0， q：2 + 5 = 7，则 q 的真值为1 2定义定义1-3 如果一个命题标识符代表如果一个命题标识符代表任意未知命题任意未知命题，则，则称该命题标识符为称该命题标识符为命题变元命题变元（命题变项）（命题变项）.如果一如果一个命题标识符代表一个确定的命题，则称之为个命

18、题标识符代表一个确定的命题，则称之为命命题常元题常元。 命题变元类似代数中的变量，命题常元类似命题变元类似代数中的变量，命题常元类似 常量，但两者有着本质的区别。命题变元或常元常量，但两者有着本质的区别。命题变元或常元 代表的是命题元素，而变量和常量代表的是一个代表的是命题元素，而变量和常量代表的是一个 数值。数值。 例如，例如，x+y 5 这是一个代数表达式，其中这是一个代数表达式，其中x和和y是是变量，不是命题变元，但该表达式也可以作为一变量，不是命题变元，但该表达式也可以作为一个命题变元。假设代表该表达式的命题变元为个命题变元。假设代表该表达式的命题变元为z，当变量当变量x和和y的值确定

19、后，表达式成为一个命题常的值确定后，表达式成为一个命题常元，命题变元元，命题变元z被该命题常元所取代成为命题，且被该命题常元所取代成为命题，且命题的真值随变量命题的真值随变量x和和y不同取值而变化。不同取值而变化。 当用确定的命题代入命题变元时称为对命题当用确定的命题代入命题变元时称为对命题变元的变元的代入代入。1.1.4 命题联结词命题联结词 在命题逻辑中在命题逻辑中, ,主要研究的是主要研究的是复合命题复合命题, ,而而复合命题复合命题是由原子命题与逻辑联结词组合而成，联结词是复合是由原子命题与逻辑联结词组合而成，联结词是复合命题的重要组成部分命题的重要组成部分. .1.2.1 否定联结词

20、否定联结词(Negation) 1.2.2 合取联结词合取联结词(Conjunction)1.2.3 析取联结词析取联结词(Disjunction)1.2.4 条件联结词条件联结词(蕴涵联结词蕴涵联结词Conditional)1.2.5 双条件联结双条件联结(等值联结词等值联结词Biconditional) 定义定义1.1 设设P为一命题，为一命题， P的否定是一个新的复合的否定是一个新的复合 命题命题, 称为称为P的否定式的否定式，记作，记作 “P”读作读作“非非P”. 符符号号“ ” 称为否定联结词。称为否定联结词。 P为真当且仅当为真当且仅当P为为假假.1 否定联结词否定联结词 例，例，

21、P: 天津是一个城市天津是一个城市.于是于是 P: 天津不是一个城市天津不是一个城市.说明说明： 1、“”属于一元属于一元(unary)运算符运算符. 2、联结词、联结词“”的定义真值表如下：的定义真值表如下：P P0110定义定义1.2 设设P,Q为二命题，复合命题为二命题，复合命题“P并且并且Q”（或（或“P与与Q”）称为）称为P与与Q的合取式的合取式，记作，记作PQ，符号，符号“” 称为合取联结词称为合取联结词. PQ为真当且仅当为真当且仅当P P和和Q Q同时为真同时为真. . 2 合取联结词合取联结词PQ P Q 0 00 00 00 01 10 01 10 00 01 11 11

22、1说明：说明：1、“” 属于二元属于二元(binary)运算符运算符. 2、联结词、联结词“”的定义真值表如下：的定义真值表如下：日常语言中与合取相似的联结词有：日常语言中与合取相似的联结词有：“和和”、“与与”、“并且并且”、“既既又又” 、“不不但但而且而且”、“尽管尽管仍然仍然”。 例例3. 将下列命题符号化将下列命题符号化. (1) 李平既聪明又用功李平既聪明又用功. (2) 李平虽然聪明李平虽然聪明, 但不用功但不用功.解解: 设设 P:李平聪明李平聪明. Q:李平用功李平用功.则则 (1) PQ (2) PQ 注意：不要见到注意：不要见到“与与”或或“和和”就使用联结词就使用联结词

23、 ！例如例如: (1)李敏和李华是姐妹。李敏和李华是姐妹。 (2)李敏和张华是朋友。李敏和张华是朋友。定义定义1.3 设设P,Q为二命题，复合命题为二命题，复合命题“P或或Q” 称为称为P与与Q的析取式的析取式，记作，记作PQ ，符号，符号称为析取联结词称为析取联结词. PQ为真当且仅当为真当且仅当 P与与Q中至少有一个为真中至少有一个为真. 3 析取联结词析取联结词2、联结词、联结词“”的定义真值表如下：的定义真值表如下：PQ P Q 0 00 00 00 01 11 11 10 01 11 11 11 1说明：说明：1、“” 属于二元属于二元(binary)运算符运算符. 日常语言中的日常

24、语言中的“（或者）（或者）或者或者”、“可能可能可能可能”等词均可符号化为等词均可符号化为“ ”。说明说明:析取又称为逻辑析取又称为逻辑“或或”。它可分为可兼或和不。它可分为可兼或和不可兼或。联结词可兼或。联结词 “”代表的是可兼或，还有不可兼代表的是可兼或，还有不可兼或。或。例如：命题例如：命题“小李在看书或听音乐小李在看书或听音乐”， 这里的这里的“或或”显然是显然是“可兼或可兼或”； 而命题而命题“小李正在教室看书或正在图书馆上网小李正在教室看书或正在图书馆上网” 的的“或或”是是“不可兼或不可兼或”，因为同一个人不可能同，因为同一个人不可能同时出现在两个不同的地方。时出现在两个不同的地

25、方。不可兼或指的是二者不能同时存在。不可兼或指的是二者不能同时存在。例例1-31-3将下列命题符号化：将下列命题符号化： （1）小李在看书或听音乐。）小李在看书或听音乐。 （2）小李正在教室看书或正在图书馆上网。）小李正在教室看书或正在图书馆上网。 解（解（1）设）设p ：小李在看书，：小李在看书， Q ：小李在听音乐；：小李在听音乐； 则该命题符号化为：则该命题符号化为：P Q 。 （2）设）设R ：小李正在教室看书，：小李正在教室看书， S ：小李正在图书馆上网；此命题必：小李正在图书馆上网；此命题必须使用多个联结词，命题符号化为：须使用多个联结词，命题符号化为：)()(SRSR4 条件联

26、结词（蕴涵联结词）条件联结词（蕴涵联结词） 定义定义1. 4 设设P,Q为二命题，复合命题为二命题，复合命题“如果如果P，则，则Q(若若P，则，则Q)” 称为称为P与与Q的条件命题的条件命题,记作记作P Q。称。称符号符号“”为条件联结词，并称为条件联结词，并称P为前件，为前件，Q为后件为后件. PQ为假当且仅当为假当且仅当P为真且为真且Q为假为假. 联结词联结词“”的定义真值表如下：的定义真值表如下：PQP Q0 00 01 10 01 11 11 10 00 01 11 11 1 在真值表中，除了前件为真，后件为假时为假，在真值表中，除了前件为真，后件为假时为假，其余都为真其余都为真。对前

27、件为真我们不难理解，因为前。对前件为真我们不难理解，因为前件为真件为真,是前提是前提,是达到结论的先决条件。如果前是达到结论的先决条件。如果前件为真，后件也为真，正符合我们的要求；若前件为真，后件也为真，正符合我们的要求；若前件为真，后件为假，则不符合我们的要求，所以件为真，后件为假，则不符合我们的要求，所以为假。至于前件为假不是我们考虑的对象，所以为假。至于前件为假不是我们考虑的对象，所以不管后件是真还是假，都有为真。这种情况逻辑不管后件是真还是假，都有为真。这种情况逻辑学上称为学上称为“善意推定善意推定”。 正是因为这个正是因为这个“善意推定善意推定”，阿基米德才会说：，阿基米德才会说：“

28、给我一个支点，我能把地球撬起来。给我一个支点，我能把地球撬起来。”，这句话，这句话永远是对的，因为没有谁能给他这样一个支点，前永远是对的，因为没有谁能给他这样一个支点，前件总为假，不管他能否把地球撬起来，他都是对的。件总为假，不管他能否把地球撬起来，他都是对的。与此类似的有：与此类似的有：“如果太阳从西边出，那末如果太阳从西边出，那末。”，“若公鸡也能下蛋，若公鸡也能下蛋， . 。”说明：说明：1、“” 属于二元属于二元(binary)运算符；运算符； 2、PQ表示的基本逻辑关系是表示的基本逻辑关系是,Q是是P的必要的必要条件或条件或P是是Q的充分条件的充分条件. 因此复合命题因此复合命题“只

29、要只要P就就Q”、“因为因为P，所以，所以Q”、“P仅当仅当Q”、“只有只有Q才才P”等都等都 可以符号化为可以符号化为 PQ 的形式。的形式。 例例1-4 将下列命题符号化将下列命题符号化 (1)如果明天是晴天，那么明天举行学校运动会。如果明天是晴天，那么明天举行学校运动会。 (2)如果明天举行学校运动会，明天必定是晴天。如果明天举行学校运动会，明天必定是晴天。 (3)如果明天不是晴天，明天不举行学校运动会。如果明天不是晴天，明天不举行学校运动会。 (4)如果明天不举行学校运动会，则明天不是晴天。如果明天不举行学校运动会，则明天不是晴天。 解解 设设P ：明天是晴天。：明天是晴天。 Q ：明

30、天举行学校运动会。：明天举行学校运动会。 （1） 原命题原命题 （2） 逆命题逆命题 （3） 否命题否命题 （4） 逆否命题逆否命题QP PQ QPPQ 从上述例子可以看出，原命题与逆否命题意思相同从上述例子可以看出，原命题与逆否命题意思相同,即等价：即等价： 逆命题与反命题意思相同。逆命题与反命题意思相同。 这一点非常重要，在推理过程中，有时按原命题进这一点非常重要，在推理过程中，有时按原命题进行推导比较困难，而用逆否命题却可收到事半功倍行推导比较困难，而用逆否命题却可收到事半功倍的效果。的效果。PQQP 定义定义1. 5 设设P,Q为二命题，复合命题为二命题，复合命题“P当且仅当当且仅当Q

31、” 称为称为P与与Q的双条件命题，记作的双条件命题，记作P iff Q或或PQ，符号，符号称为双条件（等价）联结词。称为双条件（等价）联结词。PQ为真当且仅当为真当且仅当P，Q真值相同。真值相同。 5 双条件联结词（等价联结词）双条件联结词（等价联结词） 联结词联结词“”的定义真值表如下：的定义真值表如下：PQP Q0 00 01 10 01 10 01 10 00 01 11 11 1 说明：说明：(1)“”属于二元属于二元(binary)运算符运算符; (2) 双条件命题双条件命题PQ所表达的逻辑关系是所表达的逻辑关系是, P与与 Q互为充分必要条件互为充分必要条件,相当于相当于(PQ)(QP). 只要只要P与与 Q的真值同为