algoritmo - minimizando las expresiones booleanas

Question

Estoy tratando de escribir un fragmento de código que pueda reducir al mínimo la LONGITUD de una expresión booleana, por lo que el código debería reducir el número de elementos en la expresión a la mínima posible. En este momento estoy atascado y necesito ayuda = [

Esta es la regla: puede haber un número arbitrario de elementos en una expresión booleana, pero solo contiene operadores AND y OR, más corchetes.

Por ejemplo, si paso en una expresión booleana: ABC + BCD + DE, la salida óptima sería BC (A + D) + DE, que guarda 2 espacios de unidad en comparación con la original porque los dos BC son combinado en uno

Mi lógica es que intentaré encontrar el elemento que aparece con más frecuencia en la expresión, y lo descompongo. Luego invoco la función de manera recursiva para hacer lo mismo con la expresión factorizada hasta que esté completamente factorizada. Sin embargo, ¿cómo puedo encontrar el elemento más común en la expresión original? Es decir, en el ejemplo anterior, BC? Parece que tendría que probar todas las combinaciones diferentes de elementos y encontrar el número de veces que aparece cada combinación en toda la expresión. Pero esto suena realmente ingenuo. Segundo

¿Alguien puede dar una pista sobre cómo hacer esto de manera eficiente? Incluso algunas palabras clave que puedo buscar en Google servirán.

Answer 1

En este momento no he leído acerca de todos esos algoritmos fresco todavía, pero se preguntó acerca de encontrar el factor común, así que pensé lo siguiente:

import itertools 
def commons(exprs): 
    groups = [] 
    for n in range(2, len(exprs)+1): 
     for comb in itertools.combinations(exprs, n): 
      common = set.intersection(*map(set, comb)) 
      if common: 
       groups.append(
          (len(common), n, comb, ''.join(common))) 
    return sorted(groups, reverse=True) 

>>> exprs 
['ABC', 'BCD', 'DE', 'ABCE'] 

>>> commons(exprs) 
[(3, 2, ('ABC', 'ABCE'), 'ACB'), 
(2, 3, ('ABC', 'BCD', 'ABCE'), 'CB'), 
(2, 2, ('BCD', 'ABCE'), 'CB'), 
(2, 2, ('ABC', 'BCD'), 'CB'), 
(1, 2, ('DE', 'ABCE'), 'E'), 
(1, 2, ('BCD', 'DE'), 'D')] 

La función devuelve una lista ordenada por:

1. la longitud del factor común
2. el número de términos que tienen este factor común

Answer 2

Lo que está buscando es una forma de minimizar una función booleana. Esto es algo que interesa especialmente a la comunidad de diseño de chips. Una técnica que se utiliza para sus propósitos es Quine-McCluskey algorithm, o puede usar Karnaugh Maps según lo sugerido por Li-aung Yip en los comentarios.

Answer 3

Utilice el algoritmo Quine-McCluskey para minimizar las expresiones booleanas. Es funcionalmente equivalente al enfoque del Mapa de Karnaugh, pero mucho más susceptible de implementación en una computadora.

Answer 4

Aquí hay un applet que implementa los mapas de Karnaugh: http://www-ihs.theoinf.tu-ilmenau.de/~sane/projekte/karnaugh/embed_karnaugh.html

Puede introducir su expresión o completar una tabla de verdad.

Answer 5

También le puede interesar ver Espresso heuristic logic minimizer.

Answer 6

Desafortunadamente, la mayoría de las sugerencias pueden no dar a @turtlesoup lo que está buscando. @turtlesoup pidió una forma de minimizar el número de caracteres para una expresión booleana dada. La mayoría de los métodos de simplificación no se centran en el número de caracteres como un enfoque para la simplificación. Cuando se trata de la minimización de la electrónica, los usuarios generalmente quieren la menor cantidad de puertas (o partes). Esto no siempre se traduce en una expresión más corta en términos de la "longitud" de la expresión - la mayoría de las veces lo hace, pero no siempre. De hecho, a veces la expresión puede ser más grande, en términos de longitud, aunque puede ser más simple desde el punto de vista de la electrónica (requiere menos puertas para construir).

boolengine.com es la mejor herramienta de simplificación que conozco cuando se trata de la simplificación booleana para circuitos digitales. No permite cientos de entradas, pero permite 14, que es mucho más que la mayoría de las herramientas de simplificación.

Al trabajar con productos electrónicos, los programas de simplificación generalmente desglosan la expresión en forma de suma de producto. Entonces la expresión '(ab) +' cd se convierte en 'c +' b + 'a + d. El resultado "simplificado" requiere más caracteres para imprimir como una expresión, pero es más fácil de construir desde el punto de vista de la electrónica. Solo requiere una única puerta OR de 4 entradas y 3 inversores (4 partes). Mientras que la expresión original requeriría 2 puertas AND, 2 inversores y una puerta OR (5 partes).

Después de dar el ejemplo de @ turtlesoup a BoolEngine, muestra que BC (A + D) + DE se convierte en E + D + ABC. Esta es una expresión más corta, y generalmente lo será. Pero ciertamente no siempre.