电大离散数学本科期末复习题.doc

离散数学（本）
一、单项选择题
1．设P：a是偶数，Q：b是偶数。R：a + b是偶数，则命题“若a是偶数，b是偶数，则a + b 也是偶数”符号化为（D． P Q→R）。
2．表达式x（P（x，y）Q（z））y（Q（x，y）→zQ（z））中x的辖域是（P（x，y） Q（z））。
3．设则命题为假的是（）。
4．设G是有n个结点的无向完全图，则G的边数（ 1/2 n（n-1））。
5．设G是连通平面图，有v个结点，e条边，r个面，则r=（ e-v+2）。
6．若集合A={1，{2}，{1，2}}，则下列表述正确的是( {1}ÌA )．
7．已知一棵无向树T中有8个顶点，4度、3度、2度的分支点各一个，T的树叶数为( 5 )．
8．设无向图G的邻接矩阵为则G的边数为( 7 )．
9．设集合A={a}，则A的幂集为({Æ，{a}} )．
10．下列公式中 (ØAÙØB « Ø(AÚB) )为永真式．
11．若G是一个汉密尔顿图，则G一定是( 连通图 )．
12．集合A={1, 2, 3, 4}上的关系R={|x=y且x, yA}，则R的性质为（传递的 ）．
13．设集合A={1，2，3，4，5}，偏序关系£是A上的整除关系，则偏序集上的元素5是集合A的（极大元 ）．
14．图G如图一所示，以下说法正确的是 ( {(a, d) ,(b d)}是边割集 ) ．图一
15．设A（x）：x是人，B（x）：x是工人，则命题“有人是工人”可符号化为（(x)(A(x)∧B(x)) ）．
16．若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是(AÌB，且AÎB )．
17．设有向图（a）、（b）、（c）与（d）如图一所示，则下列结论成立的是 ( （d）是强连通的 )．

18．设图G的邻接矩阵为则G的边数为( 5 )．
19．无向简单图G是棵树，当且仅当(G连通且边数比结点数少1 )．
20．下列公式 ((P®(ØQ®P))«(ØP®(P®Q)) )为重言式．
21．若集合A＝{ a，{a}{1，2}}，则下列表述正确的是({a}ÍA)．
22．设图G＝，vÎV，则下列结论成立的是 ( ) ．
23．命题公式（P∨Q）→R的析取范式是 (（ØP∧ØQ）∨R )
24．下列等价公式成立的为(P®(ØQ®P) ÛØP®(P®Q) )．
25．设A={a, b}，B={1, 2}，R1，R2，R3是A到B的二元关系，且R1={, }，R2={, , }，R3={, }，则（ R2 ）不是从A到B的函数．
26．设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，B={2, 4, 6}，则集合B的最大元、最小元、上界、下界依次为 (无、2、无、2)．
27．若集合A的元素个数为10，则其幂集的元素个数为（1024）．
28．如图一所示，以下说法正确的是 (e是割点)．图一
29．设完全图K有n个结点(n≥2)，m条边，当（ n为奇数）时，K中存在欧拉回路．
30．已知图G的邻接矩阵为 ，则G有（ 5点，7边 ）．

二、填空题（每小题3分，共15分）
1．设A，B为任意命题公式，C为重言式，若A CBC，那么AB是 重言 式（重言式、矛盾式或可满足式）。
2．命题公式（P→Q）P的主合取范式为 。
3．设集合A={{a}}，则P（A）= 。
4．设图G =〈V，E〉， G ′=〈V′，E′〉，若 V′=V,E′ E ,则G′是G的生成子图。
5．在平面G =〈V，E〉中，则= 2|E| ，其中（i=1，2，…，r）是G的面。6．命题公式的真值是 假（或F，或0） 　．
7．若无向树T有5个结点，则T的边数为 4 ．
8．设正则m叉树的树叶数为t，分支数为i，则(m-1)i= t-1 ．
9．设集合A={1，2}上的关系R＝{<1, 1>,<1, 2>}，则在R中仅需加一个元素 <2, 1> ，就可使新得到的关系为对称的．
10．("x)(A(x)→B(x，z)∨C(y))中的自由变元有 z，y ．
11．若集合A={1，3，5，7}，B={2，4，6，8}，则A∩B=　 空集（或Æ） ．
12．设集合A={1，2，3}上的函数分别为：f={<1,2>,<2,1>,<3,3>,}，g={<1,3>,<2,2>,<3,2>,}，则复合函数g°f = {<1, 2>, <2, 3>, <3, 2>,} ．
13．设G是一个图，结点集合为V，边集合为E，则G的结点度数之和为 2|E|（或“边数的两倍”） ．
14．无向连通图G的结点数为v，边数为e，则G当v与e满足 e=v-1 关系时是树．
15．设个体域D＝{1, 2, 3}， P(x)为“x小于2”，则谓词公式("x)P(x) 的真值为 假（或F，或0） ．
16．命题公式的真值是　 T （或1） 　．
17．若图G=中具有一条汉密尔顿回路，则对于结点集V的每个非空子集S，在G中删除S中的所有结点得到的连通分支数为W，则S中结点数|S|与W满足的关系式为 W£|S| ．
18．给定一个序列集合{000，001，01，10，0}，若去掉其中的元素 0 ，则该序列集合构成前缀码．
19．已知一棵无向树T中有8个结点，4度，3度，2度的分支点各一个，T的树叶数为 5 ．
20．("x)(P(x)→Q(x)∨R(x，y))中的自由变元为 R(x，y )中的y ．
21．设集合A={0, 1, 2, 3}，B={2, 3, 4, 5}，R是A到B的二元关系，则R的有序对集合为　 {<2, 2>，<2, 3>，<3, 2>}，<3, 3>　　．
22．设G是连通平面图，v, e, r分别表示G的结点数，边数和面数，则v，e和r满足的关系式 v-e+r=2 ．
23．设G＝是有6个结点，8条边的连通图，则从G中删去 3 条边，可以确定图G的一棵生成树．
24．无向图G存在欧拉回路，当且仅当G连通且 所有结点的度数全为偶数 ．
25．设个体域D＝{1,2}，则谓词公式消去量词后的等值式为 A(1)ÚA(2) ．
26．设集合A＝{a，b}，那么集合A的幂集是 {Æ,{a,b},{a},{b }} ．
27．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有 2 个．
28．设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去 4 条边后使之变成树．
29．设连通平面图G的结点数为5，边数为6，则面数为 3 ．
30．设个体域D＝{a, b}，则谓词公式("x)A(x)∧（$x）B（x）消去量词后的等值式为 (A (a)∧A (b))∧(B（a）∨B（b）) ．
31. 设集合A={0，1 ，2} ，B={l ，2 ，3 ， 剖，R 是A到B 的二元关系，R= { |x∈A且y∈B且x， y∈A∩B} 则R的有序对集合为___{<1,1>,<1,2>,<2,1>,<2,2>}___
32. 设G是连通平面图，v， e r 分别表示G的结点数， 边数和面数， 则 v， e 和r 满足的关系式__v-e+r=2_____
33.G=是有20个结点，25 条边的连通图,则从G中删去__6__条边，可以确定图G的一棵生成树.
34. 无向图G存在欧拉回路， 当且仅当G所有结点的度数全为偶数且_ 连通____
35. 设个体域D={ 1, 2 } ， 则谓词公式" xA(x)消去量词后的等值式为__A(1)∧A(2)___

三、化简解答题
11．设集合A={1，2，3，4}，A上的二元关系R，R={〈1，1〉，〈1，4〉，〈2，2〉，〈2，3〉，〈3，2〉，〈3，3〉，〈4，1〉，〈4，4〉}，说明R是A上的等价关系。
解 从R的表达式知，即R具有自反性；
三、逻辑公式翻译
1．将语句“今天上课．”翻译成命题公式．
设P：今天上课， 则命题公式为：P．
2．将语句“他去操场锻炼，仅当他有时间．”翻译成命题公式．
设 P：他去操场锻炼，Q：他有时间， 则命题公式为：P ®Q．
3．将语句“他是学生．”翻译成命题公式．
设P：他是学生， 则命题公式为： P．
4．将语句“如果明天不下雨，我们就去郊游．”翻译成命题公式．
设P：明天下雨，Q：我们就去郊游， 则命题公式为：Ø P® Q．
5．将语句“他不去学校．”翻译成命题公式．
设P：他去学校， Ø P．
6．将语句“他去旅游，仅当他有时间．”翻译成命题公式．
设 P：他去旅游，Q：他有时间， P ®Q．
7．将语句“所有的人都学习努力．”翻译成命题公式．
设P(x)：x是人，Q(x)：x学习努力， （"x）(P(x)®Q(x))．
8．将语句“如果你去了，那么他就不去．”翻译成命题公式．
设P：你去，Q：他去， P®ØQ．
9．将语句“小王去旅游，小李也去旅游．”翻译成命题公式．
设P：小王去旅游，Q：小李去旅游， PÙQ．
10．将语句“所有人都去工作．”翻译成谓词公式．
设P(x)：x是人，Q(x)：x去工作， ("x)(P(x)®Q(x))．
11．将语句“如果所有人今天都去参加活动，则明天的会议取消．”翻译成命题公式．
设P：所有人今天都去参加活动，Q：明天的会议取消， P® Q．
12．将语句“今天没有人来．” 翻译成命题公式．
设 P：今天有人来， Ø P．
13．将语句“有人去上课．” 翻译成谓词公式．
设P(x)：x是人，Q(x)：x去上课， ($x)(P(x) ÙQ(x))．
1 1. 将语句"如果小李学习努力，那么他就会取得好成绩. "翻译成命题公式.
设P：小李学习努力，Q:小李会取得好成绩，P→Q
12. 将语句"小张学习努力,小王取得好成绩. "翻译成命题公式.
设P：小张学习努力，Q:小王取得好成绩，P∧Q

四、判断说明题
1．设集合A={1，2}，B={3，4}，从A到B的关系为f={<1, 3>}，则f是A到B的函数．
错误． 因为A中元素2没有B中元素与之对应，故f不是A到B的函数．
2．设G是一个有4个结点10条边的连通图，则G为平面图．
错误． 不满足“设G是一个有v个结点e条边的连通简单平面图，若v≥3，则e≤3v-6．”

3．设N、R分别为自然数集与实数集，f：N→R，f (x)=x+6，则f是单射．
正确． 设x1，x2为自然数且x1¹x2，则有f(x1)= x1+6¹ x2+6= f(x2)，故f为单射．

4．下面的推理是否正确，试予以说明．
(1) （"x）F（x）→G（x） 前提引入
(2) F（y）→G（y） US（1）．
错误．
（2）应为F（y）→G（x），换名时，约束变元与自由变元不能混淆．
5．如图二所示的图G存在一条欧拉回路．

图二

错误． 因为图G为中包含度数为奇数的结点．
6．设G是一个有6个结点14条边的连通图，则G为平面图．
错误． 不满足“设G是一个有v个结点e条边的连通简单平面图，若v≥3，则e≤3v-6．”
7．如果R1和R2是A上的自反关系，则R1∪R2是自反的．
正确． R1和R2是自反的，"x ÎA， Î R1， ÎR2，则 Î R1ÈR2，所以R1∪R2是自反的．
8．如图二所示的图G存在一条欧拉回路．
v1
v2
v3
v5
v4
d
b
a
c
e
f
g
h
n
图二

正确． 因为图G为连通的，且其中每个顶点的度数为偶数．
9．┐P∧（P→┐Q）∨P为永真式．
正确．
┐P∧（P→┐Q）∨P是由┐P∧（P→┐Q）与P组成的析取式，
如果P的值为真，则┐P∧（P→┐Q）∨P为真，
如果P的值为假，则┐P与P→┐Q为真，即┐P∧（P→┐Q）为真，
也即┐P∧（P→┐Q）∨P为真，
所以┐P∧（P→┐Q）∨P是永真式．
另种说明：
┐P∧（P→┐Q）∨P是由┐P∧（P→┐Q）与P组成的析取式，
只要其中一项为真，则整个公式为真．
可以看到，不论P的值为真或为假，┐P∧（P→┐Q）与P总有一个为真，
所以┐P∧（P→┐Q）∨P是永真式．
或用等价演算┐P∧（P→┐Q）∨PÛT
10．若偏序集的哈斯图如图一所示，则集合A的最大元为a，最小元不存在．
图一
正确．
对于集合A的任意元素x，均有ÎR（或xRa），所以a是集合A中的最大元．按照最小元的定义，在集合A中不存在最小元．
11. 如果R1和R2是A上的自反关系， 则R1∩R2是自反的。
正确，R1和R2，是自反的，"x∈A,∈R1,∈R2,则 ∈R1∩R2，所以R1∩R2是自反的.
12. 如图二所示的图中存在一条欧拉回路.
图二

正确，因为图G为连通的，且其中每个顶点的度数为偶数。

五．计算题（每小题12分，本题共36分）
1．试求出（P∨Q）→（R∨Q）的析取范式．
（P∨Q）→（R∨Q）Û ┐(P∨Q)∨（R∨Q）
Û (┐P∧┐Q)∨（R∨Q）
Û (┐P∧┐Q)∨R∨Q（析取范式）

2．设A={{1}, 1, 2}，B={ 1 {2}}，试计算（1）（A∩B） （2）（A∪B） （3）A -（A∩B）．
（1）（A∩B）={1}
（2）（A∪B）={1, 2, {1}, {2}}
（3） A-（A∩B）={{1}, 1, 2}

3．图G=，其中V={ a, b, c, d }，E={ (a, b), (a, c) , (a, d), (b, c), (b, d), (c, d)}，对应边的权值依次为1、2、3、1、4及5，试
（1）画出G的图形；
（2）写出G的邻接矩阵；
图一
o
o
o
o
a
b
c
d
1
1
2
4
5
3
（3）求出G权最小的生成树及其权值．

（1）G的图形表示如图一所示：

图二

o
o
o
o
a
b
c
d
1
1
2
4
5
3
（2）邻接矩阵：

（3）最小的生成树如图二中的粗线所示：

权为：1+1+3=5

4．画一棵带权为1, 2, 2, 3, 4的最优二叉树,计算它们的权．
o
o
o
o
o
o
o
o
o
1
2
2
3
3
4
7
5
12
最优二叉树如图三所示

图三

权为1´3+2´3+2´2+3´2+4´2=27
5．求（P∨Q）→R的析取范式与合取范式．
（P∨Q）→R Û Ø（P∨Q）∨R
Û (ØP∧ØQ)∨R （析取范式）
Û (ØP∨R)∧(ØQ∨R) （合取范式）
6．设A={0，1，2，3}，R={|xÎA，yÎA且x+y<0}，S={|xÎA，yÎA且x+y£2}，试求R，S，R·S，S -1，r(R)．
R=Æ, S={<0,0>,<0,1>,<0,2>,<1,0>,<1,1>,<2,0>}
R·S=Æ，
S -1= S，
r(R)=IA={<0,0>,<1,1>,<2,2>,<3,3>}．
7．试求出（P∨Q）→R的析取范式，合取范式，主合取范式．
（P∨Q）→RÛ┐(P∨Q)∨RÛ (┐P∧┐Q)∨R（析取范式）
Û (┐P∨R)∧ (┐Q∨R)（合取范式）
Û ((┐P∨R)∨(Q∧┐Q))∧ ((┐Q∨R)∨(P∧┐P))
Û (┐P∨R∨Q)∧(┐P∨R∨┐Q)∧ (┐Q∨R∨P)
∧(┐Q∨R∨┐P)
Û (┐P∨Q∨R)∧(┐P∨┐Q∨R)∧ (P∨┐Q∨R)
8．设A={{a, b}, 1, 2}，B={ a, b, {1}, 1}，试计算
（1）（A-B） （2）（A∪B） （3）（A∪B）-（A∩B）．

（1）（A-B）={{a, b}, 2}
（2）（A∪B）={{a, b}, 1, 2, a, b, {1}}
（3）（A∪B）-（A∩B）={{a, b}, 2, a, b, {1}}
9．图G=，其中V={ a, b, c, d, e}，E={ (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (c, d), (d, e) }，对应边的权值依次为2、1、2、3、6、1、4及5，试
（1）画出G的图形；
（2）写出G的邻接矩阵；
（3）求出G权最小的生成树及其权值．
（1）G的图形表示为：

（2）邻接矩阵：

（3）粗线表示最小的生成树，

权为7：
10．设谓词公式，试（1）写出量词的辖域； （2）指出该公式的自由变元和约束变元．
（1）$x量词的辖域为，
"z量词的辖域为,
"y量词的辖域为．
（2）自由变元为与中的y，以及中的z
约束变元为x与中的z，以及中的y．
11．设A={{1},{2},1,2}，B={1,2,{1,2}}，试计算
（1）（A-B）； （2）（A∩B）； （3）A×B．
（1）A-B ={{1},{2}}
（2）A∩B ={1,2}
（3）A×B={<{1},1>，<{1},2>，<{1},{1,2}>，<{2},1>，<{2},2>，
<{2},{1,2}>，<1,1>，<1,2>，<1, {1,2}>，<2,1>，<2,2>,
<2, {1,2}>}

12．设G=，V={ v1，v2，v3，v4，v5}，E={ (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) }，试
（1）给出G的图形表示； （2）写出其邻接矩阵；
（3）求出每个结点的度数； （4）画出其补图的图形．

（1）G的图形表示为：

（2）邻接矩阵：

（3）v1，v2，v3，v4，v5结点的度数依次为1，2，4，3，2
（4）补图如下：

13．设集合A={1，2，3，4}，R={|x, yÎA；|x-y|=1或x-y=0}，试
（1）写出R的有序对表示；
（2）画出R的关系图；
（3）说明R满足自反性，不满足传递性．

（1）R={<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<2,1>,<2,3>,<3,2>,<3,4>,<4,3>}
°
°
°
°
1
2
3
4
（2）关系图为

3）因为<1,1>,<2,2>,<3,3>,<4,4>均属于R，即A的每个元素构成的有序对均在R中，故R在A上是自反的。
因有<2,3>与<3,4>属于R，但<2,4>不属于R，所以R在A上不是传递的。

14．求P®QÚR的析取范式，合取范式、主析取范式，主合取范式．
P→（R∨Q）
Û┐P∨(R∨Q)
Û ┐P∨Q∨R （析取、合取、主合取范式）
Û(┐P∧┐Q∧┐R)∨(┐P∧┐Q∧R) ∨(┐P∧Q∧R) ∨(P∧┐Q∧┐R)
∨(P∧┐Q∧R) ∨(P∧Q∧┐R) ∨(P∧Q∧R) （主析取范式）
15．设图G=，V={ v1，v2，v3，v4，v5}，E={ (v1, v2)，(v1, v3)，(v2, v3)，(v2, v4)，(v3, v4)，(v3, v5)，(v4, v5) }，试
(1) 画出G的图形表示；
(2) 写出其邻接矩阵；
(3) 求出每个结点的度数；
v1
v2
v3
v4
v5
o
o
o
o
o
(4) 画出图G的补图的图形．

（1）关系图

（2）邻接矩阵
（3）deg(v1)=2
deg(v2)=3
deg(v3)=4
deg(v4)=3
v1
v2
v3
v4
v5
o
o
o
o
o
deg(v5)=2
（4）补图

16．设谓词公式$x(A(x,y)∧" zB(x,y, z)) ∧" yC(y,z) 试
(1)写出量词的辖域;
$x量词的辖域为(A(x,y)∧" zB(x,y, z)), " z量词的辖域为B(x,y,z), " y量词的辖域为C(y,z)
(2)指出该公式的自由变元和约束变元.
自由变元为(A(x,y) ∧" zB(x,y, z))中的y,以及C(y,z)中的z.
约束变元为(A(x,y) ∧" zB(x,y, z))中的x与B(x,y,z)中的z,以及C(y,z)中的y。
六、证明题
1．试证明：若R与S是集合A上的自反关系，则R∩S也是集合A上的自反关系．
证明：设"xÎA，因为R自反，所以x R x，即< x, x>ÎR；
又因为S自反，所以x R x，即< x, x >ÎS．
即< x, x>ÎR∩S
故R∩S自反．
2．试证明集合等式AÈ (BÇC)=(AÈB) Ç (AÈC) ．
证明：设S= AÈ (BÇC)，T=(AÈB) Ç (AÈC)，若x∈S，则x∈A或x∈BÇC，即 x∈A或x∈B 且 x∈A或x∈C．
也即x∈AÈB 且 x∈AÈC ，即 x∈T，所以SÍT．
反之，若x∈T，则x∈AÈB 且 x∈AÈC， 即x∈A或x∈B 且 x∈A或x∈C，
也即x∈A或x∈BÇC，即x∈S，所以TÍS．
因此T=S．
3．试证明集合等式AÇ (BÈC)=(AÇB) È (AÇC)．
证明：设S=A∩(B∪C)，T=(A∩B)∪(A∩C)， 若x∈S，则x∈A且x∈B∪C，即 x∈A且x∈B 或 x∈A且x∈C，
也即x∈A∩B 或 x∈A∩C ，即 x∈T，所以SÍT．
反之，若x∈T，则x∈A∩B 或 x∈A∩C，
即x∈A且x∈B 或 x∈A且x∈C
也即x∈A且x∈B∪C，即x∈S，所以TÍS．
因此T=S．
4．试证明集合等式AÈ (BÇC)=(AÈB) Ç (AÈC) ．
证明：设S= AÈ (BÇC)，T=(AÈB) Ç (AÈC)，若x∈S，则x∈A或x∈BÇC，即 x∈A或x∈B 且 x∈A或x∈C．
也即x∈AÈB 且 x∈AÈC ，即 x∈T，所以SÍT．
反之，若x∈T，则x∈AÈB 且 x∈AÈC，
即x∈A或x∈B 且 x∈A或x∈C，
也即x∈A或x∈BÇC，即x∈S，所以TÍS．
因此T=S．
5．试证明（$x）（P（x）∧R（x））Þ （$x）P（x）∧（$x）R（x）．
证明：
（1）（$x）（P（x）∧R（x）） P
（2）P（a）∧R（a） ES(1)
（3）P（a） T(2)I
（4）（$x）P（x） EG(3)
（5）R（a） T(2)I
（6）（$x）Rx） EG(5)
（7）（$x）P（x）∧（$x）R（x） T(5)(6)I
6．设m是一个取定的正整数，证明：在任取m＋1个整数中，至少有两个整数，它们的差是m的整数倍
证明 设，，…，为任取的m＋1个整数，用m去除它们所得余数只能是0，1，…，m－1，由抽屉原理可知，，，…，这m＋1个整数中至少存在两个数和，它们被m除所得余数相同，因此和的差是m的整数倍。
7．已知A、B、C是三个集合，证明A-(B∪C)=(A-B)∩(A-C)

证明 ∵xÎ A-（B∪C）Û xÎ A∧xÏ（B∪C）Û xÎ A∧（xÏB∧xÏC）Û （xÎ A∧xÏB）∧（xÎ A∧xÏC）Û xÎ（A-B）∧xÎ（A-C）Û xÎ（A-B）∩（A-C）∴A-（B∪C）=（A-B）∩（A-C）
8．（15分）设是半群，对A中任意元a和b，如a≠b必有a*b≠b*a，证明：
(1)对A中每个元a，有a*a＝a。 (2)对A中任意元a和b，有a*b*a＝a。 (3)对A中任意元a、b和c，有a*b*c＝a*c。
证明 由题意可知，若a*b＝b*a，则必有a＝b。
(1)由(a*a)*a＝a*(a*a)，所以a*a＝a。

(2)由a*(a*b*a)＝(a*a)*(b*a)＝a*b*(a*a)＝(a*b*a)*a，所以有a*b*a＝a。
(3)由(a*c)*(a*b*c)＝(a*c*a)*(b*c)＝a*(b*c)＝(a*b)*c＝(a*b)*(c*a*c)＝(a*b*c)*(a*c)，所以有a*b*c＝a*c。
13. 设A,B为任意集合，证明：(A-B)-C = A-(B∪C).
证明：(A-B)-C = (A∩~B)∩~C
= A∩(~B∩~C)
= A∩~(B∪C)
= A-(B∪C)
9．求命题公式(ØP®Q)®(P∨ØQ) 的主析取范式和主合取范式
解：(ØP®Q)®(P∨ØQ)ÛØ(ØP®Q)∨(P∨ØQ)ÛØ(P∨Q)∨(P∨ØQ)Û(ØP∧ØQ)∨(P∨ØQ) Û(ØP∨P∨ØQ)∧(ØQ∨P∨ØQ)Û(P∨ØQ)ÛM1Ûm0∨m2∨m3
10．例5在边长为1的正方形内任意放置九个点，证明其中必存在三个点，使得由它们组成的三角形（可能是退化的）面积不超过1/8。
证明：把边长为1的正方形分成四个全等的小正方形，则至少有一个小正方形内有三个点，它们组成的三角形（可能是退化的）面积不超过小正方形的一半，即1/8。
11. 试证明集合等式AU( B∩C)=(AUB) ∩(AUC).
证明：设S=AU(B∩C),T=(AUB) ∩(AUC),若x∈S,则x∈A或x∈B∩C，
即x∈A或x∈B且x∈A或x∈C,也即x∈AUB且x∈AUC,
即x∈T,所以sÍT.
反之，若x∈T,则x∈AUB且x∈AUC,
即x∈A或x∈B且x∈A或x∈C,
也即x∈A或x∈B∩C，即x∈S,所以TÍS.
因此T=S.
12. 利用形式演绎法证明：{P→Q, R→S, P∨R}蕴涵Q∨S。
证明：{P→Q, R→S, P∨R}蕴涵Q∨S
(1) P∨R P
(2) ØR→P Q(1)
(3) P→Q P
(4) ØR→Q Q(2)(3)
(5) ØQ→R Q(4)
(6) R→S P
(7) ØQ→S Q(5)(6)
(8) Q∨S Q(7)
14.利用形式演绎法证明：{ØA∨B, ØC→ØB, C→D}蕴涵A→D。
证明：{ØA∨B, ØC→ØB, C→D}蕴涵A→D
(1) A D(附加)
(2) ØA∨B P
(3) B Q(1)(2)
(4) ØC→ØB P
(5) B→C Q(4)
(6) C Q(3)(5)
(7) C→D P
(8) D Q(6)(7)
(9) A→D D(1)(8)
所以 {ØA∨B, ØC→ØB, C→D}蕴涵A→D.
15. A, B为两个任意集合，求证：A－(A∩B) = (A∪B)－B .
证明：A－(A∩B)
= A∩~(A∩B)
＝A∩(~A∪~B)
＝(A∩~A)∪(A∩~B)
＝Æ∪(A∩~B)
＝(A∩~B)
＝A－B
而 (A∪B)－B
= (A∪B)∩~B
= (A∩~B)∪(B∩~B)
= (A∩~B)∪Æ
= A－B 所以：A－(A∩B) = (A∪B)－B.