离散数学期末试卷

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

--------------------------------------------------------------------------------------------------------------------------------------------------- 03．A?{?,{a},{b},{a,b}}上的包含关系为?，则子集C?{{a},{b}}的极大元为

＿＿＿＿，极小元为＿＿＿＿，上界为＿＿＿＿，下界为＿＿＿＿，最大元为＿＿＿， 最小元为＿＿＿（若没有填无）。 04．设A?{a,b}，则A上共有＿＿＿个不同的等价关系。

05．有一个函数f:X?Y，若要使f有逆函数，f就必须是＿＿＿。

三、演算题（每小题10分，总30分）

年级 专业 姓名 学号 座位号

大登

一、单项选择（在备选答案中选出一个正确答案，并将其号码填在题干后的括号内。每题3分，共18分） 01．下列语句中，真命题是（ ）

A、我正在说谎； B、若1?2?3，则雪是黑的； C、这句话是错的； D、若1?2?5，则太阳绕地球转。 02．下列哪个公式是永真式（ ）

A、(P?Q)?(Q?P)； B、(P?Q)?P； C、(?(P?Q))?(?(?P??Q))； D、?(P?Q)。

03．对任意集合A，B，C，下列结论正确的是（ ）

A、若A?B，B?C，则A?C； B、若A?B，B?C，则A?C； C、若A?B，B?C，则A?C； D、若A?B，B?C，则A?C。 04．A?{1,2,3}上的关系R?{?1,1?,?1,2?,?1,3?,?3,3?}，则R具备（ ） A、传递性与反对称性； B、传递性与对称性； C、自反性与对称性； D、反自反性与对称性。 05．下述4个集合中，属于拟序集合的是（ ） A、??({a}),??； B、??(N),??； C、??(N),??； D、??(?),??。 06．下列集合中基数等于c的是（ ） A、{0,1,2,...,n?1}； B、N； C、N?N； D、[2,4]。

二、填空题（以下每个下划线为一空，请按要求填入合适的内容。每空2分，共22分）。

01．有一集合A?{1,{2}}，则A的幂集为＿＿＿＿＿＿＿＿。 02．设C?{{1,2,4},{3,4,5},{4,6}}，则

S?CS?C装项 分 一 二 三 四 五 六 七 总分 阅卷人 得 分 1、用谓词和量词将下列命题符号化。

1）每个有理数都是实数；

2）某些实数是有理数；

3）不是每一个实数都是有理数； 4）没有不犯错误的人； 5）会叫的狗未必会咬人。

2、求公式?((P?Q)?R)?R所对应的主析取范式和主合取范式（注：用公式推导法）。 3、某学院学生选课情况如下：260人选艺术课，208人选生物课，160人选计算机课，76人选艺术与生物课，48人选艺术与计算机课，62人选生物与计算机课，全部三门课程都选的是30人，三门都不选的是150人。问： 1）共有多少学生？

2）有多少学生选艺术和生物课，但不选计算机课？

四、证明题（每小题10分，总30分）

1. 试证：?B是?B?D，(E??F)??D，?E的有效

结论。

2. 设R是集合A上的一个传递和自反关系，T是A上的另一个关系，使得?a,b??T，当

且仅当?a,b??R??b,a??R。证明T是一个等价关系。

3. 假定f:X?Y且g:Y?Z是映射（函数），使得g?f是一个单射，且f是满射。证明

得 分 得分 订g是一个单射。

线

得 分 ?S为＿＿＿＿，?S为＿＿＿＿。

1 学生答题注意：勿超黑线两端；注意字迹工整。 2

安徽大学2004-2005学年第一学期 《离散数学》期末考试试卷（A卷）参考答案

一、单项选择

01．D; 02.B; 03.A; 04.A; 05.C; 06.D. 二、填空题

01．{?,{1},{{2}},{1,{2}}}；02．{1,2,3,4,5,6}，{4}；03．{a}和{b}，{a}和{b}，{a,b}，

四、证明题

A B

C

?，无，无；04．2；05．双射。

三、演算题（每小题10分，总30分）

1、解：

1）设Q(x)：x是有理数；R(x)：x是实数。则此命题可表示为：?x(Q(x)?R(x))。 2）设R(x)：x是实数；Q(x)：x是有理数。则此命题可表示为：?x(R(x)?Q(x))。 3）设R(x)：x是实数；Q(x)：x是有理数。则此命题可表示为：?(?x(R(x)?Q(x)))。 4）设H(x)：x是人；P(x)：x犯错误。则此命题可表示为：

1．证明：

（1） ?(?B) P（附加前提） （2） ?B?D P

（3） D T,(1),(2),I

（4） (E??F)??D P

（5） ?(E??F) T,(3),(4),E （6） ?(?E??F) T,(5),E （7） E?F T,(6),E

（8） E T,(7),I （9） ?E P

（10） E??E T,(8),(9),I （矛盾） 所以?B?D，(E??F)??D，?E??B。

?(?x(H(x)??P(x)))??x(H(x)?P(x))。

5）设D(x)：x是会叫的狗；R(x)：x是会咬人的狗。则此命题可表示为：?x(D(x)??R(x))。

2、解：

2．证明：

a) 对任意a?A，因为R为A上自反关系，故有：?a,a??R。由T的充要条件，得到

?a,a??T，所以T是自反的。

b) 对任意a,b?A，若?a,b??T??a,b??R??b,a??R?

（主析取范式） ?b,a??R??a,b??R??b,a??T，所以T是对称的。 ??((?P?Q??R)?(P??Q??R)?(?P??Q??R)) c) 对任意a,b,c?A，若有?a,b??T??b,c??T ?(p??Q?R)?(?p?Q?R)?(p?Q?R) （主合取范式） ??a,b??R??b,a??R??b,c??R??c,b??R

??a,b??R??b,c??R??c,b??R??b,a??R 3、解：设A?{选修艺术课学生 }，B?{选修生物课学生}，C?{选修计算机课学生}。

??a,c??R??c,a??R??a,c??T，所以T是传递的。

按题意有|A|?260，|B|?208，|C|?160，|A?B|?76，|A?C|?48，|B?C|?62，

于是T是A上的等价关系。

|A?B?C|?30，|A?B?C|?150。 3．证明： 1） 生总数为： 假定g不是一个单射，则存在y1和y2，使得y1?y2时，有g(y1)?g(y2)。因为f是满

N?|A?B?C|?|A?B?C|?|A|?|B|?|C|?|A?B|?|A?C|?|B?C| 射，对于y和y存在必有x和x使得f(x)?y，f(x)?y。因为f是函数，所以

12121122?((P?Q)?R)?R ?（P?Q)?R?R ?（P?Q)?R

?(P?Q?(R??R))?((P??P)?(Q??Q)?R)

?(P?Q?R)?(P?Q??R)?(P??Q?R)?(?P?Q?R)?(?P??Q?R)?|A?B?C|?|A?B?C|?260?208?160?76?48?62?30?150?622

2）由图3-2可知：|A?B?C|?|A?B|?|A?B?C|?76?30?46

f(x1)?f(x2)时，x1?x2。现在考虑在x1和x2时g?f的值，

g?f(x1)?g[f(x1)]?g(y1)?g(y2)?g[f(x2)]?g?f(x2) 这与g?f是单射矛盾。

3 学生答题注意：勿超黑线两端；注意字迹工整。 4

本文来源：https://www.bwwdw.com/article/x4vh.html