2011年4月自考真题离散数学

2010—2011学年第2学期计算机系09级计算机科学与技术专业离散数学课程期末考试A 试卷答案一、 判断题：（每小题2分，共10分）1 ×2 √3 √ 4√ 5√二、单选题：（每小题4分，共20 分）1 D2 D3 A4 C5 B6 B7 B8 D二、 填空题：（每小题4分，共20分）1 }{><><><c c b b a a ,,,,,2 {}{}{}{}{}{}{}><><><><><><><><a a a a a a a a ,,1,1,,1,,,1,,,1,1,1,,,1,φφ3 2棵4 ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡01101011110101105 }{{}{}d c b a ,,,6 A I R ⋃ 1-⋃R R7 8个顶点8 1-n四、解答题（每小题8分，共32分）1、 解 ))(())((R Q P R Q P ∧⌝→⌝∧∧→ ８分 ４分 ２分)()()()()()()()()()())(())((R Q P R Q P R Q P R Q P R Q P R Q P R P Q P R P Q P R Q P R Q P ∨∨∧⌝∨⌝∨∧∨⌝∨∧∨⌝∨⌝∧⌝∨∨⌝∧∨∨⌝⇔∨∧⌝∨∧∨⌝∧∨⌝⇔∧⌝∨∧∧∨⌝⇔ 2 解 图的邻接矩阵⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=0100110001000121)(D A 2分 ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=1000010010001321)(2D A 6分 所以 图中长度为2的通路总数是10 7分其中有3条回路。

8分3、解 哈斯图如下A 的极大元是7、9、6、8、10；极小元是1 6分最大元不存在，最小元是1 8分4、解 设A ：在1到1000的正整数中能被5整除的数， 则200=AB ：在1到1000的正整数中能被6整除的数， 则166=BC ：在1到1000的正整数中能被8整除的数， 则125=C33=⋂B A 25=⋂C A 41=⋂C B 8=⋂⋂C B A 4分 由包含排斥原理，有C B A C B C A B A C B A C B A ⋂⋂+⋂-⋂-⋂-++=⋃⋃= 200+166+125-33-25-41+8=400 6分所以在1-1000中不能被5、6，也不能被8整除的数的个数是1000-400=600 8分五、证明题（10分）前提：r p →; p q →⌝; r ⌝ 2分结论：q 3分证明： ① r p → 前提引入 4分② r ⌝ 前提引入 5 分③ p ⌝ ①② 距取式 7分④ p q →⌝ 前提引入 8分⑤ q ⌝⌝ ③ ④ 距取式 9 分⑥ q ⑤ 置换 10分2010—2011学年第2学期计算机系计科、网工专业09、10级离散数学课程期末考试B 试卷答案一、判断题：（每小题2分，共10分）1、√2、√3、×4、×5、√二、单选题：（每小题4分，共20 分）1 、A 2、D 3 、B 4 、B 5、A 6、A 7、B 8、A三、填空题：（每小题4分，共20分）1 、{}{{}{}{}{}}a a ,,,,φφφ 2、))()((x G x F x ⌝∧∃ 3、 {}><d c , 4 、1 5 、2 6、{}><><><><><><><><><><3,4,2,4,4,3,2,3,4,2,3,2,4,4,3,3,2,2,1,1 7、6 8、回四、解答题（每小题8分，共32分）1、解： r q p r q p r q p ∨⌝∧⇔∨∨⌝⌝⇔→→)()()( 2分而54)()()(m m r q p r q p q p ∨⇔⌝∧⌝∧∨∧⌝∧⇔⌝∧ 3分7531m m m m r ∨∨∨⇔ 5分所以 ∑⇔→→)7,5,4,3,1()(r q p 6分该 公式的成真赋值是001,011,100,101,111. 8分 2 解： 关系矩阵是⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡=1001101100011001001110011A 3分 因R 自反，对称，传递，所以R 是等价关系 4分等价类有[][][]{}5,2,1521===；[][]{}4,343== 8分 3 解：（1）{}A I b d d e f e f c b e b c a e a c c e R ⋃><><><><><><><><><=,,,,,,,,,,,,,,,,,, 3分（2）A 关于R 的最大元不存在；最小元是e 5分（3）子集{c ，d ，e}的上界是b 和f ， 无上确界。

学历类《自考》自考专业(计算机应用)《离散数学》考试试题及答案解析姓名:_____________ 年级:____________ 学号:______________1、下面四组数能构成无向图的度数列的有( )。

A 、2,3,4,5,6,7 B 、1,2,2,3,4 C 、2,1,1,1,2 D 、3,3,5,6,0 正确答案：B 答案解析：暂无解析2、下列几个图是简单图的有( )。

A 、G1=(V1,E1),其中V1={a,b,c,d,e},E1={ab,be,eb,ae,de}B 、G2=(V2,E2)其中V2=V1,E2={,,,,,}C 、G=(V3,E3),其中V3=V1,E3={ab,be,ed,cc}D 、G=(V4,E4),其中V4=V1,E4={（a,a ）,（a,b ）,（b,c ）,（e,c ）,（e,d ）}。

正确答案：B 答案解析：暂无解析3、下列图中是欧拉图的有( )。

A 、 B 、 C 、 D 、 正确答案：B 答案解析：暂无解析4、与命题公式P→(Q→R)等价的公式是( ) A 、 B 、 C 、 D 、 正确答案：B 答案解析：暂无解析5、命题公式(A∧(A→B))→B 是一个矛盾式。

1、正确2、错误正确答案：错误答案解析：暂无解析6、任何循环群必定是阿贝尔群，反之亦真。

1、正确2、错误正确答案：错误答案解析：暂无解析7、根树中最长路径的端点都是叶子。

1、正确2、错误正确答案：错误答案解析：暂无解析8、若集合A上的关系R是对称的，则R∧-1也是对称的。

1、正确2、错误正确答案：正确答案解析：暂无解析9、数集合上的不等关系(≠)可确定A的一个划分。

1、正确2、错误正确答案：错误答案解析：暂无解析10、设集合A、B、C为任意集合，若A×B=A×C，则B=C。

1、正确2、错误正确答案：正确答案解析：暂无解析11、函数的复合运算“。

”满足结合律。

P F F T T Q F T F T P↔Q T F F T
每当Ｐ和Ｑ的真值相同时，则（Ｐ↔Ｑ）的真值 为“Ｔ”，否则（Ｐ↔Ｑ）的真值为“Ｆ”。
（３）举例：
▪ 春天来了当且仅当燕子飞回来了。 ▪平面上二直线平行，当且仅当这二直线不相交。 ▪２＋２＝４当且仅当雪是白色的。 （两者没有关系，但是确实命题）
举例： （a）P：王华的成绩很好 Q：王华的品德很好。 则ＰΛＱ：王华的成绩很好并且品德很好。 （b P：我们去种树 Q：房间里有一台电视机 则ＰΛＱ：我们去种树与房间里有一台电视机。 (c) P：今天下大雨 Q：3+3=6 则ＰΛＱ：今天下大雨和3+3=6
３．析取词（或运算） （１）符号“∨” 设Ｐ、Ｑ为二个命题，则 （Ｐ∨Ｑ）称作Ｐ与Ｑ的“析取”，读作： “Ｐ或Ｑ”。
（a）P：我拿起一本书 Q：我一口气读完了这本书 P→Q：如果我拿起一本书，则我一口气读完了这本书。 （b）P：月亮出来了 Q：3×3=9 P→Q：如果月亮出来了，则 3×3=9。（善意推定）
５．双条件联结词（“等价”词、“同”联结词、 “等同”词） （１）符号“↔”设Ｐ、Ｑ为二个命题，则Ｐ↔ Ｑ读作：“Ｐ当且仅当Ｑ”，“Ｐ等价 Ｑ”,“Ｐ是Ｑ的充分必要条件”。 （２）定义（见真值表）：
（４）Ｐ,Ｑ中，Ｐ、Ｑ的地位是平等的，Ｐ、Ｑ 交换位置不会改变真值表中的值。
６．命题联结词在使用中的优先级 （１）先括号内，后括号外 （２）运算时联结词的优先次序为： ¬ Λ → ↔ （由高到低） （３）联结词按从左到右的次序进行运算
∨
¬Ｐ∨（Ｑ∨Ｒ）可省去括号，因为“Ｖ”运算是可结合的。 （ ¬Ｐ∨Ｑ）∨Ｒ可省去括号，因为符合上述规定 而Ｐ→（Ｑ→Ｒ）中的括号不能省去，因为“→”不满足结合律。

离散数学试题第一部分选择题一、单项选择题1．下列是两个命题变元p，q的小项是（ C ）A．p∧┐p∧q B．┐p∨qC．┐p∧q D．┐p∨p∨q2．令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（ D ）A．p→┐q B．p∨┐qC．p∧q D．p∧┐q3．下列语句中是命题的只有（ A ）A．1+1=10 B．x+y=10C．sinx+siny<0 D．x mod 3=24．下列等值式不正确的是（ C ）A．┐(∀x)A⇔(∃x)┐AB．(∀x)(B→A(x))⇔B→(∀x)A(x)C．(∃x)(A(x)∧B(x))⇔(∃x)A(x)∧(∃x)B(x)D．(∀x)(∀y)(A(x)→B(y))⇔(∀x)A(x)→(∀y)B(y)5．谓词公式(∃x)P(x,y)∧(∀x)(Q(x,z)→(∃x)(∀y)R(x,y,z)中量词∀x的辖域是（ C ）A．(∀x)Q(x,z)→(∃x)(∀y)R(x,y,z))B．Q(x,z)→(∀y)R(x,y,z)C．Q(x,z)→(∃x)(∀y)R(x,y,z)D．Q(x,z)6．设A={a,b,c,d}，A上的等价关系R={<a,b>,<b,a>,<c,d>,<d,c>}∪I A，则对应于R的A的划分是（ D ）A．{{a},{b,c},{d}} B．{{a,b},{c},{d}}C．{{a},{b},{c},{d}} D．{{a,b},{c,d}}7．设A={Ø}，B=P(P(A))，以下正确的式子是（ A ）A．{Ø,{Ø}}∈B B．{{Ø,Ø}}∈BC．{{Ø},{{Ø}}}∈B D．{Ø,{{Ø}}}∈B8．设X，Y，Z是集合，一是集合相对补运算，下列等式不正确的是（ A ）A．(X-Y)-Z=X-(Y∩Z)B．(X-Y)-Z=(X-Z)-YC．(X-Y)-Z=(X-Z)-(Y-Z)D．(X-Y)-Z=X-(Y∪Z)9．在自然数集N上，下列定义的运算中不可结合的只有（ D ）A．a*b=min(a,b)B．a*b=a+bC．a*b=GCD(a,b)(a,b的最大公约数)02324# 离散数学试题第1 页共4页02324# 离散数学试题 第 2 页 共4页D ．a*b=a(mod b)10.设R 和S 是集合A 上的关系,R ∩S 必为反对称关系的是( A ) A ．当R 是偏序关系,S 是等价关系; B ．当R 和S 都是自反关系; C ．当R 和S 都是等价关系; D ．当R 和S 都是传递关系11.设R 是A 上的二元关系,且R ·R ⊆R,可以肯定R 应是( D ) A ．对称关系; B ．全序关系; C ．自反关系; D ．传递关系 12．设R 为实数集，函数f ：R →R ，f(x)=2x ，则f 是（ B ） A ．满射函数 B ．单射函数 C ．双射函数 D ．非单射非满射第二部分 非选择题二、填空题1．设论域是{a,b,c}，则(∀x)S(x)等价于命题公式 S(a)∧S(b)∧S(c) ；(x ∃)S(x)等价于命题公式 S(a)∨S(b) ∨S(c) 。