总复习题（一）
一．单选题
1 (C)。一连通的平面图，5个顶点3个面，则边数为（）。
、4 、5 、6 、7
2、 (A)。如果一个简单图
，则称为自补图，非同构的无向4阶自补图有（）个。
、1 、2 、3 、4
3、 (D)。为无环有向图，
为的关联矩阵，则（）
。 、是
的终点、与不关联、与关联、是的始点
4、 (B)。一连通的平面图，8个顶点4个面，则边数为。
、9 、10 、11 、12
5、 (D)。如果一个简单图
，则称为自补图，非同构的3阶有向完全图的子图中
自补图有个。
、1 、2 、3 、4
6、21条边，3个4度顶点，其余顶点为3度的无向图共有个顶点。
、13 、12 、11 、10
7、 (D)。有向图的通路包括。
、简单通路、初级通路、复杂通路、简单通路、初级通路和复杂通路
8、 (D)。一连通的平面图，9个顶点5个面，则边数为。
、9 、10 、11 、12
9、21条边，3个4度顶点，其余顶点为3度的无向图共有个顶点。
、13 、12 、11 、10
10、 (D)。有向图的通路包括。
、简单通路、初级通路、复杂通路、简单通路、初级通路和复杂通路
11、 (D)。一连通的平面图，9个顶点5个面，则边数为。
、9 、10 、11 、12
12、 (B)。为有向图，为的邻接矩阵，则。
、邻接到的边的条数是５、接到的长度为４的通路数是５
A B C D G
G ?G A B C D E ,V D =[]m n ij m ?D 1m ij =A i v j
e B i v j e C i v j e D i v j e A B C D G
G ?G A B C D A B C D A B C D A B C D A B C D A B C D A B C D E ,V D
=[]n n ij a ?D 5a )4(ij =A i v j v B i v j v
、长度为４的通路总数是５、长度为４的回路总数是５
13、 (C)。在无向完全图中有个结点，则该图的边数为（）。
A 、
B 、
C 、
D 、
14、 (C)。任意平面图最多是（）色的。
A 、3
B 、4
C 、5
D 、6
15、 (A)。对与10个结点的完全图，对其着色时，需要的最少颜色数为（）
。 A 、10 B 、9 C 、11 D 、12
16、(C)。对于任意的连通的平面图，且每个面的次数至少为有，其中，分
别为的阶数、边数。
、
、 、
、
二．判断题
1、 (A)。有向图的关联矩阵要求图是无环图。（ ）
2、 (A)。是某图的度数序列。（ ）
3、 (A)。无向连通图的点的连通关系是等价关系（ ）
4、 (B)。是某图的度数序列。（ ）
5、 (A)。V 和E 分别为无向连通图G1的点割集和边割集. G1 -E 的连通分支个数为2。
( )
6、 (A)。彼得森图不是哈密尔顿图。（ ）
7、 (B)。是平面图。（ ）
8、 (B)。设是平面图，若，则它们的对偶图。（ ） 9、 (A)。是平面图。（ ）
10、 (A)。一个简单图的闭包是汉密尔顿图时，这个简单图是汉密尔顿图。（） 11、 (B)。平面图中，任何两条边除端点外可以有其他交点。（） 12、 (B)。余树一定是树。（ ）
13、 (A)。为无向连通图，是的生成子图，并且是树，则是的生成树。（ ）
C D n 12n 212n 1
(1)2n n -(1)n n -G 10
K 10
()x K
G )3l
(l ≥m ,n G A )2n (2l l m --≥
B )2n (l 2
-l m -≤C )2n (2l l m --≤
D )2n (l 2
-l m -≥)1,1,2,2,4()1,1,1,4(5K 2,1G G 21G G ?**?21G G 4K G T G T T G
14、 (A)。是非平凡的无向树，则至少有两片树叶（ ）
15、 (B)。无向树有3个3度、2个2度顶点，其余顶点都是树叶，共有4片树叶。 ( ) 16、 (A)。无向树有3个3度、2个2度顶点，其余顶点都是树叶，共有5片树叶。( ) 17、 (B)。已知n(n>=2)阶无向简单树具有n-1条边，他一定是树。( )
18、 (A)。一个连通无向图中，存在两个结点和，如果结点和的每一条路都通过结
点，则结点比为割点。（）
19、 (A)。一个有向图，如果中有一个回路，至少包含每个结点一次，则是强连通。 20、 (A)。给定图，则关于树的定义是每一对结点之间有且仅有一条路。（） 21、 (A)。完全叉树是每一个结点的出度等于或0的根树。（）
22、 (A)。在正则叉树中，所有的树叶层次相同。（）
23、 (B)。树中分支点的通路长度为外部通路长度。（）
24、 (B)。树中树叶的通路长度为内部通路长度。（）
25、 (A)。任何一棵二叉树的树叶可对应一个前缀码。（）
26、(A)。任何一个前缀码都对应一棵二叉树。（）
三．综合题
1.证明:若图是自对偶的，则.
2.T 是一棵树,有两个2度结点，一个3度结点，三个4度结点，T 有几片树叶？
解：设树T 有x 片树叶，则T 的结点数 n =2+1+3+x
T 的边数m =n -1=5+x
又由得 2 ·（5+x ）=2·2+3·1+4·3+x
所以x =9，即树T 有9片树叶。
3.图所示的赋权图G 表示七个城市a,b,c,d,e,f,g 及架起城市间直接通讯线路的预测造价。试给出一个设计方案使得各城市间能够通讯且总造价最小,并计算出
T n T u v u v w w G G G T m m
m
最小造价。
解：最小生成树为
因此如图T
架线使各城市间能够通讯，且总造价最小，最小造价为：
G
Ｗ(Ｔ)＝１＋３＋４＋８＋９＋23＝48
4.求出下所示图的邻接矩阵和可达性矩阵，并找出
。
0100
??
解：邻接矩阵
答案错误
5.求下图的一棵最小生成树.
解：因为图中n ＝8，所以按算法要执行n －1＝7次，其过程见下图中(1)~(7)。
(2)
(3)
(4)
(1)(2)(3)(4)
01000100001000100
0101
10011001
1000
1101110111011101100011001101110111011101
11011101110111011101
110A A A P A A A A ????????????
?
??
??
?
=∧=??????
???
??
?
??????
??????
??
?
?
??
==??
??
??
??
??
?????=∨∨∨=????
?
?
??
?
6.v 1到v 4,v 4到v 1长为3的通路各有多少条?
求出下所示图的邻接矩阵和可达性矩阵
v 1到v 4长为3的通路0条，v 4到v 1长为3的通路3条。
?
??
?
?
????
???=?
?
?
?
?????
???=?
?
?
?
?????
???=?
?
?
?
?????
???=1004
0104100500010103
100301040001100201021003000101011001010200014
3
2
A A A A ?
?
?
?
?
???????=1101
1101
11110001P
总复习题二
1、 (B)。设
是半群，其中为非空集合，如果是上满足交换律的二元运算，则
称
为。
、半群、可交换半群、可交换群、域
2、 (D)。设是代数系统，其中为非空集合，如果,+是上的二元运算，则称
环
、为半群、为阿贝尔群、乘法对加法适合分配律、满足A 、B 、C 三
条
3、 (D)。设是环，如果乘法适合交换律，则称环。
、整环、除环、域、交换环
4、 (B)。设代数系统是个独异点，对任意，且均有逆元，则为（）。
A 、
B 、
C 、
D 、
5、 (D)。设代数系统是个独异点，则还需满足（）条件，代数系统为群。
A 、运算封闭
B 、运算可结合
C 、运算可交换
D 、每个元素有逆元
6、 (B)。代数系统中，如果存在为等幂元，则（）。
A 、
B 、
C 、
D 、
7、 (B)。设是个群，是的平凡子群，则=（）。
A 、
B 、
C 、
D 、
8、 (D)。在群中，对于，必存在，使得，则为（）。
A 、
B 、
C 、
D 、
9、 (C)。设代数系统是群，则运算满足（）条件，是阿贝尔群。
A 、运算封闭
B 、运算可结合
C 、运算可交换
D 、每个元素有逆元
,A A A ,A A B C D +?,,A A ?A +?,,A A ?,A B +,A C D +?,,A ?A B C D ,*S <>,a b S ∈,a b 1
(*)a b -1
1
*a b --1
1
*b a --1
*a b -1
*b a -,*G <>,*G <>***,*G <>a *a a e =*a a a =1
*a a
a -=1*a a e -=,*G <>,*S <>,*G <>S {}φ{}e {}θ{}a ,*G <>,a
b G ∈x G ∈*a x b =x e *b e 1
*b a
-1
*a b -,*G <>*,*G <>***
判断题 1、(A)
。
为独异点，且中任意元素都存在逆元，则为一个群。
（ ）
2、(A)。
为代数系统，为二元运算，如果是可结合的，且中任意元素都存在逆
元，则
为一个群。
（ ） 3、(B)。
为独异点，且中任意元素都存在逆元，则
为一个半群。（ ）
三．综合题
1.设 °运算为Q 上的二元运算，
(1) 指出°运算的性质.
(2) 求 °运算的单位元、零元和所有可逆元. 解：(1) °运算可交换，可结合. 任取 x , y ∈Q ,
x °y = x +y +2xy = y +x +2yx = y °x , 任取 x , y , z ∈Q ,
(x °y )°z = (x +y +2xy )+z +2(x +y +2xy )z = x +y +z +2xy +2xz +2yz +4xyz
x °(y °z ) = x +(y +z +2yz )+2x (y +z +2yz = x +y +z +2xy +2xz +2yz +4xyz
(2) 设°运算的单位元和零元分别为 e 和 θ，则对于任 意 x 有 x °e = x 成立，即
x +e +2xe = x ?e = 0 由于°运算可交换，所以 0 是幺元. 对于任意 x 有x °θ= θ成立，即
x +θ+2x θ =θ?x +2x θ= 0 ?θ = -1/2
给定 x ，设 x 的逆元为 y , 则有 x °y = 0 成立，即
x +y +2xy = 0 ? (x ≠ -1/2 ) 因此当x ≠-1/2时， 是x 的逆元.
2.S = P ({1, 2}), ⊕为对称差运算，写出 的运算表，并判断此代数系统是一个群。
,G G ,G ,G G ,
,G G
,G
3.证明关于gcd, lcm运算构成的布尔代数.
解(1) 不难验证S110关于gcd和lcm 运算构成格. (略)
(2) 验证分配律?x, y, z∈S110有
gcd(x, lcm(y, z)) = lcm(gcd(x, y), gcd(x, z))
(3) 验证它是有补格, 1作为S110中的全下界, 110为全上界,
1和110互为补元, 2和55互为补元, 5和22互为补元, 10和
11互为补元, 从而证明了
总复习题三
一．证明下列公式等值
二．（1）求(p→?q)∨?r公式的析取范式与合取范式以及成真赋值成假赋值。解(p→?q)→r
? (p∧q)∨r（析取范式）①
(p∧q)
? (p∧q)∧(?r∨r)
? (p∧q∧?r)∨(p∧q∧r)
?m6∨m7 ②
r
? (?p∨p)∧(?q∨q)∧r
? (?p∧?q∧r)∨(?p∧q∧r)∨(p∧?q∧r)∨(p∧q∧r)
?m1∨m3∨m5∨m7 ③
②, ③代入①并排序，得
(p→?q)→r?m1∨m3∨m5∨m6∨m7（主析取范式）
(p→?q)→r
? (p∨r)∧(q∨r) （合取范式）④
p∨r
?p∨(q∧?q)∨r
? (p∨q∨r)∧(p∨?q∨r)
?M0∧M2 ⑤
q∨r
? (p∧?p)∨q∨r
? (p∨q∨r)∧(?p∨q∨r)
?M0∧M4⑥
⑤, ⑥代入④并排序，得
(p→?q)→r?M0∧M2∧M4（主合取范式）
成真赋值为 001, 011, 101, 110, 111，
成假赋值为 000, 010, 100.
（2）已知命题公式A中含3个命题变项p, q, r，并知道它的成真
赋值为001, 010, 111, 求A的主析取范式和主合取范式，及A对应的真值函数.
解：A的主析取范式为m1 ∨m2∨m7
A的主合取范式为M0∧M3∧M4 ∧M5∧M6
pq r F pq r F
0 0 0 0 1 0 0 0
0 0 1 1 1 0 1 0
0 1 0 1 1 1 0 0
0 1 1 0 1 1 1 1
三．构造下面推理的证明：
（1）若明天是星期一或星期三，我明天就有课. 若我明天有课，今天必备课. 我今天没备课. 所以，明天不是星期一、
也不是星期三.
解(1) 设命题并符号化
设p：明天是星期一，q：明天是星期三，
r：我明天有课，s：我今天备课
(2) 写出证明的形式结构
前提：(p∨q)→r, r→s, ?s
结论：?p∧?q
(3) 证明
①r→s前提引入
② ?s前提引入
③ ?r①②拒取式
④ (p∨q)→r前提引入
⑤ ?(p∨q) ③④拒取式
⑥ ?p∧?q⑤置换
（2）2是素数或合数. 若2是素数，则是无理数. 若是无理数，则4不是素数. 所以，如果4是素数，则2是合数.
解用附加前提证明法构造证明
(1) 设p：2是素数，q：2是合数，
r：是无理数，s：4是素数
(2) 推理的形式结构
前提：p∨q, p→r, r→?s
结论：s→q
(3) 证明
① s附加前提引入
② p→r前提引入
③ r→?s前提引入
④ p→?s②③假言三段论
⑤ ?p①④拒取式
⑥ p∨q前提引入
⑦ q⑤⑥析取三段论
（3）前提：?(p∧q)∨r, r→s, ?s, p
结论：?q
证明用归缪法
① q结论否定引入
② r→s前提引入
③ ?s前提引入
④ ?r②③拒取式
⑤ ?(p∧q)∨r前提引入
⑥ ?(p∧q) ④⑤析取三段论
⑦ ?p∨?q⑥置换
⑧ ?p①⑦析取三段论
⑨ p 前提引入
?p ∧p ⑧⑨合取
（4） (P →（Q∨R))∧(┐S →┐Q)∧(P∧┐S)?R. 证：（1） P∧┐S P
（2） P T （1） I 1 （3） ┐S T （1） I 1 （4） P →（Q∨R) P
（5） Q∨R T (2)，(4) I 11 （6） ┐S →┐Q P
（7） ┐Q T(3)，(6) I 11 （8） R T(5)，(7) I 11
四．求下列公式的前束范式。
解：
五．将下列命题符号化。
(1) 所有的人都长着黑头发；(2)有的人登上过月球；
(3) 没有人登上过木星； (4)在美国留学的学生未必都是亚洲人。
(2) 令G(x)：x 登上过月球。则?x (M(x)∧G(x))。 (3) 令H(x)：x 登上过木星。则
┐?x (M(x)∧H(x))。
)量词分配))(()()(()
量词转换律)(()()()()
()()()()1(x G x F x x G x x F x x G x x F x ?∧????∧????∧?)辖域扩张))(()()()(()辖域扩张))(()()()(()换名)(()()()()量词转换律)(()()()()()()()()
2(y G x F y x y G y x F x y G y x F x x G x x F x x G x x F x ?∨?????∨????∨????∨????∨?解：令M(x)：x 为人。 (1) 令F(x)：x 长着黑头发。则?x (M(x)→ F(x))。
(4) 令F(x)：x 是在美国留学的学生; G(x)：x 是亚洲人。则
┐?x (F(x)→ G(x))。
六．给定解释I 如下：
（a ） 个体域D= {2,3}; （b ） D 中特定元素，a =2; （c ） D 上特定函数f (x) 为：f (2)=3, f (3)=2。 （d ） D 上特定谓词：
G(x,y): G(2,2)=G(2,3)=G(3,2)=1, G(3,3)=0; L(x,y): L(2,2)= L(3,3)=1, L(2,3)= L(3,2) =0; F(x)：F(2)=0, F(3)=1 在I 下求下列各式的真值。 (1) ?x(F(x)∧G(x,a));
(2) ?x(F(f(x)∧G(x,f(x))); (3) ?x ?y L(x,y); (4) ?y ?x L(x,y)
解：设公式（1）为A, 则
?(0∧1)∧(1∧1) ?0
(2) B ?(F(f(2))∧G(2,f(2)))∨(F(f(3))∧G(3,f(3))) ?(F(3)∧G(2,3))∨(F(2)∧G(3,2)) ? (1∧1)∨(0∧1) ? 1
(3) C ? (L(2, 2) ∨L(2,3))∧(L(3,2)∨L(3,3)) ? (1∨0)∧(0∨1) ? 1
(4) D ? (L(2,2) ∧ L(2,3))∨(L(3,2)∧L(3,3)) ? (1∧0)∨(0∧1) ? 0
七．求1到1000之间（包含1和1000在内）既不能被5和6整除，也不能被8整除的数有多少个？ 解：
A ?(F(2)∧G(2,2))∧(F(3)∧G(3,2)) S = { x | x ∈Z ∧1≤x ≤1000 } A = { x | x ∈S ∧x 可被5整除}
B = { x | x ∈S ∧x 可被6整除}
C = { x | x ∈S ∧x 可被8整除} |A| = int(1000/5) = 200
|B| = int(1000/6) = 166 |C| = int(1000/8) = 125 |A∩B| = int(1000/lcm(5,6)) = 33
|A∩C| = int(1000/lcm(5,8)) = 25
八．A={1,2,3,4}, R ={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>},求关系的定义域、值域与域并求 R 的关系矩阵M R 和关系图G R
解：
关系图为
dom R ={1, 2, 4} ran R ={1，2, 3, 4} fld R ={1, 2, 3, 4}
九．设A ={a ,b ,c ,d }, R ={,,,
??
??
?
???????=0010000011000011R M
十．给出A＝{1,2,3}上所有的等价关系
解：先求出A的所有划分：
π1={{1, 2, 3}}; π2={{1}, {2, 3}}；
π3={{2}, {1, 3}}; π4={{3}, {1, 2}};
π5={ {1}, {2}, {3}}。
与这些划分一一对应的等价关系是：
π1: → 全域关系E A
π2: → R2={<2, 3>, <3, 2>}∪I A
π3: → R3={<1, 3>, <3, 1>}∪I A
π4: → R4={<1, 2>, <2, 1>}∪I A
π5: → 恒等关系I A
十一．设偏序集
解A={ a, b, c, d, e, f, g, h }
R={
A
极小元：a, b, c, g；
极大元：a, f, h；
没有最小元与最大元.
B的下界和最大下界都不存在；
上界有d 和f,
最小上界为d.
离散数学试题库——填空题 （每空2分） 1 命题: ? ? {{a }} ? {{a },3,4,1} 的真值 = __ __ . 2. 设A= {a,b}, B = {x | x 2－(a+b) x+ab = 0}, 则两个集合的关系为: __ __. 3. 设集合A ＝{a ,b ,c },B ={a ,b }, 那么 P(B )－P(A )=__ __ . 4. 无孤立点的有限有向图有欧拉路的充分必要条件为: 5.公式))(),(()),()((x S z y R z y x Q x P x →?∨→?的自由变元是 , 约束变元是 . 6.)))()()(()),()(()((x R z Q z y x P y x →?→???的前束范式是 . 7．设 }7|{)},5()(|{<∈=<∈=+ x E x x B x N x x A 且且（N ：自然数集，E + 正偶 数） 则 =?B A 。 8．A ，B ，C 。 9．设P ，Q 的真值为0，R ，S 的真值为1，则 )()))(((S R P R Q P ?∨→?∧→∨?的真值= 。 10．公式P R S R P ?∨∧∨∧)()(的主合取范式为 。 11．若解释I 的论域D 仅包含一个元素，则 )()(x xP x xP ?→? 在I 下真值为 。 12．设A={1，2，3，4}，A 上关系图为 则 R 2 = 。 13．设A={a ，b ，c ，d}，其上偏序关系R 的哈斯图为
则 R= 。 14．图的补图为。15．设A={a，b，c，d} ，A上二元运算如下： 那么代数系统
离散数学试题（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 ＝{，，，，，，，，
离散数学考试试题（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 ) ?0M ∧1M ?2m ∨3m ∨4m ∨5m ∨6m ∨7m 二、（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 上的二元关系，则tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。 若'R 是包含R 的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r (R )?' R 。则sr (R )?s ('R )＝'R ，进而有tsr (R )?t ('R )＝'R 。
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 的面数为( ).
试卷二试题与参考答案 一、填空 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、下面偏序集( )能构成格。
离散数学期末试题及答 案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】
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的补元( ).
离散数学复习注意事项： 1、第一遍复习一定要认真按考试大纲要求将本学期所学习内容系统复习一遍。 2、第二遍复习按照考试大纲的要求对第一遍复习进行总结。把大纲中指定的例题及书后习题认真做一做。检验一下主要内容的掌握情况。 3、第三遍复习把随后发去的练习题认真做一做，检验一下第一遍与第二遍复习情况，要认真理解,注意做题思路与方法。 离散数学综合练习题 一、选择题 1．下列句子中，（）是命题。 A．2是常数。B．这朵花多好看呀！ C．请把门关上！D．下午有会吗？ 2．令p: 今天下雪了，q:路滑，r:他迟到了。则命题“下雪路滑，他迟到了” 可符号化为（）。 A. p q r ∨→ ∧→ B. p q r C. p q r ∨? ∧∧ D. p q r 3．令:p今天下雪了，:q路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（）。 A.p q ∧ ∧? B.p q C.p q →? ∨? D. p q 4．设() Q x:x会飞，命题“有的鸟不会飞”可符号化为（）。 P x:x是鸟，() A. ()(()()) Q x ??∧()) x P x Q x ??→ B. ()(() x P x C. ()(()()) Q x ??∧()) x P x Q x ??→ D. ()(() x P x 5.设() L x y：x大于等于y；命题“所有整数 f x:x的绝对值，(,) P x:x是整数，() 的绝对值大于等于0”可符号化为（）。 A. (()((),0)) ?→ x P x L f x ?∧B. (()((),0)) x P x L f x C. ()((),0) ?→ xP x L f x ?∧ D. ()((),0) xP x L f x 6.设() F x:x是人，() G x:x犯错误，命题“没有不犯错误的人”符号化为（）。 A．(()()) ??→? x F x G x ?∧B．(()()) x F x G x C．(()()) ??∧? x F x G x ??∧D．(()()) x F x G x 7.下列命题公式不是永真式的是（）。 A. () p q p →→ →→ B. () p q p C. () →∨ p q p p q p ?∨→ D. () 8．设() R x:x为有理数；() Q x:x为实数。命题“任何有理数都是实数”的符号化为（）
一．判断题（共10小题，每题1分，共10分） 在各题末尾的括号内画 表示正确，画 表示错误： 1．设p、q为任意命题公式，则(p∧q)∨p ? p ( ) 2．?x(F(y)→G(x)) ? F(y)→?xG(x)。( ) 3．初级回路一定是简单回路。( ) 4．自然映射是双射。( ) 5．对于给定的集合及其上的二元运算，可逆元素的逆元是唯一的。( ) 6．群的运算是可交换的。( ) 7．自然数集关于数的加法和乘法
列为。 19．n阶无向简单连通图G的生成树有条边。 20．7阶圈的点色数是。 三、运算题（共5小题，每小题8分，共40分） 21．求?xF(x)→?yG(x,y)的前束范式。 22．已知无向图G有11条边，2度和3度顶点各两个，其余为4度顶点，求G 的顶点数。 23．设A={a,b,c,d,e,f}，R=I A?{
《离散数学》试卷（A 卷） 一、 选择题（共5 小题，每题 3 分，共15 分） 1、设A={1,2,3},B={2,3,4,5},C={2,3},则C B A ⊕?)(为(C )。 A 、{1,2} B 、{2,3} C 、{1,4,5} D 、{1,2,3} 2、下列语句中哪个是真命题 ( A ) A 、如果1+2=3，则4+5=9； B 、1+2=3当且仅当4+5≠9。 C 、如果1+2=3，则4+5≠9； D 、1+2=3仅当4+5≠9。 3、个体域为整数集合时，下列公式（ C ）不是命题。 A 、)*(y y x y x =?? B 、)4*(=??y x y x C 、)*(x y x x =? D 、)2*(=??y x y x 4、全域关系A E 不具有下列哪个性质（ B ）。 A 、自反性 B 、反自反性 C 、对称性 D 、传递性 5、函数612)(,:+-=→x x f R R f 是（ D ）。 A 、单射函数 B 、满射函数 C 、既不单射也不满射 D 、双射函数 二、填充题（共 5 小题，每题 3 分，共15 分） 1、设|A|=4，|P(B)|=32，|P(A ?B)|=128，则|A ?B|=??2???.
2、公式)(Q P Q ?∨∧的主合取范式为 。 3、对于公式))()((x Q x P x ∨?，其中)(x P ：x=1， )(x Q ：x=2，当论域为{0,1,2}时，其真值为???1???。 4、设A ＝{1,2,3,4}，则A 上共有???15????个等价关系。 5、设A ＝{a ，b ，c }，B={1,2},则|B A |= 8 。 三、判断题（对的填T ，错的填F ，共 10 小题，每题 1 分，共计10 分） 1、“这个语句是真的”是真命题。 （ F ） 2、“张刚和小强是同桌。”是复合命题。 （ F ） 3、))(()(r q q p p ∧?∧→?∨是矛盾式。 （ T ） 4、)(T S R T R S R ??????。 （ F ） 5、恒等关系具有自反性，对称性，反对称性，传递性。 （ T ） 6、若f 、g 分别是单射,则g f ?是单射。 （ T ） 7、若g f ?是满射，则g 是满射。 （ F ） 8、若A B ?，则)()(A P B P ?。 （ T ） 9、若R 具有自反性，则1-R 也具有自反性。 （ T ） 10、B A ∈并且B A ?不可以同时成立。 （F ） 四、计算题（共 3 小题，每题 10 分，共30 分） 1、调查260个大学生，获得如下数据：64人选修数学课程，94人选修计算机课程，58人选修商贸课程，28人同时选修数学课程和商贸课程，26人同时选修数学课程和计算机课程，22人同时选修计算机课程和商贸课程，14人同时选修三门课程。问 （１）三门课程都不选的学生有多少？ （２）只选修计算机课程的学生有多少？
离散数学期末测验试题（有几套带答案1)
————————————————————————————————作者: ————————————————————————————————日期: ?
离散数学试题(A卷及答案） 一、证明题（10分） １)(?P∧(?Q∧Ｒ)）∨(Q∧R）∨(P∧R）?Ｒ 证明：左端?(?P∧?Q∧R)∨（(Q∨Ｐ)∧R)?（(?P∧?Q)∧R))∨((Ｑ∨Ｐ)∧R） ?(?(P∨Q）∧R)∨((Q∨P)∧Ｒ)?(?(P∨Q)∨(Ｑ∨Ｐ))∧R ?(?(P∨Q)∨(Ｐ∨Ｑ))∧R?T∧R(置换）?R 2）?x(Ａ（ｘ)→B(x)）??xＡ(x）→?xB(x) 证明:?x(A(x)→Ｂ(x））??x（?A（x)∨B(x))??x?A(x)∨?xB(x)???xA（x)∨?xB(x)??xA(x)→?xＢ(ｘ） 二、求命题公式(P∨(Q∧Ｒ))→(Ｐ∧Q∧R）的主析取范式和主合取范式(１０分) 证明:(P∨（Ｑ∧Ｒ））→(P∧Q∧R)??(P∨(Ｑ∧Ｒ）)∨（P∧Q∧R)) ?（?P∧（?Q∨?R)）∨(Ｐ∧Q∧Ｒ） ?(?P∧?Ｑ)∨(?P∧?R)）∨(Ｐ∧Q∧R) ?(?P∧?Q∧R)∨(?P∧?Ｑ∧?R）∨(?Ｐ∧Q∧?R)）∨(?P∧?Q∧?R)）∨(Ｐ∧Ｑ∧R) ?m0∨ｍ1∨m2∨ｍ７ ?Ｍ3∨M4∨M5∨M6 三、推理证明题(10分) 1）Ｃ∨D， (C∨D)→?E, ?Ｅ→(A∧?B), (A∧?B)→(R ∨S)?R∨S 证明:(1) (C∨D）→?E (２) ?E→（A∧?Ｂ) ?? (3）（C∨D）→（A∧?Ｂ) （４) （Ａ∧?B)→(R∨Ｓ) ?? (5) （C∨D）→（R∨Ｓ) ? (6) C∨Ｄ?? (7) R∨S 2) ?x(P(ｘ)→Q(ｙ）∧R(x)），?xP(x)?Q(y）∧?x（P(x)∧R(x)) 证明（1)?xP(ｘ) (2）P(a) （3)?ｘ(P(x)→Q(y）∧R(x)) (4）P（a)→Q(y)∧R(a) (５)Q(y)∧Ｒ(a) (6)Q(y) （７)R(a） (8)P(a) (9)P(ａ)∧R(a) （10)?x(Ｐ(x)∧R(ｘ)) (11)Q（ｙ)∧?x(P（x）∧R(x)） 五、已知Ａ、B、C是三个集合,证明A-(B∪C)=(A-B)∩(A-C) （１5分) 证明∵x∈A-（Ｂ∪C)?x∈A∧x?（Ｂ∪C)?x∈A∧(x?Ｂ∧ｘ?C）?(x∈A∧x?B)∧（x∈A∧x?C）?x∈（Ａ-B)∧ｘ∈(A－C）?x∈(A－B）∩（A-Ｃ)∴A-(B∪Ｃ）=（A-B)∩(A-C） 六、已知R、S是N上的关系，其定义如下：Ｒ=｛＜x，ｙ>| x，y∈N∧y=x2｝，Ｓ={
9.给定算式: {[(a ＋b)＊c]＊(d ＋e)}＋[f －(g ＊h)] 此算式的波兰符号表示式为( ), 逆波兰符号表示式为( ). A 、＋＊＊a ＋bc ＋def －g ＊h B 、＋＊＊＋abc ＋de －f ＊gh C 、＊－＊＋abc ＋de －fgh ＋ D 、ab ＋c ＊de ＋＊fgh ＊－＋ 10．设R,Z,N 分别为实数,整数和自然数集，函数f ：R →R ，f(x)＝x ，f 是（ ）; g: Z →N, g(x)＝|x|, g 是( ); h: N →N ×N. h(n)＝﹤n,n ＋1﹥,h({5})＝( ) A ．满射函数 B ．单射函数 C ．双射函数 D ．非单射非满射 E. 满射非单射 F.单射非满射 G ,<5,6> H,{<5,6>} J,以上答案都不对. 11. 75个学生去书店买语文,数学,英语书,每种书每个学生至多买1本.已知20个学生每人 买3本书,55个学生每人至少买2本书.每本书的价格都是1元,所有学生总共花费 140元,恰好买2本书的有( )多少个学生.至少买2本书的学生花费( )元.买 1本书的有( )个学生.至少买1本书的有( )个学生.没买书的有( )个学生. A.55 B.40 C.35 D.15 E.30 F.130 G.65 H.140 J.60 K.10 12. 为每个逻辑断言选择正确的解释。T(x)：x 今天来上课，S(x)：x 学计算机专业的学生， P(x)：x 编程序，G(x)：x 玩游戏。个体域是殷都大学。 ?x T(x)表示（ ），??x T(x)表示（ ），?x ? T(x)表示（ ），?x(S(x)→P(x))表示（ ），?x(S(x)∧G(x))表示（ ），?x(S(x)∧P(x))表示（ ），?x(S(x)→G(x))表示（ ）。 A 学计算机专业的学生会编程序， B 殷都大学的学生都是计算机专业且会编程序。 C 有些计算机专业的学生玩游戏， D 所有同学今天都来上课了， E 今天有同学没来上课。 F 计算机专业的学生玩游戏， G 今天没有同学来上课。 二、计算与应用题（共40分） 1. S={ 1，2，…，10 }，定义S 上的关系R={
填空10% （每小题 2 分） 1、若P，Q，为二命题，P Q 真值为0 当且仅当。 2、命题“对于任意给定的正实数，都存在比它大的实数” 令F（x）：x 为实数，L（x, y） : x y 则命题的逻辑谓词公式为。 3、谓词合式公式xP（x） xQ（x）的前束范式为。 4、将量词辖域中出现的和指导变元交换为另一变元符号，公式其余的部分不变，这种方法称为 换名规则。 5、设x 是谓词合式公式A的一个客体变元，A的论域为D，A（x）关于y 是自由的，则被称为存 在量词消去规则，记为ES。 选择25% （每小题分） 1、下列语句是命题的有（）。 A、明年中秋节的晚上是晴天； C、xy 0 当且仅当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、P Q ； B、P P Q； C、( P Q) (P Q)； D、(P Q) 。 4、下列等价式成立的有（ ）。 A、P QQ P ； B、P(P R) R； C、P (P Q) Q； D 、P (Q R) (P Q) R。 5、若A1,A2 A n和B为 wff ，且A1 A2 A n B 则 （ ）。 A、称A1 A2 A n 为 B 的前 件； B 、称 B 为A1,A2 A n 的有效结论
C 、 x(M (x) Mortal (x)) ； D 、 x(M(x) Mortal (x)) 8、公式 A x(P(x) Q(x))的解释 I 为：个体域 D={2} ，P(x) ：x>3, Q(x) ：x=4则 A 的 真 值为（ ） 。 A 、 1； B 、 0； C 、 可满足式； D 、无法判定。 9、 下列等价关系正确的是（ ）。 A 、 x(P(x) Q(x)) xP(x) xQ(x)； B 、 x(P(x) Q(x)) xP(x) xQ(x)； C 、 x(P(x) Q) xP(x) Q ； D 、 x(P(x) Q) xP(x) Q 。 10 、 下列推理步骤错在（ ）。 ① x(F(x) G(x)) P ② F(y) G(y) US ① ③ xF(x) P ④ F(y) ES ③ ⑤G(y) T ②④I ⑥ xG(x) EG ⑤ A 、②； B 、④； C 、⑤； D 、⑥ 逻辑判断 30% 1、 用等值演算法和真值表法判断公式 A ((P Q) (Q P)) (P Q) 的类型。 C 、当且仅当 A 1 A 2 A n D 、当且仅当 A 1 A 2 A n B F 。 6、 A ，B 为二合式公式，且 B ，则（ ）。 7、 A 、 A C 、 A B 为重言式； B 、 B ； E 、 A B 为重言式。 人总是要死的”谓词公式表示为（ ）。 论域为全总个体域） M （x ） ： x 是人； Mortal(x) x 是要死的。 A 、 M (x) Mortal (x) ； B M (x) Mortal (x)
精品文档院术师范学广东技模拟试题 科目：离散数学 120 分钟考试时间: 考试形式：闭卷 姓名：学号：系别、班级： 2分，共10分）一．填空题（每小题__________。?x?y?P(x)∨Q(y) 1. 谓词公式的前束范式是 __)xxQ(?xP(x)????????____，，2. 设全集A?_{4,5}B =__则A∩ {2}__,,?E?1,2,3,4,55,A?21,,32,B_____ __ {1,3,4,5}??BA????b,c}} __________，则3. 设__ ， b?,c,b,a,A?Ba???B(A)?)(_____Φ_______。???)(AB()?4. 在代数系统（N，+）中，其单位元是0，仅有_1___ 有逆元。 ne条边，则G有___e+2-n____个面。5．如果连通平面图G有个顶点，二．选择题（每小题2分，共10分） P?(Q?R)等价的公式是（1. 与命题公式） （A）（B）（C）（D）R?P?Q)()?R)R?(QPP?(Q?R?Q)(P??????b?b,?a,aA??a,b,cR?,不具备关系( 2. 设集合上的二元关系,A)性质 （A）(A)传递性(B)反对称性(C)对称性(D)自反性 G??V,E?中,结点总度数与边数的关系是3. 在图( ) ??E?Edeg(v)deg(v)?2deg(v)?Evdeg()?2E(A)(C)(B) (D) iiiiVv?Vv?4. 设D是有n个结点的有向完全图,则图D的边数为( ) n(n?1)n(n?1)n(n?1)/2n(n?1)/2(A)(B)(D)(C) 5. 无向图G是欧拉图,当且仅当( ) (A)G的所有结点的度数都是偶数(B)G的所有结点的度数都是奇数 精品文档． 精品文档 (C)G连通且所有结点的度数都是偶数(D) G连通且G的所有结点度数都是奇数。 三．计算题（共43分） p?q?r的主合取范式与主析取范式。（1. 求命题公式6分） 解：主合取方式：p∧q∨r?(p∨q∨r)∧(p∨?q∨r)∧(?p∨q∨r)= ∏0.2.4 主析取范式：p∧q∨r?(p∧q∧r) ∨(p∧q∧?r)∨(?p∧q∧r) ∨(?p∧?q∧r) ∨(p∧?q∧r)=∑1.3.5.6.7 1000????0111?????Md,A?a,b,c,的上的二元关集2. 设合系R关系矩阵为求 ??R0000????1000??)tR(),(RsRr()(),(),(rRsRtR),的关系图。R的关系矩阵，并画出分）10（，
《离散数学》练习题和参考答案 一、选择或填空（数理逻辑部分） 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），（5），（6） 4、公式?x((A(x)→B(y，x))∧?z C(y，z))→D(x)中，自由变元是( )，约束变元是( )。答：x,y, x,z 5、判断下列语句是不是命题。若是，给出命题的真值。( ) 北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。(3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。(5) 前进！ (6) 给我一杯水吧！ 答：（1）是，T （2）是，F （3）不是 （4）是，T （5）不是（6）不是 6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。 答：所有人都不是大学生，有些人不会死 7、设P：我生病，Q：我去学校，则下列命题可符号化为( )。 (1) 只有在生病时，我才不去学校 (2) 若我生病，则我不去学校 (3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校 答：（1） P Q→ ?（2）Q P? →（3）Q P? ?（4）Q P→ ? 8、设个体域为整数集，则下列公式的意义是( )。 (1) ?x?y(x+y=0) (2) ?y?x(x+y=0) 答：（1）对任一整数x存在整数 y满足x+y=0（2）存在整数y对任一整数x满足x+y=0 9、设全体域D是正整数集合，确定下列命题的真值： (1) ?x?y (xy=y) ( ) (2) ?x?y(x+y=y) ( ) (3) ?x?y(x+y=x) ( ) (4) ?x?y(y=2x) ( )答：（1） F （2） F （3）F （4）T 10、设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式?x(P(x)∨Q(x))在哪个个体域中为真?( ) (1) 自然数(2) 实数 (3) 复数(4) (1)--(3)均成立答：（1） 11、命题“2是偶数或-3是负数”的否定是（）。答：2不是偶数且-3不是负数。 12、永真式的否定是（） (1) 永真式(2) 永假式(3) 可满足式(4) (1)--(3)均有可能答：（2） 13、公式(?P∧Q)∨(?P∧?Q)化简为（），公式 Q→(P∨(P∧Q))可化简为（）。答：?P ，Q→P 14、谓词公式?x(P(x)∨?yR(y))→Q(x)中量词?x的辖域是（）。答：P(x)∨?yR(y) 15、令R(x):x是实数，Q(x):x是有理数。则命题“并非每个实数都是有理数”的符号化表示为（）。
一、填空 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 上二元运算如下： 那么代数系统的幺元是 ，有逆元的元素为 ，它们的逆元分别为 。 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上的关系，则下列说法正确的是（） R 是自反的； A．若R，S 是自反的，则S R 是反自反的； B．若R，S 是反自反的，则S R 是对称的； C．若R，S 是对称的，则S R 是传递的。 D．若R，S 是传递的，则S 5、设A={1，2，3，4}，P（A）（A的幂集）上规定二元系如下 t s p R= t s ∈ =则P（A）/ R=（） < > ∧ A ) (| || |} ( , {t , | s 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) =
离散数学试题(Ｂ卷答案１） 一、证明题(10分） 1）(P∧（Ｑ∧Ｒ）)∨(Q∧R）∨（Ｐ∧R)R 证明: 左端(P∧Q∧Ｒ）∨((Q∨P）∧R) ((P∧Q)∧R))∨((Q∨P)∧R) ((Ｐ∨Ｑ）∧R）∨((Ｑ∨P)∧Ｒ) (（P∨Q）∨（Ｑ∨P))∧Ｒ （(P∨Ｑ)∨(Ｐ∨Q))∧R T∧Ｒ(置换)Ｒ 2) x (A(x)B(ｘ）)xA(x)xＢ(ｘ) 证明：x(A(ｘ)B(x))x(Ａ(ｘ)∨B(x)） x A(ｘ)∨xB（ｘ) xA(x)∨xB(x） xＡ(x)xB(x) 二、求命题公式(P∨（Q∧R)）(P∧Q∧R)的主析取范式和主合取范式(10分）。 证明：(P∨（Q∧R))(P∧Q∧R)（P∨(Q∧R)）∨(P∧Q∧R)) (P∧(Q∨Ｒ))∨（P∧Q∧Ｒ） （Ｐ∧Q)∨（P∧R)）∨(P∧Q∧R) (P∧Q∧R)∨(P∧Q∧Ｒ)∨(P∧Q∧Ｒ))∨(P∧Ｑ∧R）)∨(Ｐ∧Q∧R） m0∨ｍ1∨m２∨ｍ７ Ｍ３∨M４∨Ｍ５∨M6 三、推理证明题（１0分) 1）Ｃ∨D，（C∨D)E, E(A∧B)，(A∧Ｂ)(R∨S)R∨Ｓ证明：(１） (C∨D) E ?P (2) E（A∧Ｂ) ??P （3) (Ｃ∨D）（A∧B) Ｔ（1）(2），I (4) （A∧B)(R∨S）??P (5) (Ｃ∨D)(Ｒ∨S) ? T(3)(4)，I (6） C∨Ｄ P (7) R∨S T(5)，I 2) x(P(ｘ)Ｑ(y)∧R(ｘ)），xＰ(ｘ)Q（y)∧x(Ｐ(x)∧R(x)) 证明(1)ｘP(x) Ｐ
（2)Ｐ(ａ） T(1），ＥS (3)ｘ（P(x)Q（y)∧R(x）) Ｐ (４)P(a)Q（y)∧R(a） T(3)，ＵS (５)Q（ｙ)∧R(a） T(2)（4），I （6）Q(y) Ｔ(５)，I （7)R(ａ) T(5),I (8)P(a)∧Ｒ（ａ) T(2)(7),I （9)x(Ｐ(x）∧R(x)) Ｔ(8),ＥG (10)Q(ｙ)∧x(P(x)∧R(ｘ)) Ｔ(６）(9)，I 四、某班有２5名学生,其中14人会打篮球,１2人会打排球，6人会打篮球和排球,5人会打篮球和网球,还有2人会打这三种球。而6个会打网球的人都会打另外一种球,求不会打这三种球的人数(10分)。 解：A，B,C分别表示会打排球、网球和篮球的学生集合。则｜A|=1２，|Ｂ|＝6,｜Ｃ|=14，｜A∩C|=6，｜B∩C｜=5，|Ａ∩Ｂ∩C｜=２。 先求|A∩B|。 ∵6＝|（Ａ∪C)∩B|=|（A∩B）∪（Ｂ∩C)|=|（A∩B）|＋|（B∩C）｜-|A∩B∩C|=|(Ａ∩B)|+5-２，∴|(A∩B）|=３。 于是|A∪Ｂ∪C｜=12+6+14-6-5－３＋２=20。不会打这三种球的人数25-20=5。五、已知Ａ、B、Ｃ是三个集合,证明A-(B∪Ｃ)=(A-B)∩(Ａ-C）(10分)。 证明：∵x A-（B∪C） x A∧x（B∪C） xＡ∧(xＢ∧x C） （x A∧x B）∧(x A∧ｘC） x（A-B）∧x(Ａ-C） ｘ（Ａ-Ｂ）∩(A-C） ∴Ａ-（B∪Ｃ)=（Ａ－B）∩(A－Ｃ） 六、已知R、S是Ｎ上的关系,其定义如下：R={