Algorithmus - Minimierung boolescher Ausdrücke

Sorry habe ich nicht gelesen, über all die coolen algorithmen noch nicht, aber Sie fragte Sie über die Suche nach dem gemeinsamen Faktor, so dachte ich an folgende:

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')]

Liefert die Funktion eine Liste sortiert nach:

1. Die Länge des gemeinsamen Faktor
2. Die Anzahl der Begriffe, die mit diesem gemeinsamen Faktor

Verwenden Sie die Quine-McCluskey Algorithmus zur Minimierung boolescher Ausdrücke. Es ist funktionell äquivalent zu der Karnaugh-Map-Ansatz, aber viel zugänglicher für die Implementierung auf einem computer.

Leider, die meisten der gegebenen Empfehlungen nicht tatsächlich geben @turtlesoup, was er/Sie sucht. @turtlesoup nach einer Möglichkeit gefragt, um minimieren Sie die Anzahl der Zeichen für einen gegebenen booleschen Ausdruck. Die meisten Vereinfachung Methoden nicht Ziel die Anzahl der Zeichen, die als Schwerpunkt für die Vereinfachung. Wenn es um die Minimierung in der Elektronik, die Benutzer wollen in der Regel die geringste Anzahl von gates (oder Teile). Dies bedeutet nicht immer Ergebnis in einer kürzeren Ausdruck in Bezug auf die "Länge" des Ausdrucks -- die meisten Zeiten tut es, aber nicht immer. In der Tat, manchmal kann der Ausdruck größer geworden, in Bezug auf die Länge, obwohl es möglicherweise einfacher, von einem Elektronik-Standpunkt (benötigt weniger Tore zu bauen).

boolengine.com ist die beste Vereinfachung tool, das ich kenne, wenn es um die Boolesche Vereinfachung digitaler schaltungen. Es nicht erlauben, Hunderte von Eingaben, sondern es ermöglicht auch 14, das ist viel mehr als die meisten vereinfachungs-tools.

Beim arbeiten mit Elektronik, Vereinfachung der Programme, die in der Regel zerlegen Sie den Ausdruck in der Summe-von-Produkt-form. So wurde der Ausdruck " (ab)+' - cd zu 'c+'b+'a+d. Die "vereinfachte" Ergebnis erfordert mehr Zeichen als Ausdruck, aber ist einfacher zu bauen, von einem Elektronik-Standpunkt. Es erfordert nur einen einzigen 4-input or gate und 3 Wechselrichtern (4 Teile). In der Erwägung, dass der ursprüngliche Ausdruck erfordern würde, 2 UND-Gatter, 2 Wechselrichter, und ein ODER-Tor (5 Teile).

Nachdem er @turtlesoup dem Beispiel BoolEngine, es zeigt, dass BC(A+D)+DE wird E+D+ABC. Dies ist eine kürzere Ausdruck, und wird in der Regel sein. Aber sicher nicht immer.