java - 在Java中生成最小项的总和

如何在Java中生成最小项的总和（布尔代数）？我们可以用(X+X')生成最小项引发AND的总和。以下示例说明了具有三个变量A，B和C的函数的算法：

F(A,B,C)= A + B´*C
        = A*(B+B´) + B´*C
        = A*B + A*B´ + B´*C
        = A*B*(C+C´) + A*B´*(C+C´) + B´*C*(A+A´)
        = A*B*C+A*B*C´+A*B´*C+A*B´*C´+B´*C*A+B´*C*A´
        = A*B*C+A*B*C´+A*B´*C+A*B´*C´+A*B´*C+A´*B´*C

Java中的方法如下所示：

String generateSumOfMinterms(String termsOfTheFunction, String variables){}


// Examples for functions with 2 variables A,B
generateSumOfMinterms("A", "A,B"){

//The result should looks like this
return "A*B+A*B'";
}
generateSumOfMinterms("A+B'", "A,B"){

//The result should looks like this (repeated terms are ok for example A*B')
return "A*B+A*B'+A'*B'+A*B'";
}


// Example for a function with 3 variables A,B,C
generateSumOfMinterms("A", "A,B,C"){

//The result should looks like this
return "A*B*C+A*B*C'+A*B'*C+A*B'*C'";
}

我尝试了以下方法：

public List<Minterm> completeMinterm(Minterm minterm, String variables){
    List<Minterm> minterms=new ArrayList<Minterm>();
    minterms.add(minterm);
    Minterm m1=new Minterm();
    Minterm m2=new Minterm();
    for (int k = 0; k < minterms.size(); k++) {
 //A AB--> AB+AB'
        for (int i = 0; i < variables.length(); i++) {
        boolean varInMinterm=false;
        for (int j = 0; j < minterms.get(k).atoms.size(); j++) {
            if(minterms.get(k).atoms.get(j).variable==variables.charAt(i)){
                varInMinterm=true;
                break;
            }
        }
        if(!varInMinterm){
            varInMinterm=false;
            m1= minterms.get(k);
            m1.addAtom(new Atom(variables.charAt(i),false));
            m2 = minterms.get(k);
            m2.addAtom(new Atom(variables.charAt(i),true));
            minterms.remove(k);
            minterms.add(m1);
            minterms.add(m2);
            k=0;

        }
    }
    }

我使用eclipse调试器查找错误，我不明白，为什么在运行此行的同时将添加到m2的原子也同时添加到m1：

m2.addAtom(new Atom(variables.charAt(i),true));

最佳答案

下面是一种可能的方法的概述：首先，您应该创建一个更方便的表达式表示形式-例如，表达式可以是Minterm类的实例列表，而Minterm可以包含实例列表Atom类中的每个，每个都可以包含一个char来告诉它是哪个变量，以及一个boolean来告诉变量是否被取反。您应该做的第一件事是遍历termsOfTheFunction并创建表示表达式的对象。然后，您可以遍历minterm，每次看到缺少一个变量的minterm时，都可以将其从列表中删除，并添加两个带有缺失变量的新minterm。最后，您可以遍历完成的minterm，并将它们“打印”为结果String。

每个请求的类声明，为了清楚起见（为简洁起见，使用公共字段）：

public class Atom {
    public final char variable;
    public final bool negated;
    public Atom(char variable, bool negated) {
        this.variable = variable;
        this.negated = negated;
    }
}

public class Minterm {
    public final List<Atom> atoms = new ArrayList<Atom>();
}

在generateSumOfMinterms()中：

List<Minterm> expression = new ArrayList<Minterm>();
Minterm currentMinterm = new Minterm();
expression.add(currentMinterm);

然后，循环浏览termsOfTheFunction的字符。每次您看到一个字母时，请查看下一个字符以查看它是否为´，并添加一个带有该字母并带有正确否定符的Atom。每次看到+时，创建一个新的Minterm并将其添加到expression，然后继续进行。之后，您可以开始分析最小项并进行扩展。

根据您的代码进行编辑：看来您一切顺利！两个原子都添加到相同的最小项的原因是，因为m1和m2，m1 = minterms.get(k);和m2 = minterms.get(k);都引用了第k个最小项。 get()不会从列表中复制或删除元素；元素仍将在列表内。因此，对于m2，您需要创建一个新的minterm，其中要包含旧原子中的所有原子以及新原子。