将总和的乘积展开为最小的乘积和

Question

我正在尝试写 Petrick's method, which is a technique for Quine–McCluskey algorithm。

假设我有一个数学方程式，它由 + 和 * 组成。例如：

(K+L)(K+M)(L+N)(M+P)(N+Q)(P+Q)

我怎样才能扩展方程得到所有乘积的总和，像这样？

K*K*L*M*N*P + K*K*L*M*N*Q + .... (63 terms)

(用WolframAlpha可以看到推断的结果)

Answer 1

我有点怀疑这是你想要的，但是要获得字符数组的结果...

w = Expand[(K + L) (K + M) (L + N) (M + P) (N + Q) (P + Q)];
x = ToString@InputForm[w];
z = StringReplace[x, y_ ~~ "^2" :> StringJoin[y, "*", y]]

K*K*L*M*N*P + K*L*L*M*N*P + K*L*M*M*N*P + ... + L*M*N*P*Q*Q

DeleteCases[Characters@z, " "]

{K,*,K,*,L,*,M,*,N,*,P,+, ... ,+,L,*,M,*,N,*,P,*,Q,*,Q}

Answer 2

我收到的条款比你预期的要少 - 只有 5 个而不是 63 个：

作为 Boolean 表达式：

(k+l) & (l+n) & (k+m) & (m+p) & (n+q) & (p+q)


knp + lmq + lmnp + klpq + kmnq

查看 this site 背后的 JavaScript 代码可能会很有趣。它是 Petrick 的 方法在 JavaScript.

中的一个实现

Answer 3

关于你的陈述

"I'm trying to write a Petrick's method, which is a technique for Quine–McCluskey algorithm."

我给你看一个

准备好使用 Petrick 的方法和
也是一个完整的 Quine & McCluskey 实现和
我实现的算法的解释

首先，完整的解决方案可以在这里找到：

MCDC

源代码是使用集合操作高效实现的优雅解决方案：

// Functor operator for applying Petricks methhod
ProductTermVector PetricksMethod::operator ()(const CNF& cnf)
{
    // We select an iterative approach. Start with the first Element of the CNF (which is a DNF)
    // And we store the result of each iterative operation again in this element
    DNF resultingDNF{ cnf[0] };
    // We will always start with the element 1 (not element 0) because in 0 is the initial value
    // or respectively the intermediate result
    for (CNF::size_type dnfInCnfIndex = 1; dnfInCnfIndex < cnf.size(); ++dnfInCnfIndex)
    {
        // Result of multipliying out the intermediate (initial) value with the current CNF Product term
        DNF intermediateCalculatedDNF;
        // Now go through all elements of the intermediate (initial) product term/DNF
        // For (1+2)(3+4)  this would be the (1+2) part
        for (const ProductTerm& productTermLeftSide : resultingDNF)
        {
            // Next we will iterate over all Minterms in the next DNF
            // For (1+2)(3+4)  this would be the (3+4) part
            for (const ProductTerm& productTermRightSide : cnf[dnfInCnfIndex])
            {
                ProductTerm productTerm{ productTermLeftSide }; // Resulting Product term is now 1
                // Add all elements from the right side
                productTerm.insert(productTermRightSide.begin(), productTermRightSide.end());   // Resulting Product term is now 1,2
                intermediateCalculatedDNF.insert(std::move(productTerm));  // Store this one
                // And continue to add more product terms. The stl::set will ensure the idempotence law and prevent memory waste
            }
        }
        // And now add all found terms to the result and continue with the next element of the right hand side
        // Please note: also here the set will prevent double terms
        resultingDNF = std::move(intermediateCalculatedDNF);
    }

    // Now we have the result (with 10 lines of code). The result contains all product terms in DNF
    // But for our prupose we are only interested in the minimum size terms
    // so, lets find the element with the minimu size (can be more than one)
    uint minLength{ narrow_cast<uint>(std::min_element(resultingDNF.begin(), resultingDNF.end(), [](const ProductTerm & left, const ProductTerm & right) noexcept {return left.size() < right.size(); })->size()) };
    // And from the big list of the DNF with all product terms, we copy all elements having the minimu size to the result. These are our best coverage sets
    ProductTermVector cheapestVector;
    // Copy result and return it to caller
    std::copy_if(resultingDNF.begin(), resultingDNF.end(), std::back_inserter(cheapestVector), [&minLength](const ProductTerm& pt) noexcept {return pt.size() == minLength; });
    return cheapestVector;
}

净代码行数为14。使用了一些额外的定义，使类型的理解和使用更容易：

using BooleanVariable = uint_fast8_t;
using ProductTerm = std::set<BooleanVariable>;
using ProductTermVector = std::vector<ProductTerm>;
// Disjunctive Normal Form
using DNF = std::set<ProductTerm>;
// Conjunctive Normal Form
using CNF = std::vector<DNF>;

class PetricksMethod    // Functor
{
public:
    ProductTermVector operator()(const CNF& cnf); // Functor operator
};

请注意。 "BooleanVariable" 类型也可以是字符、字符串或任何您喜欢的类型。这对实现无关紧要，但会对消耗的内存产生影响。

此算法背后的想法是使用 "STL set" 并采用集合操作的属性。例如，如果您查看术语 (a+b)(c+d)：如果您想将其相乘，则结果将是：ac+ad+bc+bd。如果您将布尔变量视为只有一个成员的特殊乘积项，并将该乘积项作为一个集合来实现，那么操作就是将变量添加到现有集合中。所以，如果你有一个包含 "a" 的集合，并且你想将它与包含 "b" 的集合相乘，那么你只需将 "b" 添加到 "a"。该集合将包含 "ab".

所以，我们将把包含"b"的集合插入到包含"a"的集合中，依此类推。我们将循环执行此操作并将获得 4 组（乘积项）。这 4 个集合构成了最终的 DNF。刚刚计算出的DNF可以和CNF的附加项进一步结合

如果我们有“(a+b)(c+d)(e+f)”，我们会将其视为“((a+b)(c+d)) (e+f) ”。我们首先将前 2 个 MaxTerms 相乘，得到 (ac+ad+bc+bd) 并对 (e+f) 应用相同的算法。我们将始终向现有集合添加新变量。我们将迭代地执行此操作，直到评估完整的表达式。

问题是产生的子项太多了。但幸运的是，具有独特排序元素的集合属性在这里会有所帮助。对于 (a+b)(b+a) 我们会得到 ab+aa+bb+ba。 stl集会为我们提供幂等律。意思是 "a" AND "a" 是 "a"，"b" 或 "b" 是 "b"。因此，尝试将 "a" 添加到已经包含 "a" 的集合中是行不通的。结果仍然是"a"。与完整的乘积项相同，如 2 倍 "ab"。它们不会被添加到 DNF 替身。所以，上述操作的结果是：

ab+aa+bb+ba --> ab+ab+aa+bb --> ab+aa+bb --> a+b+ab

采用这种方法，将不会出现双重任期，而且通常会缩短任期。

但请注意。计算时间和内存消耗会随着项数的增加呈几何级数增长。因此该函数只能应用于有限数量的变量/项。

我希望我能给出一个可以理解的解释。如果您需要更多信息，请询问。

将总和的乘积展开为最小的乘积和

Expand product of sums to a minimum sum of products

algorithm

math

boolean-logic

wolfram-mathematica

algebra