《离散数学》模拟练习题

离散数学模拟练习题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-1S=__________________________.3.命题公式G=（PQ）R，则解释（P，Q，R）使G的真值为。4.设谓词的定义域为{,}ab，将表达式)()(xxSxxR中的量词消除，写成与之等价的命题公式是。5.设有限集A,B，|A|=m,|B|=n,则笛卡儿积AB的子集个数有_____________________________个.6设A、B为两个集合,A={1,2,4},B={3,4},则从(A)(B)＝_________________________;AB＝_________________________.7.求公式(PQ)(PR)的主析取范式_____________________________________________________________________________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)}，则sr=____________________。13.设命题公式G=（PQ）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}}BE(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)xyP(x,y)(B)xyP(x,y)(C)xP(x,x)(D)xyP(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),则一阶逻辑公式GH是().(A)恒真的(B)恒假的(C)可满足的(D)前束范式.8设命题公式G＝(PQ)，H＝P(QP)，则G与H的关系是()。(A)GH(B)HG(C)G＝H(D)以上都不是.9设A,B为集合，当()时A－B＝B.(A)A＝B(B)AB(C)BA(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.化简命题公式((PQ)(QR))(PR)2.化简集合公式：((AB)C)(ABC)(ABC)(ABC).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.把下面公式化成前束范式：((,)(()()))xyPxyyQyRx12.设集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)(()())xFaGx15.化简))(()))(((ABBACBA.16.用迪克斯特拉算法求下面有限权图中从A到B的最短路(要求用图示给出求解过程)，并计算它们的权值。四、证明题1.利用形式演绎法证明：(),,PQRSPQSR蕴涵.2.设A,B为任意集合，证明：A∩(BC)=(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).