一、证明题（10分）
1)((p∨q)∧(p∧(q∨r)))p∧q)∨(p∧r)t
证明： 左端((p∨q)∧(p∨(q∧r)))p∨q)∧(p∨r))(摩根律)
((p∨q)∧(p∨q)∧(p∨r))∨p∨q)∧(p∨r))(分配律)
((p∨q)∧(p∨r))∨p∨q)∧(p∨r)) 等幂律)
t(代入)2)x(p(x)q(x))∧xp(x)x(p(x)∧q(x))
证明：x(p(x)q(x))∧xp(x)x((p(x)q(x)∧p(x))
x((p(x)∨q(x)∧p(x))
x(p(x)∧q(x))xp(x)∧xq(x)
x(p(x)∧q(x))
二、求命题公式(pq)(p∨q) 的主析取范式和主合取范式（10分）。
解：(pq)(p∨q)(pq)∨(p∨q)
p∨q)∨(p∨q)
p∧q)∨(p∨q)
p∨p∨q)∧(q∨p∨q)
p∨q)m1
m0∨m2∨m3
三、推理证明题（10分）
1)(p(qs))∧r∨p)∧qrs
证明：（1）r 附加前提。
2）r∨p p
3）pt(1)(2)，i
4）p(qs) p
5）qs t(3)(4)，i
6）qp7）st(5)(6)，i
8）rs cp
2) x(p(x)∨q(x))，xp(x)x q(x)
证明：(1)xp(x) p
2)p(ct(1)，us
3)x(p(x)∨q(x)) p
4)p(c)∨q(ct(3)，us
5)q(ct(2)(4)，i
6)x q(xt(5)，eg
四、在边长为1的正方形内任意放置九个点，证明其中必存在三个点，使得由它们组成的三角形（可能是退化的）面积不超过1/8（5分）。
证明：把边长为1的正方形分成四个全等的小正方形，则至少有一个小正方形内有三个点，它们组成的三角形（可能是退化的）面积不超过小正方形的一半，即1/8。
五、已知a、b、c是三个集合，证明a∩(b∪c)=(a∩b)∪(a∩c) （10分）。
证明：∵x a∩（b∪c） x a∧x（b∪c）
x a∧（xb∨xc）
x a∧xb）∨（x a∧xc）
x（a∩b）∨x a∩c
x（a∩b）∪（a∩c）
a∩（b∪c）=（a∩b）∪（a∩c）
六、a=，b=，r=，求其关系矩阵及关系图（10分）。
解：关系矩阵为。
七、设r=，求r(r)、s(r)和t(r)，并作出它们及r的关系图（15分）。
解：r(r)=
s(r)=r2=r5=
r3=r4=
t(r)=八、=是集合a的一个划分，定义r=，则r是a上的等价关系（15分）。
证明：a∈a必有i使得a∈ai，由定义知ara，故r自反。
a，b∈a，若arb ，则a，b∈ai，即b，a∈ai，所以bra，故r对称。
a，b，c∈a，若arb 且brc，则a，b∈ai及b，c∈aj。因为i≠j时ai∩aj=，故i=j，即a，b，c∈ai，所以arc，故r传递。
总之r是a上的等价关系。
九、若f:a→b是双射，则f-1:b→a是双射（15分）。
证明：对任意的x∈a，因为f是从a到b的函数，故存在y∈b，使∈f，∈f-1。所以，f-1是满射。
对任意的x∈a，若存在y1，y2∈b，使得∈f-1且∈f-1，则有∈f且∈f。因为f是函数，则y1=y2。所以，f-1是单射。
因此f-1是双射。
离散数学试题(b卷答案）
一、证明题（10分）
1)(p∧(q∧r))∨q∧r)∨(p∧r)r
证明： 左端(p∧q∧r)∨(q∨p)∧r)
(p∧q)∧r))∨q∨p)∧r)
(p∨q)∧r)∨(q∨p)∧r)
(p∨q)∨(q∨p))∧r
(p∨q)∨(p∨q))∧r
t∧r(置换)r
2)x(a(x)b(x)) xa(x)xb(x)
证明 ：x(a(x)b(x))x(a(x)∨b(x))
xa(x)∨xb(x)
xa(x)∨xb(x)
xa(x)xb(x)
二、求命题公式(p∨(q∧r))(p∧q∧r)的主析取范式和主合取范式（10分）。
证明：(p∨(q∧r))(p∧q∧r)(p∨(q∧r))∨p∧q∧r))
p∧(q∨r)）∨p∧q∧r)
p∧q)∨(p∧r))∨p∧q∧r)
p∧q∧r)∨(p∧q∧r)∨(p∧q∧r))∨p∧q∧r))∨p∧q∧r)
m0∨m1∨m2∨m7
m3∨m4∨m5∨m6
三、推理证明题（10分）
1） c∨d， (c∨d) e， e(a∧b)， a∧b)(r∨s)r∨s
证明：(1) (c∨d)e p
2) e(a∧bp
3) (c∨d)(a∧bt(1)(2)，i
4) (a∧b)(r∨sp
5) (c∨d)(r∨st(3)(4)， i
6) c∨dp
7) r∨st(5)，i
2) x(p(x)q(y)∧r(x))，xp(x)q(y)∧x(p(x)∧r(x))
证明(1)xp(xp
2)p(at(1)，es
3)x(p(x)q(y)∧r(x)) p
4)p(a)q(y)∧r(at(3)，us
5)q(y)∧r(at(2)(4)，i
6)q(yt(5)，i
7)r(at(5)，i
8)p(a)∧r(at(2)(7)，i
9)x(p(x)∧r(xt(8)，eg
10)q(y)∧x(p(x)∧r(xt(6)(9)，i
四、某班有25名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。而6个会打网球的人都会打另外一种球，求不会打这三种球的人数（10分）。
解：a，b，c分别表示会打排球、网球和篮球的学生集合。则|a|=12，|b|=6，|c|=14，|a∩c|=6，|b∩c|=5，|a∩b∩c|=2。
先求|a∩b|。
6=|（a∪c）∩b|=|a∩b）∪（b∩c）|=a∩b）|+b∩c）|-a∩b∩c|=|a∩b）|+5-2，∴|a∩b）|=3。
于是|a∪b∪c|=12+6+14-6-5-3+2=20。不会打这三种球的人数25-20=5。
五、已知a、b、c是三个集合，证明a-(b∪c)=(a-b)∩(a-c) （10分）。
证明：∵x a-（b∪c） x a∧x（b∪c）
x a∧（xb∧xc）
x a∧xb）∧（x a∧xc）
x（a-b）∧x（a-c）
x（a-b）∩（a-c）
a-（b∪c）=（a-b）∩（a-c）
六、已知r、s是n上的关系，其定义如下：r=，s=。求r-1、r*s、s*r、r、s（10分）。
解：r-1=
r*s=s*r=，r=，s=
七、设r=，求r(r)、s(r)和t(r) （15分）。
解：r(r)=
s(r)=r2= r5=
r3=r4=
t(r)=八、证明整数集i上的模m同余关系r=是等价关系。其中，xy(mod m)的含义是x-y可以被m整除（15分）。
证明：1）x∈i，因为（x-x）/m=0，所以xx(mod m)，即xrx。
2）x，y∈i，若xry，则xy(mod m)，即（x-y）/m=k∈i，所以（y - x）/m=-k∈i，所以yx(mod m)，即yrx。
3）x，y，z∈i，若xry，yrz，则（x-y）/m=u∈i，（y-z）/m=v∈i，于是（x-z）/m=（x-y+y-z）/m=u+v ∈i，因此xrz。
离散数学试题 A卷答案
一 10分 某项工作需要派a b c和d 4个人中的2个人去完成，按下面3个条件，有几种派法？如何派？1 若a去，则c和d中要去1个人 2 b和c不能都去 3 若c去，则d留下。解设a a去工作 b b去工作 c c去工作 d d去工作。则根据题意应有 acd，b c cd必须同时成立。因此。acd...
离散数学试题A卷
2010 至 2011 学年第 2 学期 课程名称 离散数学b考试时间 110 分钟 课程 7304159试卷总分 100 分。考试形式 闭卷学生自带普通计算器 否 一 填空题 每空2分，共30分 1 设e a b c 则 a b c p a p cab a c2 设m x x是人，d x x是长寿...
离散数学试题A卷
2010 至 2011 学年第 2 学期 课程名称 离散数学b考试时间 110 分钟 课程 7304159试卷总分 100 分。考试形式 闭卷学生自带普通计算器 否 一 填空题 每空2分，共30分 1 设e a b c 则 a b c p a p cab a c2 设m x x是人，d x x是长寿...