从 CNF 转换为喇叭形式

Question

如何使用 Prolog 将 CNF 子句转换为 Horn 形式？我正在尝试创建一个以 CNF 作为输入的 SAT 求解器，需要将其转换为 Horn 形式。

Answer 1

Horn 子句是 CNF 的一个子集。即 CNF 可以看作是一般子句的合取，其中每个子句具有以下形式，其中 Ai,Bk 是命题变量，n>=0 和 m>=0:

A1 v .. v An v ~B1 v .. v ~Bm

Ai 是正文字，~Bk 是负文字。 Horn 子句现在是那些最多具有一个正文字的一般子句，即 n=<1。即属于以下形式之一：

A1 v ~B1 v .. v ~Bm

~B1 v .. v ~Bm

现在不可能将每个 CNF 转换为 Horn 子句，即使我们允许更改表示中文字的符号。将这个公式 nae(A,B,C)=(A xor B) v (B xor C) 和相关的符号变化变体作为 CNF:

nae(A,B,C)       = (~A v ~B v ~C) & (A v B v C)
nae(A,B,~C)      = (~A v ~B v C) & (A v B v ~C)
nae(A,~B,C)      = (~A v B v ~C) & (A v ~B v C)
nae(A,~B,~C)     = (~A v B v C) & (A v ~B v ~C)
nae(~A,B,C)      = (~A v B v C) & (A v ~B v ~C)
nae(~A,B,~C)     = (~A v B v ~C) & (A v ~B v C)
nae(~A,~B,C)     = (~A v ~B v C) & (A v B v ~C)
nae(~A,~B,~C)    = (~A v ~B v ~C) & (A v B v C)

它们都是 non-Horn 子句，因此无法进行重命名翻译。但也许使用其他归约，可能 non-polynomial 个，可用于将 CNF 转换为 Horn 子句。

P.S.: nae(A,B,C) 例子取自here.

从 CNF 转换为喇叭形式

Converting to Horn Form from CNF

prolog

sat-solvers