离散数学试卷（十一）
一、 填空 20% （每小题 2分）
1、 称为命题。 2、命题P→Q的真值为0，当且仅当 。 3、一个命题含有4个原子命题，则对其所有可能赋值有 种。 4、所有小项的析取式为 。 5、令P（x）：x是质数，E（x）：x是偶数，Q（x）：x是奇数，D（x，y）：x除尽y. 则
?x(E(x)??y(D(x,y)?E(y)))的汉语翻译为
。 6、设S={a，b, c} 则S6的集合表示为 。 7、P（P(?)）= 。 8、A?B= 。 9、设R为集合A上的关系，则t（R）= 。 10、若R 是集合A上的偏序关系，则R满足 。
二、 选择 20% （每小题 2分）
1、 下列命题正确的有（ ）。
A、 若g,f是满射，则g?f是满射； B、若g?f是满射，则g,f都是满射； C、若g?f是单射，则g,f都是单射；D、若g?f单射，则f是单射。 2、 设f，g是函数，当（ ）时，f=g 。
A、?x?domf 都有 f(x)?g(x)； B、domg?domf 且 f?g； C、f与g的表达式相同； D、domg?domf,rangef?rangef。
3、 下列关系，（ ）能构成函数。
A、f?{?x1,x2?|x1,x2?N且x1?x2?10}； B、f?{?x1,x2?|x1,x2?R,x1?x2}；
C、f?{?x1,x2?|x1,x2?N,x2为小于x1的素数的个数}；
2 68
离散数学试卷（十一）
D、f?{?x,x?|x?R}。
4、 下列函数（ ）满射；（ ）单射；（ ）双射（ ）；
一般函数（ ）。
A、f:N?N,f(x)?x2?2； B、f:N?N,f(x)?x(mod3)（x除以3的余数）；
C、f:N?{0,1},f(x)???1x?偶数集；D、f:R?R,f(x)?2x?5。
?0x?奇数集5、 集合A={1，2，3，4}上的偏序关系为，则它的Hass图为（
6、 设集合A={1，2，3，4，5}上偏序关系的Hass图为
则子集B={2，3，4}的最大元（ ）；最小元（ ）；极大元（ 极小元（ ）；上界（ ）；上确界（ ）；下界（ ）；下确界（ A、 无，4，2、3，4，1，1，4，4； B、无，4、5，2、3，4、5，1，1，4，4；C、无，4，2、3，4、5，1，1，4，4； D、无，4，2、3，4，1，1，4，无。 7、 设R，S是集合A上的关系，则下列（ ）断言是正确的。
A、 R,S自反的，则R?S是自反的；B、若R,S对称的，则R?S是对称的；
69
。
；。
） ） ） 离散数学试卷（十一）
C、若R,S传递的，则R?S是传递的；D、若R,S反对称的，则R?S是反对称的 8、 设X为集合，|X|=n，在X上有（ ）种不同的关系。 A、n2； B、2n； C、22； D、2n。 9、 下列推导错在（ ）。 ①?x?y(x?y) ②?y(z?y) ③(z?Cz) ④?x(x?x)
P US① ES② UG③
n2A、②； B、③； C、④； D、无。
10、“没有不犯错误的人”的逻辑符号化为（ ）。 设H（x）：x是人， P（x）：x犯错误。
A、?x(H(x)?P(x))； B、?(?x(H(x)??P(x)))； C、?(?x(H(x)??P(x)))； D、?x(H(x)?P(x))。
三、 命题演绎28%
1、（10分）用反证法证明(P?Q)?(P?R)?(Q?S)?S?R。 2、（8分）用CP规则证明P?(Q?R),R?(Q?S)?P?(Q?S)。
3、（10分）演绎推理：所有的有理数都是实数，所有的无理数也是实数，虚数不是实数。因此，
虚数既不是有理数，也不是无理数。
四、
将wff8%
?x(?(?yP(x,y))?(?zQ(z)?R(x)))化为与其等价的前束范式。
五、8%
A={a,b,c,d}，R={
70
离散数学试卷（十一）
六、证明16%
1、 （8分）设A={1，2，3，4}，在 P（A）上规定二元关系如下：
R?{?s,t?|s,t? P（A）?(|s|?|t|)}
证明R是P（A）上的等价关系并写出商集P（A）/R。 2、 （8分）设f是A到A的满射，且f?f?f，证明f=IA 。
71
离散数学试卷（十一）
一、 填空 20%（每小题2分）
1、 能够断真假的阵述句；2、P的真值为1，Q的真值为0；3、24=16；4、永真式； 5、任意两数x、y,如果x是偶数且能除尽y，则y一定是偶数；6、S110={a,b}；
?7、{?,{?},{{?}},{?,{?}}}；8、(A?~B)?(~A?B)；9、?Ri；
i?110、自反性、反对称性、传递性
二、选择 20%（每小题 2分）
题目 1 2 B 3 4 5 C 6 A 7 A 8 D 9 C 10 B、D 答案 A、D
三、命题演绎 28% 1、（10分）证明： ⑴?(S?R) ⑵?S??R ⑶P?Q ⑷?P?Q ⑸Q?S ⑹?P?S ⑺?S?P
C、D C、D；A、D；D；B P（附加前提） T⑴E P T⑶E P T⑷⑸E T⑹E T⑺I T⑵⑻I P T⑽E T⑾E T⑼⑿I
⑻(?S??R)?(P??R) ⑼P??R ⑽P?R ⑾?P?R ⑿?(P??R) ⒀F 2、（8分）
72
离散数学试卷（十一）
①P
②P?(Q?R) ③Q?R ④R?(Q?S) ⑤Q?(Q?S) ⑥Q?S ⑦P?(Q?S)
P（附加前提） P T①②I P T③④I T⑤E CP
3、证明：设Q（x）：x是有理数，R(x)：x是实数，N(x)：x是无理数， C(x)：x是虚数。 前提：?x(Q(x)?R(x)) ?x(N(x)?R(x)) ?x(C(x)??R(x)) 结论：?x(C(x)??Q(x)??N(x)) ⑴?x(Q(x)?R(x)) ⑵Q(c)?R(c) ⑶?x(N(x)?R(x)) ⑷N(c)?R(c) ⑸?x(C(x)??R(x)) ⑹C(c)??R(c) ⑺R(c)??C(c) ⑻Q(c)??C(c) ⑼N(c)??C(c)
⑽(Q(c)??C(c))?(N(c)??C(c)) ⑾C(c)??Q(c)??N(c) ⑿?x(C(x)??Q(x)??N(x))
73
P US⑴ P US⑶ P US⑸ T⑹E T⑵⑺I T⑷⑺I T⑻⑼I T⑽E UG⑾
离散数学试卷（十一）
四、 8% 解：
?x(?y(?P(x,y))?(?(?zQ(z))?R(x)))??x(?(?y(?P(x,y)?(?(?zQ(z))?R(x)))??x(?y(P(x,y)??z(?Q(z))?R(x)))??x?y?z(P(x,y)??Q(z)?R(x))
五、8%
解：
?0??0??0??0?101001000??1?0??0???0??0??0??0??0??0??0??0?1010MR10100100010001001010MR2?MR?MR0??0??1??0???00???0???01??0??0??0?1??0???0???00??0??1??0?0??0???0???01010101010100100010001000??0??1??0???00???0???00??0??1??0?0??0???0???00??0??1??0?0??0???0???00100010010101010101001001??0?1??0??
MR3?MR2?MR0??1??M0??0??1??0??M1??0??R
MR4?MR3?MR?0??0??0??0?R2
?Mt(R)?MR?MR2?0??0?MR3?MR4??0??0?111011101??1? 1??0??所以t（R）={
关系图为
74
离散数学试卷（十一）
六、证明16% 1、（8分）
证明：⑴?s? P（A），由于|s|?|s|，所以?s,s??R，即R自反的。
⑵?s,t? P（A），若?s,t??R，则|s|?|t|?|t|?|s|，??t,s??R，R是对称的。 ⑶?s,t,u? P（A），若：?s,t??R且?t,u??R，即：|s|?|t|?|u|
?|s|?|u|,?s,u??R 所以R是传递的。
由⑴⑵⑶知，R是等价关系。
P（A）/R = {[?]R，[{1}]R，[{1，2}]R，[{1，2，3}]R，[{1，2，3，4}]R}
2、（8分）
证明：因为f是满射，所以?a?A，存在a1?A使得f(a1)?a，又因为f是函数，所以
f(f(a1))?f(a) 即f?f(a1)?f(a) 由 f?f?f
所以f(a1)?f(a)，又f(a1)?a，所以f(a)?a 由a的任意性知：f=IA 。
75