离散数学练习题及答案

一、填空题1、集合的表示方法有两种：法和法。请把“奇整数集合”表示出来{}。1、列举；描述；2、无向连通图G含有欧拉回路的充分必要条件是不含有奇数度结点.2*、连通有向图D含有欧拉回路的充分必要条件是D中每个结点的入度＝出度.3、设R是集合A上的等价关系，则R所具有的关系的三个特性是、自反性、对称性、传递性.4、有限图G是树的一个等价定义是：连通无回路（或任一等价定义）.5、设N(x)：x是自然数，Z(y)；y是整数，则命题“自然数都是整数，而有的整数不是自然数”符号化为x(N(x)Z(x))x(Z(x)N(x))6、在有向图的邻接矩阵中，第i行元素之和,第j列元素之和分别为、结点vi的出度和结点vj的入度．7、设A，B为任意命题公式，C为重言式，若，那么命题是重言式的真值是1．8、命题公式的主析取范式为PQ．设图G＝<V，E>和G＝<V,E>,若，则G是G的真子图，若V=V,EE，则G是G的生成子图.10、在平面图中,则＝2E,其中ri(i=1,2,…,r)是G的面．11、设，则从A到B的所有映射是11、1={（a，1），（b，1）}；2={（a，2），（b，2）}；3={（a，1），（b，2）}；4={（a，2），（b，1）}12、表达式xyL（x，y）中谓词的定义域是{a，b，c}，将其中的量词消除，写成与之等价的命题公式为12、（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））12*、设个体域D＝{a,b},公式消去量词化为(G(a)(H(a,a)H(a,b)))(G(b)(H(b,a)H(b,b)))13、含有三个命题变项P，Q，R的命题公式PQ的主析取范式是14、设R，S都是集合A上的等价关系，则对称闭包s(RS)=RS15、设G是连通平面图，v,e,r分别表示G的结点数，边数和面数，则v,e和r满足的关系式是16、设G是n个结点的简单图，若G中每对结点的度数之和≥n，则G一定是哈密顿图.17、一个有向树T称为根树，若，其中，称为树根，称为树叶.若有向图T恰有一个结点的入度为0，其余结点入度为1；入度为0的结点；出度为0的结点.18、图的通路中边的数目称为.结点不重复的通路是通路.边不重复的通路是通路.通路长度；初级；简单.19、设A和B为有限集，|A|=m，|B|=n，则有个从A到B的关系，有个从A到B的函数，其中当m£n时有个入射，当m=n时，有个双射。19、20、集合（是/不是）可数的。是21、设上的整除关系在上定义两个二元运算和：对任意，，。请填空（在横线上填是或不是）：=1\*GB3①是=2\*GB3②是=3\*GB3③是=4\*GB3④不是=1\*GB3①代数系统格。=2\*GB3②代数系统有界格。=3\*GB3③代数系统有补格。=4\*GB3④代数系统分配格。二、单项选择题（选择一个正确答案的代号，填入括号中）1、设命题公式G=（PQ），H=P（QP），则G与H的关系是（A）。A．GHB．HGC．G=HD．以上都不是2、下列命题公式等值的是(C)3、设V＝{a,b,c,d},与V能构成强连通图的边集E＝(A) (A){<a,b>,<a,c>,<d,a>,<b,d>,<c,d>}(B){<a,d>,<b,a>,<b,c>,<b,d>,<d,c>}(C){<a,c>,<b,a>,<b,c>,<d,a>,<d,c>}(D){<a,d>,<b,a>,<b,d>,<c,d>,<d,c>}4、设L(x)：x是演员，J(x)：x是老师，A(x,y)：x佩服y.那么命题“所有演员都佩服某些老师”符号化为(B) (A)(B) (C)(D)5、在由3个元素组成的集合上，可以有(D)种不同的关系。 (A)3 (B)8 (C)9(D)5126、设S1=,S2={},S3=P({}),S4=P()则命题为假的是(A)． (A)(B)(C)(D)7、设G是连通平面图，有v个结点，e条边，r个面，则r=(A)．(A)e－v＋2(B)v＋e－2(C)e－v－2(D)e＋v＋28、下列命题正确的是（A）。A．{}=B．{}=C．{a}{a，b，c}D．{a，b，c}9、设A,B,C都是集合，如果AC＝BC，则有(C) (A)A＝B(B)AB(C)当A－C＝B－C时,有A=B(D)当C=U时,有AB10、设是布尔代数，，则下式不成立的是(D)11、下面给出的一阶逻辑等价式中，（A）是错的。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））三、多重选择题(每道小题都可能有一个以上的正确选项，须选出所有的正确选项，不答不得分，多选、少选或选错都将按比例扣分。)命题公式 (P∧(P→Q))→Q是_____式。(1)重言(2)矛盾(3)可满足(4)非永真的可满足2、给定解释I=(D,)=(整数集，{f(x,y):f(x,y)=x-y；g(x,y):g(x,y)=x+y；P(x,y):x<y})，下列公式中_____在解释I下为真。(1)P(f(x,y),g(x,y))(2)xyP(f(x,y),g(x,y))(3)xy(P(x,y)→P(f(x,y),x))(4)xyP(f(x,y),g(x,y))3、Ａ是集合，=10，则=_____。(1)100(2)99(3)2048(4)1024(5)5124、集合Ａ={x|x是整数，<30}，Ｂ={x|x是质数，x<20}，C={1,3,5}，则①=_____;②=_____;③=_____;④=_____。(1){1,2,3,5}(2)(3){0} (4){1,3,5,7,11,13,17,19}(5){1,3,5,7}(6){7,11,13,17,19}5、设A、B、C是集合，下列四个命题中，_____在任何情况下都是正确的。若AB且B∈C，则A∈C(2)若AB且B∈C，则AC若A∈B且BC，则AC(4)若A∈B且BC，则A∈C6、设集合Ａ={a,b,c,d,e,f,g}，Ａ的一个划分={{a,b},{c,d,e},{f,g}}，则所对应的等价关系有_____个二元组。(1)14(2)15(3)16(4)17(5)8(6)49(7)5127、S={1,2,3,4,5,6,7,8,9,10,11,12}，≤是S上的整除关系。S的子集Ｂ＝{2,4,6｝，则在<S，≤>中，Ｂ的最大元是_____；Ｂ的最小元是_____；Ｂ的上确界是_____；Ｂ的下确界是_____。(1)不存在的(2)36(3)24(4)12(5)6(6)1(7)28、设有有限布尔代数(B,+,*,’,0,1)，则=_____能成立。(1)1(2)2(3)3(4)4(5)5(6)8(7)99、G={0,1,2,…,n}，n∈N，定义为模n加法，即xy=(x+y)modn，则代数系统(G，)_____。(1)是半群但不是群(2)是无限群(3)是循环群(4)是变换群(5)是交换群10、仅有一个结点的图称为()，当然也是() (1)零图(2)平凡图(3)补图(4)子图1.1、3。2.4。3.4。4.1；4；2；2。5.4。6.4。7.1；7；4；7。8.2、4、6。 9.3、5。10.2；1。四、化简解答题第1题图1、(1)设图G(如第1题图)，作图G的嵌入图，说明图G是平面图.第12题答案图图G的嵌入图，如第12题答案图.故图G为平面图(4分)(2)在具有n个顶点的完全图Kn中删去多少条边才能得到树？解：n个顶点的完全图Kn中共有条边，n个顶点的树应有条边，于是，删去的边有：。2、判别谓词公式的类型.2、设I为任意一个解释，D为I的个体域.若在解释I下，该公式的前件为0，无论如何取值，为1； 若在解释I下，该公式的前件为1，则使得为1，它蕴含着为1为1，由y的任意性，必有为1，于是为1.所以，是永真式．3、化简集合表达式：((ABC)(AC))－((C(C－B)－A)3、((ABC)(AC))－((C(C－B)～A)＝(AC)－（C～A）(两次用吸收律)=((AC)(～CA)=(A～C)(C～C)A(AC)=(A～C)A=A4、判断下列哪些运算结果是对的？哪些是错的？请将错误的运算结果更正过来．(1)(2)(3)(4)（5） （6） （7） （8）4、(1)对．(2)错．应为．(3)对．(4)错．应为{}（5）错．应为 （6）错．应为(或或A－AB) （7）错．应为，即（8）对．5、将命题公式化为只含和的尽可能简单的等值式．5、（优先级有误）不惟一.v1v1e1 e5v2e6 v5e7 e4e2 e8v3 v4e3v3e3v4第12题图6、设图G如右图.已知通路(1)v1e5v5e7v2e2v3(2)v5e6v2e2v3e3v4e8v2e7v5(3)v2e7v5e6v2(4)v1e1v2e2v3e3v4e8v2e6v5试回答它们各是简单通路、简单回路、初级通路还是初级回路?6、(1)初级通路；(2)简单回路；(3)初级回路；(4)简单通路.7、试问n取何值时，无向完全图Kn，存在一条欧拉回路？7、由于Kn有n个结点，并且每个结点的度数均为n－1，于是，当n为奇数时，Kn的每个结点的度数都是偶数，所以存在一条欧拉回路．8、已知(L，*，)是格，且二元运算*和满足分配律，a,b,cL，化简表达式 ((a*b)(a*c))*((a*b)(b*c))解答：((a*b)(a*c))*((a*b)(b*c))＝(a*b)((a*c)*(b*c))(分配律)=(a*b)((a*b)*c)(幂等律)=a*b(吸收律)9、化简。9、====R10、试将一阶逻辑公式化成前束范式。解：11、指出有向图D(如下图)中各图是强连通，单侧连通还是弱连通？(1)(2)(3)(4)(5)(1)(2)(3)(4)(5)aabced12、找出无向图G（如右图所示）中的一个点割集，三条边和四条边的边割集各一个．11、强连通图为：图(1),(4),(5)；单侧连通图为：如图(1),(2),(4),(5)；弱连通图为：图(1)～(5).3.点割集：{a,c,d}(不惟一)三条边的边割集：{(b,c),(c,e),(c,d)}(不惟一)四条边的边割集：{(a,b),(a,d),(d,e),(c,e)}(不惟一)13、答案图如下图的虚线图.13、求图13图G的对偶图.14、给定三个图如下图所示，试判断它们是否为欧拉图、哈密顿图、或平面图？并说明理由．abcdefg图G1图G2图G3图6－7图6－714、图G1是欧拉图，因为每个结点度数均为偶数． 图G2是哈密顿图，存在哈密顿回路，如cdgfebac．(不惟一) 图G3是平面图．可以改画成可平面图，如图．五、计算题1、设R和S是集合上的关系，其中，试求：（1）写出R和S的关系矩阵；（2）计算。1、解：（1）（2）={<1，3>，<2，4>}={<1，1>，<1，2>，<1，3>，<2，3>，<2，4>，<3，4>，<4，4>}={<1，1>，<3，1>，<3，2>，<4，3>}={<3，1>，<4，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中各元素的等价类。2、解：R1和R2的关系图如下：（略）由关系图可知，R1是等价关系。R1不同的等价类有两个，即{a，b}和{c，d}。由于R2不是自反的，所以R2不是等价关系。3、设集合A＝{1,2,3,4,6,8,12}，R是A上的整除关系，画出偏序集(A,R)的哈斯图；写出A的子集{2,4,6,8}的上界，下界，最小上界，最大下界；(3)写出集合A的最大元，最小元，极大元，极小元。集合A＝{1,2,3,4,6,8,12}(1)半序集(A,R)的哈斯图112483612(2)子集{2,4,6,8}无上界，下界是1,2，无最小上界，最大下界是2.(3)A无最大元，最小元是1，极大元是8,12，极小元是1。4、用迪克斯特拉算法求下面有限权图中从A到B的最短路，要求用图示给出求解过程，并计算它们的权值。AAB142241631892(本题12分)求有限权图的最短路ABAB1AB12ABAB122AB1422ABAB14221AB142212A到B的最短路的权值为6.145892106735、已知带权小生成树，并计算该生成树的权．6、设简单连通无向图G有12条边，G中有1度结点2个，2度结点2个，4度结点3个，其余结点度数不超过3．求G中至少有多少个结点．试作一个满足该条件的简单无向图．图55、做法如下：=1\*GB3①选边1；=2\*GB3②选边2；10673458921=3\*GB3③选边3；=4\*GB3④选边5；10673458921⑤选边7最小生成树为{1,2,3,5,7}．如图4中粗线所示．权数为18．图46、设图G有x个结点，有握手定理 21+22+34＋3（x223）122x9图G至少有9个结点．满足条件的图如图所示．7、求命题公式的主合取范式.7、7*、求┐(P→Q)(P→┐Q)的主合取范式并给出所有使命题为真的赋值。解答：原式(┐(P→Q)→(P→┐Q))∧((P→┐Q)→┐(P→Q))((P→Q)∨(P→┐Q))∧(┐(P→┐Q)∨┐(P→Q))(┐P∨Q∨┐P∨┐Q)∧(┐(┐P∨┐Q)∨(P∧┐Q))(┐(P∧┐Q)∨(P∧┐Q))(P∧Q)∨(P∧┐Q)P∧(Q∨┐Q)P∨(Q∧┐Q)(P∨Q)∧(P∨┐Q)命题为真的赋值是P=1,Q=0和P=1,Q=18、求格的表达式的对偶式，并计算当a,b,c的真值分别为0,1,1时对偶式的真值．8、的对偶式为对偶式的真值为9、设．9、,,－1＝10、重新排列1，2，3，4，5，6，7，8，9使得有4个数在原来位置上，其它5个数不在原来位置上，有多少种排法？解答：这是有4个数不动，5个数的错位排列问题。4个数没有预先指定，故有种可能。5个数的错位排列，为所求为11、试画所有不同构的四阶无向树(四个结点)．12.求从1到500的整数中，能被3或5除尽的数的个数。12.解：设A为从1到500的整数中，能被3除尽的数的集合。B为从1到500的整数中，能被5除尽的数的集合。则|A|=[500/3]=166（[x]表示不超过x的最大整数）|B|=[500/5]=100|A∩B|=[500/（3*5）]=33……（1分）由包含排斥原理：|A∪B|=|A|+|B|-|A∩B|=166+100-33=233即从1到500的整数中，能被3或5除尽的数有233个。……（2分）13、画图。对于下图，利用克鲁斯克尔算法求一棵最小生成树。13、最小生成树为14、求带权2、3、5、7、11、13的最优二叉树。14、解23571113所求最优二叉树为55711131071113171113172441六、证明题1、试构造推理证明.1..①RS[前提引入]=2\*GB3②S[前提引入]③R[①，②析取三段论]④(PQ)R[前提引入]⑤(PQ)[③,④拒取式]⑥[⑤置换]2、证明命题公式与有相同的主析取范式．2、方法1．因为两命题公式等值，由主合取范式的惟一性，可知两命题公式的主合取范式是相同．方法2． 因为它们的主合取范式相同，可知它们的主析取范式也相同．3、设G为9个结点的无向图，每个结点的度数不是5就是6，试证明G中至少有5个度数为6的结点，或者至少有6个度数为5的结点。证明：由握手定理的推论，G中度数为5的结点个数只能是0,2,4,6,8五种情况；此时，相应的结点度数为6的结点个数分别为9，7，5，3，1个，以上五种对应情况(0,9),(2,7),(4,5),(6,3),(8,1)，每对情况，两数之和为9，且满足第2个数大于或等于5，或者第1个数大于或等于6，意即满足至少有度数为6的结点5个，或者至少有度数为5的结点6个。4、试证明（A~B）（~AB）=（AB）（~A~B）证明：5、设，其中Q是有理数集，证明(Q.，+，×)是域，＋和×分别是数的加法和乘法.证明且惟一，故运算＋是Q()上的二元运算，加法满足结合律、交换律..Q()的0元是0＋0.,即存在逆元.所以(Q(),＋)是交换群.且惟一，故×是Q()上的二元运算.容易验证×在Q()上满足交换律、结合律.Q()的单位元是1＋0.任给非0元(a,b至少一个不为0)，运算×在Q()上非0元存在逆元.所以(Q()－{0}，×)是交换群.可以验证，运算＋对×满足分配律.所以(Q()，＋，×)是域.6、设G是图，无回路，但若外加任意一条边于G后，就形成一回路.试证明G必为树.证明由树的定义可知，只需证G连通即可.任取不相邻两点u,v,由题设，加上边<u,v>就形成一回路，于是去掉边<u,v>,从u到v仍有路u,…,v，即u,v连通，由u,v的任意性可知，G是连通的，故G必是树.7、设G是平面图，并且G的所有面的次数均为3，证明其中e是G的边数.v是G的结点数.7、因为G的所有面的次数为3，因此对G的任意面r，有 deg(r)=3从而，又根据定理6，G的所有面的次数之和等于其边数的2倍，即即代入欧拉公式，8、设G是连通简单平面图，则G至少有一个度数不超过5的结点．（提示：用反证法）8、因为G是连通简单平面图，它的每个面至少有3条边，所以有，即（其中r，e分别为图G的面数和边数） 假设结论不成立，则每个结点的度数都大于等于6．则有，即有（其中v是图G的结点数）由欧拉公式：2==0矛盾．所以G中至少有一个结点的度数小于或等于5．9、证明：偶数阶群中阶为2的元素的个数一定是奇数。证：由群的元素的阶的有关知识，任一个群中阶为1的就只有单位元一个，阶大于2的元素是成双成对出现的，其余的元素就是阶为2的元素。故阶大于2的元素有偶数个。由于这是一个偶数阶群，而奇数加上一个偶数还是奇数，一个偶数减去一个奇数仍是奇数，故阶为2的元素一定是奇数。我们用综合法得出了整个推理过程。10、设群<G,*>除单位元外每个元素的阶均为2，则<G,*>是交换群。10、设<G，*>为一群。证明：若对任意aÎG有a2=e，e为幺元，则G为阿贝尔群。证明：对任一aG，由已知可得a*a=e，即a-1=a。对任意a,bG，因为a*b=(a*b)-1=b-1*a-1=b*a，所以运算*满足交换律。从而＜G,*＞是交换群。10*、设<G，*>为一群。证明：若对任意a，bÎG有(a*b)2=a2*b2，则G为阿贝尔群。10*、证：对任意a,bÎG，(a*b)2=(a*b)*(a*b)=a*(b*a)*b又由题设(a*b)2=a2*b2=(a*a)*(b*b)=a*(a*b)*b……（2分）从而a*(b*a)*b=a*(a*b)*b。两边同时左乘a-1，右乘b-1得：a*b=b*a……（3分）因此，*运算满足交换律，故<G,*>为阿贝尔群。11、在一个群<G,*>中，若A和B都是G的子群。若AB=G，则A=G或B=G。证明：用反证法证明。若AG且BG，则有aA,aB且bB,bA。因为A，B都是G的子群，故a,bG，从而a*bG。因为aA,所以aA。若a*bA,则b=a*(a*b)A，这与aB矛盾。从而a*bA。同理可证a*bB。综合可得a*bAB=G，这与已知矛盾。从而假设错误，得证A=G或B=G。12、任一有限半群一定在等幂元。证明：设<S,*>是一个有限半群。任取aS，由于*满足结合律，我们有{a,a,a,…,a,…}S因为S是有限集合，故a,a,a,…,a,…不可能两两不同。从而一定存在正整数k,m,1k<m使得a=a令p=m-k，则由于*满足结合律，a=a=a*a。对任意正整数qk，有a=a*a=（a*a）*a=a*a（#）若p=q，则元素a就是一个等幂元。否则因为p1，故存在正整数n满足npk。故利用（#）可得a=a*a=a*(a*a)=a*a=a*(a*a)=a*a=……=a*a故a就是S的一个等幂元。13、设是有限字母表，给定代数系统，其中是串的连接运算。对于任一串，建立到的映射，。证明是到的一个满同态，且当时，是同构映射。13、证明对于中任意两字符串和，因为，所以，对于任一正整数，取，则，所以，，是到的一个满同态。当时，设，，，是双射，因此，是一个同构映射。14、设R，S为A上的两个等价关系，且RÍS。定义A/R上的关系R/S：<[x],[y]>ÎR/S当且仅当<x，y>ÎS证明：R/S为A/R上的等价关系。14、证明：S为A上的等价关系，那么对任意x有<x,x>ÎS，所以<[x],[x]>ÎR/S，R/S是自反的；……（2分）若<[x],[y]>ÎR/S，则<x,y>ÎS，由S对称知<y,x>ÎS，所以<[y],[x]>ÎR/S，R/S是对称的；……（3分）若<[x],[y]>ÎR/S，<[y],[z]>ÎR/S，则<x,y>ÎS，<y,z>ÎS，由S传递知<x,z>ÎS，所以<[