2016离散复习练习题

（四）一、判断题（每题1分，共10分）1.在命运题逻辑中，任何命题公式的主合取范式都是存在的，并且是惟一的。 （ ）2. 011是公式的成真赋值 ( )3. ( )4. （ ）5.三种重要的二元关系是等价关系、偏序关系和函数关系，它们的共同特点是都具有自反性 。 ( )6. 设F,R都是二元关系,则(FR)-1=F-1R-1。( )7.设n是任意一个正整数,则一定存在阶是n的群. ( )8. 布尔代数是有界格,也是分配格. ( )9.无向完全图（n2）一定是哈密顿图 ( )10.阶数至少是2 树的每一条边都是桥,因而它的边连通度是1. （ ）二、空题（每小题分，共分） 1. 谓词公式x(P(x,y) tQ(t,z)R(x,y,t)中量词的辖域是_。2.设F(x):x是人，H(x,y):x与y一样高，在一阶逻辑中，命题“人都不一样高”的符号化形式为_ _。 3.从公式分类角度来看，它为_式。 4.设R=,，则R的对称闭包是 。 5.设A,B是集合，6.，是模6加群， 则它的生成元是 。24= 7整数加群是循环群，其生成元是和。8.设是偏序集,如果_ _, 则称是(偏序)格。9.一棵二叉树先序遍历得ABDECF，中序遍历得DBEACF,则后序遍历的结果是_。 10. r=5,当s= 时，完全二部图才可能存在完美匹配。 。 三、计算题（1-4题每题8分；5-6题每题10分，共52分）1.R1=,R2=,求：(1) R1-1 (2) R1R2 (3)R22 (4)t(R1)(传递闭包)2设G=，G上的运算是矩阵乘法。已知G构成群。（1）指出个元素的阶；（2）找出G的全部子群；（3）在同构的意义下G是4阶循环群还是Klein四元群？3.(1)在一棵有2个2度顶点，4个3度顶点，其余顶点都是树叶的无向树中应该有几片树叶？(2)画出两棵非同构的满足上述条件的无向树。4.设为一个偏序集，其中，A=1，2，3，4，6，9，24，54,R是A上的整除关系。（1）画出的哈斯图； （2）求A的极大元和极小元； （3）求B=4,6的上确界和下确界。5.求公式的主和取范式(化成M1M2M3的形式)。画一棵带权为2，2，2，3，3，4，5，8的最优二叉树T，并计算它的权W（T）。四、证明题（每小题6分，共18分）1.前提： 结论: 2.定理（子群判别法1)设H是群的非空子集，则HG当且仅当(1)a，bH， abH；(2)aH，a1H。利用上述定理证明：设H是群的非空有限子集。若H关于封闭，则H是G的子群。3.用数学归纳法证明n阶无向树T有n-1边。（五）一、选择题（每小题 2分，共 20 分。请将答案填在下面的表格内）1、从集合分类的角度看,命题公式可分为() A.永真式、矛盾式 B. 永真式、可满足式、矛盾式C. 可满足式、矛盾式 D. 永真式、可满足式2、设B不含有x，等值于()A. B. C. D.3、设S,T,M是集合，下列结论正确的是（ ）A如果ST=SM，则T=M B如果S-T=，则S=TC D4、设R是集合A上的偏序关系，则R不一定是()A.自反的 B. 对称的 C. 反对称的 D. 传递的5 设R为实数集，定义R上4个二元运算，不满足结合律的是（ ）。A. f1(x,y)= x+y B. f2(x,y)=x-y C. f3(x,y)=xy D. f4(x,y)=maxx,y 6、设是一个格，则它不满足()A.交换律 B. 结合律 C. 吸收律 D. 消去律7、设A=1,2,则群的单位元和零元是()A. 与AB. A与 C. 1与 D. 1与A8、下列编码是前缀码的是( ).A.1,11,101 B.1,001,0011 C.1,01,001,000D.0,00,0009、下图中既是欧拉图又是哈密顿图的是（ ） A B C D 10、下图所示的二叉树中序遍历的结果是（ ）Aabcde Bedcba Cbdeca Dbadce二、填空题（每题3分，共24分）1、含3个命题变项的命题公式的主合取范式为,则它的主析取范式为 。()2、，模4加群， 则3是 阶元，33= ，3的逆元是 。 3、设V=,其中“+”是普通加法。，令1(x)=x, 2(x)=-x,3(x)=x+5, 4(x)=2x，其中有 个自同构.4、设是集合A=1，2，3，4,5,6上的一个置换，则把它表示成不相交的轮换的积是 。4、已知n阶无向简单图G有m条边，则G的补图有 条边。5、一个有向图是强连通的充分必要条件是 。7、已知n阶无向图G中有m条边，各顶点的度数均为3。又已知2n-3=m，则m= .8、在下图中从A点开始，用普里姆算法构造最小生成树，加入生成树的第三条边是 （ ）。三、计算题（每题9分，共 36分）1、已知命题公式，(1) 构造真值表。 (2) 求主析取范式(要求通过等值演算推出)。2、R1=, R2=,求： (1) （） () 求 、设为一个偏序集，其中，A=1，2，3，4，6，9，12，24,R是A上的整除关系。（1）画R出的哈斯图； （2）求A的极大元和极小元； （3）求B=4,6的上确界和下确界。、画一棵带权为1，1，1，3，3，5，8的最优二叉树T，并计算它的权W（T）。得分阅卷人四、证明题（共 20分）1、（7分）前提： 结论: 2、（7分）A=(0,0),(0,1),(1,0),(1,3),(2,2),(2,3),(3,1),R=| (a,b),(c,d)A且a+b=c+d .(1)证明：R是A上的等价关系 (2)给出R确定的对A的划分(分类).3、（6分）设是群, ,证明S是G的子群. （六）一、选择题（每小题2分，共20分）1一个命题公式或一阶逻辑公式的（ ）是不惟一的。A主析取范式 B主合取范式 C前束范式 D对偶式2下列四个公式正确的是 A. B. C. D.3设集合A=a，b，c，d，e，偏序关系R的哈斯图下图所示，则元素的关系不正确的是（ ）。A B C D4已知A,B是集合A=15，B=10，AB=20，则AB=（ ）A10 B5 C20 D135X=a，b，c，d，e，Y=1，2，3，4，f从X到Y的映射，其中f(a)=2,f(b)=4,f(c)=1,f(d)=3,f(e)=4,则f是（） A.双射 B. 满射 C. 单射 D. 不是单射也不是满射6设A,B,C是三个非空集合,则( )是正确的. A. B. C. D. 7在下图所示的哈斯图中的偏序集不是格的是（ ）8下图中,（ ）是欧拉图。A B C D9.关于无向树的描述,不正确的是( ).A. 无向树是连通图、没有回路,每个边都是桥；B. 无向树是连通图、边数比顶点数少,任意两个顶点的路径是惟一的；C. 无向树是连通图、没有回路,每个顶点都是割点；D. 无向树是连通图、没有回路，每条边都是割边。10.关于含有n片树叶的最优二叉树描述,不正确的是( ).A. 含有n片树叶的最优二叉树每个分支点都有两个孩子；B. 含有n片树叶的最优二叉树分支点的个数是n-1；C.W(T)等于个分支点的权重（构造最优二叉树时产生）之和；D. 在权重一定的前提下，含有n片树叶的最优二叉树是惟一的。二、计算题（每小题10分，共40分）1.(1)求的主析取范式；(2)根据主析取范式直接写出主合取范式； (3)根据主析取范式直接写出真值表。2.设集合A=a，b，c，d，A上的关系R=, 求：（1）画出R的关系图； （2）求出R的传递闭包tr(R) ； (3) tr(R)中再添加一些元素后得D(R)，若使D(R)是等价关系，则tr(R)中再添哪些元素后得D(R)?3.(1)下图的最下生成树；(2)求该图的点连通度和边连通度；(3)求A到B的最短路径的长度。 A B4.(10分)对于下有向图,(1) 写出度序列和出度序列；(2) 写出邻接矩阵A，第一行元素之和的含义是什么？(3) 求,据此说明从A到A的长度为4的回路用多少？三、证明题1 设A是正整数集合，在上定义二元关系R如下：当且