离散数学期末考试A卷.docx
《离散数学期末考试A卷.docx》由会员分享，可在线阅读，更多相关《离散数学期末考试A卷.docx（8页珍藏版）》请在冰点文库上搜索。
离散数学期末考试A卷
离散数学期末考试A卷
————————————————————————————————作者：
————————————————————————————————日期：
四川大学期末考试试题（闭卷）
（2014-2015学年第1学期）
课程号：
304039040课程名称：
离散数学（A卷）任课教师：
冯伟森石兵周莉陈瑜林兰
适用专业年级：
2013级计算机科学与技术学号：
姓名：
考试须知
四川大学学生参加由学校组织或由学校承办的各级各类考试，必须严格执行《四川大学考试工作管理办法》和《四川大学考场规则》。
有考试违纪作弊行为的，一律按照《四川大学学生考试违纪作弊处罚条例》进行处理。
四川大学各级各类考试的监考人员，必须严格执行《四川大学考试工作管理办法》、《四川大学考场规则》和《四川大学监考人员职责》。
有违反学校有关规定的，严格按照《四川大学教学事故认定及处理办法》进行处理。
题号
一（16%）
二（14%）
三（10%）
四（30%）
五（30%）
六
七
八
卷面成绩
得分
阅卷教师
阅卷时间
一、单项选择题（本大题共16小题，每小题1分，共16分）提示：
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。
错选、多选或未选均无分
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
1.令R:
小王吃饭；S：
小王看电视。
则语句“小王一边吃饭一边看电视”可以符号化为（）。
（A）R∨S；（B）R∧S；（C）R→S；（D）～R∨～S
2.令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或者y
6.设集合A={1，2，3}，则A上所有非等价关系数目为（）。
（A）512（B）507（C）508（D）506
7.下列关于有限集偏序集〈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上，定义代数系统，则关于“*”运算的下列的运算规则定义中，（）是可结合的？
（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）6
14.整数加群是一个无限循环群，其生成元是（）：
（A）-1；（B）0；（C）1；（D）-1和1两个生成元
15.在代数系统模7剩余类环
中，零因子的个数是（）：
（A）0个；（B）1个；（C）2个；（D）7个
16.下列哪些代数系统不是域（）：
（A）实数环；（B）有理数环；
（C）整数环；（D）模7剩余类环
二、多项选择题（本大题共7小题，每小题2分，共14分）提示：
在每小题列出的备选项中有不确定个数个选项是符合题目要求的，请将其代码填写在下表中。
错选、多选、少选或未选均无分。
1
2
3
4
5
6
7
8
9
10
1.下列语句中，（）是命题。
（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）是含幺半群，也是群；
（Ｃ）只要是半群，就必含有幂等元； （Ｄ）任何群中只含有一个幂等元。
6.非平凡无向树是（）。
（A）二部图（B）哈密顿图（C）平面图（D）连通图（E）欧拉图
7.下列关于格的说法正确的是（）。
（A）偏序格〈L,≤〉的Hasse图是连通图
（B）代数格〈L,∨,∧〉中，如果a∨b=a,那么a∧b=b
（C）偏序格〈L,≤〉中必有最大元，最小元
（D）偏序格〈L,≤〉中必有极大元，极小元
3、填空题（本大题共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）,（6,3）}。
那么，可以由此等价关系R对集合A产生的分划是：
。
5.素数阶群,其子群为。
四、计算题（本大题共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
解：
3.设是一个偏序集，集合A={1,2,3,4,6,9,24,54}，关系R是A上的整除关系。
（1）请画出该偏序关系的哈斯图；
（2）求集合A中的极大元；
（3）设集合A的子集合B={4,6,9}，求集合B的最小上界和最大下界。
解：
4.请利用可达矩阵求出下图中的所有强分图：
解：
5.请将下面的有序树转化为一棵二叉树。
解：
6.求A={1，2，3}上所有既是对称的，又是反对称的关系。
解：
5、证明题（本大题共3小题，每题10分，共30分）。
1.请用命题逻辑的推理法则推导：
{P→~Q，~P→R，R→~S}
S→~Q
证明：
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的元素的个数必定为偶数
证明：
升级会员 