国家开放大学《离散数学(本)》形考任务1-3参考答案

家开放大学《离散数学（本）》形考任务1-3参考答案（作形考任务时每套题的题目顺序是随机的）形考任务1一、单选题1.若集合A={a,{a},{1,2}},则下列表述正确的是（）。A.{a,{a}}eAB.{1,2}1AC.{a}CAD.0EA.若集合八二{1,2},B={1,2,{1,2}},则下列表述正确的是（）oA.AuB,且AwBB.BuA,且A£BC.AuB,且A中BD.A^B,且AEB.若集合八={2,a,{a},4},则下列表述正确的是（ ）。A.{a,{a}}£AB.①WAC.{2}£AD.{a}GA.设集合A={1,2,3},B={3,4,5},C={5,6,7},则AUB-C=（）。A.{1,2,3,4}B.{1,2,3,5}C.{2,3,4,5}D.{4,5,6,7}.设集合A={a},则A的幕集为（）oA.{{a}}B.{a,{a}}C.{0,{a}}D.{0,a}.设集合A={l,a},则P(A)=( )<,A.{{l},{a}}B.{0,{lL{a}}C.{{l},{a},{La}}D.{0,{l},{a},{l,a}}.若集合A的元素个数为10,则其幕集的元素个数为()oA.1024B.10C.100D.l.设A、B是两个任意集合，则A-B=0=()oA.A=BB.ACBC.A3BD.B=0.设集合A={2,4,6,8},B={1,3,5,7},A到B的关系R={<xzy>|y=x+1},则R=( )。A.{<2,3>,<4,5>,<6,7>}B.{<2,1>,<4,3>,<6,5>}C.{<2,1>,<3,2>,<4,3>}D.{<2,2>,<3,3>,<4,6>}.集合A={1,2,3,4,5,6,7,8}上的关系R={<x,y>|x+y=10且x,yGA),则R的性质为( )oA.自反的B.对称的C.传递且对称的D.反自反且传递的)o11.集合A={1,2,3,4}上的关系R={<x,y>|x=y且x,y£A},则R的性质为（)oA.不是自反的B.不是对称的C.传递的D.反自反.如果R1和R2是A上的自反关系，则R1UR2,R1GR2,R1-R2中自反关系有（ ）个。A.0B.2C.1D.3.设集合A={1,2,3,4}上的二元关系 <2,2>,<2,3>,<4,4>},S={vl,l>,<2,2>,<2,3>,<3,2>,<4,4>},则S是R的（ ）闭包。A.自反B.传递C对称D.自反和传递14.设A={1,2,3,4,5,6,7,8},R是A上的整除关系，B={2,4,6},则集合B的最大元、最小元、上界、下界依次为（ ）。A.8、2、8、2B.8、1、6、1C.6、2、6、2D.无、2、无、215.设集合A={1,2,3,4,5},偏序关系W是A上的整除关系，则偏序集<A,上的元素5是集合A的（ ）。A.最大元B.最小元C.极大元D.极小元.设集合A={1,2,3,4,5}上的偏序关系的哈斯图如图所示，若A的子集B={3,4,5},则元素3为B的（）o5A.下界B,最小上界C.最大下界D.最小元.设A={a,b,c},B={1,2},作f：A-B,则不同的函数个数为（ ）。A.2C.6D.8.设A={a,b},B={1,2},C={4,5},从A到B的函数f={<a,l>,<b,2>},从B到C的函数g={<l,5>,<2,4>},则下列表述正确的是( )。A.f°g={<a,5>,<b,4>}B.g°f={<a,5>z<b，4>}C.f°g={<5,a>,<4,b>}D.g°f={<5,a>,<4,b>}.设集合A={1,2,3}上的函数分别为：f={<l,2>, <3,3>},g={<l,3>,<2,2>,<3,2>},h={<l,3>,<2,1>,<3,1>},则h=( )。A.f°gB.gofC.gfDgg20.设函数f：N-N,f(n)=n+l,下列表述正确的是( )。A.f存在反函数B.f是双射的C.f是满射的D.f是单射函数D.14D.14D.14D.14不存在。不存在。（X）二、判断题.设集合A={1,2,3},B={2,3,4},C={3,4,5},则AG(C-B)={1,2,3,5}。(X).设集合A={1,2,3},B={1,2},则P(A)-P(B)={{3},{1,3},{2,3},{123}}°(V).空集的幕集是空集。(X).设集合A={1,2,3},B={1,2},则AXB={<l,l>,<l,2>/<2,l>,<2,2>/<3,l>,<3,2>}o(V).设A={1,2},B={a,b,c},则AXB的元素个数为A(X).设集合A={0,l,2,3}，B={2,3,4,5},R是A至ljB的二元关系，R={(x,y)|x£A且y£B且x,y£APB}则R的有序对集合为{<2,2>,<2,3>,<3,2>,<3,3>}。(V).设集合A={1,2,3,4},B={6,8,12},A到B的二元关系R={(x,y,)|y=2x,xAA,y£B}那么R-l={<6,3>,<8,4>}o(V).设集合八={a,b,c,d},A上的二元关系R={<a,b>,<b,a>,<b,c>,<c,d>},则R具有反自反性质。(V).设集合八={a,b,c,d},A上的二元关系R={<a,a>,<b,b>,<b,c>,<c,d>},若在R中再增加两个元素<c,b>,<d,c>,则新得到的关系就具有反自反性质。(X).若集合八二{1,2,3}上的二元关系R={<1,1>,<1,2>,<3,3>},则R是对称的关系。(X).若集合八二{1,2,3}上的二元关系R={<1,1>,<2,2>, 则R是自反的关系。(X).设A={1,2}上的二元关系为R={<x,y>|xGA,yGA,x+y=10},则R的自反闭包.设R是集合A上的等价关系，且1,2,3是A中的元素，则R中至少包含<1,1>,<2,2>,<3,3>等元素。(V).设A={1,2,3},R={<1,1>,<1,2>,<2,1>,<3,3>},则R是等价关系。(X)15.如果R1和R2是A上的自反关系，则RJ、R1UR2、RiCR2是自反的。(V).若偏序集<A,R>的哈斯图如图二所示，则集合A的最大元为a,极小元

.设集合A={1,2,3,4},B={2,4,6,8},下列关系f={vl,4>,v2,2,>,<4,6>,<l,8>}可以构成函数f：A^Bo(X).设集合A={1,2,3,4},B={2,4,6,8},下列关系f={<l,8>,<2,6>,<3,4>,<4,2,>}可以构成函数f：A^Bo(V).设A={a,b},B={1,2},C={a,b},从A到B的函数f={<a,l>,<b,2>},从B至ljC的函数g={<Lb>,<2,a>},则g°f={<L,2>,<2,1>}O(X).设A={2,3},B={1,2},C={3,4},从A到B的函数f={<2,2>,<3」>},从B到C的函数g={<l,3>,<2,4>},则Dom(g°f)={2,3}o(V)形考任务2一、单选J1.设图1.设图G=<V,E>,vev,则下列结论成立的是(C)oA.deg(v)=2|E|B.deg(v)=|E|c.deg(v)=2|E|VeVD.2deg(v)=|E|veV2,设无向图G的邻接矩阵为rO2,设无向图G的邻接矩阵为rO111111 1 li001100 0 010 0 11010则G的边数为()oC.6rO110100113.设无向图G的邻接矩阵为100000100101010则G的边数为（A.5B.4)oC.6D.3.已知无向图G的邻接矩阵为A.5点，8边B.5点，7边C.6点，8边D.6点，7边.如图一所示，以下说法正确的是（ ）。A.{(d,e)}是边割集B.{(a,e)}是割边C.{(a,e)}是边割集D.{(a,e),(b,c)}是边割集6.如图二所示，以下说法正确的是（)o图二A.{d}是点割集B.e是割点C.{b,e}是点割集D.{a,e}是点割集.图G如图三所示，以下说法正确的是（）oEEA.{b,d}是点割集B.{b,c}是点割集C.a是割点D.{c}是点割集.图G如图四所示，以下说法正确的是（）oA.{(a,d)}是边割集B.{(b,d)}是边割集C.{(a,d)}是割边D.{(a,d),(b,d)}是边割集)o.设有向图（a）、（b）、（c）与（d）如图五所示，则下列结论成立的是（)oD.5D.5A.(d)是强连通的B.(b)是强连通的C.(c)是强连通的D.(a)是强连通的(d)只是弱连通的(b)只是弱连通的(a)只是弱连通的(c)只是弱连通的.无向图G存在欧拉回路，当且仅当( )。A.G中至多有两个奇数度结点B.G连通且至多有两个奇数度结点C.G连通且所有结点的度数全为偶数D.G中所有结点的度数全为偶数.无向完全图1<4是( )。A.非平面图B.树C.汉密尔顿图D.欧拉图13.若G是一个汉密尔顿图，则G一定是()oA.欧拉图B・连通图C.平面图D.对偶图14若G是一个欧拉图，则G一定是（ ）。A.对偶图B.平面图C.连通图D.汉密尔顿图15.设G是连通平面图，有v个结点，e条边，「个面，则r=（ ）。A.e-v+2B.v+e-2C.e-v-2D.e+v+2.无向树T有8个结点，则T的边数为（ ）。A.7B.9C.8D.6.无向简单图G是棵树，当且仅当（）oA.G的边数比结点数少1B,G连通且边数比结点数少1C.G连通且结点数比边数少1D.G中没有回路.已知一棵无向树T中有8个顶点，4度、3度、2度的分支点各一个，T的树叶数为（）oA.3B.4C.819•设G是有n个结点，m条边的连通图，必须删去G的( )条边，才能确定G的一棵生成树。A.m+n+1B.m-nC.n-m+1D.m-n+120.以下结论正确的是()oA.无向完全图都是平面图B.有n个结点n-1条边的无向图都是树C.无向完全图都是欧拉图D.树的每条边都是割边二、判断题.已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G的边数是15o(V)二由的=2间.设G是一个图，结点集合为V,边集合为E,则i o(V).设图G如图七所示，则图G的点割集是{f}。(X)图七.若图G=<V,E>,其中V={a,b,c,d},E={(a,b),(a,d),(b,c),(b,d)},则该图中的割边为(b,c)。(V).无向图G存在欧拉回路，当且仅当G连通且结点度数都是偶数。(J).如果图G是无向图，且其结点度数均为偶数，则图G存在一条欧拉回路。(X).如图八所示的图G存在一条欧拉回路。(X)图八.设完全图Kn有n个结点（n22）,m条边，当n为奇数时，Kn中存在欧拉回路。（V）.汉密尔顿图一定是欧拉图。（X）.设G=<V,E>是具有n个结点的简单图，若在G中每一对结点度数之和小于n-1,则在G中存在一条汉密尔顿路。（X）.若图G=<V,E>中具有一条汉密尔顿回路，则对于结点集V的每个非空子集S,在G中删除S中的所有结点得到的连通分支数为W,则S中结点数|S|与W满足的关系式为WW|S|。（V）.如图九所示的图G不是欧拉图而是汉密尔顿图。（J）.设G是一个有7个结点16条边的连通图，则G为平面图。（X）.设G是一个连通平面图，且有6个结点11条边，则G有7个面。（J）.设连通平面图G的结点数为5,边数为6,则面数为4。（X）.结点数v与边数e满足e=v的无向连通图就是树。（X）.设图G是有6个结点的连通图，结点的总度数为18,则可从G中删去4条边后使之变成树。（J）.无向图G的结点数比边数多1,则G是树。（义）.设图G是有5个结点的连通图，结点度数总和为10,则可从G中删去6条边后使之变成树。（义）.两个图同构的必要条件是结点数相等；边数相等；度数相同的结点数相形考任务3一、选择题.设P：我将去打球，Q：我有时间。命题“我将去打球，仅当我有时间时”符号化为( )。A.QfPB.P->QD.-]p-*nQ.设命题公式G：qp-*(QAR),则使公式G取真值为1的P,Q,R赋值分别是( )oA.O,OZOB.0,0,1C.0,1,0D.1,0,0.命题公式(PVQ)fR的析取范式是()oA.^PVQJVRB.(PAQ)VRC.(PVQ)VRd.(npA-iQ)VR4.命题公式(PVQ)的合取范式是( )oA.PAQ(PAQ)V(PVQ)C.PVQD.-i(iPAnQ).命题公式1(pfQ)的主析取范式是()oPAnQ-iPAQPAQiPAnQ.命题公式P-Q的主合取范式是( )。A.(PVQ)A(nv_,o)a(■,nv1。)B.叩aq■'PVQD.PVp7.下列等价公式成立的为()oA.nPAfqoPVqB.P-(工—P)=¥—(P-Q)CQf(PVQ)=十八(pVQ)¥V(PVQ)=Q.下列等价公式成立的为()oA.¥/\PoP/\QB.十->p=pfQc.p/\q=pvqD.¥VP=Q.下列公式成立的为( )oA.nPAfqoPVqB.P-*FQoQC.QfP=PD.-«PA(PVQ)=>Q.下列公式中( )为永真式。nAA由―''AVnBnAA书―->(AVB)nAA「BCAVBnAA邛―-'(AAB).下列公式( )为重言式。A.¥人十一PVQB.(Qf(PVQ))"「QA(PVQ))C.Q->(PV(PAQ))CQfpD.(¥V(P/\Q))一Q.命题公式(PVQ)-Q为( )A.矛盾式B,可满足式C.重言式D.合取范式.设A(x)：x是书，B(x)：x是数学书，则命题“不是所有书都是数学书”可符号化为(Oo-|(Vx)(A(x)-B(x))-,(3x)(A(x)AB(x))B(x))e(Vx)(A(x)r0xXA(x)AnB(x)).设A(x)：x是人，B(x)：x是教师，则命题“有人是教师”可符号化为( )oA.-1(x)(A(x)AnB(x))B.(Vx)(A(x)AB(x))C3(Vx)(A(xLB(x))D.(x)(A(x)AB(x)).设个体域为整数集，则公式x$y(x+y=O)的解释可为( )。A.存在一整数x有整数v满足x+y=OB.任一整数x对任意整数y满足x+y=OC.对任一整数x存在整数v满足x+y=OD.存在一整数x对任意整数v满足x+y=O16.表达式(Vx)(P(x,y)VQ(Z))AOy)(R(x,y)-*(Vz)Q(Z))中Bx的辖域是()oA.P(xzy)B.P(x,y)VQ(Z)C.R(x,y)D.P(x,y)AR(x/y).谓词公式(£x)(A(x)fB(x)VC(x,y))中的()。A.x,y都是约束变元B.x,y都是自由变元C.x是约束变元，y是自由变元D.x是自由变元，y是约束变元.设个体域D={a,b,c},那么谓词公式(3x)A(x)V(Vy)(By)消去量词后的等值式为( )。A.(A(a)VA(b)VA(c))V(B(a)AB(b)AB(b))B.(A(a)AA(b)AA(c))V(B(a)VB(b)VB(b))C.(A(a)VA(b)VA(c))V(B(a)VB(b)VB(b))D.(A(a)AA(b)AA(c))V(B(a)AB(b)AB(b)).设个体域D是整数集合，则命题(Px)(By)(x-y=y)的真值是( )。A.TB.FC.不确定D.以上说法都不是.前提条件P—।02P的有效结论是()oA.PB.¥C.QD.工二、判断题.设P：小王来学校，Q：他会参加比赛。那么命题“如果小王来学校，则他会参加比赛”符号化的结果为P-Q。(V).设P：昨天下雨，Q：今天下雨。那么命题“昨天下雨，今天仍然下雨”符号化的结果为PAQo(V).设P：我们下午2点去礼堂看电影，Q：我们下午2点去教室看书。那么命题“我们下午2点或者去礼堂看电影或者去教室看书”符号化的结果为PVQ。(