离散5-answer

江苏技术师范学院20 —20 学年第 学期 《离散数学》试卷（5）参考答案与评分标准 一、单项选择题（本大题共5道小题，每小题2分，共10分） 1. 永假式的否定是（ A ）。

A.永真式 B.永假式 C.可满足式 D. A 、B 、C 均有可能 2. 设集合A={a,b,c},A 上的关系R={<a,a>,<b,b>}具备下列性质（ D ）。

A ．等价性 B ．自反性 C ．反自反性 D ．反对称性 3. Z 是整数集合，代数系统<Z ，+>的零元是（ D ）。

A. 0 B. 1 C. 0和1 D. 不存在 4. 以下不正确的是（ C ）。

A ．
B.
C. D ． 5. 设q ：郑小虎吃饭，r ：郑小虎看电视，“郑小虎一边吃饭一边看电视”在命题逻辑中的符号化形式为（ C ）。

A. q ∨ r B. q → r C. q ∧r
D. r →q 二、填空（本大题共10空，每空2分，共20分） 1.A 是一集合，|A|=20，|P(A)| = 220 。

2.设F(x)：x 是鱼；G(x)：x 会飞；则“鱼都不会飞”可符号化为：∀x （F(x)→⌝G(x)）。

3.在整数集合Z 上定义二元运算:2a b a b **=++，则Z 上关于*的单位元是 -2 。

4.集合A 上的等价关系的三个性质是 自反性 、 对称性 和传递性。

5.P({a,b,c})= {Φ,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}} 。

6.无向树T 有1个3度结点，2个2度结点，其余结点全是树叶，则该无向树T 的树叶数为 3 。

7.无向图G 是欧拉图当且仅当 G 连通且所有结点的度数为偶数 。

8.群(Z 6,+6)的所有子群：_<Z 6,+6>，<{0,2,4},+6>，<{0,3},+6>，<{0},+6>_。

9.一个图G 有12条边，若每个结点的度均为2，则G 有 12 个结点。

三、判断题（本大题共10小题，每小题1分，共10分）
正确的打“√”，错误的打“×”
1.（×）空集仅是非空集合的子集。

2.（×）设A，B，C为任意集合，则A B A C B C
⨯=⨯⇒=。

3.（×）集合R上的关系满足自反性，则一定满足反自反性。

4.（×）“前进！”这句话是命题。

5.（×）在自然数集N上定义二元运算*：a*b=a+2b，*满足结合律。

6.（√）偏序关系R的传递闭包是R。

7.（√）若A={Ф}，B=P（A），则有{Ф}∈B及{Ф}⊆B。

8.（√）阿贝尔（Abel）群是交换群。

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

10.（×）命题公式)
→不是重言式。

P→
Q
(P
四、证明题（本大题共5小题，每小题各6分，共30分）
1.设A、B、C是三个集合，证明：(A－B)⋃(A－C)=A－(B⋂C)
证明：(A-B)⋃(A-C)=(A⋂B)⋃(A⋂C)=A⋂(B⋃C)
B⋂=A-(B⋂C) （6分）
=A⋂C
2.设9阶无向图的每个顶点的度数为5或6, 证明它至少有5个6度顶点或者至少有6个5度顶点。

（6分）
证明：
方法一讨论所有可能的情况.
设有a个5度顶点和b个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
3.符号化下述命题，并构造推理的证明。

若明天是星期一或星期三，我就有课。

若有课，今天必须备课。

我今天没备课。

所以，明天不是星期一和星期三。

（6分）
解：设 p :明天是星期一, q :明天是星期三，r :我有课，s :我备课
前提: (p ∨q )→r , r →s , ⌝s
结论: ⌝p ∧⌝q （2分）证明
① r →s 前提引入
② ⌝s 前提引入
③ ⌝r ①②拒取式
④ (p ∨q )→r 前提引入
⑤ ⌝(p ∨q ) ③④拒取式
⑥ ⌝p ∧⌝q ⑤置换 （4分）
结论有效, 即明天不是星期一和星期三。

4.设B 是任意集合，试验证<P(B),⊕>是群。

其中，P(B)是B 的幂集，⊕是对称差运算。

证明：对任意集合C ，D ，E ∈P(B)，有
)()(E D C E D C ⊕⊕=⊕⊕(⊕运算满足结合律)，故<P(B),⊕>是半群。

（2分） ),(B P ∈∅对集合),(B P C ∈有∅⊕==∅--∅=⊕∅C C C C C )()( ，所以∅是二元运算⊕的单位元。

（2分）
∅=--=⊕∈∀)C C ()C C (C C ),B (P C ，
二元运算⊕的逆元是它自身，存在逆元。

（2分） 可见，<P(B),⊕>是群。

5.符号化下述命题，并构造推理的证明（个体域为全体人类组成的集合）。

非洲人都不怕热，玛丽怕热。

所以玛丽不是非洲人。

证明：
设F(x)：x 是非洲人，G(x)：x 怕热，a ：玛丽
前提：∀x(F(x)→⌝G(x)),G(a)；
结论：⌝F(a) （2分）
证明：
① G(a) 前提引入
② ∀x(F(x)→⌝G(x)) 前提引入
③ F(a)→⌝G(a) ②UI 规则
④ ⌝F(a) ①③拒取 （4分）
五、计算、应用题（本大题共5小题，第1、2、3小题各6分，第4小题4分，第5小题8分，共30分）
1. 设集合A ＝｛1,2,3,4,5,6｝，B={1,2,3}，从A 到B 的关系R ＝｛〈x,y 〉|x=2y ｝，
求(1)R ,(2)R -1
解：(1)R={<2,1>,<4,2>,<6,3>} （3分）
(2)R 1-={<1,2>,<2,4>,<3,6>} （3分）
2. 求P ∨(P →Q)的主析取范式及主合取范式。

解：P ∨(P →Q)⇔P ∨(⌝P ∨Q)⇔(P ∨⌝P)∨Q ⇔T(主合取范式) （3分）
⇔(⌝P ∧⌝Q)∨(⌝P ∧Q)∨(P ∧⌝Q)∨(P ∧Q)（主析取范式） （3分）
3. 求以1,3,4,5,6为权的最优2元树, 要求写出步骤并计算它的权。

（4分）
W(T)=(1+3)*3+(4+5+6)*2=42 （2分）
4. 求谓词公式)()(x xQ x xP ∃→∀的前束范式。

解：)()(x xQ x xP ∃→∀⇔)()(y yQ x xP ∃→∀⇔))()((y Q x P y x →∃∃ （4分）
5. A={1,2,3}，R 为A 上关系，关系矩阵为⎥⎥⎥⎦
⎤⎢⎢⎢⎣⎡101011001， (1) 画出关系图。

(2) 求R R ，R -1。

(3) 指出R 具有的性质。

(4) R 是偏序关系吗？若是画出哈斯图。

解：(1)
（2分）(2) R R={<1,1>，<2,1>，<2,2>，<3,1>，<3,3>}（1分）R-1={<1,1>，<1,2>，<1,3>，<2,2>，<3,3>}（1分）
(3) R的性质：自反性、反对称性、传递性。

（2分）
(4) R是偏序，其哈斯图如下：（2分）。