Задать вопрос
Kalombyr
@Kalombyr
алгоритмы

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

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

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

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

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

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

Похожие вопросы
Вакансии с Хабр Карьеры
С developer (алгоритмист)
СберТех • Москва
от 350 000 ₽
Разработчик WebRTC-сервисов на Go в видеоплатформу
Яндекс • Москва
от 300 000 до 490 000 ₽
С/С++ Linux разработчик
Tempesta Technologies
До 8 000 $
Ещё вакансии
Заказы с Хабр Фриланса
Во Flutter доделать функцию из Ton блокчейна (выставление на продажу)
25 нояб. 2024, в 19:44
20000 руб./за проект
Здравствуйте! Меня зовут Александр, я HR-менеджер компаний Свежий Сове
25 нояб. 2024, в 19:41
300000 руб./за проект
Перенести сайт на CMS Wordpress c Tilda
25 нояб. 2024, в 18:33
10000 руб./за проект
Ещё заказы