XXXX大学XX学院
2007 ～ 2008学年第一学期《离散数学》期末试卷（A）
年级专业
题号 得分 适用年级专业：2006级软件工程专业 试卷说明：闭卷考试，考试时间120分钟
一、单项选择题（共20小题，每小题1分，共20分）
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．1 B．2 C．3 D．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．4 B．8 C．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．2 B．3 C．4 D．9
14．设N、Q、Z、R分别表示非负整数集、有理数集、整数集和实数集，＋表示数的加法，则下面的代数系统中， 不是群。A
A． C．< Z ，＋> 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．环
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={,
则商集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={<1,3>,<3,1>,<4,1>}?IA ， 则t(R)=__ {<1,3>,<3,1>,<4,1>,<4,3>} ?IA
17．设函数f：N?N，f =x -1，函数h：N?N，h(x)=x2+1，
则复合函数f?h (x) = _______(x -1)2+1
18．完全二部图Kr,s（r 最小度?(Kr,s)= _____ r ___。 19．设一棵树有4个2度顶点，3个3度顶点，其余顶点都是1度顶点， 则该树有_______5___片树叶。 20．命题公式?(p?(p?q))的成假赋值是__00，01，10，11 三、运算题（共5小题，每小题8分，共40分） 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={,,,,, 极大元为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 ?1?1 24．画一棵叶带权为1、2、3、3、5、6、7的最优二元树T，并计算树权W(T)。 解： W(T) = 71 25．设Z为整数集合，V=< Z , *>，*是二元运算，定义为： x*y=x+y-xy 说明V是含幺半群而不是群。 解：（1）*运算在Z上封闭： （2）*运算可结合，对任意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 （3）*运算的幺元是0 （4）任意x?Z，x*1=1*x=1，所以1是零元，它没有逆元。 由上述可知，故< Z , *>是含幺半群而不是群。 四、证明题（共3小题，共20分） 26（10分）．在一阶逻辑中构造下面推理的证明： 前提：?x(F(x) ??G(x)) ，?x (G(x) ? R(x))，?x?R(x) 结论：?x?F(x) （10分）证: ① ?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（5分）．证明，若非空集合A上的关系R和S是反对称的，则R?S也是反对称的。