离散数学习题答案
习题一及答案：（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）()()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 ⌝
证明：用归谬法
① p 结论的否定引入
② p q →⌝ 前提引入
③ q ⌝ ①②假言推理
④ r q ⌝∨ 前提引入
⑤ r ⌝ ③④析取三段论
⑥ r s ∧⌝ 前提引入
⑦ r ⑥化简
⑧r r ∧⌝ ⑤⑦合取
由于0r r ∧⌝⇒，所以推理正确。
17、在自然推理系统P 中构造下面推理的证明：
只要A 曾到过受害者房间并且11点以前没离开，A 就是谋杀嫌犯。A 曾到过受害者房间。如果A 在11点以前离开，看门人会看见他。看门人没有看见他。所以，A 是谋杀嫌犯。 解：设p ：A 到过受害者房间，q ：A 在11点以前离开，r ：A 是谋杀嫌犯，s ：看门人看见过A 。
则前提：()p q r ∧⌝→，p ，q s →，s ⌝
结论：r
证明：
① q s → 前提引入
② s ⌝ 前提引入
③ q ⌝ ①②拒取式
④ p 前提引入
