离散数学形考任务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 ＝{a,{a},{1,2}}A ＝{a,{a},{1,2}}，则下列表述正确的是( C ) ．
选择一项：
A. {a,{a}∈A {a,{a}∈A
B. {1，2}∉A {1，2}∉A
C. {a}⊆A {a}⊆A
D. ∅∈A ∅∈A
题目2
答案已保存
满分10.00
标记题目
题干
设集合A={1, 2, 3}，B={3, 4, 5}，C={5, 6, 7}，则A ∪B –C =( A ) ．
选择一项：
A. {1, 2, 3, 4}
B. {1, 2, 3, 5}
C. {2, 3, 4, 5}
D. {4, 5, 6, 7}
题目3
答案已保存
满分10.00
标记题目
题干
设集合A = {1,a a}，则P (A ) = ( D )．
选择一项：
A. {{1}, {a a}}
B. {Ø,{1}, {a a}}
C. {{1},{a},{1,a}}{{1},{a},{1,a}}
D. Ø,{1},{a},{1,a}}Ø,{1},{a},{1,a}}
题目4
答案已保存
满分10.00
标记题目
题干
集合A={1, 2, 3, 4, 5, 6, 7, 8}上的关系R={|x+y=10且x, y∈A}，则R 的性质为（ B ）．
选择一项：
A. 自反的
B. 对称的
C. 传递且对称的
D. 反自反且传递的
题目5
答案已保存
满分10.00
标记题目
题干
如果R 1和R 2是A 上的自反关系，则R 1∪R 2，R 1∩R 2，R 1-R 2中自反关系有（ B ）个
选择一项：
A. 0
B. 2
C. 1
D. 3
题目6
答案已保存
满分10.00
标记题目
题干
设A={1, 2, 3, 4, 5, 6, 7, 8}，R 是A 上的整除关系，B={2, 4, 6}，则集合B 的最大元、最小元、上界、下界依次为 ( D )．
选择一项：
A. 8、2、8、2
B. 8、1、6、1
C. 6、2、6、2
D. 无、2、无、2
题目7
答案已保存
满分10.00
标记题目
题干
设集合A={2, 4, 6, 8}，B={1, 3, 5, 7｝，A 到B 的关系R={| y = x +1｝，则R= ( A )．
选择一项：
A. {, , }
B. {, , }
C. {, , }
D. {, , }
题目8
答案已保存
满分10.00
标记题目
题干
设集合A ={1 , 2, 3}上的函数分别为：ƒ= {，，}，g = {，，}，h = {，，}，
则h =（ A ）．
选择一项：
A. ƒ◦g
B. g◦ƒ
C. ƒ◦ƒ
D. g◦g
题目9
答案已保存
满分10.00
标记题目
题干
设A 、B 是两个任意集合，侧A-B = ØØ ⇔( B ) ．
选择一项：
A. A = B B. A ⊆ B
C. A ⊇ B
D. B =ØØ
题目10
答案已保存
满分10.00
标记题目
题干
设集合A ={1，2，3，4，5}，偏序关系£是A 上的整除关系，则偏序集上的元素5是集合A 的（ C ）．
选择一项： A. 最大元
B. 最小元
C. 极大元
D. 极小元
离散数学作业3
离散数学集合论部分形成性考核书面作业
一、填空题
1．设集合A ={1, 2, 3},B ={1, 2}，则P (A ) -P (B ，A ⨯B
2．设集合A 有10个元素，那么A 的幂集合P (A ) 的元素个数为
3．设集合A ={0, 1, 2, 3}，B ={2, 3, 4, 5}，R 是A 到B 的二元关系，
R ={x ∈A 且y ∈B 且x , y ∈A ⋂B }
则R 的有序对集合为{，，}，．
4．设集合A ={1, 2, 3, 4 }，B ={6, 8, 12}，A 到B 的二元关系
R ＝{y =2x , x ∈A , y ∈B }
那么R 1＝{,} －
5．设集合A =｛a , b , c , d ｝，A 上的二元关系R ={, , , }，则R 具有的性质是 没有任何性质 ．
6．设集合A =｛a , b , c , d ｝，A 上的二元关系R ={, , , }，若在R 中再增加两个元素 {,} ，则新得到的关系就具有对称性．
7．如果R 1和R 2是A 上的自反关系，则R 1∪R 2，R 1∩R 2，R 1-R 2中自反关系有 2 个．
8．设A ={1,2}上的二元关系为R ={|x ∈A ，y ∈A , x +y =10}，则R 的自反闭包为 {,} ．
9．设R 是集合A 上的等价关系，且1 , 2 , 3是A 中的元素，则R 中至少包含等元素．
10．设集合A ={1, 2}，B ={a , b }，那么集合A 到B 的双射函数是或{, }．
二、判断说明题（判断下列各题，并说明理由．）
1．若集合A = {1，2，3}上的二元关系R ={，，}，则
(1) R 是自反的关系； (2) R 是对称的关系．
解：（1）错误。R 不具有自反的关系，因为不属于R 。
（2）错误。R 不具有对称的关系，因为不属于R 。
2．如果R 1和R 2是A 上的自反关系，判断结论：“R -11、R 1∪R 2、R 1∩R 2是自反的”是否成立？并说明理由．
解：成立．
因为R 1和R 2是A 上的自反关系，即I A ⊆R 1，I A ⊆R 2。
由逆关系定义和I A ⊆R 1，得I A ⊆ R1-1；
由I A ⊆R 1，I A ⊆R 2，得I A ⊆ R1∪R 2，I A ⊆ R1⋂R 2。
所以，R 1-1、R 1∪R 2、R 1⋂R 2是自反的。
3．若偏序集的哈斯图如图一所示， a b d
e f
图一 ο c ο g 则集合A 的最大元为a ，最小元不存在． 解：错误． 集合A 的最大元不存在，a 是极大元． h
A →B ， 4．设集合A ={1,2,3,4}，B ={2, 4, 6, 8}，，判断下列关系f 是否构成函数f ：
并说明理由．
(1) f ={,,,}； (2)f ={,,}；
(3) f ={,,,}．
解：
（1）不构成函数。因为对于3属于A ，在B 中没有元素与之对应。
（2）不构成函数。因为对于4属于A ，在B 中没有元素与之对应。
（3）构成函数。因为A 中任意一个元素都有A 中唯一的元素相对应。
三、计算题
1．设E ={1, 2, 3, 4, 5},A ={1, 4},B ={1, 2, 5},C ={2, 4}，求：
(1) (A ⋂B ) ⋃~C ； (2) (A ⋃B ) -(B ⋂A ) (3) P (A ) －P (C ) ； (4) A ⊕B ．
解：(1) (A∩B) ∪~C={1}∪{1,3,5}={1,3,5}
(2) (A∪B)- (B∩A)={1,2,4,5}-{1}={2,4,5}
(3) P(A) ={Φ,{1},{4},{1,4}} P(C)={ Φ,{2},{4},{2,4}}
P(A)－P(C)={{1},{1,4}}
(4) A⊕B= (A∪B)- (B∩A)= {2,4,5}
2．设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={，，，，， ，，，，，,}
3．设A ={1，2，3，4，5}，R ={|x ∈A ，y ∈A 且x +y ≤4}，S ={|x ∈A ，y ∈A 且x +y
解：R={,,}
S=空集 R*S=空集 S*R=空集
R -1={,}
S -1 =空集
r(S)={}
s(R)={}
4．设A ={1,2,3,4,5,6,7,8}，R 是A 上的整除关系，B ={2,4, 6}．
(1) 写出关系R 的表示式； (2 )画出关系R 的哈斯图；
(3) 求出集合B 的最大元、最小元．
解：
(1)R={}
(3)集合B 没有最大元，最小元是2
(2)关系R 的唯斯图
11 关系R 的哈斯图
四、证明题
1．试证明集合等式：A ⋃ (B ⋂C )=(A ⋃B ) ⋂ (A ⋃C ) ．
证明：设，若x ∈A ⋃ (B⋂C) ，则x ∈A 或x ∈B ⋂C ，
即 x ∈A 或x ∈B 且 x ∈A 或x ∈C ．
即x ∈A ⋃B 且 x ∈A ⋃C ，
即 x ∈T=(A⋃B) ⋂ (A⋃C) ，
所以A ⋃ (B⋂C) ⊆ (A⋃B) ⋂ (A⋃C) ．
反之，若x ∈(A⋃B) ⋂ (A⋃C) ，则x ∈A ⋃B 且 x ∈A ⋃C ，
即x ∈A 或x ∈B 且 x ∈A 或x ∈C ，
即x ∈A 或x ∈B ⋂C ，
即x ∈A ⋃ (B⋂C) ，
所以(A⋃B) ⋂ (A⋃C) ⊆ A⋃ (B⋂C) ．
因此．A ⋃ (B⋂C)=(A⋃B) ⋂ (A⋃C) ．
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 ，且A ≠∅，则B = C ．
证明：
（1） 对于任意∈A ×B ，其中a ∈A ，b ∈B, 因为A ×B= A×C ，
必有∈A ×C, 其中b ∈C 因此B ⊆C
（2）同理，对于任意∈A ×C, 其中，a ∈A ，c ∈C ，因为A ×B= A×C 必有∈A ×B ，其中c ∈B ，因此C ⊆B 有（1）（2）得B=C
4．试证明：若R 与S 是集合A 上的自反关系，则R ∩S 也是集合A 上的自反关系． 证明：
若R 与S 是集合A 上的自反关系，则任意x ∈A, ＜x,x ＞∈R, ＜x,x ＞∈S,
从而＜x,x ＞∈R∩S,注意x 是A 的任意元素，所以R∩S也是集合A 上的自反关系．
离散数学形考任务四
设无向图 G 的邻接矩阵为
选择一项：
A. 6
B. 5
C. 4
D. 3
题目2
答案已保存
满分10.00 ，则 G 的边数为( B ) ．
标记题目
题干
如图一所示，以下说法正确的是 ( D ) ．
选择一项：
A. {(a,e a,e)}是割边
B. {(a,e a,e)}是边割集
C. {(a,e),(b,c)(a,e),(b,c)}是边割集
D. {(d,e d,e)}是边割集
题目3
答案已保存
满分10.00
标记题目 题干
如图三所示，以下说法正确的是 ( C ) ．
选择一项：
A. {(a,d a,d)}是割边
B. {(a,d a,d)}是边割集
C. {(a,d),(b,d)(a,d),(b,d)}是边割集
D. {(b,d b,d)}是边割集
题目4
答案已保存
满分10.00
标记题目
题干
无向图G 存在欧拉回路，当且仅当（ C ）.
选择一项：
A. G中所有结点的度数全为偶数
B. G中至多有两个奇数度结点
C. G连通且所有结点的度数全为偶数
D. G连通且至多有两个奇数度结点
题目5
答案已保存
满分10.00
标记题目
题干
若G 是一个欧拉图，则G 一定是( C ) ．
选择一项：
A. 平面图
B. 汉密尔顿图
C. 连通图
D. 对偶图
题目6
答案已保存
满分10.00
标记题目
题干
无向树T 有8个结点，则T 的边数为( B )．
选择一项：
A. 6
B. 7
C. 8
D. 9
题目7
答案已保存
满分10.00标记题目
题干
已知一棵无向树T 中有8个顶点，4度、3度、2度的分支点各一个，T 的树叶数为( A ) ． 选择一项：
A. 5
B. 8
C. 3
D. 4
题目8 答案已保存
满分10.00
标记题目
题干
设无向图 G 的邻接矩阵为
选择一项：
A. 1
B. 6
C. 7
D. 14
题目9
答案已保存
满分10.00 ，则 G 的边数为( C ) ．
标记题目
题干
设有向图（a ）、（b ）、（c ）与（d ）如图所示，则下列结论成立的是
( D )．
选择一项：
A. （a ）只是弱连通的
B. （b ）只是弱连通的
C. （c ）只是弱连通的
D. （d ）只是弱连通的
题目10
答案已保存
满分10.00
标记题目
题干
以下结论正确的是( D ) ．
选择一项：
A. 无向完全图都是欧拉图
B. 有n 个结点n －1条边的无向图都是树
C. 无向完全图都是平面图
D. 树的每条边都是割边
离散数学作业5
离散数学图论部分形成性考核书面作业
本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业。
要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求2010年12月5日前完成并上交任课教师（不收电子稿）。并在05任务界面下方点击“保存”和“交卷”按钮，以便教师评分。
一、填空题
1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G 的边数是15．
2．设给定图G (如右由图所示) ，则图G 的点割集是
{f }{e , c }．
3．设G 是一个图，结点集合为V ，边集合为E ，则
G
4．无向图G 存在欧拉回路，当且仅当G
5．设G=
E >是具有n 个结点的简单图，若在G 中每一对结点度数之和大于等于︱V ︱，则在G 中存在一条汉密尔顿回路．
6．若图G=中具有一条汉密尔顿回路，则对于结点集V 的每个非空子集S ，在G 中删除S 中的所有结点得到的连通分支数为W ，则S 中结点数|S|与W 满足
的关系式为W ≤S ．
7．设完全图K n 有n 个结点(n ≥2) ，m 条边，当n 为奇数时，K n 中存在欧拉回路．
8．结点数v 与边数e 满足
9．设图G 是有6个结点的连通图，结点的总度数为18，则可从G 中删去 条边后使之变成树．
10．设正则5叉树的树叶数为17，则分支数为i
二、判断说明题（判断下列各题，并说明理由．）
1．如果图G 是无向图，且其结点度数均为偶数，则图G 存在一条欧拉回路．． 答：错误。应叙述为：“如果图G 是无向连通图，且其结点度数均为偶数，则图G 存在一条欧拉回路。”
2．如下图所示的图G 存在一条欧拉回路．
答：错误。因为图中存在奇数度结点，所以不存在欧拉回路。
3．如下图所示的图G 不是欧拉图而是汉密尔顿图．
G
答：正确。因为有4个结点的度数为奇数，所以不是欧拉图；而对于图中任意点集V 中的非空子集V 1，都有P (G -V 1) ≤∣V 1∣。其中P (G -V 1) 是从图中删除V 1结点及其关联的边。
4．设G 是一个有7个结点16条边的连通图，则G 为平面图．
答：错误。若G 是连通平面图，那么若v ≥3, 就有e ≤3v -6，
而16>3×7－6，所以不满足定理条件，叙述错误。
5．设G 是一个连通平面图，且有6个结点11条边，则G 有7个面． 答：正确。因为连通平面图满足欧拉公式。即：v -e +r =2。由此题条件知6-11+7=2成立。
三、计算题
1．设G =，V ={ v 1，v 2，v 3，v 4，v 5}，E ={ (v 1, v 3) ，(v 2, v 3) ，(v 2, v 4) ，(v 3, v 4) ，(v 3, v 5) ，(v 4, v 5) }，试
(1) 给出G 的图形表示； (2) 写出其邻接矩阵；
(3) 求出每个结点的度数； (4) 画出其补图的图形．
答：（1） v 1
v 2
v 45
⎡0⎢0⎢（2）A (D ) =⎢1⎢⎢0
⎢⎣00100⎤0110⎥⎥1011⎥ ⎥1101⎥0110⎥⎦
（3）deg(v 1) =1、deg(v 2) =2、deg(v 3) =4、deg(v 4) =3、deg(v 5) =2
（4）°v 1
v 2
v 4°°v 5
2．图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 权最小的生成树及其权值．
b c
解：（1） 。。
2 1
。 。
e 5 d
⎡0⎢1⎢（2）A (D ) =⎢1⎢⎢0
⎢⎣11101⎤0011⎥⎥0011⎥ ⎥1101⎥1110⎥⎦
（3）
b 。
2
a 。
e 。3
3．已知带权图G 如右图所示．
(1) 求图G 的最小生成树； (2)计算该生成树的权值．
答：(1)
1 2
7
5 3
(2) 权值为18。
4．设有一组权为2,3,5,7,17,31，试画出相应的最优二叉树，计算该最优二叉树的权．
解： 65
17 48
5 1217 31
2 3 5 7
权值为65。
四、证明题
1．设G 是一个n 阶无向简单图，n 是大于等于3的奇数．证明图G 与它的补图其权值为：7
G 中的奇数度顶点个数相等．
证明：设a 为G 中任意一个奇数度顶点，由定义，a 仍为顶点，为区分起见，记为a ’, 则deg(a)+deg(a’)=n-1, 而n 为奇数，则a ’必为奇数度顶点。由a 的任意性，容易得知结论成立。
2．设连通图G 有k 个奇数度的结点，证明在图G 中至少要添加
成为欧拉图．
证明：由定理推论知：在任何图中，度数为奇数的结点必是偶数个，则k 是偶数。又由欧拉图的充要条件是图G 中不含奇数度结点。因此，只要在每对奇数度结点间各加一条边，使图G 的所有结点的度数变为偶数，成为欧拉图。故最少要加条边才能使其成为欧拉图。 k 条边才能使其2
形考任务六 设P ：我将去打球，Q ：我有时间．命题 ―我将去打球，仅当我有时间‖ 时符号化为( B ) ． 选择一项： A. B.
C.
D.
题目2
还未回答
满分10.00
标记题目
题干
命题公式(P ∨Q ) →的析取范式是 ( D )
选择一项：
A. ⌝(P ∨Q ) ∨R
B. (P ∧Q ) ∨R
C. (P ∨Q ) ∨R
D. (⌝P ∧⌝Q ) ∨R
题目3 还未回答 满分10.00
标记题目
题干
命题公式⌝(P →Q ) 析取范式是( A ) ． 选择一项：
A. P ∧⌝Q B. C. D.
题目4 答案已保存 满分10.00
标记题目
题干
下列公式成立的为( D ) ． 选择一项：
A. ⌝P ∧⌝Q ⇔P ∨Q B. P →⌝Q ⇔⌝P →Q C. Q →P ⇒ P D. ⌝P ∧(P ∨Q ) ⇒Q
题目5 答案已保存
满分10.00
标记题目
题干
下列公式 ( C ) 为重言式． 选择一项：
A. ⌝P ∧⌝Q P ∨Q
B. (Q →(P ∨Q )) (⌝Q ∧(P ∨Q )) C. (P →(⌝Q →P )) (⌝P →(P →Q )) D. (⌝P ∨(P ∧Q )) Q
题目6 答案已保存 满分10.00
标记题目
题干
设A （x ）：x 是人，B （x ）：x 是教师，则命题“有人是教师”可符号化为（ D ）．
选择一项：
A. ¬(ョx)(A(x)∧¬B(x))¬(ョx)(A(x)∧¬B(x)) B. (∀x)(A(x)∧B(x))(∀x)(A(x)∧B(x)) C. ¬(∀x)(A(x)→B(x))¬(∀x)(A(x)→B(x)) D. (ョx)(A(x)∧B(x))(ョx)(A(x)∧B(x))
题目7 还未回答 满分10.00
标记题目
题干表达式(∀x )(P (x,y ) ∨Q(z))∧∃y(R(x,y))→∀z Q(z))中 (∀x ) 中辖域是( B ) ． 选择一项：
A. P (x , y ) B. P (x , y ) ∨Q(z) C. R (x , y ) D.
题目8 答案已保存 满分10.00
标记题目
题干 A
设个体域 D ={a , b , c }，那么谓词选择一项：
A. (A (a ) ∨A (b ) ∨A (c )) ∨(B (a ) ∧B (b ) ∧B (b )) B. (A (a ) ∧A (b ) ∧A (c )) ∨(B (a ) ∨B (b ) ∨B (b )) C. (A (a ) ∨A (b ) ∨A (c )) ∨(B (a ) ∨B (b ) ∨B (b )) D. (A (a ) ∧A (b ) ∧A (c )) ∨(B (a ) ∧B (b ) ∧B (b ))
题目9 还未回答 满分10.00
公式去量词后的等值式为 A ．
标记题目
题干 A
下列等价公式成立的为( A ) ． 选择一项：
A. ⌝P ∧P ⇔⌝Q ∧Q B. C. D.
题目10 还未回答 满分10.00
标记题目
题干 A
设个体域D 是整数集合，则命题∀x ∃ y (x·y = y)的真值是（ A ）． 选择一项：
A. T B. F C. 不确定 D. 以上说法都不是
离散数学作业7
离散数学数理逻辑部分形成性考核书面作业
本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。
要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求本学期第17周末前完成并上交任课教师（不收电子稿）。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题
1．命题公式P →(Q ∨P ) 的真值是．
2．设P ：他生病了，Q ：他出差了．R ：我同意他不参加学习. 则命题“如果他 3．含有三个命题变项P ，Q ，R 的命题公式P ∧Q 4．设P (x ) ：x 是人，Q (x ) ：x 去上课，则命题“有人去上课．”可符号化为
5．设个体域D ＝{a , b }, 那么谓词公式∃xA (x ) ∨∀yB (y ) 消去量词后的等值式为∨∨(∧．
6．设个体域D ＝{1, 2, 3}，A (x ) 为“x 大于3”，则谓词公式(∃x ) A (x ) 的真值为． 7．谓词命题公式(∀x )((A (x ) ∧B (x )) ∨C (y )) 中的自由变元为． 8．谓词命题公式(∀x )(P (x ) →Q (x ) ∨R (x ，y )) 中的约束变元为
三、公式翻译题
1．请将语句“今天是天晴”翻译成命题公式． 设P ：今天是晴天。 则⌝P 。
2．请将语句“小王去旅游，小李也去旅游．”翻译成命题公式． 设P ：小王去旅游。 Q ：小李去旅游。
则P ∧Q
3．请将语句“他去旅游，仅当他有时间”翻译成命题公式． 设P ：他去旅游。 Q ：他有时间。 则P →Q
4．请将语句“41次列车下午五点开或六点开．”翻译成命题公式． 设P ：41次列车下午五点。 Q ：41次列车下午六点开。 则P 或Q
5．请将语句“有人不去工作”翻译成谓词公式． 设 A （x ）：x 是人
B （x ）：去工作 ∃x(A(x)∧⌝B(x))
6．请将语句“所有人都努力工作．”翻译成谓词公式． 设 A （x ）：x 是人 B （x ）：努力工作 ∀x(A(x)∧B(x))
四、判断说明题（判断下列各题，并说明理由．）
1．命题公式⌝P ∧P 的真值是1。
答：错误。因为P 和P 的否不能同时为真。
2．命题公式中的约束变元为y 。 （∃x ）P (x ) →Q (y ) ∧R (z ) ）
答：错误。该式中的约束元为x 。
3．谓词公式（∃x ）P (x ，y ) →(∀z ) Q (x , y , z ) 中∃x 量词的辖域为 P(x,y)→(∀z)Q(x,y,z)。 答：错误。谓词公式 （∃x ）P (x ，y ) →(∀z ) Q (x , y , z ) 中∃x 量词的辖域为P(x,y)。若谓词公式（∃x ）P (x ，y ) →(∀z ) Q (x , y , z ) 变为（∃x ）P (x ，y ) →(∀z ) Q (x , y , z ) ），∃x 量词的辖域为P(x,y)→(∀z)Q(x,y,z)。
4．下面的推理是否正确，请给予说明．
(1) (∀x ) A (x ) → B(x ) 前提引入 (2) A (y ) →B (y ) US (1)
答：错误。
因为B (x ) 不受全称量词∀x 的约束，不能使用全称指定规则。
（2）应为A (y ) →B (x ) ，换名时，约束元与自由变元不能混淆。 四．计算题
1．求P →Q ∨R 的析取范式，合取范式、主析取范式，主合取范式． P →Q ∨R ⇔⌝P ∨Q ∨R （析取范式） ⇔（⌝P ∨Q ∨R ）（合取范式）
主析取范式（⌝P ∧⌝P ∧⌝P ）∨（⌝P ∧⌝Q ∧R ）∨（⌝P ∧Q ∧⌝R ）∨（⌝P ∧Q ∧R ）∨（P ∧⌝Q ∧R ）∨（P ∧Q ∧⌝R ）∨（P ∧Q ∧R ） 主合取范式（⌝P ∨Q ∨R ）
2．求命题公式(P ∨Q ) →(R ∨Q ) 的主析取范式、主合取范式．
主析取范式（⌝P ∧⌝P ∧⌝P ）∨（⌝P ∧⌝Q ∧R ）∨（⌝P ∧Q ∧⌝R ）∨（⌝P ∧Q ∧R ）∨（P ∧⌝Q ∧R ）∨（P ∧Q ∧⌝R ）∨（P ∧Q ∧R ） 主合取范式（⌝P ∨Q ∨R ）
3．设谓词公式(∃x )(P (x , y ) →(∀z ) Q (y , x , z )) ∧(∀y ) R (y , z ) ． （1）试写出量词的辖域；
（2）指出该公式的自由变元和约束变元． 答：（1）∃x 的辖域为P （x,y ）→∀zQ(x,y,z)
∀z 的辖域为Q(x,y,z) ∀y 的辖域为R(y,z) (2) 约束变元为
P （x,y ）→∀zQ(x,y,z)中的x
Q(x,y,z) 中的 z R(y,z)中的y 自由变元为
P （x,y ）→∀zQ(x,y,z)中的y
R(y,z)中的z
4．设个体域为D ={a 1, a 2}，求谓词公式∀y ∃xP (x , y ) 消去量词后的等值式；
答：谓词公式∀y ∃xP (x , y ) 消去量词后的等值式为
=∃xP （x, a 1）∧∃xP （x, a 2）
=P (a 1, a 2）∨P (a 1, a 2）∧(P(a 1, a 2）∨P (a 1, a 2))
五、证明题
1．试证明 (P →(Q ∨⌝R )) ∧⌝P ∧Q 与⌝ (P ∨⌝Q ) 等价． 证明：(P →(Q ∨⌝R )) ∧⌝P ∧Q
⇔⌝P ∨(Q ∨⌝R )) ∧⌝P ∧Q ⇔⌝P ∧Q
⇔⌝（P ∨⌝Q ）
2．试证明⌝(A∧⌝B) ∧(⌝B ∨C) ∧⌝C ⇒⌝A
证明：⌝(A∧⌝B) ∧(⌝B ∨C) ∧⌝C ⇔(⌝A ∨B) ∧(⌝B ∨C) ∧⌝C
⇔(⌝A ∨B) ∧(⌝B ∧⌝C) ∨(C∧⌝C) ⇔(⌝A ∨B) ∧((⌝B ∨⌝C) ∨⌝∨0) ⇔(⌝A ∨B) ∧(⌝B ∨⌝C)
⇔(⌝A ∧ (⌝B ∧⌝C)) ∨(B ∧(⌝B ∧⌝C)) ⇔(⌝A ∧ (⌝B ∧⌝C)) ∨0 ⇔⌝A ∧ (⌝B ∧⌝C) ⇔⌝(A ∨B ∨C)
故由左边不可推出右边 A