一、填空 20% （每小题2分）
1．设 }7|{)},5()(|{<∈=<∈=+
x E x x B x N x x A 且且（N ：自然数集，E + 正偶数）
则 =?B A 。
2．A ，B ，C 表示三个集合，文图中阴影部分的集合表达式为 。
3．设P ，Q 的真值为0，R ，S 的真值为1，则
)()))(((S R P R Q P ?∨→?∧→∨?的真值
=
4．公式P R S R P ?∨∧∨∧)()(的主合取范式为
。
5．若解释I 的论域D 仅包含一个元素，则 )()(x xP x xP ?→? 在I 下真值为
。
6．设A={1，2，3，4}，A 上关系图为
则 R 2 = 。
7．设A={a ，b ，c ，d}，其上偏序关系R 的哈斯图为则 R=
8题
8．图的补图为 。 9．设A={a ，b ，c ，d} ，A 上二元运算如下：
那么代数系统的幺元是 ，有逆元的元素为 ，它们的逆元分别
为 。 二、选择 20% （每小题 2分）
1、下列是真命题的有（ ） A ． }}{{}{a a ?；
B ．}}{,{}}{{ΦΦ∈Φ；
C ． }},{{ΦΦ∈Φ；
D ． }}{{}{Φ∈Φ。 2、下列集合中相等的有（ ）
A ．{4，3}Φ?；
B ．{Φ，3，4}；
C ．{4，Φ，3，3}；
D ． {3，4}。
3、设A={1，2，3}，则A 上的二元关系有（ ）个。
A． 23 ；B． 32 ；C．332?； D．223?。
4、设R，S是集合A上的关系，则下列说法正确的是（）
A．若R，S 是自反的，则
S
R 是自反的；
B．若R，S 是反自反的，则
S
R 是反自反的；
C．若R，S 是对称的，则
S
R 是对称的；
D．若R，S 是传递的，则
S
R 是传递的。
5、设A={1，2，3，4}，P（A）（A的幂集）上规定二元系如下
|}
||
(|
)
(
,
|
,
{t
s
A
p
t s
t s
R=
∧
∈
>
<
=
则P（A）/ R=（）
A．A ；B．P(A) ；C．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}；
D．{{Φ}，{2}，{2，3}，{{2，3，4}}，{A}}
6、设A={Φ，{1}，{1，3}，{1，2，3}}则A上包含关系“?”的哈斯图为（）
7、下列函数是双射的为（）
A．f : I→E , f (x) = 2x ； B．f : N→N?N, f (n) =
C．f : R→I , f (x) = [x] ； D．f :I→N, f (x) = | x | 。
（注：I—整数集，E—偶数集， N—自然数集，R—实数集）
8、图中从v1到v3长度为3 的通路有（）条。
A． 0；B． 1；C． 2；D． 3。
9、下图中既不是Eular图，也不是Hamilton图的图是（）
10、在一棵树中有7片树叶，3个3度结点，其余都是4度结点则该树有（）个4度结点。
A．1；B．2；C．3；D．4 。
三、证明 26%
１、R是集合X上的一个自反关系，求证：R是对称和传递的，当且仅当< a, b> 和在R 中有<.b , c>在R中。（8分）
四、逻辑推演 16%
用CP规则证明下题（每小题 8分）
1、
F A F E D D C B A →?→∨∧→∨,
2、)()())()((x xQ x xP x Q x P x ?→??→?
五、计算 18%
1、设集合A={a ，b ，c ，d}上的关系R={ ,< b , a > ,< b, c > , < c , d >}用矩阵运算求出R 的传递闭包t (R)。 （9分）
2、如下图所示的赋权图表示某七个城市721,,,v v v 及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。 （９分）
试卷一答案：
一、填空 20% （每小题2分）
1、{0，1，2，3，4，6}；
2、A C B -
⊕)(；3、1； 4、)()(R S P R S P ∨?∨?∧∨∨?； 5、
1；6、{<1,1>, <1,3>, <2,2>, <2,4> }；7、{
9、a ；a , b , c ,d ；a , d , c , d ；10、c;
1、 证：“?” X c b a ∈?,, 若R >c ,a <,>b ,a <
∈由R 对称性知R a ,c <,>a ,b <∈>，
由R 传递性得 R >c ,b <∈
“?” 若R >b ,a <∈，R >c ,a <∈有 R >c ,b <∈ 任意 X
b a ∈,，因R
>a ,a <
∈若R >b ,a <
∈R >a ,b < ∈∴ 所以R 是对称的。
若R >b ,a <∈
，R >c b,<∈ 则 R c b, R >a b,<>∈<∧∈ R >c ,a < ∈∴ 即
R 是传递的。
二、 逻辑推演 16%
1、 证明：
①
A
P （附加前提） ②B A ∨
T ①I ③D C B A ∧→∨ P ④D C ∧ T ②③I ⑤D
T ④I ⑥E D ∨
T ⑤I ⑦F E D →∨ P ⑧F
T ⑥⑦I
⑨F A →
CP
2、证明
①)(x xP ? P （附加前提） ②)(c P US ①
③))()((x Q x P x →?
P ④)()(c Q c P →
US ③ ⑤)(c Q T ②④I ⑥)(x xQ ?
UG ⑤ ⑦)()(x xQ x xP ?→? CP
三、 计算 18%
1、 解：
???????
?
?=0000100001010010R M ， ???
????
??==00000000101
0010
12R R R M M M
??
?
??
??
??==000000000101
10102
3R R R M M M ，
??
?
??
?
?
?
?==000000001010
01013
4R R R M M M ??
?
??
??
?
?=+++=0000100011111111
4
32)(R R R R R t M M M M M
∴t (R)={ , , < a , c> , , , < b ,b > , < b , c . > ,
< b , d > , < c , d > }
2、 解： 用库斯克（Kruskal ）算法求产生的最优树。算法略。结果如图：
树权C(T)=23+1+4+9+3+17=57即为总造价。 试卷二试题与答案
一、填空 20% （每小题2分）
1、 P ：你努力，Q ：你失败。“除非你努力，否则你将失败”的翻译为
；“虽然你努力了，但还是失败了”的翻译为 。 2、论域D={1，2}，指定谓词P
P (1,1) P (1,2) P (2,1)
P (2,2) T
T
F
F
则公式x ??真值为 。
2、 设S={a 1 ，a 2 ，…，a 8}，B i 是S 的子集，则由B 31所表达的子集是 。
3、 设A={2，3，4，5，6}上的二元关系}
|,{是质数x y x y x R ∨<><=，则R=
（列举法）。R 的关系矩阵M R = 。 5、设A={1，2，3}，则A 上既不是对称的又不是反对称的关系R= ；A 上既是
对称的又是反对称的关系R= 。 6、设代数系统，其中A={a ，b ，c},
则幺元是 ；是否有幂等 性 ；是否有对称性 。
9、n 个结点的无向完全图K n 的边数为 ，欧拉图
的充要条件是 。
10、公式R Q P Q P P ?∧∨?∧∧?∨)(())((的根树表示为 。 二、选择 20% （每小题2分）
1、在下述公式中是重言式为（ ）
A ．)()(Q P Q P ∨→∧；
B ．))()(()(P Q Q P Q P →∧→??；
C ．Q Q P
∧→?)(； D ．)(Q P P ∨→。
2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为（ ），成真赋值的个数为（ ）。
A ．0；
B ．1；
C ．2；
D ．3 。
3、设}}2,1{},1{
,{Φ=S ，则 S
2 有（ ）个元素。 A ．3； B ．6； C ．7； D ．8 。
4、 设} 3 ,2 ,1 {=S ，定义S S ?上的等价关系
},,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R
产 生的
S S ?上一个划分共有（ ）个分块。
A ．4；
B ．5；
C ．6；
D ．9 。 5、设} 3 ,2 ,1 {=S
，S 上关系R 的关系图为
则R 具有（ ）性质。
A ．自反性、对称性、传递性；
B ．反自反性、反对称性；
C ．反自反性、反对称性、传递性；
D ．自反性 。 6、设 ,+ 为普通加法和乘法，则（ ）>+< ,,S 是域。
A ．
},,3|{Q b a b a x x S ∈+== B ．},,2|{Z b a n x x S ∈==
C ．},12|{Z n n x x S ∈+==
D ．}0|{≥∧∈=x Z x x S = N 。
8、在如下的有向图中，从V 1到V 4长度为3 的道路有（ ）条。
* a b c a b c
a b c b b c c c b
A ．1；
B ．2；
C ．3；
D ．4 。 9、在如下各图中（ ）欧拉图。
10
三、证明 46%
1、 设R 是A 上一个二元关系，
)},,,(),(|,{R b c R c a A c A b a b a S >∈<>∈<∈∧∈><=且有对于某一个试证明
若R 是A 上一个等价关系，则S 也是A 上的一个等价关系。（9分） 2、 用逻辑推理证明：
所有的舞蹈者都很有风度，王华是个学生且是个舞蹈者。因此有些学生很有风度。（11分） 3、 若
B
A f →:是从A 到
B 的函数，定义一个函数
A
B g 2:→对任意
B
b ∈有
)})(()(|{)(b x f A x x b g =∧∈=，证明：若f 是A 到B 的满射，则g 是从B 到 A 2 的单
射。（10分
4、 若无向图G 中只有两个奇数度结点，则这两个结点一定连通。（8分）
5、 设G 是具有n 个结点的无向简单图其边数2)2)(1(21
+--=
n n m ，G 是Hamilton 图（8分）
四、计算 14%
1、 权数1，4，9，16，25，36，49，64，81，100构造一棵最优二叉树。（7分）
试卷二答案：
一、 填空 20%（每小题2分）
1、Q P →?；Q P ∧
2、T
3、},,,,{876540001111131a a a a a B B ==
4、
R={<2,2>,<2,3>,<2,4>,<2,5>,<2,6>,<3,2>,<3,3>,<3,4>,<3,5>,<3,6>,<4,5>,<4,6>,<5,2>,<5,
3>,<5,4>,<5,5>,<5,6>}；???
?
??
??
??00000
11111110001111111111 5、R={<1,2>,<1,3>,<2,1>}；
R={<1,1>,<2,2>,<3,3>} 6、a ；否；有 7、Klein 四元群；循环群 8、 B 9、
)1(21
-n n ；图中无奇度结点且连通 10 、
二、 题目 1 2 3 4 5 6 7 8 9 10 答案
B 、D
D ；D
D
B
D
A
B
B
B
B 、C
三、 1、（9分）
（1） S 自反的
A a ∈?，由R 自反，),(),(R a a R a a >∈<∧>∈<∴，S a a >∈∴<,
（2） S 对称的
传递
对称定义R S
a b R R b c R c a S R b c R c a S b a A
b a >∈?<>∈<∧>∈∈<∧>∈∈<∈?,),(),()
,(),(,,
（3） S 传递的
定义
传递S S
c a R R c b R b a R c e R e b R b
d R d a S
c b S b a A
c b a >∈?<>∈<∧>∈∈<∧>∈<∧>∈<∧>∈∈<∧>∈<∈?,),(),(),(),(),(),(,,,,
由（1）、（2）、（3）得；S 是等价关系。 2、11分
证明：设P(x)：x 是个舞蹈者； Q(x) ：x 很有风度； S(x)：x 是个学生； a ：王华 上述句子符号化为：
前提：))()
((x Q x P x →?、)()(a P a S ∧ 结论：))()((x Q x S x ∧? ……3分
①)()(a P a S ∧ P ②))()((x Q x P x →?
P ③)()(a Q a P →
US ② ④)(a P T ①I ⑤).(a Q T ③④I ⑥)(a S T ①I ⑦)()(a Q a S ∧ T ⑤⑥I ⑧)()((x Q x S x ∧? EG ⑦
……11分
３、１0分 证明 ：)(,,212
1b b B b b ≠∈?A a a f ∈?∴21,满射
21212211,),()(,)(,)(a a f a f a f b a f b a f ≠∴≠==是函数由于且使 )
()()(),()(),()}
)(()(|{)()},)(()(|{)(21122122112211b g b g b g a b g a b g a b g a b x f A x x b g b x f A x x b g ≠∴??∈∈∴=∧∈==∧∈=但又
为单射任意性知由g b b ,,21。
4、8分
证明：设G 中两奇数度结点分别为u 和v ，若 u ，v 不连通，则G 至少有两个连通分支G 1、G 2 ，使得u 和v 分别属于G 1和G 2，于是G 1和G 2中各含有1个奇数度结点，这与图论基本定理矛盾，因而u ，v 一定连通。
5、8分
证明： 证G 中任何两结点之和不小于n 。
反证法：若存在两结点u ，v 不相邻且1)
()(-≤+n v d u d ,令},{1v u V =，则G-V 1是具有
n-2个结点的简单图，它的边数
)1(2)2)(1(2
1
'--+--≥
n n n m ,可得
1)3)(2(21
'+--≥
n n m ，这与G 1=G-V 1为n-2个结点为简单图的题设矛盾，因而G 中任何两个
相邻的结点度数和不少于n 。 所以G 为Hamilton 图. 四、
计算 14%
7分
试卷三试题与答案
一、 填空 20% （每空 2分）
1、 设 f ，g 是自然数集N 上的函数x x g x x f N x 2)(,1)(,
=+=∈?，
则=)(x g f 。
2、 设A={a ，b ，c}，A 上二元关系R={< a, a > , < a, b >,< a, c >, < c, c>} ,
则s （R ）= 。
3、 A={1，2，3，4，5，6}，A 上二元关系}
|,{是素数y x y x T ÷><=，则用列举法
T= ；T 的关系图为 ；T 具有 性质。 4、 集合
}}2{},2,{{Φ=A 的幂集A 2= 。
5、 P ，Q 真值为0 ；R ，S 真值为1。则))()(())
((S R Q P S R P wff ∧∧∨→∨∧的真值
为 。
6、 R R Q P wff →∨∧?))((的主合取范式为 。
7、 设 P （x ）：x 是素数， E(x)：x 是偶数，O(x)：x 是奇数 N (x,y)：x 可以整数y 。则谓词
))),()(()((x y N y O y x P x wff
∧?→?的自然语言是
。 8、 谓词)),,()),(),(((u y x uQ z y P z x P z y x wff ?→∧???的前束范式为 。 二、 选择 20% （每小题 2分）
1、 下述命题公式中，是重言式的为（ ）。 A 、)()(q p q p ∨→∧； B 、))())(()(p q q p q p →∧→??；
C 、q q p ∧→?)(；
D 、q p p ??∧)(。
2、
r q p wff
→∧?)(的主析取范式中含极小项的个数为（ ）。
A 、2；
B 、 3；
C 、5；
D 、0；
E 、 8 。 3、 给定推理
①))()((x G x F x →?
P ②)()(y G y F →
US ① ③)(x xF ? P ④)(y F ES ③ ⑤)(y G T ②④I ⑥)(x xG ?
UG ⑤
)())()((x xG x G x F x ??→?∴
推理过程中错在（ ）。
A 、①->②;
B 、②->③;
C 、③->④;
D 、④->⑤;
E 、⑤->⑥
4、 设S 1={1，2，…，8，9}，S 2={2，4，6，8}，S 3={1，3，5，7，9}，S 4={3，4，5}，
S 5={3，5}，在条件
31S
X S X ??且下X 与（ ）集合相等。 A 、 X=S 2或S 5 ； B 、X=S 4或S 5；
C 、X=S 1，S 2或S 4；
D 、X 与S 1，…，S 5中任何集合都不等。
5、 设R 和S 是P 上的关系，P 是所有人的集合，
},|,{的父亲是y x P y x y x R ∧∈><=，
},|,{的母亲是y x P y x y x S ∧∈><=则R S 1-表示关系 （ ）
。
A 、},|,{的丈夫是y x P y x y x ∧∈><；
B 、
},|,{的孙子或孙女是y x P y x y x ∧∈><；
C 、 Φ；
D 、
},|,{的祖父或祖母是y x P y x y x ∧∈><。
6、 下面函数（ ）是单射而非满射。
A 、12)(,
:2-+-=→x x x f R R f ； B 、x x f R Z f ln )(,
:=→+；
C 、
的最大整数表示不大于x x x x f Z R f ][],[)(,
:=→；
D 、12)(,:+=→x x f R R f 。
其中R 为实数集，Z 为整数集，R +，Z +
分别表示正实数与正整数集。 7、 设S={1，2，3}，R 为S 上的关系，其关系图为
则R 具有（ ）的性质。
A 、 自反、对称、传递；
B 、什么性质也没有；
C 、反自反、反对称、传递；
D 、自反、对称、反对称、传递。
8、 设}}2,1{},1{
,{Φ=S ，则有（ ）S ?。 A 、{{1,2}} ；B 、{1,2 } ； C 、{1} ； D 、{2} 。 9、 设A={1 ,2 ,3 }，则A 上有（ ）个二元关系。
A 、23
； B 、32
； C 、322； D 、2
32。 10、全体小项合取式为（ ）。
A 、可满足式；
B 、矛盾式；
C 、永真式；
D 、A ，B ，C 都有可能。
三、 用CP 规则证明 16% （每小题 8分） 1、
F A F
E D D C B A →?→∨∧→∨,
2、)()())()((x xQ x xP x Q x P x ?∨??∨?
四、（14%）
集合X={<1,2>, <3,4>, <5,6>,… }，R={<
设集合A={ a ,b , c , d }上关系R={< a, b > , < b , a > , < b , c > , < c , d >} 要求 1、写出R 的关系矩阵和关系图。（4分） 2、用矩阵运算求出R 的传递闭包。（6分） 六、（20%）
1、（10分）设f 和g 是函数，证明g f ?也是函数。
2、（10分）设函数S T f T
S
g →→::，证明 S T f →:有一左逆函数当且仅当f 是入射函数。
答案：
五、 填空 20%（每空2分） 1、2(x+1)；2、}
a , c ,a ,
b ,
c , c ,c , a ,b , a ,a , a {><><><><><><；3、
>}<><><><><><3,6,2,6,2,4,5,1,3,1,2,1{；
4、
反对称性、反自反性；4、}}}2{},2,{{}},2{{}},2,{{,{ΦΦΦ；5、1； 6、)()()(R Q P R Q P R Q P ∨∨∧∨∨?∧∨
?∨；7、任意x ，如果x 是素数则存在一
个y ，y 是奇数且y 整除x ；8、)),,(),(),((u y x Q z y P z x P u z y x ∨?∨?????。
七、 证明 16%(每小题8分) 1、
①
A
P （附加前提） ②B A ∨
T ①I ③D C B A ∧→∨ P ④D C ∧ T ②③I ⑤D
T ④I ⑥E D ∨
T ⑤I
⑦F E D →∨
P ⑧F T ⑥⑦I ⑨F A →
CP
2、
)()(())()(()()()()()(x xQ x xP x Q x P x x xQ x P x x xQ x xP ?→???∨??→????∨?本题可证 ① ))((x xP ?? P （附加前提）
②))((x P x ?? T ①E ③)(a P ?
ES ② ④))()((x Q x P x ∨? P ⑤)()(a Q a P ∨ US ④ ⑥)(a Q T ③⑤I ⑦)(x xQ ? EG ⑥
⑧)()((x xQ x xP ?→??
CP
八、 14% （1） 证明：
1、
自反性：y x y x X y x +=+>∈
自反R R y x y x >>∈<><<∴,,,
2、 对称性：X
y x X y x >∈∈
时当R y x y x >>∈<><<2211,,, 21121221y x y x y x y x +=++=+也即即 有对称性故R R y x y x >>∈<><<1122,,,
3、 传递性：
X y x X y x X y x >∈∈∈
时且当R y x y x R y x y x >>∈<><<>>∈<><<33222211,,,,,,
??
?+=++=+)2()1(23321221y x y x y x y x 即 23123221)2()1(y x y x y x y x +++=++++
即1
331
y x y x +=+
有传递性故R R y x y x >>∈<><<3311,,,
由（1）（2）（3）知：R 是X 上的先等价关系。 2、X/R=}]2,1{[R ><
九、 10%
1、??
?
??
??
??=0000100001010010R M ； 关系图
2、
??
?
??
??
?
?==000000001010
01012
R R R M M M
??
?
??
??
??==000000000101
10102
3R R R M M M 23
4000000001010
0101R R R R M M M M =??
??
?
??
?
?==
,,4635R R R R M M M M ==
???
????
?
?=+++=00001000111
11111432
)(R R R R R t M M M M M
∴t (R)={ , , < a , c> , , , < b ,b > , < b , c . > , < b , d > , < c , d > }
六、 20%
1、（1）
)}
()(|,{)}
()(|,{x g x f y domg domf x y x x g y x f y domg x domf x y x g f ==∧?∈><==∧=∧∈∧∈><=?
)}()(,|{x g x f domg domf x x domh g domf g
f h =?∈==?∴?=令
（2）)}()()(|,{x g x f x h y domg domf x y x h ===∧?∈><=
使得若有对21,y y domh x ∈
)()()(,)()()(21x g x f x h y x g x f x h y ======
21,)(y y g f =有是函数或由于)(x h y y domh x =∈?使得有唯一即 也是函数g f ?∴。
2、证明：
t t f g T t g f =∈??)(,"" 则对有一左逆若 是入射所以是入射故f f g , 。 的左逆元是故则且若或只有一个值则对令若此时令使入射由定义如下是入射f g t s g t f g s t f c t s g S s T c s g T f s t s g s t f T t f T f s S T f f ,)()()()(,)()(,)()(,|,),(:
:,
""===∈?∈=?==∈?∈?→? 左逆函数为使必能构造函数入射即若f g g f ,,。
试卷四试题与答案
一、 填空 10% （每小题 2分）
1、 若P ，Q ，为二命题，Q P
→真值为0 当且仅当 。
2、 命题“对于任意给定的正实数，都存在比它大的实数”令F(x)：x 为实数，y x y x L >:
),(则
命题的逻辑谓词公式为 。
3、 谓词合式公式)()(x xQ x xP ?→?的前束范式为 。
4、 将量词辖域中出现的 和指导变元交换为另一变元符号，公式其余的部分不变，
这种方法称为换名规则。
5、 设x 是谓词合式公式A 的一个客体变元，A 的论域为D ，A(x)关于y 是自由的，则
被称为存在量词消去规则，记为ES 。
二、 选择 25% （每小题 2.5分）
1、 下列语句是命题的有（ ）。
A 、 明年中秋节的晚上是晴天；
B 、0>+
y x ；
C 、0>xy 当且仅当x 和y 都大于0；
D 、我正在说谎。 2、 下列各命题中真值为真的命题有（ ）。
A 、 2+2=4当且仅当3是奇数；
B 、2+2=4当且仅当3不是奇数；
C 、2+2≠4当且仅当3是奇数；
D 、2+2≠4当且仅当3不是奇数；
3、 下列符号串是合式公式的有（ ）
A 、Q P ?；
B 、Q P P ∨?；
C 、)()(Q P Q P ?∨∧∨?；
D 、)(Q P ??。
4、 下列等价式成立的有（ ）。
A 、P Q Q P
?→??→；B 、R R P P ?∧∨)(；
C 、 Q Q P P ?→∧)(；
D 、R Q P R Q P →∧?→→)()(。
5、 若
n A A A 21,和B 为wff ，且B A A A n ?∧∧∧ 21则（ ）
。
A 、称
n A A A ∧∧∧ 21为B 的前件； B 、称B 为n A A A 21,的有效结论
C 、当且仅当
F B A A A n ?∧∧∧∧ 21；D 、当且仅当F B A A A n ??∧∧∧∧ 21。
6、 A ，B 为二合式公式，且
B A ?，则（ ）。
A 、
B A →为重言式； B 、*
*B A ?；
C 、B A ?；
D 、*
*B A ?； E 、B A ?为重言式。
7、 “人总是要死的”谓词公式表示为（ ）。
（论域为全总个体域）M(x)：x 是人；Mortal(x)：x 是要死的。 A 、)()(x Mortal x M →； B 、)()(x Mortal x M ∧ C 、))()
((x Mortal x M x →?；D 、))()((x Mortal x M x ∧?
8、 公式))()((x Q x P x A →?=的解释I 为：个体域D={2}，P(x)：x>3, Q(x)：x=4则A 的真值
为（ ）。
A 、1；
B 、0；
C 、可满足式；
D 、无法判定。 9、 下列等价关系正确的是（ ）。 A 、)()())()((x xQ x xP x Q x P x ?∨??∨?； B 、)()())()((x xQ x xP x Q x P x ?∨??∨?；
C 、Q x xP Q x P x →??→?)())
((；
D 、Q x xP Q x P x →??→?)())((。 10、下列推理步骤错在（ ）。 ①))()((x G x F x →?
P ②)()(y G y F →
US ① ③)(x xF ? P ④)(y F ES ③ ⑤)(y G
T ②④I ⑥)(x xG ?
EG ⑤
A 、②；
B 、④；
C 、⑤；
D 、⑥ 三、 逻辑判断30%
1、 用等值演算法和真值表法判断公式
)())()((Q P P Q Q P A ??→∧→=的类型。（10
分）
2、 下列问题，若成立请证明，若不成立请举出反例：（10分）
（1） 已知
C B C A ∨?∨，问B A ?成立吗？
（2）
已知B A ???，问B A ?成立吗？
3、 如果厂方拒绝增加工资，那么罢工就不会停止，除非罢工超过一年并且工厂撤换了厂长。问：若
厂方拒绝增加工资，面罢工刚开始，罢工是否能够停止。（10分） 四、计算10%
1、 设命题A 1，A 2的真值为1，A 3，A 4真值为0，求命题
)()))(((421321A A A A A A ?∨??∧→∨的真值。
（5分）
2、 利用主析取范式，求公式R Q Q P ∧∧→?)(的类型。（5分）
五、谓词逻辑推理 15%
符号化语句：“有些人喜欢所有的花，但是人们不喜欢杂草，那么花不是杂草”。推证其结论 六、证明：（10%）
设论域D={a , b , c}，求证：))()(()()(x B x A x x xB x xA ∨???∨?。 答案：
十、 填空 10%（每小题2分） 1、P 真值为1，Q 的真值为0；2、
))
,()(()0,()((x y L y F y x L x F x ∧?→∧?；3、
))()((x Q x P x ∨??；4、约束变元；5、)()(y A x xA ??，y 为D 的某些元素。
十二、 逻辑判断 30%
1、（1）等值演算法 T Q P Q P Q P P Q Q P A ???????→∧→=)()()())()((
（2）
所以A 2、（1）不成立。
若取
T C B C A T T B T
T A T C ?∨?∨?∨?∨=有则
但A 与B 不一定等价，可为任意不等价的公式。 （2）成立。 证明：
T B A B A ???????充要条件
即：
B A A B B A B A A B A B B A A B B A T ??→∧→?∨?∧∨???∨∧?∨??→?∧?→??)()()()()
()()()(
所以T B A ??故 B A ?。
3、解：设P ：厂方拒绝增加工资；Q ：罢工停止；R 罢工超壶过一年；R ：撤换厂长 前提：R P Q S R P ??→∧?→,,))(( 结论：Q ?
①)
)((Q S R P ?→∧?→
P
②P P
③Q S R ?→∧?)(
T ①②I ④R ? P ⑤S R ?∨? T ④I ⑥)(S R ∧?
T ⑤E ⑦Q ?
T ③⑥I
罢工不会停止是有效结论。 四、计算 10%
（1）
解：
1
111)01(1
)01(1()11()))001(1(=?=?∨=?→∨=∨?∧→∨
（2）
F R Q Q P R Q Q P R Q Q P R Q Q P ?∧∧?∧?∧∧?∧?∧∧∨???∧∧→?)()()
()()(
它无成真赋值，所以为矛盾式。
五、谓词逻辑推理 15%
解：
y x y x H x x G x x F x x M 喜欢是杂草是花是人:),(;:)(;:)(;:)(
))),()(()((y x H y F y x M x →?∧? ))),()(()((y x H y G y x M x ?→?→? ))()((x G x F x ?→??
证明：
⑴))),()(()((y x H y F y x M x →?∧?
P ⑵)),()(()(y a H y F y a M →?∧
ES ⑴ ⑶)(a M T ⑵I
⑷)),()((y a H y F y →?
T ⑵I ⑸))),()(()((y x H y G y x M x ?→?→? P ⑹)),()(()(y a H y G y a M ?→?→
US ⑸ ⑺)),()((y a H y G y ?→? T ⑶⑹I ⑻))(),((y G y a H y ?→?
T ⑺E ⑼),()(z a H z F → US ⑷ ⑽)()
,(z G z a H ?→ US ⑻ ⑾)()
(z G z F ?→
T ⑼⑽I ⑿))()((x G x F x ?→? UG ⑾
十三、 证明10%
))
()(()
()(())()(())()(())()(())()(())()(())()(())()(())()(())()(())()(())()(()()()(()()()(()()(x B x A x c B c A b B b A a B a A c B c A b B c A a B c A c B b A b B b A a B b A c B a A b B a A a B a A c B b B a B c A b A a A x xB x xA ∨??∨∧∨∧∨?∨∧∨∧∨∧∨∧∨∧∨∧∨∧∨∧∨?∧∧∨∧∧??∨?
试卷五试题与答案
一、填空15%（每空3分）
1、设G 为9阶无向图，每个结点度数不是5就是6，则G 中至少有 个5度结点。
2、n 阶完全图，K n 的点数X (K n ) = 。
3、有向图中从v1到v2长度为2的通路有条。
4、设[R，+，·]是代数系统，如果①[R，+]是交换群②[R，·]是半群
③则称[R，+，·]为环。
5、设
]
,
,
[⊕
?
L是代数系统，则]
,
,
[⊕
?
L满足幂等律，即对L
a∈
?有。
二、选择15%（每小题3分）
1、下面四组数能构成无向简单图的度数列的有（）。
A、（2，2，2，2，2）；
B、（1，1，2，2，3）；
C、（1，1，2，2，2）；
D、（0，1，3，3，3）。
2、下图中是哈密顿图的为（）。
3、如果一个有向图D是强连通图，则D是欧拉图，这个命题的真值为（）
A、真；
B、假。
4、下列偏序集（）能构成格。
5、设
}4,
4
1
,3,
3
1
,2,
2
1
,1{
=
s
，*为普通乘法，则[S，*]是（）。
A、代数系统；
B、半群；
C、群；
D、都不是。
三、证明48%
1、（10%）在至少有2个人的人群中，至少有2 个人，他们有相同的朋友数。
2、（8%）若图G中恰有两个奇数度顶点，则这两个顶点是连通的。
3、（8%）证明在6个结点12条边的连通平面简单图中，每个面的面数都是3。
四、计算22%
1、在二叉树中
1）求带权为2，3，5，7，8的最优二叉树T。（5分）
2）求T对应的二元前缀码。（5分）
2、下图所示带权图中最优投递路线并求出投递路线长度（邮局在D点）。
一、填空（15%）每空3 分
1、 6；
2、n ；
3、2；
4、+对·分配且·对+分配均成立；
5、a a a a a a =⊕=?且。
二、选择（15%）每小题3分
三、证明（48%）
1、（10分）证明：用n 个顶点v 1，…，v n 表示n 个人，构成顶点集V={v 1，…，v n}，设
},,,|{v ）（u v u V v u uv E ≠∈=是朋友且，无向图G=（V ，E ）
现证G 中至少有两个结点度数相同。 事实上，（1）若G 中孤立点个数大于等于2，结论成立。
（2） 若G 中有一个孤立点，则G 中的至少有3个顶点，既不考虑孤立点。设G 中每个结点度数均大于等于1，又因为G 为简单图，所以每个顶点度数都小于等于n-1，由于G 中n 顶点其度数取值只能是1，2，…，n-1，由鸽巢原理，必然至少有两个结点度数是相同的。 2、（8分）证：设G 中两个奇数度结点分别为u ，v 。若 u ，v 不连通则至少有两个连通分支G 1、G 2，使得u ，v 分别属于G 1和G 2。于是G 1与G 2中各含有一个奇数度结点，与握手定理矛盾。因而u ，v 必连通。 3（8分）证：n=6,m=12 欧拉公式n-m+f=2知 f=2-n+m=2-6-12=8 由图论基本定理知：242)deg(=?=∑m F ，而3)deg(≥i
F ，所以必有3)deg(=i
F ，即每个面
用3条边围成。 四、计算（22%）
1、（10分） （1）（5分）由Huffman 方法,得最佳二叉树为：
（2）（5分）最佳前缀码为：000，001，01，10，11 2、（12分）
图中奇数点为E 、F ，d(E)=3,d(F)=3,d(E,F)=28 p=EGF
复制道路EG 、GF ，得图G ‘，则G ‘
是欧拉图。 由D 开始找一条欧拉回路：DEGFGEBACBDCFD 。 道路长度为：
35+8+20+20+8+40+30+50+19+6+12+10+23=281。
一、 填空 15% （每小题 3分）
1、 n 阶完全图结点v 的度数d(v) = 。
2、 设n 阶图G 中有m 条边，每个结点的度数不是k 的是k+1，若G 中有N k 个k 度顶点，N k+1个k+1
度顶点，则N k = 。 3、 算式 )*()*)*(((f e d c b a ÷+的二叉树表示为 。 4、 如图
给出格L ， 则e 的补元是 。
5、 一组学生，用二二扳腕子比赛法来测定臂力的大小，则幺元是 。 二、选择 15% （每小题 3分
1、设S={0,1,2,3},≤为小于等于关系，则{S ，≤}是（ ）。
A 、群；
B 、环；
C 、域；
D 、格。
2、设
则零元为（ A 、a ； B 、b ； C 、c ； D 、没有。
3、如右图 相对于完全图K 5的补图为（ ）。
4一棵无向树T 有7片树叶，3个3度顶点，其余顶点均为4度。则T 有（）4度结点
A 、1；
B 、2；
C 、3；
D 、4。 5、设[A ，+，·]是代数系统，其中+，·为普通加法和乘法，则A=（ ）时，[A ，+，·]是整环。 A 、},2|{Z n n x x ∈=； B 、},12|{Z n n x x ∈+=；
C 、},0|{Z x x x ∈≥且；
D 、},,5|{4R b a b a x x ∈+=。
三、证明 50%
1、设G 是（n,m ）简单二部图，则
42
n m ≤
。（10分）
2、设G 为具有n 个结点的简单图，且
)2)(1(21
-->
n n m ，则G 是连通图。（10分）
3、记“开”为1
，+，·]的加法运算和乘法运算。如下：
分） 4、
],,[⊕?L 是一代数格，“≤”为自然偏序，则[L ，≤]是偏序格。（16分）
四、10%
设
)()()(),,(323221321x x x x x x x x x E ∧∨∧∨∧=是布尔代数],,},1,0[{-∧∨上的一个
布尔表达式，试写出),,(321x x x E 的析取范式和合取范式（10分） 五、10%
如下图所示的赋权图表示某七个城市721,,,v v v 及预先算出它们之间的一些直接通信成路造价（单位：万元）试给出一个设计方案，使得各城市之间既能够通信又使总造价最小。
答案：
一、填空 15%（每小题3分）
1、n-1；
2、n(k+1)-2m ；
3、如右图；
4、0 ；
5、臂力小者 二、选择 15%（每小题 3分）
三、证明 50%
（1） 证：设
G=（V ，E ）
n n n n Y n X Y X V =+==?=212
1,,,
对完全二部图有
4)2()(2
21121
1121n n n n n n n n n n n m +
--=+-=-=?=
当
21n
n =
时，完全二部图),(m n 的边数m 有最大值42n
故对任意简单二部图),(m n 有
42
n m ≤
。
（2）
证：反证法：若G 不连通，不妨设G 可分成两个连通分支G 1、G 2，假设G 1和G 2的顶点
数分别为n 1和n 2，显然n n n =+21
11112121-≤-≤∴≥≥n n n n n n
2
)2)(1(2)2)(1(2)1(2)1(212211--=
-+-≤-+-≤∴n n n n n n n n n m
与假设矛盾。所以G 连通。 （3） （1）[{0，1}，+，·]是环
①[{0，1}，+]是交换群
乘：由“+”运算表知其封闭性。由于运算表的对称性知：+运算可交换。 群： （0+0）+0=0+（0+0）=0 ；（0+0）+1=0+（0+1）=1；
（0+1）+0=0+（1+0）=1 ； （0+1）+1=0+（1+1）=0； （1+1）+1=1+（1+1）=0 …… 结合律成立。
幺：幺元为0。 逆：0，1逆元均为其本身。
②[{0，1}，·]是半群
乘：由“· ”运算表知封闭 群： （0·0）·0=0·（0·0）=0 ；（0·0）·1=0·（0·1）= 0；
（0·1）·0=0·（1·0）=0 ； （0·1）·1=0·（1·1）=0； （1·1）·1=1·（1·1）=0 。
③·对+的分配律 }1,0{,∈?y x Ⅰ 0·（x+y ）=0=0+0=(0·x)+(0·y)； Ⅱ 1·（x+y ）
当x=y (x+y)=0 则
)
1()1()11()11()01()01(1100001)(1y x y x ?+?=???
????+??+?=??????++==?=+?；
当y x ≠（1=+y x ）则
)
1()1()11()01()01()11(1001111)(1y x y x ?+?=???
????+??+?=??????++==?=+? 所以}1
,0{,,∈?z y x 均有)()()(y z x z y x z ?+?=+? 同理可证：)()()(z y z x z y x ?+?=?+
所以·对+ 是可分配的。 由①②③得，[{0，1}，+，·]是环。 （2）[{0，1}，+，·]是域 因为[{0，1}，+，·]是有限环，故只需证明是整环即可。 ①乘交环： 由乘法运算表的对称性知，乘法可交换。 ②含幺环：乘法的幺元是1 ③无零因子：1·1=1≠0 因此[{0，1}，+，·]是整环，故它是域。 4、证：（1 ）“≤”是偏序关系， ≤ 自然偏序
a b a L b a =?∈?,
①反自反性：由代数格幂等关系：a a a a a ≤∴=?。
②反对称性：L b a ∈?, 若 a b b a ≤≤, 即：b a b a b a =?=?,，
则
b a b b a a =?=?= a b ≤ ③传递性：
c b b a ≤≤,则：
a b a b a a b c b b a c b a a
b a b a c
b a
c a =?≤==?≤?=??==?≤??=?即即结合律即 c b )()(
c a ≤∴
（2）L y x ∈?,在L 中存在{x,y}的下（上）确界
设L y x ∈,则：},inf{y x y x =?
事实上：y x y x x y x x ?=??=?
?)()(
y y x x y x ≤?≤?∴:同理可证
若{x , y }有另一下界c ，则c y c y x c y x c =?=??=??)()(
y x c ?≤∴ y x ?∴是{x , y }最大下界，即},inf{y x y x =?
同理可证上确界情况。 四、14%
326《离散数学》期末考试题(B ) 一、填空题(每小题3分，共15分) 1.设,,},,{{b a b a A =?}，则-A ? = ( )，-A {?} = ( )，)(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素，则A 上的二元关系有( )个，其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ，对于其上的整除关系“|”，元素( )不存在补元. 5.当n ( )时，n 阶完全无向图n K 是平面图，当当n 为( )时，n K 是欧拉图. 二．1. 若n B m A ==||,||，则=?||B A ( )，A 到B 的2元关系共有( )个，A 上的2元关系共有( )个. 2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3, 1)}，则( )是单射，( )是满射，( )是双射. 3. 下列5个命题公式中，是永真式的有( )(选择正确答案的番号). (1)q q p p →→∧)(； (2))(q p p ∨→； (3))(q p p ∧→； (4)q q p p →∨∧?)(； (5)q q p →→)(. 4. 设D 24是24的所有正因数组成的集合，“|”是其上的整除关系，则3的补元( )，4的补元( )，6的补元( ). 5. 设G 是(7, 15)简单平面图，则G 一定是( )图，且其每个面恰由( )条边围成，G 的面数为( ).
离散数学考试（试题及答案） 一、（10分）某项工作需要派A、B、C和D4个人中的2个人去完成，按下面3个条件，有几种派法？如何派？ (1)若A去，则C和D中要去1个人； (2)B和C不能都去； (3)若C去，则D留下。 解设A：A去工作；B：B去工作；C：C去工作；D：D去工作。则根据题意应有：ACD，(B∧C)，CD必须同时成立。因此 (ACD)∧(B∧C)∧(CD) (A∨(C∧ D)∨(C∧D))∧(B∨C)∧(C∨D) (A∨(C∧ D)∨(C∧D))∧((B∧C)∨(B∧D)∨C∨(C∧D)) (A∧B∧C)∨(A∧B∧D)∨(A∧C)∨(A∧C∧D) ∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧ D∧C∧D) ∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧D F∨F∨(A∧C)∨F∨F∨(C∧ D∧B)∨F∨F∨(C∧D∧B)∨F∨(C∧D)∨F (A∧C)∨(B∧C∧ D)∨(C∧D∧B)∨(C∧D) (A∧C)∨(B∧C∧ D)∨(C∧D) T 故有三种派法：B∧D，A∧C，A∧D。 二、（15分）在谓词逻辑中构造下面推理的证明：某学术会议的每个成员都是专家并且是工人，有些成员是青年人，所以，有些成员是青年专家。 解：论域：所有人的集合。()：是专家；()：是工人；()：是青年人；则推理化形式为： (()∧())，()(()∧())
下面给出证明： (1)() P (2)(c) T(1)，ES (3)(()∧()) P (4)( c)∧( c) T(3)，US (5)( c) T(4)，I (6)( c)∧(c) T(2)(5)，I (7)(()∧()) T(6) ，EG 三、（10分）设A、B和C是三个集合，则AB(BA)。 证明：ABx(x∈A→x∈B)∧x(x∈B∧xA)x(xA∨x∈B)∧x(x∈B∧xA) x(x∈A∧xB)∧x(xB∨x∈A)x(x∈A∧xB)∨x(x∈A∨xB) (x(x∈A∧xB)∧x(x∈A∨xB))(x(x∈A∧xB)∧x(x∈B→x∈A)) (BA)。 四、（15分）设A＝{1，2，3，4，5}，R是A上的二元关系，且R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。 解 r(R)＝R∪I A＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>} s(R)＝R∪R－1＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>， <5，2>，<1，2>，<4，2>，<4，3>} R2＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>} R3＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>} R4＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}＝R2 t(R)＝R i＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，1>，<5，4>，<5，5>}。
离散数学考试题(后附详细答案) 一、命题符号化（共6小题，每小题3分，共计18分） 1.用命题逻辑把下列命题符号化 a)假如上午不下雨，我去看电影，否则就在家里读书或看报。 设P表示命题“上午下雨”，Q表示命题“我去看电影”，R表示命题“在家里读书”，S表示命题“在家看报”，命题符号化为：（PQ）(PRS) b)我今天进城，除非下雨。 设P表示命题“我今天进城”，Q表示命题“天下雨”，命题符号化为：Q→P或P→Q c)仅当你走，我将留下。 设P表示命题“你走”，Q表示命题“我留下”，命题符号化为：Q→P 2.用谓词逻辑把下列命题符号化 a)有些实数不是有理数 设R(x)表示“x是实数”，Q(x)表示“x是有理数”，命题符号化为： x(R(x) Q(x)) 或x(R(x) →Q(x)) b)对于所有非零实数x，总存在y使得xy=1。 设R(x)表示“x是实数”，E(x,y)表示“x=y”,f(x,y)=xy, 命题符号化为： x(R(x) E(x,0) →y(R(y) E(f(x,y),1)))) c) f 是从A到B的函数当且仅当对于每个a∈A存在唯一的b∈B，使得f(a)=b. 设F(f)表示“f是从A到B的函数”, A(x)表示“x∈A”, B(x)表示“x∈B”,E(x,y)表示“x=y”, 命题符号化为：F(f)a(A(a)→b(B(b) E(f(a),b) c(S(c) E(f(a),c) →E(a,b)))) 二、简答题（共6道题，共32分） 1.求命题公式(P→(Q→R))(R→(Q→P))的主析取范式、主合取范式，并写出所有成真赋值。 （5分） (P→(Q→R))(R→(Q→P))（PQR）(PQR) (（PQR）→(PQR)) ((PQR) →（PQR）). (（PQR）(PQR)) ((PQR) （PQR）) (PQR)(PQR) 这是主合取范式 公式的所有成真赋值为000,001,010,100,101,111,故主析取范式为 （PQR（PQR（PQR（PQR（PQR（PQR 2.设个体域为{1,2,3}，求下列命题的真值（4分） a)xy(x+y=4) b)yx (x+y=4) a) T b) F 3.求x(F(x)→G(x))→(xF(x)→xG(x))的前束范式。（4分） x(F(x)→G(x))→(xF(x)→xG(x)) x(F(x)→G(x))→(yF(y)→zG(z)) x(F(x)→G(x))→yz(F(y)→G(z)) xyz((F(x)→G(x))→(F(y)→G(z))) 4.判断下面命题的真假，并说明原因。（每小题2分，共4分）
离散数学 2^m*n 一、选择题（2*10） 1．令P：今天下雨了，Q：我没带伞，则命题“虽然今天下雨了，但是我没带伞”可符号化为（）。 （A）P→?Q （B）P∨?Q （C）P∧Q （D）P∧?Q 2．下列命题公式为永真蕴含式的是（）。 （A）Q→（P∧Q）（B）P→（P∧Q） （C）（P∧Q）→P （D）（P∨Q）→Q 3、命题“存在一些人是大学生”的否定是(A)，而命题“所有的人都是要死的”的否定 是（）。 （A）所有人都不是大学生，有些人不会死 （B）所有人不都是大学生，所有人都不会死 （C）存在一些人不是大学生，有些人不会死 （D）所有人都不是大学生，所有人都不会死 4、永真式的否定是（）。
（A）永真式（B）永假式（C）可满足式（D）以上均有可能 5、以下选项中正确的是（）。 （A）0= ? （B）0 ? （C）0∈? （D）0?? 6、以下哪个不是集合A上的等价关系的性质？（） ）。 （A）2 （B）4 （C）3 （D）5 10．连通图G是一棵树，当且仅当G中（）。 （A）有些边不是割边（B）每条边都是割边 （C）无割边集（D）每条边都不是割边
二、填空题（2*10） 1、命题“2是偶数或-3是负数”的否定是________。 2、设全体域D是正整数集合，则命题?x?y(xy=y)的真值是______。 3、令R(x):x是实数，Q(x):x是有理数。则命题“并非每个实数都是有理数”的符号化表示为 4 5 6、设 7 8 (1)若A去，则C和D中要去1个人； (2)B和C不能都去； (3)若C去，则D留下 五、（15分）设A={1,2,3},写出下列图示关系的关系矩阵，并讨论它们的性质：
《离散数学》模拟题（补） 一．单项选择题 1．下面四组数能构成无向图的度数列的有( )。 A、 2,3,4,5,6,7； B、 1,2,2,3,4； C、 2,1,1,1,2； D、 3,3,5,6,0。 2．图的邻接矩阵为( )。 A、； B、； C、； D、。 3.设S1={1，2，…，8，9}，S2={2，4，6，8}，S3={1，3，5，7，9}，S4={3，4，5}，S5={3，5}，在条件下X与（）集合相等。 A、X=S2或S5 ； B、X=S4或S5； C、X=S1，S2或S4； D、X与S1，…，S5中任何集合都不等。 4．下列图中是欧拉图的有( )。 5.下述命题公式中，是重言式的为（）。 A、； B、； C、； D、。 6.的主析取范式中含极小项的个数为（）。 A 、2； B、 3； C、5； D、0 ?? ? ? ? ? ? ? ? 1 1 1 1 1 1 1 ?? ? ? ? ? ? ? ? 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ?? ? ? ? ? ? ? ? 1 1 1 1 1 1 1 ?? ? ? ? ? ? ? ? 1 1 1 1 1 1 1 3 1 S X S X? ?且 ) ( ) (q p q p∨ → ∧)) ( )) (( ) (p q q p q p→ ∧ → ? ? q q p∧ → ?) (q p p? ? ∧) ( r q p wff→ ∧ ?) (
7.给定推理 ① P ② US ① ③ P ④ ES ③ ⑤ T ②④I ⑥ UG ⑤ 推理过程中错在（ ）。 A 、①->②; B 、②->③; C 、③->④; D 、④->⑤ 8.设S 1={1，2，…，8，9}，S 2={2，4，6，8}，S 3={1，3，5，7，9}，S 4={3，4，5}， S 5={3，5}，在条件 下X 与（ ）集合相等。 A 、X=S 2或S 5 ； B 、X=S 4或S 5； C 、X=S 1，S 2或S 4； D 、X 与S 1，…，S 5中任何集合都不等。 9.设R 和S 是P 上的关系，P 是所有人的集合， ， 则表示关系 （ ） 。 A 、； B 、 ； C 、 ； D 、 。 10.下面函数（ ）是单射而非满射。 A 、 ； B 、 ； C 、 ； D 、。 ))()((x G x F x →?)()(y G y F →)(x xF ?)(y F )(y G )(x xG ?)())()((x xG x G x F x ??→?∴3 1S X S X ??且},|,{的父亲是y x P y x y x R ∧∈><=},|,{的母亲是y x P y x y x S ∧∈><=R S 1-},|,{的丈夫是y x P y x y x ∧∈><},|,{的孙子或孙女是y x P y x y x ∧∈><Φ},|,{的祖父或祖母是y x P y x y x ∧∈><12)(,:2-+-=→x x x f R R f x x f R Z f ln )(,:=→+的最大整数表示不大于x x x x f Z R f ][],[)(, :=→12)(,:+=→x x f R R f
离散数学试题（A卷答案） 一、（10分）求(P↓Q)→(P∧?(Q∨?R))的主析取范式 解：(P↓Q)→(P∧?(Q∨?R))??(?( P∨Q))∨(P∧?Q∧R)) ?(P∨Q)∨(P∧?Q∧R)) ?(P∨Q∨P)∧(P∨Q∨?Q)∧(P∨Q∨R) ?(P∨Q)∧(P∨Q∨R) ?(P∨Q∨(R∧?R))∧(P∨Q∨R) ?(P∨Q∨R)∧(P∨Q∨?R)∧(P∨Q∨R) ? M∧1M ? m∨3m∨4m∨5m∨6m∨7m 2 二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断： 甲说：王教授不是苏州人，是上海人。 乙说：王教授不是上海人，是苏州人。 丙说：王教授既不是上海人，也不是杭州人。 王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人？ 解设设P：王教授是苏州人；Q：王教授是上海人；R：王教授是杭州人。则根据题意应有： 甲：?P∧Q 乙：?Q∧P 丙：?Q∧?R 王教授只可能是其中一个城市的人或者3个城市都不是。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有?Q ∧P，因此，乙全对。同理，乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为：
((?P ∧Q )∧((Q ∧?R )∨(?Q ∧R )))∨((?Q ∧P )∧(?Q ∧R )) ?(?P ∧Q ∧Q ∧?R )∨(?P ∧Q ∧?Q ∧R )∨(?Q ∧P ∧?Q ∧R ) ?(?P ∧Q ∧?R )∨(P ∧?Q ∧R ) ??P ∧Q ∧?R ?T 因此，王教授是上海人。 三、（10分）证明tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 证明 设R 是非空集合A 上的二元关系，则由定理4.19知，tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。 若'R 是包含R 的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r (R )?'R 。由定理4.15和由定理4.16得sr (R )?s ('R )＝'R ，进而有tsr (R )?t ('R )＝'R 。 综上可知，tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 四、（15分）集合A ＝{a ，b ，c ，d ，e }上的二元关系R 为R ＝{，，，，，，，，
离散数学试题与答案试卷一 一、填空 20% （每小题2分） 1．设 }7|{)},5()(|{<∈=<∈=+x E x x B x N x x A 且且（N ：自然数集，E + 正偶数） 则 =?B A 。 2．A ，B ，C 表示三个集合，文图中阴影部分的集合表达式为 。 3．设P ，Q 的真值为0，R ，S 的真值为1，则 )()))(((S R P R Q P ?∨→?∧→∨?的真值= 。 4．公式P R S R P ?∨∧∨∧)()(的主合取范式为 。 5．若解释I 的论域D 仅包含一个元素，则 )()(x xP x xP ?→? 在I 下真值为 。 6．设A={1，2，3，4}，A 上关系图为 则 R 2 = 。 7．设A={a ，b ，c ，d}，其上偏序关系R 的哈斯图为 则 R= 。 8．图的补图为 。 9．设A={a ，b ，c ，d} ，A 上二元运算如下： * a b c d A B C
a b c d a b c d b c d a c d a b d a b c ，有逆元的元素为 ，它们的 逆元分别为 。 10．下图所示的偏序集中，是格的为 。 二、选择 20% （每小题 2分） 1、下列是真命题的有（ ） A ． }}{{}{a a ?； B ．}}{,{}}{{ΦΦ∈Φ； C ． }},{{ΦΦ∈Φ； D ． }}{{}{Φ∈Φ。 2、下列集合中相等的有（ ） A ．{4，3}Φ?； B ．{Φ，3，4}； C ．{4，Φ，3，3}； D ． {3，4}。 3、设A={1，2，3}，则A 上的二元关系有（ ）个。 A ． 23 ； B ． 32 ； C ． 332?； D ． 223?。 4、设R ，S 是集合A 上的关系，则下列说法正确的是（ ） A ．若R ，S 是自反的， 则S R ο是自反的； B ．若R ，S 是反自反的， 则S R ο是反自反的； C ．若R ，S 是对称的， 则S R ο是对称的； D ．若R ，S 是传递的， 则S R ο是传递的。 5、设A={1，2，3，4}，P （A ）（A 的幂集）上规定二元系如下 |}||(|)(,|,{t s A p t s t s R =∧∈><=则P （A ）/ R=（ ） A ．A ； B ．P(A) ； C ．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}； D ．{{Φ}，{2}，{2，3}，{{2，3，4}}，{A}} 6、设A={Φ，{1}，{1，3}，{1，2，3}}则A 上包含关系“?”的哈斯图为（ ）
《离散数学》+答案 一、选择或填空: 1、下列哪些公式为永真蕴含式？( ) (1)?Q=>Q→P (2)?Q=>P→Q (3)P=>P→Q (4)?P∧(P∨Q)=>?P 答：在第三章里面有公式（1）是附加律，（4）可以由第二章的蕴含等值式求出（注意与吸收律区别） 2、下列公式中哪些是永真式？( ) (1)(┐P∧Q)→(Q→?R) (2)P→(Q→Q) (3)(P∧Q)→P (4)P→(P∨Q) 答：（2），（3），（4）可用蕴含等值式证明 3、设有下列公式，请问哪几个是永真蕴涵式?( ) (1)P=>P∧Q (2) P∧Q=>P (3) P∧Q=>P∨Q (4)P∧(P→Q)=>Q (5) ?(P→Q)=>P (6) ?P∧(P∨Q)=>?P 答：（2）是第三章的化简律，（3）类似附加律，（4）是假言推理，（3），（5），（6）都可以用蕴含等值式来证明出是永真蕴含式 4、公式?x((A(x)→B(y，x))∧?z C(y，z))→D(x)中，自由变元是( )，约束变元是( )。 答：x,y, x,z（考察定义在公式?x A和?x A中，称x为指导变元，A为量词的辖域。在?x A和?x A的辖域中，x的所有出现都称为约束出现，即称x为约束变元，A中不是约束出现的其他变项则称为自由变元。于是A(x)、B(y，x)和?z C(y，z)中y为自由变元，x和z为约束变元，在D(x)中x为自由变元） 5、判断下列语句是不是命题。若是，给出命题的真值。( ) (1)北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。 (3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。 (5) 前进！ (6) 给我一杯水吧！ 答：（1）是，T （2）是，F （3）不是（4）是，T （5）不是（6） 44
离散数学（上）模拟题 1、命题符号化（共6小题，每小题3分，共计18分） 1. 用命题逻辑把下列命题符号化 a) 假如上午不下雨，我去看电影，否则就在家里读书或看报。 b) 我今天进城，除非下雨。 c) 仅当你走，我将留下。 2. 用谓词逻辑把下列命题符号化 a) 有些实数不是有理数 b) 对于所有非零实数x，总存在y使得xy=1。 c) f 是从A到B的函数当且仅当对于每个a∈A存在唯一的b∈B，使得 f(a)=b. 2、简答题（共6道题，共32分） 1. 求命题公式(P→(Q→R))(R→(Q→P))的主析取范式、主合取范 式，并写出所有成真赋值。（5分） 2. 设个体域为{1,2,3}，求下列命题的真值（4分） a) xy(x+y=4) b) yx (x+y=4) 3. 求x(F(x)→G(x))→(xF(x)→xG(x))的前束范式。（4分） 4. 判断下面命题的真假，并说明原因。（每小题2分，共4分） a) （AB）－C=(A-B) (A-C) b) 若f是从集合A到集合B的入射函数，则|A|≤|B| 5. 设A是有穷集，|A|=5，问（每小题2分，共4分） a) A上有多少种不同的等价关系？ b) 从A到A的不同双射函数有多少个？ 6. 设有偏序集
下列集合的基数S;P(S);N,N n;P(N);R,R×R,{o,1}N（写出即 可）(6分) 3、证明题（共3小题，共计40分） 1. 使用构造性证明，证明下面推理的有效性。（每小题5分，共10 分） a) A→(B∧C),(E→F)→C, B→(A∧S)B→E b) x(P(x)→Q(x)), x(Q(x)∨R(x))，xR(x) xP(x) 2. 设R1是A上的等价关系，R2是B上的等价关系，A≠且B≠，关系R 满足：<
常熟理工学院20 ～20 学年第学期 《离散数学》考试试卷（试卷库01卷） 试题总分： 100 分考试时限：120 分钟 题号一二三四五总分阅卷人得分 一、单项选择题（每题2分，共20分） 1.下列表达式正确的有( ) （A）（B）（C）（D） 2.设P：2×2=5，Q：雪是黑的，R：2×4=8，S：太阳从东方升起，下列( )命题的真值为 真。 （A）（B）（C）（D） 3.集合A={1,2,…,10}上的关系R={
1．n个命题变元组成的命题公式共有种不同的等价公式。 2．设〈L，≤〉为有界格，a为L中任意元素，如果存在元素b∈L,使，则称b是a 的补元。 3．设*，Δ是定义在集合A上的两个可交换二元运算，如果对于任意的x,y∈A,都有 ,则称运算*和运算Δ满足吸收律。 4．设T是一棵树，则T是一个连通且的图。 5．一个公式的等价式称作该公式的主合取范式是指它仅由组成。 6．量词否定等价式? ("x)P(x) ?，? ($x)P(x) ?。 7．二叉树有5个度为2的结点，则它的叶子结点数为。 8．设
第一章 1.假定A是ECNU二年级的学生集合，B是ECNU必须学离散数学的学生的集合。请用A 和B表示ECNU不必学习离散数学的二年级的学生的集合。 2.试求： (1)P(φ) (2)P(P(φ)) (3)P(P(P(φ))) 3.在1~200的正整数中，能被3或5整除，但不能被15整除的正整数共有多少个？ 能被5整除的有40个， 能被15整除的有13个， ∴能被3或5整除，但不能被15整除的正整数共有 66-13+40-13=80个。 第三章 1.下列语句是命题吗？ (1)2是正数吗？ (2)x2+x+1=0。 (3)我要上学。 (4)明年2月1日下雨。 (5)如果股票涨了，那么我就赚钱。 2.请用自然语言表达命题(p?→r)∨(q?→r)，其中p、q、r为如下命题： p：你得流感了 q：你错过了最后的考试
3.通过真值表求p→(p∧(q→p))的主析取范式和主合取范式。 4.给出p→(q→s),q,p∨?r?r→s的形式证明。 第四章 1.将?x(C(x)∨?y(C(y)∧F(x,y)))翻译成汉语，其中C(x)表示x有电脑，F(x,y) 表示x和y是同 班同学，个体域是学校全体学生的集合。 解： 学校的全体学生要么自己有电脑，要么其同班同学有电脑。 2.构造?x(P(x)∨Q(x)),?x(Q(x)→?R(x)),?xR(x)??xP(x)的形式证明。 解： ①?xR(x) 前提引入 ②R(e) ①US规则 ③?x(Q(x)→?R(x)) 前提引入 ④Q(e) →?R(e) ③US规则 ⑤?Q (e) ②④析取三段论 ⑥?x(P(x)∨Q(x)) 前提引入 ⑦P(e) ∨Q(e) ⑥US规则 ⑧P(e) ⑤⑦析取三段论 ⑨?x (P(x)) ⑧EG规则 第五章
北京语言大学网络教育学院 《离散数学》模拟试卷一 注意： 1.试卷保密，考生不得将试卷带出考场或撕页，否则成绩作废。请监考老师负责监督。 2.请各位考生注意考试纪律，考试作弊全部成绩以零分计算。 3.本试卷满分100分，答题时间为90分钟。 4.本试卷分为试题卷和答题卷，所有答案必须答在答题卷上，答在试题卷上不给分。 一、【单项选择题】(本大题共15小题，每小题3分，共45分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。 1、在由3个元素组成的集合上，可以有 ( ) 种不同的关系。 [A] 3 [B] 8 [C]9 [D]27 2、设{}{}1,2,3,5,8,1,2,5,7A B A B ==-=,则（ ）。 [A] 3,8 [B]{}3 [C]{}8 [D]{}3,8 3、若X 是Y 的子集，则一定有（ ）。 [A]X 不属于Y [B]X ∈Y [C]X 真包含于 Y [D]X∩Y=X 4、下列关系中是等价关系的是（ ）。 [A]不等关系 [B]空关系 [C]全关系 [D]偏序关系 5、对于一个从集合A 到集合B 的映射，下列表述中错误的是（ ）。 [A]对A 的每个元素都要有象 [B] 对A 的每个元素都只有一个象 [C]对B 的每个元素都有原象 [D] 对B 的元素可以有不止一个原象 6、设p:小李努力学习，q:小李取得好成绩，命题“除非小李努力学习，否则他不能取得好成绩”的符号化形式为（ ）。 [A]p→q [B]q→p [C]┐q→┐p [D]┐p→q 7、设A={a,b,c},则A 到A 的双射共有（ ）。 [A]3个 [B]6个 [C]8个 [D]9个
试卷二试题与参考答案 一、填空 1、 P:您努力,Q:您失败。 2、 “除非您努力,否则您将失败”符号化为 ; “虽然您努力了,但还就是失败了”符号化为 。 2、论域D={1,2},指定谓词P P (1,1) P (1,2) P (2,1) P (2,2) T T F F 则公式x ??真值为 。 3设A={2,3,4,5,6}上的二元关系}|,{是质数x y x y x R ∨<><=,则 R= (列举法)。 R 的关系矩阵M R = 。 4、设A={1,2,3},则A 上既不就是对称的又不就是反对称的关系 R= ;A 上既就是对称的又就是反对称的关系R= 。 5、设代数系统
二、选择 1、在下述公式中就是重言式为( ) A.)()(Q P Q P ∨→∧; B.))()(()(P Q Q P Q P →∧→??; C.Q Q P ∧→?)(; D.)(Q P P ∨→。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为( ),成真赋值的个数为 ( )。 A.0; B.1; C.2; D.3 。 3、设}}2,1{},1{,{Φ=S ,则 S 2 有( )个元素。 A.3; B.6; C.7; D.8 。 4、设} 3 ,2 ,1 {=S ,定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产 生的S S ?上一个划分共有( )个分块。 A.4; B.5; C.6; D.9 。 5、设} 3 ,2 ,1 {=S ,S 上关系R 的关系图为 则R 具有( )性质。 A.自反性、对称性、传递性; B.反自反性、反对称性; C.反自反性、反对称性、传递性; D.自反性 。 6、设 ο,+ 为普通加法与乘法,则( )>+<ο,,S 就是域。 A.},,3|{Q b a b a x x S ∈+== B.},,2|{Z b a n x x S ∈== C.},12|{Z n n x x S ∈+== D.}0|{≥∧∈=x Z x x S = N 。 7、下面偏序集( )能构成格。
1. 写出命题公式 ﹁（P →（P ∨ Q ））的真值表。 答案： 2.证明 答案： 3. 证明以下蕴涵关系成立： 答案： 4. 写出下列式子的主析取范式： 答案： 5. 构造下列推理的论证：p ∨q, p →r, s →t, s →r, t q 答案： ) ()(R P Q P ∨∧∧?) ()(R P Q P ∨∧?∨??) )(())(R Q P P Q P ∧?∨?∨∧?∨??) ()()()(R Q R P P Q P P ∧?∨∧?∨∧?∨∧??) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) ()()(P R Q P R Q Q R P ?∧∧?∨∧∧?∨?∧∧?∨) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) (Q R P ?∧∧?∨) ()(Q P Q P Q P ?∧?∨∧??Q) P (Q)(P P) (Q P)P (Q)(Q Q)P (P) Q)P ((Q)Q)P (P) Q (Q)P (Q P ?∧?∨∧?∧∨∧?∨?∧∨?∧??∧∨?∨?∧∨??∨?∧∨???Q Q P P ?∨∧?)() ()(R P Q P ∨∧∧?
①s →t 前提 ②t 前提 ③s ①②拒取式I12 ④s →r 前提 ⑤r ③④假言推理I11 ⑥p →r 前提 ⑦p ⑤⑥拒取式I12 ⑧p ∨q 前提 ⑨q ⑦⑧析取三段论I10 6. 用反证法证明：p →((r ∧s)→q), p, s q 7. 请将下列命题符号化： 所有鱼都生活在水中。 答案： 令 F( x )：x 是鱼 W( x )：x 生活在水中 ))((W(x)F(x)x →? 8. 请将下列命题符号化： 存在着不是有理数的实数。 答案： 令 Q ( x )：x 是有理数 R ( x )：x 是实数 Q(x))x)(R(x)(?∧? 9. 请将下列命题符号化： 尽管有人聪明，但并非一切人都聪明。 答案： 令M(x)：x 是人 C(x)：x 是聪明的 则上述命题符号化为 10. 请将下列命题符号化： 对于所有的正实数x,y ，都有x+y ≥x 。 答案： 令P(x):x 是正实数 S(x,y): x+y ≥x 11. 请将下列命题符号化： 每个人都要参加一些课外活动。 答案： ))) ()((())()((x C x M x x C x M x →??∧∧?)) ,()()((y x S y P x P y x →∧??
离散数学课后答案 习题一 6.将下列命题符号化。 （1）小丽只能从框里那一个苹果或一个梨. （2）这学期，刘晓月只能选学英语或日语中的一门外语课. 答： （1）（p Λ?q ）ν（?pΛq）其中p:小丽拿一个苹果，q:小丽拿一个梨（2）（p Λ?q ）ν（?pΛq）其中p:刘晓月选学英语，q:刘晓月选学日语 14.将下列命题符号化. (1) 刘晓月跑得快, 跳得高. (2)老王是山东人或河北人. (3)因为天气冷, 所以我穿了羽绒服. (4)王欢与李乐组成一个小组. (5)李辛与李末是兄弟. (6)王强与刘威都学过法语. (7)他一面吃饭, 一面听音乐. (8)如果天下大雨, 他就乘班车上班. (9)只有天下大雨, 他才乘班车上班. (10)除非天下大雨, 他才乘班车上班. (11)下雪路滑, 他迟到了. (12)2与4都是素数, 这是不对的. (13)“2或4是素数, 这是不对的”是不对的. 答： (1)p∧q, 其中, p: 刘晓月跑得快, q: 刘晓月跳得高. (2)p∨q, 其中, p: 老王是山东人, q: 老王是河北人. (3)p→q, 其中, p: 天气冷, q: 我穿了羽绒服. (4)p, 其中, p: 王欢与李乐组成一个小组, 是简单命题. (5)p, 其中, p: 李辛与李末是兄弟. (6)p∧q, 其中, p: 王强学过法语, q: 刘威学过法语. (7)p∧q, 其中, p: 他吃饭, q: 他听音乐. (8)p→q, 其中, p: 天下大雨, q: 他乘班车上班. (9)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (10)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (11)p→q, 其中, p: 下雪路滑, q: 他迟到了. (12) ? (p∧q)或?p∨?q, 其中, p: 2是素数, q: 4是素数. (13) ? ? (p∨q)或p∨q, 其中, p: 2是素数, q: 4是素数. 16. 19.用真值表判断下列公式的类型: (1)p→ (p∨q∨r) (2)(p→?q) →?q
《离散数学》模拟试题 一、 填空题（每小题2分，共20分） 1. 已知集合A ={φ，1，2}，则A 得幂集合p （A ）=_____ _。 2. 设集合E ={a , b , c , d , e }, A = {a , b , c }, B = {a , d , e }, 则A ∪B =___ ___， A ∩ B =____ __，A －B =___ ___，～A ∩～B =____ ____。 3. 设A ，B 是两个集合，其中A = {1, 2, 3}, B = {1, 2}，则A －B =____ ___， ρ（A ）－ρ（B ）=_____ _ _。 4. 已知命题公式，则G 的析取范式为 。 5. 设P ：2＋2＝4，Q ：3是奇数；将命题“2＋2＝4，当且仅当3是奇数。”符号化 ，其真值为 。 二、单项选择题（选择一个正确答案的代号填入括号中，每小题4分，共16分。） 1. 设A 、B 是两个集合，A ＝{1,3,4}，B ＝{1,2}，则A －B 为（ ）. A. {1} B. {1, 3} C. {3,4} D. {1,2} 2. 下列式子中正确的有（ ）。 A. φ＝0 B. φ∈{φ} C. φ∈{a,b} D. φ∈φ 3. 设集合X ＝{x , y }，则ρ（X ）＝（ ）。 A. {{x },{y }} B. {φ,{x },{y }} C. {φ,{x },{y },{x , y }} D. {{x },{y },{x , y }} 4. 设集合 A ＝{1,2,3}，A 上的关系 R ＝ {(1,1),(2,2),(2,3),(3,3),(3,2)}， 则R 不具备（ ）. 三、计算题（共50分） R Q P G →∧?=)(
第1章 一.填空题 1. 2. 公式P→(Q→R)在联结词全功能集{﹁,∨}中等值形式为___________________。 3. 4. 5. 6. 7. 全体小项的析取式必为____________________式。 8. P,Q为两个命题，则德摩根律可表示为7. 全体小项的析取式必为_________式。 9. P,Q为两个命题，则吸收律可表示为____________________ 。 10. 设P：我有钱，Q：我去看电影。命题“虽然我有钱，但是我不去看电影”符号化为_____ _______________。 11. 设P：我生病，Q：我去学校。命题“如果我生病，那么我不去学校”符号化为_________ ___________。 12. 13. 14. 15. 设P、Q为两个命题，交换律可表示为____________________。 16. 17. 命题“如果你不看电影，那么我也不看电影”（P：你看电影，Q：我看电影）的符号化为____________________ 。
18. 19. 20. 21. P：你努力，Q：你失败。命题“除非你努力，否则你将失败”的翻译为_______________ _____。 22. 23. 24. 一个重言式和一个矛盾式的合取是____________________。 25. 全体小项的析取式为____________________ 。 26. 命题“如果你不看电影，那么我也不看电影”（P：你看电影，Q：我看电影）的符号化为____________________。 27. 28. 设P：它占据空间，Q：它有质量，R：它不断运动，S：它叫做物质。命题“占据空间的，有质量的而且不断运动的叫做物质”的符号化为____________________。 29. 30. 二.选择题 1. 2. 3. 在除﹁之外的四大联结词中，满足结合律的有几个( )。 A. 2 B.3 C. 4 D. 1 4. 判断下列语句哪个是命题( )。 A.你喜欢唱歌吗？ B.若7+8＞18，则三角形有4条边。 C.前进！ D. 给我一杯水吧！
02任务_000 1 试卷总分：100 测试时间：0 单项选择题 一、单项选择题（共10 道试题，共100 分。） 1. 设集合A = {1, a }，则P(A) = ( )． A. {{1}, {a}} B. {,{1}, {a}} C. {{1}, {a}, {1, a }} D. {,{1}, {a}, {1, a }} 2. 集合A={1, 2, 3, 4}上的关系R={
5. 设集合A={1 , 2 , 3 , 4}上的二元关系R={<1, 1>，<2, 2>，<2, 3>，<4, 4>}，S={<1, 1>，<2, 2>，<2, 3>，<3, 2>，<4, 4>}，则S是R的（）闭包． A. 自反 B. 传递 C. 对称 D. 自反和传递 6. 若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是( )． A. A B，且A B B. B A，且A B C. A B，且A B D. A B，且A B 7. 设集合A={1，2，3，4，5}，偏序关系≤是A上的整除关系，则偏序集