离散数学试题及答案一、填空题
1设集合A,B，其中A＝{1,2,3},B={1,2},则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=____________________________,=________________________.
10.设有限集A,B，|A|=m,|B|=n,则||?(A?B)|=_____________________________.
11设A,B,R是三个集合，其中R是实数集，A={x|-1≤x≤1,x?R},B={x|0≤x<2,x?R},则A-B=__________________________,B-A=__________________________,A∩B=
__________________________,.
R12?(A)-?(B)
13.设集合A＝{2,3,4,5,6}，R是A上的整除，则R以集合形式(列举法)记为__________________________________________________________________.
14.设一阶逻辑公式G=?xP(x)??xQ(x)，则G的前束范式是_______________________________.
15.设G是具有8个顶点的树，则G中增加_________条边才能把G变成完全图。
第1页共18页
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}?A2
(B){a}?A
(C)??{{a}}?B?E
(D){{a},1,3,4}?B.
).)。
设集合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的)。
653214(A)下界4
下列语句中，((A)请把门关上(C)x+5>6
(B)上界(C)最小上界(D)以上答案都不对
)是命题。
(B)地球外的星球上也有人(D)下午有会吗？
P(a,a) P(a,b) P(b,a) P(b,b)1 0 1 0
5设I是如下一个解释：D＝{a,b},
则在解释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
第2页共18页
是().(A)恒真的
(B)恒假的
(C)可满足的
(D)前束范式.
)。
8设命题公式G＝?(P?Q)，H＝P?(Q??P)，则G与H的关系是((A)G?H
(B)H?G
(C)G＝H)时A－B＝B.
(C)B?A
(D)A＝B＝?.
(D)以上都不是.
9设A,B为集合，当((A)A＝B
(B)A?B
10设集合A={1,2,3,4},A上的关系R＝{(1,1),(2,3),(2,4),(3,4)},则R具有((A)自反性
(B)传递性
(C)对称性
)。(C)??{a,b,c}
).
(D){a,b}?{a,b,c}(D)以上答案都不对
)。
11下列关于集合的表示中正确的为(
(A){a}?{a,b,c}(B){a}?{a,b,c}
12命题?xG(x)取真值1的充分必要条件是(
(A)对任意x，G(x)都取真值1.(C)有某些x，使G(x0)取真值1.
(B)有一个x0，使G(x0)取真值1.(D)以上答案都不对.
).
13.设G是连通平面图，有5个顶点，6个面，则G的边数是(
(A)9条
(B)5条
(C)6条
(D)11条.
14.设G是5个顶点的完全图，则从G中删去(
(A)615.设图G
(B)5
(C)10
(D)4.
1111?0100??，则
1011??0101?0110???0?1的相邻矩阵为??1??1??1)条边可以得到树.
G的顶点数与边数分别为().
(A)4,5(B)5,6(C)4,10(D)5,8.
三、计算证明题
1.设集合A＝{1,2,3,4,6,8,9,12}，R为整除关系。
(1)画出半序集(A,R)的哈斯图；
第3页共18页
(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},
a3
b2
f(2)3
f(3)2
P(2,2)0
P(2,3)0
P(3,2)1
P(3,3)1
试求(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)
第4页共18页
(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,4.(本题10分)A,B为两个任意集合，求证：A－(A∩B)=(A∪B)－B.
?C→?B,C→D}蕴涵A→D。
参考答案一、填空题1.
2.{3};{{3},{1,3},{2,3},{1,2,3}}.2.
n23.?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≤x<0,x?R};{x|1 第5页共18页
离散数学试题及答案解析
