主析取范式、主合取范式
| 主析取范式 | |
|---|---|
| 术语名称 | 主析取范式 |
| 英语名称 | principal disjunctive normal form |
| 别名 | PDNF, minterm canonical form, canonical disjunctive normal form, CDNF |
| 主合取范式 | |
|---|---|
| 术语名称 | 主合取范式 |
| 英语名称 | principal conjunctive normal form |
| 别名 | PCNF, maxterm canonical form, canonical conjunctive normal form, CCNF |
命题公式可以表示为与其等值的多个析取范式、合取范式， 可增加指定约束得到其中唯一的主析取范式(principal/canonical disjunctive normal form, PDNF, CDNF)和唯一的主合取范式(principal/canonical conjunctive normal form, PCNF, CCNF)作为其唯一标准形式，也合称主范式。 主范式在重言等价意义下是唯一的，为每个命题公式提供了规范的表示形式。
定义
析取式和合取式的类型
对析取式、合取式（定义见析取范式、合取范式#定义）：
- 若不含有互补对，称其是纯(pure)的；
- 若不含有互补对，且不含有重复文字，称其是简单(simple)的；
- 若不含有互补对，不含有重复文字，且出现命题公式中的所有命题变元，称其是完全(full)的。
极大项、极小项
| 极小项 | |
|---|---|
| 术语名称 | 极小项 |
| 英语名称 | minterm |
| 极大项 | |
|---|---|
| 术语名称 | 极大项 |
| 英语名称 | maxterm |
- 完全合取式，即对所有命题变元，任意一对互补文字在其中共出现且仅出现一次的合取式，称为极小项(minterm)，记作 [math]\displaystyle{ m_i }[/math] ，其中 [math]\displaystyle{ i }[/math] 是极小项编号。
- 完全析取式，即对所有命题变元，任意一对互补文字在其中共出现且仅出现一次的析取式，称为极大项(maxterm)，记作 [math]\displaystyle{ M_i }[/math] ，其中 [math]\displaystyle{ i }[/math] 是极大项编号。
注：
- 极大项和极小项的“编号”见后文“性质”部分。
- 有些定义中会要求形式上所有这些命题变元出现次数与指定命题变元顺序一致。
- 因为一般会默认要按某种自然的顺序书写析取式或合取式中的各项，差别在于作者是否将文字顺序不同的两个析取式或合取式是否视为形式上不同的。
- 极大和极小可以理解成极大元、极小元意义上的极大极小：越析取越接近上方的“真”，越“大”；越合取越接近下方的“假”，越“小”。
- 出现互补对的情况下，会直接得到“真”和“假”；不出现互补对时，对每个极大项（极小项）都比去除某个文字的项更接近真（假）。
主析取范式
有限个不同极小项的析取称为主析取范式(principal disjuntive normal form, PDNF)， 形如 [math]\displaystyle{ m_{i_1} \lor m_{i_2} \lor \cdots \lor m_{i_k} }[/math] ，其中每个 [math]\displaystyle{ m_i }[/math] 是不同的极小项。
注：
- 主析取范式可以是单个极小项。
- 主析取范式可以是零个极小项，空主析取范式定义为假。
主合取范式
有限个不同极大项的合取称为主合取范式(principle conjuntive normal form, PCNF)， 形如 [math]\displaystyle{ M_{i_1} \land M_{i_2} \land \cdots \land M_{i_k} }[/math] ，其中每个 [math]\displaystyle{ M_j }[/math] 是不同的极大项。
形式文法角度
不限制文字顺序及项顺序时，主析取范式和主合取范式是上下文有关文法，生成式较复杂，不能通过简单的形式表述。
限制文字顺序及项的顺序时，是上下文无关文法。但是需要通过大量可选值按顺序表述每个项的出现，不便于写出。
性质
极大项、极小项编号
极大项、极小项特征
定理：
- 极小项有且仅有唯一一个成真指派；
- 极大项有且仅有唯一一个成假指派。
编号规则
按一定顺序排列其中的命题变元，按假为 0 、真为 1 映射到二进制位，从高位到低位视作二进制数，将这个数视为这个极大项或极小项的编号。
也可以表达为将原子命题为 1 ，原子命题的否定为 0 映射到二进制位。
举例：在包括 [math]\displaystyle{ P, Q, R }[/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{ \lnot P \land \lnot Q \land \lnot R }[/math] 对应赋值 000 ，因此记作 [math]\displaystyle{ m_0 }[/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{ P \lor Q \lor R }[/math] 对应赋值 111 ，因此记作 [math]\displaystyle{ M_7 }[/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{ n }[/math] 个变元的公式 [math]\displaystyle{ \phi }[/math] ：
- 主析取范式： [math]\displaystyle{ \bigvee_{\sigma \vDash \phi} m_{\sigma} }[/math] 。
- 主合取范式： [math]\displaystyle{ \bigwedge_{\sigma \nvDash \phi} M_{\sigma} }[/math] 。
其中 [math]\displaystyle{ \sigma }[/math] 遍历所有可能的真值指派。
变换法
如果变元较多，难以列出真值表，也可以通过展开的方式求取：
- 首先转换为一般的析取范式或合取范式。
- 消去其他联结词（ [math]\displaystyle{ \rightarrow }[/math] 、 [math]\displaystyle{ \leftrightarrow }[/math] ）。
- 将否定词通过德摩根律转化为仅作用于原子命题。
- 通过分配律将公式化为析取范式或合取范式的形式。
- 向每个合取项或析取项中补充缺少的原子命题的互补对，通过分配律展开。
- 进行适当化简，消除重复项和矛盾项。