Создание SAT-решателя на основе Гребнера на языке Prolog

Я пытаюсь создать решатель SAT, который преобразует конъюнктивную нормальную форму (CNF) с реализацией логических баз Гробнера:

а) Отрицание конкретной переменной, например. -x будет преобразовано в 1+x.
b) Добавление той же переменной приведет к 0. Например. x + x = 0. (необходимо использовать XOR).
c) Умножение одной и той же переменной приведет к одной и той же переменной. например x*x = x.

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

p cnf 3 4 
1 3 -2 0
3 1 0
-1 2 0
2 3 1 0

Спасибо.

РЕДАКТИРОВАТЬ

parser :-
    open(File, read, Stream),
    read_literals(Stream,Literals),
    close(Stream),
    read_clauses(Literals,[],Clauses),
    write(Clauses).

read_literals(Stream,Literals) :-
    get_char(Stream,C),
    read_literals(C,Stream,Literals).

read_literals(end_of_file,_Stream,Literals) :-
    !,
    Literals = [].

read_literals(' ',Stream,Literals) :-
    !,
    read_literals(Stream,Literals).

read_line_then_literals('\n',Stream,Literals) :-
    !,
    read_literals(Stream,Literals).

read_line_then_literals(_C,Stream,Literals) :- 
    read_line_then_literals(Stream,Literals).

read_literal_then_literals(Stream,As,Literals) :-
    get_char(Stream,C),
    read_literal_then_literals(C,Stream,As,Literals). 

read_literal_then_literals(C,Stream,As,Literals) :-
    digit(C),
    !,
    name(C,[A]),
    read_literal_then_literals(Stream,[A|As],Literals).

read_literal_then_literals(C,Stream,As,Literals) :-
    reverse(As,RevAs),
    name(Literal,RevAs), 
    Literals = [Literal|Rest_Literals],
    read_literals(C,Stream,Rest_Literals).

digit('0').
digit('1').
digit('2').
digit('3').
digit('4').
digit('5').
digit('6').
digit('7').
digit('8').
digit('9').

read_clauses([],[],[]).

read_clauses([0|Literals],Clause,Clauses) :-
    !,
    reverse(Clause,RevClause),
    Clauses=[RevClause|RestClauses],
    read_clauses(Literals,[],RestClauses).

read_clauses([Literal|Literals],Clause,Clauses) :- 
    read_clauses(Literals,[Literal|Clause],Clauses). 

person piyo_kuro    schedule 16.08.2017    source источник
comment
Привет, Гай Кодер, на данный момент я нашел способ прочитать строки в текстовом файле. Однако моя основная проблема заключается в преобразовании строк, представленных в форме CNF, в форму ANF. Есть ли у вас какие-либо предложения о том, как начать / где читать, чтобы я мог сделать немного больше кодов?   -  person piyo_kuro    schedule 16.08.2017
comment
Привет, Гай Кодер, я надеюсь, что вам удалось решить вашу проблему, и спасибо, что нашли время, чтобы ответить мне, несмотря на то, что вы заняты. Что касается преобразования в ANF, как вы думаете, возможно ли это сделать с помощью Пролога?   -  person piyo_kuro    schedule 18.08.2017
comment
Привет, Гай Кодер, у меня есть некоторый прогресс в моей работе. Единственная проблема заключается в том, что в данный момент, когда я вижу отрицательное число (например, -2), я хочу реализовать метод, в котором not(X) = X - 1. Как вы думаете, это возможно?   -  person piyo_kuro    schedule 21.08.2017
comment
На данный момент мой код выглядит следующим образом   -  person piyo_kuro    schedule 22.08.2017
comment
часть 1 parser :- open(File, read, Stream), read_literals(Stream,Literals), close(Stream), read_clauses(Literals,[],Clauses), write(Clauses). read_literals(Stream,Literals):- get_char(Stream,C), read_literals(C,Stream,Literals). read_literals(end_of_file,_Stream,Literals):- !, Literals=[]. read_literals(' ',Stream,Literals):- !, read_literals(Stream,Literals).   -  person piyo_kuro    schedule 22.08.2017
comment
часть 2 read_line_then_literals('\n',Stream,Literals):- !, read_literals(Stream,Literals). read_line_then_literals(_C,Stream,Literals):- read_line_then_literals(Stream,Literals). read_literal_then_literals(Stream,As,Literals):- get_char(Stream,C), read_literal_then_literals(C,Stream,As,Literals).   -  person piyo_kuro    schedule 22.08.2017
comment
часть 3 ` read_literal_then_literals(C,Stream,As,Literals):-цифра(C),!, имя(C,[A]), read_literal_then_literals(Stream,[A|As],литералы). read_literal_then_literals(C,Stream,As,Literals):- reverse(As,RevAs), name(Literal,RevAs), Literals=[Literal|Rest_Literals], read_literals(C,Stream,Rest_Literals). цифра ("0"). цифра ("1"). цифра ("2"). цифра ("3"). цифра ("4"). цифра ("5"). цифра ("6"). цифра ("7"). цифра ("8"). цифра('9').`   -  person piyo_kuro    schedule 22.08.2017
comment
часть 4 read_clauses([],[],[]). read_clauses([0|Literals],Clause,Clauses):- !, reverse(Clause,RevClause), Clauses=[RevClause|RestClauses], read_clauses(Literals,[],RestClauses). read_clauses([Literal|Literals],Clause,Clauses):- read_clauses(Literals,[Literal|Clause],Clauses).   -  person piyo_kuro    schedule 22.08.2017
comment
Как File передается предикату Parser? Можете ли вы привести несколько примеров ввода с ожидаемым результатом? Что использует предикат read_literal_then_literals? Здесь весь код?   -  person Guy Coder    schedule 22.08.2017
comment
Файл фактически заменяется адресом файла cnf.   -  person piyo_kuro    schedule 26.08.2017


Ответы (1)


Чтобы иметь решатель SAT, управляемый базисом Грёбнера, при использовании обычного целочисленного полиномиального частного подхода вам нужно будет использовать перевод булевой логики Джорджа Буля:

а) Отрицание ~x будет преобразовано в 1-x.

б) Конъюнкцией, дизъюнкцией является следующая x&y = xy, x v y = x+y-xy.

в) Да, вам нужно добавить условие Буля x*(x-1) = 0, которое говорит, что x равно 0 или 1. Но вы легко видите, что это то же самое, что сказать x*x = x.

Но ограничение полиномиальных коэффициентов до 0,1 не работает, так как, например, Xor уже нуждается в коэффициенте 2:

х или у = х + у - 2ху

Это действительно работает, хотя и немного медленно. Чтобы проверить, является ли формула A тавтологией, вы можете позволить алгоритму базиса Грёбнера пройти через ~A плюс все уравнения c). Если результатом являются только уравнения c) формула в общем случае верна.

Для кода:
https://gist.github.com/jburse/99d9a636fd6218bac8c380c093e06287#gistcomment-2032509

Альтернативным подходом было бы использование логического кольца и соответствующих многочленов. Тогда вам не нужно было бы формулировать условие c), так как оно выполняется автоматически.

person Mostowski Collapse    schedule 01.11.2018