inspire
Aug 10, 2009, updated at 18:44:14 (UTC)
view4025
view10
0
Goto Top

Boolsche Funktion vereinfachen

GermansolvedQuestionDevelopment
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? face-smile

Gruß
Martin
comment-contentCommentShareShare
Share on Facebook Share on Twitter Share on Reddit Share on Linkedin

Content-Key: 122438

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

Printed on: April 23, 2024 at 22:04 o'clock

10 Comments
Latest comment
Goto Top
Member: Biber
Biber Aug 10, 2009 at 19:47:47 (UTC)
Goto Top
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
Member: inspire
inspire Aug 10, 2009 at 19:57:16 (UTC)
Goto Top
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
Member: Biber
Biber Aug 10, 2009 at 20:10:41 (UTC)
Goto Top
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
Member: miniversum
miniversum Aug 10, 2009 at 20:58:01 (UTC)
Goto Top
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.
Member: inspire
inspire Aug 11, 2009 at 10:38:33 (UTC)
Goto Top
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 ;)
Member: inspire
inspire Aug 11, 2009 at 17:33:57 (UTC)
Goto Top
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?
Member: miniversum
miniversum Aug 11, 2009 at 17:57:11 (UTC)
Goto Top
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.
Member: inspire
inspire Aug 11, 2009 at 18:16:52 (UTC)
Goto Top
Also ist es völlig egal, ob ich die vereinfachte oder die lange Form nehme? Danke, das erleichtert mir vieles! face-smile

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
Member: miniversum
miniversum Aug 11, 2009 at 18:30:01 (UTC)
Goto Top
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.
Member: inspire
inspire Aug 11, 2009 at 18:41:23 (UTC)
Goto Top
Ok, da meine Formeln ausschließlich in der Form (a * b) + (c * d) sind, kann ich das wohl so übernehmen, das ist gut face-smile

EDIT: Wäre nett, wenn mir jetzt noch jemand sagen könnte, wie ich Text aus Maple raus kopieren kann face-smile
GermansolvedQuestionDevelopment
Hotly discussed
gleixnerdCheck of ZFW Firewallgleixnerd - 5 CommentsjstrickerWireguard VPN on UDM Pro behind Fritzbox - Handshake did not completejstricker - 3 CommentsAlexWishaHow to set up and configure a Linux GRE tunnelAlexWisha - 3 Comments