离散数学期末复习指导(专科)
中央电大理工部计算机教研室
离散数学是中央电大计算机应用专业信息管理方向开设的必修统设课.该课程使用新的教学大纲,在原有离散数学课程的基础上削减了教学内容(主要是群与环,格与布尔代数这两章及图论的后三节内容),使所学的知识达到必需,够用,更加适合大学专科层次的教育.目前该课程没有新教材,借用原教材.使用的教材为中央电大出版的《离散数学》(刘叙华等编)和《离散数学学习指导书》(虞恩蔚等编).
离散数学主要研究离散量结构及相互关系,使学生得到良好的数学训练,提高学生抽象思维和逻辑推理能力,为从事计算机的应用提供必要的描述工具和理论基础.其先修课程为:高等数学,线性代数;后续课程为:数据结构,数据库,操作系统,计算机网络等.
课程的主要内容
本课程分为三部分:集合论,数理逻辑和图论.
集合论部分(集合的基本概念和运算,关系及其性质);
数理逻辑部分(命题逻辑,谓词逻辑);
图论部分(图的基本概念,树及其性质).
学习建议
离散数学是理论性较强的学科,学习离散数学的关键是对离散数学(集合论,数理逻辑和图论)有关基本概念的准确掌握,对基本原理及基本运算的运用,并要多做练习.
一,各章复习示例与解析
第一章 集 合
例1,将"大于3而小于或等于7的整数集合"用集合表示出来.
[解析]
集合的表示方法一般有两种,一种称为列举法,一种称为描述法.
列举法将集合的元素按任意顺序逐一列在花括号内,并用逗号分开."大于3而小于或等于7的整数"有4,5,6,7,用列举法表示为{4,5,6,7};
描述法是利用集合中的元素满足某种条件或性质用文字或符号在花括号内竖线后面表示出来.上例用描述法表示为{x| xZ并且3x7},其中Z为整数集合.
答:{4,5,6,7}或{x| xZ并且3x7}.
例2,判定下列各题的正确与错误:
(1)a{{a}};
(2){a}{ a,b,c };
(3){ a,b,c };
(4){ a,b,c };
(5){a,b}{a,b,c,{ a,b,c }};
(6){{a},1,3,4}{{a},3,4,1};
(7){a,b}{a,b,{ a,b }};
(8)如果AB=B,则A=E.
[解析]
此题涉及到集合中子集的概念,集合的包含关系,空集与集合的关系.解题时要注意区分两个集合之间的关系以及集合中元素与集合之间的关系的不同.
集合之间的关系分为包含关系(子集,真子集),相等关系,幂集等,判断时要准确理解这些概念,才能正确地运用这些知识.
集合与它的元素之间的关系有两种:一个元素a属于一个集合A,记为aA;一个元素A不属于一个集合A,记为aA.要注意符号的记法()与集合包含符号记法(,)的不同.
答:正确的是(2),(4),(5),(7);其余的都是错误的.
例3,设A,B是两个集合,A={1,2,3},B={1,2},请计算(A)–(B).
[解析]
集合的概念一般在中学阶段已经学过,这里只多了一个幂集概念,重点对幂集加以掌握,一是掌握幂集的构成,由集合A的所有子集组成的集合,称为A的幂集,记作(A)或2A;一是掌握幂集元数为2n,n为集合A的元数.
集合的基本运算有交,并,差,补.
答:(A)={,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}
(B)={,{1},{2},{1,2}}
于是(A)–(B)={{3},{1,3},{2,3},{1,2,3}}
例4,试证明(A~B)(~AB)=(AB)(~A~B)
[解析]
证明集合恒等式要熟练运用教材15页集合的10个基本运算.一般来说,欲证P=Q,即证PQ并且QP,也就是要证明,对于任意的x,有下式成立.
xP x Q 和 xQ x P
证明集合恒等式的另一种方法是利用已知的恒等式来代入.本题就是用的这个方法.
通过对集合恒等式证明的练习,既可以加深对集合性质的理解与掌握;又可以为第三章命题逻辑中公式的基本等价式的应用打下良好的基础.实际上,本章做题是一种基本功训练,尤其要求学生重视吸收律和重要等价式在A–B=A~B证明中的特殊作用.
证明:

第二章 关系与映射
例1,设集合A={1,2,3,4,5},试求A上的模2同余关系R的关系矩阵和关系图.
[解析]
关系的概念是第二章的基础,又是第一章集合概念的应用.因此应该真正理解并熟练掌握二元关系的概念及关系矩阵,关系图表示.
这道题要把R表示出来,先要清楚"模2同余关系"的概念,如果x,y模2同余,就是指x,y除以2的余数相同.于是,
R={(1,1),(1,3),(1,5),(2,2),(2,4),(3,1),(3,3),(3,5),(4,2),(4,4),(5,1),(5,3),(5,5)}
求出了关系R的表达式,就可以进一步求出关系矩阵和关系图了.
答:R的关系矩阵为:
R的关系图为:
例2,设集合A={1,2,3,,10},A上的关系R={(x,y)|x,yA,且x+y=10},试判断R具有哪几种性质
[解析]
关系的性质既是对关系概念的加深理解与掌握,又是关系的闭包,等价关系,半序关系的基础.对于四种性质(自反性,对称性,反对称性,传递性)的判定,可以依据其定义,也可以依据教材中49页上总结的关于关系矩阵和关系图的规律.
对于传递性的判定,难度稍大一点,这里要提及两点:一是不破坏传递性定义,可认为具有传递性.如空关系具有传递性,同时空关系具有对称性与反对称性,但是不具有自反性.另一点是介绍一种判定传递性的"跟踪法",即若(a1,a2)R,(a2,a3)R,,(ai-1,ai)R,则(a1,ai)R;如若(a,b)R,(b,a)R,则有(a,a)R,且(b,b)R.
先写出R的关系式,R={(1,9),(2,8),(3,7),(4,6),(5,5),(6,4),(7,3),(8,2),(9,1)},并在此基础上判断R是否具有四种关系的性质.
答:R只具有关系的对称性.
例3,设集合,判定下列关系,哪些是自反的,对称的,反对称的和传递的:
解:均不是自反的;R4是对称的;R1,R2,R3,R4,R5是反对称的;R1,R2,R3,R4,R5是传递的.
例4,设集合A={a,b,c,d},R1,R2都是A上的二元关系,R1={(a,b),(b,c),(c,a)},R2=,试求R1和R2的自反闭包,对称闭包和传递闭包.
[解析]
在理解掌握关系闭包概念的基础上,主要掌握闭包的求法.关键是熟记三个定理的结论:定理2,自反闭包;定理3,对称闭包;定理4的推论,传递闭包.
答:r(R1)= R1IA={(a,b),(b,c),(c,a),(a,a),(b,b),(c,c)}
s(R1)= R1 R1-1 ={(a,b),(b,c),(c,a),(b,a),(c,b),(a,c)}
R12 ={(a,c),(b,a),(c,b)}
R13 ={(a,a),(b,b),(c,c)}
t(R1)= R1 R12 R13 ={(a,b),(b,c),(c,a),(a,c),(b,a),(c,b),(a,a),(b,b),(c,c)}
空关系R2的自反闭包,对称闭包和传递闭包均为.
例5,设集合,A上的二元关系R为:

(1)写出R的关系矩阵,画出R的关系图;
(2)证明R是A上的半序关系,画出其哈斯图;
(3)若,且,求B的最大元,最小元,极大元,极小元,最小上界和最大下界.
[解析]
理解与掌握半序关系与半序集概念的关键是哈斯图.哈斯图画法掌握了,对于确定任一子集的最大(小)元,极大(小)元也就容易了.这里要注意,最大(小)元与极大(小)元只能在子集内确定,而上界与下界可在子集之外的全集中确定,最小上界为所有上界中最小者,最小上界再小也不小于子集中的任一元素,可以与某一元素相等,最大下界也同样.
解:(1)R的关系矩阵为
R的关系图为
(2)因为R是自反的,反对称的和传递的,所以R是A上的半序关系.(A,R)为半序集,(A,R)的哈斯图如下:
(3)当B={2,3,4,5},B的极大元为2,4;极小元为2,5;B无最大元与最小元;B也无上界与下界,更无最小上界与最大下界.
例6,下列映射中哪些是满射,哪些是单射,哪些是双射
(1)
(2)
(3)
(4)
[解析]
映射的概念与映射种类的判定:映射的种类主要指单射,满射,双射与非单非满射.判定的方法除定义外,可借助于关系图,而实数集的子集上的映射也可以利用直角坐标系表示进行,尤其是对各种初等函数.
答:(1),(3)是非单非满射;(2)是满射;(4)是双射.
第三章 命题逻辑
例1,试证明公式为恒真公式.
[解析]
判定公式的恒真性,包括判定公式是恒真的或是恒假的.具体方法有两种:
一是真值表法,对于任给一个公式,主要列出该公式的真值表,观察真值表的最后一列是否全为1(或全为0),就可以判定该公式是否恒真(或恒假),若不全为0,则为可满足的.
二是推导法,即利用基本等价式推导出结果为1,或者利用恒真(恒假)判定定理:公式G是恒真的(恒假的)当且仅当等价于它的合取范式(析取范式)中,每个子句(短语)均至少包含一个原子及其否定.
这里要求的析取范式中所含有的每个短语不是极小项,一定要与求主析取范式相区别,对于合取范式也同样.
证明:
证法一:真值表法,见《离散数学学习指导书》60页例6(4)的解答.
证法二 :
G=((PQ)(QR))(PR)
=(PQ)(QR)PR
=(((PQ)(PR)(QQ)(QR))P)R
=((PQP)(PRP)(QRP))R
=(1(QRP))R
=QRPR
=1
故G为恒真公式.
例2,求的主析取范式与主合取范式.
[解析]
求范式,包括求析取范式,合取范式,主析取范式和主合取范式.关键有两点:一是准确理解掌握定义;另一是巧妙使用基本等价式中的分配律,同一律和互补律,结果的前一步适当使用等幂律,使相同的短语(或子句)只保留一个.
另外,由已经得到的主析取(合取)范式,根据原理,参阅《离散数学学习指导书》71页例15,也可以求得主合取(析取)范式.
解:(1)求主析取范式,
[方法1] 利用真值表求解
G
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
0
0
0
0
0
0
1
1
1
0
1
0
1
0
1
1
0
1
0
1
1
1
1
1
因此
[方法2] 推导法
(2)求主合取范式
[方法1] 利用上面的真值表,为0的有两行,它们对应的极大项分别为,因此,

[方法2] 利用已求出的主析取范式求主合取范式,已用去6个极小项,尚有2个极小项,即与,于是,

例3,利用形式演绎法证明 { P(QR),SP,Q}蕴涵SR.
[解析]
利用形式演绎进行逻辑推理时,一是要理解并掌握14个基本蕴涵式,二是会使用三个规则:规则P,规则Q和规则D,需要进行一定的练习.
证明:
(1)SP 规则P
(2)S 规则D
(3)P 规则Q,根据(1),(2)
(4)P(QR) 规则P
(5)QR 规则Q,根据(3),(4)
(6)Q 规则P
(7)R 规则 Q,根据(5),(6)
(8)SR 规则D,根据(2),(7)
第四章 谓词逻辑
例1,在谓词逻辑中将下列命题符号化:
(1)凡正数都大于0;
(2)存在小于3的素数;
(3)没有不能表示成分数的有理数;
(4)参加考试的人未必都能取得好成绩.
[解析]
反复理解谓词与量词引入的意义,概念的含义及在谓词与量词作用下变量的自由性,约束性与改名规则.
解:
(1),其中F(x):x是正数,G(x):x大于0;
(2),其中F(x):x大于3,G(x):x是素数;
(3),其中F(x):x为有理数,G(x):x能表示成分数.
"没有不能表示成分数的有理数"与"所有的有理数都能表示成分数"是同一个命题的不同的叙述方法,因此本命题也可以符号化为.
(4),其中F(x):x是参加考试的人,G(x):x取得好成绩.与(3)类似,本命题可以符号化为.
这个例子中几个命题的符号化均有典型性,请同学们注意分析.
例2,设I是如下一个解释:
F(2) F(3) P(2) P(3) Q(2,2) Q(2,3) Q(3,2) Q(3,3)
3 2 0 1 1 1 0 1
求的真值.
[解析]
将一阶逻辑公式表达式中的量词消除,写成与之等价的公式,然后将解释I中的数值代入公式,求出真值.
解:

例3,试将一阶逻辑公式化成前束范式.
[解析]
在充分理解掌握前束范式概念的基础上,利用改名规则,基本等价式与蕴涵式(一阶逻辑中),将给定公式中量词提到母式之前称为首标.
解:

第五章 图论
例1,在具有n个顶点的完全图Kn中删去多少条边才能得到树
[解析]
本章的概念较多,学习时需要认真比较各概念的含义,如:图,子图,有向图,权图;树,支撑树,二叉树,有向树;路,简单路,回路等,这些都是图的基本概念,今后将在数据结构,数据库,计算机网络等课程中用到.
解:n个顶点的完全图Kn中共有条边,n个顶点的树应有条边,于是,删去的边有:.
例2,求下面有限图中点u到各点间的最短路.(图上数字见教材231页第3题.左侧一列的四个点为u1到u4,右侧一列的四个点为u5到u8)
u v
[解析]
计算权图中的最短路要格执行迪克斯特拉(Dijkstra)算法的骤,从起点起,到每一点求出最短路,然后进行仔细比较,最后到达终点,算出最小权和.
解:uu1, d(u, u1)=1,路(u, u1)
u u2,d(u, u2)=9,路(u, u4, u3, u7, u2)
u u3,d(u, u3)=5,路(u, u4, u3 ,)
u u4,d(u, u4)=3,路(u, u4 )
u u5,d(u, u5)=11,路(u, u1, u5)或路 (u, u4, u3 , u7 , u2 , u5)
u u6,d(u, u6)=13,路(u, u1, u5, u6)
u u7,d(u, u7)=8,路(u, u4 , u3 , u7)
u u8,d(u, u8)=11,路(u, u4, u8)
uv, d(u, v)=15,路(u, u1, u5 , u6 ,v) 或路(u, u4 , u3 , u7 , u6 ,v)
例3,利用克鲁斯卡尔(Kruskal)算法求一棵最优支撑树.
A 3 B 2 C
1 1 2 4
2 D 3 E 3
2 1
F 2 G 2 H
[解析]
权图中的最优支撑树是图中所带权和最小的支撑树,使用克鲁斯卡尔(Kruskal)算法.
解:按照Kruskal给出的在权图中求最优支撑树的算法,可生成下面的最优支撑树:(权和为11)


生成的最优支撑树结果不是唯一的,又如下图(权和为11)也是一种最优支撑树.
例4,一棵树有两个节点度数为2,一个节点度数为3,三个节点度数为4,问它有几个度数为1的节点
解:我们知道一个有限图中,各点的度数总和是边数的2倍;而树中的边数为点数减1.
根据这两点,可知树中各点的度数总和=2(树中点数1),设树叶有x个,
于是,22+3+34+x=2(2+1+3+x-1)
得x=9.
上例可推广为"一棵树有n2个节点度数为2,n3个节点度数为3,…,nk个节点度数为k,问它有几个度数为1的节点 "请同学们思考.
三, 综合练习及参考解答
(一)填空题
1,集合的表示方法有两种: 法和 法.请把"奇整数集合"表示出来{ }.
A,B是两个集合,A={1,2,3,4},B={2,3,5},则B-A= ,(B)(A)= ,(B)的元素个数为 .
设,则从A到B的所有映射是
.
设命题公式,则使公式G为假的解释是 ,
和 .
5,设G是完全二叉树,G有15个点,其中8个叶结点,则G的总度数为
,分枝点数为 .
6,全集E={1,2,3,4,5},A={1,5},B={1,2,3,4},C={2,5}, 求AB=
,(A)(C)= ,
C= .
7,设A和B是任意两个集合,若序偶的第一个元素是A的一个元素,第二个元素是B的一个元素,则所有这样的序偶集合称为集合A和B的 ,
记作AB,即AB= .AB的子集R称为A,B上的 .
8,将几个命题联结起来,形成一个复合命题的逻辑联结词主要有否定, ,
, 和等值.
9,表达式xyL(x,y)中谓词的定义域是{a,b,c},将其中的量词消除,写成与之等价的命题公式为
.
10,一个无向图表示为G=(P,L),其中P是 的集合,L是
的集合,并且要求
.
(二)选择题(选择一个正确答案的代号,填入括号中)
设命题公式,则G是( ).
A.恒真的 B.恒假的 C.可满足的 D.析取范式
2,设集合,A上的关系,则=( ).

3,一个公式在等价意义下,下面哪个写法是唯一的( ).
A.析取范式 B.合取范式 C.主析取范式 D.以上答案都不对
4,设命题公式G=(PQ),H=P(QP),则G与H的关系是( ).
A.GH B.HG C.G=H D.以上都不是
5,已知图G的相邻矩阵为,则G有( ).
A.5点,8边 B. 6点,7边 C. 5点,7边 D. 6点,8边
6,下列命题正确的是( ).
A.{}= B.{}= C.{a}{a,b,c} D.{a,b,c}
7,设集合A={a,b,c},A上的关系R={(a,b),(a,c),(b,a),(b,c),(c,a),(c,b),(c,c)},则R具有关系的( )性质.
A.自反 B.对称 C.传递 D.反对称
8,设R为实数集,映射=RR,(x)= -x2+2x-1,则是( ).
A.单射而非满射 B.满射而非单射 C.双射 D.既不是单射,也不是满射
9,下列语句中,( )是命题.
A.下午有会吗 B.这朵花多好看呀! C.2是常数. D.请把门关上.
10,下面给出的一阶逻辑等价式中,( )是错的.
x(A(x)B(x))=xA(x)xB(x)
AxB(x)=x (AB(x))
x(A(x)B(x))=xA(x)xB(x)
xA(x)=x(A(x))
(三)计算题
1,设R和S是集合上的关系,其中,试求: (1)写出R和S 的关系矩阵;
(2)计算.
设A={a,b,c,d},R1,R2是A上的关系,其中R1={(a,a),(a,b),(b,a),(b,b),(c,c),(c,d),(d,c),(d,d)},R2={(a,b),(b,a),(a,c),(c,a),(b,c),(c,b),(a,a),(b,b),(c,c)}.
画出R1和R2的关系图;
判断它们是否为等价关系,是等价关系的求A中各元素的等价类.
用真值表判断下列公式是恒真 恒假 可满足
(1)(PP)Q
(2)(PQ)Q
(3)((PQ)(QR))(PR)
设解释I为:
定义域D={-2,3,6};
F(x):x3;
G(x):x5.
在解释I下求公式x(F(x)G(x))的真值.
化简下式:
((ABC)(AB))((A(BC))A)
已知A={1,2,3,4,5},B={1,2,3},R是A到B的二元关系,并且R={(x,y)|xA且yB且2 x+y 4},画出R的关系图,并写出关系矩阵.
画出下面偏序集(A,)的哈斯图,并指出集合A的最小元,最大元,极大元和极小元.其中A={a,b,c,d,e},={(a,b),(a,c),(a,d),(a,e),(b,e),(c,e),(d,e)}IA.
求命题公式的析取范式与合取范式.
9,给定解释I如下:
定义域D={2,3};
f(2) f(3) F(2,2) F(2,3) F(3,2) F(3,3)
3 2 0 0 1 1
求.
10,求下面带权图的最优支撑树,并计算它的权.
4 7
8
20 12
8 9 10
15
(四)证明题
1,证明等价式.
利用形式演绎法证明:蕴涵Q.
A,B,C为任意的集合,证明:
利用一阶逻辑的基本等价式,证明:
练习题参考解答
(一)填空题
1,列举;描述;
2,{5};{{5},{2,5},{3,5},{2,3,5}};8
3,1={(a,1),(b,1)};2={(a,2),(b,2)};3={(a,1),(b,2)};4={(a,2),(b,1)}
4,(1,0,1); (1,1,1); (1,0,0)
28; 7
6,{5};{,{5}};{1,3,4}
7,笛卡尔积(或直乘积);{(x,y)|xA且yB};二元关系
8,并且(或合取);或者(或析取);蕴涵
9,(L(a,a)L(a,b)L(a,c))(L(b,a)L(b,b)L(b,c))(L(c,a)L(c,b)L(c,c))
10,点;连接某些不同点对的边;一对不同点之间最多有一条边
(二)选择题(选择一个正确答案的代号,填入括号中)
1,C 2,A 3,C 4,A 5,C
6,A 7,B 8,D 9,C 10,A
(三)计算题
1,解:(1)

(2)={(1,2),(3,4)}
={(1,1),(1,2),(1,3),(2,3),(2,4),
(3,4),(4,4)}
={(1,1),(3,1),(3,2),(4,3)}
={(2,1),(4,3)}
2,解:
R1和R2的关系图如下:
R1的关系图 R2的关系图
由关系图可知,R1是等价关系.R1不同的等价类有两个,即{a,b}和{c,d}.
由于R2不是自反的,所以R2不是等价关系.
3,解 :
真值表
P Q
P PP (PP)Q
0 0
1 0 1
0 1
1 0 0
1 0
0 0 1
1 1
0 0 0
因此公式(1)为可满足.
真值表
P Q
PQ (PQ) (PQ)Q
0 0
1 0 0
0 1
1 0 0
1 0
0 1 0
1 1
1 0 0
因此公式(2)为恒假.
真值表
P Q R
PQ QR PR ((PQ)(QR))(PR)
0 0 0
1 1 1 1
0 0 1
1 1 1 1
0 1 0
1 0 1 1
0 1 1
1 1 1 1
1 0 0
0 1 0 1
1 0 1
0 1 1 1
1 1 0
1 0 0 1
1 1 1
1 1 1 1
因此公式(3)为恒真.
4,解:
x(F(x)G(x))
(F(-2)G(-2))(F(3)G(3))(F(6)G(6))
(10)(10)(01)
1
5,解:
((ABC)(AB))((A(BC))A)
=(AB) A (利用两次吸收律)
=(AB)~ A
=(A~ A)(B~ A)
= (B~ A)
= B A
6,解:
R={(1,1),(1,2),(1,3),(2,1),(2,2),(3,1)}
1 1

2 2

3 3
4
5
R的关系图为
关系矩阵
7,解:
(A,)的哈斯图为:
e
b c d
a

a为A的极小元,也是最小元;
e为A的极大元,也是最大元.
8,解:
(PQ)(PQ)
((PQ)(PQ))((PQ)(PQ))
((PQ)(PQ))((PQ)(PQ)))
(PQ)(PQ)
上面结果为合取范式.
利用对分配得:(PQ)(PQ)
(PP)(PQ)(QP)(QQ)
(PQ)(QP)
上面结果为析取范式.
9,解:
xy(F(x,y)F(f(x),f(y)))
x((F(x,2)F(f(x),f(2)))(F(x,3)F(f(x),f(3))))
(F(2,2)F(f(2),f(2)))(F(2,3)F(f(2),f(3)))(F(3,2)F(f(3),f(2)))(F(3,3)F(f(3),f(3)))
(01)(01)(10)(10)
0
10,解: 带权图的最优支撑树如下,权和为28.
4 7
8 9
(四)证明题
证明:

2,证明:
(1) 规则P
(2) 规则P
(3) 规则Q,根据(1),(2)和基本蕴涵式(12)
(4) 规则P
(5) 规则Q,根据(3),(4)和基本蕴涵式(11)
(6) 规则P
(7) 规则Q,根据(5),(6)和基本蕴涵式(12)
(8) 规则P
(9) 规则Q,根据(7),(8)和基本蕴涵式(10)
3,证明:
(AB)C=(A~B)~C
= A(~B~C)
= A~(BC)
= A(BC)
4,证明:
xy(F(x)G(y))=x(F(x)y G(y))
= x(F(x)y G(y))
= x(F(x))y G(y)
= xF(x)y G(y)
= xF(x)yG(y)
4
1
3
2
5