离散数学（第五版）清华大学出版社第7章习题解答
7.1 (1),(2),(3),(5)都能构成无向图的度数列,其中除(5)外又都能构成无向简单图的度数列.
分析1°非负整数列d,d ,L,d 能构成无向图的度数列当且仅当n di为
1 2n∑
i=1偶数,即d1,d2,L,dn中的奇数为偶数个.（1）,(2),(3),(5)中分别有4个,0个,4个,4 个奇数,所以,它们都能构成无向图的度数列,当然,所对应的无向图很可能是非简单图.而(4)中有 3 个奇数,因而它不能构成无向图度数列.否则就违背了握手定理的推论.
2°(5) 虽然能构成无向图的度数列,但不能构成无向简单度数列.否则,若存在无向简单图G,以1,3,3,3 为度数列,不妨设G 中顶点为v1,v2,v3,v4,且d(vi)=1,于是d(v2)=d(v3)=d(v4)=3.而v1只能与v2,v3,v4之一相邻,设v1与v2相邻,这样一来,除v2能达到3度外, v3,v4都达不到3度,这是矛盾的.
在图7.5所示的4个图中,(1) 以1为度数列,(2)以2为度数列,(3)以3为度数列,(4)以4为度数列(非简单图).
7.2 设有几简单图D以2,2,3,3为度数列,对应的顶点分别为v1,v2,v3,v4,由于d(v)=d+(v)+d_(v),所示,d+(v)?d?(v)=2?0=2,d+(v )=d(v )?d?(v )
11222=2?0=2,d+(v)=d(v)?d?(v)=3?2=1,d+(v)=d(v)?d?(v)=3?3=0
333444
81
由此可知,D 的出度列为2,2,1,0,且满足d+(v)= d?(v).请读者画出
∑i∑i
一个有向图.以2,2,3,3为度数列,且以0,0,2,3为入度列,以2,2,1,0为出度列.
7.3 D 的入度列不可能为1,1,1,1.否则,必有出度列为2,2,2,2(因为d(v)=d+(v)+d?(v)),)此时,入度列元素之和为4,不等于出度列元素之和8,这违背握手定理.类似地讨论可知,1,1,1,1也不能为D的出席列.
7.4 不能. N阶无向简单图的最大度Δ≤n?1.而这里的n个正整数彼此不同,因而这n个数不能构成无向简单图的度数列,否则所得图的最大度大于n,这与最大度应该小于等于n-1矛盾.
7.5 (1) 16个顶点. 图中边数m=16,设图中的顶点数为n.根据握手定理可知2m=32= n d(v)=2n
∑i
i=1
所以,n=16.
(2) 13个顶点.图中边数m=21,设3度顶点个数为x,由握手定理有
2m=42=3×4+3x
由此方程解出x=10.于是图中顶点数n=3+10=13.
(3) 由握手定理及各顶点度数均相同,寻找方程
2×24=nk
的非负整数解,这里不会出现n,k均为奇数的情况. 其中n为阶级,即顶点数,k为度数共可得到下面10种情况.
①个顶点,度数为48.此图一定是由一个顶点的24个环构成,当然为非简单图.
②2个顶点,每个顶点的度数均为24.这样的图有多种非同构的情况,一定为非简单图.
③3个顶点,每个顶点的度数均为16.所地应的图也都是非简单图.
④4个顶点,每个顶点的度数均为12. 所对应的图也都是非简单图.
⑤6个顶点，每个顶点的度数均为8，所对应的图也都是非简单图.
⑥个顶点,每个顶点的度数均为 6.所对应的非同构的图中有简单图,也有非简单图.
82
⑦12 个顶点,每个顶点的度数均为 4. 所对应的非同构的图中有简单图,也有非简单图.
⑧16个顶点,每个顶点的度数均为3,所对应的非同构的图中有简单图,也有非简单图.
⑨24个顶点,每个顶点的度数均为2.所对应的非同构的图中有简单图,也有非简单图.
⑩48个顶点,每个顶点的度数均为1,所对应的图是唯一的,即由24个K2构成的简单图.
分析由于n阶无向简单图G中,ΔG( )≤n?1,的以①-⑤所对应的图不可能有简单图.⑥-⑨既有简单图,也有非简单图,读者可以画出若干个非同构的图,而⑩只能为简单图.
7.6 设G为n阶图,由握手定理可知
70=2×35= n d(v)≥3n,
∑ 1
i=1
所以,
?70?
n≤=23.
?3?
??
?70?
这里, ?x?为不大于x的最大整数,例如?2?=2,?2.5?=2,=23 .
?3?
??
7.7 由于δ(G)=n?1,说明G 中任何顶点v的度数d(v)≥δ(G)=n?1,可是由于G 为简单图,因而ΔG( )≤n?1,这又使得d(v)≤n?1,于是d(v)=n?1,也就是说,G中每个顶点的度数都是n?1,因而应有ΔG( )≤n?1.于是G为(n?1)阶正则图,即G为n阶完全图Kn.
7.8 由G的补图G的定义可知,GUG为Kn,由于n为奇数,所以, Kn中各项顶点的度数n?1为偶数.对于任意的v∈V(G),应有v∈V(G),且
dG(v)_d (v)=dK (v)=n?1
Gn
83
其中dG(v)表示v在G中的度数, d (v)表示v在G中的度数.由于n?1为偶
G
数,所以, dG(v)与d (v)同为奇数或同为偶数,因而若G有r个奇度顶点,则G也
G
有r个奇度顶点.
7.9 由于D'?D,所以,m'≤m.而n阶有向简单图中,边数m≤n(n?1),所以,应有
n(n?1)=m'≤m≤n(n?1)
这就导致m=n(n?1),这说明D为n阶完全图,且D'=D.
7.10 图7.6给出了K4的18个非同构的子图,其中有11个生成子图(8-18),其中连通的有6个11,12,13,14,16,17).图7.6中,n,m分别为顶点数和边数.
7.11 K4有11个生成子图,在图7.6中,它们分别如图8-18所示.要判断它们之中哪些是自补图,首先要知道同构图的性质,设G1与G2的顶点数和边数.若G1?G2,则n1=n2且m1=m2.
(8)的补图为(14)=K4,它们的边数不同,所以,不可能同构.因而(8)与(14)
84
均不是自补图类似地,(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 不能.
分析在同构的意义下,G1,G2,G3都中K4的子图,而且都是成子图.而K4的两条边的生成子图中,只有两个是非同构的,见图7.6 中(10)与(15)所示.由鸽巢原理可知, G1,G2,G3中至少有两个是同构的,因而它们不可能彼此都非同构.
鸽巢原理m只鸽飞进n个鸽巢,其中m≥n,则至少存在一巢飞入至少[m]只
n鸽子.这里?x?表示不小于x的最小整数.例如, ?2?=2,?2.5?=3.
7.14 G是唯一的,即使G是简单图也不唯一.
85
分析由握手定理可知2m=3n,又由给的条件得联立议程组
?2m=3n
?2n?3=m.
?
解出n=6,m=9.6个顶点,9条边,每个顶点的度数都是3的图有多种非同构的情况,其中有多个非简单图(带平行边或环),有两个非同构的简单图,在图7.8中(1),(2)给出了这两个非同构的简单图.
满足条件的非同构的简单图只有图7.8
中,(1),(2)所示的图,(1)与(2)所示的图,(1)
与(2)是非同构的.
注意在(1)中不存在3个彼此相邻的顶点,
而在(2)中存在3个彼此相邻的顶点,因而(1)
图与(2)图非同构.下面分析满足条件的简单
图只有两个是非同构的.首先注意到(1)中与
(2)中图都是K6的生成子图,并且还有这样
的事实,设G1,G2都是n 阶简单图,则G1?G2当且仅当G1?G2,其中G1,G2分别为G1与G2的补图.满足要求的简单图都是6阶9条边的3正则图,因而它们的补图都为6阶6条边的2正则图(即每个顶点度数都是2).而K6的所有生成子图中,6条边2正则的非同构的图只有两个,见图7.8中(3),(4)所示的图,其中(3)为(1)的补图,(4)为(2)的补图,满足要求的非同构的简单图只有两个.
但满足要求的非同简单图有多个非同构的,读者可自己画出多个来.
7.15 将K6的顶点标定顺序,讨论v1所关联的边.由鸽巢原理(见7.13 题),与v1关联的5条边中至少有3条边颜色相同,不妨设存在3条红色边,见图7.9中(1)所示(用实线表示红色的边)并设它们关联另外3个顶点分别为v2,v4,v6.若v2,v4,v6构成的K3中还有红色边,比如边(v2,v4)为红色,则v1,v2,v4构成的K3为红色K3,见图7.9中(2)所示.若v2,v4,v6构成的K3各边都是蓝色(用虚线表示),则v2,v4,v6构成的K3为蓝色的.
86
7.16 在图7.10 所示的3个图中,(1)为强连通图,(2)为单向连通图,但不是强连通
的,(3)是弱连通的,不是单向连通的,更不是强连通的.
分析在(1)中任何两个顶点之间都有通路,即任何两个顶点都是相互可达的,因而它是强连能的.(2)中c不可达任何顶点,因而它不是强连通的,但任两个顶点存在一个顶点可达另外一个顶点,所以,它是单向可达的.(3)中a,c互相均不可达,因而它不是单向连通的,更不是强连通的.
判断有向图的连通性有下面的两个判别法.
1°有向图D是强连通的当且仅当D中存在经过每个顶点至少一次的回路.
2°有向图D是单向连通的当且仅当D中存在经过每个顶点至少一次的通路. (1) 中abcda为经过每个顶点一次的回路,所以,它是强连能的.(2)中abdc为经过每个顶点的通路,所以,它是单向连通的,但没有经过每个顶点的回路,所以,它不是强连通的.(3)中无经过每个顶点的回路,也无经过每个顶点的通路,所以,它只能是弱连通的.
7.17 G?E的连通分支一定为2,而G?V''的连通分支数是不确定的.
分析设E为连通图G的边割集,则G?E的连通分支数p(G?E)=2,不可'''
能大于2.否则,比如p(G?E)=3,则G?E由3个小图G,G'',G 组成,且E中边'
1 2 3
的两个端点分属于两个不同的小图.设E''中的边的两个端点一个在G 中,另一个1
87
在G 中,则E''?E',易知p(G?E'')=2,这与E'为边割集矛盾,所以,
2
p(G?E'')=2.
但p(G?V')不是定数,当然它大于等于2,在图7.11中,V'={u,v}为(1)的点割集, p(G?V)=2,其中'G 为(1)中图. V''={v}为(2)中图的点割集,且v为割点, p(G'?V'')=4,其中G为(2)中图.'
7.18 解此题,只要求出D的邻接矩阵的前4次幂即可.
?0 1 1 0??1 1 0 1?
1 0 0 020 1 1 0
A=??A =??
?0 1 0 1??1 0 0 1?
?0 0 0 0??0 0 0 1?
????
?1 1 1 1??1 2 1 2?
3 1 1 0 1
4 1 1 1 1
A =??A =??
?0 1 1 1??1 1 0 1?
?0 0 0 1??0 0 0 1?
????
D中长度为4的通路数为A4中元素之和,等于15,其中对角线上元素之和为3,即D中长度为3的回路数为3.v 到v 的长度为4的通路数等于a(4)=2.
3434
分析用邻接矩阵的幂求有向图D中的通路数和回路数应该注意以下几点:
1°这里所谈通路或回路是定义意义下的,不是同构意义下的.比如,不同始点(终点)的回路
2°这里的通路或回路不但有初级的、简单的，还有复杂的.例如,v1,v2,v1,v2,v1是一条长为4的复杂回路.
3°回路仍然看成是通路的特殊情况.
88
读者可利用A2,A3,求D中长度为2和3的通路和回路数.
7.19 答案A:④.
分析G中有Nk个k度顶点,有(n?Nk)个(k+1)度顶点,由握手定理可知
n d(v)=k?N +(k+1)(n?N )=2m
∑ikk
i=1
?Nk=n(k+1)?2n .
7.20 答案A:②; B:③.
分析在图7.12中,图(1)与它的补同构,再没有与图(1)非同构的自补图了,所以非同构的无向的4阶自补图只有1个.图(2)与它的补同构,图(3)与它的补也同构,而图(2)与图(3)不同构,再没有与(2),(3)非同构的自补图了,所以,非同械的5阶自补图有
7.21 答案A:④; B:③; C:④; D:①.
分析(1)中存在经过每个顶点的回路,如adcba.(2)中存在经过每个顶点.
的通路,但无回路.(3)中无经过每个顶点至少一次的通路,其实,b,d两个顶点互不可达.(4)中有经过每个顶点至少一次的通路,但无回路,aedcbd为经过每个顶点的通路.(5)中存在经过每个顶点至少一次的回路,如aedbcdba(6)中也存在经.
过每个顶点的回路,如baebdcb.由7.16 题可知,(1),(5),(6)是强连通的,(1),(2),(4),(5),(6)是单向连能的,(2),(4)是非强连通的单向连通图.注意,强连通图必为单向连通图.6 个图中,只有(3)既不是强连通的,也不是连通的,它只是弱连通图.
在(3)中,从a到b无通路,所以d,
7.22 答案A:①; B:⑥㈩C:②; D:④.
89
分析用Dijkstra标号法,将计算机结果列在表7.1中.表中第x列最后标定y/Z表示b到x的最短路径的权为y,且在b到x的最短路径上,Z邻接到x, 即x的前驱元为Z.由表7.1可知,a的前驱元为c(即a邻接到c),c的前驱元为b,所以,b到a的最短路径为bca,其权为4.类似地计论可知,b到c的最短路径为bc,其权为1.b到d 的最短路径为bcegd,其权为9.b到e 的最短路径为bce,其权为7.
表7.1
顶点a b c d e f g
k
0 7 1∞ ∞ ∞ ∞
1 4 ∞ 5 4∞
1/b
2 12 5 4∞
4/c
3 12 5 4/c11
4 12 5/c7
5 97/e
4 01 9
5 4 7
7.23 答案A:⑧; B:⑩C:③; D:③和④.
分析按求最早、最晚完成时间的公式，先求各顶点的最早完成时间，再求最晚完成时间，最后求缓冲时间。
（1）最早完成时间：
TE(v1)=0
Γ?(v )={v,v}, TE(v )=max{0+3}=3
21 22
Γ?(v )={v,v}, TE(v )=max{0+2,3+0}=3
31 33
Γ?(v )={v,v}, TE(v )=max{0+4,3+2}=5
41 34
Γ?(v )={v ,v}, TE(v )=max{3+4,3+4}=7
52 35
Γ?(v )={v ,v}, TE(v )=max{3+4,7+0}=7
63 66
90
Γ?(v )={v ,v}, TE(v)=max{5+5,10+0}=10
74 57
Γ?(v )={v,v}, TE(v)=max{7+3,10+1}=11
86 78
Γ?(v )={v ,v}, TE(v )=max{7+6,11+1}=13
95 89
（2）最晚完成时间：
TL(v9)=13
Γ+(v )={v}, TL(v )=min{13?1}=12;
898
Γ+(v )={v}, TL(v )=min{12?3}=9;
686
Γ+(v )={v}, TL(v )=min{12?1}=11;
787
Γ+(v )={v ,v},TL(v )=min{9?0,13?6}=7;
56 95
Γ+(v )={v},TL(v )=min{11?5=6;
474
Γ+(v )={v ,v ,v}, TL(v )=min{6?2.7?4.9?4=5;
34 5 63
Γ+(v )={v,v}, TL(v )=min{3?0.7?4}=3;
23 52
Γ+(v)={v ,v ,v}, TL(v)=min{3?3.3?2,6?4}=0;
12 3 41
（3）缓冲时间：
TS(v1)=TS(v2)=TS(v3)=TS(v5)=TS(v9)=0
TS(v4)=1,TS(v6)=2,TS(v7)=TS(v8)=1.
（4）关键路径有两条：v1,v2,v5,v9和v1,v2,v3,v5,v9.
91
第8 章习题解答
8.1 图8.6 中,(1)所示的图为K1,3,(2) 所示的图为K2,3,(3)所示的图为K2,2,它们分别各有不同的同构形式.
8.2 若G为零图,用一种颜色就够了,若G是非零图的二部图,用两种颜色就够了. 分析根据二部图的定义可知,n 阶零图(无边的图)是三部图(含平凡图),对n阶零图的每个顶点都用同一种颜色染色,因为无边,所以,不会出现相邻顶点染同色,因而一种颜色就够用了.
8.3 完全二部图Kr,s,中的边数m?rs.
分析设完全二部图Kr,s的顶点集为V, 则V=V1UV2,V1IV2=?,且|V1|=r,|V2|=s, Kr,s是简单图,且V1中每个顶点与V2中所有顶点相邻,而且V1中任何两个不同顶点关联的边互不相同,所以,边数m?rs.
8.4 完全二部图Kr,s中匹配数β1=min{r,s},即β1等于r,s中的小者.
分析不妨设r≤s,且二部图Kr,s中,|V1|=r,|V2|=s,由Hall定理可知,图中存在V1到的完备匹配,设M 为一个完备匹配,则V1中顶点全为M 饱和点,所以,β1=r.
8.5 能安排多种方案,使每个工人去完成一项他们各自能胜任的任务.
分析设V1={甲,乙,丙},则V1为工人集合, V2={a,b,c},则V2为任务集合.
92
令V=V1UV2,E={(x,y)|x能胜任y},得无向图G=
对应一个分配方案.图8.7 满足Hall定理中的相异性条件,所以,
存在完备匹配,又因为|V1|=V2| |=3,所以,完备匹配也为完美匹配.
其实,从图上,可以找到多个完美匹配. 取
M1={(甲,a),(乙,b),(丙,c)}
此匹配对应的方案为甲完成a,乙完成b, 丙完成c,见图中粗边所示的匹配.
M ={(甲,b),(乙,a),(丙,c)}
M2对应的分配方案为甲完成b,乙完成a,丙完成c.
请读者再找出其余的分配方案.
8.6 本题的答案太多,如果不限定画出的图为简单图,非常容易地给出 4 族图分别满足要求.
(1) n (n 为偶数,且n≥2)阶圈都是偶数个顶点,偶数条边的欧拉图.
(2) n (n 为奇数,且n≥1)阶圈都是奇数个顶点,奇数条边的欧拉图.
(3) 在(1) 中的圈上任选一个顶点,在此顶点处加一个环,所务图为奇数个顶点,偶数条边的欧拉图.
分析上面给出的4族图都是连通的,并且所有顶点的度数都是偶数,所以,都是欧拉图.并且(1),(2) 中的图都是简单图.而(3),(4)中的图都带环,因而都是非简单图. 于是,如果要求所给出的图必须是简单图,则(3),(4)中的图不满足要求.
其实,欧拉图是若干个边不重的图的并,由这种性质,同样可以得到满足(3),(4)中要求的简单欧拉图.设G1,G2,L,Gk是长度大于等于3的k个奇圈(长度为奇数的圈称为奇圈),其中k为偶数,将G1中某个顶点与G2中的某顶点重合,但边不重合, G2中某顶点与G3中某顶点重合,但边不重合,继续地,最后将Gk?1中某顶点与Gk中某顶点重合,边不重合,设最后得连通图为G,则G中有奇数个顶点,偶数条边,且所
有顶点度数均为偶数,所以,这样的一族图满足(4)的要求,其中一
93
个特例为图8.8中(1)所示.在以上各图中,若G1,G2,L,Gk中有一个偶圈,其他条件不变,构造方法同上,则所得图G 为偶数个顶点,奇数条边的简单欧拉图,满足(3)的要求,图8.8中(2)所示为一个特殊的情况.
8.7 本题的讨论类似于8.6 题,只是将所有无向圈全变成有向圈即可,请读者自己画出满足要求的一些特殊有向欧拉图.
8.8 本题的答案也是很多的,这里给出满足要求的最简单一些图案,而且全为简单图.
(1) n(n≥3)阶圈,它们都是欧拉图,又都是哈密尔顿图.
(2) 给定k(k≥2)个长度大于等于3的初级回路,即圈G1,G2,L,Gk,用8.6题方法构造的图G均为欧拉图,但都不是哈密尔顿图,图8.8给出的两个图是这里的特例.
(3)n(n≥4)阶圈中,找两个不相邻的顶点,在它们之间加一条边,所得图均为哈密尔顿图,但都不是欧拉图.
(4) 在(2)中的图中,设存在长度大于等于4的圈,比如说G1,在G1中找两个不相邻的相邻顶点,在它们之间加一条新边,然
后用8.6题方法构造图G,则G既不是欧拉图,
也不是哈密尔顿图,见图8.9所示的图.
分析(1) 中图满足要求是显然的.(2)
中构造的图G 是连通的,并且各顶点度数均为偶数,所以,都是欧拉图,但因为G 中存在割点,将割点从G中删除,所得图至少有两个连通分支,这破坏了哈密尔顿图的必要条件,所以,G 不是哈密尔顿图.(3) 中构造的图中,所有顶点都排在一个圈上,所以,图中存在哈密尔顿回路,因而为哈密尔顿图,但因图中有奇度顶点(度数为奇数的顶点),所以,不是欧拉图. 由以上讨论可知,(4) 中图既不是欧拉
94
图,也不是哈密尔顿图.
其实,读者可以找许多族图,分别满足题中的要求.
8.9 请读者自己讨论.
8.10 其逆命题不真.
分析若D是强连通的有向图,则D中任何两个顶点都是相互可达的,但并没有要求D中每个顶点的入度都等于出度. 在图8.2 所示的3个强连通的有向衅都不是欧拉图.
8.11 除K2不是哈密尔顿图之外, Kn(n≥3)全是哈密尔顿图. Kn(n 为奇数)为欧拉图. 规定K1(平凡图)既是欧拉图,又是哈密尔顿图.
分析从哈密尔顿图的定义不难看出,n阶图G是否为哈密尔顿图,就看是否能将G中的所有顶点排在G中的一个长为n的初级回路,即圈上. Kn(n≥3)中存在多个这样的生成圈(含所有顶点的图), 所以Kn(n≥3)都是哈密尔顿图.
在完全图Kn中,各顶点的度数均为n-1,若Kn为欧拉图,则必有n?1为偶数,即n 为奇数,于是,当n为奇数时, Kn连通且无度顶点,所以, Kn(n为奇数) 都是欧拉图.当n为偶数时,各顶点的度数均为奇数,当然不是欧拉图.
8.12 有割点的图也可以为欧拉图.
分析无向图G为欧拉图当且仅当G连通且没有奇度顶点.只要G连通且无奇度顶点(割点的度数也为偶数),G就是欧拉图.图8.8所示的两个图都有割点,但它们都是欧拉图.
8.13 将7个人排座在圆桌周围,其排法为abdfgeca .
分析做无向图G=
V={a,b,c,d,e,f,g}
E={(u,v)|u,v∈V且u与v有共同语言}
图G为图8.10所示.图G是连通图,于是,能否将这7个人排座在圆桌周围,使得每个人能与两边的人交谈,就转化成了图G 中是否存在哈密尔顿回路(也就是G是否为哈密尔顿图).通过观察发现G中存在哈密尔顿回路, abdfgeca就是其
95
中的一条哈密尔顿回路.
8.14 用vi表示颜色i,i=1,2,L,6.做无向图G=
V={v1,v2,v3,v4,v5,v6},
E={(u,v)|u,v∈V且u≠v,并且u与v能搭配}.
对于任意的v∈V,d(v)表示顶点v与别的能搭配的颜色个数,易知G是简单图,且对于任意的u,v∈V,均有d(u)+d(v)≥3+3=6,由定理8.9可知,G为哈密尔顿图,因而G
中存在哈密尔顿回路,不妨设vi vivivivivivi 为其中的一条,在这种回
1 2 3 4 5 6 1
路上,每个顶点工表的颜色都能与它相邻顶点代表的颜色相.于是,让vi与vi ,vi 12 3与vi ,vi与vi所代表的颜色相搭配就能织出3种双色布,包含了6种颜色.
4 56
8.15
deg(R)=4,deg(R )=1,deg(R )=3,而deg(R )=12.3 deg(R)=20=2×10,本图边
1230∑i
i=0
数m=10.
分析平面图(平面嵌入)的面Ri的次数等于包围它的边界的回路的长度,这里所说回路,可能是初级的,可能是简单的,也可能是复杂的,还可能由若干个回路组成.图8.1所示图中,R1,R2,R3的边界都是初级回路,而R0的边界为复杂回路(有的边在回路中重复出现),即e1e2e3e4e5e6e7e8e9e10e1e2e3e4,长度为12,其中边e5,e6在其中各出现两次.
8.16 图8.11中,实线边所示的图为图8.1中图G,虚线边,实心点图为它的
96
对偶图的顶点数n*,边数m*,面数r*分别为4,10和8,于是有
分析从图8.11还可以发现,G的每个顶点位于的一个面中,且的每个面只含G的一个顶点,所以,这是连通平面图G是具有k个连通分支的平面图k≥2,则应有r*=n?k+1.读者自己给出一个非连通的平面图,求出它的对偶图来验证这个结论.另外,用图8.1还可以验证,对于任意的v*(G*中的顶点),若它处于G的面R中,则应有d(v)=deg(R).*
ii
8.17 不能与G同构.
分析任意平面图的对偶图都是连通的,因而与都是连通图,而G 是具有3个连通分支的非连通图,连通图与非连通图显然是不能同构的.
图8.12 中, 这线边图为图8.2中的图G,虚线边图为G的对偶图,带小杠的
***~
边组成的图是G 的对偶图,显然G ≠G.
8.18 因为彼得森图中有长度为奇数的圈,根据定理8.1可知它不是二部图.图中每个顶点的度数均为3,由定8.5 可知它不是欧拉图.又因为它可以收缩成K5,由库拉图期基定理可知它也不是平面图.
其实,彼得森图也不是哈密尔顿图图,这里就不给出证明了.
97
8.19 将图8.4重画在图8.13中,并且将顶点标定.图中afbdcea为图中哈密尔顿回路,见图中粗边所示,所以,该图为哈密尔顿图.
将图中边(d,e),(e,f),(f,d)三条去掉,所得图为原来图的子图,它为K3,3,可取V1={a,b,c} V2={d,e,f},由库拉图期基定理可知,该图不是平面图.
8.20 图8.14 所示图为图8.5所示图的平面嵌入.
分析该图为极大平面图.此图G中,顶点数n=9,边数m=12若G是不是极.
大平面图,则应该存在不相邻的顶点u,v,在它们之间再加一条边所得G'还应该是简单平面图, G'的顶点数n'=n=6,m'=n+1=13,于是会有
m'=13>3n?6=12. '
这与定理8.16矛盾,所以,G为极大平面图.
其实,n( n≥3)阶简单平面图G为极大平面图当且仅当G的每个面的次数均为3.由图8.14可知,G的每个面的次数均为3,所以,G为极大平面图.
8.12 答案A,B,C,D全为②
分析(1) 只有n为奇数时命题为真,见8.11的解答与分析.
(2) n≠2时,命题为真,见8.11的解答与分析.
(3) 只有n,m都是偶数时,Kn,m中才无奇度数顶点,因而Kn,m为欧拉图,其他情况下,即n,m中至少有一个是奇数,这时Kn,m中必有奇度顶点,因而不是欧拉图. (4) 只有n=m时, Kn,m中存在哈密尔顿回路,因而为哈密尔顿图.
当n≠m时,不妨设n
98
图.
8.22 答案A:②;B②;C②.
分析
图8.15中,两个实边图是同构的,但它们的对偶力(虚边图)是不同构的.
(2) 任何平面图的对偶图都是连通图.设G 是非连通的平面图,显然有~ **
G≠G .
(3) 当G是非连通的平面图时,r*=n?k+1,其中k为G的连通分支数.
8.23 答案A:④;B②;C②.
分析根据库期基定理可知,所求的图必含有K5或K3,3同胚子图,或含可收缩成K5或K3,3的子图.由于顶点数和边数均已限定,因而由K3,3加2 条边的图可满足要求,由K5增加一个顶点,一条边的图可满足要求,将所有的非同构的简单图画出来,共有4个,其中由K3,3产生的有2个,由K5产生的有2个.见图8.16所示.
99
第9章习题解答
9.1 有5片树叶.
分析设T有x个1度顶点(即树叶).则T的顶点数n=3+2+x=5+x,T的边数m=n?1=4+x.由握手定理得方程.
2m=2(4+x)= n d(v)=3×3+2×2+1?x=13+x.
∑ i
i=1
由方程解出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中的顶点数n=7+x,边数m=n?1=6+x,由握手定理得方程.
2m=12+2x= n d(v)=3x+7
∑i
i=1
由方程解出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 中的顶点数n=7+x,边数m=n?1=6+x,由握手定理得方程.
100
2m=12+2x= n d(v)=3x+7.
∑ i
i=1
由此解出x=5,即T中有5个3度顶.T的度数列为
1,1,1,1,1,1,1,3,3,3,3,3.由于T中只有树叶和3度顶
点,因而3度顶点可依次相邻,见图9.7所示. 还有一棵
与它非同构的树,请读者自己画出.
9.3 加k?1条新边才能使所得图为无向树.
分析设具有k个连通分支的森林为G,则G有k个连通分支T1,T2,LTK,Ti全为树,i=1,2,L,k.加新边不能在Ti内部加,否则必产生回路.因而必须在不同的小树之间加新边. 每加一条新边后,所得到的森林就减少一个连通分支. 恰好加k?1条新边,就使得图连通且无回路,因而是树.在加边过程中,只需注意,不在同一人连通分支中加边. 下面给出一种加边方法,取vi为Ti中顶点,加新边(vi,vi+1)i=1,2,L,k?1,则所得图为树,见图9.8 给出的一个特例.图中虚线边为新加的边.
9.4 不一定.
分析n阶无向树T具有n?1条边,这是无向树T的必要条件,但不是充公条件.例如, 阶圈(即n?1个顶点的初级回路)和一个孤立点组成无向简单图具有n?1条边, 但它显然不是树.
9.5 非同构的无向树共有2棵,如图9.9所示.
101
分析由度数列1,1,1,1,2,2,4不难看出，唯一的4度顶点必须与2度顶点相邻，它与1个2度顶点相邻，还是与两个2度顶点都相邻，所得树是非同构的，再没有其他情况.因而是两棵非同构的树.
9.6 有两棵非同构的生成树,见图9.10所示.
分析图9.10 是5阶图(5个顶点的图), 5阶非同构的无向树只有3棵,理由如下. 5阶无向树中,顶点数n=5,边数m=4,各顶点度数之和为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 基本回路为:
Cc=cbad,Ce=ead,Cg =gfa,Ch =hfab .
基本回路系统为{Cc,Ce,Cg,Ch}.
基本割集为:
Sa ={a,e,c,g,h},Sb={b,c,h},
Sd ={d,e,c}Sf ={f,g,h}
基本回路系统为{Sa,Sb,Sd,Sf}.
分析1°注意基本回路用边的序列表示,而基本割集用边的集合表示.
102
2°基本回路中,只含一条弦,其余的边全为树枝,其求法是这样的: 设弦e=(vi,vj),则vi,vj在生成树T 中,且在T 中, vi,vj之间存在唯一的路径Γi,j与e=(vi,vj)组成的回路为G中对应弦e的基本回路.
3°基本割集中,只含一条树枝,其余的边都是弦,其求法是这样的:设树枝e=(vi,vj),则e为T中桥,于是T?e(将e从T中支掉),产生两棵小树T1和T2,则
S ={e'|e在G中且e的两端点分别在T和T中}''
e1 2
Se为树枝e对应的基本割集. 显然e∈Se,Se中另外的边全是弦. 注意,两棵小树T1和T2,中很可能有平凡的树(一个顶点).
T?a得两棵小树如图9.11中(1) 所示. G中一个端点在Ti中,另一个端点在T2中的边为a(树枝), e,c,g,h,它们全是弦,于是
Sa ={a,e,c,g,h}
T?b 得两棵小树如图9.11中(2) 所示, 其中有一棵为平凡树. G中一个端点在T1中,另一个端点在T2中的边数除树枝b外,还有弦c,h所以, ,
Sb ={b,c,h}
T?d产生的两棵小树如图9.11中(3) 所示. G中一个端点在T1中,另中一个端点在T2中的边,除树枝d外,还有两条弦c,e,所示,
Sd ={d,c,e}
T?f 产生的两棵小树如图9.11中(4) 所示. 由它产生的基本割集为
Sf ={f,g,h}.
103
9.8 按Kruskal求最小生成树的算法,求出的图9.3(1)的最小生成树T为图9.12 中(1) 所示, 其W(T)=7.(2) 的最小生成树T 为图9.12 中(2)所示,其W(T)=11 . 9.9 B1,B2,B4为前缀码.
分析在B1,B2,B4中任何符号串都不是另外符号串的前串,因而它们都是前缀码.而在B3中, 1是11,101的前缀,因而B3不是前缀码. 在B5中,a是aa,,ac等的前缀,因而B5也不是前缀码.
9.10 由图9.4 (1) 给出的2元前缀码.
B1={00,0100,01010,011,11}
由(2) 给出的3元前缀码为.
B2={00,01,0200,0201,0202,022,1,2}.
分析B1是2元树产生的2元前缀码(因为码中的符号串由两个符号0,1组成),类似地,B2是由3元树产生的3元前缀码(因为码中符号串由3个符号0,1,2组成).一般地,由r元树产生r元前缀码.
9.11 (1) 算式的表达式为
(((a+(b*c)*d?e)÷(f +g)+(h*i)*j.
由于*,÷优先于+,?,因而可以省去一些括号,使其成为
((a+b*c)*d?e)÷(f+g)+h*i*j.
(2) 算式的波兰符号法表达式为
+÷?*+a*bcde+fg**hij .
104
(3) 算式的逆波兰符号法表达式为
abc*+d*e?fg+÷hi*jI*+.
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棵,请读者将它们都画出来.
105
9.13 答案A:②; B:②; C:③; D:③; E:③;F:④; G: ④; H:③.
分析将所有频率都乘100,所得结果按从小到大顺序排列:
wg =5,wf =5,we=10wd, =10wc, =15,wb=20wa, =35 .
以以上各数为权,用Huffman算法求一棵最优树,见图9.15所示.
对照各个权可知各字母的前缀码如下:
a——10，b——01，c——111，d——110，
离散数学（第五版）清华大学出版社第2章习题解答 2.1 本题没有给出个体域,因而使用全总个体域. (1) 令F(x):x是鸟 G(x):x会飞翔. 命题符号化为 ?x(F(x)→G(x)). (2)令F(x):x为人. G(x):x爱吃糖 命题符号化为 ??x(F(x)→G(x)) 或者 ?x(F(x)∧?G(x)) (3)令F(x):x为人. G(x):x爱看小说. 命题符号化为 ?x(F(x)∧G(x)). (4) F(x):x为人. G(x):x爱看电视. 命题符号化为 ??x(F(x)∧?G(x)). 分析1°如果没指出要求什么样的个体域，就使用全总个休域，使用全总个体域时，往往要使用特性谓词。（1）-（4）中的F(x)都是特性谓词。 2°初学者经常犯的错误是，将类似于（1）中的命题符号化为 27 ?x(F(x)∧G(x)) 即用合取联结词取代蕴含联结词，这是万万不可的。将（1）中命题叙述得更透彻些，是说“对于宇宙间的一切事物百言，如果它是鸟，则它会飞翔。”因而符号化应该使用联结词→而不能使用∧。若使用∧，使（1）中命题变成了“宇宙间的一切事物都是鸟并且都会飞翔。”这显然改变了原命题的意义。
3°（2）与（4）中两种符号化公式是等值的，请读者正确的使用量词否定等值式，证明（2），（4）中两公式各为等值的。 2.2 (1)d (a),(b),(c)中均符号化为 ?xF(x) 其中F(x):(x+1)2=x2+2x+1,此命题在(a),(b),(c)中均为真命题。 （2）在(a),(b),(c)中均符号化为 ?xG(x) 其中G(x):x+2=0，此命题在（a）中为假命题，在(b)(c)中均为真命题。 （3）在(a),(b),(c)中均符号化为 ?xH(x) 其中H(x):5x=1.此命题在(a),(b)中均为假命题，在(c)中为真命题。 分析1°命题的真值与个体域有关。 2°有的命题在不同个体域中，符号化的形式不同，考虑命题 “人都呼吸”。 在个体域为人类集合时，应符号化为 ?xF(x) 这里，F(x):x呼吸，没有引入特性谓词。 在个体域为全总个体域时，应符号化为 ?x(F(x)→G(x)) 这里，F(x):x为人，且F(x)为特性谓词。G(x):x呼吸。 28 2．3 因题目中未给出个体域，因而应采用全总个体域。 （1）令：F(x):x是大学生，G(x):x是文科生，H(x):x是理科生，命题符号化为?x(F(x)→(G(x)∨H(x)) （2）令F(x):x是人，G(y):y是化，H(x):x喜欢，命题符号化为 ?x(F(x)∧?y(G(y)→H(x,y))) （3）令F(x):x是人，G(x):x犯错误，命题符号化为 ??x(F(x)∧?G(x)), 或另一种等值的形式为 ?x(F(x)→G(x)
离散数学习题答案 习题二及答案：（P38） 5、求下列公式的主析取范式，并求成真赋值： （2）()()p q q r ?→∧∧ 解：原式()p q q r ?∨∧∧q r ?∧()p p q r ??∨∧∧ ()()p q r p q r ??∧∧∨∧∧37m m ?∨，此即公式的主析取范式， 所以成真赋值为011，111。 6、求下列公式的主合取范式，并求成假赋值： （2）()()p q p r ∧∨?∨ 解：原式()()p p r p q r ?∨?∨∧?∨∨()p q r ??∨∨4M ?，此即公式的主合取范式， 所以成假赋值为100。 7、求下列公式的主析取范式，再用主析取范式求主合取范式： （1）()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 ?∧∧?∨∧∧∨?∧?∧∨?∧∧∨∧?∧∨∧∧ ()()()()()p q r p q r p q r p q r p q r ??∧?∧∨?∧∧∨∧?∧∨∧∧?∨∧∧ 13567m m m m m ?∨∨∨∨，此即主析取范式。 主析取范式中没出现的极小项为0m ，2m ，4m ，所以主合取范式中含有三个极大项0M ，2M ，4M ，故原式的主合取范式024M M M ?∧∧。 9、用真值表法求下面公式的主析取范式： （1）()()p q p r ∨∨?∧ 解：公式的真值表如下：
由真值表可以看出成真赋值的情况有7种，此7种成真赋值所对应的极小项的析取即为主析取范式，故主析取范式 1234567m m m m m m m ?∨∨∨∨∨∨ 习题三及答案：（P52-54） 11、填充下面推理证明中没有写出的推理规则。 前提：,,,p q q r r s p ?∨?∨→ 结论：s 证明： ① p 前提引入 ② p q ?∨ 前提引入 ③ q ①②析取三段论 ④ q r ?∨ 前提引入 ⑤ r ③④析取三段论 ⑥ r s → 前提引入 ⑦ s ⑤⑥假言推理 15、在自然推理系统P 中用附加前提法证明下面推理： （2）前提：()(),()p q r s s t u ∨→∧∨→ 结论： p u → 证明：用附加前提证明法。 ① p 附加前提引入 ② p q ∨ ①附加 ③ ()()p q r s ∨→∧ 前提引入 ④ r s ∧ ②③假言推理 ⑤ s ④化简 ⑥ s t ∨ ⑤附加 ⑦ ()s t u ∨→ 前提引入 ⑧ u ⑥⑦假言推理 故推理正确。 16、在自然推理系统P 中用归谬法证明下面推理： （1）前提： p q →?，r q ?∨，r s ∧? 结论：p ?
习题一 1.下列句子中,哪些是命题？在是命题的句子中,哪些是简单命题？哪些是真命题？哪些命题的真值现在还不知道？ （1）中国有四大发明. 答：此命题是简单命题，其真值为1. （2）5是无理数. 答：此命题是简单命题，其真值为1. （3）3是素数或4是素数. 答：是命题，但不是简单命题，其真值为1. x+< （4）235 答：不是命题. （5）你去图书馆吗？ 答：不是命题. （6）2与3是偶数. 答：是命题，但不是简单命题，其真值为0. （7）刘红与魏新是同学. 答：此命题是简单命题，其真值还不知道. （8）这朵玫瑰花多美丽呀！ 答：不是命题. （9）吸烟请到吸烟室去！ 答：不是命题. （10）圆的面积等于半径的平方乘以π. 答：此命题是简单命题，其真值为1. （11）只有6是偶数，3才能是2的倍数. 答：是命题，但不是简单命题，其真值为0. （12）8是偶数的充分必要条件是8能被3整除. 答：是命题，但不是简单命题，其真值为0. （13）2008年元旦下大雪. 答：此命题是简单命题，其真值还不知道. 2.将上题中是简单命题的命题符号化. 解:（1）p：中国有四大发明. （2）p:是无理数. （7）p:刘红与魏新是同学. （10）p:圆的面积等于半径的平方乘以π. （13）p:2008年元旦下大雪. 3.写出下列各命题的否定式,并将原命题及其否定式都符号化,最后指出各否定式的真值. （1）5是有理数. 答：否定式：5是无理数.p：5是有理数.q：5是无理数.其否定式q的真值为1.
（2）25不是无理数. 答：否定式：25是有理数. p ：25不是无理数. q ：25是有理数. 其否定式q 的真值为1. （3）2.5是自然数. 答：否定式：2.5不是自然数. p ：2.5是自然数. q ：2.5不是自然数. 其否定式q 的真值为1. （4）ln1是整数. 答：否定式：ln1不是整数. p ：ln1是整数. q ：ln1不是整数. 其否定式q 的真值为1. 4.将下列命题符号化，并指出真值. （1）2与5都是素数 答：p ：2是素数，q ：5是素数，符号化为p q ∧，其真值为1. （2）不但π是无理数，而且自然对数的底e 也是无理数. 答：p ：π是无理数，q ：自然对数的底e 是无理数，符号化为p q ∧，其真值为1. （3）虽然2是最小的素数，但2不是最小的自然数. 答：p ：2是最小的素数，q ：2是最小的自然数，符号化为p q ∧?，其真值为1. （4）3是偶素数. 答：p ：3是素数，q ：3是偶数，符号化为p q ∧，其真值为0. （5）4既不是素数，也不是偶数. 答：p ：4是素数，q ：4是偶数，符号化为p q ?∧?，其真值为0. 5.将下列命题符号化，并指出真值. （1）2或3是偶数. （2）2或4是偶数. （3）3或5是偶数. （4）3不是偶数或4不是偶数. （5）3不是素数或4不是偶数. 答: p ：2是偶数，q ：3是偶数，r :3是素数，s :4是偶数, t :5是偶数 (1) 符号化: p q ∨，其真值为1. (2) 符号化：p r ∨，其真值为1. (3) 符号化：r t ∨，其真值为0. (4) 符号化：q s ?∨?，其真值为1. (5) 符号化：r s ?∨?，其真值为0. 6.将下列命题符号化. （1）小丽只能从筐里拿一个苹果或一个梨. 答：p ：小丽从筐里拿一个苹果，q ：小丽从筐里拿一个梨，符号化为: p q ∨. （2）这学期，刘晓月只能选学英语或日语中的一门外语课. 答：p ：刘晓月选学英语，q ：刘晓月选学日语，符号化为: ()()p q p q ?∧∨∧?. 7.设p ：王冬生于1971年，q ：王冬生于1972年，说明命题“王冬生于1971年或1972年”既可以化 答:列出两种符号化的真值表：
第五章函数Function 函数在数学、应用数学等许多领域，尤其计算机科学领域有着极其重要的作用。函数的思想、概念和应用无处不在，无时不在。 它主要是研究变量之间的关系和规律。函数的划分有很多种。有线性与非线性之分、连续与离散之分。例
如， x12345… y357911… 5.1 函数 假定A，B是两个非空集合，f : A→B，称f为A到B上的函数，对每个a∈A, 有唯一的f(a)∈B, 记做b = f(a)。 函数也叫映射mappings或变换transformations（错误） a叫做函数f的自变量argument，b被称为因变量，b=f(a)叫做函数的值value，也叫a的像。 例1. A＝{1,2,3,4}, B={a,b,c,d}, ，
则f是一个函数。 也可以简单记为， f={(1,a), (2,a), (3,d), (4,c)} 另外, g={(1,a), (1,b), (2,a), (4,c)} 因为对于1来说，1∈A, 不是唯一的f(1)∈B与之相对应,f(1)=a,并且f(1)=b, 因此g就不是一个函数。 例2． f：Z→Z， f(a)= f是函数。 例3．恒等函数1A(a)=a是函数。 正如，我们在第四章里表述的，函数f : A→B，b=f(a), 是一个特殊的二元关系，我们知道，由函数f可以确定一个关系，简单地，可以表示为(a,b)∈，或 ab。关系的特征函数为 或者简记为 因此，这样一来，我们以前所讨论的有关集合或关系的运算和性质对于函数来说，就可以完全适用。 例如，f：A→B, g：A→B, 函数的复合 设f：A→B，g：B→C，是函数，则g?f：A→C，是函数。 g?f（a）＝g(f(a))
离散数学习题解答 数理逻辑习题 1. 将下列命题符号化： （1）要是明天不下雨且我有时间，那么我去步行街购物。 设p ：明天下雨 q ：我有时间 r ：我去步行街购物 r q p →∧?)( （2）如果小王和小张是一个组，那么这次英语竞赛一定取胜。 设p ：小王和小张是一个组 q ：这次英语竞赛一定取胜 q p → （3）除非天下雨，否则他不乘出租车上班。 设p ：天下雨 q ：他乘出租车上班 p q → （4）我反悔，仅当太阳从西边出来。 设p ：我反悔 q ：太阳从西边出来 q p → （5）如果()f x 在点0x 处可导，则()f x 在点0x 处可微。反之亦然。 设p ：()f x 在点0x 处可导 q ：()f x 在点0x 处可微 q p ? （6）明天既不是晴天也不是下雨天。 设p ：明天是晴天 q ：明天是雨天 q p ?∧? 4、用真值表判断下列公式的类型。 （2）r q p →?)( 公式是可满足式。
5、证明下列等值式 方法：等值演算、主范式、真值表 （2）)()())((r p q p r q p →→→?→→ ) ()()())()(()()()()()(r q p r q p r q p r p q r p q p p r p q p r p q p r p q p →→?→∨??∨?∨??∨?∨??∨?∨?∧?∨?∨?∨?∧?∨?∨∨???→→→ 6、使用恒等式证明下列各式，并写出它们的对偶公式。 （3）T p q p q ?∧∨??∨))(( T p q q p q q p q p p q p q p q p q p q ??∨?∨??∨?∨??∨?∧?∨∨??∨?∧∨?∧∨??∨)())()(())(())(( T p q p q ?∧∨??∨))((的对偶公式： F p q p q ?∨∧??∧))(( 7、证明下列蕴涵式 （1）)(q p q p →?∧ T q p q p q p q p q p q p ?∨?∨?∨??∨?∨∧??→→∧)()()()(
《离散数学》模拟试题3 一、填空题（每小题2分，共20分） 1. 已知集合A ={φ，1，2}，则A得幂集合p（A）=_____ _。 2. 设集合E ={a, b, c, d, e}, A= {a, b, c}, B = {a, d, e}, 则A∪B =___ ___， A∩B =____ __，A－B =___ ___，～A∩～B =____ ____。 3. 设A，B是两个集合，其中A= {1, 2, 3}, B= {1, 2}，则A－B =____ ___， ρ（A）－ρ（B）=_____ _ _。 4. 已知命题公式R Q P G→ ∧ ? =) (，则G的析取范式为。 5. 设P：2＋2＝4，Q：3是奇数；将命题“2＋2＝4，当且仅当3是奇数。”符号化 ，其真值为。 二、单项选择题（选择一个正确答案的代号填入括号中，每小题4分，共16分。） 1. 设A、B是两个集合，A＝{1,3,4}，B＝{1,2}，则A－B为（）. A.{1} B. {1, 3} C. {3,4} D. {1,2} 2. 下列式子中正确的有（）。 A. φ＝0 B. φ∈{φ} C. φ∈{a,b} D. φ∈φ 3. 设集合X＝{x, y}，则ρ（X）＝（）。 A. {{x},{y}} B. {φ,{x},{y}} C. {φ,{x},{y},{x, y}} D. {{x},{y},{x, y}} 4. 设集合A＝{1,2,3}，A上的关系R＝{(1,1),(2,2),(2,3),(3,3),(3,2)}， 则R不具备（）. 三、计算题（共50分） 1. （6分）设全集E＝N，有下列子集：A＝{1，2，8，10}，B＝{n|n2<50 ，n∈N}，C＝ {n|n可以被3整除，且n<20 ，n∈N}，D＝{n|2i，i<6且i、n∈N}，求下列集合：（1）A∪(C∩D) （2）A∩(B∪(C∩D)) （3）B－(A∩C) （4）(～A∩B) ∪D 2. （6分）设集合A＝{a, b, c}，A上二元关系R1，R2，R3分别为：R1＝A×A， R2 ＝{(a，a)，(b，b)}，R3 ＝{(a，a)}，试分别用 定义和矩阵运算求R1·R2 ，22R，R1·R2 ·R3 ， (R1·R2 ·R3 )－1 。 3.（6分）化简等价式（﹁P∧（﹁Q∧R））∨（Q∧R）∨（P∧R）. 4.(8分) 设集合A＝{1,2,3}，R为A上的二元关系，且 M R＝ 写出R的关系表达式，画出R的关系图并说明R的性质. 5. （10分）设公式G的真值表如下. 试叙述如何根据真值表求G的 主析取范式和主合取范式，并 写出G的主析取范式和主合取范式. 1 0 0 1 1 0 1 0 0
习题参考答案 1、设无向图G有16条边，有3个4度结点，4个3度结点，其余结点的度数均小于3，问：G中至少有几个结点。 阮允准同学提供答案: 解：设度数小于3的结点有x个，则有 3×4＋4×3＋2x≥2×16 解得：x≥4 所以度数小于3的结点至少有4个 所以G至少有11个结点 2、设无向图G有9个结点，每个结点的度数不是5就是6，证明：G中至少有5个6度结点或至少有6个5度结点。 阮允准同学答案： 证明：由题意可知：度数为5的结点数只能是0,2，4,6，8。 若度数为5的结点数为0,2，4个，则度数为6的结点数为9，7,5个结论成立。 若度数为5的结点数为6,8个，结论显然成立。 由上可知，G中至少有5个6度点或至少有6个5度点。 3、证明：简单图的最大度小于结点数。
阮同学认为题中应指定是无向简单图. 晓津证明如下：设简单图有n个结点，某结点的度为最大度，因为简单图任一结点没有平行边，而任一结点的的边必连有另一结点，则其最多有n-1条边与其他结点相连，因此其度数最多只有n-1条，小于结点数n. 4、设图G有n个结点，n+1条边，证明：G中至少有一个结点度数≥3 。阮同学给出证明如下： 证明：设G中所有结点的度数都小于3，即每个结点度数都小于等于2，则所有结点度数之和小于等于2n，所以G的边数必小于等于n，这和已知G有n+1条边相矛盾。所以结论成立。 5、试证明下图中两个图不同构。 晓津证明：同构的充要条件是两图的结点和边分别存在一一对应且保持关联关系。我们可以看出，(a)图和(b)图中都有一个三度结点，(a)图中三度结点的某条边关联着两个一度结点和一个二度结点，而(b)图中三度结点关联着两个二度结点和一个一度结点，因此可断定二图不是同构的。 6、画出所有5个结点3条边，以及5个结点7条边的简单图。 解：如下图所示：(晓津与阮同学答案一致)
离散数学习题解答 习题五（第五章 格与布尔代数） 1．设〈L ，?〉是半序集，?是L 上的整除关系。问当L 取下列集合时，〈L ，?〉是否是格。 a) L={1，2，3，4，6，12} b) L={1，2，3，4，6，8，12} c) L={1，2，3，4，5，6，8，9，10} [解] a) 〈L ，?〉是格，因为L 中任两个元素都有上、下确界。 b) 〈L ，?〉不是格。因为L 中存在着两个元素没有上确界。 例如：8 12=LUB{8，12}不存在。 c) 〈L ，?〉不是格。因为L 中存在着两个元素没有上确界。 1 6 3 1 2 4 8 63 1 2 4 1 1
倒例如：46=LUB{4，6}不存在。 2．设A ，B 是两个集合，f 是从A 到B 的映射。证明：〈S ，?〉是〈2B ，?〉的子格。其中 S={y|y=f (x)，x ∈2A } [证] 对于任何B 1∈S ，存在着A 1∈2A ，使B 1=f （A 1），由于f(A 1)={y|y ∈B ∧(x)(x ∈A 1∧f (x)=y)}?B 所以B 1∈2B ，故此S ?2B ；又B 0=f (A)∈S (因为A ∈2A )，所以S 非空； 对于任何B 1，B 2∈S ，存在着A 1，A 2∈2A ，使得B 1=f (A 1)，B 2=f (A 2)，从而 L ∪B{B 1，B 2}=B 1∪B 2=f (A 1)f (A 2) =f (A 1∪A 2) （习题三的8的1）） 由于A 1∪A 2?A ，即A 1∪A 2∈2A ，因此f (A 1∪A 2)∈S ，即上确界L ∪B{B 1，B 2}存在。 对于任何B 1，B 2∈S ，定义A 1=f –1 (B 1)={x|x ∈A ∧f (x)∈B 1}，A 2=f -1 (B 2)={x|x ∈A ∧f (x)∈B 2}，则A 1，A 2∈2A ，且显然B 1=f (A 1)，B 2=f (A 2)，于是 GLB{B 1，B 2}=B 1∩B 2=f (A 1)∩f (A 2) ?f (A 1∩A 2) （习题三的8的2）） 又若y ∈B 1∩B 2，则y ∈B ，且y ∈B 2。由于y ∈B 1=f (A 1)={y|y ∈B ∧(x)(x ∈A 1∧f (x)=y)}，于是存在着x ∈A 1，使f (x)=y ，但是f (x)=y ∈B 2。故此x ∈A 2=f -1 (B 2)={x|x ∈A ∧f(x)∈B 2}，因此x ∈A 1∩A 2，从而y=f (x)∈f (A 1∩A 2)，所以 GLB{B 1，B 2}=B 1∩B 2=f (A 1)∩f (A 2) ?f (A 1∩A 2) 9 7 31
《离散数学》试题及答案 一、选择或填空 （数理逻辑部分） 1、下列哪些公式为永真蕴含式？( ) (1)?Q=>Q→P (2)?Q=>P→Q (3)P=>P→Q (4)?P∧(P∨Q)=>?P 答：（1），（4） 2、下列公式中哪些是永真式？( ) (1)(┐P∧Q)→(Q→?R) (2)P→(Q→Q) (3)(P∧Q)→P (4)P→(P∨Q) 答：（2），（3），（4） 3、设有下列公式，请问哪几个是永真蕴涵式?( ) (1)P=>P∧Q (2) P∧Q=>P (3) P∧Q=>P∨Q (4)P∧(P→Q)=>Q (5) ?(P→Q)=>P (6) ?P∧(P∨Q)=>?P 答：（2），（3），（4），（5），（6） 4、公式?x((A(x)?B(y，x))??z C(y，z))?D(x)中，自由变元是( )，约束变元是( )。 答：x,y, x,z 5、判断下列语句是不是命题。若是，给出命题的真值。( ) (1)北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。 (3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。 (5) 前进！ (6) 给我一杯水吧！ 答：（1）是，T （2）是，F （3）不是 （4）是，T （5）不是（6）不是 6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。 答：所有人都不是大学生，有些人不会死
7、设P：我生病，Q：我去学校，则下列命题可符号化为( )。 (1) 只有在生病时，我才不去学校 (2) 若我生病，则我不去学校 (3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校答：（1）P ?（4）Q P→ ? P? Q→ ?（2）Q P? →（3）Q 8、设个体域为整数集，则下列公式的意义是( )。 (1) ?x?y(x+y=0) (2) ?y?x(x+y=0) 答：（1）对任一整数x存在整数 y满足x+y=0（2）存在整数y对任一整数x满足x+y=0 9、设全体域D是正整数集合，确定下列命题的真值： (1) ?x?y (xy=y) ( ) (2) ?x?y(x+y=y) ( ) (3) ?x?y(x+y=x) ( ) (4) ?x?y(y=2x) ( ) 答：（1） F （2） F （3）F （4）T 10、设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式?x(P(x)?Q(x))在哪个个体域中为真?( ) (1) 自然数(2) 实数 (3) 复数(4) (1)--(3)均成立 答：（1） 11、命题“2是偶数或-3是负数”的否定是（）。 答：2不是偶数且-3不是负数。 12、永真式的否定是（） (1) 永真式(2) 永假式(3) 可满足式(4) (1)--(3)均有可能 答：（2） 13、公式(?P∧Q)∨(?P∧?Q)化简为（），公式 Q→(P∨(P∧Q))可化简为（）。 答：?P ，Q→P 14、谓词公式?x(P(x)??yR(y))→Q(x)中量词?x的辖域是（）。 答：P(x)??yR(y) 15、令R(x):x是实数，Q(x):x是有理数。则命题“并非每个实数都是有理数”的符号化表示为（）。
离散数学（第五版）清华大学出版社第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是无理数，p为真命题。 （2）p:5能被2整除，p为假命题。 （6）p→ｑ。其中，p:2是素数，q：三角形有三条边。由于p与q都是真 命题，因而p→ｑ为假命题。 （7）p→ｑ，其中，p：雪是黑色的，q：太阳从东方升起。由于p为假命 题，q为真命题，因而p→ｑ为假命题。 （8）p:2000年10月1日天气晴好，今日（1999年2月13日）我们还不 知道p的真假，但p的真值是确定的（客观存在的），只是现在不知道而已。（9）p：太阳系外的星球上的生物。它的真值情况而定，是确定的。 1 （10）p：小李在宿舍里. p的真值则具体情况而定，是确定的。 （12）p∨q，其中，p:4是偶数，q:4是奇数。由于q是假命题，所以，q 为假命题，p∨q为真命题。
第5章 习题解答 5.1 A:③; B:⑥; C:⑧; D:⑩; E:⑨ 分析 S 为n 元集,那么有个元素.S 上的一个二元运算就是函数 S S ?2n .这样的函数有个.因此上的二元运算有个. S S S f →?:2n n },{b a 162 =n n 下面说明通过运算表判别二元运算性质及求特导元素的方法. 1 °交换律 若运算表中元素关于主对角线成对称分布,则该运算满足交换律. 2 °幂等律 设运算表表头元素的排列顺序为如果主对角线元,,,21n x x x 素的排列也为 则该运算满足幂等律. ,,,21n x x x 其他性质,如结合律或者涉及到两个运算表的分配律和吸收律,在运算表中没有明显的特征,只能针对所有可能的元素等来验证相关的算律是否成立. z y x ,,3 ° 幺元设运算表表头元素的排列顺序为如果元素所在的.e ,,,21n x x x i x 行和列的元素排列顺序也是则为幺元. ,,,21n x x x i x 4 ° 零元如果元素所在的行和列的元素都是,则是零元. .θi x i x i x 5 ° 幂等元.设运算表表头元素的排列顺序为如果主对角线上,,,21n x x x 第个元素恰 为那么是幂等元.易见幺元和零元都是幂等元. i },,2,1{n i x i ∈i x 6 ° 可逆元素及其逆元.设为任意元素,如果所在的行和列都有幺元,并i x i x 且这两个幺元关于主对角线成对称分布,比如说第行第列和第行第列的两i j j i 个位置,那么与互为逆元.如果所在的行和列具有共同的幺元,则幺元一j x i x i x 定在主对角线上,那么的逆元就是自己.如果所在的和地或者所在的列没i x i x i x 有幺元,那么不是可逆元素.不难看出幺元一定是可逆元素,且;而零i x e e e =-1元不是可逆元素. θ以本题为例,的运算表是对称分布的,因此,这三个运算是可交换的, 321,,f f f
离散数学第四版课后答案 第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是无理数，p为真命题。 （2）p:5能被2整除，p为假命题。 （6）p→q。其中，p:2是素数，q：三角形有三条边。由于p与q都是真 命题，因而p→q为假命题。 （7）p→q，其中，p：雪是黑色的，q：太阳从东方升起。由于p为假命
题，q为真命题，因而p→q为假命题。 （8）p:2000年10月1日天气晴好，今日（1999年2月13日）我们还不 知道p的真假，但p的真值是确定的（客观存在的），只是现在不知道而已。（9）p：太阳系外的星球上的生物。它的真值情况而定，是确定的。 1 （10）p：小李在宿舍里. p的真值则具体情况而定，是确定的。 （12）p∨q，其中，p:4是偶数，q:4是奇数。由于q是假命题，所以，q 为假命题，p∨q为真命题。 （13）p∨q，其中，p:4是偶数，q:4是奇数，由于q是假命题，所以，p∨q 为假命题。 （14）p：李明与王华是同学，真值由具体情况而定（是确定的）。 （15）p：蓝色和黄色可以调配成绿色。这是真命题。 分析命题的真值是唯一确定的，有些命题的真值我们立即可知，有些则不能马上知道，但它们的真值不会变化，是客观存在的。 1．3 令p:2+2=4,q:3+3=6,则以下命题分别符号化为 （1）p→q （2）p→?q （3）?p→q （4）?p→?q
第四章部分课后习题参考答案 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)在两个个体域中都解释为)(x ?，在（a）中为假命题，在 xF (b)中为真命题。 (2)在两个个体域中都解释为)(x ?，在（a）(b)中均为真命 xG 题。 4. 在一阶逻辑中将下列命题符号化: (1) 没有不能表示成分数的有理数. (2) 在卖菜的人不全是外地人. 解: (1)F(x): x能表示成分数 H(x): x是有理数 命题符号化为: )) F x∧ x ?? ? ) ( H ( (x (2)F(x): x是卖菜的人
H(x): x是外地人 命题符号化为: )) F ?? x x→ (x ( H ) ( 5. 在一阶逻辑将下列命题符号化: (1) 火车都比轮船快. (3) 不存在比所有火车都快的汽车. 解: (1)F(x): x是火车; G(x): x是轮船; H(x,y): x比y快 命题符号化为: )) F y x G ? y ? ∧ x→ ( ( )) ( H ) x ((y , (2) (1)F(x): x是火车; G(x): x是汽车; H(x,y): x比y快 命题符号化为: ))) x F x y G ∧ ? H ?? y→ ) ( , x ( ( ( (y ) 9.给定解释I如下: (a) 个体域D为实数集合R. (b) D中特定元素=0. (c) 特定函数(x,y)=x y,x,y D ∈. (d) 特定谓词(x,y):x=y,(x,y):x 第一章部分课后习题参考答案 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∧10. （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是无理数，则也是无理数。另外6能被2整除，6才能被4整除。” 答：p: 是无理数 1 q: 3是无理数0 r: 是无理数 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∨r1 所以公式类型为永真式 (3)P q r p∨q p∧r （p∨q）→(p∧r) 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 所以公式类型为可满足式 4.用等值演算法证明下面等值式： (2)(p→q)∧(p→r)(p→(q∧r)) (4)(p∧q)∨(p∧q)(p∨q) ∧(p∧q) 证明（2）(p→q)∧(p→r) (p∨q)∧(p∨r) p∨(q∧r)) p→(q∧r) （4）(p∧q)∨(p∧q)(p∨(p∧q)) ∧(q∨(p∧q) (p∨p)∧(p∨q)∧(q∨p) ∧(q∨q) 1∧(p∨q)∧(p∧q)∧1 (p∨q)∧(p∧q) 5.求下列公式的主析取范式与主合取范式，并求成真赋值 (1)(p→q)→(q∨p) (2)(p→q)∧q∧r (3)(p∨(q∧r))→(p∨q∨r) 解： （1）主析取范式 (p→q)→(q p) (p q)(q p) (p q)(q p) (p q)(q p)(q p)(p q)(p q) (p q)(p q)(p q) ∑(0,2,3) 主合取范式： (p→q)→(q p) (p q)(q p) 离散数学习题答案 习题一及答案：（P14-15） 14、将下列命题符号化： （5）李辛与李末是兄弟 解：设p ：李辛与李末是兄弟，则命题符号化的结果是p （6）王强与刘威都学过法语 解：设p ：王强学过法语；q ：刘威学过法语；则命题符号化的结果是 p q ∧ （9）只有天下大雨，他才乘班车上班 解：设p ：天下大雨；q ：他乘班车上班；则命题符号化的结果是q p → （11）下雪路滑，他迟到了 解：设p ：下雪；q ：路滑；r ：他迟到了；则命题符号化的结果是()p q r ∧→ 15、设p ：2+3=5. q ：大熊猫产在中国. r ：太阳从西方升起. 求下列复合命题的真值： （4）()(())p q r p q r ∧∧???∨?→ 解：p=1，q=1，r=0， ()(110)1p q r ∧∧??∧∧??， (())((11)0)(00)1p q r ?∨?→??∨?→?→? ()(())111p q r p q r ∴∧∧???∨?→??? 19、用真值表判断下列公式的类型： （2）()p p q →?→? 解：列出公式的真值表，如下所示： 20、求下列公式的成真赋值： （4）()p q q ?∨→ 解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是： ()10p q q ?∨??????00 p q ????? 所以公式的成真赋值有：01，10，11。 习题二及答案：（P38） 5、求下列公式的主析取范式，并求成真赋值： （2）()()p q q r ?→∧∧ 解：原式()p q q r ?∨∧∧q r ?∧()p p q r ??∨∧∧ ()()p q r p q r ??∧∧∨∧∧37m m ?∨，此即公式的主析取范式， 所以成真赋值为011，111。 6、求下列公式的主合取范式，并求成假赋值： （2）()()p q p r ∧∨?∨ 解：原式()()p p r p q r ?∨?∨∧?∨∨()p q r ??∨∨4M ?，此即公式的主合取范式， 所以成假赋值为100。 7、求下列公式的主析取范式，再用主析取范式求主合取范式： （1）()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 ?∧∧?∨∧∧∨?∧?∧∨?∧∧∨∧?∧∨∧∧ ()()()()()p q r p q r p q r p q r p q r ??∧?∧∨?∧∧∨∧?∧∨∧∧?∨∧∧ 13567m m m m m ?∨∨∨∨，此即主析取范式。 主析取范式中没出现的极小项为0m ，2m ，4m ，所以主合取范式中含有三个极大项0M ，2M ，4M ，故原式的主合取范式024M M M ?∧∧。 9、用真值表法求下面公式的主析取范式： 离散数学（第五版）清华大学出版社第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是无理数，p为真命题。 （2）p:5能被2整除，p为假命题。 （6）p→q。其中，p:2是素数，q：三角形有三条边。由于p与q都是真命题，因而p→q为假命题。 （7）p→q，其中，p：雪是黑色的，q：太阳从东方升起。由于p为假命可编辑范本 题，q为真命题，因而p→q为假命题。 （8）p:2000年10月1日天气晴好，今日（1999年2月13日）我们还不知道p的真假，但p的真值是确定的（客观存在的），只是现在不知道而已。 离散数学课后习题答案(左孝凌版) 1-1，1-2解： a)是命题，真值为T。 b)不是命题。 c)是命题，真值要根据具体情况确定。 d)不是命题。 e)是命题，真值为T。 f)是命题，真值为T。 g)是命题，真值为F。 h)不是命题。 i)不是命题。 （2）解： 原子命题：我爱北京天安门。 复合命题：如果不是练健美操，我就出外旅游拉。 （3）解： a)(┓P ∧R)→Q b)Q→R c)┓P d)P→┓Q （4）解： a)设Q:我将去参加舞会。R:我有时间。P:天下雨。 Q (R∧┓P):我将去参加舞会当且仅当我有时间和天不下雨。 b)设R:我在看电视。Q:我在吃苹果。 R∧Q:我在看电视边吃苹果。 c) 设Q:一个数是奇数。R:一个数不能被2除。 （Q→R）∧(R→Q):一个数是奇数，则它不能被2整除并且一个数不能被2整除，则它是奇数。 (5) 解： a)设P：王强身体很好。Q：王强成绩很好。P∧Q b)设P：小李看书。Q：小李听音乐。P∧Q c)设P：气候很好。Q：气候很热。P∨Q d)设P： a和b是偶数。Q：a+b是偶数。P→Q e)设P：四边形ABCD是平行四边形。Q ：四边形ABCD的对边平行。P Q f)设P：语法错误。Q：程序错误。R：停机。（P∨ Q）→ R (6) 解： a)P:天气炎热。Q:正在下雨。 P∧Q b)P:天气炎热。R:湿度较低。 P∧R c)R:天正在下雨。S:湿度很高。 R∨S d)A:刘英上山。B:李进上山。 A∧B e)M:老王是革新者。N:小李是革新者。 M∨N f)L:你看电影。M:我看电影。┓L→┓M g)P:我不看电视。Q:我不外出。 R:我在睡觉。 P∧Q∧R h)P:控制台打字机作输入设备。Q:控制台打字机作输出设备。P∧Q 1-3 （1）解： 离散数学习题详细答案 ————————————————————————————————作者：————————————————————————————————日期： 离散数学习题答案 习题一及答案：（P14-15） 14、将下列命题符号化： （5）李辛与李末是兄弟 解：设p ：李辛与李末是兄弟，则命题符号化的结果是p （6）王强与刘威都学过法语 解：设p ：王强学过法语；q ：刘威学过法语；则命题符号化的结果是 p q ∧ （9）只有天下大雨，他才乘班车上班 解：设p ：天下大雨；q ：他乘班车上班；则命题符号化的结果是q p → （11）下雪路滑，他迟到了 解：设p ：下雪；q ：路滑；r ：他迟到了；则命题符号化的结果是()p q r ∧→ 15、设p ：2+3=5. q ：大熊猫产在中国. r ：太阳从西方升起. 求下列复合命题的真值： （4）()(())p q r p q r ∧∧???∨?→ 解：p=1，q=1，r=0， ()(110)1p q r ∧∧??∧∧??， (())((11)0)(00)1p q r ?∨?→??∨?→?→? ()(())111p q r p q r ∴∧∧???∨?→??? 19、用真值表判断下列公式的类型： （2）()p p q →?→? 解：列出公式的真值表，如下所示： p q p ? q ? ()p p →? ()p p q →?→? 0 0 1 1 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 1 0 0 0 1 由真值表可以看出公式有3个成真赋值，故公式是非重言式的可满足式。 20、求下列公式的成真赋值：离散数学第一章部分课后习题参考答案
最新离散数学习题答案
离散数学(第五版)清华大学出版社第
离散数学课后习题答案(左孝凌版)
离散数学习题详细答案
相关主题
文本预览