范式

基本概念

文字

命题变项及其否定的总称。

简单析取式

有限个文字构成的析取式。如 $p$ , $\neg p \lor q$ , $p \lor q \lor r$ 。

简单合取式

有限个文字构成的合取式。如 $p$ , $p \land \neg q$ , $p \land q \land r$ 。

析取范式

由有限个简单合取式组成的析取式。如 $(p \land \neg q) \lor (\neg p \land q) \lor (p \land q \land r)$ 。

合取范式

由有限个简单析取式组成的合取式。如 $(p \lor q) \land (\neg p \lor q) \land (p \lor \neg q \lor r)$ 。

范式

析取范式与合取范式的总称。

说明

单个文字既是简单析取式，又是简单合取式。
形如 $p \land q \land r$ , $\neg p \lor q \lor r$ 的公式既是析取范式，又是合取范式。

范式性质定理

定理2.1

一个简单析取式是重言式当且仅当它同时含有某个命题变项和它的否定式（如 $p \lor q \lor \neg p$ ）。
一个简单合取式是矛盾式当且仅当它同时含有某个命题变项和它的否定式（如 $p \land q \land \neg p$ ）。

定理2.2

一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式。
一个合取范式是重言式当且仅当它的每个简单析取式都是重言式。

极小项与极大项

定义2.4 在含有 $n$ 个命题变项的简单合取式（简单析取式）中，若每个命题变项均以文字的形式在其中出现且仅出现一次，而且第 $i$ 个文字出现在左起第 $i$ 位上（ $1 \leq i \leq n$ ），称这样的简单合取式（简单析取式）为极小项（极大项）。

几点说明

$n$ 个命题变项有 $2^{n}$ 个极小项和 $2^{n}$ 个极大项（每个命题变项在极小项（极大项）中以原形或者否定形式出现且仅出现一次）。
$2^{n}$ 个极小项（极大项）均互不等值（每个极小项有且仅有一个成真赋值）。
用 $m_{i}$ 表示第 $i$ 个极小项，其中 $i$ 是该极小项成真赋值的十进制表示。用 $M_{i}$ 表示第 $i$ 个极大项，其中 $i$ 是该极大项成假赋值的十进制表示。 $m_{i}$ , $M_{i}$ 称为极小项（极大项）的名称。

$m_{i}$ 与 $M_{i}$ 的关系

$\neg m_{i} \Leftrightarrow M_{i}$ ， $\neg M_{i} \Leftrightarrow m_{i}$

主范式

主析取范式

由极小项构成的析取范式。

主合取范式

由极大项构成的合取范式。

简单来说，就是主析取范式角标二进制代表公式的成真赋值，主合取范式角标二进制代表公式的成假赋值，于是两者角标的并集为所有 n 二进制数，交集为空集。

应用

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

设公式 $A$ 含 $n$ 个命题变项， $A$ 的主析取范式有 $s$ 个极小项，则 $A$ 有 $s$ 个成真赋值，它们是极小项下标的二进制表示，其余 $2^{n} - s$ 个赋值都是成假赋值。

2. 判断公式的类型

设 A 含 n 个命题变项：

A为重言式 $\Leftrightarrow A$ 的主析取范式含全部 2ⁿ个极小项 $\Leftrightarrow A$ 的主合取范式不含任何极大项，记为 1。
A为矛盾式 $\Leftrightarrow A$ 的主合取范式含全部 2ⁿ个极大项 $\Leftrightarrow A$ 的主析取范式不含任何极小项，记为 0。
A为非重言式的可满足式 $\Leftrightarrow A$ 的主析取范式中至少含一个、但不是全部极小项 $\Leftrightarrow A$ 的主合取范式中至少含一个、但不是全部极大项。

3. 判断两个公式是否等值

用主析取范式可以判断每一组公式是否等值。

由主析取范式确定主合取范式

设公式 A含 n个命题变项，A的主析取范式含 s（0<s<2ⁿ）个极小项，即 $A = m_{i 1} \lor m_{i 2} \lor$ … $\lor m_{i s}$ 。没出现的极小项为 mⱼ₁, mⱼ₂,…, mⱼₖ，它们的角标的二进制表示为 ┐A的成真赋值，因而 ┐A的主析取范式为 $┐ A = m_{j 1} \lor m_{j 2} \lor$ … $\lor m_{jk}$ 。由定理可知： $A \Leftrightarrow ┐┐ A \Leftrightarrow ┐ (m_{j 1} \lor m_{j 2} \lor$ … $\lor m_{jk}) \Leftrightarrow ┐ m_{j 1} \land ┐ m_{j 2} \land$ … $\land ┐ m_{jk} \Leftrightarrow M_{j 1} \land M_{j 2} \land$ … $\land M_{jk}$ 这就由公式的主析取范式直接求出它的主合取范式。

真值函数与联结词完备集

定义2.6称 $F : 0, 1^{n} \to 0, 1$ 为 n元真值函数。 ${0,1}ⁿ = {00$ …0, 00…1,…, 11…1}，包含 2ⁿ个长为 n的 0,1符号串。共有 2²ⁿ个 n元真值函数。

任何一个含 n 个命题变项的命题公式 A 都对应惟一的一个 n 元真值函数，恰好为 A 的真值表。等值的公式对应的真值函数相同。

定义2.7设 S是一个联结词集合，如果任何 n（ $n \geq 1$ ）元真值函数都可以由仅含 S中的联结词构成的公式表示，则称 S是联结词完备集。若 S是联结词完备集，则任何命题公式都可由 S中的联结词表示。

**定理 $2.6 * * S = ┐, \land, \lor$ 是联结词完备集（由范式存在定理可证）。

与非式和或非式

定义2.8 设 p, q 为两个命题： $- ┐ (p \land q)$ 称作 p与 q的与非式，记作 p↑q，即 $p ↑ q \Leftrightarrow ┐ (p \land q)$ ，↑称为与非联结词。 $- ┐ (p \lor q)$ 称作 p与 q的或非式，记作 p↓q，即 $p ↓ q \Leftrightarrow ┐ (p \lor q)$ ，↓称为或非联结词。