离散数学期末考试试卷(A卷)

2离散数学期末考试试卷(A卷)〔每题2分，共10分〕〔1〕对任意的命题公式,假设 ,则〔0〕设是集合上的等价关系,是由 诱导的上的等价关系，则。 〔1〕任意一个命题公式都与某一个只含合取和析取两种联结词的命题公式等价。〔0〕设是上的关系， 分别表示〔0〕〔每题2分，共10分〕(１)空集的幂集的幂集为 〔 。(２)写出 的对偶式 〔 。〔３〕设校本科生全体构成的集合，两位同学等价当且仅当他们在同一个班，则等价类的个数为〔 ，同学小王所在的等价类为〔 。〔４〕设是 上的关系，则 性质的哪几条：自反的，对称的，传递的，反自反的，反对称的。〔 〕(5)写出命题公式 的两种等价公式( 。三、用命题公式符号化以下命题〔１〔２〔３，用谓词公式符号化以下命题〔４〔５〔６〔12分〕〔１〕〔１〕仅当今晚有时间，我去看电影。〔２〕〔２〕假设上午不下雨，我去看电影，否则就在家里读书。〔3〕你能通你能通过考试，除非你不复习。〔４〕〔４〕并非发光的都是金子。〔５〕〔５〕有些男同志，既是教练员，又是国家选手。〔６〕〔６〕有一个数比任何数都大。

，给定

上的两个关系和分别是写出五、求分〕

和的关系矩阵〔２〕求及 〔1２分〕〔１０分〕

是到的关系，是是一个等价关系，设

的关系，证明： 对某一个,有，证明： 也是一个等价关系〔10分〕八〔1０分〕用命题推理理论来论证 下述推证是否有效？甲、乙、丙、丁四人参与竞赛，假设甲获胜，则乙失败；假设丙获胜，则乙也获胜，假设甲不获胜，则丁不失败。所以，假设丙获胜，则丁不失败。〔１０分〕用谓词推理理论来论证下述推证。自行车〔可能这两种都宠爱域是人)。(8利用命题公式求解以下问题。甲、乙、丙、丁四人参与考试后，有人问他们，谁的成绩最好，好，是谁？离散数学期末考试试卷答案(A卷)〔每题2分，共10分〕〔1〕x{x}{{x}} 〔〕(2)对任意的命题公式A,B,C,假设ACBC,则AB ( )

R是集合

A,

L是由

ARA上的等价关系，则RL。 ( )命题公式都与某一个只含合取和析取两种联结词的命题公式等价。 〔 〕〔5〕RA上的关系，sRtR分别表示R的对称和传递闭包，则ts(R)st(R) 〔 〕〔每题2分，共10分〕(１)空集的幂集的幂集为 ( {{},})。(２)写出PQPR的对偶式〔PQ(PR)。〔３〕A是我校本科生全体构成的集合，两位同学等价当且仅当他们在同一个班，则等价类的个数为〔我校本科生的班级数，同学小王所在的等价类为〔小王所在的班的集合。〔４〕A{1,2,3R{1,21,3AR满足以下性质的哪〔传递的，反自反的，反对称的〕(5) 写出命题公式 PQ 的两种等价公式( PQ(QP)(PQ(QP。三、用命题公式符号化以下命题〔１〔２〔３，用谓词公式符号化以下命题〔４〔５〔６〔12分〕〔３〕〔１〕仅当今晚有时间，我去看电影。解：P:今晚我有时间. Q:我去看电影QP假设上午不下雨，我去看电影，否则就在家里读书。解P:上午下雨, Q:我去看电影R:我在家里读书。(PQ)(PR)〔3〕你能通你能通过考试，除非你不复习。解P 你能通过考试，Q:你复习.QP〔７〕〔４〕并非发光的都是金子。解Ax):x是发光的，Bx):x是金子(x)(A(x)B(x))〔８〕〔５〕有些男同志，既是教练员，又是国家选手。解Ax):xBx):xCx):x是国家选手(x)(A(x)B(x)C(x)〕〔９〕〔６〕有一个数比任何数都大。解Ax):xBx,y):xy大，(x)(A(x)(y)(A(y)B(x,y)))四A{abcdARL分别是R{(a,b),(b,c),(c,a)},L{(a,d),(b,b),(c,a),(c,c),(d,a),(d,c)}.〔２〕〔１〕RL〔２〕RL及t(RL〔1２分〕解0100

00010010 0100M

M R

L 1010 0000

10100100 1010 0101M M RL 0001

(RL)2

0000 0000 00000101 1010 0101M M (RL)3

0000

(RL)4

0000 0000 000011111111M t(RL)

0001 0000五(P(QR))(P(QR))的主析取范式和主合取范式〔１０分〕(P(QR))(P(QR))(P(QR))(P(QR))(PQ)(PR)(PQ)(PR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PRQ)(PRQ)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)1,2,3,4,5,60,7解 六、设0,7X到YS是YZ(TS)c证明：z,x(TS)cx,zTS(y)(yYx,yTy,zS)(y)(yYy,xTcz,ySc)z,xScTc

Sc

Tc〔8分〕七、设R 是一个等价关系，设S{a,b: 对某一个c ,有acR,且cbRS〔10分〕1〕xA,RA上是自反的，所以x,xR.S的定义，<x,x>S,S是自反的。〔３〕〔２〕x,yA，假设x,ySc使得xcRc,yRRycRc,xR由SyxS,S是对称的。〔3〕x,yzA，假设x,yS及yzS,12则必存在某个c1x,c12

Rc1

,yRRx,yR，2同理存在c2

使得yc

Rc2

zR,R传递性，可知yzR。S的定义，得xzS故S是传递的。SA上的等价关系。〔1０分〕用命题推理理论来论证下述推证是否有效？甲、乙、丙、丁四人参与竞赛，假设甲获胜，则乙失败；假设丙获胜，则乙也获解：B：乙获胜。C：丙获胜。D:丁获胜。ABCBADCD〔1〕AB P(2) BA (1)T,E(3) AD P(4) BD (2)(3)T,I(5) CB P(6) CD (5)(4)T,I〔１０分〕用谓词推理理论来论证下述推证。自行车〔可能这两种都宠爱。有的人不爱骑自行车，因而有的人不爱步行(论域是人)。宠爱不行。Q(x)宠爱乘汽车。R(x):x宠爱骑自行车。(XP(X)Q(x)),(X)(Qx)Rx)),(x)R(x)(x)P(x)〔1〕(x)R(x) P(2) R(c) (1)ES(3) (X)(Q(x)R(x)) P(4) Q(c)R(c) (3)US(5) Q(c) (2)(4)T,I(6) (X)(P(X)Q(x)) P(7) P(c)Q(c)) (6)US(8) P(c) (9) (x)P(x) (8)EG十、(8分)利用命题公式求解以下问题。好，是谁？A:甲的成绩最好，B:乙的成绩最好，C:丙的成绩最好，D:丁的成绩最好。由于四人的答复只有一人符合实际，故(ADBD)(ADBD)((ADBD)(AD