•  Download Version 0.2 (ca.170k)
• Einleitung
• Bedienung
• Änderungen
• FAQ
• neu! Aufbau des Parsers

Im Verlaufe der Studienvorlesungen zu Mathematik I und Technischen Informatik I stand ich enorm oft vor dem Problem, ständig Wertetabellen zu erstellen. Während es bei 2 Variablen noch durchaus schnell und einfach geht, können komplexere Ausdrücke, insbesondere beim Aussagenkalkül, die Angelegenheit zu einer nur schwer fehlerfrei durchzuführenden Sache wachsen lassen. Neben dem exponentiell ansteigenden Schreibaufwand sind das Hauptübel die kleinen Flüchtigkeitsfehler, die trotz intensiver Konzentration immer wieder Wege finden, unbemerkt zu bleiben.

So habe ich mir also gesagt, dass ich als angehender Softwaresystemtechniker mein Werkzeug, den Computer, dazu bringen müßte, meine Ergebnisse überprüfen zu könen. Das Ergebnis meiner Bemühungen liegt mit der LieMachine jetzt vor. Und nicht vergessen: ich habe das Programm in erster Linie für mich selbst geschrieben, deshalb kann ich auf keinen Fall Allgemeingültigkeit und Fehlerfreiheit garantieren. Je mehr aber damit arbeiten, mißtrauisch auch mal die Ergebnisse von Hand überprüfen, desto besser und flexibel wird es.

Die Eingabe erfolgt genau so, wie man es aus dem Unterricht gewohnt ist. Das bedeutet, dass verschachtelten Klammern, Konstanten usw. erlaubt sind. Die einzige Einschränkung besteht darin, dass die Variablen a,b,c,... heißen müssen (x₁,x₂,... funktionieren nicht !). Zur Zeit belasse ich es bei 12 Variablen, d.h. bei l (kleines L) ist Schluß. Diese Anzahl ist willkürlich gewählt und kann von mir noch beliebig erweitert werden. Ich muß jedoch davor warnen, diese Grenze von 12 auszureizen, schließlich berechnet der Computer dann 2¹² = 4096 Funktionswerte. Da bekommt zwar nicht das Programm, aber die Fenster- und deren Speicherverwaltung durch Windows arge Probleme.

Ich habe nicht alle Verknüpfungsoperatoren implementiert, was darin begründet ist, dass mir einfach keine sinnvollen Zeichen auf der Tastatur dafür einfielen (allerdings betrifft dies nur NAND und NOR). Die zur Verfügung stehenden Zeichen sind größtenteils bei C++ und Java entliehen, so dass normalerweise kaum Probleme beim Eingeben auftreten sollten. Seit der Version 0.2 können auch über die entsprechenden Buttons unterhalb der Eingabezeile die Aussagen zusammengeklickt werden. Hier eine Kurzübersicht der Zeichen:

Die Prioritäten der Operatoren verteilen sich wie folgt (ranghöchste zuerst):

Bei der Eingabe sind Groß-/Kleinschreibung und überflüssige Leerzeichen egal, die werden automatisch korrigiert bzw. entfernt. Die Fehlerabfangroutinen sind aber lediglich rudimentär, also alles andere als perfekt. Nach all der Theorie nun ein Bildschirmphoto:

In der Eingabezeile ("Aussage") tippt man den zu evaluierenden Ausdruck ein, und ein einfaches Enter erstellt die darunter stehende Tabelle. Bei mehr als 16 zu berechnenden Möglichkeiten, also bei mehr als 4 Variablen, erscheint rechts automatisch ein Scrollbalken.

Weiter wird noch die Konjunktive Normalform (KNF), die Disjunktive Normalform (DNF) und die Antivalente Normalform (ANF) ermittelt. Dabei wird der Sonderfall der Tautologie beachtet und kenntlich gemacht. Sollten die Normalformen, wie im Foto, für die Bildschirmwiedergabe zu lang sein, so kann man mit der Maus draufklicken und mit dem Cursor nach links bzw. rechts gehen. Ebenso sind Markierungen und Kopieraktionen über die Zwischenablage möglich, da dies eigentlich nur schreibgeschützte Eingabefelder sind.

Die Felder K₀, K₁, K_sd, K_lin und K_mon geben an, ob die Funktion jeweils zur abgeschlossende Klasse der 0-erhaltenen, 1-erhaltenen, selbstdualen, linearen oder monotonen Funktionen gehört. Gehört sie zu allen 5, so handelt es sich um eine Shefferfunktion.

Welche Voraussetzungen an die Hard- / Software stellt die LieMachine ?

32-Bit-Windows reicht aus. Ich habe allerdings bislang nur unter Windows 98 und NT 4 (SP4) getestet, die 95er dürfte genauso problemlos sein. Win32s fällt aus der Reihe, da das verwendete ListControl (die Tabelle) erst mit der Oberflächentechnologie von Windows 95 Einzug hielt. Es sollte weiterhin irgendein Internet-Browser installiert sein.

Ich habe aus Platzgründen auf eine Installationsroutine verzichtet, da sie wesentlich größer als das eigentliche Programm wäre. Somit braucht bloß ein eigenes Verzeichnis erstellt werden, in das die Programmdateien hineinkopiert werden, fertig !

Die Parser-Engine ist zwar in ANSI-C++ erstellt worden und somit problemlos portabel, aber ich denke nicht an eine X-Windows-Portierung (sorry, Linux-Fans !), da ich die gesamte Benutzeroberfläche neu schreiben müßte. Falls jemand daran interessiert ist, kann er sich die Funktionsweise und den Quellcode des Parsers anschauen.

Die Rechengeschwindigkeit wird erst ab ca. 10 Variablen zu einem Faktor und selbst dann liegt die Laufzeit im deutlich einstelligen Sekundenbereich. Genaue Zahlen kann und will ich hier nicht nennen, da mir als Testplattformen nur 2 Pentium III (450 und 500 MHz) zur Verfügung stehen ;). Der Hauptspeicherbedarf ist für mich nur schwer meßbar, da ich ständig an den Routinen herumexperimentiere und sich ihr Laufzeitverhalten dadurch teilweise extrem verändert. In jedem Fall werden weniger als 1 MByte RAM verbraucht, wovon der Großteil auf die Oberflächengestaltung entfällt.

Die Hilfe funktioniert nicht !

Genau diese Datei, die hier gerade gelesen wird, ist die Hilfe. Die von der LieMachine aufgerufene Hilfe greift zur Anzeige auf den Internet-Browser zurück (meist also Internet Explorer, Navigator oder Opera). Vielleicht wurden nicht alle Verknüpfungen richtig in die Registry eingetragen, das überprüft man am besten, indem man versucht, mit dem Windows Explorer diese Datei (Index.htm) zu öffnen. Weiter gilt: die Datei Index.html und alles, was irgendwie mit LieMachine beginnt, löschen, es handelt sich um integrale Bestandteile der Hilfe !

In der Version 0.10 hieß die Hilfe noch ReadMe.Htm. Wer sich also die alte Version und dann das Update installiert hat, der kann sich mit einer einfachen Umbennung von ReadMe.htm in Index.htm behelfen.

Wie kann ich die Ergebnisse ausdrucken ?

Es gibt keine integrierten Druckroutinen. Somit bleibt nur der Weg über die Windows-Zwischenablage (Alt-Druck, dann irgendwo (z.B. Word) einfügen und von da ausdrucken) oder das gute, alte Abschreiben.

Warum gibt es zwei Versionen der LieMachine ?

Im Zip-Archiv sind LieMachine.exe und LieMachineSmall.exe enthalten. Ersteres hat die MFC-Bibliothek statisch eingelinkt, das zweite dagegen vertraut darauf, daß die MFC-DLLs schon irgendwo im Windows-System vorhanden sind, was aber heutzutage Standard sein sollte. Funktional gibt es, wenn beide die gleiche Versionsnummer haben, zwischen ihnen keinen Unterschied. Jedoch ist auf der Webseite oft von LieMachineSmall.exe schon ein Update vorhanden. Dieses behebt kleinere Fehler oder bringt neue Features, ist aber in der Regel noch experimentell. Es werden alle wichtigen Updates parallel bei beiden Versionen durchgeführt, so daß die beste Lösung in der Paketversion besteht, da nur diese die Hilfe (nämlich diese Datei) enthält.

Was wird noch verändert oder gar verbessert ?

Das hängt ganz davon ab, wieviel Zeit ich habe. Im Moment scheue ich den Aufwand, die Eingabemaske derart zu programmieren, daß die Operatoren richtig angezeigt werden, daß also das XOR nicht nur ein +, sondern auch noch den entsprechenden Kreis hat: Å. Dieses Problem würde sich jedoch in Luft auflösen, wenn ich mich dazu bewegen kann, die Dialoganwendung in eine SDI-/MDI-Anwendung umzuschreiben. Dann erledigt der Symbol-Zeichensatz von Windows die optische Gestaltung.

Mir schwebt auch vor, dass man die Wertetabelle vorgeben kann (eventuell mit dont-care-Stellen) und daraus dann die Normalformen ermittelt werden. Zusätzlich könnte die DNF noch optimiert werden (Quine-McCluskey ist straight-forward einbaubar).

Für weitere Anregungen oder reproduzierbare Fehler bin ich jederzeit offen.

Woher kriegt man den Sourcecode ?

Zur Zeit ist ist nur der Quelltext des Parser frei verfügbar. Der Grund liegt einfach darin, dass im Rest noch etliche kleine Bugs schlummern und (leider) nur sehr wenig kommentiert ist. Das einzige, was ich erzähle, ist, dass ich das Programm mit Visual C++ 5 in etwa 900 Zeilen geschrieben habe und es somit nicht allzuviel größer als diese Dokumentation ist. Wenn die Evolution des Programmes so weit fortgeschritten ist, dass ich es - in einem sinnvollen Rahmen - als vollständig und fehlerfrei erachte, werde ich den kompletten Quellcode veröffentlichen.

Wer ein ernstes Interesse an der Mit- und Weiterentwicklung der LieMachine hat, kann gerne mit mir in Kontakt treten (Adressen stehen weiter unten im Text).

Was bedeutet eigentlich der Name "LieMachine" ?

Das ist ein Akronym für Logical Instructions Evaluating Machine. Vielleicht bedeutet LIE (lügen) auch nur, daß man ab und zu kontrollieren sollte, was der Computer berechnet, denn er hat beleibe nicht immer recht. Somit darf niemand das Denken komplett den Maschinen überlassen, schon gar nicht bei Hausaufgaben.

Und wer ist der Autor ?

Ich heiße Stephan Brumme, bin 31 Jahre alt und studiere Softwaresystemtechnik am Hasso-Plattner-Institut der Universität Potsdam. Weitere Infos gibt in englisch.

Kontakt:

• eMail:  mail@stephan-brumme.com
• Homepage:  www.stephan-brumme.com