5

问题如下：考虑三个输入 A、B、C，找到一个带有 AND、OR 和 NOT 门的布尔电路，使得输出为 not(A)、not(B)、not(C)，最多使用 2 个 NOT大门。

我想用序言找到电路。我的想法是计算一个谓词“可访问”，它接受一个函数并说明它是否存在计算 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 代码的字符串？

4

1 回答 1

1

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

   01010101  
   00110011

回想一下布尔代数的正常形式。例如合取范式。合取范式如下：

    /\ clause_i

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

    \/ literal_i

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

    variable
    ~ variable

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

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

 01100110

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

再见

于 2015-09-10T06:24:33.173 回答