离散数学期末试卷(A)XXXX大学XX学院2007 ～2008学年第一学期《离散数学》期末试卷年级专业题号得分适用年级专业：2006级软件工程专业试卷说明：闭卷考试，考试时间120分钟一、单项选择题1．下列语句中只有不是命题。
C A．今年元旦会下雪。
B．1+1=10。
C．嫦娥一号太棒了！D．嫦娥奔月的神话已成为现实。
2．p?q 的主合取范式是。
B A．(p?q)?(p??q)B．(p??q)?(?p?q) C．(p?q)?(?p??q)D．(p?q)?(?p?q) 3．与p? q等值的命题公式是。
D A．?p?q B．p??q C．p??q D．?p?q 4．在一阶逻辑中使用的量词只有个。
B A．1B．2 C．3D．4 5．??xA(x)?。
C A．??xA(x) B．?x?A(x) C．?x?A(x)D．?xA(x) 6．若|A|=4，则|P(A)|=。
C A．4B．8C．16 D．64 7．设A、B、C为任意集合，集合的对称差运算不具有的性质是。
D A．A?B = B?A B．(A?B)?C = B?(A?C) 班级学号一二三姓名____________ 四总分C．A?A = ?D．A?A = 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 A．2B．3 C．4D．9 14．设N、Q、Z、R分别表示非负整数集、有理数集、整数集和实数集，＋表示数的加法，则下面的代数系统中，不是群。
A A．B．C．D．15．简单通路是没有的通路。
A A．重复边B．重复顶点C．平行边D．环16．设个体域为N，下列公式为真的是。
B A．?y ?x (xy = 1)B．?y ?x (xy = x) C．?x ?y (x+y=0)D．?x ?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．整除关系二、填空题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) = ___________ {?,{?}} 。
14．?xA(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)=__ {,,,} ?IA 17．设函数f：N?N，f =x -1，函数h：N?N，h(x)=x2+1，则复合函数f?h (x) = _______(x -1)2+118．完全二部图Kr,s的最大度?(Kr,s) = ______S____，最小度?(Kr,s)= _____ r ___。
19．设一棵树有4个2度顶点，3个3度顶点，其余顶点都是1度顶点，则该树有_______5___片树叶。
20．命题公式?(p?(p?q))的成假赋值是__00，01，10，11 三、运算题21．求命题公式?(p??q) ? (q ? r)的主析取范式，并指出其类型。
解：?(p??q) ? (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(a)= F(b)=1 , F(c)= 0，G(a)=1，G(b)=G(c)=0。
解：?x?? xF(x) ??yG(y) ?? ??? 1 ?1?1 24．画一棵叶带权为1、2、3、3、5、6、7的最优二元树T，并计算树权W(T)。
解：W(T) = 71 25．设Z为整数集合，V=，*是二元运算，定义为：x*y=x+y-xy 说明V是含幺半群而不是群。
解：*运算在Z上封闭：*运算可结合，对任意a、b、c?Z 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 *运算的幺元是0 任意x?Z，x*1=1*x=1，所以1是零元，它没有逆元。
上述可知，故是含幺半群而不是群。
四、证明题26．在一阶逻辑中构造下面推理的证明：前提：?x(F(x) ??G(x)) ，?x (G(x) ? R(x))，?x?R(x) 结论：?x?F(x) 证:①?x?R(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)⑤⑦拒取式⑨?x?F(x)⑧EG 27．证明，若非空集合A上的关系R和S是反对称的，则R?S也是反对称的。
证: 任取，x≠y ?R?S??R??S??R??S??R?S。
故R?S是对称的。
28．若无向图G中恰有两个奇度顶点，证明这两个奇度顶点必连通。
证: 用反证法。
假设G中两个奇度顶点u和v不连通，则u和v分别处于G的两不同连通分支G1和G2中，因而G1和G2作为独立的图时，均只有一个奇度顶点，这是不可能的，故这两个奇度顶点必连通。
2007 ～2008学年第一学期《离散数学》期末试卷答案适用年级专业：2006级软件工程专业试卷说明：闭卷考试，考试时间120分钟一、单项选择题1C 2B 3D 4B 5C 6C 7D 8B 9D 10B 11B 12C 13B 14A 15A 16B 17B 18B 19B 20A 二、填空题11．?x(S(x)?L(x))12．{{a , b} , {c}} 13．{?,{?}}14．?u?v (A(u) ?B(x,v))或?x?y(A(x) ?B(u,y)) 15．16 16．{,,,} ?IA 17．(x -1)2+118．s , r 19．520．00，01，10，11 三、运算题21．解：?(p??q) ? (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 23．解：?x?? xF(x) ??yG(y) ?? ??? 1 ?1?1 24．解：W(T) = 71 25．解：*运算在Z上封闭：*运算可结合，对任意a、b、c?Z 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 *运算的幺元是0 任意x?Z，x*1=1*x=1，所以1是零元，它没有逆元。
上述可知，故是含幺半群而不是群。
四、证明题26证: ①?x?R(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)⑤⑦拒取式⑨?x?F(x)⑧EG 27证: 任取，x≠y ?R?S??R??S??R??S??R?S。
故R?S是对称的。
28 证: 用反证法。
假设G中两个奇度顶点u和v不连通，则u和v分别处于G的两不同连通分支G1和G2中，因而G1和G2作为独立的图时，均只有一个奇度顶点，这是不可能的，故这两个奇度顶点必连通。