n( r>
中原工学院
2009?2010学年第一学期I重修标识
08级计算机科学专业直散数t课程期末试卷
题号—*二三四五六七八九十总分
B卷
一、填空(每题4分，共20分)
1、设P:天下雨，Q:我骑自行车上班，将命题“只要天不下雨，我就骑自行车上班”符
号化为 ______________ o
2、在谓词逻辑屮，设是有理数，是整数，将命题“有的有理数是整
数”符号化为______________________ 。
3、设图G是6个顶点的连通图，总度数是24,则从图G中删除 _________ 边后，使之成为
树。
4、设4 = ｛1，2,3,4,5｝，〈P(A)，?〉是群，(其中/>(4)是A的幂集，十为集合的对称
差)，若方程｛1，2｝?X=｛3,4,5｝，贝ij X=____________ 。3、给定解释I如下：
(a)个体域D = 0,2｝，
(b)F(x，y)为F(l,l) = F(2,2) = l, F(l,2) = F(2,l) = 0 ,
则公式( )真值为真。
A. Vx3yF(x,y)
B. VWyF(x,)’)
C. D. 3A-VyF(x,y)
4、以下四组数( )能构成简单无向图的度数列。
A. (1,2,2,34,5)
B. (3,3,44,5,7)
C. (1,1,1,23,5,7)
D. (3,3,34,5,6)
5、对于下而的二元有序正则树，先根遍历的次序是( )。
A.ABCEFKDGIHJ
B.CEKFBG I JHDA
C.ABCFEKDGIIIJ
D.DGHIJABCFEK
5、设A = ,二元关系R = ｛
、a，
b、人b，a
、人a，c、人b，c
、人c，d、、，
三.(本题9分)设命题公式A的真值表如不，试写出命题公式A的主析取范式与主合取范式。
则该公式的成真赋值为()o
B. 011,100,101,111
D. 全体赋值
则Z(R)= _____________________________ 。
二、单项选择题(每题4分，共20分)
1、给定命题公式(pvd + r ,则该公式在全功能集｛-sv｝中的形式为( )o A. (pv^)vr
B. (-ipvg)vr
C. -i(p v^r) v r C. (p v-.r
2?给定命题公式p v A -ir), A.无
C. 010,100,101,110,111
n( r> 本题9分)
n( r>
本题8分）设是由a 生成的循环群，证明若“的阶力m ,
则^ ^与^ ^ +一同构。本题8分）
设G 是有打个结点m 条边的连通简单平面图，若n 2 3 ,则m 幺3 n -6。
中原工学院2009?2010学年第一学期| B卷08计算机科学专业离散数学课程期末试卷标准答案(即评分标准) 一、1. P —> Q； 2 . 3x(F(x) A C(X))； 3.7； 4 . {1,2,3,4,5}:
二、1. C; 2 . C ； 3 . A； 4 . A； 5 . C
三、解A = (-i p A-12A/?)V(-i PAeA/?)V(PA^2A/?)； --------------------------- 4分
A = (P V g V 7?) A(P V—ig V 7?)(—iP V g v-i/?) A(-iP v-i/? V /?) A(—iPv-ig v-i/?)
------------ 9分P4、证明因为具有自反性、对称性及传递性，所以，R是等价关系。% = {[1]，[2][3]}
..................... 9分五、解3%Vy3z(-iF(x, y) v Q(z) v /?(x))
=3xVj3z(-iP(x, y) v 2 (z) v /? (x)) ............................. 7 分1
树权为W) = 3x7 + 2x5 + 5x3 + 4x4 + 3x9 + 3x5 + 2x13 + 3x6 + 2x10 =
168 ------------- 9
分
七、首先将本题用权图来描述，于是求解此问题变成为求权图中的最优支撑树问题，然后按克鲁斯克尔算法，下图是求解最优支撑树的过程：
本试卷答案共2页，此页为A 卷第1页
八、证明作映射/:0 4 2，,:，/(6?)=［々］.若7=“"必有闪= >］，因为若?［//］，
则有 k-h = mq^r^Q^r 矛盾。/是满射，同时/还是单射，即如果a k a h ,则必有 因力如果［々］ = ［/!］，则k-h = mq,k = mq + h 故有 a k = a ,,tq+h = a h 证明当zi = 3,z7i = 2时上式显然成立，除此之外，若m>3,则每一个 2 次数不小于3,因此，2m>3r,r<-m,3 2 m + — m,故有 m < 3/? — 6。 3 对于尺5，/7 = 5,爪=10，若尺5是平而图，则它的每个而得次数至论得 m < 3n — 6 = 15 — 6 = 9 这是个矛盾，因而，火5不是平面图。 .............. 8分 同时又有 所以，〈0，。〉与〈2…,，+…,〉同构。 ................8分 本试卷答案共2页，此页为 九、 2 = 77 = m + r < Z2 -
相关主题
文本预览