Wie man eine Wahrheitstabelle in einen kleinstmöglichen if / else Block verwandelt

20

Wie kann ich eine Wahrheitstabelle in einen komprimierten if-Block verwandeln?

Angenommen, ich habe diese Wahrheitstabelle, in der A und B Bedingungen und x, y und z mögliche Aktionen sind:

A B | x y z
-------------
0 0 | 0 0 1
0 1 | 0 0 1
1 0 | 0 1 0
1 1 | 1 0 0

Dies könnte sich wie folgt umwandeln, wenn block:

if(A)
{
    if(B)
    {
        do(x)
    }
    else
    {
        do(y)
    }
}
else
{
    do(z)
}

Dies ist ein einfaches Beispiel, aber ich habe häufig mehrere Bedingungen, die auf unterschiedliche Weise kombiniert unterschiedliche Ausgaben ergeben sollten, und es wird schwierig, die kompakteste und eleganteste Art und Weise zu finden, um ihre Logik in einem if-Block darzustellen.

Juan
quelle
10
Sie meinen, eine Karnaugh-Karte in eine ifelse-Kaskade zu verwandeln ?
Ratschenfreak
@ratchet: Scheint so, als würde ich es tun, nicht wahr? Ich wusste vorher nichts über sie. Müssen etwas lesen, aber noch und App, die es für mich tun würde, wäre schön, wenn nichts anderes, um meine handgemachten Ergebnisse zu überprüfen.
Juan
1
@jalayn Die meisten Karnaugh-Tools sind für digitale Schaltkreise vorgesehen. Diese haben andere Heuristiken als die, um die es geht
Ratschenfreak
1
@jsoldi: Die Antworten, die Sie erhalten, hängen davon ab, welche Site Sie fragen. Wenn Sie Kommentare zu einem bestimmten Codefragment suchen, das einige If-Then-else-Blöcke enthält, gehört es zweifellos zu Code Review (Beta) . Stackoverflow bringt Ihnen die Werkzeuge und Techniken bei. Auf programmers.SE wird Ihnen mitgeteilt, ob Sie sich Gedanken über das Umschreiben von logischen Anweisungen machen sollten, um das menschliche Verständnis zu fördern oder die Ausführung zu beschleunigen.
rwong
2
Tool-Empfehlungen sind nicht thematisch, aber wenn Sie die Frage in "Wie kann ich das tun?" Ändern es wird thematisch sein. Wenn Sie eine Software-Empfehlung wünschen, sollten Sie zu softwarerecs.stackexchange.com gehen.
Kilian Foth

Antworten:

14

Wenn Sie von einer Karnaugh-Karte aus entwerfen, kann der Code auch so aussehen:

//                   a      b
def actionMap = [ false: [false: { z() },
                          true:  { z() }],
                  true:  [false: { x() },
                          true:  { y() }]]

actionMap[a][b]()
Kevin Cline
quelle
Welche Sprache ist das? Javascript? Python?
TheLQ
TheLQ, nicht Python, ist möglicherweise Javascript. Aber es wäre sehr ähnlich, wenn in Python geschrieben
grizwako
@TheLQ: Es ist Groovy, weil ich das in diesen Tagen mache und wahrscheinlich auch Ruby. Der Code für Javascript oder Python oder LUA oder Perl wäre sehr ähnlich.
Kevin Cline
2
Dies hat natürlich den Effekt, dass b auch dann ausgewertet wird, wenn die Auswertung nicht benötigt wird. Vielleicht ist das ein Problem, vielleicht ist es nicht.
Pseudonym
@ Kevincline bitte, bitte schön, "Lua", nicht "LUA". :)
Machado
4

In C # .NET können Sie eine Dictionary-Klasse verwenden, um das Ergebnis ohne IF ELSE zu erhalten. Das Schöne daran ist:

  1. Es ist lesbar
  2. Neue Schlüssel sind eindeutig (andernfalls wird eine Fehlermeldung angezeigt)
  3. Reihenfolge spielt keine Rolle
  4. Einträge einfach hinzufügen oder entfernen

Wenn Sie kein Äquivalent zur Dictionary-Klasse haben, können Sie dasselbe in einer binären Suchfunktion tun.

//A B | x y z
//-------------
//0 0 | 0 0 1
//0 1 | 0 0 1
//1 0 | 0 1 0
//1 1 | 1 0 0
// Create a Dictionary object and populate it
Dictionary<string, string> _decisionTable = new Dictionary<string, string>() { 
    { "0,0", "0,0,1" }, 
    { "0,1", "0,0,1" }, 
    { "1,0", "0,1,0" }, 
    { "1,1", "1,0,0"} 
};

//usage example: Find the values of X,Y,Z for A=1,B=0
Console.WriteLine(_decisionTable["1,0"]);
Console.Read();
Keine Chance
quelle
1
Ich mag diese Lösung. Die einzige Änderung, die ich vornehmen würde, wäre die Verwendung eines Dictionary <Tuple <bool, bool>, Tuple <bool, bool, bool> anstelle eines Dictionary <string, string>. Dann müssen Sie keine Zeichenfolge erstellen, um nachzuschlagen und das Ergebnis anschließend zu dekonstruieren, da Tuples dies für Sie erledigt.
Lyise
@Lyise, danke für deine Bemerkung. Sie sind absolut richtig. Ich sollte Ihren guten Punkt berücksichtigen, wenn ich eine Chance bekomme.
NoChance
2

Was Sie wollen, ist ein Rete-Algorithmus . Auf diese Weise werden automatisch eine Reihe von Regeln gekämmt und gemäß Ihrer Beschreibung in einem Baum priorisiert.

Es gibt eine Reihe von kommerziellen "Rules Engine" -Systemen, die dies in sehr großem Maßstab tun (Millionen von Regeln), bei denen die Ausführungsgeschwindigkeit von entscheidender Bedeutung ist.

Alex Feinman
quelle
2

Hier ist Ihre Bibliothek :) Und Sie müssen keine vollständige K-Tabelle übergeben, sondern nur Felder, die Sie interessieren :) Es wird davon ausgegangen, dass der AND-Operator in der Wahrheitstabelle steht. Wenn Sie mehr Operatoren verwenden möchten, sollten Sie in der Lage sein, diese neu zu schreiben. Sie können eine beliebige Anzahl von Argumenten haben. Eingeschrieben pythonund getestet.

def x():
    print "xxxx"

def y():
    print "yyyyy"

def z(): #this is default function
    print "zzzzz"

def A():
    return 3 == 1

def B():
    return 2 == 2


def insert(statements,function):
    rows.append({ "statements":statements, "function":function })

def execute():
    for row in rows:
        print "==============="
        flag = 1

        for index, val in enumerate(row["statements"]):
            #for first pass of lopp, index is 0, for second its 1....
            #if any function returns result different than one in our row, 
            # we wont execute funtion of that row (mark row as not executable)
            if funcs[index]() != val:
                flag = 0

        if flag == 1:
            #we execute function 
            row["function"]()
        else: z() #we call default function


funcs = [A,B]  #so we can access functions by index key
rows = []

insert( (0,0), y)
insert( (0,1), y)
insert( (1,0), x)
insert( (1,1), x)
insert( (0,1), x)

execute()
grizwako
quelle
1

Ordnen Sie die Eingaben einem einzelnen Wert zu und schalten Sie ihn ein:

#define X(a, b) (!!(a) * 2 + !!(b))
switch(X(A, B)) {
case X(0, 0):
    ...
    break;
case X(0, 1):
    ...
    break;
case X(1, 0):
    ...
    break;
case X(1, 1):
    ...
    break;
}
#undef X
Deduplizierer
quelle
1

Eine Nachschlagetabelle mit Funktionszeigern kann in einigen Situationen gut funktionieren. In C können Sie beispielsweise Folgendes tun:

typedef void(*VoidFunc)(void);

void do(int a, int b)
{
    static VoidFunc myFunctions[4] = {z, z, y, x}; // the lookup table

    VoidFunc theFunction = myFunctions[ a * 2 + b ];
    theFunction();
}

Dies ist eine gute Lösung, wenn die Anzahl der Eingaben relativ gering ist, da die Anzahl der Einträge in der Tabelle 2 ^^ n sein muss, wobei n die Anzahl der Eingaben ist. 7 oder 8 Eingänge sind möglicherweise überschaubar, 10 oder 12 werden unangenehm. Wenn Sie so viele Eingaben haben, versuchen Sie zunächst, diese auf andere Weise zu vereinfachen (z. B. durch Karnaugh-Karten).

Caleb
quelle
0

Schauen Sie sich die Software "Gorgeous Karnaugh" an - sie kann Wahrheitstabellen akzeptieren, die genau wie Ihre Stichprobe sind, analytische boolesche Formeldefinitionen akzeptieren, Lua-Skripte akzeptieren, um Wahrheitstabellen zu erstellen. Als Nächstes zeichnet die Software "Gorgeous Karnaugh" die K-Maps für die genommenen Eingaben, die Sie manuell oder mit dem Logik-Minimierer "Espresso" minimieren können, und erstellt Ausgaben für C / C ++ und einige Hardwaresprachen. Schauen Sie auf die Seite mit den zusammenfassenden Funktionen für "Gorgeous Karnaugh" ( http://purefractalsolutions.com/show.php?a=xgk/gkm)

Petruchio
quelle
Das sieht sehr nach dem aus, was ich brauche, aber ich konnte nicht erreichen, dass der C / C ++ - Code ifnach Eingabe einer Wahrheitstabelle etwas anderes als leere s anzeigt.
Juan
Ja, dieses Tool wurde für Logikfunktionsminimierungen entwickelt. Nach Eingabe der Wahrheitstabelle müssen Sie die Logikfunktion (PoS / SoP - um 0 / um 1) minimieren. Der C ++ - Code befindet sich nach der Minimierung im Fenster "Minimierungsergebnisse".
Petruchio