第二章作业
评分要求：
1. 每小题6分: 结果正确1分; 方法格式正确3分; 计算过程2分. 合计48分
2. 给出每小题得分(注意: 写出扣分理由)
3. 总得分在采分点1处正确设置.
一. 证明下面等值式(真值表法, 解逻辑方程法, 等值演算法, 三种方法每种方法至少使用一次):
说明
证
1. p⇔(p∧q) ∨(p∧¬q)
解逻辑方程法
设 p ((p∧q) ∨(p∧¬q)) =0,
分两种情况讨论:
⎧p =1 或者 (1) ⎨⎩(p ∧q ) ∨(p ∧⌝q ) =0
⎧p =0 (2) ⎨(p ∧q ) ∨(p ∧⌝q ) =1⎩
(1)(2)两种情况均无解, 从而, p(p∧q) ∨(p∧¬q) 无成假赋值, 为永真式.
等值演算法
(p∧q) ∨(p∧¬q)
⇔ p ∧(q∨¬q)
⇔ p ∧1 排中律 ⇔ p 同一律 ∧对∨的分配率 真值表法
2. (p→q) ∧(p→r) ⇔p →(q∧r)
等值演算法
(p→q) ∧(p→r)
⇔ (¬p ∨q) ∧(¬p ∨r) 蕴含等值式
⇔ ¬p ∨(q∧r) 析取对合取的分配律
⇔ p →(q∧r) 蕴含等值式
3. ¬(pq) ⇔(p∨q) ∧¬(p∧q)
等值演算法
¬(pq)
⇔ ¬( (p→q) ∧(q→p) )等价等值式
⇔ ¬( (¬p ∨q) ∧(¬q ∨p) )蕴含等值式
⇔ ¬( (¬p ∧¬q) ∨(p∧q) )合取对析取分配律, 矛盾律, 同一律
⇔ (p∨q) ∧¬(p∧q) 德摩根律
4. (p∧¬q) ∨(¬p ∧q) ⇔(p∨q) ∧¬(p∧q)
等值演算法
(p∧¬q) ∨(¬p ∧q)
⇔ (p∨q) ∧¬(p∧q) 析取对合取分配律, 排中律, 同一律
说明: 用真值表法和解逻辑方程法证明相当于证明为永真式.
等值演算法证明时每一步后面最好注明理由以加深印象, 熟练后可以不写. 由于等值演算法证明具有较强的技巧性, 平时应注意总结心得.
二. 求下列公式的主析取范式与主合取范式(等值演算法与用成真赋值或成假赋值求解都至少使用一次):
1.
2.
3.
4.
1. (¬p →q) →(¬q ∨p)
解
(¬p →q) →(¬q ∨p)
⇔ (p∨q) →(¬q ∨p) 蕴含等值式
⇔ (¬p ∧¬q) ∨(¬q ∨p) 蕴含等值式, 德摩根律
⇔ (¬p ∧¬q) ∨¬q ∨ p 结合律
⇔ p ∨¬q 吸收律, 交换律
⇔ M 1
因此, 该式的主析取范式为m 0∨m 2∨m 3
2. (¬p →q) ∧(q∧r)
解逻辑方程法
设 (¬p →q) ∧(q∧r) =1, 则 ¬p →q=1且 q ∧r=1,
解得q=1, r=1, p=0 或者 q=1, r=1, p=1, 从而所求主析取范式为 m 3∨m 7, 主合取范式为 M 0∧M 1∧M 2∧M 4∧M 5∧M 6
等值演算法
(¬p →q) ∧(q∧r)
⇔ (p∨q) ∧(q∧r) 蕴含等值式
⇔ (p∧q ∧r) ∨(q∧r) ∧对∨分配律, 幂等律
⇔ (p∧q ∧r) ∨ (p∧q ∧r) ∨(⌝p ∧q ∧r) 同一律, 矛盾律, ∧对∨分配律
⇔ m 7 ∨ m3
主合取范式为M 0∧M 1∧M 2∧M 4∧M 5∧M 6
3. (pq) →r
解逻辑方程法
设 (pq) →r =0, 解得 p=q=1, r=0 或者 p=q=0, r=0, 从而所求主合取范式为M 0∧M 6, 主析取范式为m 1∨m 2∨m 3∨m 4∨m 5∨m 7
等值演算法
(pq) →r
⇔ ((p→q) ∧(q→p)) →r 等价等值式
⇔ ⌝((p→q) ∧(q→p)) ∨r 蕴含等值式
⇔ (p∧⌝q) ∨(q∧⌝p) ∨r 德摩根律, 蕴含等值式的否定(参见PPT)
⇔ (p∨q ∨r) ∧(⌝q ∨⌝p ∨r) ∨对∧分配律, 矛盾律, 同一律
⇔ M 0 ∧ M6
主析取范式为 m 1∨m 2∨m 3∨m 4∨m 5∨m 7
4. (p→q) ∧(q→r)
解
等值演算法
(p→q) ∧(q→r)
⇔ (⌝p ∨q) ∧(⌝q ∨r) 蕴含等值式
⇔ (⌝p ∧⌝q) ∨(⌝p ∧r) ∨(q∧r) ∧对∨分配律, 矛盾律, 同一律
⇔ (⌝p ∧⌝q ∧r) ∨(⌝p ∧⌝q ∧⌝r) ∨ (⌝p ∧q ∧r) ∨(⌝p ∧⌝q ∧r) ∨ (p∧q ∧r) ∨(⌝p ∧q ∧r) ⇔ m 1 ∨ m0 ∨ m3 ∨ m7
主合取范式为M 2 ∧ M4 ∧ M5 ∧ M6.
解逻辑方程法
设 (p → q) ∧ (q → r) = 1, 则p → q =1 且 q → r =1. 前者解得: p=0, q=0; 或者 p=0, q=1; 或者 p=1, q=1. 后者解得: q=0, r=0; 或者 q=0, r=1; 或者 q=1, r=1.
综上可得成真赋值为 000, 001, 011, 111, 从而主析取范式为m 0 ∨ m1 ∨ m3 ∨ m7, 主合取范式为M 2 ∧ M4 ∧ M5 ∧ M6.
真值表法
公式 (p → q) ∧ (q
从而主析取范式为m 0 ∨ m1 ∨ m3 ∨ m7, 主合取范式为M 2 ∧ M4 ∧ M5 ∧ M6.