离散数学(一)练习题与答案
1-5 题：× × × ×√
6-10 题：× ×√√√
11-15题：× ×√ ×√
16-17题：√ ×
二、单项选择题
1 A C
2 C
3 C 4. B 5 A
6 B
7 B
8 C
9 B 10 B
11 D 12 A 13 C 14 C
三、填空题
1 ┐Q→P 或┐P→Q，Q→P
2 A B=｛{a,b}, {a},{b},{c}｝，A B=｛｛c｝｝，
A B
-=｛{a,b}｝，A B
⊕=｛{a,b},{a},{b}｝。
3．{}
ΦΦ=Φ，{,{}}
ΦΦ-Φ={Φ,{ Φ}}，
ΦΦ={Φ}。
{,{}}{}
ΦΦ-Φ={{Φ}}，{}
4．A={1,2,3,……,12}，R是A上的整除关系，子集B={2,4,6}。
则B的最大元是：无，最小元是：2，
极大元是：4，6，极小元是：2，
上界是：12，下界是：2，
上确界是：12，下确界是：2。
5. g g g
6 R, T
7. 略
8．极大元：{a,b}, {b,c}，最大元：无，上界：{a,b,c}，下确界：Φ。
( )1．设A ，B ，C 为任意的命题公式，若A C B C ∨?∨,则A B ?。
( )2．公式P Q ∧是合取范式，不是析取范式。
( )3．公式()()P Q P Q ?∨∧→与公式()P Q R →∧等价。
( )4．()(()())()()()()x A x B x x A x x B x ?∨??∨?。
( )5．谓词公式()()((,)(,))x y P x y Q y z ??∨中，x,y 是约束变元，z 是自由变元。
( )6．对谓词公式()(()(,))(,)x P y Q x y R x y ?→∧中的自由变元进行代入后得到
公式()(()(,))(,)x P z Q x z R x y ?→∧。
( )7．对谓词公式()(()(,))(,)x P x Q x y R x y ?→∧中的约束变元进行换名后得到公
式()(()(,))(,)y P y Q y y R x y ?→∧。
( )8．{}{,{}}Φ∈ΦΦ，且{}{,{}}Φ?ΦΦ。
( )9．对任意的集合A,B,C,D.若,A C B D ??，则A B C D ???。
( )10．设A,B,C 是任意的集合，则()()()A B C A B A C ⊕=⊕。
( )11．集合A={a,b,c}上的任何二元关系R 都不可能既是对称的，又是反对称
的。
( )12．若R 和S 是集合A 上的任意的两个反自发的关系，则R ○S 也是反自反
的。
( )13．设
成员。
( )14．R 是等价关系一定是相容关系，反之亦然。
( )15．当X 和Y 都是有限集合时，若f :X →Y 是单射函数，则|X|≤|Y|。
( )16．设N 是自然数集合，f : N →N,且f (j )=j 2+2,则f 是单射函数。
( )17．设X={1,2,3,4}, f 是X 上的关系且f ={<1,4>,<2,1>,<2,3>,<3,2>,
<4,4>}，则f 是函数。
二、单项选择题
1．给定命题公式()P Q R ∨∧，则它的成真指派为( )，
成假指派为( )。
A ．111, 011, 100, 101,110 B. 111, 011
C. 000, 010, 001
D. 000
2．给定命题公式：()()P Q P R ?∨∧→与之等价的是( )。
A ．()P Q R →?∧ B. ()P Q R →∨
C. ()P Q R →∧
D. ()P Q R ?→∧
3．命题：“所有马都比某些牛跑得快” 的符号化公式为( )。
假设：H(x )：x 是马；C(x )：x 是牛；F(x,y )：x 跑得比y 快。
A. ()(()()(()(,)))x H x y C y F x y ?∧?∧
B. ()(()()(()(,)))x H x y C y F x y ?→?→
C. ()(()()(()(,)))x H x y C y F x y ?→?∧
D. ()()(()(()(,)))y x H x C y F x y ??→→
4．给定命题公式：()(())x A x B ?→与之等价的公式是( )。
A ．()()x A x
B ?→ B. ()()x A x B ?→
C. ()()B x A x ?→?
D. ()()B x A x ?→??
5．对任意的集合A,B,C,下述论断正确的是（ ）。
A ．若,A
B B
C ∈?，则A C ∈. B. 若,A B B C ∈?，则A C ?.
C. 若,A B B C ?∈，则A C ∈.
D. 若,A B B C ?∈，则A C ?.
6．下列选项错误的是（ ）。
A. Φ?Φ
B. Φ∈Φ
C. {}Φ?Φ
D. {}Φ∈Φ
7．设A={1,{1}}, P(A)为A 的幂集，下列选项错误的是（ ）。
A ．{1}()P A ∈ B. {1}()P A ? C. {{1}}()P A ∈ D.{{1}}()
P A ? 8．集合A={1,2,3,6}, A 上的整除关系具有的性质是（ ）
A ．自反的，对称的，可传递的
B. 反自反的，对称的，可传递的
C. 自反的，反对称的，可传递的
D. 反自反的，反对称的，可传递的
9．关系R 的关系矩阵1010010100100001R M ??
??
??=??????
, 则关系R 具有的性质是 (
)。 A ．自反的，对称的，可传递的
B ．自反的，反对称的，可传递的
C ．自反的，对称的
D ．都不是
10．函数的复合运算满足（ ）。
A ．交换律 B.结合律 C.等幂律 D.分配律
11．若g ○f 是双射函数，则（ ）。
A ．f ，g 必是满射 B.f ，g 必是单射
C ．f 必是满射, g 必是单射 D. f 必是单射, g 必是满射
12．设N 是自然数集合，R 是实数集合，f : N →R ，且给定10()log f j j =，
则（ ）。
A ．f 是单射 B.f 是满射 C ．f 是双射 D.都不是
13．设A B -=Φ，则有（ ）。
A ．
B =Φ B. B ≠Φ
C ．A B ? D. B A ?
14．给定公式()(,)()()x F y x y G y ?→?，它的前束范式是（ ）。
A ．()()((,)())x y F y x G y ??→ B. ()()((,)())x y F z x G y ??→
C ．()()((,)())x y F z x G y ???∨ D. ()()((,)())x y F z x G y ???∨
三、填空题
1．给定命题1：“除非你努力，否则你将失败”（假设Q ：你努力，P ：你将失败）；命题2：“只有睡觉才能恢复疲劳”（假设P ：睡觉，Q ：恢复疲劳）。则命题1符号
化为_________________， 命题2符号化为___________________。
2．集合A={{a,b},{c}}，B={{a},{b},{c}}, 试写出：
A B =___________________，A B =___________________，
A B -=___________________，A B ⊕=___________________。
3．确定以下各式：{}ΦΦ=____________，{,{}}ΦΦ-Φ=____________，
{,{}}{}ΦΦ-Φ=________________，{}ΦΦ=________________。
4．A={1,2,3,……,12}，R 是A 上的整除关系，子集B={2,4,6}。
则B 的最大元是____________，最小元是____________，
极大元是____________，极小元是____________，
上界是______________，下界是______________，
上确界是____________，下确界是____________。
5．设A={1,2,3}，f, g, h 均为A 到A 的函数，即f , g , h ：A →A ，其中
f={<1,1>,<2,1>,<3,1>}, g={<1,1>,<2,3>,<3,2>}, h={<1,3>,<2,1>,<3,1>}，则__________是单射，__________是满射，__________是双射。
6．设A={a,b,c}, B={x,y,z}，R，S，T：A→B的关系，且R={
函数。
7．关系R是自反的，当且仅当在关系矩阵中___________________________，在关系图中____________________________________________________；
关系R是反自反的，当且仅当在关系矩阵中_________________________，在关系图中___________________________________________________；
关系R是对称的，当且仅当在关系矩阵中__________________________，
在关系图中__________________________________________________。
8．设A={a,b,c}上偏序集(),
，其中P(A)是A的幂集，则幂集P(A)的
P A
子集{,{},{},{,},{
B a b a b b c
=Φ的极大元是______________，最大元是_______________，上界是______________，下确界是______________。
四、简答题
1. 将下列命题符号化
(1) 不存在两片完全相同的叶子。
(2) 发光的不都是金子。
(3)尽管有人聪明，但未必一切人都聪明。
2. 利用两种方法证明下列蕴涵式：
?∧→??.
()
Q P Q P
3.利用求主合取范式证明下列公式等价性：
→∧→?→∧
P Q P R P Q R
()()()
4．设A,B和C是集合，则回答下列问题：
⊕=⊕, 是否必须B=C?
若A B A C
五、综合题
1 应用CP规则证明：R→S可以从前提P→(Q→S),┐R∨P和Q推出。
2.符号化下列命题，并给出构造推理证明
每位资深名士或是中科院院士或是国务院参事。所有的资深名士是政协委员。张大为是资深名士，但他不是中科院院士，因此有的政协委员是国务院参事。
六R是整数集合Z上的二元关系，对任意m,n∈Z,
(1)证明R是等价关系。
(2)求R的等价类。
七.设S为X上的偏序关系，T为Y上的偏序关系，若<