安徽大学2007-2008学年第1学期 《离散数学》期末考试试卷（B卷）
（时间120分钟）
开课院（系、部） 姓名 学号 .
题 号 得分 一 二 三 四 五 六 七 得分 一、选择题（每小题2分，共20分） 得分 1．设P:2?2?5，Q:雪是黑的，R:2?4?8，S:太阳从东方升起，下列命题中真值为T的是（ ） A、P?Q?R； B、R?P?S； C、S?Q?R； D、(P?R)?(Q?S)。 2．下列命题公式中，为重言式的是（ ） A、P?(Q?R)； B、(P?R)?(P?Q)； C、(P?Q)?(Q?R)； D、(P?(Q?R))?((P?Q)?(P?R))。 3．设L(x):x是演员，J(x):x是老师，A(x,y):x钦佩y，命题“所有演员都钦佩某些老师”符号化为（ ） A、?x(L(x)?A(x,y))； B、?x(L(x)??y(J(y)?A(x,y)))； C、?x?y(L(x)?J(y)?A(x,y))； D、?x?y(L(x)?J(y)?A(x,y))。 4．设A?{?} ， B??(?(A))，以下各小题中不正确的有（ ） A、{{?}}?B； B、{?,{{?}}}?B ； C、{?,{{?}}}?B； D、{{?},{?,{?}}}?B。 5．设A?? ， B?{?,{?}}，则B?A是（ ）。 A、 {{?}}； B、{?} ； C、 {?,{?}}； D、 ?。 6．设A?{a,b,c}，R,S,T是集合?(A)上的二元关系。其中，R?{?x,y?|x?y}，
S?{?x,y?|x?y??}，T?{?x,y?|x?y?A}。下列哪些命题为真？（ ） I.R是反自反、反对称和传递的 II.S是反自反和对称的 III.T是反自反和对称的 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．I是整数集合，函数f定义为：I?I，f(x)?x?2x，则f是： （ ） A、单射； B、满射； C、双射； D、非单射也非满射。 10．下列集合中，哪个集合的基数与其他集合的基数不同（ ） A、N（N为自然数集，n?N）； B、N（N为自然数集）； C、R?R（R为实数集）； D、x坐标轴上所有闭区间集合；
《离散数学》试卷 共5页第1页
nN4324
二、填空题（每小题2分，共32分）
得分
1．设P:小王走路，Q:小王听音乐，在命题逻辑中，命题“小王边走路边听音乐”的符号化形式为：
________________________；设F(x):x是人，H(x,y):x与y一样高，在谓词逻辑中，命题“人都不一样高”的符号化形式为________________________________________________。
2．设M?{x|1?x?12,x被2整除，x?Z}， N?{x|1?x?12,x被3整除，x?Z}， 则M?N?________________________，M?N?________________________。
3．在自然数集N中，偶数集为N1，奇数集为N2，则N1?N2=________________________，
N1?N2=________________________。
4．设集合A?{1,2,3,4}上的二元关系R?{?1,2?,?2,4?,?3,3?,?1,3?}，则 r(R)=________________________________________________； s(R)=________________________________________________； t(R)=________________________________________________；
5．设A?{1,2,3,4}，则A上共有多少个二元关系________________；其中有多少个等价关系
________________；在等价关系中，商集为二元集（即有两个元素的集合）的有________________个。
6．设A?{0,1}，N为自然数集，f(x)???0,x是奇数。若f:A?A，则f是__________射的，若
1,x是偶数?f:N?A，则f是__________射的。
7． 设函数f:A?A，B?A为A的子集。则下列集合之间的关系是f(f?1(B))____________B，
f?1(f(B))____________B。
三、综合题（第2小题16分，其它各小题8分，共48分）
1．用等值演算方法，按要求求解。（8分） （1）求命题公式(?p?q)?(?q?p)的主析取范式；（4分） （2）求命题公式?(p?q)?q?r的主合取范式。（4分）
《离散数学》试卷 共5页第3页
2．用推理规则证明：（第1小题6分，第二小题10分，共16分） （1）?(P??Q)，?Q?R，?R永真蕴含?P。（6分）
（2）前提：?x(F(x)?S(x))??y(M(y)?R(y))，?y(M(y)??R(y))；
结论：?x(F(x)??S(x))。（10分）
3．设A?{1,2,3,4,5}，A上的篇序关系R?{?1,2?,?3,2?,?4,1?,?4,2?,?4,3?,?3,5?,
（共8分） ?4,5?}?IA。
（1）作出篇序关系R的哈斯图；（2分）
（2）令B?{1,2,3,5}，求B的最大、最小、极大、极小元，上界，最小上界，下界，最大下界。（6分）
4．设A?{1,2,3,...,9}，在A?A上定义关系R：??a,b?,?c,d???R当且仅当a?d?b?c，证明R是A?A上的等价关系，并求出[?2,5?]R。（8分）
5．设f:N?N，g:N?N均是函数，N为自然数集，且
x为偶数?x/2?x?1x?0,1,2,3??x?4 f(x)??0，g(x)?? （共8分）
?x?3x?5x为奇数??①求g?f。 （2分）
②g?f是单射，满射吗？（2分） ③设A?{0,1,2}，求g?f(A)。（2分） ④设B?{0,1,2}，求(g?f)(B)。（2分）
《离散数学》试卷 共5页第3页
?1
安徽大学2007-2008学年第1学期《离散数学》期末考试试卷答案（B卷）
一、选择题（每小题2分，共20分）
1. A；2. D；3. B；4. B；5 C；6. D；7. B；8. D；9. A；10. A。 二、填空题（每空2分，共32分）
1. P?Q，?x?y(F(x)?F(y)??H(x,y))； 2. {6,12}，{2,4,8,10}； 3. N2，?；
4. {?1,2?,?2,4?,?3,3?,?1,3?,?1,1?,?2,2?,?4,4?}，
{?1,2?,?2,4?,?3,3?,?1,3?,?2,1?,?4,2?,?3,1?}， {?1,2?,?1,3?,?1,4?,?2,4?,?3,3?}；
5. 2（65536），15，7； 6. 双射，满射； 7. ?，?；
三、综合题（第2小题16分，其它各小题8分，共48分） 1．（1）解：(?p?q)?(?q?p)??(p?q)?(?q?p)
?(?p??q)?(?q?p)?(?p??q)??q?p（2分） ?(?p??q)??q?(p??p)?p?(q??q)
?(?p??q)?(?q?p)?(?q??p)?(p?q)?(p??q) ?(p?q)?(p??q)?(?p??q)（主析取范式）（4分）
（2）?(p?q)?q?r??(?p?q)?q?r?(p??q)?q?r?p?r?F?F ??(0,1,2,3,4,5,6,7)
16?(p?q?r)?(p?q??r)?(p??q?r)?(p??q??r)?
(?p?q?r)?(?p?q??r)?(?p??q?r)?(?p??q??r)（主合取范式）（4分）
2．（1）证明：
① ?(P??Q) P
② ?P?Q T,①,E （1分） ③ P?Q T,②,E （2分） ④ ?Q?R P
⑤ Q?R T,④,E （3分） ⑥ P?R T,③, ⑤,I （4分） ⑦ ?R P
⑧ ?P T,⑥, ⑦,I （6分） （2）证明：
(1) ?y(M(y)??R(y)) P
(2) M(c)??R(c) ES,(1) （1分） (3) ?(M(c)?R(c)) T,(2),E （2分） (4) ?y?(M(y)?R(y)) EG，(3) （3分） (5) ??y(M(y)?R(y) T,(4),E （4分） (6) ?x(F(x)?S(x))??y(M(y)?R(y)) P
(7) ??x(F(x)?S(x)) T,(5),(6),I （5分） (8) ?x?(F(x)?S(x)) T, (7),I （6分） (9)?(F(a)?S(a)) US,(8) （7分）
《离散数学》试卷 共5页第3页
(10) ?F(a)??S(a) T,(9),E （8分） (11) F(a)??S(a) T,(10),E （9分） (12) ?x(F(x)??S(x)) UG,(11) （10分）
3．解：
（1）偏序关系R的哈斯图为 2 5 （2分） 1 3
4
（2）B的最大元：无；最小元：无；（4分）极大元：2,5；极小元：1,3；（6分）下界：4；最大下界：4；上界：无；最小上界：无。（8分）
4．证明：
1）??a,b??A?A，?a?b?b?a，???a,b?,?a,b???R，即R自反。（2分） 2）???a,b?,?c,d???R，则a?d?b?c，?d?a?c?b，即c?b?d?a，从而??c,d?,?a,b???R，即R对称。（4分） 3）???a,b?,?c,d???R，???c,d?,?e,f???R，则a?d?b?c，c?f?d?e，
?f?d?e?c，从而a?f?a?d?e?c?b?c?e?c?b?e， （6分） ???a,b?,?e,f???R，即R传递。综上得出，R是等价关系。 且[?2,5?]R?{?a,b?|?a,b??A?A,a?5?b?2} ={?a,b?|?a,b??A?A,a?b?3} ={?1,4?,?2,5?,?3,6?,?4,7?,?5,8?,?6,9?} （8分）
5．解（1）如下列出g?f的对应关系 x 0 1 2 3 4 5 6 7 8 … f(x) 1 2 3 4 5 6 7 8 9 … g(f(x)) 3 1 3 2 0 3 3 3 4 … 从而得到
g?f:N?N ?3?1??g?f(x)??2?x/2???0x?0,2或大于等于5的奇数x?1x?3x?6且x为偶数x?4（2分） （2）g?f是满射的，但不是单射的。 （4分） （3）g?f({0,1,2})?{1,3}。 （6分） （4）(g?f)({0,1,2})?{1,3,4}。 （8分）
?1
《离散数学》试卷 共5页第3页
2007-2008(1B)离散数学期末试卷及答案
