离散数学习题解答
数理逻辑习题
1.
（1）要是明天不下雨且我有时间，那么我去步行街购物。
设p：明天下雨q：我有时间r：我去步行街购物
（2）如果小王和小张是一个组，那么这次英语竞赛一定取胜。
设p：小王和小张是一个组q：这次英语竞赛一定取胜
（3）除非天下雨，否则他不乘出租车上班。
设p：天下雨q：他乘出租车上班
设p：马会飞。q：羊吃草。r：母鸡是飞鸟。s：烤熟的鸭子会跑。
前提： ， ，
结论：
证明：
① 前提引入
② 前提引入
③ ①②拒取式
④ 前提引入
⑤ ③④拒取式
⑥ ⑤等值演算
⑦ ⑥化简规则
17
（1）有会说话的机器人。
设： ：x是机器人。 ：x会说话。
符号化为：
（2）尽管有人很聪明，但未必一切人都聪明。
设： ：x是人。 ：x很聪明。
符号化为：
（3）并不是所有的ቤተ መጻሕፍቲ ባይዱ车都比火车快。
设： ：x是汽车。 ：y是火车。 ：x比y快。
符号化为：
（4）有的人不吃萝卜，但人都要喝水。
设： ：x是人。 ：x吃萝卜。 ：x要喝水。
符号化为：
（5）男人一定比女人高，是不对的。
设： ：x是男人。 ：y是女人。 ：x比y高。
符号化为：
（6）某些汽车慢于所有的火车，但至少有一火车快于每一汽车。
（4）自反
（5）对称
（6）对称
13
14
[a]=[b]={a,b}，[c]=[d]={c,d}。
15
（1）证明：
1） ， ，所以R自反。
2） ，
，所以R对称。
3） ， ，
，
，
由 和 可得 。
。所以R传递。
由1），2），3）可证R是A×A上的等价关系。
（2） 具有R关系，
具有R关系，
具有R关系，
具有R关系，
具有R关系，
由R确定的划分为{{ },
{ },
{ },
{ },
{ },
{ },
{ }}
19
（1）必要性
R循环，由 则 ，所以R对称，
由 则 ，因为R对称，由 ，可得 ，所以R传递，
因R自反，所以综上所述，R是等价关系。
（2）充分性
R是等价关系，所以R自反；
R是等价关系， 则 ，因为R对称，所以可得 ，故R是循环的。
设： ：x是汽车。 ：y是火车。 ：x比y慢。
符号化为：
（7）两个不相等的实数间，必存在第三个实数。
设： ：x是实数。 ：x和y相等。 ：z在x和y之间。
符号化为：
19
（1）x是任意自然数，2x=x。真值为假。
（2）x和y是任意自然数，若x+2=y，那么y+2=x。真值为假。
（3）x和y是任意自然数，存在自然数z，使得x+y=z。真值为真。
22
极大元：7，8，9，10，11，12；
极小元：1
最小元：1
最大元：无
24
上界：12，下界：1，最小上界：12，最大下界：1。
27
（1）单射，不是满射
（2）不是满射，也不是单射
（3）不是满射，也不是单射
（4）是满射，不是单射
（5）是单射，不是满射
（6）不是单射，也不是满射
29
（1）计算 。
（2）确定商集 。
5
方法：等值演算、主范式、真值表
（2）
6
（3）
的对偶公式：
7
（1）
8
（1）
（2）
（3）
（4）可满足式
9
（1）
真值表法也很简单：00，10，11时是1，01时是0。
10
（1）
14
（1）如果今天是星期六，我们就要到独秀峰或象鼻山去玩，如果独秀峰人太多，我们就不去独秀峰。今天是星期六。独秀峰游人太多，所以我们去象鼻山玩。
20
（1）命题公式的代换实例。永真式
（3）个体域：自然数。 ：x=y。真命题。 ：x>y。假命题。可满足式。
24
（1）
（2）
25、
设 ：x是无理数。 ：x是有理数。 ：x能表示成分数。
前提： ，
结论：
证明：
① 前提引入
② ①量词等值式
③ ②等值式
④ ③等值式
⑤ ④全称量词消去规则
⑥ 前提引入
⑦ ⑥全称量词消去规则
解：
设p：今天是星期六。q：我们到独秀峰玩。r：我们到象鼻山玩。s：独秀峰游人多。
前提： ， ， 。
结论：
证明：
① 前提引入
② 前提引入
③ ①②假言推理
④ 附加前提引入
⑤ 前提引入
⑥ ④⑤假言推理
⑦ ③⑥析取三段论
（2）如果马会飞或羊吃草，则母鸡就会是飞鸟。如果母鸡是飞鸟，那么烤熟的鸭子还会跑。烤熟的鸭子不会跑。所以，羊不吃草。
⑧ ⑤⑦假言三段论
⑨ ⑧全称量词引入规则
集合论与关系习题
2
文氏图求解，答案是5人。
5
解：
7
解：R的关系矩阵为
R的关系图为：
9
dom(A)={1,2,3}，dom(B)={1,2,4}，ran(A)={2,3,4}，ran(B)={2,3,4}。
11
， ， ，
12
（1）自反
（2）反对称、传递
（3）自反、对称、传递
（4）我反悔，仅当太阳从西边出来。
设p：我反悔q：太阳从西边出来
（5）如果 在点 处可导，则 在点 处可微。反之亦然。
设p： 在点 处可导q： 在点 处可微
（6）明天既不是晴天也不是下雨天。
设p：明天是晴天q：明天是雨天
4
（2）
0
0
0
0
0
0
1
1
0
1
0
1
0
1
1
1
1
0
0
1
1
0
1
1
1
1
0
0
1
1
1
1
公式是可满足式。