析取范式与合取范式分析.ppt

一个公式在等值的意义下，可以有许多种不同的形式。 反过来，几个形式上完全不同的公式可能是同一个公式（在等值的意义下）。 那么，在一个公式的诸多表示形式中，有没有一种标准的形式呢？更进一步的说，有没有一种标准形式是一个公式的唯一表示形式呢？ 第二章 命题逻辑等值演算 定义2.1（文字） 命题变项及其否定统称为文字。 定义2.2（简单析取式、简单合取式） 仅由有限个文字构成的析取式（或单个文字）称作简单析取式。 仅由有限个文字构成的合取式（或单个文字）称作简单合取式。 注意：单个文字既是简单析取式，又是简单合取式 例：p，q，┐p，┐q，p∨┐q，p∨┐q∨r为简单析取式 p，q，┐p，┐q，p∧┐q，p∧┐q∧r为简单合取式 析取范式、合取范式 定义2.3 （1）由有限个简单合取式的析取构成的析取式称为析取范式。 （2）由有限个简单析取式的合取构成的合取式称为合取范式。 （3）析取范式和合取范式统称为范式。 由定义可知： 若A1，A2，…，An为简单合取式，则A1∨A2∨…∨An为析取范式 例如：p∨（p∧q）∨（p∧┐q∧r）为析取范式 若A1，A2，…，An为简单析取式，则A1∧A2∧…∧An为合取范式 例如：p∧（p∨q）∧（p∨┐q∨r）为合取范式 析取范式、合取范式 定义2.3 （1）由有限个简单合取式的析取构成的析取式称为析取范式。 （2）由有限个简单析取式的合取构成的合取式称为合取范式。 （3）析取范式和合取范式统称为范式。 析取范式和合取范式的性质：（定理2.2） （1）一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式。 （2）一个合取范式是重言式当且仅当它的每个简单析取式都是重言式。 （3）对于每个命题公式，都有与之等值的析取范式和合取范式。 范式的构造步骤（p24）： 例：求（p→q）?r的析取范式和合取范式。 解： （1）合取范式 （p→q）?r =（┐p∨q）?r （消去→） =（（┐p∨q）→r）∧（r→（┐p∨q）)（消去?） =（┐（┐p∨q）∨r）∧（┐r∨（┐p∨q）） （消去→） =（（p∧┐q）∨r）∧（┐p∨q∨┐r） （德莫根律将┐内移） =（p∨r）∧（┐q∨r）∧（┐p∨q∨┐r） （∨对∧的分配律） （2）析取范式 （p→q）?r =（（p∧┐q）∨r）∧（┐p∨q∨┐r） (∧对∨的分配律) 练习 求下列公式的析取范式和合取范式。 （1）（p→q）→r （2）（p→q）∧（q→r） 定义（极小项）：在共含有n个命题变项p1，p2，…，pn的简单合取式 中，每个命题变项pi或其否定式┐pi，均出现且两者仅出现一个，并且按命题变项的下标排列（或字母按字典序列），这样的简单合取式称为极小项。 例如：对于含三个命题变项p、q、r的公式 p∧┐q∧r，┐p∧q∧┐r是极小项 p∧┐q不是极小项，其中没出现r p∧┐p∧┐r不是极小项，p，┐p同时出现 关于极小项的两点说明 关于极小项的两点说明 例：3个命题变项p，q，r可形成的极小项。 定义（主析取范式）：如果析取范式中所有的简单合取式都是极小项，则称该析取范式为主析取范式。 例如：对于含三个命题变项p、q、r的公式 （1） p∨（┐p∧q） （2）（p∧q）∨（┐p∧r） （3）（p∧┐q∧r）∨（┐p∧q∧┐r） 显然公式（1）和（2）不是主析取范式。而公式（3）是主析取范式。 定理（主析取范式唯一存在性）： 任何一个命题公式均存在唯一与之等值的主析取范式。 求给定命题公式A的主析取范式的步骤 （1）将公式A化为析取范式A’ （2）若A’的某简单合取式B不是极小项，即B中缺命题变项pi，也不含它的否定， 则对B做如下等值变换： B=B∧（pi∨┐pi）=（B∧pi）∨（B∧┐pi） （3）用幂等律将重复的极小项消去，即