第一章命题逻辑（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，┐PQ,P┐P，QP┐P , P┐QR┐S. 简单合取式：仅有有限个命题变项或其否定构成的合取式。 如:P, ┐Q , Q┐P，P┐P，QP┐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）