离散数学复习题参考带答案

1、一、选择题：（每题2）1、下列语句中不是命题的有（ ）。A离散数学是计算机专业的一门必修课。B鸡有三只脚。C太阳系以外的星球上有生物。D你打算考硕士研究生吗?2、命题公式A与B是等价的，是指（ ）。A A与B有相同的原子变元 B A与B都是可满足的C 当A的真值为真时，B的真值也为真D A与B有相同的真值3、所有使命题公式P(Q¬R)为真的赋值为（ ）。A 010，100，101，110，111B 010，100，101，111C 全体赋值D 不存在4、合式公式Ø(PQ)®R的主析取范式中含极小项的个数为（ ）。A2B3C5D0 5、一个公式在等价意义下，下面哪个

2、写法是唯一的（ ）。A析取范式 B合取范式 C主析取范式 D以上答案都不对6、下述公式中是重言式的有（ ）。A(PQ) ® (PQ)B(P«Q) « ( P®Q)(Q®P)CØ(P ®Q)QDP ®(PQ)7、命题公式 (ØP®Q) ®(ØQP) 中极小项的个数为（ ），成真赋值的个数为（ ）。A0B1C2D3 8、若公式 (PQ)(ØPR) 的主析取范式为 m001m011m110m111 则它的主合取范式为（ ）。Am001m011m110m111BM000M0

3、10M100M101CM001M011M110M111Dm000m010m100m1019、下列公式中正确的等价式是（ ）。AØ($x)A(x) Û ($x)ØA(x)B("x) ("y)A(x, y) Û ($y) ("x) A(x, y)CØ("x)A(x) Û ($x)ØA(x)D("x) (A(x) B(x) Û ("x) A(x) ("x) B(x)10、下列等价关系正确的是（ ）。A"x ( P(x) Q(x) ) 

4、9; "x P(x) "x Q(x)B$x ( P(x) Q(x) ) Û $x P(x) $x Q(x)C"x ( P(x) ®Q ) Û "x P(x) ® QD$x ( P(x) ®Q ) Û $x P(x) ® Q11、设个体域为整数集，下列真值为真的公式是（）。A"x$y（x·y=1）B$x"y（x·y=0）C"x"y（x·y=y）D$x"y（x+y=2y）12、设S=Æ,1,1,2，则

5、有（ ）ÍS。A1,2 B1,2 C1 D2 13、下列是真命题的有（ ）。AaÍa BÆÎÆ,ÆCÆÎÆ,Æ DÆÎÆ,Æ 14、设S=Æ,1,1,2，则2S 有（ ）个元素。A3B6 C7D8 15、已知幂集的基数|r( A)|=2048，则集合A的基数|A|为（ ）。A11B12C10D916、设A=1，2，3，则A上的二元关系有（ ）个。A 23 B 32 C23´3D32´217、设A=a, b, c, d，A上的等

6、价关系R=<a, b>,<b, a>,<c, d>,<d, c>IA，则对应于R的A的划分是（ ）。Aa, b, c, d Ba, b, c, dCa, b, c, d Da, b, c, d18、设R，S是集合A上的关系，则下列说法正确的是（ ）。A若R、S是自反的，则R°S是自反的B若R、S是反自反的，则R°S是反自反的C若R、S是对称的，则R°S是对称的D若R、S是传递的，则R°S是传递的19、集合A上的相容关系R的关系矩阵M(R)的对角线元素（ ）。A全是1B全是0C有的是1，有的是0D有的是220

7、、设集合 A=1，2，3，A上的关系R=<1,1>，<1,2>，<2,2>，<3,3>，<3,2>，则R不具备（ ）。A 自反性B 传递性C 对称性D 反对称性21、设，S上关系R的关系图为（如图所示），则R具有（ ）性质。A自反性、对称性、传递性 B反自反性、反对称性 C反自反性、反对称性、传递性 D自反性 22、设S=1，2，3，R为S上的关系，其关系图为 则R具有（ ）的性质。A自反、对称、传递 B什么性质也没有 C反自反、反对称、传递 D自反、对称、反对称、传递23、设A=1, 2, 3，B=a, b，下列各二元关系中是A到B

8、的函数的是（ ）。AR=<1,a>,<2,a>,<3,a>BR=<1,a>,<2,a>,<2,b>,<3,a>CR=<1,a>,<2,b>DR=<2,a>,<2,b>24、设R为实数集，映射f：R®R，f(x)= -x2+2x-1，则f是（ ）。A单射而非满射 B满射而非单射C双射 D既不是单射，也不是满射25、设A=F，1，1，3，1，2，3则A上包含关系“Í”的哈斯图为（ ）。 AB CD26、N是自然数集合，定义f：N®N，f

9、(x) = x mod 3（即x除以3的余数），则 f 是（ ）。A满射不是单射B单射不是满射C双射D不是单射也不是满射27、设S=Æ,1,1,2，则有（ ）ÍS。A1,2 B1,2 C1 D2 28、集合A=x | x=2nnÎN 对（ ）运算封闭。A加法B减法C乘法D|xy|29、设*是集合A上的二元运算，称Z是A上关于运算*的零元，若（ ）。A"x ÎA，有x*Z=Z*x=ZBZ ÎA，且"x ÎA有x*Z=Z*x=ZCZ ÎA，且"x ÎA有x*Z=Z*x=xDZ Î

10、A，且$x ÎA有x*Z=Z*x=Z30、下面偏序集（ ）能构成格。31、在（ ）中，补元是唯一的。A有界格B有补格 C分配格D有补分配格。32、下面四组数能构成无向简单图的度数序列的有（ ）。A(2, 2, 2, 2, 2)B(1, 1, 2, 2, 3) C(1, 1, 2, 2, 2)D(1, 1, 3, 3, 3)33、无向图结点之间的连通性，是结点集之间的一个（ ）。A 连通关系B 偏序关系C 等价关系D 函数关系34、已知图G的相邻矩阵为：则G有（ ）。A5点，8边B6点，7边C5点，7边D6点，8边35、下列四组数为结点度序列，能构成无向图的是（ ）。A2, 3, 4,

11、 5, 6, 7B1, 2, 2, 3, 4C2, 1, 1, 1, 2 D3, 3, 5, 6, 036、下列几个图是简单图的有（ ）。AG1=(V1,E1)，其中 V1=a, b, c, d, e，E1=(a,b), (b,e), (e,b), (a,e), (d,e)BG2=(V2,E2)，其中V2=V1，E2=<a,b>, <b,c>, <c,a>, <a,d>, <d,a>, <d,e>CG3=(V3,E3)，其中V3=V1，E3=(a,b), (b,e), (e,d), (c,c)DG4=(V4,E4)，其中V

12、4=V1，E4=<a,a>, <a,b>, <b,c>, <e,c>, <e,d>37、在一棵树中有7片树叶，3个3度结点，其余都是4度结点则该树有（ ）个4度结点。A1B2C3D4 38、一棵树有2个4度结点，3个3数度结点，其余是树叶，则该树中树叶的个数是（ ）。A8B9C10D1139、设图G是有6个顶点的连通图，总度数为20，则从G中删去（ ）边后使之变成树。A10B 5C 3D 240、下面那一个图可一笔画出（ ）。41、在如下各图中（ ）欧拉图。42、下图中既不是欧拉图，也不是哈密尔顿图的是（ ）。43、在如下的有向图中，

13、从V1到V4长度为3 的道路有（ ）条。A1B2C3D4 44、图 中 从v1到v3长度为3 的通路有（ ）条。A0B1C2D3二、判断题（每题 1分）1。 （ Y ）2设A，B， C是任意三个集合。（1）若AÎB且BÍC，则AÎC。 （ Y ） （2）若AÍB且BÎC，则AÎC。（ N ）（3）若AÎB且BËC，则AÏC。 （ N ） （4）(AÅB)C=(A×C) Å (B×C)。（ Y ）（5）AÅ(BÅC)= (AB)Å(AC)

14、。 （ N ）3A，B，C为任意集合，若AB=AC，则B = C 。（ N ）4可能有某种关系，既不是自反的，也不是反自反的。（ Y ）5可能有某种关系，既是对称的，又是反对称的。（ Y ）6设R是实数集，R上的关系S=<x, y>|x-y|2x,yÎR，S是相容关系。（ Y ）7若集合A上的关系R是对称的，则Rc也是对称的。（ Y ）8数集合上的不等关系（）可确定A的一个划分（ N ）9设集合A、B、C为任意集合，若A×B = A×C，则B = C。（ N ）10函数的复合运算“ ° ”满足结合律。（ Y ）11集合A上的恒等关系是一个双射

15、函数。（ Y ）12任何一个循环群必定是阿贝尔群。（ Y ）13任何循环群必定是阿贝尔群，反之亦真。（ N ）14设< A， >是偏序集，BÍA，则B的极大元bÎB且唯一。（ N ）15群是每个元素都有逆元的半群。（ N ）16在代数系统< S , *> 中，若一个元素的逆元是唯一的，其运算*必是可结合的。（ N ）17每一个有限整环一定是域，反之也对。（ N ）18设<A,>是布尔代数，则<A,>一定为有补分配格。（ Y ）19若平面图共有v个结点，e条边和r个面，则v e + r = 2。（ N ）20任何有向图中各结点入

16、度之和等于边数。（ Y ）21若两图结点数相同，边数相等，度数相同的结点数目相等，则两图是同构的。（ N ）22一个图是平面图，当且仅当它包含与3,3或5在度结点内同构的子图。（ N ）23有割点的连通图可能是哈密尔顿图。（ N ）24无多重边的图是简单图。（ N ）25根树中最长路径的端点都是叶子。（ N ）26在完全二叉树中，若有片叶子，则边的总数 e =2 t1 。（ N ）27群中可以有零元（对阶数大于1的群）。 （ N ）28任何循环群必定是阿贝尔群，反之亦真。 （ N ）29每一个链都是分配格。 （ Y ）30不可能有偶数个结点，奇数条边的欧拉图。 （ N ）31集合A上的恒等关系

17、是一个双射函数。 （ Y ）32设Q为有理数集，Q上运算 * 定义为，则是半群。（ Y ）33在完全二元树中，若有片叶子，则边的总数 。 （ N ）34能一笔画出的图不一定是欧拉图。 （ Y ）35根树中最长路径的端点都是叶子。 （ N ）36命题公式(A(A®B)®B是一个矛盾式。 （ N ）37设R是实数集，R上的关系F=<x,y>| |x-y|<2x,yÎR ，则F是相容关系。（ Y ）38设< A，>是偏序集，BÍA，则B的极大元bÎB且唯一。 （ N ）39无多重边的图是简单图。 （ N ）40谓词公式$

18、xP(x) ®"xQ(x)$yR(y)的前束范式是"x"z$y(P(x)®Q(z)R(y)。（ Y ）三、解答题（本题分4小题，共计35分）1、试求的主析取范式。2、用真值表判断下列公式是永真式？永假式？可满足式？（1）(PØP)«Q（2）Ø(P®Q) Q（3）(P®Q)(Q®R)®(P®R)解：（1）真值表：P QØP PØP (PØP)«Q0 01 0 10 11 0 01 00 0 11 10 0 0 因此公式（1）为可

19、满足。 （2）真值表P QP®Q Ø（P®Q） Ø(P®Q)Q0 01 0 00 11 0 01 00 1 01 11 0 0 因此公式（2）为永假式。 （3）真值表P Q RP®Q Q®R P®R （P®Q）（Q®R）®（P®R）0 0 01 1 1 10 0 11 1 1 10 1 01 0 1 10 1 11 1 1 11 0 00 1 0 11 0 10 1 1 11 1 01 0 0 11 1 11 1 1 1 因此公式（3）为永真式。3、设个体域是D=2，3，6，

20、F(x):x3，G(x):x>5，消去公式"x(F(x)$yG(y)中的量词，并讨论其真值。解："x(F(x)$yG(y)Û "x(F(x)$yG(y)Û (F(2)F(3)F(6)(G(2)G(3)G(6)Û FT ÛF4、求下列公式的前束范式： (1) "xF(x)$xG(x) (2) ("xF(x,y)$yG(y)"xH(x,y)5、通过求主析取范式判断下列命题公式是否等值：(PQ)(ØPQR) 与(P(QR)(Q(ØPR)。解：(PQ)(ØPQR)&#

21、219; (PQ(ØRR)(ØPQR)Û (PQØR)(PQR)(ØPQR)Û M1M0M4Û M0M1M4 Û(0,1,4)Û (2,3,5,6,7) (P(QR)(Q(ØPR)Û (PQ)(PR)(ØPQ)(QR)Û (PQR)(PQØR)(PQR)(PØQR)(ØPQR)(ØPQØR)(PQR) (ØPQR)Û (PQR)(PQØR)(PØQR)(ØPQR)(&

22、#216;PQØR)Û m7m6m5m3m2Û (2,3,5,6,7) 由此可见 (PQ)(ØPQR) Û (P(QR)(Q(ØPR)6、设个体域为D=-2,3,6，谓词，求谓词公式的真值： 7、若集合A=a,b,c的幂集为r(A)，集合B=Æ,Æ的幂集为r(B)，求：r(A) År(B)。解：r(A)= Æ,a,b,c,a,b,c r(B)=Æ,Æ,Æ, Æ,Æ r(A) År(B)= a,b,c,a,b,c,Æ,Æ

23、;, Æ,Æ 8、设集合A=2, 3, 4, 6, 8, 12, 24，R为A上的整除关系， (1) 画出偏序集<A, R>的哈斯图；(2) 写出集合A中的最大元、最小元、极大元、极小元；(3) 写出A的子集B=2, 3, 6, 12的上界、下界、最小上界、最大下界。9、集合S=1，2，3，4，5，找出S上的等价关系，此关系能产生划分1，2，3，4，5，并画出关系图。 10、已知Aa，b，c，d ，A上的关系R定义为：R<a, b>，<b, a>，<a, c>，<b, d>，<d, a>，求：r(R)，

24、s(R)，t(R)。11、已知A1，2，3，4，5，A上的关系R定义为：R<1,2>，<2,1>，<1,3>，<2,4>，<4,1>，<5,5>，<5,3>，<5,4>，求：r(R)，s(R)，t(R)。12、集合上的关系R=<1,1>, <1,3>, <2,2>, <3,3>, <3,1>, <3,4>,<4,3>, <4,4>，写出关系矩阵MR，画出关系图并讨论关系R的性质。13、设集合A=2, 3,

25、 4, 6, 8, 12, 24，R为A上的整除关系，画出偏序集<A, R>的哈斯图。14、已知G=1,2,3,4,5,6，×7为模7乘法。试说明<G, ×7>是否构成群？是否为循环群？若是，生成元是什么？15、一棵树T中，有3个2度结点，一个3度结点，其余结点都是树叶。（1）T中有几个结点；（2）画出具有上述度数的所有非同构的无向图。16、设A=1，2，3，4，5，A上的偏序关系如右图所示，求：A的子集3，4，5和1，2，3的上界，下界，上确界和下确界。17、求图中A到其余各顶点的最短路径，并写出它们的权。18、设带权无向图如下，求其最小生成树T及

26、该树的总权值。19、权数1，4，9，16，25，36，49，64，81，100构造一棵最优二叉树。20、如下图所示的赋权图表示某七个城市v1, v2, , v7及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。四、写出对应下面推理的证明：（本题10分，1*10=10）1、(A®B)(C®D)，B®E，D®F，(EF)，A®CÞA2、PW®R，R®ST，S®T，TQÞW3、如果小张和小王去看电影，则小李也去看电影；小赵不去看电影或小张去看电影；小王

27、去看电影。所以，当小赵去看电影时，小李也去看电影。 4、如果小张去看电影，则当小王去看电影时，小李也去。小赵不去看电影或小张去看电影。小王去看电影。所以当小赵去看电影时，小李也去。5、如果我学习（P），那么我数学不会不及格。如果我不热衷于玩扑克（R），那么我将学习。但我数学不及格（Q）。因此我热衷于玩扑克。（注：请按括号中提示的字母翻译并进行论证。）6、或者是天晴，或者是下雨。如果是天晴，我去看电影。如果我去看电影，我就不看书。所以，如果我在看书，则天在下雨。7、所有牛都有角，有些动物是牛；所以，有些动物有角。（P(x)：x是牛；Q(x)：x有角；R(x)：x是动物）8、每个喜欢步行的人都不喜

28、欢坐汽车；每个人或者喜欢坐汽车或者喜欢骑自行车；有的人不喜欢骑自行车。因而有的人不喜欢步行。（先将推理在一阶逻辑中符号化，随后验证其正确性）五、解答题（本题10分，1*10=10）1、某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。而6个会打网球的人都会打另外一种球（指篮球或排球），求不会打这三种球的人数。2、120名学生参加考试，这次考试有A、B和C共3道题，考试结果如下：12名学生3道题都做对了；20名学生做对A和B；16名学生做对A和C；28名学生做对B和C；做对A题的有48名学生；做对B题的有56名学生；还有16名学生

29、一道题也没做对。试求做对了C题的学生有多少名。3、已知100个学生中有32人学数学，20人学物理，45人学生物，15人学数学和生物，7人学数学和物理，10学物理和生物，30人这三门课一门也没学。问三门课程全部都学的学生人数是多少？ 4、设A=a,b,c，求A上所有的等价关系。5、给定权1，4，9，16，25，36，49，64，81，100；构造一棵最优二叉树。6、画出哈斯图：设Ba,b,c，R=<s1,s2>|s1Ís2Ùs1,s2ÎP(B)7、偏序集的关系图如下图所示，(1) 画出的哈斯图；(2) 设B=b,c，求B的所有上界、上确界，下界和下确界。8、给