Cómo convertir la tabla de verdad en el bloque if / else más pequeño posible

20

¿Cómo puedo tomar una tabla de verdad y convertirla en un bloque if compactado?

Por ejemplo, digamos que tengo esta tabla de verdad donde A y B son condiciones y x, y y z son acciones posibles:

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

Esto podría transformarse en el siguiente bloque si:

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

Esta es una muestra fácil, pero con frecuencia tengo varias condiciones que combinadas de diferentes maneras deberían producir diferentes salidas y se hace difícil encontrar la forma más compacta y elegante de representar su lógica en un bloque if.

Juan
fuente
10
quieres decir transformar un mapa de Karnaugh en una cascada ifelse?
monstruo de trinquete
@ratchet: Parece que lo hago, ¿no? No sabía sobre ellos antes. Tendré que leer un poco, pero aún así, y la aplicación que lo haría por mí sería agradable, por lo menos, verificar mis resultados hechos a mano.
Juan
1
@jalayn la mayoría de las herramientas de karnaugh son para circuitos digitales; esos tienen heurísticas diferentes de lo que se trata la pregunta
fanático del trinquete el
1
@jsoldi: las respuestas que reciba dependerán del sitio que pregunte. Si está buscando comentarios sobre un fragmento de código en particular que contiene algunos bloques if-then-else, ciertamente pertenece a Code review (beta) . Stackoverflow te enseñará las herramientas y técnicas. En los programadores.SE, la gente le dirá si debería / no debería preocuparse por reescribir las declaraciones lógicas para la comprensión humana, o para una ejecución más rápida.
rwong
2
Recomendaciones de herramientas son fuera de tema, pero si cambia la pregunta en "¿Cómo pueden yo hacer esto?" Será sobre el tema. Si desea una recomendación de software, debe ir a softwarerecs.stackexchange.com.
Kilian Foth

Respuestas:

14

Si está diseñando desde un mapa de Karnaugh, entonces el código también puede verse así:

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

actionMap[a][b]()
Kevin Cline
fuente
¿Qué lenguaje es este? Javascript? ¿Pitón?
TheLQ
TheLQ, no es Python, podría ser JavaScript. Pero sería muy similar si estuviera escrito en python
grizwako
@TheLQ: es Groovy, porque eso es lo que estoy haciendo estos días, y probablemente también Ruby. El código para Javascript o Python o LUA o Perl sería muy similar.
Kevin Cline
2
Esto, por supuesto, tiene el efecto de evaluar b incluso cuando la evaluación no es necesaria. Tal vez sea un problema, tal vez no lo sea.
Seudónimo
@kevincline por favor, bastante por favor, "Lua", no "LUA". :)
Machado
4

En C # .NET, puede usar una clase de diccionario para obtener el resultado sin IF IFSE de la siguiente manera: lo bueno de esto es:

  1. Es legible
  2. Las nuevas claves serán únicas (de lo contrario, obtendrá un error)
  3. La secuencia no importa
  4. Fácil de agregar o eliminar entradas

Si no tiene un equivalente de Clase de diccionario, puede hacer lo mismo en una función de búsqueda / búsqueda binaria.

//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();
Ninguna posibilidad
fuente
1
Me gusta esta solución, el único cambio que haría sería usar un Dictionary <Tuple <bool, bool>, Tuple <bool, bool, bool> en lugar de un Dictionary <string, string>. Entonces no necesita construir una cadena para buscar y deconstruir el resultado después, ya que Tuples lo hará por usted.
Lyise
@ Lyise, gracias por tu comentario. Tienes toda la razón. Debería incorporar tu buen punto cuando tenga la oportunidad.
NoChance
2

Lo que quieres es un algoritmo Rete . Esto combina automáticamente un conjunto de reglas y las prioriza en un árbol de la manera que usted describe.

Existen varios sistemas comerciales de "motor de reglas" que hacen esto a gran escala (millones de reglas) donde la velocidad de ejecución es esencial.

Alex Feinman
fuente
2

Aquí está su biblioteca :) Y no necesita pasar la tabla K completa, solo los campos que le interesan :) Asume que es el operador AND en la tabla de verdad. Si desea utilizar más operadores, debería poder reescribirlo. Puedes tener cualquier cantidad de argumentos. Escrito pythony probado.

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

Asigne las entradas en un solo valor y luego actívelo:

#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
Deduplicador
fuente
1

Una tabla de búsqueda que contiene punteros de funciones puede funcionar bien en algunas situaciones. En C, por ejemplo, puede hacer algo como esto:

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

Esta es una buena solución cuando el número de entradas es relativamente pequeño, ya que el número de entradas en la tabla tiene que ser 2 ^^ n donde n es el número de entradas. 7 u 8 entradas pueden ser manejables, 10 o 12 comienzan a ponerse feas. Si tiene tantas entradas, intente simplificar por otros medios (como los mapas de Karnaugh) primero.

Caleb
fuente
0

Mire el software "Gorgeous Karnaugh": puede aceptar tablas de verdad bastante exactas como su muestra, aceptar definiciones de fórmulas booleanas analíticas, aceptar secuencias de comandos Lua para construir tablas de verdad. A continuación, el software "Gorgeous Karnaugh" dibuja los K-Maps para la entrada tomada, que puede minimizar manualmente o usando el minimizador lógico "Espresso", y produce salida para C / C ++ y algunos lenguajes de hardware. Consulte la página de características de resumen para "Gorgeous Karnaugh": http://purefractalsolutions.com/show.php?a=xgk/gkm

Petruchio
fuente
Esto se parece mucho a lo que necesito, pero no pude obtener el código C / C ++ para mostrar nada más que ifs vacíos después de ingresar a una tabla de verdad.
Juan
Sí, esa herramienta diseñada para minimizar las funciones lógicas: después de ingresar a la tabla de verdad, debe minimizar la función lógica (PoS / SoP - por 0 / por 1). El código C ++ se puede encontrar en la ventana "Resultados de minimización" después de la minimización.
Petruchio