天津理工大学：《离散数学》课程教学资源（PPT课件）第一章 命题逻辑 Propositional Logic 1.5 对偶与范式（Dual & Normal Form）

第一章命题逻辑（Propositional Logic）1.5对偶与范式(Dual&NormalForm）1 对偶式与对偶原理2命题公式的析(合)取范式3命题公式的主析(合)取范式2026/3/15计算机科学与工程系

2026/3/15 计算机科学与工程系 1 第一章 命题逻辑（Propositional Logic） 1.5对偶与范式(Dual & Normal Form) 1 对偶式与对偶原理 2 命题公式的析(合)取范式 3 命题公式的主析(合)取范式

第一章命题逻辑（PropositionalLogic）1.5对偶与范式（Dual&NormalForm）1对偶式与对偶原理(DualisticFormula&DualityPrinciple)在第三节中我们给出了命题定律其中多数等价公式都是成对出现的，每一对公式的不同之处是将入与v互换，我们把这样的公式称为是对偶的。定义1.17:设命题公式A仅含有联结词，^,V,在A中将v换成入，^换成V，若A中含有F或T，就将F，T分别换以T，F得出公式A*，则A*称为A的对偶式。说明：（A*)*=A例1. ( Pv(Q^R))*= P^(QvR)((P^Q)^1)*=((PvQ)v0)由 P↑Q台(PΛQ)和 PIQ台 (PVQ)可知(P↑Q)*= PIQ2026/3/152计算机科学与工程系

2026/3/15 计算机科学与工程系 2 第一章 命题逻辑（Propositional Logic） 1.5对偶与范式(Dual & Normal Form) 1 对偶式与对偶原理(DualisticFormula & Duality Principle) 在第三节中我们给出了命题定律其中多数等价公式都是成 对出现的, 每一对公式的不同之处是将与互换,我们把 这样的公式称为是对偶的. 定义1.17:设命题公式A仅含有联结词┐,,,在A中将换 成，换成 ，若A中含有F或T，就将F，T分别换以T， F得出公式A * ，则A *称为A的对偶式。 说明:(A *) *=A 例1.(┐P(QR))*=┐P(QR) ((PQ)1)*=((PQ)0) 由 P↑Q ┐(P∧Q) 和 P↓Q ┐(P∨Q) 可知 (P↑Q)*= P↓Q

第一章命题逻辑（PropositionalLogic）1.5对偶与范式(Dual&NormalForm）关于对偶式我们有如下两个定理：定理1.2:设A，A*是对偶式，Pi,P2..,P,是出现于A和A*中的所有命题变项，则(1) A(P1, P2...,Pn )αA* (- Pi, P2..., Pn)(2) A(- Pi, P2...., P,)台 A* (Pi, P2...,P.)证明:因为 (P^Q)台( PV Q) (PVQ)P Q所以- A(P1, P2....,P, )台A* (- P1, P2..., P.)同理 A*(Pi, P2...,Pn )台A ( P1,P2...,P,)2026/3/153计算机科学与工程系

2026/3/15 计算机科学与工程系 3 第一章 命题逻辑（Propositional Logic） 1.5对偶与范式(Dual & Normal Form) 关于对偶式我们有如下两个定理: 定理1.2:设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）

第一章命题逻辑（PropositionalLogic）1.5对偶与范式（Dual&NormalForm）定理1.3(对偶原理):设A,B为两个仅含有联结词一，^，V的命题公式,若A台B，则A*台B*.证：设P1,P2..…,P,是出现于A和B中的所有原子变元因为 A(P1, P2...,P,)B(P1, P2...,P,)则A(Pi,P2...,P,)<B(Pi, P2...,P,)永真.故A(- Pi, P2...., P,)B( Pi, P2..., P,)永真.又由定理1.2得 A*(P1,P2....,Pn) B*(P1, P2....,Pn)因此 A*B*2026/3/154计算机科学与工程系

2026/3/15 计算机科学与工程系 4 第一章 命题逻辑（Propositional Logic） 1.5对偶与范式(Dual & Normal Form) 定理1.3(对偶原理):设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)永真. 故 A(┐P1 , ┐P2 ,., ┐Pn)B(┐P1 , ┐P2 ,., ┐Pn) 永真. 又由定理1.2得 ┐A *(P1 , P2 ,.,Pn)┐B*(P1 , P2 ,.,Pn ) 因此 A *B *

第一章命题逻辑（PropositionalLogic）1.5对偶与范式(Dual&NormalForm）例1：因为：Pv (P^Q)<←P由对偶原理：P^(PVQ) 台P例2： 若A台1 则 A*台(1)*即 A*0.例3：设A为 (P^Q)v( Pv( PvQ)),B为 PvQ且A台B,则 A*台B* P^Q2026/3/155计算机科学与工程系

2026/3/15 计算机科学与工程系 5 第一章 命题逻辑（Propositional Logic） 1.5对偶与范式(Dual & Normal Form) 例1：因为： P(PQ)P 由对偶原理: P(PQ) P 例2: 若A1 则 A *(1)* 即 A *0. 例3: 设A为 (PQ)(┐P(┐PQ)),B为┐PQ, 且AB,则 A *B *┐PQ