离散数学(屈婉玲)答案

第一章部分课后习题参考答案

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 上的二元运算,,

* =

(1)*运算在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 上的二元运算,,

* =

(1)*运算在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个二进制数字


相关文章

  • 离散型随机变量的均值
  • <离散型随机变量的均值>教案 教学目标:了解离散型随机变量的均值或期望的意义,会根据离散型随机变量的分布列求出 均值或期望.理解公式"E (a ξ+b)=aEξ+b",以及"若ξ B (n,p ), ...查看


  • [离散数学]期末试题及答案
  • 326<离散数学>期末考试题(B) 一.填空题(每小题3分,共15分) 1. 设A ={{a , b },a , b , ∅},则A -∅ = ( ) ,A -{∅} = ( ) ,P (A ) 中的元素个数|P (A ) |= ...查看


  • 第46-48课时 离散型随机变量的均值与方差
  • 第46课时 离散型随机变量的均值与方差(1) 主备人:范连兵 审核人:张玉玺 知识与技能: 学会根据离散型随机变量的分布列计算均值:理解离散型随机变量的均值含义: 熟练掌握两点分布和二项分布中随机变量的均值计算. 过程与方法:在推导公式的过 ...查看


  • 2014离散数学作业5答案
  • 离散数学作业5 离散数学图论部分形成性考核书面作业 本课程形成性考核书面作业共3次,内容主要分别是集合论部分.图论部分.数理逻辑部分的综合练习,基本上是按照考试的题型(除单项选择题外)安排练习题目,目的是通过综合性书面作业,使同学自己检验学 ...查看


  • 离散数学第五版 模拟试题 及答案
  • <离散数学>模拟试题3 一. 填空题(每小题2分,共20分) 1. 已知集合A ={φ,1,2},则A 得幂集合p (A ). 2. 设集合E ={a , b , c , d , e }, A = {a , b , c }, B ...查看


  • 傅里叶变换和拉普拉斯变换的应用
  • 傅里叶变换和拉普拉斯变换的应用 积分变换的理论和方法是简化问题的一种重要而有效的数学方法,它不仅应用于许多数学分支,而且在物理与工程技术上都有广泛应用,特别是在自动控制和电信技术上,积分变换是分析问题的重要而有效的手段.本文将就积分变换中最 ...查看


  • 离散数学期末考试试题(配答案) 1
  • 广东技术师范学院 模拟试题 科 目:离散数学 考试形式:闭卷 考试时间: 120 分钟 系别.班级: 姓名: 学号: 一.填空题(每小题2分,共10分) 1. 谓词公式∀xP (x ) → P(x)∨Q(y) __________. ∃xQ ...查看


  • 八年级数学下册第12周教案
  • 第十二周 教案 第1课时 §5.4.1 数据的波动(一) 教学目标:(一)教学知识点1. 掌握极差.方差.标准差的概念.2. 明白极差.方差.标准差是反映一组数据稳定性大小的.3. 用计算器(或计算机)计算一组数据的标准差与方差. (二)能 ...查看


  • 离散数学课后习题答案第一章
  • 第一章部分课后习题参考答案 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)( ...查看


  • 离散数学期末考试试题(配答案)
  • 一.填空题(每小题2分,共10分) 1. 谓词公式∀xP (x ) →∃xQ (x ) 的前束范式是__ ∃x ∃y¬P(x)∨Q(y) __________. 2. 设全集E ={1, 2, 3, 4, 5}, A ={1, 2, 3}, ...查看


热门内容