离散数学最全最新答案 屈婉玲

第一章 命题逻辑基本概念

课后练习题答案

4.将下列命题符号化，并指出真值：

（1）p∧q,其中，p:2是素数，q:5是素数,真值为1；

（2）p∧q,其中，p:是无理数，q:自然对数的底e是无理数,真值为1； （3）p∧┐q,其中，p:2是最小的素数，q:2是最小的自然数,真值为1； （4）p∧q,其中，p:3是素数，q:3是偶数,真值为0； （5）┐p∧┐q,其中，p:4是素数，q:4是偶数,真值为0.

5.将下列命题符号化，并指出真值：

（1）p∨q,其中，p:2是偶数，q:3是偶数,真值为1； （2）p∨q,其中，p:2是偶数，q:4是偶数,真值为1； （3）p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0； （4）p∨q,其中，p:3是偶数，q:4是偶数,真值为1；

（5）┐p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0；

6.（1）(┐p∧q)∨(p∧┐q),其中，小丽从筐里拿一个苹果，q：小丽从筐里拿一个梨； （2）(p∧┐q)∨(┐p∧q),其中，p：刘晓月选学英语，q：刘晓月选学日语；.

7.因为p与q不能同时为真.

13.设p:今天是星期一，q:明天是星期二，r:明天是星期三：

（1）p→q，真值为1（不会出现前件为真，后件为假的情况）； （2）q→p，真值为1（也不会出现前件为真，后件为假的情况）； （3）pq，真值为1；

（4）p→r，若p为真，则p→r真值为0，否则，p→r真值为1.

16 设p、q的真值为 0；r、s的真值为1，求下列各命题公式的真值。 （1）p∨(q∧r) 0∨(0∧1) 0 （2）（p r）∧(﹁q∨s)

（0 1）∧(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→01 17．判断下面一段论述是否为真：

“

是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。”答：p: 是无理数 1 q: 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∨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)→(qp)

(pq)(qp) (pq)(qp) (pq)(qp)(qp)(p (pq)(pq)(pq)

m0 m2 m3

∑(0,2,3)

主合取范式：

(p→q)→(qp)

(pq)(qp) (pq)(qp)

(p(qp))(q(qp)) 1(pq) (pq) M1 ∏(1) (2) 主合取范式为： (p→q)qr(pq)qr (pq)qr0 所以该式为矛盾式.

主合取范式为∏(0,1,2,3,4,5,6,7) 矛盾式的主析取范式为 0 (3)主合取范式为：

(p(qr))→(pqr) (p(qr))→(pqr)

(p(qr))(pqr) (p(pqr))((qr))(pq

11 1

所以该式为永真式.

永真式的主合取范式为 1

主析取范式为∑(0,1,2,3,4,5,6,7)

p∧q)

q) (p q)

r))

7.(1)：∨∨∨∨ ∧∧ (2)：∨∨∨ ∧∧∧

8.(1)：1 ∨∨∨,重言式； (2)：∨ ∨∨∨∨∨ (3)：∧∧∧∧∧∧∧

11.(1)：∨∨ ∧∧∧∧ (2)：∨∨∨∨∨∨∨ (3)：0 ∧∧∧.

12.A ∧∧∧∧ ∨∨

； ；

∨；

0，矛盾式. ； 1；

.

第三章 命题逻辑的推理理论

本章自测答案

6.在解本题时，应首先将简单陈述语句符号化，然后写出推理的形式结构*，其次就是判断*是否为重言式，若*是重言式，推理就正确，否则推理就不正确，这里不考虑简单语句之间的内在联系

(1)、(3)、(6)推理正确，其余的均不正确，下面以(1)、(2)为例，证明(1)推理正确，(2)推理不正确 (1)设p:今天是星期一，q:明天是星期三，推理的形式结构为 (p→q)∧p→q(记作*1)

在本推理中，从p与q的内在联系可以知道，p与q的内在联系可以知道，p与q不可能同时为真，但在证明时，不考虑这一点，而只考虑*1是否为重言式.

可以用多种方法（如真值法、等值演算法、主析取式）证明*1为重言式，特别是，不难看出，当取A为p,B为q时，*1为假言推理定律，即 (p→q)∧p→q q

(2)设p:今天是星期一，q:明天是星期三，推理的形式结构为 (p→q)∧p→q(记作*2)

可以用多种方法证明*2不是重言式，比如，等值演算法、主析取范式（主和取范式法也可以）等 (p→q)∧q→p (┐p∨q) ∧q →p q →p ┐p∨┐q

∨∨

从而可知，*2不是重言式，故推理不正确，注意，虽然这里的p与q同时为真或同时为假，但不考虑内在联系时，*2不是重言式，就认为推理不正确.

9.设p:a是奇数，q:a能被2整除，r:a：是偶数 推理的形式结构为

(p→q┐)∧(r→q)→(r→┐p) (记为*)

可以用多种方法证明*为重言式，下面用等值演算法证明： (p→┐q)∧(r→q)→(r→┐p)

(┐p∨┐q) ∨(q∨┐r)→(┐q∨┐r) (使用了交换律) (p∨q)∨(┐p∧r)∨┐q∨┐r (┐p∨q)∨(┐q∧┐r) ┐p∨(q∨┐q)∧┐r 1

10.设p:a,b两数之积为负数，q:a,b两数种恰有一个负数，r：a，b都是负数. 推理的形式结构为

(p→q)∧┐p→(┐q∧┐r) (┐p∨q) ∧┐p→(┐q∧┐r)

┐p→(┐q∧┐r) (使用了吸收律) p∨(┐q∧┐r) ∨∨∨

由于主析取范式中只含有5个W极小项，故推理不正确.

11.略

14.证明的命题序列可不惟一，下面对每一小题各给出一个证明 ① p→(q→r) 前提引入 ② P 前提引入

③ q→r ①②假言推理 ④ q 前提引入

⑤ r ③④假言推理 ⑥ r∨s 前提引入 （2）证明：

① ┐(p∧r) 前提引入 ② ┐q∨┐r ①置换 ③ r 前提引入

④ ┐q ②③析取三段论 ⑤ p→q 前提引入 ⑥ ┐p ④⑤拒取式 （3）证明：

① p→q 前提引入 ② ┐q∨q ①置换 ③ (┐p∨q)∧(┐p∨p) ②置换 ④ ┐p∨(q∧p ③置换 ⑤ p→(p∨q) ④置换

15.(1)证明：

① S 结论否定引入

③ P ①②假言推理 ④ P→(q→r) 前提引入 ⑤ q→r ③④假言推论 ⑥ q 前提引入 ⑦ r ⑤⑥假言推理 （2）证明：

① p 附加前提引入 ② p∨q ①附加 ③ (p∨q)→(r∧s) 前提引入

④ r∧s ②③假言推理 ⑤ s ④化简 ⑥ s∨t ⑤附加 ⑦ (s∨t)→u 前提引入 ⑧ u ⑥⑦拒取式

16.(1)证明：

① p 结论否定引入 ② p→ ┐q 前提引入 ③ ┐q ①② 假言推理 ④ ┐r∨q 前提引入

⑤ ┐r ③④析取三段论 ⑥ r∧┐s 前提引入 ⑦ r ⑥化简 ⑧ ┐r∧r ⑤⑦合取 （2）证明：

① ┐(r∨s) 结论否定引入 ② ┐r∨┐s ①置换 ③ ┐r ②化简 ④ ┐s ②化简 ⑤ p→r 前提引入 ⑥ ┐p ③⑤拒取式 ⑦ q→s 前提引入 ⑧ ┐q ④⑦拒取式 ⑨ ┐p∧┐q ⑥⑧合取 ⑩ ┐(p∨q) ⑨置换 口 p∨q 前提引入

⑾①口 ┐(p∨q) ∧(p∨q) ⑩口合取

16在自然推理系统P中用归谬法证明下面各推理：

q, rq,r s (1)前提：p

结论： p 证明：

①p 结论的否定引入 ②p﹁q 前提引入 ③﹁q ①②假言推理 ④￢rq 前提引入 ⑤￢r ④化简律 ⑥r￢s 前提引入 ⑦r ⑥化简律 ⑧r﹁r ⑤⑦ 合取

由于最后一步r﹁r 是矛盾式,所以推理正确.

17．设p：A到过受害者房间，q: A在11点以前离开，r：A犯谋杀罪，s：看门人看见过A。 前提：(p∧┐q) →r , p ,q →s , ┐s 结论：r 证明：

① q→s 前提引入 ② ┐s 前提引入 ③ ┐q ①②拒取式 ④ p 前提引入

⑤ p∧┐q ③④合取

⑥（p∧┐q）→r 前提引入 ⑦ r ⑤⑥假言推理

18．（1）设 p：今天是星期六，q：我们要到颐和园玩，s：颐和园游人太多。 前提：p→(p∨r) , s→┐q , p , s 结论：r 证明：

① s→┐q 前提引入 ② s 前提引入 ③ ┐q ①②假言推理

⑤ p→(q∨r) 前提引入 ⑥ q∨r ④⑤假言推理 ⑦r ③⑥析取三段论

（2）设p:小王是理科学生，q：小王数学成绩好，r：小王是文科学生。 前提：p→q ,┐r→p ,┐q 结论：r 证明：

① p→q 前提引入 ② ┐q 前提引入 ③ ┐p ①②拒取式 ④ ┐r→p 前提引入 ⑤ r ③④拒取式

返回

第四章 (一阶)谓词逻辑基本概念

本章自测答案3. 在一阶逻辑中将下面将下面命题符号化,并分别讨论个体域限制为(a),(b)条件时命题的真值:

(1) 对于任意x,均有2=(x+)(x). (2) 存在x,使得x+5=9. 其中(a)个体域为自然数集合. (b)个体域为实数集合. 解：

F(x): 2=(x+)(x). G(x): x+5=9.

(1)在两个个体域中都解释为 xF(x)，在（a）中为假命题，在(b)中为真命题。 (2)在两个个体域中都解释为 xG(x)，在（a）(b)中均为真命题。

4.(1)┐x(F(x)∧ ┐G(x)) x( F (x) →G (x) ),其中,F(x)：x是有理数,G(x) ：x能表示成分数； (2)┐x( F (x) →G (x) ) x(F(x)∧ ┐G(x)),其中,F (x)：x在北京卖菜,G (x) ：x是外地人； (3)x( F (x) →G (x) ),其中,F (x)：x是乌鸦,G (x) ：x是黑色的； (4)xF(x)∧ G(x)),其中,F (x)：x是人,G (x) ：x天天锻炼身体。 因为本题中没有指明个体域,因而使用全总个体域。

5.(1)xy (F(x) ∧ G( y ) → H(x,y)),其中,F(x)：x是火车,G(y) ：y是轮船,H(x,y)：x比y快； (2)xy (F(x) ∧ G( y ) → H(x,y)),其中,F(x)：x是火车,G(y) ：y是汽车, H(x,y)：x比y快；

(3)┐x(F(x)∧y(G (y) → H (x,y))) x(F(x) → y(G(y) ∧ ┐H(x,y))),其中,F(x)：x是汽车,G (y) ：y是火车,H(x,y)：x比y快； (4)┐x(F(x)→y(G(y) → H(x,y))) xy(F(x)∧G(y)∧┐H(x,y))),其中,F(x)：x是汽车,G(y) ：y是火车,H(x,y)：x比y慢。 6.各命题符号化形式如下： (1)xy (x ．y = 0)； (2)xy (x ．y = 0)； (3)xy (y =x+1)

(4)xy(x ．y = y．x) (5)xy(x ．y =x+ y) (6)xy (x + y ＜0 )

9.(1)对任意数的实数x和y,若x ＜y,则x ≠ y； (2)对任意数的实数x和y,若x–y = 0,则x＜y； (3)对任意数的实数x和y,若x＜y,则x–y≠0； (4)对任意数的实数x和y,若x–y ＜0,则x=y. 其中,(1)(3)真值为1(2)与(4)真值为0.

11.(1)、(4)为永真式,(2)、(6)为永假式,(3)、(5)为可满足式。 这里仅对(3)、(4)、(5)给出证明。

(3)取解释I 为：个体域为自然数集合N,F(x,y)：x ≤ y,在下,xy F(x,y)为真,而xy F(x,y)也为真(只需取x =0即可),于是(3)中公式为真,取解释 为：个体域仍为自然数集合N,而F(x,y)：x = y。此时,xyF(x,y)为真(取y为x即可),可是xyF(x,y)为假,于是(3)中公式在 下为假,这说明(3)中公式为可满足式。

(4)设I为任意一个解释,若在I下,蕴涵式前件xy F(x,y)为假,则

xyF(x,y)→yxF(x,y)为真,若前件xyF(x,y)为真,必存在I的个体域D1中的个体常项0,使yF(0,y)为真,并且对于任意

y∈,F(0,y)为真,由于有0∈,F(0,y)为真,所以xF(x,y)为真,又其中y是任意个体变项,所以 yxF(x,y )为真,由于I的任意性,所以(4)中公式为永真式(其实,次永真式可用第五章的构造证明法证明之)。

(5)取解释为：个体域为自然数集合,F(x,y)：x = y在下,(5)中公式为真,而将F(x,y)改为F(x,y)：x ＜ y,(5)中公式就为假了,所以它为可满足式。

xxx

xx

10. 给定解释I如下：

（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) xy(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）取解释为：个体域为自然数集合N，F（x）：x为奇数，G（x）：x为偶数，在 下， x（F（x）∨G（x））为真命题。 取解释为：个体域为整数集合Z，F（x）：x为正整数，G（x）：x为为负整数，在 下， x（F（x）∨G（x））为假命题。 （2）与（3）可类似解答。

14．提示：对每个公式分别找个成真的解释，一个成假的解释。

返回

第五章 谓词逻辑等值演算与推理

本章自测答案

2.(1) (F(a)∧ F(b)∧ F (c)) ∧ (G (a )∨G (b)∨G (c)) (2) (F(a)∧ F(b)∧ F (c)) ∨ (G (a)∧G (b)∧G (c)) (3) (F(a)∧ F(b)∧ F (c)) → (G (a)∧G (b)∧G (c))

(4) (F(a ,y) ∨ F(b,y)∨ F (c,y)) → (G (a)∨G (b)∨G (c))

5.提示：先消去量词，后求真值，注意，本题3个小题消去量词时，量词的辖域均不能缩小，经过演算真值分别为：1,0,1 . (1) 的演算如下： xyF(x,y)

x (F(x,3)∨F(x,4))

(F(3,3)∨F(3,4))∧(F(4,3)∨F(4 ,4)) 1∧1 1

6.乙说得对，甲错了。本题中，全称量词 的指导变元为x ，辖域为(F (x)→G(x,y)),其中F(x )与G(x,y)中的x都是约束变元，因而不能将量词的辖域缩小。

7.演算的第一步，应用量词辖域收缩与扩张算值式时丢掉了否定联结词“ ┐”。演算的第二步，在原错的基础上又用错了等值式，即 (F(x)∧(G(y)→ H(x,y))) ≠(F(x) ∧G(y)→H (x,y))

12.公式的前束范式不唯一，下面每题各给出一个答案。 (1) xy (F(x)→ G(z,y)); (2) xt (x,y) → G(x,t,z)); (3) 4 ((F(,y) →G(,y))∧(G(,y) →F(4,y))); (4) ((F()→G(,)) → (H () → L(,))); (5) (F(,)→(F() → ┐G (,))).

13.(1)xy(F(x) ∧G(y) ∧H(x ,y)),其中，F(x):x是汽车，G(y)：y是火车，H(x，y)：x比y跑的快； (2)xy(F(x) ∧G(y)→H(x ,y)),其中，F(x):x是火车，G(y)：y是汽车，H(x，y)：x比y跑的快； (3)xy(F(x) ∧G(y) ∧┐H(x ,y)),其中，F(x):x是火车，G(y)：y是汽车，H(x，y)：x比y跑的快； (4)xy(F(x) ∧G(y) → ┐H(x ,y)),其中，F(x):x是飞机，G(y)：y是汽车，H(x，y)：x比y慢； 14.(1)对F(x) → xG(x)不能使用EI规则，它不是前束范式，首先化成前束范式。 F(x) → xG(x) <=> x(F(y)→G(x))

因为量词辖域(F(y)→G(x))中，除x外还有自由出现的y，所以不能使用EI规则。

(2)对 x F(x) → y G(y)也应先化成前束范式才能消去量词，其前束范式为 x y(F(x) →G(y)),要消去量词，既要使用UI规则，又要使用EI规则。

(3)在自然推理系统F中EG规则为 A(c)/∴x(x)

其中c为特定的个体常项，这里A(y) = F(y) →G(y)不满足要求。 (4)这里，使F(a)为真的a不一定使G(a)为真，同样地使G(b)为真的b不一定使F(b)为真，如，F(x):x为奇数，G(x):x为偶数，显然F(3)∧G(4)为真，但不存在使F(x)∧G(x)为真的个体。

(5)这里c为个体常项，不能对F(c)→G(c)引入全称量词。 15.(1)证明：①xF(x) 前提引入 ②xF(x)→ y((F(y)∨G(y)) →R(y)) 前提引入 ③y((F(y)∨G(y)) →R(y) ①②假言推理 ④F(c) ①EI ⑤(F(c)∨G(c))→R(c) ③UI

xx

⑥F(c)∨G(c) ④附加

⑦R(c) ⑤⑥假言推理 ⑧xR(x) ⑦EG (2)证明①xF(x) 前提引入 ②x((F(x)→G(a)∧R(x))) 前提引入 ③F(c) ①EI ④F(c)→G(a)∧R(a) ②UI

⑤G(a)∧R(c) ③④假言推理 ⑥R(c) ⑤化简 ⑦F(c)∧R(c) ③⑥合取 ⑧x(F(x)∧R(x)) ⑦EG (3)证明：①┐xF(x) 前提引入 ②x┐F(x) ①置换 ③┐F(c) ②UI ④x(F(x)∨G(x)) 前提引入 ⑤F(c)∨G(c) ④UI

⑥F(c) ③⑤析取三段论 ⑦xF(x) ⑥EG (4)证明①x(F(x)∨G(x)) 前提引入 ②F(y)∨G(y) ①UI ③x(┐G(x)∨┐R(x)) 前提引入 ④┐G(y)┐R(y) ③UI ⑤x R(x) 前提引入 ⑥R(y) ⑤UI

⑦┐G(y) ④⑥析取三段论 ⑧F（y） ②⑦析取三段论 ⑨xF(x) ⑧UG

17．本题不能用附加前提证明法.

20.(1)与(2)均可用附加前提证明法。

22.(1)设F(x)：x为偶数，G(x):x能被2整除。 前提:x(F(x)→G(x))，F(6) 结论：G(6)

(2)设F(x)：x是大学生，G(x):x是勤奋的，a：王晓山。 前提:x(F(x)→G(x))，┐G(a) 结论：┐F(a)

23.(1)设F(x)：x是有理数，G(x):x是实数，H(x)：x是整数。 前提:x( F(x)→G(x))， x(F(x)∧H(x)) 结论:x(G(x)∧H(x))

证明提示：先消存在量词。

(2)设F(x)：x是有理数，G(x):x是无理数，H(x)：x是实数，I(x)：x是虚数。 前提:x((F(x)∨G(x)) →H(x))， x( I(x)→┐H(x)) 结论:x(I(x)→(┐F(x)∧┐G(x)))

证明①x(I(x)→(┐H(x)) 前提引入 ②I(y)→H(y) ①UI ③x((F(x)∨G(x))→H(x)) 前提引入 ④(F(y)∨G(y))→H(y) ③UI ⑤┐H(y)→(┐F(y)∧┐G(y)) ④置换

⑥I(y)→(┐F(y)∧┐G(y)) ②⑤假言三段论 ⑦x(I(x)→(┐F(x)∧┐G(x)) ⑧UG

24.设F(x)：x喜欢步行，G(x)：x喜欢骑自行车，H(x)：x喜欢乘汽车。 前提:x(┐F(x)→┐G(x))， x(G(x)∨H(x))， x┐H(x) 结论:x┐F(x)

证明①x┐H(x) 前提引入 ②┐H(c) ①UI ③x(G(x)∨H(x)) 前提引入 ④G(c)∨H(c) ③UI

⑤G(c) ②④析取三段论 ⑥x(F(x) →G(x)) 前提引入 ⑦F(c)→┐G(c) ⑥UI

⑧┐F(c) ⑤⑦拒取式 ⑨x┐F(x) ⑧UG

25.设F(x)：x是科学工作者，G(x)：x是刻苦钻研的，H(x)：x是聪明的，I(x)：x在事业中获得成功。 前提:x(F(x)→G(x))，x(G(x)∧H(x)→I(x))，a：王大海，F(a)，H(a) 结论：I(a)

证明①F(a) 前提引入 ②x(F(x)→G(x)) 前提引入 ③F(a)→G(a) ②UI

⑤H(a) 前提引入 ⑥x(G(x)∧H(x)→I(x)) 前提引入 ⑦G(a)∧H(a)→I(a) ⑥UI

⑧G(a)∧H(a) ④⑤合取 ⑨I(a) ⑦⑧假言推理

返回

第六章 集合代数

本章自测答案

4.(1) ③ (2) ④ (3) ⑤ (4) ⑦ (5) ⑧ 6.只有(2)为真，其余为假。

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人会打这三种球。已知6个会打网球的人都会打篮球或排球。求不会打球的人数。 解: 阿A={会打篮球的人}，B={会打排球的人}，C={会打网球的人} |A|=14, |B|=12, |A B|=6,|A C|=5,| A B C|=2, |C|=6,CA B 如图所示。

25-(5+4+2+3)-5-1=25-14-5-1=5 不会打球的人共5人

打篮球和网球，还有2人会

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）得证。

9.(1) {4}；(2) {1,3,5,6}；(3) {2,3,4,5,6}；(4) {, { 1 }}；(5) {{ 4 },{1,4}}. 11.(1)； (2) {1,4,5}.

22.(2)、(3)、(4)、(8)、(10)为真，其余为假。

24.(1)为真，其余为假，因为

(P-Q) = P (P-Q)∩Q = P∩Q

= P∩Q (2)(3)(4)的反例：P ={1} ，Q ={2}

26.(A–B)∪(B–A) = (A∩B)∪(B∩A)

=(A∪B)∩(B∪B)∩(A∪A)∩(B∪A) =(A∪B)∩E∩(A∩B)=(A∪B)-(A∩B)

27.(1)(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=(A–B)- C

(3)(A–B-C=A∩B∩C =A∩C∩B=(A–C)–B 28.(1)A∩(B∪A) = (A∩B)∪(A∩A) =(A∩B)∪ =A∩B=B∩A

(2)((A∪B)∩A) = (A∪B)∪A =(A∩B)∪A = A

29.由第26题有(A-B)∪(B-A)=(A∪B)–(A∩B)，故(A-B)∪(B-A)A∪B。假若x∈A∩B，那么x∈A∪B，因此x(A∪B)-(A∩B),与(A-B)∪(B-A) = (A∪B)-(A∩B) = A∪B矛盾.

30.AB x(x∈A→x∈B) x(xB→xA) x(x∈B→x∈A) BA AB A∪AA∪B EA∪B

而A∪BE，因此AB A∪B=E反之，

A∪B = E A∩(A∪B)= A A∩B = A AB 综合上述，AB A∪B = E AB A-B = A-BB

反之A-BB (A-B)∪BB A∪BB A∪B = B AB 综合上述AB A-BB

31.任取x ,x∈A {x} A=>{x}∈P(A)=>{x}∈P(B)=>{x}B x∈B

32.先证CA∧CB CA∩B,任取x,x∈C x∈C∧x∈C x∈A∧x∈B x∈A∪B,从而得到CA∪B.再证CA∩B CA∧CB，这可以由CA∩BA,CA∩BB得到。 33.PQ P-Q= P-QP，反之，P-QP P∩(P-Q)P∩P P-Q= PQ 34.令X=，则有∪Y =，即Y = .

35.AB A∪AB∪A EB∪A因为E为全集,B∪AE综合上述B∪A=E. 36.由A∩CB∩C,A-CB-C，利用A∪CB∪D有： (A∩C)∪(A-C) (B∩C)∪(B-C)

(A∩C)∪(A∩C)(B∩C)∪(B∩C)

(A∩(C∪C)(B∩(C∪C) A∩EB∩E AB 37.恒等变形法

B=B∩(B∪A)=B∩(AB)=B∩(AC) =(B∩A)∪(B∩C)=(A∩C)∪(B∩C) =(A∪B)∩C=(A∪C)∩C=C

39.任取x，有x∈P(A) x A x B x∈P(B)，因此P(A)P(B). 40.(1)任取x有

x∈P(A)∩P(B) x∈P(A)∧x∈P(B) xA∧xB xA∩B x∈P(A∩B) (2)任取x有

x∈P(A)∪P(B) x∈P(A)∨x∈P(B) xA∧xB xA∪B x∈P(A∪B)

注意与(1)的推理不同，上面的推理中有一步是“ ”符号，而不是“ ”符号。 (3)反例如下：A = {1}，B = {2}，则 P(A)∪P(B)= {,{1},{2}} P(A∪B)={,{1},{2},{1,2}}

返回

第七章 二元关系

本章自测答案

3.(1) 任取< x,y >,有

<x,y>∈(A ∩ B)×(C ∩ D) <=>x∈A ∩ B ∧ y ∈C ∩ D x ∈A∧x ∈ B∧y ∈C∧y ∈ D (x ∈A∧y ∈C )∧(x∈B∧y∈D)

<x,y>∈A×C∧< x,y >∈B×D <x,y>∈(A×C)∩(B×D)

(2)都为假,反例如下:

A ={1}, B ={1,2}, C ={2}, D ={3} 4.(1)为假,反例如下:A ={1}, B =,C = {2}; (2)为真,证明如下:任取<x,y>有

<x,y>∈A×(B∩C)×(C∩D) x∈A∩B∧y∈B∧y∈C (x∈A∧y∈B)∧(x∈A∧y∈C)

<x,y>∈A×B∧<x,y>∈A×C <x,y>∈(A×B)∩(A×C) (3)为真,令A = 即可; (4)为假,反例如下: A = 7.={<2,2>,<3,3 >,<4,4>} ={<2 . 3>,<2,4>,<3,2>,<3,4>,<4,2>,<4,3>} ∪ LA={<2,2>,<2,3>,<2,4>,<3,3>,<3,4>,<4,4>} DA={<2,2>,<2,4>,<3,3>,<4,4>}

9.(1){<1,2>,<1,4>,<1,6>,<2,1>,<2,2>,<2,4> <2,6>,<4,1>,<4,2>,<4,4>, <4,6> <6,1>, <6,2>,<6,4> <6,6>} (2){<1,2>,<2,1>};

(3){<1,1>,<2,1>,<4,1>,<6,1>,<2,2>,<4,2>,<4,4>,<6,6>} (4){<1,2>,<2,2>,<4,2>,<6,2>} 12.（略）

13.A∩B = {<1,2>,<2,4>,<3,3>,<1,3>,<4,2>}, A ∩ B ={<2,4>} 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(A - B) = {1,2,3}

14.RR = {<0,2>,<0,3>,<1,3>}

R= {<1,0>,<2,0>,<3,0>,<2,1>,<3,1>,<3,2>} R{0,1} = {<0,1>,<0,2>,<0,3>,<1,2>,<1,3>} R[{1,2}] = {2,3}

16．设A={a,b,c,d}，R1R2为A上的关系，其中

R=，R1a,d,b,c,b,d,c ,b2

23

求122112。 解: R1 R2={<a,d>,<a,c>,<a,d>} R2 R1={<c,d>}

2

R1=R1 R1={<a,a>,<a,b>,<a,d>} 2

R2=R2 R2={<b,b>,<c,c>,<c,d>} 32

R2=R2 R2={<b,c>,<c,b>,<b,d>}

a,a,a,b,b,d

R R,R R,R,R

18.(1)F(G∪H) = FG∪FH 任取<x,y> ,有

<x,y>∈F (G∪H) t(<x,t>∈F∧<t,y>∈G∪H) t(<x,t>∈F∧(<t,y>∈G∨<t,y>∈H))

t((<x,t>∈F∧<t,y>∈G)∨(<x,t>∈F∧<t,y>∈H)) t(<x,t>∈F∧<t,y>∈G)∨t(<x,t>∈F∧<t,y>∈H)) <x,t>∈FG∨<x,t>∈FH <x,y>∈FG∪FH (2)和(4)类似可证 19.(2)任取y,有

y∈R[T∪W] x(x∈T∪W∧<x,y>∈R) x((x∈T∨x∈W)∧<x,y>∈R

x((x∈A∧<x,y>∈R)∨(x∈W∧<x,y>∈R)) x(x∈T∧<x,y>∈R)∨x(x∈W∧<x,y>∈R) y∈R[T]∨y∈R[W] y∈R[T]∩R[W] (3)任取<x,y>,有

<x,y>∈F(A∩B) x∈A∩B∈F x∈A∧x∈B∧<x,y>∈F

(x∈A∧<x,y>∈F)(x∈B∧<x,y>∈F) <x,y>∈FA∧<x,y>∈FB <x,y>∈FA∩F B 20.(1)任取<x,y>,有

<x,y>∈(∪) <=><y,x>∈∪ <x,y>∈∨<y,x>∈ <x,y>∈∨<x,y>∈ <x,y>∈∪ (2)和(1)类似可证.

21.只有对称性,因为1+1≠10,<1,1>R,R不是自反的,又由于<5,5>∈R,因此R不是反自反的,根据xRy x+y = 10=>yRx ,可知R是对称的,又由于<1,9>,<9,1>都是属于R,因此R不是反对称的, <1,9>,<9,1>都属于R,如果R是传递的,必有<1,1>属于R.但这是不成立的,因此R也不是传递的. 22.(1)关系图如图7.15所示; (P148) (2)具有反自反性、反对称性、传递性.

26.(1)R={<3,3>,<3,1>,<3,5>}, = {<3,3>,<3,1>,<3,5>}

(2)r(R)={<1,1>,<1,5>,<2,2>,<2,5>,<3,3>,<3,1>,<4,4>,<4,5>,<5,5>,<6,6>} s(R)={<1,5>,<5,1>,<2,5>,<5,2>,<3,3>,<3,1>,<1,3>,<4,5>,<5,4>} T(R)={<1,5>,<2,5>,<3,3>,<3,1>,<3,5>,<4,5>}

31.(1)R = {<2,3>,<3,2>,<2,4>,<4,2>,<3,4>,<4,3>}∪；(2)R； (3)R. 32.(1)不是等价关系，因为<1,1> R，R不是自反的；

(2)不是等价关系，因为R不是传递的，1R3，3R2但是没有1R2； (3)不是等价关系，因为<2,2> R，R不是自反的； (4)不是等价关系，因为R不是传递的。 (5)是等价关系。

33．关系图如图7.17说示 (P151)

[a] = [b] ={a,b},[c] = [d] = {c,d}

36．设

A={1，2，3，4}

，在A A上定义二元关系

R， <u,v>,<x,y>A A ，〈u,v> R <x,y>u + y = x + v.

(1) 证明R 是A A上的等价关系. (2)确定由R 引起的对A A的划分. （1）证明：∵<u,v>R<x,y> u+y=x-y

∴<u,v>R<x,y>

u-v=x-y

<u,v>A A

∵u-v=u-v ∴<u,v>R<u,v> ∴R是自反的

任意的<u,v>,<x,y>∈A×A

如果<u,v>R<x,y> ，那么u-v=x-y ∴x-y=u-v ∴<x,y>R<u,v> ∴R是对称的

任意的<u,v>,<x,y>,<a,b>∈A×A 若<u,v>R<x,y>,<x,y>R<a,b> 则u-v=x-y,x-y=a-b

∴u-v=a-b ∴<u,v>R<a,b> ∴R是传递的

∴R是A×A上的等价关系

(2) ∏={{<1,1>,<2,2>,<3,3>,<4,4>}, {<2,1>,<3,2>,<4,3>}, {<3,1>,<4,2>}, {<4,1>}, {<1,2>,<2,3>,<3,4>}, {<1,3>,<2,4>}, {<1,4>} }

38.现取x，有x∈A <x,x>∈R <x,x>∈R∧<x,x>∈R <x,x>∈R∧<x,x>∈ <x,x>∈R∩R

任取<x,y>,有<x,y>∈ R∩ <x,y>∈R∧<x,y>∈ <y,x>∈ ∧<y,x>∈R <y,x>∈R∩R 任取<x,y>,<y,z>,有

<x,y>∈R∩ ∧<y,z>∈R∩

<x,y>∈R∧<x,y>∈ ∧<y,z>∈R∧<y,z>∈ (<x,y>∈R∧<y,z>∈R)∧(<x,y>∈ ∧<y,z>∈ <x,z>∈R∧<x,z>∈R <x,z>∈R∩R

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 A

a+b=a+b

∴<a,b>R<a,b> ∴R是自反的

任意的<a,b>,<c,d>∈A×A 设<a,b>R<c,d>，则a+b=c+d ∴c+d=a+b ∴<c,d>R<a,b> ∴R是对称的

任意的<a,b>,<c,d>,<x,y>∈A×A 若<a,b>R<c,d>,<c,d>R<x,y> 则a+b=c+d,c+d=x+y

∴a+b=x+y ∴<a,b>R<x,y> ∴R是传递的

∴R是 A×A上的等价关系

(2)∏={{<1,1>}, {<1,2>,<2,1>}, {<1,3>,<2,2>,<3,1>}, {<1,4>,<4,1>,<2,3>,<3,2>}, {<2,4>,<4,2>,<3,3>}, {<3,4>,<4,3>}, {<4,4>}}

42.x,x∈A <x,x>∈R <x,x>∈R∧<x,x>∈R <x,x>∈T,T是自反的。 x,y∈A,<x,y>∈T <x,y>∈R∧<y,x>∈R

<y,x>∈R∧<x,y>∈R <y,x>∈T,T是对称的。 x,y,z∈A,<x,y>∈T∧<y,z>∈T

<x,y>∈R∧<y,x>∈R∧<y,z>∈R∧<z,y>∈R <x,y>∈R∧<y,z>∈R∧<z,y>∈R∧<y,x>∈R <x,z>∈R∧<z,x>∈R <x,z>∈T T是传递的。

43．哈斯图如下图所示.

44.(a)偏序集<A,R>,A={1,2,3,4,5},R={<1,3>,<1,5>,<2,4>,<2,5>,<3,5>,<4,5>}∪ (b)偏序集<A,R>,A={a,b,c,d,e,f},R={<a,b>,<c,d>,<e,f>}∪

(c)偏序集<A,R>,A={1,2,3,4,5}, R={<1,2>,<1,4>,<1,5>,<1,3>,<2,4>,<2,5>,<3,4>,<3,5>,<4,5>}∪

45.(a)A={a,b,c,d,e,f,g}, ={<a,b>,<a,c>,<a,d>,<a,e>,<a,f>,<a,g>,<b,d>, <b,e>,<c,f>,<c,g>}∪ (b)A = {a,b,c,d,e,f,g},R口 = {<a,b>,<a,c>,<a,d>,<a,e>,<a,f>,<d,f>,<e,f>}∪ 46.哈斯图如图7.19所示 （P153）

（1）极大元e,f；极小元a,f；没有最大与最小元。

（2）极大元a,b,d,e；极小元a,b,c,e；没有最大与最小元。

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

5、设无向图G有10条边，3度与4度顶点各2个，其余顶点的度数均小于3，问G至少有多少个顶点？在最少顶点的情况下，写出度数列、 (G)、 解：由握手定理图G的度数之和为：2 10

(G)。

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条边的无向简单图G1、G2、G3，证明它们至少有两个是同构的。

证明：4阶4条边的无向简单图的顶点的最大度数为3，度数之和为8，因而度数列为2，2，2，2；3，2，2，1；3，3，1，1。但3，3，1，1对应的图不是简单图。所以从同构的观点看，4阶4条边的无向简单图只有两个：

所以，G1、G2、G3至少有两个是同构的。

20、已知n阶无向简单图G有m条边，试求G的补图G的边数m 。

解：m

n(n 1)

m

2

21、无向图G如下图

(1)求G的全部点割集与边割集，指出其中的割点和桥； (2) 求G的点连通度k(G)与边连通度

(G)。

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

得

n=6,m=9.

2n 3 m

31、设图G和它的部图G的边数分别为

m和m，试确定G的阶数。

解：m m

n(n 1)m)

2

得

n

1 8(m 2

45、有向图D如图

(1)求v2到v5长度为1，2，3，4的通路数；

(2)求v5到v5长度为1，2，3，4的回路数； (3)求D中长度为4的通路数； (4)求D中长度小于或等于4的回路数； (5)写出D的可达矩阵。

v4

v3

解：有向图D的邻接矩阵为：

00001 0010 20

20 10100

1

00002

0202A 2 0

0001 ，A010 A320 10100 01

002

20

01010 00

20 002200 2

0000 00004 215

40400

01

52522

A4 0

0004 A A2 A3 A4 2215 40400

1

0 42

522

4040 25254

(1)v2到v5长度为1，2，3，4的通路数为0,2,0,0； (2)v5到v5长度为1，2，3，4的回路数为0,0,4,0； (3)D中长度为4的通路数为32； (4)D中长度小于或等于4的回路数10；

1

1111

11111

(4)出D的可达矩阵P 11111 11111

11111

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

0

0

0 0

4

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

度数列

111111113344

4、棵无向树T有ni (i=2，3， ，k)个i度分支点，其余顶点都是树叶，问T应该有几片树叶? 解：设树叶

x片，则

ni i x 1 2 (ni x 1)，解得x (i 2)ni 2

n 1

评论：2，3，4题都是用了两个结论,一是握手定理，二是m5、n(n≥3)阶无向树T的最大度解：2，n-1

6、若n(n≥3)阶无向树T的最大度解：n-1

至少为几？最多为几？

=2，问T中最长的路径长度为几？

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的基本割集系统.

(a) (b) 图16.16 解：(a)T的弦：c,d,g,h

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个二进制数字

本文来源：https://www.bwwdw.com/article/rr8i.html