Дизъюнктивная нормальная форма с предикатом диапазона

Question

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

Пример: (x> 40) & ((x> 50) | (y> 10)) -> (x> 50) | (x> 40) & (y> 10)

В принципе, я хочу просто такое выражение, чтобы оценивать как можно быстрее.

Кто-нибудь может мне помочь?

Answer 1

Инструменты, такие как ANTLR, помогут вам построить дерево разбора для вашего выражения. Возможно, вы сможете «сгладить» дерево на основе коммутативных свойств ваших операторов. Я лично не знаю об алгоритме или библиотеке, которые это сделают.

Answer 2

Wolfram Alpha обрабатывает ваше выражение довольно хорошо:

see here.

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