Kalombyr
@Kalombyr

Есть ли готовая библиотека или алгоритм для превращения if выражения в CNF формулу?

Доброго дня!
Для SAT солвера нужны формулы в CNF формате, т.е.:
(a | b | c) &
(a | !d ) &
(a | !c )

т.е. можем использовать только "и" "или" "не", причём в каждой строке переменные ИЛИ, а каждая строка объединяется как И, ну и только у переменной можно использовать отрицание.

Как можно сконвертировать вот такие условия:
if ( (a && b && c) || (c && d && f) || )
Нужно именно либо алгоритм, а в идеале готовую библиотеку, подскажите, пожалуйста.
  • Вопрос задан
  • 72 просмотра
Решения вопроса 1
@lorc
Ну собственно алгоритм прямо в Википедии описан.

Если термов не очень много - можно попробовать применить Метод Куайна—Мак-Класки. Таким образом вы убьете двух зайцев сразу - получите не просто КНФ, а минимальную КНФ.
Ответ написан
Комментировать
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы