离散数学练习题

一、填空题（10分，每空1分，请将本题答案填在原题横线．．．．上！）1、设集合X={0，1，2}，R是X上的二元关系，R={0，0，0，2，1，2，2，0，2，1}，则R的关系矩阵MR=。2、66,Z为模6整数加群，则由2生成的子群2=，右陪集2⊕65=。3、设A和B为有限集，|A|=m，|B|=n，则有个从A到B的关系，有个从A到B的函数。4、无向图G如下图所示，G的点连通度κ为，边连通度λ为。5、在上面无向图中，已给出了一棵生成树T（粗边所示），则树枝d对应的基本割集是，弦b对应的基本回路是。6、令F(x)：x是整数，G(x)：x是奇数，则“不存在不是奇数的整数”符号化为。7、含有三个命题变项P，Q，R的命题公式PQ的主析取范式是（用mi形式表示最小项）。二、单选题（20分，每题1分，请将本题答案写在下方表格．．．．中！）1、下面给出的符号串集合中，（）不是前缀码。A、1111,110,10,0B、01,001,000,10C、1101,1001,101,110,D、abcabaacaacb,,,,,2、下列()组赋值不是命题公式C()AB的成真赋值。A、010B、011C、110D、1013、设A={a，b，c，d}，A上的等价关系R={a，b，b，d，d，a}∪R-1∪IA，则对应于R的A的划分是（）。A、{{a，b}，{c，d}}B、{{a，b，d}，{c}}C、{{a}，{b}，{c}，{d}}D、{{a}，{b，c}，{d}}4、二部图3,3K是()。A、欧拉图B、哈密顿图C、非连通图D、完全图5、令p:我将去上网，q:我有时间，则“我将去上网，仅当我有时间”可符号化为()。(A)qp(B)qp(C)pq(D)qp12345678910111213141516171819206、下面（）图不一定是树。A、每对结点间都有路的图B、无回路的连通图C、连通但删去一条边则不连通的图D、有n个顶点n—1条边的连通图7、集合A={1,2,…,10}上的关系R={x,y|x+y=10,x,y∈A},则R的性质是()。(A)自反的(B)传递的、对称的(C)对称的(D)反自反的、传递的8、设G如右图，那么G不是()。(A)哈密顿图(B)完全图(C)欧拉图(D)树9、设图D的邻接矩阵为0110110101110110010111110，则D的顶点数与边数分别为()。A、4，5B、5，16C、4，10D、5，810、下列式子中正确的是（）。A、＝1B、C、｛｝D、＝{}11、由2个命题变元p和q组成的不等值的命题公式的个数有()。(A)2(B)4(C)16(D)812、给定下列非负整数序列，可构成简单无向图的节点度数序列的为()。(A)(1，3，4，4，5)(B)(1，1，2，2，2)(C)(0，1，3，3，5)(D)(1，1，2，2，3)13、4阶完全无向图4K中含3条边的不同构的生成子图有()。(A)5(B)4(C)3(D)214、任意12阶群的子群的阶一定不为()。(A)3(B)6(C)8(D)415、在公式xF(x，y)→yG(x，y)中变元x是()。(A)既是自由变元，又是约束变元(B)既不是自由变元，又不是约束变元(C)自由变元(D)约束变元16、设图G=V，E为无向图，|V|=5，|E|=20，则G一定是()。A、完全图B、正则图C、多重图D、简单图17、给定公式)()(xxPxxP，当D={a,b}时，解释()使该公式真值为0。A.P(a)=0、P(b)=0B.P(a)=0、P(b)=1C.P(a)=1、P(b)=118、设A={1,2,3}，则A上有（）个二元关系。A、23B、32C、322D、23219、设Z是整数集合，“+”是数的加法运算，则Z，+的单位元是()A、1B、-1C、没有单位元D、020、设R和S是集合A={1，2，3，4}上的二元关系，则S是R的（）闭包。R={1，1，1，2，2，2，2，3，4，4}S={1，1，1，2，2，2，2，3，3，3，4，4}A、对称B、自反C、传递D、以上都不对三、求解题（40分，每题8分，请将本题答案写在后面答题纸上！）1、在自然推理系统中构造证明：已知张三或李四的彩票中奖了。如果张三的彩票中奖了，那么你会知道张三的彩票中奖了。如果李四的彩票中奖了，那么王五的彩票也中奖了。你不知道张三的彩票中奖了。所以，李四和王五的彩票都中奖了。2、设A={a,b,c,d,e}，A上的偏序关系R＝{c,a，c,b，d,a，d,b，e,a，e,b，e,c，e,d}IA，求：(1)画出偏序集A，R的哈斯图；(2)求子集B={c,d,e}的极大元，极小元，最大元，最小元。3、求一阶逻辑公式的前束范式：(xF(x,y)→yG(y))→xH(x,y,z)。4、设7个字母在通信中出现的频率如下：a:35%，b:20%，c:15%，d:10%，e:10%，f:5%，g:5%，用Huffman算法求传输它们的最佳前缀码。要求画出最优二叉树，并指出传输100个按上述频率出现的字母，需要多少个二进制数字。5、四、证明题（30分，每题7、7、8、8分，请将本题答案写在后面答题纸上！）1、例如，f和g都是群G1，。到群G2，*的同态映射，C={x|x∈G1∧f(x)=g(x)}。证明：C，。是G1，。的一个子群。2、要在七天安排七场考试，同一个老师监的任何两场考试不能安排在接连的两天内进行。假如每个教师最多监四场考试，请证明：安排这样的考试日程表是可以的。3、设R是集合A上一个等价关系，{,|,(,,)}SxyxyAzxzRzyR，试证明S也是A上的一个等价关系。4、参考答案一、1、1010011102、{0，2，4}，{5，1，3}3、2mn，nm4、2，35、d,b,c，bade6、(F()(x))或(F()(x))xxGxxG7、m6˅m7二、12345678910CBBBAACDBC11121314151617181920CBCCACBDDB