Find a boolean circuit with prolog

Question

The problem is the following : considering three inputs A,B,C, find a boolean circuit with AND,OR and NOT gates such that the output is not(A), not(B), not(C) using at most 2 NOT gates.

I would like to find the circuit with prolog. My idea is to compute a predicate "accessible" that takes a function and says if it exists a circuit that computes f.

I have the following predicates :

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].

I would like to compute the function xor between 11,12 so I try the following goal : accessible([0,1,1,0,0,1,1,0], X, 4).

But prolog runs a while before getting the good answer. I'd like to know how to improve the program in order to make it faster.

P.S. How to print a string without ASCII codes with GNU prolog ?

Answer 1

You searching over arbitrary formed boolean expressions, and you are basically asking what boolean algebra over bit arrays is generated by the following bit arrays:

   01010101  
   00110011  

Just recall normal forms of boolean algebra. For example conjunctive normal form. A conjunctive normal form reads as follows:

    /\ clause_i

Whereby each clause has the form:

    \/ literal_i

And each literal has either one of the following forms:

    variable
    ~ variable

Just take 2 variables for your generator bit arrays. This reduces the search space somehow. With 2 variables there are 4 different clauses. Which makes 2^4 different normal forms.

Further, if you have the goal to find a normal form that results in a certain bit array, such as you specified:

 01100110

You can further prune your search by considering this value as a lower bound.

Bye