离散试卷有答案..doc

文档介绍：离散数学试题(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分)
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的整数倍
证明设,,…,为任取的m+1个整数,用m去除它们所得余数只能是0,1,…,m-1,由抽屉原理可知,,,…,这m+1个整数中至少存在两个数和,它们被m除所得余数相同,因此和的差是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=x2},S={<x,y>| x,yÎN∧y=x+1}。求R-1、R*S、S*R、R{1,2}、S[{1,2}](10分)
解:R-1={<y,x>| x,yÎN∧y=x2},R*S={<x,y>| x,yÎN∧y=x2+1},S*R={<x,y>| 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是双射。
因为<x,y>∈f-1g-1Û存在z(<x,z>∈g-1Ù<z,y>∈f-1)Û存在z(<y,z>∈fÙ<z,x>∈g)Û<y,x>∈gfÛ<x,y>∈(gf)-1,所以(gf)-1=f-1g-1。
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。
九、给定简单无向图G=<V,E>,且|V|=m,|E|=n。试证:若n≥+2,则G是哈密尔顿图
证明若n≥+2,则2n≥m2-