离散数学期末考试试题与答案

1. (6分) 已知 A=a,a,b, B=b, a, 求 AB, AB, P(A).,解: AB=(a,b), (a,a), (a, b), (a, a), (b, b), (b, a) AB=(A-B) (B-A)=a, b, b P(A)=, a, a, b, a, a, a,b, a,b, A.,4. (6分) A=1,2,3,5,10,15,30, x,yA, xyx|y. (1) 画出(A, )的哈斯图 (2) 判断(A, )是格否?分配格吗?有补格?布尔格吗?,格? 分配格? ?有补格? 布尔格 ,5. 已知 f: AB, g: BC, f是单射,g是单射,证明gf 是单射. 若gf是满射,证明g是满射.,证明: (1) 对于任意的x1,x2A, 若gf (x1)= gf (x2), 即有 g(f(x1)= g(f(x2).由于g是单射,故有f(x1)=f(x2). 由于f是单射,故有x1=x2. 因而, gf 是单射.(2) 对于任意zC, 存在xA, 使得gf (x)=z,即 g(f(x)=z.故存在 y=f(x) B, 使得g(y)=z.故 g是满射.,7. (5分) 画出5个顶点的自互补图。证明当n=4k 或4k+1时才有. 若一个图和它的补图同构，说它是自互补图。,解:（1）,（2）因为n个顶点的无向完全图有n(n-1)/2个边，所以自互补图各有n(n-1)/4个边，因此，n=4k或4k+1。,17. (4分) 试求公式 (pq)(qr)p)的主析取范式和主合取范式.,解: (pq)(qr)p) = (pq)(qr)p) = (pq)(qr) p) (qr) p) = (pq)(qp)(rp) (qr) p) = pq (qp)(rp) (qrp) = pq (qrp) = (pqr) (pqr) (pqr) (pqr) (pqr) (pqr) (pqr) =(0,1,2,3,4,5,6) =(7)= pqr,18. (6分) 将下列语句化为含有量词的谓词演算公式,不是每个人都能干,但一定有人能干.有一种气体可以腐蚀任何金属. 凡是对顶角一定相等.,解: ( x(P(x) A(x) (x(P(x) A(x) x(G(x) (y(M(y) R(x,y) xy(A(x,y) (x=y),19. (5分) 已知公理 A: (pq) (qp) (pq) B: ppq C: pp D: (pr) (qr) (pq) r) E: pqp 证明定理: p(pp),证明:(1) ppq 公理B(2) ppp 代入(3) (pr) (qr) (pq) r) 公理D(4) (pp) (pp) (pp) p) 代入(5) p p 公理C(6) (pp) (pp) p) (4)(5)分离(7) (pp) p (5)(6)分离(8) (pq) (qp) (pq) 公理A(9) (p(pp) (pp)p) (p(pp) 代入(10) (pp)p) (p(pp) (2)(9)分离(11) (p(pp) (7)(10)分离,20. (5分) 试求公式 x(yX(x,y