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

1、第二章作业评分要求：1. 每小题6分: 结果正确1分; 方法格式正确3分; 计算过程2分. 合计48分2. 给出每小题得分(注意: 写出扣分理由) 3. 总得分在采分点1处正确设置.一.证明下面等值式(真值表法,解逻辑方程法,等值演算法,三种方法每种方法至少使用一次):说明证1. p(pq)(pq)解逻辑方程法设 p(pq)(pq) =0, 分两种情况讨论: 或者(1)(2)两种情况均无解, 从而, p(pq)(pq)无成假赋值, 为永真式.等值演算法(pq)(pq) p(qq)对的分配率 p1 排中律 p同一律真值表法pqp (pq)(pq)001011101111即 p (pq)(pq)为

2、永真式, 得证2. (pq)(pr)p(qr)等值演算法(pq)(pr) (pq)(pr)蕴含等值式 p(qr)析取对合取的分配律 p(qr)蕴含等值式3. (pq)(pq)(pq)等值演算法(pq) ( (pq)(qp) )等价等值式 ( (pq)(qp) )蕴含等值式 ( (pq)(pq) )合取对析取分配律, 矛盾律, 同一律 (pq)(pq)德摩根律4. (pq)(pq)(pq)(pq)等值演算法(pq)(pq) (pq)(pq)析取对合取分配律, 排中律, 同一律说明: 用真值表法和解逻辑方程法证明相当于证明为永真式.等值演算法证明时每一步后面最好注明理由以加深印象, 熟练后可以不写

3、. 由于等值演算法证明具有较强的技巧性, 平时应注意总结心得.二.求下列公式的主析取范式与主合取范式(等值演算法与用成真赋值或成假赋值求解都至少使用一次):1. 2. 3. 4. 1. (pq)(qp)解 (pq)(qp) (pq)(qp)蕴含等值式 (pq)(qp)蕴含等值式, 德摩根律 (pq)q p结合律 pq吸收律, 交换律 M1因此, 该式的主析取范式为m0m2m32. (pq)(qr) 解逻辑方程法设 (pq)(qr) =1, 则 pq=1且 qr=1, 解得q=1, r=1, p=0 或者 q=1, r=1, p=1, 从而所求主析取范式为 m3m7, 主合取范式为 M0M1M2

4、M4M5M6等值演算法(pq)(qr) (pq)(qr)蕴含等值式 (pqr)(qr)对分配律, 幂等律 (pqr) (pqr)(pqr)同一律, 矛盾律, 对分配律 m7 m3主合取范式为M0M1M2M4M5M63. (pq)r解逻辑方程法设 (pq)r =0, 解得 p=q=1, r=0 或者 p=q=0, r=0, 从而所求主合取范式为M0M6, 主析取范式为m1m2m3m4m5m7等值演算法(pq)r (pq)(qp)r等价等值式 (pq)(qp)r蕴含等值式 (pq)(qp)r德摩根律, 蕴含等值式的否定(参见PPT) (pqr)(qpr)对分配律, 矛盾律, 同一律 M0 M6主析

5、取范式为 m1m2m3m4m5m74. (pq)(qr) 解 等值演算法(pq)(qr) (pq)(qr)蕴含等值式 (pq)(pr)(qr)对分配律, 矛盾律, 同一律 (pqr)(pqr) (pqr)(pqr) (pqr)(pqr) 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) 真值表如下:pqr