《离散数学》作业学习资料

第1页共1页在您完成作业过程中，如有疑难，请登录学院网站“辅导答疑”栏目，与老师进行交流讨论！《离散数学》作业一、选择或填空1．下列公式中哪些是永真式？()A.(┐PQ)→(Q→R)B.P→(Q→Q)C.(PQ)→PD.P→(PQ)2．设全体域D是正整数集合，确定下列命题的真值：A.xy(xy=y)()B.xy(x+y=y)()C.xy(x+y=x)()D.xy(y=2x)()3．有n个结点的树，其结点度数之和是()。4．举出集合A上的既是等价关系又是偏序关系的一个例子。()5．群<G,*>的等幂元是()，有()个。6．下面给出的集合中，哪一个不是前缀码()。A.{a，ab，110，a1b11}B.{01，001，000，1}C.{1，2，00，01，0210}D.{12，11，101，002，0011}7．下列哪些公式为永真蕴含式？()A.Q=>Q→PB.Q=>P→QC.P=>P→QD.P(PQ)=>P8．设P：我生病，Q：我去学校，则下列命题可符号化为()。（1）若我生病，则我不去学校(2)当且仅当我生病时，我才不去学校9．任一有向图中，度数为奇数的结点有()个。10．集合A上的等价关系的三个性质是什么？()11．群＜A,*＞的等幂元有()个，是()，零元有()个。12．一个图的欧拉回路是一条通过图中()的回路。13．设有下列公式，请问哪几个是永真蕴涵式?()A.P=>PQB.PQ=>PC.PQ=>PQD.P(P→Q)=>QE.(P→Q)=>PF.P(PQ)=>P14．判断下列命题哪几个为正确？()A.{Ф}∈{Ф，{{Ф}}}B.{Ф}{Ф，{{Ф}}}C.Ф∈{{Ф}}D.Ф{Ф}E.{a,b}∈{a,b,{a},{b}}15．设a是10阶群的生成元，则a4是()阶元素，a3是()阶元素。16．设G是一个哈密尔顿图，则G一定是()。A.欧拉图B.树C.平面图D.连通图17．设G是一棵树，则G的生成树有()棵。A.0B.1C.2D.18．设无向图G有16条边且每个顶点的度数都是2，则图G有()个顶点。A.10B.4C.8D.1619．Ａ，Ｂ，Ｃ是三个集合，则下列哪几个推理正确：A.AB，BC=>ACB.AB，BC=>A∈BC.A∈B，B∈C=>A∈C20．设S={１，２，３，４}，Ａ上的关系Ｒ＝｛〈1，2〉，〈2，1〉，〈2，3〉，〈3，4〉｝，求(1)RR(2)R-1。21．一棵无向树的顶点数n与边数m关系是()。22．设A={3，6，9}，A上的二元运算*定义为：a*b=min{a，b}，则在独异点<A，*>中，单位元是()，零元是()。23．设G是有n个结点m条边的连通平面图，且有k个面，则k等于:A.m-n+2B.n-m-2C.n+m-2D.m+n+2。24．设无向图G有18条边且每个顶点的度数都是3，则图G有()个顶点。A.10B.4C.8D.1225、A，B，C是三个集合，则下列哪个推理正确?()(1)AB，BCAC(2)AB，BCAB(3)AB，BCAC26、判断下列命题哪个正确?()(1){Ф}{Ф,{{Ф}}}(2){Ф}{Ф,{{Ф}}(3)Ф{{Ф}}(4)Ф={Ф}27、设T是一棵树，则T是一个().(1)欧拉图(2)哈密尔顿图(3)连通图28、下列公式中哪个不是蕴涵式?()(1)PPQ(2)PQP(3)PQPQ(4)P(P→Q)Q39、下面给出的集合中，哪一个不是前缀码().(1){a，ab，110，a1b11}(2){01，001，000，1}(3){1，2，00，01，0210}(4){12，11，101，002，0011}306阶有限群的任何子群一定不是().(1)2阶(2)3阶(3)4阶(4)6阶31、在有n个顶点的连通图中，其边数().(1)最多有n-1条(2)至少有n-1条(3)最多有n条(4)至少有n条32、下列哪一种图不一定是树?()(1)无简单回路的连通图(2)有n个顶点n-1条边的连通图(3)每对顶点间都有通路的图(4)连通但删去一条边便不连通的图33、下面给出的集合中，哪一个是前缀码?()(1){0，10，110，101111}(2){01，001，000，1}(3){b，c，aa，ab，aba}(4){1，11，101，001，0011}34、有限布尔代数的元素的个数一定等于().(1)偶数(2)奇数(3)4的倍数(4)2的正整数次幂35、在自然数集N上，下列哪种运算是可结合的?()(1)a*b=a-b(2)a*b=max{a,b}(3)a*b=a+2b(4)a*b=|a-b|36、判断下列命题哪个为真?()(1)A-B=B-AA=B(2)空集是任何集合的真子集(3)空集只是非空集合的子集(4)若A的一个元素属于B，则A=B二、求下列各公式的主析取范式和主合取范式1．PQ2．Q→(PR)3．P→Q4．(P→Q)(RP)5．PQ6Q→(PR)7(P→Q)(P→R)三、证明1．PQ，P→R,Q→S=>RS2．A→(CB)，B→A，D→C=>A→D3．P→Q，QR，R，SP=>S4．BD，(E→F)→D，E=>B5．A→(B→C)，C→(DE)，F→(DE),A=>B→F6、A→(B→C)，C→(DE)，F→(DE),AB→F.7、BD，(E→F)→D，EB.8、A→(CB)，B→A，D→CA→D.9、P→Q，QR，RSP.四、设Ａ，Ｂ，Ｃ是三个集合，证明1．(A－B)∪(A－C)=A－(B∩C)2．A∩B=A∩C，∩B=∩C，则C=B3．A∩(B－C)＝(A∩B)－(A∩C)4．A－(B∪C)＝(A－B)－C5．(A－B)∩(A－C)=A－(B∪C)五、证明1．设e和0是关于A上二元运算*的单位元和零元，如果|A|>1，则e0。2．任一图中度数为奇数的结点是偶数个。3．设群＜G，＊＞除单位元外每个元素的阶均为2，则＜G，＊＞是交换群。4．在一个连通简单无向平面图G=〈V，E，F〉中若|V|3，则|E|3|V－6。5．单位元有惟一逆元。6．7．设代数系统<G,*>是一个群，则G除单位元以外无其它等幂元。8．若连通简单无向平面图G有n个结点，m条边，k个面，且每个面至少由k(k3)条边围成，则mk(ｎ－2)／(ｋ－2)。9．证明在元素不少于两个的群中不存在零元。10．素数阶循环群的每个非单位元都是生成元。11．设G=〈V，E〉是一个连通且|V|=|E|+1的图，则G中有一个度为1的结点。12．给定无向连通简单平面图G=<V,E,F>，且|V|=6,|E|=12,则对于任意fF,deg(f)=3。13．证明在一个群中单位元是惟一的。14．在一个群〈G，*〉中，若G中的元素a的阶是k，即|a|=k，则