离散15-answer

更新时间：2023-09-30 13:24:01 阅读量：综合文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

装：号学订：名姓线：级班

江苏技术师范学院20 —20 学年第学期《离散数学》试卷（15）参考答案与评分标准

一、选择题（本大题共5道小题，每小题2分，共10分）

1. 设个体域为正整数集，公式?x?y(xy=y)和?x?y(x+y=y)的真值分别是（ A ）。

A.0和0 B.0和1 C. 1和0 D. 1和1 2. 谓词公式?xF(x)?G(x,y)，?x的辖域为（ A ）。

A．F(x) B．?xF(x) C．F(x)?G(x,y) D．?xF(x)?G(x,y)

3. 下图中欧拉图是（ C ）。

A B C D

4. 令p：今天下雨了，q：我上学，则命题“因为今天下雨了，所以我不上学

了”可符号化为（ A ）。

A.p??q B.?q?p C. p?q D. p?q 5. 以下不正确的是（ C ）。

A． B.

D．

二、填空题（本大题共10道小题，每小题2分，共20分）

1. 已知A,B是集合│A│=15，│B│=10，│A∪B│=20，则│A∩B│= 5 。 2. 设F(x): x是无理数；G(x)：x可以表示成分数；则“无理数都不可以表示

成分数”可符号化为： ?x(F(x)??G(x)) 。

3. Z是整数集合，代数系统的单位元是 0 。 4. 集合A上的等价关系的三个性质是自反性、对称性和传递性。

《离散数学》试卷15答案第 1 页共 6 页

5. 在布尔代数中，有a??a?b??a?b,则该式的对偶式为 a?a?b?a?b 。 6. 无向树T有1个3度顶点, 2个2度顶点, 其余顶点全是树叶，则该无向树T的树叶数为： 3 。

7. 设K6是有6个顶点的完全图，则K6共有_____15______条边。

8. 设A={2,4,6}，A上的二元运算*定义为：a*b=max{a,b}，则在中，零元是 6 。

9. 设〈G,*〉是一个群，若a,b,x∈G，a?x=b，则x=__ a-1?b ______。 10. 已知集合A={?，1，2}，则A的幂集合P(A)=__ {?，{?}，{1}，{2}，

{?,1}，{?,2}，{1,2}，{?,1,2}} ____ __。

三、判断题（本大题共10道小题，每小题1分，共10分） 1. （√）??{?}。

2. （×）设G是一棵树，n,m分别表示结点数和边数，则n=m。 3. （√）??xA(x)??x?A(x)。 4. （√）(p?q)?(p?q)是重言式。

5. （×）在自然数集N 上定义二元运算*：a*b=a+2b，*满足结合律。 6. （×）无向图G?V,E，其中V?n，E?m，则G为树当且仅当G无回路。 7. （√）A是一集合，|A|=20，则A的幂集P(A)的基数|P(A)| =220-1。 8. （√）A={3,6,9}，A上二元运算*定义为：a*b=min{a,b}，则中单位元是9。

9. （×）对集合A,B,C,D，有（A?B）?(C?D)=(A?C)?(B?D)。

10.（√）集合A={a,b,c}及其上的二元关系R={,}?IA，则R具有自

反性和对称性。

四、证明题（本大题共3道小题，每小题8分，共24分）

1.设9阶无向图的每个顶点的度数为5或6, 证明它至少有5个6度顶点或者至少有6个5度顶点。

证明：（8分）方法一讨论所有可能的情况. 设有a个5度顶点和b个6度顶点

《离散数学》试卷15答案第 2 页共 6 页

(1)a=0, b=9; (2)a=2, b=7; (3)a=4, b=5; (4)a=6, b=3; (5)a=8, b=1

(1)~(3) 至少5个6度顶点, (4)和(5) 至少6个5度顶点方法二假设b<5, 则a> 9-

5=4. 由握手定理的推论, a>=6

2.在命题逻辑中符号化下述命题，并构造推理的证明。

若明天是星期二或星期五，张老师就有课。若有课，张老师今天必须备课。张老师今天没备课。所以，明天不是星期二和星期五。

解：设p:明天是星期二,q:明天是星期五，r:张老师有课，s:张老师备课（2分）前提: (p?q)?r, r?s, ?s

结论: ?p??q （2分）证明：

① r?s 前提引入 ② ?s 前提引入 ③ ?r ①②拒取式 ④ (p?q)?r 前提引入 ⑤ ?(p?q) ③④拒取式 ⑥ ?p??q ⑤置换

结论有效, 即明天不是星期二和星期五。（4分）

3.在谓词逻辑中符号化下述命题，并构造推理的证明。

哲学家都善于思考。亚里士多德是哲学家。所以，亚里士多德善于思考。证明：令F(x)：x是哲学家，G(x)：x善于思考，a：亚里士多德，（2分）前提：?x(F(x)?G(x))，F(a) （2分）结论：G(a) 推演：

(1)F(a) 前提引入 (2)?x(F(x)?G(x)) 前提引入 (3) F(a)?G(a) (2)UI

(4)G(a) (1)(3)假言推理（4分）

《离散数学》试卷15答案第 3 页共 6 页

4.设A1、A2、A3是三个集合，证明：A1?(A2－A3)＝(A1?A2)－(A1?A3)。证明：(A1?A2)－(A1?A3) ＝(A1?A2)?~(A1?A3) =(A1?A2)?(~A1?~A3)

=(A1?A2?~A1)?(A1?A2?~A3) =??(A1?A2?~A3) = A1?A2?~A3 =A1?(A2?~A3)

=A1?(A2-A3) （8分）

五、计算、应用题（本大题共6小题，每小题6分，共36分） 1. R1={<1,2>,<1,3>,<2,3>,<3,3>}, R2={<2,2>,<2,3>,<3,4>}, (1) 求 R1-1 (2) 求R2?R1 (3)R1是函数吗？解：(1)R1-1={<2,1>,<3,1>,<3,2>,<3,3>}, （2分） (2) 求R2?R1={<2,3>}, （2分） (3)R1不是函数。（2分）

2. 是布尔代数，?a,b,c?A，化简abc?abc?bc?abc?abc。解：abc?abc?bc?abc?abc

?ab(c?c)?bc?ab(c?c)?ab?bc?ab?(a?a)b?bc?b?bc?b （6分）

3.求公式((p?q)?r)?p的析取范式和合取范式。解：原式

?????p?q??r??p 消去? ??????p?q????r??p ?内移 ???p?q???r??p 消去??

《离散数学》试卷15答案第 4 页共 6 页

??p??r???q??r??p 分配律(?对?分配) （3分）上式即原式的析取范式，再利用第三步的结论，即：原式

???p?q???r??p

??p?q?p????r?p? 分配律(?对?分配) ??p?q???p??r?

即原式的合取范式。（3分）

4.求以1,3,4,5,6为权的最优2元树, 要求写出步骤并计算它的权。

（4分）

W(T)=(1+3)*3+(4+5+6)*2=42 （2分）