Schaltnetze, Boolesche Algebra, Crashkurs. Kann mir jemand helfen?
Hallo!
Ich lerne gerade crashkursmäßig Schaltnetze und habe versucht, folgende Aufgabe aus meinen Altklausuren zu lösen:
Gegeben sei ein unvollständiger Ausdruck Phi = a <- c v b ^ ¬a
a) Geben Sie für Phi einen vollständig geklammerten booleschen Ausdruck an, der nur die Elementaroperatoren ¬, ^ und v enthält.
b) Geben Sie die Wahrheitstabelle für die booleschen Funktion an, die durch Phi definiert sind.
c) Angenommen man würde den vollständig geklammerten booleschen Ausdruck aus a) als Schaltnetz realisieren und dabei nur AND-Gatter und OR-Gatter mit zwei Eingängen und Inverter mit einem eingang verwenden. Welche Kosten und Tiefe hätte dieses Schaltnetz? (Eine Zeichnung ist zwar hilfreich aber nicht unbedingt erforderlich).
Meine Ideen:
a) Zuallererst habe ich das Ganze umgestellt, sodass da steht:
Phi = ¬a ^ b v c -> a
Danach habe ich das Ganze nach Operatorenrangfolgen eingeklammert:
Phi = ((¬a ^ b) v c) -> a
Und zum Schluss die Folgerung auf a mit und / oder umgeschrieben:
Phi = ((¬a ^ b) v c) ^ a v ¬((¬a ^ b) v c) ^ (a v ¬a)
Habe das Ganze via Wahrheitstabelle überprüft und es scheint zu passen.
b) Spare ich mir hier, da das nur endlose Schreibarbeit ist und ich weiß, wie das geht.
c)
Daran knoble ich gerade. Ich weiß nicht, wie ich Kosten und Tiefe berechnen soll. Ich weiß nur, dass die Tiefe die Länge des längsten weges ist, aber ich weiß nicht so wirklich, was alles zu diesem Weg dazugehört. Ich habe auch einmal probeweise ein Schaltnetz gezeichnet, welches ich angehängt habe.
Kann mir jemand bei dieser Aufgabe weiterhelfen, eventuell überprüfen ob ich soweit alles richtig gemacht hab und wo, wenn meine Fehler waren?
Liebe Grüße! Arkaine
1 Antwort
Also wenn ich mich nicht irre, kann man den Ausdruck besser anders zusammenfassen:
Folgerung auflösen:
-(c v (-a^ b)) v a
Dann die Negation reinziehen:
(-c ^ -(-a ^ b)) v a
(-c ^ (a v -b)) v a
Das ist äquivalent zu: a v (-c ^ -b) (Wahrheitstabelle als Beweis, lässt sich aber auch über Umformungen zeigen)