离散数学南昌大学软件学院试卷(软工)(A)

2007 2008学年第一学期离散数学期末试卷（A）年级专业 班级 学号 姓名_题号一二三四总分得分适用年级专业：2006级软件工程专业试卷说明：闭卷考试，考试时间120分钟一、 单项选择题（共20小题，每小题1分，共20分）1下列语句中只有 不是命题。CA今年元旦会下雪。B1+1=10。 C嫦娥一号太棒了！ D嫦娥奔月的神话已成为现实。2pq的主合取范式是 。B A(pq)(pq) B(pq)(pq) C(pq)(pq) D(pq)(pq)3与p q等值的命题公式是 。D Apq Bpq Cpq Dpq4在一阶逻辑中使用的量词只有 个。B A1 B2 C3 D45xA(x) 。C A$xA(x) BxA(x) C$xA(x) D$xA(x)6若|A|=4，则|P(A)|= 。C A4 B8 C16 D647设A、B、C为任意集合，集合的对称差运算不具有的性质是 。D AAB = BA B(AB)C = B(AC) CAA = DAA = A8二元关系是 。B A两个集合的笛卡儿积 B序偶的集合 C映射的集合 D以上都不是9下面关于函数的叙述中正确的是 。DA函数一定是满射 B函数一定是单射 C函数不是满射就单射 D函数是特殊的关系10半群中的二元运算一定满足= 。B A交换律 B结合律 C分配律 D幂等律11环中有 个二元运算。B A一 B二 C三 D四12群与独异点的区别是 。C A满足交换律 B满足结合律 C每个元素都有逆元 D满足分配律13九阶轮图的点色数是 。BA2 B3 C4 D914设N、Q、Z、R分别表示非负整数集、有理数集、整数集和实数集，表示数的加法，则下面的代数系统中， 不是群。AA B C D15简单通路是没有 的通路。A A重复边 B重复顶点 C平行边 D环16设个体域为N（非负整数集），下列公式为真的是 。BA$y x (xy = 1) B$y x (xy = x) Cx $y (x+y=0) Dx $y (x y)17非平凡树一定是 。B A正则图 B二部图 C欧拉图 D哈密顿图18环中的 运算只要求满足 。B A交换律 B结合律 C分配律 D幂等律19集合A上的等价关系与 一 一 对应。B A集合A的子集 B集合A的划分 C集合A到A的双射 D集合A与A的单射20全序关系一定不是 。A A等价关系 B偏序关系 C线序关系 D整除关系二、填空题（共10题，每题2分，共20分）11 设S(x)：x是计算机学院的学生。L(x)：x学离散数学。则“计算机学院的学生都要学离散数学。”可符号化为 ： _ x(S(x)L(x) _。 12 设A=a,b,c，A上的等价关系R=, IA ，则商集A/R=_ a , b , c13设B=，则幂集P(B) = _ , 。 14xA(x) $yB(x,y)的前束范式是_u$v (A(u) B(x,v)或 x$y(A(x) B(u,y)15设集合A=0，1，则A上可定义的二元运算有_16_个。16设A=1，2，3，4，A上关系R=,IA ，则t(R)=_ , IA17设函数f：NN，f =x -1，函数h：NN，h(x)=x2+1，则复合函数foh (x) = _(x -1)2+118完全二部图Kr,s（rs）的最大度D(Kr,s) = _S_，最小度d(Kr,s)= _ r _。19设一棵树有4个2度顶点，3个3度顶点，其余顶点都是1度顶点，则该树有_5_片树叶。20命题公式(p(pq)的成假赋值是_00，01，10，11三、运算题（共5小题，每小题8分，共40分）21求命题公式(pq) (q r)的主析取范式，并指出其类型。解：(pq) (q r) (p q ) (q r) (p r) q (p ( q q ) r) ( p p ) q ( r r ) ) (p q r) (p q r) (p q r) (p q r) (p q r) (p q r) (p q r) (p q r) (p q r) (p q r) (p q r) 该公式是可满足式22设A=a,b,c,d,e,f， A上的偏序关系：R=, IA 画出该偏序关系的哈斯图，并求A的极大元、极小元、最大元和最小元。解：极大元为d、e、f；极小元为a；无最大元；最小元为a23设个体域D=a,b,c，消去一阶公式 x（F(x) $yG(y)）中的量词 ，并在下述解释下求其真值：F(a)= F(b)=1 , F(c)= 0，G(a)=1， G(b)=G(c)=0。 解：x（F(x) $yG(y)）$ xF(x) $yG(y)（F(a) F(b) F(c)）（G(a) G(b) G(c)）（1 1 0）（1 0 0） 1 1124画一棵叶带权为1、2、3、3、5、6、7的最优二元树T，并计算树权W(T)。解： W(T) = 7125设Z为整数集合，V=，*是二元运算，定义为： x*y=x+y-xy说明V是含幺半群而不是群。解：（1）*运算在Z上封闭：（2）*运算可结合，对任意a、b、cZa*(b*c) = a*(b+c-bc) = a+ b+c-bc -a(b+c-bc) = a+b+c-ab-ac-bc+abc(a*b)*c = (a+b-ab)*c = a+b-ab+c- (a+b-ab) c = a+b+c-ab-ac-bc+abc所以a*(b*c) =(a*b)*c（3）*运算的幺元是0（4）任意xZ，x*1=1*x=1，所以1是零元，它没有逆元。由上述可知，故是含幺半群而不是群。四、证明题（共3小题，共20分）26（10分）在一阶逻辑中构造下面推理的证明： 前提：x(F(x) G(x) ，x (G(x) R(x)，$xR(x)结论：$xF(x)（10分）证: $xR(x) 前提引入 R(c) EI x (G(x) R(x) 前提引入 G(c) R(c) UI G(c) 析取三段论 x(F(x) G(x) 前提引入 F(c) G(c) UI F(c) 拒取式 $xF(x) EG27（5分）证明，若非空集合A上的关系R和S是反对称的，则RS也是反对称的。证: 任取，xyRSRSRSRS。故RS是对称的。28（5分）若无向图G中恰有两个奇度顶点，证明这两个奇度顶点必连通。证: 用反证法。假设G中两个奇度顶点u和v不连通，则u和v分别处于G的两不同连通分支G1和G2中，因而G1和G2作为独立的图时，均只有一个奇度顶点，这是不可能的，故这两个奇度顶点必连通。2007 2008学年第一学期离散数学期末试卷（A）答 案适用年级专业：2006级软件工程专业试卷说明：闭卷考试，考试时间120分钟一、 单项选择题（共20小题，每小题1分，共20分）1C 2B 3D 4B 5C 6C 7D 8B 9D 10B11B 12C 13B 14A 15A 16B 17B 18B 19B 20A二、填空题（共10题，每题2分，共20分）11 x(S(x)L(x) 12 a , b , c13 , 14u$v (A(u) B(x,v)或 x$y(A(x) B(u,y) 15 16 16 , IA17 (x -1)2+1 18 s , r19 5 2000，01，10，11三、运算题（共5小题，每小题8分，共40分）21解：(pq) (q r) (p q ) (q r) (p r) q (p ( q q ) r) ( p p ) q ( r r ) ) (p q r) (p q r) (p q r) (p q r) (p q r) (p q r) (p q r) (p q r) (p q r) (p q r) (p q r) 该公式是可满足式22 解：极大元为d、e、f；极小元为a；无最大元；最小元为a23 解：x（F(x) $yG(y)）$ xF(x) $yG(y)（F(a) F(b) F(c)）（G(a) G(b) G(c)）（1 1 0）（1 0 0） 1 1124 解： W(T) = 7125 解：（1）*运算在Z上封闭：（2）*运算可结合，对任意a、b、cZa*(b*c) = a*(b+c-bc) = a+ b+c-bc -a(b+c-bc) = a+b+c-ab-ac-bc+abc(a*b)*c = (a+b-ab)*c = a+b-ab+c- (a+b-ab) c = a+b+c-ab-ac-bc+abc所以a*(b*c) =(a*b)*c（3）*运算的幺元是0（4）任意xZ，x*1=1*x=1，所以1是零元，它没有逆元。由上述可知，故是含幺半群而不是群。四、证明题（共3小题，共20分）26（10分）证: $xR(x) 前提引入 R(c) EI x (G(x) R(x) 前提引入 G(c) R(c) UI