一、判断题（正确√，错误×）
1-5 题： × × × × √ 6-10 题：× × √ √ √ 11-15题：× × √ × √ 16-17题：√ ×
二、单项选择题
1 A C 2 C 3 C 4. B 5 A 6 B 7 B 8 C 9 B 10 B 11 D 12 A 13 C 14 C 三、填空题
1 ┐Q→P 或┐P→Q， Q→P
2 AB?｛{a,b}, {a},{b},{c}｝，AB?｛｛c｝｝，
A?B?｛{a,b}｝， A?B?｛{a,b},{a},{b}｝。
3． ?{?}?Φ，{?,{?}}???{Φ,{ Φ}}，
{?,{?}}?{?}?{{Φ}}，?{?}?{Φ}。
4．A={1,2,3,……,12}，R是A上的整除关系，子集B={2,4,6}。 则B的最大元是：无，最小元是：2，
极大元是：4，6，极小元是：2， 上界是：12，下界是：2， 上确界是：12，下确界是：2。
5. g g g 6 R, T 7. 略
8．极大元：{a,b}, {b,c}，最大元：无，上界：{a,b,c}，下确界：Φ。
1
一、判断题（正确√，错误×）
( )1．设A，B，C为任意的命题公式，若A?C?B?C,则A?B。 ( )2．公式P?Q是合取范式，不是析取范式。 ( )3．公式(?P?Q)?(P?Q)与公式P?(Q?R)等价。 ( )4．(?x)(A(x)?B(x))?(?x)A(x)?(?x)B(x)。
( )5．谓词公式(?x)(?y)(P(x,y)?Q(y,z))中，x,y是约束变元，z是自由变元。 ( )6．对谓词公式(?x)(P(y)?Q(x,y))?R(x,y)中的自由变元进行代入后得到
公式(?x)(P(z)?Q(x,z))?R(x,y)。
( )7．对谓词公式(?x)(P(x)?Q(x,y))?R(x,y)中的约束变元进行换名后得到公
式(?y)(P(y)?Q(y,y))?R(x,y)。
( )8．{?}?{?,{?}}，且{?}?{?,{?}}。
( )9．对任意的集合A,B,C,D.若A?C,B?D，则A?B?C?D。 ( )10．设A,B,C是任意的集合，则A(B?C)?(AB)?(AC)。
( )11．集合A={a,b,c}上的任何二元关系R都不可能既是对称的，又是反对称
的。
( )12．若R和S是集合A上的任意的两个反自发的关系，则R○S也是反自反
的。
( )13．设
成员。
( )14．R是等价关系一定是相容关系，反之亦然。
( )15．当X和Y都是有限集合时，若f:X→Y是单射函数，则|X|≤|Y|。 ( )16．设N是自然数集合，f : N→N,且f(j)=j2+2,则f是单射函数。 ( )17．设X={1,2,3,4}, f是X上的关系且f={<1,4>,<2,1>,<2,3>,<3,2>,
<4,4>}，则f是函数。
二、单项选择题
1．给定命题公式P?(Q?R)，则它的成真指派为( )， 成假指派为( )。
A．111, 011, 100, 101,110
B. 111, 011
C. 000, 010, 001 D. 000
2．给定命题公式：(?P?Q)?(P?R)与之等价的是( )。
A．P?(?Q?R) B. P?(Q?R)
2
C. P?(Q?R) D. ?P?(Q?R)
3．命题：“所有马都比某些牛跑得快” 的符号化公式为( )。 假设：H(x)：x是马；C(x)：x是牛；F(x,y)：x跑得比y快。
A. (?x)(H(x)?(?y)(C(y)?F(x,y))) B. (?x)(H(x)?(?y)(C(y)?F(x,y))) C. (?x)(H(x)?(?y)(C(y)?F(x,y))) D. (?y)(?x)(H(x)?(C(y)?F(x,y)))
4．给定命题公式：(?x)(A(x)?B)与之等价的公式是( )。
A．(?x)A(x)?B B. (?x)A(x)?B
C. ?B?(?x)A(x)
D. ?B?(?x)?A(x)
5．对任意的集合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. 6．下列选项错误的是（ ）。
A. ??? B. ??? C. ??{?} D. ??{?} 7．设A={1,{1}}, P(A)为A的幂集，下列选项错误的是（ ）。 A．{1}?P(A) B. {1}?P(A) C. {{1}}?P(A) D.{{1}}?P(A)8．集合A={1,2,3,6}, A上的整除关系具有的性质是（ ） A．自反的，对称的，可传递的
B. 反自反的，对称的，可传递的 C. 自反的，反对称的，可传递的 D. 反自反的，反对称的，可传递的
??1010?9．关系R的关系矩阵M0101?R????0010??, 则关系R具有的性质是 ( ?0001?? A．自反的，对称的，可传递的
B．自反的，反对称的，可传递的
C．自反的，对称的
3
)。 D．都不是
10．函数的复合运算满足（ ）。
A．交换律 B.结合律 C.等幂律 D.分配律 11．若g○f是双射函数，则（ ）。
A．f，g必是满射 B.f，g必是单射 C．f必是满射, g必是单射 D. f必是单射, g必是满射
12．设N是自然数集合，R是实数集合，f : N→R，且给定f(j)?log10j，
则（ ）。
A．f是单射 B.f是满射 C．f是双射 D.都不是 13．设A?B??，则有（ ）。
A．B?? B. B?? C．A?B D. B?A 14．给定公式(?x)F(y,x)?(?y)G(y)，它的前束范式是（ ）。
A．(?x)(?y)(F(y,x)?G(y)) B. (?x)(?y)(F(z,x)?G(y)) C．(?x)(?y)(?F(z,x)?G(y)) D. (?x)(?y)(?F(z,x)?G(y)) 三、填空题
1．给定命题1：“除非你努力，否则你将失败”（假设Q：你努力，P：你将失败）；命题2：“只有睡觉才能恢复疲劳”（假设P：睡觉，Q：恢复疲劳）。则命题1符号化为_________________， 命题2符号化为___________________。 2．集合A={{a,b},{c}}，B={{a},{b},{c}}, 试写出：
AB?___________________，AB?___________________，
A?B?___________________，A?B?___________________。
3．确定以下各式：?{?}?____________，{?,{?}}???____________，
{?,{?}}?{?}?________________，?{?}?________________。
4．A={1,2,3,……,12}，R是A上的整除关系，子集B={2,4,6}。 则B的最大元是____________，最小元是____________，
极大元是____________，极小元是____________， 上界是______________，下界是______________， 上确界是____________，下确界是____________。
5．设A={1,2,3}，f, g, h均为A到A的函数，即f, g, h：A→A，其中
4
f={<1,1>,<2,1>,<3,1>}, g={<1,1>,<2,3>,<3,2>}, h={<1,3>,<2,1>,<3,1>}，则__________是单射，__________是满射，__________是双射。
6．设A={a,b,c}, B={x,y,z}，R，S，T：A→B的关系，且R={,
7． 关系R是自反的，当且仅当在关系矩阵中___________________________， 在关系图中____________________________________________________； 关系R是反自反的，当且仅当在关系矩阵中_________________________，在关系图中___________________________________________________； 关系R是对称的，当且仅当在关系矩阵中__________________________， 在关系图中__________________________________________________。 8．设A={a,b,c}上偏序集?P(A),??，其中P(A)是A的幂集，则幂集P(A)的 子集B?{?,{的极大元是______________，最大元是a},b{}a,{b,b},c{_______________，上界是______________，下确界是______________。 四、简答题
1. 将下列命题符号化
(1) 不存在两片完全相同的叶子。 (2) 发光的不都是金子。
(3)尽管有人聪明，但未必一切人都聪明。 2. 利用两种方法证明下列蕴涵式：
?Q?(P?Q)??P.
3.利用求主合取范式证明下列公式等价性：
(P?Q)?(P?R)?P?(Q?R)
4．设A,B和C是集合，则回答下列问题： 若A?B?A?C, 是否必须B=C? 五、综合题
1 应用CP规则证明：R→S可以从前提P→(Q→S),┐R∨P和Q推出。 2.符号化下列命题，并给出构造推理证明
每位资深名士或是中科院院士或是国务院参事。所有的资深名士是政协委员。张大为是资深名士，但他不是中科院院士，因此有的政协委员是国务院参事。
5