Find Prolog Logic

Question

The problem is this: consider the three inputs A, B, C, find a logic circuit with the logical elements AND, OR, and NOT, so that the output is not (A), not (B), not (C), using most 2 NOT the gate.

I would like to find a prolog scheme. My idea is to compute the predicate "available", which takes a function and says if it exists, which evaluates 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 xor function between 11,12, so I try the following goal: available ([0,1,1,0,0,1,1,0], X, 4).

But the prologue works for a while before getting a good answer. I would like to know how to improve the program to make it faster.

PS How to print a string without ASCII codes using the GNU prolog?

Answer 1

You search by arbitrary generated Boolean expressions and you basically specify what logical algebra over bitmaps is generated by the following bitmaps:

  01010101 00110011 

Just recall the normal forms of Boolean algebra. For example, conjunctive normal form. Connective normal form reads as follows:

  /\ clause_i 

Each sentence has the following form:

  \/ literal_i 

And each literal has either one of the following forms:

  variable ~ variable 

Just take 2 variables for your generator bitmaps. This somehow reduces the search space. With two variables, there are 4 different sentences. Which makes 2 ^ 4 different normal forms.

In addition, if you have a goal to find a normal form, which leads to a specific bitmap specified by you:

  01100110 

You can further trim your search by treating this value as a lower bound.

Bye