离散数学1.7对偶与范式.ppt

* 第一章 命题逻辑（Propositional Logic） 1.7对偶与范式(Dual Normal Form) (3) 将 中重复出现的简单析取式和相同变元都消去; (4)若 中某简单析取式B中不含命题变元Pi, 添加 (Pi?┐Pi), 然后应用分配律展开. 即 B ?B?0?B?(Pi?┐Pi) ?(B?Pi)?(B?┐Pi). 例1：求((P?Q)?R)?P的主合取范式。 例2: 求(P ? Q) ? R的主合取范式. 例3: 求 ┐(P?Q)?(P?Q)的主合取范式. 注：1.命题公式的主析(合)取范式唯一。 2.两命题公式若有相同的主析(合)取范式，则二命题公式等价. * 第一章 命题逻辑（Propositional Logic） 1.7对偶与范式(Dual Normal Form) 例1：求((P?Q)?R)?P的主合取范式。 解: 原式?┐(┐(P∨Q)∨R)∨P ? (P∨Q)∧(┐R∨P ) (合取范式) ?((P∨Q)∨(R ∧┐R ))∧((┐R∨P )∨(Q∧┐Q)) ?(P∨Q∨R)∧(P∨Q∨┐R)∧(P∨Q∨┐R)∧ (P∨┐Q∨┐R) ?(P∨Q∨R)∧(P∨Q∨┐R)∧(P∨┐Q∨┐R) (主合取范式) ?M0∧M1∧M3? * * 离散数学(Discrete Mathematics) * 第一章 命题逻辑（Propositional Logic） 1.7对偶与范式(Dual Normal Form) 1.7.1 对偶式与对偶原理(Dualistic Formula Duality Principle) 1.7.2命题公式的析(合)取范式(The Disjunctive Conjunctive Normal Forms of a Propositional Formula) 1.7.3命题公式的主析(合)取范式(The Principal Disjunctive Conjunctive Normal Form of a Propositional Formula) * 第一章 命题逻辑（Propositional Logic） 1.7对偶与范式(Dual Normal Form) 1.7.1 对偶式与对偶原理(Dualistic Formula Duality Principle) 在第四节(1.4)中我们给出了命题定律(P15 表1-4.8), 其中 多数等价公式都是成对出现的, 每一对公式的不同之处 是将?与?互换,我们把这样的公式称为是对偶的. 定义1.7.1:设命题公式A仅含有联结词┐,?,?,在A中将?,?， F，T分别换以?，?，T，F得出公式A*，则A*称为A的对偶 公式。 说明:(A*)*=A * 第一章 命题逻辑（Propositional Logic） 1.7对偶与范式(Dual Normal Form) 例1.(┐P?(Q?R))*=┐P?(Q?R) ((P?Q)?T)*=((P?Q)?F) 由 P↑Q ?┐(P∧Q) 和 P↓Q ?┐(P∨Q) 可知 (P↑Q)*= P↓Q * 第一章 命题逻辑（Propositional Logic） 1.7对偶与范式(Dual Normal Form) 关于对偶式我们有如下两个定理: 定理1.7.1:设A，A*是对偶式， P1 , P2 ,…,Pn是出现于A和A*中的所有原子变元,则 (1) ┐A(P1 , P2 ,…,Pn )?A*（┐P1 , ┐P2 ,…, ┐Pn） (2) A(┐P1 , ┐P2 ,…, ┐Pn)?┐A*（P1 , P2 ,…,Pn） 证明:因为 ┐(P?Q)?┐P?┐Q ┐(P?Q)?┐P?┐Q 所以┐A(P1 , P2 ,…,Pn )?A*（┐P1 , ┐P2 ,…, ┐Pn） 同理 ┐A*(P1 , P2 ,…,Pn )?A（┐P1 , ┐P2 ,…, ┐Pn） * 第一章 命题逻辑（Propositional Logic） 1.7对偶与范式(Dual Normal Form) 定理1.7.2(对偶原理):设A,B为两个仅含有联结词┐,?,?的命题公式, 若A?B，则A*?B*. 证：设P1 , P2 ,…,Pn是出现于A和B中的所有原子变元. 因为 A(P1 , P2 ,…,Pn)?B(P1 , P2 ,…,Pn) 则 A(P1 , P2 ,…,Pn)?B(P1 , P2 ,…,Pn)永真