Найти булеву схему с прологом

Question

Проблема заключается в следующем: рассматривая три входа A,B,C, найдите логическую схему с логическими элементами И, ИЛИ и НЕ, чтобы выход не был (А), не (В), не (С), используя не более 2 НЕ ворота.

Я хотел бы найти схему с прологом. Моя идея состоит в том, чтобы вычислить предикат "доступный", который принимает функцию и говорит, существует ли схема, которая вычисляет 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].

Я хотел бы вычислить функцию xor между 11,12, поэтому я пытаюсь достичь следующей цели: доступный ([0,1,1,0,0,1,1,0], X, 4).

Но пролог проходит некоторое время, прежде чем получает хороший ответ. Я хотел бы знать, как улучшить программу, чтобы сделать ее быстрее.

PS Как напечатать строку без кодов ASCII с прологом GNU?

Answer 1

Вы выполняете поиск по произвольно сформированным логическим выражениям и в основном спрашиваете, какая логическая алгебра над битовыми массивами генерируется следующими битовыми массивами:

   01010101  
   00110011  

Просто вспомните нормальные формы булевой алгебры. Например, конъюнктивная нормальная форма. Конъюнктивная нормальная форма гласит:

    /\ clause_i

При этом каждое предложение имеет вид:

    \/ literal_i

И каждый литерал имеет одну из следующих форм:

    variable
    ~ variable

Просто возьмите 2 переменные для ваших битовых массивов генератора. Это как-то уменьшает пространство поиска. С 2 переменными есть 4 разных предложения. Что делает 2^4 разных нормальных форм.

Далее, если у вас есть цель найти нормальную форму, которая приводит к определенному битовому массиву, например, указанному вами:

 01100110

Вы можете дополнительно сократить поиск, считая это значение нижней границей.

до свидания