# Boolsche Algebra via eval vereinfachen -> Ausmultiplizieren gesucht



## NT2005 (25. Nov 2012)

Hallo Ihr,

Ich versuche zurzeit boolsche Ausdrücke zu vereinfachen. Dazu habe ich mir ein paar _eval_ Biblotheken angeschaut.

Ich verwende zurzeit Javalator, gefällt mir recht gut. Es beginnt mit der niedrigsten Klammer und alles läuft rund.


```
/* The logical AND operator. */
    final static Operator AND = new Operator("*", 2, Operator.Associativity.LEFT, 2);
    /* The logical OR operator. */
    final static Operator OR = new Operator("+", 2, Operator.Associativity.LEFT, 1);

    @Override
    protected String evaluate(Operator operator, Iterator<String> operands,
                              Object evaluationContext) {
        List<String> tree = (List<String>) evaluationContext;
        String o1 = operands.next();
        String o2 = operands.next();

        cout (o1 + operator.getSymbol() +  o2);

        String eval = "";
        if (operator == OR) {
           ...
        } else if (operator == AND) {
           ...
        }
        return eval;
    }
```

Jedoch würde ich mir wünschen, dass als aller erstes ausmultipliziert wird. Jedoch habe ich keine Ahnung wie dies gehen soll.

Folgender Ablauf:
(a*b+c) * d
a*b*d+c*d 
und dann nach * und + lösen. 

Jemand eine Idee wie man dies macht oder kennt jemand eine andere Biblothek die dies unterstützt?
Beste Grüße und einen Schönen Sonntag!


----------



## Antoras (25. Nov 2012)

Wenn du als erstes ausmultiplizieren möchtest, dann muss du auch als erstes ausmultiplizieren. Das bedeutet, dass du den AST mehr als einmal durchlaufen musst. Beim ersten Mal machst du nichts anderes wie ausmultiplizieren (und etwaige andere Umformungen) wohingegen du beim zweiten Mal den AST dann auflösen kannst.


----------



## NT2005 (25. Nov 2012)

Hallo Antoras,

Danke für die Hilfe. Das habe ich jetzt gemacht und funktioniert auch.
Jedoch scheitere ich an der Vereinfachung von ODER-Verknüpfungen.

Also wenn ich dies habe: _a*b*c + a*b*c = a*b*c_ bekomm ich dies hin, aber so etwas wie: _a*b*c + a*b = a*b_ fehlt mir der richtige Algorithmus.

Gibt es denn schon so etwas fertiges in Java oder C++/C?
Was ich bisher gefunden habe ist dies: https://github.com/alkant/simbool oder Lisp-Quelle aber diese zwei Sprachen beherrsche ich so gut wie gar nicht. :/


----------



## Spacerat (26. Nov 2012)

Vieles lässt sich in Programmen per Tabellen und Diagrammen vereinfachen. Evtl. sagen dir im Bereich boolscher Algebra in Verbindung mit Wahrheitstabellen und wie man diese vereinfacht ja KV-Diagramme etwas. Wenn nicht, dann such' dir Quellcode oder zerpflück' halt das Applet auf der verlinkten Seite und schau nach, wie die das damit lösen.
Zu guter letzt ist hier noch ein WIKI-Link.

Karnaugh-Veitch-Diagramm ? Wikipedia

Ich hoffe das hilft weiter.


----------



## NT2005 (26. Nov 2012)

Danke Spacerat,

Karnauh wollte ich eigentlich meiden, da ich später nicht mit 4 Variablen sondern eher 100+ arbeiten will.
Deshalb wollte ich es durch "genaues hinsehen" (Vergleichen) erreichen.


----------



## SlaterB (26. Nov 2012)

> Also wenn ich dies habe: a*b*c + a*b*c = a*b*c bekomm ich dies hin, aber so etwas wie: a*b*c + a*b = a*b fehlt mir der richtige Algorithmus.

bekommst du es mit dem Kopf hin? wenn es nicht gerade um Probleme wie 'Erkennen einer Blume in Wiese' oder 'Erkennen der Ironie in einer Regierungserklärung' geht, dann wäre es günstig auch einfach nachzuforschen, welche Wege da in deinem Denken abfolgen,

das + trennt zwei Gruppen, zwei Kandidaten, diese analyisieren, auftrennen, Liste oder besser noch Set von Einzelelementen, 
wenn alle Elemente der einen Gruppe in der anderen drin sind, dann zusammenfassen,

bei n Kandidaten notfalls n^2 paarweise Vergleiche, evtl. etwas einsparen durch gewisse Grundaufteilung nach Elementen,
wenn aber alle das 'a' enthalten..


----------



## NT2005 (26. Nov 2012)

Hallo Slater,

Ja, dies bekomme ich im Kopf hin. Werde mich mal daran nochmal probieren und Fortschritte hier posten.
Danke für den Hinweis mit den Set, daran habe ich gar nicht mehr gedacht.


----------



## NT2005 (26. Nov 2012)

Hier nun der aktuelle Stand:
-ausmultiplizieren über extra Evaluator (kann man dies evtl. besser machen, in einem Evaluator?)
-alle UND Terme vereinfachen
-alle gleichen oder abhängigen ODER Terme vereinfachen

Noch nicht implementiert:
-ODER Terme vereinfachung wenn negationen vorhanden z.B. a*b*~t + a*b*t = a*b



```
import java.util.*;

import net.astesana.javaluator.*;

class ExpandLogic extends AbstractEvaluator<String> {

    /* The logical AND operator. */
    final static Operator AND = new Operator("*", 2, Operator.Associativity.LEFT, 2);
    /* The logical OR operator. */
    final static Operator OR = new Operator("+", 2, Operator.Associativity.LEFT, 1);

    private static final Parameters PARAMETERS;

    static {
        // Create the evaluator's parameters
        PARAMETERS = new Parameters();
        PARAMETERS.add(AND);
        PARAMETERS.add(OR);
        // Add the parentheses
        PARAMETERS.addExpressionBracket(BracketPair.PARENTHESES);
    }

    public ExpandLogic() {
        super(PARAMETERS);
    }

    @Override
    protected String toValue(String literal, Object evaluationContext) {
        return literal;
    }

    @Override
    protected String evaluate(Operator operator, Iterator<String> operands,
                              Object evaluationContext) {
        List<String> tree = (List<String>) evaluationContext;
        String o1 = operands.next();
        String o2 = operands.next();

        String eval = "";
        if (operator == AND) {
            Set<String> terms = new HashSet<String>();
            for (String term : o2.split("\\+")) {
                terms.add(o1 + AND.getSymbol() + term);
            }

            for (String term : terms) {
                eval += term + "+";
            }
            if (!eval.isEmpty())
                eval = eval.substring(0, eval.length() - 1);
        } else if (operator == OR) {
            eval = o1 + operator.getSymbol() + o2;
        }

        tree.add(eval);
        return eval;
    }
}

public class SimpleLogic extends AbstractEvaluator<String> {

    /* The logical AND operator. */
    final static Operator AND = new Operator("*", 2, Operator.Associativity.LEFT, 2);
    /* The logical OR operator. */
    final static Operator OR = new Operator("+", 2, Operator.Associativity.LEFT, 1);

    private static final Parameters PARAMETERS;

    static {
        // Create the evaluator's parameters
        PARAMETERS = new Parameters();
        // Add the supported operators
        PARAMETERS.add(AND);
        PARAMETERS.add(OR);
    }

    public SimpleLogic() {
        super(PARAMETERS);
    }

    @Override
    protected String toValue(String literal, Object evaluationContext) {
        return literal;
    }

    @Override
    protected String evaluate(Operator operator, Iterator<String> operands,
                              Object evaluationContext) {
        List<String> tree = (List<String>) evaluationContext;
        String o1 = operands.next();
        String o2 = operands.next();

        String eval = "";
        if (operator == AND) {
            boolean result = true;
            if (o1.contains("0") || o2.contains("0"))
                eval = "0";
            else {
                Set<String> vars = new TreeSet<String>();
                Collections.addAll(vars, o1.split("\\*"));
                vars.remove("1");
                if (!vars.contains(o2) && !o2.equals("1"))
                    vars.add(o2);
                if (vars.contains("~" + o2) || o2.contains("~") && vars.contains(o2.substring(1, o2.length())))
                    eval = "0";
                else
                {
                    for (String var : vars)
                        eval += var + operator.getSymbol();
                    if(!eval.isEmpty())
                        eval = eval.substring(0, eval.length()-1);
                }
            }
        } else if (operator == OR) {

            Set<String> vars = new TreeSet<String>();
            Collections.addAll(vars, o1.split("\\+"));
            vars.remove("0");

            if (vars.contains("1") || o2.equals("1")) {
                eval = "1";
            } else if (!o2.equals("0")) {

                Set<String> o2Vars = new HashSet<String>();
                Collections.addAll(o2Vars, o2.split("\\*"));
                int o2VarsLength = o2Vars.size();

                boolean equal = false;

                Iterator<String> varsIterator = vars.iterator();
                while (varsIterator.hasNext())
                {
                    String var = varsIterator.next();

                    if (var.equals(o2)) {
                        equal = true;
                        break;
                    }

                    Set<String> o1Vars = new HashSet<String>();
                    Collections.addAll(o1Vars, var.split("\\*"));
                    int o1VarsLength = o1Vars.size();

                    if (o1VarsLength == o2VarsLength) {
                        // Todo negations
                    } else if (o1VarsLength > o2VarsLength) {
                        if (o1Vars.containsAll(o2Vars)) {
                            varsIterator.remove();
                        }
                    } else {
                        if (o2Vars.containsAll(o1Vars))
                        {
                            equal = true;
                            break;
                        }
                    }
                }
                if (!equal)
                    vars.add(o2);

                for (String var : vars)
                    eval += var + operator.getSymbol();
                if(!eval.isEmpty())
                    eval = eval.substring(0, eval.length()-1);
            } else {
              eval = o1;
            }
        } else {
            throw new IllegalArgumentException();
        }

        tree.add(eval);
        return eval;
    }

    public static void main(String[] args) {

        String term = "t * (a*b + 1 + (a + c)) + a*b*t + a*c + a*c*d + c*d";

        // noch nicht implemtiert: a*b*~t + a*b*t-> a*b
        //term = "a*b*~t + a*b*t";

        ExpandLogic expandLogic = new ExpandLogic();
        String expandedLogic = doIt(expandLogic, term);

        SimpleLogic simpleLogic = new SimpleLogic();
        String result = doIt(simpleLogic, expandedLogic);
        System.out.println("---> " + result);
    }

    private static String doIt(AbstractEvaluator<String> evaluator, String expression) {
        List<String> sequence = new ArrayList<String>();
        evaluator.evaluate(expression, sequence);
        System.out.println("Evaluation sequence for :" + expression);
        for (String string : sequence) {
            System.out.println(string);
        }
        System.out.println();
        return sequence.get(sequence.size() - 1);
    }
}
```


----------



## Antoras (27. Nov 2012)

Als Tipp möchte ich hier noch erwähnen, dass du dir Recursive descent parser anschauen solltest. Einen Parser sich selbst zu bauen wird schnell sehr haarig wenn man die richtigen Algorithmen nicht kennt. Dein Programm bekommst du mit Sicherheit auch ohne hin, aber falls du das irgendwie noch mit anderen Sachen ergänzen möchtest, würde ich von Anfang an auf einen ordentlichen Parser setzen.


----------



## NT2005 (27. Nov 2012)

Hey Antoras,

Ich verwende doch Javalator. Ist das nicht so ein Parser? Der geht ja auch von innersten Operation (a+b) zur äußersten c*d*(r+d(a+b)).

Ich versuche ja "nur" den linken und rechten Operanden auszuwerten. Mich wundert es nur, dass es dies noch nicht wirklich public gibt....


----------



## Antoras (27. Nov 2012)

Ach stimmt, das hatte ich übersehen. Dann musst du dich darum natürlich nicht kümmern.

Das ganze gibt es mit Sicherheit schon fertig, nur wird wohl so selten danach gefragt, dass die Suchmaschinen lieber erst andere Sachen anzeigen.


----------



## NT2005 (29. Nov 2012)

Habe einmal etwas weiter gemacht. Hatte zum Beispiel beim ausmultiplizieren vergessen sachen wie: (a+b)*(c+b) mit auszurechnen.

Noch nicht implementiert sind immer noch:
-ODER Terme vereinfachung wenn negationen vorhanden z.B. a*b*~t + a*b*t = a*b

Ein kleiner Anfang ist drinnen, jedoch funktioniert dieser noch nicht wie es soll:

```
import java.util.*;

import net.astesana.javaluator.*;
import sun.font.TrueTypeFont;

class ExpandLogic extends AbstractEvaluator<String> {

    /* The logical AND operator. */
    final static Operator AND = new Operator("*", 2, Operator.Associativity.LEFT, 2);
    /* The logical OR operator. */
    final static Operator OR = new Operator("+", 2, Operator.Associativity.LEFT, 1);

    private static final Parameters PARAMETERS;

    static {
        // Create the evaluator's parameters
        PARAMETERS = new Parameters();
        PARAMETERS.add(AND);
        PARAMETERS.add(OR);
        // Add the parentheses
        PARAMETERS.addExpressionBracket(BracketPair.PARENTHESES);
    }

    public ExpandLogic() {
        super(PARAMETERS);
    }

    @Override
    protected String toValue(String literal, Object evaluationContext) {
        return literal;
    }

    @Override
    protected String evaluate(Operator operator, Iterator<String> operands,
                              Object evaluationContext) {
        List<String> tree = (List<String>) evaluationContext;
        String o1 = operands.next();
        String o2 = operands.next();

        String eval = "";
        if (operator == AND) {
            Set<String> terms = new HashSet<String>();

            for (String andVar : o1.split("\\+")) {
                for (String term : o2.split("\\+")) {
                    terms.add(andVar + AND.getSymbol() + term);
                }
            }

            for (String term : terms) {
                eval += term + "+";
            }
            if (!eval.isEmpty())
                eval = eval.substring(0, eval.length() - 1);
        } else if (operator == OR) {
            eval = o1 + operator.getSymbol() + o2;
        }

        tree.add(eval);
        return eval;
    }
}

public class SimpleLogic extends AbstractEvaluator<String> {

    /* The logical AND operator. */
    final static Operator AND = new Operator("*", 2, Operator.Associativity.LEFT, 2);
    /* The logical OR operator. */
    final static Operator OR = new Operator("+", 2, Operator.Associativity.LEFT, 1);

    private static final Parameters PARAMETERS;

    static {
        // Create the evaluator's parameters
        PARAMETERS = new Parameters();
        // Add the supported operators
        PARAMETERS.add(AND);
        PARAMETERS.add(OR);
    }

    public SimpleLogic() {
        super(PARAMETERS);
    }

    @Override
    protected String toValue(String literal, Object evaluationContext) {
        return literal;
    }

    @Override
    protected String evaluate(Operator operator, Iterator<String> operands,
                              Object evaluationContext) {
        List<String> tree = (List<String>) evaluationContext;
        String o1 = operands.next();
        String o2 = operands.next();

        String eval = "";
        if (operator == AND) {
            boolean result = true;
            if (o1.contains("0") || o2.contains("0"))
                eval = "0";
            else {
                Set<String> vars = new TreeSet<String>();
                Collections.addAll(vars, o1.split("\\*"));
                vars.remove("1");
                if (!vars.contains(o2) && !o2.equals("1"))
                    vars.add(o2);
                if (vars.contains("~" + o2) || o2.contains("~") && vars.contains(o2.substring(1, o2.length())))
                    eval = "0";
                else
                {
                    for (String var : vars)
                        eval += var + operator.getSymbol();
                    if(!eval.isEmpty())
                        eval = eval.substring(0, eval.length()-1);
                }
            }
        } else if (operator == OR) {

            Set<String> vars = new TreeSet<String>();
            Collections.addAll(vars, o1.split("\\+"));
            vars.remove("0");

            if (vars.contains("1") || o2.equals("1")) {
                eval = "1";
            } else if (!o2.equals("0")) {

                Set<String> o2Vars = new HashSet<String>();
                Collections.addAll(o2Vars, o2.split("\\*"));
                int o2VarsLength = o2Vars.size();
                boolean o2HasNot = o2.contains("~");

                boolean equals = false;

               Set<String> newVars = new HashSet<String>();

                Iterator<String> varsIterator = vars.iterator();
                while (varsIterator.hasNext())
                {
                    String var = varsIterator.next();

                    if (var.equals(o2)) {
                        equals = true;
                        break;
                    }

                    Set<String> o1Vars = new HashSet<String>();
                    Collections.addAll(o1Vars, var.split("\\*"));
                    int o1VarsLength = o1Vars.size();
                    boolean o1HashNot = var.contains("~");

                    if (o1VarsLength == o2VarsLength) {
                        if(o1HashNot || o2HasNot) {
                            String newVar = checkDisjunktionSimilarity(o1Vars, o2Vars);
                            if (newVar != null)
                            {
                                newVars.add(newVar);
                                varsIterator.remove();
                                equals = true;
                            }
                        }

                    } else if (o1VarsLength > o2VarsLength) {
                        if (o1Vars.containsAll(o2Vars)) {
                            varsIterator.remove();
                        } else if(o1HashNot || o2HasNot) {
                            String newVar = checkDisjunktionSimilarity(o2Vars, o1Vars);
                            if (newVar != null) {
                                newVars.add(newVar);
                                equals = true;
                            }
                        }
                    } else {
                        if (o2Vars.containsAll(o1Vars))
                        {
                            equals = true;
                            break;
                        } else if(o1HashNot || o2HasNot) {
                            String newVar = checkDisjunktionSimilarity(o1Vars, o2Vars);
                            if (newVar != null) {
                                newVars.add(newVar);
                                equals = true;
                            }
                        }
                    }
                }
                if (!equals)
                    vars.add(o2);

                vars.addAll(newVars);

                for (String var : vars)
                    eval += var + operator.getSymbol();
                if(!eval.isEmpty())
                    eval = eval.substring(0, eval.length()-1);

            } else {
              eval = o1;
            }
        } else {
            throw new IllegalArgumentException();
        }

        tree.add(eval);
        return eval;
    }

    public static String checkDisjunktionSimilarity(Set<String> smallOp, Set<String> bigOp)
    {
        boolean similar = false, oneNot = false;
        String newVar = "";
        Iterator<String> o2VarsIterator = bigOp.iterator();
        while (o2VarsIterator.hasNext())
        {
            String o2Var = o2VarsIterator.next();
            if (!(smallOp.contains("~"+o2Var) || smallOp.contains(o2Var.substring(1)))) {
                newVar += o2Var+AND.getSymbol();
                if (smallOp.contains(o2Var))
                    similar = true;
            } else {
                similar = true;
                if (oneNot == false)
                    oneNot = true;
                else {
                    oneNot = false;
                    break;
                }
            }
        }

        if(similar && oneNot) {
            if (newVar.length() > 1)
                newVar = newVar.substring(0, newVar.length()-1);
            return newVar;
        }
        return null;
    }

    public static void main(String[] args) {

        Set<String> smallOne = new HashSet<String>();
        smallOne.add("a");
        smallOne.add("b");
        smallOne.add("~c");
        //smallOne.add("~d");

        Set<String> bigOne = new HashSet<String>();
        bigOne.add("a");
        bigOne.add("b");
        bigOne.add("c");
        //bigOne.add("~d");
       /// bigOne.add("e");


        //cout(checkDisjunktionSimilarity(smallOne, bigOne).toString());

        String term = "t * (a*b + 1 + (a + c)) + a*b*t + a*c + a*c*d + c*d";

        //term = "a*b*~c*~d + a*b*~c*~d";
        // nicht implemtiert -> a*b
        term = "a+~b+~a*b+(a+~b)*(~a*b)";

        //term = "b*~a+a";

        ExpandLogic expandLogic = new ExpandLogic();
        String expandedLogic = doIt(expandLogic, term);

        SimpleLogic simpleLogic = new SimpleLogic();
        String result = doIt(simpleLogic, expandedLogic);
        cout(result);
    }

    private static String doIt(AbstractEvaluator<String> evaluator, String expression) {
        List<String> sequence = new ArrayList<String>();
        evaluator.evaluate(expression, sequence);
        System.out.println("Evaluation sequence for :" + expression);
        for (String string : sequence) {
            System.out.println(string);
        }
        System.out.println();
        return sequence.get(sequence.size() - 1);
    }

    public static void cout(Object o) {
        System.out.println(o);
    }
}
```


----------



## NT2005 (30. Nov 2012)

Habe nun endlich eine passende Library gefunden über Google.
Erspart mir eine Menge Arbeit. 

Minimizing Boolean Functions

Ach Mist, das unterstützt nur 26 Buchstaben...


----------



## Landei (30. Nov 2012)

Na du wirst doch den Sourcecode ein bisschen aufbohren können...


----------



## NT2005 (30. Nov 2012)

Hmm, habe mir den jetzt angeschaut. Sehr gut geschrieben und auch kommmentiert. Die Variante ist sehr sauber und führt zu den richtigen Ergebnissen. Aber er verwendet Minterme. Das heißt, er geht jedes Ergebnis durch (ähnlich wie Karnaugh). 
Das bedeutet, bei n Variablen sind das 2^n Berechnungen.

Die Lösung für _a+b+c+d+e+f+g+h+i+j+k+l+m+n+o+p+q+r+s+t+u+v+w+x+y+z_ endet in java.lang.OutOfMemoryError: Java heap space. 67 108 864 Minterme müsste er aufstellen und diese müssten alle verglichen werden. Zu Speicheraufwendig und rechenintensiv.

Komm ich wohl doch nicht darum rum.


----------



## NT2005 (2. Dez 2012)

Ein Update des aktuellen Standes.

Leider noch nicht wirklich an der Vereinfachung von den Nicht Termen vorrangekommen, dagegen eine sehr wichtige Sache hinzugefügt, die ich glatt vergessen hatte und zwar die _De Morgan’sche Gesetze_. Diese habe ich jetzt in die Klasse ExpandLogic eingearbeitet.

Terme wie ~(a+~b*c) werden richtig zu ~a*b+~a*~c aufgelöst.

Bin immer noch über jede Hilfe dankbar. Komplementärgesetze und Konsensusregeln sind noch nicht meine Freunde. Diese Algorithmen, wenn das Absorbtionsgesetz nicht funktionert, bitte ersteinmal ignorieren. 
Boolesche Algebra ? Wikipedia


```
import net.astesana.javaluator.AbstractEvaluator;
import net.astesana.javaluator.BracketPair;
import net.astesana.javaluator.Operator;
import net.astesana.javaluator.Parameters;

import java.util.*;

class ExpandLogic extends AbstractEvaluator<String> {

    /* The logical NOT operator. */
    final static Operator NOT = new Operator("~", 1, Operator.Associativity.RIGHT, 3);
    /* The logical AND operator. */
    final static Operator AND = new Operator("*", 2, Operator.Associativity.LEFT, 2);
    /* The logical OR operator. */
    final static Operator OR = new Operator("+", 2, Operator.Associativity.LEFT, 1);

    private static final Parameters PARAMETERS;

    static {
        // Create the evaluator's parameters
        PARAMETERS = new Parameters();
        PARAMETERS.add(NOT);
        PARAMETERS.add(AND);
        PARAMETERS.add(OR);
        // Add the parentheses
        PARAMETERS.addExpressionBracket(BracketPair.PARENTHESES);
    }

    public ExpandLogic() {
        super(PARAMETERS);
    }

    @Override
    protected String toValue(String literal, Object evaluationContext) {
        return literal;
    }

    static Set<List<String>> allComb(String[][] opts) {

        Set<List<String>> results = new HashSet<List<String>>();

        if (opts.length == 1) {
            for (String s : opts[0])
                results.add(new ArrayList<String>(Arrays.asList(s)));
        } else
            for (String str : opts[0]) {
                String[][] tail = Arrays.copyOfRange(opts, 1, opts.length);
                for (List<String> combs : allComb(tail)) {
                    combs.add(str);
                    results.add(combs);
                }
            }
        return results;
    }

    @Override
    protected String evaluate(Operator operator, Iterator<String> operands,
                              Object evaluationContext) {

        List<String> tree = (List<String>) evaluationContext;

        String eval = "";

        String o1 = operands.next();
        if (operator == NOT) {

            String[] orSplit = o1.split("\\" + OR.getSymbol());
            String[][] andVars = new String[orSplit.length][];
            for (int i = 0; i < orSplit.length; i++) {
                String[] andSplit = orSplit[i].split("\\" + AND.getSymbol());
                for (int k = 0; k < andSplit.length; k++) {
                    if (andSplit[k].contains("~"))
                        andSplit[k] = andSplit[k].substring(1);
                    else
                        andSplit[k] = NOT.getSymbol() + andSplit[k];
                }
                andVars[i] = andSplit;
            }

            Set<List<String>> combinations = allComb(andVars);
            for (List<String> combination : combinations) {
                for (String var : combination) {
                    eval += var + AND.getSymbol();
                }
                eval = eval.substring(0, eval.length()-1) + OR.getSymbol();
            }
            eval = eval.substring(0, eval.length() - 1);

        } else if (operator == AND) {
            String o2 = operands.next();
            Set<String> terms = new HashSet<String>();

            for (String andVar : o1.split("\\+")) {
                for (String term : o2.split("\\+")) {
                    terms.add(andVar + AND.getSymbol() + term);
                }
            }

            for (String term : terms) {
                eval += term + "+";
            }
            if (!eval.isEmpty())
                eval = eval.substring(0, eval.length() - 1);

        } else if (operator == OR) {
            eval = o1 + operator.getSymbol() + operands.next();
        }

        tree.add(eval);
        return eval;
    }
}

public class SimpleLogic extends AbstractEvaluator<String> {

    /* The logical AND operator. */
    final static Operator AND = new Operator("*", 2, Operator.Associativity.LEFT, 2);
    /* The logical OR operator. */
    final static Operator OR = new Operator("+", 2, Operator.Associativity.LEFT, 1);

    private static final Parameters PARAMETERS;

    static {
        // Create the evaluator's parameters
        PARAMETERS = new Parameters();
        // Add the supported operators
        PARAMETERS.add(AND);
        PARAMETERS.add(OR);
    }

    public SimpleLogic() {
        super(PARAMETERS);
    }

    @Override
    protected String toValue(String literal, Object evaluationContext) {
        return literal;
    }

    @Override
    protected String evaluate(Operator operator, Iterator<String> operands,
                              Object evaluationContext) {
        List<String> tree = (List<String>) evaluationContext;
        String o1 = operands.next();
        String o2 = operands.next();

        String eval = "";
        if (operator == AND) {
            boolean result = true;
            if (o1.contains("0") || o2.contains("0"))
                eval = "0";
            else {
                Set<String> vars = new TreeSet<String>();
                Collections.addAll(vars, o1.split("\\*"));
                vars.remove("1");
                if (!vars.contains(o2) && !o2.equals("1"))
                    vars.add(o2);
                if (vars.contains("~" + o2) || o2.contains("~") && vars.contains(o2.substring(1, o2.length())))
                    eval = "0";
                else {
                    for (String var : vars)
                        eval += var + operator.getSymbol();
                    if (!eval.isEmpty())
                        eval = eval.substring(0, eval.length() - 1);
                }
            }
        } else if (operator == OR) {

            Set<String> vars = new TreeSet<String>();
            Collections.addAll(vars, o1.split("\\+"));
            vars.remove("0");

            if (vars.contains("1") || o2.equals("1")) {
                eval = "1";
            } else if (!o2.equals("0")) {

                Set<String> o2Vars = new HashSet<String>();
                Collections.addAll(o2Vars, o2.split("\\*"));
                int o2VarsLength = o2Vars.size();
                boolean o2HasNot = o2.contains("~");

                boolean equals = false;

                Set<String> newVars = new HashSet<String>();

                Iterator<String> varsIterator = vars.iterator();
                while (varsIterator.hasNext()) {
                    String var = varsIterator.next();

                    if (var.equals(o2)) {
                        equals = true;
                        break;
                    }

                    Set<String> o1Vars = new HashSet<String>();
                    Collections.addAll(o1Vars, var.split("\\*"));
                    int o1VarsLength = o1Vars.size();
                    boolean o1HashNot = var.contains("~");

                    if (o1VarsLength == o2VarsLength) {
                        if (o1HashNot || o2HasNot) {
                            String newVar = checkDisjunktionSimilarity(o1Vars, o2Vars);
                            if (newVar != null) {
                                newVars.add(newVar);
                                varsIterator.remove();
                                equals = true;
                            }
                        } 

                    } else if (o1VarsLength > o2VarsLength) {
                        if (o1Vars.containsAll(o2Vars)) {
                            varsIterator.remove();
                        } else if (o1HashNot || o2HasNot) {
                            String newVar = checkDisjunktionSimilarity(o2Vars, o1Vars);
                            if (newVar != null) {
                                newVars.add(newVar);
                                equals = true;
                            } 
                        }
                    } else {
                        if (o2Vars.containsAll(o1Vars)) {
                            equals = true;
                            break;
                        } else if (o1HashNot || o2HasNot) {
                            String newVar = checkDisjunktionSimilarity(o1Vars, o2Vars);
                            if (newVar != null) {
                                newVars.add(newVar);
                                equals = true;
                            }
                        }
                    }
                }
                if (!equals)
                    vars.add(o2);

                vars.addAll(newVars);

                for (String var : vars)
                    eval += var + operator.getSymbol();
                if (!eval.isEmpty())
                    eval = eval.substring(0, eval.length() - 1);

            } else {
                eval = o1;
            }
        } else {
            throw new IllegalArgumentException();
        }

        tree.add(eval);
        return eval;
    }

    public static String checkDisjunktionSimilarity(Set<String> smallOp, Set<String> bigOp) {
        boolean similar = false, oneNot = false;
        String newVar = "";
        Iterator<String> o2VarsIterator = bigOp.iterator();
        while (o2VarsIterator.hasNext()) {
            String o2Var = o2VarsIterator.next();
            if (!(smallOp.contains("~" + o2Var) || smallOp.contains(o2Var.substring(1)))) {
                newVar += o2Var + AND.getSymbol();
                if (smallOp.contains(o2Var))
                    similar = true;
            } else {
                similar = true;
                if (oneNot == false)
                    oneNot = true;
                else {
                    oneNot = false;
                    break;
                }
            }
        }

        if (similar && oneNot) {
            if (newVar.length() > 1)
                newVar = newVar.substring(0, newVar.length() - 1);
            return newVar;
        }
        return null;
    }

    public static void main(String[] args) {

        String term = "t * (a*b + 1 + (a + c)) + a*b*t + a*c + a*c*d + c*d";
        term = "~(a+~b*c)";

        ExpandLogic expandLogic = new ExpandLogic();
        String expandLogicR = doIt(expandLogic, term);
        cout(expandLogicR);

        SimpleLogic simpleLogic = new SimpleLogic();
        String result = doIt(simpleLogic, expandLogicR);
        cout(result);
    }

    private static String doIt(AbstractEvaluator<String> evaluator, String expression) {
        List<String> sequence = new ArrayList<String>();
        evaluator.evaluate(expression, sequence);
        System.out.println("Evaluation sequence for :" + expression);
        for (String string : sequence) {
            //    System.out.println(string);
        }
        System.out.println();
        return sequence.get(sequence.size() - 1);
    }

    public static void cout(Object o) {
        System.out.println(o);
    }
}
```


----------

