Где я могу найти метод для преобразования произвольного логического выражения в конъюнктивную или дизъюнктивную нормальную форму?

Question

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

Я нашел способ убедительно составить более точные предположения о том, как следует оценивать запросы, но мне нужно сначала поместить свое выражение в CNF или DNF, чтобы получить достоверно правильные ответы. Я знаю, что это может привести к потенциально экспоненциальному времени и пространству, но для типичных запросов, выполняемых моими пользователями, это не проблема.

Теперь я все время делаю конвертацию в CNF или DNF, чтобы упростить сложные выражения. (Ну, может быть, не всегда, но я знаю, как это делается, используя, например, законы Деморгана, законы распределения и т. Д.) Однако я не уверен, как начать переводить это в метод, который может быть реализован как алгоритм. Я посмотрел статьи по оптимизации запросов, и некоторые из них начинаются с "ну, сначала мы помещаем вещи в CNF" или "сначала мы помещаем вещи в DNF", и они, кажется, никогда не объясняют свой метод для достижения этой цели.

С чего мне начать?

Answer 1

Наивный ванильный алгоритм для формул без кванторов:

• для CNF преобразовать в отрицательную нормальную форму с законами Де Моргана, затем распределить ИЛИ по AND
• для DNF преобразовать в отрицательную нормальную форму с законами Де Моргана, затем распределить И по ИЛИ

Мне неясно, если ваши формулы количественно. Но даже если это не так, кажется, что конец статей в Википедии о конъюнктивной нормальной форме и ее - примерно эквивалентно в мире автоматизированных проверок теормов - клаузальных нормальных форм альтер-эго обрисовывают в общих чертах используемый алгоритм (и указывают на ссылки, если вы хотите чтобы сделать это преобразование немного более умным). Если вам нужно больше, пожалуйста, расскажите нам больше о том, где вы столкнулись с трудностями.

Answer 2

Посмотрите на https://github.com/bastikr/boolean.py Пример:

def test(self):
    expr = parse("a*(b+~c*d)")
    print(expr)

    dnf_expr = normalize(boolean.OR, expr)
    print(list(map(str, dnf_expr)))

    cnf_expr = normalize(boolean.AND, expr)
    print(list(map(str, cnf_expr)))

Выход:

a*(b+(~c*d))
['a*b', 'a*~c*d']
['a', 'b+~c', 'b+d']

ОБНОВЛЕНИЕ: Теперь я предпочитаю этот симпозиальный пакет логики:

>>> from sympy.logic.boolalg import to_dnf
>>> from sympy.abc import A, B, C
>>> to_dnf(B & (A | C))
Or(And(A, B), And(B, C))
>>> to_dnf((A & B) | (A & ~B) | (B & C) | (~B & C), True)
Or(A, C)

Answer 3

Я наткнулся на эту страницу: Как конвертировать формулу в CNF. Он показывает алгоритм для преобразования логического выражения в CNF в псевдокоде. Помог мне начать работу в этой теме.