大学《离散数学》期末考试试卷及答案(1)

安徽大学2006-2007学年第1学期 《离散数学》期末考试试卷（A卷）

（时间120分钟）

开课院（系、部） 姓名 学号 .

题 号 得分 一 二 三 四 五 六 七 得分 阅卷人 一、选择题（每小题2分，共20分）

得分 1．下列语句中，哪个是真命题（ ）

A、x?2?4； B、我们要努力学习；

C、如果ab为奇数，那么a是奇数，或b是偶数； D、如果时间流逝不止，你就可以长生不老。 2．下列命题公式中，永真式的是（ ）

A、(P?Q)?P； B、?(Q?P)?P； C、(P??P)?Q； D、P?(P?Q)。 3．在谓词逻辑中，令F(x)表示x是火车；G(y)表示y是汽车；L(x,y)表示x比y快。命题“并不是所有的火车比所有的汽车快”的符号表示中哪些是正确的？（ ） I.??x?y(F(x)?G(y)?L(x,y)) II.?x?y(F(x)?G(y)??L(x,y))

III. ?x?y(F(x)?G(y)??L(x,y))

A、仅I； B、仅III； C、I和II； D、都不对。 4．下列结论正确的是：（ ）

A、若A?B?A?C，则B?C； B、若A?B?A?B，则A?B；

C、若A?B?A?C，则B?C； D、若A?B且C?D，则A?C?B?D。 5．设A1??，A2?{?}，A3??({?})，A4??(?)，以下命题为假的是（ ） A、A2?A4； B、A1?A3； C、A4?A2； D、A4?A3。 6．设R是集合A?{a,b,c,d}上的二元关系，

R?{?a,d?,?d,a?,?a,c?,?c,a?,?b,d?,?d,b?}。下列哪些命题为真？（ ） I.R?R是对称的 II. R?R是自反的 III. R?R不是传递的

A、仅I； B、仅II； C、I和II； D、全真。 7．R是二元关系且R?R，则一定是传递的是（ ）

A、R ； B、R； C、R ； D、R。

8．设R1和R2是非空集合A上的等价关系，确定下列各式，哪些是A上的等价关系（ ） A、A?A?R1； B、R1?R2； C、R1?R2； D、R1?R2。 9．函数f:X?Y可逆的充要条件是：（ ）

A、A?B； B、|A|?|B|； C、f为双射； D、f为满射。 10．下列集合中，哪个集合的基数与其他集合的基数不同（ ） A、N（N为自然数集，n?N）； B、N（N为自然数集）； C、R?R（R为实数集）； D、x坐标轴上所有闭区间集合；

n4432N《离散数学》试卷 共3页第1页

二、填空题（每小题2分，共32分）

得分

1．全集U?{1,2,3,4,5}，A?{1,5}，B?{1,2,3,4}，C?{2,5}，则可求出：

A?B?_________________________________； ?(A)??(C)?___________________________；

C?_____________________________________。

2．设A?3，

?(B)?16，?(A?B)?64，则：

B=______________________________， A?B=__________________________，

A?B=__________________________， A?B=__________________________。

3．设A?{1,2,3,4}，R是A上的二元关系，且R?{?1,2?,?2,4?,?3,3?}，则

r(R)=________________________________________________； s(R)=________________________________________________； t(R)=________________________________________________；

4．设A={1,2,3,4,5}，则A上共有多少个二元关系________________？ 其中有多少个等价关系________________？

5．设函数f:A?A，B?A为A的子集。则：

f(ff?1?1(B))____________B，

?1(f(B))____________B；

(B))?B；

?1当f为__________函数时f(f当f为__________函数时f(f(B))?B。

《离散数学》试卷 共3页第2页

三、综合题（第2小题16分，其它各小题8分，共48分）

1．求命题公式((P?Q)??R)?P的主析取范式与主合取范式 （要求用等值演算的方法求解）。（8分）

2．用推理规则证明：（每小题8分，共16分）

①P?(Q?R)，?S?P，Q永真蕴含S?R。

得分 ②前提：?x(F(x)?(Q(y)?R(x)))，?xF(x)；结论：?x(F(x)?R(x))。

3．设集合A?{a,b,c}，?(A)是集合A的幂集，试给出??(A),??的哈斯图，并指出子集{{a},{b}}的极大元、极小元、最大元、最小元、上界、下界、最小上界、最大下届（如果存在的话）。（8分）

4．设R是集合A上的关系，令S?{?a,b??c?A,使?a,c??R且?c,b??R}，证明：如果R是等价关系，则S也是等价关系。（8分）

5．已知f:N?N?N，f(?x,y?)?x?y。请问：（8分） ①f是单射吗？ ②f是满射吗？ ③计算f

《离散数学》试卷 共3页第3页

22({0})。

④计算f({?0,0?,?1,2?})。

?1安徽大学2006-2007学年第1学期 《离散数学》期末考试试卷答案（A卷）

（时间120分钟）

一、选择题（每小题2分，共20分）

1．C;2.D;3.C;4.B;5.A;6.C;7.B;8.D;9.C;10.A

二、填空题（每空2分，共32分） 1．{5}；{?,{5}}；{1,3,4}

2．4，1，2，5

3．{<1,2>,<2,4>,<3,3>,<1,1>,<2,2>,<4,4>}；{<1,2>,<2,4>,<3,3>,<2,1>,<4,2>}；

{<1,2>,<2,4>,<3,3>,<1,4>} 4．225,52

5．?，满射，?，单射

三、综合题（第2小题16分，其它各小题8分，共48分）

1．

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

?(?P?R)?(?Q?R)?P 2分

?((?P?R)?(?Q?Q))?((?Q?R)?(P??P)?(P?(Q??Q)?(R??R))?(?P?Q?R)?(?P??Q?R)?(P??Q?R)?(?P??Q?R)? (P?Q?R)?(P?Q??R)?(P??Q?R)?(P??Q??R) ?(?P?Q?R)?(?P??Q?R)?(P??Q?R)?(P?Q?R)? (P?Q??R)?(P??Q??R)（主析取范式） 6分 ? ?A?(?P??Q??R)?(?P?Q??R)

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

?(P?Q?R)?(P??Q?R)（主合取范式） 8分

2．①证明：

(1) ?S?P P 1分 (2) S P（附加前提） 2分 (3) P T (1),(2) I 3分 (4) P?(Q?R) P 4分 (5) Q?R T (3),(4) I 5分 (6) Q P 6分 (7) R T (5),(6) I 7分 (8) S?R CP (2),(7) 8分 ②证明：

(1) ?xF(x) P 1分 (2) F(c) ES (1) 2分 (3) ?x(F(x)?(Q(y)?R(x))) P 3分 (4) F(c)?(Q(y)?R(c)) US (3) 4分

《离散数学》试卷 共3页第3页

4分 (5) Q(y)?R(c) T (2),(4) I 5分 (6) R(c) T (5) I 6分 (7) F(c)?R(c) T (2),(6) I 7分 (8) ?x(F(x)?R(x)) EG (7) 8分

3．解：??(A),??的哈斯图如下图所示。 {a,b,c}

{b,c} {a,c} {a,b}

{c}

{b} {a} ? （2分）；{{a},{b}}的极大元是：{a},{b}；极小元是：{a},{b}（4分）；最大元不存在；最小元不存在（6分）；上界有：{a,b},{a,b,c}；下界为：?；最小上界为：{a,b}；最大下界为：?（8分）。

4．证明：已知R是等价关系，对S是等价关系的证明分3步： （1）自反性

?R是自反的，

?对?a?A，有?a,a??R， 根据S的定义，有?a,a??S，

?S是自反的；（2分）

（2）对称性

如果?a,b??S，则?c?A，使?a,c??R且?c,b??R，

?R是对称的，

??b,c??R且?c,a??R， ?再根据S的定义有?b,a??S， ?S是对称的；（5分）

（3）传递性

如果?a,b??S，?b,c??S，

则?d?A使?a,d??R，且?d,b??R。?R是传递的，??a,b??R。 则?e?A使?b,e??R，且?e,c??R。 ?R是传递的，??b,c??R。

?根据S的定义有?a,c??S。?S是传递的。（8分） 由（1），（2），（3）得S是等价关系。

5．解答：

①?1,2?,?2,1??N?N，f(?1,2?)?f(?2,1?)?1?2?5，但?1,2???2,1?，所以f不是单射（2分）。 ②3?N，但找不出这样的?x,y??N?N，使得f(?x,y?)?x?y?3。所以f不是满射（2分）。 ③f?12222({0})?{?x,y?x2?y2?0}，解之，得x?y?0，所以f?1({0})?{?0,0?}（2分）。

④f{?0,0?,?1,2?}?{0,5}（2分）。

《离散数学》试卷 共3页第3页