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

第1章 命题逻辑
P7 习题
1. 给出下列命题的否定命题：
（1）大连的每条街道都临海。
否命题：不是大连的每条街道都临海。
（2）每一个素数都是奇数。
否命题： 并非每一个素数都是奇数。
2. 对下述命题用中文写出语句：
（1）
如果非P与R，那么Q。
（2）
Q并且R。
3. 给出命题，我们把、、分别称为命题的逆命题、反命题、逆反命题。
（1）如果天不下雨，我将去公园。
解：逆命题：如果我去公园，则天不下雨；
反命题：如果天下雨，则我不去公园；
逆反命题：如果我不去公园，则天下雨了。
（2）仅当你去我才逗留。
解：（此题注意：p仅当q翻译成）
逆命题：如果你去，那么我逗留。
反命题：如果我不逗留，那么你没去。
逆反命题：如果你没去，那么我不逗留。
（3）如果n是大于2的正整数，那么方程无整数解。
解：逆命题：如果方程无整数解，那么n是大于2的正整数。
反命题：如果n不是大于2的正整数，那么方程有整数解。
逆反命题：如果方程有整数解，那么n不是大于2的正整数。
（4）如果我不获得更多的帮助，那么我不能完成这项任务。
解：逆命题：如果我不完成任务，那么我不获得更多的帮助。
反命题：如果我获得了更多的帮助，那么我能完成任务。
逆反命题：如果我能完成任务，那么我获得了更多的帮助。
4. 给P和Q指派真值T，给R和S指派真值F，求出下列命题的真值。
（1）
=
=
=
=
（2）
=
=
=
=
（3）
=
=
=
=
（4）
=
=
=
5. 构成下来公式的真值表：
（1）
P
Q

F
F
F
T
F
T
T
F
T
F
F
T
T
T
T
T

（2）
P
Q
R

F
F
F
T
F
F
F
F
T
T
F
F
F
T
F
T
F
F
F
T
T
F
T
F
T
F
F
F
T
F
T
F
T
F
T
F
T
T
F
F
T
F
T
T
T
F
T
F

（3）
P
Q
R

F
F
F
T
F
F
F
F
T
T
F
F
F
T
F
F
F
T
F
T
T
F
F
T
T
F
F
F
T
T
T
F
T
F
F
T
T
T
F
T
T
T
T
T
T
T
F
F

（4）
P
Q
R

F
F
F
T
T
F
F
T
F
F
F
T
F
T
T
F
T
T
F
F
T
F
F
T
T
T
F
T
F
F
T
T
F
F
T
T
T
T
F
F

6. 使用真值表证明：如果为，那么和都是，反之亦然。
证明：
P
Q

F
F
T
T
T
F
T
F
T
F
T
F
F
F
T
T
T
T
T
T
由上表可知：当为时，和都是；和为时，为。故命题得证。
7. 使用真值表证明：对于和的所有值，与有同样的真值。
P
Q

F
F
T
T
F
T
T
T
T
F
F
F
T
T
T
T
8. 一个有两个运算对象的逻辑运算符，如果颠倒其运算对象的次序，产生一逻辑等价命题，则称此逻辑运算符是可交换的。
（1）确定所给出的逻辑运算符哪些是可交换的：，，，。
（2）用真值表证明你的判断。
解：（1），，是可交换的。
（2）真值表如下：
P
Q

F
F
F
F
F
F
T
T
T
T
F
T
F
F
T
T
T
F
F
F
T
F
F
F
T
T
F
T
F
F
T
T
T
T
T
T
T
T
T
T

9.设是具有两个运算对象的逻辑运算符，如果和逻辑等价，那么运算符是可结合的。
（1）确定逻辑运算符，，，哪些是可结合的？
（2）用真值表证明你的判断。
解：（1）是可结合的。
（2）真值表如下：
P
Q
R

F
F
F
F
F
F
T
F
F
T
F
T
T
T
F
T
F
F
T
F
T
F
T
T
F
T
T
F
T
F
F
F
T
T
T
T
F
T
F
T
T
F
T
T
F
F
T
F
F
T
T
T
T
T

T
T

P
Q
R

F
F
F
F
F
T
T
F
F
T
F
T
T
T
F
T
F
F
T
T
T
F
T
T
F
T
T
F
T
F
F
F
T
T
T
T
F
T
F
T
T
F
T
T
F
F
T
F
F
T
T
T
T
T
T
T

10. 令表示命题“苹果是添的”，表示命题“苹果是红的”，表示命题“我买苹果”。试将下列命题符号化：
（1）如果苹果甜而红，那么我买苹果。
（2）苹果不是甜的。
（3）我没买苹果，因为苹果不红也不甜。

解：（1）
（2）
（3）

P15 习题
1. 指出下面命题公式哪些是重言式、永假式或可满足式。
解：
（1）重言式

（2）永假式

（3）重言式

（4）重言式

（5）重言式

（6）重言式

=
（7）重言式

=
（8）重言式

=
=
=
（9）重言式

=
（10）可满足式

=，当为真时公式为真，为假时公式为假。故为可满足式。
（11）重言式

（12）重言式

（13）可满足式
的真值表如下：
P
Q

F
F
T
T
T
F

T
T
F
F
T
F
F
F
T
T
T
T
T
T

（14）可满足式

=
=
当或有一个为真时公式为真；当和均为假时，若和真值相同时，公式为真；真值不同时，公式为假。故公式是可满足式。
2. 写出与下面给出的公式等价并且仅含有联接词与的最简公式。
（1）

（2）

（3）

（4）

（5）

3. 写出与下面的公式等价并且仅含联结词和的最简公式。
（1）

（2）

（3）

4. 使用常用恒等式证明下列各式，并给出下列各式的对偶式。
（1）
证明：

对偶式：
（2）
证明：

对偶式：
（3）
证明：

对偶式：
5. 试证明下列合式公式是永真式。
（1）
证明：

（2）
证明：

（3）
证明：

（4）
证明：

6. 证明下列蕴含式。
（1）
证明：

（2）
证明：

（3）
证明：

（4）
证明：

（5）
证明：

（6）
证明：

7. 对一个重言式使用代入规则后仍为一个重言式，对一个可满足式和一个矛盾式，使用代入规则后，结果如何？对重言式、可满足式和矛盾式，使用替换规则后，结果如何？
解：对于代入规则：
（1）如果是可满足式，使用代入规则后可能是重言式、可满足式或矛盾式。如：可满足式，将分别替换为，分别得到重言式和可满足式，对于可满足式，将替换为得到矛盾式。
（2）如果是矛盾式，使用代入规则后仍然是矛盾式。设是矛盾式，则是重言式。而对于重言式使用代入规则后仍为重言式，即是重言式，故是矛盾式。
对于替换规则：由于替换规则是一种对子公式逻辑上等价的替换，故对于重言式、可满足式和矛盾式使用替换规则后其真值不变。
8. 求出下列各式的代入实例。
（1）；用代，用代。
解：
（2）；用代，用代
解：

P21 习题
1.求下列各式的主合取范式。
（1）
解：
（2）

（3）

2.求下列公式的主析取范式和主合取范式：
（1）

合取范式：

析取范式：
（2）
合取范式：

析取范式：
（3）
合取范式：
析取范式：
（4）
析取范式：

合取范式：

P25 习题
1.试用真值表法证明：不是,,和的有效结论。
解：构造真值表如下：
A B C D E

0 0 0 0 0
1
1
1
0
0
0 0 0 0 1
1
1
0
1
0
0 0 0 1 0
1
1
1
0
0
0 0 0 1 1
1
1
0
1
0
0 0 1 0 0
1
1
0
0
0
0 0 1 0 1
1
1
1
1
0

0 0 1 1 0
1
0
0
0
0
0 0 1 1 1
1
0
1
1
0
0 1 0 0 0
0
0
1
0
0
0 1 0 0 1
0
0
0
1
0
0 1 0 1 0
0
0
1
0
0
0 1 0 1 1
0
0
0
1
0
0 1 1 0 0
0
0
0
0
0
0 1 1 0 1
0
0
1
1
0
0 1 1 1 0
0
1
0
0
0
0 1 1 1 1
0
1
1
1
0
1 0 0 0 0
0
1
0
1
0
1 0 0 0 1
0

1
0
1
1
1 0 0 1 0
0
1
0
1
0
1 0 0 1 1
0
1
0
1
1
1 0 1 0 0
0
1
1
1
0
1 0 1 0 1
0
1
1
1
1
1 0 1 1 0
0
0
1
1
0
1 0 1 1 1
0
0
1
1
1
1 1 0 0 0
1
0
0
1
0
1 1 0 0 1
1
0
0
1
1
1 1 0 1 0
1
0
0
1
0
1 1 0 1 1
1
0
0
1
1
1 1 1 0 0
1
0
1
1
0
1 1 1 0 1
1
0
1
1
1
1 1 1 1 0
1
1
1
1
0
1 1 1 1 1
1
1
1
1
1
第6，31行前提取值均为1时，结论为0。故命题得证。
2.，和是前提。在下列情况下，试确定结论C是否有效（可以使用真值表法证明。）
（1）

证明：真值表如下：
P Q

0 0
1
1
0 1
1
1
1 0
0
0
1 1
1
1
第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规则（附加前提）
{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），
{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），
推出的结论与命题公式矛盾，因此命题公式不能同时为真。
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） 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规则（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）（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章 谓词逻辑
习题 P39
1.证明下列各式。
（1），
证明： （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）
（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）所有的有理数是实数，某些有理数是整数，因此某些实数是整数。
解：首先定义如下谓词：
是有理数
是实数
是整数
于是问题符号化为：

推理如下：
（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）
（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） 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所整除。因此，有的自然数是奇数。
解首先定义如下谓词：
是自然数
是奇数
是偶数
能被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）如果一个人怕困难，那么他就不会获得成功。每个人或者获得成功或者失败过。有些人未曾失败过，所以，有些人不怕困难。
解：首先定义如下谓词：
是人
怕困难
曾获得成功
曾获得失败
于是命题符号化为：

推理如下：
（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） P
2） US，1）
解：错误。1）中改为。
（2） 1） P
2） EG，1）
解：错误。
（3） 1） P
2） EG，1）

解：错误。变量x不自由。
（4） 1） P
2） EG，1）
解：错误。
5.试找出下列推导过程中的错误，并问结论是否有效？如果有效，写出正确的推导过程。
解：错误，第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）
习题 P42
1.将下列公式化为前束范式。
（1）
解：

（2）
解：

（3）
解：

2.求等价于下面公式的前束主析取范式与前束主合取范式。
（