离散数学练习题(含答案)
- 格式：doc
- 大小：309.00 KB
- 文档页数：7
易自考
02324# 离散数学试题 第 1 页 共4页 离散数学试题
第一部分 选择题
一、单项选择题
1．下列是两个命题变元p，q的小项是（ C ）
A．p∧┐p∧q B．┐p∨q
C．┐p∧q D．┐p∨p∨q
2．令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（ D ）
A．p→┐q B．p∨┐q
C．p∧q D．p∧┐q
3．下列语句中是命题的只有（ A ）
A．1+1=10 B．x+y=10
C．sinx+siny<0 D．x mod 3=2
4．下列等值式不正确的是（ C ）
A．┐(x)A(x)┐A
B．(x)(B→A(x))B→(x)A(x)
C．(x)(A(x)∧B(x))(x)A(x)∧(x)B(x)
D．(x)(y)(A(x)→B(y))(x)A(x)→(y)B(y)
5．谓词公式(x)P(x,y)∧(x)(Q(x,z)→(x)(y)R(x,y,z)中量词x的辖域是（ C ）
A．(x)Q(x,z)→(x)(y)R(x,y,z))
B．Q(x,z)→(y)R(x,y,z)
C．Q(x,z)→(x)(y)R(x,y,z)
D．Q(x,z)
6．设A={a,b,c,d}，A上的等价关系R={
A．{{a},{b,c},{d}} B．{{a,b},{c},{d}}
C．{{a},{b},{c},{d}} D．{{a,b},{c,d}}
7．设A={Ø}，B=P(P(A))，以下正确的式子是（ A ）
A．{Ø,{Ø}}∈B B．{{Ø,Ø}}∈B
C．{{Ø},{{Ø}}}∈B D．{Ø,{{Ø}}}∈B
8．设X，Y，Z是集合，一是集合相对补运算，下列等式不正确的是（ A ）
A．(X-Y)-Z=X-(Y∩Z)
B．(X-Y)-Z=(X-Z)-Y
C．(X-Y)-Z=(X-Z)-(Y-Z)
D．(X-Y)-Z=X-(Y∪Z)
9．在自然数集N上，下列定义的运算中不可结合的只有（ D ）
A．a*b=min(a,b)
B．a*b=a+b
C．a*b=GCD(a,b)(a,b的最大公约数) 易自考
02324# 离散数学试题 第 2 页 共4页 D．a*b=a(mod b)
10.设R和S是集合A上的关系,R∩S必为反对称关系的是( A )
A．当R是偏序关系,S是等价关系; B．当R和S都是自反关系;
C．当R和S都是等价关系; D．当R和S都是传递关系
11.设R是A上的二元关系,且R·RR,可以肯定R应是( D )
A．对称关系; B．全序关系; C．自反关系; D．传递关系
第二部分 非选择题
二、填空题
1．设论域是{a,b,c}，则(x)S(x)等价于命题公式 S(a)∧S(b)∧S(c) ；(x)S(x)等价于命题公式 S(a)∨S(b) ∨S(c) 。
2．设R为A上的关系，则R的自反闭包r(R)= _R∪AI_ ，对称闭包s(R)= _R∪R~ 。
3．某集合A上的二元关系R具有对称性，反对称性，自反性和传递性，此关系R是 AI_ ，其关系矩阵是 只有主对角线上元素为1 。
三、计算题
1．（4分）如果论域是集合{a,b,c}，试消去给定公式中的量词：)0yx)(x)(y(。
2．用等值演算求下面公式的主析取范式。)()(PQQP
易自考
02324# 离散数学试题 第 3 页 共4页 3．用等值演算法求公式)()(QPQP的主合取范式。
4．（6分）在偏序集
5．设集合A={1,2,3,4,5},A上的划分为＝{{1,2,3},{4,5}},试求：
1) 写出划分诱导的等价关系R；
2) 写出关系矩阵RM；
3) 画出关系图。
易自考
02324# 离散数学试题 第 4 页 共4页
6. 设A＝{a，b，c，d}，R是A上的二元关系，且R＝{
解 r(R)＝R∪IA＝{
s(R)＝R∪R-1＝{
R2＝{
R3＝{
R4＝{
t(R)＝iiR1＝{
四、证明题
1．设R和S是二元关系，证明111)(SRSR 易自考
02324# 离散数学试题 第 5 页 共4页
2．设A={a,b,c},R={(a,a),(a,b),(b,c)},验证rs(R)=sr(R)。
3．设R是A上的二元关系，试证：R是传递的当且仅当RR2，其中2R表示RR•。
4．证明下列结论：
（1）RQPRQP
（2）DADCBCABA),(),()(
解：（1）1 P∧Q P附加前提
2 P T，1，I2
3 P∨Q T，2，I1 易自考
02324# 离散数学试题 第 6 页 共4页 4 P∨Q→R P
5 R T，3，4，I3
6 P∧Q→R CP
（2）1 D P假设前提
2 D∨A P
3 A T，1，2，I5
4 (A→B)∧(A→C) P
5 A→B T，4，I2
6 B T，3，5，I3
7 A→C T，4，I2
8 C T，3，7，I3
9 B∧C T，6，8 ，合取式
10 （B∧C） P
11 （B∧C）∧（B∧C） T，9，10，合取式，矛盾
5. 已知R和S是非空集合A上的等价关系，试证：1）R∩S是A上的等价关系；2）对a∈A，[a]R∩S=[a]R∩[a]S。
解：x∈A，因为R和S是自反关系，所以
x、y∈A，若
x、y、z∈A，若
总之R∩S是等价关系。
2）因为x∈[a]R∩S
所以[a]R∩S=[a]R∩[a]S。
五、应用题 易自考
02324# 离散数学试题 第 7 页 共4页 1．所有的主持人都很有风度。李明是个学生并且是个节目主持人。因此有些学生很有风度。请用谓词逻辑中的推理理论证明上述推理。（论述域：所有人的集合）
