《离散数学》期末试卷（含答案）

学院姓名学号任课老师选课号………密………封………线………以………内………答………题………无………效……第1页共6页电子科技大学二零二至二零二学年第二学期期末考试离散数学课程考试题B卷（120分钟）考试形式：闭卷考试日期年月日课程成绩构成：平时分，期中分，实验分，期末分一二三四五六七八九十合计一、单选题（四选一）（10×1＝10分）如果命题公式G=P∧Q，则下列之一哪一个成立（）。1).G=(P→Q) 2).G=(P→Q) 3).G=(P→Q) 4).G=(P→Q)设Φ是一个空集，则下列之一哪一个不成立（）。1).Φ∈Φ 2).ΦΦ 3).Φ∈{Φ} 4).Φ{Φ}谓词逻辑的推理中，使用的是规则（ ）。1).ES 2).US 3).UG 4).EG在集合｛0，1｝上可定义（）个不同的二元运算。1).2 2).4 3).8 4).16设集合A＝{a,b,c}，A上的二元关系R＝{<a,a>,<b,b>,<c,c>,<a,b>,<c,b>}，则R是A上的（ ）关系。1).拟序 2).偏序 3).全序 4).良序设图G的邻接矩阵为，则G中长度为2的回路总数为（ ）。1).1 2).2 3).4 4).5下列图中（ ）即非欧拉图又非哈密尔顿图。1).2).3).4).设G是一个7阶群，则该群一定有（）个不变子群。1).2 2).4 3).6 4).8设G是连通的平面图，设n、m、r分别为G的顶点数，边数和面数，则有：n－m＋r＝()。1).1 2).2 3).3 4).4设G是一个24阶群，a是G中任意一个元素，则a的周期一定不是（）。1).2 2).8 3).16 4).24二、多项选择题（五选二至五）（5×1＝5分）设G=PQ是仅含原子P和Q的命题公式，则G是（ ）。1).短语2).析取范式3).合取范式4).主析取范式5).主合取范式下列哈斯图中，是格的有（）。1). 2). 3). 4). 5). 若<G,*>是一个13阶群，则运算“*”一定满足（）。1).交换律 2).消去律3.幂等律 4).结合律5).分配律下列谓词的蕴涵公式中，错误的有（ ）。 1). 2).3). 4).5).非空集合A上的恒等关系具有（ ）。 1).自反性 2).反自反性 3).对称性4).反对称性 5).传递性三、简答题（4×2=8分）1、试述幂集的定义。2、设R是集合A上的二元关系，试述R是传递性的定义。3、试述树的定义。4、试述格同态的定义。四、判断分析改错题(如果正确，说明理由，如果不正确，举例说明)（4×5＝20分）“若R，S是集合A上的反自反的二元关系，则RS也是反自反的二元关系。”这句话对吗？为什么？等价公式“（x）(G(x)H(x))＝（x）G(x)（x）H(x)”成立吗？如果成立，说明理由，如果不成立，举例说明。 “无向简单图中的每条边都必须在一个连通分支中。”这句话对吗？为什么？“设<G,>是满足消去律的二元代数系统，且幺元存在，则G中除幺元外无其它幂等元。”这句话对吗？为什么？五、计算题（4×8＝32分）设有合适公式(x)P(x)(x)Q(f(a)，x)，给定如下解释：个体域D＝{1，0}，a＝0，f(1)＝0，f(0)＝1，P(0)＝0，P(1)＝1，Q(1，1)＝1，Q(1，0)＝1，Q(0，1)＝0，Q(0，0)＝0，计算该合适公式在给定的解释下的真值。设A＝{1,2,3,4,5,6,7,8,9},R={<x,y>|x,y∈A且3|(x-y)}，则R是等价关系，计算商集A/R。下图为一个无有向图，用邻接矩阵计算该图中长度为3的所有通路和回路总数。设有代数系统<Z,*>，其中Z是整数集合，运算“*”定义如下：a,b∈Z，有：a*b=a+b+2。试验证该代数系统是否存在有幺元，零元，可逆元，如果存在则请求出幺元，零元，每个元素的逆元。六、证明题（共25分）1、所有的有理数都是实数；所有的无理数也是实数；虚数不是实数。因此，虚数即不是有理数也不是无理数。2、设是两个函数，证明：(1)若为满射，则为满射；(2)若为单射，则为单射设<L,≤>是一有界分配格，L1是L中所有具有补元的元素构成的集合。试证明：<L1,≤>是<L,≤>的子格。离散数学期末考试标准答案一、单项选择题：评分标准：对1个给1分(2) (1)(3)(4)(2)(2)(2)(2)(2)(3)二、多项选择题：评分标准：完全正确1个给1分，否则不给分（1，2，3，4，5）（2，3，4）（1，2，4）（2，4，5）（1，3，4，5）三、简答题：评分标准：答对大意给2分1、答：设A为集合，把A的全体子集构成的集合叫做A的幂集。2、答：设R是集合A上的二元关系，对任意的x,y,z∈A，如果<x,y>∈R且<y,z>∈R，那么<x,z>∈R，则称关系R是传递的，或称R具有传递性。3、答：连通而不含回路的无向图称为无向树，简称树。4、答：设<L,∧,∨>和<S,*,>是两个格，ψ是L到S的映射。如果对任意x,y∈L，都有ψ(x∧y)=ψ(x)*ψ(y)，ψ(x∨y)=ψ(x)ψ(y)则称ψ为从格<L,∧,∨>到格<S,*,>的格同态映射，简称格同态。四、判断分析改错题：评分标准：判断正确给3分，理由正确给2分。判断错误则不给分。1、答：不是。例如：A＝{1,2}，A上的关系R＝{<1,2>}、S＝{<2,1>}均反自反，但RS＝{<1,1>}不反自反。2、答：不成立。例如：①个体域为D={a,b}；②G(a)指定为：1，G(b)指定为：0③H(a)指定为：0，H(b)指定为：1则（x）(G(x)H(x))为0，（x）G(x)（x）H(x)为1。故不等。3、答：对。假设无向简单图G中存在一条边(u,v)不在任何一个连通分支中。若u、v在同一个连通分支P中，则P∪(u,v)是G的子图且仍然是连通的，这与P是连通分支矛盾；若u、v不在同一个连通分支中，设u在连通分支P中，v在连通分支Q中，则P∪(u,v)∪Q是G的子图且然是连通的，这与P是连通分支矛盾。故无向简单图中的每条边都必须在一个连通分支中。4、答：对。假设a是G中非幺元e的幂等元，即a*a=a，且a≠e。因此a*a=a*e，由消去律知a=e，矛盾。五、计算题（4×8＝32分，每小题8分）1解(x)P(x)(x)Q(f(a),x)=(P(1)∧P(0))(Q(f(a),1)∨(f(a),1))――（4分）=(P(1)∧P(0))(Q(f(0),1)∨Q(f(0),1))――（1分）=(1∧0)(Q(1,1)∨Q(1,1))――（1分）=(0∧1)(1∨1)――（1分）=01＝1――（1分）2证明(1)对"xÎA，有3|(x-x)，所以<x,x>ÎR，即R是自反的。――（1分）(2)对"x,yÎA，若<x,y>ÎR，即3|(x-y)，所以3|(y-x)，所以，<y,x>ÎR，即R是对称的。――（1分）(3)对"x,y,AÎA，若<x,y>ÎR且<y,z>ÎR，有3|(x-y)且3|(y-z)，所以由(x-z)=(x-y)+(y-z)得3|(x-z)，所以，<x,z>ÎR，即R是传递的。――（2分）由(1)、(2)、(3)知，R是A上的等价关系。因为[1]R＝{1,4,7}＝[4]R＝[7]R――（1分）[2]R={2,5,8}＝[5]R=[8]R――（1分）[3]R={3,6,9}=[6]R=[9]R――（1分）所以商集A/R＝{[1]R,[2]R,[3]R}={{1,4,7}，{2,5,8}，{3,6,9}}――（1分）3解右图的邻接矩阵为：――(2分)则――(2分)――(2分)从而，――(1分)即右图中长度为3的通路(含回路)总数为48，其中10条为回路。――(1分)4解<Z,*>有么元，可逆元，但没有零元.――(1分)因为存在-2∈Z，使得对任意a∈Z，有a*(-2)=a+(-2)+2=a，2*a=(-2)+a+2=a.故－2是<Z,*>的幺元；――(2分)不存在x∈Z，使得对任意a∈Z，有a*x=x*a=x.故<Z,*>无零元；――(2分)对任意a∈Z，存在4-a∈Z，使得a*(-4-a)=a+(-4-a)+2=-2，(-4-a)*a=-4-a+a+2=-2.故a的逆元是-4-a。由a的任意性知，Z中每个元素都有逆元。――(3分)六、证明题（共25分,第1题9分，第2，3题各8分）1、解：设Q(x)：x是有理数；R(x)：x是实数；N(x)：x是无理数；C(x)：x是虚数，则上述句子可符号为：(x)(Q(x)→R(x))，(x)(N(x)→R(x))，(x)(C(x)→┐R(x))(x)(C(x)→┐Q(x)∧┐N(x))。――(3分)①(x)(Q(x)→R(x))P②Q(x)→R(x)US，①――(1分)③(x)(N(x)→R(x))P④N(x)→R(x)US，③――(1分)⑤(x)(C(x)→┐R(x))P⑥C(x)→┐R(x)US，⑤――(1分)⑦R(x)→┐C(x)T，⑥，E――(0.5分)⑧Q(x)→┐C(x)T，②，⑦，I――(0.5分)⑨N(x)→┐C(x)T，④，⑦，I――(0.5分)⑩(Q(x)→┐C(x))∧(Q(x)→┐C(x))T，⑧，⑨，E――(0.5分)11(C(x)→┐Q(x)∧┐N(x))T，⑩，E――(0.5分)12(x)(C(x)→┐Q(x)∧┐N(x))UG，11――(0.5分)2、证明（1）对任意cC,由fg是满射，所以存在aA，使得fg(a)=c,即g(f(a))=c。――(2分)所以存在b=f(a)B，使得g(b)=c，由c的任意性，所以g是满射。――(2分)（2）对任意a1,a2C(a1≠a2),由fg是单射，有fg(a1)≠fg(a2),即g(f(a1))≠g(f(a2))。――(3分)因g是函数，所以，f(a1)≠f(a2)。所以f是单射。――(1分)3、证明设<L,,,0,1>是有界分配格，并设A是所有有补元构成的集合。――(1分)由于0和1有补元，所以0,1∈A，于是A非空。――(1分)又对任意的a,b∈A，设a,b的补元分别是和，因为(a*b)*()=(a*b*)(a*b*)=((a*)*b)(a*(b*))=(0*b)(a*0)=00=0；――(1.5分)(a