离散数学期末考试试卷（A卷）

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

一、判断题：（每题2分，共10分）

（1）

（1）

, 则

（0）

（2）对任意的命题公式 , 若

（3）设 是集合 上的等价关系, 是由 诱导的 上的等价关系，则

。 （1） （4）任意一个命题公式都与某一个只含合取和析取两种联结词的命题公式等价。 （0） （5）设

是

上的关系，

分别表示

的对称和传递闭包，则

（0）

二、填空题：（每题2分，共10分） (１) 空集的幂集的幂集为

（ ）。

(２) 写出 的对偶式 （ ）。

（３）设 是我校本科生全体构成的集合，两位同学等价当且仅当他们在 同一个班，则等价类的个数为（ ），同学小王所在 的等价类为（ ）。 （４）设 是 上的关系，则 满足下列性质的哪几条：自反的，对称的，传递的，反自反的，反对称的。 （ ）

(5)写出命题公式 的两种等价公式( ）。 三、用命题公式符号化下列命题（１）（２）（３），用谓词公式符号化下列命题（４）（５）（６）。（12分）

（１）（１）仅当今晚有时间，我去看电影。

（２）（２）假如上午不下雨，我去看电影，否则就在家里读书。 （3）你能通你能通过考试，除非你不复习。 （４）（４）并非发光的都是金子。

（５）（５）有些男同志，既是教练员，又是国家选手。 （６）（６）有一个数比任何数都大。 四、设

（１）（１）写出 五、求 分） 六、设 是 分） 七、设

到

的关系，

是

到

，给定 和

上的两个关系

和

分别是

的关系矩阵。（２）求

及

（1２分）

的主析取范式和主合取范式。（１０的关系，证明： 对某一个 ,有

（8

是一个等价关系，设

1

，证明： 也是一个等价关系。（10分）

八、（1０分）用命题推理理论来论证 下述推证是否有效？

甲、乙、丙、丁四人参加比赛，如果甲获胜，则乙失败；如果丙获胜，则乙也获胜，如果甲不获胜，则丁不失败。所以，如果丙获胜，则丁不失败。 九、（１０分） 用谓词推理理论来论证下述推证。

任何人如果他喜欢步行，他就不喜欢乘汽车，每一个人或喜欢乘汽车，或喜欢骑自行车（可能这两种都喜欢）。有的人不爱骑自行车，因而有的人不爱步行 (论域是人)。

十、(8分) 利用命题公式求解下列问题。

甲、乙、丙、丁四人参加考试后，有人问他们，谁的成绩最好， 甲说：“不是我，”乙说：“是丁，”丙说：“是乙，” 丁说：“不是我。” 四人的回答只有一人符合实际，问若只有一人成绩最 好，是谁？

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

一、判断题：（每题2分，共10分）

（1）x?{x}?{{x}} （ ?）

(2) 对任意的命题公式A,B,C, 若 A?C?B?C, 则A?B ( ? )

A（3）设R是集合A上的等价关系, L是由R诱导的A上的等价关系，则R?L。 ( ? )

（4） 任意一个命题公式都与某一个只含合取和析取两种联结词的命题公式等价。 （ ? ）

（5）设R是A上的关系，s(R),t(R)分别表示R的对称和传递闭包，则

ts(R)?st(R) （ ? ） 二、填空题：（每题2分，共10分）

(１) 空集的幂集的幂集为 ( {{?},?})。 (２) 写出(P?Q)?(P?R)的对偶式（ (P?Q)?(?P?R) ）。 （３）设A是我校本科生全体构成的集合，两位同学等价当且仅当他们在 同一个班，则等价类的个数为（我校本科生的班级数 ），同学小王所在 的等价类为（小王所在的班的集合）。

（４）设A?{1,2,3},R?{?1,2?,?1,3?}是A上的关系，则R满足下列性质的哪

几条：自反的，对称的，传递的，反自反的，反对称的。 （ 传递的，反自反的，反对称的 ）

(5)写出命题公式P?Q的两种等价公式( (P?Q)?(Q?P)(?P?Q)?(?Q?P)）。

三、用命题公式符号化下列命题（１）（２）（３），用谓词公式符号化下列命题（４）（５）（６）。（12分）

（３）（１）仅当今晚有时间，我去看电影。

2

解：P: 今晚我有时间. Q: 我去看电影 （４）（２）假如上午不下雨，我去看电影，否则就在家里读书。 Q?P

解 P: 上午下雨, Q: 我去看电影 R: 我在家里读书。 （3）你能通你能通过考试，除非你不复习。 (?P?Q)?(P?R)

解 P你能通过考试， Q: 你复习.

Q?P

（７）（４）并非发光的都是金子。

解 A(x):x是发光的， B(x):x是金子

?(?x)(A(x)?B(x))（８）（５）有些男同志，既是教练员，又是国家选手。

解 A(x):x是男同志，B(x):x是教练员，C(x):x是国家选手 (?x)(A(x)?B(x)?C(x)）

（９）（６）有一个数比任何数都大。 解 A(x):x是数，B(x,y):x比y大，

(?x)(A(x)?(?y)(A(y)?B(x,y)))c,d}

四、设A?{a,b,，给定A上的两个关系R和L分别是

R?{(a,b),(b,c),(c,a)},L?{(a,d),(b,b),(c,a),(c,c),(d,a),(d,c)}.?L) （２）（１）写出R和L的关系矩阵。（２）求R?L及t(R（1２分）解

??000?1?0100?M0010??R????M010?0L??1000????101?0

?0000??? ?101??0 ??0100??1010?M??1010?R?L???0101???0001?M(R?L)2???0000??0000????

?0000?

??0101??1010?M(R?L)3??1010????M0101?(R?L)4????0000??0000??0000???? ?0000?

3

Mt(R?L)五、求(P?(Q?R))?(?P?(?Q??R))的主析取范式和主合取范式。（１０分） (P?(Q?R))?(?P?(?Q??R))?(?P?(Q?R))?(P?(?Q??R))?(?P?Q)?(?P?R)?(P??Q)?(P??R)?(?P?Q?R)?(?P?Q??R)?(?P?Q?R)?(?P??Q?R)?(P??Q?R)?(P??Q??R)?(P??R?Q)?(P??R??Q)?(?P?Q?R)?(?P?Q??R)?(?P??Q?R)?(P??Q?R)?(P??Q?R)?(P?Q??R)??1,2,3,4,5,6解

??0,7?1111??1111?????0001???0000??

六、设Tccc是X到Y的关系，S是Y到Z的关系，证明：(T?S)?S?T（8分） 证明：

?z,x??(T?S)c??x,z??T?S?(?y)(y?Y??x,y??T??y,z??S)?(?y)(y?Y??y,x??Tc??z,y??Sc)??z,x??ScTc

七、设R是一个等价关系，设S?{?a,b?:对某一个c,有?a,c??R,且?c,b??R}，证明：S也是一个等价关系。（10分） 证明：（1） 对任一x?A, 因为R在A上是自反的，

所以?x,x??R. 由S的定义，?S, 所以S是自反的。

（３）（２）对任意x,y?A，若?x,y??S,则对于某个c 使得?x,c??R??c,y??R,因为R对称的，故有：?y,c??R??c,x??R,由S的定义可知：?y,x??S, 所以S是对称的。

（3）对任意x,y,z?A，若?x,y??S及?y,z??S,

则必存在某个c1，使得?x,c1??R??c1,y??R,由R传递性，可知?x,y??R，同理存在c2使得?y,c2??R??c2,z??R,由R传递性，可知?y,z??R。 再由S的定义，得?x,z??S,故 S是传递的。 综上可知，S是A上的等价关系。

八、（1０分）用命题推理理论来论证下述推证是否有效？

甲、乙、丙、丁四人参加比赛，如果甲获胜，则乙失败；如果丙获胜，则乙也获

4