Como transformar a tabela verdade no menor bloco if / else possível

20

Como posso pegar uma tabela verdade e transformá-la em um bloco compactado se?

Por exemplo, digamos que eu tenha essa tabela de verdade em que A e B são condições e x, ye z são ações possíveis:

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

Isso pode se transformar em abaixo se o bloco:

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

Esta é uma amostra fácil, mas frequentemente tenho várias condições que combinadas de maneiras diferentes devem produzir saídas diferentes e fica difícil descobrir a maneira mais compacta e elegante de representar sua lógica em um bloco if.

Juan
fonte
10
você quer dizer transformar um mapa de Karnaugh em uma cascata ifelse?
catraca aberração
@ catraca: Parece que eu faço, não é? Eu não sabia sobre eles antes. Vou ter que ler um pouco, mas ainda assim, o aplicativo que faria isso por mim seria bom, se não mais, para verificar meus resultados feitos à mão.
Juan
1
@jalayn a maioria das ferramentas de karnaugh são para circuitos digitais; aqueles têm heurísticas diferentes do que o que a pergunta é sobre
aberração catraca
1
@jsoldi: As respostas que você recebe dependerão do site que você solicitar. Se você está procurando comentários sobre um fragmento de código específico que contém alguns blocos if-then-else, ele certamente pertence à revisão de código (beta) . O Stackoverflow ensinará as ferramentas e técnicas. No programmers.SE, as pessoas dirão se você deve ou não se preocupar em reescrever instruções lógicas para o entendimento humano ou para uma execução mais rápida.
Rwong
2
Recomendações de ferramentas são off-topic, mas se você mudar a pergunta para "Como pode eu fazer isso?" será no tópico. Se você deseja uma recomendação de software, acesse softwarerecs.stackexchange.com.
precisa

Respostas:

14

Se você estiver projetando a partir de um mapa de Karnaugh, o código também pode ser assim:

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

actionMap[a][b]()
Kevin Cline
fonte
Que língua é essa? Javascript? Python?
TheLQ
TheLQ, não é python, pode ser javascript. Mas seria muito semelhante, se escrito em python
grizwako
@ TheLQ: é Groovy, porque é isso que estou fazendo hoje em dia, e provavelmente Ruby também. O código para Javascript ou Python ou LUA ou Perl seria muito semelhante.
Kevin cline
2
Obviamente, isso tem o efeito de avaliar b mesmo quando a avaliação não é necessária. Talvez isso seja um problema, talvez não seja.
Pseudônimo
@kevincline por favor, muito por favor, "Lua", não "LUA". :)
Machado
4

No C # .NET, você pode usar uma classe Dictionary para obter o resultado sem nenhum IF ELSE da seguinte maneira - A coisa boa sobre isso é:

  1. É legível
  2. Novas chaves serão únicas (caso contrário, você receberá um erro)
  3. Sequência não importa
  4. Fácil de adicionar ou remover entradas

Se você não tiver um equivalente da classe Dictionary, poderá fazer o mesmo em uma função de pesquisa / pesquisa binária.

//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();
NoChance
fonte
1
Eu gosto dessa solução, a única alteração que eu faria seria usar um Dictionary <Tuple <bool, bool>, Tuple <bool, bool, bool> em vez de um Dictionary <string, string>. Então você não precisa criar uma string para procurar e desconstruir o resultado posteriormente, pois as Tuplas farão isso por você.
Lyise
@ Lyise, obrigado por sua observação. Você está absolutamente correto. Eu deveria incorporar o seu ponto positivo quando eu tiver uma chance.
NoChance
2

O que você quer é um algoritmo Rete . Isso combina automaticamente um conjunto de regras e as prioriza em uma árvore da maneira que você descreve.

Existem vários sistemas comerciais de "mecanismo de regras" que fazem isso em uma escala muito grande (milhões de regras) em que a velocidade de execução é essencial.

Alex Feinman
fonte
2

Aqui está sua biblioteca :) E você não precisa passar a tabela K completa, apenas os campos nos quais está interessado :) Pressupõe que seu operador AND na tabela verdade. Se você quiser usar mais operadores, poderá reescrevê-lo. Você pode ter qualquer número de argumentos. Escrito pythone testado.

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
fonte
1

Mapeie as entradas em um único valor e ligue-o:

#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
Desduplicador
fonte
1

Uma tabela de pesquisa contendo ponteiros de funções pode funcionar bem em algumas situações. Em C, por exemplo, você pode fazer algo assim:

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

Essa é uma boa solução quando o número de entradas é relativamente pequeno, pois o número de entradas na tabela deve ser 2 ^^ n onde n é o número de entradas. 7 ou 8 entradas podem ser gerenciáveis, 10 ou 12 começam a ficar feias. Se você tiver muitas entradas, tente simplificar por outros meios (como mapas de Karnaugh) primeiro.

Caleb
fonte
0

Veja o software "Gorgeous Karnaugh" - ele pode aceitar tabelas verdadeiras exatamente como sua amostra, aceitar definição de fórmulas booleanas analíticas, aceitar scripts Lua para criar tabelas verdadeiras. Em seguida, o software "Gorgeous Karnaugh" desenha o K-Maps para entrada, que você pode minimizar manualmente ou usando o minimizador lógico "Espresso" e produz saída para C / C ++ e algumas linguagens de hardware. Consulte a página de recursos resumidos para "Gorgeous Karnaugh" - http://purefractalsolutions.com/show.php?a=xgk/gkm

Petruchio
fonte
Isso parece muito com o que eu preciso, mas não foi possível obter o código C / C ++ para mostrar algo diferente de ifs vazios depois de inserir uma tabela verdade.
Juan Juan
Sim, essa ferramenta projetada para minimizar as funções lógicas - depois de entrar na tabela verdade, você precisa minimizar a função lógica (PoS / SoP - por 0 / por 1). O código C ++ pode ser encontrado na janela "Resultados da minimização" após a minimização.
Petruchio