……………………………………………线………………………………………订………………………………………装…………………………………………………攀枝花学院考试试卷 2013～2014学年度第二学期
《离散数学》试卷（A卷）
适用年级专业：2012级网络工程本科班 、2012级软件工程卓越工程师试点本科班
考 试 形 式：（ ）开卷、（ √ ）闭卷
二级学院： 行政班级： 学 号： 教 学 班： 任课教师： 姓 名： 注：本试卷共四个大题，学生在答题前，请将以上内容完整、准确填写，填写不清者，成绩不计。
题号 得分
得分 阅卷人 一 二 三 总分 统分人 一、选择题（每题 3 分，共 15 分）
1、下列选项不是联结词完备集的是（ ）。
A．{?} B．{?} C．{?,?,?} D．{?,?,?} 2、设G??Z8,??是模8的整数加群，则下列选项不是G的生成元的是（ ）。 A．1 B．2 C．3 D．5
3、设公式A(x)含自由出现的个体变项x，B不含x的出现，则下列一阶逻辑等值式正确的是（ ）。 A．?x(A(x)?B)??xA(x)?B B．?x(A(x)?B)??xA(x)?B C．?x(A(x)?B)??xA(x)?B D．B??xA(x)??x(B?A(x)) 4、设集合A?{a,b,c}，下列选项为集合A的划分的是（ ）。 A．?1?{{a,{a}},{b,c}} B．?2?{{a,b},{c}} C．?3?{{a},{a,b,c}} D．?4?{?,{a,b},{c}} 5、图1给出了4个偏序集的哈斯图，其中是格的选项为（ ）。
第 1 页 共 4 页
A B C D
图1 哈斯图
得分 阅卷人 二、填空题（每题 3 分，共 15分）
1、公式(p?q)?p的成真赋值为： 。 2、关系的闭包包括： 。
3、图2给出了一个关系图，写出该图具有的关系的性质： 。
图2 关系图
4、公式?xF(x)??xG(x)的前束范式为： 。 5、设R?{?1,2?,?1,3?,?2,2?,?2,4?,?3,2?}，则R[{3}]? 。 得分 阅卷人 三、解答、证明题（每题10分，共70分）
1、求公式(p?q)?(?p?r)?(q?r)的主析取范式（极小项的成真赋值和名
称分别如下：000 m0；001 m1；010 m2；011 m3；100 m4；101 m5；110 m6；111 m7）。
第 2 页 共 4 页
2、在自然推理系统P中构造下面推理的证明。 前提：p?(q?r)，?s?p，q 结论：s?r
3、设A?{1,2,3,4}，R为A?A上的二元关系，??a,b?,?c,d??A?A，
?a,b?R?c,d??a?b?c?d
（1）证明R为等价关系； （2）求R导出的划分。
4、画出下面偏序集?A,R??的哈斯图，并找出A的极大元、极小元、最大元和最小元。
A?{a,b,c,d,e,f}，R??{?a,d?,?a,c?,?a,b?,?a,e?,?b,e?,?c,e?,d,e?}IA。
5、求由图3所示的2叉树产生的二元前缀码。
图3 2叉树
第 3 页 共 4 页
6、设Z为整数集合，在Z上定义二元运算如下：
?x,y?Z，xy?x?y?1
验证?Z,?是一个群。
7、用Dijkstra标号法求下图从顶点v1到其余各顶点的最短路径和距离。
图4
第 4 页 共 4 页