学年学期 程名称 20 12 ~ 20 13 学年第 1 学期 离散数学A/B 考核方式 A/B卷 闭卷 （ A ）卷 1．公式?(p?q)与(p??q)?(?p?q)共同的成真赋值为 A． 00，01 B. 10,11 C. 10, 01 D. 00,11 2．取个体域为整数集，给定下列公式：
（1）?x?y(x?y?0) （2）?x?y(x?y?2y) （3）?x?y(x?y?2) （4）?x?y?z(x?y?z) （5）?x(x?y?x) 上面公式中，真命题有 个 A．2个 B. 3个 C. 4个 D. 5个
3. 设A为人类集合，R和S是A上的二元关系，R?{?x,y?|x是y的父亲}
S?{?x,y?|x是y的母亲}，则S?1R表示关系
A．{?x,y?|x是y的丈夫} B. {?x,y?|x是y的孙子或孙女} C. R?{?x,y?|x是y的祖父} D. R?{?x,y?|x是y的祖母}
4．一个无向图有4个结点，有 3个度数为2,3,3，则第4个结点度数不可能是 A．0 B. 1 C. 2 D. 4 5．有n个结点的无向完全图的边数为 A．n(n?1) B. n2 C. 2n D.
n(n?1) 26. 下图中既不是欧拉图，也不是哈密尔顿图的图是
7. 下面函数 是单射而非满射 A．f:R?R,B．f:Z?R,C．f:R?Z,D．f:R?R,?f(x)??x2?2x?1； f(x)?lnx；
f(x)?[x],[x]表示不大于x的最大整数；
f(x)?2x?1。
二、填空题（每空3分，共24分）
第1页，共3页
1． 判断命题公式(p?q)?p的公式类型 ；
2． 令R(x):x是实数，Q(x):x是有理数，将命题“并非每个实数都是有理数”一阶逻辑符号化 ； 3．令X?{x1,x2,,xm},Y?{y1,y2,,yn}，则从X到Y有 个不同的二元关系，有 个不同的函数；
4．设集合A?{1}，则A?P(A)= ；
5．谓词公式?xF(x)??yG(x,y)的前束范式为 ； 6.带权1,3,4,5,6的最优二元树T对应的最佳前缀码是 ；
?0?1?7. 设图D??V,E?，V?{v1,v2,v3,v4}，若D的邻接矩阵为A??1??1则从v3到v4的长度为2的通路数目为 条。
101001001??1?，0??0?三、（8分）要设计一个灯泡和3个开关A、B、C组成的电路，要求在且仅在下述4种情况下灯亮：（1）C的扳键向上，A，B的扳键向下；
（2）A的扳键向上， B,C的扳键向下； (3) B,C的扳键向上，A的扳键向下； (4) A,B的扳键向上，C的扳键向下；
设p：A扳键向上，q：B扳键向上，r：C扳键向上，公式G表示灯亮。 求G的主析取范式和主合取范式； 四、（8分）某公司要选派员工去广州出差。由于工作需要，选派时要满足以下条件： 派小李或小张去出差。如果派小李去，则小赵要加班。如果派小张去，小王也得去。小赵没有加班。问公司如何派遣？（ 用命题逻辑推理理论解题，必须有推理过程）。
五、（共20分）设集合A?{a,b,c,d}，R为A上的二元关系，且
R?{?b,c?,?a,c?,?c,d?,?d,d?}，
1. 求R的关系矩阵；（2分） 2. 求R的性质；（2分）
第2页，共3页
3. 求R的自反闭包r(R) ,对称闭包s(R) ，传递闭包t（R）；（8分）
4. 在关系R中添加最少的有序对使其成为A上的偏序关系，并画出其哈斯图。（6分）
六、（6分）设N是自然数集合，定义N上的二元关系R：
?x,y?N,?x,y??R?x?y是偶数 1．证明R是一个等价关系； 2. 求关系R的等价类。
七、（7分）设集合A?{a,b,c,d,e}，R为A上的 偏序关系，其哈斯图为右图所示， 1. 有序对, ,
a b c d e 2. 设B={ a, c, d},求B的最大元、最小元、 极大元、极小元、上界和下界。
八、（8分）已知无向赋权图G=
1 v27 v42 2 5 3 6 v14 v6v31 v5 1. 用Dijkstra算法求从v1到v5的最短路径；
2. 假设图中点v3是邮局，其他结点为投递点，边为投递点间的路线，边上的权代表路线的长度。求邮递员的最佳投递路线（即权和最小的路线）。
第3页，共3页