第一章部分课后习题参考答案
16 设p 、q 的真值为0；r 、s 的真值为1，求下列各命题公式的真值。 （1）p ∨(q∧r) ⇔ 0∨(0∧1) ⇔0
（2）（p r ）∧(﹁q ∨s) ⇔（01）∧(1∨1) ⇔0∧1⇔0.
（3）（⌝p ∧⌝q ∧r ）(p∧q ∧﹁r) ⇔（1∧1∧1） (0∧0∧0) ⇔0 (4)（⌝r ∧s ）→(p∧⌝q) ⇔（0∧1）→(1∧0) ⇔0→0⇔1
17．判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。”
答：p: π是无理数 1 q: 3是无理数 0 r:
2是无理数 1
s: 6能被2整除 1
t: 6能被4整除 0
命题符号化为： p ∧(q→r) ∧(t→s) 的真值为1，所以这一段的论述为真。 19．用真值表判断下列公式的类型： （4）(p→q) →(⌝q →⌝p) （5）(p∧r) (⌝p ∧⌝q) （6）((p→q) ∧(q→r)) →(p→r)
答： （4）
p q p →q ⌝q ⌝p ⌝q →⌝p (p→q) →(⌝q →⌝p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式 //最后一列全为1
（5）公式类型为可满足式（方法如上例）//最后一列至少有一个1 （6）公式类型为永真式（方法如上例）//
第二章部分课后习题参考答案
3. 用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ⌝(p∧q →q) (2)(p→(p∨q)) ∨(p→r) (3)(p∨q) →(p∧r)
答：(2)（p →(p∨q) ）∨(p→r) ⇔(⌝p ∨(p∨q)) ∨(⌝p ∨r) ⇔⌝p ∨p ∨q ∨r ⇔1 所以公式类型为永真式
(3) P q r p ∨q p ∧r （p ∨q ）→(p∧r)
0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1
所以公式类型为可满足式 4. 用等值演算法证明下面等值式： (2)(p→q) ∧(p→r) ⇔(p→(q∧r))
(4)(p∧⌝q) ∨(⌝p ∧q) ⇔(p∨q) ∧⌝(p∧q) 证明（2）(p→q) ∧(p→r)
⇔ (⌝p ∨q) ∧(⌝p ∨r) ⇔⌝p ∨(q∧r)) ⇔p →(q∧r)
（4）(p∧⌝q) ∨(⌝p ∧q) ⇔(p∨(⌝p ∧q)) ∧(⌝q ∨(⌝p ∧q)
⇔(p∨⌝p) ∧(p∨q) ∧(⌝q ∨⌝p) ∧(⌝q ∨q) ⇔1∧(p∨q) ∧⌝(p∧q) ∧1 ⇔(p∨q) ∧⌝(p∧q)
5.求下列公式的主析取范式与主合取范式，并求成真赋值
(1)(⌝p →q) →(⌝q ∨p) (2)⌝(p→q) ∧q ∧r (3)(p∨(q∧r)) →(p∨q ∨r) 解：
（1）主析取范式
(⌝p →q) →(⌝q ∨p)
⇔⌝(p∨q) ∨(⌝q ∨p)
⇔(⌝p ∧⌝q) ∨(⌝q ∨p)
⇔ (⌝p ∧⌝q) ∨(⌝q ∧p) ∨(⌝q ∧⌝p) ∨(p∧q) ∨(p∧⌝q) ⇔ (⌝p ∧⌝q) ∨(p∧⌝q) ∨(p∧q)
⇔m 0∨m 2∨m 3
⇔∑(0,2,3)
主合取范式：
(⌝p →q) →(⌝q ∨p)
⇔⌝(p∨q) ∨(⌝q ∨p)
⇔(⌝p ∧⌝q) ∨(⌝q ∨p)
⇔(⌝p ∨(⌝q ∨p)) ∧(⌝q ∨(⌝q ∨p)) ⇔1∧(p∨⌝q) ⇔(p∨⌝q) ⇔ M1 ⇔∏(1) (2) 主合取范式为：
⌝(p→q) ∧q ∧r ⇔⌝(⌝p ∨q) ∧q ∧r ⇔(p∧⌝q) ∧q ∧r ⇔0 所以该式为矛盾式.
主合取范式为∏(0,1,2,3,4,5,6,7)
矛盾式的主析取范式为 0 (3)主合取范式为：
(p∨(q∧r)) →(p∨q ∨r)
⇔⌝(p∨(q∧r)) →(p∨q ∨r)
⇔(⌝p ∧(⌝q ∨⌝r)) ∨(p∨q ∨r)
⇔(⌝p ∨(p∨q ∨r)) ∧((⌝q ∨⌝r)) ∨(p∨q ∨r))
⇔1∧1 ⇔1
所以该式为永真式.
永真式的主合取范式为 1
主析取范式为∑(0,1,2,3,4,5,6,7)
第三章部分课后习题参考答案
14. 在自然推理系统P 中构造下面推理的证明： (2)前提：p →q, ⌝(q∧r),r
结论：⌝p
(4)前提：q →p,q s,s t,t ∧r 结论：p ∧q
证明：（2）
①⌝(q∧r) 前提引入 ②⌝q ∨⌝r ①置换 ③q →⌝r ②蕴含等值式 ④r 前提引入
⑤⌝q ③④拒取式 ⑥p →q 前提引入 ⑦￢p ⑤⑥拒取式
证明（4）：
①t ∧r 前提引入 ②t ①化简律 ③q s 前提引入 ④s t 前提引入
⑤q t ③④等价三段论 ⑥（q →t ）∧(t→q) ⑤ 置换 ⑦（q →t ） ⑥化简 ⑧q ②⑥ 假言推理 ⑨q →p 前提引入 ⑩p ⑧⑨假言推理 (11)p∧q ⑧⑩合取
15在自然推理系统P 中用附加前提法证明下面各推理： (1) 前提：p →(q→r),s →p,q
结论：s →r 证明
①s 附加前提引入 ②s →p 前提引入 ③p ①②假言推理 ④p →(q→r) 前提引入 ⑤q →r ③④假言推理 ⑥q 前提引入 ⑦r ⑤⑥假言推理
16在自然推理系统P 中用归谬法证明下面各推理：
(1)前提：p →⌝q, ⌝r ∨q,r ∧⌝s
结论：⌝p 证明：
①p 结论的否定引入 ②p →﹁q 前提引入
③﹁q ①②假言推理 ④￢r ∨q 前提引入 ⑤￢r ④化简律 ⑥r ∧￢s 前提引入 ⑦r ⑥化简律 ⑧r ∧﹁r ⑤⑦ 合取
由于最后一步r ∧﹁r 是矛盾式, 所以推理正确.
第四章部分课后习题参考答案
3. 在一阶逻辑中将下面将下面命题符号化, 并分别讨论个体域限制为(a),(b)条件时命题的真值: (1) 对于任意x, 均有(2) 存在x, 使得x+5=9. 其中(a)个体域为自然数集合. (b)个体域为实数集合. 解：
F(x):
2=(x+
)(x
). 2=(x+
)(x
).
G(x): x+5=9.
(1)在两个个体域中都解释为∀xF (x ) ，在（a ）中为假命题，在(b)中为真命题。 (2)在两个个体域中都解释为∃xG (x ) ，在（a ）(b)中均为真命题。
4. 在一阶逻辑中将下列命题符号化: (1) 没有不能表示成分数的有理数. (2) 在北京卖菜的人不全是外地人. 解:
(1)F(x): x能表示成分数 H(x): x是有理数
命题符号化为: ⌝∃x (⌝F (x ) ∧H (x )) (2)F(x): x是北京卖菜的人 H(x): x是外地人
命题符号化为: ⌝∀x (F (x ) →H (x )) 5. 在一阶逻辑将下列命题符号化: (1) 火车都比轮船快.
(3) 不存在比所有火车都快的汽车. 解:
(1)F(x): x是火车; G(x): x是轮船; H(x,y): x比y 快
命题符号化为: ∀x ∀y ((F (x ) ∧G (y )) →H (x , y )) (2) (1)F(x): x是火车; G(x): x是汽车; H(x,y): x比y 快 命题符号化为: ⌝∃y (G (y ) ∧∀x (F (x ) →H (x , y ))) 9. 给定解释I 如下:
(a) 个体域D 为实数集合R. (b) D中特定元素=0.
(c) 特定函数(x,y)=xy,x,y ∈D .
(d) 特定谓词(x,y):x=y,(x,y):x
答:(1) 对于任意两个实数x,y, 如果x
(2) 对于任意两个实数x,y, 如果x-y=0, 那么x
（a ） 个体域D=N(N为自然数集合). （b ） D中特定元素=2. （c ） D上函数
=x+y,(x,y)=xy.
（d ） D上谓词(x,y):x=y.
说明下列各式在I 下的含义，并讨论其真值. (1) xF(g(x,a),x)
(2) x y(F(f(x,a),y)→F(f(y,a),x) 答:(1) 对于任意自然数x, 都有2x=x, 真值0.
(2) 对于任意两个自然数x,y, 使得如果x+2=y, 那么y+2=x. 真值0.
11. 判断下列各式的类型:
(1) (3)
yF(x,y).
解:(1)因为 p →(q →p ) ⇔⌝p ∨(⌝q ∨p ) ⇔1 为永真式； 所以
(3)取解释I 个体域为全体实数 F(x,y)：x+y=5
所以, 前件为任意实数x 存在实数y 使x+y=5，前件真； 后件为存在实数x 对任意实数y 都有x+y=5，后件假，]
为永真式；
此时为假命题
再取解释I 个体域为自然数N ， F(x,y)：:x+y=5
所以, 前件为任意自然数x 存在自然数y 使x+y=5，前件假。此时为假命题。
此公式为非永真式的可满足式。 13. 给定下列各公式一个成真的解释，一个成假的解释。
(1)
(F(x)
(2) x(F(x)G(x)H(x)) 解:(1)个体域:本班同学
F(x)：x 会吃饭, G(x)：x 会睡觉. 成真解释
F(x)：x 是泰安人,G(x)：x 是济南人. （2）成假解释 (2)个体域:泰山学院的学生
F(x)：x 出生在山东,G(x):x出生在北京,H(x):x出生在江苏, 成假解释. F(x)：x 会吃饭,G(x)：x 会睡觉,H(x)：x 会呼吸. 成真解释.
第五章部分课后习题参考答案
5. 给定解释Ｉ如下:
(a)个体域D={3,4};
(b)f (x ) 为f (3) =4, f (4) =3
(c)F (x , y ) 为F (3, 3) =F (4, 4) =0, F (3, 4) =F (4, 3) =1. 试求下列公式在Ｉ下的真值. (1)∀x ∃yF (x , y )
(3)∀x ∀y (F (x , y ) →F (f (x ), f (y ))) 解:(1) ∀x ∃yF (x , y ) ⇔∀x (F (x , 3) ∨F (x , 4))
⇔ (F (3, 3) ∨F (3, 4)) ∧(F (4, 3) ∨F (4, 4)) ⇔(0∨1) ∧(1∨0) ⇔1
(2) ∀x ∀y (F (x , y ) →F (f (x ), f (y )))
⇔∀x ((F (x , 3) →F (f (x ), f (3))) ∧(F (x , 4) →F (f (x ), f (4))))
⇔∀x ((F (x , 3) →F (f (x ), 4)) ∧(F (x , 4) →F (f (x ), 3))) ⇔((F (3, 3) →F (f (3), 4)) ∧(F (3, 4) →F (f (3), 3)))
∧((F (4, 3) →F (f (4), 4)) ∧(F (4, 4) →F (f (4), 3)))
⇔((0→F (4, 4)) ∧(F (3, 4) →F (4, 3))) ∧((1→F (3, 4)) ∧(0→F (3, 3)))
⇔(0→0) ∧(1→1) ∧(1→1) ∧(0→0) ⇔1 12. 求下列各式的前束范式。
(1)∀xF (x ) →∀yG (x , y )
(5)∃x 1F (x 1, x 2) →(H (x 1) →⌝∃x 2G (x 1, x 2)) (本题课本上有错误)
解:(1) ∀xF (x ) →∀yG (x , y ) ⇔∀xF (x ) →∀yG (t , y ) ⇔∃x ∀y (F (x ) →G (t , y )) (5) ∃x 1F (x 1, x 2) →(H (x 1) →⌝∃x 2G (x 1, x 2))
⇔∃x 1F (x 1, x 2) →(H (x 3) →∀x 2⌝G (x 3, x 2)) ⇔∃x 1F (x 1, x 4) →∀x 2(H (x 3) →⌝G (x 3, x 2)) ⇔∀x 1∀x 2(F (x 1, x 4) →(H (x 3) →⌝G (x 3, x 2)))
15. 在自然数推理系统F 中, 构造下面推理的证明:
(1) 前提: ∃xF (x ) →∀y ((F (y ) ∨G (y )) →R (y )) , ∃xF (x )
结论: ∃xR(x)
(2) 前提: ∀x(F(x)→(G(a)∧R(x))), xF(x)
结论:x(F(x)∧R(x)) 证明(1)
①∃xF (x ) 前提引入 ②F(c) ①EI
③∃xF (x ) →∀y ((F (y ) ∨G (y )) →R (y )) 前提引入 ④∀y ((F (y ) ∨G (y )) →R (y )) ①③假言推理 ⑤(F(c)∨G(c))→R(c)) ④UI ⑥F(c)∨G(c) ②附加 ⑦R(c) ⑤⑥假言推理 ⑧∃xR(x) ⑦EG (2)
①∃xF(x) 前提引入 ②F(c) ①EI
③∀x(F(x)→(G(a)∧R(x))) 前提引入 ④F(c)→(G(a)∧R(c)) ③UI
⑤G(a)∧R(c) ②④假言推理 ⑥R(c) ⑤化简 ⑦F(c)∧R(c) ②⑥合取引入
⑧∃x(F(x)∧R(x))
第六章部分课后习题参考答案
5. 确定下列命题是否为真：
（1）∅⊆∅ 真 （2）∅∈∅ 假 （3）∅⊆{∅}
真
（4）∅∈{∅} 真 （5）｛a,b ｝⊆｛a,b,c, ｛a,b,c ｝｝ 真 （6）｛a,b ｝∈｛a,b,c, ｛a,b ｝｝ 真 （7）｛a,b ｝⊆｛a,b, ｛｛a,b ｝｝｝ 真 （8）｛a,b ｝∈｛a,b, ｛｛a,b ｝｝｝ 假
6．设a,b,c 各不相同，判断下述等式中哪个等式为真: （1）｛｛a,b ｝，c,
｝ =｛｛a,b ｝,c ｝ 假
（2）｛a ,b,a｝=｛a,b ｝ 真 （3）｛｛a ｝，{b}｝=｛｛a,b ｝｝ 假 （4）｛∅，｛∅｝，a,b ｝=｛｛∅, ｛∅｝｝,a,b ｝ 假 8．求下列集合的幂集：
（1）｛a,b,c ｝ P(A)={ ∅,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}} （2）｛1，｛2，3｝｝ P(A)={ ∅, {1}, {{2,3}}, {1，{2，3}} } （3）｛∅｝ P(A)={ ∅, ｛∅｝ }
（4）｛∅，｛∅｝｝ P(A)={ ∅, {1}, {{2,3}}, {1，{2，3}} } 14．化简下列集合表达式： （1）（A B ） B ）-（A B ） （2）（（A B C ）-（B C ）） A 解:
(1)（A B ） B ）-（A B ）=（A B ） B ） ～（A B ）
=（A B ） ～（A B ）) B=∅ B=∅
（2）（（A B C ）-（B C ）） A=（（A B C ） ～（B C ）） A =（A ～（B C ）） （（B C ） ～（B C ）） A =（A ～（B C ）） ∅ A=（A ～（B C ）） A=A
18．某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球
和网球，还有2人会打这三种球。已知6个会打网球的人都会打排球。求不会打球的人数。
解: 阿A={会打篮球的人}，B={会打排球的人}，C={会打网球的人} |A|=14, |B|=12, |A B|=6,|A C|=5,| A B C|=2, |C|=6,C⊆A B 如图所示。
25-(5+4+2+3)-5-1=25-14-5-1=5
不会打球的人共5人
21. 设集合A ＝{{1，2}，{2，3}，{1，3},{∅}},计算下列表达式： （1） A （2） A （3） A （4） A 解:
（1） A={1，2} {2，3} {1，3} {∅}={1，2，3, ∅}
（2） A={1，2} {2，3} {1，3} {∅}=∅
（3） A=1 2 3 ∅=∅
（4） A=∅27、设A,B,C 是任意集合，证明 (1)(A-B)-C=A- B⋃C (2)(A-B)-C=(A-C)-(B-C) 证明
(1) (A-B)-C=(A ～B) ～C= A ( ～B ～C)= A ～(B⋃C) =A- B⋃C (2) (A-C)-(B-C)=(A ～C) ～(B ～C)= (A ～C) (～B C)
=(A ～C ～B) (A ～C C)= (A ～C ～B) ∅ = A ～(B⋃C ) =A- B⋃C 由（1）得证。
第七章部分课后习题参考答案
7. 列出集合A={2,3,4}上的恒等关系I A , 全域关系E A , 小于或等于关系L A , 整除关系D A . 解：I A ={,,}
EA ={,,,,,,,,}
L A ={,,,,,} D A ={}
13. 设
A={,,}
篮球或
B={,,}
求A ⋃B,A ⋂B, domA, domB, dom(A⋃B), ranA, ranB, ran(A⋂B ), fld(A-B). 解：A ⋃B={,,,,} A⋂B={}
domA={1,2,3} domB={1,2,4} dom(A∨B)={1,2,3,4}
ranA={2,3,4} ranB={2,3,4} ran(A⋂B)={4} fld R=dom R⋃ran R
A-B={,}，fld(A-B)={1,2,3} 14. 设R={,,,,}
求R R, R -1, R ↑{0,1,}, R[{1,2}]
解：R R={,,}
R , ={,,,,,}
R ↑{0,1}={,,,,} R[{1,2}]=ran(R↑{1,2})={2,3}
16．设A={a,b,c,d}，R 1
R 1
-1
，
R 2为A 上的关系，其中
=
{
a , a , a , b , b , d
}
R 2={a , d , b , c , b , d , c , b
23
求R 1 R 2, R 2 R 1, R 1, R 2。
解: R1 R 2={,,} R2 R 1={}
R 12=R1 R 1={,,} R 2=R2 R 2={,,} R 23=R2 R 22={,,}
36．设A={1，2，3，4}，在A ⨯A 上定义二元关系R ，
∀,∈A ⨯A ，〈u,v> R ⇔u + y = x + v.
2
(1) 证明R 是A ⨯A 上的等价关系. (2)确定由R 引起的对A ⨯A 的划分. （1）证明：∵R ⇔u+y=x-y
∴R⇔u-v=x-y
∀∈A ⨯A
∵u-v=u-v ∴R ∴R 是自反的
任意的,∈A ×A 如果R ，那么u-v=x-y ∴x-y=u-v ∴R
∴R 是对称的
任意的,,∈A ×A 若R,R 则u-v=x-y,x-y=a-b ∴u-v=a-b ∴R ∴R 是传递的
∴R 是A ×A 上的等价关系
(2) ∏={{,,,}, {,,}, {,}, {}, {,,}, {,}, {} }
41. 设A={1，2，3，4}，R 为A ⨯A 上的二元关系, ∀〈a ，b 〉，〈c ，d 〉∈ A ⨯A , 〈a ，b 〉R 〈c ，d 〉⇔a + b = c + d
(1) 证明R 为等价关系. (2) 求R 导出的划分. (1)证明：∀
a+b=a+b ∴R ∴R 是自反的
任意的,∈A ×A 设R，则a+b=c+d ∴c+d=a+b ∴R ∴R 是对称的
任意的,,∈A ×A
若R,R 则a+b=c+d,c+d=x+y ∴a+b=x+y ∴R ∴R 是传递的
∴R 是 A×A 上的等价关系
(2)∏={{}, {,}, {,,}, {,,,}, {,,}, {,}, {}}
43. 对于下列集合与整除关系画出哈斯图:
(1) {1,2,3,4,6,8,12,24}
(2) {1,2,3,4,5,6,7,8,9,10,11,12}
解
:
842
1
63
1
11
7
(1) (2)
45. 下图是两个偏序集的哈斯图. 分别写出集合A 和偏序关系R 的集合表达式.
d
g
b
f
g
a
a
(a) (b)
解: (a)A={a,b,c,d,e,f,g}
R ={,,,,,,,,,}⋃I A
(b) A={a,b,c,d,e,f,g}
R ={,,,,,,}⋃I A
46. 分别画出下列各偏序集的哈斯图, 并找出A 的极大元`极小元`最大元和最小元.
(1)A={a,b,c,d,e}
R ={,,,,,,}⋃I A . (2)A={a,b,c,d,e}, R ={}⋃IA.
解:
d
e
a
b
c
(1) (2) 项目 (1) (2) 极大元: e a,b,d,e 极小元: a a,b,c,e 最大元: e 无 最小元: a 无 第八章部分课后习题参考答案
1． 设f :N→N, 且
⎧1，若x 为奇数⎪
f (x)=⎨x
⎪若x 为偶数⎩2，
求f (0), f ({0}), f (1), f ({1}), f ({0,2,4,6,„})，f ({4,6,8}), f -1({3,5,7}). 解：f (0)=0, f ({0})={0}, f (1)=1, f ({1})={1},
f ({0,2,4,6,„})=N，f ({4,6,8})={2,3,4}, f -1 ({3,5,7})={6,10,14}. 4. 判断下列函数中哪些是满射的? 哪些是单射的? 哪些是双射的? (1) f:N→N, f(x)=x2+2 不是满射，不是单射
(2) f:N→N,f(x)=(x)mod 3, x 除以3的余数 不是满射，不是单射 ⎧1，若x 为奇数
(3) f:N→N,f(x)=⎨ 不是满射，不是单射
0，若x 为偶数⎩
⎧0，若x 为奇数
(4) f:N→{0,1},f(x)=⎨ 是满射，不是单射
⎩1，若x 为偶数
(5) f:N-{0}→R,f(x)=lgx 不是满射，是单射
(6) f:R→R,f(x)=x2-2x-15 不是满射，不是单射
5. 设X={a,b,c,d},Y={1,2,3},f={,,,}判断以下命题的真假: (1)f是从X 到Y 的二元关系, 但不是从X 到Y 的函数; 对 (2)f是从X 到Y 的函数, 但不是满射, 也不是单射的; 错 (3)f是从X 到Y 的满射, 但不是单射; 错 (4)f是从X 到Y 的双射. 错
第十章部分课后习题参考答案
4．判断下列集合对所给的二元运算是否封闭： （1） 整数集合Z 和普通的减法运算。
封闭, 不满足交换律和结合律，无零元和单位元 （2） 非零整数集合
普通的除法运算。不封闭
（R ）和矩阵加法及乘法运算，其中n 2。
（3） 全体n ⨯n 实矩阵集合
封闭 均满足交换律，结合律，乘法对加法满足分配律； 加法单位元是零矩阵，无零元；
乘法单位元是单位矩阵，零元是零矩阵；
（4）全体n ⨯n 实可逆矩阵集合关于矩阵加法及乘法运算，其中n 2。不封闭 （5）正实数集合
和运算，其中运算定义为：
不封闭 因为 1 1=1⨯1-1-1=-1∉R （6）
n
关于普通的加法和乘法运算。
+
封闭，均满足交换律，结合律，乘法对加法满足分配律 加法单位元是0，无零元；
乘法无单位元（n >1），零元是0；n =1单位元是1 （7）A = {a 1, a 2, , a n } n
运算定义如下：
封闭 不满足交换律，满足结合律， （8）
S =
关于普通的加法和乘法运算。
封闭 均满足交换律，结合律，乘法对加法满足分配律 （9）S = {0,1},S是关于普通的加法和乘法运算。 加法不封闭，乘法封闭；乘法满足交换律，结合律
（10）
S = ,S 关于普通的加法和乘法运算。
加法不封闭，乘法封闭，乘法满足交换律，结合律
5．对于上题中封闭的二元运算判断是否适合交换律，结合律，分配律。 见上题
7． 设 * 为Z +上的二元运算∀x , y ∈Z +，
X * Y = min ( x，y ),即x 和y 之中较小的数.
(1) 求4 * 6，7 * 3。 4, 3
(2)* 在Z 上是否适合交换律，结合律，和幂等律？ 满足交换律，结合律，和幂等律
(3)求*运算的单位元，零元及Z +中所有可逆元素的逆元。 单位元无，零元1, 所有元素无逆元
8．S =Q ⨯Q Q 为有理数集，*为S 上的二元运算，,
可结合：(*)*=*= *(*)=*= (*)*=*(*) 不是幂等的
（2）*运算是否有单位元，零元？ 如果有请指出，并求S 中所有可逆元素的逆元。 设是单位元，
S ，*= *=
S 有
+
则==，解的=，即为单位。
设是零元，
S ，*= *=
则==，无解。即无零元。
S ，设是它的逆元*= *=
==
a=1/x,b=-y/x
所以当x ≠0时，
>-1=
1x , -y x
10．令S={a，b}，S 上有四个运算：*，
分别有表10.8确定。
(a) (b) (c) (d)
(1)这4个运算中哪些运算满足交换律，结合律，幂等律？ (a) 交换律，结合律，幂等律都满足， 零元为a, 没有单位元； (b)满足交换律和结合律，不满足幂等律，单位元为a, 没有零元
a
-1
=a , b
-1
=b
(c)满足交换律, 不满足幂等律, 不满足结合律 a (b b ) =a a =b , a (b b ) ≠(a b ) b 没有单位元, 没有零元
(d) 不满足交换律，满足结合律和幂等律 没有单位元, 没有零元
(2) 求每个运算的单位元，零元以及每一个可逆元素的逆元。 见上
16．设V=〈 N，+ ，〉，其中+ ，分别代表普通加法与乘法，对下面给定的每个集合确定它是否构成V 的子代数，为什么？
（1）S 1=（2）S 2=
是
不是 加法不封闭
(a b ) b =a b =a
（3）S 3 = {-1，0，1} 不是，加法不封闭
第十一章部分课后习题参考答案
8. 设S={0，1，2，3}，
为模4乘法，即
y=(xy)mod 4
"∀x,y ∈S, x
问〈S ，
〉是否构成群？为什么？
y=(xy)mod 4∈S ,
是S 上的代数运算。
解：(1) ∀x,y ∈S, x
(2) ∀x,y,z ∈S, 设xy=4k+r 0≤r ≤3
(x
y)
z =((xy)mod 4)
z=r
z=(rz)mod 4
=(4kz+rz)mod 4=((4k+r)z)mod 4 =(xyz)mod 4 同理x 所以，(x(3) ∀x ∈S, (x
(yy)
z) =(xyz)mod 4 z = x1)=(1
(y
z) ，结合律成立。
x)=x,，所以1是单位元。
(4)1-1=1, 3-1=3, 0和2没有逆元 所以，〈S ，
9. 设Z 为整数集合，在Z 上定义二元运算。如下： " ∀x,y ∈Z,xoy= x+y-2 问Z 关于o 运算能否构成群？为什么？
解：(1) ∀x,y ∈Z, xoy= x+y-2∈Z ,o 是Z 上的代数运算。 (2) ∀x,y,z ∈Z,
(xoy) oz =(x+y-2)oz=(x+y-2)+z-2=x+y+z-4 同理(xoy)oz= xo(yoz)，结合律成立。
(3)设e 是单位元，∀x ∈Z, xoe = e ox=x,即x+e -2= e +x-2=x, e=2 (4) ∀x ∈Z , 设x 的逆元是y, xoy= yox=e , 即x+y-2=y+x-2=2, 所以，x -1=y =4-x 所以〈Z ，o 〉构成群
⎧⎛111. 设G=⎨
⎩⎝0
0⎫⎪, ⎪1⎭
⎛1 0⎝
0⎫⎪, ⎪-1⎭
⎛-1 0⎝
0⎫⎪, ⎪1⎭
⎛-1 0⎝
0⎫⎫⎪⎬，证明G 关于矩阵乘法构成一个群． ⎪-1⎭⎭
〉不构成群
解：(1) ∀x,y ∈G, 易知xy ∈G, 乘法是Z 上的代数运算。
(2) 矩阵乘法满足结合律 (3)设
⎛1⎝0
0⎫
⎪是单位元， 1⎪⎭
(4)每个矩阵的逆元都是自己。 所以G 关于矩阵乘法构成一个群．
14. 设G 为群，且存在a∈G,使得 G={ak ∣k∈Z} 证明：G 是交换群。
证明:∀x,y ∈G ，设x =a k , l
y =a ，则
xy =a k a l =a k +l ==a l +k =a l a k =yx 所以，G 是交换群
17. 设G 为群，证明e 为G 中唯一的幂等元。
22
证明:设e 0∈G 也是幂等元，则e 0=e 0，即e 0=e 0e ，由消去律知e 0=e
18. 设G 为群，a,b,c∈G,证明
∣abc∣=∣bca∣=∣cab∣ 证明：先证设(abc ) k =e ⇔(bca ) k =e
设(abc ) k =e , 则(abc )(abc )(abc ) (abc ) =e ，
-1
即 a (b c )(a b c )(a b c ) a (b c ) a a =e
左边同乘a -1，右边同乘a 得
(bca )(bca )(bca ) (bca ) =(bac )
k
=a ea =e
-1
反过来，设(bac ) k =e , 则(abc ) k =e .
由元素阶的定义知，∣abc∣=∣bca∣，同理∣bca∣=∣cab∣
19. 证明：偶数阶群G 必含2阶元。
证明：设群G 不含2阶元，∀a ∈G ，当a =e 时，a 是一阶元，当a ≠e 时，a 至少是3阶元, 因为群G 时有限阶的，所以a 是有限阶的，设a 是k 阶的, 则a
-1
也是k 阶的，所以高于3阶的元成对出
现的，G 不含2阶元，G 含唯一的1阶元e , 这与群G 是偶数阶的矛盾。所以，偶数阶群G 必含2阶元
20. 设G 为非Abel 群，证明G 中存在非单位元a 和b,a≠b,且ab=ba. 证明：先证明G 含至少含3阶元。
若G 只含1阶元, 则G={e},G为Abel 群矛盾；
若G 除了1阶元e 外, 其余元a 均为2阶元，则a =e ，a
∀a , b ∈G , a
-1
2-1
=a
-1
=a , b
-1
=b , (ab )
-1
=ab , 所以ab =a b
-1-1
=(ba ) =ba ，
与G 为Abel 群矛盾；
222
所以，G 含至少含一个3阶元，设为a ，则a ≠a ，且a a =aa 。
令b =a 的证。
21. 设G 是M n (R)上的加法群，n≥2，判断下述子集是否构成子群。
2
（1）全体对称矩阵 是子群 （2）全体对角矩阵 是子群
（3）全体行列式大于等于0的矩阵. 不是子群 （4）全体上（下）三角矩阵。 是子群
22. 设G 为群，a 是G 中给定元素，a 的正规化子N （a ）表示G 中与a 可交换的元素构成的集合，即 N（a ）={x∣x ∈G ∧xa=ax} 证明N （a ）构成G 的子群。 证明：ea=ae,e ∈N (a ) ≠φ
∀x , y ∈N (a ),
则
ax =xa , ay =ya
a (xy ) =(ax ) y =(xa ) y =x (ay ) =x (ya ) =(xy ) a , 所以xy ∈N (a )
由ax =xa ，得x -1axx
-1
=x
-1
xax
-1
, x ae =eax
-1-1
，即x -1a =ax -1，所以x -1∈N (a )
所以N （a ）构成G 的子群
31. 设ϕ1是群G 1到G 2的同态，ϕ2是G 2到G 3的同态，证明ϕ1 ϕ2是G 1到G 3的同态。 证明：有已知ϕ1是G 1到G 2的函数，ϕ2是G 2到G 3的函数，则ϕ1·ϕ2是G 1到G 3的函数。 ∀a , b ∈G 1, (ϕ1 ϕ2)(ab ) =ϕ2(ϕ1(ab )) =ϕ2(ϕ1(a ) ϕ1(b )) =(ϕ2(ϕ1(a )))(ϕ2(ϕ1(b ))) =(ϕ1 ϕ2)(a )(ϕ1 ϕ2)(b ) 所以:ϕ1·ϕ2是G 1到G 3的同态。
33. 证明循环群一定是阿贝尔群，说明阿贝尔群是否一定为循环群，并证明你的结论。 证明：设G 是循环群, 令G=,∀x , y ∈G , 令x =a k , y =a l , 那么
xy =a a =a
k
l
k +l
=a
l +k
=a a
l k
=yx ,G 是阿贝尔群
克莱因四元群, G ={e , a , b , c }
e a b c
e e a b c
a a e c b
b b c e a
c c b a e
是交换群, 但不是循环群, 因为e 是一阶元，a,b,c 是二阶元。 36. 设σ, τ是5元置换，且
⎛1σ= 2
⎝
21
34
45
5⎫⎛1⎪，τ= ⎪ 33⎭⎝
24
35
41
5⎫
⎪ 2⎪⎭
(1)计算στ, τσ, τ(2)将τσ, τ
-1
-1
, σ
-1
, σ
-1
τσ；
, σ
-1
τσ表示成不交的轮换之积。
(3)将（2）中的置换表示成对换之积，并说明哪些为奇置换，哪些为偶置换。 解：(1) τσ= 4
⎝
σ
-1
⎛12535
3343
42
5⎫⎛1⎪ στ= 41⎪⎭⎝
-1
2324
3131
4243
5⎫
⎪ τ5⎪⎭5⎫⎪ 2⎪⎭
-1
⎛1
= 4⎝
25
31
42
5⎫⎪ 3⎪⎭
⎛1
= 2⎝
21
5⎫⎪ σ4⎪⎭
-1
τσ= 5
⎝
-1
⎛1
(2) τσ=(1425) τ=(14253) στσ=(143)(25)
(3) τσ=(14)(12)(15) 奇置换， τ
-1
=(14)(12)(15)(13) 偶置换
σ-1τσ=(14)(13)(25) 奇置换
第十四章部分课后习题参考答案
5、设无向图G 有10条边，3度与4度顶点各2个，其余顶点的度数均小于3，问G 至少有多少个顶点？在最少顶点的情况下，写出度数列、∆(G ) 、δ(G ) 。 解：由握手定理图G 的度数之和为：2⨯10=20
3度与4度顶点各2个，这4个顶点的度数之和为14度。 其余顶点的度数共有6度。
其余顶点的度数均小于3，欲使G 的顶点最少，其余顶点的度数应都取2, 所以，G 至少有7个顶点, 出度数列为3,3,4,4,2,2,2, ∆(G ) =4, δ(G ) =2.
7、设有向图D 的度数列为2，3，2，3，出度列为1，2，1，1，求D 的入度列，并求∆(D ), δ(D ) ，
∆(D ), δ(D ) , ∆(D ), δ(D ) .
+
+
-
-
解：D 的度数列为2，3，2，3，出度列为1，2，1，1，D 的入度列为1,1,1,2.
∆(D ) =3, δ(D ) =2, ∆(D ) =2, δ(D ) =1, ∆(D ) =2, δ(D ) =1
+
+
-
-
8、设无向图中有6条边，3度与5度顶点各1个，其余顶点都是2度点，问该图有多少个顶点？
解：由握手定理图G 的度数之和为：2⨯6=12
设2度点x 个，则3⨯1+5⨯1+2x =12，x =2，该图有4个顶点.
14、下面给出的两个正整数数列中哪个是可图化的？对可图化的数列，试给出3种非同构的无向图，其中至少有两个时简单图。
(1) 2,2,3,3,4,4,5 (2) 2,2,2,2,3,3,4,4 解：(1) 2+2+3+3+4+4+5=23 是奇数，不可图化； (2) 2＋2+2+2+3+3+4+4=16, 是偶数，可图化；
18、设有3个4阶4条边的无向简单图G 1、G 2、G 3，证明它们至少有两个是同构的。
证明：4阶4条边的无向简单图的顶点的最大度数为3，度数之和为8，因而度数列为2，2，2，2；3，2，2，1；3，3，1，1。但3，3，1，1对应的图不是简单图。所以从同构的观点看，4阶4条边的无向简单图只有两个：
所以，G 1、G 2、G 3至少有两个是同构的。
20、已知n 阶无向简单图G 有m 条边，试求G 的补图G 的边数m '。
解：m '=
n (n -1)
2
-m
21、无向图G 如下图
(1)求G 的全部点割集与边割集，指出其中的割点和桥； (2) 求G 的点连通度k (G ) 与边连通度λ(G ) 。
a
c
解：点割集: {a,b},(d)
边割集{e2,e3},{e3,e4},{e1,e2},{e1,e4}{e1,e3},{e2,e4},{e5}
k (G ) =λ(G ) =1
23、求G 的点连通度k (G ) 、边连通度λ(G ) 与最小度数δ(G ) 。
解：k (G ) =2、λ(G ) =3 、δ(G ) =4
28、设n 阶无向简单图为3-正则图，且边数m 与n 满足2n-3=m问这样的无向图有几种非同构的情况？
解：⎨
⎧3n =2m ⎩2n -3=m
得
n=6,m=9.
31、设图G 和它的部图G 的边数分别为m 和m ，试确定G 的阶数。
解：m +m =
n (n +1)
+8(m +m ) 2
得n =
-1+2
45、有向图D 如图
(1)求v 2到v 5长度为1，2，3，4的通路数；
(2)求v 5到v 5长度为1，2，3，4的回路数； (3)求D 中长度为4的通路数；
(4)求D 中长度小于或等于4的回路数； (5)写出D 的可达矩阵。
v1
v4
v3
解：有向图D 的邻接矩阵为： ⎛ 00001⎫1010⎫⎛0 10100⎪⎛ 0⎪ 0
0002⎪ 2
⎪ 0
2A = 0
0001⎪，A 2
= ⎪ 01010⎪A 3
= ⎪ 20 10100⎪ 00002⎪ 02 ⎝0
1010⎪⎭ ⎝2
2
0⎪⎭ ⎝0
0⎛ 00004⎫⎛0121 40400⎪ ⎪ 5
252A
4
= 00004⎪234
⎪ A +A +A +A = 2121 40400⎪ 4252 ⎝0
404
0⎪⎭ ⎝2
5
2
5
(1)v 2到v 5长度为1，2，3，4的通路数为0,2,0,0； (2)v 5到v 5长度为1，2，3，4的回路数为0,0,4,0；
200⎫020⎪⎪200⎪⎪020⎪00
4⎪⎭
5⎫
2⎪⎪5⎪⎪ 2⎪4⎪⎭
(3)D中长度为4的通路数为32； (4)D中长度小于或等于4的回路数10； ⎛1 1
(4)出D 的可达矩阵P = 1
1 ⎝1
1111⎫
⎪
1111⎪1111⎪
⎪
1111⎪
⎪
1111⎭
第十六章部分课后习题参考答案
1、画出所有5阶和7阶非同构的无向树
.
2、一棵无向树T 有5片树叶，3个2度分支点，其余的分支点都是3度顶点，问T 有几个顶点? 解：设3度分支点x 个，则
5⨯1+3⨯2+3x =2⨯(5+3+x -1) ，解得x =3
T 有11个顶点
3、无向树T 有8个树叶，2个3度分支点，其余的分支点都是4度顶点，问T 有几个4度分支点？根据T 的度数列，请至少画出4棵非同构的无向树。
解：设4度分支点x 个，则
8⨯1+2⨯3+4x =2⨯(8+2+x -1) ，解得x =2
度数列
[1**********]4
4、棵无向树T 有n i (i=2，3，„，k ) 个i 度分支点，其余顶点都是树叶，问T 应该有几片树叶? 解：设树叶x 片，则
n i ⨯i +x ⨯1=2⨯(n i +x -1) ，解得x =(i -2) n i +2 评论：2，3，4题都是用了两个结论, 一是握手定理，二是m =n -1 5、n(n≥3) 阶无向树T 的最大度解：2，n-1
6、若n(n≥3) 阶无向树T 的最大度解：n-1
7、证明：n(n≥2) 阶无向树不是欧拉图. 证明：无向树没有回路，因而不是欧拉图。 8、证明：n(n≥2) 阶无向树不是哈密顿图. 证明：无向树没有回路，因而不是哈密顿图。 9、证明：任何无向树T 都是二部图.
证明：无向树没有回路，因而不存在技术长度的圈，是二部图。 10、什么样的无向树T 既是欧拉图，又是哈密顿图? 解：一阶无向树
14、设e 为无向连通图G 中的一条边， e 在G 的任何生成树中，问e 应有什么性质?
解：e 是桥
15、设e 为无向连通图G 中的一条边， e 不在G 的任何生成树中， 问e 应有什么性质?
解：e 是环
23、已知n 阶m 条的无向图 G 是k(k≥2) 棵树组成的森林，证明：m = n-k.；
证明：数学归纳法。k=1时, m = n-1，结论成立；
设k=t-1(t-1≥1) 时，结论成立，当k=t时, 无向图 G 是t 棵树组成的森林, 任取两棵树，每棵树任取一个顶点，这两个顶点连线。则所得新图有t-1棵树，所以m = n-（k-1）.
所以原图中m = n-k 得证。
24、在图16.6所示2图中，实边所示的生成子图T 是该图的生成树.
(1)指出T 的弦，及每条弦对应的基本回路和对应T 的基本回路系统.
(2) 指出T 的所有树枝， 及每条树枝对应的基本割集和对应T 的基本割集系统.
=2，问T 中最长的路径长度为几？ 至少为几？最多为几？
图16.16 解：(a)T的弦：c,d,g,h
(a) (b)
T 的基本回路系统: S={{a,c,b},{a,b,f,d},{e,a,b,h},{e,a,b,f,g}} T 的所有树枝: e,a,b,f
T 的基本割集系统: S={{e,g,h},{a,c,d,g,h},{b,c,d,g,h},{f,d,g}} (b)有关问题仿照给出
25、求图16.17所示带权图中的最小生成树.
(a) (b)
图16.17
解：
注：答案不唯一。
37、画一棵权为3，4，5，6，7，8，9的最优2叉树，并计算出它的权.
38. 下面给出的各符号串集合哪些是前缀码? A1={0，10，110，1111} 是前缀码 A2={1，01，001，000} 是前缀码 A3={1，11，101，001，0011} 不是前缀码 A4={b，c ，aa ，ac ，aba ，abb ，abc} 是前缀码 A5={ b，c ，a ，aa ，ac ，abc ，abb ，aba} 不是前缀码 41. 设7个字母在通信中出现的频率如下: a: 35% b: 20% c: 15% d: 10% e: 10% f: 5% g: 5%
用Huffman 算法求传输它们的前缀码. 要求画出最优树，指出每个字母对应的编码. 并指出传输10n (n≥2) 个按上述频率出现的字母，需要多少个二进制数字.
解：
a:01 b:10 c:000 d:110 e:001 f:1111 g:1110 W(T)=5*4+5*4+10*3+10*3+15*3+20*2+35*2=255
传输10n (n≥2) 个按上述频率出现的字母，需要255*10n-2个二进制数字
第一章部分课后习题参考答案
16 设p 、q 的真值为0；r 、s 的真值为1，求下列各命题公式的真值。 （1）p ∨(q∧r) ⇔ 0∨(0∧1) ⇔0
（2）（p r ）∧(﹁q ∨s) ⇔（01）∧(1∨1) ⇔0∧1⇔0.
（3）（⌝p ∧⌝q ∧r ）(p∧q ∧﹁r) ⇔（1∧1∧1） (0∧0∧0) ⇔0 (4)（⌝r ∧s ）→(p∧⌝q) ⇔（0∧1）→(1∧0) ⇔0→0⇔1
17．判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。”
答：p: π是无理数 1 q: 3是无理数 0 r:
2是无理数 1
s: 6能被2整除 1
t: 6能被4整除 0
命题符号化为： p ∧(q→r) ∧(t→s) 的真值为1，所以这一段的论述为真。 19．用真值表判断下列公式的类型： （4）(p→q) →(⌝q →⌝p) （5）(p∧r) (⌝p ∧⌝q) （6）((p→q) ∧(q→r)) →(p→r)
答： （4）
p q p →q ⌝q ⌝p ⌝q →⌝p (p→q) →(⌝q →⌝p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式 //最后一列全为1
（5）公式类型为可满足式（方法如上例）//最后一列至少有一个1 （6）公式类型为永真式（方法如上例）//
第二章部分课后习题参考答案
3. 用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ⌝(p∧q →q) (2)(p→(p∨q)) ∨(p→r) (3)(p∨q) →(p∧r)
答：(2)（p →(p∨q) ）∨(p→r) ⇔(⌝p ∨(p∨q)) ∨(⌝p ∨r) ⇔⌝p ∨p ∨q ∨r ⇔1 所以公式类型为永真式
(3) P q r p ∨q p ∧r （p ∨q ）→(p∧r)
0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1
所以公式类型为可满足式 4. 用等值演算法证明下面等值式： (2)(p→q) ∧(p→r) ⇔(p→(q∧r))
(4)(p∧⌝q) ∨(⌝p ∧q) ⇔(p∨q) ∧⌝(p∧q) 证明（2）(p→q) ∧(p→r)
⇔ (⌝p ∨q) ∧(⌝p ∨r) ⇔⌝p ∨(q∧r)) ⇔p →(q∧r)
（4）(p∧⌝q) ∨(⌝p ∧q) ⇔(p∨(⌝p ∧q)) ∧(⌝q ∨(⌝p ∧q)
⇔(p∨⌝p) ∧(p∨q) ∧(⌝q ∨⌝p) ∧(⌝q ∨q) ⇔1∧(p∨q) ∧⌝(p∧q) ∧1 ⇔(p∨q) ∧⌝(p∧q)
5.求下列公式的主析取范式与主合取范式，并求成真赋值
(1)(⌝p →q) →(⌝q ∨p) (2)⌝(p→q) ∧q ∧r (3)(p∨(q∧r)) →(p∨q ∨r) 解：
（1）主析取范式
(⌝p →q) →(⌝q ∨p)
⇔⌝(p∨q) ∨(⌝q ∨p)
⇔(⌝p ∧⌝q) ∨(⌝q ∨p)
⇔ (⌝p ∧⌝q) ∨(⌝q ∧p) ∨(⌝q ∧⌝p) ∨(p∧q) ∨(p∧⌝q) ⇔ (⌝p ∧⌝q) ∨(p∧⌝q) ∨(p∧q)
⇔m 0∨m 2∨m 3
⇔∑(0,2,3)
主合取范式：
(⌝p →q) →(⌝q ∨p)
⇔⌝(p∨q) ∨(⌝q ∨p)
⇔(⌝p ∧⌝q) ∨(⌝q ∨p)
⇔(⌝p ∨(⌝q ∨p)) ∧(⌝q ∨(⌝q ∨p)) ⇔1∧(p∨⌝q) ⇔(p∨⌝q) ⇔ M1 ⇔∏(1) (2) 主合取范式为：
⌝(p→q) ∧q ∧r ⇔⌝(⌝p ∨q) ∧q ∧r ⇔(p∧⌝q) ∧q ∧r ⇔0 所以该式为矛盾式.
主合取范式为∏(0,1,2,3,4,5,6,7)
矛盾式的主析取范式为 0 (3)主合取范式为：
(p∨(q∧r)) →(p∨q ∨r)
⇔⌝(p∨(q∧r)) →(p∨q ∨r)
⇔(⌝p ∧(⌝q ∨⌝r)) ∨(p∨q ∨r)
⇔(⌝p ∨(p∨q ∨r)) ∧((⌝q ∨⌝r)) ∨(p∨q ∨r))
⇔1∧1 ⇔1
所以该式为永真式.
永真式的主合取范式为 1
主析取范式为∑(0,1,2,3,4,5,6,7)
第三章部分课后习题参考答案
14. 在自然推理系统P 中构造下面推理的证明： (2)前提：p →q, ⌝(q∧r),r
结论：⌝p
(4)前提：q →p,q s,s t,t ∧r 结论：p ∧q
证明：（2）
①⌝(q∧r) 前提引入 ②⌝q ∨⌝r ①置换 ③q →⌝r ②蕴含等值式 ④r 前提引入
⑤⌝q ③④拒取式 ⑥p →q 前提引入 ⑦￢p ⑤⑥拒取式
证明（4）：
①t ∧r 前提引入 ②t ①化简律 ③q s 前提引入 ④s t 前提引入
⑤q t ③④等价三段论 ⑥（q →t ）∧(t→q) ⑤ 置换 ⑦（q →t ） ⑥化简 ⑧q ②⑥ 假言推理 ⑨q →p 前提引入 ⑩p ⑧⑨假言推理 (11)p∧q ⑧⑩合取
15在自然推理系统P 中用附加前提法证明下面各推理： (1) 前提：p →(q→r),s →p,q
结论：s →r 证明
①s 附加前提引入 ②s →p 前提引入 ③p ①②假言推理 ④p →(q→r) 前提引入 ⑤q →r ③④假言推理 ⑥q 前提引入 ⑦r ⑤⑥假言推理
16在自然推理系统P 中用归谬法证明下面各推理：
(1)前提：p →⌝q, ⌝r ∨q,r ∧⌝s
结论：⌝p 证明：
①p 结论的否定引入 ②p →﹁q 前提引入
③﹁q ①②假言推理 ④￢r ∨q 前提引入 ⑤￢r ④化简律 ⑥r ∧￢s 前提引入 ⑦r ⑥化简律 ⑧r ∧﹁r ⑤⑦ 合取
由于最后一步r ∧﹁r 是矛盾式, 所以推理正确.
第四章部分课后习题参考答案
3. 在一阶逻辑中将下面将下面命题符号化, 并分别讨论个体域限制为(a),(b)条件时命题的真值: (1) 对于任意x, 均有(2) 存在x, 使得x+5=9. 其中(a)个体域为自然数集合. (b)个体域为实数集合. 解：
F(x):
2=(x+
)(x
). 2=(x+
)(x
).
G(x): x+5=9.
(1)在两个个体域中都解释为∀xF (x ) ，在（a ）中为假命题，在(b)中为真命题。 (2)在两个个体域中都解释为∃xG (x ) ，在（a ）(b)中均为真命题。
4. 在一阶逻辑中将下列命题符号化: (1) 没有不能表示成分数的有理数. (2) 在北京卖菜的人不全是外地人. 解:
(1)F(x): x能表示成分数 H(x): x是有理数
命题符号化为: ⌝∃x (⌝F (x ) ∧H (x )) (2)F(x): x是北京卖菜的人 H(x): x是外地人
命题符号化为: ⌝∀x (F (x ) →H (x )) 5. 在一阶逻辑将下列命题符号化: (1) 火车都比轮船快.
(3) 不存在比所有火车都快的汽车. 解:
(1)F(x): x是火车; G(x): x是轮船; H(x,y): x比y 快
命题符号化为: ∀x ∀y ((F (x ) ∧G (y )) →H (x , y )) (2) (1)F(x): x是火车; G(x): x是汽车; H(x,y): x比y 快 命题符号化为: ⌝∃y (G (y ) ∧∀x (F (x ) →H (x , y ))) 9. 给定解释I 如下:
(a) 个体域D 为实数集合R. (b) D中特定元素=0.
(c) 特定函数(x,y)=xy,x,y ∈D .
(d) 特定谓词(x,y):x=y,(x,y):x
答:(1) 对于任意两个实数x,y, 如果x
(2) 对于任意两个实数x,y, 如果x-y=0, 那么x
（a ） 个体域D=N(N为自然数集合). （b ） D中特定元素=2. （c ） D上函数
=x+y,(x,y)=xy.
（d ） D上谓词(x,y):x=y.
说明下列各式在I 下的含义，并讨论其真值. (1) xF(g(x,a),x)
(2) x y(F(f(x,a),y)→F(f(y,a),x) 答:(1) 对于任意自然数x, 都有2x=x, 真值0.
(2) 对于任意两个自然数x,y, 使得如果x+2=y, 那么y+2=x. 真值0.
11. 判断下列各式的类型:
(1) (3)
yF(x,y).
解:(1)因为 p →(q →p ) ⇔⌝p ∨(⌝q ∨p ) ⇔1 为永真式； 所以
(3)取解释I 个体域为全体实数 F(x,y)：x+y=5
所以, 前件为任意实数x 存在实数y 使x+y=5，前件真； 后件为存在实数x 对任意实数y 都有x+y=5，后件假，]
为永真式；
此时为假命题
再取解释I 个体域为自然数N ， F(x,y)：:x+y=5
所以, 前件为任意自然数x 存在自然数y 使x+y=5，前件假。此时为假命题。
此公式为非永真式的可满足式。 13. 给定下列各公式一个成真的解释，一个成假的解释。
(1)
(F(x)
(2) x(F(x)G(x)H(x)) 解:(1)个体域:本班同学
F(x)：x 会吃饭, G(x)：x 会睡觉. 成真解释
F(x)：x 是泰安人,G(x)：x 是济南人. （2）成假解释 (2)个体域:泰山学院的学生
F(x)：x 出生在山东,G(x):x出生在北京,H(x):x出生在江苏, 成假解释. F(x)：x 会吃饭,G(x)：x 会睡觉,H(x)：x 会呼吸. 成真解释.
第五章部分课后习题参考答案
5. 给定解释Ｉ如下:
(a)个体域D={3,4};
(b)f (x ) 为f (3) =4, f (4) =3
(c)F (x , y ) 为F (3, 3) =F (4, 4) =0, F (3, 4) =F (4, 3) =1. 试求下列公式在Ｉ下的真值. (1)∀x ∃yF (x , y )
(3)∀x ∀y (F (x , y ) →F (f (x ), f (y ))) 解:(1) ∀x ∃yF (x , y ) ⇔∀x (F (x , 3) ∨F (x , 4))
⇔ (F (3, 3) ∨F (3, 4)) ∧(F (4, 3) ∨F (4, 4)) ⇔(0∨1) ∧(1∨0) ⇔1
(2) ∀x ∀y (F (x , y ) →F (f (x ), f (y )))
⇔∀x ((F (x , 3) →F (f (x ), f (3))) ∧(F (x , 4) →F (f (x ), f (4))))
⇔∀x ((F (x , 3) →F (f (x ), 4)) ∧(F (x , 4) →F (f (x ), 3))) ⇔((F (3, 3) →F (f (3), 4)) ∧(F (3, 4) →F (f (3), 3)))
∧((F (4, 3) →F (f (4), 4)) ∧(F (4, 4) →F (f (4), 3)))
⇔((0→F (4, 4)) ∧(F (3, 4) →F (4, 3))) ∧((1→F (3, 4)) ∧(0→F (3, 3)))
⇔(0→0) ∧(1→1) ∧(1→1) ∧(0→0) ⇔1 12. 求下列各式的前束范式。
(1)∀xF (x ) →∀yG (x , y )
(5)∃x 1F (x 1, x 2) →(H (x 1) →⌝∃x 2G (x 1, x 2)) (本题课本上有错误)
解:(1) ∀xF (x ) →∀yG (x , y ) ⇔∀xF (x ) →∀yG (t , y ) ⇔∃x ∀y (F (x ) →G (t , y )) (5) ∃x 1F (x 1, x 2) →(H (x 1) →⌝∃x 2G (x 1, x 2))
⇔∃x 1F (x 1, x 2) →(H (x 3) →∀x 2⌝G (x 3, x 2)) ⇔∃x 1F (x 1, x 4) →∀x 2(H (x 3) →⌝G (x 3, x 2)) ⇔∀x 1∀x 2(F (x 1, x 4) →(H (x 3) →⌝G (x 3, x 2)))
15. 在自然数推理系统F 中, 构造下面推理的证明:
(1) 前提: ∃xF (x ) →∀y ((F (y ) ∨G (y )) →R (y )) , ∃xF (x )
结论: ∃xR(x)
(2) 前提: ∀x(F(x)→(G(a)∧R(x))), xF(x)
结论:x(F(x)∧R(x)) 证明(1)
①∃xF (x ) 前提引入 ②F(c) ①EI
③∃xF (x ) →∀y ((F (y ) ∨G (y )) →R (y )) 前提引入 ④∀y ((F (y ) ∨G (y )) →R (y )) ①③假言推理 ⑤(F(c)∨G(c))→R(c)) ④UI ⑥F(c)∨G(c) ②附加 ⑦R(c) ⑤⑥假言推理 ⑧∃xR(x) ⑦EG (2)
①∃xF(x) 前提引入 ②F(c) ①EI
③∀x(F(x)→(G(a)∧R(x))) 前提引入 ④F(c)→(G(a)∧R(c)) ③UI
⑤G(a)∧R(c) ②④假言推理 ⑥R(c) ⑤化简 ⑦F(c)∧R(c) ②⑥合取引入
⑧∃x(F(x)∧R(x))
第六章部分课后习题参考答案
5. 确定下列命题是否为真：
（1）∅⊆∅ 真 （2）∅∈∅ 假 （3）∅⊆{∅}
真
（4）∅∈{∅} 真 （5）｛a,b ｝⊆｛a,b,c, ｛a,b,c ｝｝ 真 （6）｛a,b ｝∈｛a,b,c, ｛a,b ｝｝ 真 （7）｛a,b ｝⊆｛a,b, ｛｛a,b ｝｝｝ 真 （8）｛a,b ｝∈｛a,b, ｛｛a,b ｝｝｝ 假
6．设a,b,c 各不相同，判断下述等式中哪个等式为真: （1）｛｛a,b ｝，c,
｝ =｛｛a,b ｝,c ｝ 假
（2）｛a ,b,a｝=｛a,b ｝ 真 （3）｛｛a ｝，{b}｝=｛｛a,b ｝｝ 假 （4）｛∅，｛∅｝，a,b ｝=｛｛∅, ｛∅｝｝,a,b ｝ 假 8．求下列集合的幂集：
（1）｛a,b,c ｝ P(A)={ ∅,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}} （2）｛1，｛2，3｝｝ P(A)={ ∅, {1}, {{2,3}}, {1，{2，3}} } （3）｛∅｝ P(A)={ ∅, ｛∅｝ }
（4）｛∅，｛∅｝｝ P(A)={ ∅, {1}, {{2,3}}, {1，{2，3}} } 14．化简下列集合表达式： （1）（A B ） B ）-（A B ） （2）（（A B C ）-（B C ）） A 解:
(1)（A B ） B ）-（A B ）=（A B ） B ） ～（A B ）
=（A B ） ～（A B ）) B=∅ B=∅
（2）（（A B C ）-（B C ）） A=（（A B C ） ～（B C ）） A =（A ～（B C ）） （（B C ） ～（B C ）） A =（A ～（B C ）） ∅ A=（A ～（B C ）） A=A
18．某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球
和网球，还有2人会打这三种球。已知6个会打网球的人都会打排球。求不会打球的人数。
解: 阿A={会打篮球的人}，B={会打排球的人}，C={会打网球的人} |A|=14, |B|=12, |A B|=6,|A C|=5,| A B C|=2, |C|=6,C⊆A B 如图所示。
25-(5+4+2+3)-5-1=25-14-5-1=5
不会打球的人共5人
21. 设集合A ＝{{1，2}，{2，3}，{1，3},{∅}},计算下列表达式： （1） A （2） A （3） A （4） A 解:
（1） A={1，2} {2，3} {1，3} {∅}={1，2，3, ∅}
（2） A={1，2} {2，3} {1，3} {∅}=∅
（3） A=1 2 3 ∅=∅
（4） A=∅27、设A,B,C 是任意集合，证明 (1)(A-B)-C=A- B⋃C (2)(A-B)-C=(A-C)-(B-C) 证明
(1) (A-B)-C=(A ～B) ～C= A ( ～B ～C)= A ～(B⋃C) =A- B⋃C (2) (A-C)-(B-C)=(A ～C) ～(B ～C)= (A ～C) (～B C)
=(A ～C ～B) (A ～C C)= (A ～C ～B) ∅ = A ～(B⋃C ) =A- B⋃C 由（1）得证。
第七章部分课后习题参考答案
7. 列出集合A={2,3,4}上的恒等关系I A , 全域关系E A , 小于或等于关系L A , 整除关系D A . 解：I A ={,,}
EA ={,,,,,,,,}
L A ={,,,,,} D A ={}
13. 设
A={,,}
篮球或
B={,,}
求A ⋃B,A ⋂B, domA, domB, dom(A⋃B), ranA, ranB, ran(A⋂B ), fld(A-B). 解：A ⋃B={,,,,} A⋂B={}
domA={1,2,3} domB={1,2,4} dom(A∨B)={1,2,3,4}
ranA={2,3,4} ranB={2,3,4} ran(A⋂B)={4} fld R=dom R⋃ran R
A-B={,}，fld(A-B)={1,2,3} 14. 设R={,,,,}
求R R, R -1, R ↑{0,1,}, R[{1,2}]
解：R R={,,}
R , ={,,,,,}
R ↑{0,1}={,,,,} R[{1,2}]=ran(R↑{1,2})={2,3}
16．设A={a,b,c,d}，R 1
R 1
-1
，
R 2为A 上的关系，其中
=
{
a , a , a , b , b , d
}
R 2={a , d , b , c , b , d , c , b
23
求R 1 R 2, R 2 R 1, R 1, R 2。
解: R1 R 2={,,} R2 R 1={}
R 12=R1 R 1={,,} R 2=R2 R 2={,,} R 23=R2 R 22={,,}
36．设A={1，2，3，4}，在A ⨯A 上定义二元关系R ，
∀,∈A ⨯A ，〈u,v> R ⇔u + y = x + v.
2
(1) 证明R 是A ⨯A 上的等价关系. (2)确定由R 引起的对A ⨯A 的划分. （1）证明：∵R ⇔u+y=x-y
∴R⇔u-v=x-y
∀∈A ⨯A
∵u-v=u-v ∴R ∴R 是自反的
任意的,∈A ×A 如果R ，那么u-v=x-y ∴x-y=u-v ∴R
∴R 是对称的
任意的,,∈A ×A 若R,R 则u-v=x-y,x-y=a-b ∴u-v=a-b ∴R ∴R 是传递的
∴R 是A ×A 上的等价关系
(2) ∏={{,,,}, {,,}, {,}, {}, {,,}, {,}, {} }
41. 设A={1，2，3，4}，R 为A ⨯A 上的二元关系, ∀〈a ，b 〉，〈c ，d 〉∈ A ⨯A , 〈a ，b 〉R 〈c ，d 〉⇔a + b = c + d
(1) 证明R 为等价关系. (2) 求R 导出的划分. (1)证明：∀
a+b=a+b ∴R ∴R 是自反的
任意的,∈A ×A 设R，则a+b=c+d ∴c+d=a+b ∴R ∴R 是对称的
任意的,,∈A ×A
若R,R 则a+b=c+d,c+d=x+y ∴a+b=x+y ∴R ∴R 是传递的
∴R 是 A×A 上的等价关系
(2)∏={{}, {,}, {,,}, {,,,}, {,,}, {,}, {}}
43. 对于下列集合与整除关系画出哈斯图:
(1) {1,2,3,4,6,8,12,24}
(2) {1,2,3,4,5,6,7,8,9,10,11,12}
解
:
842
1
63
1
11
7
(1) (2)
45. 下图是两个偏序集的哈斯图. 分别写出集合A 和偏序关系R 的集合表达式.
d
g
b
f
g
a
a
(a) (b)
解: (a)A={a,b,c,d,e,f,g}
R ={,,,,,,,,,}⋃I A
(b) A={a,b,c,d,e,f,g}
R ={,,,,,,}⋃I A
46. 分别画出下列各偏序集的哈斯图, 并找出A 的极大元`极小元`最大元和最小元.
(1)A={a,b,c,d,e}
R ={,,,,,,}⋃I A . (2)A={a,b,c,d,e}, R ={}⋃IA.
解:
d
e
a
b
c
(1) (2) 项目 (1) (2) 极大元: e a,b,d,e 极小元: a a,b,c,e 最大元: e 无 最小元: a 无 第八章部分课后习题参考答案
1． 设f :N→N, 且
⎧1，若x 为奇数⎪
f (x)=⎨x
⎪若x 为偶数⎩2，
求f (0), f ({0}), f (1), f ({1}), f ({0,2,4,6,„})，f ({4,6,8}), f -1({3,5,7}). 解：f (0)=0, f ({0})={0}, f (1)=1, f ({1})={1},
f ({0,2,4,6,„})=N，f ({4,6,8})={2,3,4}, f -1 ({3,5,7})={6,10,14}. 4. 判断下列函数中哪些是满射的? 哪些是单射的? 哪些是双射的? (1) f:N→N, f(x)=x2+2 不是满射，不是单射
(2) f:N→N,f(x)=(x)mod 3, x 除以3的余数 不是满射，不是单射 ⎧1，若x 为奇数
(3) f:N→N,f(x)=⎨ 不是满射，不是单射
0，若x 为偶数⎩
⎧0，若x 为奇数
(4) f:N→{0,1},f(x)=⎨ 是满射，不是单射
⎩1，若x 为偶数
(5) f:N-{0}→R,f(x)=lgx 不是满射，是单射
(6) f:R→R,f(x)=x2-2x-15 不是满射，不是单射
5. 设X={a,b,c,d},Y={1,2,3},f={,,,}判断以下命题的真假: (1)f是从X 到Y 的二元关系, 但不是从X 到Y 的函数; 对 (2)f是从X 到Y 的函数, 但不是满射, 也不是单射的; 错 (3)f是从X 到Y 的满射, 但不是单射; 错 (4)f是从X 到Y 的双射. 错
第十章部分课后习题参考答案
4．判断下列集合对所给的二元运算是否封闭： （1） 整数集合Z 和普通的减法运算。
封闭, 不满足交换律和结合律，无零元和单位元 （2） 非零整数集合
普通的除法运算。不封闭
（R ）和矩阵加法及乘法运算，其中n 2。
（3） 全体n ⨯n 实矩阵集合
封闭 均满足交换律，结合律，乘法对加法满足分配律； 加法单位元是零矩阵，无零元；
乘法单位元是单位矩阵，零元是零矩阵；
（4）全体n ⨯n 实可逆矩阵集合关于矩阵加法及乘法运算，其中n 2。不封闭 （5）正实数集合
和运算，其中运算定义为：
不封闭 因为 1 1=1⨯1-1-1=-1∉R （6）
n
关于普通的加法和乘法运算。
+
封闭，均满足交换律，结合律，乘法对加法满足分配律 加法单位元是0，无零元；
乘法无单位元（n >1），零元是0；n =1单位元是1 （7）A = {a 1, a 2, , a n } n
运算定义如下：
封闭 不满足交换律，满足结合律， （8）
S =
关于普通的加法和乘法运算。
封闭 均满足交换律，结合律，乘法对加法满足分配律 （9）S = {0,1},S是关于普通的加法和乘法运算。 加法不封闭，乘法封闭；乘法满足交换律，结合律
（10）
S = ,S 关于普通的加法和乘法运算。
加法不封闭，乘法封闭，乘法满足交换律，结合律
5．对于上题中封闭的二元运算判断是否适合交换律，结合律，分配律。 见上题
7． 设 * 为Z +上的二元运算∀x , y ∈Z +，
X * Y = min ( x，y ),即x 和y 之中较小的数.
(1) 求4 * 6，7 * 3。 4, 3
(2)* 在Z 上是否适合交换律，结合律，和幂等律？ 满足交换律，结合律，和幂等律
(3)求*运算的单位元，零元及Z +中所有可逆元素的逆元。 单位元无，零元1, 所有元素无逆元
8．S =Q ⨯Q Q 为有理数集，*为S 上的二元运算，,
可结合：(*)*=*= *(*)=*= (*)*=*(*) 不是幂等的
（2）*运算是否有单位元，零元？ 如果有请指出，并求S 中所有可逆元素的逆元。 设是单位元，
S ，*= *=
S 有
+
则==，解的=，即为单位。
设是零元，
S ，*= *=
则==，无解。即无零元。
S ，设是它的逆元*= *=
==
a=1/x,b=-y/x
所以当x ≠0时，
>-1=
1x , -y x
10．令S={a，b}，S 上有四个运算：*，
分别有表10.8确定。
(a) (b) (c) (d)
(1)这4个运算中哪些运算满足交换律，结合律，幂等律？ (a) 交换律，结合律，幂等律都满足， 零元为a, 没有单位元； (b)满足交换律和结合律，不满足幂等律，单位元为a, 没有零元
a
-1
=a , b
-1
=b
(c)满足交换律, 不满足幂等律, 不满足结合律 a (b b ) =a a =b , a (b b ) ≠(a b ) b 没有单位元, 没有零元
(d) 不满足交换律，满足结合律和幂等律 没有单位元, 没有零元
(2) 求每个运算的单位元，零元以及每一个可逆元素的逆元。 见上
16．设V=〈 N，+ ，〉，其中+ ，分别代表普通加法与乘法，对下面给定的每个集合确定它是否构成V 的子代数，为什么？
（1）S 1=（2）S 2=
是
不是 加法不封闭
(a b ) b =a b =a
（3）S 3 = {-1，0，1} 不是，加法不封闭
第十一章部分课后习题参考答案
8. 设S={0，1，2，3}，
为模4乘法，即
y=(xy)mod 4
"∀x,y ∈S, x
问〈S ，
〉是否构成群？为什么？
y=(xy)mod 4∈S ,
是S 上的代数运算。
解：(1) ∀x,y ∈S, x
(2) ∀x,y,z ∈S, 设xy=4k+r 0≤r ≤3
(x
y)
z =((xy)mod 4)
z=r
z=(rz)mod 4
=(4kz+rz)mod 4=((4k+r)z)mod 4 =(xyz)mod 4 同理x 所以，(x(3) ∀x ∈S, (x
(yy)
z) =(xyz)mod 4 z = x1)=(1
(y
z) ，结合律成立。
x)=x,，所以1是单位元。
(4)1-1=1, 3-1=3, 0和2没有逆元 所以，〈S ，
9. 设Z 为整数集合，在Z 上定义二元运算。如下： " ∀x,y ∈Z,xoy= x+y-2 问Z 关于o 运算能否构成群？为什么？
解：(1) ∀x,y ∈Z, xoy= x+y-2∈Z ,o 是Z 上的代数运算。 (2) ∀x,y,z ∈Z,
(xoy) oz =(x+y-2)oz=(x+y-2)+z-2=x+y+z-4 同理(xoy)oz= xo(yoz)，结合律成立。
(3)设e 是单位元，∀x ∈Z, xoe = e ox=x,即x+e -2= e +x-2=x, e=2 (4) ∀x ∈Z , 设x 的逆元是y, xoy= yox=e , 即x+y-2=y+x-2=2, 所以，x -1=y =4-x 所以〈Z ，o 〉构成群
⎧⎛111. 设G=⎨
⎩⎝0
0⎫⎪, ⎪1⎭
⎛1 0⎝
0⎫⎪, ⎪-1⎭
⎛-1 0⎝
0⎫⎪, ⎪1⎭
⎛-1 0⎝
0⎫⎫⎪⎬，证明G 关于矩阵乘法构成一个群． ⎪-1⎭⎭
〉不构成群
解：(1) ∀x,y ∈G, 易知xy ∈G, 乘法是Z 上的代数运算。
(2) 矩阵乘法满足结合律 (3)设
⎛1⎝0
0⎫
⎪是单位元， 1⎪⎭
(4)每个矩阵的逆元都是自己。 所以G 关于矩阵乘法构成一个群．
14. 设G 为群，且存在a∈G,使得 G={ak ∣k∈Z} 证明：G 是交换群。
证明:∀x,y ∈G ，设x =a k , l
y =a ，则
xy =a k a l =a k +l ==a l +k =a l a k =yx 所以，G 是交换群
17. 设G 为群，证明e 为G 中唯一的幂等元。
22
证明:设e 0∈G 也是幂等元，则e 0=e 0，即e 0=e 0e ，由消去律知e 0=e
18. 设G 为群，a,b,c∈G,证明
∣abc∣=∣bca∣=∣cab∣ 证明：先证设(abc ) k =e ⇔(bca ) k =e
设(abc ) k =e , 则(abc )(abc )(abc ) (abc ) =e ，
-1
即 a (b c )(a b c )(a b c ) a (b c ) a a =e
左边同乘a -1，右边同乘a 得
(bca )(bca )(bca ) (bca ) =(bac )
k
=a ea =e
-1
反过来，设(bac ) k =e , 则(abc ) k =e .
由元素阶的定义知，∣abc∣=∣bca∣，同理∣bca∣=∣cab∣
19. 证明：偶数阶群G 必含2阶元。
证明：设群G 不含2阶元，∀a ∈G ，当a =e 时，a 是一阶元，当a ≠e 时，a 至少是3阶元, 因为群G 时有限阶的，所以a 是有限阶的，设a 是k 阶的, 则a
-1
也是k 阶的，所以高于3阶的元成对出
现的，G 不含2阶元，G 含唯一的1阶元e , 这与群G 是偶数阶的矛盾。所以，偶数阶群G 必含2阶元
20. 设G 为非Abel 群，证明G 中存在非单位元a 和b,a≠b,且ab=ba. 证明：先证明G 含至少含3阶元。
若G 只含1阶元, 则G={e},G为Abel 群矛盾；
若G 除了1阶元e 外, 其余元a 均为2阶元，则a =e ，a
∀a , b ∈G , a
-1
2-1
=a
-1
=a , b
-1
=b , (ab )
-1
=ab , 所以ab =a b
-1-1
=(ba ) =ba ，
与G 为Abel 群矛盾；
222
所以，G 含至少含一个3阶元，设为a ，则a ≠a ，且a a =aa 。
令b =a 的证。
21. 设G 是M n (R)上的加法群，n≥2，判断下述子集是否构成子群。
2
（1）全体对称矩阵 是子群 （2）全体对角矩阵 是子群
（3）全体行列式大于等于0的矩阵. 不是子群 （4）全体上（下）三角矩阵。 是子群
22. 设G 为群，a 是G 中给定元素，a 的正规化子N （a ）表示G 中与a 可交换的元素构成的集合，即 N（a ）={x∣x ∈G ∧xa=ax} 证明N （a ）构成G 的子群。 证明：ea=ae,e ∈N (a ) ≠φ
∀x , y ∈N (a ),
则
ax =xa , ay =ya
a (xy ) =(ax ) y =(xa ) y =x (ay ) =x (ya ) =(xy ) a , 所以xy ∈N (a )
由ax =xa ，得x -1axx
-1
=x
-1
xax
-1
, x ae =eax
-1-1
，即x -1a =ax -1，所以x -1∈N (a )
所以N （a ）构成G 的子群
31. 设ϕ1是群G 1到G 2的同态，ϕ2是G 2到G 3的同态，证明ϕ1 ϕ2是G 1到G 3的同态。 证明：有已知ϕ1是G 1到G 2的函数，ϕ2是G 2到G 3的函数，则ϕ1·ϕ2是G 1到G 3的函数。 ∀a , b ∈G 1, (ϕ1 ϕ2)(ab ) =ϕ2(ϕ1(ab )) =ϕ2(ϕ1(a ) ϕ1(b )) =(ϕ2(ϕ1(a )))(ϕ2(ϕ1(b ))) =(ϕ1 ϕ2)(a )(ϕ1 ϕ2)(b ) 所以:ϕ1·ϕ2是G 1到G 3的同态。
33. 证明循环群一定是阿贝尔群，说明阿贝尔群是否一定为循环群，并证明你的结论。 证明：设G 是循环群, 令G=,∀x , y ∈G , 令x =a k , y =a l , 那么
xy =a a =a
k
l
k +l
=a
l +k
=a a
l k
=yx ,G 是阿贝尔群
克莱因四元群, G ={e , a , b , c }
e a b c
e e a b c
a a e c b
b b c e a
c c b a e
是交换群, 但不是循环群, 因为e 是一阶元，a,b,c 是二阶元。 36. 设σ, τ是5元置换，且
⎛1σ= 2
⎝
21
34
45
5⎫⎛1⎪，τ= ⎪ 33⎭⎝
24
35
41
5⎫
⎪ 2⎪⎭
(1)计算στ, τσ, τ(2)将τσ, τ
-1
-1
, σ
-1
, σ
-1
τσ；
, σ
-1
τσ表示成不交的轮换之积。
(3)将（2）中的置换表示成对换之积，并说明哪些为奇置换，哪些为偶置换。 解：(1) τσ= 4
⎝
σ
-1
⎛12535
3343
42
5⎫⎛1⎪ στ= 41⎪⎭⎝
-1
2324
3131
4243
5⎫
⎪ τ5⎪⎭5⎫⎪ 2⎪⎭
-1
⎛1
= 4⎝
25
31
42
5⎫⎪ 3⎪⎭
⎛1
= 2⎝
21
5⎫⎪ σ4⎪⎭
-1
τσ= 5
⎝
-1
⎛1
(2) τσ=(1425) τ=(14253) στσ=(143)(25)
(3) τσ=(14)(12)(15) 奇置换， τ
-1
=(14)(12)(15)(13) 偶置换
σ-1τσ=(14)(13)(25) 奇置换
第十四章部分课后习题参考答案
5、设无向图G 有10条边，3度与4度顶点各2个，其余顶点的度数均小于3，问G 至少有多少个顶点？在最少顶点的情况下，写出度数列、∆(G ) 、δ(G ) 。 解：由握手定理图G 的度数之和为：2⨯10=20
3度与4度顶点各2个，这4个顶点的度数之和为14度。 其余顶点的度数共有6度。
其余顶点的度数均小于3，欲使G 的顶点最少，其余顶点的度数应都取2, 所以，G 至少有7个顶点, 出度数列为3,3,4,4,2,2,2, ∆(G ) =4, δ(G ) =2.
7、设有向图D 的度数列为2，3，2，3，出度列为1，2，1，1，求D 的入度列，并求∆(D ), δ(D ) ，
∆(D ), δ(D ) , ∆(D ), δ(D ) .
+
+
-
-
解：D 的度数列为2，3，2，3，出度列为1，2，1，1，D 的入度列为1,1,1,2.
∆(D ) =3, δ(D ) =2, ∆(D ) =2, δ(D ) =1, ∆(D ) =2, δ(D ) =1
+
+
-
-
8、设无向图中有6条边，3度与5度顶点各1个，其余顶点都是2度点，问该图有多少个顶点？
解：由握手定理图G 的度数之和为：2⨯6=12
设2度点x 个，则3⨯1+5⨯1+2x =12，x =2，该图有4个顶点.
14、下面给出的两个正整数数列中哪个是可图化的？对可图化的数列，试给出3种非同构的无向图，其中至少有两个时简单图。
(1) 2,2,3,3,4,4,5 (2) 2,2,2,2,3,3,4,4 解：(1) 2+2+3+3+4+4+5=23 是奇数，不可图化； (2) 2＋2+2+2+3+3+4+4=16, 是偶数，可图化；
18、设有3个4阶4条边的无向简单图G 1、G 2、G 3，证明它们至少有两个是同构的。
证明：4阶4条边的无向简单图的顶点的最大度数为3，度数之和为8，因而度数列为2，2，2，2；3，2，2，1；3，3，1，1。但3，3，1，1对应的图不是简单图。所以从同构的观点看，4阶4条边的无向简单图只有两个：
所以，G 1、G 2、G 3至少有两个是同构的。
20、已知n 阶无向简单图G 有m 条边，试求G 的补图G 的边数m '。
解：m '=
n (n -1)
2
-m
21、无向图G 如下图
(1)求G 的全部点割集与边割集，指出其中的割点和桥； (2) 求G 的点连通度k (G ) 与边连通度λ(G ) 。
a
c
解：点割集: {a,b},(d)
边割集{e2,e3},{e3,e4},{e1,e2},{e1,e4}{e1,e3},{e2,e4},{e5}
k (G ) =λ(G ) =1
23、求G 的点连通度k (G ) 、边连通度λ(G ) 与最小度数δ(G ) 。
解：k (G ) =2、λ(G ) =3 、δ(G ) =4
28、设n 阶无向简单图为3-正则图，且边数m 与n 满足2n-3=m问这样的无向图有几种非同构的情况？
解：⎨
⎧3n =2m ⎩2n -3=m
得
n=6,m=9.
31、设图G 和它的部图G 的边数分别为m 和m ，试确定G 的阶数。
解：m +m =
n (n +1)
+8(m +m ) 2
得n =
-1+2
45、有向图D 如图
(1)求v 2到v 5长度为1，2，3，4的通路数；
(2)求v 5到v 5长度为1，2，3，4的回路数； (3)求D 中长度为4的通路数；
(4)求D 中长度小于或等于4的回路数； (5)写出D 的可达矩阵。
v1
v4
v3
解：有向图D 的邻接矩阵为： ⎛ 00001⎫1010⎫⎛0 10100⎪⎛ 0⎪ 0
0002⎪ 2
⎪ 0
2A = 0
0001⎪，A 2
= ⎪ 01010⎪A 3
= ⎪ 20 10100⎪ 00002⎪ 02 ⎝0
1010⎪⎭ ⎝2
2
0⎪⎭ ⎝0
0⎛ 00004⎫⎛0121 40400⎪ ⎪ 5
252A
4
= 00004⎪234
⎪ A +A +A +A = 2121 40400⎪ 4252 ⎝0
404
0⎪⎭ ⎝2
5
2
5
(1)v 2到v 5长度为1，2，3，4的通路数为0,2,0,0； (2)v 5到v 5长度为1，2，3，4的回路数为0,0,4,0；
200⎫020⎪⎪200⎪⎪020⎪00
4⎪⎭
5⎫
2⎪⎪5⎪⎪ 2⎪4⎪⎭
(3)D中长度为4的通路数为32； (4)D中长度小于或等于4的回路数10； ⎛1 1
(4)出D 的可达矩阵P = 1
1 ⎝1
1111⎫
⎪
1111⎪1111⎪
⎪
1111⎪
⎪
1111⎭
第十六章部分课后习题参考答案
1、画出所有5阶和7阶非同构的无向树
.
2、一棵无向树T 有5片树叶，3个2度分支点，其余的分支点都是3度顶点，问T 有几个顶点? 解：设3度分支点x 个，则
5⨯1+3⨯2+3x =2⨯(5+3+x -1) ，解得x =3
T 有11个顶点
3、无向树T 有8个树叶，2个3度分支点，其余的分支点都是4度顶点，问T 有几个4度分支点？根据T 的度数列，请至少画出4棵非同构的无向树。
解：设4度分支点x 个，则
8⨯1+2⨯3+4x =2⨯(8+2+x -1) ，解得x =2
度数列
[1**********]4
4、棵无向树T 有n i (i=2，3，„，k ) 个i 度分支点，其余顶点都是树叶，问T 应该有几片树叶? 解：设树叶x 片，则
n i ⨯i +x ⨯1=2⨯(n i +x -1) ，解得x =(i -2) n i +2 评论：2，3，4题都是用了两个结论, 一是握手定理，二是m =n -1 5、n(n≥3) 阶无向树T 的最大度解：2，n-1
6、若n(n≥3) 阶无向树T 的最大度解：n-1
7、证明：n(n≥2) 阶无向树不是欧拉图. 证明：无向树没有回路，因而不是欧拉图。 8、证明：n(n≥2) 阶无向树不是哈密顿图. 证明：无向树没有回路，因而不是哈密顿图。 9、证明：任何无向树T 都是二部图.
证明：无向树没有回路，因而不存在技术长度的圈，是二部图。 10、什么样的无向树T 既是欧拉图，又是哈密顿图? 解：一阶无向树
14、设e 为无向连通图G 中的一条边， e 在G 的任何生成树中，问e 应有什么性质?
解：e 是桥
15、设e 为无向连通图G 中的一条边， e 不在G 的任何生成树中， 问e 应有什么性质?
解：e 是环
23、已知n 阶m 条的无向图 G 是k(k≥2) 棵树组成的森林，证明：m = n-k.；
证明：数学归纳法。k=1时, m = n-1，结论成立；
设k=t-1(t-1≥1) 时，结论成立，当k=t时, 无向图 G 是t 棵树组成的森林, 任取两棵树，每棵树任取一个顶点，这两个顶点连线。则所得新图有t-1棵树，所以m = n-（k-1）.
所以原图中m = n-k 得证。
24、在图16.6所示2图中，实边所示的生成子图T 是该图的生成树.
(1)指出T 的弦，及每条弦对应的基本回路和对应T 的基本回路系统.
(2) 指出T 的所有树枝， 及每条树枝对应的基本割集和对应T 的基本割集系统.
=2，问T 中最长的路径长度为几？ 至少为几？最多为几？
图16.16 解：(a)T的弦：c,d,g,h
(a) (b)
T 的基本回路系统: S={{a,c,b},{a,b,f,d},{e,a,b,h},{e,a,b,f,g}} T 的所有树枝: e,a,b,f
T 的基本割集系统: S={{e,g,h},{a,c,d,g,h},{b,c,d,g,h},{f,d,g}} (b)有关问题仿照给出
25、求图16.17所示带权图中的最小生成树.
(a) (b)
图16.17
解：
注：答案不唯一。
37、画一棵权为3，4，5，6，7，8，9的最优2叉树，并计算出它的权.
38. 下面给出的各符号串集合哪些是前缀码? A1={0，10，110，1111} 是前缀码 A2={1，01，001，000} 是前缀码 A3={1，11，101，001，0011} 不是前缀码 A4={b，c ，aa ，ac ，aba ，abb ，abc} 是前缀码 A5={ b，c ，a ，aa ，ac ，abc ，abb ，aba} 不是前缀码 41. 设7个字母在通信中出现的频率如下: a: 35% b: 20% c: 15% d: 10% e: 10% f: 5% g: 5%
用Huffman 算法求传输它们的前缀码. 要求画出最优树，指出每个字母对应的编码. 并指出传输10n (n≥2) 个按上述频率出现的字母，需要多少个二进制数字.
解：
a:01 b:10 c:000 d:110 e:001 f:1111 g:1110 W(T)=5*4+5*4+10*3+10*3+15*3+20*2+35*2=255
传输10n (n≥2) 个按上述频率出现的字母，需要255*10n-2个二进制数字