上海大学 离散数学2 图部分试题
离散数学图论部分综合练习
一、单项选择题
1．设无向图G 的邻接矩阵为
???????
?
???
??
???010
1010010000011100100110
则G 的边数为( )．
A ．6
B ．5
C ．4
D ．3
2．已知图G 的邻接矩阵为
， 则G 有（ ）．
A ．5点，8边
B ．6点，7边
C ．6点，8边
D ．5点，7边
3．设图G ＝
A ．deg(V )=2∣E ∣
B ．deg(V )=∣E ∣
C ．E v V
v 2)deg(=∑∈ D ．E v V
v =∑∈)deg(
4．图G 如图一所示，以下说法正确的是 ( ) ． A ．{(a , d )}是割边 B ．{(a , d )}是边割集 C ．{(d , e )}是边割集 D ．{(a, d ) ,(a, c )}是边割集
5．如图二所示，以下说法正确的是 ( )． A ．e 是割点 B ．{a, e }是点割集 C ．{b , e }是点割集 D ．{d }是点割集
6．如图三所示，以下说法正确的是 ( ) ．
A ．{(a, e )}是割边
B ．{(a, e )}是边割集
C ．{(a, e ) ,(b, c )}是边割集
D ．{(d , e )}是边割集
ο
ο
ο ο ο
c
a b e
d
ο f
图一
图二
图三
7．设有向图（a ）、（b ）、（c ）与（d ）如图四所示，则下列结论成立的是 ( )．
图四
A ．（a ）是强连通的
B ．（b ）是强连通的
C ．（c ）是强连通的
D ．（d ）是强连通的 应该填写：D
8．设完全图K n 有n 个结点(n ≥2)，m 条边，当（ ）时，K n 中存在欧拉回路．
A ．m 为奇数
B ．n 为偶数
C ．n 为奇数
D ．m 为偶数 9．设G 是连通平面图，有v 个结点，e 条边，r 个面，则r = ( )．
A ．e －v ＋2
B ．v ＋e －2
C ．e －v －2
D ．e ＋v ＋2 10．无向图G 存在欧拉通路，当且仅当( )． A ．G 中所有结点的度数全为偶数 B ．G 中至多有两个奇数度结点 C ．G 连通且所有结点的度数全为偶数 D ．G 连通且至多有两个奇数度结点
11．设G 是有n 个结点，m 条边的连通图，必须删去G 的( )条边，才能确定G 的一棵生成树．
A ．1m n -+
B ．m n -
C ．1m n ++
D ．1n m -+ 12．无向简单图G 是棵树，当且仅当( )．
A ．G 连通且边数比结点数少1
B ．G 连通且结点数比边数少1
C ．G 的边数比结点数少1
D ．G 中没有回路．
二、填空题
1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结
点，则G 的边数是 ． 2．设给定图G (如图四所示)，则图G 的点割
ο ο
ο ο
c a b f
集是 ．
3．若图G=
4．无向图G 存在欧拉回路，当且仅当G 连通 且 ．
5．设有向图D 为欧拉图，则图D 中每个结点的入度 ． 应该填写：等于出度
6．设完全图K n 有n 个结点(n 2)，m 条边，当 时，K n 中存在欧拉回路．
7．设G 是连通平面图，v , e , r 分别表示G 的结点数，边数和面数，则v ，e 和r 满足的关系式 ．
8．设连通平面图G 的结点数为5，边数为6，则面数为 ． 9．结点数v 与边数e 满足 关系的无向连通图就是树．
10．设图G 是有6个结点的连通图，结点的总度数为18，则可从G 中删去 条边后使之变成树．
11．已知一棵无向树T 中有8个结点，4度，3度，2度的分支点各一个，T 的树叶数为 ．
12．设G ＝
13．给定一个序列集合{000，001，01，10，0}，若去掉其中的元素 ，则该序列集合构成前缀码．
三、判断说明题
1．如图六所示的图G 存在一条欧拉回路．
2．给定两个图G 1，G 2（如图七所示）：
（1）试判断它们是否为欧拉图、哈密顿图？并说明理由． （2）若是欧拉图，请写出一条欧拉回路．.
v 1
23
图六
图七
3．判别图G (如图八所示)是不是平面图， 并说明理由．
4．设G 是一个有6个结点14条边的连 通图，则G 为平面图．
四、计算题
1．设图G =
（1）试给出G 的图形表示； （2）求G 的邻接矩阵；
（3）判断图G 是强连通图、单侧连通图还是弱连通图？
2．设图G =
（1）画出G 的图形表示； （2）写出其邻接矩阵； （2）求出每个结点的度数； （4）画出图G 的补图的图形． 3．设G =
（1）给出G 的图形表示； （2）写出其邻接矩阵； （3）求出每个结点的度数； （4）画出其补图的图形． 4．图G =
（1）画出G 的图形； （2）写出G 的邻接矩阵；
（3）求出G 权最小的生成树及其权值．
5.用Dijkstra 算法求右图中A 点到其它各点的最短路径。 6．设有一组权为2,3,5,7,11,13,17,19,23,29,31,试
（1）画出相应的最优二元树； （2）计算它们的权值． 7．给出右边所示二元有序树的
三种遍历结果．
v 1
v 2
v 3
v 4
v 5
v 6
ο
ο
ο ο ο v 5
v 1 v 2
v
4
v 6 ο v 3
图八
五、证明题
1．若无向图G 中只有两个奇数度结点，则这两个结点一定是连通的． 2．设G 是一个n 阶无向简单图，n 是大于等于2的奇数．证明图G 与它的补图G 中的奇数度顶点个数相等．
3．设连通图G 有k 个奇数度的结点，证明在图G 中至少要添加2
k
条边才能使其成为欧拉图．
参考解答
一、单项选择题
1．B 2．D 3．C 4．C 5．A 6．D 7．D 8．C 9．A 10．D 11．A 12．A
二、填空题
1．15 2．{f }，{c ，e } 3．W ≤|S| 4．所有结点的度数全为偶数 5．等于出度 6．n 为奇数 7．v -e +r =2 8．3 9．e=v -1 10．4 11．5
12．3 13．0
三、判断说明题
1．解：正确．
因为图G 为连通的，且其中每个顶点的度数为偶数． 2．解：（1）图G 1是欧拉图． 因为图G 1中每个结点的度数都是偶数．
图G 2是汉密尔顿图．
因为图G 2存在一条汉密尔顿回路（不惟一）： a (a , b )b (b , e ) e (e , f ) f (f , g ) g (g , d ) d (d , c ) c (c , a )a
问题：请大家想一想，为什么图G 1不是汉密尔顿图，图G 2不是欧拉图。
（2）图G 1的欧拉回路为：（不惟一）：
v 1(v 1, v 2) v 2 (v 2, v 3) v 3 (v 3, v 4) v 4 (v 4, v 5)v 5 (v 5, v 2) v 2 (v 2, v 6)v 6 (v 6, v 4) v 4 (v 4, v 1)v 1 3．解：图G 是平面图．
因为只要把结点v 2与v 6的连线(v 2, v 6)拽 到结点v 1的外面，把把结点v 3与v 6的连线
ο
ο
ο ο v 1 v 2
v 6 v 3
(v 3, v 6)拽到结点v 4, v 5的外面，就得到一个平 面图，如图九所示．
4．解：错误．
不满足“设G 是一个有v 个结点e 条边的连通简单平面图，若v ≥3，则e ≤3v -6．”
四、计算题
1．解：（1）图G 是有向图： （2）邻接矩阵如下：
,00010
1000000001
01000
00010)(???
???
?
?????????=D A
（3）图G 是单侧连通图，也是弱连通图． 2．解：（1）图G 如图十
（2）邻接矩阵为 图十
?????
???????????0110010110110110110100110
（3）deg(v 1)=2
deg(v 2)=3 deg(v 3)=4 deg(v 4)=3
deg(v 5)=2
（4）补图如图十一
图十一 3．解：（1）G 的图形如图十二
ο ο ο
ο ο a 1
a 2 a 3 a 4 a 5 v 1 v 2 v 3
v 4 v 5
ο ο
ο ο ο v 1 v 2 v 3
v 4 v 5
ο
ο
ο
ο
（2）邻接矩阵： 图十二
?????
???????????0110010110110110110000100 （3）v 1，v 2，v 3，v 4，v 5结点的度数依次为1，2，4，3，2
（4）补图如图十三：
图十三 4．解：（1）G 的图形表示如图十四：
图十四 （2）邻接矩阵：
?????
??
?
???
??
???011
1110110110011100110110
（3）粗线表示最小的生成树，如图十五
如图十五 最小的生成树的权为1+1+2+3=7： 5. 解：注意算法执行过程的数据要完整的表示。 6．解：（1）最优二叉树如图十六所示： 方法（Huffman ）：从2,3,5,7,11,13,17 ,19,23,29,31中选2,3为最低层结点，并 从权数中删去，再添上他们的和数，即 5,5,7,11,13,17,19,23,29,31；
再从5,5,7,11,13,17,19,23,29,31中选 5,5为倒数第2层结点，并从上述数列中
删去，再添上他们的和数，即7,10,11,13, 17,19,23,29,31； 然后，从7,10,11,13,17,19,23,29,31中 选7,10和11,13为倒数第3层结点，并从 如图十六 上述数列中删去，再添上他们的和数，即 17,17,24,19,23,29,31； ……
（2）权值为：2?6+3?6+5?5+7?4+11?4+13?4+17?3+19?3+23?3+29?3+31?2 =12+18+25+28+44+52+51+57+69+87+62=505
7．解：ａ）前根：ａ，ｂ，ｄ，ｇ，ｅ，ｈ，ｉ，ｃ，ｆ
ｂ）中根：ｇ，ｄ，ｂ，ｈ，ｅ，ｉ，ａ，ｃ，ｆ ｃ）后根：ｇ，ｄ，ｈ，ｉ，ｅ，ｂ，ｆ，ｃ，ａ
五、证明题
1．证明：用反证法．设G 中的两个奇数度结点分别为u 和v ．假设u 和v 不连通，即它们之间无任何通路，则G 至少有两个连通分支G 1，G 2，且u 和v 分别属于G 1和G 2，于是G 1和G 2各含有一个奇数度结点．这与定理3.1.2的推论矛盾．因而u 和v 一定是连通的．
2．证明：设,G V E =<>，,G V E '=<>．则E '是由n 阶无向完全图n K 的边
ο ο ο ο ο
ο ο ο ο 3
2 7 1
3 5 5 11 17 3
4 ο
ο 160
29 10 ο ο ο 23 19 42 ο ο 17 ο 24 ο 53
31
ο ο
ο 95
65
删去E 所得到的．所以对于任意结点u V ∈，u 在G 和G 中的度数之和等于u 在
n K 中的度数．由于n 是大于等于2的奇数，从而n K 的每个结点都是偶数度的（ 1 (2)n -≥度），于是若u V ∈在G 中是奇数度结点，则它在G 中也是奇数度结点．故图G 与它的补图G 中的奇数度结点个数相等．
3．证明：由定理3.1.2，任何图中度数为奇数的结点必是偶数，可知k 是偶数．
又根据定理4.1.1的推论，图G 是欧拉图的充分必要条件是图G 不含奇数度结点．因此只要在每对奇数度结点之间各加一条边，使图G 的所有结点的度数变为偶数，成为欧拉图．
故最少要加2
k
条边到图G 才能使其成为欧拉图．
离散数学形考任务1-7试题及答案完整版
2017年11月上交的离散数学形考任务一 本课程的教学内容分为三个单元，其中第三单元的名称是（A ）． 选择一项： A. 数理逻辑 B. 集合论 C. 图论 D. 谓词逻辑 题目2 答案已保存 满分10.00 标记题目 题干 本课程的教学内容按知识点将各种学习资源和学习环节进行了有机组合，其中第2章关系与函数中的第3个知识点的名称是（D ）． 选择一项： A. 函数 B. 关系的概念及其运算 C. 关系的性质与闭包运算 D. 几个重要关系 题目3 答案已保存 满分10.00 标记题目 题干 本课程所有教学内容的电视视频讲解集中在VOD点播版块中，VOD点播版块中共有（B）讲． 选择一项： A. 18 B. 20 C. 19
D. 17 题目4 答案已保存 满分10.00 标记题目 题干 本课程安排了7次形成性考核作业，第3次形成性考核作业的名称是（ C）．选择一项： A. 集合恒等式与等价关系的判定 B. 图论部分书面作业 C. 集合论部分书面作业 D. 网上学习问答 题目5 答案已保存 满分10.00 标记题目 题干 课程学习平台左侧第1个版块名称是：（C）． 选择一项： A. 课程导学 B. 课程公告 C. 课程信息 D. 使用帮助 题目6 答案已保存 满分10.00 标记题目 题干 课程学习平台右侧第5个版块名称是：（D）． 选择一项：
A. 典型例题 B. 视频课堂 C. VOD点播 D. 常见问题 题目7 答案已保存 满分10.00 标记题目 题干 ―教学活动资料‖版块是课程学习平台右侧的第（A）个版块． 选择一项： A. 6 B. 7 C. 8 D. 9 题目8 答案已保存 满分10.00 标记题目 题干 课程学习平台中―课程复习‖版块下，放有本课程历年考试试卷的栏目名称是：（D ）． 选择一项： A. 复习指导 B. 视频 C. 课件 D. 自测 请您按照课程导学与章节导学中安排学习进度、学习目标和学习方法设计自己的学习计划，学习计划应该包括：课程性质和目标（参考教学大纲）、学习内容、考核方式，以及自己的学习安排，字数要求在100—500字．完成后在下列文本框中提交． 解答：学习计划 学习离散数学任务目标：
(完整版)离散数学试卷及答案
离散数学试题（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 。
离散数学试题与答案
试卷二试题与参考答案 一、填空 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，q的小项是（ C ） A．p∧┐p∧q B．┐p∨q C．┐p∧q D．┐p∨p∨q 2．令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（ D ）A．p→┐q B．p∨┐q C．p∧q D．p∧┐q 3．下列语句中是命题的只有（ A ） A．1+1=10 B．x+y=10 C．sinx+siny<0 D．x mod 3=2 4．下列等值式不正确的是（ C ） A．┐(?x)A?(?x)┐A B．(?x)(B→A(x))?B→(?x)A(x) C．(?x)(A(x)∧B(x))?(?x)A(x)∧(?x)B(x) D．(?x)(?y)(A(x)→B(y))?(?x)A(x)→(?y)B(y) 5．谓词公式(?x)P(x,y)∧(?x)(Q(x,z)→(?x)(?y)R(x,y,z)中量词?x的辖域是（ C ） A．(?x)Q(x,z)→(?x)(?y)R(x,y,z)) B．Q(x,z)→(?y)R(x,y,z) C．Q(x,z)→(?x)(?y)R(x,y,z) D．Q(x,z) 6．设A={a,b,c,d}，A上的等价关系R={
离散数学期末试题及答案完整版
离散数学期末试题及答 案 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的补元( ).
2016离散数学练习题 (答案修改)
2016注意事项： 1、第一遍复习一定要认真按考试大纲要求将本学期所学习内容系统复习一遍。 2、第二遍复习按照考试大纲的总结把重点内容再做复习。另外，把大纲中指定的例题及书后习题认真做一做。检验一下主要内容的掌握情况。 3、第三遍复习把随后发去的练习题认真做一做，检验一下复习情况，要认真理解,注意做题思路与方法。 离散数学综合练习题 一、选择题 1．令p : 今天下雪了，q :路滑，r :他迟到了。则命题“下雪路滑，他迟到了” 可符号化为（ A ）。 A. p q r ∧→ B. p q r ∨→ C. p q r ∧∧ D. p q r ∨? 2.设()P x :x 是整数，()f x :x 的绝对值，(,)L x y ：x 大于等于y ；命题“所有整数的绝对值大于等于0”可符号化为（ B ）。 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 ?→ 3.设()F x :x 是人，()G x :x 犯错误，命题“没有不犯错误的人”符号化为（D ）。 A ．(()())x F x G x ?∧ B ． (()())x F x G x ??→? C ．(()())x F x G x ??∧ D ． (()())x F x G x ??∧? *4.下列命题公式不是永真式的是（ A ）。 A . ()p q p →→ B . ()p q p →→ C . ()p q p ?∨→ D . ()p q p →∨ 5．设p ：我们划船，q ：我们跳舞，命题“我们不能既划船又跳舞”符号化正确的是（ B ）。 A. p q ∧ B. ()p q ?∧ C. p q ?∧? D. p q ?∧ 6．设()R x :x 为有理数；()Q x :x 为实数。命题“任何有理数都是实数”的符号化为（ A ） A ．()(()())?→x R x Q x B ．()(()())?∧x R x Q x C ．()(()())x R x Q x ?∧ D ．(()())x R x Q x ?→ 7. 设个体域{,}D a b =，与公式()xA x ?等价的命题公式是( C ) A ．()()A a A b ∧ B ．()()A a A b → C ．()()A a A b ∨ D ．()()A b A a → 8．无向图G 有20条边，4个6度顶点，2个5度顶点，其余均为2度顶点， 则G 一共有（ C ）个顶点。
离散数学期末试卷及答案
一．判断题（共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?{
离散数学练习题
离散数学练习题 1、图中度为零的结点称为孤立结点。 A. 正确 B. 错误 正确：【A】 2、域是整环。 A. 正确 B. 错误 正确：【A】 3、有限格都是有界格。 A. 正确 B. 错误 正确：【A】 4、连通且不含圈的图称为树。 A. 正确 B. 错误 正确：【A】 5、“如果1+1≠3，则2+2≠4”是真命题。 A. 正确 B. 错误 正确：【B】 6、无向图G为欧拉图，则G是连通的。 A. 正确 B. 错误 正确：【A】 7、若A和B都是谓词公式，则(A∧B)、(A∨B)、(A→B)、(A<->B)都是谓词公式。 A. 正确 B. 错误
8、设A, B, C是命题公式，则AVBV﹁C 也是命题公式。 A. 正确 B. 错误 正确：【A】 9、设〈L，≤〉是格，则格的交∧和并∨运算满足等幂律。 A. 正确 B. 错误 正确：【A】 10、“x+3>1。”是命题。 A. 正确 B. 错误 正确：【B】 11、半群满足交换律。 A. 正确 B. 错误 正确：【B】 12、在任何图中，奇数度的结点数必是偶数。 A. 正确 B. 错误 正确：【A】 13、在格〈L，∨，∧〉中，如果交运算对并运算是可分配的，则并运算对交运算也是可分配的。 A. 正确 B. 错误 正确：【A】 14、完全图Kn没有割集，它的连通性能是最好的。 A. 正确 B. 错误
15、对任意集合A，都有??A。 A. 正确 B. 错误 正确：【A】 17、强连通图一定是单向连通图。 A. 正确 B. 错误 正确：【A】 18、代数系统〈G，°〉为群的条件是存在零元素。 A. 正确 B. 错误 正确：【B】 19、对应日常生活中的“任意的”，“所有的”，“一切的”等词，用符号“任意”表示。 A. 正确 B. 错误 正确：【A】 20、如果a是集合A中的元素，则称a属于A，记作a?A。 A. 正确 B. 错误 正确：【B】 21、A,B是集合,P（A），P（B）为其幂集,且,则P(A)∩P(B)为（） A. B. C. D. 正确：【B】 22、设M={x|f1(x)=0},N={x|f2(x)=0}，则方程f1(x)?f2(x)=0的解
离散数学期末试卷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人同时选修三门课程。问 （１）三门课程都不选的学生有多少？ （２）只选修计算机课程的学生有多少？
离散数学试题及解答
离散数学 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）自反性（B）有限性（C）对称性（D）传递性 7、集合A={1,2,…,10}上的关系R={
（C ）弱连通图 （D ）不连通图 9、具有6个顶点，12条边的连通简单平面图中，每个面都是由（ ）条边围成？ （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、公式(?P ∧Q)∨(?P ∧?Q)化简为________。 5、设A ∩B=A ∩C ，A ∩B=A ∩C ，则B________C 。 6、设A={2,4,6}，A 上的二元运算*定义为：a*b=max{a,b}，则在独异点
离散数学试卷及答案
填空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)
离散数学复习题及答案
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 →∧??
离散数学试题及解答
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 ）自反性 （ B ）有限性 （ C ）对称性 （ D ）传递性 7、集合 A={1,2, ?,10}上的关系 R={
离散数学试卷及答案(1)
一、填空 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) =
离散数学期末练习题 (带答案)
离散数学复习注意事项： 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）(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={