离散数学-第二章命题逻辑等值演算习题及答案

第二章作业
评分要求：
1. 每小题6分: 结果正确1分; 方法格式正确3分; 计算过程2分. 合计48分
2. 给出每小题得分(注意: 写出扣分理由)
3. 总得分在采分点1处正确设置.
一. 证明下面等值式(真值表法, 解逻辑方程法, 等值演算法, 三种方法每种方法至少使用一
次):

说明
证
1. p⇔(p∧q)∨(p∧¬q)
解逻辑方程法
设 p↔((p∧q)∨(p∧¬q)) =0, 分两种情况讨论:




0)()(1)1(qpqp
p

或者




1)()(0)2(qpqp
p

(1)(2)两种情况均无解, 从而, p↔(p∧q)∨(p∧¬q)无成假赋值, 为永真式.
等值演算法
(p∧q)∨(p∧¬q)
⇔ p∧(q∨¬q) ∧对∨的分配率
⇔ p∧1 排中律
⇔ p 同一律
真值表法
p q
p↔ ((p∧q)∨(p∧¬q))
0 0 1
0 1 1
1 0 1
1 1 1
即 p↔ ((p∧q)∨(p∧¬q))为永真式, 得证
2. (p→q)∧(p→r)⇔p→(q∧r)
等值演算法
(p→q)∧(p→r)
⇔ (¬p∨q)∧(¬p∨r)蕴含等值式
⇔ ¬p∨(q∧r)析取对合取的分配律
⇔ p→(q∧r)蕴含等值式
3. ¬(p↔q)⇔(p∨q)∧¬(p∧q)
等值演算法
¬(p↔q)
⇔ ¬( (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吸收律, 交换律
⇔ M1
因此, 该式的主析取范式为m0∨m2∨m3

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, 从而所求主析取范式为 m3∨m7, 主合取范式为 M
0

∧M1∧M2∧M4∧M5∧M6

等值演算法
(¬p→q)∧(q∧r)
 (pq)(qr) 蕴含等值式
 (pqr)(qr) 对分配律, 幂等律
 (pqr)  (pqr)(pqr) 同一律, 矛盾律, 对分配律
 m7  m3
主合取范式为M0∧M1∧M2∧M4∧M5∧M6

3. (p↔q)→r
解逻辑方程法
设 (p↔q)→r =0, 解得 p=q=1, r=0 或者 p=q=0, r=0, 从而所求主合取范式为M0∧M6, 主析
取范式为m1∨m2∨m3∨m4∨m5∨m7

等值演算法
(p↔q)→r
 ((pq)(qp))r 等价等值式
 ((pq)(qp))r 蕴含等值式
 (pq)(qp)r 德摩根律, 蕴含等值式的否定(参见PPT)
 (pqr)(qpr) 对分配律, 矛盾律, 同一律
 M0  M6
主析取范式为 m1∨m2∨m3∨m4∨m5∨m7

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)
 m1  m0  m3  m7
主合取范式为M2  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, 从而主析取范式为m0  m1  m3  m7, 主合取范式
为M2  M4  M5  M6.

真值表法
公式 (p  q)  (q  r) 真值表如下:
p q r
(p  q)  (q  r)

0 0 0 1
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 0
1 1 1 1
从而主析取范式为m0  m1  m3  m7, 主合取范式为M2  M4  M5  M6.