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

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(

2、x): x是健壮的，则命题“没有一个国家级运动员不是健壮的”可符号化为 ( ) 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

3、.设Z为整数集，A为集合，A的幂集为P（A），、/ 为数的加、减、除运算，为集合的交运算，下列系统中是代数系统的有（ ）（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分

4、，答案写于后面答题纸中。）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. 如图所示

5、哈斯图中构成分配格的有 。6.群G其中为集合的对称差运算，对于1,2P(1,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具有什么

6、性质（指自反性、反自反性、对称性、反对称性、传递性） 求R2 求r(R),s(R),t(R) 4.(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 页 学号； 姓

7、名： 班级： 。密。封。线。3410799712685136.(8分)(3分)求图G的最小生成树(5分)设有如下有向图D= 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分)构造下面的推理证明：每个喜欢步行的人都不喜欢骑自行车。每个人或者喜欢骑自行车或者喜

8、欢乘汽车。有的人不喜欢乘汽车，所以有的人不喜欢步行。五、应用题（6分，答案写于后面答题纸中。）某次国际会议有8人参加，已知每人至少与其余7人中的4人有共同语言，问服务员能否将他们安排在同一张圆桌周围就坐，使每个人能与两边的人交谈，请说明依据。青岛理工大学试卷纸 共 5 页 第 3 页 学号； 姓名： 班级： 。密。封。线。 答题一、 选择题(每题2分，共20分)1B 2D 3C 4A 5A 6A 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分）

9、1、（6分）(pq)(rp)(pq)(rP)（合取范式）(pq(rr)(p(qq)r)(pqr)(pqr)(pqr)(pqr) (pqr)(pqr)(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,

10、r=0；p=0,q=0,r=1； p=0,q=1,r=0 p=0,q=1,r=1；p=1,q=0,r=0（1分）2（6分）(3分)(3分)（答案不唯一）3.（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. 图

11、G的最小生成树，如第6题答案图. 首先选对边(v1,v2)得1分，再选对每一条边得2分. v1 v2 v5 v6 v8 v7 v4 v 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关于运算是封闭

12、的。（1分） （2）任取a，b，cG，有 （a b）c（au1b）c（au1b）u1cau1b u1c a（b c）a（b u1c）au1（b u1c）au1b u1c 结合律成立。（2分） （3）单位元是u 因为auau1ua uauu1aa（1分） （4）a的逆元为ua1u 因为a（u a1u）au1u a1uu ，（u a1u）au a1u u1au （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分）将每个人与会者对