关于“范式”的无用思考

$\mathscr{Author:CoolWind}$

写主范式真的好烦啊！鼠鼠不想学离散啦！

0、需要用到的知识！

0.1 常用的等值演算

$$\begin{align}p \to q &\Leftrightarrow \neg p \vee q\\p \leftrightarrow q &\Leftrightarrow (p \land q)\vee (\neg p \land \neg q)\\p \oplus q &\Leftrightarrow (\neg p \vee q)\land (p \vee \neg q)\end{align}$$

0.2 运算符优先级

​ 运算符优先级从高到低排列为：

$$\neg , \land , \vee , \oplus , \to , \leftrightarrow$$

​ 同一个联结词连续多次出现且无括号则按从左至右的顺序运算，

​ 在满足运算次序不变的情况下，运用联结词的优先级规则可以减少合式公式括号。

0.3 文字

​ 原子公式和原子公式的否定统称为文字。如$p$与$\neg p$均被称为文字。

0.4 简单析取式和简单合取式

​ 设n为正整数，$A_1,…,A_n$都是文字，则$A_1 \vee … \vee A_n$称之为简单析取式，$A_1 \land … \land A_n$称之为简单合取式。

1、什么是范式？

​ 所谓“范式”，就是一种十分“规范”的式子。这样的式子是任意公式的一种“标准”形式，而通过这种形式，我们能十分容易的判断出两个看起来不同的公式是否等价。

​ 例如，完全不同的两个式子：$p \oplus q $与 $\neg (p \leftrightarrow q) $ 却是等价的，通过等值演算，可得出以下发现：

$$\begin{align} p \oplus q &\Leftrightarrow (p \land \neg q)\vee (\neg p \land q)\\ &\Leftrightarrow (p \vee (\neg p \land q))\land (\neg q \vee (\neg p \land q))\\ &\Leftrightarrow ((p\vee \neg p )\land (p \vee q))\land ((\neg q \vee \neg p)\land (\neg q \vee q))\\ &\Leftrightarrow (p \vee q) \land (\neg p \vee \neg q)\\ \\ \neg (p \leftrightarrow q) &\Leftrightarrow \neg ((p \land q)\vee (\neg p \land \neg q))\\ &\Leftrightarrow \neg (p \land q)\land \neg (\neg p \land \neg q)\\ &\Leftrightarrow (p \vee q)\land(\neg p \vee \neg q)\\ \end{align}$$

​ （引自《离散数学》第三版1.6节）

​ 挖！居然相等诶！好简单的计算过程！

​ 可以发现，等值演算的最后两个看似不相等的公式得到的值是一样的，所以这两个公式是等价的。那么$(p \vee q)\land(\neg p \vee \neg q)$这个公式就被称为“范式”，通过这个“规范的式子”可以知道以上两个公式是完全等价的。

​ 实际上，范式分为析取范式和合取范式。

​ 设n为正整数，$A_1,…,A_n$都是简单合取式，则$A_1 \vee … \vee A_n$称之为析取范式；$A_1,…,A_n$都是简单析取式，$A_1 \land … \land A_n$称之为合取范式。

2、什么是主范式？

2.1 主范式的简单定义

​ 在将同一个式子进行等值演算的过程中，我们可以看到，能够产生很多种等价但是看起来完全不相同的析取范式和合取范式。例如：

$$\begin{aligned} & (p \vee q \rightarrow r) \rightarrow p \\ \Leftrightarrow & \neg(\neg(p \vee q) \vee r) \vee p \\ \Leftrightarrow & ((p \vee q) \wedge \neg r) \vee p \\ \Leftrightarrow & (p \vee q \vee p) \wedge(\neg r \vee p) &合取范式\\ \Leftrightarrow & (p \vee q) \wedge(\neg r \vee p) &合取范式\\ \Leftrightarrow & p \vee(q \wedge \neg r) &析取范式 \\ \Leftrightarrow & p \vee(q \wedge \neg r) \vee(q \wedge \neg q) &析取范式\end{aligned}$$

​ （引自《离散数学》第三版1.6）

​ 所以，为了能够用唯一的一个式子来“规范”公式，因此产生了“主范式”。

​ 同范式一样，主范式也分为主析取范式和主合取范式。

​ 那么，聪明的同学就要问了，什么是主范式呢？

​ 在我看来，主范式无非就是将范式的每一个$A_i$都用本身公式中的所有“文字”给塞满。这样的话，必然不会存在两个都是范式但是不相等的尴尬情况啦！

​ 例如，在本节所举的例子中我们可以知道主析取范式是：

$$(p \land q \land r) \vee (p \land q \land \neg r)\vee (p \land \neg q \land r)\vee (p \land \neg q \neg r)\vee (\neg p \land q \land \neg r)$$

​ 可见，每一个括号中都存在与$p$相关、与$q$相关、与$r$相关的文字，其为主范式。

2.2 主范式的简单理解

​ 先放出合取和析取的真值表：

$p$	$q$	$p \land q$
0	0	0
0	1	0
1	0	0
1	1	1

$p$	$q$	$p \vee q$
0	0	0
0	1	1
1	0	1
1	1	1

​ 在以上两个真值表中，我们可以看出，在合取时，至少一项为假，公式为假；在析取时，至少一项为真，公式为真。

​ 根据合取和析取的性质，主合取范式就可以理解为：这是一个表明公式为假时所有变元取值情况的式子；主析取范式也可以理解为：这是一个表明公式为真时所有变元取值情况的式子。

​ 同时，我们可以将主范式中每一个公式中文字理解为：原文字（如$p$,$q$）即表示1/0，其相反文字（如$\neg p $,$\neg q$）即表示0/1。

​ 那么，主范式可以这样理解：

​ 主合取范式：将范式中的每一个公式中文字提取出来写成集合形式，原文字表示0，相反文字表示1，主合取范式即表示公式为假时变元取值情况。

​ 主析取范式：将范式中的每一个公式中文字提取出来写成集合形式，原文字表示1，相反文字表示0，主合取范式即表示公式为真时变元取值情况。

​ 同样的，范式也可以这样理解。

3、如何优雅的写出主范式

3.1 主析取范式和主合取范式之间的关系

​ 我们可以得出以下结论：

​ 主析取范式和主合取范式的公式数量之和等于$2^n$，其中$n$为变元的数量，且两个范式中的公式“互补”。

​ 公式：指上文主范式定义中提到的$A_i$；

​ 互补：指两个式子中包含的每个公式中的文字组合的相关性，例如：

$$p \vee q的主合取范式为p \vee q，主析取范式为(p \land \neg q )\vee (\neg p \land q)\vee (p \land q)$$

​ 在上例中，可知主合取范式中公式包含的文字组合的集合为$\left\{(p,q)\right\}$，主析取范式中公式包含的文字组合的集合为$\left\{(p,\neg q),(\neg p , q),( p , q)\right\}$，我们设文字组合集合的全集为

$$\left\{(p,\neg q),(\neg p , q),( \neg p ,\neg q),(p,q)\right\}$$

​ 我们可以发现，主析取范式中文字组合的集合，为主合取范式文字组合的集合在全集中的补集取反（即将每一个文字变为其相反文字，如：$p$变成$\neg p$；可由2.2结论易知），这样我们这样我们称其互补，所有的主析取范式和主合取范式均遵循这样的规律。所以，在求取主范式的过程中，我们只需要算出主析取范式或主合取范式的其中一个就可以。

3.2 从范式到主范式

​ 拿到一个式子，我们需要进行等值演算。而在将公式变为只由$\left\{\neg,\vee,\land\right\}$表示之后，我们便可以由2.2的简单理解去对范式进行变形，不用运用分配律进行复杂的等值验算。这里引入离散第三周作业中的例子：

$$求合式公式 ( p \to q)\to r的主析取范式和主合取范式$$

​ 首先我们将该合式公式进行等值演算，消除掉其中的$\to$，这里需要用到0.1与0.2的知识。

$$\begin{align} (p \to q)\to r &\Leftrightarrow \neg (\neg p \vee q)\vee r\\ &\Leftrightarrow (p\land \neg q )\vee r \end{align}$$

​ 可见，我们只用了两步就可以将这个式子转化为析取范式的形式，接下来，我们可以使用奇技淫巧来将其转化成主析取范式。

​ 根据2.2，我们可以将该范式理解为：当$p$与$q$为真时，或者$r$为真时，公式为真。换言之，当$p$与$q$为真时，或者$r$为真时，无论剩下变量如何取值，该公式为真。

​ 又由于根据2.2，主析取范式可以理解为在公式为真的时候所有变量的取值，那么我们不再需要计算，直接将公式写出即可：

$$\begin{align} &\left\{(p \land \neg q)\right\}\vee \left[r\right]\\ \Leftrightarrow &\left\{(p \land \neg q \land r)\vee(p \land \neg q \land \neg r)\right\}\\ &\vee\left[(p \land q \land r) \vee (\neg p \land q\land r)\vee (\neg p \land \neg q \land r)\vee(p \land \neg q\land r)\right]\\ \Leftrightarrow&\left\{(p \land \neg q \land r)\vee(p \land \neg q \land \neg r)\right\}\vee\left[(\neg p \land q\land r)\vee (\neg p \land \neg q \land r)\vee(p \land \neg q\land r)\right]\\ \Leftrightarrow&\left\{ p \land \neg q \land \neg r\right\}\vee \left[(\neg p \land q\land r)\vee (\neg p \land \neg q \land r)\vee(p \land \neg q\land r)\right] \end{align}$$

​ 我们只需要将大括号包括的部分与小括号包括的部分根据2.2的理解简单扩充，并且根据幂等律进行消元，便可写出其主析取范式。

​ 再根据3.1的互补的性质可知，可写根据真值表或全集补集写出主合取范式：

$$(p \vee q \vee r)\land (p \vee\neg q \vee r)\land(\neg p \vee q\vee r)\land(\neg p \vee \neg q \vee \neg r)$$

​

这里建议使用真值表（因为我就是这么做的）：

step1

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1

step2

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1

step3

0 0 0$\to$ $ p \quad q \quad r$

0 0 1

0 1 0$\to$ $ p \quad \neg q \quad r$

0 1 1

1 0 0 $\to$ $\neg p \quad q \quad r$

1 0 1

1 1 0

1 1 1$\to $ $\neg p \quad \neg q \quad \neg r$

（从合取到析取也是同样，但是要注意2.2中0和1的转换）

​ 同时，根据真值表方法我们可以看出，直接使用真值表也可以很快的写出主析取范式和主合取范式，当然这样有一定的计算难度，仅适用于简单的公式。

​ 自此，我们完成了奇技淫巧的使用。虽然看起来很无用，但是不用分配律真的很爽。