Boolsche Funktion vereinfachen

Hallo,

ich suche eine Möglichkeit, mit der man große boolsche Terme vereinfachen kann. Per Hand würde es viel zu lange dauern, da die Terme dafür viel zu groß sind.

Sowas wie
( R09 * R014 )
+ ( R09 * R010 * R011 * R07 * R06 * R018 * R02 * R01 * R013 * R014 )
+ ( R09 * R010 * R011 * R07 * R06 * R05 * R017 * R02 * R01 * R013 * R014 )
...

oder

( R009 AND R014 ) OR ( R009 AND R010 AND R011 AND R007 AND R006 AND Pp1 AND R002 AND R001 AND R013 AND R014 )
...

möchte ich vereinfachen. Ob mit * und + oder AND und OR ist egal.

Hat jemand 'ne Idee?

Gruß
Martin

Bitte markiere auch die Kommentare, die zur Lösung des Beitrags beigetragen haben

Content-ID: 122438

Url: https://administrator.de/contentid/122438

Ausgedruckt am: 16.11.2024 um 15:11 Uhr

10 Kommentare

Neuester Kommentar

Moin inspire,

vielleicht verstehe ich ja das Beispiel nicht, aber es reduziert sich doch darauf, dass immer (R09 und R014) gegeben sein muss. Demnach kannst Du doch zumindest umformen

( R09 AND R014) AND (
( R010 * R011 * R07 * R06 * R018 * R02 * R01 * R013 ) OR ( R010 * R011 * R07 * R06 * R05 * R017 * R02 * R01 * R013 )
)

-oder konsequent weitergesponnen.
( R09 AND R014 AND R010 AND R011 AND R07 AND R06 AND R01 AND R013) AND ( R018 OR R017 )

Oder verstehe ich die Frage miss?

Grüße
Biber

Du verstehst meine Frage richtig, nur habe ich hier einen kleinen Termausschnitt reinkopiert. Es stimmt, dass man hier R09 und R014 ausklammern kann, doch bei dem gesamten Term würde ich das gerne automatisiert haben., da der Term so aussieht:

RL1 = ( R09 * R014 )
+ ( R09 * R010 * R011 * R07 * R06 * R018 * R02 * R01 * R013 * R014 )
+ ( R09 * R010 * R011 * R07 * R06 * R05 * R017 * R02 * R01 * R013 * R014 )
+ ( R09 * R010 * R011 * R07 * R06 * R05 * R04 * R016 * R02 * R01 * R013 * R014 )
+ ( R09 * R010 * R011 * R07 * R06 * R05 * R04 * R03 * R01 * R013 * R014 )
+ ( R09 * R010 * R011 * R02 * R01 * R013 * R014 )
+ ( R09 * R010 * R012 * R05 * R06 * R07 * R02 * R01 * R013 * R014 )
+ ( R09 * R010 * R012 * R05 * R018 * R02 * R01 * R013 * R014 )
+ ( R09 * R010 * R012 * R017 * R02 * R01 * R013 * R014 )
+ ( R09 * R010 * R012 * R04 * R016 * R02 * R01 * R013 * R014 )
+ ( R09 * R010 * R012 * R04 * R03 * R01 * R013 * R014 )
+ ( R08 * R07 * R011 * R010 * R014 )
+ ( R08 * R07 * R011 * R012 * R05 * R018 * R02 * R01 * R013 * R014 )
+ ( R08 * R07 * R011 * R012 * R017 * R02 * R01 * R013 * R014 )
+ ( R08 * R07 * R011 * R012 * R04 * R016 * R02 * R01 * R013 * R014 )
+ ( R08 * R07 * R011 * R012 * R04 * R03 * R01 * R013 * R014 )
+ ( R08 * R07 * R02 * R03 * R04 * R012 * R010 * R014 )
+ ( R08 * R07 * R02 * R01 * R013 * R014 )
+ ( R08 * R06 * R018 * R011 * R010 * R014 )
+ ( R08 * R06 * R018 * R011 * R012 * R017 * R02 * R01 * R013 * R014 )
+ ( R08 * R06 * R018 * R011 * R012 * R04 * R016 * R02 * R01 * R013 * R014 )
+ ( R08 * R06 * R018 * R011 * R012 * R04 * R03 * R01 * R013 * R014 )
+ ( R08 * R06 * R018 * R02 * R03 * R04 * R012 * R010 * R014 )
+ ( R08 * R06 * R018 * R02 * R01 * R013 * R014 )
+ ( R08 * R06 * R05 * R017 * R011 * R010 * R014 )
+ ( R08 * R06 * R05 * R017 * R011 * R012 * R04 * R016 * R02 * R01 * R013 * R014 )
+ ( R08 * R06 * R05 * R017 * R011 * R012 * R04 * R03 * R01 * R013 * R014 )
+ ( R08 * R06 * R05 * R017 * R02 * R03 * R04 * R012 * R010 * R014 )
+ ( R08 * R06 * R05 * R017 * R02 * R01 * R013 * R014 )
+ ( R08 * R06 * R05 * R012 * R010 * R014 )
+ ( R08 * R06 * R05 * R012 * R011 * R02 * R01 * R013 * R014 )
+ ( R08 * R06 * R05 * R04 * R016 * R011 * R010 * R014 )
+ ( R08 * R06 * R05 * R04 * R016 * R02 * R01 * R013 * R014 )
+ ( R08 * R06 * R05 * R04 * R03 * R02 * R011 * R010 * R014 )
+ ( R08 * R06 * R05 * R04 * R03 * R01 * R013 * R014 )
+ ( R013 * R014 )
+ ( R01 * R02 * R011 * R010 * R014 )
+ ( R01 * R02 * R011 * R012 * R05 * R06 * R08 * R09 * R014 )
+ ( R01 * R02 * R07 * R08 * R09 * R014 )
+ ( R01 * R02 * R07 * R06 * R05 * R012 * R010 * R014 )
+ ( R01 * R03 * R04 * R012 * R010 * R014 )
+ ( R01 * R03 * R04 * R012 * R011 * R07 * R08 * R09 * R014 )
+ ( R01 * R03 * R04 * R05 * R06 * R08 * R09 * R014 )
+ ( R01 * R03 * R04 * R05 * R06 * R07 * R011 * R010 * R014 )
+ ( R01 * R03 * R04 * R05 * R018 * R011 * R010 * R014 )
+ ( R01 * R03 * R04 * R05 * R018 * R07 * R08 * R09 * R014 )
+ ( R01 * R03 * R04 * R017 * R011 * R010 * R014 )
+ ( R01 * R03 * R04 * R017 * R07 * R08 * R09 * R014 )
+ ( R01 * R03 * R016 * R011 * R010 * R014 )
+ ( R01 * R03 * R016 * R011 * R012 * R05 * R06 * R08 * R09 * R014 )
+ ( R01 * R03 * R016 * R07 * R08 * R09 * R014 )
+ ( R01 * R03 * R016 * R07 * R06 * R05 * R012 * R010 * R014 )
+ ( R014 * R09 * R08 * R07 * R011 * R012 * R05 * R018 * R02 * R01 )
+ ( R014 * R09 * R08 * R07 * R011 * R012 * R017 * R02 * R01 )
+ ( R014 * R09 * R08 * R07 * R011 * R012 * R04 * R016 * R02 * R01 )
+ ( R014 * R09 * R08 * R06 * R018 * R011 * R012 * R017 * R02 * R01 )
+ ( R014 * R09 * R08 * R06 * R018 * R011 * R012 * R04 * R016 * R02 * R01 )
+ ( R014 * R09 * R08 * R06 * R018 * R011 * R012 * R04 * R03 * R01 )
+ ( R014 * R09 * R08 * R06 * R018 * R02 * R01 )
+ ( R014 * R09 * R08 * R06 * R05 * R017 * R011 * R012 * R04 * R016 * R02 * R01 )
+ ( R014 * R09 * R08 * R06 * R05 * R017 * R011 * R012 * R04 * R03 * R01 )
+ ( R014 * R09 * R08 * R06 * R05 * R017 * R02 * R01 )
+ ( R014 * R09 * R08 * R06 * R05 * R04 * R016 * R02 * R01 )
+ ( R014 * R010 * R011 * R07 * R06 * R018 * R02 * R01 )
+ ( R014 * R010 * R011 * R07 * R06 * R05 * R017 * R02 * R01 )
+ ( R014 * R010 * R011 * R07 * R06 * R05 * R04 * R016 * R02 * R01 )
+ ( R014 * R010 * R012 * R05 * R018 * R07 * R08 )
+ ( R014 * R010 * R012 * R05 * R018 * R02 * R01 )
+ ( R014 * R010 * R012 * R017 * R07 * R08 )
+ ( R014 * R010 * R012 * R017 * R02 * R01 )
+ ( R014 * R010 * R012 * R04 * R016 * R07 * R08 )
+ ( R014 * R010 * R012 * R04 * R016 * R02 * R01 )
+ ( R014 * R013 * R01 * R03 * R04 * R05 * R018 * R011 * R010 * R09 )
+ ( R014 * R013 * R01 * R03 * R04 * R05 * R018 * R07 * R08 )
+ ( R014 * R013 * R01 * R03 * R04 * R017 * R011 * R010 * R09 )
+ ( R014 * R013 * R01 * R03 * R04 * R017 * R07 * R08 )
+ ( R014 * R013 * R01 * R03 * R016 * R011 * R010 * R09 )
+ ( R014 * R013 * R01 * R03 * R016 * R011 * R012 * R05 * R06 * R08 )
+ ( R014 * R013 * R01 * R03 * R016 * R07 * R08 )
+ ( R014 * R013 * R01 * R03 * R016 * R07 * R06 * R05 * R012 * R010 * R09 )
+ ( R014 * R015 )

...und davon müssen noch 35 weitere Terme umgeformt werden :D

Na ja,

dennoch ist doch -auf den ersten Blick offensichtlich- ein immenser Anteil an Redundanz in den einzelnen Tupeln.
So enthält doch jede Zeile/Teilbedingung die "R014".

Und natürlich lässt es sich, vielleicht vergleichbar mit der Suche nach dem größten gemeinsamen Teiler, automatisiert umformen.

Aber dazu müssten wir doch wissen:

wer oder was generiert denn diese Terme?
welche Skript/Programmiersprache steht Dir denn zur Verfügung?

Denn vermutlich wolltest Du es nicht mit einem Texteditor neu sortieren.

Grüße
Biber

Dein drei kürzesten terme sind
( R09 * R014 )
( R014 * R015 )
( R013 * R014 )
verodert mit anderen. das bedeutet doch das alle andern terme indenen "R09 * R014", "R014 * R015 " und "R013 * R014" vorkommen schonmal wegfallen.
Somit reduziert sich das ganze hierauf:

RL1 = ( R09 * R014 )
+ ( R013 * R014 )
+ ( R014 * R015 )
+ ( R08 * R07 * R011 * R010 * R014 )
+ ( R08 * R07 * R02 * R03 * R04 * R012 * R010 * R014 )
+ ( R08 * R06 * R018 * R011 * R010 * R014 )
+ ( R08 * R06 * R018 * R02 * R03 * R04 * R012 * R010 * R014 )
+ ( R08 * R06 * R05 * R017 * R011 * R010 * R014 )
+ ( R08 * R06 * R05 * R017 * R02 * R03 * R04 * R012 * R010 * R014 )
+ ( R08 * R06 * R05 * R012 * R010 * R014 )
+ ( R08 * R06 * R05 * R04 * R016 * R011 * R010 * R014 )
+ ( R08 * R06 * R05 * R04 * R03 * R02 * R011 * R010 * R014 )
+ ( R01 * R02 * R011 * R010 * R014 )
+ ( R01 * R02 * R07 * R06 * R05 * R012 * R010 * R014 )
+ ( R01 * R03 * R04 * R012 * R010 * R014 )
+ ( R01 * R03 * R04 * R05 * R06 * R07 * R011 * R010 * R014 )
+ ( R01 * R03 * R04 * R05 * R018 * R011 * R010 * R014 )
+ ( R01 * R03 * R04 * R017 * R011 * R010 * R014 )
+ ( R01 * R03 * R016 * R011 * R010 * R014 )
+ ( R01 * R03 * R016 * R07 * R06 * R05 * R012 * R010 * R014 )
+ ( R014 * R010 * R011 * R07 * R06 * R018 * R02 * R01 )
+ ( R014 * R010 * R011 * R07 * R06 * R05 * R017 * R02 * R01 )
+ ( R014 * R010 * R011 * R07 * R06 * R05 * R04 * R016 * R02 * R01 )
+ ( R014 * R010 * R012 * R05 * R018 * R07 * R08 )
+ ( R014 * R010 * R012 * R05 * R018 * R02 * R01 )
+ ( R014 * R010 * R012 * R017 * R07 * R08 )
+ ( R014 * R010 * R012 * R017 * R02 * R01 )
+ ( R014 * R010 * R012 * R04 * R016 * R07 * R08 )
+ ( R014 * R010 * R012 * R04 * R016 * R02 * R01 )

jetzt noch ein paar sachen vorklammernudn fertig.
Dann das ganze wiederholen.

Es hilft sehr wen du die Reihenfolge sortiert udn bstände läst, so das di werte imem ran der gleichen position unter einande stehen. dan sirehs du was kurz ist udn was andere kombinationen überbrückt.
Programmiertechnisch gibt das eine Tabelle die immer wieder sortiert udn durchsucht wird und bei der imemr wieder gleich vorkommende strukturen vorgeklammert oder gleich ganz gelöscht werden.
Aber wenns nur ein paar Formeln sind wirds woll manuell schneller gehen als bis du was zusammenprogrammiert hast.

Ihr habt Recht, soweit kann man das im Kopf machen. Doch damit habe ich ewig verbracht, da ich verdammt viele dieser Terme habe...und noch viel größere, bei denen man etliches ausklammern könnte...doch damit würde ich wieder Stunden verbringen, deshalb habe ich gefragt ;)

Ich habe rausgefunden, dass das Programm Maple mir helfen könnte. Es gibt die Funktion "BooleanSimplify", die so eine lange Gleichung kürzt.

Doch was mich wundert ist, wenn ich das Ergebnis hinterher mittels "Equivalent" prüfe, ob die Funktion mit der Ausgangsfunktion gleichwertig ist, kommt immer false raus :/

Woran liegt das?

Rechne doch mal eine gleichung per hand nach ob das ergebniss stimmt. dan weist du ja woran es liegt. Aber es macht schon sinn das die Gleichungen nach der Vereinfachung eben nicht mehr gleich sind, da ja im Gegensatz zu mathematischen Formeln hier auch so einfach ganze Terme wegfallen können und dadurch ja keine wirkliche Umrechnung stattfindet sondern eben erkannt wird das bestimmte Ausdrücke überflüssig werden.
Aus dienem geposteten Beispiel nehme ich einfach mal die ersten paar Zeilen:

RL1 = 
( R09 * R014 )
+ ( R09 * R010 * R011 * R07 * R06 * R018 * R02 * R01 * R013 * R014 )
+ ( R09 * R010 * R011 * R07 * R06 * R05 * R017 * R02 * R01 * R013 * R014 )
+ ( R09 * R010 * R011 * R07 * R06 * R05 * R04 * R016 * R02 * R01 * R013 * R014 )
+ ( R09 * R010 * R011 * R07 * R06 * R05 * R04 * R03 * R01 * R013 * R014 )
+ ( R09 * R010 * R011 * R02 * R01 * R013 * R014 )
+ ( R09 * R010 * R012 * R05 * R06 * R07 * R02 * R01 * R013 * R014 )
+ ( R09 * R010 * R012 * R05 * R018 * R02 * R01 * R013 * R014 )
+ ( R09 * R010 * R012 * R017 * R02 * R01 * R013 * R014 )
+ ( R09 * R010 * R012 * R04 * R016 * R02 * R01 * R013 * R014 )
+ ( R09 * R010 * R012 * R04 * R03 * R01 * R013 * R014 )

In den Zeilen 3-12 kommen jeweils die Kombination "R09 * R014" vor. Das kannst du also vorlammern wodurch folgender Ausdruck entsteht:

RL1 = ( R09 * R014 ) * (1 + (der Rest))

Es ist also egal was sosnt noch kommt (im Rest), durch die 1 reicht:

RL1 = ( R09 * R014 )

Und alles andere kann wegfallen. Dadurch sind die Gleichungen eben nicht mehr gleich, aber dennoch korrekt umgeformt.

Also ist es völlig egal, ob ich die vereinfachte oder die lange Form nehme? Danke, das erleichtert mir vieles!

Achso, mir ist noch aufgefallen, dass Maple die ganzen Klammern entfernt. Ist es denn egal, ob man
(a * b) + (c * d)
oder
a * b + c * d
schreibt?

Eine letzte Frage hab ich dann nebenbei noch, undzwar: Wie kopiert man Text aus Maple raus? Bei mir macht er in z. B. Word immer ein Bild draus :/

Vielen Dank!
Martin

Es ist nicht immer egal. Es kommt drauf an ob es logisch ist.
(a * b) + (c * d) zu a * b + c * d geht
(a + b) * (c + d) zu a + b * c + d nicht (so wie ich es kenne zumindest)
Die Zeichen mit Mal und Plus kommen ja nicht ohne Grund. Normalerweiße kommt UND vor ODER, wie eben Punkt vor Strich Rechnung.
Mit Mapel kenne ich mich nicht aus, sorry.