离散数学期末考试试题及答案

离散数学试题(B卷答案1）

一、证明题（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))

??x?A(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 (2) ?E?(A∧?B)

P P

P

(3) (C∨D)?(A∧?B) T(1)(2)，I (4) (A∧?B)?(R∨S) (5) (C∨D)?(R∨S) (6) C∨D

T(3)(4)， I

P

(7) R∨S T(5)，I

2) ?x(P(x)?Q(y)∧R(x))，?xP(x)?Q(y)∧?x(P(x)∧R(x))

证明(1)?xP(x) P

(2)P(a) T(1)，ES (3)?x(P(x)?Q(y)∧R(x)) P (4)P(a)?Q(y)∧R(a) T(3)，US (5)Q(y)∧R(a) T(2)(4)，I (6)Q(y) T(5)，I (7)R(a) T(5)，I (8)P(a)∧R(a) T(2)(7)，I (9)?x(P(x)∧R(x)) T(8)，EG (10)Q(y)∧?x(P(x)∧R(x)) T(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∧（x?B∧x?C）

?（x? A∧x?B）∧（x? A∧x?C） ? x?（A-B）∧x?（A-C） ? x?（A-B）∩（A-C）

∴A-（B∪C）=（A-B）∩（A-C）

六、已知R、S是N上的关系，其定义如下：R={| x，y?N∧y=x}，S={| x，y?N∧y=x+1}。求R、R*S、S*R、R{1，2}、S[{1，2}]（10分）。

解：R={| x，y?N∧y=x} R*S={| x，y?N∧y=x+1}

S*R={| x，y?N∧y=（x+1）}，R{1，2}={<1，1>，<2，4>}，S[{1，2}]={1，4}。

七、设R={，，}，求r(R)、s(R)和t(R) （15分）。

解：r(R)={，，，，，} s(R)={，，，，，}

2

2

-1

2

-1

2

R= R={，，} R={，，} R={，，}

t(R)={，，，，，，，，，}

八、证明整数集I上的模m同余关系R={|x?y(mod m)}是等价关系。其中，x?y(mod m)的含义是x-y可以被m整除（15分）。

证明：1）?x∈I，因为（x-x）/m=0，所以x?x(mod m)，即xRx。

2）?x，y∈I，若xRy，则x?y(mod m)，即（x-y）/m=k∈I，所以（y - x）/m=-k∈I，所以y?x(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。

九、若f:A→B和g:B→C是双射，则（gf）=fg（10分）。

-1

-1-1

43

25

证明：因为f、g是双射，所以gf：A→C是双射，所以gf有逆函数（gf）：C→A。同理可推fg：C→A是双射。

因为∈fg?存在z（∈g?∈f）?存在z（∈f?∈g）?∈gf?∈（gf），所以（gf）=fg。

-1

-1

-1-1

-1-1

-1

-1

-1-1

-1

离散数学试题(B卷答案2）

一、证明题（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?y(P(x)?Q(y))? ?(?xP(x)??yQ(y)) 证明：?x?y(P(x)?Q(y))??x?y(?P(x)∨Q(y))

??x(?P(x)∨?yQ(y)) ??x?P(x)∨?yQ(y) ???xP(x)∨?yQ(y) ?(?xP(x)??yQ(y))

二、求命题公式(?P?Q)?(P∨?Q) 的主析取范式和主合取范式（10分）

解：(?P?Q)?(P∨?Q)??(?P?Q)∨(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?(Q?S))∧(?R∨P)∧Q?R?S

证明：(1)R (2)?R∨P (3)P (4)P?(Q?S) (5)Q?S (6)Q (7)S (8)R?S

2) ?x(A(x)??yB(y))，?x(B(x)??yC(y))?xA(x)??yC(y)。

证明：(1)?x(A(x)??yB(y)) P (2)A(a)??yB(y) T(1)，ES (3)?x(B(x)??yC(y)) P (4)?x(B(x)?C(c)) T(3)，ES (5)B(b)?C(c) T(4)，US (6)A(a)?B(b) T(2)，US (7)A(a)?C(c) T(5)(6)，I (8)?xA(x)?C(c) T(7)，UG (9)?xA(x)??yC(y) T(8)，EG

四、只要今天天气不好，就一定有考生不能提前进入考场，当且仅当所有考生提前进入考场，考试才能准时进行。所以，如果考试准时进行，那么天气就好（15分）。

解 设P：今天天气好，Q：考试准时进行，A(e)：e提前进入考场，个体域：考生的集合，则命题可符号化为：?P??x?A(x)，?xA(x)?QQ?P。

(1)?P??x?A(x) P (2)?P???xA(x) T(1)，E (3)?xA(x)?P T(2)，E (4)?xA(x)?Q P (5)(?xA(x)?Q)∧(Q??xA(x)) T(4)，E (6)Q??xA(x) T(5)，I (7)Q?P T(6)(3)，I 五、已知A、B、C是三个集合，证明A∩(B∪C)=(A∩B)∪(A∩C) （10分）

证明：∵x? A∩（B∪C）? x? A∧x?（B∪C）? x? A∧（x?B∨x?C）?（ x? A∧x?B）∨（x? A∧x?C）? x?（A∩B）∨x? A∩C? x?（A∩B）∪（A∩C）∴A∩（B∪C）=（A∩B）∪（A∩C）

六、A={ x1,x2,x3 }，B={ y1,y2}，R={,,}，求其关系矩阵及关系图（10分）。

七、设R={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>}，求r(R)、s(R)和t(R)，并作出它们及R的关系图（15分）。

解：r(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,1>,<2,2>,

<3,3>,<4,4>,<5,5>}

s(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,2>,<4,2>,<4,3>} R=R={<2,2>,<2,4>,<3,4>,<4,4>,<5,1>,<5,5>,<5,4>} R={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<5,4>} R={<2,2>,<2,4>,<3,4>,<4,4>,<5,1>,<5,5>,<5,4>}

t(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<2,2>,<5,1>,<5,4>,<5,5>} 八、设R1是A上的等价关系，R2是B上的等价关系，A≠?且B≠?。关系R满足：<，>∈R?∈R1且∈R2，证明R是A×B上的等价关系（10分）。

证明 对任意的∈A×B，由R1是A上的等价关系可得∈R1，由R2是B上的等价关系可得∈R2。再由R的定义，有<，>∈R，所以R是自反的。

对任意的、∈A×B，若R，则∈R1且∈R2。由R1对称得∈R1，由R2对称得∈R2。再由R的定义，有<，>∈R，即R，所以R是对称的。

432

5

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

一、（10分）求命题公式?(P∧Q)??(?P?R)的主合取范式。

解：?(P∧Q)??(?P?R)?（?(P∧Q)??(?P?R)）∧（?(?P?R)??(P∧Q)） ?（(P∧Q)∨(?P∧?R)）∧（(P∨R)∨(?P∨?Q)） ?(P∧Q)∨(?P∧?R)

?(P∨?R)∧（Q∨?P）∧（Q∨?R）

?(P∨Q∨?R)∧(P∨?Q∨?R)∧（?P∨Q∨R）∧（?P∨Q∨?R） ?M1∧M3∧M4∧M5

二、（8分）叙述并证明苏格拉底三段论

解：所有人都是要死的，苏格拉底是人，所以苏格拉底是要死的。 符号化：F（x）：x是一个人。G（x）：x要死的。A：苏格拉底。 命题符号化为?x（F（x）?G（x）），F（a）?G（a） 证明：

（1）?x(F(x)?G(x)) P （2）F(a)?G(a) T(1),US （3）F(a) P （4）G(a) T(2)(3),I

三、（8分）已知A、B、C是三个集合，证明A∩(B∪C)=(A∩B)∪(A∩C)

证明：∵x? A∩（B∪C）? x? A∧x?（B∪C）

? x? A∧（x?B∨x?C）

?（ x? A∧x?B）∨（x? A∧x?C） ? x?（A∩B）∨x? A∩C ? x?（A∩B）∪（A∩C）

∴A∩（B∪C）=（A∩B）∪（A∩C）

四、（10分）已知R和S是非空集合A上的等价关系，试证：1）R∩S是A上的等价关系；2）对a∈A，[a]R∩S=[a]R∩[a]S。

解：?x∈A，因为R和S是自反关系，所以∈R、∈S，因而∈R∩S，故R∩S是自反的。

?x、y∈A，若∈R∩S，则∈R、∈S，因为R和S是对称关系，所以

因∈R、∈S，因而∈R∩S，故R∩S是对称的。

?x、y、z∈A，若∈R∩S且∈R∩S，则∈R、∈S且∈R、∈S，因为R和S是传递的，所以因∈R、∈S，因而∈R∩S，故R∩S是传递的。

总之R∩S是等价关系。

2）因为x∈[a]R∩S?∈R∩S?

∈R∧∈S? x∈[a]R∧x∈[a]S? x∈[a]R∩[a]S 所以[a]R∩S=[a]R∩[a]S。

五、(10分) 设A＝{a，b，c，d}，R是A上的二元关系，且R＝{，，，}，求r(R)、s(R)和t(R)。

解 r(R)＝R∪IA＝{，，，，，，，}

s(R)＝R∪R＝{，，，，，} R＝{，，，} R＝{，，，} R＝{，，，}＝R

t(R)＝?R＝{，，，，，，，

i?1?i4

2

32

-1

d>，}

六、(15分) 设A、B、C、D是集合，f是A到B的双射，g是C到D的双射，令h：A×C?B×D且?∈A×C，h()＝。证明h是双射。

证明：1）先证h是满射。

?∈B×D，则b∈B，d∈D，因为f是A到B的双射，g是C到D的双射，所以存在a∈A，c∈C，使得f(a)=b，f(c)=d，亦即存在∈A×C，使得h()＝＝，所以h是满射。

2）再证h是单射。

?、∈A×C，若h()＝h()，则＝ ，所以f(a1)＝f(a2)，g(c1)＝g(c2)，因为f是A到B的双射，g是C到D的双射，所以a1＝a2，c1＝c2，所以＝，所以h是单射。

综合1）和2），h是双射。

七、(12分)设是群，H是G的非空子集，证明是的子群的充要条件是若a，b?H，则有a*b?H。

证明：? ?a,b∈H有b∈H，所以a*b∈H。 ??a∈H，则e=a*a∈H a=e*a∈H ∵a,b∈H及b∈H，∴a*b=a*（b）∈H ∵H?G且H≠?,∴*在H上满足结合律 ∴是的子群。

八、（10分）设G=是简单的无向平面图，证明G至少有一个结点的度数小于等于5。

解：设G的每个结点的度数都大于等于6，则2|E|=?d(v)≥6|V|，即|E|≥3|V|，与简单无向平面图的|E|≤3|V|-6矛盾，所以G至少有一个结点的度数小于等于5。 九.G=,A={a,b,c},*的运算表为：(写过程，7分)

-1

-1

-1

-1

-1

-1

-1

-1

-1

（1）G是否为阿贝尔群？

（2）找出G的单位元；（3）找出G的幂等元（4）求b的逆元和c的逆元 解：（1）(a*c)*(a*c)=c*c=b=a*b=(a*a)*(c*c)

(a*b)*(a*b)=b*b=c=a*c=(a*a)*(b*b) (b*c)*(b*c)=a*a=a=c*b=(b*b)*(c*c) 所以G是阿贝尔群

（2）因为a*a=a a*b=b*a=b a*c=c*a=c 所以G的单位元是a （3）因为a*a=a 所以G的幂等元是a

（4）因为b*c=c*b=a，所以b的逆元是c且c的逆元是b

十、(10分)求叶的权分别为2、4、6、8、10、12、14的最优二叉树及其权。

解：最优二叉树为

权＝148

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

一、（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是勤奋的；H(x)：x是身体健康的；S(x)：

x是科学家；C(x)：x是事业获得成功的人；F(x)：x是事业半途而废的人；则推理

化形式为：

?x(S(x)?

H(x))

Q(x))，?x(Q(x)∧H(x)?C(x))，?x(S(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 (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＝{<1，2>}，S＝{<2，1>}，则R和S是反自反的，但R*S＝{<1，1>}不是反自反的。

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

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

(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种取法，所以不同的函数共nm个。

(2)显然当|m|≤|n|时，存在单射。由于在Y中任选m个元素的任一全排列都形成X到

mY的不同的单射，故不同的单射有Cnm!＝n(n－1)(n―m―1)个。

(3)显然当|m|＝|n|时，才存在双射。此时Y中元素的任一不同的全排列都形成X到Y的不同的双射，故不同的双射有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＝a1*b，则a*x＝a*(a1*b)＝(a*a1)*b＝e*b＝b。

－

－

－

所以，x＝a1*b是a*x＝b的解。

－

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

－

－

－

＝a1*b是a*x＝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|＝

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

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

一、（15分）设计一盏电灯的开关电路，要求受3个开关A、B、C的控制：当且仅当A和C同时关闭或B和C同时关闭时灯亮。设F表示灯亮。

(1)写出F在全功能联结词组{?}中的命题公式。 (2)写出F的主析取范式与主合取范式。

解 (1)设A：开关A关闭；B：开关B关闭；C：开关C关闭；F＝(A∧C)∨(B∧C)。 在全功能联结词组{?}中：

?A??(A∧A)?A?A

A∧C???( A∧C)??( A?C)?(A?C)?(A?C)

A∨B??(?A∧?B)??(( A?A)∧(B?B))?( A?A)?(B?B)

所以

F?((A?C)?(A?C))∨((B?C)?(B?C))

?(((A?C)?(A?C))?((A?C)?(A?C)))?(((B?C)?(B?C))?((B?C)?(B?C)))

(2)F?(A∧C)∨(B∧C)

?(A∧(B∨?B)∧C)∨((A∨?A)∧B∧C)

?(A∧B∧C)∨(A∧?B∧C)∨(A∧B∧C)∨(?A∧B∧C) ?m3∨m5∨m7 主析取范式 ?M0∧M1∧M2∧M4∧M6 主合取范式 二、（10分）判断下列公式是否是永真式？ (1)(?xA(x)??xB(x))??x(A(x)?B(x))。

(2)(?xA(x)??xB(x))??x(A(x)?B(x)))。 解 (1)(?xA(x)??xB(x))??x(A(x)?B(x))

?(??xA(x)∨?xB(x))??x(A(x)?B(x)) ??(??xA(x)∨?xB(x))∨?x(?A(x)∨B(x)) ?(?xA(x)∧??xB(x))∨?x?A(x)∨?xB(x)

?(?xA(x)∨?x?A(x)∨?xB(x))∧(??xB(x)∨?x?A(x)∨?xB(x)) ??x(A(x)∨?A(x))∨?xB(x) ?T

所以，(?xA(x)??xB(x))??x(A(x)?B(x))为永真式。

(2)设论域为{1，2}，令A(1)＝T；A(2)＝F；B(1)＝F；B(2)＝T。

则?xA(x)为假，?xB(x)也为假，从而?xA(x)??xB(x)为真；而由于A(1)?B(1)为假，所以?x(A(x)?B(x))也为假，因此公式(?xA(x)??xB(x))??x(A(x)?B(x))为假。该公式不是永真式。

三、（15分）设X为集合，A＝P(X)－{?}－{X}且A≠?，若|X|＝n，问 (1)偏序集是否有最大元？ (2)偏序集是否有最小元？

(3)偏序集中极大元和极小元的一般形式是什么？并说明理由。 解 偏序集不存在最大元和最小元，因为n＞2。

考察P(X)的哈斯图，最底层的顶点是空集，记作第0层，由底向上，第一层是单元集，第二层是二元集，…，由|X|＝n，则第n－1层是X的n－1元子集，第n层是X。偏序集与偏序集相比，恰好缺少第0层和第n层。因此的极小元就是X的所有单元集，即{x}，x∈X；而极大元恰好是比X少一个元素，即X－{x}，x∈X。

四、（10分）设A＝{1，2，3，4，5}，R是A上的二元关系，且R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。

解 r(R)＝R∪IA＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>}

s(R)＝R∪R1＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，2>，

－

<4，2>，<4，3>}

R2＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}

R3＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>} R4＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}＝R2 t(R)＝?Ri＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，

i?1?1>，<5，4>，<5，5>}。

五、（10分）设函数g：A→B，f：B→C， (1)若f?g是满射，则f是满射。 (2)若f?g是单射，则g是单射。

证明 因为g：A→B，f：B→C，由定理5.5知，f?g为A到C的函数。

(1)对任意的z∈C，因f?g是满射，则存在x∈A使f?g(x)＝z，即f(g(x))＝z。由g：A→B可知g(x)∈B，于是有y＝g(x)∈B，使得f(y)＝z。因此，f是满射。

(2)对任意的x1、x2∈A，若x1≠x2，则由f?g是单射得f?g(x1)≠f?g(x2)，于是f(g(x1))≠f(g(x2))，必有g(x1)≠g(x2)。所以，g是单射。

六、（10分）有幺元且满足消去律的有限半群一定是群。

证明 设是一个有幺元且满足消去律的有限半群，要证是群，只需证明G的任一元素a可逆。

考虑a，a2，?，ak，?。因为G只有有限个元素，所以存在k＞l，使得ak＝al。令m＝k－l，有al*e＝al*am，其中e是幺元。由消去率得am＝e。

于是，当m＝1时，a＝e，而e是可逆的；当m＞1时，a*am-1＝am-1*a＝e。从而a是可逆的，其逆元是am-1。总之，a是可逆的。

七、（20分）有向图G如图所示，试求： (1)求G的邻接矩阵A。

(2)求出A2、A3和A4，v1到v4长度为1、2、3和4的路有多少？

(3)求出ATA和AAT，说明ATA和AAT中的第(2，2)元素和第(2，3)元素的意义。 (4)求出可达矩阵P。 (5)求出强分图。

解 (1)求G的邻接矩阵为：

?0??0A??0??0?101??011?

101??100??

(2)由于

?0??0A2??0??0?111??02??201?3?01A??

02111????02011???12??03??22??044A? ?0312????0101???23??13? 23??22??所以v1到v4长度为1、2、3和4的路的个数分别为1、1、2、3。 (3)由于

?0??0ATA??0??0?000??21??312??12 AAT???01121???10213???21??10? 21??21??再由定理10.19可知，所以ATA的第(2，2)元素为3，表明那些边以v2为终结点且具有不同始结点的数目为3，其第(2，3)元素为0，表明那些边既以v2为终结点又以v3为终结点，并且具有相同始结点的数目为0。AAT中的第(2，2)元素为2，表明那些边以v2为始结点且具有不同终结点的数目为2，其第(2，3)元素为1，表明那些边既以v2为始结点又以v3为始结点，并且具有相同终结点的数目为1。

(4)

?0??0B4?A?A2?A3?A4??0??0?101??0??011??0+

101??0???100???0因

111??0??201??0+

111??0???011???0212??03??122??04+

212??03???201???0123??13??23??22???0??0?0??0?为

741??747?，

747??434???0??0所以求可达矩阵为P??0??0??0??0(5)因为P?PT??0??0?111??111?。

111??111??111??0??111??1∧??1111???1111???000??0??111??0＝??1110???0111???000??111?，所以{v1}，{v2，v3，v4}

111??111??构成G的强分图。

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

一、（10分）证明(P∨Q)∧(P?R)∧(Q?S)S∨R

证明 因为S∨R??R?S，所以，即要证(P∨Q)∧(P?R)∧(Q?S)?R?S。

(1)?R 附加前提 (2)P?R P (3)?P T(1)(2)，I (4)P∨Q P (5)Q T(3)(4)，I (6)Q?S P (7)S T(5)(6)，I (8)?R?S CP (9)S∨R T(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(x)) P (2)??x(?P(x)∨Q(x)) T(1)，E (3)?x(P(x)∧?Q(x)) T(2)，E (4)P(a)∧?Q(a) T(3)，ES (5)P(a) T(4)，I (6)?Q(a) T(4)，I (7)?x(P(x)?(A(x)∨B(x)) P (8)P(a)?(A(a)∨B(a)) T(7)，US (9)A(a)∨B(a) T(8)(5)，I (10)?x(A(x)?Q(x)) P

(11)A(a)?Q(a) T(10)，US (12)?A(a) T(11)(6)，I (13)B(a) T(12)(9)，I (14)P(a)∧B(a) T(5)(13)，I (15)?x(P(x)∧B(x)) T(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，|A?B?C|＝25－20＝5。故，不会打这三种球的共5人。

四、（10分）设A1、A2和A3是全集U的子集，则形如?Ai?(Ai?为Ai或Ai)的集合称

i?13为由A1、A2和A3产生的小项。试证由A1、A2和A3所产生的所有非空小项的集合构成全集U的一个划分。

证明 小项共8个，设有r个非空小项s1、s2、…、sr(r≤8)。

对任意的a∈U，则a∈Ai或a∈Ai，两者必有一个成立，取Ai?为包含元素a的Ai

或Ai，则a∈?Ai?，即有a∈?si，于是U??si。又显然有?si?U，所以U＝?si。

i?1i?1i?1i?1i?13rrrr任取两个非空小项sp和sq，若sp≠sq，则必存在某个Ai和Ai分别出现在sp和sq中，于是sp∩sq＝?。

综上可知，{s1，s2，…，sr}是U的一个划分。

五、（15分）设R是A上的二元关系，则：R是传递的?R*R?R。

证明 (5)若R是传递的，则∈R*R??z(xRz∧zSy)?xRc∧cSy，由R是传递的得xRy，即有∈R，所以R*R?R。

反之，若R*R?R，则对任意的x、y、z∈A，如果xRz且zRy，则∈R*R，于是有∈R，即有xRy，所以R是传递的。

六、（15分）若G为连通平面图，则n－m＋r＝2，其中，n、m、r分别为G的结点数、边数和面数。

证明 对G的边数m作归纳法。

当m＝0时，由于G是连通图，所以G为平凡图，此时n＝1，r＝1，结论自然成立。 假设对边数小于m的连通平面图结论成立。下面考虑连通平面图G的边数为m的情况。

设e是G的一条边，从G中删去e后得到的图记为G?，并设其结点数、边数和面数

分别为n?、m?和r?。对e分为下列情况来讨论：

若e为割边，则G?有两个连通分支G1和G2。Gi的结点数、边数和面数分别为ni、mi和ri。显然n1＋n2＝n?＝n，m1＋m2＝m?＝m－1，r1＋r2＝r?＋1＝r＋1。由归纳假设有n1－m1＋r1＝2，n2－m2＋r2＝2，从而(n1＋n2)－(m1＋m2)＋(r1＋r2)＝4，n－(m－1)＋(r＋1)＝4，即n－m＋r＝2。

若e不为割边，则n?＝n，m?＝m－1，r?＝r－1，由归纳假设有n?－m?＋r?＝2，从而n－(m－1)＋r－1＝2，即n－m＋r＝2。

由数学归纳法知，结论成立。

七、（10分）设函数g：A→B，f：B→C，则： (1)f?g是A到C的函数；

(2)对任意的x∈A，有f?g(x)＝f(g(x))。

证明 (1)对任意的x∈A，因为g：A→B是函数，则存在y∈B使∈g。对于y∈B，因f：B→C是函数，则存在z∈C使∈f。根据复合关系的定义，由∈g和∈f得∈g*f，即∈f?g。所以Df?g＝A。

对任意的x∈A，若存在y1、y2∈C，使得、∈f?g＝g*f，则存在t1使得∈g且∈f，存在t2使得∈g且∈f。因为g：A→B是函数，则t1＝t2。又因f：B→C是函数，则y1＝y2。所以A中的每个元素对应C中惟一的元素。

综上可知，f?g是A到C的函数。

(2)对任意的x∈A，由g：A→B是函数，有∈g且g(x)∈B，又由f：B→C是函数，得∈f，于是∈g*f＝f?g。又因f?g是A到C的函数，则可写为f?g(x)＝f(g(x))。

八、（15分）设是的子群，定义R＝{|a、b∈G且a1*b∈H}，

－

则R是G中的一个等价关系，且[a]R＝aH。

证明 对于任意a∈G，必有a1∈G使得a1*a＝e∈H，所以∈R。

－

－

若∈R，则a1*b∈H。因为H是G的子群，故(a1*b)1＝b1*a∈H。所以

－

－

－

－

a>∈R。

若∈R，∈R，则a1*b∈H，b1*c∈H。因为H是G的子群，所以(a

－

－

－

1

*b)*(b1*c)＝a1*c∈H，故∈R。

－

－

综上可得，R是G中的一个等价关系。

对于任意的b∈[a]R，有∈R，a1*b∈H，则存在h∈H使得a1*b＝h，b＝a*h，

－

－

于是b∈aH，[a]R?aH。对任意的b∈aH，存在h∈H使得b＝a*h，a1*b＝h∈H，

－

b>∈R，故aH?[a]R。所以，[a]R＝aH。

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

一、（10分）证明(P∧Q∧A?C)∧(A?P∨Q∨C)?(A∧(P?Q))?C。 证明：(P∧Q∧A?C)∧(A?P∨Q∨C)?(?P∨?Q∨?A∨C)∧(?A∨P∨Q∨C)

?(?P∨?Q∨?A∨C)∧(?A∨P∨Q∨C) ?((?P∨?Q∨?A)∧(?A∨P∨Q))∨C ??((P∧Q∧A)∨(A∧?P∧?Q))∨C ??( A∧((P∧Q)∨(?P∧?Q)))∨C ??( A∧(P?Q))∨C ?(A∧(P?Q))?C。

二、（10分）举例说明下面推理不正确：?x?y(P(x)?Q(y))，?y?z(R(y)?Q(z))?x?z(P(x)?R(z))。

解：设论域为{1，2}，令P(1)＝P(2)＝T；Q(1)＝Q(2)＝T；R(1)＝R(2)＝F。则： ?x?y(P(x)?Q(y))??x((P(x)?Q(1))∨(P(x)?Q(2)))

?((P(1)?Q(1))∨(P(1)?Q(2)))∧((P(2)?Q(1))∨(P(2)?Q(2)))

?((T?T)∨(T?T))∧((T?T)∨(T?T)) ?T

?y?z(R(y)?Q(z))??y((R(y)?Q(1))∨(R(y)?Q(2)))

?((R(1)?Q(1))∨(R(1)?Q(2)))∧((R(2)?Q(1))∨(R(2)?Q(2))) ?((F?T)∨(F?T))∧((F?T)∨(F?T)) ?T 但

?x?z(P(x)?R(z))??x((P(x)?R(1))∧(P(x)?R(2)))

?((P(1)?R(1))∧(P(1)?R(2)))∨((P(2)?R(1))∧(P(2)?R(2))) ?((T?F)∧(T?F))∨((T?F)∧(T?F)) ?F

所以，?x?y(P(x)?Q(y))，?y?z(R(y)?Q(z))?x?z(P(x)?R(z))不正确。

三、（15分）在谓词逻辑中构造下面推理的证明：所有牛都有角，有些动物是牛，所以，有些动物有角。

解：令P(x)：x是牛；Q(x)：x有角；R(x)：x是动物；则推理化形式为：

?x(P(x)?Q(x))，?x(P(x)∧R(x))?x(Q(x)∧R(x))

下面给出证明：

(1)?x(P(x)∧R(x)) P (2)P(a)∧R(a) T(1)，ES (3)?x(P(x)?Q(x)) P (4)P(a)?Q(a) T(3)，US (5)P(a) T(2)，I (6)Q(a) T(4)(5)，I (7)R(a) T(2)，I (8)Q(a)∧R(a) T(6)(7)，I (9)?x(Q(x)∧R(x)) T(8)，EG 四、（10分）证明(A∩B)×(C∩D)＝(A×C)∩(B×D)。

证明：因为∈(A∩B)×(C∩D)?x∈(A∩B)∧y∈(C∩D)?x∈A∧x∈B∧y∈C∧y∈D?(x∈A∧y∈C)∧(x∈B∧y∈D)?∈A×C∧∈B×D?∈(A×C)∩(B×D)，所以(A∩B)×(C∩D)＝(A×C)∩(B×D)。

五、（15分）设A＝{1，2，3，4，5}，R是A上的二元关系，且R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。

解 r(R)＝R∪IA＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>}

s(R)＝R∪R1＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，2>，

－

<4，2>，<4，3>}

R2＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>} R3＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>} R4＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}＝R2

本文来源：https://www.bwwdw.com/article/0wyx.html