第一章部分课后习题参考答案
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. 给定解释I如下:
(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. 试求下列公式在I下的真值. (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. 给定解释I如下:
(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. 试求下列公式在I下的真值. (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个二进制数字