主析取范式和主合取范式

主析取范式

小项

是n个命题变元的合取式，其中每个变元必出现且仅出现一次（以本身或否定形式），称这个合取式为小项

例：含有两个变元的小项

P ^ Q , P ^ !Q , !P ^ Q , !P ^ !Q

若有n个变元，则有2的n次方个小项

小项编码：

-含有n个变元的小项的角标用n位二进制码表示。

-变元按字母次序排列

-用1表示变元本身，0表示变元的否定形式。

例:m00 <=> !P^!Q , m01 <=> !P ^ Q

m101 <=> P!QR m100 <=> P!Q!R

当列出小项的真值表的时候就会发现，只有真值与小项的下标相同时，小项才为真，其余都为假。

全体小项的析取式位永真式，记为：

Σmi <=> m0 V m1 V… Vm2n-1(2的n次方减一) <=>T

**主析取范式定义：**若一个命题公式的析取范式为A1 V A2 V … V An(n>=1),其中每个Ai（i=1,2,…n）都是小项，则称之为该命题公式的主析取范式

主析取范式求法：

1. 先写出给定公式的析取范式 A1 V A2 V … V An
2. 为使每个Ai都变成小项，对缺少变元的项Ai要补全变元，比如缺变元R，就用“^(R V !R)”的形式补R。
3. 用分配律等公式加以整理

主合取范式

**大项：**是n个命题变元的析取式，其中每个变元必出现且仅出现一次（以本身或否定形式），称该析取式为大项。

大项的编码：大项的编码真好与小项相反

用0表示变元本身，1表示变元的否定形式

如：M00 <=>P V Q M01 <=> P V !Q

M101 <=> !P V Q V !R

每个大项当且仅当其赋值与编码相同时，其真值为F，其余都为T，全体大项的合取式必为永假式。

主合取范式定义：若一个命题公式的析取范式为A1 ^ A2 ^ … ^ An(n>=1),其中每个Ai（i=1,2,…n）都是大项，则称之为该命题公式的主合取范式

主合取范式求法：

1. 先写出给定公式的合取范式 A1 ^ A2 ^ … ^ An
2. 为使每个Ai都变成大项，对缺少变元的项Ai要补全变元，比如缺变元R，就用“v(R ^ !R)”的形式补R。
3. 用分配律等公式加以整理

在真值表中，一个使公式的真值为F的赋值所对应的大项的析取，即为此公式的主合取范式。