# Boolsche Algebra - Funktionen vereinfachen?



## Zorck (2. September 2002)

Hallo,
ich hab mal ne Frage. Und zwar will ich ein Programm schreiben.
Wollen ist vielleicht nicht ganz richtig. Ich muss.
Daher wollte ich fragen, ob mir wer helfen kann. Hat irgendwer Quelltext rumzuliegen, mit dem ich Aussagenlogische Funktionen vereinfachen und/oder Schaltungen dazu zeichnen kann?
Muss nich unbedingt in VB sein. Vielleicht kann ich mir dann den Quelltext auseinanderfutzeln.
Fertige Programme(natürlich mit Quelltext)oder Adressen sowie Tipps kann ich natürlich auch gut gebrauchen.

Ich hoffe es kann mir wer helfen. Danke schon einmal!


----------



## Dario Linsky (2. September 2002)

ich versteh irgendwie nicht so ganz, worauf du hinaus willst. wenn es dir nur darum geht, fallunterscheidungen zu verkürzen, kannst du einfach logische ausdrücke zuweisen. 
	
	
	



```
If x = 2 Then
    y = False
Else
    y = True
End If
```
 ... wird ... 
	
	
	



```
y = Not (x = 2)
```

ansonsten beschreib doch mal genauer, was du meinst.


----------



## Zorck (2. September 2002)

Es geht darum, ein Programm zu schreiben mit dem man logische Funktionen vereinfachen kann. Diese Funktionen dienen dazu logische Schaltungen zu zeichnen. So wie ein Computer halt funktioniert nur auf der niedrigsten Stufe.

Da man ja immer danach bestrebt ist so wenig Bauteile wie möglich zu verwenden um alles billiger und kleiner zu gestalten, versucht man solche Funktionen zu vereinfachen.

Weist du jetzt was ich meine??
Wenn nicht, kann ich mir auch nicht vorstellen, dass du mir dann helfen könntest (is nich böse gemeint  ).
Aber vielleicht hab ichs auch wirklich nur zu blöd beschrieben.


----------



## Dario Linsky (2. September 2002)

was du meinst, versteh ich schon. aber ich wüsste nicht, wie man eine boolesche anweisung vereinfachen könnte. man könnte z.b. eine komplexe anweisung wie 
	
	
	



```
If (Not x Or y) And ((z = 7) Or (z = 5)) Then ...
```
 aufteilen, und in einzelnen schritten durch die gleichen bauteile laufen lassen. aber das ist wahrscheinlich nicht das, was du meinst. mehr fällt mir dazu aber nicht ein...


----------



## Zorck (2. September 2002)

Es geht darum logische Funktionen nach bestimmten Gesetzen umzustellen und so zu vereinfachen. Also genauso wie bei mathematischen Funktionen.

So ist z.B. (not A and A) = 0
Dann gibt es aber auch wie bei "normalen" Gleichungen Distributivgesetze usw.

Noch ein Beispiel: f(A,B)=not(not (A and B) and (not A and B)) 
und nach der Vereinfachung: f(A,B) = A and not B

Das ist doch nun einfacher und leichter vorzustellen. Und man benötigt nun weniger Bauteile.


----------



## Dario Linsky (2. September 2002)

schon klar, was du meinst. eine solche code-optimierung ist bei manchen entwicklungsumgebungen integriert. das geht also schon teilweise in die gleiche richtung wie compilerbau.
aber da boolesche algebra ja eigentlich nicht viele schlüsselworte kennt (not, and, or, nor, xor, etc.) lässt sich da sicher was einfaches machen. du kannst ja einfach eine eingegebene logische anweisung wie in deinem beispiel eingeben und in ihre einzelteile zerlegen. danach vereinfachst du dann das ganze, indem du ein paar sachen zusammenfasst, oder einfach nur negierst.


----------



## Zorck (2. September 2002)

Ja, vom Prinzip ist mir das schon klar wie ich das mache.
Aber das ist doch gar nicht so einfach die ganzen Rechengesetze zu beachten. Abgesehen davon basieren die Befehle die du genannt hast (xor,nor ...) alle nur auf den drei befehlen and,or,not. Also sind es noch weniger. Ich finde aber, dass es dadurch nicht einfacher wird.

Schau mal nochmal hier! 
So ungefähr soll das Programm werden (nur ohne Diagramm)


----------



## Dario Linsky (2. September 2002)

> Ich finde aber, dass es dadurch nicht einfacher wird.


was du vorhast, ist nun mal nicht gerade einfach. ich kann dir nur sagen, dass du die logische anweisung in einzelne tokens aufteilen musst, die du dann untersuchst.
bestandteile der anweisung sind dann schlüsselwörter (not, and, or), klammern und werte. im prinzip ist das schon eine art compiler, und compilerbau ist ein nicht ganz so leichtes thema. trotzdem gehört compilerbau zu einem der am besten erforschten gebiete in der informatik und somit gibts auch einiges an lektüre zu diesem thema.


----------



## Zorck (2. September 2002)

Ja,kann ich mir echt gut vorstellen.Aber ich hatte gehofft, dass irgendwer schon ein ähnliches Programm geschrieben hat.
Naja, vielleicht meldet sich ja noch wer.


----------



## Dario Linsky (2. September 2002)

du kannst dich ja mal auf die jagd nach lektüre zu diesem thema machen. ich werd mal sehen, ob ich sowas zusammenkriege.


----------



## Zorck (2. September 2002)

Cool! Danke!
Und dann wieder in diesem Thread!?
Bis dann!


----------



## Dario Linsky (2. September 2002)

klar, aber garantieren kann ich für nichts, weil ich im moment ein paar andere dinge zu tun hab. aber grundsätzlich würd ich das mal so anfangen:

```
Private Sub btnParsen_Click()
Dim strTokens() As String
Dim i As Integer

'Eingegebenen Ausdruck zerlegen
If txtEingabe.Text <> "" Then
    strTokens() = Split(txtEingabe.Text, " ")
End If

For i = 0 To UBound(strTokens)
    If LCase(strTokens(i)) = "not" Then
        'logischen NOT-Operator gefunden
    ElseIf LCase(strTokens(i)) = "or" Then
        'logische OR-Verknüpfung gefunden
    ElseIf LCase(strTokens(i)) = "and" Then
        'logische AND-Verknüpfung gefunden
    ElseIf strTokens(i) = "(" Then
        'linke Klammer gefunden
    ElseIf strTokens(i) = ")" Then
        'rechte Klammer gefunden
    Else
        'Variable oder Wert gefunden
    End If
Next i

End Sub
```
in der schleife prüfst du jedes gefundene token auf seine bedeutung. dann kannst du später mit den fallunterscheidungen verschiedene aktionen für die gefundenen tokens durchführen. z.b. prüfen, ob ein gefundener wert in einer klammer steht oder ähnliches.
ich mach morgen mal weiter.


----------



## Zorck (3. September 2002)

Das ist au jeden Fall schon mal cool. 
Aber wäre es nicht günstiger, nicht gleich alles so klein zu zerstückeln.
Wäre es nicht günstiger die Terme die in einer Klammer stehen als einzelne Strings zu speichern und diese dann an eine Funktion zu übergeben, wo sie ausgewertet werden?
Oder wie würdest du ab dieser Stelle rangehen?

Aber auf jeden Fall schon mal Danke!
Solche  Hilfen sind echt super. Sind nen paar nette Befehle dabei, die ich nicht kannte. Echt praktisch!
Tja, Übung macht den meister!


----------



## Dario Linsky (3. September 2002)

stimmt, mir ist auch eingefallen, dass es sinnvoller wäre, erstmal teilterme auszuschneiden. das ganze könnte man z.b. als rekursive funktion laufen lassen, bis alle teilterme aufgelöst sind.
teilterme erkennt man ja daran, dass sie umklammert sind. also durchsuchst du einfach rekursiv den gesamten term nach eingeklammerten blöcken.

ausserdem ist mir an dem code noch aufgefallen, dass er zwar funktioniert, aber nicht ganz sauber läuft. z.b. wird 
	
	
	



```
not(a and b)
```
 nicht richtig aufgeteilt, weil zwischen not, der klammer und a kein leerzeichen steht. das array sieht also nachher so aus: ("not(a", "and", "b)").

alles weitere müsste ich aber auch selber ausprobieren. sieh dir doch einfach mal in der hilfe oder in einem buch die befehle zur verarbeitung von strings an.
als vorrübergehendes ziel kannst du ja eine kleine aufgabe nehmen, beispielsweise die vereinfachung von dieser anweisung: 
	
	
	



```
not (not (a and b))
```
und noch was: um das ganze zu perfektionieren kannst du natürlich auch noch eine kleine syntax-prüfung mit einbauen, indem du sicherstellst, dass zu jeder linken klammer "(" auch eine rechte klammer ")" steht.


----------



## Zorck (3. September 2002)

Den kleinen Fehler mit dem Leerzeichen hab ich auch schon mitbekommen. Aber ich denke, dass das kein so arges Problem ist.
Dann muss man halt den User daraufhinweisen.
Und wenn man dann sowieso ne Syntaxprüfung macht,kann der User ja gleich drauf hingewiesen werden.


----------



## smartguy (15. Juli 2003)

Ich bezweifle zwar, dass das Problem noch aktuell ist, aber falls doch... 

Meines Wissens nach wird es grundsetzlich so gemacht, dass man nicht den Ausdruck abklappert und versucht ihn direkt unter Verwendung von Distributivgesetz & Co zu optimieren, sondern in dem man Algorithmen wie die Verwendung von Karnaugh-Veitch-Diagrammen implementiert. So würde man das im übrigen ja auch mit Papier und Bleistift lösen, wobei man dann aber bei 10 stelligen Ausdrücken schon ziemlich viel Papier brauchen würde .


----------

