离散数学期末考试试题有几套带答案 下载本文

离散数学试题(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

2)

x(A(x)

B(x))

B(x))xA(x)

xA(x)

x(xB(x)

(P∧Q∧R)的主析取范式和主合取范式(10

T∧R(置换)xB(x) A(x)∨B(x))

x

A(x)∨xB(x)R

证明 :x(A(x)xA(x)∨xB(x)

二、求命题公式(P∨(Q∧R))分)

证明:(P∨(Q∧R))

(((

∨(

P∧

Q∧

P∧(P∧P∧

(P∧Q∧R)Q∨Q)∨(

(P∨(Q∧R))∨(P∧Q∧R))

R))∨(P∧Q∧R) P∧

R))∨(P∧Q∧R) P∧

Q∧

R)∨(

P∧Q∧

R))

Q∧R)∨(

R))∨(P∧Q∧R) m0∨m1∨m2∨m7 M3∨M4∨M5∨M6

三、推理证明题(10分) 1)

C∨D, (C∨D)(A∧R∨S

证明:(1) (C∨D)

E

(5) (C∨D)

(R∨S)

B), (A∧

B)

E,

E

(2)

E

(A∧(A∧B)

B) B)

(R∨S)(3) (C∨D)(4) (A∧

(R∨S)

(6) C∨D (7) R∨S 2) xP(x)

x(P(x)Q(y)∧

Q(y)∧R(x)),x(P(x)∧R(x)) xP(x)

(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))

x(P(x)∧R(x))

证明(1)(2)P(a) (3)

x(P(x)Q(y)∧R(x)) (11)Q(y)∧

(4)P(a)Q(y)∧R(a)

四、设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∧xx

A-(B∪C)

A∧x

x

A∧x

(B∪C) x A∧x

C)

x A∧(x

B

C) (x(A-C)

x

B)∧(x(A-B)∧

(A-B)∩(A-C)∴A-(B∪C)=(A-B)∩(A-C)

N∧y=x},

2

六、已知R、S是N上的关系,其定义如下:R={| x,yS={| x,y分)

解:R={| x,yS*R={| x,y

-1

-1

N∧y=x+1}。求R、R*S、S*R、R{1,2}、S[{1,2}](10

N∧y=x},R*S={| x,y

2

2

N∧y=x+1},

2

N∧y=(x+1)},

-1

-1

-1

七、若f:A→B和g:B→C是双射,则(gf)=fg(10分)。

证明:因为f、g是双射,所以gf:A→C是双射,所以gf有逆函数(gf):C→A。同理可推fg:C→A是双射。

因为∈fg∈f

-1-1

-1

-1-1

存在z(∈g

-1

∈f)存在z(

-1

-1

-1-1

-1

∈g)∈gf∈(gf),所以(gf)=fg。

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)对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是哈密尔顿图

2证明 若n≥Cm。 ?1+2,则2n≥m-3m+6 (1)

2

若存在两个不相邻结点u、v使得d(u)+d(v)<m,则有2n=?d(w)<m+(mw?V-2)(m-3)+m=m-3m+6,与(1)矛盾。所以,对于G中任意两个不相邻结点u、v都有d(u)+d(v)≥m,所以G是哈密尔顿图。 离散数学试题(B卷及答案) 一、证明题(10分)

2