管理学 点击: 2011-11-09
吉大15春学期《离散数学》在线作业一
单选题 判断题
一、单选题(共 15 道试题,共 60 分。) 1.
如题
A.
B.
C.
D.
-----------------选择:B
2.
如题
A.
B.
C.
D.
-----------------选择:C
3.
如题
A.
B.
C.
D.
-----------------选择:D
4.
如题
A.
B.
C.
D.
-----------------选择:C
5.
如题
A.
B.
C.
吉大吉大15春学期《离散数学》在线作业二满分答案
吉大15春学期《离散数学》在线作业二
单选题 判断题
一、单选题(共 15 道试题,共 60 分。) 1.
如题
A.
B.
C.
D.
-----------------选择:A
2.
如题
A.
B.
C.
D.
-----------------选择:D
3.
如题
A.
B.
C.
D.
-----------------选择:A
4.
如题
A.
B.
C.
D.
-----------------选择:D
5.
如题
A.
B.
C.
离散数学2014春学期图论综合练习辅导
离散数学2014春学期图论部分综合练习辅导
大家好!本学期的第二次教学辅导活动现在开始,本次活动主要是针对第二单元图论的重点学习内容进行辅导,方式同样是通过讲解一些典型的综合练习作业题目,帮助大家进一步理解和掌握图论的基本概念和方法.
图论作为离散数学的一部分,主要介绍图论的基本概念、理论与方法.教学内容主要有图的基本概念与结论、图的连通性与连通度、图的矩阵表示、最短路问题、欧拉图与汉密尔顿图、平面图、对偶图与着色、树与生成树、根树及其应用等.
本次综合练习主要是复习这一单元的主要概念与计算方法,与集合论一样,也安排了五种类型,有单项选择题、填空题,判断说明题、计算题、证明题.这样的安排也是为了让同学们熟悉期末考试的题型,能够较好地完成这一部分主要内容的学习.
一、单项选择题
单项选择题主要是第4次形考作业的部分题目.
第4次作业同样也是由10个单项选择题组成,每小题10分,满分100分.在每次作业在关闭之前,允许大家反复多次练习,系统将保留您的最好成绩,希望大家要多练几次,争取好成绩.需要提醒大家的是每次练习的作业题目可能不一样,请大家一定要认真阅读题目.
1.设图G=<V, E>,vV,则下列结论成立的是 ( ) .
A.deg(v)=2E B. deg(v)=E
C.deg(v)2E D.deg(v)E
vVvV
该题主要是检查大家对握手定理掌握的情况.复习握手定理:
定理3.1.1 设G是一个图,其结点集合为V,边集合为E,则
deg(v)2|E|
vV
也就是说,无向图G的结点的度数之和等于边数的两倍.
正确答案:C
2.设无向图G的邻接矩阵为
0110
0110000110000, 10011010
则G的边数为( ).
A.6 B.5 C.4 D.3
主要是检查对邻接矩阵的概念理解是否到位.大家要复习邻接矩阵的定义,
要记住当给定的简单图是无向图时,邻接矩阵为对称的.即当结点vi与vj相邻时,结点vj与vi也相邻,所以连接结点vi与vj的一条边在邻接矩阵的第i行第j列处和第j行第i列处各有一个1,题中给出的邻接矩阵中共有10个1,故有102=5条边.
正确答案:B
3.如右图所示,以下说法正确的是 ( ) .
A.{(a, e)}是割边
B.{(a, e)}是边割集
C.{(a, e) ,(b, c)}是边割集
D.{(d, e)}是边割集
先复习割边、边割集的定义: e a b c d
定义3.2.9 设无向图G=<V,E>为连通图,若有边集E1E,使图G删除了E1的所有边后,所得的子图是不连通图,而删除了E1的任何真子集后,所得的子图是连通图,则称E1是G的一个边割集.若某个边构成一个边割集,则称该边为割边(或桥)
因为删除答案A或B或C中的边后,得到的图是还是连通图,因此答案A、
B、C是错误的.
正确答案:D
注:如果第3题只给出图的结点和边,没有图示,大家也应该会做.如: 若图G=<V, E>,其中V={ a, b, c, d, e },E={ (a, b), (a, c) , (a, e) , (b, c) , (b, e) , (c, e) , (e, d)},则该图中的割边是什么?
4.设有向图(a)、(b)、(c)与(d)如下图所示,则下列结论成立的是( ).
A.(a)是强连通的 B.(b)是强连通的
C.(c)是强连通的 D.(d)是强连通的
我们先复习强连通的概念:
定义3.2.5 在简单有向图中,若在任何结点偶对中,至少从一个结点到另一个结点可达的,则称图G是单向(侧)连通的;
若在任何结点偶对中,两结点对互相可达,则称图G是强连通的. 正确答案:A
问:上面的图中,哪个仅为弱连通的?
请大家要复习“弱连通”的概念.
5.设完全图Kn有n个结点(n2),m条边,当( )时,Kn中存在欧拉回路.
A.m为奇数 B.n为偶数 C.n为奇数 D.m为偶数
我们先复习完全图的概念:
定义3.1.6 简单图G=<V,E>中,若每一对结点间都有边相连,则称该图为完全图.有n个结点的无向完全图记为Kn.
由定义可知,无向完全图Kn中的任一结点v到其它结点都有一条边,共有n-1条边,即每个结点的度数是n-1,当n为奇数时,n-1为偶数.
由定理4.1.1的推论
一个无向图具有一条欧拉回路,当且仅当该图是连通的,并且它的结点度数都是偶数.
所以,正确答案应该是C.
提示:前面提到n阶无向完全图Kn的每个结点的度数是n-1,现在要问:无向完全图Kn的边数是多少?
如2013年7月份试卷中:
3.n阶无向完全图Kn的边数及每个结点的度数分别是( ).
A.n(n-1)/2,n-1 B.n-1,n
C.n(n-1), n-1 D.n(n-1), n
6.设G是连通平面图,有v个结点,e条边,r个面,则r= ( ).
A.e-v+2 B.v+e-2 C.e-v-2 D.e+v+2 本题主要检查大家是否掌握了欧拉定理.
定理4.3.2(欧拉定理) 设连通平面图G的结点数为v,边数为e,面数为r,则欧拉公式v-e+r =2成立.
由欧拉公式v-e+r =2,得到r = e- v+2.
所以,答案A是正确的.
问:如果连通平面图G有4个结点,7条边,那么图G有几个面?
7.无向简单图G是棵树,当且仅当( ).
A.G连通且边数比结点数少1 B.G连通且结点数比边数少1
C.G的边数比结点数少1 D.G中没有回路.
可以运用教材中的定理5.1.1,可以作出正确选择.因为定理5.1.1中给出的图T为树的等价定义之一是图T连通且e=v-1,其中e是边数,v是结点数.也就是说:无向简单图G是棵树,当且仅当G连通且边数比结点数少1. 正确答案:A
注:由上面的树的等价定义可知,结点数v与边数e满足e=v-1关系的无向连通图就是树.问当树T有6个结点,那么它有多少条边?
8.已知一棵无向树T中有8个结点,4度,3度,2度的分支点各一个,T的树叶数为( ).
A.8 B.5 C.4 D.3
设无向树T的树叶数为x,因为树叶是度数为1的结点.
那么,由定理3.1.1(握手定理) 设G是一个图,其结点集合为V,边集
合为E,则
vVdeg(v)2|E|,
得 4+3+2+x=2(8-1),即x=5.
正确答案:B{16春学期《离散数学》在线作业1}.
下面的内容主要是第5次形考作业的部分题目.
二、填空题
1.已知图G中有1个1度结点,2个2度结点,3个3度结点,4个4度结点,则G的边数是 .
也是检查大家对握手定理掌握的情况.
因为图G中有1个1度结点,2个2度结点,3个3度结点,4个4度结点,即deg(v)1122334430,根据握手定理,边数有
vV
E30/215.
应该填写:15
讨论: 已知图G中有15条边,3个3度结点,4个4度结点,其它结点的度数小于等于2,讨论图G可能的结点数.
2.设给定图G (如右图所示),则图G的点割集是
a f b c 本题主要是检查大家对点割集、割点的概念理解的情况.
定义3.2.7 设无向图G=<V, E>为连通图,若有点集V1V, d 使图G删除了V1的所有结点后,所得的子图是不连通图,而删{16春学期《离散数学》在线作业1}.
除了V1的任何真子集后,所得的子图是连通图,则称V1是G的一个点割集.若某个结点构成一个点割集,则称该结点为割点.
从图G中删除结点f,得到的子图是不连通图,即结点集{f}是点割集;同样,从图G中删除结点c,e,得到的子图也是不连通图,那么结点集{c, e}也是点割集.而删除其他结点集都没有满足点割集、定义的集合,所以
应该填写:{f}、{c, e}
提示:若f是图G的割点,则{f}是图G的点割集,删除f点后图G是连通吗?
3.无向图G存在欧拉回路,当且仅当G连通且 由定理4.1.1的推论
一个无向图具有一条欧拉回路,当且仅当该图是连通的,并且它的结点度数都是偶数.
应该填写:结点度数都是偶数
4.若图G=<V, E>中具有一条汉密尔顿回路,则对于结点集V的每个非空子集S,在G中删除S中的所有结点得到的连通分支数为W,则S中结点数|S|与W满足的关系式为 .{16春学期《离散数学》在线作业1}.
定理4.2.1 若图G=<V,E>中具有一条汉密尔顿回路,则对于结点集V的每个非空子集S均有W(G-S) |S|成立,其中W(G-S)是(G-S)中连通分支数. 应该填写:W(G-S) |S|
5.设图G是有6个结点的连通图,结点的总度数为18,则可从G中删去 G的一棵生成树)
由握手定理(定理3.1.1)知道图G有182=9 条边,又由定理5.1.1中给出的图T为树的等价定义之一是“图T连通且e=v-1”,可以知道: 应该填写:4.
注意:选择题和填空题讲完后还要强调考核说明中第3章的第1个考核要求:
1.理解图的基本概念:结点、边、有向图,无向图、简单图、完全图、结点的度数、图的同构、子图等,理解握手定理.
三、判断说明题
1.如果图G是无向图,且其结点度数均为偶数,则图G存在一条欧拉回路. 分析:先复习欧拉图的判别定理:
定理4.1.1的推论:一个无向图具有一条欧拉回路,当且仅当该图是连通的,并且它的结点度数都是偶数.
解:不正确.
因为题中的图G没有“连通”的条件.
问:“如果图G是无向连通图,则图G存在一条欧拉回路”
是否正确? a 2.如右图所示的图G不是欧拉图而是汉密尔顿图.
解:正确. b d 图G有4个3度结点a,b,d,f,所以图G不是 欧拉图.图G有汉密尔顿回路abefgdca,所以图G是 e g 汉密尔顿图. f
注意:汉密尔顿图不一定是欧拉图,为什么?. 图G
3.设G是一个有7个结点16条边的连通图,则G为平面图.
分析:定理4.3.3 设G是一个有v个结点e条边的连通简单平面图,若v≥3,则e≤3v-6.
利用该定理判断本题.
解:不正确.
因为题中的连通简单平面图有v=7个结点,e=16条边,那么1637-6=15,由定理4.3.3知道,图G不是平面图.
问:“完全图K6是平面图”是否正确?
答:不正确.
因为完全图K6有6个结点15条边,且1536-6=12,即e 3v-6对K6不成立,所以K6不是平面图.
《离散数学》模拟题
北航10秋学期《离散数学》模拟题一
一、单项选择题(本大题共15小题,每小题2分,共30分)
1. ∑中所有有限长度的串形成的集合记为∑* ,容易证得∑*上的连接运算不满足交换律,但满足( A )
A.结合律 B.分配律 C.幂等律 D.吸收律
2. Klein群中元素a,b,c的阶为( B )。
A.1 B.2 C.3 D.4
3. 群G的元素x的所有幂的集合为G的子群,称由x生成的子群。记为( A ).
A.<x> B.(x) C.x D.[x]
4. 交换环是指乘法满足( A )。
A.交换律 B.结合律 C.分配律 D.吸收律
5. 至少有( B )元素的含单位元、无零因子环称为除环。
A.一 B.二 C.三 D.四
6. ∨,∧满足( C )的格称为分配格
A.交换律 B.结合律 C.分配律 D.幂等律
7. 若L为有限布尔代数,则( B )正整数n,L与含有n个元素的集合A的幂集同构。
A.不存在 B.存在 C.有可能存在
8. 有向图D的顶点v作为边的始点的次数之和称为v的出度,记为d+(v), v作为边的终点的次数之和称为v的入度,记为
d-(v),v的度数d(v)= ( A )。
A.d+(v)+d-(v) B.d+(v) C.d-(v) D.d+(v)*d-(v)
9. 若通路Г=v0e1v1e2„e1v1 中所有顶点互不相同(所有边自然互不相同)时称为( B )
A.初级回路 B.路径 C.复杂通路 D.迹
10. 在n阶图中,若一顶点存在到自身的回路,则必存在从该顶点到自身的长度不超过( B )的回路。
A.n-1 B.n C.n+1 D.2n
11. “人总是要死的”谓词公式表示为( C )。
(论域为全总个体域)M(x):x是人;Mortal(x):x是要死的。
A.M(x)Mortal(x); B.M(x)Mortal(x)
Mortal(x)); D.x(M(x)Mortal(x)) C.x(M(x)
12. 公式Ax(P(x)Q(x))的解释I为:个体域D={2},P(x):x>3, Q(x):x=4则A的真值为( A )。
A.1; B.0; C.可满足式; D.无法判定。
13. 下列等价关系正确的是( B )。
A.x(P(x)Q(x))xP(x)xQ(x);
B.x(P(x)Q(x))xP(x)xQ(x);
C.x(P(x)
D.x(P(x)
14. Q)xP(x)Q; Q)xP(x)Q。 下列偏序集( C )能构成格。
s{1,
15. 设111,2,,3,,4}234,*为普通乘法,则[S,*]是( D )。
A.代数系统; B.半群; C.群; D.都不是。
参考答案:
1-5 ABAAB 6-10 CBABB 11-15 CABCD
二、填空题(本大题共4题,16题2分,其它每空3分,共20分)
16、设格中表达式E = (a⊕b)×(c⊕d),则E的对偶表达式E*=_______________。
考核知识点:格的对偶表达式 ,参见教材P144
参考答案:(a×b)⊕(c×d)
17、设集合A = {a, b, c, d, e},A上半序关系R的哈斯图如下图所示,则A的极大元为__________,极小元为__________。
考核知识点:半序关系的极值 ,参见教材P93
参考答案:
18、由集合运算的基本定律:
(1)A∩A = A,满足__________律;
(2)A∪E = E,满足__________律;
(3)A∩E = A,满足__________律;
(4)A∩~A =υ,满足__________律。
考核知识点:集合的运算律 ,参见教材P65-67
参考答案:
三、问答题(本大题共3小题,每小题10分,共30分)
19.求命题公式((QR)P)(PQR)PR的真值.
考核知识点:命题公式的真值表 ,参见教材P5
参考答案:((QR)P)(PQR)PR
(QRP)(PQR)PR
PR(QQ)PR
1
20、设集合A={0,1,2,3,4,5,6}上的偏序关系R如下:
R={<0,1>,<0,2>,<0,3>,<0,4>,<0,5>,<0,6>,<4,6>,<2,5>,<3,5>}IA
做偏序集<A,R>的哈斯图,并求B={0,2,3}的极大元、极小元、最大元和最小元。
考核知识点: 偏序关系的极值 ,参见教材P93
参考答案:A={0,1,2,3,4,5,6}, B={0,2,3},
哈斯图如右图.
B的极大元:2,3, B的极小元:0
B的最大元:无 B的最小元:0
21、解释N如下:
个体域DN 为全体自然数的集合
DN中特定元素a=0
DN上函数f(x,y)xy,g(x,y)xy
y D上谓词F(x,y)为x
在解释N下,判断公式的真假:
(1)个体域为自然数集合DN;
(2)DN上特定函数f(x,y)xy,g(x,y)xy。
考核知识点: 前束范式 ,参见教材P48
参考答案:
(1)在解释 N下,g(x,a)
公式xFx00, Fg(x,a),x0x, g(x,a),x成为具体命题:“任自然数等于0”。显然为假命题。
f(x,y),z (2)在解释 N下,xyzF
成为xyzxyz,即“任二自然数的和仍为自然数”。显然为真命题。
四、证明题(本题共2小题,每小题10分,共计20分)
22.证明如果非空集合A上的二元关系R和S是偏序关系,则RS也是A上的偏序关系。
考核知识点: 偏序关系的判定 ,参见教材P91
参考答案:① xA,x,xR,x,xSx,xRS,所以RS有自反性;
②x,yA,因为R,S是反对称的,
x,yRSy,xRS(x,yRx,yS)(y,xRy,xS) 所以,RS有反对称(x,yRy,xR)(x,ySy,xS)xyyxxy性.
③ x,y,zA,因为R,S是传递的,
x,yRSy,zRS
x,yRx,ySy,zRy,zS
x,yRy,zRx,ySy,zS
x,zRx,zSx,zRS
所以,RS有传递性。
总之,R是偏序关系。
23.设A,B,C为三个集合,证明若CA.则(AB)CA(BC)
考核知识点: 集合的运算 参见P 65
参考答案:x(AB)CxABxC
(xAxB)xC
(xAxC)(xBxC)
xA(xBC)xA(BC)
即 (AB)CA(BC)
北航10秋学期《离散数学》模拟题二
一、单项选择题(本大题共15小题,每小题2分,共30分)
1. 设集合A={1,2,3},A上的关系R={(1,1),(2,2)},则R不具有关系的( A )性质。
A.自反性 B.对称性 C.传递性 D.反对称性
2. 设集合A={a, b, c},A上关系R的关系图如下图所示,则R具有( B )。{16春学期《离散数学》在线作业1}.
A.自反性、对称性、传递性
B.自反性、传递性
C.对称性、反对称性
D.对称性、反对称性、传递性
3. 设命题公式G=(PQ),H=P(QP),则G与H的关系是( A )。
A.GH B.H
G C. G=H D.以上都不是
4. 下面给出的一阶逻辑等价式中,( B )是错的。
A. x(A(x) ∨B(x))=x A(x) ∨x B(x)
B. x(A(x) ∨B(x))=xA(x) ∨xB(x)
C. xA(x)=x(A(x))
D. AxB(x)=x(AB(x))
5. 如下图所示,半序集中哪个不是格?( B )
6. 设(B,·,+,-,0,1)是布尔代数,a,b是B中元素,a ≤ b,则下面( C )公式不成立。
A. a·b= 0 B. a+b = 1
C. a+b= 1 D. a+b
=a
7. 下图是( C )。
A.完全图 B.平面图 C.哈密顿图 D.欧拉图
8. 已知图G的相邻矩阵为0010001000011000010011010,则G的边数与分枝数为( B )
A. 5,3 B. 4,2 C. 5,1 D. 6,4
9. 若干能等值地表示出全部(合式)公式(真值函数)的逻辑联结词集合称为( A )
A. 全功能集 B.功能集 C.全功能联结词集合 D.特殊联结词集合
10. 下列不是极小全功能集的是( D )
A {┐,∨} B.{┐,∧} C. {┐,→} D. {∨,→}
11. 设SS{,{1},{1,2}},则 2 有( D )个元素。
A.3; B.6; C.7; D.8 。
12. 设S{ 1, 2, 3 },定义SS上的等价关系
R{a,b,c,d | a,bSS,c,dSS,adbc}则由 R产 生的SS上一个划分共有( B )个分块。
A.4; B.5; C.6; D.9 。
13. 设S{ 1, 2, 3 },S上关系R的关系图为,则R具有( D )性质。
A.自反性、对称性、传递性; B.反自反性、反对称性;
C.反自反性、反对称性、传递性; D.自反性 。
14. 设 , 为普通加法和乘法,则( A )S,,是域。
A.S
C.S{x|xab3,a,bQ} B.S{x|x2n,a,bZ} {x|x2n1,nZ} D.S{x|xZx0}= N 。
北航《离散数学》模拟题!!!!
北航10秋学期《离散数学》模拟题一
本复习题页码标注所用教材为: 《离散数学基础》 耿素云、屈婉玲 1994年 北京大学出版社 如学员使用其他版本教材,请参考相关知识点
一、单项选择题(本大题共15小题,每小题2分,共30分)
1. ∑中所有有限长度的串形成的集合记为∑* ,容易证得∑*上的连接运算不满足交
换律,但满足( A )
A.结合律 B.分配律 C.幂等律 D.吸收律
2. Klein群中元素a,b,c的阶为( B )。
A.1 B.2 C.3 D.4
3. 群G的元素x的所有幂的集合为G的子群,称由x生成的子群。记为( A ).
A.<x> B.(x) C.x D.[x]
4. 交换环是指乘法满足( A )。
A.交换律 B.结合律 C.分配律 D.吸收律
5. 至少有( B )元素的含单位元、无零因子环称为除环。
A.一 B.二 C.三 D.四
6. ∨,∧满足( C )的格称为分配格
A.交换律 B.结合律 C.分配律 D.幂等律
7. 若L为有限布尔代数,则( B )正整数n,L与含有n个元素的集合A的幂集
同构。
A.不存在 B.存在 C.有可能存在
8. 有向图D的顶点v作为边的始点的次数之和称为v的出度,记为d+(v), v作为边
的终点的次数之和称为v的入度,记为d-(v),v的度数d(v)= ( A )。
A.d+(v)+d-(v) B.d+(v) C.d-(v) D.d+(v)*d-(v)
9. 若通路Г=v0e1v1e2„e1v1 中所有顶点互不相同(所有边自然互不相同)时称为
( B )
A.初级回路 B.路径 C.复杂通路 D.迹
10. 在n阶图中,若一顶点存在到自身的回路,则必存在从该顶点到自身的长度不超
过( B )的回路。
A.n-1 B.n C.n+1 D.2n
11. “人总是要死的”谓词公式表示为( C )。
(论域为全总个体域)M(x):x是人;Mortal(x):x是要死的。
A.M(x)Mortal(x); B.M(x)Mortal(x)
C.x(M(x)Mortal(x)); D.x(M(x)Mortal(x))
12. 公式Ax(P(x)Q(x))的解释I为:个体域D={2},P(x):x>3, Q(x):x=4则
A的真值为( A )。
A.1; B.0; C.可满足式; D.无法判定。
13. 下列等价关系正确的是( B )。
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。
14. 下列偏序集( C )能构成格。
s{1,
15. 设111,2,,3,,4}234,*为普通乘法,则[S,*]是( D )。
A.代数系统; B.半群; C.群; D.都不是。
参考答案:
1-5 ABAAB 6-10 CBABB 11-15 CABCD
二、填空题(本大题共4题,16题2分,其它每空3分,共20分)
16、设格中表达式E = (a⊕b)×(c⊕d),则E的对偶表达式E*=_______________。
考核知识点:格的对偶表达式 ,参见教材P144
参考答案:(a×b)⊕(c×d)
17、设集合A = {a, b, c, d, e},A上半序关系R的哈斯图如下图所示,则A的极大元为__________,极小元为__________。
考核知识点:半序关系的极值 ,参见教材P93
18、由集合运算的基本定律:
(1)A∩A = A,满足__________律;
(2)A∪E = E,满足__________律;
(3)A∩E = A,满足__________律;
(4)A∩~A =υ,满足__________律。
考核知识点:集合的运算律 ,参见教材P65-67
参考答案:
三、问答题(本大题共3小题,每小题10分,共30分)
19.求命题公式((QR)P)(PQR)PR的真值.
考核知识点:命题公式的真值表 ,参见教材P5
参考答案:((QR)P)(PQR)PR
(QRP)(PQR)PR
PR(QQ)PR
1
20、设集合A={0,1,2,3,4,5,6}上的偏序关系R如下:
R={<0,1>,<0,2>,<0,3>,<0,4>,<0,5>,<0,6>,<4,6>,<2,5>,<3,5>}IA
做偏序集<A,R>的哈斯图,并求B={0,2,3}的极大元、极小元、最大元和最小元。
考核知识点: 偏序关系的极值 ,参见教材P93
参考答案:A={0,1,2,3,4,5,6}, B={0,2,3},
哈斯图如右图.
B的极大元:2,3, B的极小元:0
B的最大元:无 B的最小元:0
21、解释N如下:
个体域DN 为全体自然数的集合
DN中特定元素a=0
DN上函数f(x,y)xy,
D上谓词F(x,y)为xy
在解释N下,判断公式的真假:
(1)个体域为自然数集合DN;
(2)DN上特定函数f(x,y)xy,
考核知识点: 前束范式 ,参见教材P48
参考答案:
(1)在解释 N下,g(x,a)x00, Fg(x,a),x0x,
公式xFg(x,a),x成为具体命题:“任自然数等于0”。显然为假命题。
(2)在解释 N下,xyzFf(x,y),z
成为xyzxyz,即“任二自然数的和仍为自然数”。显然为真命题。
g(x,y)xy g(x,y)xy。
四、证明题(本题共2小题,每小题10分,共计20分)
22.证明如果非空集合A上的二元关系R和S是偏序关系,则RS也是A上的偏序关系。 考核知识点: 偏序关系的判定 ,参见教材P91
参考答案:① xA,x,xR,x,xSx,xRS,所以RS有自反性; ②x,yA,因为R,S是反对称的,
x,yRSy,xRS(x,yRx,yS)(y,xRy,xS)(x,yRy,xR)(x,ySy,xS)xyyxxy 所以,RS有反对称性.
③ x,y,zA,因为R,S是传递的,
x,yRSy,zRS x,yRx,ySy,zRy,zS
x,yRy,zRx,ySy,zS x,zRx,zSx,zRS
所以,RS有传递性。
总之,R是偏序关系。
23.设A,B,C为三个集合,证明若CA.则(AB)CA(BC) 考核知识点: 集合的运算 参见P 65
参考答案:x(AB)CxABxC
(xAxB)xC (xAxC)(xBxC) xA(xBC)xA(BC)
即 (AB)CA(BC)
离散数学2014春学期数理逻辑综合练习辅导-6.26 (1)
离散数学2014春数理逻辑部分综合练习辅导
一、单项选择题
单项选择题主要是第6次形考作业的部分题目.
第6次作业还是由10个单项选择题组成,每小题10分,满分100分.在每次作业在关闭之前,允许大家反复多次练习,系统将保留您的最好成绩,希望大家要多练几次,争取好成绩.需要提醒大家的是每次练习的作业题目可能不一样,请大家一定要认真阅读题目.
1.设P:我将去打球,Q:我有时间.命题“我将去打球,仅当我有时间时”符号化为( ).
A.QP B.PQ C.PQ D.PQ
因为语句“仅当我有时间时”是“我将去打球”的必要条件,一般地,当语句是由“„„,仅当„„”组成,它的符号化用条件联结词.所以选项B是正确的.
正确答案:B
问:如果把“我将去打球”改成“我将去学习”、“我将去旅游”等,怎么符号化呢?
2.命题公式PQ的合取范式是 ( ).
A.PQ B.(PQ)(PQ)
C.PQ D.(PQ)
复习合取范式的定义:
定义6.6.2 一个命题公式称为合取范式,当且仅当它具有形式:
A1∧A2∧„∧An , (n1)
其中A1,A2,„,An均是由命题变元或其否定所组成的析取式.
由此可知,选项B和D是错的.又因为PQ 与PQ不是等价的,选项A是错的.所以,选项C是正确的.
正确答案:C
3.命题公式(PQ)的析取范式是( ).
A.PQ BPQ C.PQ D.PQ
复习析取范式的定义:
定义6.6.3 一个命题公式称为析取范式,当且仅当它具有形式:
A1∨A2∨„∨An , (n1)
其中A1,A2,„,An均是有命题变元或其否定所组成的合取式.
由教材第167页中的蕴含等价式知道,公式(PQ)与PQ是等价的,PQ满足析取范式的定义,所以,选项A是正确的.
正确答案:A
注意:第2,3题复习了合取范式和析取范式的概念,大家一定要记住的。如果题目改为求一个变元(P或P)命题公式的合取范式或析取范式,那么答案是什么?
4.下列公式成立的为( ).
A.PQ PQ B.PQ PQ
C.QP P D.P(PQ)Q
因为: P(PQ)Q(析取三段论,P171公式(10))
所以,选项D是正确的.
正确答案:D
5.下列公式 ( )为重言式.
A.PQPQ B.(Q(PQ)) (Q(PQ)){16春学期《离散数学》在线作业1}.
C.(P(QP))(P(PQ)) D.(P(PQ)) Q
由教材第167页中的蕴含等价式,得
(P(QP)) P(Q P),(P(PQ)) P (PQ)
所以,C是重言式,也就是永真式.
正确答案:C
说明:如果题目改为“下列公式 ( )为永真式”,应该是一样的.
6.设A(