离散数学南昌大学软件学院试卷(软工)(A)2007 ～ 2008学年第一学期《离散数学》期末试卷（A）年级专业班级学号姓名____________适用年级专业：2006级软件工程专业试卷说明：闭卷考试，考试时间120分钟一、单项选择题（共20小题，每小题1分，共20分）1．下列语句中只有不是命题。

CA．今年元旦会下雪。

B．1+1=10。

C．嫦娥一号太棒了！D．嫦娥奔月的神话已成为现实。

2．p↔q的主合取范式是。

BA．(p∨q)∧(p∨⌝q) B．(p∨⌝q)∧(⌝p∨q)C．(p∨q)∧(⌝p∨⌝q) D．(p∨q)∧(⌝p∨q)3．与p→ q等值的命题公式是。

DA．⌝p∧q B．p∨⌝q C．p∧⌝q D．⌝p∨q4．在一阶逻辑中使用的量词只有个。

BA．1 B．2 C．3 D．45．⌝∀xA(x)⇔。

CA．⌝∃xA(x) B．∀x⌝A(x) C．∃x⌝A(x) D．∃xA(x)6．若|A|=4，则|P(A)|= 。

CA．4 B．8 C．16 D．647．设A、B、C为任意集合，集合的对称差运算不具有的性质是。

D A．A⊕B = B⊕A B．(A⊕B)⊕C = B⊕(A⊕C)C．A⊕A = ∅ D．A⊕A = A8．二元关系是。

BA．两个集合的笛卡儿积 B．序偶的集合C．映射的集合 D．以上都不是9．下面关于函数的叙述中正确的是。

DA．函数一定是满射 B．函数一定是单射C．函数不是满射就单射 D．函数是特殊的关系10．半群中的二元运算一定满足= 。

BA．交换律 B．结合律 C．分配律 D．幂等律11．环中有个二元运算。

BA．一 B．二 C．三 D．四12．群与独异点的区别是。

CA．满足交换律 B．满足结合律C．每个元素都有逆元 D．满足分配律13．九阶轮图的点色数是。

BA．2 B．3 C．4 D．914．设N、Q、Z、R分别表示非负整数集、有理数集、整数集和实数集，＋表示数的加法，则下面的代数系统中，不是群。

AA．<N ，＋> B．<Q ，＋>C．< Z ，＋> D．<R ，＋>15．简单通路是没有的通路。

AA．重复边 B．重复顶点 C．平行边 D．环16．设个体域为N（非负整数集），下列公式为真的是。

BA．∃y ∀x (xy = 1) B．∃y ∀x (xy = x)C．∀x ∃y (x+y=0) D．∀x ∃y (x > y)17．非平凡树一定是。

BA．正则图 B．二部图 C．欧拉图 D．哈密顿图18．环<R，+ ，•>中的•运算只要求满足。

BA．交换律 B．结合律 C．分配律 D．幂等律19．集合A上的等价关系与一一对应。

BA．集合A的子集 B．集合A的划分C．集合A到A的双射 D．集合A与A的单射20．全序关系一定不是。

AA．等价关系 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,b>,<b,a>} ⋃I A ，则商集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>}⋃I A ，则t(R)=__ {<1,3>,<3,1>,<4,1>,<4,3>} ⋃I A17．设函数f：N→N，f =x -1，函数h：N→N，h(x)=x2+1，则复合函数f h (x) = _______(x -1)2+118．完全二部图K r,s（r<s）的最大度∆(K r,s) = ______S____，最小度δ(K r,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={<a,b>,<a,d>,<a,c>,<a,f>,<a,e>,<b,d>,<b,e>,<c,e>,<c,f>} ⋃ I A画出该偏序关系的哈斯图，并求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 →1⇔124．画一棵叶带权为1、2、3、3、5、6、7的最优二元树T，并计算树权W(T)。

解： W(T) = 7125．设Z为整数集合，V=< Z , *>，*是二元运算，定义为：x*y=x+y-xy说明V是含幺半群而不是群。

解：（1）*运算在Z上封闭：（2）*运算可结合，对任意a、b、c∈Za*(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) ⑧ EG27（5分）．证明，若非空集合A上的关系R和S是反对称的，则R⋂S也是反对称的。

证: 任取<x,y>，x≠y<x,y>∈R⋂S⇒<x,y>∈R∧<x,y>∈S⇒<y,x>∈R∧<y,x>∈S⇒<y,x>∈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 10B11B 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>} ⋃I A17． (x -1)2+1 18． s , r19． 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；无最大元；最小元为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 →1⇔124．解： W(T) = 7125．解：（1）*运算在Z上封闭：（2）*运算可结合，对任意a、b、c∈Za*(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是零元，它没有逆元。