16春学期《离散数学》在线作业1

管理学  点击:   2011-11-09

16春学期《离散数学》在线作业1篇一

吉大吉大15春学期《离散数学》在线作业一满分答案

吉大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.

16春学期《离散数学》在线作业1篇二

吉大吉大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.

16春学期《离散数学》在线作业1篇三

离散数学2014春学期图论综合练习辅导

离散数学2014春学期图论部分综合练习辅导

大家好!本学期的第二次教学辅导活动现在开始,本次活动主要是针对第二单元图论的重点学习内容进行辅导,方式同样是通过讲解一些典型的综合练习作业题目,帮助大家进一步理解和掌握图论的基本概念和方法.

图论作为离散数学的一部分,主要介绍图论的基本概念、理论与方法.教学内容主要有图的基本概念与结论、图的连通性与连通度、图的矩阵表示、最短路问题、欧拉图与汉密尔顿图、平面图、对偶图与着色、树与生成树、根树及其应用等.

本次综合练习主要是复习这一单元的主要概念与计算方法,与集合论一样,也安排了五种类型,有单项选择题、填空题,判断说明题、计算题、证明题.这样的安排也是为了让同学们熟悉期末考试的题型,能够较好地完成这一部分主要内容的学习.

一、单项选择题

单项选择题主要是第4次形考作业的部分题目.

第4次作业同样也是由10个单项选择题组成,每小题10分,满分100分.在每次作业在关闭之前,允许大家反复多次练习,系统将保留您的最好成绩,希望大家要多练几次,争取好成绩.需要提醒大家的是每次练习的作业题目可能不一样,请大家一定要认真阅读题目.

1.设图G=<V, E>,vV,则下列结论成立的是 ( ) .

A.deg(v)=2E B. deg(v)=E

C.deg(v)2E D.deg(v)E

vVvV

该题主要是检查大家对握手定理掌握的情况.复习握手定理:

定理3.1.1 设G是一个图,其结点集合为V,边集合为E,则

deg(v)2|E|

vV

也就是说,无向图G的结点的度数之和等于边数的两倍.

正确答案:C

2.设无向图G的邻接矩阵为

0110

0110000110000, 10011010

则G的边数为( ).

A.6 B.5 C.4 D.3

主要是检查对邻接矩阵的概念理解是否到位.大家要复习邻接矩阵的定义,

要记住当给定的简单图是无向图时,邻接矩阵为对称的.即当结点vi与vj相邻时,结点vj与vi也相邻,所以连接结点vi与vj的一条边在邻接矩阵的第i行第j列处和第j行第i列处各有一个1,题中给出的邻接矩阵中共有10个1,故有102=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>为连通图,若有边集E1E,使图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个结点(n2),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,则

vVdeg(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)1122334430,根据握手定理,边数有

vV

E30/215.

应该填写:15

讨论: 已知图G中有15条边,3个3度结点,4个4度结点,其它结点的度数小于等于2,讨论图G可能的结点数.

2.设给定图G (如右图所示),则图G的点割集是

a f b c 本题主要是检查大家对点割集、割点的概念理解的情况.

定义3.2.7 设无向图G=<V, E>为连通图,若有点集V1V, 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有182=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条边,那么1637-6=15,由定理4.3.3知道,图G不是平面图.

问:“完全图K6是平面图”是否正确?

答:不正确.

因为完全图K6有6个结点15条边,且1536-6=12,即e  3v-6对K6不成立,所以K6不是平面图.

16春学期《离散数学》在线作业1篇四

《离散数学》模拟题

北航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)

{16春学期《离散数学》在线作业1}.

12. 公式Ax(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.求命题公式((QR)P)(PQR)PR的真值.

考核知识点:命题公式的真值表 ,参见教材P5

参考答案:((QR)P)(PQR)PR

(QRP)(PQR)PR

PR(QQ)PR

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)xy,g(x,y)xy

y D上谓词F(x,y)为x

在解释N下,判断公式的真假:

(1)个体域为自然数集合DN;

(2)DN上特定函数f(x,y)xy,g(x,y)xy。

考核知识点: 前束范式 ,参见教材P48

参考答案:

(1)在解释 N下,g(x,a)

公式xFx00, Fg(x,a),x0x, g(x,a),x成为具体命题:“任自然数等于0”。显然为假命题。

f(x,y),z (2)在解释 N下,xyzF

成为xyzxyz,即“任二自然数的和仍为自然数”。显然为真命题。

四、证明题(本题共2小题,每小题10分,共计20分)

22.证明如果非空集合A上的二元关系R和S是偏序关系,则RS也是A上的偏序关系。

考核知识点: 偏序关系的判定 ,参见教材P91

参考答案:① xA,x,xR,x,xSx,xRS,所以RS有自反性;

②x,yA,因为R,S是反对称的,

x,yRSy,xRS(x,yRx,yS)(y,xRy,xS) 所以,RS有反对称(x,yRy,xR)(x,ySy,xS)xyyxxy性.

③ x,y,zA,因为R,S是传递的,

x,yRSy,zRS

x,yRx,ySy,zRy,zS

x,yRy,zRx,ySy,zS

x,zRx,zSx,zRS

所以,RS有传递性。

总之,R是偏序关系。

23.设A,B,C为三个集合,证明若CA.则(AB)CA(BC)

考核知识点: 集合的运算 参见P 65

参考答案:x(AB)CxABxC

(xAxB)xC

(xAxC)(xBxC)

xA(xBC)xA(BC)

即 (AB)CA(BC)

北航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=(PQ),H=P(QP),则G与H的关系是( A )。

A.GH 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. AxB(x)=x(AB(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的相邻矩阵为0010001000011000010011010,则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 },定义SS上的等价关系

R{a,b,c,d | a,bSS,c,dSS,adbc}则由 R产 生的SS上一个划分共有( 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|xab3,a,bQ} B.S{x|x2n,a,bZ} {x|x2n1,nZ} D.S{x|xZx0}= N 。

16春学期《离散数学》在线作业1篇五

北航《离散数学》模拟题!!!!

北航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. 公式Ax(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.求命题公式((QR)P)(PQR)PR的真值.

考核知识点:命题公式的真值表 ,参见教材P5

参考答案:((QR)P)(PQR)PR

(QRP)(PQR)PR

PR(QQ)PR

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)xy,

D上谓词F(x,y)为xy

在解释N下,判断公式的真假:

(1)个体域为自然数集合DN;

(2)DN上特定函数f(x,y)xy,

考核知识点: 前束范式 ,参见教材P48

参考答案:

(1)在解释 N下,g(x,a)x00, Fg(x,a),x0x,

公式xFg(x,a),x成为具体命题:“任自然数等于0”。显然为假命题。

(2)在解释 N下,xyzFf(x,y),z

成为xyzxyz,即“任二自然数的和仍为自然数”。显然为真命题。

g(x,y)xy g(x,y)xy。

四、证明题(本题共2小题,每小题10分,共计20分)

22.证明如果非空集合A上的二元关系R和S是偏序关系,则RS也是A上的偏序关系。 考核知识点: 偏序关系的判定 ,参见教材P91

参考答案:① xA,x,xR,x,xSx,xRS,所以RS有自反性; ②x,yA,因为R,S是反对称的,

x,yRSy,xRS(x,yRx,yS)(y,xRy,xS)(x,yRy,xR)(x,ySy,xS)xyyxxy 所以,RS有反对称性.

③ x,y,zA,因为R,S是传递的,

x,yRSy,zRS x,yRx,ySy,zRy,zS

x,yRy,zRx,ySy,zS x,zRx,zSx,zRS

所以,RS有传递性。

总之,R是偏序关系。

23.设A,B,C为三个集合,证明若CA.则(AB)CA(BC) 考核知识点: 集合的运算 参见P 65

参考答案:x(AB)CxABxC

(xAxB)xC (xAxC)(xBxC) xA(xBC)xA(BC)

即 (AB)CA(BC)

16春学期《离散数学》在线作业1篇六

离散数学2014春学期数理逻辑综合练习辅导-6.26 (1)

离散数学2014春数理逻辑部分综合练习辅导

一、单项选择题

单项选择题主要是第6次形考作业的部分题目.

第6次作业还是由10个单项选择题组成,每小题10分,满分100分.在每次作业在关闭之前,允许大家反复多次练习,系统将保留您的最好成绩,希望大家要多练几次,争取好成绩.需要提醒大家的是每次练习的作业题目可能不一样,请大家一定要认真阅读题目.

1.设P:我将去打球,Q:我有时间.命题“我将去打球,仅当我有时间时”符号化为( ).

A.QP B.PQ C.PQ D.PQ

因为语句“仅当我有时间时”是“我将去打球”的必要条件,一般地,当语句是由“„„,仅当„„”组成,它的符号化用条件联结词.所以选项B是正确的.

正确答案:B

问:如果把“我将去打球”改成“我将去学习”、“我将去旅游”等,怎么符号化呢?

2.命题公式PQ的合取范式是 ( ).

A.PQ B.(PQ)(PQ)

C.PQ D.(PQ)

复习合取范式的定义:

定义6.6.2 一个命题公式称为合取范式,当且仅当它具有形式:

A1∧A2∧„∧An , (n1)

其中A1,A2,„,An均是由命题变元或其否定所组成的析取式.

由此可知,选项B和D是错的.又因为PQ 与PQ不是等价的,选项A是错的.所以,选项C是正确的.

正确答案:C

3.命题公式(PQ)的析取范式是( ).

A.PQ BPQ C.PQ D.PQ

复习析取范式的定义:

定义6.6.3 一个命题公式称为析取范式,当且仅当它具有形式:

A1∨A2∨„∨An , (n1)

其中A1,A2,„,An均是有命题变元或其否定所组成的合取式.

由教材第167页中的蕴含等价式知道,公式(PQ)与PQ是等价的,PQ满足析取范式的定义,所以,选项A是正确的.

正确答案:A

注意:第2,3题复习了合取范式和析取范式的概念,大家一定要记住的。如果题目改为求一个变元(P或P)命题公式的合取范式或析取范式,那么答案是什么?

4.下列公式成立的为( ).

A.PQ  PQ B.PQ  PQ

C.QP  P D.P(PQ)Q

因为: P(PQ)Q(析取三段论,P171公式(10))

所以,选项D是正确的.

正确答案:D

5.下列公式 ( )为重言式.

A.PQPQ B.(Q(PQ)) (Q(PQ)){16春学期《离散数学》在线作业1}.

C.(P(QP))(P(PQ)) D.(P(PQ)) Q

由教材第167页中的蕴含等价式,得

(P(QP)) P(Q P),(P(PQ))  P (PQ)

所以,C是重言式,也就是永真式.

正确答案:C

说明:如果题目改为“下列公式 ( )为永真式”,应该是一样的.

6.设A(

相关文章
推荐内容
上一篇:101作文节日总结
下一篇:2017下雨天的心情说说
Copyright 学习网 版权所有 All Rights Reserved