离散考试原题青岛理工大学.doc

《离散考试原题青岛理工大学.doc》由会员分享，可在线阅读，更多相关《离散考试原题青岛理工大学.doc（8页珍藏版）》请在三一文库上搜索。

1、 教师试做时间70出题教师楠取题时间审核教研室主任出题单位计算机使用班级计071075考试日期2008.12.26院（部）主任考试成绩期望值70印刷份数规定完成时间110交教务科印刷日期 学号： ： 班级：。密。封。线。计算机科学与技术专业2年级计算071075班 20082009学年第1学期 离散数学课试卷 试卷类型：A卷题号一二三四五六七八九十总成绩得分阅卷人一、单项选择题(每小题2分，共20分，答案写于后面答题纸中。)1. 命题公式（pq）q为 ( )(A) 矛盾式 (B) 可满足式 (C) 重言式 (D) 合取式2. 设C(x): x是国家级运动员，G(x): x是健壮的，则命题“没有

2、一个国家级运动员不是健壮的”可符号化为 ( )3.设集合A=1,2,3, 4,5, 6,7,8，则下式为真的是( )(A) 1A (B) 1,2, 3A(C) 4,5A (D) A4. 设A1,2,B=a,b,c,C=c,d, 则A(BC)= ( )(A) , (B) , (C) , (D) ,5.在布尔代数L中，表达式(ab)(abc)(bc)的等价式是（）（A）b(ac)（B）(ac)(ab)（C）(ab)(abc) (bc)（D）(bc)(ac)6.设i是虚数，是复数乘法运算，则G=是群，下列是G的子群是（ ）（A） （B） （C） （D） 7.设Z为整数集，A为集合，A的幂集为P（A）

3、/为数的加、减、除运算，为集合的交运算，下列系统中是代数系统的有（ ）（A） （B）（C）（D）。8.下列各代数系统不含有零元的是（）（A）,Q是全体有理数集，*是数的乘法运算（B）, Mn(R)是全体n阶实矩阵集合，*是矩阵乘法运算（C）, Z是整数集，*定义为x*y=xy,x,yZ（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:小王

4、迟到。命题“除非天下大雨，否则小王不会迟到”的符号化形式为。理工大学试卷纸 共 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,2P(1

5、2,3)的生成子群是。7.，。8.G为4阶无向连通简单图，则G中至多有棵非同构的生成树。9.若n阶无向简单图G的，则G为。10.无向图G中有8条边，1个1度顶点，2个2度顶点，1个5度顶点，其余顶点的度数均为3，则G中3度顶点的个数。三、计算或简答题(共36分，答案写于后面答题纸中。) 1.(6分)求下面公式的主析取式和主合取式并写出成真赋值和成假赋值(pq)(rp)2. (6分) (3分)设个体域,消去下面公式的量词 (3分)求下面公式的前束式3.(6分) R的关系图如图所示1234说明R具有什么性质（指自反性、反自反性、对称性、反对称性、传递性）求R2求r(R),s(R),t(R)4.(

6、6分)设为偏序集，其中A1,2,3,4,6,9,24,54,R是A上的整除关系画出的哈斯图求A中的极大元，极小元，最大元，最小元求B4,6,9的上界，上确界，下界，下确界5.（4分）设代数系统V=的运算表如下表所列 *a b c d *a b c d *a b c da b c da b c db c b dc a b cd a c c说明*运算是否满足交换律、结合律、幂等律*运算的单位元和零元（如果存在）写出所有可逆元素的逆元理工大学试卷纸 共 5 页 第 2 页 学号； ： 班级： 。密。封。线。3410799712685136.(8分)(3分)求图G的最小生成树(5分)设有如下有向图D=

7、 1)求D的邻接矩阵；2)D中v1到v4的长度为4 的通路有多少条？3) D中经过v1的长度为3 的回路有多少条？4)D中长度不超过4 的通路有多少条？其中有多少条回路？V1V4V2V3四、证明题（共18分，答案写于后面答题纸中。）1.(6分)对任意集合A,B，证明：若AA=BB，则A=B。2.(6分)设u是群G中任意固定元素，如下定义新运算：有abau1b证明：G关于运算构成群3.(6分)构造下面的推理证明：每个喜欢步行的人都不喜欢骑自行车。每个人或者喜欢骑自行车或者喜欢乘汽车。有的人不喜欢乘汽车，所以有的人不喜欢步行。五、应用题（6分，答案写于后面答题纸中。）某次国际会议有8人参加，已知每

8、人至少与其余7人中的4人有共同语言，问服务员能否将他们安排在同一圆桌周围就坐，使每个人能与两边的人交谈，请说明依据。理工大学试卷纸 共 5 页 第 3 页 学号； ： 班级： 。密。封。线。答题一、 选择题(每题2分，共20分)1B 2D3C4A5A6A 7D 8D 9D 10C二、 填空题(每题2分，共20分)1、2、3、1,3,5, 2,44、5、L2 L36、7、(15634)(2)8、29、无向完全图Kn10、2三、 计算题或简答题（共36分）1、（6分）(pq)(rp)(pq)(rP)（合取式）(pq(rr)(p(qq)r)(pqr)(pqr)(pqr)(pqr) (pqr)(pqr

9、)(pqr)（主合取式） (2分)m5m6m7或(1分)M0M1M2M3M4（主析取式）或 (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.（

10、6分）不具有任何性质（1分）R2(1分) 或r(R)=(1分)或s(R)=(1分)或t(R)=(2分)4（6分）123 669424546的哈斯图（2分）A中的极大元为24 54，极小元1，最大元 无，最小元1 （2分）B4,6,9的上界 无，上确界 无，下界1，下确界1 （2分）5.（4分）不满足交换律、不满足结合律、不满足幂等律 （2分）*运算的单位元 a 零元 无 （1分）a1a （1分）3477685 6. 图G的最小生成树，如第6题答案图. 首先选对边(v1,v2)得1分，再选对每一条边得2分. v1 v2 v5 v6 v8 v7v4v1）A=，A2=A3=，A4=（2分）2）G中v

11、1到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，cG，有 （a b）c（au1b）c（au1b）u1cau1bu1c a（b c）a（bu1c）au1（bu1c）au1bu1c 结合律成立。（2分） （

12、3）单位元是u 因为auau1ua uauu1aa（1分） （4）a的逆元为ua1u 因为a（ua1u）au1ua1uu ，（ua1u）aua1uu1au （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。即图中任两个不相邻的顶点的度数大于等于8n1，即顶点数加1。（2分）故这个图是一个哈密尔顿图，从而存在哈密尔顿回路。任取一条哈密尔顿回路，按回路经过的顶点的次序安排对应的人的座位，就可满足要求。（2分）理工大学试卷纸 共 5 页 第 4 页8 / 8