国家开放大学2020至2022年（202001-202207）《1009离散数学（本）》期末考试真题及答案完整版（共6套）

A.A.正确 B.错误A.A.正确 B.错误试卷代号：1009 座位号国家开放大学2019年秋季学期期末统一考试离散数学（本）试题（半开卷）2020年1月一、 单项选择题（毎小题4分，本题共20分）若集合A={1,2,3,4）,则下列表述正确的是（）.TOC\o"1-5"\h\z{1, 2} 6A B. {1,2, 3}匸 AC{1,2,3尸A D.{1,2,3） eA若集合A的元素个数为5,则其暴集的元素个数为（）.A.5 B. 16C.32 D. 64若图G=vV,E>,其中V={a,b,c,d},E={a,b）.（b.c）,（b,d）},则该图中的割点为（）■A.d B. bC.c D. d无向图G是棵树，结点数为10,则G的边数是（）.A.9 B. 10C.11 D. 12设个体域为整数集，则公式（Vx）0y）（x+y=O）的解释可为（）.存在一整数x有整数y满足x+y=0任一整数x对任意整数y满足x+y=0存在一整数攻寸任意整数y满足x+y=0对任一整数x存在整数y满足x+y=0二、 判断题（毎小题4分，本题共20分）设N、R分别为自然数集与实数集，f:N-R,f（x）=x+6,则f是单射.（）设G是一个无向图，结点集合为V,边集合为E,则G的结点度数之和为IEI.()A.正确 B.错误有n个结点的无向完全图七的边数为n(n-ll).()A.正确 B.错误设G是具有n个结点m条边k个面的连通平面图，则有关系式:n+k.2=m.()A.正确 B.错误设个体域。=相，b.c[,则谓词公式(Vx)A(x)消去量词后的等值式为A(a)VA(b)VA(c).()A.正确 B.错误三、 逻辑公式翻译(毎小题6分，本题共12分)11.将语句“3大于2或1加1等于2”翻译成命题公式.将语句“他们明天去旅游，仅当明天天晴，”翻译成命题公式.四、 计算题(毎小题12分，本题共48分)设集合A={1,2,3},B={2,3,4},C={2,{3}},试计算:A—C;(2)AnB;(3)(AnB)xC.设偏序集＜A,R＞的哈斯图如图一所示,B%A的子集，其中B={a,b,c},试图_写出R的关系表达式;画出关系R的关系图;求出B的最大元、极小元、最小上界图G=<V,E>,其中V={a,b,c,d,e),E={(a,b),(a,c).(a,e),(b,d),(b,e),(c,d),(c.e),(d,e)},对应边的权值依次为2、1、2、3、6、4、1及5,试：(1)画出G的图形；(2)求出G权最小的生成树及其权值.求P一(QAR)的合取范式与主合取范式。A.A.正确 B.错误A.A.正确 B.错误试卷代号：1009国家开放大学2020年春季学期期末统一考试离散数学(本)试题2020年7月一'单项选择题(每小题4分，本题共20分)若集合A={a,b,c},则下列表述不正确的是().A.06A B.aGAC.{a(GA D.{a,b,c}頌A设集合A={1,3,5,7,9}.B=(2,4,6},A到B的关系R=(vx,y>lxEA,yGBfix=y+1),则R=()•A.{<3,2>,<5,4>,<7,6>} B.(<1,2>,<3,4>,<5,6>}C,{<1,2>,<2.3>,<3,4>)D.{vl,1>.<2,2>,<3.6>}n阶无向完全图Kn的边数及每个结点的度数分别是().A.n(n-1),n B.n-1,nn(n-l)C7~2~,n-1 D.n(n-l),n-1无向图G是棵树，边数为12,则G的结点数是().A.12 B.24C.ll D.13设个体域D={1,2},则谓词公式Wx)P(x)V0x)Q(x)消去量词后的等值式为()A.(P(l)Ap⑵)V(Q(1)Aq(2)) B.(P(1)AP⑵)V(Q(1)VQ(2))C.(P(I)VP(2》Vcoci)VQ(2》 D.(P(1)VP(2))V(Q(1)Aq(2))二、判断题(每小题4分本题共20分)设集合入=伍，b},B={1,2},C={a,b},从A到B的函数2{va,1>,<b,2>)，从B到C的函数g={<l.b>,<2,a>)，则go仁{vl,2>,<2,1>}.()A.正确 B.错误任一无向图中，度数为奇数的结点的个数为偶数.()A.正确 B.错误若图G中存在欧拉路，则图G是一个欧拉图.()设G是具有n个结点m条边k个面的连通平面图，则有关系式:n+k-m=2.()A.正确 B.错误设个体域D=|l,2,3},则谓词公式(Vx)A(x)消去量词后的等值式为A(1)Aa⑵AA(3).()A.正确 B.错误二、逻辑公式翻译(每小题G分，本题共12分)将语句“如果小王来学校，则他会参加比赛，”翻译成命题公式.将语句“小王是个学生，小李是个职员，而小张是个军人.”翻译成命题公式.四、计算题(每小题12分，本题共48分)设集合/={1,2,3},B={2,{3}},C={{3},4).试计算:BUC;(2)A—B;(3)(A・B)xC.设集合A={2,3,6,12,24.36},B为A的子集,其中B={6,12},R是A上的整除关系,试：写出R的关系表达式；画出关系R的哈斯图；求出B的最大元、极大元、最小上界.设图G=<V,E>,V=M，v2.%，V4,%}，E={M，V2),(VItV3),(VbV5),(V2,V3),(V2,V4).(%,%).(%,!),(%,%),(*,%)),试：(I)画出G的图形表示；求出每个结点的度数；⑶画出图G的补图的图形.求(PVQ)-R的析取范式与主合取范式.试卷代号：1009国家开放大学2019年秋季学期期末统一考试离散数学（本）试题答案及评分标准（半开卷）（供參考）2020年1月一、 单项选择题（毎小题4分，本题共20分）1.B2.C3.B4.A5.D二、 判断题（毎小题4分，本题共20分）6.A7.B8.B9.A10.B三•逻辑公式翻译（毎小题6分，本题共12分）TOC\o"1-5"\h\z设P:3大于2,。：1加1等于2. （2分）则命题公式为:PVQ. （6分）设P:他们明天去旅游，Q:明天天晴. （2分）则命题公式为:P-Q. （6分）四、计算题（毎小题12分，本題共48分）（1）A-C={1,3}; （4分）（2）AB=（2,3}; （8分）⑶（AnB）xC={v2,2>,v2,{3}>,v3,2>,<3,{3}>）・ （12分）（l）R={va,a>,vb,b>.vc,c>,vd,d>,va,b>,va,c>,va,d>,<b,d>,vc,d>}.（4分）（2）关系图如图二所示：图二

(8分)集合B无最大元、极小元为a、最小上界为d. (12分)(1)G的图形如图三所示：图三(4分)(2)用Kruskal算法球最小生成树的步骤为：w(a,c)=l,选(a,c)w(a,e)=l,选(a,e)w(a,b)=2,选(a,b)w(a,d)=3,选(b,d)最小生成树如图四所示：图四（吩）

最小生成树的权C（T）=1+1+2+3=7.最小生成树的权C（T）=1+1+2+3=7.(12分)注:用破圈法求最小生成树参照评分16.P->(QAR)=yv(Qar)（2分）=（TVQ）A（叩VR）合取范式（5分）<=>(叩VQ)V(RAnR)A(TVR)（7分）=CPVQ)V(RA-,R)A(TVRJV(QA^Q)（9分）Q(TVQVR)A(TVQVnR)A(TVRVQ)A(nPVRVP)(11分)<=>(TVQVR)A(TVQVnR)A(nPV0VR)主合取范式（12分）试卷代号试卷代号：1009国家开放大学2020年春季学期期末统一考试离散数学（本）试题答案及评分标准

（供參考）2020年7月一、 单项选择题（毎小题4分，本题共20分）C2.A3.C4.D5.B二、 判断题（毎小题4分，本题共20分）B7.A8.B9.A10.A三、 逻辑公式翻译（毎小题6分，本题共12分）设P：小王来学校，Q：他会参加比赛.（2分）则命题公式为:PTQ.（6分）设P：小王是个学生，Q：小李是个职员，R：小张是个军人.（2分）则命题公式为:PAQAR.（6分）四、 计算题（毎小题12分，本題共48分）（1）BUC={2,{3},4）;（4分）（2）A・B={1,3};侶分）⑶（A—B）xC={v1,{3}>,v1,4>,v3,{3}>,v3,4>}（以分）⑴集合A={2,3.6,12.24,36}上的整除关系R为:R={<2,2>,<3,3>,v6,6>,v12,12>,v24,24>,<36,36>,<2,6>,<3,6>,<2,12>,V3,12>,V6,12>,<2,24>,V3,24>,V（4分）<2,36>,<3,36>,<6,36>,<12,36>（4分）（2）关系R的哈斯图如图一所示:（8分） 24图_(3)集合B的最大元为12、极大元为12、最小上界为12.(12分)（4分）(1)关系图如图二所示:（2）deg（vj=3degg=4deg（v3）=4deg（v4）=3degM）=4信分）(3)补图如图三所示:图三图三（5分）（5分）（12分）（PVQ）tR=」（PVQ）VR（2分）0（「PV「Q）VR析取范式0（*VR）AeQVR）（7分）=（「PVR）V（QVP）A（「QVR）（9分）0（「PVR）V（QVP）A（「QVR）V（PA「P）（10分）0（*VRVQ）A（「PVRV「Q）A（「QVRVP）A（「QVRV「P）（11分）=（PV-QV/?）A（-PVQV/?）A（-PV^QVR）（］2分）国家开放大学2020年秋季学期期末统一考试

离散数学(本)试题2021年1月B.a《AD.{a,b,c,d}€A设集合A=B.a《AD.{a,b,c,d}€A设集合A={1,2,3,4,5,6),B={1,A,y£B且x=y2},则R=(A.{<1,1>,<2,4»C.{<1,1>,<6,3»2,3),A到B的关系R={<x,y>|x£).B.D.«1,1>,<4,2»<2,1»一、单项选择题(每小题4分，本题共20分)1.若集合A={a,b,c.d),则下列表述正确的是( ).{a|GAC.{a,b,c)uAA.v-e+i■=2C.v-e-r=2设A(x)：x是人,A.v-e+i■=2C.v-e-r=2设A(x)：x是人,B(x)：x是学生,为().则命题“不是所有人都是学生”可符号化A.(A(x))Ab(x))B.(Vx)(A(x))AB(x))己知无向图G的结点度数之和为10,则G图的边数为(A.10 B.20C.5 D.30设G是连通平面图，v,e,r分别表示G的结点数、边数和面数，则v,e和r满足关系式()v+c+r=2D.e-v+r=2-«(女)(A(x))A->B(x))D.-•(Vx)(A(x))TB(x))二、判断题(每小题4分，本题共20分)设集合人={1,2),B={2,3),C={3,4),则AUB-C=(1,2}.( )A.正确 B.错误如果R］和R2是A上的自反关系，则R,^R2是自反的.( )A.正确 B.错误设集合A={a,b,c),B二{1,2,3)，作f：A-B,则不同的函数个数为9.()A.正确 B错误两个图同构的必要条件是结点数相等、边数相等、度数相同的结点数相等.()A.正确 B.错误设个体域D={1,2,3,4),A(x)为“x等于3”，则谓词公式0x)a(x)的真值为F.( )A.正确 B.错误三、 逻辑公式翻译(每小题6分，本题共12分)将语句“他上午去教室上课，下午去体育馆参加比赛，”翻译成命题公式.将语句“如果他接受了这个任务，他一定能完成的翻译成命题公式.四、 计算题(每小题12分.本题共48分)设集合A={1,2,3),A上的关系R=Kx,y>|xEA,yGA且x+y>4},S=(<x>y>|x』A,yEA且x〈y},试求R,S,R_I>s(S).设G=<V,E>,V={vbv2,v3,v4),E=((vbv3),(v2,v3),(V3,V4)},试：给出G的图形表示；求出每个结点的度数；画出其补图的图形.设图G*V,E>,其中,结点集V={a,b,c,d.e),边集E={(a,c),(a,e),(b,d),(b,e),(c,e),(d,e)),对应边的权值依次为2、3、3、4、1及5,试：画出G的图形；求出G权最小的生成树及其权值.设谓词公式(3X)(A(x,y)A(VX)B(VZ))A(Vy)C(y,z),试：写出量词的辖域；指出该公式的自由变元和约束变元.试卷代号：试卷代号：1009试卷代号：试卷代号：1009国家开放大学2021年春季学期期末统一考试

离散数学(本)试题2021年7月一、 单项选择题(每小题4分，本題共20分)若集合A={1,2,3,4},则下列表述不正确的是( ).{2,3)GJ B.{1,2,3,4}C.2ej D.{2,3}u，设走设,2},B={1,2,3,4,5},4到/的关系林x,y>|xUA,y£B且x+l=y},则R=( )•(<1,2>}(<1,1>,<1,2>,<1,3>,<1,4>,<1,5>}{<1,1>,<2,1»{<h2>,<2,3»TOC\o"1-5"\h\z设G是欧拉图，则G的奇数度数的结点数为( )个.A.O B.1C.2 D.4无向图G是棵树，边数是12,则G的结点度数之和是( ).A.12 B.13C.24 D.6设A(x)：x是水果，B(x)：x是草莓，则命题“不是所有的水果都是草德'‘可符号化为().A.(Vx)(a(x)AB(x)) B.Wx)(A(x)AB(x))C.1(3X)(A(x)A-iB(x))D.1(Vx)(A(x)-B(x))二、 判断题(每小题4分，本题共20分)TOC\o"1-5"\h\z设A={1,2},B={a,b,c},作f:A-*B,则共有6个不同的函数。( )A.正确 B.错误边数相等与度数相同的结点数相等是两个图同构的必要条件.( )A.正确 B.错误设G是具有扎个结点m条边五个面的连通平面图，则n-m=2-k.( )A.正确 B.错误不存在集合A与B，使得AEB与A(B同时成立.( )A.正确 B.错误设个体域D={1,2),贝U谓词公式(Vx)p(x)V(3X)q(x)消去量词后的等值式为(P(l)Ap(2))V(Q(i)VQ(2)).( )A.正确 B.错误三、 逻辑公式翻译(每小题6分，本题共12分)将语句“我会英语，并且会德语.”翻译成命题公式，将语句“如果明天下雨，我们就去图书馆。”翻译成命题公式，试卷代号：1009试卷代号：10092021年1月四、计算题(每小题12分，本题共48分)设集合A={{a},a,b},B={a,{b}),试计算(DAAb；(2)AUb； ⑶A-(A^B)设偏序集＜A,R＞的哈斯图如下，B为A的子集，其中B={b,c),试写出R的关系表达式；画出关系R的关系图；求出B的最大元、极大元、上界，图G*V,E＞,其中V={a,b,c,d},E={(a,b),(a,c),(a,d),(b,c),(c,d)},对应边的权值依次为6、5、2、3及8,试画出G的图形；写出G的邻接矩阵；求出G权最小的生成树及其权值.求P-(QAR)的合取范式与主析取范式.国家开放大学2020年秋季学期期末统一考试

离散数学（本）试题答案及评分标准（供参考）一、 单项选择题（每小题4分,本题共20分）TOC\o"1-5"\h\zC 2.R 3.C 4.A 5.D二、 判断题（每小题4分,本题共20分）6.A 7.A 8.B 9.A 10.B三、 逻辑公式翻译（每小题6分,本题共12分）设P:他上午去教室上课,Q:他下午去体育馆参加比赛.（2分）则命题公式为:PAQ （6分）设P:他接受了这个任务,Q:他一定能完成这个任务，（2分）则命题公式为:P-Q.（6分）四、 计算题（每小题12分,本题共48分）R=（<2,3>,<3,2>,<3,3»（3分）S={<1,2>,<1,3>,<2,3>}（6分）R*=（<2,3>,<3,2>,<3,3»（9分）s（S）={<1,2>,<1,3>,<2,3>,<2,1>,<3,1>,<3,2>}（12分）（1）G的图形表示如图一所示：图一(4分)⑵dg(vi)=l,deg"。，deg(v3)=3,

deg(v4)=l(8分)(3)补图如图二所示:图二15.(1)G的图形如图三所示:图三用Kruskal算法求最小生成树的步骤为:w(c,e)=选(c,e)w(a,。二选(a,c)w(b,d)=3,选(b,d)w(b,e)=4,选(b,e)最小生成树如图四所示:图四(12分)(9分)(12分)(9分)(12分)注:用破圈法求最小生成树参照评分。.入量词的辖域为A(x,y)A(Vz)B(x,y,z),(2分)▼z量词的辖域为B(x,y,z),(4分)Vy量词的辖域为C(x,z)(6分)自由变元为A(x,y)A(Vz)B(x,y,z)中的y,以及C(y,z)中的z.(9分)约束变元为A(x,y)A(vz)B(x,y,z)中的x与B(x,y,z)中的z,以及C(y,z)中的y.(12分)试卷代号：1009国家开放大学2021年春季学期期末统一考试

离散数学（本）试题答案及评分标准（供参考）一、 单项选择题（每小题4分，本题共20分）A 2.D 3.A 4.C b.D二、 判断题（每小题4分，本题共20分）6.B 7.A 8.A 9.B 10.A三、 逻辑公式翻译（每小题6分，本题共12分）设P：我会英语，Q：我会德语.则命题公式为：PAQ-设P:明天下雨，Q:我们就去图书馆.则命题公式为：P-Q.四、 计算题（每小题12分，本题共48分）解：（1）AnB={a|；（2） AUB={{a},a,（8分）（3） A-（AnB）-{{a}>b|.解：（1）R={<a,a>,<b,b>,<c,c>,<d>,<b,d>}. 0121（4分）（2）关系图2021年7月（2分）（6分）（2分）（6分）（4分）（12分）,d>,<a,b>,<a,c>,（3）集合B无最大元，极大元为b与c、无上界15.解：（1）G的图形表示如图一所示：（8分）（12分）（2）邻接矩阵:a2d（3分）（6分）（3）图二中的粗线与结点表示的是最小生成树:权值为10.16.解：Pt(QAR)=1PV(Q△R)权值为10.16.解：Pt(QAR)=1PV(Q△R)o(-|PVQ)AP-(QAR)=1PV(QAR)PA(QVnQ)«•(-)PAQ)V(nP(10分)(12分)(nPR）合取范式(QAR)-1Q)V(QAR)（2分）（5分）0(1PAQ)v((-1PA-]Q)A(RV-1R))V(QAR)(~|PA-|QA-|R)(~|PA-|QA-|R)"E堪V.R))"E堪V.R))V(QAR)V(-1PA-]QAR)V(1PA-]Q<=>(-1PAQAR)V(-1P

V(-1PAAQA-]R)V(QAR)A-iR)<=>(-1PAQAR)V(-1P

V(-1PAAQA-]R)V(QAR)A-iR)V(-1pA-1QAR)=(-iPAQAR)V(-1PAQA-iR)V((QAR)A(PVnP))

V(-1PA-iQAR)V(-1PA-iQA-iR)试卷代号：1009试卷代号：1009P)P)V(-1PAnQ(12分)0(-1PAQAR)V(-1PAQAnR)V(QARA

AR)V(-1PA-iQAR)主析取范式说明：解法多样，能按照正确步骤得到结果参照给分国家开放大学2021年秋季学期期末统一考试

离散数学(本)试题2022年1月一、 单项选择题(每小题4分,本题共20分)若集合A={1.2,3),则下列表述不正确的是().A.3eA B.{1,3}uATOC\o"1-5"\h\zC.{2}5 D.0E4设A={1,2,3},B={1,2,3,4},A到B的关系R={<x,y>|x大于y)，则R=( ).A.{V1,2>,V2,3 >,V3,4 > } b.{V2,1>,V 3,2 >,V4,3>}C.(<2,1>,<3,1 >,<3,2 > } d.{V1,2>,V 2,3 > }若图G=<V.E>,其中V={a,b,c,d},E={(a,b),(a,d)0c),0d)},则该图中的割点为()A.a B.bC.c D.d设无向完全图Kt有九个结点(〃N2),m条边，当( )时,K”中存在欧拉回路.A.m仇为奇数 B.m为偶数C.”为奇数 D.“为偶数设A3)”是学生，B(x)：x去跑步，则命题“所有学生都去跑步”可符号化为( ).A.(3x)(A(x)AB(x)) B.(Vx)(A(x)-»B(x))C.(3x)(A(x)A->B(x)) D.(Vx)(A(x)AB(x))二、 判断题(每小題4分,本题共20分)设A=(a,b),B={1,2,3},则AXB的元素个数为6.( )A,正确 B.错误设G是一个有6个结点13条边的连通图，则G为平面图.( )A.正确 B.错误设6•是有8个结点的连通图，结点的度数之和为28,则可从G中删去6条边后使之变成树.( )A.正确 B.错误j设集合A={1.2},B={2,3},C=(3,4}.WJAUB-C=(1,3}.( )A.正确 B.错误(Vx)(P(X)AQ(y))TR(X)中量词▼的辖域为(P(x)AQ(y)).( )A.正确 B.错误三、 逻辑公式翻译(每小题6分,本題共12分)将语句“A选项是汽车，B选项是大树.”翻译成命题公式.将语句“如果今天是周三，则昨天是周二.”翻译成命题公式.四、 计算题(每小题12分,本题共48分)在此处键入公式。设/t={1,2,3,4,5),/^{<x,y>IxGj,ye且x-y=3},5={<x,y〉|x€y€4且x+y=3}试求R，S,R-S,r(S).设图G=<V,B>,^<vrv2-v3^i-v5),位{(约昭)，OXV3),(v】,v5),『2,v3),(73,v4),浮尸5)},试画出G的图形表示；写出其邻接矩阵；求出每个结点的度数；画出图。的补图的图形，试利用Kruskal算法(避圏法)求出如下所示赋权图中的最小生成树(要求写出求解步骤)，并求此最小生成树的权.求MV(QVR)的合取范式与主合取范式.国家开放大学2022年春季学期期末统一考试离散数学(本)试题2022年7月一、 单项选择题(每小题4分，本题共20分)若集合A={1,2,3,4},则下列表述不正确的是( ).A.{2,3}EA B.AS{1,2,3,4}C.(1,2,3,4}頌A D.ISA设集合A={2},B={3,4,5),A到B的关系R=(<z,y>|xGA,yGBKx=y+l),则R=(A.0 B.{<2,3>,<2,4>,<2,5>}C.{<2,3>) D.{<2,2>,<3,3>|n阶无向完全图匕。的边数是().A.n B. n(n-l)/2C.n~l D. n(n~l)TOC\o"1-5"\h\z无向图G是树，边数是10,则G的结点度数之和是( ).A.10 B.9C.20 D. 11设A(x)：x是人，b(x)：x是学生，则命题“不是所有人都是学生”可符号化为( ).A.-i(3x)(A(x)AB(x)) B.(Vx)(A(x)AB(x))C. A]B(x)) D.i(Vx)(71(x)-*F(x))二、 判断题(每小题4分，本題共20分)设集合A={a,b,c},B={\,2},作八AtB,则不网的函数个数为8.( )A,正确 B.错误设G是汉密尔顿图，S是其结点集的一个子集，若S的元素个数为4,则在G-5中的连通分支数不超过4.( )A,正确 B.错误若无向图G的边数比结点数少1,则G是树°( )A.正确 B.错误不存在集合[与&使得4耳9与AE同时成立.( )A.正确 B.错误(VX)(P(X)AQ(y)TR(x))中量词V的辖域为(P(x)AQ(y)).( )A.正确 B.错误三、 逻辑公式翻译(每小题6分，本题共12分)将语句选项是苹果，月选项是桃子.”翻译成命题公式，将语句“如果明天天晴，则我们去郊游，”翻译成命题公式，四、 计算题(每小题12分，本题共48分)设集合A={a,6,c,d},B={a,6},试计算(l)4UB;(2)4-B;(3MxB.设图G=<V,E>,V={vrv2,p3,%，V5},E={(vpv2),(vpv4),(u,,v5),(v2,v4),(v3v5)t试(1)画出G的图形表示；(1.)写出其邻接矩阵；求出每个结点的度数；画出图G的补图的图形，试求出如下所示赋权图中的最小生成树(要求写出求解步骤)，并求此最小生成树的权.求「PV(QAR)的合取范式与主合取范式.（1009（1009号）离散数学（本）答案第#页（共2页）试卷代号:1009国家开放大学2021年秋季学期期末统一考试离散数学（本）试题答案及评分标准离散数学（本）试题答案及评分标准（供参考）2022年1月一、 单项选择题（每小题4分，本题共20分）TOC\o"1-5"\h\zD 2.C 3.B 4.C 5.B二、 判断题（每小题1分，本题共20分）6.A 7.B 8.B 9.B 10.A三、 逻辑公式翻译（每小题6分，本题共12分）设P：A选项是汽车，Q：B选项是大树. （2分）则命题公式为：PAQ. （6分）设P：今天是周三，Q：昨天是周二. （2分）则命题公式为：P-Q. （6分）四、 计算题（毎小题12分，本题共48分）解：R={V4,1>,V5,2>} （3分）S={<1.2>,<2,1>} （6分）R.S={<4,2>,<5,1>} （9分）r（S）={<l.l>.<2.2>.<3.3>,<4,4X5.5>,<1.2>.<2,1>} （12分）解：（1）关系图（2）邻接矩阵（3分）（2）邻接矩阵（3分）（6分）（9分）(3)deg(V))=3deg(辺〉=2deg(V3)=3deg(=2deg(v5)=2

（9分）（4）补图V3步骤为:(12分)15.解：用Kruskal算法求产生的最小生成树。w(V2,V6)=1,选(彩2,P6)W(Z,4.Vs)=1，选(切f)W(Vi*Vfi)=2,选(,TM)W(V3,V3)=2.选(P3，寸5)W(Z»Z•,^3)=4,选