找一个带prolog的布尔电路

Question

问题如下:考虑三个输入A,B,C,找到一个带AND,OR和NOT门的布尔电路,使输出不是(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,所以我尝试了以下目标:accessible([0,1,1,0,0,1,1,0],X,4).

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

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

Answer 1

您搜索任意形式的布尔表达式，基本上是在询问以下位数组生成的位数组上的布尔代数：

   01010101  
   00110011  

只要回忆一下布尔代数的范式即可。例如合取范式。合取范式如下：

    /\ clause_i

其中每个子句的形式为：

    \/ literal_i

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

    variable
    ~ variable

只需为您的生成器位数组选取 2 个变量即可。这在某种程度上减少了搜索空间。有 2 个变量有 4 个不同的子句。这就产生了 2^4 种不同的范式。

此外，如果您的目标是找到产生特定位数组的范式，例如您指定的：

 01100110

您可以通过将此值视为下限来进一步修剪搜索。

再见