离散数学期末试卷A卷

注：试题字迹务必清晰，书写工整。本题9页，本页为第1页教务处试题编号：四川大学期末考试试题（闭卷）（2014-2015学年第1学期）课程号：304039040课程名称：离散数学（A卷）任课教师：冯伟森石兵周莉陈瑜林兰适用专业年级：2013级计算机科学与技术学号：姓名：考试须知四川大学学生参加由学校组织或由学校承办的各级各类考试，必须严格执行《四川大学考试工作管理办法》和《四川大学考场规则》。有考试违纪作弊行为的，一律按照《四川大学学生考试违纪作弊处罚条例》进行处理。四川大学各级各类考试的监考人员，必须严格执行《四川大学考试工作管理办法》、《四川大学考场规则》和《四川大学监考人员职责》。有违反学校有关规定的，严格按照《四川大学教学事故认定及处理办法》进行处理。题号一（16%）二（14%）三（10%）四（30%）五（30%）六七八卷面成绩得分阅卷教师阅卷时间一、单项选择题（本大题共16小题，每小题1分，共16分）提示：在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分123456789101112131415161.令R:小王吃饭；S：小王看电视。则语句“小王一边吃饭一边看电视”可以符号化为（）。（A)R∨S；（B）R∧S；（C）R→S；（D）～R∨～S2.令P(x):x是实数，Q(x):x是有理数。则语句“并非每个实数都是有理数”可以符号化为（）。（A）～x(R(x)Q(x))；（B）～(R(x)Q(x))；（C）～x(R(x)∧Q(x))；（D）～x(R(x)∨Q(x))3.下列公式中，（）是永真公式。（A）R→S；（B）R∧～R；（C）R∨～R；（D）(R→S)∧(R∧～S)4.下列公式中（）是等价公式。（A）G∧(H∨S)(G∨H)∧(G∨S)；（B）G∧(H∨S)(G∧H)∧(G∧S)；（C）G∧(H∨S)(G∧H)∨(G∧S)；（D）G∧(H∨S)(G∨H)∨(G∨S)；5.公式x((P(x)Q(y，x))zR(y，z))S(x)中，自由变元是()。（A）x和y；（B）y和z；（C）x和z；（D）z或者y6.设集合A={1，2，3}，则A上所有非等价关系数目为（）。课程名称：离散数学任课教师：学号：姓名：------------------------------------------------------------------------------------------------------------------------本题9页，本页为第2页教务处试题编号：（A）512(B)507(C)508(D)5067.下列关于有限集偏序集〈A,≤〉的描述，（）是正确的(A)一定存在最大元(B)一定存在最小元(C)任意两元素都存在最大下界(D)一定存在极大元8.下列说法不正确的是（）(A)任意两个非空集合之间都可构造函数(B)任意两个非空集合之间都可构造单射函数(C)任意两个非空集合之间都可构造满射函数(D)任意两个非空集合之间如可构造单射函数，也可构造满射函数，那么一定可构造双射函数9.下列各组数中，不能构成无向图的点度数序列的是（）。(A){1，1，2，2，3}(B){1，3，5，7，8}(C){2，2，2，2}(D){2，2，3，8，1}10.下列说法正确的是（）。(A)树至少有两个叶结点(B)存在既是二部图又是哈密顿图的简单无向图(C)平面图满足欧拉公式n–m+f=2(D)连通无向图都有非平凡生成树11.已知图G中存在一条欧拉道路，以下说法正确的是（）：（A）图中没有奇度数结点；（B）图中只有2个奇度数结点；（C）图中有0个或2个奇度数结点；（D）无法确定图中奇度数结点的个数12.在实数集R上，定义代数系统R,*，则关于“*”运算的下列的运算规则定义中，（）是可结合的？(A)a*b=a-b；(B)a*b=max{a,b}；(C)a*b=a+2b；(D）a*b=|a-b|13.３次对称群S3的集合中含有（）个元素：（A）2；（B）3；（C）4；（D）614.整数加群Z,+是一个无限循环群，其生成元是（）：（A）-1；（B）0；（C）1；（D）-1和1两个生成元15.在代数系统模7剩余类环7,,Z中，零因子的个数是（）：（A）0个；（B）1个；（C）2个；（D）7个16.下列哪些代数系统不是域（）：（A）实数环R,+,×；（B）有理数环Q,+,×；（C）整数环Z,+,×；（D）模7剩余类环7,,Z课程名称：离散数学任课教师：学号：姓名：------------------------------------------------------------------------------------------------------------------------本题9页，本页为第3页教务处试题编号：二、多项选择题（本大题共7小题，每小题2分，共14分）提示：在每小题列出的备选项中有不确定个数个选项是符合题目要求的，请将其代码填写在下表中。错选、多选、少选或未选均无分。123456789101.下列语句中，（）是命题。（A）上海不是一个大城市；（B）你去哪里？（C）4+3=7；（D）不存在最大的质数；（E）请认真答题！2.下列命题中，（）是真命题。(A){Ф}∈{Ф,{{Ф}}}；(B){Ф}{Ф,{{Ф}}}；(C)Ф∈{{Ф}}；(D)Ф{Ф}3.右图所示的关系具有（）(A)自反性(B)反自反性(C)对称性(D)反对称性(E)传递性4.下列描述那些是不正确的（）。(A)〈N,〉是自然数域上的偏序关系(B)〈2A,〉一定不是全序集(C)〈N,≤〉是自然数域上的全序集(D)〈2Φ,〉是良序集5.以下关于代数系统描述正确的是（）：（A）2A,∩和2A,∪都是含幺半群；（B）R，+是含幺半群，也是群；（Ｃ）只要是半群，就必含有幂等元；（Ｄ）任何群中只含有一个幂等元。6.非平凡无向树是（）。(A)二部图(B)哈密顿图(C)平面图(D)连通图(E)欧拉图7.下列关于格的说法正确的是（）。(A)偏序格〈L,≤〉的Hasse图是连通图(B)代数格〈L,∨,∧〉中，如果a∨b=a,那么a∧b=b(C)偏序格〈L,≤〉中必有最大元，最小元(D)偏序格〈L,≤〉中必有极大元，极小元三、填空题（本大题共5小题，每题2分，共10分）。1.若集合A={1,{2,3}})，则2A=。2.设集合A和B，则从A到B的不同的二元关系有个。3.设Ａ＝｛1,2,3,4,5,6｝，B={1,2,3}。从Ａ到B的关系Ｒ＝｛（x,y）|x=2y｝，则：R=；R-1=。4.设R是定义在集合A={1,2,3,4,5,6}上的等价关系，并且R=IA∪{（1,5）,（5,1）,（2,4）,（4,2）,（3,6）,课程名称：离散数学任课教师：学号：姓名：------------------------------------------------------------------------------------------------------------------------本题9页，本页为第4页教务处试题编号：（6,3）}。那么，可以由此等价关系R对集合A产生的分划是：。5.素数阶群G,*,其子群为。四、计算题（本大题共6小题，每题5分，共30分）。1.请用公式的等价变换法求公式（P→Q）∧（P→R）的主合取范式。解：2.设有谓词公式(x)(P(x,f(x))→Q(x))，在如下给定解释下，判断该公式的真值解释I指定为：（1）个体域D={a,b}(2)f(a)=b,f(b)=a（3）P(a,a)=0,P(a,b)=1,P(b,a)=1,P(b,b)=0（4）Q(a)=0,Q(b)=1解：课程名称：离散数学任课教师：学号：姓名：------------------------------------------------------------------------------------------------------------------------本题9页，本页为第5页教务处试题编号：3.设A,R是一个偏序集，集合A={1,2,3,4,6,9,24,54}，关系R是A上的整除关系。（1）请画出该偏序关系的哈斯图；（2）求集合A中的极大元；（3）设集合A的子集合B={4,6,9}，求集合B的最小上界和最大下界。解：4.请利用可达矩阵求出下图中的所有强分图：v1v3v2v4v5解：课程名称：离散数学任课教师：学号：姓名：------------------------------------------------------------------------------------------------------------------------本题9页，本页为第6页教务处试题编号：5.请将下面的有序树转化为一棵二叉树。v1v3v2v4v5v6v7v8v9v10v11v12解：课程名称：离散数学任课教师：学号：姓名：------------------------------------------------------------------------------------------------------------------------本题9页，本页为第7页教务处试题编号：6.求A={1，2，3}上所有既是对称的，又是反对称的关系。解：五、证明题（本大题共3小题，每题10分，共30分）。1.请用命题逻辑的推理法则推导：{P→~Q，~P→R，R→~S}S→~Q证明：课程名称：离散数学任课教师：学号：姓名：------------------------------------------------------------------------------------------------------------------------本题9页，本页为第8页教务处试题编号：2.证明下面A上的关系是偏序关系，并画出Hasse图A={a,b,c,d,e},R={(a,b)，（a,c）,(a,d),(a,e),(b,e),(c,e),(d,e)}∪IA证明：3.证明：在有限群中周期为2的元素的个数必定为偶数证明：宁可累死在路上，也不能闲死在家里！宁可去碰壁，也不能面壁。是狼就要练好牙，是羊就要练好腿。什么是奋斗？奋斗就是每天很难，可一年一年却越来越容易。不奋斗就是每天都很容易，可一年一年越来越难。能干的人，不在情绪上计较，只在做事上认真；无能的人！不在做事上认真，只在情绪上计较。拼一个春夏秋冬！赢一个无悔人生！早安！—————献给所有努力的人.课程名称：离散数学任课教师：学号：姓名：------------------------------------------------------------------------------------------------------------------------本题9页，本页为第9页教务处试题编号：