[工学]04对偶与范式2011-03-22-34.ppt

34 离散数学(Discrete Mathematics) 复习 本讲主要内容 范式：合取范式与析取范式，及转化步骤 对偶式 对偶式 - 相关定理 合取范式 - 析取式的合取 析取范式 - 合取式的析取 求解范式的步骤 求解范式-举例 范式不唯一 小项 小项的真值表与二进制编码 小项的性质 主析取范式 定理证明 求解主析取范式的方法 求解主析取范式真值表法举例(1) 求解主析取范式真值表法举例(2) 求解主析取范式等价推导举例 结论 大项 大项的真值表与二进制编码 大项的性质 主合取范式 求解主合取范式的方法 求解主合取范式真值表法举例 求解主合取范式等价推导举例 简化约定 练习 练习 练习 练习 练习 小结 3. 求 ┐(P∨Q)?(P∧Q) 的析取范式 解：原式 ? (┐(P∨Q)?(P∧Q)) ∧ ((P∧Q)?┐(P∨Q)) ? ((P∨Q)∨(P∧Q)) ∧ ((┐P∨┐Q)∨(┐P∧┐Q)) ? ((P∨Q∨P)∧(P∨Q∨Q)) ∧ ((┐P∨┐Q∨┐P)∧(┐P∨┐Q∨┐Q)) ? (P∨Q)∧(┐P∨┐Q) ? ((P∨Q)∧┐P)∨((P∨Q)∧┐Q)) ? (P∧┐P)∨(┐P∧Q)∨(P∧┐Q)∨(Q∧┐Q) 4. 求 (P∧Q)∨(┐P∧R) 的主合取范式 解：原式 ? ((P∧Q)∨┐P)∧((P∧Q)∨R) ? (P∨┐P)∧(┐P∨Q)∧(P∨R)∧(Q∨R) ? (┐P∨Q∨(R∧┐R)) ∧ (P∨(Q∧┐Q)∨R) ∧ ((P∧┐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∨┐R)) ∧ (P∨Q∨R)∧(P∨┐Q∨R) * * 第四讲 对偶与范式 命题公式的最小联结词组为：{┐, ∨}或{┐, ∧}为了表示更为方便，常包含{┐, ∨, ∧}。 命题定律（P15）除对合律外都成对出现，不同的只是∨, ∧互换，我们把这样的公式称为对偶规律。 对偶式 合取范式：布尔析取(大项)、主合取范式 析取范式：布尔合取(小项)、主析取范式 定义：在给定命题公式中，将联结词 “∨” 换成 “∧”，将“∧” 换成 “∨”，若有特殊变元 F 和 T 也相互取代，所得公式 A* 称为 A 的对偶式。显然，A 是 A* 的对偶式。 写出对偶式： 1. (P∨Q)∧R 2. (P∧Q)∨T 3. ┐(P∨Q)∧(P∨┐(Q∧┐S)) 解： 1. (P∧Q)∨R 2. (P∨Q)∧F 3. ┐(P∧Q)∨(P∧┐(Q∨┐S)) *注：对偶式定义的前提，给定命题公式要由最小联结词组表示的。 P?Q ? ┐P∨Q 的对偶式: ┐P∧Q ? ┐(P∨┐Q) 例： P∧Q 的对偶式: P∨Q; P∨Q 的对偶式: P∧Q P?Q ? (P∧Q)∨(┐P∧┐Q) 的对偶式: (P∨Q)∧(┐P∨┐Q) ? ┐((P∧Q)∨(┐P∧┐Q)) 定理：设A和A*是对偶式，P1, P2, …, Pn是出现在A和A*中的原子变元，则 ┐A(P1,P2,…,Pn) ? A*(┐P1, ┐P2, …, ┐Pn) 定理：设公式A, B的对偶式分别为A*和B*，若 A?B，则 A*?B*。 注：可以看作前一个定理的推论。 注：对原命题(A)的否定等价于对其对偶式(A*)分量的否定。可以看作德·摩根律的推广表示。 定义：一个命题公式称为合取范式，当且仅当它具有型式： A1 ∧ A2 ∧ … ∧ An，(n≥1) 其中 A1, A2, …,An 都是由命题变元或其否定所组成的析取式。 例：(P∨┐Q∨R) ∧ (┐P∨Q) ∧ ┐Q * 一个命题公式的合取范式不是唯一的。 定义：一个命题公式称为析取范式，当且仅当它具有型式： A1 ∨ A2 ∨ … ∨ An，(n≥1) 其中A1,A2,…,An都是由命题变元或其否定所组成的合取式。 例：┐P ∨ (P∧Q) ∨ (P∧┐Q∧R) *一个命题公式的析取范式不是唯一的。 注意：┐P∨┐Q 是析取式； ┐(P∧Q)不是析取式。 判断：(┐Q∧R) ∨ ┐Q ∨ R ┐(P∨Q) ∨ ┐Q (┐P∧┐Q) ∨ ┐Q 是否为析取范式 (1) 将公式中的联结词化归成 ∧, ∨ 及 ┐。 -用最小联结词组的常态表示 (2) 利用德·摩根律将否定符号 ┐直接移到各个命题变元之前。 -使命题公式由命题变元或其否定组成 (3) 利用分配律，结合律将公式化约为合