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

Question

Я собираюсь реализовать проверку на логические термины в прологе. Мой текущий код не очень презентабельный, поэтому я просто скажу, что я хочу, чтобы моя программа делала, и, надеюсь, вы можете дать мне несколько полезных советов для этого:)

Он должен принимать список переменных (так сказать, логических аргументов) и, во-вторых, логическую формулу, содержащую эти аргументы (например, 'not'(A 'and' B) 'or' 'not'(B 'and' C) 'or' ... и так далее).

В качестве результата я хотел бы, чтобы моя программа ответила возможными последовательными заданиями. Одиночные аргументы могут быть либо истинными (1) или ложь (0).

Поэтому я стремлюсь к возвращению, как A=0, B=0, C=0 ; A=1 и так далее.

Я рад за любую помощь, касающуюся моей программы:)

Answer 1

Есть несколько способов приблизиться к этому. Одним из удобных с точки зрения синтаксиса способов является определение операторов, например:

:- op(500, fx, not).
:- op(600, xfx, and).
:- op(700, xfx, or).

(Я просто догадываюсь о разумных настройках приоритета здесь, но только для иллюстрации. op документация для деталей.)

Сделав это, вы можете написать выражение, такое как: A and B и Пролог "увидит" это как and(A, B):

| ?- write_canonical(A and B).
and(_23,_24)

Оттуда у вас должен быть способ оценить выражение. Здесь есть много вопросов по SO (выполните поиск на этом сайте на [prolog] boolean expression evaluation), но я приведу простой пример. Теперь все о том, как вы хотите представить результат, и о рекурсии.

Когда дело доходит до представления результата, вы можете использовать механизм успеха / неудачи Пролога, поскольку вы имеете дело с логическими результатами. Или вы можете получить явный результат, например, 0 и 1. Давайте попробуем 0 и 1, так как это ваше представление для истинных и ложных.

% Describe a valid boolean
bool(0).
bool(1).

% The evaluation of a valid boolean is itself
exp_eval(X, X) :- bool(X).

% Evaluation of an 'and' expression
exp_eval(and(A, B), Result) :-
    exp_eval(A, ResultA),
    exp_eval(B, ResultB),
    Result #= ResultA * ResultB.

% Evaluation of an 'or' expression
exp_eval(or(A, B), Result) :-
    exp_eval(A, ResultA),
    exp_eval(B, ResultB),
    % Just a little trick to get 1 if either ResultA or ResultB or both are 1
    Result #= (ResultA + ResultB + 1) // 2.

% Evaluation of a 'not' expression
exp_eval(not(A), Result) :-
    exp_eval(A, ResultNot),
    Result #= 1 - ResultNot.  % 0 ---> 1, and 1 ---> 0

Вместо того, чтобы вычислять "логические" результаты 1/0, как я делал выше, вы могли бы вместо этого утверждать их как факты:

bool_not(0, 1).
bool_not(1, 0).

bool_and(0, 0, 0).
bool_and(0, 1, 0).
bool_and(1, 0, 0).
bool_and(1, 1, 1).

bool_or(0, 0, 0).
bool_or(0, 1, 1).
bool_or(1, 0, 1).
bool_or(1, 1, 1).

И тогда, например, вместо Result #= (ResultA + ResultB + 1) // 2 ты мог бы просто иметь, bool_or(ResultA, ResultB, Result),

Теперь, когда мы можем оценивать выражения, нам нужен решатель:

solve(Exp) :-
    term_variables(Exp, Variables),
    maplist(bool, Variables),  % Variables should be valid booleans
    exp_eval(Exp, 1).          % We only want true results for the expression

Обратите внимание, что в исходной постановке задачи сказано, что список переменных будет задан в качестве аргумента, но вы можете использовать term_variables/2 чтобы получить переменные из выражения.

Тогда вы можете запустить решатель:

| ?- solve(not(A and B) or not(B and C)).

A = 0
B = 0
C = 0 ? a

A = 0
B = 0
C = 1

A = 0
B = 1
C = 0

A = 0
B = 1
C = 1

A = 1
B = 0
C = 0

A = 1
B = 0
C = 1

A = 1
B = 1
C = 0

no
| ?-

Я не знаю, что вы представляете для выражения. Но что бы это ни было, вы можете сопоставить это с вышеупомянутым решением. То, что я показал, просто и понятно. Вы могли бы пропустить op/3 вещи и использовать стандартные выражения, как, например, or(not(and(A,B)), not(and(B,C))) используя приведенный выше код. Если у вас есть вход в виде последовательности токенов, например, [not, (, A, and, B, ...] тогда вам придется сделать небольшую обработку списка.