习题参考解答.doc

离散数学部分课后习题答案
离散数学部分课后习题答案
习题1.1
1、（3）P：银行利率降低
Q：股价没有上升
P∧Q
（5） P：他今天乘火车去了北京
Q：他随旅行团去了九寨沟

（7） P：不识庐山真面目
Q：身在此山中
Q→P，或 ～P→～Q
（9） P：一个整数能被6整除
Q：一个整数能被3整除
R：一个整数能被2整除
T：一个整数的各位数字之和能被3整除
P→Q∧R ，Q→T
2、（1）T （2）F （3）F （4）T （5）F
（6）T （7）T（F） （8）悖论
习题 1.3
1、（3）

（4）

2、不， 不， 能
习题 1.4
2、①

③

3、
，
4、
习题 1.5

主合取范式

————主析取范式

3、解：根据给定的条件有下述命题公式：
（A→（CÑD））∧～（B∧C）∧～（C∧D）
Û（～A∨（C∧～D）∨（～C∧D））∧（～B∨～C）∧（～C∨～D）
Û（（～A∧～B）∨（C∧～D∧～B）∨（～C∧D∧～B）∨
（～A∧～C）∨（C∧～D∧～C）∨（～C∧D∧～C））∧（～C∨～D）
Û（（～A∧～B）∨（C∧～D∧～B）∨（～C∧D∧～B）∨
（～A∧～C）∨（～C∧D∧～C）） ∧（～C∨～D）
Û（～A∧～B∧～C）∨（C∧～D∧～B∧～C）∨（～C∧D∧～B∧～C）∨
（～A∧～C∧～C）∨（～C∧D∧～C∧～C）∨（～A∧～B∧～D）∨
（C∧～D∧～B∧～D）∨（～C∧D∧～B∧～D）∨（～A∧～C∧～D）∨
（～C∧D∧～C∧～D）（由题意和矛盾律可得下式）
（～C∧D∧～B）∨（～A∧～C）∨（～C∧D）∨（C∧～D∧～B）
Û（～C∧D∧～B∧A）∨ （～C∧D∧～B∧～A）∨ （～A∧～C∧B）∨
（～A∧～C∧～B）∨ （～C∧D∧A）∨ （～C∧D∧～A）∨
（C∧～D∧～B∧A）∨（C∧～D∧～B∧～A）
Û（～C∧D∧～B∧A）∨ （～A∧～C∧B∧D）∨ （～A∧～C∧B∧～D）∨
（～A∧～C∧～B∧D）∨ （～A∧～C∧～B∧～D）∨
（～C∧D∧A∧B）∨ （～C∧D∧A∧～B）∨ （～C∧D∧～A∧B）∨
（～C∧D∧～A∧～B）∨（C∧～D∧～B∧A）∨（C∧～D∧～B∧～A）
（由题意可得下式）
（～C∧D∧～B∧A）∨ （～A∧～C∧B∧D）∨ （～C∧D∧A∧～B）∨
（～C∧D∧～A∧B） ∨（C∧～D∧～B∧A）
Û（～C∧D∧～B∧A）∨ （～A∧～C∧B∧D）∨（C∧～D∧～B∧A）
三种方案：A和D、 B和D、 A和C
习题 1.6
1、 （1）需证为永真式

（3）需证为永真式

为永真式。即永真
永真
当且仅当
4、设： P：珍宝藏在东厢房
Q：藏宝的房子靠近池塘
R：房子的前院栽有大柏树
S：珍宝藏在花园正中地下
t：后院栽有香樟树
m：珍宝藏在附近（后院）
命题化后进行推理：

即S为真，珍宝藏在花园正中地下
5、(1)F (P=0,Q=1) (2)F (P=1,Q=R=0) (3)F (P=0,Q=1)
习题 1.7
1.（1）
证：利用CP规则
① P P(附加前提)
②
③ ①②I
④
⑤ ③④I
⑥ 结论成立 CP规则①⑤
（2）
证：① (附加)
② P∨Q T①
③
④ ②③
⑤ ④
⑥ S∨E T⑤
⑦ S∨E→B P
⑧ ⑥⑦
⑨ (①⑧)
2. (2) P：无任何痕迹
Q：失窃时，小花在OK厅
R：失窃时，小英在OK厅
S：失窃时，小胖在附近
T：金刚是偷窃者
M：瘦子是偷窃者
命题可符号化为：
{}
证：①
②
③ ①②
④
⑤ ③④
⑥
⑦ ⑤⑥
⑧
⑨ ⑦⑧
∴金刚是窃贼。
3. (1) 不相容
(2) 相容
（3）不相容
（4）不相容
4. (1)证：

即
利用消解原理：
① P
② P
③ ①②
④ P
⑤ ③④
⑥ □ ①⑤

习题 2.1
1. (1)：是实数 ：是有理数

(2)：是直线
：与平行 ：与相交

(3)：是会员 P: 这个活动有意义
：参加活动

或者
（4） ：是正整数 ：是合数 ：是质数

（5） ：是存钱的人 B（x）：x想有利息
P:存钱没有利息 Q：人们不存钱

2.(1)
(2)
4.(1)
习题 2.2
1.（1）D：数

可满足式
(2)是诚实的人，讲实话 ，a：小林
T
(3) 不便宜，是好货，a：小王买的衣服
T
（4）是懂得人性本质的作家
是真正的诗人
能刻画人们内心世界
很高明 创作了
a：莎士比亚 b：哈姆雷特

T

2.(1)
3.(1) (2)
4.
习题 2.3
1.（1）

2. 不成立
D={0,1,2}
3.(1)

——skolem范式
(2)

——前束范式
——skolem范式
习题 2.4
1. （1）证：在某个解释下，取值1，必有,
，取值1，因此， 取值1。
取值1，由定义，蕴含关系成立。
（2）①

(2) 证: 在某个解释下，取值1
即取值0，分二种情况：
i)，则无论为何值，取值1。
ii) ，则取值1
由定义，蕴含关系成立。
习题 2.5
1（2）（反证法）
① P
② T①,E
③ T②,I
④ T③,I
⑤ US④
⑥ T⑤,I
⑦ UG⑥
⑧ P
⑨ T⑧,I
⑩ T⑤,I
US⑨
□ T⑩I
2. (1) 错误，应换元，即
①，
②
（2） 正确
（3） 错误，a、b应是同一个常元
（4） 错误，因为在 中x并不是自由出现
(5) 错误，因为在中，前件是命题，
而后件不是命题
（6） 错误，因为a、b并不是同一个常量
（7） 错误，①②和③④的顺序不对
应先使用ES，再使用US
3(1)解：设F(x,y):x≥y; G(z):z≥0 ; f(x,y)=x-y
前提：
① "(x)"(y)（F(x,y)→G(f(x,y))
② "(x)"(y)（ØF(x,y)→ØG(f(x,y))
③ "(x)"(y)(ØG(f(x,y)→ G(f(y,x)))
结论： "(x)"(y)（G(f(x,y))∨G(f(y,x))）
证明（反证法）：
① Ø "(x)"(y)（G(f(x,y))∨G(f(y,x))）
② （$ｘ）（$ｘ）Ø（G(f(x,y))∨G(f(y,x))）
③ ØG(f(a,b))∧ ØG(f(b,a))
④ "(x)"(y)（F(x,y)→G(f(x,y))
⑤ F(a,b)→G(f(a,b))
⑥ ØG(f(a,b))→ØF(a,b)
⑦ "(x)"(y)(ØG(f(x,y)→ G(f(y,x)))
⑧ Ø G(f(b,a))→G(f(a,b))
⑨ "(x)"(y)（ØF(x,y)→ØG(f(x,y))
⑩ ØF(a,b)→ØG(f(a,b))
⑾ G(f(a,b)) → F(a,b)
⑿ ØF(a,b) ∧ F(a,b)
4. （2）
证：首先，将结论否定否作为前提加入到原有前提中

Skolem 范式
子句集为
①
②
③ ①,②代换{a/x}
④ ③代换{c/x}
⑤
⑥ ④,⑤代换{c/w}
⑦ ⑥代换{c/y}
⑧□
习题 3.3
5、

习题 4.2
2.
关系
性质
R1
R2
R3
R4
R5
自反性
√
√
√
√
×
反自反性
×
×
×
×
√
对称性
×
√
√
√
×
反对称性
√
×
×
×
√
传递性
√
√
√
×
√
习题 4.3
2. （3）“”R是对称的，设则
，即
“” ，由的定义，
，即R是对称的。
（5）“”R是传递的，对

即
“”，对，由R2的定义，
有，即R是可传递的。
4. 解：，且

需3|m，5|m
，即

故使的最小正整数
习题 4.4
2、解：

3. (3)证：

由归纳法可证：对

(4)证：①

由归纳法可证：

③

习题 5.1
1. 证：

①自反性 由A的定义，

②对称性 设，则
即
③传递性 设，则
，则

3. 解：
设

4. 解：∵每个集合的划分就可以确定一个等价关系
∴集合有多少个划分就可以确定多少个等价关系
种。
5. 解：
①不是A上的等价关系 ②是A上的等价关系
④ 是A上的等价关系 ④不是A上的等价关系
习题 5.2
2. 解：
<2C,Í>
F
{a}
{b}
{c}
{a,b}
{a,c}
{b,c}
{a,b,c}

3. 解：集合A上的空关系、恒等关系IA都是等价关系和偏序关系。
6. 证：i）自反性，对，（的自反性）
显然
ii)反对称性，对
即，由R的反对称性，
iii)传递性，对，设，
则，。
由R的传递性，，显然

习题 5.3
2. 解：

习题6.2
4、证：

习题6.3
4、证：

习题10.1
1、

3、解：（1）不是图的序列，因为奇数度结点的
个数不是偶数。
（2）、（3）、（4）都是图的序列。
4、证：

习题10.3
1、证：（反证法）设v与u不连通
∴G={V1，V2} ，v与u分别属于V1，V2二个子图
∵ v与u是G中仅有的二个奇数度结点
∴v与u即是V1与V2中仅有的一个奇数度结点，与
欧拉定理的推论相矛盾，故v与u必连通
3、证：（归纳法，对n进行归纳）
n=2时, ∵ m>0
∴ 二个结点至少有一条边，即G是连通图
设 n=k 时，结论成立,即 时， G是连通图

证n=k+1时，结论成立，即 时， G是连通图
（用反证法）
如果G是非连通图，必存在一个结点v，使1≤d(v)<k(否则，如d(v)=0，则G-{v}是一个有k个结点的简单图，其边数 与 矛盾；如d(v)=k,则G是一个完全图，与假设矛盾）
∴从G中删除该结点v所得子图G′=G-v
其边数
由归纳假设，G′=G-v的结点数为k，所以G′是简单图，
∵G=G′+{v} ，∴G连通 故由归纳法，结论成立
习题10.4
3、解：

三个强分图

习题11.1
1、解：设L是叶的数目，m是树的边数
由Euler定理

由树的定义

2、证明：
习题11.3
6、证明：由正则二叉树的定义，其叶结点的个数必为偶数，设叶数为t，分支数为i
由定理10-2.1 (m-1)i=t-1
∵ m=1 ∴ i=t-1 有分支点数是奇数 故结点数=i+t=奇数
习题12.2
1、证：（反证法）
设G=（n，m）和G’=（n，m’）都是平面图
由G的定义 m+m’=n(n-1)/2
由定理10-4.2 m≤3n-6 , m’≤3n-6
∴ m+m’=n(n-1)/2 ≤6n-12
有 n2-13n+24=(n-11)2+9n-97 ≤0
又∵（n-11)2 ≥0，n ≥11时,9n-97 ≥2
∴ （n-11)2 +9n-97 ≥2
与上式相矛盾， 故G与G’至少有一个是非平面图
2、证：由Euler公式，n-m+f=2
∴ 6-12+f=2 f=8 即面数为8，
∵对每个面，其度数≥ 3
∴总面度≥3×8=24
∵总面度=2×m=24
∴每个面的度数为3
3、证：（反证法）
设所有顶点的度数5
由Euler公式，
由定理10-4.2 m≤3n-6
3n-6≥5n/2 即n≥12
则 m≥5n/2≥5×12/2=30 与 m＜30矛盾
至少存在一个顶点的度数不超过4
习题13.2
2、证：∵ G是2k正则图，
∴ 对任意的u、v∈G，d(u)+d(v)=4k
由定理10-6-2 在G中存在一条Hamilton道路，设为：
v1v2,…,v4k+1
1) v1v4k+1∈E， 则v1v2,…,v4k+1v1构成一个Hamilton圈
2) v1v4k+1 E， 则
∵ G的阶数为4k+1
∴
（否则d(v4k+1)=4k-1-2k=2k-1与d(v4k+1)=2k矛盾)
设 ，可构造
即为G的一个Hamilton圈，故G是一个Hamilton图
5、证：（反证法）假设G不是哈密尔顿图，则

因为G除结点s,t外的其余n-2结点之间最多可以构成完全
图，所以 2m<(n-2)(n-3)+n+n<n2-3n+6=(n-1)(n-2)+4
从而

与已知 矛盾，故结论成立。

习题15.1
4、证：（反证法）
设 构造 ，则
即 可交换，与已知条件相矛盾
∴
习题15.2
1、证明：群中只有幺元是幂等元。
证：（反证法）
设，
矛盾

5、写出中的全部子群。
解：á（1），（1 2）ñ，á（1），（1 3）ñ，á（1），（2 3）ñ，
á（1），（1 2 3），（1 3 2）ñ和二个平凡子群。
6、证明：1）∵ S、T是G的子群
∴ eÎS , eÎT 即 eÎS ∩T
设 a，bÎS ∩T，即a，bÎS 和a，bÎT
b-1 ÎS 和b-1ÎT ∴ a×b-1 ÎS 和a×b-1ÎT
即 a×b-1 ÎS∩T ∴〈S∩T，×〉是G的子群
2） eÎST，设c、dÎST
则 $ a1ÎS，b1ÎT ，' c=a1b1，
$ a2ÎS，b2ÎT ，' d=a2b2，
∵ d-1=b2-1a2-1
又 ∵S和T中的元素关于“×” 可交换
∴c×d-1= a1b1b2-1a2-1= a1a2-1b1b2-1 ÎST
即 ST是子群
习题15.3
2、证明：设G是阶数大于1的群，
则 $ a≠eÎG 构造G′={e,a}ÍG， 则 G′是G的交换群。
3、证明：
设 G=(a),G′是G的子群，则G′中的每个元素具有am的形式，设k是所有m中最小的正整数，则
G′=（ak）（否则对" amÎG′，m=nk+l，0≤l＜k，

5、证明：

习题16.2
5、证：1）对任何 aÎR，由已知
对
由定理16-1.1，
∴
2）∵ (a*b)2=a*b=a2*b2 ∴ 由定理15-3.1 áR，*ñ为交换半群 故áR，+，*ñ为交换环
23
离散数学部分课后习题答案