2022年2022年离散数学期末试卷 2.pdf

XXXX 大学 XX 学院2007 2008 学年第一学期离散数学期末试卷（A）年级专业班级学号姓名 _题号一二三四总分得分适用年级专业：2006 级软件工程专业试卷说明：闭卷考试，考试时间120 分钟一、单项选择题（共20 小题，每小题1 分，共 20 分）1下列语句中只有不是命题。C A今年元旦会下雪。B1+1=10。C嫦娥一号太棒了！D嫦娥奔月的神话已成为现实。2pq 的主合取范式是。B A(p q)(pq)B(pq)(p q)C(p q)(pq)D(p q)(p q)3与 p q 等值的命题公式是。D Apq Bpq Cpq Dpq 4在一阶逻辑中使用的量词只有个。B A1 B2 C3 D4 5xA(x)。C AxA(x)BxA(x)C xA(x)D xA(x)6若|A|=4，则|P(A)|=。C A4 B8 C16 D64 7设 A、B、C 为任意集合，集合的对称差运算不具有的性质是。D AAB=BA B(AB)C=B(AC)名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 9 页 -CAA=DAA=A 8二元关系是。B A两个集合的笛卡儿积B序偶的集合C映射的集合D以上都不是9下面关于函数的叙述中正确的是。D A函数一定是满射B函数一定是单射C函数不是满射就单射D函数是特殊的关系10半群中的二元运算一定满足=。B A交换律B结合律C分配律D幂等律11环中有个二元运算。B A一B二C三D四12群与独异点的区别是。C A满足交换律B满足结合律C每个元素都有逆元D满足分配律13九阶轮图的点色数是。B A2 B3 C4 D 9 14设 N、Q、Z、R 分别表示非负整数集、有理数集、整数集和实数集，表示数的加法，则下面的代数系统中，不是群。AA B C D 15简单通路是没有的通路。A A重复边B重复顶点C平行边D环16设个体域为N（非负整数集），下列公式为真的是。B A 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 的单射名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 9 页 -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,c 13设 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，则复合函数f h(x)=_(x-1)2+1 18完全二部图Kr,s（rs）的最大度(Kr,s)=_S_，最小度(Kr,s)=_ r _。19设一棵树有4 个 2 度顶点，3 个 3 度顶点，其余顶点都是1 度顶点，则该树有 _5_ 片树叶。20命题公式(p(pq)的成假赋值是_00，01，10，11 名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 9 页 -三、运算题（共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；无最大元；最小元为a 23设个体域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 11 24画一棵叶带权为1、2、3、3、5、6、7 的最优二元树T，并计算树权W(T)。名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 9 页 -解：W(T)=71 25设 Z 为整数集合，V=，*是二元运算，定义为：x*y=x+y-xy 说明 V 是含幺半群而不是群。解：（1）*运算在 Z 上封闭：（2）*运算可结合，对任意a、b、cZ a*(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)EG 27（5 分）证明，若非空集合A 上的关系R 和 S 是反对称的，则RS 也是反对称的。名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 9 页 -证:任取 ，xy RSR SRSRS。故 RS 是对称的。28（5 分）若无向图G 中恰有两个奇度顶点，证明这两个奇度顶点必连通。证:用反证法。假设G 中两个奇度顶点u 和 v 不连通，则u 和 v 分别处于G 的两不同连通分支G1和 G2中，因而G1和 G2作为独立的图时，均只有一个奇度顶点，这是不可能的，故这两个奇度顶点必连通。名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 9 页 -2007 2008 学年第一学期离散数学期末试卷（A）答案适用年级专业：2006 级软件工程专业试卷说明：闭卷考试，考试时间120 分钟一、单项选择题（共20 小题，每小题1 分，共 20 分）1C 2B 3D 4B 5C6C 7D 8B 9D 10B11B 12C 13B 14A 15A 16B 17B 18 B 19 B 20A 二、填空题（共10 题，每题 2 分，共 20 分）11x(S(x)L(x)12 a,b,c 13,14u v(A(u)B(x,v)或x y(A(x)B(u,y)15 16 16,IA17(x-1)2+1 18 s,r 19 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；无最大元；最小元为a 名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 9 页 -23 解：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 11 24 解：W(T)=71 25 解：（1）*运算在 Z 上封闭：（2）*运算可结合，对任意a、b、cZ a*(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 G(c)析取三段论x(F(x)G(x)前提引入 F(c)G(c)UI F(c)拒取式xF(x)EG 27（5 分）证:任取 ，xy RSR SRSRS。故 RS 是对称的。28（5 分）证:用反证法。假设G 中两个奇度顶点u 和 v 不连通，则u 和 v 分别处于G 的两不同连通分支G1和 G2中，因而G1和 G2作为独立的图时，均只有一个奇度顶点，这是不可能的，故这两个奇度顶点必连通。名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 9 页 -名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 9 页 -