您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 薪酬管理 > 《离散数学》模拟练习题
离散数学模拟练习题04一、填空题1设A为集合,且A={,1,2},则(A)=__________________________.2.设R,S是集合A={a,b,c,d}上的二元关系,R={(a,a),(a,b),(b,a)},S={(b,c),(c,d),(b,d)},则R-1S=__________________________.3.命题公式G=(PQ)R,则解释(P,Q,R)使G的真值为。4.设谓词的定义域为{,}ab,将表达式)()(xxSxxR中的量词消除,写成与之等价的命题公式是。5.设有限集A,B,|A|=m,|B|=n,则笛卡儿积AB的子集个数有_____________________________个.6设A、B为两个集合,A={1,2,4},B={3,4},则从(A)(B)=_________________________;AB=_________________________.7.求公式(PQ)(PR)的主析取范式_____________________________________________________________________________8.设R是集合A上的半序关系,则R所具有的关系的三个特性是______________________,________________________,_______________________________.9.设命题公式()GPQR,则使公式G为假的解释是.10.设G=(P,L)是图,如果G是____________,并且____________,则G是树。11设A,B是二个集合,A={1,2,3,4},B={2,3,6},则B-A=__________________________,(B)-(A)=__________________________,.12.设集合A={1,2,3},r与s都是A上的映射,r={(1,2),(2,1),(3,3)},s={(1,3),(2,2),(3,2)},则sr=____________________。13.设命题公式G=(PQ)R,则G共有个不同的解释.14.将公式化成等价的前束范式,)))()((),((xRzzQyxyPx。15.设G是完全二叉树,G有15个点,其中8个叶结点,则G的总度数为____________,分枝点数为____________。二、选择题1设集合A={2,{a},3,4},B={{a},3,4,1},E为全集,则下列命题正确的是()。(A){2}A(B){a}A(C){{a}}BE(D){{a},1,3,4}B.2设集合A={1,2,3},A上的关系R={(1,1),(2,2),(2,3),(3,2),(3,3)},则R不具备().(A)自反性(B)传递性(C)对称性(D)反对称性3设半序集(A,≤)关系≤的哈斯图如下所示,若A的子集B={2,3,4,5},则元素6为B的()。(A)下界(B)上界(C)最小上界(D)以上答案都不对4下列语句中,()是命题。(A)请把门关上(B)地球外的星球上也有人(C)x+56(D)下午有会吗?5设I是如下一个解释:D={a,b},0101b)P(b,a)P(b,b)P(a,),(aaP则在解释I下取真值为1的公式是().(A)xyP(x,y)(B)xyP(x,y)(C)xP(x,x)(D)xyP(x,y).6.若供选择答案中的数值表示一个简单图中各个顶点的度,能画出图的是().(A)(1,2,2,3,4,5)(B)(1,2,3,4,5,5)(C)(1,1,1,2,3)(D)(2,3,3,4,5,6).7.设G、H是一阶逻辑公式,P是一个谓词,G=xP(x),H=xP(x),则一阶逻辑公式GH是().(A)恒真的(B)恒假的(C)可满足的(D)前束范式.8设命题公式G=(PQ),H=P(QP),则G与H的关系是()。(A)GH(B)HG(C)G=H(D)以上都不是.9设A,B为集合,当()时A-B=B.(A)A=B(B)AB(C)BA(D)A=B=.10设集合A={1,2,3,4},A上的关系R={(1,1),(2,3),(2,4),(3,4)},则R具有()。(A)自反性(B)传递性(C)对称性(D)以上答案都不对11下列关于集合的表示中正确的为()。(A){a}{a,b,c}(B){a}{a,b,c}(C){a,b,c}(D){a,b}{a,b,c}12命题xG(x)取真值1的充分必要条件是().(A)对任意x,G(x)都取真值1.(B)有一个x0,使G(x0)取真值1.(C)有某些x,使G(x0)取真值1.(D)以上答案都不对.13.设G是连通平面图,有5个顶点,6个面,则G的边数是().(A)9条(B)5条(C)6条(D)11条.14.设G是5个顶点的完全图,则从G中删去()条边可以得到树.(A)6(B)5(C)10(D)4.15.设图G的相邻矩阵为0110110101110110010111110,则G的顶点数与边数分别为().(A)4,5(B)5,6(C)4,10(D)5,8.三、计算证明题1234561.化简命题公式((PQ)(QR))(PR)2.化简集合公式:((AB)C)(ABC)(ABC)(ABC).3.设一阶逻辑公式:(()(,))(()(,))FxAxBxyyCyzDyz,把F化成前束范式.4.试用克鲁斯卡尔算法求出如下权图的最优支撑树。5.设R和S是集合A={1,2,3,4}上的关系,其中R={(1,1),(1,2),(2,3),(3,4)},S={(3,3),(4,4)}.(1)试写出R和S的关系矩阵;(2)计算R•S,R∪S,R-1,S-1•R-1.6.写出下图的相邻矩阵和关联矩阵:7.设集合A={b,c,d,e},A上的关系R={(b,c),(b,e),(c,d),(d,c),(e,e)},(1)画出R的关系图;(2)写出R的关系矩阵.(3)求出r(R),s(R),t(R).8.设集合A={1,2,3},R和S是A上的两个关系,它们的图表示如下:写出关系R和S,写出R和S的关系矩阵,说明R和S满足关系的哪些特性.9.设T是如下的二叉树,写出对T先根遍历、中根遍历和后根遍历时访问节点的顺序。10.试将公式G=((P∧Q)∨R)P化为主合取范式。11.把下面公式化成前束范式:((,)(()()))xyPxyyQyRx12.设集A={1,2,3},R是集合A上的关系,R={(1,2),(2,1),(2,3)},求r(R),s(r),t(r),并分别画出它们的关系图。13.设命题公式G=(P→Q)∨(P→R),求G的主析取范式和主合取范式。14.设I是如下一个解释:D={1,2}.(1)(2)(1)(2)(1)(2)2210101affFFGG试求下列公式在I下的真值:(1)(()(()))xFxGfa(2)(()())xFaGx15.化简))(()))(((ABBACBA.16.用迪克斯特拉算法求下面有限权图中从A到B的最短路(要求用图示给出求解过程),并计算它们的权值。四、证明题1.利用形式演绎法证明:(),,PQRSPQSR蕴涵.2.设A,B为任意集合,证明:A∩(BC)=(A∩B)(A∩C).3.利用形式演绎法证明:{A→B,S→T,S→B,T}蕴涵A。4.A,B,C为三个任意集合,求证:A-(B-C)=((A-B)-C)∪(A∩C).
本文标题:《离散数学》模拟练习题
链接地址:https://www.777doc.com/doc-2844514 .html