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

《离散数学期末考试题及答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、.离散数学试题(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(置换)ÛR2)$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)的主析取范式和主

2、合取范式（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)®ØEP(2)ØE®(A∧ØB)P(3)(C∨D)®(A∧ØB)T(1)(2)，I(4)(A∧ØB)®(R∨S)P(5)(C∨D

3、)®(R∨S)T(3)(4)，I(6)C∨DP(7)R∨ST(5)，I2)"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

4、人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。而6个会打网球的人都会打另外一种球，求不会打这三种球的人数（10分）。解：A，B，C分别表示会打排球、网球和篮球的学生集合。则

5、A

6、=12，

7、B

8、=6，

9、C

10、=14，

11、A∩C

12、=6，

13、B∩C

14、=5，

15、A∩B∩C

16、=2。先求

17、A∩B

18、。∵6=

19、（A∪C）∩B

20、=

21、（A∩B）∪（B∩C）

22、=

23、（A∩B）

24、+

25、（B∩C）

26、-

27、A∩B∩C

28、=

29、（A∩B）

30、+5-2，∴

31、（A∩B）

32、=3。于是

33、A∪B∪C

34、=12+6+14-6-5-3+2=20。不会打这三种球的人数25-20=5。五、已知A、B、C是三个集合，证明A-(B∪C)=

35、(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={

36、x，yÎN∧y=x2}，S={

37、x，yÎN∧y=x+1}。求R-1、R*S、S*R、R{1，2}、S[{1，2}]（10分）。解：R-1={

38、x，yÎN∧y=x2}R*S={

39、x，yÎN∧y=x2+1}S*R={

40、x，yÎN∧y=（x+1）2}，R{

41、1，2}={<1，1>，<2，4>}，S[{1，2}]={1，4}。七、设R={，，}，求r(R)、s(R)和t(R)（15分）。解：r(R)={，，，，，}..s(R)={，，，，，}R2=R5={，，}R3={，，}R4={，，}t(R)={，，，，，，，，，}八、

42、证明整数集I上的模m同余关系R={

43、xºy(modm)}是等价关系。其中，xºy(modm)的含义是x-y可以被m整除（15分）。证明：1）"x∈I，因为（x-x）/m=0，所以xºx(modm)，即xRx。2）"x，y∈I，若xRy，则xºy(modm)，即（x-y）/m=k∈I，所以（y-x）/m=-k∈I，所以yºx(modm)，即yRx。3）"x，y，z∈I，若xRy，yRz，则