可满足性与范式

称$A$$A$是可满足式(Satisfiable),当且仅当存在某些解释$I$$I$使得公式$A$$A$的取值$v_I(A)=T$$v_I(A)=T$. 使公式$A$$A$取值为真的解释$I$$I$称为$A$$A$的模型(Model).

称$A$$A$是永真式(Tautology),当且仅当所有的解释均使公式$A$$A$的取值为真,记作$\models A$$\models{A}$.

称$A$$A$是永假式或不可满足式(Unsatisfiable),当且仅当所有的解释均使公式$A$$A$的取值为假,记作$⊭A$$\nvDash{A}$.

称$A$$A$是可为假式(Falsifiable),当且仅当存在某些解释$I$$I$使得公式$A$$A$的取值$v_I(A)=F$$v_I(A)=F$.

例：$(p\vee q)\wedge \mathrm{\neg }p\wedge \mathrm{\neg }q$$(p \lor q) \land \lnot p \land \lnot q$是不可满足式。

设$U=\{A_1,A_2,\cdots ,A_n\}$$U = \{A_1,A_2,\cdots,A_n\}$为一个公式集合,称$U$$U$是可满足的,当且仅当存在一个解释$I$$I$使得对于所有的$k$$k$,$v_I(A_k)=T$$v_I (A_k)=T$, 该解释称为$U$$U$​的模型。

称$U$$U$是不可满足的,当且仅当对于所有的$k$$k$,$v_I(A_k)=F$$v_I (A_k)=F$.

令$U$$U$为一个公式集合,$B$$B$为一个公式。称$A$$A$是$U$$U$的逻辑后果(Logical Consequence),当且仅当$U$$U$的每一个模型也是$A$$A$的模型。记作$U\models A$$U\models{A}$​.

由有限个命题变量或其否定所组成的合取式称为基本积。

例如: $\mathrm{\neg }q$${\lnot}q$, $p\wedge q$$p{\wedge}q$, $p\wedge q\wedge \mathrm{\neg }r$$p{\wedge}q{\wedge}{\lnot}r$都是基本积。

由有限个命题变量或其否定所组成的合取式称为基本和。

例如: $p$$p$, $\mathrm{\neg }p\vee q$${\lnot}p{\vee}q$, $p\vee q\vee \mathrm{\neg }r$$p{\vee}q{\vee}{\lnot}r$都是基本和。

$p$$p$, $\mathrm{\neg }p$${\lnot}p$既是基本积,也是基本和。

一个由基本积的析取组成的命题公式,称为析取范式(Disjunctive Normal Form, DNF),即该命题公式具有形式: $A_1\vee A_2\vee \cdots \vee A_n$$A_{1}{\vee}A_{2}{\vee}{\cdots}{\vee}A_n$ 其中$A_1,A_2,\cdots ,A_n$$A_{1},A_{2},{\cdots},A_n$都是基本积。

例如: 命题公式$\mathrm{\neg }p\vee (p\wedge q)\vee (p\wedge \mathrm{\neg }q\wedge r)$${\lnot}p{\vee}(p{\wedge}q){\vee}(p{\wedge}{\lnot}q{\wedge}r)$是析取范式。

一个由基本和的合取组成的命题公式,称为合取范式(Conjunctive Normal Form, CNF),即该命题公式具有形式: $B_1\wedge B_2\wedge \cdots \wedge B_n$$B_{1}{\wedge}B_{2}{\wedge}{\cdots}{\wedge}B_n$ 其中$B_1,B_2,\cdots ,B_n$$B_{1},B_{2},{\cdots},B_n$都是基本和。

例如: 命题公式$q\wedge (p\vee q)\wedge (\mathrm{\neg }q\vee r)$$q{\wedge}(p{\vee}q){\wedge}({\lnot}q{\vee}r)$是合取范式。

$p\wedge \mathrm{\neg }q$$p{\wedge}{\lnot}q$和$\mathrm{\neg }p\vee q$${\lnot}p{\vee}q$既是析取范式,也是合取范式。

定理:(范式存在定理)任何命题公式都存在与其等值的析取范式和合取范式。

任何命题公式的析取范式和合取范式不一定是唯一的。

对于一个命题公式,求其析取范式和合取范式的步骤如下:

(1)消去{$\mathrm{\neg },\wedge ,\vee$${\lnot},{\wedge},{\vee}$}以外的逻辑联结词;

(2)利用德$\cdot$${\cdot}$摩根律将否定联结词$\mathrm{\neg }$${\lnot}$内移,消去双重否定;

(3)利用分配律将公式化成析取范式或合取范式。

例:求下面命题公式的合取范式: $((p\vee q)\to r)\to p$$((p{\vee}q){\rightarrow}r){\rightarrow}p$ 解: $((p\vee q)\to r)\to p$$((p{\vee}q){\rightarrow}r){\rightarrow}p$ $\iff (\mathrm{\neg }(p\vee q)\vee r)\to p$${\Leftrightarrow}({\lnot}(p{\vee}q){\vee}r){\rightarrow}p$ $\iff \mathrm{\neg }(\mathrm{\neg }(p\vee q)\vee r)\vee p$${\Leftrightarrow}{\lnot}({\lnot}(p{\vee}q){\vee}r){\vee}p$ $\iff ((p\vee q)\wedge \mathrm{\neg }r)\vee p$${\Leftrightarrow}((p{\vee}q){\wedge}{\lnot}r){\vee}p$ $\iff (p\vee q\vee p)\wedge (\mathrm{\neg }r\vee p)$${\Leftrightarrow}(p{\vee}q{\vee}p){\wedge}({\lnot}r{\vee}p)$ $\iff (p\vee q)\wedge (\mathrm{\neg }r\vee p)$${\Leftrightarrow}(p{\vee}q){\wedge}({\lnot}r{\vee}p)$

利用析取范式和合取范式可对命题公式的可满足性进行判定。

(1) 一个析取范式$A_1\vee A_2\vee \cdots \vee A_n$$A_{1}{\vee}A_{2}{\vee}{\cdots}{\vee}A_n$是永假式,当且仅当它的每个基本积都是永假式。

(2) 一个合取范式$B_1\wedge B_2\wedge \cdots \wedge B_n$$B_{1}{\wedge}B_{2}{\wedge}{\cdots}{\wedge}B_n$是永真式,当且仅当它的每个基本和都是永真式。

(3) 一个命题公式为永假式当且仅当它的析取范式中每一个基本积都至少含有一个命题及其否定。

(4) 一个命题公式为永真式当且仅当它的合取范式中每一个基本和都至少含有一个命题及其否定。

在含有$n$$n$个命题变量的基本积中,如果每个命题变量与它的否定不同时存在,但二者之一必出现且仅出现一次,则这样的基本积称为极小项。

例如: $\mathrm{\neg }p\wedge \mathrm{\neg }q$${\lnot}p{\wedge}{\lnot}q$, $\mathrm{\neg }p\wedge \mathrm{\neg }q\wedge r$${\lnot}p{\wedge}{\lnot}q{\wedge}r$.

在含有$n$$n$个命题变量的基本和中,如果每个命题变量与它的否定不同时存在,但二者之一必出现且仅出现一次,则这样的基本和称为极大项。

例如: $p\vee q\vee \mathrm{\neg }r$$p{\vee}q{\vee}{\lnot}r$.

对于给定的含$n$$n$个命题变量的命题公式,若其析取范式的基本积均是这$n$$n$个命题变量的极小项,则称该析取范式为命题公式的主析取范式。

基本形式: $A_1\vee A_2\vee \cdots \vee A_n$$A_{1}{\vee}A_{2}{\vee}{\cdots}{\vee}A_n$

定理:(主析取范式存在唯一性)任何不为永假式的命题公式都存在与其等价的主析取范式,且唯一。

对于给定的含$n$$n$个命题变量的命题公式,若其合取范式的基本和均是这$n$$n$个命题变量的极大项,则称该合取范式为命题公式的主合取范式。

基本形式: $B_1\wedge B_2\wedge \cdots \wedge B_n$$B_{1}{\wedge}B_{2}{\wedge}{\cdots}{\wedge}B_n$

定理:(主合取范式存在唯一性)任何不为永真式的命题公式都存在与其等价的主合取范式,且唯一。

求主范式可采用真值表法

在真值表中,命题公式真值为$T$$T$的解释所对应真值为$T$$T$的极小项的析取,即为该命题公式的主析取范式。

在真值表中,命题公式真值为$F$$F$的解释所对应真值为$F$$F$的极大项合取,即为该命题公式的主合取范式。

可以按以下步骤构造主析取范式:

(1)将命题公式化为析取范式;

(2)除去析取范式中所有永假的基本积;

(3)利用等幂律将重复出现的基本积和基本积中重复出现的变量合并;

(4)利用同一律在基本积中补入未出现的命题变量(如$p\vee \mathrm{\neg }p$$p{\vee}{\lnot}p$),然后用分配律展开;

(5)再次利用等幂律将重复出现的极小项合并。

例:求$\mathrm{\neg }p\vee \mathrm{\neg }q$${\lnot}p{\vee}{\lnot}q$的主析取范式。

解:$\mathrm{\neg }p\vee \mathrm{\neg }q$${\lnot}p{\vee}{\lnot}q$ $\iff (\mathrm{\neg }p\wedge (q\vee \mathrm{\neg }q))\vee ((p\vee \mathrm{\neg }p)\wedge \mathrm{\neg }q)$${\Leftrightarrow}({\lnot}p{\wedge}(q{\vee}{\lnot}q)){\vee}((p{\vee}{\lnot}p){\wedge}{\lnot}q)$ $\iff (\mathrm{\neg }p\wedge q)\vee (\mathrm{\neg }p\wedge \mathrm{\neg }q)\vee (p\wedge \mathrm{\neg }q)\vee (\mathrm{\neg }p\wedge \mathrm{\neg }q)$${\Leftrightarrow}({\lnot}p{\wedge}q){\vee}({\lnot}p{\wedge}{\lnot}q){\vee}(p{\wedge}{\lnot}q){\vee}({\lnot}p{\wedge}{\lnot}q)$ $\iff (\mathrm{\neg }p\wedge q)\vee (\mathrm{\neg }p\wedge \mathrm{\neg }q)\vee (p\wedge \mathrm{\neg }q).$${\Leftrightarrow}({\lnot}p{\wedge}q){\vee}({\lnot}p{\wedge}{\lnot}q){\vee}(p{\wedge}{\lnot}q).$