离散数学期末考试试题（有几套带答案）

离散试卷及答案

离散数学试题(A卷及答案）

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

(7) R∨S

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

证明（1）?xP(x) (2)P(a)

(3)?x(P(x)?Q(y)∧R(x)) (4)P(a)?Q(y)∧R(a) (5)Q(y)∧R(a)

第 1 页 共 20 页

∧?B), (A∧?B)?(R∨S)?R∨S 证明：(1) (C∨D)??E (2) ?E?(A∧?B) (3) (C∨D)?(A∧?B) (4) (A∧?B)?(R∨S) (5) (C∨D)?(R∨S) (6) C∨D

离散试卷及答案

(6)Q(y) (7)R(a) (8)P(a)

(9)P(a)∧R(a) (10)?x(P(x)∧R(x)) (11)Q(y)∧?x(P(x)∧R(x))

四、设m是一个取定的正整数，证明：在任取m＋1个整数中，至少有两个整数，它们的差是m的整数倍

证明 设a1，a2，…，am?1为任取的m＋1个整数，用m去除它们所得余数只能是0，1，…，m－1，由抽屉原理可知，a1，a2，…，am?1这m＋1个整数中至少存在两个数as和at，它们被m除所得余数相同，因此as和at的差是m的整数倍。 五、已知A、B、C是三个集合，证明A-(B∪C)=(A-B)∩(A-C) （15分） 证明 ∵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=x2}，S={| x,y?N∧y=x+1}。求R-1、R*S、S*R、R{1,2}、S[{1,2}]（10分）

解：R-1={| x,y?N∧y=x2}，R*S={| x,y?N∧y=x2+1}，S*R={| x,y?N∧y=（x+1）2}，

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

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

-1

：C→A。同理可推f-1g-1：C→A是双射。

因为∈f-1g-1?存在z（∈g-1?∈f-1）?存在z（∈

f?∈g）?∈gf?∈（gf）-1,所以（gf）-1=f-1g-1。

R{1,2}={<1,1>,<2,4>}，S[{1,2}]={1,4}。

八、（15分）设是半群，对A中任意元a和b，如a≠b必有a*b≠b*a，证明：

(1)对A中每个元a，有a*a＝a。

第 2 页 共 20 页

离散试卷及答案

(2)对A中任意元a和b，有a*b*a＝a。 (3)对A中任意元a、b和c，有a*b*c＝a*c。 证明 由题意可知，若a*b＝b*a，则必有a＝b。 (1)由(a*a)*a＝a*(a*a)，所以a*a＝a。

(2)由a*(a*b*a)＝(a*a)*(b*a)＝a*b*(a*a)＝(a*b*a)*a，所以有a*b*a＝

a。

(3)由(a*c)*(a*b*c)＝(a*c*a)*(b*c)＝a*(b*c)＝(a*b)*c＝(a*b)*(c*a*c)＝(a*b*c)*(a*c)，所以有a*b*c＝a*c。

2九、给定简单无向图G＝，且|V|＝m，|E|＝n。试证：若n≥Cm?1＋2，

则G是哈密尔顿图

22证明 若n≥Cm。 ?1＋2，则2n≥m－3m＋6 （1）

若存在两个不相邻结点u、v使得d(u)＋d(v)＜m，则有2n＝?d(w)＜m＋(m－

w?V2)(m－3)＋m＝m2－3m＋6，与（1）矛盾。所以，对于G中任意两个不相邻结点

u、v都有

d(u)＋d(v)≥m，所以G是哈密尔顿图。

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

一、证明题（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)) 二、求命题公式(?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

第 3 页 共 20 页

离散试卷及答案

三、推理证明题（10分） 1)(P?(Q?S))∧(?R∨P)∧Q?R?S

证明：（1）R 附加前提 (2)?R∨P P (3)P T(1)(2),I (4)P?(Q?S) P (5)Q?S T(3)(4),I (6)Q P (7)S T(5)(6),I

(8)R?S CP 2) ?x(P(x)∨Q(x))，?x?P(x)??x

Q(x)

证明：(1)?x?P(x) P (2)?P(c) T(1),US

(3)?x(P(x)∨Q(x)) P (4)P(c)T(3),US

(5)Q(c) T(2)(4),I

(6)?x T(5),EG

∨

Q(c)

Q(x)

四、例5在边长为1的正方形内任意放置九个点，证明其中必存在三个点，使得由它们组成的三角形（可能是退化的）面积不超过1/8（10分）。

证明：把边长为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∧（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）

六、?={A1，A2，…，An}是集合A的一个划分，定义R={|a、b∈Ai，I=1，2，…，n}，则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传递。

第 4 页 共 20 页