离散数学期末试卷(A)(2)

证: 任取，x≠y

?R?S??R??S??R??S??R?S。 故R?S是对称的。 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 10B

11B 12C 13B 14A 15A 16B 17B 18B 19B 20A 二、填空题（共10题，每题2分，共20分）

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． {<1,3>,<3,1>,<4,1>,<4,3>} ?IA 17． (x -1)2+1 18． s , r

19． 5 20．00，01，10，11 三、运算题（共5小题，每小题8分，共40分）

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（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． 解： W(T) = 71

25． 解：（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?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分）证: 任取，x≠y

?R?S??R??S??R??S??R?S。 故R?S是对称的。 28（5分）

证: 用反证法。假设G中两个奇度顶点u和v不连通，则u和v分别处于G的两不同连通分支G1和G2中，因而G1和G2作为独立的图时，均只有一个奇度顶点，这是不可能的，故这两个奇度顶点必连通。