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

Question

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

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

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

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

Answer 1

Wolfram Alpha хорошо справляется с вашим выражением:

+40)+and+(+(x+>+50)+or+(y+>+10))" rel="nofollow noreferrer"> см. Здесь .

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

Answer 2

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