计算机应用专业《离散数学》模拟试题一一、填空题(每空3分，本题共24分)1设集合A,B，其中A＝{1,2,3},B={1,2},则A-B＝____________________;(A)-(B)＝__________________________.2.设有限集合A,|A|=n,则|(A×A)|=__________________________.3.设集合A={a,b},B={1,2},则从A到B的所有映射是_______________________________________,其中双射的是__________________________.4.已知命题公式G＝(PQ)∧R，则G的主析取范式是_________________________________________________________________________________________.5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为__________，分枝点数为________________.二、选择题(每小题3分，本题共15分)1设集合A，B，当()时，A–B=B.(A)A=B(B)AB(C)BA(D)A=B=.2设集合A={1,2,3,4},A上的关系R＝{(1,1),(2,3),(2,4),(3,4)}，则R具有().(A)自反性(B)传递性(C)对称性(D)以上答案都不对3设命题公式G=(PQ)∧R,H=P(QP)，则G与H的关系是()。(A)GH(B)HG(C)G=h(D)以上都不是4设I是如下一个解释：D＝{a,b},P(a,a)=1,P(a,b)=1,P(b,a)=0,P(b,b)=0,则在解释I下取真值为1的公式是().(A)xyP(x,y)(B)xyP(x,y)(C)xP(x,x)(D)xyP(x,y).5.设G是有5个顶点的完全图，则从G中删去()条边可以得到树.(A)4(B)5(C)6(D)10.三、计算证明题(本题共51分)(12分)设集合A＝{1,2,3,4,6,8,9,12}，R为整除关系。画出半序集(A,R)的哈斯图；写出A的子集B={3,6,9,12}的上界，下界，最小上界，最大下界；写出A的最大元，最小元，极大元，极小元。2.(10分)设I是如下一个解释：D={2,3},abf(2)f(3)P(2,2)P(2,3)P(3,2)P(3,3)32320011试求(1)P(a,f(a))∧P(b,f(b));(2)xyP(y,x).3.(9分)设一阶逻辑公式：G=(xP(x)∨yQ(y))→xR(x)，把G化成前束范式.4.(10分)试用克鲁斯卡尔算法求出如下权图的最优支撑树。5.(10分)设R和S是集合A＝{a,b,c,d}上的关系，其中R＝{(a,a),(a,c),(b,c),(c,d)},S＝{(a,b),(b,c),(b,d),(d,d)}.(1)试写出R和S的关系矩阵；(2)计算R•S,R∪S,R－1,S－1•R－1.四、证明题(本题10分)利用形式演绎法证明：{P→Q,R→S,P∨R}蕴涵Q∨S。