离散数学1-1,1-2汇编

离散数学DiscreteMathematics

陈明

Mobilemail:mingchen_gang@163.com信息科学与工程学院，J13-108二零一三年九月离散数学课程简介◆离散数学，是现代数学的一个重要分支，是计算机科学中基础理论的核心课程，是整个计算机学科的专业基础课。◆离散数学是以研究离散量的结构和相互间的关系为主要目标，其研究对象一般地是有限个或可数个元素，因此它充分描述了计算机科学离散性的特点。◆离散数学是随着计算机科学的发展而逐步建立的，它形成于七十年代初期，是一门新兴的工具性学科。离散数学离散数学的应用◆关系型数据库的设计（关系代数）◆表达式解析（树）◆编译技术、程序设计语言（代数结构）◆人工智能、自动推理、机器证明（数理逻辑）◆网络路由算法（图论）◆游戏中的人工智能算法（图论、树、博弈论）◆专家系统（集合论、数理逻辑—知识和推理规则的计算机表达）◆软件工程—团队开发—时间和分工的优化（图论—网络、划分）◆(各种)算法的构造、正确性的证明和效率的评估（离散数学的各分支）离散数学教材左孝凌，李为鉴，刘永才编著．离散数学．上海：上海科学技术文献出版社,1982主要参考教材:孙吉贵，杨凤杰，欧阳丹彤，李占山编著．离散数学．高等教育出版社，2002离散数学学习要求◆本课程特点

定义+定理+例题◆多做习题，认真独立完成作业

离散数学本课程主要内容◆第一篇数理逻辑

命题逻辑、谓词逻辑◆第二篇集合论

集合与关系、函数◆第三篇代数系统

代数结构、格和布尔代数◆第四篇图论

图论离散数学第一篇数理逻辑

离散数学◆思维的形式结构包括了概念，判断和推理之间的结构和联系，其中概念是思维的基本单位，通过概念对事物是否具有某种属性进行肯定或否定的回答，这就是判断；由一个或几个判断推出另一判断的思维形式，就是推理。◆研究推理有很多方法，用数学方法来研究推理的规律称为数理逻辑，即通过引入表意符号研究推理，因此，数理逻辑又名符号逻辑。现代数理逻辑可分为四论、两演算：证明论、模型论、递归函数论、公理化集合论，以及命题演算和谓词演算，这里介绍的是数理逻辑最基本的内容：命题逻辑和谓词逻辑。离散数学设有下列情况，结论是否有效？

(a)或者是天晴，或者是下雨。

(b)如果是天晴，我去看电影。.(c)如果我去看电影，我就不看书。

结论：如果我在看书则天在下雨。

解若设M：天晴。Q：下雨。

S：我看电影。R：我看书。故本题即证：M∨Q，M→S，S→┐R，推出R→Q离散数学逻辑学中著名的三段论方法，是由一个大前提，一个小前提推出结论的方法。例如：

所有的人都是要死的。苏格拉底是人。所以苏格拉底是要死的。离散数学第一章命题逻辑目标语言：就是表达判断的一些语言的汇集。目标语言和一些符号公式构成了数理逻辑的形式符号体系。离散数学一、命题1、定义能表达判断的陈述句，称作命题（Proposition）。例：判断下列语句是否为命题:(1)地球外存在智慧生物。(2)1＋1=10。(3)今天下雨。(4)你今年暑假去旅行吗？（疑问句）(5)克里特岛人说：“克里特岛人是说谎话者”。（悖论）陈述句：述说一件事情的句子，句末用句号。祈使句：要求或者希望别人做什么事或者不做什么事时用的句子，句末用句号或感叹号。疑问句：提出问题的句子，句末用问号。感叹句：带有浓厚感情的句子，句末用感叹号。悖：相反。悖论：自相矛盾的陈述。1-1命题及其表示法

离散数学命题所表达的判断结果称为命题的真值（值）。真值只有“真”和“假”两种，记作True（真）和False（假），分别用符号T（1）和F（0）表示。由于命题只有两种真值，所以称这种逻辑为二值逻辑。命题的真值是具有客观性质的，而不是由人的主观决定的。

2、真值（truthvalue）离散数学

下面的语句中，哪些语句是命题，如果是命题，指出它的真值：

（1）能整除7的正整数只有1和7本身。

（2）对于每一个正整数n存在一个大于n的素数。

（3）煤是白的。

（4）雪是黑的。

（5）在宇宙中地球是唯一有生命的星球。

（6）1+101=110

（7）买两张星期六的电影票。（祈使句）

（8）全体立正！（祈使句）

（9）明天是否开会？（疑问句）

（10）天气多好啊！（感叹句）

（11）我正在说谎。（悖论）

（3）和（4）是命题，真值为F。（1）、（2）是命题，真值为T。祈使句、疑问句、感叹句等都不能作为命题，悖论无真值，也不能作为命题。语句（7）—（11）都不是命题。

（5）是命题，有确定真值，只是目前还不知道。

（6）不是命题，在二进制中为T，在十进制中为F，故需根据上下文才能确定其真假。

离散数学命题有两种类型：原子命题和复合命题原子命题：不能分解为更简单的陈述句。复合（分子）命题：由联结词、标点符号和原子命题复合构成的命题。前面例子中：（1～5）是原子命题；“我学英语，或者我学日语”是复合命题。

3、分类离散数学

练习：指出下列语句哪些是命题，哪些不是命题，如果是命题，指出它的真值。（见教材第8页习题（1））

a）离散数学是计算机科学系的一门必修课。

b）小李有空吗？

c）明天我去看电影。

d）请勿随地吐痰！

e）不存在最大质数。

f）如果我掌握了英语、法语，那么学习其他欧洲语言就容易的多。

g）x=3

h）我们要努力学习。

离散数学解：

a）离散数学是计算机科学系的一门必修课。是命题，真值为T。

b）小李有空吗？疑问句，不是命题。

c）明天我去看电影。是命题，真值要根据具体情况确定。

d）请勿随地吐痰！祈使句，不是命题。

e）不存在最大质数。是命题，真值为T。

f）如果我掌握了英语、法语，那么学习其他欧洲语言就容易的多。是命题，真值为T。

g）x=3不是命题，x=3的真假由x确定，当x取3时句子为真，当x取其他值时句子为假。

h）我们要努力学习。祈使句，不是命题。

a），c），e）是原子命题，f）是复合命题。

离散数学1、命题标识符：表示命题的符号称为命题标识符。在数理逻辑中，使用大写字母，或带下标的大写字母，或用方括号括起的数字表示命题。

例：P：今天下雨。

“今天下雨”是一个命题，P是命题标识符。

A1：今天下雨。

[12]：今天下雨。

A1

、

[12]也是命题标识符。

2、命题常量：一个命题标识符如表示确定的命题，就称为命题常量。

3、命题变元：如果命题标识符只表示任意命题的位置标志，就称为命题变元。命题变元可以表示任意命题，所以它不能确定真值，故命题变元不是命题。当命题变元用一个特定命题取代时，才能确定真值，这称为对命题变元进行指派。

4、原子变元：当命题变元表示原子命题时，该变元称为原子变元。二、命题的表示法离散数学1-2联结词

在数理逻辑中，复合命题是由原子命题与逻辑联结词组合而成，命题的连接方式叫做命题联结词或命题运算符。联结词是复合命题中的重要组成部分，为了便于书写和进行推演，必须对联结词作出明确规定并符号化。我们主要讨论下述五种联结词（亦称真值联结词，逻辑联结词或逻辑运算符），借助它们组成复合命题。

离散数学（1）否定（Negation）

（一元联结词）

1.定义定义1-2.1设P为一命题，P的否定是一个新的命题，记作┐P。若P为T，┐P为F；若P为F，┐P为T。联结词“┐”表示命题的否定，称为否定联结词或否定词，读作“非”或“not”。否定联结词有时亦可记作“ˉ”。P┐PTFFT2.真值表（truthtable）表1-2.1

命题P与其否定┐P的关系如表1-2.1所示。1/2离散数学“否定”的意义仅是修改了命题的内容，它是一个一元运算，我们仍把它看作为联结词。自然语言中的“不”、“无”、“没有”等词在命题演算中常与“非”相当。例：P：今天下雨。

┐P：今天不下雨。

┐P：今天无雨。

┐P：今天没有下雨。

P：上海是一个大城市。

┐P：上海不是一个大城市。

┐P：上海是一个不大的城市。练习：P：一个世纪是一百年。写出┐P。2/2离散数学（2）合取（Conjunction）

（二元联结词）

1.定义定义1-2.2两个命题P和Q的合取是一个复合命题，记作P∧Q。当且仅当P、Q同时为T时，P∧Q为T，在其他情况下，P∧Q的真值都是F。联结词“∧”称为合取词，读作“和”或“and”。2.真值表联结词“∧”的定义如表1-2.2所示。PQP∧QTT

TTFFFTFFFF表1-2.2

表1-2.2中给出复合命题P∧Q为T当且仅当P、Q同时为T。

1/7离散数学与“和”有相同意义的汉字还有“与”、“以及”、“并且”、“而且”等。例：P：今天下雨。

Q：明天下雨。上述命题的合取为

P∧Q：今天下雨而且明天下雨。

P∧Q：今天与明天都下雨。

P∧Q：这两天都下雨。显然只有当“今天下雨”与“明天下雨”都是真时，“这两天都下雨”才是真的。2/7离散数学

合取的概念与自然语言中的“与”意义相似，但并不完全相同。例如

P：我们去看电影。

Q：房间里有十张桌子。上述命题的合取为

P∧Q：我们去看电影与房间里有十张桌子。在自然语言中，上述命题是没有意义的，因为P与Q没有内在联系，但作为数理逻辑中P和Q的合取P∧Q来说，它仍可成为一个新的命题，只要按照定义，在P、Q分别取真值后，P∧Q的真值也必确定。3/7离散数学

例如

①P：雪是白的

Q：地球是行星。

P∧Q：雪是白的与地球是行星。

P∧Q的真值为T。②P：雪是白的

Q：地球是恒星。

P∧Q：雪是白的与地球是恒星。

P∧Q的真值为F。4/7离散数学

③P：雪是黑的

Q：地球是行星。

P∧Q：雪是黑的与地球是行星。

P∧Q的真值为F。④P：雪是黑的

Q：地球是恒星。

P∧Q：雪是黑的与地球是恒星。

P∧Q的真值为F。5/7离散数学

命题联结词“合取”甚至可以将两个互为否定的命题联结在一起。这时，其真值永为F。

P：今天下雨。

Q：今天不下雨。（此时Q既是┐P）

P∧Q：今天下雨与今天不下雨。

P∧Q的真值为F。

命题联结词“合取”也可以将若干个命题联结在一起。

“合取”是一个二元运算。

6/7离散数学

注意，并非所有的“和”、“与”、“并且”均可用“∧”表示。例如“李华和张南是表兄弟。”“王丽与王萍是堂姐妹”“他打开箱子并且取出一件衣服来。”这三句中的“和”、“与”、“并且”就不能用“∧”表示。

练习：1）P：一个世纪是一百年。

Q：4是偶数。写出P∧Q并确定其真值。

2）P：5是一个整数，Q：5不是一个奇数P∧Q：5是一个整数且5不是一个奇数P∧Q：5是一个整数但5不是一个奇数7/7离散数学（3）析取（Disjunction）

（二元联结词）

1.定义定义1-2.3两个命题P和Q的析取是一个复合命题，记作P∨Q。当且仅当P、Q同时为F时，P∨Q为F，否则P∨Q的真值为T。联结词“∨”称为合取词，读作“或”或“or”。PQP∨QTTTTFTFTTFF

F2.真值表联结词∨的定义如表1-2.3所示。表1-2.3表1-2.3中给出复合命题P∨Q为F当且仅当P、Q同时为F。1/4离散数学

例：P：灯泡坏了。

Q：开关坏了。上述命题的析取为

P∨Q：灯泡坏了或开关坏了。2/4离散数学注意，并非所有的“或”可用“∨”表示。例如，“我向东行或向西行。”该语句中的“或”称为“排斥或”，因为事实上一个人不会既向东行，又向西行。析取“∨”指的是“可兼或”。例如，他可能是100米或400米赛跑的冠军。这里

P：他可能是100米赛跑的冠军。

Q：他可能是400米赛跑的冠军。

P∨Q：他可能是100米或400米赛跑的冠军。3/4离散数学

还有一些汉语中的“或”字实际上不是命题联结词。例如，他昨天做了二十或三十道习题。这里的“或”字只表示了习题的近似数目，不能用联结词“∨”表达。

练习：P：雪是黑的。

Q：4是偶数。写出P∨Q并确定其真值。4/4离散数学（4）条件（Condition）

（二元联结词）1.定义定义1-2.4给定两个命题P和Q，其条件命题是一个复合命题，记作P→Q，读作“如果P，那么Q”或“若P则Q”。当且仅当P的真值为T，Q的真值为为F时，P→Q的真值为F，否则P→Q的真值为T。我们称P为前件，Q为后件。PQP→QTTTTFFFTTFFT2.真值表联结词→的定义如表1-2.4所示。

表1-2.41/4离散数学

例1如果我得到这本小说，那么我今夜就读完它。例2如果雪是黑的，那么太阳从西方出。上述二个例子都可用条件命题P→Q表达。在例1中，P：我得到这本小说，Q：我今夜就读完它。P的真值为T，Q的真值为T，P→Q的真值为T。如果P的真值为T，Q的真值为F，P→Q的真值为F。如果P的真值为F，Q的真值为T，P→Q的真值为T。如果P的真值为F，Q的真值为F，P→Q的真值为T

在例2中，P：雪是黑的，Q：太阳从西方出。P的真值为F，Q的真值为F，P→Q的真值为T。2/4离散数学在自然语言中，“如果…”与“那么…”之间常常是有因果联系的，否则就没有意义，但对条件命题P→Q来说，只要P、Q能够分别确定真值，P→Q即成为命题。自然语言中对“如果…、则…”这样的语句，当前提为假时，结论不管真假，这个语句的意义，往往无法判断。而在条件命题中，规定为“善意的推定”，即前提为F时，条件命题的真值都取为T。注意：3/4离散数学在数学上和有些逻辑学的书籍中，“若P则Q”亦可叫作P蕴含Q，而本书在条件命题中将避免使用“蕴含”一词，因为在以后将另外定义“蕴含”这个概念。4/4离散数学(5)双条件（DoubleCondition）

（二元联结词）1.定义定义1-2.5给定两个命题P和Q，其复合命题PQ称作双条件命题，读作“P当且仅当Q”，当P和Q的真值相同时，PQ的真值为T，否则PQ的真值为F。

PQPQTTTTFFFTFFFT表1-2.52.真值表联结词“”的定义可如表1-2.5所示。

1/2离散数学

例1两个三角形全等，当且仅当它们的三组对应边相等。例22+2＝4当且仅当雪是白的。上面三个例子都可用双条件命题PQ来表示。与前面的联结词一样，双条件命题也可以不顾其因果联系，而只根据联结词定义确定真值。双条件联结词亦可记作“”或“iff”。它亦是二元运算。应强调指出的是：复合命题的真值只取决于各原子命题的真值，而与它们的内容、含义无关，与原子命题之间是否有关系无关。理解和掌握这一点是至关重要的。

2/2离散数学

学习本节要掌握下列概念：

命题能表达判断的语句，并具有确定真值的陈述句。

真值一个命题总具有一个“值”，称为真值。真值只有真和假两种，分别记为T和F。

原子命题不能分解为更简单的陈述句，称为原子命题。

复合命题由联结词、标点符号和原子命题复合构成的命题，称为复合命题。复合命题亦称分子命题。

命题标识符表示命题的符号。

命题常量一个命题标识符表示确定的命题，该标识符称作命题常量。

命题变元命题标识符如仅是表示任意命题的位置标志，就成为命题变元。

原子变元当命题变元表示原子命题时，该变元称原子变元。

小结离散数学本节给出了如下五种联结词的定义：

否定设P为一命题，P的否定是一个新的命题，记作┐P。若P为T，┐P为F；若P为F，┐P为T。

合取两个命题P和Q的合取是一个复合命题，记作P∧Q。当且仅当P、Q同时为T时，P∧Q为T，在其他情况下，P∧Q的真值都是F。

析取两个命题P和Q的析取是一个复合命题，记作P∨Q。当且仅当P、Q同时为F时，P∨Q为F，否则P∨Q的真值为T。

条件给定两个命题P和Q，其条件命题是一个复合命题，记作P→Q，读作“如果P，那么Q”或“若P则Q”。当且仅当P的真值为T，Q的真值为为F时，P→Q的真值为F，否则P→Q的真值为T。

双条件给定两个命题P和Q，其复合命题PQ称作双条件命题，读作“P当且仅当Q”，当P和Q的真值相同时，PQ的真值为T，否则PQ的真值为F。小结离散数学作业P8:（3）

离散数学例：(a)P:今晚我写字,Q:今晚我看书。

P∨Q:今晚我写字或看书

“或”字常见的含义有两种:

◆“可兼或”,如上例中它不排除今晚既看书又写字这种情况。运算符∨表示可兼或。

◆“排斥或”，例如“人固有一死,或重于泰山,或轻于鸿毛”中的“或”,它表示非此即彼,不可兼得。再比如：张明正在睡觉或者游泳。此两题的或者是“排斥或”，也就是如果睡觉就不能游泳，如果游泳就不能睡觉。

P：张明在睡觉Q：张明在游泳可以翻译为：

（P∧┓Q）Ⅴ(┓P∧Q)(可以利用真值表证明其等价于原命题)“可兼或”与“排斥或”的区别离散数学思考下列命题用哪个联结词：只要P，就Q；因为P，所以Q；P仅当Q；只有Q才P；除非Q才P；Q：你努力，P：你成功离散数学练习8页（2）--（6）

(2)举例说明原子命题和复合命题。

(3)设P表示命题“天下雪

Q表示命题“我将去镇上。

R表示命题“我有时间”以符号形式写出下列命题。

a)如果天不下雪和我有时间，那么我将去镇上。

b)我将去镇上，仅当我有时间时。

c)天不下雪。

d)天下雪，那么我不去镇上。离散数学

(4)用汉语写出一句子，对应下列每一个命题。

a)Q(R∧┐P)b)R∧Qc)(Q→R)∧(R→Q)(5)将下列命题符号化。

a)王强身体很好，成绩也很好。

b)小李一边看书，一边听音乐。

c)气候很好或很热。

d)如果a和b是偶数，则a+b是偶数。

e)四边形ABCD是平行四边形，当且仅当它的对边平行．

f)停机的原因在于语法错误或程序错误。离散数学(6)将下列复合命题分成若干原子命题，

a)天气炎热且正在下雨。

b)天气炎热但湿度较低。

c)天正在下雨或湿度很高。

d)刘英与李进上山。

e)老王或小李是革新者。

f)如果你不看电影，那么我也不看电影。

g)我既不看电视也不外出，我在睡觉。

h)控制台打字机既可作输入设备，又可作输出设备。离散数学

解答

(2)举例说明原子命题和复合命题。原子命题：北京是中国的首都。复合命题：李毅和王强都是优秀学生。离散数学

(3)设P表示命题“天下雪”

Q表示命题“我将去镇上。

R表示命题“我有时间”以符号形式写出下列命题。

a)如果天不下雪和我有时间，那么我将去镇上。（┐P∧R）→Qb)我将去镇上，仅当我有时间时。R→Qc)天不下雪。┐Pd)天下雪，那么我不去镇上。P→┐Q离散数学(4)用汉语写出一句子，对应下列每