1
y
2
>∈R2
。
试证明：
R是A×B上的
等价关系。
（10分）
3.用伯恩斯坦定理证明（0,1]和（a,b）等势。
（10分）
2
4.设R是集合A上的等价关系，A的元素个数为n，R作为集合有s个元素，若A关于R的商集A/R有r个元素，证明：
rs≥n。
（10分）
三、应用题（10分）
在一个道路上连接有8个城市，分别标记为a,b,c,d,e,f,g,h。
城市之间的直接连接的道路是单向的，有a→b,a→c,b→g,g→b,c→f,f→e,b→d,d→f.对每一个城市求出从它出发所能够到达的所有其他城市。
离散数学考试题答案
一、命题符号化（共6小题，每小题3分，共计18分）
1.用命题逻辑把下列命题符号化
a）设P表示命题“上午下雨”，Q表示命题“我去看电影”，R表示命题“在家里读书”，S表示命题“在家看报”，命题符号化为：
（P⇄Q）（P⇄RS）
b）
c）
2.
a）
b）
设P表示命题“我今天进城”，Q表示命题“天下雨”，命题符号化为：
Q→P或P→Q设P表示命题“你走”，Q表示命题“我留下”，命题符号化为：
Q→P
用谓词逻辑把下列命题符号化
设R（x）表示“x是实数”，Q（x）表示“x是有理数”，命题符号化为：
x（R（x）Q（x））或x（R（x）→Q（x））
设R（x）表示“x是实数”，E（x,y）表示“x=y”,f（x,y）=xy,命题符号化为：
x（R（x）E（x,0）→y（R（y）E（f（x,y）,1））））
c）设F（f）表示“f是从A到B的函数”,A（x）表示“x∈A”,B（x）表示“x∈B”,E（x,y）表示“x=y”,命题符号化为：
F（f）⇄a（A（a）→b（B（b）E（f（a）,b）c（S（c）E（f（a）,c）→E（a,b））））
二、简答题（共6道题，共32分）
1.（P→（Q→R））（R→（Q→P））（PQR）（PQR）
（（PQR）→（PQR））（（PQR）→（PQR））.
（（PQR）（PQR））（（PQR）（PQR））
（PQR）（PQR）这是主合取范式
公式的所有成真赋值为000,001,010,100,101,111,故主析取范式为
（PQR（PQR（PQR（PQR（PQR（PQR2.a）Tb）F
3.x（F（x）→G（x））→（xF（x）→xG（x））x（F（x）→G（x））→（yF（y）→zG（z））
x（F（x）→G（x））→yz（F（y）→G（z））xyz（（F（x）→G（x））→（F（y）→G（z）））4.a）真命题。
因为（AB）－C=（AB）~C=（A~C）（B~C）=（A-C）（B-
C）
b）真命题。
因为如果f是从集合A到集合B的入射函数，则|ranf|=|A|，且ranfB,故命题成立。
5.a）52b）5!
=120
6.B的最小元是b，无最大元、极大元是d和e、极小元是b、上界集合是{g}、下界集合是{a,b}、上确界是g、下确界是b.
7.K[S]=n;K[P（S）]=2;K[N]=
0
K[N]=
0
K[P（N）]=;K[R]=,K=[R×R]=
N
x
K[{0,1}]=
三、证明题（共3小题，共计40分）
1.a）证
（1）BP（附加条件）
（2）B→（A∧S）P
（3）A∧ST
（1）
（2）I（4）AT（3）I（5）A→（B∧C）P
（6）B∧CT（4）（5）I（7）CT（6）I（8）（E→F）→CP
（9）（E→F）T（7）（8）I（10）E∧FT（9）E（11）ET（10）I（12）B→ECP
b）证
（1）xR（x）P
（2）R（c）ES
（1）
（3）x（Q（x）∨R（x））P
（4）Q（c）∨R（c）US（3）
（5）Q（c）T
（2）（4）I（6）x（P（x）→Q（x））P
（7）P（c）→Q（c）US（6）
（8）P（c）T（5）（7）I（9）xP（x）EG（8）
2.证任取,
∈A×Bx∈Ay∈B∈R1
∈R2
<,>∈R，故R是自反的
任取<,>,
<,>∈R∈R1∈R2∈R1∈R2<,>∈R.故R是对称的。
任取<,>,<,>∈R
<,>,<,>∈R∈R1
∈R2
∈R1
∈R2
（
∈R1
∈R1
）（∈R2
∈R2
）R1
∈R2
<,>∈R,故R
是传递的。
综上所述R是A×B上的等价关系。
3.证构造函数f：
（0,1]→（a,b），f（x）=
ab
22
显然f是入射函数
构造函数g:
（a,b）→（0,1]，g（x）故（0,1]和（a,b）等势。
xa
ba
显然g是入射函数，
由于
m1m2r
m
2
r
m1m2r
m
r
2
，所以
rr
2
2
4.证
设商集A/R的r个等价类的元素个数分别为m1,m2
…,mr
，由于一个划分对应一个
等价关系，m1
+m2
+…+mr
=n，m1m2
mrs
由于
22
12
r
m
2
r
m1
m
2
r
m
r
2
（r个数的平方的平均值大于等于
这r个数的平均值的平方），所以
sn
rr
2
2
，即rsn
2
四、应用题（10分）
解把8个城市作为集合A的元素，即A={a,b,c,d,e,,f,g,h}，在A上定义二元关系R，∈R当且仅当从x到y有直接连接的道路，即R={,,,,,,,}那么该问题即变为求R的传递闭包。
利用Warshal算法，求得t（R）=
0
0
0
0
0
0
0
0
11111100011110000110000011000000000000100010111100000000
那么从城市x出发能到达的城市为（t（R）I
A
）[{x}]{y|x,yt（R）xy}，
故有（t（R）I
A
）[{a}]{b,c,d,e,f,g}
（t（R）I
（t（R）I
（t（R）I
（t（R）I
（t（R）I
A
A
A
A
A
）[{b}]{d,e,f,g}）[{c}]{e,f}
）[{d}]{e,f}
）[{f}]{e}
）[{g}]{b,d,e,f}
（t（R）I
A
）[{e}]（t（R）I
A
）[{e}]
离散考试模拟试题及答案2
一、填空题
1设集合A,B，其中A＝{1,2,3},B={1,2},则A-B＝____________________;（B）＝__________________________.
（A）-
2
2.设有限集合A,|A|=n,则|（A×A）|=__________________________.
3.设集合A={a,b},B={1,2},则从A到B的所有映射是_______________________________________,其中双射的是__________________________.
4.
已知命题公式
G＝（PQ）∧R，则
G的主析取范式是
_______________________________
__________________________________________________________.
5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为__________，分枝点数为________________.
6设A、B为两个集合,A={1,2,4},B={3,4},则从AB＝_________________________;AB＝_________________________;A－B＝_____________________.
7.设R是集合A上的等价关系，则R所具有的关系的三个特性是
______________________,________________________,
_______________________________.
8.设命题公式G＝（P（QR）），则使公式G为真的解释有
__________________________，_____________________________,
__________________________.
9.设集合A＝{1,2,3,4},A上的关系R1
={（1,4）,（2,3）,（3,2）},R1
={（2,1）,（3,2）,（4,3）},则
R1R2=________________________,R2R1=____________________________,
R1=________________________.
10.设有限集A,B，|A|=m,|B|=n,则||（AB）|=_____________________________.
11设A,B,R是三个集合，其中R是实数集，A={x|-1≤x≤1,xR},B={x|0≤x<2,xR},则A-B=__________________________,B-A=__________________________,
A∩B=__________________________,.
13.设集合A＝{2,3,4,5,6}，R是A上的整除，则R以集合形式（列举法）记为__________________________________________________________________.
14.设一阶逻辑公式G=xP（x）xQ（x），则G的前束范式是_______________________________.
13.设G是具有8个顶点的树，则G中增加_________条边才能把G变成完全图。
13.设谓词的定义域为{a,b},将表达式xR（x）→xS（x）中量词消除，写成与之对应的命题公
式是__________________________________________________________________________.
2
17.设集合A＝{1,2,3,4}，A上的二元关系R＝{（1,1）,（1,2）,（2,3）},S＝{（1,3）,（2,3）,（3,2）}。
则RS＝_____________________________________________________,
R＝______________________________________________________.
二、选择题
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
3
设集合A={1,2,3},A上的关系R＝{（1,1）,（2,2）,（2,3）,（3,2）,（3,3）}，则R不具备（）.（A）自反性（B）传递性（C）对称性（D）反对称性
设半序集（A,≤）关系≤的哈斯图如下所示，若A的子集B={2,3,4,5},则元素6为B的
（）。
（A）下界（B）上界（C）最小上界（D）以上答案都不对4下列语句中，（）是命题。
（A）请把门关上（B）地球外的星球上也有人
（C）x+5>6（D）下午有会吗？
6
5
34
2
5设I是如下一个解释：
D＝{a,b},
P（a,a）P（a,b）P（b,a）P（b,b）1010
1
则在解释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）有一个x
0
，使G（x
0
）取真值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的相邻矩阵为
0
1
1
1
1
11110100101101010110
，则G的顶点数与边数分别为（）.
－1－1－1
（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）的哈斯图；
（2）写出A的子集B={3,6,9,12}的上界，下界，最小上界，最大下界；（3）写出A的最大元，最小元，极大元，极小元。
2.
3.
4.
设集合A＝{1,2,3,4}，A上的关系R＝{（x,y）|x,yA且xy},求
（1）画出R的关系图；
（2）写出R的关系矩阵.
设R是实数集合，,,是R上的三个映射，（x）=x+3,（x）=2x,（x）＝x/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）xyP（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,S•R.
四、证明题
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。
mn
4.（本题10分）A,B为两个任意集合，求证：
A－（A∩B）=（A∪B）－B.
参考答案
一、填空题
1.{3};{{3},{1,3},{2,3},{1,2,3}}.
2.
2.
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
升级会员 