离散数学期末考试试题(有几套带答案)

离散数学 中央电大

离散数学试题(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∧ 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 (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) (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>| x,y N∧y=x}，S={<x,y>| x,y N∧y=x+1}。求R、R*S、S*R、

R{1,2}、S[{1,2}]（10分）

解：R={<y,x>| x,y N∧y=x}，R*S={<x,y>| x,y N∧y=x+1}，S*R={<x,y>| x,y N∧y=（x+1）}， 七、若f:A→B和g:B→C是双射，则（gf）=fg（10分）。

-1

-1-1

-1

2

2

2

2

-1

离散数学 中央电大

证明：因为f、g是双射，所以gf：A→C是双射，所以gf有逆函数（gf）：C→A。同理可推fg：C→A是双射。 因为<x,y>∈fg 存在z（<x,z>∈g <z,y>∈f） 存在z（<y,z>∈f <z,x>∈g） <y,x>∈gf <x,y>∈（gf）,所以（gf）=fg。

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

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

(1)对A中每个元a，有a*a＝a。 (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，E>，且|V|＝m，|E|＝n。试证：若n≥Cm 1＋2，则G是哈密尔顿图 2证明 若n≥Cm。 1＋2，则2n≥m－3m＋6 （1）

2

-1

-1-1

-1-1

-1

-1

-1

-1

-1-1

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

w V

d(w)＜m＋(m－2)(m－3)＋m＝m－3m＋6，与（1）矛

2

盾。所以，对于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 三、推理证明题（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)∨Q(c) T(3),US (5)Q(c) T(2)(4),I (6) x Q(x) T(5),EG

四、例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>|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传递。 总之R是A上的等价关系。

七、若f:A→B是双射，则f:B→A是双射（15分）。

证明: 对任意的x∈A，因为f是从A到B的函数，故存在y∈B，使<x,y>∈f，<y,x>∈f。所以,f是满射。

对任意的x∈A，若存在y1,y2∈B，使得<y1,x>∈f且<y2,x>∈f,则有<x,y1>∈f且<x,y2>∈f。因为f是函数，则y1=y2。所以，f是单射。 因此f是双射。

八、设<G，*>是群，<A，*>和<B，*>是<G，*>的子群，证明：若A∪B＝G，则A＝G或B＝G（10分）。

证明 假设A≠G且B≠G，则存在a A，a B，且存在b B，b A（否则对任意的a A，a B，从而A B，即A∪B＝B，得B＝G，矛盾。）

对于元素a*b G，若a*b …… 此处隐藏：11052字，全部文档内容请下载后查看。喜欢就下载吧 ……