《离散数学》试题及答案

一、填空题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的总度数为__________，分枝点数为________________.6设A、B为两个集合,A={1,2,4},B={3,4},则从AB＝_________________________;AB＝_________________________;A－B＝_____________________.7.设R是集合A上的等价关系，则R所具有的关系的三个特性是______________________,________________________,_______________________________.8.设命题公式G＝(P(QR))，则使公式G为真的解释有__________________________，_____________________________,__________________________.9.设集合A＝{1,2,3,4},A上的关系R1={(1,4),(2,3),(3,2)},R1={(2,1),(3,2),(4,3)},则R1R2=________________________,R2R1=____________________________,R12=________________________.10.设有限集A,B，|A|=m,|B|=n,则||(AB)|=_____________________________.11设A,B,R是三个集合，其中R是实数集，A={x|-1≤x≤1,xR},B={x|0≤x2,xR},则A-B=__________________________,B-A=__________________________,A∩B=__________________________,.13.设集合A＝{2,3,4,5,6}，R是A上的整除，则R以集合形式(列举法)记为__________________________________________________________________.14.设一阶逻辑公式G=xP(x)xQ(x)，则G的前束范式是_______________________________.15.设G是具有8个顶点的树，则G中增加_________条边才能把G变成完全图。16.设谓词的定义域为{a,b},将表达式xR(x)→xS(x)中量词消除，写成与之对应的命题公式是__________________________________________________________________________.17.设集合A＝{1,2,3,4}，A上的二元关系R＝{(1,1),(1,2),(2,3)},S＝{(1,3),(2,3),(3,2)}。则RS＝_____________________________________________________,R2＝______________________________________________________.二、选择题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.三、计算证明题1.设集合A＝{1,2,3,4,6,8,9,12}，R为整除关系。123456(1)画出半序集(A,R)的哈斯图；(2)写出A的子集B={3,6,9,12}的上界，下界，最小上界，最大下界；(3)写出A的最大元，最小元，极大元，极小元。2.设集合A＝{1,2,3,4}，A上的关系R＝{(x,y)|x,yA且xy},求(1)画出R的关系图；(2)写出R的关系矩阵.3.设R是实数集合，,,是R上的三个映射，(x)=x+3,(x)=2x,(x)＝x/4,试求复合映射•，•,•,•，••.4.设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).5.设集合A＝{1,2,4,6,8,12}，R为A上整除关系。(1)画出半序集(A,R)的哈斯图；(2)写出A的最大元，最小元，极大元，极小元；(3)写出A的子集B={4,6,8,12}的上界，下界，最小上界，最大下界.6.设命题公式G=(P→Q)∨(Q∧(P→R)),求G的主析取范式。7.(9分)设一阶逻辑公式：G=(xP(x)∨yQ(y))→xR(x)，把G化成前束范式.9.设R是集合A={a,b,c,d}.R是A上的二元关系,R={(a,b),(b,a),(b,c),(c,d)},(1)求出r(R),s(R),t(R)；(2)画出r(R),s(R),t(R)的关系图.11.通过求主析取范式判断下列命题公式是否等价：(1)G=(P∧Q)∨(P∧Q∧R)(2)H=(P∨(Q∧R))∧(Q∨(P∧R))13.设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.四、证明题1.利用形式演绎法证明：{P→Q,R→S,P∨R}蕴涵Q∨S。2.设A,B为任意集合，证明：(A-B)-C=A-(B∪C).3.(本题10分)利用形式演绎法证明：{A∨B,C→B,C→D}蕴涵A→D。4.(本题10分)A,B为两个任意集合，求证：A－(A∩B)=(A∪B)－B.参考答案一、填空题1.{3};{{3},{1,3},{2,3},{1,2,3}}.2.22n.3.1={(a,1),(b,1)},2={(a,2),(b,2)},3={(a,1),(b,2)},4={(a,2),(b,1)};3,4.4.(P∧Q∧R).5.12,3.6.{4},{1,2,3,4},{1,2}.7.自反性；对称性；传递性.8.(1,0,0),(1,0,1),(1,1,0).9.{(1,3),(2,2),(3,1)};{(2,4),(3,3),(4,2)};{(2,2),(3,3)}.10.2mn.11.{x|-1≤x0,xR};{x|1x2,xR};{x|0≤x≤1,xR}.12.12;6.13.{(2,2),(2,4),(2,6),(3,3),(3,6),(4,4),(5,5),(6,6)}.14.x(P(x)∨Q(x)).15.21.16.(R(a)∧R(b))→(S(a)∨S(b)).17.{(1,3),(2,2)};{(1,1),(1,2),(1,3)}.二、选择题1.C.2.D.3.B.4.B.5.D.6.C.7.C.8.A.9.D.10.B.11.B.13.A.14.A.15.D三、计算证明题1.(1)(2)B无上界，也无最小上界。下界1,3;最大下界是3.(3)A无最大元，最小元是1，极大元8,12,90+;极小元是1.2.R={(1,1),(2,1),(2,2),(3,1),(3,2),(3,3),(4,1),(4,2),(4,3),(4,4)}.124836129124836129(1)(2)1000110011101111RM3.(1)•＝((x))＝(x)+3＝2x+3＝2x+3.(2)•＝((x))＝(x)+3＝(x+3)+3＝x+6,(3)•＝((x))＝(x)+3＝x/4+3,(4)•＝((x))＝(x)/4＝2x/4=x/2,(5)••＝•(•)＝•+3＝2x/4+3＝x/2+3.4.(1)P(a,f(a))∧P(b,f(b))=P(3,f(3))∧P(2,f(2))=P(3,2)∧P(2,3)=1∧0=0.(2)xyP(y,x)=x(P(2,x)∨P(3,x))=(P(2,2)∨P(3,2))∧(P(2,3)∨P(3,3))=(0∨1)∧(0∨1)=1∧1=1.5.(1)(2)无最大元，最小元1，极大元8,12;极小元是1.(3)B无上界，无最小上界。下界1,2;最大下界2.6.G=(P→Q)∨(Q∧(P→R))123424168122416812=(P∨Q)∨(Q∧(P∨R