离散考试原题青岛理工大学.doc
《离散考试原题青岛理工大学.doc》由会员分享，可在线阅读，更多相关《离散考试原题青岛理工大学.doc（7页珍藏版）》请在冰点文库上搜索。
教师试做时间
70
出题教师
张楠
取题时间
审核
教研室主任
出题单位
计算机
使用班级
计071~075
考试日期
2008.12.26
院（部）主任
考试成绩期望值
70
印刷份数
规定完成时间
110
交教务科印刷日期
学号：
姓名：
班级：
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
密。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
封。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
线。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
计算机科学与技术专业2年级计算071~075班2008~2009学年第1学期《离散数学》课试卷试卷类型：
A卷
题号
一
二
三
四
五
六
七
八
九
十
总成绩
得分
阅卷人
一、单项选择题（每小题2分，共20分，答案写于后面答题纸中。
）
1.命题公式（p∨q）→q为（）
（A）矛盾式 （B）可满足式（C）重言式 （D）合取范式
2.设C（x）:
x是国家级运动员，G（x）:
x是健壮的，则命题“没有一个国家级运动员不是健壮的”可符号化为（）
3.设集合A={{1,2,3},{4,5},{6,7,8}}，则下式为真的是（）
（A）1ÎA（B）{1,2,3}ÍA
（C）{{4,5}}ÌA（D）ÆÎA
4.设A＝{1,2},B={a,b,c},C={c,d},则A×（BÇC）=（）
（A）{<1,c>,<2,c>}（B）{,<2,c>}（C）{,}（D）{<1,c>,}
5.在布尔代数L中，表达式（a∧b）∨（a∧b∧c）∨（b∧c）的等价式是（）
（A）b∧（a∨c）
（B）（a∧c）∨（a∧b）
（C）（a∨b）∧（a∨b∨c）∧（b∨c）
（D）（b∨c）∧（a∨c）
6.设i是虚数，·是复数乘法运算，则G=<{1,-1,i,-i},·>是群，下列是G的子群是（）
（A）<{1},·>
（B）<{-1},·>
（C）<{i},·>
（D）<{-i},·>
7.设Z为整数集，A为集合，A的幂集为P（A），＋、－、/为数的加、减、除运算，∩为集合的交运算，下列系统中是代数系统的有（）
（A）（B）（C）（D）。
8.下列各代数系统不含有零元的是（）
（A）,Q是全体有理数集，*是数的乘法运算
（B）,Mn（R）是全体n阶实矩阵集合，*是矩阵乘法运算
（C）,Z是整数集，*定义为x*y=xy,x,y∈Z
（D）,Z是整数集，+是数的加法运算
9.设G是连通简单平面图，G中有11个顶点5个面，则G中的边是（）
（A）10（B）12（C）16（D）14
10.下列图形中为欧拉图的是（）
（A）
（B）
（C）
（D）
二、填空题（每题2分，共20分，答案写于后面答题纸中。
）
1.令p:
天下大雨，q:
小王迟到。
命题“除非天下大雨，否则小王不会迟到”的符号化形式为。
青岛理工大学试卷纸共5页第1页
试题要求:
1.试题后标注本题得分;2.试卷应附有评卷用标准答案,并有每题每步得分标准;3.试卷必须提前一周送考试中心;4.考试前到指定地点领取试卷；5.考生不得拆散试卷，否则试卷无效。
学号；姓名：
班级：
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
密。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
封。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
线。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
2.F（x）:
x是火车，G（y）:
y是汽车，H（x,y）:
x比y快。
命题“说火车都比汽车快是不对的”的符号化形式为。
3.R为A={1,2,3,4,5}上的关系，则R导出的A的划分是。
4.，P（A）=。
5.如图所示哈斯图中构成分配格的有。
6.群G＝其中⊕为集合的对称差运算，对于{1,2}∈P（{1,2,3}）的生成子群<{1,2}>是。
7.，，。
8.G为4阶无向连通简单图，则G中至多有棵非同构的生成树。
9.若n阶无向简单图G的，则G为。
10.无向图G中有8条边，1个1度顶点，2个2度顶点，1个5度顶点，其余顶点的度数均为3，则G中3度顶点的个数。
三、 计算或简答题（共36分，答案写于后面答题纸中。
）
1.（6分）求下面公式的主析取范式和主合取范式并写出成真赋值和成假赋值
（p→q）（rp）
2.（6分）①（3分）设个体域,消去下面公式的量词
②（3分）求下面公式的前束范式
3.（6分）R的关系图如图所示
1
2
3
4
①说明R具有什么性质（指自反性、反自反性、对称性、反对称性、传递性）
②求R2
③求r（R）,s（R）,t（R）
4.（6分）设为偏序集，其中A＝{1,2,3,4,6,9,24,54},R是A上的整除关系
①画出的哈斯图
②求A中的极大元，极小元，最大元，最小元
③求B＝{4,6,9}的上界，上确界，下界，下确界
5.（4分）设代数系统V=的运算表如下表所列
*
abcd
*
abcd
*
abcd
abcd
abcd
bcbd
cabc
dacc
①说明*运算是否满足交换律、结合律、幂等律
②*运算的单位元和零元（如果存在）
③写出所有可逆元素的逆元
青岛理工大学试卷纸共5页第2页
学号；姓名：
班级：
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
密。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
封。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
线。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
3
4
10
7
9
9
7
12
6
8
5
13
6.（8分）①（3分）求图G的最小生成树
②（5分）设有如下有向图D=1）求D的邻接矩阵；2）D中v1到v4的长度为4的通路有多少条？
3）D中经过v1的长度为3的
回路有多少条？
4）D中长度不超过4的通路有多少条？
其中有多少条回路？
V1
V4
V2
V3
四、证明题（共18分，答案写于后面答题纸中。
）
1.（6分）对任意集合A,B，证明：
若AA=BB，则A=B。
2.（6分）设u是群G中任意固定元素，如下定义新运算：
有a•b＝au－1b证明：
G关于•运算构成群
3.（6分）构造下面的推理证明：
每个喜欢步行的人都不喜欢骑自行车。
每个人或者喜欢骑自行车或者喜欢乘汽车。
有的人不喜欢乘汽车，所以有的人不喜欢步行。
五、应用题（6分，答案写于后面答题纸中。
）
某次国际会议有8人参加，已知每人至少与其余7人中的4人有共同语言，问服务员能否将他们安排在同一张圆桌周围就坐，使每个人能与两边的人交谈，请说明依据。
青岛理工大学试卷纸共5页第3页
学号；姓名：
班级：
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
密。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
封。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
线。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
答题
一、选择题（每题2分，共20分）
1B2D3C4A5A6A7D8D9D10C
二、填空题（每题2分，共20分）
1、
2、
3、{{1,3,5},{2,4}}
4、
5、L2L3
6、
7、（15634）
（2）
8、2
9、无向完全图Kn
10、2
三、计算题或简答题（共36分）
1、（6分）
（p→q）（rp）
（pq）（rP）（合取范式）
（pq（rr））（p（qq））r）
（pqr）（pqr）（pqr）（pqr）
（pqr）（pqr）（pqr）（主合取范式）（2分）
m5∨m6∨m7或（1分）
M0∧M1∧M2∧M3∧M4（主析取范式）或∏（0,1,2,3,4）（1分）
所有成真赋值为：
101，110，111或m5，m6，m7，或M5,M6,M7或p=1,q=0,r=1；p=1,q=1,r=0；p=1,q=1,r=1（1分）
所有成假赋值为：
000，001，010，011，100或m0，m1，m2，m3，m4，或M0,M1,M2，M3,M4或p=0,q=0,r=0；p=0,q=0,r=1；p=0,q=1,r=0p=0,q=1,r=1；p=1,q=0,r=0（1分）
2．（6分）
①（3分）
②（3分）
（答案不唯一）
3.（6分）
①不具有任何性质（1分）
②R2＝{<1,1><1,2><1,3><1,4><2,2><2,4><3,3><3,4>}（1分）
③或r（R）={<1,1><1,3><1,4><2,2><2,3><2,4><3,2><3,3><3,4><4,4>}（1分）
或s（R）={<1,1><1,3><1,4><2,3><2,4><3,1><3,2><3,4><4,1><4,2><4,3>}（1分）
或t（R）={<1,1><1,3><1,4><1,4><2,2><2,3><2,4><3,2><3,3><3,4><4,4>}（2分）
4．（6分）
1
2
3
66
9
4
24
54
6
①的哈斯图（2分）②A中的极大元为2454，极小元1，最大元无，最小元1（2分）
③B＝{4,6,9}的上界无，上确界无，下界1，下确界1（2分）
5.（4分）①不满足交换律、不满足结合律、不满足幂等律（2分）
②*运算的单位元a零元无（1分）
③a－1＝a（1分）
3
4
7
7
6
8
5
6.①图G的最小生成树，如第6题答案图.
首先选对边（v1,v2）得1分，再选对每一条边得2分.
v1v2
v5v6
v8v7
v4v
②1）A=，A2=A3=，A4=（2分）
2）G中v1到v4的长度为4的通路有4条；（1分）
3）G中经过v1的长度为3的回路有3条；（1分）
4）G中长度不超过4的通路有72条，其中有19条回路。
（1分）
四、证明题（共18分）
1.（6分）若B=，则BB=。
从而AA=。
故A=。
从而B=A。
（2分）
若B，则BB。
从而AA。
（1分）
对,BB。
因为AA=BB，则A。
从而xA。
故BA。
（2分）
同理可证，AB。
故B=A。
（1分）
2.（6分）
（1）易见G关于•运算是封闭的。
（1分）
（2）任取a，b，c∈G，有
（a•b）•c＝（au－1b）•c＝（au－1b）u－1c＝au－1bu－1c
a•（b•c）＝a•（bu－1c）＝au－1（bu－1c）＝au－1bu－1c
结合律成立。
（2分）
（3）单位元是u
因为a•u＝au－1u＝au•a＝uu－1a＝a（1分）
（4）a的逆元为ua－1u
因为a•（ua－1u）＝au－1ua－1u＝u，（ua－1u）•a＝ua－1uu－1a＝u（2分）
3.设喜欢步行，喜欢骑自行车，喜欢乘汽车。
前提：
，，
结论：
（给出问题的谓词表示得2分）
证明：
（1）前提引入
（2）
（1）UI规则
（3）前提引入
（4）（3）UI规则（1分）
（5）（3）（4）析取三段论（1分）
（6）前提引入
（7）（6）UI规则
（8）（5）（7）拒取式（1分）
（9）（8）UG（1分）
五、应用题（6分）
将每个人与会者对应成相应的顶点，若两人有共同语言，则对应的两个顶点间连上一条无向边，作出一个简单无向图。
（2分）由已知，图中每个顶点的度数都大于等于4。
即图中任两个不相邻的顶点的度数大于等于8＝n＋1，即顶点数加1。
（2分）故这个图是一个哈密尔顿图，从而存在哈密尔顿回路。
任取一条哈密尔顿回路，按回路经过的顶点的次序安排对应的人的座位，就可满足要求。
（2分）
青岛理工大学试卷纸共5页第4页
升级会员 