AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

Boolsche Ausdrücke vereinfachen

Ein Thema von jfheins · begonnen am 12. Apr 2007 · letzter Beitrag vom 12. Apr 2007
Antwort Antwort
Benutzerbild von jfheins
jfheins

Registriert seit: 10. Jun 2004
Ort: Garching (TUM)
4.579 Beiträge
 
#1

Boolsche Ausdrücke vereinfachen

  Alt 12. Apr 2007, 17:13
Guten Abend

Ich würde gerne Boolsche Ausdrücke vereinfachen ...

Im Gegensatz zu Luckie habe ich jedoch keinen bestimmten Ausdruck da, sondern wüsste gerne mehr über das allgemene Verfahren, mit dem man solche Ausdrücke vereinfachen kann.

Mal schauen, vll. programmiere ich auch mal so n Tool dafür, wenn ichs verstanden hab
(Features wären dann wahrscheinlich sowas wie "Ausdruck as Tabelle generieren" oder "Ausdruck vereinfachen", aber das ist jetzt Nebensache ...)

Ich hab schon gesehen (in unserem Lehrbuch) dass es da "ein paar" Gleichen gibt, mit denen man rumsoielen kann, aber irgendwie ... greift das nicht so richtig

Wäre nett, wenn mir da wer helfen könnte ... *zu alcähh... Informatik Studenten im allgemeinen rüberschiel*

Danke schonmal
  Mit Zitat antworten Zitat
Benutzerbild von Matze
Matze
(Co-Admin)

Registriert seit: 7. Jul 2003
Ort: Schwabenländle
14.929 Beiträge
 
Turbo Delphi für Win32
 
#2

Re: Boolsche Ausdrücke vereinfachen

  Alt 12. Apr 2007, 17:18
Moin,

ich bin zwar kein Informatik-Student (mehr), aber ich antworte trotzdem mal.

Vereinfachen kannst du die logische Ausdrücke, indem du die konjunktive und disjunktive Normalform ermittelst, doch diese Formen liefern nicht unbedingt den am weitest vereinfachten Ausdruck.

Aber das Karnaugh-Diagramm könnte dich interessieren und das Verfahren nach Quine und McCluskey ebenfalls.
  Mit Zitat antworten Zitat
Benutzerbild von jfheins
jfheins

Registriert seit: 10. Jun 2004
Ort: Garching (TUM)
4.579 Beiträge
 
#3

Re: Boolsche Ausdrücke vereinfachen

  Alt 12. Apr 2007, 17:30
Zitat von Matze:
Moin,

ich bin zwar kein Informatik-Student (mehr), aber ich antworte trotzdem mal.
Macht nix, im Gegenteil

Ich weis zwar nicht, was diese ...junktiven Ausdrücke sind, aber dieses Diagram mit den Kreisen sieht schön aus (und inzwischen geht Wikipedia auch wieder ...)

Wenn ich also 3 Variablen hab (maximum für mich, mehr hab ich nicht ) dann mach is so ein Diagram
http://upload.wikimedia.org/wikipedi...agramm_ABC.png
Und mach Blöcke, die alle einsen abdecken. Dann gucke ich, was in jedem Block gleich ist, und kann dann den Ausdruck einfach zusammensetzen. Hab ich das richtig verstanden ?
  Mit Zitat antworten Zitat
Benutzerbild von 3_of_8
3_of_8

Registriert seit: 22. Mär 2005
Ort: Dingolfing
4.129 Beiträge
 
Turbo Delphi für Win32
 
#4

Re: Boolsche Ausdrücke vereinfachen

  Alt 12. Apr 2007, 17:31
Eine DNF ist schon recht nützlich dabei, auch ein binärer Entscheidungsbaum hilft da sehr.

Das funktioniert so:

Du nimmst dir eine aussagenlogische Formel (oder einen Booleschen Ausdruck) und schaust nach, welche Variable am häufigsten vorkommt. Die nennen wir dann V. Dann zeichnest du von der Formel aus zwei Zweige nach unten. Bei dem einen setzt du V:=0, beim anderen V:=1 bzw. V:=F(alse) und V:=T(rue) oder auch V:=O und V:=L.

Dann vereinfachst du nach einer Reihe von Regeln:
A and 0=0, A and 1=A, A or 0=A, A or 1=A für beliebige Terme A
not 0=1, not 1=0
A and A=A, A or A=A, A and not A=0, A or not A=1

Klammern darfst du auflösen, nach den De-Morgan-Formeln, Absorptionsgesetz usw.

Wenn du das hast, machst du bei den zwei Subknoten wieder das gleiche: Häufigste Variable suchen, einsetzen usw.

Irgendwann hast du dann lauter terminale Knoten, also Formeln, in denen keine Variable mehr vorkommt, die lassen sich dann vereinfachen als 0 oder 1.

Da kannst du dann eventuell ableiten, wie die Formel "funktioniert", also welche Variablen überhaupt wichtig sind, welche sich "rauskürzen", ob die Formel allgemeingültig ist oder unerfüllbar und wieviele Modelle sie hat.

EDIT: Disjunktive Normalform geht so:

Sei V eine Variable.
V und not V sind Literale.

Seien L(1) bis L(n) Variablen.
Ein Minterm ist L(1) and L(2) and ... and L(n).

Seien M(1) bis M(n) Minterme.
Eine Disjunktive Normalform, auch Boolesches Polynom genannt, ist M(1) or M(2) or ... or M(n).

Eine Disjunktive Normalform ist also die Oder-Verbindung der Und-Verbindung von verneinten oder nicht-verneinten Variablen.
Manuel Eberl
„The trouble with having an open mind, of course, is that people will insist on coming along and trying to put things in it.“
- Terry Pratchett
  Mit Zitat antworten Zitat
Benutzerbild von jfheins
jfheins

Registriert seit: 10. Jun 2004
Ort: Garching (TUM)
4.579 Beiträge
 
#5

Re: Boolsche Ausdrücke vereinfachen

  Alt 12. Apr 2007, 17:37
Ehrlich gesagt: Da finde ich das mit der coolen Tabelle einfacher

Zitat:
Klammern darfst du auflösen, nach den De-Morgan-Formeln, Absorptionsgesetz usw.
Da wollte ich ja grad drumherum kommen
  Mit Zitat antworten Zitat
Benutzerbild von 3_of_8
3_of_8

Registriert seit: 22. Mär 2005
Ort: Dingolfing
4.129 Beiträge
 
Turbo Delphi für Win32
 
#6

Re: Boolsche Ausdrücke vereinfachen

  Alt 12. Apr 2007, 17:40
Die sind nicht schwer.

De-Morgan-Gesetze:
not (A and B)=not A or not B
not (A or B)=not A and not B

Absorptionsgesetze:
A and (A or B)=A
A or (A and B)=A

Idempotenzgesetze:
A and A=A
A or A=A

Distributivgesetze:
A and (B or C)=(A and B) or (A and C)
A or (B and C)=(A or B) and (A or C)
Manuel Eberl
„The trouble with having an open mind, of course, is that people will insist on coming along and trying to put things in it.“
- Terry Pratchett
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 02:10 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz