&>&&>&离散数学-副本
离散数学-副本 投稿：雷徠御
离散数学-结课论文 姓名：学号：专业： 13计算机学院： 信息工程学院手机号码： 日 目录摘要 ..................................................................…
哈九中2013级高一下学期语文晨读9一、基础知识（每题5分，共60分）1.下列各组词语中加横线字的注音完全不相同的一组是A. 禅让 阐明 嬗变 煽风点火 潸然泪下B. 庇荫 纰漏 毗连 筚路蓝缕 蚍蜉撼树C. 侍奉 对峙 吞噬 恃才傲物 舐犊情深D.…
关于保护花草树木的标语研究 11级语文教育（1）班 李诺 学号： 摘要：标语，指用简短的文字写出的有宣传鼓动作用的口号。近年来，随着全球气候变暖带来的影响，政府及社会大众也越来越重视保护环境的宣传，关于保护花草树木的标语也越来越重要。…
专业： 13计算机
学院： 信息工程学院
手机号码：
摘要 ................................................................................................................................................... 2
第一部分 ........................................................................................................................................... 3
命题逻辑 ............................................................................................................................ 3
1.1知识点总结 ................................................................................................................................... 3
1.2实例 ............................................................................................................................................... 6
第二章 谓词逻辑 .............................................................................................................................. 7
2.1知识点总结 ................................................................................................................................... 7
2.2实例 ............................................................................................................................................... 9
第三章 集合、关系与函数 ............................................................................................................. 11
3.1知识点总结 ................................................................................................................................. 11
3.2实例 ............................................................................................................................................. 16
第四章 图论.................................................................................................................................... 17
4.1知识点总结 ................................................................................................................................. 17
4.2实例 ............................................................................................................................................. 20
第二部分 ......................................................................................................................................... 20
逻辑推理故事 .................................................................................................................................. 20
趣味推理一：头巾的颜色 ................................................................................................................ 20
趣味推理二：找出两处破绽 ............................................................................................................ 21
趣味推理三：四个旅行者过桥 ........................................................................................................ 22
趣味推理四：圣诞树 ........................................................................................................................ 23
趣味推理五：磁铁 ............................................................................................................................ 23
趣味推理六：男孩把表修好了 ........................................................................................................ 24
第三部分 ......................................................................................................................................... 25
故事大集结 ..................................................................................................................................... 25
一、尔伯特的旅馆 ............................................................................................................................ 25
二、救命的小故事 ............................................................................................................................ 25
三、半费之讼 .................................................................................................................................... 26
四、飞矢不动 .................................................................................................................................... 26
五、阿基里斯追龟 ............................................................................................................................ 27
第四部分 ......................................................................................................................................... 28
作业习题 ......................................................................................................................................... 28
离散数学(Discrete mathematics)是研究离散量的结构及其相互关系的数
主要是研究基于离散量的结构和相互间的关系，其对象一般是有限个或可数个元
必不可少的先行课程。通过离散数学的学习，不但可以掌握处理离散结构的描述
通过学习了离散数学，我通过总结离散的知识点，部分知识点的实例，收集
一些逻辑推理的题，与离散有关的小故事，并插入作业习题来总结我对离散数学
关键字：离散数学、实例、逻辑推理、作业习题
1.1知识点总结
1. 命题 命题表述为具有确定真假意义的陈述句。命题必须具备二个条件：其一，语
句是陈述句；其二，语句有唯一确定的真假意义.
2. 命题公式、赋值与解释，命题公式的分类与判别
?命题公式与赋值，命题P含有n个命题变项P1，P2,,,,Pn，给P1，P2,,,,Pn
各指定一个真值，称为对P的一个赋值(真值指派). 若指定的一组值使P的真值
为1，则这组值为P的真指派；若使P的真值为0，则称这组值称为P的假指派.
?命题公式分类，在各种赋值下均为真的命题公式A，称为重言式(永真式)；
在各种赋值下均为假的命题公式A，称为矛盾式(永假式)；命题A不是矛盾式，
称为可满足式；
判定命题公式类型的方法：其一是真值表法，任给公式，列出该公式的真值
表，若真值表的最后一列全为1，则该公式为永真式；若真值表的最后一列全为
0，则该公式是永假式；若真值表的最后一列既非全1，又非全0，则该公式是可
满足式.其二是推导演算法. 利用基本等值式(教材P.16的十六个等值式或演算
律)，对给定公式进行等值推导，若该公式的真值为1，则该公式是永真式；若
该公式的真值为0，则该公式为永假式.既非永真，也非用假，成为非永真的可
满足式.其三主析取(合取)范式法，该公式的主析取范式有2n个极小项(即无极
大项)，则该公式是永真式；该公式的主合取范式有2n个极大项(即无极小项)，
则该公式是永假式；该公式的主析取(或合取)范式的极小项(或极大项)个数大于
0小于2n,，则该公式是可满足式.
?等值式A?B，命题公式A，B在任何赋值下，它们的真值均相同，称A，
设?(A)是含命题公式A的命题，?(B)是用命题公式B置换?(A)中
的A之后得到的命题公式. 如果A?B，则?(A)??(B).
? 析取(合取)范式，仅有有限个简单合取式(析取式)构成的析取式(合取
式)，就是析取(合取)范式.
? 极小项(极大项)，n个命题变项P1,P2,,,,Pn，每个变项或它的否定两者只
有其一出现且仅出现一次，第i个命题变项或者其否定出现在从左起第i个位置
上(无脚标时，按字典序排列)，这样的简单合取式(析取式)为极小项(极大项).
以两个命题变项为例，m00=?P??Q，m01=?P?Q,m10=P??Q,m11=P?Q是极小
项;M00=P?Q，M01=P??Q,M10=?P?Q,M11=?P??Q是极大项.
? 主析取范式(主合取范式)
含有n个命题变项的命题公式，如果与一个
仅有极小项(极大项)的析取(合取)构成的析取(合取)范式等值，则该等值式称为
原命题公式的主析取(合取)范式。
每项含有n个命题变项(变项字母齐全)的合取式(析取式)的析取(合取)为主
析取(合取)范式.
任意命题公式都存在与之等值的范式，存在与之等值的主范式，且是惟一的.
求范式，包括求析取范式、合取范式、主析取范式和主合取范式. 关键有两
点：其一是准确掌握范式定义；其二是巧妙使用基本等值式中的分配律、同一律
和摩根律，结果的前一步适当使用幂等律.
求析取(合取)范式的步骤： ① 将公式中的联结词都化成?，?，?(即消去个数中的联结词?，?，??)；
② 将否定联结词?消去或移到各命题变项之前；
③ 利用分配律、结合律等，将公式化为析取(合取)范式.
求命题公式A的主析取(合取)范式的步骤
① 求公式A的析取(合取)范式；
② “消去”析取(合取)范式中所有永假式(永真式)的析取项(合取项)，如
P??P(P??P)用0(1)替代. 用幂等律将析取(合取)范式中重复出现的合取项(析
取项)或相同的变项合并，如P?P(P?P)用P替代，mi?mi(Mi?Mi)用mi(Mi)替代.
③ 若析取(合取)范式的某个合取项(析取项)B不含有命题变项Pi或?Pi，则
添加Pi??Pi(Pi??Pi)，再利用分配律展开，使得每个合取项(析取项)的命题变项
④ 将极小(极大)项按由小到大的顺序排列，用?(?)表示.
4. 命题演算的推理理论 ?设A1,A2,,,,An,C是命题公式，如果A1?A2???An?C是重言式，称C
是前提集合{ A1,A2,,,,An}的有效结论或{A1,A2,,,,An}逻辑地推出C。记作
A1?A2???An?C
掌握演绎或形式证明. 要理解并掌握14个重言蕴含式(即I1～I14)，17个等
值式(E1～E17)；二是会使用三个规则(P规则、T规则和CP规则)。
推理方法有： 真值表法；等值演算法；主析取范式法，构造证明法(直接证明法、附加前
提证明法和间接证明法)
常用的等值式
(1)双重否定律
A∨B ? B∨A
A∧B ? B∧A
(A∨B)∨C ? A∨(B∨C)
(A∧B)∧C ? A∧(B∧C)
A∨(B∧C) ? (A∨B)∧(A∨C)
A∧(B∨C) ? (A∧B)∨(A∧C)
(6)德·摩根律
┐(A∨B) ? ┐A∧┐B
┐(A∧B) ? ┐A∨┐B
A∨(A∧B) ? A
A∧(A∨B) ? A
(10)否定律
A∨┐A ? 1
A∧┐A ? 0
(11)蕴涵等值式
A→B ? ┐A∨B
(12)等价等值式
AB ?(A→B)∧(B→A)
(13)逆反律
A→B ? ┐B→┐A
(14)输出律
A→(B→C) ?(A∧B)→C
(15)归谬论
(A→B)∧(A→┐B) ? ┐A
常用的蕴涵式
(1) P∧Q?P； (2) P∧Q?Q； (3) P?P∨Q； (4) Q?P∨Q； (5) ?P?(P→Q)； (9) P，P→Q?Q； (10) ?Q，P→Q??P； (11) ?P，P∨Q?Q； (12) P→Q，Q→R?P→R； (13) P∨Q，P→R，Q→R?R；
(14) P→Q，R→S?(P∧R)→(Q∧S)；
(15) P，Q?P∧Q。
(6) Q?(P→Q)；
(7) ?(P→Q)?P；
(8) ?(P→Q)??Q；
例1.1 判别下列语句是否命题？如果是命题，指出其真值.
中国是一个人口众多的国家.
存在最大的质数.
这座楼可真高啊！
请你跟我走!
(5) 火星上也有人.
(1) 是命题，真值为1.
(2) 是命题，真值为0.
(3), (4)不是命题因为不是陈述句.
(5) 是命题. 真值是唯一的，迟早会被指出.
例1.2 将下列命题符号化：
(1) 虽然交通堵塞，但是老王还是准时到达火车站；
(2) 张力是三好生，他是北京人或是天津人.
(3) 除非天下雨，否则我骑车上班.
解 (1) 设P：交通堵塞，Q：老王准时到达火车站.
该命题符号化为：P?Q.
(2)设P：张力是三好生；
Q：张力是北京人，R：张力是天津人.
该命题符号化为P?(Q??R ).
(3)设P：天下雨，Q：我不骑车上班.
该命题符号化为：Q?P，义即“只有天下雨，我才不骑车上班”，不下雨是
我骑车上班的必要条件。它的等价说法是“如果天不下雨，我就骑车上班”，即
“如果天下雨，我就不骑车上班”，这是蕴含关系，符号化为：P?Q
例1.3 用等值演算法判定公式P??(Q?R)?P?Q?R是永真式？永假式？可满
解 等值运算法.
P??(Q?R)?P?Q?R??(P??(Q?R)?P?Q?R
??(P??(Q?R)??P?(Q?R))?P?Q?R
??((P??(Q?R))?(?P?Q?R))?P?Q?R
?(?(P??(Q?R))??(?P?Q?R))?P?Q?R
?((?P?(Q?R))?(P??Q??R))?P?Q?R
?((?P?(Q?R)) ?P?Q?R)?((P??Q??R)?P?Q?R)
(?对?的分配律)
?(?P?P)?Q?R?(Q?R)?1
因此，P??(Q?R)?P?Q?R是永真式
第二章 谓词逻辑
2.1知识点总结
1. 谓词与量词
?谓词，在谓词逻辑中，原子命题分解成个体词和谓词. 个体词是可以独立存在的客体，它可以是具体事物或抽象的概念。谓词是用来刻划个体词的性质或事物之间关系的词.
个体词分个体常项(用a,b,c,,,表示)和个体变项(用x,y,z,,,表示)；谓词分谓词常项(表示具体性质和关系)和谓词变项(表示抽象的或泛指的谓词)，用F,G,P,,,表示.
注意，单独的个体词和谓词不能构成命题，将个体词和谓词分开不是命题.
?量词，是在命题中表示数量的词，量词有两类：全称量词?，表示“所有的”或“每一个”；存在量词?，表示“存在某个”或“至少有一个”.
在谓词逻辑中，使用量词应注意以下几点：
(1)在不同个体域中，命题符号化的形式可能不同，命题的真值也可能会改变.
(2)在考虑命题符号化时，如果对个体域未作说明，一律使用全总个体域.
(3)多个量词出现时，不能随意颠倒它们的顺序，否则可能会改变命题的含义.
谓词公式只是一个符号串，没有什么意义，但我们给这个符号串一个解释，使它具有真值，就变成一个命题. 所谓解释就是使公式中的每一个变项都有个体域中的元素相对应.
在谓词逻辑中，命题符号化必须明确个体域，无特别说明认为是全总个体域。一般地，使用全称量词?，特性谓词后用?；使用存在量词?，特性谓词后用?.
2. 公式与解释
?谓词公式，由原子公式、联结词和量词可构成谓词公式(严格定义见教材). 命题的符号化结果都是谓词公式.
例如?x(F(x)?G(x))，?x(F(x)?G(x))，?x?y(F(x)?F(y)?L(x,y)?H(x,y))等都是谓词公式.
?变元与辖域，在谓词公式?xA和?xA中，x是指导变元，A是相应量词的辖域. 在?x和?x的辖域A中，x的所有出现都是约束出现，即x是约束变元，不是约束出现的变元，就是自由变元. 也就是说，量词后面的式子是辖域. 量词只对辖域内的同一变元有效.
?换名规则，就是把公式中量词的指导变元及其辖域中的该变元换成该公式中没有出现的个体变元，公式的其余部分不变.
?代入规则，就是把公式中的某一自由变元，用该公式中没有出现的个体变元符号替代，且要把该公式中所有的该自由变元都换成新引入的这个符号.
?解释(赋值)，谓词公式A的个体域D是非空集合，则 (1) 每一个常项指定D中一个元素； (2) 每一个n元函数指定Dn到D的一个函数； (3) 每一个n元谓词指定Dn到{0,1}的一个谓词；
按这个规则做的一组指派，称为A的一个解释或赋值.
在有限个体域下，消除量词的规则为：如D＝{a1,a2,,,,an}，则
?xA(x)?A(a1)?A(a2)?...?A(an)?xA(x)?A(a1)?A(a2)?...?A(an)
?谓词公式分类，在任何解释下，谓词公式A取真值1，公式A为逻辑有效式(永真式)；在任何解释下谓词公式A取真值0，公式A为永假式；至少有一个解释使公式A取真值1，公式A称为可满足式.
3. 前束范式
一个谓词公式的前束范式仍是谓词公式. 若谓词公式F等值
Q1x1Q2x2...QkxkB
那么Q1x1Q2x2...QkxkB就是F的前束范式，其中Q1，Q2，,,，Qk只能是?或?，x1,x2,,,,xk是个体变元，B是不含量词的谓词公式.
每个谓词公式F都可以变换成与它等值的前束范式. 其步骤如下： ① 消去联结词?，?，??；
② 将联结词?移至原子谓词公式之前；
③ 利用换名或代入规则使所有约束变元的符号均不同，并且自由变元与约束变元的符号也不同；
④将?x,?x移至整个公式最左边；
⑤ 得到公式的前束范式.
4.谓词逻辑的推理理论 谓词演算的推理是命题演算推理的推广和扩充，命题演算中的基本等值公式，重言蕴含式以及P，T，CP规则在谓词演算中仍然使用. 在谓词演算推理中，某些前提和结论可能受到量词的限制，为了使用这些推理，引入消去和附加量词的规则，有US规则(全称量词消去规则)，UG规则(全称量词附加规则)，ES规则(存在量词消去规则)，EG规则(存在量词附加规则)等，以便使谓词演算公式的推理过程可类似于命题演算的推理进行
例2.1 将下列命题符号化：
(1) 有某些实数是有理数；
(2) 所有的人都呼吸；
(3)每个母亲都爱自己的孩子.
注意：一般地，全称量词“?”后，跟蕴含联结词“?”；存在量词“?”后，跟合取联结词“?”.
解：(1) 设R(x)：x是实数，Q(x)：x是有理数。
该命题符号化?x(R(x)?Q(x)).
(2) 设全总个体域，设M(x)：x是人.，H(x)：x要呼吸，
该命题符号化为：?x(M(x)?H(x))
该命题等价说法：“不存在不需要呼吸的人”，符号化为：??x(M(x)??H(x)). 其实它们是等值的，
?x(M(x)?H(x))???
?x(M(x)?H(x))??( ??x(?M(x)?H(x)))???x(M(x)??H(x))
若个体域D为人的集合。H(x)：x要呼吸. 则该命题符号化为?xH(x).
(3) 在全总个体域，设M(x):x是母亲，L(x,y):x爱y，A(y):y是孩子, H(x,y):x属于y 命题符号化为：
?x(M(x)??y(A(y)?H(y,x)?L(x,y)))或?x?y(M(x)?A(y)?H(y,x)?L(x,y)))
若个体域D是所有母亲的集合.
M(x)：x爱自己的孩子，该命题符号化为?xM(x).
例2.2 将公式 F??x(A(x)?B(x,y))?(?y?C(y)??zD(y,z))化为前束范式.
解 ①消去联结词?(若有?，??也要消去).
F??(?x(?A(x)?B(x,y))?(??yC(y)??zD(y,z))
② 将联结词?移至原子公式之前.
F??x?(?A(x)?B(x,y))?(?y?C(y)??zD(y,z))
??x(A(x)??B(x,y))?(?y?C(y)??zD(y,z))
F??x(A(x)??B(x,y))?(?t?C(t)??zD(y,z))(自由变元的y未改)
④ 把量词提到整个公式的前面. 为所求前束范式.
写在一起，所求前束范式是
F??x?t?z((A(x)??B(x,y))??C(t)?D(y,z))
F??(?x(?A(x)?B(x,y))?(??yC(y)??zD(y,z))
??x?(?A(x)?B(x,y))?(?y?C(y)??zD(y,z))
??x(A(x)??B(x,y))?(?y?C(y)??zD(y,z))
??x(A(x)??B(x,y))?(?t?C(t)??zD(y,z))(自由变元的y未改)
??x?t?z((A(x)??B(x,y))??C(t)?D(y,z))
第三章 集合、关系与函数
3.1知识点总结 1. 集合的概念
?集合与元素，具有确定的，可以区分的若干事物的全体称为集合，其中的事物叫元素.集合A中元素的个数为集合的元数?A?.
?集合的表示方法：列举法和描述法.
列举集合的元素，元素不能重复出现，集合中的元素无顺序之分. 集合与其元素之间存在属于“?”或不属于“?”关系.
2. 集合的关系：包含，子集，集合相等.
?包含(子集)，若?a?A?a?B，则B包含A(或A包含于B)，称A是B的
子集，记A?B，又A?B，则A是B的真子集，记A?B.
?集合相等，若A?B，B?A，则A＝B.
注意：元素与集合,集合与子集，子集与幂集，?与?(?)，空集?与所有集合等的关系.
3. 特殊集合：全集、空集和幂集.
?全集合E，在一个具体问题中，所涉及的集合都是某个集合的子集，该集合为全集.
?空集?，不含任何元素的集合为空集. 空集是惟一的，它是任何集合的子集.
?集合A的幂集P(A)，有集合A的所有子集构成的集合
P(A)={xx?A}.
若?A?＝n, 则?P(A)?=2n.
4. 集合的运算
?集合A和B的并A?B，由集合A和B的所有元素组成的集合. ?集合A和B的交A?B，由集合A和B的公共元素组成的集合.
?集合A的补集?A，属于E但不属于集合A的元素组成的集合，?A. 补集
总相对于一个全集.
?集合A与B的差集A－B，由属于A，而不属于B的所有元素组成的集合.. ?集合A与B的对称差A?B，A?B＝(A－B)?(B－A)或A?B＝）A?B〕－（A?B） 应该很好地掌握10条运算律(运算的性质)(教材P71～72)，即交换律、结合律、分配律、幂等律、同一律、零律、补余律、吸收律、摩根律和双补律等.
5. 恒等式证明
集合运算部分有三个方面的问题：其一是进行集合的运算；其二是集合运算式的化简；其三是集合恒等式的推理证明.
集合恒等式的证明方法通常有二：(1)要证明A＝B，只需要证明A?B，又A?B；
(2)通过运算律进行等式推导.
6. 有序对与笛卡儿积
?有序对，就是有顺序的数组，如，x,y 的位置是确定的，不能随意
注意：有序对?，以a,b为元素的集合{a,b}={b,a}；有序对(a,a)
有意义，而集合{a,a}是单元素集合，应记作{a}.
?笛卡儿积，把集合A，B合成集合A×B，规定
A×B＝{?x?A?y?B}
由于有序对中x,y的位置是确定的，因此A×B的记法也是确定的，不
能写成B×A.
笛卡儿积也可以多个集合合成，A1×A2×,,×An.
笛卡儿积的运算性质. 一般不能交换.
1. 关系的概念
包括定义、关系的表示方法：集合表示、矩阵表示、图形表示.
?二元关系，是一个有序对集合，设集合A,B，R?{?x,y?x?A?y?B}，
二元关系的定义域：Dom(R)?A； 二元关系的值域：Ran(R)?B ?关系的表示方法：
集合表示法：关系是集合，有类似于集合的表示方法.
列举法，如R＝{,}；描述法：如R?{?x,y?x?A?y?B}
MR?(rij)m?n,rij??
关系矩阵： R?A×B，R的矩阵
aiRbj?i?1,2...,m,?
???aiR?bj?j?1,2,...,n??
关系图： R是集合上的二元关系，若?R，由结点aI画有向弧到bj构成的图形.
2. 几个特殊的关系
空关系?；唯一是任何关系的子集的关系.
全关系EA?{?a,b?a,b?A}?A?A
恒等关系IA?{?a,a?a?A}，MI是单位矩阵.
3. 关系的运算
?关系的集合运算，有并、交、补、差和对称差. ?复合关系
R?R1?R2?{?a,c??b使?a,b??R1??b,c??R2}
MR?MR1?MR2(布尔运算)，
复合关系矩阵：有结合律：(R?S)?T＝R?(S?T)
R?{?y,x??x,y??R}M?1?MR
?逆关系，R，(R?S)－1=S－1?R－1.
4. 关系的性质
?x?A,?x,x??R；矩阵MR的主对角线元素全为1；关系图的
每个结点都有自回路.
?反自反性 ?x?A,?x,x??R；矩阵MR的主对角线元素全为0；关系图的每个结点都没有自回路.
若?x,y??R，则?y,x??R；矩阵MR是对称矩阵，即rij?rji；关系图中有向弧成对出现,方向相反.
若?x,y??R且?y,x??R，则x=y或若?x,y??R,x?y，则?y,x??R；矩阵MR不出现对称元素.
若?a,b??R且?b,c??R，则?a,c??R；在关系图中，有从a到b的弧，有从b到c的弧，则有从a到c的弧. 判断传递性较为困难.
可以证明：R是集合A上的二元关系，
(1) (1)R是自反的?IA?R;
(2)R是反自反的?IA?R＝?;
(3)R是对称的 ?R＝R－1；
(4)R是反对称的?R?R－1?IA； (5)R是传递的?R?R?R.
关系的性质所具有的运算见表4－1.
二元运算的并、交、补、差、逆、复合具有的性质表
由表可见，IA具有自反性，对称性、反对称性和传递性.EA具有自反性，对称性和传递性.故IA，EA是等价关系.?具有反自反性、对称性、反对称性和传递性。
?是偏序关系.
关系性质的判定，可以用定义、关系矩阵或关系图.
传递性的判定，难度稍大. 也常如下判定：不破坏传递性的定义，可认为具有传递性. 例如?可认为具有传递性，同时具有对称性和反对称性，但是不具有自反性；
5. 关系的闭包
设R是非空集合A上的二元关系，在关系R中，添加最少的有序对，新
关系用R?表示，使得R?具有关系的自反(对称、传递)性质，R?就是R的自反(对称、传递)闭包，记作r(R) ，s(R)和t(R)。闭包的求法：
i?1 定理12：r(R)?R?IA；定理13：s(R)?R?R；定理14的推论：
6. 等价关系和偏序关系
极大(小)元、最大(小)元问题 ?等价关系和偏序关系是具有不同性质的两个关系.
??等价关系?对称性?
自反性????传递性?
?反对称性???偏序关系
?等价关系图的特点：每一个结点都有一个自回路；两个结点间如有有向
弧线，则是双向弧线，如果从a到b，从b到c各有一条有向弧线，则从a到c一定有有向弧线。
?等价类，若R是等价关系，与R中的某个元素等价的元素组成的集合，
就是R的一个等价类，[a]R={b?b?A?aRb}.
?偏序集的哈斯图
偏序集概念和偏序集的哈斯图。哈斯图的画法：(1) 用
空心点表示结点，自环不画；(2) 若a?b，则结点b画在上边，a画在下边，并画a到b的无向弧；(3) 若,?,则?R，此时，a到c的有向弧不画出.
确定任一子集的最大(小)元，极大(小)元.
极大(小)元、最大(小)元、界 一个子集的极大(小)元可以有多个，而最大(小)元若有，只能惟一. 且极元、最元只在该子集内；而上界与下界可在子集之外确定，最小上界是所有上界中最小者，最小上界再小也不会小于子集中的任一元素；可以与某一元素相等，最大下界也是同样.
?函数, 设f是集合A到B的二元关系，?a?A,?b?B,且?f，且
Dom(f)=A，f是一个函数(映射). 函数是一种特殊的关系.
集合A×B的任何子集都是关系，但不一定是函数. 函数要求对于定义域A中每一个元素a，B中有且仅有一个元素与a对应，而关系没有这个限制.
二函数相等是指：定义域相同，对应关系相同，而且定义域内每个对应值都
?函数的类型
若a1?a2?f(a1)?f(a2)
f(A)=B. 即?y?B,?x?A,使得y?f(x) 双射
单射且满射.
?复合函数f:A?B,g:B?C,则f?g:A?C,即f?g(x)?g(f(x)). 复合成立
的条件是：Ran(f)?Dom(g)
一般f?g?g?f，但(f?g)?h?f?(g?h) 复合函数的性质：
如果f,g都是单射的，则f?g是单射的；
如果f,g都是满射的，则f?g是满射的；
如果f,g都是双射的，则f?g是双射的；
如果f,g是单射的，则f是单射的；
如果f,g是满射的，则g是满射的；
如果f?,g是双射的，则f是单射的，g是满射的.
若f：A?B是双射，则有反函数f－1：B?A
f?1?{?b,a?b?B,f(a)?b,a?A}，(f?g)?1?g?1?f?1,(f?1)?1?f
例3.1 已知S＝{2,a,{3},4},R={{a},3,4,1},指出下列命题的真值.
(1) {a}?S;
(2) {a}?R;
(3) {a,4,{3}}?S;
(4) {{a},1,3,4}?R; (5) R=S;
(6) {a}?S (7) {a}?R
(8) ??R (9) ??{{a}}?R
(10) {?}?S (11) ??R
(12) ??{{3},4}
解 集合S有四个元素：2，a，{3}，4，而元素{3}又是集合. 集合R类似.
(1) {a}，这是单元素的集合，{a}不是集合S的元素. 故命题“{a}?S”的真值为0.
(2) {a}是R的元素，故命题“{a}?R”的真值为1.
(3) a,4,{3}都是S的元素,以此为元素构成S的子集. 故命题“{a,4,{3}}?S”的真值为1.
(4) {a},1,3,4都是R的元素，构成R的子集，故命题“{{a},1,3,4}?R”的真值为1.
(6), (8)，(9)和(12)题号的命题真值为1；而(5),(7),(10)题号命题真值为0。
例3.2设集合A＝{1,2,3,4},B={2,3,5},求A?B,A?B,A?B,B?A,A?B.
解 A?B?{1,2,3,4,5}
A?B?{1,4}B?A?{5}
A?B?(A?B)?(B?A)?{1,4}?{5}?{1,4,5}
例3.3 设集合A＝{1,2},求A×P(A).
解 P(A)={?,{1},{2},{1,2}}
A×P(A)＝{1,2}×{?,{1},}{2},{1,2}
={,,,,,,,}
例3.4 设集合A＝{a,b},R是P(A)上的包含关系，写出R的表达式和关系矩阵.
解 用描述法表示； R?{?x,y?x,y?P(A)?x?y} 用列举法表示：因为P(A)?{?,{a},{b},A}，所以
?{??,??,??,{a}?,??,{b}?,??,A?,?{a},{a}?, ?{a},A?,?{b},{b}?,?{b},A?,?A,A?}
0??0?关系矩阵：
1??1?1??1??，关系图如图3-4
第四章 图论
4.1知识点总结 1. 欧拉图
? 欧拉通路(回路)与欧拉图
通过图G的每条边一次且仅一次，而且走遍
每个结点的通路(回路)，就是欧拉通路(回路). 存在欧拉回路的图就是欧拉图.
欧拉回路要求边不能重复，结点可以重复. 笔不离开纸，不重复地走完所有的边，且走过所有结点，就是所谓的一笔画.
?欧拉图或通路的判定
(1) 无向连通图G是欧拉图?G不含奇数度结点(G的所有结点度数为偶
数):(定理1)
(2) 非平凡连通图G含有欧拉通路?G最多有两个奇数度的结点；(定理1
连通有向图D含有有向欧拉通路?D中除两个结点外，其余每个结点的入度＝出度，且此两点满足deg－(u)－deg＋(v)＝?1. (定理2)
2. 哈密顿图
?哈密顿通路(回路)与哈密顿图
通过图G的每个结点一次，且仅一次的通路(回路)，就是哈密顿通路(回路). 存在哈密顿回路的图就是哈密顿图.
判断哈密顿图是较为困难的.
?哈密顿图的充分条件和必要条件
(1) 在无向简单图G=中?V??3,任意不同结点u,v?G,deg(u)?deg(v)?V,(3) 连通有向图D含有有向欧拉回路(即欧拉图)?D中每个结点的入度＝出
则G是哈密顿图.(充分条件，定理4)
(2) 有向完全图D＝, 若?3，则图D是哈密顿图. (充分条件，定
(3) 设无向图G=,?V1?V，则P(G－V1)??V1?(必要条件，定理3) 若此条件不满足，即?V1?V，使得P(G－V!)>?V1?,则G一定不是哈密顿图(非哈密顿图的充分条件).
一个图能画在平面上，除结点之外，再没有边与边相交.
面、边界和面的次数
由连通平面图G的边围成的其内部不含G的结点和边的区域是面，常用r表示. 围成面的各边组成的回路是边界. 边界回路的长度是面的次数，记作deg(r).
G??V,E?,?v,E?e,则?deg(ri)?2e
(1)平面图(所有面的次数之和＝
边的2倍)(定理6).
(2)欧拉公式：平面图G??V,E?,?v,E?e,面数为r，则v?e?r?2(结点数与面数之和＝边数＋2)(定理7)
(3)平面图G??V,E?,?v,E?e,若v?3，则e?3v?6(定理8)
?判定条件：图G是平面图的充分必要条件是G不含与K3，3或K5在2度结点内同构的子图.
连通无回路的无向图.
图T??V,E?,?n,E?m,T是树的充分必要条件是(六个等价定义) (定理14):
(1) T是无回路的连通图；
(2) 图T无回路且m＝n－1； (3) 图T连通且m＝n－1
(4) 图T无回路，若增加一条边，就得到一条且仅一条回路； (5) 图T连通，若删去任一边，G则不连通； (6) 图T的每一对结点之间有一条且仅有一条通路.
图G的生成子图是树，该树就是生成树.
?权与带权图
n个结点的连通图G，每边指定一正数，称为权，每边带权的图称为带权图. G的生成树T的所有边的权之和是生成树T的权，记作W(T).
?最小生成树
带权最小的生成树.
有向图删去边的方向为树，该有向图就是有向树.
?根树与树根
非平凡有向树，恰有一个结点的入度为0(该结点为树根)，其余结点的入度为1，该树为根树.
?每个结点的出度小于或等于2的根树为二元树(二叉树)；每个结点的出
度等于0或2的根树为二元完全树(二叉完全树)；每个结点的出度等于2的根树称为正则二元树(正则二叉树).
用哈夫曼算法得到的最优二叉树.
4. 有关树的求法
?生成树的破圈法和避圈法求法； ?最小生成树的克鲁斯克尔求法； ?哈夫曼树的哈夫曼求法.
1. 设G??V,E?,?n,E?m为连通平面图且有r个面，则r＝(
(A) m－n+2
(B) n－m－2
解答：见定理7欧拉公式.
2. 设G是5个结点的无向完全图，则从G中删去(
)条边可以得到树.
?n?(n?1)(n?2)???(n?1)???2解答：删去边的公式为?2?. 故选择(C)正确.
3. 在5个结点的二元完全树中，若有4条边，则有 (
解答：二元完全树，即每个结点只有0个或2树枝的树，树根必有2个树枝，于是2个树枝只能其一又有2个树枝，而另一个就无树枝. 满足5个结点4条边. 可见有3片树叶. 选择(B)正确.
一般地，在二元完全树中，有m条边，t片树叶，则有m=2(t－1)
4. 右图是(
(A) 完全图
(C) 平面图
(D) 哈密顿图
解答：因为n=6, 每对结点度数之和
大于或大于6，满足存在哈密顿回路的条
件，故为哈密顿图. 选择(D)正确.
逻辑推理故事
趣味推理一：头巾的颜色
有三个白人被一个印第安反对部落俘虏了。部落的首领愿意把他们放了，所以他把他们领到一个没有亮光的帐篷里。他给了每人一条头巾（他有三条头巾，
三白二红-所以有两条是没用到的）。然后他们排着队出去，这样，每个人都可以看到前面人的头巾颜色，但是看不到自己头巾的颜色（第一个走出去的人看不到任何头巾，第二个人可以看到第一个人的头巾，第三个人可以看到前面两个人的头巾）。如果有其中一个人说出了自己头巾的颜色，那所有人的可以被放了。几分钟的沉默后，其中一个人说：“我的头巾的颜色是,,”。
他头巾是什么颜色？你是怎样推敲到的？
附加条件：
你可以设想所有的囚犯都是聪明的，而且他们对同伴的智慧也很有信心。
他们猜错了一次就会被监禁。
所有人加起来只能猜一次。
所有人都想被释放。
第一个人（他看不到任何的头巾）是这样想的：
最后一个人不出声，说明了他不知道，因此他看到的最少有一条头巾是白色的。中间的人也不出声（他也知道最后一个人看到的是什么）。如果我的头巾是红色的，那么中间的那个人就知道他的是白的。然而，没有人说话，那么我的头巾一定不是红的，我的头巾是白色的。
趣味推理二：找出两处破绽 我公安机关追捕已久的黑社会头目突然被发现在一个雨天莫名其妙地触电而死。现场情况如下：死者倒在郊外一座工厂后的泥地上，面部无明显损伤，身穿普通的工作服，泥迹斑斑，脚蹬一 双新皮鞋，鞋底的花纹清晰可辨。死者仰面朝天，手心向上，手指搭在一根因失修而垂下的断电线上，头部有一处伤痕，旁边石头上有血迹宛然可见。
干警小王说，死者肯定是因路滑摔倒， 头正好撞在石头上，手指触电而死。但队长金明认为不那么简单，该罪份恐怕是与同伙火并后被害的。而现场明显是伪造的，说着他便指出了两处破绽，小王不由得心悦诚服。你能看出这两处破绽吗？
结论： 如果是滑倒，仰面朝天，应该是后脑受伤，死者“仰面朝天”，应该看不到“头部有一处伤痕”；手心向上，手指碰到电线是不会触电身亡的，因为当手指触电之后，人的肌肉会本能地收缩 ，所以只有手心向下。
趣味推理三：四个旅行者过桥
在漆黑的夜里，四位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的话，大家是无论如何也不敢过桥去的。不幸的是，四个人一共只带了一只手电筒，而桥窄得只够让两个人同时过。如果各自单独过桥的话，四人所需要的时间分别是1、2、5、8分钟；而如果两人同时过桥，所需要的时间就是走得比较慢的那个人单独行动时所需的时间。问题是:如何设计一个方案，让这四人尽快过桥。
假设这四人分别为A、B、C、D。很明显，开始两人拿着手电筒过桥后，手电筒就在桥的另一边了，此时需要已经过桥的那两人中的一个再把手电筒送回桥这边。送手电筒回来过桥也要化时间，所以要选一个跑得比较快的。一个很自然的想法就是，每次让跑得最快的A陪着另一个过桥，然后A快速地跑回来，再陪下一位过去，最后所有人就都可以过桥了。
让我们来算一下这要多长时间。为了方便起见，我们把旅行者出发的桥的这一边称为“此岸”，而把旅行者想要到达的那边叫“彼岸”。在表达一个过桥方案时，我们用“←”来表示从彼岸到此岸的移动，用“→”表示从此岸到彼岸的移动。前面“A护送大家过河”的方案就可以写成：
一共就是2+1+5+1+8=17分钟。但其实有更快的办法：
一共是2+1+8+2+2=15分钟。这个办法的聪明之处在于让两个走得最慢的人同时过桥，这样花去的时间只是走得最慢的那个人花的时间，而走得次慢的那位就不用另花时间过桥了。可以把所有可能的方案都列举一遍，就会发现这是最快的方案了。
趣味推理四：圣诞树
圣诞树上有四个天使（除了其他的东西）。两个有蓝色的光环，两个有黄色的光环，但是没有一个能看到他自己背后光环的颜色。天使A在树的最高处，他可以看到挂在下面的天使B和C。
在下面挂着天使B，他只能看见在他下面的天使C。天使C看不到任何天使，因为天使D挂在一个横枝上（没人可以看到他，他也看不到其他人）。
哪一个天使将首先说出他自己光环的颜色呢？
１ 如果天使Ｂ和天使Ｃ有同样颜色的光环，那么天使Ａ肯定马上说出他自己的颜色（不同于
其他的颜色）
２ 如果天使Ｂ和天使Ｃ有不同颜色的光环，那么天使Ａ就不肯定和沉默，那么这是给天使Ｂ
的一个信号，那么Ｂ（能看到天使Ｃ）就知道他自己的颜色（不同于天使Ｃ）。 趣味推理五：磁铁
这是一个在美国科学杂志上发表的逻辑推理题。
你在一个除了两根铁针就没有其它金属的房间里。只有一根铁针是磁铁。
你怎样鉴定呢？
1、你可以把铁棒用一根绳子吊起来看看哪一根指向北面（或者只挂一根铁棒）。
2、拿起一根铁棒用它的一头去触碰另一根铁棒的中间。如果它们互相吸引，那么拿在你手上的就是磁铁。
一块真的磁铁的磁场会在它的两级，而不在它的中间。所以就像刚才所说的，如果你拿着的是一根铁条，去触碰磁铁的中心，那么铁条是不会被吸引的。这就是假定磁铁的两级在它的两头。如果它的两级在整条磁铁上，那么这种方法就比较难了。 如果是这样，那你可以抓住一根铁棒，用它的一头去靠近另一根绕着
它的轴线旋转着的铁棒的中心。如果旋转着的铁棒是磁铁，那么磁力会随着它的旋转而变化。如果旋转着的那根不是磁铁，那么磁力的大小会保持不变（前提是你可以保持它们的位置不要移动）。
趣味推理六：男孩把表修好了
一对相爱的恋人因为家人的反对一直没有在一起，女孩曾经送给男孩一块手表，但是没多久就坏了。女孩的家人决定送她去英国读书，临行前，在机场，女孩期待来送别的男孩能够挽留她，男孩什么也没说，只是默默的把那块女孩送手表还给了女孩并且只说了一句：“已经修好了！”，女孩很伤心，在登机的一刹那，看着手里的手表，女孩突然明白了男孩的意思，决定留下来。
你知道是为什么吗？
答案：男孩把手表修好了，女孩看着手中的手表突然明白，原来男孩想表达的意思是：“不要（表）走了！”。
故事大集结
一、尔伯特的旅馆
这个旅馆有一个讨人喜欢的特性，即它有无穷多个房间。有一天，来了个新客，他失望地知道，尽管旅馆的房间是无穷多的，但是房间都有人住着。旅馆的接待员希尔伯特 (Hilbert) 想了一下，然后向这个新来的客人保证他会找到一个空房。他请每一位住客都搬到隔壁的房间去住。结果１号房间的客人搬到２号房间，２号房间的客人搬到３号房间，依此类推。原来住在旅馆中的每一位客人仍然有一个房间，而新来的客人则可以住进空出来的１号房间。
第二天晚上，希尔伯特必须对付的则是一个更大的问题。旅馆仍然是客满的，而这时无穷多辆马车载着无穷多个新客人来到了。希尔伯特依然十分镇定，搓着他的双手，心里想着旅馆又将有无穷多的进账了。他请每一位住客搬到房号为他们现在住着的房间号两倍的房间中去。结果１号房间的客人搬到了２号房间，２号房间的客人搬到了４号房间，依此类推。不但原来住在旅馆中的每一位客人仍然有一个房间，而无穷多个房间，即奇数号的房间都空出来让新来的客人居住。
从数学上讲，这个故事说的是，可数无穷多集合之间都存在一一对应的关系，也就是说它们的元素一样多。比如，自然数集、正整数集、奇数集和偶数集中的数字都一样多。这听起来似乎有些奇妙，因为所有的正整数和所有的整数怎么能一样多呢？但在数学上它们确实一样多。尽管这个故事在现实中是不可能的，但有很多其他类似的地方、类似的情况下需要人们动脑子。
二、救命的小故事
传说古代有位残暴的国王，有一次抓到一个反对他的人，一定要将这个 人处死。国王虽然心里要将反对者处死，但表面上还装出仁慈的样子：“让上帝来决定这个可怜人的命运吧，我允许他在临刑前说一句话，如果他讲的是真话，那么他将受刀斩；如果他讲的是假话，那么他将被绞死；只有他的话使我缄默不言，
那才是上帝的旨意让我赦免他。”
在国王这番冠冕堂皇的话语背后，有他的如意算盘；尽管话是由你说的，但判定真假还是由我，所以，该刀斩还是绞死不就是凭我一句话嘛。
请你想一想，反对者应该说句什么话，才能救自己一命呢？
可能你能够想出来，如果不能想出来的话，我告诉你，反对者说：“我将被绞死。”我们运用逻辑推理的知识分析这句话。
国王如果判定这句话是真话，那么按照国王的规定，反对者应当处刀斩。然而，反对说的是自己“将被绞死”，因而显然不能算为真话。
如果国王判为假话，那么按说假话的规定，反对者将被绞死，但反对者恰恰就是说自己“将被绞死”，这表明他的话是真话。因此，也不能将反对者的话定为假话。
由于国王不能自圆其说，为了顾全自己的面子，只好放了反对者。
三、半费之讼
古希腊有一个名叫普罗达哥拉斯的著名辩论家，有一天他新收了一个叫欧提勒士的学生，双方约定：两人曾订有合同，其中约定欧提勒士先付一 半学费给普罗达哥拉斯，另一半学费等欧提勒士毕业后头一次打赢官司时付清，几年后欧提勒士毕业了，但他并没有从事律师的工作，普罗达哥拉斯等得不耐烦了， 把学生告上了法庭，讨要另一半学费。
双方在各自陈述完自己的情况后，法官却面临了这样一个问题：如果欧提勒士这场官司胜诉，那么，按合同的约定，他应付给我另一半学费：如 果欧提勒士这场官司败诉，那么按法庭的判决，他也应付给我另一半学费：他这场官司或者胜诉或者败诉，所以，他无论是哪一种情况都应付给我另一半学费。
四、飞矢不动
“飞矢不动”：飞着的箭在任何瞬间都是既非静止又非运动的。如果瞬间是不可分的，箭就不可能运动，因为如果它动了，瞬间就立即是可以分的了。但是时间是由瞬间组成的，如果箭在任何瞬间都是不动的，则箭总是保持静止。所以飞出的箭不能处于运动状态。 芝诺问他的学生：“一支射出的箭是动的还是不
动的？” “那还用说，当然是动的。” “确实是这样，在每个人的眼里它都是动的。可是，这支箭在每一个瞬间里都有它的位置吗？” “有的，老师。” “在这一瞬间里，它占据的空间和它的体积一样吗？” “有确定的位置，又占据着和自身体积一样大小的空间。” “那么，在这一瞬间里，这支箭是动的，还是不动的？” “不动的，老师” “这一瞬间是不动的，那么其他瞬间呢？” “也是不动的，老师” “所以，射出去的箭是不动的？”
五、阿基里斯追龟
“阿基里斯追不上乌龟”是古希腊的一个哲学故事。阿基里斯是当时的一个善于长跑的人。阿基里斯当然能够追上乌龟，用方程可以来解决。假设阿基里斯的速度为a，乌龟的速度为b，阿基里斯开始追赶乌龟的时候，乌龟在阿基里斯的前面，假设这段距离为c，请问需要多少时间阿基里斯可以追上乌龟。设所需要的时间为x，那么ax=bx+c, x=c/(a-b).由于a b c都是常数，x当然可以求得一个解。当然如果a b 的差如果很小，那么解可以趋于无穷大。 但是在这个哲学故事里面和这个问题却毫无关系，在这个故事里面说阿基里斯追不上乌龟是说，不论阿基里斯比乌龟跑得有多快，他都追不上。 但是当我们引入无限分割的问题时，马上出现了变化。 如果我们故意这样思考：阿基里斯在追赶乌龟的过程中，或者追上乌龟之前，必须先走完乌龟当前已经超过他的距离。（这不是假设，而是确实应该的事情。但是这种思维方式却是假定的，你可以用这样的思维方式，也可以不用。一旦用了这样的思维方式，就会使思维过程没有完结，从而使得阿基里斯追不上乌龟。）按照这种思维方式，当阿基里斯走完乌龟超过他的距离后，乌龟在这段时间里也前进了一段距离，虽然愈来愈小。每次这样的思维，结果都是一样的，在这个过程中，逻辑并没有犯错。我们可以把这样的思考无限循环下去，而且乌龟继续前进的距离永远不会是零，虽然趋向无穷小，那么可以用形式逻辑的方法，推出这样的结论：阿基里斯永远追不上乌龟。 以上的问题怎么解决呢？ 或许可以用微积分的方法。阿基里斯追不上乌龟的故事中，实际涉及到：对有限空间在有限时间内以无限速度作无限分割。这个分割实际就是无穷小，我们完全可以规定这个无穷小等于0，因此只要出现无穷小的现象或情况，我们就可以认为0要出现，事物的变化就有确定性。 或许我们和古人的区别在于，我
们认为无穷小是0，而古人认为无穷小是永远不能等于0。古人他们太认真了，他们会想，无穷小仅仅是无穷小，怎么会是0呢，相反它永远也不会是0。实际上无穷小是一个完整的概念，一旦把它有限化，那么它就不是零了。要找到0与非0之间的界限，实际上还是用有限的方式，去思维无限的对象，或者把有限的事物予以无限化。
离散数学-结课论文 姓名：学号：专业： 13计算机学院： 信息工程学院手机号码： 日 目录摘要 ..................................................................…
离散数学-结课论文 姓名：学号：专业： 13计算机学院： 信息工程学院手机号码： 日 目录摘要 ..................................................................…
离散数学-结课论文 姓名：学号：专业： 13计算机学院： 信息工程学院手机号码： 日 目录摘要 ..................................................................…
本文由()首发，转载请保留网址和出处！
免费下载文档：}