prolog - 用 prolog 找到一个 bool 电路

Question

问题如下:考虑三个输入 A、B、C，找到一个带有 AND、OR 和 NOT 门的 bool 电路，使得输出不是(A)，不是(B)，不是(C)，最多使用 2 个 NOT盖茨。

我想用prolog找到电路。我的想法是计算一个谓词“可访问”，它接受一个函数并说明它是否存在计算 f 的电路。

我有以下谓词:

not([],[]).
not([H|T],[G|S]) :- G #=# 1-H, not(T,S).

or([],[],[]).
or([0|T],[0|S],[0|R]) :- or(T,S,R).
or([1|T],[0|S],[1|R]) :- or(T,S,R).
or([1|T],[1|S],[1|R]) :- or(T,S,R).
or([0|T],[1|S],[1|R]) :- or(T,S,R).

and([],[],[]).
and([1|T],[1|S],[1|R]) :- and(T,S,R).
and([0|T],[1|S],[0|R]) :- and(T,S,R).
and([1|T],[0|S],[0|R]) :- and(T,S,R).
and([0|T],[0|S],[0|R]) :- and(T,S,R).

accessible(_,_,0) :- !,fail.
accessible([0,1,0,1,0,1,0,1],[12],_) :- !.
accessible([0,0,1,1,0,0,1,1],[11],_) :- !.
accessible([0,0,0,0,1,1,1,1],[10],_) :- !.
accessible(F,L,C) :- CC is C-1, or(G,H,F), accessible(G,M,CC), accessible(H,N,CC), L=[0, [M,N]].
accessible(F,L,C) :- CC is C-1, and(G,H,F), accessible(G,M,CC), accessible(H,N,CC), L=[1,[M,N]].
accessible(F,L,C) :- CC is C-1,  not(F,X), accessible(X,M,CC), L=[2,M].

我想计算 11,12 之间的函数 xor 所以我尝试以下目标:
可访问([0,1,1,0,0,1,1,0], X, 4)。

但是 prolog 在得到好的答案之前运行了一段时间。我想知道如何改进程序以使其更快。

附言
如何使用 GNU prolog 打印没有 ASCII 代码的字符串？

Answer 1

您搜索任意形式的 bool 表达式，并且
您基本上是在问位数组上的 bool 代数是什么
由以下位数组生成:

   01010101  
   00110011  

回想一下 bool 代数的正常形式。例如
合取范式。一个连接范式读
如下:

    /\ clause_i

其中每个子句具有以下形式:

    \/ literal_i

每个文字都具有以下形式之一:

    variable
    ~ variable

只需为您的生成器位数组取 2 个变量。这个
以某种方式减少了搜索空间。有 2 个变量
4个不同的条款。这构成了 2^4 种不同的范式。

此外，如果您的目标是找到一个范式
导致某个位数组，例如您指定的:

 01100110

您可以通过考虑这一点来进一步修剪您的搜索
值作为下限。

再见