一、（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)∧(b∧c)∧(cd)
a∨(c∧ d)∨(c∧d))∧b∨c)∧(c∨d)
a∨(c∧ d)∨(c∧d))∧b∧c)∨(b∧d)∨c∨(c∧d))
a∧b∧c)∨(a∧b∧d)∨(a∧c)∨(a∧c∧d)
(c∧ d∧b∧c)∨(c∧ d∧b∧d)∨(c∧ d∧c)∨(c∧ d∧c∧d)
(c∧d∧b∧c)∨(c∧d∧b∧d)∨(c∧d∧c)∨(c∧d∧c∧d)
f∨f∨(a∧c)∨f∨f∨(c∧ d∧b)∨f∨f∨(c∧d∧b)∨f∨(c∧d)∨f
a∧c)∨(b∧c∧ d)∨(c∧d∧b)∨(c∧d)
a∧c)∨(b∧c∧ d)∨(c∧d)
t故有三种派法：b∧d，a∧c，a∧d。
二、（15分）在谓词逻辑中构造下面推理的证明：某学术会议的每个成员都是专家并且是工人，有些成员是青年人，所以，有些成员是青年专家。
解：论域：所有人的集合。()是专家； (是工人； (是青年人；则推理化形式为：
下面给出证明：
1p2) (ct(1)，es
3p4) (c)∧(ct(3)，us
5) (ct(4)，i
6) (c)∧(ct(2)(5)，i
7t(6) ，eg
三、（10分）设a、b和c是三个集合，则ab(ba)。
证明：abx(x∈a→x∈b)∧x(x∈b∧xa)x(xa∨x∈b)∧x(x∈b∧xa)
x(x∈a∧xb)∧x(xb∨x∈a)x(x∈a∧xb)∨x(x∈a∨xb)
x(x∈a∧xb)∧x(x∈a∨xb))(x(x∈a∧xb)∧x(x∈b→x∈a))
ba)。四、（15分）设a＝，r是a上的二元关系，且r＝，求r(r)、s(r)和t(r)。
解 r(r)＝r∪ia＝
s(r)＝r∪r－1＝
r2＝r3＝
r4＝＝r2
t(r)＝ri＝。
五、（10分）r是非空集合a上的二元关系，若r是对称的，则r(r)和t(r)是对称的。
证明对任意的x、y∈a，若xr(r)y，则由r(r)＝r∪ia得，xry或xiay。因r与ia对称，所以有yrx或yiax，于是yr(r)x。所以r(r)是对称的。
下证对任意正整数n，rn对称。
因r对称，则有xr2yz(xrz∧zry)z(zrx∧yrz)yr2x，所以r2对称。若对称，则xyz(xz∧zry)z(zx∧yrz)yx，所以对称。因此，对任意正整数n，对称。
对任意的x、y∈a，若xt(r)y，则存在m使得xrmy，于是有yrmx，即有yt(r)x。因此，t(r)是对称的。
六、（10分）若f：a→b是双射，则f－1：b→a是双射。
证明因为f：a→b是双射，则f－1是b到a的函数。下证f－1是双射。
对任意x∈a，必存在y∈b使f(x)＝y，从而f－1(y)＝x，所以f－1是满射。
对任意的y1、y2∈b，若f－1(y1)＝f－1(y2)＝x，则f(x)＝y1，f(x)＝y2。因为f：a→b是函数，则y1＝y2。所以f－1是单射。
综上可得，f－1：b→a是双射。
七、（10分）设是一个半群，如果s是有限集，则必存在a∈s，使得a*a＝a。
证明因为是一个半群，对任意的b∈s，由*的封闭性可知，b2＝b*b∈s，b3＝b2*b∈s，…，bn∈s，…。
因为s是有限集，所以必存在j＞i，使得＝。令p＝j－i，则＝*。所以对q≥i，有＝*。
因为p≥1，所以总可找到k≥1，使得kp≥i。对于∈s，有。
令a＝，则a∈s且a*a＝a。
八、（20分）（1）若g是连通的平面图，且g的每个面的次数至少为l(l≥3)，则g的边数m与结点数n有如下关系：
m≤(n－2)。
证明设g有r个面，则2m＝≥lr。由欧拉公式得，n－m＋r＝2。于是， m≤(n－2)。
2）设平面图g＝是自对偶图，则| e|＝2(|v|－1)。
证明设g*＝是连通平面图g＝的对偶图，则g* g，于是|f|＝|v*|＝v|，将其代入欧拉公式|v|－|e|＋|f|＝2得，|e|＝2(|v|－1)。
离散数学试题（b卷答案）
一、（10分）证明(p∨q)∧(pr)∧(qs) s∨r
证明因为s∨rrs，所以，即要证(p∨q)∧(pr)∧(qs) rs。
1)r附加前提。
2)prp3)pt(1)(2)，i
4)p∨qp
5)qt(3)(4)，i
6)qsp7)st(5)(6)，i
8)rscp
9)s∨rt(8)，e
二、（15分）根据推理理论证明：每个考生或者勤奋或者聪明，所有勤奋的人都将有所作为，但并非所有考生都将有所作为，所以，一定有些考生是聪明的。
设p(e)：e是考生，q(e)：e将有所作为，a(e)：
e是勤奋的，b(e)：e是聪明的，个体域：人的集合，则命题可符号化为：
x(p(x)(a(x)∨b(x)))x(a(x)q(x))，x(p(x)q(x)) x(p(x)∧b(x))。
1)x(p(x)q(xp
2)x(p(x)∨q(xt(1)，e
3)x(p(x)∧q(xt(2)，e
4)p(a)∧q(at(3)，es
5)p(at(4)，i
6)q(at(4)，i
7)x(p(x)(a(x)∨b(xp
8)p(a)(a(a)∨b(at(7)，us
9)a(a)∨b(at(8)(5)，i
10)x(a(x)q(xp
11)a(a)q(at(10)，us
12)a(at(11)(6)，i
13)b(at(12)(9)，i
14)p(a)∧b(at(5)(13)，i
15)x(p(x)∧b(xt(14)，eg
三、（10分）某班有25名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。而6个会打网球的人都会打另外一种球，求不会打这三种球的人数。
解设a、b、c分别表示会打排球、网球和篮球的学生集合。则：
a|＝12，|b|＝6，|c|＝14，|a∩c|＝6，|b∩c|＝5，|a∩b∩c|＝2，|(a∪c)∩b|＝6。
因为|(a∪c)∩b|＝(a∩b)∪(b∩c)|＝a∩b)|＋b∩c)|－a∩b∩c|＝|a∩b)|＋5－2＝6，所以|(a∩b)|＝3。于是|a∪b∪c|＝12＋6＋14－6－5－3＋2＝20，＝25－20＝5。故，不会打这三种球的共5人。
离散数学试题 A卷答案
一 证明题 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 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是长寿...
离散数学试题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是长寿...