关键词不能为空

当前您在: 主页 > 数学 >

高士其简介大学离散数学答案

作者:高考题库网
来源:https://www.bjmy2z.cn/gaokao
2020-11-30 08:03
tags:

-

2020年11月30日发(作者:蓝孟)第1章 习题解答



1.1 除(3),(4),(5),(11)外全是 命题,其中,(1),(2),(8),(9),(10),(14),(15)是简单命题,(6),(7), (12),(13)是复合命题。

分析 首先应注意到,命题是陈述句,因而不是陈述句的句 子都不是命题。本题中,(3)为疑问句,(5)为感叹句,(11)为祈使句,它们都不是陈述句,所以它们都 不是命题。

其次,(4)这个句子是陈述句,但它表示的 判断结果是不确定。又因为(1), (2),(8),(9),(10),(14),(15)都是简单的陈述句,因而作为命题,它们都是简单命题 。(6)和(7)各为由联结词“当且仅当”联结起来的复合命题,(12)是由联结词“或”联结的复合命题, 而(13)是由联结词“且”联结起来的复合命题。这里的“且”为“合取”联结词。在日常生活中,合取联结词 有许多表述法,例如,“虽然……,但是……”、“不仅……,而且……”、“一面……,一面……”、“……和 ……”、“……与……”等。但要注意,有时“和”或“与”联结的是主语,构成简单命题。例如,(14)、( 15)中的“与”与“和”是联结的主语,这两个命题均为简单命题,而不是复合命题,希望读者在遇到“和”或 “与”出现的命题时,要根据命题所陈述的含义加以区分。

1.2 (1) 是无理数,p为真命题。

(2) 能被2整除,p为假命题。

(6) 。其中, 是素数,q:三角形有三条边。由于p与q都是真命题,因而 为假命题。

(7) ,其中,p:雪是黑色的,q:太阳从东方升起。由于p为假命题,q为真命题,因而 为假命题。

(8) 年10月1日天气晴好,今日(1999年2月 13日)我们还不知道p 的真假,但p的真值是确定的(客观存在的),只是现在不知道而已。

(9)p:太阳系外的星 球上的生物。它的真值情况而定,是确定的。

(10)p:小李在宿舍里. p的真值则具体情况而定,是确定的。

(12) ,其中, 是偶数, 是奇数。由于q是假命题,所以,q为假命题, 为真命题。

(13) ,其中, 是偶数, 是奇数,由于q是假命题,所以, 为假命题。

(14) p:李明与王华是同学,真值由具体情况而定(是确定的)。

(15) p:蓝色和黄色可以调配成绿色。这是真命题。

分析 命题的真值是唯一确定的,有些命题的 真值我们立即可知,有些则不能马上知道,但它们的真值不会变化,是客观存在的。

1.3 令 则以下命题分别符号化为

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

以上命题中,(1),(3),(4),(5),(8)为真命题, 其余均为假命题。

分析 本

题要求读者记住 及 的真值情况。 为假当且仅当p为真,q为假,而 为真当且仅当p与q真值相同.由于p与q都是真命题,在4个蕴含式中,只有(2) ,其中,p同(1),r:明天为3号。

在这里,当p为真时,r一定为假, 为假,当p为假时,无论r为真还是为假, 为真。

1.5 (1) ,其中,p:2是偶数,q:2是素数。此命题为真命题。

(2) ,其中,p:小王聪明,q:小王用功

(3) ,其中,p:天气冷,q:老王来了

(4) ,其中,p:他吃饭,q:他看电视

(5) ,其中,p:天下大雨,q:他乘公共汽车上班

(6) ,其中,p,q的含义同(5)

(7) ,其中,p,q的含义同(5)

(8) ,其中,p:经一事,q:长一智

分析 1°在前4个复合命题中,都使用了合取联结词,都 符号化为合取式,这正说明合取联结词在使用时是很灵活的。在符号化时,应该注意,不要将联结词部分放入简单 命题中。例如,在(2)中,不能这样写简单命题:p:小王不但聪明,q:小王而且用功。在(4)中不能这样 写:p:他一边吃饭,tq:他一边看电视。

2° 后4个复合命题中,都使用了蕴含联结词, 符号化为蕴含式,在这里,关键问题是要分清蕴含式的前件和后件。

所表达的基本逻辑关系为, p是q的充公条件,或者说q是p的必要条件,这种逻辑关系在叙述上也是很灵活的。例如,“因为p,所以q” ,“只要p,就q”“p仅当q”“只有q才p”“除非q,否则 ”“没有q,就没有p”等都表达了q是p的必要条件,因而都符号化为 或 的蕴含式。

在(5)中,q是p的必要条件,因而符号化为 ,而在(6)(7)中,p成了q的必要条件,因而符号化为 。

在(8)中,虽然没有出现联 结词,但因两个命题的因果关系可知,应该符号化为蕴含式。

1.6 (1),(2)的真值为0,(3),(4)的真值为1。

分析 1° (1)中公式含3个命题变项,因而它应该有 个赋值:000,001,…,111题中指派p, q为0, r为1,于是就是考查001是该公式 的成真赋值,还是成假赋值,易知001是它的成假赋值。

2° 在公式(2),(3),(4)中均含4个命题就项,因而共有 个赋值:0000,0001,…,1111。现在考查0011是它的成假赋值。

1.7 (1),(2),(4),(9)均为重言式,(3),(7)为矛盾式,(5),(6),(8),(10)为 非重言式的可满足式。

一般说来,可用真值表法、等值演算法、主析取范式(主合取范式)法等 判断公式的类型。

(1)对(1)采用两种方法判断它是重言式。

真值表法< br>
表1.2给出了(1)中公式的真值表,由于真值表的最后一列全为1,所以,(1)为重言式。

ptqtrt

0t0t0t0t1

0t0t1t1t1< br>
0t1t0t1t1

0t1t1t1

1

1t 0t0t1t1

1t0t1t1t1

1t1t0t1t1

1 t1t1t1t1

等值演算法



(蕴含等值式)
(结合律)

(排中律)

(零律)

由最后一步可知,(1 )为重言式。

(2)用等值演算法判(2)为重言式。



(蕴 含等值式)

(等幂律)

(蕴含等值式)

(排中律)

(3)用等值演算法判(3)为矛盾式



(蕴含等值式)
(德?摩根律)

(结合律)

(矛盾律)

(零律)

由最后一步可知,(3)为矛盾式。

(5)用两种方法判(5)为非重言式的可满足 式。

真值表法











0t0t1t0t1t1

0t1t1t1t1t1

1t0t0t1t1t1

1t1t0t1t0t0

由表1.3可知(5)为非 重言式的可满足式。

主析取范式法


















< br>.

在(3)的主析取范式中不含全部(4个)极小项,所以(3)为非重言式的可满足式 ,请读者在以上演算每一步的后面,填上所用基本的等值式。

其余各式的类型,请读者自己验证 。

分析 真值表法判断公式的类别是万能。公式A为重言式当且仅当A的真值表的最后一 旬全为1;A为矛盾式当且仅当A的真值表的最后一列全为0;A为非重言式的可满足式当且仅当A的真值表最后 一列至少有一个1,又至少有一个0。真值表法不易出错,但当命题变项较多时,真值表的行数较多。
< br>用等值演算法判断重言式与矛盾式比较方例,A为重言式当且仅当A与1等值;A为矛盾式当且仅当A与0 等值,当A为非重言式的可满足式时,经过等值演算可将A化简,然后用观察法找到一个成真赋值,再找到一个成 假赋值,就可判断A为非重言式的可满足式了。例如,对(6)用等值演算判断它的类型。


(矛盾律)

(等价等值式)

(蕴含等值式)

( 同一律)

(零律)

(同一律)

到最后一步已将公式化得很简 单。由此可知,无论 取0或1值,只要 取0值,原公式取值为1,即00或10都为原公式的成真赋值,而0 1,11为成假赋值,于是公式为非重言式的可满足式。

用主析取范式判断公式的类型也是万能 的。A为重言式当且仅当A的主析取范式含 ( 为A中所含命题变项的个数)个极小项;A为矛盾式当且仅当A 的主析取范式中不含任何极小项,记它的主析取范式为0;A为非重言式的可满足式当且仅当A的主析取范式中含 极小项,但不是完全的。

当命题变项较多时,用主析取范式法判公式的类型,运算量是很大的。

用主合取范式判断公式的类型也是万能的。A为重言式当且仅当A的主合取范式中不含任何极大 项,此时记A的主合取范式为1;A为矛盾式当且仅当A的主合取范式含 个极大项( 为A中含的命题变项的个 数);A为非重言式的可满足

式当且仅当A的主析取范式中含含极大项,但不是全部的。

1.8 (1)从左边开始演算



(分配律)

(排中律)

(同一律)

(2)从右边开始演算


(蕴含等值式)

(分配律)

(蕴含等值式)

(3)从左 边开始演算










< br>



请读者填上每步所用的基本等值式。

本题也可以从右 边开始演算










< br>





读者填上每步所用的基本的等值式。

1.9 (1)



(蕴含等值式)

(德?摩根律)

(结合律、交换律)

(矛盾式)

(零律)

由最后 一步可知该公式为矛盾式。

(2)

(蕴含等值式)

由于较 高层次等价号两边的公式相同,因而此公式无成假赋值,所以,它为重言式。

(3)

(蕴含等值式)

(蕴含等值式)

(德?摩根律)

( 吸收律)

(交换律)

由最后一步容易观察到,11为该公式成假赋值,因而它 不是重言式,又00,01,10为成真赋值,因而它不是矛盾式,它是非重言式的可满足式。

1.10 题中给出的F,G,H,R都是2元真值函数。给出的5个联结词集都是全功能集,可以用观察法或 等值演算法寻找与真值函数等值的公式。

首先寻找在各联结词集中与F等值的公式。
< br>(1)设 ,易知A是 中公式且与F等值,即

(2)设 ,易知B是 中公式且与F等值,即

(3)设 ,易知C是 中公式,且

(4)设 ,易知D为 中公式,且

(5)设 ,易知E为 中公式,且

分析 只要找到一个联结词集中与F等值的公式,经过等值演算就可以找出其他联结词集中与F等值的公式。例如,已知 是 公式,且 。进行以下演算,就可以找到F等值的其他联结词集中的公式。对A进行等值演算,消去联结词 ,用 , 取代,得







则B为 中公式,且 。再对A进行等值演算,消去 ,用 , 取代,得





则C为 中公式,且 。再对B进行演算,消去 , ,用 取代,在演算中,注意,对于任意的公式A,有












则D为 中公式,且 再对C进行演算,消去 用 取代,在演算中注意,对于任意的公式A

< br>






则E为 中公式,且

开 始找一个与某真值函数等值的公式的方法,除观察法外,就是根据该真值函数的真值表,求它的主析取范式,而后 进行等值演算即可。例如,由G的真值表可知G的主析取范式为 ,于是









由于公式 不带 联结词,所以,它应该为任何联结词集中的合式公式。

在各联结词集中找到的与某真值函数等值 的公式并不唯一。例如,取

中公式)

中公式)

中公式)
中公式)

中公式)

则 对于同一个真值函数 ,找到与

它等值的形式各异的公式。

对于H和R,请读者自己去完成。

1.1 1 (1)对C是否为矛盾式进行讨论。

当C不是矛盾式时, ,则一定有 ,这是因为,此时, ,所以,有



必有

而当C不是矛盾式时, ,不一定有 ,举反例如下:

设A,B,C均为含命题变项 的公式,A,B,C及 的真值表如表1.4所示,从表1.4可看出, ,但 B。

表1.4

pt qtAtBtCtAVCtBVC

0

0

1

1t0

1

0

1t0

0

1

0t0

0

1

1t0

0< br>
1

1t0

0

1

1t0
0

1

1

(2) 对C是否为重言式进行讨论:

若C为重言式,则 于是



因而 有



当C不是重言式时,请读者举反例说明, 时, 不一定有 .

(3) 若 则 .证明如下:

(双重否定律)

( )

(双重否定律)

所以



1.12 (1) 设(1)中公式为A.















于是,公式A的主析取范式为


< br>易知,A的主合取范式为



A的成真赋值为

000, 001, 010, 111

A的成假赋值为

011,100,101,11 0

(2)设(2)中公式为B






< br>



(吸收律)






所以,B的主析取范式为 .

B的主合取范式为

B的成真赋值 为00,10,11.

B的成假赋值为01.

(3)设(3)中公式为C.< br>


]







所以 ,C的主析取范式为0.

C的主合取范式为

C的成假赋值为00,01,1 0,11

C无成真赋值,C为矛盾式.

分析 1°设公式A中含 个命题变项,且A的主析取范式中含 个极小项,则A的主合邓范式中含 个极大项,而且极大项的角标分别为0到 这 个十进制数中未在A的主析取范式的极小项角标中出现过的十进制 数.

在(1)中,n=3,A的主析取范式中含4个极小项,所以,A的主合取范式中必含 个极大项,它们的角标为0到7中未在主析取范式的极小项角标中出现过的3,4,5,6. 这样,只要知道A 的主析取范式,它的主合邓范式自然也就知道了,在(2),(3)中情况类似.

2° A的主 析取范式中极小项角标的二进制表示即为A的成真赋值.在(1)中,由于主析取范式中的极小项角标分别为0, 1,2,7,它们的二进制表示分别为000,001,010,111,所以,A的成真赋值为以上各值.类似 地,A的主合取范式中所含极大项角标的二进制表示,即为A的成假赋值.

1.13 (1) 首先求 的主析取范式.

错误!链接无效。



.
由于演算过程较长,可以分别先求出由 派生的极小项.注意,本公式中含3个命题变项,所以,极小项长度 为3.























< br>


类似地,可求出 主的析取范式也为上式,由于公式的主析取范式的唯一性,可知,



(2) ①






















由于 与 的主析取范式不同.因而它们不等值,即 .

1.14 设p:A输入;
< br>设q:B输入;

设r:C输入;

由题的条件,容易写出 的真值表,见表1.5所示.由真值表分别写出它们的主析范邓范式,而后,将它们都化成与之等值的 中的公式即可.

表1.5

p q rt



0 0 0

0 0 1

0 1 0

0 1 1



1 0 0

1 0 1

1 1 0

1 1 1t0

0

0

0

1

1

1

1t0

0

1

1

0
0

0

0t0

1

0

0

0

0

0

0



























.















分析 在将公式化成 或 中公式时,应分以下几步:

(1)先将公式化成全功能集 中的公式.

(2) 使用







使用双重否定律











使用德?摩根律










1.1 5 设p:矿样为铁;

q:矿样为铜;

r:矿样为锡.











.



























































则F为真命题,并且





但,矿样不可能既是铜又是锡,于是q,r中必有假命题, 所以 因而必有



于是,必有P为真,q与r为假,即矿样为铁。
1.16 令p:今天是1号;

q:明天是5号.

由于本题给出的推理 都比较简单,因而可以直接判断推理的形式结构是否为重言式。

(1)推理的形式结构为



可以用多种方法判断上公式为重言式,其实,本推理满足假言推理定律,即



所以,推理正确。

(2)推理的形式结构为



可以用多种方法证明上公式不是重言式,其实,当p为假(即今天不是1号),q为真(明天真是5号 ),也即01是上面公式的成假赋值,所以,推理的形式结构不是重方式,故,推理不正确。

( 3)推理的形式结构为



可以用多种方法证明上面公式为重言式,其实,它满足 拒取式推理定律,即



所以,推理正确。

(4)推理的形式结 构为



可以用多种方法证明上公式不是重言式,01为上公式的成假赋值,所以 ,推理不正确。

分析 对于前提与结论都比较简单的推理,最好直接判推理的形式结构是否为 重言式,来判断推理是否正确,若能观察出一个成假赋值,立刻可知,推理不正确。

1.17 (1)

证明 ① 前提引入

② 前提引入

③ ①②析取三段论

④ 前提引入

⑤ ④置换

⑥ ②⑤析取三段论

(2)

证明 ① 前提引入

② ①置换

③q 前提引入

④ ②③假言推理

⑤ 前提引入

⑥ ⑤置换

⑦ ④⑥假言三段论

(3)

证明 ① 附加前提引入

② 前提引入

③q ①②假言推理

④ ①③合取

或者

证明 ① 前提引入

② ①置换

③ ②置换

④ ③置换

⑤ ④置换

(4)

证明 ① 前提引入

② ①置换

③ ②化简

④ 前提引入



⑥s ③⑤假言推理

⑦ 前提引入

⑧ ⑦置换

⑨ ⑧化简

⑩q ⑥⑨似言推理

? 前提引入

?p ⑩? 假言

推理

?r ④化简

? ⑥⑩??合取

分析 由于


< br>





所以,当推理的结论也为蕴含式时,可以将结论的前 件作为推理的前提,称为附加前提,并称使用附加前提的证明方法为附加前提证明法.(3)中第一个证明,即为 附加前提证明法.

1.18 设p:他是理科生

q:他是文科生

r:他学好数学

前提

结论q

通过对前提和结论的观察,知道推理是正确的,下面用构造证明法给以 证明。

证明 ① 前提引入

前提引入

③ ①②拒取式

④ 前提引入

⑤ ③④拒邓式

⑥q ⑤置理

1.19 本题可以用多种方法求解,根据要求回答问题,解本题最好的方法是真值表 示或主析取范式法。这里采用主析取范式的主析取范式(过程略)




< br>所以,成真赋值为010,100,101,110,111,由④给也,成假赋值为000,001,0 11,由③给出,公式是非重言式的可满足式,由③给出。

1.20 答案 A:③; B:④; C:②

分析 解本题的方法不限于求主析取范式或主合取范式,也可以利用真值表法。

方法1: 求主析取范 式









从上式可知, 的主 析取范式中含5个极小项。极小项角码的二进制表示为成真赋值,因而成真赋值为001,011,101,11 0,111。由成真赋值立即可知成假赋值为000,

010,100,成假赋值的十进制的十 进表示为极大项的角码,因而极大项为 ,故有3个极大项。

方法2:求主合取范式,分析类似 主析取范式法。

方法3:真值表法

由真值表,求出成真赋值,将成真赋值转化 成十进制数做为极小项的角码,这样就求出了全部极小项,也容易求出极大项。

1.21 答案 A:③; B:⑤; C:⑥

分析 可用构造证明法解此题。

(1) ① 前提引入

② 前提引入

③ ①②析取三段论

④ 前提引入

⑤ ④置换

⑥ ③⑤析取三段论

至此可知 是(1)的逻辑结论。

(2) ① 前提引入

② tt前提引入

③ tt①②析取三段论

④ 前提引入

⑤ tt④置换

⑥ t⑤置换

至此可知 是(2)的国逻辑结论。

(3) ① t前提引入

② t t①置换前提引入

③ t前提引入

④ t③置换

⑤ t②④假言推理

⑥ t前提引入

⑦ t⑤⑥假言推理

至此可知 是(3)的逻辑结论。

1.22 答案 A:④

分析 在本题 中,设A,B,C分别表示3个开关状态的命题变项,开关的扳键向上时,对应命题变项的真值为1,否则为0, 由真值表易知。





















第2

章 习题解答



2.1 本题没有给出个体域,因而使用全 总个体域.

(1) 令 是鸟

会飞翔.

命题符号化为

.

(2)令 为人.

爱吃糖

命题符号化为



或者



(3)令 为人.

爱看小说.

命题符号化为

.

(4) 为人.

爱看电视.

命题符号化为

.

分析 1°如果没指出要求什么样的个体域,就使用全总个休域,使用全总个体域时,往往要使用特性谓词。(1)-( 4)中的 都是特性谓词。

2° 初学者经常犯的错误是,将类似于(1)中的命题符号化为< br>


即用合取联结词取代蕴含联结词,这是万万不可的。将(1)中命题叙述得更透 彻些,是说“对于宇宙间的一切事物百言,如果它是鸟,则它会飞翔。”因而符号化应该使用联结词→而不能使用 。若使用 ,使(1)中命题变成了“宇宙间的一切事物都是鸟并且都会飞翔。”这显然改变了原命题的意义。< br>
3° (2)与(4)中两种符号化公式是等值的,请读者正确的使用量词否定等值式,证明(2 ),(4)中两公式各为等值的。

2.2 (1)d (a),(b),(c)中均符号化为



其中 此命题在 中均为真命题。

(2) 在 中均符号化为



其中 ,此命题在(a)中为假命题,在(b)(c)中均为真命题。

(3)在 中均符号化为



其中 此命题在 中均为假命题,在(c)中为真命题。

分析 1°命题的真值与个体域有关。

2° 有的命题在不同个体域中,符号化的形式不同,考虑命题

“人都呼吸”。

在个体域为人类集合时,应符号化为



这里, 呼吸,没有引入特性谓词。

在个体域为全总个体域时,应符号化为



这里, 为人,且 为特性谓词。 呼吸。

2.3 因题目中未给出个体域,因而应采用全总个体域。

(1) 令: 是大学生, 是文科生, 是理科生,命题符号化为



(2)令 是人, 是化, 喜欢,命题符 号化为



(3)令 是人, 犯错误,命题符号化为



或另一种等值的形式为



(4)令 在北京工作, 是北京人,命题符号化为







(5)令 是金属, 是液体, 溶解在y中,命题符号化为



(6)令 与y是对顶角, 与y相等,命题符号化为



分析 (2),(5),(6)中要使用2无谓词,用它们来描述事物之间的关系。

2.4 (1)对所有的x,存在着y,使得 ,在 中为真命题,在 中为假命题。

(2)存在着 对所有的y,都有 ,在 中为真命题,在 中为假命题。

(3)对所有x,存在着y,使得 ,在 中均为假命题,而在 中为真命题。

(4)存在着x,对所有的y,都有 ,在 中都是假命题。

(5)对所有的x,存在着y,使得 在 中都是真命题。

(6)存在x,对所有的y,都有 ,在 中为真命题,在 中为假命题。

(7)对于所有的x和y,

存在着z,使得 ,在 中为真命题,在 中为假命题。

2.5 (1)取解释 为:个体域 (实数集合), 为有理数, 能表示成分数,在 下, 的含义为

“对于叙何实数x而言,若x为有理数,则x 能表示成分数”,简言之为“有理数都能表示成分数。”在此蕴含式中,当前件 为真时,后件 也为真,不会出现前件为真,后件为假的情况,所以在 下, 为真命题。

在在 下, 的含义为

“对于任何实数x,x既为有理数,又能表示成分数。”

取 ,则 显然为假,所以,在 下, 为假命题.

(2) 取解释 为:个体域D=N(自然数集合), 为奇数, 为偶数,在 下, 的含义为

“存在自然数x,x发既为奇数,又为偶数。”

取 ,则 为假,于是 为真,这表明 为真命题。

分析 本题说明





这里, 表示A与B不等值,以后遇到 ,含义相同。

在一阶逻辑中,将命题符号化时,当引入特性谓词(如题中的 之后,全称量词 后往往使用联结词→而不使用 ,而存在量词 后往往使用 ,而不使用→,如果用错了,会将真命题变成假命题,或者将假命题变成真命题。

2.6 在解释R下各式分别化为

(1)

(2)

(3)

(4)

易知,在解释R下,(1),(2)为假;,(3)(4)为真。

2.7 给定解释 为:个体域D=N(自然数集合), 为奇数, 为偶数。

(1)在解释 下,公式 被解释为

“如果所有的自然数不是奇数就是偶数,则所有自然数全为奇数,或所有自然数全为偶 数。”因为蕴含式的前件为真,后件为假,所以真值为假。

(2)在 下,公式解释为

“如果存在着自然数为奇数,并且存在着自然为偶数,则存在着自然数既是奇数,又是偶数。”

由于蕴含式的前件为真,后件为假,后以真值为假。

分析 本题说明全称量词对析取不满足分配律,存在量词对合取不满足分配律。

2.8 令 在A中,无自由出现的个体变项,所以A为闭式。

给定解释 :个体域D=N(整数集合), 为正数, 为负数, ,在 下,A的含义为

“对于任意的整数x和y,如果x为正整数,y为负整数,则 。”

这是真命题。

设解释 :个体域D=R(R整数集合), 为有理数, 为无理数, ,在 下,A的含义为

“对于任意的实数x和y,如果x为有理数,y为元理数,则 。”

这是假命题。

分析 闭式在任何解释下不是真就是假,不可能给出解释I, 使得闭式在I下真值不确定,这一点是闭式的一个重要 特征。而非封闭的公式就没有这个特征。

2.9 取 和 ,则 和 都是非土产的公式,在 中,x, y都是自由出现的,在 中,y是自出现的。

取解释I为,个体域D=N(N为自然数集合), 为 。在I下, 为 为假,所以在I下, 真值不确定,即在I下 的

真值也是命题。

在I下, 为 当 时,它为真; 时为假,在I下 的真值也不确定。

分析 非闭式与 闭式的显著区 别是,前者可能在某些解释下,真值不确定,而后者对于任何解释真值都确定,即不是真就是假。

当然非闭式也可以是逻辑有效式(如 ),也可能为矛盾式(如 ,也可能不存在其值不确定的解释。

2.10 (1)

(消去量词等值式)

(德?摩根律)

(消去量词等值式)

(2)

(消去量词等值式)

(德?摩根律)

(消去量词等值式)

2.11 (1) 令 为人。

长着绿色头发。

本命题直接符号化验为

]



(量词否定等值式)

(德?摩根律 )

(蕴含等值式)

最后一步得到的公式满足要求(使用全称量词),将它翻译 成自然语言,即为

“所有的人都不长绿色头发”。

可见得“没有人长着绿色头 发。”与“所有人都不长绿色头发。”是同一命题的两种不同的叙述方法。

(2)令 是北京人

去过香山。

命题直接符号化为

]



(双重否定律)

(理词否定等值式)

(德?摩根律)

(蕴含等值式)

最后得到的公式满足要求(只含全称量词),将它翻译成自然语言, 即为

“并不是北京人都去过香山。”

可见,“有的北京人没过过香山。”与“ 并不是北京人都去过香山。”是同一命题不同的叙述方法。

2.12 (1)



(2)

(量词辖域收缩扩张等值式)



(3)









分析 在有穷个体域内消去量词时,应将量词的辖域尽量缩小,例如,在(2)中,首先将量词辖域缩小了(因为 中不 含x,所以,可以缩小)。否则,演算是相当麻烦的。见下面的演算:













显然这个演算比原来的喾算麻 烦多了。

2.13 在I下

(1)





所以, 在 下为假。

(2)





所以,此公式在I下也是假命题。

(3)

(量词分配等值式)





所以,此公式在I下 为真

2.14 (1)



(量词否定等值式)

(约束变项换名规则)

(量词辖域收缩扩张等值式)



(2 )









在以上演算中分别使 用了德?摩根律、量词否定等值式、约束变项换名规则等。

分析 公式的前束范式是不唯一的。(1)中最后两步都是前束范式,其实

也是(1)中公式的前束范式。

2.15 (1)







(2)








在以上演算中分别使用了自由变项换名规则和量词辖域收缩扩张等值式。

2.16 (1)②错。使用UI,UG,EI,EG规则应对前束范式,而①中公式下不是前束范式 ,所以,不能使用UI规则。

(2)。①中公式为 ,这时, ,因而使用UI

规则时,应得 (或 ),故应有 而不可能为

(3)②错。应对 使用EG规则,其中c为特定的使A为真的个体常项,而不能为个体变项。

(4)②错。①中公式含个体变项x,不能使用EG规则。

(5)②错。①公 式含两个个体常项,不能使用EG规则。

(6)⑤错。对①使用EI规则得 ,此c应使 为真,此c不一定使 为真。

分析 由于⑤的错误,可能由真前提,推出假结论。反例如下:

设个体域为自然数集合 为偶数, 为素数, 能被3整除, 能被4整数,显然此时,



均为真,但 为假。其实在(6)中,③应为 ,它是真命题,而 为假命题。对 使用EI规则,得 才为真。所以,对两个公式使用EI规则使用同一个个体常项是会犯错误的。

2.17

(1)证明

① 前提引入

② 前提引入

③ ①② 假言推理

④ ②EI

⑤ ④附加

⑥ ③UI

⑦ ⑤⑥假言推理

⑧ ⑦ EG

(2)证明:

① 前提引入

② ①EI

③ 前提引入

④ ③UI

⑤ ②④假言推理

⑥ ⑤化简

⑦ ②⑥合取

⑧ ⑦ EG

2.18 令 是大熊猎。

产在中国。

欢欢

前提:

结论:

证明:

① 前提引入

② 前提引入

③ ①UI

④ ②③假言推理

2.19令 为有理数。

为实数。

为整数。

前提:

结论:

证明:

① 前提引入

② 前提引入

③ ①② 假言推理

④ ②EI

⑤ ④附加

⑥ ③UI

⑦ ⑤⑥假言推理

⑧ ⑦ EG

(2)证明:

① 前提引入

② ①EI

③ 前提引入

④ ③UI

⑤ ②化简

⑥ ④⑤假言推理

⑦ ②化简

⑧ ⑥与⑦合取

⑨ ⑧EG

分析 在以上证明中,不能如下进行。

① 前提引入

② 前提引入

③ ②UI

④ ①EI

至此,可能犯了错误,在③中取 则 为真,但 为假,就是说,由UI规则得到的c不 一定满足EI规则,但反之为真,这一点务必注意。

2.20

答案 A:③; B:②

分析 (7)式为非闭式,在个体域为整数集Z时, 的真值不能确定,当 时为真,当 时为假,所以,它不是命题,其余各式都是命题。(5)虽然不是闭式,但它为真。

2.21 答案 A:②; B:④,⑤,⑨ C:⑦; D:⑧

分析 注意约束变项和自由变项 改名规则的使用。供选答案中,(1)的前束范式只有一个,就是②。而②的前束范式有3个,当然它们都是等值 的。(3)的前束范式有2个,就是⑦和⑧。注意,在(3)式中, 的辖域为 ,这就决定了它们的前束范式为

, (将自由出现的y改名为z)

但由 于





所以,⑧也是(3)的前束范式。

2. 22 答案 A:⑤。

分析 (1),(4)正确;可以构造证明。

(1)证明:

① 前提引入

② ①EI

③ 前提引入

④ ③UI

⑤ ②④假言推理

⑥ ⑤EG

注意应先使用EI规则。

(4)证明:

① 前提引入

② ①UI

③ 前提引入

④ ②③拒取式

⑤ ④UG

(2),(3)推理不正确,只要举出反例即可.

在自然数集合中,令 是偶数, 是素数,则 为真命题,而 为假命题,所以, 不是逻辑有效蕴含式,这说明(2)是推理 不正确,读者可举反例说明(3)中推理也不正确.

2.23 答案 A: ② B:① C: ⑦ D:⑤



第3章 习题解答



3.1 A:③; B:④; C:⑤; D:⑦;E:⑧

3.2 A:③;B:①; C:⑤; D:⑥; E:⑦

3.3 A:①;B:③; C:⑧; D:⑤; E:⑩

分析 对于给定的集合或集合公式,比如说是A和B,判别B是否被A包含,可以有下述方法:

1° 若A和B是通过列元素的方式给出的,那么依次检查B中的每个元素是否在A中出现,如果都在A中出现,则 否则不是。例如,3.3题给的答案中有{{1,2}}和{1},谁是 的子集呢?前一个集合的元素是{1, 2},要S中出现,但后一个集合的元素是1,不在S中出现,因此,{{1,2}}

2° 若A和B是通过用谓词概括元素性质的主试给出的,B中元素的性质为P,A中元素的性质为Q,那么,

“如果P则Q”意味着

“只有P才Q”意味着

“除去P都不Q”意味着

“P且仅P则Q”意味着

例如 ,3.1题(1)是“如果P则Q”的形式,其中“计算机专业二年级学生”是性质P,“学《离散数学》课”是 性质;题(2)是“P且仅P则Q”的形式,此外

“如果P就非Q”则意味着 。

例如,3.1 题(3)和3.2题(3)都是这种形式。

3° 通过集合运算差别 如果 , , 三个等式中有任何一个成立,则有 。

4° 通过文氏图观察

,如果代表B的区域落在代表A的区域内部,则 。这后两种方法将在后面的解答中给出实例。

3.4 A:②; B:④; C:⑦; D:⑥;E:⑧

3.5 A:②;B:④; C:⑤; D:⑥; E:⑨

3.6 A:①;B:⑨; C:④; D:⑦; E:⑧

3.7 A:④;B:⑨; C:①; D:⑧; E:①

分析 设只买1本、2本及3本书的学生集合分别为 和 ,它们之间两两不交,由题意可知,



又知 ,所以,



然后列出下面的方程:



求得 .因此,没有买书的人数是

75-(10+35+20)=10.

3.8 (1)和(4)为真,其余为假.

分析 这里可以应用集合运算的方法来差别集合之间的包含或相等关系.如题(3)中的条件 意味着, ,这时不一定有S=T成立.而对于题(4),由条件~ 可推出



这是 的充公必要条件,从而结论为真.

对于假命题都可以找到反例,如题(2)中令 即可;而对于题(5),只要 即可.

3.9 (2),(3)和(4)为真,其余为假.

3.10 (1)

(2)

(3)

(4)



3.11 (1) 或

(2) 任何

(3)

(4)

(5) 且 .

3.12 (1),(2)和(6)都是 而(3),(4),(5)是A=B.

分析 对于用谓词给定的集合先尽量用列元素的方法表 示,然后进行集合之间包含关系的判别.如果有的集合不能列元素,也要先对谓词表示尽可能化简.如题(3)中 的A可化简为



题(5)中的A和B都可以化简为 题(6)中的
< br>

而对于题(4),不难看出A=B=R,是实数集合.

3.13 (1)



(2)





(3)



(4)观察到 故



(5) 观察到 ,故





3.14 (1)

(2)

(3)



,



(4)

(5)

分析 在做集合运算前先要化简集合,然后再根据题目要求进行 计算.这里的化简指的是元素,谓词表示和集合公式三种化简.

元素的化简——相同的元素只保 留一个,去掉所有冗余的元素。

谓词表示的化简——去掉冗余的谓词,这在前边的题解中已经用 到。

集合公工的化简——利用简单的集合公式代替相等的复杂公式。这种化简常涉及到集合间包 含或相等关系的判别。

例如,题(4)中的 化简后得 ,而题(5)中的 化简为 。

3.15





3.16 (1),(2),(3)和(6)为真。(4)和(5)不为真。

分析 如果给出的是集合恒 等式,可以用两种方法验证。一是分别对等式两边的集合画出文氏图,然后检查两个图中的阴影区域是否一致。二 是利用集合恒等式的代入不断对等式两边的集合公式进行化简或者变形,直到两边相等或者一边是另一边的子集为 止。例如,题(1)中的等式左边经恒等变形后可得到等式右边,即





类似地,对题(2)和(3)中的等式分别有












但对于等式(4),左边经变形后得



=

易见, 但不一定有 如令 时,等式(4)不为真。类假地

,等式(5)的左边经化简后得 ,而 不一定恒等于A-C。

3.17 (1)不为真。(2),(3)和(4)都为真。对于题(1)举反例如下:令

则 且 ,但 ,与结论矛盾。

分析 (2)由于 又由 可得 即 成立。

(3)由于 ,故有



这里用到 的充要条件为 或 或

(4)易见, 当A=B成立时,必有A-B=B-A。反之,由A-B=B-A得



化简后得 ,即 ,同理,可证出 ,从而得到A=B。

3.18 由 可知|B|=6。又由 知 ,代入包含排斥原理得



从而有

3.19 令

是完全平方数},

是完全立方数},

从而有 代入包含排斥 原理得





=998910



第4章 习题解答



4.1 A:⑤; B:③; C:①; D:⑧; E:⑩

4.2 A:②; B:③; C:⑤; D:⑩; E:⑦

4.3 A:②; B:⑦; C:⑤; D:⑧; E:④

分析 题4.1-4.3 都涉及到关系 的表示。先根据题意将关系表示成集合表达式,然后再进行相应的计算或解答,例如,题4.1中的




而题4.2中的



为得到题4.3中的 R须求解方程 ,最终得到



求 有三种方法,即集合表达式、关系矩阵和关系 图的主法。下面由题4.2的关系分别加以说明。

1°集合表达式法

将 的元素列出来,如图4.3所示。然后检查R的每个有序对,若 ,则从 中的x到 中的y画一个箭头。若 中的x经过2步有向路径到达 中的y,则 。由图4.3可知



如果求 ,则将对应于G中的有序对的箭头画在左边,而将对应于F中的有序对的箭头画在右边。对应的三个集合分别为 ,然后,同样地寻找 到 的2步长的有向路径即可。

2° 矩阵方法

若M是R的关系矩阵,则 的关系矩阵就是M?M,也可记作M2,在计算乘积时的相 加不是普通加法,而是逻辑加,即0+0=0,0+1=1+0=1+1=1,根据已知条件得







中含有7个1,说明 中含有7个有序对。



图4.3 ttt tttttt 图4.4

3°关系图方法

设G是R的关系图。为求 的关系图 ,无将G的结点复制到 中,然后依次检查G的每个结点。如果结点x到y有一条n步长的路径,就在 中从x到y加一条有向边。当所有的结点检查完毕,就得到图 。以题4.2为例。图4.4(1)表示R的关系 图G。依次检查结点1,2,3,4。从1出发,沿环走2步仍回到1,所以, 中有过1的环。从1出发,经<1,1>和<1,4>,2步可达4,所以, 中有从1到4的边。结点1检查完 毕。类似地检查其他3个结点,2步长的路径还有2→1→1,2→1→4,3→4→1,4→1→1,4→1→ 4。将这些路径对应的边也加到 中,最终得到 的关系图。这个图给在图4.4(2).

4.4 A:④; B:⑧; C:⑨; D:⑤; E:⑩

分析 根据表4.1中关系图的特征来判定 的性质,如表4.2所示。

表4.2

自反t反自反t对称t反对称t传递









√t



√t






√t





√t







从表中可知 和 不是传递的,理上如下:在 中有边<3,1>和<1,2>,但缺少边<3,2>.在 中有边<1,3>和<3,2>,但缺少边<1,2>。在 中有边<1,2>和<2,1>,但缺少过1的环。

4.5 A:①; B:③; C:⑧; D:⑨; E:⑤

分析 等价关系和划分是两个不同的概念,有着不同的表示方法,等价关系 是有序对的集合,而划分是子集的集合,切不可混淆起来,但是对于给定的集合A,A上的等价关系R和A的划分 中一一对应的,这种对应的含义是

和y在 的同一划分块里。

拘句话说,等价说系R的等价类就是划分 的划分块,它们表示了对A中元素的同一种分类方式。

给定划分 ,求对应的等价关系R的方法和步骤说明如下:

1°设 中含有两个以上元素的划分块有 块,记作 。若 , ,则 求出 。



本题中的 的划分块都是单元集,没有含有个以上元素的划分块,所以, 含有两个划分块,故对应地等价关系含有两个等价类。 中只有一个划分块 包含了集合中的全体元素,这说明 因此,这个划分块对应的关系 就 上的全域关系,从而得到 也是 上的全域关系。

4.6 A:③; B:⑩; C:⑤; D:⑩; E:⑤

分析 画哈斯图的关键在于确定结点的层 次和元素间的盖住关系,下面讨论一下画图的基本步骤和应该注意的问题。

画图的基本步骤是:

1° 确定偏序集 中的极小元,并将这些极小元放在哈斯图的最底层,记为第0层。

2° 若第n层的元素已确定 完毕,从A中剩余的元素中选取至少能盖住第n层中一个元素的元素,将这些元素放在哈斯图的第n+1层。在排 列第n+1层结点的位置时,注意把盖住较多元素的结点放在中间,将只盖住一个元素的结点放在两边,以减少连 绩的交叉。

3° 将相邻两层的结点根据盖住关系进行连线。

以本题的偏序集 为例,1可以整除S中的全体整数,故1是最小元,也是唯一的极小元应该放在第0层。是1的倍数,即2,3, 5,7,S中剩下的元素是4,6,8,9,10。哪些应该放在第2层呢?根据盖住关系,应该是4,6,9和 10。因为4盖住,2,6盖住2和3,9盖住3,10盖住2和5. 8不盖住2,3,5,7中的任何一个元 素,最后只剩下一个8放在第3层。图4.5给出了最终得到的哈斯图。在整除关系的哈斯图中,盖住关系体现为 最小的倍数或最小的公倍数关系。

如果偏序集是 ,那么哈斯图的结构将呈现出十分规则的形式。第0层是空集 ,第1层是所有的单元集,第2层是所有的2元子 集,…,直到最高层的集合A。这里的盖住关系就体现为包含关系。



在画哈斯 图时应该注意下面几个问题。

1°哈斯图中不应该出现三角形,如果出现三角形,一定是盖住关 系没有找对。纠正

的方法是重新考察这3个元素在偏序中的顺序中的顺序,然后将不满足盖住关 系的那条边去掉。请看图 4.6(1)中的哈斯图。图中有两个三角形,即三角形abc和abd。根据结点位 置可以看出满足如下的偏序关系:



从而得到 和 。这就说明c和d不盖住a ,应该把ac边和ad边从图中去掉,从而得到正确的哈斯图,如图4.6(2)所示。

2° 哈斯图中不应该出现水平线段。根据哈斯图的层次结构,处在同一水平位置的结点是同一层的,它们没有顺序上的 “大小”关系,是不可比的。出现这种错误的原因在于没有将“较大”的元素放在“较小”元素的上方。纠正时只 要根据“大小”顺序将“较大”的元素放到更高的一层,将水平线改为斜一就可以了。

3° 哈 斯图中应尽量减少线的交叉,以使得图形清晰、易读,也便于检查错误,图形中线的交叉多少主要取决于同一层结 点的排列顺序,如果出现交叉过多,可以适当调正结点的排列顺序,注意变动结点时要同时移动连线。
< br>最后谈谈怎样确定哈斯图中的极大元、极小元、最大元、最小元、最小上界和最大下界,具体的方法是:< br>
1° 如果图中有孤立结点,那么这个结点既是极小元,也是极大元,并且图中既元最小元,也元 最大元(除了图中只有唯一孤立结点的特殊情况)。

2° 除了孤立结点以外,其他的极小元是 图中所有向下通路的终点,其他的极大元是图中所有向上通路的终点。

3° 图中唯一的极小元是最小元,唯一的极大元是最大元;否则最小元和最大元不存在。

4° 设B为偏序集 的子集,若B中存在最大元,它就是B的最小上界;否则从A-B中选择那些向下可达B中每一个 元素的结点,它们都是B的上界,其中的最小元是B的最小上界。类似地可以确定B的最大下界。

观察图4.5,1是所有向下通路的终点,是极小元,也是最小元,向上通路的终点有9,6,8,10和7, 这些是极大元。由于极大元不是唯一的,所以,没有最在元。地于整个偏序集的最小上界和最大下界,就是它的最 在元和最小元,因此,该偏序集没有最小上界,最大下界是1。

4.7 A:④; B:⑤; C:③; D:①; E:⑦

4.8 A:②; B:①; C:④; D:②; E:⑨

分析 给定函数 ,怎样判别它是否满足单射性呢?通常是根据函数的种类采取不同的方法。

1° 若 是实数区间上的连续函数,那么,可以通过函数的图像来判别它的单射性。如果 的图像是严格单调上升(或下升)的,则 是单射的。如果在 的图像中间有极大或极小值,则 不是单射的。

2° 若 不是通常的初等函数。那么,就须检查在 的对应关系中是否存在着多对一的形式,如果存在 但 ,这就是二

对一,即两个自变量对应于一个函数值,从而判定 不是单射的。

下面考虑满射性的判别,满射性的判别可以归结为 的值域 的计算。如果 ,则 是满射的,否则不是满射的。求 的方法说明如下:

1° 若 是实数区间上的初等函数,为了求 首先要找到 的单调区间。针对 的每个单调区间求出 的该区音的最小和最大值,从而确定 在这个区间的局部值域。 就是所有局部值域的并集。对于分段的初等函数也可以采用这种方法处理。

2° 若 是用列元素的方法给出的,那么 就是所有有序对的第二元素构成的集合。

本题中只有 是定义 于实数区间上的初等函数。易见,指数函数的图像是严格单调上升的,并且所有的函数值都大于0。从而知道 是单射的,但不是满射的。对于 ,由

可知,它不是单射的。但 ,所以,它是满射的。 既不是单射的,也不是满射的,因为 且 是单射的,但不是满射的。因为 时,必有 但

4.9 A:③; B:①; C:⑦; D:⑤; E:⑨

分析 (1)先求出T的特征函数 ,它是从S到 的函数。而 中的函数是从 到 的函数,这就是说该函数应包含3个有序对,有序对的第一元素是 ,而第二元素应该从 中选取(可以重复选取 )。不难年出只有①满足要求。

(2)等价关系R对应的划分就是商集S/R。检查R的表达式 ,如果 ,那么x,y就在同一个等价类。不难看出S中的元素被划分成两个等价类: ,因而对应的划分有2个划分块。

考虑自然映射 它将S中的元素所在的等价类,即将a映到 ,将b映到 ,将c映到 ,将g写成集合表达式就是



通常的自然映射是满射 的,但不一定是单射的,除非等价关系为恒等关系,这时每个等价类只含有一个元素,不同元素的等价类也不同, g就成为双射函数了。

4.11 (1)





(2)



(3)

]

4.12 对称性

4.13







4.14














图4.7

分析 根据闭包的计算公式



可以得到由关系图 求闭包的方法.

设G是R的关系图,G的结点记为 的关系图分别记作 和 .

为求 ,先将图G的结点和边拷贝到 中缺少环的结点都加上环就得到了 的关系图.

为求 ,也须将图G拷贝到 ,然后检查 的每一对结点 和 .如果在 和 之间只存在一条单向的边,就在这两个结点间加上一条方向相反的边.当 中所有的单向边都变成双向边以后就得到了 的关系图.

最后拷虑 .首先将图G拷贝到 ,然后从 开始依次检查 .在检查结点 时,要找出从 出发经过有限步(至少1步,至多n步)可达的所结点(包括 自己在内)。如果从 到这种结点之间缺少边,就把这条边加到 中,当n个结点全部处理完毕,就得到 的关系图。

以本题为例,依次检查结点 从a出发可达 四个结点

,所以图 中应该加上 和的边。从b出发可达 三个结点,所以,图 中应该加上 的边。从c出发可达c和d,在 中应该加上边 ,即通过c的环,类似地分析可以知道,在 中还应该加上过d的环。

4.15 若S不是单元集,则 不构成S的划分。

4.16 在图4.8(1)中极小元、最小元是1, 极大元、最大元是24,在图4.8(2)中极小元、最小元是1,极大元是5,6,7,8,9,没有最大元。












4.17 (1)不能; (2)能; (3)不能。

分析 函数和关系的区别在于它们的对应法则。在关系R的表达式中,如果 ,就说x对应到y,对于二元关系R,这种 对应可以是一对一的,多对一的和一对多的。这里的一对多指的是一个x对应到多个y,但是对于函数,则不允许 这种一对多的对应。至于单射函数,不但不允许一对多,也不允许多对一,只能存在一对一的对应。为了判别一个 关系是否为函数,就要检查关系的对应中是否存在一对多的情况。如本题中的(1)式,<1,2>和<1,1> 同时在关系中出现,因此不是函数。又如(3)式,<1,1>和<1,-1>也同时在关系中出现,破坏了函数 定义。

4.18 当 时满足要求。

4.19 ,且









分析 注意合成的正确表示方法。表示 和 合成的方法有两种:

1°说明 是从哪个集合到个集合的函数,然后给出 的计算公式。

2° 给出 的集合表达式。

本题中的结果都采用了第一种表示方法,先说明地果函数是从N到N的函数,然后分别给出函数值的计算 公式。也可以彩用第二种方法,如

,



但是,如果写成 就错了,因为 是函数,是有序对的集合,与函数值 是根本不同的两回事,不能混为一谈。

4.20



分析 首先由 的双射性确定 一定存在,然后通过 的定义求出反函数的对应法则。设 将 对应到 。根据 的定义有



因而反函数的对应法则是 对应到 。

4.21 (1) 如下列出 的对应关系

0 1 2 3 4 5 6 7 8…

1 2 3 4 0 5 6 7 8…

3 1 3 2 0 3 3 3 4…

从而得到



是满射的,但不是单射的。

(2)

4.22 (1)

其中





(2)令 ,且



分析 对于任意集合A,都可以构造从 到 的双射函数,任取A的子集 的特征函数 定义为



不同的子集的特征函数也不 同,因此,令



是 到 的双射,在本题的实例中的 是



4.23 (1)

(2)

分析 给定集合A,B,如何构造从A到B的双射?一般可采用下面的方法处理。

1° 若A,B都是 有穷集合,可以先用列元素的方法表示A,B,然后顺序将A中的元素与B中的元素建立对应,如习题4.22.

1° 若A,B都是有穷集合,可以先用列元素的方法表示A,B,然后顺序将A中
< br>的元素与B中的元素建立对应,如习题4.22。

2° 若A,B是实数区间,可以采用直线方程作为从A到B的双射函数。

例如, 是实数区间。如图 4.9所示,先将A,B区间分别标记在直角坐标系的x轴和y轴上,过(1,2)和(2,6)两点的直线方程 将A中的每个数映到B中的每个数,因此,该直线方程所代表的一次函数就是从A到B的双射函数。由解析几何的 知识可以得到双射函数

这种通过直线方程构造双射函数的方法对任意两个同类型的实数区间( 同为闭区间、开区间或音开半闭的区间)都是适用的。但对半开半闭的区间要注意开端点与开端点对应,闭端点与 闭端点对应。此外还要说明一点,对于某些特殊的实数区间可能选择其他严格单调的初等函数更方便,例如, ,那么取 即可。

3°A是一个无穷集合,B是自然数集N。

为构造从A到B 的双射只须将A中的元素排成一个有序序列,且指定这个序列的初始元素,这就叫做把A“良序化”。比如说A良 序化以后,是集合 ,那令

就是从A到B的双射。

例如,构造从整数集Z到 自然数集N到自然数集N的双射。如下排列Z中元素,然后列出对应的自然数,即








观察这两个序列,不难找到对应法则。







显然f是从Z到N的双射。

最后要指出 ,并不是任何两个集合都可以构造双射的。比如说,含有元素不一样多的有穷集之间不存在双射。即使都是无穷集 也不一定存在双射,如实数集R和自然数集N之间就不存在双射。这就涉及到集合“大小”的描述和度量方法,限 于篇幅地此就不进行探入讨论了,有兴趣的读者可以阅读其他的《离散数学》书籍。

4.24 为N上的恒等关系,且有



与y的奇偶性相同。在N中的所有奇数构成一个等价 类,所有的偶数构成另一个等价类。因此,



,即x除以3的余数与y除以3的 余数相等。根据余数分别这0,1,2,可将N中的数分成3个等价类,因而



4.25 (1)

不是单射也不是满射。





(2)
不是单射也不是满射。







第5 章 习题解答



5.1 A:③; B:⑥; C:⑧; D:⑩; E:⑨

分析 S为n元集,那么 有 个元素.S上的一个二元运算就是函数 .这样的函数有 个.因此 上的二元运算有 个.

下面说明通过运算表判别二元运算性质及求特导元素的方法.

1 °交换律 若运算表中元素关于主对角线成对称分布,则该运算满足交换律.

2 °幂等律 设运算表表头元素的排列顺序为 如果主对角线元素的排列也为 则该运算满足幂等律.

其他 性质,如结合律或者涉及到两个运算表的分配律和吸收律,在运算表中没有明显的特征,只能针对所有可能的元素 等来验证相关的算律是否成立.

3 ° 幺元 设运算表表头元素

的排列顺序为 如果元素 所在的行和列的元素排列顺序也是 则 为幺元.

4 ° 零元 如果元素 所在的行和列的元素都是 ,则 是零元.

5 ° 幂等元.设运算表表头元素的排列顺序为 如果主对角线上第 个元素恰 为 那么 是幂等元.易见幺元和零元都是幂等元.

6 ° 可逆元素及其逆元.设 为任意元素,如果 所在的行和列都有幺元,并且这两个幺元关于主对角线成对称分布,比如说第 行第 列和第 行第 列的两个位置,那么 与 互为逆元.如果 所在的行和列具有共同的幺元,则幺元一定在主对角线上,那么 的逆元就是 自己.如果 所在的和地或者所在的列没有幺元,那么 不是可逆元素.不难看出幺元 一定是可逆元素,且 而零元 不是可逆元素.

以本题为例, 的运算表是对称分布的,因此,这三个运算是可交换的,而 不是可交换的.再看幂等律.四个运算表表头元素排列都是 ,其中主对角线元素排列为 的只有 ,所以, 遵从幂等律.下面考虑幺元.如果某元素所在的行和列元素的排列都是 ,该元素就是幺元.不难看出只有 中的a满足这一要求,因此,a是 的幺元,其他三个运算都不存在幺元.最后考虑零元.如果a所在的行和列元 素都是a,那么a就是零元;同样的,若b所在的行和列元素都是b,那么b就是零元.检查这四个运算表, 中的a满足要求,是零元,其他运算都没有零元.在 的运算表中,尽管a和b的列都满足要求,但行不满足要求.因而 中也没有零元.

5.2 A:①; B:③; C:⑤; D:⑦; E:⑩

分析 对于用解析表达式定义的二元运算 °和 *,差别它们是否满足交换律,结合律,幂等律,分配律和吸收律的方法总结如下:

任取 ,根据 °运算的解析表达式验证等式 是否成立.如果成立 °运算就满足交换律.

2 ° °运算的地合律

任取 根据 °运算的解析表达式验证等式 是否成立. 如果成立, °运算就是可结合的.

3 ° °运算的幂等律

任取x,根据 °运算的解析表达式验证等式 是否成立.如果成立, °运算满足幂等律.

4 ° °运算对*运算的分配律

任取 ,根据 °和*运算的解析表达式验证等式 和 是否成立。如果成立,则°运算对*运算满足分配律。

5 ° °和*运算的吸收律

首先验证 °和*运算是可交换的。然后任取 根据 °和 *运算的解析表达式验证等式 和 是否成立。如果成立,则°和 *运算满足吸收律。

设°是 用解析表达式定义的A上的二元运算,求解对于该运算的特导元素可以采用下述方法:

1 ° 求幺元e。根据幺元定义, 应满足等式 。将等式中的 和 用关于°运算的解析表达式代入并将结果化简,然后由x的任意性来确定

2 °求零元 根据零元定义, 应该满足等式 。将等式中的 和 用关于 °运算的解析表达式代入并将结果化简,然后由x的

任意性确定

3 ° 求幂等元. 将 等式中的 用关于 °运算的解析表达式代入并化简单,然后求解该议程,所得到的解就是幂等元.

4 ° 求可逆元素的逆元. 任取 ,设x的逆元为y,则x与y应该满足等式 将等式中的 与 用关于°运算的解析表达式代入,并将e用 °运算的幺元代入,然后化简等式.观察使得该等式成产的x应该满 足的条件,然后将y用含有x的公式表示出来,从而得到x的逆元.这里特别要说明一点,如果°运算不存在幺元 则所有有元素都是不可逆的.

以本题为例,具体的分析过程如下:

任取 ,由





可知一般情况下 ,所以 运算不是可交换的.

任取 ,由









可知 运算是可结合的.

设 运算的幺元为 则 有

,

,

代入关于 运算的解析表达式得

< br>


从而得到



由于 是任意有理数,要使得上述四个等式都成立,必有



所以, 运算的幺元为 .

对于任意的 ,设 的逆元为 ,那么有





代入关于 运算的解析表达式得





从而得到



解得



这说明对一切 ,只要 都存在逆元 .

最后补充说明一点.不难验证, 运算没有零元.而关于 运算的幂等元是 和 ,其中 为任意有理数.

5.3 A:⑦; B:⑥; C:⑤; D:③; E:②

分析 怎样检验运算 是否为S上的二元运算,或者说S是否关于 运算封闭?主要是验证以下两个条件是否满足;

1 °任何S中的元素都可以作为参与运算的元素.

2° 运算的结果仍旧是S中的元素.

如果给定了两个以上的运算,在讨论封闭性时要分别对每个运算讨论.

容易验证本题中 的6个函数全是实数集R上的二元运算.它们的可交换性,结合性, 幺元和零元的判别结果如下.
交换t结合t幺元t零元








< br>





×











×







×

为0

×

为1
×

×

×

×

×

为0

×

×

×



5.4 A:②; B:⑤; C:⑦; D:⑧; E:⑧

分析 对于给定的自然数



是V的子代数,因为 有





这说明 关于+和 运算都是封闭的,满足子代数的定义.由于 可以取任何自然数,这样的子代数有无数多个.其中当 时, 是有穷集合.即有限的子代数,其余都是无限的子代数.

对于 来说,它是奇整数的集合.而奇数加奇数等于偶数,因而 关于加法不封闭.类似地, 关于加法也不封闭,因为 ,但 .因而可以判定 和 都不是V的子代数,尽管 和 对于乘法是封闭的.

5.5 A:④; B:⑨; C:①; D:①; E:④

分析 构成代数系统的要素有三个:集合,二元或一元运算及代数常数.如果 是代数系统 和 的同态,那么 必须满足以下条件:

1° 即 是 和 的函数.

2° 对 和 上任意对应的二元运算 和 有



对 和 上任意对应的二元运算 和 有



3° 对 和 上任意对应的代数常数 和 有



以本题为例.因为只有一个二元运算,验证时只要检验条件1°,2° 即可.具体的验

证过程如下: 都是 到 的映射, 且





所以 和 是V的自同态.但是 和 不是V的自同态.原因如下:



,

故 ,破坏了同态映射的条件2°.而对于 ,它将正数映到负数,根本不是 到 的函数,破坏了条件1°,当然更 谈不到同态了.

通过上面的分析已经知道了判别同态及其性质的基本方法.下面补公介绍一些典 型同态映射的实例,以供读者参考.

1° 是整数加群.令 这里的a是给定的整数.那么 有



是V的自同态.

当 时, 不是单同态,也不是满同态,其同态象为 .

当 时, 为自同态.

当 时, 为单自同态,其同态象为 ,其中

2° 是模n整数加群,其中 .可以证明 是V的自同态.因为 有







由于p有n种取 值,这里定义了n个自同态.

例如, 上有6个自同态,即 .其中




















这3个自同态中 和 是自同构,其他的既不是单同态,也不是满同态. 的同态象为 . 和 的同态象为 的同态象为 .

3° 设 分别为整数加群和模n整数加群. 容易证明 是 满同态.

4° 设 其中 和 分别代表实数集和非零实数集,+和?分别代表普能加法和乘法. 是 和 的单同态,其同态象为 ,这里的 是正实数集.

5° 设 是具有一个二元运算和代数系统. 和 的积代数为 令 ,那么 是积代数 到 同态的,因为对任意 有





容易看出 是满同态.只有当B为单元集时 为同构.

5.6 A:⑤; B:③; C:②; D:①; E:⑧

5.7 (1)和(4)是代数系统.

(2)不是,例如

(3)不是,例如

(5)不是,例如

5.8 (1)封闭,若 是16的倍数,则 也是16的倍数.

(2)不封闭,例如2和5互质,3也 和5互质,但2+3=5却不和5互质.

(3)不封闭,3和5都是30的因子,但是3+5= 8不是30的因子.

(4)封闭

5.9 (1)可交换,不幂等.a是幺元,且 和c互逆元.

(2)不可交换,有幂等性,元幺元,当 然不考虑逆元了.

(3)可交换,有幂等性, 幺元是 和c都没有逆元.

分析 这里补谈谈结合律的判定问题.在验证结合律 是否成立时,等式中的 可以取 中的任何元素,共有27种可能的选法.这意味着必须要要验证27个等式,工作量很大.若 中有幺元或零元存 在,则等式显然成立.考虑到这个因素,在验证时可以不选取集合中的幺元和零元.下面以本题为例来判定结合律 是否成立.

(1)a是幺元.只须对b和 c进行验证.又由于*运算的可交换性,全是b或全 是c情况可以忽略,因而需要验证的只有下面六种情况:





< br>






由以上验证可知*运算是可结合的.

(2)通过观察发现, 有 每个元素都是右零元.因而必有 ,



这就证明了结合律是成立的.

(3)c是零元,故只须对a和b验证.显然 因此,只须考虑至少含有一个b的等式.由 可知无论b处在哪一个位置,等式两边都等于b,因此结合律成立.

5.10 结果如表5.2 所示

表5.2

<0,0>t<0,1>t<1,0>t<1,1>t<2,0 >t<2.1>



<0,0>

<0,1>

< 1,0>

<1,1>

<2,0>

<2,1>t<0,0>< br>
<0,0>

<1,0>

<1,0>

<2,0 >

<2,0>t<0,0>

<0,1>

<1,0>

<1,1>

<2,0>

<2,1>t<1,0>

< 1,1>

<2,0>

<2,0>

<0,0>

<0,0>t<1,0>

<1,1>

<2,0>

<2,1 >

<0,0>

<0,1>t<2,0>

<2,0>

<0,0>

<0,0>

<1,0>

<1,0>t< 2,0>

<2,1>

<0,0>

<0,1>

<1,0>

<1,1>

其中<0,1>为幺元.

5.11 t运算表如表5.3所示.



1 2 5 10t*t1 2 5 10txt 1

2

5

10t1 1 1 1

1 2 1 1

1 1 5 5

1 2 5 10

1

2

5

10t1 2 5 10

2 2 10 10

5 10 5 10

10 10 10 10

1

2

5

10t10
5

2

1

5.12 (1)可交换,不可结合 ,无幺元,无可逆元素.

(2)不可交换,不可结合,无幺元,无可逆元素.

(3)可交换,可结合, 幺元是1, 有 .

5.13 结果如表5.4所示.

表5.4

*t0 1 2 3 4

0

1

2

3

4t0 0 0 0 0

0 1 2 3 4

0 2 4 1 3

0 3 1 4 2

0 4 3 2 1

零元 0

幺元 1

逆元

0元逆元.

5.14 其中









第6章 习题解答



6.1 A:⑨; B:⑨; C:④; D:⑥; E:③

分析 对于给定的集合和运算判别它们是否构成代数系统的关键是检查集合对给定运算 的封闭性,具体方法已在5.3节做过说明. 下面分别讨论对各种不同代数系纺的判别方法.

1°给定集合S和二元运算°,判定是否构成关群、独导点和群.

根据定义,判别时要涉及到以下条件的验证:

条件1 S关于 °运算封闭:

条件2 °运算满足结合集

条件3 °运算有幺元,

条件4 °

其中关群判定只涉及条件1和2;独导点判定涉 及条件1、2、和3;而群的判定则涉及到所有的四个条件。

2 ° 给定集合S和二元运算 °和 *,判定是否构成环,交换环,含幺环,整环,域.根据有关定义需要检验的条件有:

条件1 S构成交换群,

条件2 构成关群,

条件 3 * 对 °运算的分配律,

条件4 * 对运算满足交换律,

条件5 * 运算有幺元,

条件6 * 运算不含零因子——消去律,

条件7 有 (对*运算).

其中环的判定涉及条件1,2和3;交换环的判定涉及条件1,2,3和4;含 幺环的判定涉及条件1,2,3和5;整环的判定涉及条件1-6;而域的判定则涉及全部7个条件.
< br>3° 判定偏序集 或代数系统 是否构成格、分本配格、有补格和布尔格.

若 为偏序集,首先验证 和 是否属于S.若满足条件则S为格,且 构成代数系统.若 是代数系统且°和*运算满足交换律、结合律和吸收律,则 构成格。

在此基础上作为分配格的 充分必要条件是不含有与图6.3所示的格同构的子格。而有补格和布尔格的判定只要根据定义进行即可。注意对 于有限格,只要元素个数不是2的幂,则一定不是布尔格。但元素个数恰为 的有限格中只有唯一的布尔格。

以本题为例具体的判定过程如下:

(1)t由 可知 对+运算不封闭,根本不构成代数系统。

(2)由 可知 对*运算不封闭,也不构成代数系统。



(3) 关于 运算封闭,构成代数系统。且 关于模n加法 满足交换群的定义,关于模n乘法*满足关群的定义,且*对 有分配律。因而 构成环。但当n=6时,有 中含有零因子2和3,不是整环,也不是域。类似地分析可知,当n为合数时, 不是域,但n为素数时 构成域。

(4) 是偏序集。对于小于等于关系 ,显然有 ,构成格。但 不是有补格,2和3没有补元,也不是布尔代数。

(5)容易验证 关于矩阵加法构成群。

6.2 A:②; B:③; C:⑦; D:⑩; E:⑨

分析 此处的G实际上是 关于模n加法构成群,但关于模n乘法只构成独导点,而不构成群,因为0没乘法逆元。 是循环群。2是2阶元 ,1和3是4阶元。

如何求群G中元素的阶?如果 ,则 是n的正因子。首先找到n的正因子,并从小到大列出来,然后依次检查每相正因子r。使得 的最小的正因子r就是x的阶。本题的 4的正因子是1,2,4。由于





所以, 。类似地有





6.3 2 A:②; B:④; C:⑤; D:⑦; E:⑧

分析 (1)根据布尔代数定义可知 和 运算适合交换律、结合律、幂等律、分配律、D?M律等,适合消去律。 ,所以,0是V运算的幺元,1是V运算的零元。由于在布尔代数的表示 中,0和1是作为代数常数列出来的,所以,最小的子布尔代数应包含所有的代数常数。经验证 恰构成子布尔代 数,因而是最小的子布尔代数。

(2)表达式的等价式与对偶式是两个要领,应加以区别.容易 看出,由吸收律、交换律、分配律有



= 吸收集

= 交换集

= 分配律

这说明该表达式与 是等价的,而其他两个表达式都不满足要求。

6.4 易证Z对 °运算是封闭的,且对任意 有





结合律成立。2是 °运算的幺元。 是x关于 °运算的逆元。综合上述,构成群。

6.5 根据矩阵乘法可以得到G的运算表如下:



?ta b c d

a

b

c

dta b c d

b a d c

c d b a

d c a b

由运算表可以看出a是幺元。又由



知道 当 与G中元素x的阶相等时,有 。因此G是4阶循环群。

G的子群有 三个。令 ,则 的哈斯图如图6.4所示。

分析 这里对怎样求一个循环群的生成元和子群做一点说明。

1 °若 是无限循环群,那么G只有两个生成元,即 和 。G的子群有元数多个,它们分别由 生成。这里的 可以是0,1…。将 生成子群的元素列出来就是



该子群也是一个无限循环群。不难证明当 时,子群 。

例如, 是n阶循环群,那么 。G的生成元有 个,这里的 是欧拉图函数,即 小于等于n且与n互素的正整数个数。求生成元的方法是:先找到所有有小于等于n且与n互素的正整数.对于每 个这样的正整数r, 就是G的d阶子群.

以本题为例. ,与4互素的数是1和3.因此 的生成元

是 再考虑子群.4的正因子是1,2,4所以,G的子群有3个,即

1阶子群

2阶子群

4阶子群

根据包含关系不难得到图6. 4所示的哈斯图.

6.6 对普通加法和乘法是封闭的,且加法满足交换律,结合律,乘法满 足结合律,第六法对加法满足分配律.又知道加法的幺元是0, 是 的负元.从而 关于加法和乘法构成环.容易看出这是一个整环,但不是域.

6.7 (1) 不是格,(2),(3)和(4)都是格.

6.8 任取 由S的性质有

,

S关于 是封闭的,构成代数系统 容易验证 运算满足结合律. 幺元是0,因为 有



同理有 且 有



6.9 (1)

(2)

分析 设G为群, .群方程 在G中有唯一解 类似地,群方程 在G中也有唯一解 .代入本题有



由于对任何 有 ,因而有



尽管 中包含了B的所有幂,但只有两个结果,即 和 .

6.10 (1)

(2)



分析 为了求出 的轮换表示,先任选一个元素,比如说1,从上述表示式中找到 如果 ,则第一个轮换就找到了,是(1).如果 ,接下去找 继续这一过程,直到某个 满足 为止.通过这样的挑选,从 中选出了一个序列: 其中的元素满足 , .这就是从 中中解出来的第一个轮换 如果该轮换包含了 中的所有元素,那么分解结否,并且有 否则任取 中没有剩下的元素为止.

以本题的 为例.由 的置换表示知道. 从而得到第一个轮换(124).接着从 中选取3,继续这一过程,得到 ,这就是第二个轮换(365).所有的元素都出现在轮换之中,分解结束,并且

在求置换 的轮换表示时可将表示式中的1轮换省略.例如, 中的(2)和(5)都是1-轮换,可将 简记为(13) (46).此外要说明的是表示式中的轮换是不相交的,即同一个元素不能出现在两个轮换之中.如果交换了轮换 的次序,或者选择了轮换中不同的元素作为首元素而保持顺序不变,那么所得的轮换表示是相同的.例如, 也可以写作 或 等.

给定n元置换 和 ,怎样求 或 呢?根据复合函数的定义,只需求出 (1), (2),…, (n)就可以得到 的置换表示或轮换表示.以本题为例, 类似地有

,从而得到 =(15423)(6),化简为 =(15423).逆的计算比乘法简单.设 为 的轮换表示式,那么 ,其中的 若为轮换 ,则有 例如, ,则 .从而







因此,得到 .在 的计算中有 出现.观察到 的表示式(15423)中不含有6,这就意味着 (6)=(6).

6.11 (1) 是同态映射. 当 时为单同态,满同态和同构.而当G不是平凡群时, 既不是单同态,也不是满同态.

(2) 是同态映射,且为单同态,不是满同态.

(3) 是同态映射,也是单同态和满同态.

6.12 (1) 哈斯图如图6.5 所示.

(2) 可以构成布尔代数. 是x与y的最小公倍数, 是x与y的最大公约数.而A关于 和 运算是封闭的.容易验证 和 运算满足交换律,结合律,吸收律,且是互相可分配的,因此,该偏序集构成分配

格. 是x与y的最小公倍数, 是x与y的最大公约数.而A关于 和 运算是封闭的.容易验证 和 运算满足交换律,结合律,吸收律,且是互相可分配的,因引,该偏序集构成分配格. 是x的补元,这就证明了该偏序集构成分配格.即布尔代数.

6.13 (1) 图6.1中的(3),(4),(5),(8)图不是格.(3)图中的 没有最小上界;(4)图中的 没有最大下界;(5)图中的 没有最大下界;(8)图中的 没有最小上界.

(2) 图6. 1中的(1),(2)图为分配格,但不是有补格和布尔格;(6)图不是分配格和布尔格,但是有补格;(7) 图不是分配格,也不是有补格和布尔格.

分析 图 6.1中格(1)和(2)的所有五元子 格都不与图6.3中的格同构,因而它们都是分配格.但对于图6.1(6)和(7)中的格都能找到与图6.3 (2)中的格同构的子路.例如,图6.1(6)中的 和(7)中的 ,因此,它们都不是分配格.

再考虑补元.(1)图中格的 元素都没补元;(2)图中格的 元素都没补元;(7)图中格的d元素没有补元.它们不是有补格.而(6)图中格的每个元素都有补元,是有补 格.

6.14 (1)图中0与1互为补元; 都没有补元.(2)图中0与1互为补元;a的补元是b和d; c的补元是b和d的补元为a和c;d的补元为 a和c.(3)图中0与1互为补元;b与c互为补元;a和d都没有补元.



第7章 习题解答



7.1 (1),(2),(3),(5)都能构成无 向图的度数列,其中除(5)外又都能构成无向简单图的度数列.

分析 1° 非负整数列 能构成无向图的度数列当且仅当 为偶数,即 中的奇数为偶数个.(1),(2),(3),(5)中分别有4 个,0个,4个,4个奇数,所以,它们都能构成无向图的度数列,当然,所对应的无向图很可能是非简单图.而 (4)中有3个奇数,因而它不能构成无向图度数列.否则就违背了握手定理的推论.

2°(5 ) 虽然能构成无向图的度数列,但不能构成无向简单度数列.否则,若存在无向简单图G,以1,3,3,3为 度数列,不妨设G中顶点为 ,且 ,于是 而 只能与 之一相邻,设 与 相邻,这样一来,除 能达到3度外, 都达不到3度,这是矛盾的.

在图7.5所示的4个图中,(1) 以1为 度数列,(2)以2为度数列,(3)以3为度数列,(4)以4为度数列(非简单图).














7.2 设有几简单图D以2,2,3,3为度数列,对应的顶点分别为 ,由于 所示,



由此可知,D的出度列为2,2,1,0,且满足 .请读者画出一个有向图 .以2,2,3,3为度数列,且以0,0,2,3为入度列,以2,2,1,0为出度列.

7 .3 D的入度列不可能为1,1,1,1.否则,必有出度列为2,2,2,2(因为 ,)此时,入度列元素 之和为4,不等于出度列元素之和8,这违背握手定理.类似地讨论可知,1,1,1,1也不能为D的出席列.

7.4 不能. N阶无向简单图的最大度 而这里的n个正整数彼此不同,因而这n个数不能 构成无向简单图的度数列,否则所得图的最大度大于n,这与最大度应该小于等于n-1矛盾.

7.5 (1) 16个顶点. 图中边数 ,设图

中的顶点数为 .根据握手定理可知

所以,

(2) 13个顶点.图中边数 ,设3度顶点个数为x,由握手定理有



由此方程解出 .于是图中顶点数

(3) 由握手定理及各顶点度数均相同,寻找方程



的非负整数解,这里不会出现 均为奇数的情况. 其中 为阶级,即顶点数, 为度数共可得到下面10种情况.

①个顶点, 度数为48.此图一定是由一个顶点的24个环构成,当然为非简单图.

②2个顶点,每个顶点 的度数均为24.这样的图有多种非同构的情况,一定为非简单图.

③3个顶点,每个顶点的度 数均为16.所地应的图也都是非简单图.

④4个顶点,每个顶点的度数均为12. 所对应的 图也都是非简单图.

⑤6个顶点,每个顶点的度数均为8,所对应的图也都是非简单图.

⑥个顶点,每个顶点的度数均为6.所对应的非同构的图中有简单图,也有非简单图.

⑦12个顶点,每个顶点的度数均为4. 所对应的非同构的图中有简单图,也有非简单图.

⑧16个顶点,每个顶点的度数均为3,所对应的非同构的图中有简单图,也有非简单图.

⑨2 4个顶点,每个顶点的度数均为2.所对应的非同构的图中有简单图,也有非简单图.

⑩48个 顶点,每个顶点的度数均为1,所对应的图是唯一的,即由24个 构成的简单图.

分析 由于n阶无向简单图G中, ,的以①-⑤所对应的图不可能有简单图.⑥-⑨既有简单图,也有非简单图,读者 可以画出若干个非同构的图,而⑩只能为简单图.

7.6 设G为n阶图,由握手定理可知

,

所以,



这里, 为不大于 的最大整数,例如

7.7 由于 ,说明G中任何顶点 的度数 ,可是由于G为简单图,因而 ,这又使得 ,于是 ,也就是说,G中每个顶点的度数都是 ,因而应有 .于是G为 阶正则图,即G为n阶完全图

7.8 由G的补图 的定义可知, 为 ,由于n为奇数,所以, 中各项顶点的度数 为偶数.对于任意的 应有 且



其中 表示 在G中的度数, 表示 在 中的度数.由于 为偶数,所以, 与 同为奇数或同为偶数,因而若G有r个奇度顶点,则 也有r个奇度顶点.

7.9 由于 所以, .而n阶有向简单图中,边数 ,所以,应有



这就导致 ,这说明D为n阶完全图,且 .

7.10 图7.6给出了 的18个非同构的子图,其中有11个生成子图(8-18), 其中连通的有6个11,12,13,14,16,17).图7.6中,n,m分别为顶点数和边数.

7.11 有11个生成子图,在图7.6中,它们分别如图8-18所示.要判断它们之中哪些是 自补图,首先要知道同构图的性质,设 与 的顶点数和边数.若 ,则 且 .




















(8)的补图为 ,它们的边数不同,所以,不可能同构. 因而(8)与(14)均不是自补图类似地,(9)的补图为(13),它们也非同构,因而它们也都不是自补图 .(10)与(12)互为补图,它们非同构,因而它们都不是自补图.(15)与(17)互为补图,它们非同 构,所以,它们都不是

自补图.类似地,(16)与(18)互为补图且非同构,所以,它们也 都不是自补图.

而(11)与自己的补图同构,所以,(11)是自补图.

7 .12 3阶有向完全图共有20个非同构的子图,见图7.7所示,其中(5)-(20)为生成子图,生成 子图中(8),(13),(16),(19)均为自补图.

分析 在图7.7所示的生成子图中, (5)与(11)互为补图,(6)与(10)互为补图,(7)与(9)互为 补图,(12)与(14)互为补图,(15)与(17)互为补图,(18)与(20)互为补图,以上互为补 图的两个图边数均不相同,所以,它们都不是自补图.而(8),(13),(16),(19)4个图都与自己 的补图同构,所以,它们都是自补图.

7.13 不能.

分析 在同构的意义下, 都中 的子图,而且都是成子图.而 的两条边的生成子图中,只有两个是非同构的,见图7.6 中(10)与(15)所示.由鸽巢原理可知, 中至少有两个是同构的,因而它们不可能彼此都非同构.

鸽巢原理 只鸽飞进 个鸽巢,其中 ,则至少存在一巢飞入至少 只鸽子.这里 表示不小于x的最小整数.例如,

7.14 G是唯一的,即使G是简单图也不唯一.




















分析 由握手定理可知 ,又由给的条件得联立议程组



解出 6个顶点,9条边,每个顶点的度数都是3的图有多种非同构的情况,其中有多个非简单图(带平行边或环),有 两个非同构的简单图,在图7.8 中(1),(2)给出了这两个非同构的简单图.

满足条件的非同构的简单图只有图7.8 中 ,(1),(2)所示的图,(1)与(2)所示的图,(1)与(2)是非同构的.

注意在( 1)中不存在3个彼此相邻的顶点,而在(2)中存在3个彼此相邻的顶点,因而(1)图与(2)图非同构.下 面分析满足条件的简单图只有两个是非同构的.首先注意到(1)中与(2)中图都是 的生成子图,并且还有这样的事实,设 都是n阶简单图,则 当且仅当 ,其中 分别为 与 的补图.满足要 求的简单图都是6阶9条边的3正则图,因而它们的补图都为6阶6条边的2正则图(即每个顶点度数都是2). 而 的所有生成子图中,6条边2正则的非同构的图只有两个,见图7.8中(3),(4)所示的图,其中(3 )为(1)的补图,(4)为(2)的补图,满足要求的非同构的简单图只有两个.

但满足要求 的非同简单图有多个非同构的,读者可自己画出多个来.

7.15 将 的顶点标定顺序,讨论 所关联的边.由鸽巢原理(见7.13 题),与 关联的5条边中至少有3条边颜色相同,不妨设存在3条红色 边,见图7.9中(1)所示(用实线表示红色的边)并设它们关联另外3个顶点分别为 若 构成的 中还有红色边,比如边( )为红色,则 构成的 为红色 ,见图7.9中(2)所示.若 构成的 各边都是蓝色(用虚线表示),则 构成的 为蓝色的.





< br>




7.16 在图7.10 所示的3个图中,(1)为强连通 图,(2)为单向连通图,但不是强连通的,(3)是弱连通的,不是单向连通的,更不是强连通的.
< br>











分析 在(1)中任何两个顶点之

间都有通路,即任何两个顶点都是相互可达的,因而它是 强连能的.(2)中c不可达任何顶点,因而它不是强连通的,但任两个顶点存在一个顶点可达另外一个顶点,所 以,它是单向可达的.(3)中 互相均不可达,因而它不是单向连通的,更不是强连通的.

判 断有向图的连通性有下面的两个判别法.

1°有向图D是强连通的当且仅当D中存在经过每个顶 点至少一次的回路.

2°有向图D是单向连通的当且仅当D中存在经过每个顶点至少一次的通路 .

(1) 中 为经过每个顶点一次的回路,所以,它是强连能的.(2)中 为经过每个顶点 的通路,所以,它是单向连通的,但没有经过每个顶点的回路,所以,它不是强连通的.(3)中无经过每个顶点 的回路,也无经过每个顶点的通路,所以,它只能是弱连通的.

7.17 的连通分支一定为2,而 的连通分支数是不确定的.

分析 设 为连通图G的边割集,则 的连通分支数 不可能大于2.否则,比如 ,则 由3个小图 组成,且 中边的两个端点分属于两个不同的小图.设 中的边的两个端点一个在 中,另一个在 中,则 ,易知 ,这与 为边割集矛盾,所以, .

但 不是定数,当然它大于等于2,在图7.11中, 为(1)的点割集, 其中G为(1)中图. 为(2)中图的点割集,且 为割点, ,其中 为(2) 中图.











7.18 解此题,只要求出D的邻接矩阵的前4次幂即可.






D中长度为4的通路数为 中元素之和,等于15,其中对角线上元素之和为3,即D中长度为3的回路数为3. 到 的长度为4的通路数等于 .

分析 用邻接矩阵的幂求有向图D中的通路数和回路数应该注意 以下几点:

1°这里所谈通路或回路是定义意义下的,不是同构意义下的.比如,不同始点(终 点)的回路

2° 这里的通路或回路不但有初级的、简单的,还有复杂的.例如, 是一条长为4的复杂回路.

3° 回路仍然看成是通路的特殊情况.

读者可利用 ,求 中长度为2和3的通路和回路数.

7.19 答案 A:④.

分析 G中有 个 度顶点,有 个 度顶点,由握手定理可知





7.20 答案 A:②; B:③.

分析 在图7.12中,图(1)与它的补同构,再没有与图(1)非同构的自补图 了,所以非同构的无向的4阶自补图只有1个.图(2)与它的补同构,图(3)与它的补也同构,而图(2)与 图(3)不同构,再没有与(2),(3)非同构的自补图了,所以,非同械的5阶自补图有2个.








7.21 答案 A:④; B:③; C:④; D:①.

分析 (1)中存在经过每个顶点的回路,如 .(2)中存在经过每个顶点的通路,但无回路.(3)中无经过每个顶点至少一次的通路,其实, 两个顶点互不可达.(4)中有经过每个顶点至少一次的通路,但无回路, 为经过每个顶点的通路.(5)中存在经过每个顶点至少一次的回路,如 (6)中也存在经过每个顶点的回路,如 由7.16题可知,(1),(5),(6)是强连

通的,(1),(2),(4),(5),(6)是单向连能的,(2),(4)是非强连通的单向连通图.注意 ,强连通图必为单向连通图.6个图中,只有(3)既不是强连通的,也不是连通的,它只是弱连通图.

在(3)中,从a到b无通路,所以 而 到 有唯一的通路 ,所以 .

7.22 答案 A:①; B:⑥㈩ C:②; D:④.

分析 用 标号法,将计算机结果列在表7.1中.表中第x列最后标定 /Z表示b到x的最短路径的权为y,且在b到x的最短路径上,Z邻接到x, 即x的前驱元为Z.由表7.1 可知,a的前驱元为c(即a邻接到c),c的前驱元为b,所以,b到a的最短路径为 ,其权为4.类似地计论可知,b到c的最短路径为bc,其权为1.b到d的最短路径为 ,其权为9.b到e 的最短路径为 ,其权为7.

表7.1

k

atbtct dtetftg

0

1

2

3

4

5

6t7

4

4/ct0t1

1/bt



12

12

12

9

9/gt

5

5

5

5/ct

4

4

4/ct





11

7

7/e



4t0t1t9 t5t4t7

7.23 答案 A:⑧; B:⑩u3000C:③; D:③和④.

分析 按求最早、最晚完成时间的公式,先求各顶点的最早完成时间,再求最晚 完成时间,最后求缓冲时间。

(1)最早完成时间:
















< br>

(2)最晚完成时间:






< br>











(3)缓冲时间:



(4)关键路径有两条: 和



第8 章 习题解答



8.1 图8.6 中,(1)所示的图为 (2)t所示的图为 (3)所示的图为 它们分别各有不同的同构形式.< br>












8.2 若G为零图,用一种颜色就够了,若G是非零图的二部图,用两种颜色就够了.

分析 根据二 部图的定义可知,n阶零图(无边的图)是三部图(含平凡图),对n阶零图的每个顶点都用同一种颜色染色,因 为无边,所以,不会出现相邻顶点染同色,因而一种颜色就够用了.

8.3 完全二部图 中的边数 .

分析 设完全二部图 的顶点集为V, 则 ,且 是简单图,且 中每个顶点与 中所有顶点相邻,而且 中任何两个不同顶点关联的边互不相同,所以,边数 .

8.4 完全二部图 中匹配数 ,即 等于 中的小者.

分析 不妨设 且二部图 中, 由Hall定理可知,图中存在 到的完备匹配,设M为一个完备匹配,则 中顶点全为M饱和点,所以,

8.5 能安排多种方案,使每个工人去完成一项他们各自能胜任的任务.

分析 设 ,则 为工人集合, ,则 为任务集合.令 ,得无向图 ,则G为二部图,见图8.7 所示.本题是求图中完美匹配问题. 给图中一个完美匹配就对应一个分配方案.图8.7 满足Hall定理中的相异性条件,所以,存在完备匹配,又因为 所以,完备匹配也为完美匹配.其实,从图上,可以找到多个完美匹配. 取



此匹配对应的方案为甲完成a,乙完成b, 丙完成c,见图中粗边所示的 匹配.



对应的分配方案为甲完成b,乙完

成a,丙完成c.

请读者再找出其余的分配方案.

8.6 本题的答案太多,如果不限定画出的图为简单图,非常容易地给出4族图分别满足要求.

(1) n (n 为偶数,且 )阶圈都是偶数个顶点,偶数条边的欧拉图.

(2) n (n 为奇数,且 )阶圈都是奇数个顶点,奇数条边的欧拉图.

(3) 在(1) 中的圈上任选一个顶点,在此顶点处加一个环,所务图为奇数个顶点,偶数条边的欧拉图.

分析 上面给出的4族图都是连通的,并且所有顶点的度数都是偶数,所以,都是欧拉图.并且(1),(2) 中的图都是简单图.而(3),(4)中的图都带环,因而都是非简单图. 于是,如果要求所给出的图必须是简 单图,则(3),(4)中的图不满足要求.

其实,欧拉图是若干个边不重的图的并,由这种性 质,同样可以得到满足(3),(4)中要求的简单欧拉图.设 是长度大于等于3的k个奇圈(长度为奇数的圈称为奇圈),其中k为偶数,将 中某个顶点与 中的某顶点重合,但边不重合, 中某顶点与 中某顶点重合,但边不重合,继续地,最后将 中某顶点与 中 某顶点重合,边不重合,设最后得连通图为G,则G中有奇数个顶点,偶数条边,且所有顶点度数均为偶数,所以 ,这样的一族图满足(4)的要求,其中一个特例为图8.8中(1)所示.在以上各图中,若 中有一个偶圈, 其他条件不变,构造方法同上,则所得图G为偶数个顶点,奇数条边的简单欧拉图,满足(3)的要求,图8.8 中(2)所示为一个特殊的情况.











8.7 本题的讨论类似于8.6题,只是将所有无向圈全变成有向圈即可,请读者 自己画出满足要求的一些特殊有向欧拉图.

8.8 本题的答案也是很多的,这里给出满足要求的最简单一些图案,而且全为简单图.

(1) ( )阶圈,它们都是欧拉图,又都是哈密尔顿图.

(2) 给定 ( )个长度大于等于3的初级回路,即圈 ,用8.6题方法构造的图G均为欧拉图,但都不是哈密尔顿图,图8. 8给出的两个图是这里的特例.

(3) ( )阶圈中,找两个不相邻的顶点,在它们之间加一 条边,所得图均为哈密尔顿图,但都不是欧拉图.

(4) 在(2)中的图中,设存在长度大于等于4的圈,比如说 ,在 中找两个不相邻的相邻顶点,在它们之间加一条 新边,然后用8.6题方法构造图G,则G既不是欧拉图,也不是哈密尔顿图,见图8.9所示的图.
< br>分析 (1) 中图满足要求是显然的.(2) 中构造的图G是连通的,并且各顶点度数均为偶数, 所以,都是欧拉图,但因为G中存在割点,将割点从G中删除,所得图至少有两个连通分支,这破坏了哈密尔顿图 的必要条件,所以,G不是哈密尔顿图.(3) 中构造的图中,所有顶点都排在一个圈上,所以,图中存在哈密 尔顿回路,因而为哈密尔顿图,但因图中有奇度顶点(度数为奇数的顶点),所以,不是欧拉图. 由以上讨论可知,(4) 中图既不是欧拉图,也不是哈密尔顿图.

其实,

读 者可以找许多族图,分别满足题中的要求.

8.9 请读者自己讨论.

8.10 其逆命题不真.

分析 若D是强连通的有向图,则D中任何两个顶点都是相互可达的,但并没有要求D中每个顶点的入度都等于出度. 在图8.2 所示的3个强连通的有向衅都不是欧拉图.

8.11 除 不是哈密尔顿图之外, ( )全是哈密尔顿图. (n为奇数)为欧拉图. 规定 (平凡图)既是欧拉图,又是哈密尔顿图.

分析 从哈密尔顿图的定义不难看出,n阶图G是 否为哈密尔顿图,就看是否能将G中的所有顶点排在G中的一个长为n的初级回路,即圈上. ( )中存在多个这样的生成圈(含所有顶点的图), 所以 ( )都是哈密尔顿图.

在完全图 中,各顶点的度数均为n-1,若 为欧拉图,则必有 为偶数,即n为奇数,于是,当n为奇数时, 连通且无度顶点,所以, ( 为奇数) 都是欧拉图.当n为偶数时,各顶点的度数均为奇数,当然不是欧拉图.

8.12 有割点的图也可以为欧拉图.

分析 无向图G为欧拉图当且仅当G连通且没有奇度顶点.只要 G连通且无奇度顶点(割点的度数也为偶数),G就是欧拉图.图8.8所示的两个图都有割点,但它们都是欧拉 图.

8.13 将7个人排座在圆桌周围,其排法为

分析 做无向图 ,其中,





图G为图8.10所示.图G是连通图,于是,能 否将这7个人排座在圆桌周围,使得每个人能与两边的人交谈,就转化成了图G中是否存在哈密尔顿回路(也就是 G是否为哈密尔顿图).通过观察发现G中存在哈密尔顿回路, 就是其中的一条哈密尔顿回路.












8.14 用 表示颜色 做无向图 ,其中





对于任意的 表示顶点 与别的能搭配的颜色个数,易知G是简单图,且对于任意的 ,均有 ,由定理8.9可知,G为哈密尔顿图,因而G中存在哈密尔顿回路,不妨设 为其中的一条,在这种回路上,每个顶点工表的颜色都能与它相邻顶点代表的颜色相.于是,让 与 , 与 , 与 所代表的颜色相搭配就能织出3种双色布,包含了6种颜色.

8.15 本图边数m=10.

分析 平面图(平面嵌入)的面 的次数等于包围它的边界的回路的长度 ,这里所说回路,可能是初级的,可能是简单的,也可能是复杂的,还可能由若干个回路组成.图8.1所示图中 , 的边界都是初级回路,而 的边界为复杂回路(有的边在回路中重复出现),即 ,长度为12,其中边 在其中各出现两次.

8.16 图8.11中,实线边所示的图为图8.1中图G,虚线边,实心点图为它的对偶图的顶点数 ,边数 ,面数 分别为4,10和8,于是有








< br>



分析 从图8.11还可以发现,G的每个顶点位于的一个面中,且 的每个面只含G的一个顶点,所以,这是连通平面图G是具有 个连通分支的平面图 ,则应有 .读者自己给出 一个非连通的平面图,求出它的对偶图来验证这个结论.另外,用图8.1还可以验证,对于任意的 (

中的顶点),若它处于G的面 中,则应有 .

8.17 不能与G同构.

分析 任意平面图的对偶图都是连通的,因而与都是连通图,而G是具有3个 连通分支的非连通图,连通图与非连通图显然是不能同构的.

图 8.12 中, 这线边图为图8.2中的图G,虚线边图为G的对偶图,带小杠的边组成的图是 的对偶图,显然












8.18 因为彼得森图中有长度为奇数的圈,根据定理8.1可知它不是二部图.图中每个顶点的度数均为3, 由定8.5可知它不是欧拉图.又因为它可以收缩成 ,由库拉图期基定理可知它也不是平面图.

其实,彼得森图也不是哈密尔顿图图,这里就不给出证明了.

8.19 将图8.4重画在图8.13中,并且将顶点标定.图中 为图中哈密尔顿回路,见图中粗边所示,所以,该图为哈密尔顿图.

将图中边 三条去掉,所得图为原来图的子图,它为 ,可取 ,由库拉图期基定理可知,该图不是平面图.

8.20 图8.14 所示图为图8.5所示 图的平面嵌入.











分析 该图为极大平面图.此图G中,顶点数 ,边数 若G是不是极大平面图,则应该存在不相邻的顶点 在它们之间再加一条边所得 还应该是简单平面图, 的顶点数 ,于是会有



这与定理8.16矛盾,所以,G为极大平面图.
其实, ( )阶简单平面图G为极大平面图当且仅当G的每个面的次数均为3.由图8.14可 知,G的每个面的次数均为3,所以,G为极大平面图.

8.21 答案 A,B,C,D全为②

分析 (1) 只有n为奇数时命题为真,见8.11的解答与分析.

(2) 时,命题为真,见8.11的解答与分析.

(3) 只有 都是偶数时, 中才无奇度数顶点,因而 为欧拉图,其他情况下,即 中至少有一个是奇数,这时 中必有奇度顶点,因而不是欧拉图.

(4) 只有 时, 中存在 哈密尔顿回路,因而为哈密尔顿图.

当 时,不妨设 ,并且在二部图 中, ,则 ,这与定理8.8矛盾. 所以, 时, 不是哈密尔顿图.

8.22 答案 A:②;B②;C②.

分析















图8.15中,两个实边图是同 构的,但它们的对偶力(虚边图)是不同构的.

(2) 任何平面图的对偶图都是连通图.设G是非连通的平面图,显然有

(3) 当G是非连通的平面图时, 其中 为G的连通分支数.

8.23 答案 A:④;B②;C②.

分析 根据库期基定理可知,所求的图必含有 或 同胚子图,或含可收缩成 或 的子图.由于顶点数和边数均已限定,因而由 加2条边的图可满足要求,由 增加一个顶点,一条边的图可满足要求,将所有的非同构的简单图画出来,共有4个,其中由 产生的有2个,由 产生的有2个.见图8.16所示.





第9章 习题解答



9.1 有5片树叶.

分析 设T有x个1度顶点(即树叶).则T的顶点数 的边数 由握手定理得方程.



由方程解出

所求无向树T的度数列为 1,1,1,1,1,2,2,3,3,3.由这个度数列可以画多棵非同构的无向树,图9.6给出的4

棵都具有上述度数列,且它们是非同构的.





9. 2 T中有5个3度顶点.

分析 设T中有 个3度顶点,则T中的顶点数 边数 ,由握手 定理得方程.



由方程解出x=5.

所求无向树T的度数列为 1,1,1,1,1,2,2,3,3,3.由这个度数列可以画多棵非同构的无向树,图9.6给出的4棵都具 有上述度数列,且它们是非同构的.










9.2 T中有5个3度顶点.

要析 设T中有x个3度顶点,则T中的顶点数 ,边数 ,由握手定理得方程.

.

由此解出 ,即T中有5个3度顶.T的度数列为1 ,1,1,1,1,1,1,3,3,3,3,3.由于T中只有树叶和3度顶点,因而3度顶点可依次相邻,见 图9.7所示. 还有一棵与它非同构的树,请读者自己画出.

9.3 加 条新边才能使所得图为无向树.

分析 设具有 个连通分支的森林为G,则G有 个连通分支 全为树, 加新边不能在 内部加,否则必产生回路.因而必须在不同的小树之间加新边. 每加一条新边后,所得到的森林就减少一个连通分支. 恰好加 条新边,就使得图连通且无回路,因而是树.在加边过程中,只需注意,不在同一人连通分支中加边. 下面给出一种加边方法,取 为 中顶点,加新边 ,则所得图为树,见图9.8 给出的一个特例.图中虚线边为新加的边.

9.4 不一定.

分析 n阶无向树T具有 条边,这是无向树T的必要条件,但不是充公条件.例如, 阶圈(即 个顶点的初级回路)和一个孤立点组成无向简单图具有 条边, 但它显然不是树.


< br>





9.5 非同构的无向树共有2棵,如图 9.9所 示.











分析 由度数列1,1,1,1,2,2,4不难看出,唯一的4度顶点必须与2度顶点相邻,它与1个2度顶 点相邻,还是与两个2度顶点都相邻,所得树是非同构的,再没有其他情况.因而是两棵非同构的树.
< br>9.6 有两棵非同构的生成树,见图9.10所示.










分析 图9.10 是5阶图(5个顶点的图), 5阶非同构的无向树只有3棵,理由如下. 5阶无向树中,顶点数 ,边数 ,各顶点度数之和为8,度数分配 方案有3种,分别为

①1,1,1,1,4;

②1,1,1,2,3;

③1,1,2,2.2.

每种方案只有一棵非同构的树.图9.10所示的5阶图的 非同构的生成树的度数列不能超出以上3种,也就是说,它至多有3棵非同构的生成树, 但由于图中无4度顶点,所示,不可能有度数列为①的生成树,于是该图最多有两棵非同构的生成树. 但在图9.10 中已经找出了两个非同构的生成树,其中(1)的度数列为③,(2) 的度数列为②,因而该图准确地有两棵非同构的生成树.

9.7 基本回路为:



基本回路系统为

基本割集为:



基本回路系统为 .

分析 1°注意基本回路用边的序列表示,而基本割集用边的集合表示.

2° 基本回路中,只含一条弦,其余的边全为树枝,其求法是这样的: 设弦 ,则 在生成树T中,且在T中, 之间存在唯一的路径 与 组成的回路为G中对应弦 的基

本回路.

3° 基本割集中,只含一条树枝,其余的边都是弦,其求法是这样的:设树枝 ,则 为T中桥,于是 (将 从T中支掉),产生两棵小树 和 ,则



为树枝 对应的基本割集. 显然 中另外的边全是弦. 注意,两棵小树 和 ,中很可能有平凡的树(一个顶点).


< br>







得两棵小树如图9.11中(1) 所示. G中一个端点在 中,另一个端点在 中的边为 (树枝), ,它们全是弦,于是



得两棵小树如图9.11中(2) 所示, 其中有一棵为平凡树. G中一个端点在 中,另一个端点在 中的边数除树枝 外,还有弦 所以,



产生的两棵小树如图9.11中(3) 所示 . G中一个端点在 中,另中一个端点在 中的边,除树枝 外,还有两条弦 ,所示,



产生的两棵小树如图9.11中(4) 所示. 由它产生的基本割集为

.

9.8 按Kruskal求最小生成树的算法,求出的图9.3(1)的最小生成树T为图9.12中(1) 所示, 其 .(2) 的最小生成树T为图9.12中(2)所示,其

9.9 为前缀码.

分析 在 中任何符号串都不是另外符号串的前串,因而它们都是前缀码.而在 中, 1是11,101的前缀,因而 不是前缀码. 在 中, 是 等的前缀,因而 也不是前缀码.











9.10 由图9.4 (1) 给出的2元前缀码.



由(2) 给出的3元前缀码为.



分析 是2元树产生的2元前缀码(因为码中的符号串由两个符号0,1组成),类似地, 是由3元树产生的3元前缀码(因为码中符号串由3个符号0,1,2组成).一般地,由 元树产生 元前缀码.

9.11 (1) 算式的表达式为

.

由于

.

(2) 算式的波兰符号法表达式为



(3) 算式的逆波兰符号法表达式为



9.12 答案 A:①; B②; C:④; D:⑨.

分析 对于每种情况都先求出非同构的无向树,然后求出每棵非同构的无向树派生出来的所有非同构的根树.图9.13 中,(1),(2),(3),(4)分别画出了2阶,3阶,4阶,5阶所有非同构的无向树,分别为1棵,1 棵,2棵和3棵无向树.











2阶无向树只有1棵,它有两个1度顶点,见图9.13中(1)所示,以1个顶点为树根, 1个顶点为树叶,得到1棵根树.

3阶非同的无向树也只有1棵,见图9.13中(2)所示. 它有两个1度顶点,1个2度顶点,以1度顶点为根的根树与以2度顶点为根的树显然是非同构的根树,所以2个 阶非同构的根树有两棵.

4阶非同构的无向树有两棵,见图9.13中(3)所示. 第一棵树有3片树叶,1个3度顶点, 以树叶为根的根树与以3度顶点为根的树非同构.所以,由第一棵树能生成两个非同构的根树, 见图9.14 中(1)所示. 第二棵树有两片树叶,两个2度顶点,由对称性,以树叶为根的根树与2度顶点为根的根树非同 构,见图9.14中(2) 所示. 所以,4阶非同构的根树有4棵.










5阶非同构的无向树有3棵,见图9.13中 (4)所示. 由第一棵能派生两棵非同构的根树, 由第二棵能派生4棵非同构的根树,由第三棵能派生3棵非 同构

的根树,所以,5阶非同构的根树共有9棵,请读者将它们都画出来.

9 .13 答案 A:②; B:②; C:③; D:③; E:③;F:④; G: ④; H:③.

分析 将所有频率都乘100,所得结果按从小到大顺序排列:

< br>
以以上各数为权,用Huffman算法求一棵最优树,见图9.15所示.

< br>








对照各个权可知各字母的 前缀码如下:

a——10, b——01, c——111, d——110,

e——001, f——0001,g——0000.

于是,a,b的码长为 的码长为 的码长为4.

W(T)=255(各分支点的权之和),W(T)是传输100按给定频率出现的字母所用的二进制数 字,因则传输104个按上述频率出现的字母要用 个二进制数字.

最后还应指出一点,在画最优树叶, 由于顶点位置的不同,所得缀码可能不同 ,即有些字母的码子在不同的最优树中可能不同,但一般说来码长不改变.特别是,不同的最优树,它们的权是固 定不变的.

9.14 答案 A:②; B:④

分析 用2元有序正则树表 示算式,树叶表示参加运算的数,分支点上放运算符,并将被减数(被除数)放在左子树上,所得2元树如图9. 16所示.

用前序行遍法访问此树,得波兰符号表示法为



用 后序行遍法访问此树,得逆波兰符号表示法为





-


-


-


-


-


-


-


-



本文更新与2020-11-30 08:03,由作者提供,不代表本网站立场,转载请注明出处:https://www.bjmy2z.cn/gaokao/472400.html

大学离散数学答案的相关文章