文档介绍：上下1-7 对偶与范式目的要求: 、关系及性质。 (析取)范式、主合取(析取) 范式的定义。 (析取)范式、主合取(主析取)范式的方法与步骤。重点会求命题公式的主合取(析取)范式上下1-7 --、对偶式在前面介绍的命题定律中,大多都是成对出现的,这些成对出现的定律是对偶性质的体现。利用对偶式的命题定律,可以扩大等价式的个数。 1- 在给定的命题公式中,把联结词?换成?,将?换成?,若有特殊变元 F和T亦互相取代,所得公式称为 A的对偶式,记为 A*。显然, A称为 A *的对偶式上下一、对偶式例1:写出下列命题公式的对偶式 1) (P ∨ Q) ∧ R 2) (P ∧ Q) ∨ T 3) ?(P ∨ Q) ∧(P ∨? (Q ∧? S) (P ∧ Q) ∨ R (P ∨ Q) ∧ F ?(P ∧ Q) ∨(P ∧? (Q ∨? S) 上下一、对偶式 1 -( 对偶定理):设A和A*是对偶式, P 1, P 2, …, P n是出现在 A和A*中的原子变元,则? A(P 1,P 2,…, P n ) ? A*(? P 1, ? P 2, …, ?P n) A( ? P 1, ? P 2, …, ?P n ) ?? A* (P 1, P 2, …, P n ). 证明: 利用数学归纳法 1 - 设P 1, P 2, …, P n是出现在 A和B中的所有原子变元,如果 A ? B,则 A*? B* 上下二、公式的标准型--范式同一命题公式可以有各种相互等价的表达形式,为了把命题公式规范化,需要讨论命题公式的标准型。例如: P ? Q ?(P→Q)∧(Q→P) ?(P∧Q)∨(?P∧?Q) 上下简单合取式:除联结词∧外不出现其他任何二元联结词的命题公式,其中每个命题变元或其否定称为合取项。如P,?Q,P∧Q,?P∧Q∧R 简单析取式:除联结词∨外不出现其他任何二元联结词的命题公式,其中每个命题变元或其否定称为析取项。如P,?Q, P ∨ Q,?P∨Q∨?R 注意: 一个命题变元或其否定既可以是简单合取式, 也可以是简单析取式。上下 1- 一个命题公式 A称为合取范式,当且仅当 A 表示为简单析取式的合取,即 A ?A 1 ∧A 2 ∧…∧A n , (n ≥1) 其中 A 1,A 2 ,…,A n为简单析取式。例如: (?P∨Q∨ R)∧(?P∨Q)∧? Q为合取范式。若干个简单析取式的合取构成合取范式。上下定义 1- 一个命题公式 A称为析取范式,当且仅当 A 表示为简单合取式的析取,即 A ?A 1 ∨A 2 ∨…∨A n , (n ≥1) 其中 A 1,A 2 ,…,A n为简单合取式。例如: ?P∨( P ∧ Q)∨(P∧? Q ∧R)为析取范式。若干个简单合取式的析取构成析取范式。上下 2. 范式的求法: 任何一个命题公式,求它的合取范式或析取范式, 可以通过下面三个步骤进行: (1)使用命题定律,消去公式中除∧、∨及?外的所有出现的?、?等联结词。(2)利用德?摩根律将否定符号?直接移到各个命题变元之前。(3)利用分配律、结合律将公式划为合取范式或析取范式。