离散数学

离散数学试题（A卷答案）

一、（10分）

（1）证明(PQ)∧(QR)(PR) （2）求(P∨Q)R的主析取范式与主合取范式，并写出其相应的成真赋值和成假赋值。 解：（1）因为((PQ)∧(QR))(PR) ((P∨Q)∧(Q∨R))∨(P∨R) (P∧Q)∨(Q∧R)∨P∨R (P∧Q)∨((Q∨P∨R)∧(R∨P∨R)) (P∧Q)∨(Q∨P∨R) (P∨Q∨P∨R)∧(Q∨Q∨P∨R) T 所以，(PQ)∧(QR)(PR)。

（2）(P∨Q)R(P∨Q)∨R(P∧Q)∨R (P∨(Q∧Q)∨R)∧((P∧P)∨Q∨R) (P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R) M2∧M4∧M6 m0∨m1∨m3∨m5

所以，其相应的成真赋值为000、00

1、0

11、10

1、111：成假赋值为：0

10、100、110。

二、（10分）分别找出使公式x(P(x)y(Q(y)∧R(x，y)))为真的解释和为假的解释。

解：设论域为{1，2}。

若P(1)＝P(2)＝T，Q(1)＝Q(2)＝F，R(1，1)＝R(1，2)＝R(2，1)＝R(2，2)＝F，则 x(P(x)y(Q(y)∧R(x，y))) x(P(x)((Q(1)∧R(x，1))∨(Q(2)∧R(x，2)))) (P(1)((Q(1)∧R(1，1))∨(Q(2)∧R(1，2))))∧(P(2)((Q(1)∧R(2，1))∨(Q(2)∧R(2，2)))) (T((F∧F)∨(F∧F)))∧(T((F∧F)∨(F∧F))) (TF)∧(TF) F 若P(1)＝P(2)＝T，Q(1)＝Q(2)＝T，R(1，1)＝R(1，2)＝R(2，1)＝R(2，2)＝T，则 x(P(x)y(Q(y)∧R(x，y))) x(P(x)((Q(1)∧R(x，1))∨(Q(2)∧R(x，2)))) (P(1)((Q(1)∧R(1，1))∨(Q(2)∧R(1，2))))∧(P(2)((Q(1)∧R(2，1))∨(Q(2)∧R(2，2)))) (T((T∧T)∨(T∧T)))∧(T((T∧T)∨(T∧T))) (TT)∧(TT) T

三、（10分）

在谓词逻辑中构造下面推理的证明：每个喜欢步行的人都不喜欢做汽车，每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车，因而有的人不喜欢步行。

解

论域：所有人的集合。A(x)：x喜欢步行；B(x)：x喜欢坐汽车；C(x)：x喜欢骑自行车；则推理化形式为：

x(A(x)B(x))，x(B(x)∨C(x))，xC(x)xA(x) 下面给出证明： (1)xC(x)

P (2)xC(x)

T(1)，E (3)C(c)

T(2)，ES (4)x(B(x)∨C(x))

P (5)B(c)∨C(c)

T(4)，US (6)B(c)

T(3)(5)，I (7)x(A(x)B(x))

P (8)A(c)B(c)

T(7)，US (9)A(c)

T(6)(8)，I (10)xA(x)

T(9) ，EG

四、（10分）

下列论断是否正确？为什么？ (1)若A∪B＝A∪C，则B＝C。 (2)若A∩B＝A∩C，则B＝C。 (3)若AB＝AC，则B＝C。

解 (1)不一定。例如，令A＝{1}，B＝{1，2}，C＝{2}，则A∪B＝A∪C，但B＝C不成立。 (2)不一定。例如，令A＝{1}，B＝{1，2}，C＝{1，3}，则A∩B＝A∩C，但B＝C不成立。 (3)成立。因为若AB＝AC，对任意的x∈B，当x∈A时，有x∈A∩BxABxAC＝(A∪C)－(A∩C)x∈A∩Cx∈C，所以BC；当xA时，有xA∩B，而x∈Bx∈A∪B，所以x∈A∪B－A∩B＝ABx∈AC，但x A，于是x∈C，所以BC。

同理可证，C B。

因此，当AB＝AC时，必有B＝C。

五、（10分）若R是集合A上的自反和传递关系，则对任意的正整数n，R＝R。

证明 当n＝1时，结论显然成立。设n＝k时，Rk＝R。当n＝k＋1时，Rk+1＝Rk*R＝R*R。下面由R是自反和传递的推导出R*R＝R即可。

由传递性得R*RR。另一方面，对任意的∈R，由R自反得∈R，再由关系的复合得∈R*R，从而RR*R。因此，R＝R*R。

由数学归纳法知，对任意的正整数n，Rn＝R。

n

六、（15分）设函数f：R×RR×R，f定义为：f()＝。

(1)证明f是单射。 (2)证明f是满射。 (3)求逆函数f。

(4)求复合函数f－1f和ff。

证明 (1)对任意的x，y，x1，y1∈R，若f()＝f()，则＝，x＋y＝x1＋y1，x－y＝x1－y1，从而x＝x1，y＝y1，故f是单射。

(2)对任意的∈R×R，令x＝uw2uw2－

1，y＝

uw2，则f()＝

uw2＋

uw2，

uw2－>＝，所以f是满射。

uw2－1(3)f()＝

uw2>。

xyxy2xy(xy)2(4)ff()＝f(f())＝f()＝

，>＝ ff()＝f(f())＝f()＝＝。

七、（15分）设X＝{1，2，3，4}，R是X上的二元关系，R＝{，，，，，，，，} (1)画出R的关系图。 (2)写出R的关系矩阵。

(3)说明R是否是自反、反自反、对称、传递的。 解 (1)R的关系图如图所示： (2) R的关系矩阵为：

10M(R)111011101100 00(3)对于R的关系矩阵，由于对角线上不全为1，R不是自反的；由于对角线上存在非0元，R不是反自反的；由于矩阵不对称，R不是对称的；

经过计算可得 102M(R)111011101100M(R)，所以R是传递的。 00

八、（10分）若是群，H是G的非空子集，则是的子群对任意的a、b∈H有a*b－1∈H。

3 证明 必要性：对任意的a、b∈H，由是的子群，必有b－1∈H，从而a*b－1∈H。 充分性：由H非空，必存在a∈H。于是e＝a*a∈H。 任取a∈H，由e、a∈H得a－1＝e*a－1∈H。

对于任意的a、b∈H，有a*b＝a*(b)∈H，即a*b∈H。 又因为H是G非空子集，所以*在H上满足结合律。 综上可知，是的子群。

九、（10分）给定二部图G＝，且|V1∪V2|＝m，|E|＝n，证明n≤m/4。

证明 设|V1|＝m1，则|V2|＝m－m1，于是n≤m1(m－m1)＝m1m－m22

2－

1－1

－1

m12。因为(m2m1)20，即4mm1m1，所以n≤m2/4。

4 离散数学试题（B卷答案）

一、（20分）用公式法判断下列公式的类型： (1)(P∨Q)(PQ) (2)(PQ)(P∧(Q∨R)) 解：（1）因为(P∨Q)(PQ)(P∨Q)∨(P∧Q)∨(P∧Q)

(P∧Q)∨(P∧Q)∨(P∧Q) m1∨m2∨m3 M0

所以，公式(P∨Q)(PQ)为可满足式。

（2）因为(PQ)(P∧(Q∨R))(( P∨Q))∨(P∧Q∧R))

(P∨Q)∨(P∧Q∧R))

(P∨Q∨P)∧(P∨Q∨Q)∧(P∨Q∨R) (P∨Q)∧(P∨Q∨R)

(P∨Q∨(R∧R))∧(P∨Q∨R) (P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R) M0∧M1

m2∨m3∨m4∨m5∨m6∨m7

所以，公式(PQ)(P∧(Q∨R))为可满足式。

二、（15分）在谓词逻辑中构造下面推理的证明：每个科学家都是勤奋的，每个勤奋又身体健康的人在事业中都会获得成功。存在着身体健康的科学家。所以，存在着事业获得成功的人或事业半途而废的人。

Q(x)：x是勤奋的；x是科学家；C(x)：解：论域：所有人的集合。H(x)：x是身体健康的；S(x)：x是事业获得成功的人；F(x)：x是事业半途而废的人；则推理化形式为：

x(S(x)Q(x))，x(Q(x)∧H(x)C(x))，x(S(x)∧H(x))

x(C(x)∨F(x)) 下面给出证明：

(1)x(S(x)∧H(x))

P (2)S(a)∧H(a)

T(1)，ES (3)x(S(x)Q(x))

P (4)S(a)Q(a)

T(1)，US (5)S(a)

T(2)，I (6)Q(a)

T(4)(5)，I (7)H(a)

T(2)，I (8)Q(a)∧H(a)

T(6)(7)，I

5 (9)x(Q(x)∧H(x)C(x))

P (10)Q(a)∧H(a)C(a)

T(9)，Us (11)C(a)

T(8)(10)，I (12)xC(x)

T(11)，EG (13)x(C(x)∨F(x))

T(12)，I

三、（10分）设A＝{，1，{1}}，B＝{0，{0}}，求P(A)、P(B)－{0}、P(B)B。 解

P(A)＝{，{}，{1}，{{1}}，{，1}，{，{1}}，{1，{1}}，{，1，{1}}} P(B)－{0}＝{，{0}，{{0}}，{0，{0}}－{0}＝{，{0}，{{0}}，{0，{0}} P(B)B＝{，{0}，{{0}}，{0，{0}}{0，{0}}＝{，0，{{0}}，{0，{0}}

四、（15分）设R和S是集合A上的任意关系，判断下列命题是否成立？ (1)若R和S是自反的，则R*S也是自反的。 (2)若R和S是反自反的，则R*S也是反自反的。 (3)若R和S是对称的，则R*S也是对称的。 (4)若R和S是传递的，则R*S也是传递的。 (5)若R和S是自反的，则R∩S是自反的。 (6)若R和S是传递的，则R∪S是传递的。

解

(1)成立。对任意的a∈A，因为R和S是自反的，则∈R，∈S，于是∈R*S，故R*S也是自反的。

(2)不成立。例如，令A＝{1，2}，R＝{}，S＝{}，则R和S是反自反的，但R*S＝{}不是反自反的。

(3)不成立。例如，令A＝{1，2，3}，R＝{，，}，S＝{，}，则R和S是对称的，但R*S＝{，}不是对称的。

(4)不成立。例如，令A＝{1，2，3}，R＝{，，}，S＝{，，}，则R和S是传递的，但R*S＝{，，}不是传递的。

(5)成立。对任意的a∈A，因为R和S是自反的，则∈R，∈S，于是∈R∩S，所以R∩S是自反的。

五、（15分）令X＝{x1，x2，…，xm}，Y＝{y1，y2，…，yn}。问 (1)有多少个不同的由X到Y的函数？

(2)当n、m满足什么条件时，存在单射，且有多少个不同的单射？ (3)当n、m满足什么条件时，存在双射，且有多少个不同的双射？

解

(1)由于对X中每个元素可以取Y中任一元素与其对应，每个元素有n种取法，所以不同的函数共n个。

(2)显然当|m|≤|n|时，存在单射。由于在Y中任选m个元素的任一全排列都形成X到Y的不同的单射，故不同的单射有Cnm!＝n(n－1)(n―m―1)个。

(3)显然当|m|＝|n|时，才存在双射。此时Y中元素的任一不同的全排列都形成X到Y的不同的双射，

6 mm故不同的双射有m!个。

六、（5分）集合X上有m个元素，集合Y上有n个元素，问X到Y的二元关系总共有多少个？ 解

X到Y的不同的二元关系对应X×Y的不同的子集，而X×Y的不同的子集共有个2mn，所以X到Y的二元关系总共有2mn个。

七、（10分）若是群，则对于任意的a、b∈G，必有惟一的x∈G使得a*x＝b。

证明 设e是群的幺元。令x＝a－1*b，则a*x＝a*(a－1*b)＝(a*a－1)*b＝e*b＝b。所以，x＝a－1*b是a*x＝b的解。

若x∈G也是a*x＝b的解，则x＝e*x＝(a*a)*x＝a*(a*x)＝a*b＝x。所以，x＝a*b是a*x

－

1－1

－1

－1＝b的惟一解。

八、（10分）给定连通简单平面图G＝，且|V|＝6，|E|＝12。证明：对任意f∈F，d(f)＝3。 证明

由偶拉公式得|V|－|E|＋|F|＝2，所以|F|＝2－|V|＋|E|＝8，于是d(f)＝2|E|＝24。若存在f∈

fFF，使得d(f)＞3，则3|F|＜2|E|＝24，于是|F|＜8，与|F|＝8矛盾。故对任意f∈F，d(f)＝3。

离散数学

离散数学

离散数学

离散数学学习心得

离散数学总结

离散数学心得

离散数学教学大纲

离散数学复习题

离散数学练

离散数学期末试卷

《离散数学.doc》

将本文的Word文档下载到电脑，方便收藏和打印

推荐度：

点击下载文档