离散数学作业布置
第1次作业（P15）
1.16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 解：（1）p∨(q∧r)=0∨(0∧1)=0 （2）（p?r）∧(﹁q∨s)=（0?1）∧(1∨1)=0∧1 =0 （3）（﹁p∧﹁q∧r）?(p∧q∧﹁r)=（1∧1∧1）? (0∧0∧0)=0 (4)（ r∧s）→(p∧ q)=（0∧1）→(1∧0)=0→0=1
1.17 判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2 也是无理数。另外只有6能被2整除，6才能被4整除。” 解： p: π是无理数 1 q: 3是无理数 0 r:
2是无理数 1
s: 6能被2整除 1
t: 6能被4整除 0
命题符号化为： p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。 1.19 用真值表判断下列公式的类型： （4）(p→q) →(﹁q→﹁p) （5）(p∧r) ? (﹁p∧﹁ q)
（6）((p→q) ∧(q→r)) →(p→r) 解： （4）
p q p→q q p q→ p (p→q)→( q→ p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式 ，最后一列全为1 （5）公式类型为可满足式（方法如上例），最后一列至少有一个1 （6）公式类型为永真式（方法如上例，最后一列全为1）。
第2次作业（P38）
2.3 用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ﹁(p∧q→q)
(2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r)
解：(1) ﹁(p∧q→q) ?﹁(﹁(p∧q) ∨q) ?(p∧q) ∧﹁q?p∧(q ∧﹁q)
? p∧0 ?0
所以公式类型为矛盾式
(2)（p→(p∨q)）∨(p→r) ? (﹁p∨(p∨q))∨(﹁ p∨r) ?﹁p∨p∨q∨r?1 所以公式类型为永真式
(3) (p∨q) → (p∧r) ? ￢(p∨q) ∨ (p∧r) ? (￢p∧￢q) ∨(p∧r) 易见, 是可满足式, 但不是重言式. 成真赋值为: 000,001, 101, 111
P q r ￢p∧￢q p∧r (￢p∧￢q) ∨(p∧r) 0 0 0 1 0 1 0 0 1 1 0 1 0 1 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 1 0 1 0 1 1 1 1 0 0 0 0 1 1 1 0 1 所以公式类型为可满足式 2.4 用等值演算法证明下面等值式： (2) ( (p→q)∧(p→r) ) ? (p→(q∧r))
(4)(p∧﹁q)∨(﹁p∧q) ? (p∨q)∧﹁(p∧q) 证明（2）(p→q)∧(p→r) ?( ﹁p∨q)∧(﹁p∨r) ?﹁p∨(q∧r)) ?p→(q∧r)
（4）(p∧﹁q)∨(﹁p∧q) ? (p∨(﹁p∧q)) ∧(﹁q∨(﹁p∧q) ) ? (p∨﹁p)∧(p∨q)∧(﹁q∨﹁p) ∧(﹁q∨q) ?1∧(p∨q)∧ (﹁p∨﹁q)∧1 ? (p∨q)∧﹁(p∧q)
第3次作业（P38）
2.5 求下列公式的主析取范式, 并求成真赋值: (1)( ￢p→q) →(￢q∨p) (2) (￢p→q) ∧q∧r (3)(p∨∧r)) →(p∨q∨r) (4) ￢(p→q) ∧q∧r 解：
(1)(￢p→q) →(￢q∨p) ?￢(p∨q) ∨(￢q∨p) ?￢p∧￢q ∨￢q ∨p ?￢q ∨p (吸收律)
? (￢p∨p)∧￢q ∨p∧(￢q∨q)
?￢p∧￢q∨p∧￢q ∨p∧￢q ∨p∧q ?m0∨m2∨m2∨m3 ?m0∨m2∨m3
成真赋值为 00, 10, 11.
(2) (￢p→q) ∧q∧r ? (p∨q) ∧q∧r ? (p∧q∧r) ∨q∧r
? (p∧q∧r) ∨(￢p ∨p) ∧q∧r ?p∧q∧r∨￢p ∧q∧r∨p∧q∧r
1
?m3∨m7
成真赋值为011，111.
(3) (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∨￢p∧￢r∨p∨q∨r
?￢p∧￢q∧(r∨￢r)∨￢p∧(q∨￢q)∧￢r∨p∧(q∨￢q) ∧(r∨￢r) ∨ (p∨￢p) ∧q∧(r∨￢r)∨(p∨￢p) ∧(q∨￢q) ∧r ?m0∨m1∨m2∨m3∨m4∨m5∨m6∨m7, 为重言式. (4) ￢(p→q) ∧q∧r ?￢(￢p∨q) ∧q∧r ? (p∧￢q) ∧q∧r ? p∧(￢q ∧q)∧r ?0
主析取范式为0, 无成真赋值, 为矛盾式.
第4次作业（P38）
2.6 求下列公式的主合取范式, 并求成假赋值: (1) ￢(q→￢p) ∧￢p (2)(p∧q) ∨ (￢p∨r) (3)(p→(p∨q)) ∨r 解：
(1) ￢(q→￢p) ∧￢p ?￢(￢q∨￢p) ∧￢p ?q∧p ∧￢p ?q∧0 ?0
?M0∧M1∧M2∧M3
这是矛盾式. 成假赋值为 00, 01, 10, 11.
(2)(p∧q) ∨ (￢p∨r) ?(p∧q) ∨￢p∨r
?(p∨￢p)∧(￢p ∨q)∨r ? (￢p ∨q)∨r ? ￢p ∨q∨r
?M4, 成假赋值为100.
(3)(p→(p∨q)) ∨r ?(￢p∨(p∨q)) ∨r ?(￢p∨p)∨q ∨r ?1
主合取范式为1, 为重言式.
第5次作业（P41）
2.32 用消解原理证明下述公式是矛盾式:
(1) (￢p∨q) ∧ (￢p∨r) ∧ (￢q∨￢r) ∧ (p∨￢r) ∧r (2) ￢((p∨q) ∧ ￢p→q) 解：
(1) (￢p∨q) ∧ (￢p∨r) ∧ (￢q∨￢r) ∧ (p∨￢r) ∧r
第一次循环 S0=Φ, S1=｛￢p∨q,￢p∨r,￢q∨￢r,p∨￢r,r｝, S2=Φ 由￢p∨r, p∨￢r消解得到λ 输出“no”，计算结束 (2) ￢((p∨q) ∧ ￢p→q) ?￢(￢((p∨q) ∧ ￢p) ∨q) ?((p∨q) ∧ ￢p) ∧￢q ? (p∨q) ∧ ￢p ∧￢q
第一次循环 S0=Φ, S1=｛p∨q,￢p, ￢q｝, S2=Φ 由p∨q,￢p消解得到q, 由q, ￢q消解得到λ, 输出“no”，计算结束
2.33 用消解法判断下述公式是否可满足的: (1) p∧ (￢p∨￢q) ∧q
(2) (p∨q) ∧(p∨￢q) ∧(￢p∨ r) 解：
(1) p∧ (￢p∨￢q) ∧q
第一次循环 S0=Φ, S1=｛p, ￢p∨￢q, q｝, S2=Φ 由p, ￢p∨￢q消解得到￢q, 由q, ￢q消解得到λ, 输出“no”，计算结束
(2) (p∨q) ∧(p∨￢q) ∧(￢p∨ r)
第一次循环 S0=Φ, S1=｛p∨q, p∨￢q, ￢p∨ r｝, S2=Φ 由p∨q, p∨￢q消解得到p, 由p∨q, ￢p∨ r消解得到q ∨r, 由p∨￢q, ￢p∨ r消解得到￢q ∨r, 由p, ￢p∨ r消解得到r, S2=｛p, q ∨r, ￢q ∨r, r｝
第二次循环 S0=｛p∨q, p∨￢q, ￢p∨ r｝, S1=｛p, q ∨r, ￢q ∨r, r｝, S2=Φ 由p∨q, ￢q ∨r消解得到p∨r, 由p∨￢q, q ∨r消解得到p∨r, 由p∨￢q, q ∨r消解得到p∨r, 由￢p∨ r, p 消解得到r, S2=｛p∨r｝
第三次循环 S0=｛p, q ∨r, ￢q ∨r, r｝, S1=｛p∨r｝, S2=Φ S2=Φ
输出“yes”，计算结束
第6次作业（P52）
3.6 判断下面推理是否正确. 先将简单命题符号化, 再写出前提, 结论, 推理的形式结构(以蕴涵式的形式给
出)和判断过程(至少给出两种判断方法):
(1)若今天是星期一, 则明天是星期三；今天是星期一. 所以明天是星期三. (2)若今天是星期一, 则明天是星期二；明天是星期二. 所以今天是星期一.
(3)若今天是星期一, 则明天是星期三；明天不是星期三. 所以今天不是星期一. (4)若今天是星期一, 则明天是星期二；今天不是星期一. 所以明天不是星期二. (5)若今天是星期一, 则明天是星期二或星期三. 今天是星期一. 所以明天是星期二. (6)今天是星期一当且仅当明天是星期三；今天不是星期一. 所以明天不是星期三.
设p: 今天是星期一, q: 明天是星期二, r: 明天是星期三. (1)推理的形式结构为 (p→r) ∧p→r
此形式结构为重言式, 即 (p→r) ∧p?r 所以推理正确.
(2)推理的形式结构为 (p→q) ∧q→p
此形式结构不是重言式, 故推理不正确. (3)推理形式结构为 (p→r) ∧￢r→￢p
此形式结构为重言式, 即 (p→r) ∧￢r?￢p 故推理正确.
(4)推理形式结构为 (p→q) ∧￢p→￢q
此形式结构不是重言式, 故推理不正确. (5)推理形式结构为 (p→(q∨r) )∧p →q
它不是重言式, 故推理不正确. (6)推理形式结构为 (p?r) ∧￢p→￢r
此形式结构为重言式, 即 (p?r) ∧￢p?￢r 故推理正确.
推理是否正确, 可用多种方法证明. 证明的方法有真值表法, 等值演算法. 证明推理正确还可用构造证明法.
下面用等值演算法和构造证明法证明(6)推理正确. 1. 等值演算法 (p?r) ∧￢p→￢r
?(p→r) ∧(r→p)∧￢p→￢r
?￢((￢p∨r) ∧(￢r∨p)∧￢p) ∨￢r ?￢ (￢p∨r) ∨￢(￢r∨p) ∨p ∨￢r ?(p∧￢r)∨(r∧￢p)∨p ∨￢r