北京化工大学2006——2007学年第二学期。
离散数学（i） 》期末考试试卷。
班级姓名学号分数。
本试卷满分共100分）
一、（填空题，本题共20分，每题2分）
1. 已知集合a是由6个元素组成的集合，那么集合a上可以产生 203 个不同的划分。
2. 已知f(x)= x2+1和g(x)=2x+1均是实数集合r到实数集合r的函数，则复合函数fg = 2x+1)2+1
3. 已知ф为空集，集合a则a的幂集ρ(a
4. 已知命题公式(p↑q)→(r↓t)，则它的对偶式为 (p∨q)∧~r∧f) 。
5. 设s(x): x是大学生，l(x):
x是运动员，a(x, y): x钦佩y，则命题“有些大学生不钦佩运动员”的符号化形式为 x (s(x)∧y(l(y)→~a(x, y)))
6.已知集合a=，集合b=，求a××b =
7. 设p:天下雨，q:天刮风，r:我去书店，则命题“如果天不下雨并且不刮风，我就去书店”的符号化形式为__ p∧~q)→r __
8. 已知集合a=，a上的二元关系r＝，则r-1 =_
9. 设a=，b=，则a到b的一个双射函数为__f: a→b, f(x)=x+10___
10. 设a=，则a上满足自反性的二元关系共有__26=64___个。
二、（判断题，本题共20分，每题2分）
1. （对任意集合a、b、c，若b－a = c－a，则b = c。
2. （已知p、q、r为命题公式，如果p∧r q∧r，则p q。
3. （x (f(y)→g(x)) f(y)→x g(x)。
4. （设a、b、c为任意的三个集合，则(a×b)×c=a×(b×c)。
5. （已知r和s都是集合x上的等价关系，那么r∩s也是集合x上的等价关系。
6. （对任意集合a、b、c、d，都有(a∪b)×(c∪d)=(a×c)∪(b×d)。
7. （函数g: n→n，g定义为g(x)=2x，则g是单射函数。
8. （设r是x上的二元关系，则ix∪r∪r-1是x上的相容关系。
9. （偏序集的子集q如果有上界，则q一定有上确界。
10. （如果f和g是函数，那么f∩g也是函数。
三、计算证明题。
1. 求下面公式的主析取范式和主合取范式：
p→(q∧r))∧p→(~q∧~r))
解： (p→(q∧r))∧p→(~q∧~r))
(~p∨(q∧r))∧p∨(~q∧~r))
((~p∨(q∧r))∧p) ∨p∨(q∧r))∧q∧~r)))
(f∨(q∧r∧p)) p∧~q∧~r)∨(q∧r∧~q∧~r))
(p∧q∧r)∨(p∧~q∧~r)∨f
m111∨m000
(~p∧~q∧~r)∨(p∧q∧r) (主析取范式)
m001∧m010∧m011∧m100∧m101∧m110
(p∨q∨~r)∧(p∨~q∨r)∧(p∨~q∨~r)∧(p∨q∨r) ∧p∨q∨~r)∧(p∨~q∨r) (主合取范式)
2. 证明：对任意集合a、b、c，有。
a－b)∪(b－a) =a∪b)－(a∩b)
证明： (a－b)∪(b－a)
= (a∩~b) ∪b∩~a)
a∩~b)∪b) ∩a∩~b)∪~a))
=((a∪b)∩(b∪b)) a∪~a)∩(b∪~a))
(a∪b) ∩b∪~a)
(a∪b) ∩a∩b)
(a∪b)－(a∩b)
四、(本题共10分，) 设r是整数集合上的二元关系，r当且仅当a=b或a=-b，问r是等价关系吗，若是，给出证明。
解：r是等价关系。
r=① 对ai，由定义可知r，可知r是自反关系。
② 对a,bi，若r，则有a=b或a=-b，因此有b=a或b=-a，可知r，故r是对称关系。
③ 对a,b,ci，若r且r，则有a=b或a=-b，和b=c或b=-c，因此有a=c或a=-c，可知r，故r是传递关系。
由上证明可知r是等价关系。
元素a的等价类[a]r=。
五、(本题共15分) 设为一个偏序集，其中，a=，r是a上的整除关系。
1）画出的哈斯图；
2）求a的最大元、最小元、极大元和极小元；
3）求子集b=的上确界和下确界。
解：=∪ia
cova=1) 的哈斯图。
2) a的最大元不存在，最小元为1，极大元为8，6，9，10，7
极小元为13)b的上确界为6，下确界为1
六、(10分) 用推理规则证明下式：
前提：，结论：.
证明：证明序列如下：
1） y (u(y)∧~v(yp
2）u(c)∧~v(c1), es
3）~(u(c)→v(ct, (2), e22
4） x (f(x)∧g(x))→y(u(y)→v(yp
5）y ( x (f(x)∧g(x))→u(y)→v(yt, (4), e36
6） x (f(x)∧g(x))→u(c)→v(c5), us
7）~ x (f(x)∧g(xt, (3)(6), i9
8）x ~(f(x)∧g(xt, (7), e28
9）x (~f(x)∨~g(xt, (8), e12
10）x (f(x)→~g(xt, (9), e20
七、(10分) 设a=，其上关系r=，s=，求
1）r·s（2）r的自反闭包、对称闭包及传递闭包。
解：（1）r·s =
2）r(r) =ia
s(r)=
t(r)=
07下离散试题B
一。判断题 每小题2分，20 1 设g1是群，如果f是g1到g2的同构，那么同态像f g1 g2是群。2 设a是一代数，若b是a的子代数，且a有零元 那么 也是b的零元。3 设s是半群，若 s是有限子集，则s一定含有等幂元。4 设g是质数阶群，任意都是g的生成元。5 已知群h是群g的子群，h是g的正...
07离散数学试题
答案。一 单项选择题 15 2 30分 1 若p 小李聪明，q 小李怕吃苦，r 小李成绩好 则 小李因为聪明而且不怕吃苦所以成绩好 可符号化为 a p q r b p q r c p q r d p q r 2 下列语句中是命题。a 请把灯打开 b 这个星期天会下雨吗 c x 8 7d 地球外的星球...
离散07期末试题
一 给定代数系统v g，7，其中g 7的运算为模7乘法运算。1 写出7的运算表。2 求其所有的子群。二 通过化主范式的方法证明等价式。三 设二元树有1个度为2的结点，3个度为3的结点，3个顶点度为4，求叶结点的个数？4 通过化主范式的方法判定下面公式的属性。五 设g，是一个群，定义为。证明r是g上的...