离散数学期末测试卷I及复习资料.docx

离散数学期末考试复习题及答案第一局部、考试形式和时间答题时限： 120 分钟 考试形式：闭卷笔试第二局部、考试题型和得分构成大题号总分一二三四10020101060一、选择题：对每一道小题，从其4个备选答案中选择最合适的一项，每小题2分，共10道小题，20分。二、填空题：每空1分，共5道小题，10个空白处待填，10分。三、推断题：每一道小题均以陈述语句描绘，对的打，错的打。每小题1分，共10道小题，10分。四、综合题：每小题10分，共6道小题，60分。第三局部、考试复习范围一、选择题1含n个元素的集合A的幂集的元素个数为多少？答案：2n个。2 数理逻辑的创始人是谁？答案：莱布里茨。3 设(R,+,×)是环，它有哪些特性？答案：1.(R,+)是阿贝尔群。2.(R,)是半群。3.对+可安排。4 排中律满意哪些性质？答案：A 不成立。（不应同时否认一个命题（A）及其否认（非A）x（F（x）F（x）对任何个体x而言，x有性质F或没有性质F。5 什么是真命题？命题“假如雪是黑的，则1+1=0”是真命题吗？ 答案：真值为真的命题为真命题。命题“假如雪是黑的，则1+1=0”是真命题！解析：p:雪是黑的；q:1+1=0;假如雪是黑的，则1+1=0:pq。由于p为假，所以无论的真值如何，“pq”的真值都为真。6. 下列哪个等价公式有错？A；B；C；答案：A 7. 设G为4阶有向图，度数列为（3,4,2,3），若它的入度列为（1,2,2,1），则出度列为哪项？A （1,2,1,2）； B（2,2,0,2）； C（2,1,1,2） 答案：B解析：有向图中：度数=出度数+入度数。8. 设,则表示空元素属于S怎样写？答案:ØS9. 什么是前束范式？下面哪个是前束范式？A ； B答案：前束范式：假如量词均在全式的开头，它们的作用域延长到整个公式的末端，则该公式叫做前束范式。B。解析：假如量词均在全式的开头，它们的作用域延长到整个公式的末端，则该公式叫做前束范式，明显B选项满意定义。9. 无向图中有16条边，且每个结点的度数均为2，则结点数是多少？答案：16解析：由于每个结点的度数为2，所以可以解除G中存在孤立点（度数为0）和悬挂点（度数为1）。由此可知，G中的任何一个结点皆是运用一度与上一个结点相连再运用另一度与下一个结点相连，从而每条边与两个结点关联（上一个结点与下一个结点），但是每个结点又与两条边相连，故结点数为：16×2÷2=16个。10. 含n个命题变元的命题公式的不同的真值指派有几种？答案：2n种 11. 集合论的创始人是？答案：G.Cantor(康托尔)13以下推理错误的是？ A； B； C答案：B14设G为4阶有向图，度数列为（4,4,2,2），若它的入度列为（2,2,1,1），则出度列为哪项？C A（2,1,1,2）； B（1,2,1,2）； C（2,2,1,1） 15图论中的握手定理的内容是什么？答案：握手定理：在任何（n,m）图G=（V，M）中，其全部结点度数之和等于边数m 的两倍，即：deg(v)=2m。16下面哪一种图不肯定是树？ A有个结点条边； B无圈连通图； C每对结点间有唯一的一条路的图 D无圈但增加一条边，就得到一个且仅有一个圈答案：A17对于随意素数p和正整数n，存在多少个元素的有限域？答案：Pn18 下面所示的偏序集中，哪个是格？答案：B【解析】要想对偏序格进展正确地推断，前提是肯定要吃透概念和定义：设(L,)是偏序集，若L中的随意两个元素组成的子集均存在上确界及下确界，则称(L,)为偏序格。另外，加设SL。上确界：子集S的最小上界：lub(S)或sup(S)下确界：子集S的最大下界：glb(S)或inf(S)留意：1.只有一条线上的两个元素可以比拟大小。未在一条线上的两个元素没有偏序关系（无法比拟大小）2.若对于均有,则a为S的上界，反之，为下界。A选项中a,b的下界元素有c和0，但是由于c和0无偏序关系而无法比拟大小，导致a,b没有下确界。C选项a,b没有上确界。D选项a,b没有上、下确界,c,d没有上、下确界。B选项中（a,c上确界:a,下确界:c;a,b上确界：1，下确界：c;d,e上确界：c,下确界：0；.）随意两个元素组成的子集都存在上确界和下确界，故B选项是偏序格！19 设表示是学生。表示是教师，表示敬佩。则命题“全部学生都敬佩某些教师”符号化为后的表达式是什么？答案：20 谓词公式中量词（）辖域是答案：R(x,y)21 图论的创始人是谁？答案：瑞士数学家L.Euler(欧拉)22 两个图同构是指其中一个图近经过哪些变换可以变为另一个图？答案：1.挪动点的位置；2.伸缩边的长短。23. 什么是孤立点和悬挂点？答案：孤立点：在随意图G(V,E)中，度数为0的结点。悬挂点：在随意图G(V,E)中，度数为1的结点。24.域和环相比增加了哪些要求？答案：域：设(F,+,)是环，若(F-0,)是阿贝尔群，则称(F,+,)是域。25.阿贝尔群具有哪些特点？比一般群增加了什么？答案：阿贝尔群：设(G,)是群，若其运算是可交换的，则称(G,)为阿贝尔群。二、填空题1鸽笼原理是指什么？ 答：n+1只或更多的鸽子飞进n个笼子时，肯定有一个笼子里面至少有2只鸽子。2 哪位挪威数学家和法国数学家先后为群的探讨做出了出色的奉献？答案：挪威数学家Niels Henrik Abel （尼尔斯· 亨利克·阿贝尔）和法国数学家Évariste Galois（埃瓦里斯特伽罗瓦） 为群的探讨做出了出色的奉献。3 单独一个节点v构成的序列v到v的长度为多少的路？叫做什么？答案：单独一个节点v构成的序列v到v的长度为0的路叫做平凡路4 命题公式(pq)r的析取范式与合取范式各为什么？答案：析取范式： 合取范式：5 集合A, B的对称差AÅB可以表示为什么？答案：6 半群（S, *）满意哪些特性答案：S是非空集合，*是S上满意结合律的二元封闭运算。7 在谓词逻辑中，命题“全部有理数是实数”符号化为什么？命题“有些实数是有理数”符号化为什么？答案：设Q(x):x是有理数，R(x):x是实数。则命题“全部有理数是实数”符号化为：命题“有些实数是有理数”符号化为：8 布尔代数的定义是怎样的答案：元素个数2的有补安排格称作布尔代数。9 设R Í A ´ A, 则R在A是反自反的充要条件是什么？答案：IAR=10 什么状况下称 f 是 A到B的双射？答案：f既是A到B的单射，也是A到B的满射时称f是A到B的双射。11 补元的定义是怎样的？答案：.则称是A的补元。 12 什么是安排格？答案：若格的乘法运算“”对格的加法运算“+”互相可安排，则称是安排格。13 设(R,+,×)是环，怎样成为交换环、含幺环、无零因子环？答案：环的定义：(R,+,)是含有两个二元运算的代数构造，若：(1) (R,+)是阿贝尔群。(2) (R,)是半群。(3) 对+可安排。则称(R,+,)是环。另外：R中的乘法运算可交换，则称(R,+,)是交换环。R中的乘法运算有幺元，则称(R,+,)是含幺环。14 命题公式中的对偶式分别是怎样定义的？答案：将至多含有3个逻辑联结词（否认联结词，析取联结词，合取联结词）的命题公式A中的析取联结词换成合取联结词，将1换成0，将0换成1，合取联结词换成析取联结词后所得到的命题公式A*称为命题公式A的对偶式。15 一个集合的上/下确界是怎样定义的？答案：在偏序集(A,)，SA，S的最小上界称为上确界sup(S)，S的最大下界称为下确界inf(S).三、推断题1 (A, f1, f2, fk)=(B, g1, g2, gk) 表示这两个代数构造是同构的。答：错。 (A, f1, f2, fk)(B, g1, g2, gk)才表示这两个代数构造是同构的。2 关系图GR中的每一对不同点之间的边都是成对出现的，则称R是对称的。答：正确。3 若(S, *)是有限半群，则肯定存在幺元e，并构成独异点(S, *，e)。答：错误。代数构造(S,*)中，若S为有限集合，*是S上满意结合律的二元封闭运算，则称(S,*)为有限半群。例如：S=0,2,4,*8是模8乘法运算。则(S,*8)是有限半群，但不存在幺元。4 有向图G=(V, E)中的"u, vÎV, u和v互相可达，则称G为强连通图。答：正确。5 在关系图GR中，对随意的x,y,zÎA,只要x到y有边且y到z有边，就肯定有x到z有边，则R是传递的。答：正确。6 设是一个群，则0。答：错误。设G是非0实数集，*是其上的数的乘法运算，明显(G,*)是群。则随意属于G的元素x，其逆元X-1 = ，从而(X-1)-1=X。7 设是一个偏序集，假如中随意两个元素都有上确界和下确界，则称 是一个格。答：正确。也称(A,)为偏序格。8 命题公式的逆反式是。答：正确。左边=右边9 图 是弱连通图。答：正确。该图为强连通图且属于弱连通图。10 A上的关系R是等价的意味着R必需具有自反性、对称性和传递性。答：正确。11 若关系R的MR中主对角线元素全为1，则R是反自反的。答：错误。若关系R的MR中主对角线元素全为1，表示R是自反的。12 设R，S是集合A上的传递关系，则RS肯定是传递的。答：错误。不肯定：取A=a,b,c,d,令R=(a,b),(b,c),(a,c),S=(b,c),(c,a),(b,a),易知R,S是A上的传递关系。然而，RS=(a,c),(a,a),(b,a),其中(b,a)RS,(a,c)RS,但是(b,c)RS，因此RS不传递。13 对命题变元p和q，则命题公式p(pØ q）是中性的。答：正确。14 图 是强连通图。答：错误。应为弱连通图。15 (R, +, ×)是环的主要特性之一是 × 对+可安排。 答：正确。16 整数集合Z上的整除关系“|”是对称的。答：错误。1|2，但是2不整除1，故整数集合Z上的整除关系“|”是反对称的。17 实数集合R是的小于等于关系“”不是对称的。答：正确。18 随意非永假命题公式都存在多个的主析取范式。答：错误。随意非永假（非永真）命题公式都存在唯一的主析取范式（主合取范式）。19 设A和B是两个命题公式，则A = B的充要条件是A « B为永真式 。 答：正确。20 答：正确。四、综合题：1设代数系统V=N8，是群。（1）写出运算表； （2）求每个元素的逆元 ； （3）求元素2的阶及含2的各阶元素的子集A使A，构成N6，的子群。0 1 2 3 4 5 0 0 1 2 3 4 5 1 1 2 3 4 5 0 2 2 3 4 5 0 1 3 3 4 5 0 1 2 4 4 5 0 1 2 3 5 5 0 1 2 3 4 解：(1)(2) 0-1=0 1-1=5 2-1=4 3-1=3 (3) 元素4的阶为3, A=0,2,4 2. 设集合A=1，2，3，5，6，10，15，30，“”是整除关系，代数系统 V=，是布尔格。（1）画出偏序集V=，的哈斯图； （2）求出每个元素的补元；（3）求A的四元子集B，使B，是，的子格； （4）求A的四元子集C，使C，是格，但不是，的子格。解：哈斯图. .（2分）1与30互补；（1分） 2 与15互补； （1分） 3 与10互补；（1分） 5 与6互补； （1分） B=1，2，3，6 (不唯一) （2分） C=1，2，3，30 （不唯一） .（2分） 3. 某电路中有一只灯泡和三个开关A, B, C。已知当且仅当在下述4种状况之一灯亮：（1）C的搬键向上，A和B的搬键向下；（2）A的搬键向上，B和C的搬键向下；（3）B和C的搬键向上，A的搬键向下； （4）A和B的搬键向上，C的搬键向下.令F表示灯亮，p, q, r分别表示A, B, C的搬键向上，求F=F(p, q, r)的逻辑表达式以及F的主合取范式。解：01(主合取范式)4. 设集合a, b, c, d，上的关系a, b,b, a,b, c,c,d，用集合表示法求R的自反闭包、对称闭包、传递闭包。解：r(R)=a, b,b, a,b, c,c,d，<a,a>,<b,b>,<c,c>,<d,d>S(R)=a, b,b, a,b, c,c,d,<c,b>,<d,c>t(R)=a, b,b, a,b, c,c,d,<a,a>,<a,c>,<b,b>,<b,d>,6 是一个群，而,若f是从G到G的映射，使得对每一个，都有：。试证明：f是一个从G到G上的自同构。证：首先证明f是单射。 其次证明f是满射。 对 综合以上两点，知f是双射。 6. 对于以下谓词公式的说明。个体域D=1, 2， 个体常量：a/1, b/2, 函词f：f (1)/2, f (2)/1,谓词P：P(1,1)/1, P(1, 2)/1, P(2, 1)/0, P(2, 2)/0分别求下列谓词公式在上述说明下的真值。（1）P(f(a), a)P(f(b), b)（2）$y"xP(y, x).解：（1）P(f (a), a)P(f (b), b)=P(f (1), 1)P(f (2), 2) =P(2, 1)P(1, 2) =01=0 （2）$y"xP(y, x).=$y (P(y, 1).P(y, 2) =(P(1, 1).P(1, 2)(P(2, 1).P(2, 2) =(11)(00)=17. 证明：（1）3-正则图的阶必为偶数；（2）有n个人，每个人恰有3个挚友，则n为偶数。证：（1）设G是3-正则（n, m）图，依据握手定理，有 3*n=2*m. 由于2|2m，因此2|n，即n为偶数。（2）将n个人看做n个节点，当两个人是挚友时，则在相应的两个节点之间连一条无向边，于是得到一个无向图G。依据已知条件，G是一个3-正则图，由（1）知，n偶数。7 用推理规则论证下述问题：证： 1 2 3 4 5 6 7 8 由8得出了冲突，依据归谬法说明原推理正确。第二种方式：证：(1)P (2)T(1)I(3)P(4)T(2)(3)I(5)P(6)T(4)(5)I