如何在 JavaScript 中高效地分发逻辑表达式

Question

假设你有这个逻辑表达式

(A or B or C) and (D or E) and (F or G or H)

正如您在这里看到的，我们在括号内有 OR 运算符，在括号外有 AND 运算符。我们可以说这个逻辑表达式是 AND(OR) 类型。

我想将这个表达式转换为 OR(AND)。

例子：

(A or B) and (C or D) = (A and C) or (A and D) or (B and C) or (B and D)

实现这一点的简单方法（在 JavaScript 中）：

class OrNode<C = string> {
    /* constructor logic */
    nodeType = 'OR';
    children: C[];
}

class AndNode<C = string> {
    /* constructor logic */
    nodeType = 'AND';
    children: C[];
}

function convert(expression: AndNode<OrNode>): OrNode<AndNode> {
    let children: AndNode[] = [{ nodeType: 'AND', children: [] }];
    expression.children.forEach((orNode) => {
        let temp = children;
        children = [];
        orNode.children.forEach((leafNode) => {
            temp.forEach((andNode) => {
                children.push({
                    nodeType: 'AND',
                    children: [...andNode.children, leafNode],
                });
            });
        });
    });
    return new OrNode<AndNode>({ nodeType: 'OR', children });
}

假设我们有这个表达式：

const expression = new AndNode<OrNode>({
    nodeType: 'AND',
    children: [
        { nodeType: 'OR', children: ['A', 'B', 'C'] },
        { nodeType: 'OR', children: ['D', 'E'] },
        { nodeType: 'OR', children: ['F', 'G', 'H'] },
    ]
});

然后，如果我们进行转换，新的转换后的表达式将等于

{
    nodeType: 'OR',
    children: [
        { nodeType: 'AND', children: ['A', 'D', 'F'] },
        { nodeType: 'AND', children: ['A', 'D', 'G'] },
        { nodeType: 'AND', children: ['A', 'D', 'H'] },
        { nodeType: 'AND', children: ['A', 'E', 'F'] },
        { nodeType: 'AND', children: ['A', 'E', 'G'] },
        { nodeType: 'AND', children: ['A', 'E', 'H'] },
    
        { nodeType: 'AND', children: ['B', 'D', 'F'] },
        { nodeType: 'AND', children: ['B', 'D', 'G'] },
        { nodeType: 'AND', children: ['B', 'D', 'H'] },
        { nodeType: 'AND', children: ['B', 'E', 'F'] },
        { nodeType: 'AND', children: ['B', 'E', 'G'] },
        { nodeType: 'AND', children: ['B', 'E', 'H'] },

        { nodeType: 'AND', children: ['C', 'D', 'F'] },
        { nodeType: 'AND', children: ['C', 'D', 'G'] },
        { nodeType: 'AND', children: ['C', 'D', 'H'] },
        { nodeType: 'AND', children: ['C', 'E', 'F'] },
        { nodeType: 'AND', children: ['C', 'E', 'G'] },
        { nodeType: 'AND', children: ['C', 'E', 'H'] },
    ]
}

这个蛮力解决方案的复杂度是O(M^N)，M是括号之间的条件的最大数量，N是括号块的数量。

有没有办法有另一种算法并降低这种复杂性？

Answer 1

您有一个“合取范式”的表达式，并且您想将其转换为“析取范式”。

转换总是可能的，但它也解决了诸如布尔可满足性之类的 NP 难题，因此没有已知的有效方法来确定结果公式是否为空。

事实上，对于某些输入，所得公式的大小将呈指数级增长，因此高效转换肯定是不可能的。上面的 DNF 维基百科文章中给出了一个简单的例子：

（a ₁或 b ₁）和（a ₂或 b ₂）和...（a _n或 b _n）

将在 DNF 中展开以包含 2 ⁿ个项。