离散数学复习题参考带

一、选择题：（每题2’）1、以下语句中不是命题的有（

）。A．失散数学是计算机专业的一门必修课。

B．鸡有三只脚。C．太阳系之外的星球上有生物

。

D．你打算考硕士研究生吗2、命题公式

A与

B是等价的，是指（

）。A．A与B有同样的原子变元C．当A的真值为真时，B的真值也为真

D．

B．A与

A与B都是可知足的B有同样的真值3、所有使命题公式

P∨(Q∧R)为真的赋值为（

）。A．010，100，101，110，111C．全体赋值

B．D．

010，100，101，111不存在4、合式公式(P∧Q)R的主析取范式中含极小项的个数为（）。A．2B．3C．5D．05、一个公式在等价意义下，下边哪个写法是独一的（）。A．析取范式B．合取范式C．主析取范式D．以上答案都不对6、下述公式中是重言式的有（）。A．(P∧Q)(P∨Q)B．(PQ)((PQ)∧(QP))C．(PQ)∧QD．P(P∧Q)7、命题公式(PQ)(Q∨P)中极小项的个数为（），成真赋值的个数为（）。A．0B．1C．2D．38、若公式(P∧Q)∨(P∧R)的主析取范式为m001∨m011∨m110∨m111则它的主合取范式为（）。A．m001∧m011∧m110∧m111B．M∧M∧M100∧M101000010C．M001∧M011∧M∧M111D．m000∧m010∧m100∧m1011109、以下公式中正确的等价式是（）。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))xP(x)∨xQ(x)B．x(P(x)∨Q(x))xP(x)∨xQ(x)C．x(P(x)Q)xP(x)QD．x(P(x)Q)xP(x)Q11、设个体域为整数集，以下真值为真的公式是（）。A．xy（x·y=1）B．xy（x·y=0）C．xy（x·y=y）D．xy（x+y=2y）12、设S={,{1},{1,2}}，则有（）S。A．{{1,2}}B．{1,2}C．{1}D．{2}13、以下是真命题的有（）。A．{a}{{a}}B．{{}}{,{}}C．{,{}}D．{}{,{}}S）个元素。14、设S={,{1},{1,2}}，则2有（A．3B．6C．7D．815、已知幂集的基数|(A)|=2048，则会合A的基数|A|为（）。A．11B．12C．10D．916、设A={1，2，3}，则A上的二元关系有（）个。323322A．2B．3C．2D．317、设A={a,b,c,d}，A上的等价关系R={<a,b>,<b,a>,<c,d>,<d,c>}∪I，则对应于R的A的区分是（）。AA．{{a},{b,c},{d}}B．{{a,b},{c},{d}}C．{{a},{b},{c},{d}}D．{{a,b},{c,d}}18、设R，S是会合A上的关系，则以下说法正确的选项是（）。A．若R、S是自反的，则RS是自反的B．若R、S是反自反的，则RS是反自反的C．若R、S是对称的，则RS是对称的D．若R、S是传达的，则RS是传达的19、会合A上的相容关系R的关系矩阵M(R)的对角线元素（）。A．所有是1B．所有是0C．有的是1，有的是0D．有的是220、设会合A={1，2，3}，A上的关系R={<1,1>，<1,2>，<2,2>，<3,3>，<3,2>}，则R不具备（）。A．自反性B．传达性C．对称性D．反对称性21、设S{1,2,3}，S上关系R的关系图为（以下图），则R拥有（A．自反性、对称性、传达性C．反自反性、反对称性、传达性

）性质。B．反自反性、反对称性D．自反性22、设S={1，2，3}，R为S上的关系，其关系图为则R拥有（）的性质。A．自反、对称、传达B．什么性质也没有C．反自反、反对称、传达D．自反、对称、反对称、传达23、设A={1,2,3}，B={a,b}，以下各二元关系中是A到B的函数的是（）。A．R={<1,a>,<2,a>,<3,a>}B．R={<1,a>,<2,a>,<2,b>,<3,a>}C．R={<1,a>,<2,b>}D．R={<2,a>,<2,b>}24、设R为实数集，映照f：RR，f(x)=-x2+2x-1，则f是（）。A．单射而非满射B．满射而非单射C．双射D．既不是单射，也不是满射25、设A={，{1}，{1，3}，{1，2，3}}则A上包括关系“”的哈斯图为（）。A．B．C．D．26、N是自然数会合，定义f：NN，f(x)=xmod3（即x除以3的余数），则f是（）。A．满射不是单射B．单射不是满射C．双射D．不是单射也不是满射27、设S={,{1},{1,2}}，则有（）S。A．{{1,2}}B．{1,2}C．{1}D．{2}28、会合A={x|x=2n∧nN}对（）运算关闭。A．加法B．减法C．乘法D．|x－y|29、设*是会合A上的二元运算，称Z是A上对于运算*的零元，若（）。A．xA，有x*Z=Z*x=ZB．ZA，且xA有x*Z=Z*x=ZC．ZA，且xA有x*Z=Z*x=xD．ZA，且xA有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有（）。A．5点，8边B．6点，7边C．5点，7边D．6点，8边35、以下四组数为结点度序列，能组成无向图的是（）。A．2,3,4,5,6,7B．1,2,2,3,4C．2,1,1,1,2D．3,3,5,6,036、以下几个图是简单图的有（）。A．G1=(V1,E1)，此中V1={a,b,c,d,e}，E1={(a,b),(b,e),(e,b),(a,e),(d,e)}B．G2=(V2,E2)，此中V2=V1，E2={<a,b>,<b,c>,<c,a>,<a,d>,<d,a>,<d,e>}C．G=(V,E)，此中V=V，E={(a,b),(b,e),(e,d),(c,c)}333313D．G=(V,E)，此中V=V，E={<a,a>,<a,b>,<b,c>,<e,c>,<e,d>}44441437、在一棵树中有7片树叶，3个3度结点，其他都是4度结点则该树有（）个4度结点。A．1B．2C．3D．438、一棵树有2个4度结点，3个3数度结点，其他是树叶，则该树中树叶的个数是（）。A．8B．9C．10D．1139、设图G是有6个极点的连通图，总度数为20，则从G中删去（）边后使之变为树。A．10B．5C．3D．240、下边那一个图可一笔划出（）。41、在以下各图中（）欧拉图。42、以下图中既不是欧拉图，也不是哈密尔顿图的是（）。43、在以下的有向图中，从

V1到

V4长度为

3的道路有（

）条。A．1B．2C．3D．444、图中从v到v长度为3的通路有（）条。13A．0B．1C．2D．3二、判断题（每题1分）1．x(A(x)B(x))xA(x)xB(x)。（Y）2．设A，B，C是随意三个会合。（1）若AB且BC，则AC。（Y）（2）若AB且BC，则AC。（N）（3）若AB且BC，则AC。（N）（4）(AB)C=(A×C)(B×C)。（Y）（5）A∪(BC)=(A∪B)(A∪C)。（N）3．A，B，C为随意会合，若A∪B=A∪C，则B=C。（N）4．可能有某种关系，既不是自反的，也不是反自反的。（Y）5．可能有某种关系，既是对称的，又是反对称的。（Y）6．设R是实数集，R上的关系S={<x,y>||x-y|＜2∧x,yR}，S是相容关系。（Y）c也是对称的。（Y）7．若会合A上的关系R是对称的，则R8．数会合上的不等关系（≠）可确立A的一个区分（N）9．设会合A、B、C为随意会合，若A×B=A，×C则B=C。（N）10．函数的复合运算“”知足联合律。（Y）11．会合A上的恒等关系是一个双射函数。（Y）12．任何一个循环群必然是阿贝尔群。（Y）13．任何循环群必然是阿贝尔群，反之亦真。（N）14．设<A，≤>是偏序集，BA，则B的极大元bB且独一。（N）15．群是每个元素都有逆元的半群。（N）16．在代数系统<S,>中，若一个元素的逆元是独一的，其运算必是可联合的。（N）17．每一个有限整环必定是域，反之也对。（N）18．设<A,∧,∨>是布尔代数，则<A,∧,∨>必定为有补分派格。（Y）19．若平面图共有v个结点，e条边和r个面，则v–e+r=2。（N）20．任何有向图中各结点入度之和等于边数。（Y）21．若两图结点数同样，边数相等，度数同样的结点数量相等，则两图是同构的。（N）22．一个图是平面图，当且仅当它包括与Ｋ3,3或Ｋ5在２度结点内同构的子图。（N）23．有割点的连通图可能是哈密尔顿图。（N）24．无多重边的图是简单图。（N）25．根树中最长路径的端点都是叶子。（N）26．在完整二叉树中，如有t片叶子，则边的总数e=2t－1。（N）27．群中能够有零元（对阶数大于1的群）。（N）28．任何循环群必然是阿贝尔群，反之亦真。（N）29．每一个链都是分派格。（Y）30．不行能有偶数个结点，奇数条边的欧拉图。（N）31．会合A上的恒等关系是一个双射函数。（Y）32．设Q为有理数集，Q上运算*定义为abmax(a,b)，则Q，是半群。（Y）33．在完整二元树中，如有t片叶子，则边的总数e2t1。（N）34．能一笔划出的图不必定是欧拉图。（Y）35．根树中最长路径的端点都是叶子。（N）36．命题公式(A∧(AB))B是一个矛盾式。（N）37．设R是实数集，R上的关系F={<x,y>||x-y|<2∧x,yR}，则F是相容关系。（Y）38．设<A，≤>是偏序集，BA，则B的极大元bB且独一。（N）39．无多重边的图是简单图。（N）40．谓词公式xP(x)xQ(x)∨yR(y)的前束范式是xzy(P(x)Q(z)∨R(y))。（Y）三、解答题（此题分4小题，合计35分）1、试求P((PQ)(QP))的主析取范式。2、用真值表判断以下公式是永真式永假式可知足式（1）(P∧P)Q（2）(PQ)∧Q（3）((PQ)∧(QR))(PR)解：（1）真值表：PQPP∧P(P∧P)Q00101011001000111000所以公式（1）为可知足。（2）真值表PQPQ（PQ）(PQ)∧Q00100011001001011100所以公式（2）为永假式。（3）真值表PQRPQQRPR（（PQ）∧（QR））（PR）00011110011111010101101111111000101101011111010011111111所以公式（3）为永真式。3、设个体域是D={2，3，6}，F(x):x，≤3G(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))F∧TF4、求以下公式的前束范式：(1)xF(x)∧﹁xG(x)(2)(xF(x,y)→yG(y))→xH(x,y)5、经过求主析取范式判断以下命题公式能否等值：(P∨Q)∧(P∨Q∨R)与(P∧(Q∨R))∨(Q∧(P∨R))。解：(P∨Q)∧(P∨Q∨R)(P∨Q∨(R∧R))∧(P∨Q∨R)(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)M∧M∧M?M∧M∧M∏(0,1,4)∑(2,3,5,6,7)104014(P∧(Q∨R))∨(Q∧(P∨R))(P∧Q)∨(P∧R)∨(P∧Q)∨(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)m7∨m6∨m5∨m3∨m2∑(2,3,5,6,7)因而可知(P∨Q)∧(P∨Q∨R)(P∧(Q∨R))∨(Q∧(P∨R))6、设个体域为

D={-2,3,6}，谓词

P(x):x

3，

G(x):x

5，R(x):x

7，求谓词公式的真值：x(R(x)

P(x))

G(5)7、若会合A={a,{b,c}}的幂集为(A)，会合B={,{}}的幂集为(B)，求：(A)(B)。解：(A)={,{a},{{b,c}},{a,{b,c}}}(B)={,{},{{}},{{,{}}}(A)(B)={{a},{{b,c}},{a,{b,c}},{},{{}},{{,{}}}8、设会合A={2,3,4,6,8,12,24}，R为A上的整除关系，画出偏序集<A,R>的哈斯图；写出会合A中的最大元、最小元、极大元、极小元；写出A的子集B={2,3,6,12}的上界、下界、最小上界、最大下界。9、会合S={1，2，3，4，5}，找出S上的等价关系，此关系能产生区分{{1，2}，{3}，{4，5}}，并画出关系图。10、已知A＝{a，b，c，d}，A上的关系R定义为：R＝{<a,b>，<b,a>，<a,c>，<b,d>，<d,a>}，求：r(R)，s(R)，t(R)。11、已知A＝{1，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、会合A{1,2,3,4}上的关系R={<1,1>,<1,3>,<2,2>,<3,3>,<3,1>,<3,4>,<4,3>,<4,4>}，写出关系矩阵MR，画出关系图并议论关系R的性质。13、设会合A={2,3,4,6,8,12,24}，R为A上的整除关系，画出偏序集<A,R>的哈斯图。14、已知G={1,2,3,4,5,6}，×为模7乘法。试说明<G,×>能否组成群能否为循环群假如，生成元是什么7715、一棵树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及该树的总权值。v27v354v112333v65v519、权数1，4，9，16，25，36，49，64，81，100结构一棵最优二叉树。20、以以下图所示的赋权图表示某七个城市v1,v2,,v7及早先算出它们之间的一些直接通讯线路造价，试给出一个设计方案，使得各城市之间能够通讯并且总造价最小。四、写出对应下边推理的证明：（此题10分，1*10’=10’）1、(AB)∧(CD)，BE，DF，￢(E∧F)，AC￢A2、P∨WR，RS∨T，ST，￢T∧Q￢W3、假如小张和小王去看电影，则小李也去看电影；小赵不去看电影或小张去看电影；小王去看电影。所以，当小赵去看电影时，小李也去看电影。4、假如小张去看电影，则当小王去看电影时，小李也去。小赵不去看电影或小张去看电影。小王去看电影。所以当小赵去看电影时，小李也去。5、假如我学习（

P），那么我数学不会不及格。假如我不热中于玩扑克（

R），那么我将学习。但我数学不及格（Q）。所以我热中于玩扑克。（注：请按括号中提示的字母翻译并进行论证。

）6、或许是天晴，或许是下雨。假如是天晴，我去看电影。假如我去看电影，我就不看书。所以，假如我在看书，则天在下雨。7、所有牛都有角，有些动物是牛；所以，有些动物有角。（P(x)：x是牛；Q(x)：x有角；R(x)：x是动物）8、每个喜爱步行的人都不喜爱坐汽车；每个人或许喜爱坐汽车或许喜爱骑自行车；有的人不喜爱骑自行车。因此有的人不喜爱步行。（先将推理在一阶逻辑中符号化，随后考证其正确性）五、解答题（此题10分，1*10’=10’）1、某班有还有

25个学生，此中14人会打篮球，12人会打排球，6人会打篮球和排球，2人会打这三种球。而6个会打网球的人都会打此外一种球（指篮球或排球）

5人会打篮球和网球，，求不会打这三种球的人数。2、120名学生参加考试，此次考试有A、B和名学生做对A和B；16名学生做对A和

C共3道题，考试结果以下：12名学生C；28名学生做对B和C；做对A题的有

3道题都做对了；48名学生；做对

20B题的有

56名学生；还有

16名学生一道题也没做对。试求做对了

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、画出哈斯图：设B＝{a,b,c}，R={<s1,s2>|s1s2s