Schaltalgebra

[Michael Schröpl]

Hi annA,

Die Tafeln müssen nicht grafisch darstellbar sein, möchte nur,
daß mein Programm logische Ausdrücke vereinfach kann.

Das Hauptproblem Deiner Aufgabenstellung ist meiner Meinung nach, daß der Begriff "vereinfachen" hoffnungslos unterdefiniert ist. Welches Komplexitätsmaß legst Du diesem Begriff zugrunde? (Stringlänge? Klammertiefe? Anzahl Operatoren? Anzahl elementarer Schaltbausteine - und aus welchem Vorrat? Letzteres war mal früher ein Optimierungsziel, wo es hauptsächlich NAND und EXOR gab, oder was auch immer - das waren diese Bausteine direkt ein Kostenfaktor, also mußte man scheinbar triviale Ausdrücke in schauerlicher Weise umschreiben, weil das eigentlich gewünschte Koordinatensystem nicht zur Realität der Hardware paßte ... ist das heute immer noch so?)

Würde man sowas am besten mit einem mehrdimensionalen Array lösen,
dieses dann Feld für Feld durchlaufen, Gruppen zusammenfassen etc?

Algebraische Transformationen direkt durchzuführen ist schwierig, weil es viel Intelligenz erfordert. Operationen wie "Terme ausklammern" aus beliebig komplexen Konstruktionen, das ist nicht in drei Zeilen zu beschreiben.
Wenn Du so etwas willst, solltest Du als Datenmodell einen Operatoren-Baum für den Ausdruck erzeugen. Innerhalb eines solchen Baums lassen sich bestimte Transformationen als Zusammenfassungen und Manipulationen von Teilbäumen formulieren - "Ausklammern" ist beispielsweise eine solche Transformation, die dann über die Suche identischer Teilbäume an 'passenden' Stellen funktionieren würde. Dies alles ist aber hochkomplex ...

Für die Methode mit dem Array spricht, daß Du bei <n> variablen gerade mal 2^n Werte auszurechnen hast. Anschließend aus der vollständigen Wertemenge einzelne Variablen als irrelevant zu erkennen usw., das ist dann der 'tricky' Teil des Problems.

Ist das ein Standard-Problem?

Wenn Du einen vollständigen n-dimensionalen Binärwürfel erzeugt hast, dann kannst Du diesen wohl irgendwie algorithmisch in einen Ausdruck umwandeln, welcher ein OR aus so vielen Termen ist, bis Du alle Werte einer bestimmten Sorte (Nuller, Einser) abgedeckt hast. Das erinnert entfernt an das Knapsack-Problem.
Was Dir bisher fehlt, das ist eine Bewertungsfunktion für die Komplexität eines Ausdruckes - hast Du diese, dann kannst Du überhaupt erst eine Strategie definieren, welche die Minimierung dieser Bewertungsfunktion zum Ziel hat.

Kann mein Taschenrechner TI-83plus das vielleicht sogar schon von alleine?

Momentan sind wir noch im Stadium der Definition der Aufgabenstellung - über Lösungswege können wir später diskutieren.

Viele Grüße
      Michael