主析取范式、主合取范式
| 主析取范式 | |
|---|---|
| 术语名称 | 主析取范式 |
| 英语名称 | principle disjunctive normal form |
| 别名 | PDNF, minterm canonical form |
| 主合取范式 | |
|---|---|
| 术语名称 | 主合取范式 |
| 英语名称 | principle conjunctive norm form |
| 别名 | PCNF, maxterm canonical form |
命题公式可以表示为与其等值的多个析取范式、合取范式，在一定约束下，其中有唯一的主析取范式(principle disjunctive normal form)和唯一的主合取范式(principle conjunctive normal form)。
定义
析取式和合取式的类型
对析取式及合取式：
- 若不含有互补对，称其是纯(pure)的；
- 若不含有互补对且不含有重复，称其是简单的；
- 若不含有互补对、不含有重复，且出现命题公式中的所有命题变元，称其是完全的。
极大项、极小项
| 极大项 | |
|---|---|
| 术语名称 | 极大项 |
| 英语名称 | maxterm |
| 极小项 | |
|---|---|
| 术语名称 | 极小项 |
| 英语名称 | minterm |
- 完全析取式称为极大项(maxterm)。
- 完全合取式称为极小项(minterm)。
注：有些定义中会要求所有命题变元出现次数与指定命题变元顺序一致。 因为一般会默认要按某种自然的顺序书写析取式或合取式中的各项， 这个定义差别完全看作者是否把文字有不同顺序的两个析取式或合取式视作不同的。
大和小可以理解成，越析取越“大”，越接近“真”；越合取越“小”，越接近“假”。 出现互补对的情况下，会直接得到“真”和“假”；而不出现互补对时，对每个极大项（极小项）都不存在比起更接近真（假）的析取式（合取式）。
主析取范式、主合取范式
对任意命题公式，都分别存在且仅存在一个具有以下的形式的公式与其等值：
- 有限个不同极小项的析取称为主析取范式(principle disjuntive normal form, PDNF)。
- 有限个不同极大项的合取称为主合取范式(principle conjuntive normal form, PCNF)。
注：其中有限个包含一个甚至0个的情况。
性质
极大项、极小项编号
- 极大项有且仅有唯一一组命题变元的取值使其为假，极小项有且仅有唯一一组命题变元的取值使其为真。
按一定顺序排列其中的命题变元，并按照取值中假为0、真为1的规则，从高位到低位把这组取值视作二进制编码，这个编码视为这个极大项或极小项的编号。
如在包括 [math]\displaystyle{ P, Q, R }[/math] 三个命题变元的场景下， 极大项 [math]\displaystyle{ \lnot P \lor \lnot Q \lor \lnot R }[/math] 仅在三个命题变元的真值均为真时为假，因此编号为 [math]\displaystyle{ 111_2 = 7_{10} }[/math] ，记作 [math]\displaystyle{ M_7 }[/math] ；极大项 [math]\displaystyle{ \lnot P \lor Q \lor R }[/math] 仅在 [math]\displaystyle{ P }[/math] 为真、 [math]\displaystyle{ Q,R }[/math] 为假时为假，因此编号为 [math]\displaystyle{ 100_2 = 4_{10} }[/math] ，记作 [math]\displaystyle{ M_4 }[/math] 。 反过来， 极小项 [math]\displaystyle{ \lnot P \land \lnot Q \land \lnot R }[/math] 仅在三个命题变元的真值均为假时为真，因此编号为 [math]\displaystyle{ 000_2 = 0_{10} }[/math] ，记作 [math]\displaystyle{ m_0 }[/math] ；极小项 [math]\displaystyle{ \lnot P \land Q \land R }[/math] 仅在 [math]\displaystyle{ P }[/math] 为假、 [math]\displaystyle{ Q,R }[/math] 为真时为真，因此编号为 [math]\displaystyle{ 011_2 = 3_{10} }[/math] ，记作 [math]\displaystyle{ m_3 }[/math] 。
可以看到， [math]\displaystyle{ m_i }[/math] 和 [math]\displaystyle{ M_i }[/math] 互为否定，同时 [math]\displaystyle{ m_i }[/math] 和 [math]\displaystyle{ M_{2^n-1-i} }[/math] 互为对偶。即其有相似的结构，仅改变联结词而不改变否定。
主析取范式、主合取范式记号
首先，
- 对任意命题公式，都存在唯一与其等价的主析取范式；
- 对任意命题公式，都存在唯一与其等价的主合取范式。
由于极大项和极小项有编号，可以对应地编码这些主析取范式和主合取范式。
- 对于有 [math]\displaystyle{ n }[/math] 个命题变元且包含了部分极小项 [math]\displaystyle{ m_{j_1},m_{j_2},\dots,m_{j_p} }[/math] 的主析取范式，将其记为 [math]\displaystyle{ \mathrm{DNF}^n_{m_{j_1},m_{j_2},\dots,m_{j_p}} }[/math] ；
- 对于有 [math]\displaystyle{ n }[/math] 个命题变元且包含了部分极大项 [math]\displaystyle{ M_{j_1},M_{j_2},\dots,M_{j_p} }[/math] 的主合取范式，将其记为 [math]\displaystyle{ \mathrm{CNF}^n_{m_{j_1},m_{j_2},\dots,m_{j_p}} }[/math] 。
主析取范式和主合取范式的关系
主析取范式和主合取范式的下标互补，分别对应着命题公式的全体成真指派和全体成假指派。
求取方式
真值表技术
如果把真值表列出来，并且写出全部 [math]\displaystyle{ 2^n }[/math] 个极小项（极大项）与之对应，可以看到：
- 真值表中的每一个真与主析取范式中出现的每一个极小项，及其记号中的每一个下标，一一对应。当然，真值表中的假也就对应一个主析取范式中未出现的极小项。
- 真值表中的每一个假与主合取范式中出现的每一个极大项，及其记号中的每一个下标，一一对应。当然，真值表中的真也就对应一个主合取范式中未出现的极大项。
这种通过真值表来确定极小项极大项的操作称为真值表技术。
化简
如果变元较多，难以列出真值表，也可以通过展开的方式求取：
- 消去其他联结词（[math]\displaystyle{ \rightarrow }[/math]、[math]\displaystyle{ \leftrightarrow }[/math]）。
- 将否定词通过德摩根律转化为仅作用于原子命题。
- 通过分配律将公式化为析取范式或合取范式的形式。
- 加入子句中缺少的原子命题的互补对并通过分配率展开。
- 进行适当化简。