文章同步于@c.w.-知乎，个人博客
本文及其系列文章用于离散数学（1）科目的期末考试复习
命题公式的真值表
对于一个含有\(n\)个命题变元\(P_1,P_2,……,P_n\)的命题公式\(A\)来说，可以根据\(P_1,P_2,……,P_n\)的真值给出\(A\)的真值，从而建立起了一个命题公式的真值表。
一般我们认为，从真值表出发写命题公式可以从列表中值为\(T\)或者值为\(F\)来写。
比如，如果真值表为
那么，从取到\(T\)的那几行来看，\(A=(\neg P\land Q)\lor(P\land Q)\)。即，A在取\(T\)的时候，\(P,Q\)的取值应该让\(A\)的表达式中某个括号的真值为1。
从取到\(F\)的那几行来看，\(A=(\neg P \lor\neg Q)\land(P\lor\neg Q)\)。即，A在取到\(F\)的时候，\(P,Q\)的取值应该让\(A\)的表达式中某个括号的真值为0。
联结词的完备集
除了常见的5个联结词外，我们还可以定义更多的联结词。以下是三个较为常见的联结词。
异或\(\overline\lor\)
与非\(\uparrow\)
或非\(\downarrow\)
理论上，其他的联结词都是存在的，但是因为使用甚少，所以常常不予讨论。
还有一个问题是，对于\(n\)个命题变项而言，我们可以定义出多少个联结词。容易知道，答案是\(2^{2^n}\)个。这由归纳法或者直接构造即可得证。
对偶式和补公式
将\(A\)中所有出现的\(\land,\lor,T,F\)分别以\(\lor,\land,F,T\)替换，得到公式\(A^*\)，则称，\(A^*\)是\(A\)的对偶式。或者说，\(A\)和\(A^*\)互为对偶式。
设\(A=A(P_1,P_2,……,P_n)\)，令\(A^-=A(\neg P_1,\neg P_2,……,\neg P_n)\)，则称\(A^-\)为A的补公式
那么，我们由如下定理：
- \(\neg(A^* )=(\neg A)^* ,\neg(A^-)=(\neg A)^-\)
- \((A^* )^* =A=(A^-)^-\)
- \(\neg A=(A^* )^-\)
其中，性质2.非常显然，性质1.和3.可以通过对式子中联结词个数进行归纳来证明。实际上，3.是摩根律的推广形式。
以下是对偶式、补公式有关真值性的的一些性质。
- 如果\(A=B\)，那么\(A^* =B^*\)
- 如果\(A\rightarrow B\)永真，那么\(B^* \rightarrow A^*\)永真
- 若\(A\)永真，那么\(A^-\)永真。反之亦然
- 若\(\neg A\)永真，那么\(A^*\)永真。反之亦然。
范式
一些定义
为了描述方便，先定义几个术语。
简单命题\(P\)和\(\neg P\)被称为文字
一些文字的合取被称为合取式
一些文字的析取被称为析取式
\(P\)和\(\neg P\)为互补对
析取范式是形如\(A_1\lor A_2\lor …… \lor A_n\)的公式，其中，\(A_i(1\leq i\leq n)\)是合取式
合取范式是形如\(A_1\land A_2\land …… \land A_n\)的公式，其中，\(A_i(1\leq i\leq n)\)是析取式
极小项指的是一种特殊的合取式。对于\(n\)个命题变项而言，所组成的公式\(Q_1\land Q_2\land ……\land Q_n\,,\,Q_i=P_i\)或者\(\neg P_i\)，那么称\(Q_1\land Q_2\land ……\land Q_n\)为极小项（可以理解为不能够再消去、化简的合取式）。
极大项指的是一种特殊的析取式。对于\(n\)个命题变项而言，所组成的公式\(Q_1\lor Q_2\lor ……\lor Q_n\,,\,Q_i=P_i\)或者\(\neg P_i\)，那么称\(Q_1\lor Q_2\lor ……\lor Q_n\)为极大项（可以理解为不能够再消去、化简的析取式）。
范式定理
任何公式都存在（不止一个的）与之等值的合区范式和析取范式。
主范式
仅由极小项构成的析取式称为主析取范式
仅由极大项构成的合取式称为主析合范式
我们有如下定理：
- 任何一个含有\(n\)个命题变项的公式，都有唯一一个与之等值的、且恰仅含这\(n\)个命题变项的主析取范式，也有唯一一个与之等值的、且恰仅含这\(n\)个命题变项的主析合范式。
即主合式和主析式唯一存在定理。
我们比较关心的是如何去把一个式子化为主析取范式和主合取范式。一般的做法就是
- 把所有的\(\rightarrow\)和\(\leftrightarrow\)都变成与或非的表示。
- 反复运用分配律、摩根律，进行适当的化简，让整个式子变成合取范式或者析取范式
- 更进一步化简，消去多余的项，变成主合取范式或者主析取范式。
- 如果有命题变项没有出现，例如\(Q\)，如果要化为主合式，那么给每个括号内加上\(\lor (Q\land\neg Q)\)，再分配律拆开；如果要化为主析式，那么给每个括号内加上\(\land (Q\lor\neg Q)\)，再分配律拆开。
如果有真值表，那么主合取范式和主析取范式就是从真值表\(F\)和\(T\)出发得到的式子。
同时，仍旧是从真值表出发， 我们有一个更加简单的表达方式。那就是给每个极小项和极大项按照二进制编号。笼统来说，可以理解为让极小/大项中有\(\neg\)的文字视作0，没有的视作1，然后连接成一串二进制数\(i\)，这一项就记做\(m_i\)或\(M_i\)。
例如，对于拥有极小项而言，我们可以有如下标号方式。
对于极大项，我们也同理有
例如，我们给出如下例子
\(P\rightarrow Q\\\\=m_0\lor m_1\lor m_3=\lor_{0,1,3}\\\\=M_1=\land_{1}\)
其中的简写容易理解。并且，主析取范式和主合取范式的简写能够用一种比较简单的式子互相转化.
即，设\(A\)是由\(n\)个变项组成的命题公式，记\(U=\{ 0,1,2,……2^n-1 \}\),\(I\)是一个下标集，那么我们有：
若\(A=\land_I\)，则\(\neg A=\land_{U-I}\)
从而，\(A=\land_I=\lor_{{(U-I)}_{\text{补}}}\)
其中，“补”的意思是\(A_{补}=\{x|x+a=2^n-1,a\in A\}\)
比如，举个例子，
若\(A=\land_{1,4,5}\)，\(A\)是一个拥有三个命题变项的公式。则\(U=\{0,1,2,……,7\}\)我们有：
\(A\\\\=\land_{1,4,5} \\\\ = \lor_{({ \{0,1,……,7 \} - \{1,4,5\} })_{\text{补}}} \\\\=\lor_{\{ 0,2,3,6,7\}_{\text{补}}}\\\\=\lor_{0,1,4,5,7}\)
并且明显的，对于从主析取范式到主合取范式的过程反之亦然。