《离散数学》第1章练习题参考答案
2017年
一、填空题
1. 设命题公式)(r q p G ∨⌝∧=，则G 的成真赋值是 100 、 101 、 111 .
2. 已知命题公式r q p G →∧⌝=)(，则G 的析取范式为r q p ∨⌝∨.
3. 设B A ,为两个命题公式，B A ⇔当且仅当为重言式B A ↔，B A ⇒当且仅当为重言式B A →.
4. 已知命题公式),,(r q p A 的主合取范式为530M M M ∧∧，则它的主析取范式为76421m m m m m ∨∨∨∨.
5. 已知命题公式),,(r q p A 的成真赋值为000,001,010,100,110，则其主合取范式为357M M M ∧∧.
二、选择题
1. 设命题公式)(p q p G ⌝→∧=，则使G 的真值为1的p ，q 的取值是 （ C ）
（A ） 00 （B ） 01 （C ） 10 （D ） 11
2. 与命题公式)(r q p →→等值的公式是 （ B ）
（A ）r q p →∨)( （B ）r q p →∧)( （C ）)(r q p ∧→ （D ）)(r q p ∨→
3. 命题公式p q p →∧)(是 （ A ）
（A ）永真式 （B ）永假式 （C ）非永真式的可满足式 （D ）合取范式
4. 设命题公式)(),(p q H q p G ⌝→=→⌝=，则G 与H 的关系是 （ D ）
（A ）G H ⇔ （B ）G H → （C ）G H ⇒ （D ）H G ⇒
5. 下列重言蕴涵式中，不正确的是 （ C ）
（A ）Q P Q ∨⇒ （B ）Q P Q →⇒
（C ）P Q P Q ⇒→∧⌝)( （D ）Q Q P ⌝⇒→⌝)(
三、计算题
1. 将下列命题符号化
（1）李强不是不聪明，而是不用功 （2）如果天不下雨，我们就去郊游 解 （1）设p ：李强聪明，q ：李强用功.
原命题符号化为：q p ⌝∧
（2）设p ：天下雨，q ：我们去郊游.
原命题符号化为：q p →⌝
2.给出下列公式的真值表
（1）r q p r q p ⌝∧∧→→∧)(
（2）)()()(r p r q q p ⌝∧⌝→→∧∨⌝
解略.
3. 设命题变项q p ,为1， s r ,为0，试求出下列命题的真值
（1）)(r q p ∧∨ （2）)()(s q r p →⌝∧→
解 （1）101)01(1)(⇔∨⇔∧∨⇔∧∨r q p
（2）010)00()01()()(⇔∧⇔→∧→⇔→⌝∧→s q r p
4. 判断下列公式的类型
（1）)(r q p p ∨∨→ （2）)()(q p q p ∨⌝→↔
解 用真值表知（1）是重言式，（2）是可满足式.
5. 求命题公式r q p →∨)(的主合取范式，并求其成假赋值. 解 用真值表可得642)(M M M r q p ∧∧⇔→∨.
真值为0的赋值有三种：001，100，110.
6. 求命题公式r q p ∨∧)(的主合取范式与主析取范式.
解 用真值表法可知
42076531)(M M M m m m m m r q p ∧∧⇔∨∨∨∨⇔∨∧
四、证明题
1. 用等值演算法证明q q p p →→∧)(为重言式. 证 原式q q p p q q p p →∨⌝∧⇔→→∧⇔)()( q q p q q p p ∨∧⌝⇔∨∨⌝∧⌝⇔)())((
11⇔∨⌝⇔∨⌝∨⌝⇔p q q p
2. 构造下列推理的证明
（1）前提：q p q s s r q r →⌝→∨⌝→,,,，结论：p ⌝；
（2）前提：s r s p q s r q p ,),)((),()(⌝∨→∧⌝→→⌝，结论：q p ↔；
(3) 前提：)(,)(,t p r r q q p ∧⌝⌝⌝∧∨⌝→，结论：t ⌝. 证 （1）用归谬法证明
①p 结论的否定引入 ②q p → 前提引入 ③q ①②假言推理 ④q s ⌝→ 前提引入 ⑤s ⌝ ③④拒取 ⑥ s r ∨ 前提引入
⑦r ⑤⑥析取三段论 ⑧q r ⌝→ 前提引入
⑨q ⌝ ⑦⑧假言推理 ⑩q q ⌝∧ ③⑨合取 ⑩得出矛盾，因此，p ⌝是前提的有效结论.
（2）
① s p q ⌝∨→)( 前提引入
② s 前提引入
③ p q → ①②析取三段论 ④ )()(s r q p ∧⌝→→⌝ 前提引入
⑤ r 前提引入
⑥ s r ∧ ②⑤合取
⑦ q p → ④⑥拒取
⑧)
p→
∧
q
→③⑦合取
(
q
)
(p
⑨q
p↔⑧置换
（3）①r
⌝)
(前提引入
∨
∧
q⌝
r
②r
q∨
⌝①化简
③r
⌝①化简
④)
⌝前提引入
⌝
p∧
(t
⑤t
p⌝
∨④置换
⑥q
⌝②③析取三段论
⑦q
p→前提引入
⑧p
⌝⑥⑦拒取
⑨t⌝⑤⑧析取三段论
