离散数学答案-(1,2,7章)陈志奎

1、第1章 命题逻辑P7 习题1. 给出下列命题的否定命题： （1）大连的每条街道都临海。否命题：不是大连的每条街道都临海。（2）每一个素数都是奇数。否命题： 并非每一个素数都是奇数。2. 对下述命题用中文写出语句：（1）如果非P与R，那么Q。（2）Q并且R。3. 给出命题，我们把、分别称为命题的逆命题、反命题、逆反命题。（1）如果天不下雨，我将去公园。解：逆命题：如果我去公园，则天不下雨； 反命题：如果天下雨，则我不去公园； 逆反命题：如果我不去公园，则天下雨了。（2）仅当你去我才逗留。解：（此题注意：p仅当q翻译成） 逆命题：如果你去，那么我逗留。 反命题：如果我不逗留，那么你没去。 逆反命题

2、：如果你没去，那么我不逗留。（3）如果n是大于2的正整数，那么方程无整数解。解：逆命题：如果方程无整数解，那么n是大于2的正整数。 反命题：如果n不是大于2的正整数，那么方程有整数解。 逆反命题：如果方程有整数解，那么n不是大于2的正整数。（4）如果我不获得更多的帮助，那么我不能完成这项任务。解：逆命题：如果我不完成任务，那么我不获得更多的帮助。 反命题：如果我获得了更多的帮助，那么我能完成任务。 逆反命题：如果我能完成任务，那么我获得了更多的帮助。4. 给P和Q指派真值T，给R和S指派真值F，求出下列命题的真值。（1）=（2）=（3）=（4）=5. 构成下来公式的真值表：（1）PQFFFTF

3、TTFTFFTTTTT（2）PQRFFFTFFFFTTFFFTFTFFFTTFTFTFFFTFTFTFTFTTFFTFTTTFTF（3）PQRFFFTFFFFTTFFFTFFFTFTTFFTTFFFTTTFTFFTTTFTTTTTTTFF（4）PQRFFFTTFFTFFFTFTTFTTFFTFFTTTFTFFTTFFTTTTFF6. 使用真值表证明：如果为，那么和都是，反之亦然。证明：PQFFTTTFTFTFTFFFTTTTTT由上表可知：当为时，和都是；和为时，为。故命题得证。7. 使用真值表证明：对于和的所有值，与有同样的真值。PQFFTTFTTTTFFFTTTT8. 一个有两个运算对象的

4、逻辑运算符，如果颠倒其运算对象的次序，产生一逻辑等价命题，则称此逻辑运算符是可交换的。（1）确定所给出的逻辑运算符哪些是可交换的：，。（2）用真值表证明你的判断。解：（1），是可交换的。（2）真值表如下：PQFFFFFFTTTTFTFFTTTFFFTFFFTTFTFFTTTTTTTTTT9.设是具有两个运算对象的逻辑运算符，如果和逻辑等价，那么运算符是可结合的。（1）确定逻辑运算符，哪些是可结合的？（2）用真值表证明你的判断。解：（1）是可结合的。 （2）真值表如下：PQRFFFFFFTFFTFTTTFTFFTFTFTTFTTFTFFFTTTTFTFTTFTTFFTFFTTTTTTTPQRFF

5、FFFTTFFTFTTTFTFFTTTFTTFTTFTFFFTTTTFTFTTFTTFFTFFTTTTTTT10. 令表示命题“苹果是添的”，表示命题“苹果是红的”，表示命题“我买苹果”。试将下列命题符号化：（1）如果苹果甜而红，那么我买苹果。（2）苹果不是甜的。（3）我没买苹果，因为苹果不红也不甜。解：（1）（2）（3）P15 习题1. 指出下面命题公式哪些是重言式、永假式或可满足式。解：（1）重言式（2）永假式（3）重言式（4）重言式 （5）重言式（6）重言式 = （7）重言式 =（8）重言式=（9）重言式 =（10）可满足式=，当为真时公式为真，为假时公式为假。故为可满足式。（11）重言

6、式（12）重言式 （13）可满足式 的真值表如下：PQFFTTTFTTFFTFFFTTTTTT（14）可满足式= 当或有一个为真时公式为真；当和均为假时，若和真值相同时，公式为真；真值不同时，公式为假。故公式是可满足式。2. 写出与下面给出的公式等价并且仅含有联接词与的最简公式。（1）（2）（3）（4）（5）3. 写出与下面的公式等价并且仅含联结词和的最简公式。（1）（2）（3）4. 使用常用恒等式证明下列各式，并给出下列各式的对偶式。（1）证明： 对偶式：（2）证明：对偶式：（3）证明：对偶式：5. 试证明下列合式公式是永真式。（1）证明：（2）证明：（3）证明：（4）证明：6. 证明下列蕴

7、含式。（1）证明：（2）证明：（3）证明：（4）证明：（5）证明：（6）证明：7. 对一个重言式使用代入规则后仍为一个重言式，对一个可满足式和一个矛盾式，使用代入规则后，结果如何？对重言式、可满足式和矛盾式，使用替换规则后，结果如何？解：对于代入规则：（1）如果是可满足式，使用代入规则后可能是重言式、可满足式或矛盾式。如：可满足式，将分别替换为，分别得到重言式和可满足式，对于可满足式，将替换为得到矛盾式。（2）如果是矛盾式，使用代入规则后仍然是矛盾式。设是矛盾式，则是重言式。而对于重言式使用代入规则后仍为重言式，即是重言式，故是矛盾式。对于替换规则：由于替换规则是一种对子公式逻辑上等价的替换，

8、故对于重言式、可满足式和矛盾式使用替换规则后其真值不变。8. 求出下列各式的代入实例。（1）；用代，用代。解：（2）；用代，用代解：P21 习题1.求下列各式的主合取范式。（1）解： （2）（3）2.求下列公式的主析取范式和主合取范式：（1）合取范式：析取范式：（2）合取范式：析取范式：（3）合取范式：析取范式：（4）析取范式：合取范式：P25 习题1.试用真值表法证明：不是,和的有效结论。解：构造真值表如下：A B C D E0 0 0 0 0111000 0 0 0 1110100 0 0 1 0111000 0 0 1 1110100 0 1 0 0110000 0 1 0 111110

9、0 0 1 1 0100000 0 1 1 1101100 1 0 0 0001000 1 0 0 1000100 1 0 1 0001000 1 0 1 1000100 1 1 0 0000000 1 1 0 1001100 1 1 1 0010000 1 1 1 1011101 0 0 0 0010101 0 0 0 1010111 0 0 1 0010101 0 0 1 1010111 0 1 0 0011101 0 1 0 1011111 0 1 1 0001101 0 1 1 1001111 1 0 0 0100101 1 0 0 1100111 1 0 1 0100101 1 0

10、1 1100111 1 1 0 0101101 1 1 0 1101111 1 1 1 0111101 1 1 1 111111第6，31行前提取值均为1时，结论为0。故命题得证。2.，和是前提。在下列情况下，试确定结论C是否有效（可以使用真值表法证明。）（1）证明：真值表如下：P Q0 0110 1111 0001 111第1，2，4行当前提取值为1时，结论都为1。故结论C是有效的。（2）证明：1（1）P规则1（2）T规则，（1），3（3）P规则1，3（4）T规则，（2），（3），5（5）P规则1，3，5（6）T规则，（4），（5），结论C是有效结论。（3）（4）证明：1（1）P规则（附加前

11、提）2（2）P规则1，2（3）T规则，（1），（2），4（4）P规则1，2，4（5）T规则，（3），（4），1，2，4（6）规则，（1），（5）3.不构成真值表证明：不是、和的有效结论。证明：（1） P规则 （2） P规则 （3） T规则，(1)(2) （4） P规则 （5） T规则,(1)(4) （6） T规则(5) （7） T规则(3) （8） T规则(6)(7) （9） T规则(8)因此，是题目的有效结论，不是。4.使用推理的方法证明：是和的有效结论。证明：1（1）P规则1（2）T规则，（1），1（3）T规则，（2），1（4）T规则，（3），1（5）T规则，（1），1（6）T规则，（5）

12、，1（7）T规则，（6），1（8）T规则，（4），（7），9（9）P规则1，9（10）T规则，（8），（9），5.不构成真值表证明下列命题公式不能同时全为真。（1），证明：1（1）P规则2（2）P规则1，2（3）T规则，（1），（2），4（4）P规则1，2，4（5）T规则，（3），（4），6（6）P规则1，2，4，6（7）T规则，（5），（6），8（8）P规则(1，2，4，6，8)（9）T规则，（7），（8），推出结论与前提矛盾，因此命题公式不能同时为真。（2），证明：1（1）P规则2（2）P规则1，2（3）T规则，（1），（2），4（4）P规则1，2，4（5）T规则，（3），（4），推出的结

13、论与命题公式矛盾，因此命题公式不能同时为真。6. ，和是前提，根据推理规则断定，在下列情况下是否是有效结论。（1） 证明：1（1）P规则（假设前提）2（2）P规则1，2（3）T规则，（1），（2），4（4）P规则1，2，4（5）T规则，（3），（4），6（6）P规则1，2，4，6（7）T规则，（5），（6），1，2，4，6（8）T规则，（1），（7），1，2，4，6（9）F规则，（1），（8）因此是有效结论。（2）证明：因为，再由前提，得到、的值任意，即、的值任意。因此不是有效结论。7.证明下列结论的有效性。（1），证明：（1）P规则（2）P规则（3）T规则，（1），（2），（4）P规则（5）

14、T规则，（4），（6）T规则，（3），（5），（2），证明：（1） P规则 （2） P规则 （3） T规则（1）（2） （4） P规则 （5） T规则（3）（4） （6） T规则（5）（3），由得R为真，再由得真假任意，故无法推出P一定为真的结论。（题目有问题）8.导出下列结论（如果需要，就是用规则）（1）证明： （1） P P规则（假设前提） （2） P规则 （3） Q T规则（1）（2） （4） P规则 （5） R T规则（3）（4） （6） P规则 （7） S T规则（5）（6） （8） CP规则（1）（7）（2）证明： （1） P P规则（假设前提） （2） P规则 （3） Q T规则

15、（1）（2） （4） T规则（1）（3） （5） CP规则（1）（4）（3）证明： （1） P规则（假设前提） （2） P T规则（1） （3） Q T规则（1） （4） T规则（2）（3） （5） P规则 （6） R T规则（4）（5） （7） CP规则（1）（6）9.证明下列各式的有效性（如果需要，就使用间接证明法）。（1）证明： （1） P规则（假设前提） （2） P T规则（1） （3） P规则 （4） Q T规则（2）（3） （5） P规则 （6） T规则（4）（5） （7） P规则 （8） R T规则（6）（7） （9） P规则 （10） T规则（8）（9） （11） T规则（4）

16、（10） （12） F规则（1）（11）（2）证明： （1） P规则（假设前提） （2） P T规则（1） （3） P规则 （4） Q T规则（2）（3） （5） P规则 （6） T规则（4）（5） （7） P规则 （8） R T规则（6）（7） （9） P规则 （10） T规则（8）（9） （11） F规则（1）（10）（3）证明： （1） R P规则 （2） P规则 （3） T规则（1）（2） （4） T规则（1） （5） P规则 （6） T规则（4）（5） （7） T规则（6） （8） T规则（3）（7） （9） T规则（8）第2章 谓词逻辑习题 P391.证明下列各式。（1），证明：（

17、1）P（2）US，（1）（3）P（4）US，（3）（5）T，（2），（4），（6）EG，（5）（2）证明： （1） P（假设前提） （2） T （3） T （4） T （5） T （6） T （7） P （8） T（5）（7） （9） ES（6） （10） US（8） （11） T（9）（10） （12） F（1）（11）（3），证明：（1）P（假设前提）（2）T，（1）（3）US，（2）（4）T，（3）（5）T，（3）（6）P（7）US，（6）（8）T，（5），（7）（9）P（10）US，（8）（11）T，（4），（10）（12）T，（8），（11）（4）证明： （1） P （2） US（1

18、） （3） P （4） US（3） （5） T（2）（4） （6） P （7） US（6） （8） T（5）（7） （9） UG（8）2.用CP规则证明下列各式。（1）证明： （1） P（假设前提） （2） US（1） （3） P （4） US（3） （5） T（2）（4） （6） UG（5） （7） CP（1）（6）（2）证明：由于 因此，原题等价于证明 （1） P（假设前提） （2） US（1） （3） P （4） US（3） （5） T（2）（4） （6） UG（5） （7） CP（1）（6）3.将下列命题符号化并推证其结论。（1）所有的有理数是实数，某些有理数是整数，因此某些实数是整数

19、。解：首先定义如下谓词：是有理数是实数是整数于是问题符号化为：推理如下： （1） P （2） ES（1） （3） P （4） US（3） （5） T（2） （6） T（2） （7） T（4）（5） （8） T（6）（7） （9） EG（8）（2）任何人如果他喜欢步行，他就不喜欢乘汽车，每一个人或者喜欢乘汽车或者喜欢骑自行车，有的人不爱骑自行车，因而有的人不爱步行。解：首先定义如下谓词：是人喜欢步行喜欢乘汽车x喜欢骑自行车于是问题符号化为：推理如下： （1） P （2） ES（1） （3） T（2） （4） T（2） （5） P （6） US（5） （7） T（3）（6） （8） T（4）（7）

20、 （9） P（10） US（9）（11） T（8）（10）（12） T（11）（13） T（3）（12）（14） T（3）（13）（15） EG（14）（3）每个科学工作者都是刻苦钻研的，每个刻苦钻研而且聪明的科学工作者在他的事业中都将获得成功。华为是科学工作者并且他是聪明的，所以，华为在他的事业中将获得成功。解：首先定义如下谓词：是科学工作者是刻苦钻研的是聪明的在他的事业中将获得成功定义个体a：华为于是命题符号化为：推理如下： （1） P （2） US（1） （3） P （4） T（3） （5） T（3） （6） T（2）（4） （7） P （8） US（7） （9） T（3）（6）（10）

21、 T（8）（9）（4）每位资深名士或是中科院院士或是国务院参事，所有的资深名士都是政协委员。张伟是资深名士，但他不是中科院院士。因此，有的政协委员是国务院参事。解：首先定义如下谓词：是资深名士是中科院院士是国务院参事是政协委员定义个体a：张伟于是命题符号化为：推理如下： （1） P （2） T（1） （3） T（1） （4） P （5） US（4） （6） T（2）（5） （7） P （8） US（7） （9） T（2）（8）（10） T（3）（9）（11） T（6）（10）（12） EG（11）（5）每一个自然数不是奇数就是偶数，自然数是偶数当且仅当它能被2整除。并不是所有的自然数都能被2所

22、整除。因此，有的自然数是奇数。解：首先定义如下谓词：是自然数是奇数是偶数能被2整除于是命题符号化为：推理如下： （1） P （2） T（1） （3） ES（2） （4） T（3） （5） T（3） （6） P （7） US（6） （8） T（4）（7） （9） T（5）（8）（10） P（11） US（10）（12） T（4）（11）（13） T（9）（12）（14） T（4）（13）（15） EG（14）（6）如果一个人怕困难，那么他就不会获得成功。每个人或者获得成功或者失败过。有些人未曾失败过，所以，有些人不怕困难。解：首先定义如下谓词：是人怕困难曾获得成功曾获得失败于是命题符号化为：推理

23、如下： （1） P （2） ES（1） （3） T（2） （4） T（2） （5） P （6） US（5） （7） T（3）（6） （8） T（4）（7） （9） P （10） US（9） （11） T（8）（10） （12） T（11） （13） T（3）（12） （14） T（3）（13） （15） EG（14）4.下列推导步骤中哪个是错误的？（1）1）P2）US，1）解：错误。1）中改为。（2）1）P2）EG，1）解：错误。（3）1）P2）EG，1）解：错误。变量x不自由。（4）1）P2）EG，1）解：错误。5.试找出下列推导过程中的错误，并问结论是否有效？如果有效，写出正确的推导过程。

24、 解：错误，第2行的y是泛指，第4行的y是特制更改如下： （1） P （2） ES（1） （3） P （4） US（3） （5） T（2）（4） （6） EG（5）6.用构成推导过程的方法证明下列蕴含式。（1） 证明：（2）证明： （1） P （2） T（1） （3） T（2） （4） T（3） （5） T（4）习题 P421.将下列公式化为前束范式。（1）解： （2）解：（3）解：2.求等价于下面公式的前束主析取范式与前束主合取范式。（1）解：前束主析取范式：前束主合取范式：（2）解：前束析取范式由于是基本和，因此前束合取范式与前束析取范式一样：（3）前束主析取范式：前束主合取范式与前束主析

25、取范式相同。（4）解：前束析取范式：前束合取范式：3.将下列公式化为斯柯林范式。（1）（2）第7章 图论习题 P1351.画出图的图示，指出其中哪些图是简单图。（1）不是简单图。（2）不是简单图。（3）是简单图。2.写出图7-8的抽象数学定义。（1）解：，其中，（2）解：，其中， ， 3.证明：在n阶简单有向图中，完全有向图的边数最多，其边数为。证明：简单有向图是没有自环，没有平行边的有向图，只要两个不同的结点之间才能有边。完全有向图是每个结点的出度和入度都是n-1的简单有向图，也就是每个结点都有到其他所有结点的边，因此，完全有向图的边数最多。在完全有向图中，所有结点的出度之和为n(n-1)，

26、所有结点的入度之和为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，因此，集

27、会上所有人的握手次数之和为偶数。与偶数个人握手的人，这些人的握手次数之和为（其中，都是偶数），为偶数。与奇数个人握手的人，这些人的握手次数之和为（其中，为基数），由于所有人的握手次数之和偶数，因此也要为偶数，即又因为即，因此x为偶数，即与奇数个人握手的人是偶数个，得证。6.证明：图7-7中的两个图同构。证明：首先，给这两幅图标上对应的结点编号，如下两个图的结点和边的数目都相同。假设函数，左图中相邻的结点是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.证明

28、：在任意六个人中，若没有三个人彼此认识，则必有三个人彼此都不认识。证明：分三种情况：（1）任何一个人最多认识另外一个人将相互认识的两个人分成一组，则至少可以分3组，每组取一个人，则这三个必不认识。（2）任何一个人最多认识另外两个人最糟糕的情况是当每个人都认识另外两个人时，若认识的人之间画一条线可以构成一个六边形，取不相邻的三个点即是不认识的。（3）任何一个人最多认识另外的三个人不妨设点A与B,C,E认识（用实线连接）。因为B,C,E之间只有有两个人认识就不满足任何三个人都不认识的条件，比如B,C认识画一条实线，那么A,B,C就相互认识，与已知矛盾。所以B,C,E是所求的三个互补认识的人。（4）

29、任何一个人最多认识两外4或5个人该情况与（3）类似，所求的人即与A认识的两外4或5个人中的三个人。证毕。8.证明：图7-9的两个图不同构。证明：给这两幅图标上对应的结点编号，如下：两个图的点数和边数相同。假设函数：易证： a）中的子图，与b）中的子图，同构。 a）中的子图，与b）中的子图，同构。除这两个子图以外，对应a）中的子图，在b）无中对应的同构图。因此a）和b）两个图不同构。9图7-10的两个图是否同构？说明理由。解：对于图b）中的点，其出度为：，入度：。而在a)图中不存在这样的结点。因此这两个图不同构。10证明：任何阶大于1的简单无向图必有两个结点的度数相等。证明：考虑一个有n个结点的

30、连通图（如果有一个孤立结点，去掉孤立结点考虑联通子图）。因为是无向连通图，每个结点的最大度数是n-1，最小度数是1。即对n个点赋值，共n-1种取值，由抽屉原理，必有两个结点的取值相同，即必有两个点的度数相同。11设n阶无向图G有m条边，其中个结点的度数为k，其余结点的度数为k+1，证明：。证明：由题意，结点数为n，由总边数建立关系：，由此可得：。习题 P1391画出的所有不同的子图，并说明其中哪些是生成子图，找出互为补图的生成子图。解：其中，（1）和（7），（2）和（6），（3）和（5），（4）中的后两个图可以构成互补的生产子图。2设是完全有向图。证明：对于的任意非空子集，是完全有向图。证明：

31、（1）当中只有一个结点时，是完全有向图。（2）当中有多于一个结点时，对其中任意两个结点是的子集，即。因为图G是完全有向图，因此间存在两条有向边和。是由非空子集生成的子图，故，即中任意两个结点间存在两条有向边，故是完全有向图。3画出图7-15的两个图的交、并和环和。解：交： 并： 环和：4设G是任意6阶简单无向图，证明：G或必有一个子图是3阶无向图。证明：取G或任意取三个点，取与这三个点相关联的变构成一个3阶的无向子图。5我们称与补图同构的简单无向图为自补图。证明：每个自补图的阶能够被4整除或被4整除余数为1。证明：设图的顶点数为n，Kn的边数为,由自补图的定义知该图与其子图的边数相同（同构），

32、故其边数为，由该数是整数得：，。故每个自补图的阶能够被4整除或被4整除余数为1。6证明：没有3阶完全有向图的子图的n阶简单无向图，最多有条边。证明：用数学归纳法：（1） 当n=3时，显然成立。最多有2条边。（2） 设当n=k（）时成立，即最多有条边，当n=k+1时，若k是偶数，则第k+1个结点最多k/2个边（否则会构成K3），成立。当k是奇数时，则第k+1个结点最多有个边，成立。综上，原命题成立。习题 P1441考虑图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

33、 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证

34、明：图7-21中基本路径必为简单路径。证明：基本路径要求途经的顶点不重复，简单路径要求途经的边不重复。在图7-21中，对于所有的基本路径，边不重复出现。所以基本路径必是简单路径。3考虑图7-22（1）对于每个结点，求。解： （2）找出所有强分支、单向分支和弱分支。解：强分支7个，分别是单项分支4个，分别是弱分支3个，分别是4设是任意无向图（有向图）G的三个任意结点，以下三个公式是否成立？如果成立，给出证明；如果不成立，举出反例。（1），并且等号成立，当且仅当。解：成立。当时，距离必定大于1。（2）解：成立。因为无向图是无方向的。5. 证明：有向图的每个结点和每条边恰处于一个弱分支中。反证法：若任意结点V处于两个或两个以上的弱分支中，不妨设两个弱分支为G1, G2, 则G1, G2是G的极大联通子图。设，又,故联通。这与G1, G2是极大联通子图矛盾，故命题得证。6. 有向图的每个结点（每条边）是否恰处于一个强分支中？是否恰处于一个单向分支中？解：有向图中的每个结点处于一个强分支中，而边不一定。有向图的结点和边可能出现在两个单向分支中。图见书上（P141 图7-18）7. 证明同阶的回路必同构。证明：同阶表明两个图的顶点个数相同，设为V; 又联通二度正则图称为回路。即两个图的每个顶点的度数相同为2. 边数为