Comment transformer la table de vérité en un bloc if / else le plus petit possible

20

Comment puis-je prendre une table de vérité et la transformer en un bloc if compacté?

Par exemple, disons que j'ai cette table de vérité où A et B sont des conditions et x, y et z sont des actions possibles:

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

Cela pourrait se transformer en bloc ci-dessous:

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

C'est un échantillon facile, mais j'ai souvent plusieurs conditions qui combinées de différentes manières devraient produire différentes sorties et il devient difficile de trouver la manière la plus compacte et élégante de représenter leur logique dans un bloc if.

Juan
la source
10
tu veux dire transformer une carte de Karnaugh en une cascade ifelse?
ratchet freak
@ratchet: On dirait que je ne le fais pas? Je ne les connaissais pas avant. Il faudra faire de la lecture, mais une application qui le ferait pour moi serait bien, si rien d'autre, de vérifier mes résultats faits à la main.
Juan
1
@jalayn la plupart des outils karnaugh sont destinés aux circuits numériques; ceux-ci ont une heuristique différente de celle de la question
ratchet freak
1
@jsoldi: Les réponses que vous recevrez dépendront du site que vous demandez. Si vous recherchez des commentaires sur un fragment de code particulier contenant des blocs if-then-else, il appartient certainement à Code review (beta) . Stackoverflow vous apprendra les outils et les techniques. Sur programmers.SE, les gens vous diront si vous devez / ne devez pas vous soucier de réécrire des instructions logiques pour une compréhension humaine ou pour une exécution plus rapide.
rwong
2
Les recommandations d'outils sont hors sujet, mais si vous changez la question en "Comment puis- je faire cela?" ce sera sur le sujet. Si vous souhaitez une recommandation logicielle, vous devez vous rendre sur softwarerecs.stackexchange.com.
Kilian Foth du

Réponses:

14

Si vous concevez à partir d'une carte de Karnaugh, le code peut également ressembler à cela:

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

actionMap[a][b]()
Kevin Cline
la source
Quelle langue est-ce? Javascript? Python?
TheLQ
TheLQ, ce n'est pas python, peut être javascript. Mais ce serait très similaire s'il était écrit en python
grizwako
@TheLQ: c'est Groovy, parce que c'est ce que je fais ces jours-ci, et probablement Ruby aussi. Le code pour Javascript ou Python ou LUA ou Perl serait très similaire.
kevin cline
2
Ceci, bien sûr, a pour effet d'évaluer b même lorsque l'évaluation n'est pas nécessaire. C'est peut-être un problème, peut-être pas.
Pseudonyme
@kevincline s'il vous plaît, très bien, "Lua", pas "LUA". :)
Machado
4

Dans C # .NET, vous pouvez utiliser une classe de dictionnaire pour obtenir le résultat sans IF ELSE comme suit - La bonne chose à ce sujet est:

  1. C'est lisible
  2. Les nouvelles clés seront uniques (sinon, vous obtenez une erreur)
  3. La séquence n'a pas d'importance
  4. Facile à ajouter ou à supprimer des entrées

Si vous n'avez pas d'équivalent de classe de dictionnaire, vous pouvez faire de même dans une fonction de recherche / recherche binaire.

//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();
Aucune chance
la source
1
J'aime cette solution, le seul changement que je ferais serait d'utiliser un dictionnaire <Tuple <bool, bool>, Tuple <bool, bool, bool> au lieu d'un Dictionary <string, string>. Ensuite, vous n'avez pas besoin de construire une chaîne pour rechercher et déconstruire le résultat par la suite, car Tuples le fera pour vous.
Lyise
@Lyise, Merci pour votre remarque. Vous avez tout à fait raison. Je devrais intégrer votre bon point lorsque j'aurai une chance.
NoChance
2

Ce que vous voulez, c'est un algorithme Rete . Cela regroupe automatiquement un ensemble de règles et les hiérarchise dans un arbre comme vous le décrivez.

Il existe un certain nombre de systèmes de "moteur de règles" commerciaux qui le font à très grande échelle (des millions de règles) où la vitesse d'exécution est essentielle.

Alex Feinman
la source
2

Voici votre bibliothèque :) Et vous n'avez pas besoin de passer la table K complète, seulement les champs qui vous intéressent :) Elle suppose que son opérateur AND dans la table de vérité. Si vous souhaitez utiliser plus d'opérateurs, vous devriez pouvoir le réécrire. Vous pouvez avoir n'importe quel nombre d'arguments. Écrit pythonet testé.

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
la source
1

Mappez les entrées en une seule valeur, puis activez-la:

#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
Déduplicateur
la source
1

Une table de recherche contenant des pointeurs de fonctions peut bien fonctionner dans certaines situations. En C, par exemple, vous pouvez faire quelque chose comme ceci:

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();
}

C'est une bonne solution lorsque le nombre d'entrées est relativement faible, car le nombre d'entrées dans le tableau doit être 2 ^^ n où n est le nombre d'entrées. 7 ou 8 entrées peuvent être gérables, 10 ou 12 démarrages deviennent laids. Si vous avez autant d'entrées, essayez d'abord de simplifier par d'autres moyens (comme les cartes de Karnaugh).

Caleb
la source
0

Regardez le logiciel "Gorgeous Karnaugh" - il peut accepter des tables de vérité tout à fait exactes comme votre échantillon, accepter la définition de formules booléennes analytiques, accepter les scripts Lua pour construire des tables de vérité. Ensuite, le logiciel "Gorgeous Karnaugh" dessine les K-Maps pour les entrées prises, que vous pouvez minimiser manuellement ou en utilisant le minimiseur logique "Espresso", et produit une sortie pour C / C ++ et certains langages matériels. Consultez la page récapitulative des fonctionnalités de "Gorgeous Karnaugh" - http://purefractalsolutions.com/show.php?a=xgk/gkm

Petruchio
la source
Cela ressemble beaucoup à ce dont j'ai besoin, mais je n'ai pas pu obtenir le code C / C ++ pour afficher autre chose que des ifs vides après avoir entré une table de vérité.
Juan
Oui, cet outil conçu pour la minimisation des fonctions logiques - après avoir entré la table de vérité, vous devez minimiser la fonction logique (PoS / SoP - de 0 / par 1). Le code C ++ se trouve dans la fenêtre "Résultats de la minimisation" après la minimisation.
Petruchio