1.4 范式

1.4.1 析取范式和合取范式

范式是命题公式的规范表示形式，又称为标准形。一个命题公式可以有不同的等价式，因而为命题公式的研究带来一定的困难。把命题公式化成规范的标准形可为命题公式的研究和应用带来方便。

定义1.4.1 一个命题公式具有形式A₁∨A₂∨…∨A_n（n≥1），其中A₁，A₂，…，A_n都是由命题变元或其否定所组成的合取式，则称该命题公式为析取范式。

例如，给定命题变元p、q和是析取范式。

定义1.4.2 一个命题公式具有形式B₁∧B₂∧…∧B_n（n≥1），其中B₁，B₂，…，B_n都是由命题变元或其否定所组成的析取式，则称该命题公式为合取范式。

例如，给定命题变元p、q和r，是合取范式。

定理1.4.1（范式存在定理） 任意一个命题公式都存在着与之等价的析取范式和合取范式。

证明 设G为任意一个公式。

1）消去、∧、∨以外的联结词。

2）将否定联结词内移或消去。

3）利用分配律、交换律和结合律等将公式归纳为析取范式和合取范式。

通过上面的3个步骤可以求出与G等价的析取范式和合取范式。因此，任意一个命题公式都存在着与之等价的析取范式和合取范式。以上也是求析取范式和合取范式的步骤。

◀

例1.4.1 求命题公式（p∧（p→q））∨q的析取范式和合取范式。

解

按析取范式的定义，、（p∧q）∨q、q都是原公式的析取范式，也就是说，与某个命题公式等值的析取范式是不唯一的。同理，与某个命题公式等值的合取范式也是不唯一的，如上例中，（p∨q）∧q、和q都是合取范式。因而析取范式和合取范式不能作为命题公式的标准形。下面介绍主范式的概念。可以证明任意命题公式的主范式都是唯一的，因而可以用与命题公式等值的主范式作为它的标准形。