我在哪里可以找到将任意布尔表达式转换为合取或析取范式的方法？

发布于 2024-12-13 10:14:10 字数 500 浏览 0 评论 0原文

我编写了一个小应用程序，它将表达式解析为抽象语法树。现在，我对表达式使用一系列启发式方法来决定如何最好地评估查询。不幸的是，有些例子使查询计划变得非常糟糕。

我找到了一种方法，可以证明对如何评估查询做出更好的猜测，但我需要首先将我的表达式放入 CNF 或 DNF 中，以获得可证明正确的答案。我知道这可能会导致时间和空间呈指数级增长，但对于我的用户运行的典型查询来说，这不是问题。

现在，为了简化复杂的表达式，我一直手动转换为 CNF 或 DNF。（好吧，也许不是一直，但我确实知道如何使用例如德摩根定律、分配定律等来实现这一点。）但是，我不确定如何开始将其转化为一种方法可以作为算法实现。我看过有关查询优化的论文，其中有几篇以“首先我们将内容放入 CNF”或“首先我们将内容放入 DNF”开头，但他们似乎从未解释过实现这一目标的方法。

我应该从哪里开始？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

路还长，别太狂 2024-12-20 10:14:10

看看 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']

更新：现在我更喜欢这个 sympy 逻辑包：

>>> 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)

Look at https://github.com/bastikr/boolean.py
Example:

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)))

Output is:

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

UPDATE: Now I prefer this sympy logic package:

>>> 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)

回复收藏 0 原文