离散数学(第2版)电子教案
21st Century University Planned Textbooks of Computer Science
(第2版) Discrete Mathematics (2nd Edition)
李盘林赵铭伟徐喜荣李丽双编著
□概念严谨精炼
□叙述简明清晰
□推理详尽严格
人民邮电出版社
POSTS & TELECOM PRESS
第2版前言
离散数学是现代数学的一个重要分支，是计算机科学与技术的理论基础。因此，它是计算机科学与技术专业的核心、骨干课程。一方面，它给后继课，如数据结构、编译系统、操作系统、数据库原理和人工智能等，提供必要的数学基础；另一方面，通过学习离散数学，培养和提高了学生的抽象思维和逻辑推理能力，为其今后继续学习和工作，进行科学研究，攀登科技高峰，打下扎实的数学基础。
本书第1版于2002年2月出版以来，六年来，先后多次印刷发行，已得到了普遍认可，被全国部分普通高校选作教材，本版除了勘误了第1版中的不妥之处外，还增加了一些新的章节，并相应补充了例题和习题，以适应高等学校教学改革的需要。
本书共12章，内容包括命题逻辑、谓词逻辑、集合、关系、函数、代数结构的概念及性质、半群与群、环和域、格与布尔代数、图的概念与表示、几类重要的图以及数论。
本书是笔者结合多年教学实践与科学研究，参考国内外教材，在力求通俗易懂、简明扼要的指导思想下编写而成的。在编写过程中有如下3点考虑。
1. 力求做到“少而精”，注意突出重点，论证详细明了，便于自学，在定理证明中多次运用归纳法，希望读者熟练掌握这一方法。
2. 在加强基本理论教学的同时，注意了分析问题、解决问题的技能培养和训练。书中各知识点均配有典型例子，并加以说明。此外，各章都配有适量的习题，希望通过做习题这个环节，来培养、提高学生解决问题的能力。
3. 一方面每章各有独立性，教师根据需要可以单独选讲几章；另一方面，尽可能注意各章之间的联系，规范并统一了符号和术语。
本书在编写过程中，得到了有关领导、老师和同学的热情关心、支持和帮助，在此一并表示感谢。
限于作者水平，书中难免有不当和疏漏之处，恳请读者批评指正。
编者
于大连理工大学
2008年9月
目录
第1章命题逻辑 (1)
1.1 命题与联结词 (1)
1.2 合式公式及分类 (3)
1.3 等价式与等价演算 (5)
1.4 对偶式与蕴涵式 (8)
1.5 联结词的扩充与功能完全组 (10)
1.6 公式标准型——范式 (12)
1.7 公式的主范式 (13)
1.8 命题逻辑的推理理论 (17)
第2章谓词逻辑 (21)
2.1 个体谓词和量词 (21)
2.2 谓词公式与翻译 (23)
2.3 约束变元与自由变元 (24)
2.4 公式解释与类型 (26)
2.5 等价式与蕴涵式 (27)
2.6 谓词公式范式 (29)
2.7 谓词逻辑的推理理论 (30)
第3章集合 (32)
3.1 集合论基础 (32)
3.2 集合运算及其性质 (34)
3.3 集合的笛卡儿积与无序积 (37)
3.4 有限集合的计数 (38)
第4章关系 (40)
4.1 二元关系 (40)
4.2 关系运算 (43)
4.3 关系类型 (46)
第5章函数 (51)
5.1 函数基本概念 (51)
5.2 函数类型 (52)
5.3 函数运算 (53)
5.4 基数 (55)
第6章代数结构概念及性质 (58)
6.1 代数结构的定义与例 (58)
6.2 代数结构的基本性质 (58)
6.3 同态与同构 (63)
6.4 同余关系 (66)
6.5 商代数 (67)
6.6 积代数 (68)
第7章半群与群 (70)
7.1 半群和独异点的定义及其性质 (70)
7.2 半群和独异点的同态与同构 (71)
7.3 积半群 (72)
7.4 群的基本定义与性质 (73)
7.5 置换群和循环群 (74)
7.6 子群与陪集 (77)
7.7 群的同态与同构 (80)
第8章环和域 (83)
8.1 环 (83)
8.2 子环与理想 (85)
8.3 环同态与环同构 (86)
8.4 域 (88)
第9章格与布尔代数 (90)
9.1 格 (90)
9.2 布尔代数 (97)
9.3 子布尔代数、积布尔代数和布尔代数
同态 (99)
9.4 (100)
9.5 布尔代数B2r (101)
9.6 布尔表达式及其范式定理 (102)
第10章图的概念与表示 (106)
10.1 图的基本概念 (106)
10.2 链(或路)与圈(或回路) (111)
10.3 图的矩阵表示 (115)
10.4 最短链与关键路 (124)
第11章几类重要的图 (128)
11.1 欧拉图与哈密尔顿图 (128)
11.2 二部图 (134)
11.3 树 (136)
11.4 平面图 (147)
参考文献 (153)
由于离散数学上课学时普遍减少，电子教案只包含了数理逻辑、集合论、代数结构和图论的基本理论部分。使用它的各位老师，可以根据教学计划的需求，适当做删减或增补。
第1章命题逻辑
命题逻辑，也称命题演算，记为L S。它与谓词逻辑构成数理逻辑的基础，而命题逻辑又是谓词逻辑的基础。数理逻辑，又名为符号逻辑，它是选用数学方法即通过引入没有二义性的表意符号，使用公认的与任一特定的论证无关的规则研究推理的学问。
命题逻辑是研究由命题为基本单位构成的前提和结论之间的可推导关系。那么，什么是命题？如何表示和构成？如何进行推理的？下面逐一地进行讨论。
1.1 命题与联结词
1.命题的概念
所谓命题，是指具有非真必假的陈述句。而疑问句、祈使句和感叹句等因都不能判断其真假，故都不是命题。命题仅有两种可能的真值：真和假，且二者只能居其一。真用1或T表示，假用0或F表示。由于命题只有两种真值，所以称这种逻辑为二值逻辑。命题的真值是具有客观性质的，而不是由人的主观决定的。
例1.1.1 判断下列语句哪些是命题
①6是整数。
②地球是方的。
③3+5=8。
④金星的表面温度是800?F。
⑤请勿吸烟！
⑥你去书店吗？
⑦今天天气真好！
⑧本命题是假的。
解显然，①-④都是命题，①和③的真值为真，②真值是假，而④目前尚不知真和假，但随着科技的发展，其真值是可以确定的。⑤-⑦都不是命题。因为它们不是陈述句，而分别是祈使句、疑问句和感叹句。⑧无法确定它的真值，当它假时，它便真；当它真时，它便假。这种断言叫悖论。
2.命题分类与表示
命题分为两类，第一类是原子命题，它是由再也不能分解成更为简单的语句构成的命题，称为原子命题。原子命题是命题逻辑的基本单位。原子命题用大写英文字母P，Q，R，…及其带下标P i，Q i，R i，…表示之。例如，用P表示大连是一座美丽的城市，记为P：大连是一座美丽的城市。冒号：代表表示的意思，下同。上面那些表示命题的英文字母，称为命题标识符。
第二类是复合命题，它由原子命题、命题联结词和圆括号组成。什么是命题联结词？下面就来定义五个常用命题联结词。
3.命题联结词
定义1.1.1设P表示一个命题，由命题联结词?和命题P连接成?P，称?P为P的否定式复合命题，?P读“非P”。称?为否定联结词。?P是真当且仅当P为假；否定联结词“?”的定义可由表1.1.1表示之。
例1.1.2举例说明如何构成命题的否定。
解令命题
P：大连是一座美丽的城市。
于是命题的否定为
?P：大连不是一座美丽的城市。
可见，“否定”修改了命题，它是对单个命题进行操作，称它为一元联结词。
定义1.1.2设P和Q为两个命题，由命题联结词∧将P和Q连接成P∧Q，称P∧Q为命题P和Q的合取式复合命题，P∧Q读做“P与Q”，或“P且Q”。称∧为合取联结词。
当且仅当P和Q的真值同为真，命题P∧Q的真值才为真；否则，P∧Q的真值为假。合取联结词∧的定义由表1.1.2表示之。
例1.1.3 用合取联结词表示命题：我们踢足球，他们在游泳。
解令P：我们踢足球
Q：他们在游泳
本例可表成：P∧Q。
在日常生活中，常将“合取”表示具有某种关系的两个命题；但在命题逻辑中则不尽然，允许用于两个相互无关的原子命题。例如，可用原子命题“P：今天天晴”和“Q：三加三等于六”，构成复合命题P∧Q，其意义是
今天天晴且三加三等于六。
这在日常生活中会认为有语病，而在逻辑学中是允许的。
类似定义1.1.2，可定义1.1.3-1.1.5的定义。
4.命题符号化
把一个用文字叙述的命题相应地表成由命题标识符、联结词和圆括号的形式，称为命题的符号化。符号化应该注意下列事项：
①确定给定句子是否为命题。
②句子中连词是否为命题联结词。
③要正确地表示原子命题和适当选择命题联结词。
例1.1.7张明正在睡觉或游泳。
解此例可改叙为“张明在睡觉而没游泳，或者张明在游泳而没睡觉。”可知其中的“或者”是可兼或，因此可用析取式复合命题表示。
令P：张明在睡觉，Q：张明在游泳，则该例符号化为(P∧?Q)∨(Q∧?P)。
命题符号化是很重要的，一定要掌握好，在命题推理中常常最先遇到的就是符号化一个问题，解决不好，等于说推理的首要前提没有了。
在本节结束时，应强调指出的是：复合命题的真值只取决于各原子命题的真值，而与它们的内容、含义无关，与原子命题之间是否有关系无关。理解和掌握这一点是至关重要的，请读者认真去领会。
1.2 合式公式及分类
由于合式公式重要涉及命题变元，因此先来讨论什么是命题变元。
1.命题变元
在命题逻辑中，命题又有命题常元和命题变元之分。如果P代表一个确定的具体的命题，称P为命题常元；若P代表一个不确定的泛指的任意命题，称P为命题变元。显然，命题变元P不是命题，只有用一个特定的命题或一个真值取代P才能成为命题。这时也说对P指派或解释，记为I(P)。在命题逻辑中并不关心具体命题的涵义，只关心其真值。因此，可以形式地定义它们如下：
定义1.2.1以真、假为其变域的变元，称为命题变元；真值，以及一个确定的具体命题称为命题常元。
2.合式公式
通常把含有命题变元的断言称为命题公式。但这没能指出命题公式的结构。因为不是所有由命题变元、联结词和括号所组成字符串都能成为命题公式。为此常使用归纳定义命题公式，以便构成的公式有规则可循。由这种定义产生的公式称为合式公式。
定义1.2.2单个命题变元和命题常元称为原子命题公式，简称原子公式。
定义1.2.3合式公式是由下列规则生成的公式：
①单个原子公式是合式公式。
②若A是一个合式公式，则(?A)也是一个合式公式。
③若A、B是合式公式，则(A∧B)、(A∨B)、(A→B)和(A?B)都是合式公式。
④只有有限次使用①、②和③生成的公式才是合式公式。
合式公式中的命题标识符、联结词和左右括号的数目，称为合式公式的长度。请注意，这里A，B等表示任意合式公式，而不是某个具体的公式，称它们为元语言符号；对于诸如P∧Q，(P→Q)∨R等称为目标语言符号或对象语言符号。
例1.2.1说明(P→(Q∨R))是合式公式
解(1) Q是合式公式根据规则①
(2) R是合式公式根据规则①
(3) (Q∨R)是合式公式根据(1)、(2)和规则③
(4) (Q→(Q∨R))是合式公式根据(1)、(3)和规则③
显然那些不能由定义中指出的规则生成的字符串，均不是合式公式，如下列字符串：
①?P∧Q
②P→(∧Q)
③(P→Q
当合式公式比较复杂时，常常使用很多圆括号，为了减少圆括号的使用量，可作以下约定：
①规定联结词的优先级由高到低的次序为：
?、∧、∨、→、?
②相同的联结词按从左至右次序计算时，圆括号可省略。
③最外层的圆括号可以省略。
例如，(?((P∧Q)∨(?R))→((P∨Q)∨R))
可写成：
?(P∧Q∨?R)→P∨Q∨R
便有时为了看起来清楚醒目，也常常保留某些原可省去的圆括号。
为了方便计，合式公式也简称公式。
3.公式真值表
对于含有命题变元的公式A，因它不能确定其真假，故该公式不是命题。但对公式中A出现的每一个命题变元指派一真值，称该组真值为公式的一个指派或解释，记为I(A)。于每个指派，公式确定一个真值。若公式确定真值为真，称该指派为成真指派；否则，称为成假指派。对于所有的指派及相应的公式真值即组成了该公式的真值表。下面正式给出公式真值表的定义。
定义1.2.4对于公式中命题变元的每一种可能的真值指派，以及由它们确定出的公式真值所列成的表，称为该公式的真值表。
由本定义可知，在先前命题联结词定义中所给出的各表，都是真值表，即相应也称为各命题联结词真值表。
定义1.2.5如果B是公式A中的一部分，且B为公式，则称B是公式A的子公式。
例如，设A为(P→Q)∧?R，则?R，P→Q等都是A的子公式。
下面用例子说明公式真值表的构造方法。
例1.2.2 构造公式P→(Q∧?P)的真值表。
解该公式含有两个命题变元P和Q，它们一共有4种指派，分别为：00、01、10、11。对此4种指派，依据联结词的定义及其优先级和括号，逐步求出各子公式直至给定公式的真值。详见下表：
其中①、②、③和④是求各子公式真值的次序，⑤为给定公式的真值。
4.公式分类
定义1.2.6设A为任一公式
①对应每一个指派，公式A均相应确定真值为真，称A为重言式，或永真式。
②对应每一个指派，公式A均相应确定真值为假，称A为矛盾式，或永假式。
③至少存在一个指派，公式A相应确定真值为真，称A为可满足式。
由定义可知，重言式必是可满足式，反之一般不真。
判定给定公式是否为永真式，永假式或可满足式的问题，称为给定公式的判定问题。
在L S 中，由于任何一个命题公式的指派数目总是有限的，所以L S 的判定问题是可解的。其判定方法有真值表法和公式推演法。
例1.2.3 用真值表判定公式?(?P →Q )∧P 是永真式，永假式还是可满足式。
解
可见，?(?P →Q )∧P 为永假式。
1.3 等价式与等价演算
1.等价式
从例1.2.4可知，的确有一些公式，它们的真值表是相同的，也就是说，同一个真值表可能会代表许多公式。这样，又可以按真值表是否相同来对公式进行分类。同一类中的公式之间，它们彼此是等价的。下面正式给出两个公式是等价的定义。
定义1.3.1 设A 和B 是两个命题公式，如果A 、B 在其任意指派下， 其真值都是相同的，则称A 和B 是等价的，或逻辑相等，记作A ?B ，读作A 等价B ，称A ?B 为等价式。
显然，若公式A 和B 的真值表是相同的，则A 和B 等价。因此，验证两公式是否等价，只需做出它们的真值表即可。
例1.3.1 证明P ?Q ?(
P →Q )∧(Q →P )
证明 列出真值表如下：
可见，P 读者也不难验证下列等价式：
① P ???P ② P ∨P ?P ③ (P ∨?P )∧Q ?Q ④ P ∨?P ?Q ∨?Q
由此可见，两公式等价，不一定是含相同的命题变元。
在这里，请读者注意?和?的区别与联系。
区别：?是逻辑联结词，属于目标语言中的符号，它出现在命题公式中；?不是逻辑联结词，属于元语言中的符号，表示两个命题公式的一种关系，不属于这两个公式的任何一个公式中的符号。
联系：可用下面定理表明之。
定理1.3.1 A ?B 当且仅当A ?B 是永真式。
2.基本等价式——命题定律
在判定公式间是否等价，有一些简单而又经常使用的等价式，称为基本等价式或称命题定律。
牢固地记住它并能熟练运用，是学好数理逻辑的关键之一，读者应该注意到这一点。现将这些命题定律列出如下：
(1) 双否定：??A?A。
(2) 交换律：A∧B?B∧A，A∨B?B∨A，A?B?B?A。
(3) 结合律：(A∧B)∧C?A∧(B∧C)，(A∨B)∨C?A∨(B∨C)，(A?B)?C?A?(B?C)。
(4) 分配律：A∧(B∨C)?(A∧B)∨(A∧C)，A∨(B∧C)?(A∨B)∧(A∨C)。
(5) 德·摩根律：?(A∧B)??A∨?B，?(A∨B)??A∧?B。
(6) 等幂律：A∧A?A，A∨A?A。
(7) 同一律：A∧T?A，A∨F?A。
(8) 零律：A∧F?F，A∨T?T。
(9) 吸收律：A∧(A∨B)?A，A∨(A∧B)?A。
(10) 互补律：A∧?A?F，(矛盾律)
A∨?A?T。(排中律)
(11) 条件式转化律：A→B??A∨B，A→B??B→?A。
(12) 双条件式转化律：A?B?(A→B)∧(B→A)?(A∧B)∨(?A∧?B)
?A?B??(A?B)
(13) 输出律：(A∧B)→C?A→(B→C)。
(14) 归谬律：(A→B)∧(A→?B)??A。
3.代入规则和替换规则
在定义合成公式时，已看到了逻辑联结词能够从已知公式形成新的公式，从这个意义上可把逻辑联结词看成运算。除逻辑联结词外，还要介绍“代入”和“替换”，它们也有从已知公式得到新的公式的作用，因此有人也将它们看成运算，这不无道理，而且在今后讨论中，它的作用也是不容忽视的。
(1) 代入规则
定理1.3.2在一个永真式A中，任何一个原子命题变元R出现的每一处，用另一个公式代入，所得公式B仍是永真式。本定理称为代入规则。
证明因为永真式对任意指派，其值都是真，与所给的某个命题变元指派的真值是真还是假无关，因此，用一个命题公式代入到原子命题变无R出现的每一处后，所得命题公式的真值仍为真，证毕。
例1.3.2求证：(P→Q)∨?(P→Q)为永真式。
证明由排中律可知，R∨?R?T，即R∨?R为永真式。今用公式(P→Q)代入前面公式中的命题变元R，则得(P→Q)∨?(P→Q)。根据代入规则可知，给定公式是永真式。
注意，若仅仅反映(P→Q)代入到一个析取项R，得到(P→Q)∨?R，显然它不是永真式，因为这不符合代入规则所要求的处处代入。
(2)替换规则
定理1.3.3设A1是合式公式A的子公式，若A1?B1，并且将A中的A1用B1替换所得到公式B，则A?B。称该定理为替换规则。
证明因为A1?B1，即对于它们的命题变元做任何真值的指派，A1与B1的真值相同，故以B1替换A1后，公式B与A在对其命题变无做相应的任何真值指派，它们的真值亦相同，因此，A?B成立。
华南农业大学 离散数学 期末考试2013试卷及答案
华南农业大学期末考试试卷（A 卷） 2013-2014学年第 一 学期 考试科目： 离散结构 考试类型：（闭卷）考试 考试时间： 120 分钟 学号 姓名 年级专业 ①本试题分为试卷与答卷2部分。试卷有四大题，共6页。 ②所有解答必须写在答卷上，写在试卷上不得分。 一、选择题（本大题共 25 小题，每小题 2 分，共 50 分） 1、下面语句是简单命题的为_____。 A 、3不是偶数 B 、李平既聪明又用功 C 、李平学过英语或日语 D 、李平和张三是同学 2、设 p:他主修计算机科学, q:他是新生，r:他可以在宿舍使用电脑，下列命题“除非他不是新生，否则只有他主修计算机科学才可以在宿舍使用电脑。”可以符号化为______。 A 、r q p →?∧? B 、r q p ?→∧? C 、r q p →?∧ D 、r q p ∧→ 3、下列谓词公式不是命题公式P →Q 的代换实例的是______。 A 、)()(y G x F → B 、),(),(y x yG y x xF ?→? C 、))()((x G x F x →? D 、)()(x G x xF →? 4、设个体域为整数集，下列公式中其值为 1的是_____。 A 、)0(=+??y x y x B 、)0(=+??y x x y C 、)0(=+??y x y x D 、)0(=+???y x y x
2 5、下列哪个表达式错误_____。 A 、 B x xA B x A x ∧??∧?)())(( B 、B x xA B x A x ∨??∨?)())(( C 、B x xA B x A x →??→?)())(( D 、)())((x xA B x A B x ?→?→? 6、下述结论错误的是____。 A 、存在这样的关系，它可以既满足对称性，又满足反对称性 B 、存在这样的关系，它可以既不满足对称性，又不满足反对称性 C 、存在这样的关系，它可以既满足自反性，又满足反自反性 D 、存在这样的关系，它可以既不满足自反性，又不满足反自反性 7、集合A 上的关系R 为一个等价关系，当且仅当R 具有_____。 A 、自反性、对称性和传递性 B 、自反性、反对称性和传递性 C 、反自反性、对称性和传递性 D 、反自反性、反对称性和传递性 8、下列说法不正确的是：______。 A 、R 是自反的，则2R 一定是自反的 B 、R 是反自反的，则2R 一定是反自反的 C 、R 是对称的，则2R 一定是对称的 D 、R 是传递的，则2R 一定是传递 9、设R 和S 定义在P 上，P 是所有人的集合，=R {x P y x y x ∧∈><,|,是y 的父亲}，=S {x P y x y x ∧∈><,|,是y 的母亲}，则关系{y P y x y x ∧∈><,|,是的x 外祖父}的表达式是：______。 A 、11--R R B 、11--S R C 、11--S S D 、11--R S 10、右图描述的偏序集中，子集},,{f e b 的上界为_____。 A 、c b , B 、b a , C 、b D 、c b a ,, 11、以下整数序列，能成为一个简单图的顶点度数序列的是_____。 A 、1，2，2，3，4，5
离散数学答案屈婉玲版第二版高等教育出版社课后答案
离散数学答案屈婉玲版 第二版高等教育出版社课后答案 第一章部分课后习题参考答案 16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 （1）p∨(q∧r)?0∨(0∧1) ?0 （2）（p?r）∧(﹁q∨s) ?（0?1）∧(1∨1) ?0∧1?0. （3）（?p∧?q∧r）?(p∧q∧﹁r) ?（1∧1∧1）? (0∧0∧0)?0 (4)（?r∧s）→(p∧?q) ?（0∧1）→(1∧0) ?0→0?1 17．判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。” 答：p: π是无理数1 q: 3是无理数0 r: 2是无理数 1 s: 6能被2整除1 t: 6能被4整除0 命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。19．用真值表判断下列公式的类型： （4）(p→q) →(?q→?p) （5）(p∧r) ?(?p∧?q) （6）((p→q) ∧(q→r)) →(p→r) 答：（4） p q p→q ?q ?p ?q→?p (p→q)→(?q→?p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式
（5）公式类型为可满足式（方法如上例） （6）公式类型为永真式（方法如上例） 第二章部分课后习题参考答案 3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ?(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 答：(2)（p→(p∨q)）∨(p→r)?(?p∨(p∨q))∨(?p∨r)??p∨p∨q∨r?1所以公式类型为永真式 (3)P q r p∨q p∧r （p∨q）→(p∧r) 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 所以公式类型为可满足式 4.用等值演算法证明下面等值式： (2)(p→q)∧(p→r)?(p→(q∧r)) (4)(p∧?q)∨(?p∧q)?(p∨q) ∧?(p∧q) 证明（2）(p→q)∧(p→r) ?(?p∨q)∧(?p∨r) ??p∨(q∧r)) ?p→(q∧r) （4）(p∧?q)∨(?p∧q)?(p∨(?p∧q)) ∧(?q∨(?p∧q)
屈婉玲版离散数学课后习题答案【2】
第四章部分课后习题参考答案 3. 在一阶逻辑中将下面将下面命题符号化,并分别讨论个体域限制为(a),(b)条件时命题的真值: (1) 对于任意x,均有错误！未找到引用源。2=(x+错误！未找到引用源。)(x 错误！未找到引用源。). (2) 存在x,使得x+5=9. 其中(a)个体域为自然数集合. (b)个体域为实数集合. 解： F(x): 错误！未找到引用源。2=(x+错误！未找到引用源。)(x 错误！未找到引用源。). G(x): x+5=9. (1)在两个个体域中都解释为)(x xF ?，在（a ）中为假命题，在(b)中为真命题。 (2)在两个个体域中都解释为)(x xG ?，在（a ）(b)中均为真命题。 4. 在一阶逻辑中将下列命题符号化: (1) 没有不能表示成分数的有理数. (2) 在北京卖菜的人不全是外地人. 解: (1)F(x): x 能表示成分数 H(x): x 是有理数 命题符号化为: ))()((x H x F x ∧??? (2)F(x): x 是北京卖菜的人 H(x): x 是外地人 命题符号化为: ))()((x H x F x →?? 5. 在一阶逻辑将下列命题符号化: (1) 火车都比轮船快. (3) 不存在比所有火车都快的汽车. 解: (1)F(x): x 是火车; G(x): x 是轮船; H(x,y): x 比y 快
命题符号化为: )) F x G x→ ∧ ? ? y y ( )) ( ) , x ((y ( H (2) (1)F(x): x是火车; G(x): x是汽车; H(x,y): x比y快 命题符号化为: ))) x x F y y→ ?? ∧ ? G (y H ( , ( ) ( ( x ) 9.给定解释I如下: (a) 个体域D为实数集合R. (b) D中特定元素错误！未找到引用源。=0. (c) 特定函数错误！未找到引用源。(x,y)=x错误！未找到引用源。y,x,y D ∈错误！未找到引用源。. (d) 特定谓词错误！未找到引用源。(x,y):x=y,错误！未找到引用源。(x,y):x 、基本等值式 ⑴双重否定律 A A ⑵籍等律 A A A A A V A A ⑶交换律 A A B BA A A V B BV A ⑷结合律 A V (B V C) (A V B) V C A A (B A C) (A A B) A C ⑸分配律 A V (B A C) (A V B) A (A V C) A A (B V C) (A A B) V (A A C) (6)德摩根律(A V B) AA B (A A B) AV B ⑺吸收律 A (8)零律A ⑼同一律 A (10) 排中律 A (11) 矛盾律 A (12) 蕴含等值式A (13) 等价等值式A V (A A B) V1 1 A1 A V A 1 A A 0 B AV B (A A A A A B B) A (B A) A (A V B) A 0 0 V 0 A A A B (AV B) A (A V B) A B (A A B) V ( AA B ) (14) 假言易位ABBA (15) 等价否定等值式ABA B (16)归谬论(A B) A (A B) A 一、推理定律里口编涵式 1.A ( A B) 附加律 2.( A B) A 化简律 3.( A B) A B 假言推理 4.( A B) B A 拒取式 5.( A B) B A 析取三段论 6.( A B) (B C) (A 假言三段论 7.( A B) (B Q (A C) 等价三段论 8.( A B) (C D) (A C) (B D) 构造性二难 (A B) ( A B) B 构造性二难(特殊形式) 9.( A B) (C D) ( B D) ( A Q 破坏性二难 三、量词辖域收缩与扩张 x(A(x) V B) xA(x) VB x(A(x) A B) xA(x) AB x(A(x) —B) xA(x) F x(B t A(x)) B T xA(x) x(A(x) V B) xA(x) VB x(A(x) A B) xA(x) A B x(A(x) —B) xA(x) F x(B t A(x)) B T xA(x) 四、量词分配 x(A(x) A B(x)) xA(x) A xB(x) x(A(x) V B(x)) xA(x) V xB(x) x(A(x) V B(x)) xA(x) V xB(x) 《离散数学》期末复习题 一、填空题（每空2分，共20分） 1、集合A上的偏序关系的三个性质是、 和。 2、一个集合的幂集是指。 3、集合A={b,c}，B={a,b,c,d,e}，则A?B= 。 4、集合A={1,2,3,4}，B={1,3,5,7,9}，则A?B= 。 5、若A是2元集合, 则2A有个元素。 6、集合A={1,2,3｝，A上的二元运算定义为：a* b = a和b两者的最大值，则 2*3= 。 7、设A={a, b,c,d }, 则∣A∣= 。 8、对实数的普通加法和乘法，是加法的幂等元， 是乘法的幂等元。 9、设a,b,c是阿贝尔群 19、代数系统是指由及其上的或 组成的系统。 20、设 离散数学基础试题（二） 一、判断题（每题2分，共12分） 1.在命运题逻辑中，任何命题公式的主合取范式都是存在的，并且是唯一的。（） 2.与是不等值的（） 3.设是非连通平面图G的对偶图，设分别为的顶点数，边数和面数，则它们之间满足欧拉公式：。（） 4.设无向图G具有割点，则G中一定不存在哈密尔顿通路。（） 5.设，A上的恒等关系既是A上的等价关系也是A上的偏序关系。（） 6.设A,B,C,D均为非空的集合，已知A*B且C*D，则一定有。（） 二、填空题（每小题3分，共30分） 1.设p:小王走路,q:小王听音乐,在命题逻辑中，命题“小王边走路边听音乐”的符号化形式为___________________。 2.设F(x):x是人，H(x,y):x与y一样高，在一阶逻辑中，命题“人都不一样高”的符号化形式为_________________。 3.的成真赋值为________________________。 4.设G是n阶无向带权边通图，各变的权均为a(a>0),设T是G的一棵最小生成树，则T的权W(T)=_______________________。 5.设G1,G2,G3,G4都是4阶3条边的无向简单图，则它们之间至少有 ___________________个是同构的。 6．设G是n（n2）阶二部图，又是平面图，则命题“G的对偶图是欧拉图”的真值为_______________________。 7.设为整数集，，则f的值域ranf=___________。 8.设则A上共有____________个不同的等价关系。 9.设，恒等关系IA的传递闭包t(IA)=_________________。 1.常用公式 p ∧(P →Q)=>Q 假言推论 ┐Q ∧(P →Q)=>┐P 拒取式 ┐p ∧(P ∨Q)=>Q 析取三段式 (P →Q) ∧(Q →R)=>P →R 条件三段式 (PQ) ∧(QR)=>PR 双条件三段式 (P →Q)∧(R →S)∧(P ∧R)=>Q →S 合取构造二难 (P →Q)∧(R →S)∧(P ∨R)=>Q ∨S 析取构造二难 (?x)((Ax)∨(Bx)) <=>( ?x)(Ax)∨(?x)(Bx) (?x)((Ax)∧(Bx)) <=>(?x)(Ax)∧(?x)(Bx) —┐(?x)(Ax) <=>(?x)┐(Ax) —┐(?x)(Ax) <=>(?x)┐(Ax) (?x)(A ∨(Bx)) <=>A ∨(?x)(Bx) (?x)(A ∧(Bx)) <=>A ∧(?x)(Bx) (?x)((Ax)→(Bx)) <=>(?x)(Ax)→(?x)(Bx) (?x)(Ax) →B <=>(?x) ((Ax)→B) (?x)(Ax) →B <=>(?x) ((Ax)→B) A →(?x)(Bx) <=>(?x) (A →(Bx)) A →(?x)(Bx) <=>(?x) (A →(Bx)) (?x)(Ax)∨(?x)(Bx) =>(?x)((Ax)∨(Bx)) (?x)((Ax)∧(Bx)) =>(?x)(Ax)∧(?x)(Bx) (?x)(Ax)→(?x)(Bx) =>(?x)((Ax)→(Bx)) 2.命题逻辑 1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假； 2.主析取范式：极小项(m)之和；主合取范式：极大项(M)之积； 3.求极小项时，命题变元的肯定为1，否定为0，求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假； 5.求范式时，为保证编码不错，命题变元最好按P ,Q,R 的顺序依次写； 6.真值表中值为1的项为极小项，值为0的项为极大项； 7.n 个变元共有n 2个极小项或极大项，这n 2为(0~n 2-1)刚好为化简完后的主析取加主合取； 8.永真式没有主合取范式，永假式没有主析取范式； 9.推证蕴含式的方法(=>)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假推出后键也为假) 10.命题逻辑的推理演算方法：P 规则，T 规则 ①真值表法；②直接证法；③归谬法；④附加前提法； 3.谓词逻辑 1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n 个个体，多元谓词描述个体之间的关系； 2.全称量词用蕴含→，存在量词用合取^; 3.既有存在又有全称量词时，先消存在量词，再消全称量词； 4.集合 1.N ，表示自然数集，1,2,3……，不包括0； 2.基：集合A 中不同元素的个数，|A|； 3.幂集：给定集合A ，以集合A 的所有子集为元素组成的集合，P(A)； 4.若集合A 有n 个元素，幂集P(A)有n 2个元素，|P(A)|=||2A =n 2； 5.集合的分划：(等价关系) ①每一个分划都是由集合A 的几个子集构成的集合； ②这几个子集相交为空，相并为全(A)； 6.集合的分划与覆盖的比较： 分划：每个元素均应出现且仅出现一次在子集中； 覆盖：只要求每个元素都出现，没有要求只出现一次； 5.关系 1.若集合A 有m 个元素，集合B 有n 个元素，则笛卡尔A ×B 的基数为mn ，A 到B 上可以定义mn 2种不同的关系； 2.若集合A 有n 个元素，则|A ×A|=2n ，A 上有22n 个不同的关系； 3.全关系的性质：自反性，对称性，传递性； 空关系的性质：反自反性，反对称性，传递性； 全封闭环的性质：自反性，对称性，反对称性，传递性； 4.前域(domR)：所有元素x 组成的集合； 后域(ranR)：所有元素y 组成的集合； 5.自反闭包：r(R)=RU Ix ; 对称闭包：s(R)=RU 1-R ; 传递闭包：t(R)=RU 2R U 3R U …… 6.等价关系：集合A 上的二元关系R 满足自反性，对称性和传递性，则R 称为等价关系； 7.偏序关系：集合A 上的关系R 满足自反性，反对称性和传递性，则称R 是A 上的一个偏序关系； 8.covA={ 一（6%）选择填空题。 (1) 设S = {1，2，3}，R 为S 上的二元关系，其关系图如右图所示，则R 具有（ ）的性质。 A. 自反、对称、传递； B. 反自反、反对称； C. 自反、传递； D. 自反。 (2) 设A = {1, 2, 3, 4}， A 上的等价关系 R = { (4)没有不犯错的人。 五（10%）在自然推理系统Ｐ中构造下面推理的证明： 如果他是计算机系本科生或者是计算机系研究生，则他一定学过DELPHI语言且学过C++语言。只要他学过DELPHI语言或者Ｃ++语言，那么他就会编程序。因此如果他是计算机系本科生，那么他就会编程序。 六（10%）在自然推理系统中构造下面推理的证明（个体域：人类）： 每个喜欢步行的人都不喜欢坐汽车，每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车，因而有的人不喜欢步行。 七（14%）下图给出了一些偏序集的哈斯图，判断其是否为格，对于不是格的说明理由，对于是格的说明它们是否为分配格、有补格和布尔格（布尔代数）。 八（12%）设S = {1, 2, 3, 4, 6, 8, 12, 24}，“ ”为S上整除关系， (1)画出偏序集> ,S的哈斯图； < (2)设B = { 2, 3, 4, 6, 12}，求B的极小元、最小元、极大元、最大元，下界，上界。 九（8%）画一个无向图，使它是： (1)是欧拉图，不是哈密尔顿图； (2)是哈密尔顿图，不是欧拉图； (3)既不是欧拉图，也不是哈密尔顿图； 并且对欧拉图或哈密尔顿图，指出欧拉回路或哈密尔顿回路，对于即不是欧拉图也不是哈密尔顿图的说明理由。 十（8%）设6个字母在通信中出现的频率如下： 12 13 :c :b% 45 :a% % :e% :f 9 5 : d% % 16 用Huffman算法求传输它们的最佳前缀码。要求画出最优树，指出每个字母对应的编码，n个按上述频率出现的字母需要多少个二进制数字。 并指出传输)2 ( n 10≥ 理学院 《离散数学基础》实验教学大纲 课程名称：离散数学基础实验 课程编号：080J21A 课程总学时：51 实验学时数：17 课程总学分：2.5 实验学分：0.5 开设实验项目数：5 一、实验教学目的 面向离散数学在计算机中的应用，通过实验操作，使学生掌握研究计算机科学的基础理论，进一步提高学生的抽象思维与逻辑推理能力，增强实际应用能力。 二、实验项目内容、基本要求与学时分配 注：1、实验类型：演示、验证、操作、综合、设计、研究。2、实验要求：指必做、选做。 三、实验考核方式与标准 实验考核以学生的实验态度、掌握的实验理论、实际操作技能和实验报告等为主，各单项考核内容所占分数比例为：实验态度占10%、实验理论占15%；操作技能占50%；实验报告占25%。 四、实验教材与参考书 推荐教材：《离散数学》（修订版），耿素云屈婉玲编著，高等教育出版社，2004年。 主要参考书：《离散数学导论》第二版，徐洁磬编著，高等教育出版社，1997年。 《离散数学》， [美]S.利普舒尔茨， M.利普森，周兴和、孙志人、张学斌译, 科学出版社和麦格劳-希尔教育出版集团, 2001年。 《计算方法》实验教学大纲 课程名称：计算方法实验 课程编号：080J22B 课程总学时：85 实验学时数：34 课程总学分：4 实验学分：1 开设实验项目数：5 一、实验教学目的 本课程以MATLAB或C为编程语言，将《计算方法》课程中的常用算法用MATLAB语言描述并上机进行数值实验。通过实验，使学生进一了解各个算法的特点及适用范围，提高学生用计算机解决实际问题的能力。 二、实验项目内容、基本要求与学时分配 三、实验考核方式与标准 实验考核以学生的实验态度、掌握的实验理论、实际操作技能和实验报告等为主，各单项考核内容所占分数比例为：实验态度占10%、实验理论占15%；操作技能占50%；实验报告占25%。 四、实验教材与参考书 1、《计算机数值方法》（第二版），施吉林等，高教出版社出版，2005年 2、《计算方法引论》（第二版），徐翠薇、孙绳武，高等教育出版社，2002 《离散数学》试卷（A 卷） 一、 选择题（共5 小题，每题 3 分，共15 分） 1、设A={1,2,3},B={2,3,4,5},C={2,3},则C B A ⊕?)(为(C )。 A 、{1,2} B 、{2,3} C 、{1,4,5} D 、{1,2,3} 2、下列语句中哪个是真命题 ( A ) A 、如果1+2=3，则4+5=9； B 、1+2=3当且仅当4+5≠9。 C 、如果1+2=3，则4+5≠9； D 、1+2=3仅当4+5≠9。 3、个体域为整数集合时，下列公式（ C ）不是命题。 A 、)*(y y x y x =?? B 、)4*(=??y x y x C 、)*(x y x x =? D 、)2*(=??y x y x 4、全域关系A E 不具有下列哪个性质（ B ）。 A 、自反性 B 、反自反性 C 、对称性 D 、传递性 5、函数612)(,:+-=→x x f R R f 是（ D ）。 A 、单射函数 B 、满射函数 C 、既不单射也不满射 D 、双射函数 二、填充题（共 5 小题，每题 3 分，共15 分） 1、设|A|=4，|P(B)|=32，|P(A ?B)|=128，则|A ?B|=??2???. 2、公式)(Q P Q ?∨∧的主合取范式为 。 3、对于公式))()((x Q x P x ∨?，其中)(x P ：x=1， )(x Q ：x=2，当论域为{0,1,2}时，其真值为???1???。 4、设A ＝{1,2,3,4}，则A 上共有???15????个等价关系。 5、设A ＝{a ，b ，c }，B={1,2},则|B A |= 8 。 三、判断题（对的填T ，错的填F ，共 10 小题，每题 1 分，共计10 分） 1、“这个语句是真的”是真命题。 （ F ） 2、“张刚和小强是同桌。”是复合命题。 （ F ） 3、))(()(r q q p p ∧?∧→?∨是矛盾式。 （ T ） 4、)(T S R T R S R ??????。 （ F ） 5、恒等关系具有自反性，对称性，反对称性，传递性。 （ T ） 6、若f 、g 分别是单射,则g f ?是单射。 （ T ） 7、若g f ?是满射，则g 是满射。 （ F ） 8、若A B ?，则)()(A P B P ?。 （ T ） 9、若R 具有自反性，则1-R 也具有自反性。 （ T ） 10、B A ∈并且B A ?不可以同时成立。 （F ） 四、计算题（共 3 小题，每题 10 分，共30 分） 1、调查260个大学生，获得如下数据：64人选修数学课程，94人选修计算机课程，58人选修商贸课程，28人同时选修数学课程和商贸课程，26人同时选修数学课程和计算机课程，22人同时选修计算机课程和商贸课程，14人同时选修三门课程。问 （１）三门课程都不选的学生有多少？ （２）只选修计算机课程的学生有多少？ 离散数学基本知识 体积和表面积三角形的面积,底×高?2。公式S= a×h?2 正方形的面积,边长×边长公式 S= a2 长方形的面积,长×宽公式S= a×b 平行四边形的面积,底×高公式S= a×h 梯形的面积,(上底+下底)×高?2 公式 S=(a+b)h?2 内角和:三角形的内角 和,180度。 长方体的表面积,(长×宽，长×高，宽×高) ×2 公 式:S=(a×b+a×c+b×c)×2 正方体的表面积,棱长×棱长×6 公式: S=6a2 长方体的体积,长×宽×高公式:V = abh 长方体(或正方体)的体积,底面积×高公式:V = abh 正方体的体积,棱长×棱长×棱长公式:V = a3 圆的周长,直径×π公式:L,πd,2πr 1 圆的面积,半径×半径×π公式:S,πr2 圆柱的表(侧)面积:圆柱的表(侧)面积等于底面的周长乘高。公 式:S=ch=πdh,2πrh 圆柱的表面积:圆柱的表面积等于底面的周长乘高再加上两头的圆的面积。公式:S=ch+2s=ch+2πr2 圆柱的体积:圆柱的体积等于底面积乘高。公式:V=Sh 圆锥的体积,1/3底面×积高。公式:V=1/3Sh 算术 1、加法交换律:两数相加交换加数的位置，和不变。 2、加法结合律:a + b = b + a 3、乘法交换律:a × b = b × a 4、乘法结合律:a × b × c = a ×(b × c) 5、乘法分配律:a × b + a × c = a × b + c 6、除法的性质:a ? b ? c = a ?(b × c) 7、7、除法的性质:在除法里，被除数和除数同时扩大(或缩小)相同的倍数，商不变。 O除以任何不是O的数都得O。简便乘法:被乘数、乘数末尾有O的乘法，可以先把O前面的相乘，零不参加运算，有几个零都落下，添在积的末尾。 8、 8、有余数的除法: 被除数,商×除数+余数方程、代数与等式 2 9、等式:等号左边的数值与等号右边的数值相等的式子叫做等式。等式的基本性质:等式两边同时乘以(或除以)一个相同的数，等式仍然成立。 10、方程式:含有未知数的等式叫方程式。一元一次方程式:含有一个未知数，并且未知数的次数是一次的等式叫做一元一次方程式。学会一元一次方程式的例法及计算。即例出代有χ的算式并计算。 11、代数: 代数就是用字母代替数。代数式:用字母表示的式子叫做代数式。如:3x =ab+c 分数:把单位“1”平均分成若干份，表示这样的一份或几分的数,叫做分数。 分数大小的比较:同分母的分数相比较，分子大的大，分子小的小。异分母的分数相比较，先通分然后再比较;若分子相同，分母大的反而小。 分数的加减法则:同分母的分数相加减，只把分子相加减，分母不变。异分母的分数相加减， 先通分，然后再加减。 分数乘整数，用分数的分子和整数相乘的积作分子，分母不变。 分数乘分数，用分子相乘的积作分子，分母相乘的积作为分母。 3离散数学基本公式
中国石油大学大学《离散数学》期末复习题及答案
离散数学基础试题(二)
大学离散数学期末重点知识点总结(考试专用)
厦门大学离散数学2015-2016期末考试试题答案年
离散数学基础实验教学大纲Word版
离散数学期末试卷A卷及答案
离散数学基本知识