|
一、范式
为叙述方便, 先定义几个术语。
简单命题P及其否定式 P统称文字。
一些文字的合取称合取式。
一些文字的析取称析取式(也称子句)。
P与 P称为互补对。即简单命题与其否定式称为互补对。合取称为积,
析取称为和。由一些简单命题或其否定的合取组成的公式称为基本积。由一些简单命题或其否定的析取组成的公式称基本和。
如P, P,
P∧Q,
P∧ Q∧ P都是合取式,
而P, P,
P∨Q, P∨Q∨ Q都是析取式。
1. 范式存在定理 任一命题公式都存在有与之等值的合取范式和析取范式。
可通过求范式的具体步骤, 来认识范式存在定理的正确性。
2. 求范式的步骤
对一个已给的公式, 可按下述步骤求得该公式的合取范式和析取范式。
(1) 消去已给公式中的联结词→和 。
(2) 重复使用摩根律和双重否定律, 把否定词内移到直接作用于命题变项上。
(3) 重复使用分配律。
3. 求范式举例
例1: 求 (P∨Q) (P∧Q)的析取范式。
例2: 求 (P∨Q) (P∧Q)的合取范式
4. 范式可用来判断重言式和矛盾式
若一公式的合取范式中,所有的析取式都至少含有一个互补对,则该范式及相应的公式必为重言式。
若一公式的析取范式中,所有的合取式都至少含有一个互补对,则该范式及相应的公式必为矛盾式。
|
|