离散数学期末考试试卷(A卷).pdf
.离散数学期末考试试卷(A 卷)一、判断题：（每题 2 分，共 10 分）（1）（1）（2）对任意的命题公式,若,则 （0）（3）设 是集合 上的等价关系,是由 诱导的 上的等价关系，则。（1）（4）任意一个命题公式都与某一个只含合取和析取两种联结词的命题公式等价。（0）（5）设 是 上的关系，分别表示 的对称和传递闭包，则 （0）二、填空题：（每题 2 分，共 10 分）()空集的幂集的幂集为 （）。()写出 的对偶式 （）。（）设 是我校本科生全体构成的集合，两位同学等价当且仅当他们在 同一个班，则等价类的个数为（），同学小王所在 的等价类为（）。（）设 是 上的关系，则 满足下列性质的哪几条：自反的，对称的，传递的，反自反的，反对称的。（）(5)写出命题公式 的两种等价公式(）。三、用命题公式符号化下列命题（）（）（），用谓词公式符号化下列命题（）（）（）。（12 分）（）（）仅当今晚有时间，我去看电影。（）（）假如上午不下雨，我去看电影，否则就在家里读书。（3）你能通你能通过考试，除非你不复习。（）（）并非发光的都是金子。（）（）有些男同志，既是教练员，又是国家选手。（）（）有一个数比任何数都大。四、设，给定 上的两个关系 和 分别是 （）（）写出 和 的关系矩阵。（）求 及（1分）五、求 的主析取范式和主合取范式。（分）六、设 是 到 的关系，是 到 的关系，证明：（8分）七、设 是一个等价关系，设 对某一个,有.，证明：也是一个等价关系。（10 分）八、（1分）用命题推理理论来论证 下述推证是否有效？甲、乙、丙、丁四人参加比赛，如果甲获胜，则乙失败；如果丙获胜，则乙也获胜，如果甲不获胜，则丁不失败。所以，如果丙获胜，则丁不失败。九、（分）用谓词推理理论来论证下述推证。任何人如果他喜欢步行，他就不喜欢乘汽车，每一个人或喜欢乘汽车，或喜欢骑自行车（可能这两种都喜欢）。有的人不爱骑自行车，因而有的人不爱步行(论域是人)。十、(8 分)利用命题公式求解下列问题。甲、乙、丙、丁四人参加考试后，有人问他们，谁的成绩最好，甲说：“不是我，”乙说：“是丁，”丙说：“是乙，”丁说：“不是我。”四人的回答只有一人符合实际，问若只有一人成绩最 好，是谁？离散数学期末考试试卷答案(A 卷)一、判断题：（每题 2 分，共 10 分）（1）xxx （）(2)对任意的命题公式CBA,若 CBCA,则BA ()（3）设R是集合A上的等价关系,L是由RA诱导的A上的等价关系，则LR。()（4）任意一个命题公式都与某一个只含合取和析取两种联结词的命题公式等价。（）（5）设R是A上的关系，)(),(RtRs分别表示R的对称和传递闭包，则)()(RstRts （）二、填空题：（每题 2 分，共 10 分）()空集的幂集的幂集为 (,)。()写出)()(RPQP的对偶式（)()(RPQP）。（）设A是我校本科生全体构成的集合，两位同学等价当且仅当他们在 同一个班，则等价类的个数为（我校本科生的班级数），同学小王所在 的等价类为（小王所在的班的集合）。（）设,3121321RA是A上的关系，则R满足下列性质的哪几 条：自 反 的，对 称 的，传 递 的，反 自 反 的，反 对 称 的。（传递的，反自反的，反对称的）(5)写出命题公式QP 的两种等价公式()()()()(PQQPPQQP）。三、用命题公式符号化下列命题（）（）（），用谓词公式符号化下列命题（）（）（）。（12 分）（）（）仅当今晚有时间，我去看电影。.0000000111111111)(LRtM 五、求)()(RQPRQP的主析取范式和主合取范式。（分）解70654321,)()()()()()()()()()()()()()()()()()()()()()(RQPRQPRQPRQPRQPRQPQRPQRPRQPRQPRQPRQPRQPRQPRPQPRPQPRQPRQPRQPRQP六、设T是X到Y的关系，S是Y到Z的关系，证明：cccTSST)(（8 分）证明：cccccTSxzSyzTxyYyySzyTyxYyySTzxSTxz,),)(),)(,)(,七、设R是 一 个 等 价 关 系，设:,baS对 某 一 个c,有,RbcRca且，证明：S也是一个等价关系。（10 分）证明：（1）对任一Ax,因为 R 在 A 上是自反的，所以Rxx,.由 S 的定义，S,所以 S 是自反的。（）（）对任意Ayx,，若,Syx则对于某个c 使得,RycRcx因为R 对称的，故有：,RxcRcy由S 的定义可知：,Sxy 所以S 是对称的。（3）对任意Azyx,，若Syx,及,Szy 则必存在某个1c，使得,RycRcx11由 R 传递性，可知Ryx,，同理存在2c使得,RzcRcy22由 R 传递性，可知Rzy,。再由S 的定义，得,Szx故 S 是传递的。综上可知，S 是 A 上的等价关系。八、（1分）用命题推理理论来论证 下述推证是否有效？甲、乙、丙、丁四人参加比赛，如果甲获胜，则乙失败；如果丙获胜，则乙也获.胜，如果甲不获胜，则丁不失败。所以，如果丙获胜，则丁不失败。解：设 A：甲获胜。B：乙获胜。C：丙获胜。D:丁获胜。前提为：DABCBA,结论为：DC （1）BA P (2)AB (1)T,E(3)DA P(4)DB (2)(3)T,I(5)BC P(6)DC (5)(4)T,I 九、（分）用谓词推理理论来论证下述推证。任何人如果他喜欢步行，他就不喜欢乘汽车，每一个人或喜欢乘汽车，或喜欢骑自行车（可能这两种都喜欢）。有的人不爱骑自行车，因而有的人不爱步行(论域是人)。解：设 P(x):x 喜欢不行。Q(x)喜欢乘汽车。R(x):x 喜欢骑自行车。本题符号化为：),()()(),()()(xRxQXxQXPX)()()()(xPxxRx（1）)()(xRx P(2)(cR (1)ES(3)()()(xRxQX P (4)()(cRcQ (3)US (5)(cQ (2)(4)T,I (6)()()(xQXPX P (7)()(cQcP (6)US (8)(cP (5)(7)T,I(9)()(xPx (8)EG 十、(8 分)利用命题公式求解下列问题。甲、乙、丙、丁四人参加考试后，有人问他们，谁的成绩最好，甲说：“不是我，”乙说：“是丁，”丙说：“是乙，”丁说：“不是我。”四人的回答只有一人符合实际，问若只有一人成绩最 好，是谁？解：设 A:甲的成绩最好，B:乙的成绩最好，C:丙的成绩最好，D:丁的成绩最好。因为四人的回答只有一人符合实际，故 TDBDADBDADBDADBDA)()()()(.即 TDBADBA)()(但)()()()()()(CDBACDBACDBACDBADBADBA 故有（一）甲、丙、丁三人并列成绩最好。（二）甲、丁并列成绩最好。（三）甲、丙并列成绩最好。(四)甲的成绩最好。只有一人成绩最好的是甲。
