资源描述：
《电大《离散数学》期末综合复习资料小抄》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、电大《离散数学》期末综合复习资料小抄一、判断题1.（）命题联结词{Ø，Ù，Ú}是最小联结词组。2.（）（PÙQ）ÙØP为矛盾式。3.（）（（ØPÚQ）Ù（Q®R））®（P®R）为重言式。4.（）A、B、C是任意命题公式，如果AÚCÛBÚC，一定有AÛB。5.（）若集合A上的二元关系R是对称的，RC一定是对称的。6.（）R是A上的二元关系，R是自反的，当且仅当r(R)=R。7.（）集合A上的等价关系确定了A的一个划分。8.（）有理数集是可数的。9.（）若函数f，g为入射则其复合函数也为入射。10.（）R是集合A上的关系，R有传递性的充要条件是RoRÍR。11.（）设是一个代数系统，
2、且集合A中元素的个数大于1。如果该代数系统中存在幺元e和零元q，则e¹q。12.（）交换群必是循环群。13.（）一个群可以有多个等幂元。14.（）模格一定是分配格。15.（）每个有向图中，结点入度数总和等于结点出度总和。16.（）图G的邻接矩阵A，Al中的i行j列表示结点vi到vj长度为l路的数目。17.（）任何图中必有偶数个度数为奇数的结点。18.（）有向图中，它的每一个结点位于且只位于一个单侧分图中。19.（）任意平面图最多是四色的。20.（）不存在既有欧拉回路又有汉密尔顿回路的图。二、填空题1．设P：“天下雨”，Q：“他骑自行车上班”，R：“他乘公共汽车上班”。则命题“除非下雨，否则
3、他就骑自行车上班”可符号化为。“他或者骑自行车，或者乘公共汽车上班”可符号化为2．设N(x)：x是自然数；J(x)：x是奇数；Q(x)：x是偶数，用谓词公式符号化命题“任何自然数不是偶数就是奇数”。3．设P(x)：x是运动员，Q(x)：x是教练。则命题“不是所有运动员都是教练”可符号化为。4．设D={a,b}；P(a,a)=P(b,b)=T；P(a,b)=P(b,a)=F。则公式("x)($y)(P(x,y)®P(y,x))的真值是。5．集合A={Æ,{Æ}}的幂集P(A)为6．集合A={1,2}，B={a,b,c,d}，C={c,d,e}，则A´(B-C)为7．试用空集Æ构成集合A（A¹
4、Æ）=和B=，使得AÎB且AÍB都成立。并且A´B=。8．设A={1,2,3}，R={<1,2>,<2,1>,<1,3>,<1,1>}，传递闭包t(R)为。9．设A={1,2,3}，B={x,y}，f：A®B，则不同的函数个数为个。10．Q为有理数集，Q上定义运算*为a*b=a+b-ab，则的幺元为。11．代数系统，其中Sk={x
5、xÎZÙx>=K}，+为普通加法，则是一个半群的必要条件是。12．设G为v个结点e条边的连通平面图，则面r等于。13．一棵树有n2个结点度数为2，n3个结点度数为3，……，nk个结点度数为k，则度数为1的结点的个数为。14．设T
6、为根树，若每个结点的出度都小于等于m，则T称为树，若除外，每个结点的出度都等于m，则T称为完全m叉树。51．设是偏序集，如果A中任意两个元素都有和，则称为格。三、解答题1.将公式((P®Q)Ù(Q®R))®(P®R)化成与之等价且仅含{Ø、Ú、Ù}的公式。2.将下列命题符号化：（1）他虽聪明但不用功。（2）除非你努力否则你将失败。（3）我们不能既划船又跑步（4）仅当你走我才留下。3.用谓词表达式符号化下列命题：（1）所有老的国家选手都是运动员。（2）某些教练是年老的，但是健壮的。（3）任何自然数不是偶数就是奇数。（4）不是所有运动员都是教练。4.求命题公式Ø(P®Q)的
7、主合取范式。5.求命题公式PÙ(P®Q)的主析取范式。6.设集合A＝{1,2,3}，A上的关系R＝{<1,1>,<1,2>,<2,2>,<3,2>,<3,3>},（1）画出R的关系图；（2）写出R的关系矩阵；（2）问R具有关系的哪几种性质(自反、反自反、对称、反对称、传递)。7.构造一非空偏序集，它存在一子集有上界，但没有最小上界。它还有一子集，存在最大下界但没有最小元。8.以下哪些是函数？哪些是入射？哪些是满射？对任意一个双射，写出它们的逆函数。a)f:Z®N,f(x)=x2+1b)f:N®Q,f(x)=1/xc)f:{1,2,3}®{a,b,c},f={<1,b>,<2,c>,<3,a
8、>}d)f:N®N,f(x)=2xe)f:R´R®R´R,f(x,y)=9.设S={1,2,3,4,6,12}，D为S上的整除关系，（1）试写出该关系并画出哈斯图；（2）设子集B={2,3,6}，试求B的最大元、最小元、极大元和极小元；（3）试求B的上界、上确界、下界和下确界。10.设集合A有m个元素，B有n个元素，则A到B的关系有多少个？A到B的函数有多少个？11.判定下列代数系统是否为群，请说明原因
