&>&&>&离散数学答案-(1,2,7章)陈志奎
离散数学答案-(1,2,7章)陈志奎 投稿：武極楶
第1章 命题逻辑P7 习题1. 给出下列命题的否定命题： （1）大连的每条街道都临海。 否命题：不是大连的每条街道都临海。 （2）每一个素数都是奇数。否命题： 并非每一个素数都是奇数。 2. 对下述命题用中文写出语句： （1）(?P?R)?Q如果非P…
必修1数学试卷本试题分第Ⅰ卷（选择题）和第Ⅱ卷（非选择题）两部分．共150分，考试时间120分钟．第Ⅰ卷（选择题，共50分） 一、选择题（本大题共10小题，每小题5分，在每小题给出的4个答案中，只有一个是符合题目要求的）各题答案必须答在答题卡上。1、…
强基础，健体制，春风化雨创党建——XXX社区党建“三有一化”工作情况汇报 近年来，XXXXX认真按照“三有一化”（有人管事、有钱办事、有场所议事，构建区域化党建新格局）标准大力推进社区建设，社区居委会的办公条件明显改观，社区工作人员素质明显提高，各项…
第1章 命题逻辑
1. 给出下列命题的否定命题：
（1）大连的每条街道都临海。
否命题：不是大连的每条街道都临海。 （2）每一个素数都是奇数。
否命题： 并非每一个素数都是奇数。 2. 对下述命题用中文写出语句： （1）(?P?R)?Q
如果非P与R，那么Q。
3. 给出命题P?Q，我们把Q?P、?P??Q、?Q??P分别称为命题P?Q的逆命题、反命题、逆反命题。
（1）如果天不下雨，我将去公园。
解：逆命题：如果我去公园，则天不下雨；
反命题：如果天下雨，则我不去公园；
逆反命题：如果我不去公园，则天下雨了。 （2）仅当你去我才逗留。
解：（此题注意：p仅当q翻译成p?q）
逆命题：如果你去，那么我逗留。
反命题：如果我不逗留，那么你没去。
逆反命题：如果你没去，那么我不逗留。 （3）如果n是大于2的正整数，那么方程x
解：逆命题：如果方程x
?yn?zn无整数解。
?yn?zn无整数解，那么n是大于2的正整数。
反命题：如果n不是大于2的正整数，那么方程x
逆反命题：如果方程x
?yn?zn有整数解。
?yn?zn有整数解，那么n不是大于2的正整数。
（4）如果我不获得更多的帮助，那么我不能完成这项任务。
解：逆命题：如果我不完成任务，那么我不获得更多的帮助。
反命题：如果我获得了更多的帮助，那么我能完成任务。
逆反命题：如果我能完成任务，那么我获得了更多的帮助。 4. 给P和Q指派真值T，给R和S指派真值F，求出下列命题的真值。 （1）(?(P?Q??R)?((Q??P)?(R??S)))
=(?(T?T??F)?((T??T)?(F??F))) =?T?(F?T) =T?F =T
（2）Q?(P?Q)?P
=T?(T?T)?T =T?T?T =T?T =T
（3）(P?(Q?(R??P)))?(Q??S)
=(T?(T?(F??T)))?(T??F) =(T?(T?F))?T =T?T =T
（4）(P?R)?(?Q?S)
=(T?F)?(?T?F) =F?(F?F)
5. 构成下来公式的真值表： （1）Q?(P?Q)?P
（2）?(P?Q?R)?(P?Q)?(P?R)
（3）(P?Q?Q?P)?P??R
（4）?(P?P??Q?R)?Q??R
6. 使用真值表证明：如果P?Q为T，那么P?Q和Q?P都是T，反之亦然。
由上表可知：当P?Q为T时，P?Q和Q?P都是T；P?Q和Q?P为T时，
P?Q为T。故命题得证。
7. 使用真值表证明：对于P和Q的所有值，P?Q与?P?Q有同样的真值。
8. 一个有两个运算对象的逻辑运算符，如果颠倒其运算对象的次序，产生一逻辑等价命题，则称此逻辑运算符是可交换的。
（1）确定所给出的逻辑运算符哪些是可交换的：?，?，?，?。 （2）用真值表证明你的判断。 解：（1）?，?，?是可交换的。
9.设?是具有两个运算对象的逻辑运算符，如果(x?y)?z和x?(y?z)逻辑等价，那么运算符?是可结合的。
（1）确定逻辑运算符?，?，?，?哪些是可结合的？ （2）用真值表证明你的判断。 解：（1）?,?,?是可结合的。
10. 令P表示命题“苹果是添的”，Q表示命题“苹果是红的”，R表示命题“我买苹果”。试将下列命题符号化：
（1）如果苹果甜而红，那么我买苹果。 （2）苹果不是甜的。
（3）我没买苹果，因为苹果不红也不甜。 解：（1）P?Q?R （2）?P
（3）?R??P??Q
1. 指出下面命题公式哪些是重言式、永假式或可满足式。 解：
（1）重言式
（2）永假式
（3）重言式
（4）重言式
?(P?Q)?(?P??Q)?(?P??Q)?(?P??Q)?T
（5）重言式
?(P?Q)?(?P??Q)?(?P??Q)?(?P??Q)?T
（6）重言式
(P?Q)?(?Q??P) =(?P?Q)?(Q??P)?T
（7）重言式
((P?Q)?(Q?P))?(P?Q)
=(P?Q)?(P?Q)?T
（8）重言式
P?(Q?R)?(P?Q?P?R)
=((P?Q)?(P?R))?(P?Q?P?R) =(P?Q?P?R)?(P?Q?P?R)
=T （9）重言式
P??P?Q =F?Q?T
（10）可满足式
=?(P??Q)?Q??P?Q?Q，当Q为真时公式为真，Q为假时公式为假。故为可
满足式。 （11）重言式
P?P?Q??P?P?Q?T
（12）重言式
P?Q?P??(P?Q)?P??P??Q?P?T
（13）可满足式
(P?Q?P)?(P?Q)的真值表如下：
（14）可满足式
((P?Q)?(R?S))?((P?R)?(Q?S))
=(?P?Q??R?S)?(?P??R?Q?S)
=((?P??R)?(Q?S))?((?P??R)?(Q?S))
当Q或S有一个为真时公式为真；当Q和S均为假时，若P和R真值相同时，公式
为真；真值不同时，公式为假。故公式是可满足式。
2. 写出与下面给出的公式等价并且仅含有联接词?与?的最简公式。 （1）?(P?(Q?(R?P)))
??((P?(Q?(R?P)))?((Q?(R?P))?P))??((?P??Q?R?P)?((?Q?R?P)?P))??(T?(Q??R??P?P))??(Q??R??P?P)??P??(?P?Q??R)
（2）((P?Q)?R)?(P?R)
?(?(P?Q)?R)?(P?R)??(?(P?Q)?R)?(P?R)?((P?Q)??R)?P?R?(P?Q?P)?(?R?P)?R?((P?Q)?(?R?P))?R?(P?Q?R)?(?R?P?R)?(P?Q?R)??(?P??Q??R)
（3）P?Q??R
??(?P??Q?R)
（4）P?(?Q?R?P)
?P?(?(?Q?R)?P)?P?(Q??R?P)?P?Q??R??(?P??Q?R)
（5）P?(Q?P)
?P?(?Q?P)??P?(?Q?P) ?T
3. 写出与下面的公式等价并且仅含联结词?和?的最简公式。
（1）(P?Q)??P
（2）(P?(Q??Q))??P?Q
?(P?T)??P?Q?T??P?Q??P?Q??(P??Q)
（3）?P??Q?(?R?P)
??P??Q?(R?P)
?(?P??Q?R)?(?P??Q?P)?(?P??Q?R)?F??P??Q?R??(P?Q??R)
4. 使用常用恒等式证明下列各式，并给出下列各式的对偶式。 （1）?(?P??Q)??(?P?Q)?P 证明：
?(?P??Q)??(?P?Q)?(P?Q)?(P??Q)
对偶式：?(?P??Q)??(?P?Q)?P
（2）(P??Q)?(P?Q)?(?P??Q)??(?P?Q) 证明：
(P??Q)?(P?Q)?(?P??Q)?(P?(?Q?Q))?(?P??Q)?P?(?P??Q)?(P??P)?(P??Q)?(P??Q)??(?P?Q)
对偶式：(P??Q)?(P?Q)?(?P??Q)??(?P?Q)
（3）Q??((?P?Q)?P)?T 证明：
Q??((?P?Q)?P)?Q?(?(?P?Q)??P)?Q?(P??Q)??P?(P??Q)??(P??Q)?T
对偶式：Q??((?P?Q)?P)?F 5. 试证明下列合式公式是永真式。 （1）((P?Q)?P)?T 证明：
((P?Q)?P)??(P?Q)?P??P??Q?P?T
（2）?(?(P?Q)??P)?F 证明：
?(?(P?Q)??P)??((P?Q)??P)??(P?Q)?P??P??Q?P?F
（3）(Q?P)?(?P?Q)?P 证明：
(Q?P)?(?P?Q)?(?Q?P)?(P?Q)?P?(?Q?Q)?P?F?P
（4）(P??P)?(?P?P)?F 证明：
(P??P)?(?P?P)?(?P??P)?(P?P)??P?P?F
6. 证明下列蕴含式。 （1）P?Q?P?Q 证明：
(P?Q)?(P?Q)??(P?Q)?(?P?Q)??P??Q??P?Q ??P??Q?Q?T
（2）P?(Q?R)?(P?Q)?(P?R) 证明：
(P?(Q?R))?((P?Q)?(P?R))?(?P?(?Q?R))?(?(?P?Q)?(?P?R))?(?P??Q?R)?((P??Q)??P?R)?(?P??Q?R)?(?P??Q?R)?T
（3）P?Q?P?P?Q 证明：
(P?Q)?(P?P?Q)?(P?Q)?(?P?(P?Q))?(P?Q)?((?P?P)?(?P?Q))?(P?Q)?(?P?Q)?(P?Q)?(P?Q)?T
（4）(P?Q)?Q?P?Q 证明：
((P?Q)?Q)?(P?Q)?(?(?P?Q)?Q)?(P?Q)?((P??Q)?Q)?(P?Q)?((P?Q)?(?Q?Q))?(P?Q)?(P?Q)?(P?Q)?T
（5）(P??P?Q)?(P??P?R)?Q?R 证明：
((P??P?Q)?(P??P?R))?(Q?R)?((T?Q)?(T?R))?(Q?R)?((F?Q)?(F?R))?(Q?R)?(Q?R)?(Q?R)?T
（6）(Q?P??P)?(R?P??P)?R?Q 证明：
((Q?P??P)?(R?P??P))?(R?Q)?((Q?F)?(R?F))?(R?Q)?((?Q?F)?(?R?F))?(R?Q)?(?Q??R)?(R?Q)?(R?Q)?(R?Q)?T
7. 对一个重言式使用代入规则后仍为一个重言式，对一个可满足式和一个矛盾式，使用代入规则后，结果如何？对重言式、可满足式和矛盾式，使用替换规则后，结果如何？ 解：对于代入规则：
（1）如果是可满足式，使用代入规则后可能是重言式、可满足式或矛盾式。如：可满足式P?Q，将Q分别替换为?P，R分别得到重言式P??P和可满足式P?R，对于可满足式P?Q，将Q替换为?P得到矛盾式P??P。
（2）如果是矛盾式，使用代入规则后仍然是矛盾式。设P是矛盾式，则?P是重言式。而对于重言式使用代入规则后仍为重言式，即?P?是重言式，故P?是矛盾式。
对于替换规则：由于替换规则是一种对子公式逻辑上等价的替换，故对于重言式、可满足式和矛盾式使用替换规则后其真值不变。 8. 求出下列各式的代入实例。
（1）(((P?Q)?P)?P)；用P?Q代P，用((P?Q)?P)代Q。 解：((((P?Q)?((P?Q)?P))?(P?Q))?(P?Q)) （2）((P?Q)?(Q?P))；用Q代P，用?P代Q 解：((Q??P)?(?P?Q))
1.求下列各式的主合取范式。
（1）(P?Q?R)?(?P?Q?R)?(?P??Q??R)
?((P?(Q?R))?(?P?(Q?R)))?(?P??Q??R)?((P??P)?(Q?R))?(?P??Q??R)?(Q?R)?(?P??Q??R)
?(?P?Q)?(Q??R)?(?P?R)?(?Q?R)
?(?P?Q??R)?(?P?Q?R)?(P?Q??R)?(?P??Q?R)?(P??Q?R)??(1,2,4,5,6)
（2）(P?Q)?(?P?Q)?(P??Q)
?((P??P)?Q)?(P??Q)?Q?(P??Q)?(P?Q)?(Q??Q)?P?Q??(0)
（3）(P?Q)?(?P?Q?R)
?(P??P)?(P?Q)?(P?R)?(?P?Q)?(Q?Q)?(Q?R)?(P?Q)?(P?R)?(?P?Q)?Q?(Q?R)
?(P?Q?R)?(P?Q??R)?(P??Q?R)?(?P?Q?R)?(?P?Q??R)??(0,1,2,4,5)
2.求下列公式的主析取范式和主合取范式： （1）(?P??Q)?(P??Q) 合取范式：
?(P??Q)?((P??Q)?(?Q?P))??(P??Q)?((P??Q)?(?Q?P))??(P??Q)?(?Q?P)??(?P??Q)?(P?Q)?(P?Q)?P?Q?P?Q??(0)
析取范式：?(1,2,3)
（2）P?(?P?(Q?(?Q?R))) 合取范式：
?P?(P?(Q?(Q?R)))?P?Q?R??(0)
析取范式：?(1,2,3)
（3）(P?(Q?R))?(?P?(?Q??R)) 合取范式：
?(?P?(Q?R))?(P?(?Q??R))?(?P?Q)?(?P?R)?(P??Q)?(P??R)
?(?P?Q?R)?(?P?Q??R)?(?P??Q?R)?(P??Q?R)?(P??Q??R)?(P?Q??R)??(1,2,3,4,5,6)
析取范式：?(0,7)
（4）(P??Q?S)?(?P?Q?R) 析取范式：
?(P??Q?R?S)?(P??Q??R?S)?(?P?Q?R?S)?(?P?Q?R??S)??(6,7,9,11)
合取范式：?(0,1,2,3,4,5,8,10,12,13,14,15)
1.试用真值表法证明：A?E不是A?B,B?(C?D),C?(A?E)和A?E的有效结论。
解：构造真值表如下：
第6，31行前提取值均为1时，结论为0。故命题得证。
2.H1，H2和H3是前提。在下列情况下，试确定结论C是否有效（可以使用真值表法证明。） （1）H1:P?Q
证明：真值表如下：
（2）H1:?P?Q
第1，2，4行当前提取值为1时，结论都为1。故结论C是有效的。
H2:?(Q??R) H3:?R
C:?P 证明： {1}
（1） （2） （3）
T规则，（1），E11 P规则
{1，3} {5}
（4） （5）
T规则，（2），（3），I9 P规则
T规则，（4），（5），E11
{1，3，5}（6）
结论C是有效结论。 （3）H1:P?(Q?P)
（4）H1:P?Q
C:P?R 证明： {1}
{1，2} {4}
（2） （3） （4） （5） （6）
P规则（附加前提） P规则
T规则，（1），（2），I10 P规则
T规则，（3），（4），I10 （1），（5） CP规则，
{1，2，4} {1，2，4}
3.不构成真值表证明：A?C不是A?(B?C)、B?(?A??C)、C?(A??B)和B的有效结论。
证明：（1）
T规则，(1)(2)
T规则,(1)(4)
(A?C)?(?A??C)
T规则(6)(7)
因此，?(A?C)是题目的有效结论，A?C不是。
4.使用推理的方法证明：L?M是P?Q?R和(Q?R)?(L?M)的有效结论。 证明： {1}
（1） （2） （3） （4） （5） （6） （7） （8） （9）
T规则，（1），I2 T规则，（2），I4 T规则，（3），E27 T规则，（1），I2 T规则，（5），I4 T规则，（6），E27 T规则，（4），（7），E26
(Q?R)?(L?M) P规则
T规则，（8），（9），I10
5.不构成真值表证明下列命题公式不能同时全为真。 （1）P?Q，Q?R，?R?S，?P?S，?S 证明：
{1，2} {4}
（1） （2） （3） （4） （5） （6） （7） （8）
P规则 P规则
T规则，（1），（2），I11 P规则
T规则，（3），（4），I10 P规则
T规则，（5），（6），I10 P规则
{1，2，4} {6}
{1，2，4，6}
(1，2，4，6，8) （9）
T规则，（7），（8），I9
推出结论与前提矛盾，因此命题公式不能同时为真。
（2）R?M，?R?S，?M，?S 证明： {1}
{1，2} {4}
（3） （4） （5）
T规则，（1），（2），I9 P规则
T规则，（3），（4），I9
推出的结论与命题公式?S矛盾，因此命题公式不能同时为真。
6. H1，H2和H3是前提，根据推理规则断定，在下列情况下C是否是有效结论。 （1）H1:P?Q
H2:P?R H3:Q?R
证明： {1}
{1，2} {4}
（1） （2） （3） （4） （5） （6） （7） （8）
P规则（假设前提） P规则
T规则，（1），（2），I11 P规则
T规则，（3），（4），I9 P规则
T规则，（5），（6），I10 T规则，（1），（7），I16 F规则，（1），（8）
{1，2，4} {6}
{1，2，4，6}
{1，2，4，6}
{1，2，4，6}
因此C是有效结论。 （2）H1:P?(Q?R)
证明：因为P?(Q?R)??P??Q?R，再由前提H2:R，得到?P、?Q的值任意，即P、Q的值任意。因此C不是有效结论。 7.证明下列结论的有效性。
（1）?(P??Q)，?Q?R，?R??P 证明：（1）
（2） （3） （4） （5） （6）
P规则 P规则
T规则，（1），（2），I9 P规则
T规则，（4），E11 T规则，（3），（5），I9
（2）(P?Q)?R，?R??S，?S??P??Q 证明：（1）
P规则 P规则
T规则（1）（2） P规则
T规则（3）（4） T规则（5）
（3）(P?Q)?R，R?S，Q?T?P
由R?S得R为真，再由(P?Q)?R得(P?Q)真假任意，故无法推出P一定为真的结论。（题目有问题）
8.导出下列结论（如果需要，就是用规则CP） （1）?P?Q,?Q?R,R?S?P?S
证明： （1）
P规则（假设前提）
T规则（1）（2）
T规则（3）（4）
T规则（5）（6）
CP规则（1）（7） （2）P?Q?P?(P?Q)
证明： （1）
P规则（假设前提）
T规则（1）（2）
T规则（1）（3）
CP规则（1）（4） （3）(P?Q)?R?(P?Q)?R
证明： （1）
P规则（假设前提）
T规则（1）
T规则（1）
T规则（2）（3）
T规则（4）（5）
CP规则（1）（6） 9.证明下列各式的有效性（如果需要，就使用间接证明法）。 （1）(R??Q),R?S,S??Q,P?Q??P
证明： （1）
P规则（假设前提）
T规则（1）
T规则（2）（3）
T规则（4）（5）
T规则（6）（7）
T规则（8）（9）
（11） Q??Q
T规则（4）（10）
F规则（1）（11） （2）S??Q,R?S,?R,P?Q??P
证明： （1）
P规则（假设前提）
T规则（1）
T规则（2）（3）
T规则（4）（5）
T规则（6）（7）
（10） R??R
T规则（8）（9）
F规则（1）（10） （3）?(P?Q)??(R?S),((Q?P)??R),R?P?Q 证明： （1）
T规则（1）（2）
T规则（1）
?(P?Q)??(R?S )
T规则（4）（5）
T规则（6）
(P?Q)?(Q?P )
T规则（3）（7）
T规则（8）
1.证明下列各式。
（1）(?x)(?A(x)?B(x))，(?x)?B(x)?(?x)A(x) 证明： （1）
（2） （3） （4） （5） （6）
(?x)(?A(x)?B(x))
?A(a)?B(a)
P US，（1） P US，（3） T，（2），（4）， EG，（5）
（2）(?x)A(x)?(?x)B(x)?(?x)(A(x)?B(x))
证明： （1）
?(?x)(A(x)?B(x
P（假设前提）
(?x)(?A(x(?)Bx(
(?x)(A(x?)?B(x
T ??(x?)B (x
(?x)?B(x )
(?x)A(x) x
T（5）（7）
?B(a)?B(a )
T（9）（10）
(?x)(A(x?)
（11） B(x
（3）(?x)(A(x)?B(x))，(?x)(C(x)??B(x))?(?x)(C(x)??A(x)) 证明： （1）
?(?x)(C(x)??A(x))
P（假设前提）
（2） （3） （4） （5） （6） （7） （8） （9）
(?x)?(?C(x)??A(x))
T，（1） US，（2） T，（3） T，（3） P US，（6） T，（5），（7） P US，（8） T，（4），（10） T，（8），（11）
(?x)(A(x)?B(x))
A(a)?B(a) B(a)
(?x)(C(x)??B(x))
（10） C(a)??B(a)
（11） ?B(a)
（12） B(a)??B(a)
（4）(?x)(A(x)?B(x)),(?x)(B(x)??C(x)),(?x)C(x)?(?x)A(x)
证明： （1）
(?x)(B(x)??C(x))
B(x)??C(x )
T（2）（4）
(?x)(A(x?)B(x
A(x)?B(x )
T（5）（7）
UG（8） 2.用CP规则证明下列各式。
（1）(?x)(P(x)?Q(x))?(?x)P(x)?(?x)Q(x)
证明： （1）
P（假设前提）
(?x)(P(x?)Q(x
P(x)?Q(x )
T（2）（4）
CP（1）（6） ??(x)Q (x（2）(?x)(P(x)?Q(x))?(?x)P(x)?(?x)Q(x)
证明：由于(?x)P(x)?(?x)Q(x)??(?x)(?Q(x))?(?x)P(x)
?(?x)(?Q(x))?(?x)P(x)
因此，原题等价于证明(?x)(P(x)?Q(x))?(?x)(?Q(x))?(?x)P(x)
(?x)?(Q(x ) )
P（假设前提）
(?x)(P(x?)Q(x
P(x)?Q(x )
T（2）（4）
CP（1）（6） ?Q(x)?)?(xP) x3.将下列命题符号化并推证其结论。
（1）所有的有理数是实数，某些有理数是整数，因此某些实数是整数。 解：首先定义如下谓词：
P(x):x是有理数 R(x):x是实数 I(x):x是整数
于是问题符号化为：
(?x)(P(x)?R(x)),(?x)(P(x)?I(x))?(?x)(R(x)?I(x))
推理如下：
(?x)(P(x?)I(x
P(a)?I(a )
ES（1） (?x)(P(x?)R(x
P P(a)?R(a )
US（3） P(a)
T（2） R(a)
T（4）（5）
R(a)?I(a )
T（6）（7） (?x)(R(x?)I(x
（2）任何人如果他喜欢步行，他就不喜欢乘汽车，每一个人或者喜欢乘汽车或者喜欢骑自
行车，有的人不爱骑自行车，因而有的人不爱步行。 解：首先定义如下谓词：
P(x):x是人 F(x):x喜欢步行 C(x):x喜欢乘汽车 B(x):x喜欢骑自行车
于是问题符号化为：
(?x)(P(x)?F(x)??C(x)),(?x)(P(x)?C(x)?B(x)),(?x)(P(x)??B(x))?(?x)(P(x)??F(x))
推理如下：
(?x)(P(x?)?B(x
P P(a)??B(a )
ES（1） P(a)
?B(a)(?x)(P(x?)C(x?)B(x
P P(a)?C(a?)
（6） C(a)?B(a )
T（3）（7） C(a)
(?x)(P(x?)F(x?)?C(x
P P(a)?F(a)??C( a )
US（9） ?(P(a)?F(a)
T（8）（10） ?P(a)??F(a )
T（11） ?F(a)
T（3）（12） P(a)??F(a )
T（3）（13） (?x)(P(x?)?F(x
（3）每个科学工作者都是刻苦钻研的，每个刻苦钻研而且聪明的科学工作者在他的事业中
都将获得成功。华为是科学工作者并且他是聪明的，所以，华为在他的事业中将获得成功。 解：首先定义如下谓词：
P(x):x是科学工作者 Q(x):x是刻苦钻研的 R(x):x是聪明的
S(x):x在他的事业中将获得成功
定义个体a：华为 于是命题符号化为：
(?x)(P(x)?Q(x)),(?x)(P(x)?Q(x)?R(x)?S(x)),P(a)?R(a)?S(a)
推理如下：
(?x)(P(x?)Q(x
P P(a)?Q(a )
P(a)?R(a)P(a)
T（3） R(a)
（4） Q(a)
(?x)(P(x?)Q(x?)R(x?)P(a)?Q(a)?R(a?)P(a)?Q(a?)
T（3）（6）
T（8）（9）
（4）每位资深名士或是中科院院士或是国务院参事，所有的资深名士都是政协委员。张伟
是资深名士，但他不是中科院院士。因此，有的政协委员是国务院参事。 解：首先定义如下谓词：
P(x):x是资深名士 Q(x):x是中科院院士 R(x):x是国务院参事 S(x):x是政协委员
定义个体a：张伟 于是命题符号化为：
(?x)(P(x)?Q(x)?R(x)),(?x)(P(x)?S(x)),P(a)??Q(a)?(?x)(S(x)?R(x))
推理如下：
P(a)??Q(a )
T（1） ?Q(a)
T（1） (?x)(P(x?)S(x
P(a)?S(a )
US（4） S(a)
T（2）（5）
(?x)(P(x?)Q(x?)R(x)P(a)?Q(a?)
（8） Q(a)?R(a )
T（3）（9） S(a)?R(a )
T（6）（10） (?x)(S(x?)R(x
（5）每一个自然数不是奇数就是偶数，自然数是偶数当且仅当它能被2整除。并不是所有
的自然数都能被2所整除。因此，有的自然数是奇数。 解：首先定义如下谓词：
N(x):x是自然数
Q(x):x是奇数 O(x):x是偶数 P(x):x能被2整除
于是命题符号化为：
(?x)(N(x)?(Q(x)?O(x))),(?x)(N(x)?(O(x)?P(x))),?(?x)(N(x)?P(x))?(?x)(N(x)?Q(x))
推理如下：
?(?x)(N(x)?P(x
P (?x)(N(x?)?P(x
N(a)??P(a )
ES（2） N(a)
T（3） ?P(a)
T（3） (?x)(N(x?)O(x(?)Px(
P N(a)?(O(a?)
O(a)?P(a )
T（4）（7）
?O(a)(?x)(N(x?)Q(x(?)Ox(
P N(a)?(Q(a?)O(a
US（10） Q(a)?O(a )
T（4）（11）
（12） Q(a)
N(a)?Q(a )
T（4）（13） (?x)(N(x?)Q(x
（6）如果一个人怕困难，那么他就不会获得成功。每个人或者获得成功或者失败过。有些
人未曾失败过，所以，有些人不怕困难。 解：首先定义如下谓词：
P(x):x是人 Q(x):x怕困难 R(x):x曾获得成功 S(x):x曾获得失败
于是命题符号化为：
(?x)(P(x)?Q(x)??R(x)),(?x)(P(x)?(R(x)?S(x))),(?x)(P(x)??S(x))?(?x)(P(x)??Q(x))
推理如下：
(?x)(P(x?)?S(x
P(a)??S(a )
ES（1） P(a)
T（2） (?x)(P(x?)R(x(?)Sx(
P P(a)?(R(a?)
R(a)?S(a )
T（3）（6）
R(a)(?x)(P(x?)Q(x?)?R(x
P P(a)?Q(a)??R( a )
US（9） ?(P(a)?Q(a ) )
T（8）（10） ?P(a)??Q(a )
T（11） ?Q(a)
T（3）（12）
P(a)??Q(a )
T（3）（13）
(?x)(P(x?)?Q(x
(?x)P(x)?Q(x) P(x)?Q(x)
4.下列推导步骤中哪个是错误的？ （1）
解：错误。1）中改为(?x)(P(x)?Q(x))。
(?x)(P(x)?Q(x))
解：错误。(?x)(P(x)?Q(x))(?x)P(x)?(?x)Q(x)?P(a)?Q(b)
(?x)P(x)?Q(x)
解：错误。变量x不自由。
(?x)(P(x)?Q(x))
解：错误。
5.试找出下列推导过程中的错误，并问结论是否有效？如果有效，写出正确的推导过程。
解：错误，第2行的y是泛指，第4行的y是特制 更改如下：
(?x)(P(x)?Q(x))
T（2）（4）
EG（5） 6.用构成推导过程的方法证明下列蕴含式。 （1）(?x)P(x)?(?x)((P(x)?Q(x))?R(x)),
(?x)P(x)?,(xQ)x(?)?(x?)y(证明：
(1)(?x)P(x)(2)P(a)(3)(?x)Q(x)(4)Q(b)
(6)(?x)((P(x)?Q(x))?R(x))(7)(P(a)?Q(a))?R(a)(8)P(a)?Q(a)(9)R(a)
(10)(P(b)?Q(b))?R(b)(11)P(b)?Q(b)(12)R(b)(13)R(a)?R(b)(14)(?y)(R(a)?R(y))(15)(?x)(?y)(R(x)?R(y))
PES,(1)PES,(3)T,(1),(5)US,(6)T,(2)T,(7),(8)US,(6)T,(4)T,(10),(11)T,(9),(12)EG,(13)EG,(14)
(5)(?x)P(x)?(?x)((P(x)?Q(x))?R(x))P
（2）(?x)P(x)?(?x)Q(x)?(?x)(P(x)?Q(x)) 证明： （1）
P ??(x)Q (x
T（1） x)P(x)?(?x)Q (x
(?x)?P(x)?(
T（2） ?x)Q (x
(?x)(?P(x)?Q(x
(?x)(P(x?)Q(x
T（4） 习题 P42
1.将下列公式化为前束范式。 （1）(?x)(P(x)?(?y)Q(y)) 解： (?x)(P(x)?(?y)Q(y))
?(?x)(?P(x)?(?y)Q(y))?(?x)(?y)(?P(x)?Q(y))
（2）(?x)(?y)((?z)(P(x,y)?P(y,z))?(?u)Q(x,y,u)) 解：
(?x)(?y)((?z)(P(x,y)?P(y,z))?(?u)Q(x,y,u))?(?x)(?y)(?(?z)(P(x,y)?P(y,z))?(?u)Q(x,y,u))?(?x)(?y)((?z)(?P(x,y)??P(y,z))?(?u)Q(x,y,u))?(?x)(?y)(?z)(?u)(?P(x,y)??P(y,z)?Q(x,y,u))
（3）?(?x)(?y)A(x,y)?(?x)(?y)(B(x,y)?(?y)(A(y,x)?B(x,y))) 解：
?(?x)(?y)A(x,y)?(?x)(?y)(B(x,y)?(?y)(A(y,x)?B(x,y)))?(?x)(?y)A(x,y)?(?x)(?y)(B(x,y)?(?y)(A(y,x)?B(x,y)))?(?x)(?y)A(x,y)?(?x)(?y)(B(x,y)?(?y)(?A(y,x)?B(x,y))) ?(?x)(?y)A(x,y)?(?u)(?v)(B(u,v)?(?z)(?A(z,u)?B(u,z)))?(?x)(?y)(?u)(?v)(?z)(A(x,y)?(B(u,v)?(?A(z,u)?B(u,z))))
2.求等价于下面公式的前束主析取范式与前束主合取范式。 （1）(?x)P(x)?(?x)Q(x)?(?x)(P(x)?Q(x)) 解：前束主析取范式：
(?x)P(x)?(?x)Q(x)?(?x)(P(x)?Q(x)) ??((?x)P(x)?(?x)Q(x))?(?x)(P(x)?Q(x))?(?x)?P(x)?(?x)?Q(x)?(?x)(P(x)?Q(x))?(?x)?P(x)?(?x)?Q(x)?(?y)(P(y)?Q(y)) ?(?x)(?y)(?P(x)??Q(x)?Q(y))?(?x)(?y)((?P(x)??Q(x))?Q(y))
前束主合取范式：
(?x)P(x)?(?x)Q(x)?(?x)(P(x)?Q(x))
??((?x)P(x)?(?x)Q(x))?(?x)(P(x)?Q(x))?(?x)?P(x)?(?x)?Q(x)?(?x)(P(x)?Q(x))?(?x)?P(x)?(?x)?Q(x)?(?y)(P(y)?Q(y)) ?(?x)(?y)(?P(x)??Q(x)?Q(y))
?(?x)(?y)((?P(x)?Q(y))?(?Q(x)?Q(y)))
（2）(?x)(P(x)?(?y)((?z)Q(x,z)??(?z)R(x,y))) 解：前束析取范式
(?x)(P(x)?(?y)((?z)Q(x,z)??(?y)R(x,y)))?(?x)(?P(x)?(?y)((?z)Q(x,z)??(?y)R(x,y)))?(?x)(?P(x)?(?y)(?(?z)Q(x,z)??(?y)R(x,y)))?(?x)(?P(x)?(?y)(?(?z)Q(x,z)??(?u)R(x,u))) ?(?x)(?P(x)?(?y)((?z)?Q(x,z)?(?u)?R(x,u)))?(?x)(?y)(?z)(?u)(?P(x)?(?Q(x,z)??R(x,u)))?(?x)(?y)(?z)(?u)(?P(x)??Q(x,z)??R(x,u))
由于?P(x)??Q(x,z)??R(x,u)是基本和，因此前束合取范式与前束析取范式一样：
(?x)(P(x)?(?y)((?z)Q(x,z)??(?z)R(x,y)))?(?x)(?y)(?z)(?u)(?P(x)??Q(x,z)??R(x,u))
（3）(?x)P(x)?(?x)((?z)Q(x,z)?(?z)R(x,y,z)) 前束主析取范式：
(?x)P(x)?(?x)((?z)Q(x,z)?(?z)R(x,y,z)) ??(?x)P(x)?(?x)((?z)Q(x,z)?(?z)R(x,y,z))?(?x)?P(x)?(?u)((?z)Q(u,z)?(?v)R(u,y,v)) ?(?x)(?u)(?z)(?v)(?P(x)?Q(u,z)?R(u,y,v))
前束主合取范式与前束主析取范式相同。
（4）(?x)(P(x)?Q(x,y))?((?y)P(y)?(?z)Q(y,z)) 解：前束析取范式：
(?x)(P(x)?Q(x,y))?((?y)P(y)?(?z)Q(y,z))??(?x)(P(x)?Q(x,y))?((?y)P(y)?(?z)Q(y,z))??(?x)(?P(x)?Q(x,y))?((?y)P(y)?(?z)Q(y,z))?(?x)(P(x)?Q(x,y))?((?y)P(y)?(?z)Q(y,z))?(?x)(P(x)?Q(x,u))?((?y)P(y)?(?z)Q(u,z))?(?x)(?y)(?z)((P(x)?Q(x,u))?(P(y)?Q(u,z)))
前束合取范式：
(?x)(P(x)?Q(x,y))?((?y)P(y)?(?z)Q(y,z))?(?x)(?y)(?z)((P(x)?Q(x,u))?(P(y)?Q(u,z)))
?(?x)(?y)(?z)((P(x)?(P(y)?Q(u,z)))?(Q(x,u)?(P(y)?Q(u,z))))
?(?x)(?y)(?z)((P(x)?P(y))?(P(x)?Q(u,z))?(Q(x,u)?P(y))?(Q(x,u)?Q(u,z)))
3.将下列公式化为斯柯林范式。 （1）(?x)(P(x)?(?y)Q(x,y))
?(?x)(?P(x)?(?y)Q(x,y))?(?x)(?y)(?P(x)?Q(x,y))
?(?u)(?x)(?y)((?P(x)?Q(x,y))?(G(u)??G(u)))?(?u)(?x)(?y)((?P(x)?Q(x,y))?(G(u)??G(u)))
?(?u)(?x)(?y)((((?P(x)?Q(x,y))?(G(u)??G(u)))??H(u,x))?(?z)H(u,z))?(?u)(?x)(?y)(?z)((((?P(x)?Q(x,y))?(G(u)??G(u)))??H(u,x))?H(u,z))
（2）(?x)(?y)((?z)(P(x,z)?P(y,z))?(?u)Q(x,y,u)) ?(?x)(?y)(?(?z)(P(x,z)?P(y,z))?(?u)Q(x,y,u))?(?x)(?y)((?z)(?P(x,z)??P(y,z))?(?u)Q(x,y,u))?(?x)(?y)(?z)(?u)(?P(x,z)??P(y,z)?Q(x,y,u))
?(?v)(?x)(?y)(?z)(?u)((?P(x,z)??P(y,z)?Q(x,y,u))?(G(v)??G(v)))
?(?v)(?x)(?y)(?z)(?u)((((?P(x,z)??P(y,z)?Q(x,y,u))?(G(v)??G(v)))??H(v,x))?(?a)H(v,a))?(?v)(?x)(?y)(?z)(?u)(?a)((((?P(x,z)??P(y,z)?Q(x,y,u))?(G(v)??G(v)))??H(v,x))?H(v,a))?(?v)(?x)(?y)(?z)(?u)(?a)((((((?P(x,z)??P(y,z)?Q(x,y,u))?(G(v)??G(v)))??H(v,x))?H(v,a))??I(v,x,y))?(?b)I(v,x,b))
?(?v)(?x)(?y)(?z)(?u)(?a)(?b)((((((?P(x,z)??P(y,z)?Q(x,y,u))?(G(v)??G(v)))??H(v,x))?H(v,a))??I(v,x,y))?I(v,x,b))
?(?v)(?x)(?y)(?z)(?u)(?a)(?b)((((((((?P(x,z)??P(y,z)?Q(x,y,u))?(G(v)??G(v)))??H(v,x))?H(v,a))??I(v,x,y))?I(v,x,b))??J(v,x,y,z))?(?c)H(v,x,y,c))
?(?v)(?x)(?y)(?z)(?u)(?a)(?b)(?c)((((((((?P(x,z)??P(y,z)?Q(x,y,u))?(G(v)??G(v)))??H(v,x))?H(v,a))??I(v,x,y))?I(v,x,b))??J(v,x,y,z))?H(v,x,y,c))
1.画出图G??V,E,??的图示，指出其中哪些图是简单图。 （1）
不是简单图。
不是简单图。
是简单图。
2.写出图7-8的抽象数学定义。 （1）解：G??V,E,??，其中V
?{1,2,3,4}，E?{a,b,c,d,e,f}，
??{?a,?2,4??,?b,?1,2??,?c,?1,1??,?d,?1,3??,?e,?3,2??,?f,?4,2??}
（2）解：G??V,E,??，其中V
?{1,2,3,4,5,6,7,8,9}，E?{a,b,c,d,e,f,g,h,i,
j,k,l}，??{?a,{1,3}?,?b,{1,3}?,?c,{1,2}?,?d,{2,3}?,?e,{3,4}?, ?f,{2,4}?,?g,{2,5}?,?h,{6,7}?,?i,{7,9}?,?j,{7,8}?,?k,{8,9}?,?l,{9,9}?}
3.证明：在n阶简单有向图中，完全有向图的边数最多，其边数为n(n?1)。
证明：简单有向图是没有自环，没有平行边的有向图，只要两个不同的结点之间才能有边。完全有向图是每个结点的出度和入度都是n-1的简单有向图，也就是每个结点都有到其他所有结点的边，因此，完全有向图的边数最多。
在完全有向图中，所有结点的出度之和为n(n-1)，所有结点的入度之和为n(n-1)，设边的个数为m，由握手定理可知，2m= n(n-1)+ n(n-1)，即m= n(n-1)，得证。 4.证明：3度正则图必有偶数个结点。
证明：设三度正则图的结点个数为n，那么所有结点的度数之和为3n，由握手定理可知，边的个数为3n/2=1.5n，由于边的个数一定是整数，因此，n为偶数。得证。
5.在一次集会中，相互认识的人会彼此握手，试证明：与奇数个人握手的人数是偶数个。 证明：设集会上的人一共有m个，可分为两部分，一部分为与奇数个人握手的人，设为x个，另一部分为与偶数个人握手的人，为m-x个。
由于握手是相互的，即一次握手，两个人握手的次数都加1，一共加2，因此，集会上所有人的握手次数之和为偶数。
与偶数个人握手的人，这些人的握手次数之和为a1
?a2???am?x（其中，
a1,a2,?,am?x都是偶数），为偶数。
与奇数个人握手的人，这些人的握手次数之和为b1基数），由于所有人的握手次数之和偶数，因此b1
?b2???bx（其中，b1,b2,?,bx为
?b2???bx也要为偶数，即
(b1?b2???bx)mod2?0
(b1?b2???bx)mod2
?b1mod2?b2mod2???bxmod2
即xmod2?0，因此x为偶数，即与奇数个人握手的人是偶数个，得证。
6.证明：图7-7中的两个图同构。
证明：首先，给这两幅图标上对应的结点编号，如下
两个图的结点和边的数目都相同。假设函数
??{?1,1'?,?5,2'?,?3,3'?,?4,4'?,?5,2'?,?6,6'?}，左图中相邻的结点是
1和4，1和5，1和6，2和4，2和5，2和6，3和4，3和5，3和6，对应的像点1’和4’，1’和2’，1’和6’，5’和4’，5’和2’，5’和6’，3’和5’，3’和2’，3’和6’在右图中也相邻，因此，两图同构。
7.证明：在任意六个人中，若没有三个人彼此认识，则必有三个人彼此都不认识。 证明：分三种情况：
（1）任何一个人最多认识另外一个人
将相互认识的两个人分成一组，则至少可以分3组，每组取一个人，则这三个必不认识。 （2）任何一个人最多认识另外两个人
最糟糕的情况是当每个人都认识另外两个人时，若认识的人之间画一条线可以构成一个六边形，取不相邻的三个点即是不认识的。 （3）任何一个人最多认识另外的三个人
不妨设点A与B,C,E认识（用实线连接）。因为B,C,E之间只有有两个人认识就不满足任何三个人都不认识的条件，比如B,C认识画一条实线，那么A,B,C就相互认识，与已知矛盾。所以B,C,E是所求的三个互补认识的人。 （4）任何一个人最多认识两外4或5个人
该情况与（3）类似，所求的人即与A认识的两外4或5个人中的三个人。 证毕。
8.证明：图7-9的两个图不同构。
证明：给这两幅图标上对应的结点编号，如下：
e2?e4?e87'
两个图的点数和边数相同。假设函数：
??{?1,1'?,?2,2'?,?3,3'?,?4,4'?,?5,5'?,?6,6'?,?7,7'?,?8,8'?}
易证：① a）中的子图G1??V1,E1,?1?，V1?{1,2,3,4}，E1?{e1,e2,e3,e4}，
?1?{?e1,{1,2}?,?e2,{2,3}?,?e3,{3,4}?,?e4,{1,4}?}与b）中的子图
G1???V1?,E1?,?1??，V1??{1?,2?,3?,4?}，E1??{e1?,e2?,e3?,e4?}，
?1??{?e1?,{1,2}?,?e2?,{2,3}?,?e3?,{3,4}?,?e4?,{1,4}?}同构。
② a）中的子图G2??V2,E2,?2?，V2?{5,6,7,8}，E2?{e5,e6,e7,e8}，
?2?{?e5,{5,6}?,?e6,{6,7}?,?e7,{7,8}?,?e8,{8,9}?}与b）中的子图
G2???V2?,E2?,?2??，G2???V2?,E2?,?2??，V2??{5?,6?,7?,8?}，E2??{e5?,e6?,e7?,e8?}，
?2??{?e5?,{5,6}?,?e6?,{6,7}?,?e7?,{7,8}?,?e8?,{8,9}?}同构。
除这两个子图以外，对应a）中的子图G3??V3,E3,?3?，V2?{1,5,7,3}，
E2?{e4,e8,e9,e10}，?2?{?e9,{1,5}?,?e8,{5,7}?,?e10,{7,3}?,?e4,{3,1}?}在b）无
中对应的同构图。因此a）和b）两个图不同构。 9．图7-10的两个图是否同构？说明理由。
解：对于图b）中的点d?，其出度为：dG?(d?)?3，入度：dG?(d?)?0。而在a)图中不存在这样的结点。因此这两个图不同构。
10．证明：任何阶大于1的简单无向图必有两个结点的度数相等。
证明：考虑一个有n个结点的连通图（如果有一个孤立结点，去掉孤立结点考虑联通子图）。因为是无向连通图，每个结点的最大度数是n-1，最小度数是1。即对n个点赋值，共n-1种取值，由抽屉原理，必有两个结点的取值相同，即必有两个点的度数相同。
11．设n阶无向图G有m条边，其中nk个结点的度数为k，其余结点的度数为k+1，证明：
nk?(k?1)n?2m。
证明：由题意，结点数为n，由总边数建立关系：
nk?k?(n?nk)(k?1)
，由此可得：nk?(k?1)n?2m。
1．画出K4的所有不同的子图，并说明其中哪些是生成子图，找出互为补图的生成子图。 解：
其中，（1）和（7），（2）和（6），（3）和（5），（4）中的后两个图可以构成互补的生产子图。
2．设G??V,E,??是完全有向图。证明：对于V的任意非空子集V?，
G[V?]是完全有向图。
证明：（1）当V?中只有一个结点时，G[V?]是完全有向图。
（2）当V?中有多于一个结点时，对其中任意两个结点Vi,Vj是V的子集，即Vi,Vj?V。因为图G是完全有向图，因此Vi,Vj间存在两条有向边eij和eji。G[V?]是由非空子集V?生成的子图，故eij,eji?G[V?]，即
G[V?]中任意两个结点间存在两条有向边，故G[V?]是完全有向图。
3．画出图7-15的两个图的交、并和环和。
4．设G是任意6阶简单无向图，证明：G或必有一个子图是3阶无向图。
证明：取G或任意取三个点，取与这三个点相关联的变构成一个3阶的无向子图。
5．我们称与补图同构的简单无向图为自补图。证明：每个自补图的阶能够被4整除或被4整除余数为1。
,由自补图的定义知该2
图与其子图的边数相同（同构），故其边数为，由该数是整数
n(n?1)得：?k，n?4korn?4k?1。故每个自补图的阶能够被4整除或
证明：设图的顶点数为n，Kn的边数为
被4整除余数为1。
6．证明：没有3阶完全有向图的子图的n阶简单无向图，最多有[n2/4]条边。
证明：用数学归纳法：
?32?（1） 当n=3时，显然成立。最多有2条边。???2
（2） 设当n=k（k?4）时成立，即最多有??条边，
当n=k+1时，
①若k是偶数，则第k+1个结点最多k/2个边（否则会构成K3），
2?k?kk2k?2k?2k?2??1k?()?1?2
?4?244?????4?
②当k是奇数时，则第k+1个结点最多有
?k2?k?1?k2?1?k?1?k2?1?2k?2??(k?1)2?
??，成立。 ?4??2??4??2????4???????4?
综上，原命题成立。
习题 P144 1．考虑图7-21
（1）从A至F的路径有多少条？找出所有长度小于6的从A至F的路径。
解：A到F的路径有无数条。长度小于6的有24条。（c f h:4,c g h:4, c e i:4, b d e f h:2, b d e g h:2, b d i:4） （2）找出从A至F的所有简单路径。
解：12条。(c f h, c g h, c e I, b d e f h, b d e g h, b d i),
还有一个自环，需乘以2.
（3）找出从A至F的所有基本路径。
解：6条。(c f h, c g h, c e I, b d e f h, b d e g h, b d i) （4）求出从A至F的距离。求出该图的直径。 解：距离为3。直径为3。 （5）找出该图的所有回路。
解：AaA, AbDdEeBcA, BeEiFhCgB; BgCfB; AbDdEiFhCgBcA; BeEiFhCfB;
2．证明：图7-21中基本路径必为简单路径。
证明：基本路径要求途经的顶点不重复，简单路径要求途经的边不重复。在图7-21中，对于所有的基本路径，边不重复出现。所以基本路径必是简单路径。 3．考虑图7-22
（1）对于每个结点v，求R(v)。
解：R(v1)?R(v2)?R(v3)?R(v4)?{v1,v2,v3,v4,v5,v6},
R(v5)?{v5,v6},R(v6)?{v6},R(v7)?{v6,v7}
R(v8)?{v6,v7,v8},R(v9)?{v9},R(v10)?{v10} （2）找出所有强分支、单向分支和弱分支。
解：强分支7个，分别是{v9},{v10},{v8},{v7},{v6},{v5},{v1,v2,v3,v4} 单项分支4个，分别是{v9},{v10},{v6,v7,v8},{v1,v2,v3,v4,v5,v6} 弱分支3个，分别是{v9},{v10},{v1,v2,v3,v4,v5,v6,v7,v8}
4．设v1v2v3是任意无向图（有向图）G的三个任意结点，以下三个公
式是否成立？如果成立，给出证明；如果不成立，举出反例。 （1）d(v1,v2)?0，并且等号成立，当且仅当v1?v2。 解：成立。当v1?v2时，距离必定大于1。 （2）d(v1,v2)?d(v2,v1)
解：成立。因为无向图是无方向的。
5. 证明：有向图的每个结点和每条边恰处于一个弱分支中。 反证法：若任意结点V处于两个或两个以上的弱分支中，不妨设两个弱分支为G1, G2, 则G1, G2是G的极大联通子图。设v?G1,v?G2，又G1,G2?G,故G1,G2联通。这与G1, G2是极大联通子图矛盾，故命题得证。
6. 有向图的每个结点（每条边）是否恰处于一个强分支中？是否恰处于一个单向分支中？
解：有向图中的每个结点处于一个强分支中，而边不一定。有向图的结点和边可能出现在两个单向分支中。图见书上（P141 图7-18） 7. 证明同阶的回路必同构。
证明：同阶表明两个图的顶点个数相同，设为V; 又联通二度正则图称为回路。即两个图的每个顶点的度数相同为2. 边数为2V/2 = V,相同。由于两个图的顶点数，边数相同，且每个顶点的度数均为2，故两个图同构。
8. 判断是否G是否存在环。
解：存在。只需要找到起点和终点是同一个点的有向边序列即可。如：4j5i8e7d6f4; 5i8e7g5; 8e7g5i8; 7g5i8e7;
(v)?1,则G恰9. 设G是弱联通有向图，如果对于G的任意结点v, dG
有一条有向回路。试给出证明。
证明：因为G是弱联通有向图，不妨设一条极大单向联通子图：
(v)?1, 所以对Vk，?e??Vk,V?。若V?V1???Vk?1，则与极大联因为: dG
通子图矛盾，故V必为V1???Vk?1之一。
又假设有两条以上的回路（反证法），不妨设有两条，则这两条回路上所有点的出度为1，而要使这两条回路联通，则至少其中有一个点
(v)?1矛盾。故G恰有一条会向回路。 的出度大于1，这与dG
10. 证明：有k个弱分支的n阶简单有向图至多有(n?k)?(n?k?1)条边。 证明：
11. 设G为n阶简单无向图，对G的任意结点v, dG(v)?(n?1)/2，证明G是联通的。 证明：
任取Vi,Vj, 因为dG(v)?(n?1)/2, 故至少存在??
个点与Vi相连，最??2?
多还剩余n?2???
n?1??n?1?n?1
Vi,Vj剩余的点）。故对于Vj??1????2?2??2?
至少存在一个与Vi连接的点与Vj相连，因此Vi与Vj联通。由Vi与Vj选取的任意性，G联通。
12. 证明：对于小于或等于n的任意正整数k, n阶连通无向图有k阶连通子图。
证明：n阶连通无向图，则n个顶点中的任意点与其他顶点均可达。取其中的k个顶点也满足该性质，故存在k阶连通子图。
13. 图7-23给出了一个加权图，旁边的数字是该边上的权，求出从v1到v11的加权距离。 解：
v1到v11的距离路径如上图红色线，加权距离为：2+1+3+1+1+1+2=11
习题 P152 1.
解：根据图7-26得邻接矩阵为：
长度为1的基本路径为：v1?v4
长度为2的基本路径为：v1?v2?v4
长度为4的基本路径为：v1?v2?v3?v2?v4
111??212???0
，?A2??0?0111??
A3??0?0212??
解：（1）对于n=1,2,,,,6，试计算矩阵An1中的各元素。
0??211??4?
?101010?，A2
?102311?，A3
?752?010010????110112???
?232??????
?A4???????
?1010100??
010100?，A2
???100? ?1001000?
?0100000????
0100000????
572?253?522??
?3??0?0??12?0??6?5
?022?????100?
??2400?，A2
?000????0000044
?0800044???
?0000000???
（3）试求出图中G1和G2中的所有基本循环。
对于A1和A2，aii表示结点vi(i?1,2,...7)上长度为k的循环的个数。
3. 对于图7-26中的有向图，试求出邻接矩阵A的转置AT,AAT,ATA,列出矩阵A?AT的元素值，并说明它们的意义。
解：A表示有向图逆图的邻接矩阵，即原图中如果有第i个结点到第j个结点长度为1的路径，则A中第j行第i列为1；
第i个结点和第j个结点引出的边，可以同时终止于某些结点，这些结点的个数为AA中第i行第j列的元素值。
从某些结点引出的边，可以同时终止于第i个结点和第j个结点，这
些结点的个数为AA中第i行第j列的元素值。
A?AT中第i行第j列对应元素为1表示从第i个结点和第j个结点
引出的边，可以同时终止于某些结点；为0表示第i个结点和第j个结点引出的边，不可以同时终止于某个结点。
4. 对于nxn的布尔矩阵A，试证明：
(I?A)(2)?(I?A)?(I?A)?I?A?A(2)
其中I是nxn的单位矩阵，并且有A(2)?A?A。再证明：对于任何正整数n?I?,都有(I?A)(n)?I?A?A2?????A(n)
证明：（1）(I?A)(2)?(I?A)?(I?A)，若该矩阵中的aij?1, 则存在vk使得aik?1且akj?1，即(I?A)?(I?A), 故(I?A)(2)?(I?A)?(I?A)。又
I?A?A，A?I?A (因为I相当于每个顶点到自己的边，不改变该顶
点到其他顶点的边)，因此有：(I?A)?(I?A)?I2?(I?A)?(A?I)?A2=
I?A?A2, 故问题一得证。
（2）用数学归纳法证明： 当n=2时成立。
假设当n=k是成立，则有：(I?A)(k)?I?A?A(2)?????A(k) 当n=k+1时，
(I?A)(k?1)?(I?A)(k)?(I?A)
?(I?A?A(2)?????A(k))?(I?A)
?(I?A?A(2)?????A(k))?(I?A)
?((I?A?A(2)?????A(k))?I)?((I?A?A(2)?????A(k))?A) ?(I?A?A(2)?????A(k))?((I?A?A(2)?????A(k))?A) ?(I?A?A(2)?????A(k))?(A?A(2)?????A(k)?A(k?1))
?I?A?A(2)?????A(k)?A(k?1)
故命题成立。
5.给定简单有向图G??V,E,??，并且有?n。设A是G的邻接矩阵。试证明：根据第1题中所得到的结果能够把路径矩阵表示成
P?(I?A)(n)。
证明：对于有向图的路径矩阵：P?A?A(2)?(3)?????A(n)，而对于第一题有：A?A(2)?(3)?????A(n)?I?A?A(2)?(3)?????A(n)，故有：
由第4题得到：(I?A)(n)?I?A?A2?????A(n)，P?I?A?A(2)?(3)?????A(n)，故有：P?(I?A)(n)，得证。
6. 图7-27给出一个简单有向图。试求出该图的邻接矩阵A，并求出其路径矩阵P?A?。 解：
?000010???2
0000?，A??01
?1000???00
?01001???3
000?，A??00
?010???00010?
001??000?，
000??010?，
?01000??00
?00010??00???4(5)
A??00001?，A??01
???00001???01???01000???00P?A??A?A(2)?A(3)?A(4)?A(5) ?0???=?11011? ??01011????01011??
7. 使给出图7-25中的有向图的距离矩阵。dij?1意味着什么？ 解：
?012????101?????
D??210???, dij?1表示有一条vi到vj的边。
?????01???????10??
8. 试求出第2题中的图G1和G2的距离矩阵。 解：
?0?2??1D1??
3???, D2??12?
?1????0???
0???11???012???
?101??? ?210???
1???02?1???20??
9. 如何才能从一个距离矩阵中求得一个路径矩阵呢？
证明：对于任意结点vi和vj（i?j），由题意aij?0，因此从vi到vj必定存在一条长度不为0的路径，由结点选取的任意性得：任何两个结点均是联通的。故G的强联通的有向图。
从距离矩阵求路径矩阵：将距离矩阵中不为0的值变为1，即可得到。 10. 试确定图7-25所示的图是否是强分支。 解：对图7-25由距离矩阵求得的路径矩阵为：
1000?，由路径矩阵知该图不是强分支。
习题 P155 1.
解：a), b), c)是欧拉图，d), e), f)不是欧拉图。
2.如果G1和G2是可运算的欧拉有向图，则G1?G2仍是欧拉有向图。这句话对吗？如果对，给出证明，如果不对，举出反例。
证明：正确。参照定理7.5.5的证明，对于有向图运算后仍然是有向图。
3.设G是平凡的连通无向图，证明：G是欧拉图，当且仅当G是若干个边不相交的回路的并。
证明：充分性，当进行若干个不相交的回路的并运算后，每个结点都是偶结点，因此G是欧拉图。
必要性，对于G是欧拉图，则G必定有欧拉闭路。如果某个结点的度数大于2，可以对结点的环路进行分解，分解为多个小的环路的并。 4. 设G是平凡的连通有向图，证明：G是欧拉有向图，当且仅当G是若干个边不相交的有向回路的并。 证明：证明过程类似于3。
1.图7-34是不是二部图？如果是，找出其互补结点子集。 解：是，互补结点子集是：{v1,v3,v5},{v2,v4,v6,v7}。 2.如何由无向图G的邻接矩阵判断G是不是二部图？
解：设G的邻接矩阵为A，?n，计算A(2)，A(3)，,,A(n)。其中如果矩阵的对角线出现了基数，则G不是二部图。如果所有的矩阵（包括矩阵A）的回路长度都是偶数，则是二部图。
第1章 命题逻辑P7 习题1. 给出下列命题的否定命题： （1）大连的每条街道都临海。 否命题：不是大连的每条街道都临海。 （2）每一个素数都是奇数。否命题： 并非每一个素数都是奇数。 2. 对下述命题用中文写出语句： （1）(?P?R)?Q如果非P…
第1章 命题逻辑P7 习题1. 给出下列命题的否定命题： （1）大连的每条街道都临海。 否命题：不是大连的每条街道都临海。 （2）每一个素数都是奇数。否命题： 并非每一个素数都是奇数。 2. 对下述命题用中文写出语句： （1）(?P?R)?Q如果非P…
第1章 命题逻辑P7 习题1. 给出下列命题的否定命题： （1）大连的每条街道都临海。 否命题：不是大连的每条街道都临海。 （2）每一个素数都是奇数。否命题： 并非每一个素数都是奇数。 2. 对下述命题用中文写出语句： （1）(?P?R)?Q如果非P…
本文由()首发，转载请保留网址和出处！
免费下载文档：