Boolean逻辑基础

    设Boolean变量$x_1 \cdots x_n \cdots$组成一个可数的无限字母集$X=\{x_1 \cdots x_n \cdots\}$，这些变量取真值true或false，简记为1或0，同时这些变量可以通过析取$\lor$，合取$\land$，否$\neg$这些运算符号连接起来得到一个Boolean表达式。另外还有符号蕴含：$\Rightarrow$，$x_1\Rightarrow x_2$意味着$\neg x_1 \lor x_2$，$x_1\Rightarrow x_2$并且$x_2\Rightarrow x_1$意味着$x_1\Leftrightarrow x_2$，即$(\neg x_1 \lor x_2)\land (\neg x_2 \lor x_1)$。对于Boolean变量$x$，$x$与$\neg x$均称为文字。

    一个赋值$T$是从Boolean变量的集合到真值集合$\{0,1\}$的一个映射，对于一个Boolean表达式$\phi$，记$X(\phi)$表示$\phi$中Boolean变量的集合，如果$X(\phi)$在$T$的定义域内，称赋值$T$适合$\phi$。设赋值$T$适合$\phi$，如果$X(\phi)$中变量在$T$下的取值使得$\phi$的真值为1，则称$T$满足$\phi$，记为$T|=\phi$，否则，称$T$不满足$\phi$，记为$T|\neq \phi$。显然，根据Boolean变量真值的取值，Boolean表达式可以取0或1，如果存在适合$\phi$的赋值$T$，有$T|=\phi$，则称$\phi$是可满足的，否则，称之为不可满足。

    如果$\bigwedge_{i=1}^n{\phi _i}$，其中$n\geq 1$，且每个$\phi _i$为一些文字的析取，则称$\phi$为合取范式，称$\phi _i$为分句，类似的，可以定义析取范式形式为$\bigvee _{i=1}^n{D _i}$，其中$n\geq 1$，且每个$D_i$为一些文字的合取，易证，每个Boolean表达式等价于一个合取范式，而且也等价于一个析取范式。

SAT问题与HORNSAT问题

    SAT问题是一个NP完备问题，虽然我们目前没有找到SAT问题的确定的有效算法，但是有一类特殊的SAT问题是比较容易求解的，比如HORNSAT问题。如果一个分句至多有一个正的文字，如$\neg x_1 \lor \neg x_2 \lor x_3$和$x_1 \lor \neg x_2$，则称此分句为HORN分句，HORNSAT问题即设$\phi$为HORN分句的合取，问$\phi$是否为可满足的。

    HORNSAT问题的算法非常简单，首先任意HORN分句都可以写成蕴含式，比如$\neg x_1 \lor \neg x_2 \lor x_3$可以改写成$(x_1 \land x_2)\Rightarrow x_3$，$x_1 \lor \neg x_2$可以改写为$x_2 \Rightarrow x_1$。这种蕴含式只在左边为1，右边为0时取到false。HORNSAT问题的算法流程非常简单，令$T$为赋值为true的变量的集合，初始令$T$为空集，即所有的变量都取0，执行下列步骤直到所有蕴含式都被满足：

    算法里有几个需要注意的点，首先对于蕴含式$x\Rightarrow y$，如果$x$与$y$都取0，这个蕴含式显然是取1的，但HORN分句不止这种类型，单个的$x$或$\neg x$也是一种HORN分句，那此时让所有的变量都取0就不一定能让所有分句取1，所以算法中重复寻找不满足的蕴含式是有必要的。由于$x\Rightarrow y$只在$x=1$，$y=0$时取0，则对于$(x_1 \land \cdots \land x_t)\Rightarrow y$，若其为0，则必有$x_1=\cdots =x_t=1$，$y=0$，接下来只需令$y=1$，即$T\leftarrow y$即可把此蕴含式的值变为1，也就是在集合$T$中放入了一个新的元素。

    由于变量的个数必为有限的，不妨设为$n$个，上面的算法至多会把$n$个元素放入$T$中，也就是算法最多重复执行$n$次，显然是多项式时间的。所以特殊的HORNSAT问题是有效可解的。

赏

谢谢你请我喝冰露

支付宝

微信