天津理工大学：《离散数学》课程教学资源（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

第一章命题逻辑（PropositionalLogic）1.5对偶与范式(Dual&NormalForm）2命题公式的析（合）取范式从前面的讨论可知，存在大量互不相同的命题公式，实际上互为等价，因此，有必要引入命题公式的标准形式使得相互等价的命题公式具有相同的标准形式。这无疑对判别两个命题公式是否等价以及判定命题公式的类型是一种好方法，同时对命题公式的简化和推证也是十分有益的2026/3/156计算机科学与工程

2026/3/15 计算机科学与工程系 6 第一章 命题逻辑（Propositional Logic） 1.5对偶与范式(Dual & Normal Form) 2 命题公式的析(合)取范式 从前面的讨论可知,存在大量互不相同的命题公式，实 际上互为等价,因此,有必要引入命题公式的标准形式, 使得相互等价的命题公式具有相同的标准形式。这无 疑对判别两个命题公式是否等价以及判定命题公式的 类型是一种好方法,同时对命题公式的简化和推证也是 十分有益的

第一章命题逻辑（PropositionalLogic）1.5对偶与范式(Dual&NormalForm）定义1.18简单析取式：仅有有限个命题变项或其否定构成的析取式如:P， PvQ,Pv P,QvPv P, Pv QvRv S.简单合取式：仅有有限个命题变项或其否定构成的合取式如:P, Q,Q^ P，P^ P,QP^ P,p^ Q^R从定义不难看出（1）一个简单析取式是重言式当且仅当它同时含有某个命题变元及其否定式。（2）一个简单合取式是矛盾式当且仅当它同时含有某个命题变元及其否定式，2026/3/15计算机科学与工程系

2026/3/15 计算机科学与工程系 7 第一章 命题逻辑（Propositional Logic） 1.5对偶与范式(Dual & Normal Form) 定义1.18 简单析取式：仅有有限个命题变项或其否定构成的析取式。 如:P，┐PQ,P┐P，QP┐P , P┐QR┐S. 简单合取式：仅有有限个命题变项或其否定构成的合取式。 如:P, ┐Q , Q┐P，P┐P，QP┐P, p∧┐Q∧R. 从定义不难看出: （1）一个简单析取式是重言式当且仅当它同时含有某个命 题变元及其否定式。 （2）一个简单合取式是矛盾式当且仅当它同时含有某个命 题变元及其否定式

第一章命题逻辑（PropositionalLogic）1.5对偶与范式（Dual&NormalForm）定义1.19:(1)析取范式：一个命题公式称为析取范式,当且仅当它具有形式：AiVA2V......VAn(n大于等于1)其中Ai(i-1,2,3,...n)为简单合取式。如: PV- Q, (P ^ Q) V(P^- Q^R),Q^- P.(2)合取范式：一个命题公式称为合取范式,当且仅当它具有形式：A1^A2^.....^An(n大于等于1)其中Ai(i-1,2,3,...n)为简单析取式。如: PV- Q, (PV Q) ^(PV- Q VR),Q^ P.(3)范式：析取范式与合取范式统称为范式。显然，任何合(析)取范式的对偶式是析(合)取范式2026/3/158计算机科学与工程系

2026/3/15 计算机科学与工程系 8 第一章 命题逻辑（Propositional Logic） 1.5对偶与范式(Dual & Normal Form) 定义1.19: (1)析取范式：一个命题公式称为析取范式,当且仅当 它具有形式: A1∨A2∨.∨An (n大于等于1) 其中Ai(i=1,2,3,.n)为简单合取式. 如：P∨┐Q ，(P ∧ Q) ∨(P ∧┐Q∧R), Q∧┐P. (2)合取范式：一个命题公式称为合取范式,当且仅当 它具有形式: A1∧A2∧.∧An (n大于等于1) 其中Ai(i=1,2,3,.n)为简单析取式. 如：P∨┐Q ，(P ∨ Q) ∧(P ∨┐Q ∨R), Q∧┐P. (3)范式：析取范式与合取范式统称为范式。 显然, 任何合(析)取范式的对偶式是析(合)取范式

第一章命题逻辑（PropositionalLogic）1.5对偶与范式(Dual&NormalForm)析取范式与合取范式的性质：(1)一个析取范式是矛盾式,当且仅当它的每一个简单合取式都是矛盾式(2)一个合取范式是重言式,当且仅当它的每一个简单析取式都是重言式定理1.4 (范式存在定理)任一个命题公式都存在着与之等价的析取范式与合取范式。2026/3/159计算机科学与工程系

2026/3/15 计算机科学与工程系 9 第一章 命题逻辑（Propositional Logic） 1.5对偶与范式(Dual & Normal Form) 析取范式与合取范式的性质: (1) 一个析取范式是矛盾式,当且仅当它的每一个简 单合取式都是矛盾式; (2)一个合取范式是重言式,当且仅当它的每一个简 单析取式都是重言式. 定理1. 4 (范式存在定理) 任一个命题公式都存在着与之等价的析取范式与 合取范式

第一章命题逻辑（PropositionalLogic）1.5对偶与范式(Dual&NormalForm）求命题公式的范式的基本步骤：(1)将公式中的联结词化归成一，入及V(2)将否定联结词消去或内移到各命题变元之前。利用下列等价式：77A台A(AVB)A^B(A^B)AVB（3）利用分配律、结合律将公式转化为合取范式或析取范式。CA(AVB)α (CAA) V (CA B)CV(A^B)(CVA)A(CVB)2026/3/1510算机科学与工程系

2026/3/15 计算机科学与工程系10 第一章 命题逻辑（Propositional Logic） 1.5对偶与范式(Dual & Normal Form) 求命题公式的范式的基本步骤： （1）将公式中的联结词化归成┐,及. （2）将否定联结词消去或内移到各命题变元之前。 利用下列等价式： ┐┐A A ┐( A∨B)  ┐A∧┐B ┐( A∧B)  ┐A∨┐B （3）利用分配律、结合律将公式转化为合取范式或析 取范式. C ∧( A ∨ B) （C∧ A）∨（C ∧ B） C ∨( A ∧ B) （C ∨ A）∧（C ∨ B）