1.4 析取范式与合取范式

这一小节内容较多，我们由浅入深的来。首先要明白简单析取式和简单合取式的定义。

定义：我们将命题变项及其否定统称作文字\red{文字}文字。 简单析取式\red{简单析取式}简单析取式是仅由有限个文字构成的析取式。 简单合取式\red{简单合取式}简单合取式是仅由有限个文字构成的合取式。

注意：一个简单文字既是简单析取式，又是简单合取式。

例如：

p ， ¬q既是一个简单析取式，又是一个简单合取式p ∨\vee∨ ¬q , p ∨\vee∨ r 均是有两个文字的简单析取式p ∧\wedge∧ q ∧\wedge∧ r , ¬ p∧\wedge∧ q ∧\wedge∧ ¬q 均是有三个文字的简单合取式

性质：

一个简单析取式是重言式当且仅当它同时含某个命题变项及它的否定式。一个简单合取式是矛盾式当且仅当它同时含某个命题变项及它的否定式。

定义：

1. 由有限个简单合取式\red{简单合取式}简单合取式构成的析取式\red{析取式}析取式被称为析取范式\red{析取范式}析取范式

2.由有限个简单析取式\red{简单析取式}简单析取式构成的合取式\red{合取式}合取式被称为合取范式\red{合取范式}合取范式

3. 析取范式与合取范式统称为范式\red{范式}范式

性质：

一个文字既是一析取范式又是一合取范式一个析取范式为矛盾式，当且仅当它的每个简单合取式都是矛盾式一个合取范式是重言式当且仅当它的每一个简单析取式都是重言式

范式存在定理：任一命题公式都存在着与之等值的析取范式与合取范式。

范式，顾名思义即规范的式子。我们想找到对某一命题公式有唯一规范的式子，显然析取范式和合取范式还不能达到我们的目的。所以我们又在此基础上对析取范式和合取范式加一些限制，使得他们的形式是唯一的。即引申出主析取范式和主合取范式。而主析取范式和主合取范式分别是由极小项和极大项组成的。

定义：

极小项：包含公式A中每一个\red{每一个}每一个命题变元或其否定一次且仅一次\red{一次且仅一次}一次且仅一次的简单合取式

极大项：包含公式A中每一个\red{每一个}每一个命题变元或其否定一次且仅一次\red{一次且仅一次}一次且仅一次的简单析取式

主析取范式：设由n个命题变项构成的析取范式中所有的简单合取范式都是极小项，则称该析取范式为主析取范式

主合取范式：设由n个命题变项构成的合取范式中所有的简单析取范式都是极大项，则称该合取范式为主合取范式

1.若AAA的主析取范式中不含任何极小项，则AAA的主析取范式为0\red{0}0

2.若AAA的主合取范式中不含任何极大项，则AAA的主合取范式为1\red{1}1

定理：任何命题公式的主析取范式（主合取范式）都是存在的，并且是唯一\red{唯一}唯一的

对此定理的证明也是主析取范式（主合取范式）的求解过程，如下：

例题：

这个转化过程看似很麻烦，其实求出析取范式后只需一步便可转化为主析取范式。如下：

析取范式中第一项：（¬ p ∧\wedge∧ ¬ q）⇔\Leftrightarrow⇔ m000m_{000}m000​ ∨\vee∨ m001m_{001}m001​ 二进制转十进制为 m0m_{0}m0​ ∨\vee∨ m1m_{1}m1​

析取范式中第二项：（¬ p ∧\wedge∧ ¬ r）⇔\Leftrightarrow⇔ m000m_{000}m000​ ∨\vee∨ m010m_{010}m010​ 二进制转十进制为 m0m_{0}m0​ ∨\vee∨ m2m_{2}m2​

析取范式中第二项：（ p ∧\wedge∧ q ∧\wedge∧ r）⇔\Leftrightarrow⇔ m111m_{111}m111​ 二进制转十进制为 m7m_{7}m7​

∴\therefore∴ 主析取范式为 m0m_{0}m0​ ∨\vee∨ m1m_{1}m1​ ∨\vee∨ m2m_{2}m2​ ∨\vee∨ m7m_{7}m7​ 即 ∑(0,1,2,7)\sum (0,1,2,7)∑(0,1,2,7)

同上，这个也可以简便转化，如下：

合取范式中第一项：（¬ p ∨\vee∨ q）⇔\Leftrightarrow⇔ M100M_{100}M100​ ∧\wedge∧ M101M_{101}M101​ 二进制转十进制为 M4M_{4}M4​ ∧\wedge∧ M5M_{5}M5​

合取范式中第二项：（¬ p ∨\vee∨ r）⇔\Leftrightarrow⇔ M100M_{100}M100​ ∧\wedge∧ M110M_{110}M110​ 二进制转十进制为 M4M_{4}M4​ ∧\wedge∧ M6M_{6}M6​

合取范式中第二项：（ p ∨\vee∨ ¬q ∨\vee∨ ¬r）⇔\Leftrightarrow⇔ M011M_{011}M011​ 二进制转十进制为 M3M_{3}M3​

∴\therefore∴ 主合取范式为 M3M_{3}M3​ ∧\wedge∧ M4M_{4}M4​ ∧\wedge∧ M5M_{5}M5​ ∧\wedge∧ M6M_{6}M6​ 即 ∏(3,4,5,6)\prod (3,4,5,6)∏(3,4,5,6)

因为我们求m时取的是成真赋值，求M时取得是成假赋值。所以m与M的十进制下标在0 ~ 2n−12^n-12n−1这个范围内互补。

主析取范式与主合取范式的用途：

1.判断命题公式是否等价

∵\because∵ 任意命题公式的主析（合）取范式都是存在且唯一的。

∴\therefore∴ 通过比较他们的主析（合）取范式可以判断两公式是否等价，如下：

2.求公式的成真赋值和成假赋值

这个在上面求m与M的过程中已充分体现，不再赘述。

3.判断公式类型

例如：

4.解决实际问题

还记得我们在等值演算那一小节中的压轴题吗？此类题目也可以用今天讲的东西解，但其实思路都是一样的。都是筛除矛盾的式子，如下：

总结：

练习：