苏XI友离散数学模拟试题2(附参考答案)

1离散数学模拟试题2一、单选题（本大题共8小题，每小题2分，共16分）1．设p：天下大雨，q：我们乘公共汽车。命题“除非天下大雨，否则我们不乘公共汽车。”符号化为（）A.pqB.qpC.p∧qD.qp2．设F(x)：x是兔子，G(y)：y是乌龟，H(x,y)：x比y跑得快。命题“有的兔子比所有的乌龟跑得快”符号化为（）A.x(F(x)→y(G(y)∧H(x,y)))B.xy((F(x)∧G(y))→H(x,y))C.xy(F(x)→(G(y)→H(x,y)))D.x(F(x)∧y(G(y)→H(x,y)))3．设集合A=｛，a｝，下面四个命题为真的是（）A.aAB.AC.｛｝AD.｛a｝A4．设集合A=｛a,b,c,d｝,A上的关系R=｛〈a,b〉,〈b,a〉,〈c,d〉,〈d,c〉｝∪IA，则下面命题为真的是（）A.R是A上的等价关系B.R是A上的偏序关系C.R是A上的全序关系D.R是A上的全域关系5．设V=〈N，+〉，其中N为自然数集合，+为数的普通加法。令φ:N→N，φ（x）=2x。下面四个命题为真的是（）A.是满同态B.是单自同态C.是自同构D.是V到自身的映射，但A，B，C都不是6．设Z是整数集合，∩是Z的幂集P（Z）上的交运算。令V=〈P（Z）；∩〉，则V是（）A.循环群B.有限群C.无限群D.含幺半群7．设G是有n个顶点m条边的无向简单图,并且m=n－1,则有结论（）A.G一定是树B.G不一定是树C.G一定不是树D.G是森林8．完全图K4是（）A.欧拉图B.二部图C.平面图D.非平面图二、填空题（本大题共8小题，每小题3分，共24分）1．含n个命题变项的矛盾式的主析取范式为。2．设个体域为自然数集合N，命题xy(x+y=1)的真值为。3．设A=｛a,b｝，IA是A上的恒等关系，则商集A/IA=。4．设A=｛1,2,3,4｝，则S上的4元对称群是阶群。5．群中唯一的幂等元是。6．设Z是整数集合，×是数的乘法运算.令V=〈Z,×〉，则命题“V是群”的真值为。7．两个同构的图的顶点数一定。28．设二元正则树T的顶点数为n，则n必为数。三、简答题（本大题共8小题，每小题5分，共40分）1．用主析取范式法判断命题公式(pq)→r的类型。2．给定解释I如下：D=｛1,2｝，P(1,1)=P(2,2)=0，P(1,2)=P(2,1)=1。求xyP(x,y)在解释I下的真值。3．设A=｛1，2，3｝，A上关系R=｛〈1,1〉,〈1,2〉，〈2,1〉,〈2,2〉,〈3,1〉,〈3,3〉｝,（1）写出R的关系矩阵；（2）画出R的关系图；（3）并确定R具有哪些性质。4．设集合A=｛2,3,5,7,8,12｝，A上的偏序关系R=｛〈x,y〉∣x能整除y｝。求出集合A的极小元、极大元、最小元、最大元、上界、下界、最小上界、最大下界。5．设〈L，∧，∨〉是格，a,b∈L，验证：a∧b=a⇔a∨b=b。6．设R为实数集合，◦定义为：对任意x，yR，有x◦y=x+y–xy，这里+、-为数的加法和减法运算。验证：〈R，◦〉是否为群。7．画出带权为2，2，5，5，10，11的最优树T，求T对应的前缀码，计算T的权。8．设10阶平面图G有5个面，求G中的边数。四、证明题（本大题共4小题，每小题5分，共20分）1．在命题逻辑中构造下面推理的证明前提：q→p，p∨r，q∨s.结论：r→s.2．设R是集合A上的关系，证明：R是反自反的当且仅当R∩IA=。3．设群G中含有2阶元a（即2是使ak=e的最小正整数，其中e为单位元），证明与a可交换的元素构成G的子群。4．试证明：简单连通无向图G的任何一条边，都是G的某一棵生成树的边。3离散数学模拟试题2参考答案一、单项选择题1.B2.D3.B4.A5.B6.D7.B8.C二、填空题1.0.2.0.3.{{a},{b}}.4.4!=24.5.幺元(单位元).6.0(假).7.相同.8.奇.三、简答题1.(p∧q)r¬(p∧q)∨r¬p∨¬q∨rM6.该式为公式(p∧q)r的主合取范式，由主合取范式定义知，110为公式的成假赋值，000,001,010,011,100,101,111为公式的成真赋值，而成真赋值与公式主析取范式中的极小项一一对应，故公式的主析取范式为:(p∧q)rm0∨m1∨m2∨m3∨m4∨m5∨m7.公式的主析取范式只包含了部分极小项，故公式(p∧q)r为非重言式的可满足式.2.xyP(x,y)x(P(x,1)∧P(x,2))(P(1,1)∧P(1,2))∧(P(2,1)∧P(2,2))(0∧1)∧(1∧0)0∧00.3.(1).101011011MR(2)R的关系图为:321(3)因为IA={1,1,2,2,3,3}⊆R，所以R是自反的，不是反自反的；4因为3,1∈R，但1,3R，所以R不是对称的；因为1,2,2,1∈R，所以R也不是反对称的；因为3,1∈R，1,2∈R，但3,2R，所以R不是传递的.4.A上偏序关系的哈斯图为:由哈斯图A的极小元为2,3,5,7，最小元无；极大元为5,7,8,12，最大元无；不存在上界、上确界、下界、下确界.5.必要性.由a∧b=a，有a∨b=(a∧b)∨b=b.充分性.由a∨b=b，有a∧b=a∧(a∨b)=a.6.(1)x,yR，x◦y=x+y-xyZ，所以，Z,◦为代数系统；(2)x,y,zZ，(x◦y)◦z=(x+y-xy)◦z=x+y+z-xz-yz+xyz，x◦(y◦z)=x◦(y+z-yz)=x+y+z-xz-yz+xyz，即(x◦y)◦z=x◦(y◦z)，所以，Z,◦为半群；(3)设eZ为◦的幺元，则对xZ，有x◦e=e◦x=x，即x+e-xe=e+x-ex=x，解得e=0，故e=0为◦的幺元，所以Z,◦为独异点；(4)xZ，设yZ为x的逆元，则有x◦y=y◦x=0，即x+y-xy=y+x-yx=0，解得y=x/(x-1)(x≠1)，从而x=1时无逆元，所以，Z,◦不是群.7.用Huffman算法画出最优树如下:85237125T对应的最佳前缀码为：{01,10,11,001,0000,0001}.T的权为：W(T)=(2+2)×4+5×3+(5+10+11)×2=83.8.设平面图G为连通图，由已知条件，n=10，r=5，设G有m条边，则据欧拉公式，有10-m+5=2，则m=13，即G有13条边.设平面图G为非连通图，设G有k个连通分支，则由推广的欧拉公式，有10-m+5=k+1，则m=14-k.四、证明题1.①¬r附加前提引入②¬p∨r前提引入③¬p①②析取三段论④q→p前提引入⑤¬q③④拒取式⑥q∨s前提引入⑦s⑤⑥析取三段论2.必要性.设R是反自反的，即x∈A，x,xR.设R∩IA≠，则在A中存在元素x,y使得x,y∈R∩IA，从而x,y∈R，同时x,y∈IA，即x=y，这与00011110224591011215010010001000010111401356R是反自反的矛盾.必要性得证.充分性.设R∩IA=，则x,y∈R，由于R∩IA=，所以x,yIA，即x≠y，从而x∈A，x,xR，即R是反自反的.充分性得证.3.设S={x|ax=xa，x∈G，|a|=2}，则e∈S，因为ae=ea，即S非空；又因a是2阶元，即aa=e，故a-1=a.于是，x,y∈S，有(xy-1)a=x(y-1a)=x(y-1a-1)=x(ay)-1=x(ya)-1=x(a-1y-1)=x(ay-1)=(xa)y-1=(ax)y-1=a(xy-1)，所以，xy-1∈S.由子群判定定理，S为G的子群.4.假设G中有一条边(u,v)不是G的任何一棵生成树的边，设T是G的一棵生成树，则边(u,v)不在T中，从而T∪{(u,v)}中存在唯一一条回路C，假设边(s,t)是C上不同于(u,v)的边，则从T∪{(u,v)}中删除边(s,t)后得到的图便没有回路，并且是连通的，即(T∪{(u,v)}-{(s,t)})是一棵树，从而是G的一棵生成树，故边(u,v)在G的一棵生成树中，矛盾.