第一章 命题逻辑基本概念
课后练习题答案
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）p
q，真值为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→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 所以公式类型为永真式
（5）公式类型为可满足式（方法如上例） （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 (吸收律) ?(p∨p)∧q∨p∧(q∨q)?p∧q∨p∧q∨p∧q∨p∧q?m10∨m00∨m11∨m10?m0∨m2∨m3?↖(0, 2, 3). 成真赋值00, 10, 11.
(2) 主析取范式为0、 无成真赋值、 为矛盾式
(3) M0 ∨ M1 ∨ M2 ∨ M3 ∨ M4 ∨ M5 ∨ M6 ∨ M7.
(1)：
∨
∨
,成真赋值为00、10、11；
(2)：0，矛盾式，无成真赋值； (3)：
∨
∨
∨
∨
∨
∨
∨
,重言式，000、001、010、011、100、101、110、111全部为成真赋值；
6. (1) (q→p)∧p
?(q∨p)∧p ?q∧p∧p ?q∧0 ?0
?M0∧M1∧M2∧M3
这是矛盾式，成假赋值00,01,10,11 （2）M4，成假赋值100 （3）主合取范式为1，为重言式
7.(1)： (2)：
8.(1)：1? (2)： (3)： 11.(1)： (2)：
∨∨
∨∨∧
?∨∧
∧∨∧
∧∨.
∧∨
∧∨
； ?1；
∨∧∨?∧∨∨∧∨∨∧
,重言式； ∨∧
∨∧
∨∧
∨
；
∨∨
∨∨
∨∨
∨?
?∧
∧∧
∧∧
； ；
?0，矛盾式.
(3)：0? 12.A?
∧
∧∧∧?∨∨.
15.(1)(p→q)→r与q→(p→r) (2(p→q)→r ?(p∨q)∨r ?(p∨q)∨r ?p∧q∨r
?p∧q∧(r∨r)∨(p∨p)∧(q∨q)∧r
?p∧q∧r∨p∧q∧r∨p∧q∧r∨p∧q∧r∨p∧q∧r∨p∧q∧r = m101∨m100∨m111∨m101∨m011∨m001 ?m1∨m3∨m4∨m5∨m7 = ↖(1,4、5、7)。 而 q→(p→r) ?q∨(p∨r) ?q∨p∨r
?(p∨p)∧q∧(r∨r)∨p∧(q∨q)∧(r∨r)∨(p∨p)∧(q∨q) ∧r
?(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)
= m0∨m1∨m4∨m5∨m0∨m1∨m2∨m3∨m1∨m3∨m5∨m7 ?m0∨m1∨m2∨m3∨m4∨m5∨m7
?↖(01、2 3,4,5、 7)。两个公式的主吸取范式不同，所以(p→q) →r,q→(p→r)。 16.
(1 )(p→q)→r与q→(p→r) (2) (1) (p→q)(p∧q)与(p∨q)→r) ?m1∨m3∨m4∨m5∨m7 q→(p→r) ?m0∨m1∨m2∨m3∨m4∨m5∨m7 所以(p→q) →r) q→(p→r) (2)(p∧q) ?m0∨m1∨m2 ?
(p∨q) ?m0 所以(p∧q) (p∨q) 17
17合取范式判断下列公式是否等值： (1)p→(q→r)与(p∧q)∨r (2)p→(q→r)与(p→q) →r
(1) p→(q→r) ?M6(p∧q)∨r ?M6
所以p→(q→r)?(p∧q)∨r (2) p→(q→r) ?M6 (p → q) →r ?M0∧M1∧M2∧M6
所以p→(q→r) (p→q)→r q→(p→r)。
20将下列公式化成与之等值且仅含 {结构型式、 →} 中联结词的公式。
(3) (p∧q) ?r。注意到A?B ?(A→B)∧(B→A) 和 A∧B ?(A∨B) ?(A→B) 只 A∨B ?A→B。(p∧q)?r 10 ?(p∧q→r)∧(r→p∧q)?((p→q)→r)∧(r→(p→q)) ?(((p→q)→r)→(r→(p→q))) 注联结词越少、 公式越长。
2.21.证明： (1) (p↑q)?(q↑p)、(p↓q) ?(q↓p)。(p↑q) ?(p∧q) ?(q∧p) ?(q↑p)。(p↓q) ?(p∨q) ?(q∨p) ?(q↓p)。
第三章 命题逻辑的推理理论
本章自测答案
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 结论否定引入 ② S→P 前提引入 ③ 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) ⑩口合取
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 前提引入 ⑤ p→(q∨r) 前提引入 ⑥ q∨r ④⑤假言推理 ⑦r ③⑥析取三段论
（2）设p:小王是理科学生，q：小王数学成绩好，r：小王是文科学生。 前提：p→q ,┐r→p ,┐q 结论：r 证明：
① p→q 前提引入 ② ┐q 前提引入 ③ ┐p ①②拒取式 ④ ┐r→p 前提引入 ⑤ r ③④拒取式
返回
第四章 (一阶)谓词逻辑基本概念
本章自测答案
1.将下面命题用0元谓词符号化：
(1) 小王学过英语和法语。
(2) 除非李建是东北人、 否则他一定怕冷。(1) 破产令 f (x): x 学过英语;F (x): x 学过法语;答： 小王。符号化为 F(a)∧F(b)。或进一步细分，L (x，y) 破产令： x 学过 y;答： 小王 ；b1： 聚会 ；b2： 法语。则符号化为 L （a、 b1 等） ∧L （a、 b2 等）。(2) 破产令 f (x): x 是东北人;G (x): x 怕冷;答： 李建。符号化为 ?F(a)→G(a) 或 ?G(a)→F(a)。或进一步细分，H (x，y) 破产令： x，y 地方人;G (x): x 怕冷;答： 小王 ；b: 东北。则符号化为 ?H （a、 b)→G(a) 或 ?G (a) →H （a，b）。
2.在一阶逻辑中将下面命题符号化，并分别讨论个体域限制为 (a)、 (b) 时命题的真值：
(1) 凡有理数都能被2整除。(2) 有的有理数能被2整除。其中 (a) 个体域为有理数集合，(b) 个体域为实数集合。() 1(a) 中，?xF(x)，其中，f (x)： x能被2整除，真值为0。(b) 中，?x(G(x) ∧F(x))，其中，g (x)： x为有理数，F (x) 同 (a) 中，真值为0。() 2(a) 中，
?xF(x)，其中，f (x)： x能被2整除，真值为1。(b) 中，?x(G(x) ∧F(x))，其中，F (x) 同 (a) 中，g (x)： x为有理数，真值为1。
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))
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 )
7.将下列各公式翻译成自然语言，个体域为整数集，并判断各命题的真假。 (1) ?x?y?z(x ?y = z) ；(2) ?x?y(x?y = 1)。
(1) 可选的翻译： ①\任意两个整数的差是整数\②\对于任意两个整数，都存在第三个整数，它等于这两个整数相减\。③\对于任意整数 x 和 y，都存在整数 z，使得 x ?y = z.\选③，直接翻译，无需数理逻辑以外的知识。以下翻译意思相同，都是错的:\有个整数，它是任意两个整数的
y = z.\这3
差\存在一个整数，对于任意两个整数，第一个整数都等于这两个整数相减\。\存在整数 z，x，y 使得对于任意整数、 都有 x ?个句子都可以符号化为 ?z?x?y (x ?y = z）。量词顺序不可随意调换。
(2) 可选的翻译： 21 ①\每个整数都有一个倒数\②\对于每个整数，都能找到另一个整数，它们相乘结果是零\。③\对于任意整数 x 都存在整数 y，使得 x?y = z.\
8.指出下列公式中的指导变元，量词的辖域，各个体变项的自由出现和约束出现： (3) ?x?y (F (x，y) ∧G (y，z)) ∨?xH (x，y，z) ?x?y (F (x，y) ∧G (y，z)) ∨?x H (x，y，z) 前件 ?x?y (F (x，y)
∧G (y，z)） 中，?的指导变元是 x ?的辖域是 ?y (F (x，y) ∧G (y，z)) ；?的指导变元是 y、 ?的辖域是 （F (x，y) ∧G (y，z))。后件 ?xH (x，y，z) 中，?的指导变元是 x，?的辖域是 H (x，y，z)。整个公式中 x 约束出现两次，y 约束出现两次，自由出现一次;z 自由出现两次。
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.
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)、(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中的个体常项
x0,使
yF(0,y)为真,并且对于任意
x
y?,F(0,y)为真,由于有
xx0?
,F(0,y)为真,所以xF(x,y)为真,又其中y是任意个体变项,所以 yxF(x,y )为真,由于I的任意性,所
x
以(4)中公式为永真式(其实,次永真式可用第五章的构造证明法证明之)。 (5)取解释可满足式。
13．（1）取解释 取解释
为：个体域为自然数集合N，F（x）：x为奇数，G（x）：x为偶数，在 下， x（F（x）∨G（x））为真命题。 为：个体域为自然数集合,F(x,y)：x = y在
下,(5)中公式为真,而将F(x,y)改为F(x,y)：x ＜ y,(5)中公式就为假了,所以它为
为：个体域为整数集合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)) . 8.在一阶逻辑中将下列命题符号化，要求用两种不同的等值形式。 (1) 没有小于负数的正数。(2) 相等的两个角未必都是对顶角。
(1) 破产令 f (x): x 小于负数，g (x): x 是正数。符合化为: ??x((F(x) ∧G(x)) ??x(G(x) →?G(x))。(2) 破产令 f (x): x 是
H (x，y) →L (x，y)) ??x?y(F(x)
角，H (x，y)： x，y 是相等的，L (x，y)： x，y 是对顶角。符合化为: ??x?y(F(x) ∧∧
12.公式的前束范式不唯一，下面每题各给出一个答案。 (1) xy (F(x)→ G(z,y)); (2) xt (x,y) → G(x,t,z)); (3) (4) (5)
(F(
F(y) ∧H (x，y) ∧?L (x，y)) ??x(F(x) ∧(?y(F(y) ∧F(y) ∧H (x，y) ∧?L (x，y)))。
x4 ((F(
((F(,
)→G()→(F(
,y) →G(,
,y))∧(G(,y) →F(4,y)));
,
)));
x
)) → (H (
,
) → L())).
) → ┐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 ⑥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 ④G(a) ①③假言推理 ⑤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) ⑧
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}} }
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}.
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??=?
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∩ =(A∪B)∩( =(A∪B)∩E∩
B)∪(B∩
A)∩(
A) B∪
A)
（4）??A=?
B∪B)∩(A∪
(A∩B)=(A∪B)-(A∩B) B∩C∩
C =A∩(B∩
(B∪C) = A-(B∪C) C) C∩
B)∪(A∩
C∩C)
27.(1)(A-B)-C = A∩ (2)(A-C)-(B-C)A∩ =A∩ =A∩
C∩(∩
B∪C) = (A∩C=(A–B)- C B∩
C =A∩
(3)(A–B-C=A∩28.(1)A∩(B∪
C∩B=(A–C)–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? AB ? 而
A)?
B
A A∪B A∪B=E反之，
A∪AA∪B ? E
A∪BE，因此AB ? 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-Q
P，反之，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∩ ? (A∩(C∪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}}
返回
C)(B∩C)∪(B∩
C)
C)(B∩(C∪C) ? A∩EB∩E ? AB
第七章 二元关系
本章自测答案
1.已知A={?,{?}},求A×P(A)。A×P(A)={ ?{?},{?,{?}}?} 3.(1) 任取< x,y >,有
?,??,??,{?}?,??,{{?}}?,??,{?,{?}}?,?{?},??,?{?},{?}?,?{?},{{?}}?, ?
?x ?A∧x ? B∧y ?C∧y ? D ?(x ?A∧y ?C )∧(x?B∧y?D) ?
(2)都为假,反例如下:
A ={1}, B ={1,2}, C ={2}, D ={3} 4.(1)为假,反例如下:A ={1}, B =,C = {2}; (2)为真,证明如下:任取
?
={<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>}
.8。 列出集合A = {?，{?} {?，{?}}，{?，{?} {?，{?}}} 上的包含关系。R?={??,??,??,{?}?,??,{?,{?}}?,??,{?,{?},{?,{?}}}?,?{?},{?}?,?{?},{?,{?}}?,?{?},{?,{?},??,{ ?}?}?,?{?,{?}}, {?,{?}}?,?{?,{?}},{?,{?},{?,{?}}}?, ?{?,{?},{?,{?}}},{?,{?},{?,{?}}}?}
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>}
.11.R i是X上的二元关系、 对于x?X定义集合
R 我 (x) = {y|xR 我 y}。显然Ri(x) ?X。如果X = {? 4，? 3，? 2，? 1，0、 1、 2、 3、 4}，且令 R1 = {〈x，y〉|x，y?X∧x < y}R2 = {〈x，y〉|x，y?X∧y?1 < x < y + 2} R3 = {〈x、 y〉|x、 y?X∧x2≤y} 求R1 (0) R1 (1) R2 (0)，R2 (? 1)，R3 (3)。R1 (0) = {1,2,3,4}R1 (1) = {2,3,4}R2 (0) = {? 1，0}R2 (? 1) = {? 2，? 1}R3 (3) = ? 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}
15.设 A = {〈?，{?，{?}} 〉、 〈 {?} ?〉} 求A?1、 A2、 A3 {?}、 [?]，A?，{{?}}、 [{{?}}]。A?1 ={?{?,{?}},??,??,{?}?}, A2 ={?{?},{?,{?}}?}, A3 =?, A{?}={??,{?,{?}}?}, A[?]={?,{?}}, 33 A?=?, A{{?}}={?{?},??}, A[{{?}}]=?
16．设A={a,b,c,d}，R1，
R2为A上的关系，其中
R1=?a,a,a,b,b,d?
R2??a,d,b,c,b,d,c,b求R1?R2,R2?R1,R1,R2。 解: R1?R2={
23?
R1=R1?R1={
2
R2=R2?R2={
2
R2=R2?R2={
3
2
18.(1)F(G∪H) = FG∪FH 任取
?t((
y?R[T∪W]?x(x?T∪W∧
?x((x?A∧
?(x?A∧
∪
) <=>
∪
?
∨
(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>}∪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}
；(2)R； (3)R.
36．设A={1，2，3，4}，在A?A上定义二元关系R，
?
∴
??
∵u-v=u-v ∴
任意的
任意的
∴u-v=a-b ∴
(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 ?
?
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是 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 ? ? 44.(a)偏序集 (b)偏序集 (c)偏序集 45.(a)A={a,b,c,d,e,f,g}, ={ （1）极大元e,f；极小元a,f；没有最大与最小元。 （2）极大元a,b,d,e；极小元a,b,c,e；没有最大与最小元。 口 = 返回 (b)A = {a,b,c,d,e,f,g},R 第八章 函数 1． 本章自测答案 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}. 2. = { , ,? } = {<1,a>,<2,b>}, = {<1,b>,<2,b>}, = {<1,c>,<2,b>}, = {<1,a>,<2,c>} = {<1,b>,<2,c>} = {<1,c>,<2,c>} = {<1,a>,<2,a>}, = {<1,b>,<2,a>}, = {<1,c>,<2,a>}, 3.(1)双射，反函数 (2)双射，反函数 =,f({8}=|8|),：R→ R， ({4}={4}； （x）= logx, ({1}) = {2}, ({1,2}) ={0,1}； (3)单射，({5}) = {<5,6>}, (4)单射，({2,3}) = {5,7}, (5)单射，({-1,2}) = {1,2}, (6)单射，((0,1)) = (1/4,3/4), (8)单射，((0,1)) = (1,+∞), ({2,3}) = {2}； ({1,3}) = {0,1}； ({1}) = {-1,1}； ([1/4,1/2]) = [0,1/2]； ({2,3}) = {1/2,1/3}. 4.(1) 单射 (2) 不单射,也不满射 (3) 不单射,也不满射 (4) 满射 (5) 单射 (6) 不单射，也不满射. 5.(1) 为真，其余都为假. 6.对于给定的A，B和f，判断f是否为从A到B的函数f： →B。如果是、 说明f是否为单射、 满射、 双射的。 (1)A = B = f (x) = x 2 + 1。f (x) = 1 ?x。f (〈x，y〉) = x ?(y+1)...() 4A = {1，2，3}，B = {p、 q、 r}，f = {〈1、 q〉、 〈2、 q〉、 〈3、 q〉}。() 5A = B = f (x) = 2 x。(6) A = B = ? f (〈x，y〉) = 〈y + 1，x + 1〉。(7) A = ?，B = f (〈x，y〉) = x 2 + 2y2。x1。(9) A = ?，B = f (〈x，y，z〉) = x + y ?z。 7.(1) 结果不唯一，={ (4) 存在单射还书的充要条件是m ≤ n ，存在满射函数的充要条件是m ≥ n, 存在双射函数的充要条件是m = n . 9.双射函数与单射函数都是n!个 10.(1)不是单射，不是满射，也不是双射； (2){<1,1>,<0,2>,<2,0>}; (3){3,5,7} 11.确定f是否为从X到Y的函数、 并对f： X →Y指出哪些是单射、 哪些是满射、 那些是双射的。 (1)X = Y = 为实数集，f (x) = x 2-x;(2) X = Y = f (x) = ↗?x ；38 1 ；x + (4) X = Y = = {x | x ?，x > 0}，f (x) = x + 1 ；x ?1 ?x (5) X = Y = f (x) = ? ?x ?1 x?1 .12.设f: S→T，证明。 (1) f (a ∩ B) ?f (A) ∩ f (B)、 其中A、 B ?S。(2) 举出反例说明等式f (a ∩ B) = f (A) ∩ f (B) 不是永远为真的。(3) 说明 对于什么函数、 上述等式为真。G： 13.设A为非空集合，R为A上的等价关系，→A / R 为自然映射。(1) 设R为整数集合上的模n相等关系、 求g(2)。(2) 说明g的性质 (单射、 满射、 双射)。(3) 说明在什么条件下、 g为双射函数。 14.设S为集合，且?A，?T表示T的特征函数，B是S的子集，A = {从中、 1〉、 〈b、 1〉、 〈c、 0〉、 〈d、 0〉}，?B = {从中、 0〉、 〈b、 1〉、 〈c、 0〉、 〈d、 1〉}，求?AB。∩ 15.15.设A={1，2，3，4}，A1 = {1，2}，A2 = {1}，A3 = ?，求A1，A2、 A3和A的特征函数?A1、 ?A2、 ?A3和?A。 16.设A={a、 b、 c}。R为A上的等价关系，且 R = {从中、 b〉、 〈b、 a〉} ∪IA 求自然映射g: A→A/R. 17.fg(x)=2x +7, bf(x) =2x +4, ff(x) =x +6, gg(x) =4x +3, hf(x)=x/2 +3, gh(x) = x +1/2, fh(x) =(x +5)/2 gh f(x) =x +7/2 18.ff(n) =n+2, gf(n)=2n+1, fg(n)=2n+2, gh(n) =0 hg(n)=, hgf(n)=. 19.(1)gf(x)=x+8x +14, fg(x)=x+2 (2)都不是单射，也不是满射和双射。 (3)g和h有反函数，g:R→R,g(x) = x–4; h:R→R,h(x)=20． (1)fg:N→N, fg(x) (2)不是单射，不是满射，也不是双射。 21.(1)单射，假设f(因为<0,0>ran (2)不存在反函数 (3)ran={ 23.设f1、 f2、 f3、 f4为实数集到的函数、 且 ?) = f( )，那么< , +1> = <,+1>。根据有序对相等的条件得=，因此f是单射的，但是f不是满射的， 1、 x ≥0 f1 (x) = ? ??1，x?0 f2 (x) = x，，??1，x为整率、 ?1，否则 f4 (x) = 1。在上定义二元关系E 我、 ?x、 y?、 〈x、 y〉?E 我 ?f (x) = f (y)、 则E i是上的等价关系、 名称为f i导出的等价关系、 求商集/E 我 = 1，2，3，4。 24.这些函数都是不唯一的，以下只是一个可能的结果。 (1)f = {<1,a>,<2,b>,<3,c>} (2)f(x) = 2x (3)f(x) = ｜x｜ - 1 (4)f(x) = e 返回 第九章 集合的基数 本章自测答案 1.令:P(A)→2,(T) = Xт, 假如( ), ）≠（ )， ,?P(A),且≠,那么存在x只属于和之中的一个集合，不妨设x?∧x,因此 于是（ ）,从而证明了是单射的，对于任意g?2,令B={x｜x?A,g(x) = 1}，则B?P(A), 且(B)= Xв = g. 2.令:[1,2] →[0,1],(x) = x – 1,则为[1,2]到[0,1]的双射函数. 3.令:A→N,(x) = x/2 , 则为双射函数. 6.提示：根据A ≈ C,B ≈ D，存在双射：A→C,g:B→D,构造函数h：A×B→C×D,h() = <(a),g(b)>容易证明h的双射性。 7.A = {2n｜n?N},B = {2|k?N},C=Z 9.(1) 3∪6 = 6, 2∩5 = 2; (2)4–3 ={3},3⊕1 = {1,2} (3)∪4 = 3, ∩1 = 0 (4)1×4 = {<0,0>,<0,1>,<0,2>,<0,3>},2= { 10.(1)3, (2) , (3) , (4) , (5) , (6), 返回 ={<0,0>,<1,0>} = {<0,0>,<1,1>} ={<0,1>,<1,0>} = {<0,1>,<1,1>} , , , }，其中: 第十章 代数系统 本章自测答案 3.(1)可以，A = {-1,0,1}. (2)不可以. 4.(1)封闭 (2)不封闭 (4)加法不封闭，乘法封闭 (5)不封闭 (7)封闭 (9)加法不封闭，乘法封闭 5.(1)没有交换律、结合律，对于一个运算不能考虑分配律； (3)加法满足交换律、结合律，乘法满足结合律，乘法对加法满足分配律； (4)乘法满足结合律 (6)加法和乘法都满足交换律、结合律，乘法对加法满足分配律； (7)满足结合律； (8)乘法满足交换律、结合律； (9)乘法满足交换律、结合律； (10)乘法满足交换律、结合律。 6.(1)没有单位元、零元，没有可逆元素。 (3)n阶全0矩阵是加法单位元，也是乘法的零元；n阶单位矩阵是乘法单位元；加法没有零元。任意n阶矩阵M对于加法都是可逆元，起逆元为 – M；只有n阶可逆矩阵(行列式不为0)对乘法是可逆元，其逆元为M . (4) 乘法单元为n阶单位矩阵，没有零元。每个矩阵M都有逆元M . (6) 加法单位元0，没有零元，每个元素x都可逆，其逆元是它的相反数 – x 。 当n = 1时，乘法有单位元1，只有两个可逆元素：1 = 1, ( - 1) = - 1. 当n＞1时乘法没有单位元和可逆元素。 (7)没有单位元和零元，也没有可逆元素。 (8)乘法单位元为1，只有1是可逆元素，1 = 1 (9)乘法单位元为1，只有1是可逆元素，1 = 1 (10)乘法没有单位元、零元以及可逆元素。 8.(1)不可交换。反例：<0,1> * <1,2> = <0,1>,<1,2> * <0,1> = <0,3>. 可结合，因为 不是幂等的，因为<1,1> * <1,1> = <1,2> (2) 容易严整<1,0>为单位元，没有零元，当 a≠0 时， 11.(1)能构成代数系统。满足交换律、结合律、无单位元，零元是1； (3)能构成代数系统。满足交换律、结合律，单位元是10，零元是1。 15.(1)能 (2)不能 (3)不能 (4)能 第十一章 半群与群 本章自测答案 2.(1)构成半群、独异点和群； (3)构成半群，不构成独异点，也不构成群； (4)构成半群、独异点和群 5.(1)假设a*b ≠ b*a，那么或者a*b = a , a = b ；或者a*b = b , b*a = a。若为前者，则 (a*b)*a = a*a = b , a*(b*a) = a*b = a 与结合律矛盾，若为后者，有 (a*b)* a = b*a = a ; a*(b*a) = a*a = b 也与结合律矛盾。 (2) 假设b*b = a ，那么或者a*b = b*a = a，或者a*b = b*a = b 。若为前者，则 (b*a)*a = a*a = b ; b*(a*a) = b*b = a 与结合律矛盾，若为后者，有 (b*a)*a = b*a = b ; b*(a*a) = b*b = a 也与结合律矛盾。 7.任取a + bi , c + di?G , 有 (a + bi)+(c + di)=(a + c)+(b + d)i?G 任取a + bi , c + di , e + i ?G ,有 返回 ((a + bi)+(c + di))+(e + i)=(a + c)+(b + d)i +(r + i) = (a + c + e) + (b + d + ) i 同理 (a + bi)+((c + di)+(e + i))=(a + c + e) + (b + d + ) i 单位元是0，a + bi的逆元是 – a – bi . 9. 能构成群，运算封闭。 x , y , z ?A , 有 (xy)z = (x + y - 2) z = (x + y - 2) + z – 2 = x + y + z – 4 x(yz) = xо(y + z - 2) = x + (y + z - 2) – 2 = x + y + z – 4 结合律成立，单位元是2，x的逆元是4 – x。 11．设矩阵A=, B=， C=， D=， 那么运算表如表11.7所列 · A B C D A B C D A B C D B A D C C D A B D C B A 13.(2)a,b?G有 (ab)(ba)=a(bb)a=aa=e (ba)(ab)=b(aa)b=bb=e 因此b a 是ab的逆元，根据逆元唯一性，命题得证. (4) 当m，n为自然数时任意给顶n，对m进行归纳， a?G，有 m = 0,(a)= e = a 假设(a)= a (a) ，则 =(a)a=a a=a = a 根据归纳法，命题得证. 下面对n或m小于0的情况进行验证,不妨设n＜0,m≥0,则n=-t,t＞0 (a)=(a)=((a))=(a) 其他类似情况可以类似加以验证. (5)设G为交换群，当n为自然数时对n归纳。 N = 0,(ab)= e = ee = ab 假设(ab)= ab,则 (ab) = (ab)(ab) =(ab)ab = a(ba)b b =a =a = a(ab)b = (aa)(bb) = a 根据归纳法，命题得证. 若n＜0,令n=-m,m＞0 ，那么有 (ab)=(ba)=(ba) =((ba))=(ab) =(a)(b) =ab=ab 16.若x?G有x= e,因此x?G有x= x.x ,y?G，有 xy = (xy) = yx = yx 17.设a是幕等元，则aa = a,即aa = ae.根据消去律必有a = e. 19.由x=e?|x|=1或2,换句话说。对于G中元素x，如果|x|＞2,必有x≠x，由于|x|=|x|，阶大于2的元素成对出现，共有偶数个，那么剩下的1阶元总共应该是偶数个，1阶元只有1个，就是单位元，从而证明了G中必有的2阶元. 22.a?N(a),N(a)≠,任取x,y?N(a),有 ay = ya ? a(ay)a= a(ya)a ? ya = a y (xy)a = x(ya) = x(ay) = x(ya) = x(ay ) = (xa)y = a(xy ) 根据判定定理，N(a)为G的子群。 30.(1)是同态，不是单同态，也不是满同态。() = {-1,1},ker = 2Z; (2)是同态，不是单同态，也不是满同态。() = {cosx + i·sinx｜x?Z},ker = {0}; (3)是同态，不是单同态，是满同态，()={cosx + i·sinx｜x?R}= A,ker ={2kπ｜k?Z} 31.设 ：x,y? → ，： → ，因此: → , ，有 (xy) = ( (xy)) = ( (x) (y)) =((x))((y)) =(x)(x) 因此是到的同态。 32.由于： → 是双射，因此：→ 也是双射。 x,y?,a,b?,使得(a) = x,(b) = y.从而得到 (x)= a,(y) = b (xy) =((a)(b)) = ((ab)) = ab =(x)(y) 33.设是循环群，a，a?有 aa=ａ =ａ =ａａ 因此G是Abel群，但是Abel群不一定是循环群，例如KIein四元群是Abel群，但不是循环群。 y=(ａ)=()=()=((a)) 因此(a)是生成元，即()=<(a)>. 35.(1)生成元为a,a,a,a,a,a,a,a (2)子群为 36.(1)στ=，τσ=，σ=，τ=，στσ= (2)στ= (1 4 2 3 )，τ = (1 4 2 5 3 )， στσ = (1 5 2 4 3 ) (3)στ = (1 4)(1 2)(1 3)奇置换 τ σ = (14)(12)(15)(13)偶置换 τσ = (15)(12)(14)(13) 偶置换 返回 第十二章 环与域 本章自测答案 4．（1）是环，是整环，也是域； （2）不是环，因为关于加法不封闭； （3）是环，不是整环和域，因为乘法没有么元； （4）不是环，因为正整数关于加法的负元不存在，关于加法不构成群； （5）不是环，因为关于乘法不封闭。 6.(1) ( - a )( - a) = - - (a a) = 1 , ( - a)( - a ) = - - ( a a ) = 1 因此 - a 是( - a)的逆元，根据逆元的唯一性得( - a) = - a (2) (b a )(a b) = b (a a) b = 1 , (ab) (b a ) = a (b b ) a = 1 因此b a 是ab的逆元，根据逆元唯一性有(a b) = b a . 十三章 1.图13.9中给出6个偏序集的哈斯图.判断其中哪些是格。如果不是格，说明理由。d c d c b (a) (b) g f f d e d c b c (d) (e) f d e b b (c) d e b b (f) f e c f e c 图13.9 (a)、 (c)、 (f) 是格。(b) 中的 {e、 d} 没有最大下界。(d) 中的 {d，e} 没有最大下界。(e) 中的 {a，b} 没有最大下界。 2.下列各集合对于整除关系都构成偏序集，判断哪些偏序集是格。(1) L = {1，2，3，4，5} (2) L = {1、 2、 3、 6、 12} (3) L = {1、 2、 3、 4、 6、 9、 12、 18、 36} (4) L = {1，2，2 2，...，2n} n? + (1) 不是格、 其他都是。 3.(1) 群〈 12，⊕〉的子群格。 (2) 画出3元对称群S3的子群格。见答图。52 12 S3 〈3〉 〈6〉 〈0〉 〈2〉 (1) 〈 (12) 〉〈 (123) 〉〈 (23) 〉〈 (13) 〉 〈4〉 〈 (1) 〉 (2) 第3题答图 13.4.4.设L是格，求以下公式的对偶式： (1) a∧(a∨b) (2) a∨∧(b∧c) (3) b∨(c∧a) (1) a∨(a∧b) (2) a∧(b∨c) (3) b (c∨a) (a∨b) ∧(a∨c) (b∨c) ∧a。(a∧b) ∨(a∧c) (b∧c) ∨a b = b ∧ 5.设?为集合S上可交换、 可结合的二元运算、 若a、 b是S上关于?运算的幂等元、 证明a?b也是关于?运算的幂等元。掌握 ∨c (?b) ? (?b) = ((a ?b) ?a) ?b = (?(a ?b)) ?b = ((a ?a) ?b） ?b = （.... 8、 设〈L、 证明〈S、 〉是格、 任取a?L。破产令 S = {x | x?L∧y x，x ∨y ∨a =，x ∨y ?xa}。〉是〈L，〉的子格。S非空。?x y ?S a、 y 有x，从而x ∧ y ?S。因此 〈S、 〉是 〈L、 〉的子格。 S，即S对运算 ∧，∨ 是封闭的，于是x ∧13.9.9.针对图13.9中的每个格，如果格中的元素存在补元，则求出这些补元。(b)、 (d) (e) 不是格。(a) a与d互补;b、 c没有补元。(c) a与f互补;b的补元为c，d ；c的补元为b、 e ；d的补元为b、 e ；e的补元为c，d。(f) a与f互补;b的补元为e ；c和d没有补元 ；e的补元为b。10.说明图 9中的每个格是否为分配格、 有补格和布尔格、 并说明理由。(b)、 (d) (e) 不是格。(a) 是分配格，因为不包含与钻石格和五角格同构的子格 ；不是有补格和布尔格、 b、 c没有补元。(c) 不是分配格、 不是布尔格、 因为包含五角格作为子格 ；是有补格、 a与f互补、 b和e的补元有c、 d;c、 d的补元有b、 e。(f) 是分配格，因为没有5元子格与钻石格或五角格同构 ；不是有补格，也不是布尔格，因为c和d没有补元。11.证明定理13.8。12.对以下各小题给定的集合和运算判断它们是哪一类代数系统 （半群、 独异点、 去、 圆心、 域、 攫、 城市尔代数)、 并说明理由。(1) S1 = {0，1，? 1}，运算为普通加法和乘法。(2) S2 = {a1，a2，...，n}，?a i，j?S2，i * j = i.这里的n是给定的正整数，且n≥2。(3) S3 = {0，1}，* 为普通乘法。(4) S4 = {1，2，3，6}，和 * 分别表示求最小公倍数和最大公约数运算。(5) S5 = {0，1}，* 为模2加法，为模2乘法。(1) 不是代数系统，对于加法不封闭。(2) 是半群但不是独异点、 运算封闭、 有结合...... 返回 第十四章部分课后习题参考答案 3 写出图14.17中各图的度数列，对有向图还要写出出度列和入度列。解 (a) 图G1的度数列d = （3、 2、 2、 2、 1）。(b) 图G2的度数列d = （3、 2、 2、 1、 2)。(c) 图D1的度数列d = (2、 4、 2、 3、 3，0);出度列d + = (1、 2、 1、 2、 1、 0） ；入度列d ?? = （1、 2、 1、 1、 2，0）。 4.(1)写出图14.18(a)中顶点中v1的邻域N(v1) 与闭邻域?N (v1)。(2) (b) 写出图14.18 中顶点中u1的先驱元集??? (u1) 后继元集?? + (u1)、 邻域N (u1) 与闭邻域?N (u1)。56 v2 v1 u1 v5 v3 v4 u4 (a) (a) 顶点v1的邻域N 图14.18 (v1) = {v2、 v3、 v4}、 闭邻域?N (v1) = {v1、 v2、 v3、 v4}。u2 u3 u5 (b) (b) 中顶点中u1的先驱元集??? (u1) = {u3、 u4}，后继元集?? + (u1) = {u2，u3}，邻域N (u1) = ??? (u1) ∪ ?? + (u1) = {u2、 u3、 u4}、 闭邻域?N (u1) = N (u1) ∪ {u1} = {u1、 u2、 u3、 u4}。G有10条边、 3度与4度顶点各2个、 其余顶点的度数均小于3、 问G中至少有几个顶，将为? 在最少顶点的情况下、 写出G的度数列、 ??(G)、 ??(G)。解设有x个2度顶点。由握手定理 2 m = 2·10 = ↖d(v i) ≤2·3 + 2·4 + x·2， 解得x ≥3。G至少有2 + 2 + 3 = 7个顶点，这时度数列为 2、 2、 2、 3、 3、 4 4），而??(G) = 4，??(G) = 2。 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. 6(1)设n阶图G中有m条边、 证明： ?(G) ≤2m/n ≤?(G)。(2) n 阶非连通 的简单图的边数最多可为多少?最少呢吗？(1)设V(G) = {v1、 v2、......，v n}，由握手定理得 n ↖d (v) (1) i 我 ?1 又 n ↖d （v)≤得 ?(G) ≤n?(G) (2) i 我 (2) 2m/n (2) ≤?(G) 设G ?1 由(1) = 〈V，E〉是n阶 1) V2 = V 不连通的 (无向) 简单图。令V1是G的一个连通分支的顶点集，k = |V1 |(≥? V1。注意V2 ≠?(?) |V2 |= |V|?|V1 |= n ?k ≥1。V1的顶点与V2的顶点 之间没有G的边(?)、 而G的边关联的顶点都是V1的顶点或者都是V2的顶点，即 E = E (G [V1]) ∪ E (G [V1])。要使G的边数最大，G [V1] 和G [V2] 都要含尽可能多的边、 这时它们都是完全图，分别有k(k ?G有|E|= k(k ?1)/2 + (n ?1)/2条边和(n ?k ?k) (n ?k ?1) / 2条边，而 k)(n ?1)/2条边。下面证明当k = 1 (或n ?1) 布置 |E|最大。2 2 n ?n ? 2 n ?尽可能远。当k = 1或n ?阶不连通的简单图由K n ? ? 2? 4 要使?E?最大、 k要离n/2 1)(n ?2)/2。边数最多的n 1)(n ?2)/2 1时 |E|取得最大值 (n ?1和K1 (平凡图) 两个连通分支组成，有 (n ?条边。边数最少的n阶不连通的简单图显然是n阶零图N n = ?K n，边数为0。QEI 另解: n阶连通的简单图中，K n的边数最多、 有n(n ?少(?)要删除关联某个顶点的 (n ?得，它的边数 = K n ?1)/2条边、 要破坏K n的连通性、 至 1和一个孤立点 (K1) 获 1) 条边，所得图由K n ?1)(n ?1的边数 = (n ?2)/2条边。这是 n阶非连通的简单 图的边数最多的情况。 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 221、无向图G如下图 (1)求G的全部点割集与边割集，指出其中的割点和桥； (2) 求G的点连通度k(G)与边连通度?(G)。 ae2be3解：点割集: {a,b},(d) e1de5ee4c 边割集{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??1?1?8(m?m)n(n?1) 得n? 2245、有向图D如图 (1)求v2到v5长度为1，2，3，4的通路数； (2)求v5到v5长度为1，2，3，4的回路数； (3)求D中长度为4的通路数； (4)求D中长度小于或等于4的回路数； (5)写出D的可达矩阵。 v1v4v5v2v3 解：有向图D的邻接矩阵为： ??00001??010??2?10100???01?00002???A???00001?，A2????0010A3????10100???01?0002???2??01010???0?20200???0?0??00004??012?40400???5A4???0??520004 A?A2?A3?A4??2??40400???21?45?04040???2?252(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； ??11111??11111??(4)出D的可达矩阵P???11111? ??11111???11111??第十六章部分课后习题参考答案 02020202020200015?22??15?22? ?54??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 评论：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中最长的路径长度为几？ 至少为几？最多为几？ (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个二进制数字.