Okay, dann heiße ich Sie herzlich willkommen bei der heutigen zweiten
Übung zu Digitaltechnik.
Wieder in Vertretung von Professor Asfur, der heute leider ein sehr
wichtiges Meeting hat an der Fakultät.
Deswegen werde ich ihn heute hier vertreten.
Und in dieser zweiten Übung geht es um bulsche Algebren, um die
Darstellung von bulschen Funktionen und dann entsprechend auch um die
sogenannten Normalformen, die Sie ja schon aus der Vorlesung kennen.
Nämlich genauer die disjunktive und die konjunktive Normalform.
Und wir werden uns heute nochmal anschauen, mit welchen
unterschiedlichen Techniken wir diese Normalformen von beliebigen
bulschen Funktionen bestimmen können.
Hier sind es im Wesentlichen drei verschiedene Verfahren, die ich
Ihnen dann auch entsprechend mit Übungsaufgaben hier zeigen werde.
Und wenn Sie sich mal das Übungsblatt anschauen, also vor allem das
von nächster Woche, das Sie jetzt natürlich noch nicht anschauen
können, dann werden Sie feststellen, dass das eben auch der
Schwerpunkt des Übungsblatts ist.
Hier nochmal zur Erinnerung, diese Übersichtsfolie über die bulschen
Algebren, wie die zusammenhängen.
Ich hatte Ihnen ja schon genau diese Folie hier in der Vorlesung
gezeigt.
Ich glaube, das war genau heute vor 14 Tagen hier an diesem Ort.
Und hier nochmal wichtig, also bulsche Algebra ist zunächst mal nur
ein Konstrukt, was definiert ist durch die Huntington'schen Axiome,
die wir eben vorgeben.
Und zusätzlich zum Beispiel noch die Abgeschlossenheit, also dieses
nullte Huntington'sche Axiom.
Und davon ausgehend können wir dann verschiedene reale Algebren uns
suchen, die eben diese geforderten Eigenschaften einer
Huntington'schen Algebra erfüllen.
Zum Beispiel die Mengenalgebra mit den Operationen eben Schnitt und
Vereinigung und auch die Aussagenlogik mit der Menge eben falsch und
wahr.
Oder ganz wichtig eben die Schaltalgebra und die Schaltalgebra ist
natürlich die bulsche Algebra, die hier für uns im Rahmen der
Digitaltechnik besonders interessant ist.
Nochmal als Wiederholung, das kennen Sie schon, also hier oben die
Abgeschlossenheit, Kommutativgesetz, Distributivgesetz und hier die
neutralen Elemente und die inversen Elemente.
Das sind die Huntington'schen Axiome.
Sollten Sie alle kennen, werden wir jetzt auch in dieser Übung sehr
viel verwenden, wenn wir eben damit rechnen.
Und auf der nächsten Folie sehen Sie noch ein paar abgeleitete
Gesetze.
Das sind also Gesetze, die müssen wir nicht als Axiomen vorgeben,
sondern die können wir unter den Axiomen, die wir schon haben, einfach
ableiten und beweisen.
Ich werde Ihnen hier keine Beweise heute mehr zeigen, aber das wurde
in der Vorlesung schon gezeigt, also zumindest die demorganschen
Gesetze, die habe ich hier direkt bewiesen vor 14 Tagen und ich
glaube, die Idempotenzgesetze, die werde ich Ihnen jetzt gleich noch
beweisen.
Doch zunächst nochmal das Dualitätsprinzip.
Wenn Sie sich die Konstruktion der Buchenalgebra anschauen, dann
werden Sie feststellen, dass das alles symmetrisch ist und das führt
genau zu diesem Dualitätsprinzip.
Das heißt, Sie können, klar, wenn Sie Literale haben, lassen Sie die
Literale so stehen, wie sie sind und Sie können 0 und 1 ersetzen und
Disjunktion und Konjunktion vertauschen und wenn Sie diese beiden
Vertauschungen durchführen, dann erhalten Sie die sogenannte duale
Aussage.
Und diese duale Aussage hat den gleichen Wahrheitswert wie der
ursprüngliche Term.
Das heißt, Sie können hier, indem Sie die Huntington'schen Axiomen
nehmen und das Dualitätsprinzip anwenden, duale Aussagen gewinnen, die
ebenfalls gültig sind, die also ebenfalls direkt aus den Axiomen
folgen.
Jetzt werde ich Ihnen die beiden Idempotenzgesetze beweisen.
Wenn Sie sich das mal anschauen, streng genommen muss ich Ihnen nur
eins beweisen.
Das andere Idempotenzgesetz folgt dann ja direkt mit dem
Dualitätsprinzip, was ich Ihnen gerade eben gezeigt habe.
Das heißt, Sie ersetzen einfach die Konjunktion durch eine Disjunktion
oder umgekehrt, je nachdem, welches Sie bewiesen haben und dann folgt
das eine direkt aus dem anderen.
Also, wir wollen zeigen A und A.
Und das soll A sein.
Gut, das ist die erste Aufgabe.
Vielleicht rechne ich die einfach mal vor.
Bei der nächsten Aufgabe wird es dann ein bisschen mehr
Interaktionsmöglichkeit geben.
Wir fangen an mit dem neutralen Element.
Das heißt,
wir disjungieren das Ganze einfach mit unserem neutralen Element, mit
dem Null-Element hier an der Stelle.
Also irgendwas oder Null ist immer irgendwas, dafür ändert sich
nichts.
Jetzt wenden wir unser inverses Element an und ersetzen unser Null
-Element durch A und Nicht-A.
A und Nicht-A ist immer Null.
Und als nächstes kommt nun das Distributivgesetz zum Einsatz.
Und mit diesem Distributivgesetz werden wir jetzt A ausklammern.
Das Radiergummi funktioniert nicht so ganz.
A und A oder Nicht-A.
Sie sehen, was ich gemacht habe.
Ich habe einfach A ausgeklammert.
Und Sie sehen womöglich schon, worauf es hinausläuft.
Weil A oder Nicht-A ist ja immer 1.
Ist immer unser 1-Element.
Und irgendwas konjugiert mit dem 1-Element ist immer irgendwas.
Das heißt, hier bleibt A übrig.
Und wie gesagt, mit dem Dualitätsprinzip.
Ich kann das hier mal noch drüber schreiben.
Also jede Null wird durch eine 1 ersetzt und umgekehrt.
Und jede Disjunktion wird durch eine Konjunktion ersetzt.
Und Sie sehen, das ist echt hier ein No-Brainer.
Da kann ich einfach durchgehen und das überall eintragen.
Und dann habe ich hier am Ende steht eben A oder Null.
Und das ist auch wieder entsprechend dem neutralen Element eben
einfach A.
Soweit Fragen dazu.
Also Übung bei mir ist immer interaktiv.
Das heißt, wenn Sie irgendwie eine Frage haben, wenn Sie was nicht
verstehen, dann fragen Sie bitte.
Weil Sie können davon ausgehen, dass Sie nicht der Einzige sind, der
etwas nicht versteht.
Gerade wenn es vielleicht eine etwas schwierigere Stelle ist.
Aber hier haben wir jetzt ja nur Axiome angewendet.
So, Sie sehen, ich habe das hier nochmal zusammengefasst auf den
Folien.
Es kam auch letztes Mal das Feedback, dass meine Schrift womöglich
nicht immer so super lesbar ist.
Aber ich denke, bei dieser Schrift hier gibt es nun keine Ausreden
mehr, dass man es nicht lesen kann.
Aufgabe 2.
Wir wollen diese Behauptung beweisen.
Also, es ist auch eine ehemalige Übungsaufgabe von dem Übungsblatt.
Die wird natürlich jetzt auf dem Übungsblatt nicht mehr drankommen.
Also da müssen Sie sich keine Hoffnung machen.
Aber ähnliche Aufgaben können natürlich immer drankommen, auch in der
Klausur.
Und auch hier gibt es wieder ganz viele Wege, wie wir das beweisen
können.
Ein möglicher Weg ist, wir fangen einfach mal an.
Wir schreiben mal B hin.
Und jetzt formen wir B so um, dass wir irgendwann C rauskriegen.
Dann haben wir gezeigt, dass B gleich C ist.
Und damit das klappt, müssen wir natürlich unsere Voraussetzungen,
also das, was auf der linken Seite der Implikation steht, irgendwie
verwenden.
Fangen wir einfach mal an mit dem Absorptionsgesetz.
Das Absorptionsgesetz kennen Sie, das war gerade auf der Folie.
Ich kann es Ihnen aber auch nochmal hinschreiben.
Das Absorptionsgesetz besagt, X ist X oder Y und X.
Und ja natürlich auch umgekehrt, also X und Y oder X.
Und wenn man sich das mal anschaulich anschaut, das ist vielleicht das
Gesetz, also ich finde vielleicht das Gesetz, was am wenigsten
anschaulich ist von diesen Gesetzen.
Also sowas wie Kommutativgesetz kann man sich dann doch leichter
vorstellen.
Aber im Grunde ist auch das nicht schwer zu verstehen.
Also Sie fordern, es muss gelten X oder Y und es muss aber auch gelten
X.
Wenn also sowieso gelten muss X, dann ist X oder Y sowieso immer
erfüllt.
Und deswegen können Sie dieses X oder Y weglassen.
So kann man sich das vielleicht in einem Satz einfach ganz einfach
klar machen.
Und also hier wird das, ich mache vielleicht mal hier ein Sternchen
hin.
Jetzt geht es weiter.
Kommutativgesetz, klar, nichts besonderes.
Und jetzt können wir unsere Voraussetzungen verwenden.
Wir wissen also gemäß der Voraussetzung, A oder B ist gleich A oder C.
Und dann kommt das Distributivgesetz zum Einsatz.
Das Distributivgesetz, das ist H2, B
und C.
Kommutativgesetz.
Und was machen wir jetzt als nächstes?
Also wenn ich schon zur Frage komme, wahrscheinlich nochmal die
Voraussetzung zum Einsatz.
Denn wir haben ja hier in der Voraussetzung zwei Voraussetzungen
gegeben.
Und das ist natürlich bei so Aufgaben gibt es manchmal natürlich die
Falle, dass sie was gegeben haben, was sie gar nicht brauchen.
Aber im Normalfall wird natürlich jede Voraussetzung auch irgendwo mal
verwendet.
Das heißt, jetzt kommt wieder die Voraussetzung zum Einsatz.
Dann haben wir hier eben A und B wird ersetzt durch A und C.
Und nochmal das Distributivgesetz.
Wir klammern wieder aus quasi.
Und jetzt sehen Sie wahrscheinlich schon worauf es hinausläuft.
Denn jetzt ersetzen wir das letzte B durch ein C.
Und jetzt kommt wieder unser Absorptionsgesetz zum Einsatz.
Und dann steht da noch ein C.
Okay.
Ist vielleicht ein etwas komplizierterer Beweis, aber ich denke sehr
gut trotzdem nachzuvollziehen.
Also eigentlich nicht schwer darauf zu kommen, wenn man sich anschaut,
dass man diese beiden Voraussetzungen benutzen muss.
Und damit komme ich jetzt schon zum zweiten Teil der Übung.
Wir haben uns jetzt ja nur allgemein mit schaltalgebraischen Termen
beschäftigt.
Und jetzt werden wir uns im Speziellen mit Funktionen beschäftigen.
Und die Funktion ist natürlich elementar, wenn es dann später darum
geht Schaltnetze zu konstruieren.
Und ein Beispiel, wie ein Schaltnetz aus einer sehr High-Level
-Perspektive aussieht, das haben Sie schon hier.
Sie haben also hier diesen Block.
Das ist Ihre Funktion oder Ihr Schaltnetz.
Und das hat eine Menge von Eingängen.
In dem Fall hier n Eingänge, also von 0 bis n-1 und einen Ausgang.
Wir beschäftigen uns also hier mit binären Funktionen.
Das heißt, die Funktion hat nur einen Ausgang und dieser Ausgang ist
eben ein logischer Wert, also entweder eine 0 oder eine 1.
Natürlich werden Sie dann später auch Schaltnetze konstruieren, die
mehr als einen Ausgang haben.
Dann können Sie aber immer diese Ausgänge jeweils unabhängig
voneinander als Schaltfunktion beschreiben.
Und dann hat Ihr Schaltnetz eben, wenn es drei Ausgänge hat, sind es
eben drei Funktionen, die Sie verwenden, um dieses Schaltnetz zu
beschreiben.
Ich denke hier, das ist alles klar.
Wichtig ist noch hier die Kombinatorik.
Wenn Sie n Eingangsvariablen haben, dann können Sie sich mal
überlegen, wie viele Funktionen wir realisieren können.
Wenn wir also n Eingangsvariablen haben, dann haben wir 2 hoch n
mögliche Kombinationen, wie wir diese Eingangsvariablen beschalten
können.
Und für jede dieser Kombinationen, was wir als Eingabe reingeben
können, das sind also quasi die Zeilen Ihrer Wahrheitstabelle, haben
wir dann die Möglichkeit, entweder eine 0 oder eine 1 auszugeben.
Das heißt, wir haben hier 2 hoch 2 hoch n mögliche Funktionen, die
sich alle unterscheiden, also die alle in Ihrer Wahrheitstabelle
irgendwo einen Unterschied haben in der Ausgabe bei irgendeiner
Eingabe.
Das zeigt natürlich, wie hochdimensional dieses Problem eigentlich
ist.
Wenn Sie sich das jetzt überlegen, Sie haben 5 Eingänge, 2 hoch 2 hoch
5, 2 hoch 5 ist 32, 2 hoch 32, da sehen Sie schon, in welcher
Größenordnung wir dann hier sind.
Das ist 4 Milliarden irgendwas, 2 hoch 32.
Da können Sie nicht mal eben so schnell dann den Funktionen alle noch
einen schönen Namen geben oder sowas.
Damit wir uns dem Problem ein bisschen nähern können, betrachten wir
jetzt nur zweistellige Budget-Funktionen.
Das heißt, die Funktionen haben nur 2 Eingänge.
Das sind also die klassischen zweistelligen Funktionen, die Sie schon
kennen.
Werden Sie auch gleich wieder sehen, die zweistellige Disjunktion, die
zweistellige Konjunktion und noch ein paar andere.
Denn es gibt ja 2 hoch 2 hoch 2, also 2 hoch 4, das sind also 16
Funktionen und die wurden in der Vorlesung auch schon gezeigt.
Werde ich Ihnen nochmal zeigen jetzt hier.
Also vielleicht nochmal schematisch, wie sieht das aus?
Wir haben also hier unsere möglichen Eingaben
und hierneben haben wir die möglichen Funktionswerte.
Und Ihre Funktion ist jetzt dadurch definiert, dass Sie jeder
möglichen Eingabebelegung
einen Funktionswert zuordnen.
Zumindest, wenn Sie eine vollständig definierte Funktion haben.
Sie sehen, man kann das auch noch komplizierter machen.
Wir werden auch später unvollständig definierte Funktionen betrachten.
Da gibt es dann sogenannte Don't-Care-Stellen.
Da möchte ich allerdings nicht vorgreifen.
Jetzt schauen wir uns mal eine Funktion an, irgendeine.
Zum Beispiel nehmen wir die Nend-Funktion.
Und wann ist die Nend-Funktion 1?
Also Frage an Sie, wann ist die Nend-Funktion 1?
Ja?
Genau, solange nicht beide Eingaben wahr sind.
Das heißt, wenn
beide Eingaben wahr sind, dann ist die Nend-Funktion 0.
Das wäre jetzt ein Beispiel, das wäre die Nend-Funktion.
Und hier sehen Sie jetzt die Liste, die kennen Sie ja schon aus der
Vorlesung.
Und was mich ein bisschen ärgert, ist, dass hier oben bei der Null
-Funktion nichts steht.
Also das hier ist die Null-Funktion oder auch genannt Kontradiktion.
Und Sie sehen, jede von diesen Funktionen hat einen Namen.
Manche sind vielleicht ein bisschen wichtiger als andere in dem Sinne,
dass Sie den Operator häufiger verwenden werden.
Und ganz wichtig eben hier, Sie sehen hier die NOR-Funktion und Sie
sehen auch die Nend-Funktion.
Die sind also jeweils, das wurde ja auch schon gezeigt, die jeweils
nur mit Nend oder nur mit NOR ein vollständiges Operatoren-System
aufspannen können.
Das heißt, nur mit Nend können Sie jede beliebige Funktion darstellen.
Ansonsten haben Sie hier auch die Funktionen, die Sie kennen.
Also hier ist die Disjunktion zum Beispiel, hier oben ist auch die
Konjunktion und hierneben sehen Sie immer die Wahrheitstabelle.
Also hier sehen Sie für alle vier möglichen Eingabebelegungen, sehen
Sie die Ausgabe.
Hier unten ist die Nend, also das, was wir gerade eingezeichnet haben.
Und hier sehen Sie immer noch die symbolische Darstellung.
Ist natürlich auch wichtig, wenn Sie jetzt irgendwo so ein Zeichen
sehen, zum Beispiel hier die Antivalenz, vielleicht besser bekannt als
exklusives Oder, also XOR.
Wenn Sie das irgendwo sehen, das Zeichen, dann müssen Sie natürlich
wissen, um was für eine Funktion es sich dabei handelt.
Und eine Sache ist noch ganz wichtig, auf die möchte ich Sie noch
hinweisen.
Und zwar betrifft das die Nend und die NOR und natürlich auch noch
andere.
Wir haben jetzt nur die zweistelligen Funktionen betrachtet.
Achtung, dreistellig.
So, schauen wir uns mal zum Beispiel ein dreistelliges Nend an.
Also Nend 3 von X2, X1 und X0.
Das ist ja dann X2 und X1 und X0 negiert.
Und das ist was ganz anderes, als X2 nennt X1 nennt X0.
Also, es ist hier ganz essentiell, dass Sie nicht hingehen und so ein
dreistelliges Nend-Gatter oder auch ein endstelliges Nend-Gatter dann
einfach reduzieren auf die zweistellige Nend-Funktion.
Das ist nicht äquivalent.
Es gibt natürlich Funktionen, bei denen es äquivalent ist, zum
Beispiel eine Konjunktion.
Wenn Sie sagen A und B und C, dann ist das eben äquivalent zu A und B
und C.
Das können Sie machen, Sie können es bei der Disjunktion, funktioniert
es auch.
Aber es funktioniert nicht bei jeder Funktion und da müssen Sie
ziemlich aufpassen.
Also wenn es einen Fehler gibt, der vielleicht auf den Übungsblättern
und in der Klausur auch am häufigsten gemacht wird bei Schalteigebra,
dann würde ich sagen, ist es vermutlich dieser Fehler.
Deswegen an der Stelle nochmal der Hinweis.
Genau.
Dann kommen wir jetzt zu den Normalformen und wir werden uns in
Zukunft zusätzlich zu den Normalformen auch noch mit den sogenannten
Minimalformen beschäftigen.
Das ist allerdings ein Thema, was ich heute nicht anschneiden werde.
Das wird in der Vorlesung noch sehr viel ausführlicher kommen.
Diese Normalformen, die erlauben uns eine normalisierte Darstellung
der Funktion.
Das heißt, wir können die Funktion in einer Weise darstellen, dass wir
zwei Funktionen zum Beispiel vergleichen können anhand ihrer
Normalformen und sofort sagen können, diese Funktion ist identisch
oder diese Funktion ist unterschiedlich.
Letztendlich das Gleiche, was wir auch machen würden mit einer
Wertetabelle.
Mit der Wertetabelle geht es natürlich auch, nur dass die Wertetabelle
ungleich viel mehr Aufwand ist, einfach um sie hinzuschreiben.
Letztendlich ist die Darstellung eigentlich äquivalent.
Abgesehen natürlich von der Reihenfolge der Terme.
Wir sehen also in der Normalform, hier in der disjunktiven Normalform
zum Beispiel, Sie haben Min-Terme, die werden disjungiert und die
Reihenfolge dieser Min-Terme, die ist mehr oder weniger beliebig.
Normalerweise werden Sie das schon irgendwie sortieren, einfach nach
der Nummer des Min-Termes aufsteigend.
Das ist allerdings nicht unbedingt Pflicht.
Das heißt, die Reihenfolge kann ein bisschen abweichen.
Aber die Terme, die da stehen, sind immer die gleichen.
Und das werden wir uns jetzt am Beispiel anschauen.
Hier steht es auch schon.
Ich schreibe es vielleicht doch nochmal dazu.
Wir haben jetzt hier eine Funktion gegeben, in schaltalgebraischer
Form.
Und von dieser Funktion wollen wir jetzt die disjunktive und die
konjunktive Normalform angeben.
Und jetzt haben wir verschiedene Arten, wie wir das machen könnten.
Eine Möglichkeit wäre zum Beispiel eine Wertetabelle.
In dem Fall machen wir es mal schaltalgebraisch.
Das heißt, wir versuchen einfach mithilfe der Gesetze der
Schaltalgebra, die wir ja schon kennen, die wir ja auch jetzt vorhin
schon verwendet haben, diese Funktion so umzuformen, dass am Ende hier
eine disjunktive Normalform steht.
Und in dem Fall werde ich jetzt einfach mal hier zum Beispiel das
inverse Element einfügen.
Das heißt, ich schreibe hier einfach mal rein c oder nicht c.
Das ist ja immer 1.
Das heißt, das kann ich da einfach einfügen.
Oder, und hier schreibe ich dazu b oder nicht b, a oder nicht a, ist
auch beides immer 1, kann ich also einfügen.
Sie sehen schon, was die Idee ist hierhinter.
Die Idee ist, dass wir letztendlich in jedem Term hinterher jede
Variable drin haben, denn das brauchen wir für unsere Normalform.
Und jetzt sind wir eigentlich schon fast fertig.
Jetzt müssen wir nur noch das Distributivgesetz anwenden.
Dann haben wir hier also a, nicht b, c oder a, nicht b, nicht c oder
c, b, a oder c, b, nicht a oder c, nicht b, a oder c, nicht b, nicht
a.
Wie geht es weiter?
Wir müssen die Terme ein bisschen umsortieren.
Die Umsortierung ist optional, aber wir müssen vor allem schauen, dass
wir kein Doppelt haben.
Und hier empfiehlt es sich, die Terme so zu sortieren, dass wir sie
nach der Nummer sortieren.
Das heißt, das werde ich Ihnen gleich noch zeigen, wenn Sie das noch
nicht mitbekommen haben in der Vorlesung.
Wir sollten eine eindeutige Variablenreihenfolge verwenden.
Ich werde jetzt hier einfach mal c, b, a verwenden.
Das kann man vielleicht auch hier nochmal kenntlich machen.
Wenn Sie also hier sowas gegeben haben in der Aufgabenstellung, dass
da steht f von c, b, a, dann bedeutet das, dass Ihre
Variablenreihenfolge immer c, b, a ist.
Und das ist wichtig für die Nummerierung der MINTERME.
Das werden wir jetzt gleich noch sehen.
Das heißt, hier haben wir unseren MINTERME 1.
Das ist also der zweite hier, der hier.
Sie sehen es mit der Maus, das ist eigentlich ziemlich gut als Zeiger.
Und dann, was haben wir noch?
Wir haben den Vierer, c nicht b nicht a.
Wir haben den Fünfer und wir haben auch den Sechser und den Siebener.
Und jetzt können wir das noch explizit hinschreiben.
Das ist diese MINTERM-Darstellung.
Das ist dann eben MINTERM 1, 4, 5, 6 und 7.
Und hier sehen Sie, wir haben einfach die TERME als Binärzahl
interpretiert, mehr oder weniger.
Also hier haben wir nur die eine Stelle, also es ist eine 1.
Vierer Stelle 4, 4 plus 1 ist 5.
Und der Vorteil ist natürlich, hier zum einen ist es eine sehr
kompakte Art, die Funktion darzustellen.
Das ist also wirklich eindeutig hier.
Sie können jetzt also sagen, das ist genau die Funktion mit drei
Eingängen, die dreistellige Funktion, diese hier.
Und damit ist die Funktion eindeutig bestimmt.
Sie brauchen jetzt nicht noch die Konjunktiven Normalform zum
Beispiel, um die Funktion eindeutig zu bestimmen.
Sie brauchen nur eine Normalform.
Und die Konjunktive ist natürlich eine Alternative, die schauen wir
uns als nächstes an.
Und diese MINTERME, die sagen, das sind genau die fünf Belegungen, bei
denen die Funktion 1 ist.
Es gibt also acht mögliche Belegungen, wenn wir drei Eingänge haben.
Und das sind die fünf Belegungen, bei denen unsere Funktion 1 ist.
Und bei den anderen drei Belegungen, da es eine vollständig definierte
Funktion ist, ist die Funktion dann entsprechend 0.
Jetzt schauen wir uns noch die KNF an.
Ja,
das ist also mehr als enttäuschend.
Unser Präsenter hat schon wieder den Geist aufgegeben.
Ja, jetzt geht er wieder.
Okay, mal sehen, wie lange er durchhält.
Sie sehen, das ist auch ein Problem.
Die Lösung steht jetzt schon hier.
Es hat einfach den Hintergrund, dass es nicht funktioniert, dass ich
was schreibe und danach noch eine Animation mache und es erst danach
einblende.
Ich zeige Ihnen trotzdem noch, wie die Rechnung aussieht.
Also, das war ja unsere Funktion.
Und jetzt machen wir genau das gleiche wieder, nur dass wir jetzt
entsprechend umformen zu einer konjunktiven Form.
Vielleicht machen wir noch einen Schritt vorher.
Wir fangen also an mit einer konjunktiven Form.
Wir formen das Ganze um auf eine konjunktive Form.
Wie machen wir das?
Wir wenden einfach unser Distributivgesetz an.
Jetzt haben wir das Distributivgesetz angewendet und jetzt können wir
diese konjunktive Form erweitern.
Dann haben wir hier also A oder C oder B und Nicht-B.
Das ist immer Null, können wir ergänzen.
Und B, Nicht-B oder C oder A und Nicht-A.
Und jetzt kommt wieder unser Distributivgesetz zum Einsatz.
A oder C oder Nicht-B.
Und wieder müssen wir schauen, haben wir irgendwelche Terme doppelt.
Man sieht schnell hier, der zweite und der dritte Term, die sind
identisch.
Und dann formen wir es wieder so, um dass unser C vorne steht.
Okay, was stellen wir fest?
Also zunächst mal, klar, es stimmt überein mit dem, was hier unten
steht.
Wichtige Feststellung, die Max-Terme sind genau die Belegungen, die
unsere Min-Terme nicht sind.
Also ist logisch, weil die Min-Terme sind die Einstellen der Funktion
und die Max-Terme sind die Nullstellen der Funktion.
Die Funktion kann aber bei der gleichen Belegung nicht Null und Eins
sein.
Das heißt, entweder eine Belegung ist ein Null- oder eine Einstelle.
Und da die Funktion vollständig definiert ist, ist auch jede Belegung
genau entweder eine Nullstelle oder eine Einstelle.
Das heißt, wenn wir fünf Min-Terme hatten und die Funktion hat eben
acht mögliche Belegungen, dann muss es genau drei Max-Terme geben.
Wenn es nicht der Fall wäre, wenn Sie jetzt hier zwei Max-Terme raus
hätten oder vier, dann wissen Sie, dass Sie irgendwas falsch gemacht
haben.
Also zwei Max-Terme könnte noch sein, wenn die Funktion unvollständig
definiert ist.
Aber wenn Sie hier vier Max-Terme rauskriegen, haben Sie definitiv
irgendwo sich verrechnet.
Das können Sie also auch schnell verwenden in Aufgaben, um zu prüfen,
ob das plausibel ist, was Sie hier rauskriegen.
Und jetzt schauen wir uns noch an, wie man das Ganze realisieren kann.
Sie sind ja hier in der Vorlesung zur Digitaltechnik.
Das heißt, wir beschäftigen uns hier auch immer dann mit der Umsetzung
von dem Ganzen im Rahmen von digitalen Schaltungen.
Und gegeben, wir haben diese disjunktive Normalform, die ist also
zweistufig.
Das heißt, hier innen drin haben Sie Konjunktionen, das sind Ihre
sogenannten Min-Terme.
Und diese Min-Terme, die werden dann disjungiert.
Und das, was ich Ihnen jetzt hier zeige, das gilt genauso auch für
disjunktive Minimalformen.
Das Prinzip ist das gleiche.
Und wir haben sie also dann hier.
Hier haben Sie Ihre Min-Terme, die Sie zusammenbauen.
Und dann haben Sie hier x0 bis xn-1.
Und diese Min-Terme, die müssen Sie dann disjunktiv verknüpfen.
Und ich kann sie auch noch beschriften.
Hier haben Sie also k0, k1,
kk.
Und heraus kommt dann Ihr y.
Das Ganze ist zweistufig.
Also hier,
erste Stufe, nehmen Sie die zweite Stufe.
Schauen wir uns das noch für die konjunktive Normalform an.
Auch wenn es wahrscheinlich langweilig ist für Sie.
Sollte man schon der Vollständigkeit aber auch zeigen.
Hier haben wir eben hier vorne unsere Max-Terme, die werden
disjungiert.
Und dann ist hier die Konjunktion.
Klar, es ist eine konjunktive Normalform.
Und heraus kommt y.
Und hier haben wir auch, hier ist d0, d1 und hier dk.
Und auch hier haben wir wieder einen zweistufigen Aufbau.
Soweit irgendwelche Fragen?
So, jetzt habe ich Ihnen gezeigt, wie wir die disjunktive Normalform
erhalten können.
Jetzt würde ich Ihnen dann gerne zeigen, wie wir das systematisch
machen können.
Allerdings, glaube ich, machen wir zuerst die 5 Minuten Pause.
Das heißt, in 5 Minuten geht es dann hier an dieser Stelle weiter.
Okay, dann machen wir mal weiter.
Ich habe Ihnen ja schon angekündigt, worum es jetzt geht.
Ich werde Ihnen also jetzt zeigen, wie Sie systematisch jede Funktion,
die Sie irgendwie schaltalgebraisch gegeben haben, in Ihre konjunktive
oder auch Ihre disjunktive Normalform überführen können.
Ohne, dass Sie irgendwie mit scharfem Hinsehen die richtigen
Rechenregeln anwenden müssen, sondern systematisch.
Und das funktioniert mit dem Schengenischen Entwicklungssatz.
Der Schengenische Entwicklungssatz, Sie haben ja im Sommersemester
schon R.O.
gehört.
Das heißt, wenn ich Ihnen jetzt sage, es handelt sich um ein
Multiplexer, dann wissen Sie hoffentlich ungefähr, welches Bauteil ich
meine.
Und der Schengenische Entwicklungssatz ist genau die Realisierung
eines Multiplexers.
So, und hier unten sehen Sie, wie das Ganze funktioniert.
Wir haben also eine Funktion, und die Funktion hängt von n Variablen
ab, von x1 bis xn.
Und wir wollen die Funktion entwickeln, in dem Fall nach der Variable
xi.
Und das funktioniert so, das ist die disjunktive Variante des
Schengenischen Entwicklungssatzes.
Wir nehmen an, diese Variable, nach der wir entwickeln wollen, die
wäre 1.
Und konjugieren das Ganze mit dieser Variablen.
Und dann disjunktieren wir das Ganze unter der Annahme, dass es 0 ist.
Also wir machen quasi eine Fallunterscheidung.
Das ist das, was wir hier machen.
Und wenn Sie jetzt fragen, wie uns das dann zu der Normalform bringt,
dann müssen wir das natürlich mehrmals machen.
Wir müssen also nach jeder Variablen, die vorkommt, entwickeln.
Und dann müssen wir das Ganze wieder ein bisschen vereinfachen und
zusammenfassen.
Und dann steht unsere Normalform fertig da, und wir müssen nichts mehr
machen.
Schauen wir uns das ein Beispiel an.
Ich habe dieses Beispiel, die Lösung, komplett auf den Folien.
Weil Sie können sich vorstellen, dass man da relativ viel schreiben
muss.
Das werden Sie auf dem Übungsblatt auch noch merken.
Und das ist einfach zeitlich.
Wenn ich Ihnen das jetzt alles hinschreibe, dann braucht das zu lange.
Wir haben jetzt also hier die Funktion.
Und wir wollen diese Funktion schrittweise entwickeln mit dem Shannon
-Entwicklungssatz.
Und die jeweils gefundenen Restfunktionen mit den folgenden Regeln
vereinfachen.
Nämlich mit diesen Regeln, also Idem-Potenz-Gesetz und die
Rechenregeln mit Konstanten.
Und hier haben Sie nochmal den Shannon-Entwicklungssatz.
Und jetzt fangen wir mal an.
Wir entwickeln zunächst nach A.
Das heißt, wir nehmen an, A ist 1 und ersetzen jedes Vorkommen von A
in diesem Term durch eine 1.
Oder A ist 0 und ersetzen jedes Vorkommen von A in diesem Term durch
eine 0.
Das haben wir gemacht.
Und dann wenden wir die Rechenregeln an, die Sie eben gesehen haben.
Also Sie könnten jetzt natürlich auf viele Arten weiterrechnen.
Aber wenn Sie sich an diese Rechenregeln halten und keine anderen
Regeln verwenden, dann funktioniert das Verfahren immer.
Dann können Sie nichts falsch machen.
Und zum Beispiel dieses 1 oder B ist immer 1.
Fällt also weg.
Dieser komplette Term, der fällt weg.
Jetzt die Frage, ob ich das reinschreiben soll.
Vielleicht schreibe ich es mal kurz rein.
Also dieser Term ist immer 1.
Über den nächsten Term können wir nichts aussagen.
Hier hinten, das ist immer B.
Und 0 oder B ist auch immer B.
Und 0B ist immer 0.
Das haben wir eingesetzt.
Dann kommt das hier raus.
Jetzt geht es weiter.
Jetzt entwickeln wir nach B.
Wir setzen also ein B gleich 1.
Hier wird B durch 1 ersetzt.
Und hier setzen wir ein B gleich 0.
Na gut, das ist nur der erste Teil.
Also hier oben, das hier, haben wir jetzt B gleich 0 eingesetzt.
Und jetzt geht es noch weiter.
Und hier setzen wir ein B gleich 1 und B gleich 0.
Dann haben wir das hier.
Jetzt wenden wir wieder unsere Rechenregeln an.
Und Sie sehen diese Terme mit 1.
Irgendwas oder 1 ist immer 1.
Fällt also weg, wegen neutralem Element.
Und jetzt sind wir hier.
Und wir entwickeln wieder.
Jetzt nach A und nach B haben wir entwickelt.
Und Sie sehen schon, woraus es hinausläuft.
Wir haben also hier jetzt schon die Terme sortiert.
Nach den Termen, wo A und B 1 sind.
Nach den Termen, wo A 1 ist und B 0.
Nach den Termen, wo A 0 ist und B 1.
Und nach den Termen, wo beide 0 sind.
Und das ist genau das, was wir für die disjunktive Normalform am Ende
brauchen.
Nur brauchen wir es eben für alle 4 Variablen.
Deswegen entwickeln wir jetzt auch noch nach C.
Und ich glaube, das Prinzip ist klar.
Wir setzen jetzt eben ein C ist 1 und C ist 0.
Und jetzt haben wir das Ganze aufgesplittet.
Das hätte man vielleicht die nächste Zeile machen sollen, dass es noch
ein bisschen übersichtlicher ist.
Jetzt haben wir das Ganze aufgesplittet nach A, B und C.
Und
jetzt sind wir im Prinzip fertig.
Also Sie sehen, wenn wir hier alles rausstreichen, dann bleibt sowas
übrig.
Und jetzt können wir einfach hingehen und sagen, die Terme, wo 0 drin
vorkommt, die sind 0, die sind sowieso weg.
Können wir rausstreichen.
Die 1, die vorkommen, können wir auch rausstreichen.
Das ist die hier.
Und die 1 müssen wir ersetzen.
Ich sehe nur gerade, ich darf hier gar nicht hinschreiben.
Da kommt nämlich noch eine Animation.
Und Sie sehen, die 1 ist D oder nicht D.
Und jetzt haben Sie die disjunktive Normalform.
Also, viel Schreibarbeit, aber komplett Schema F.
Und natürlich, je mehr Variablen Sie haben, desto mehr Aufwand ist
dieses Verfahren.
Ist ja auch irgendwie logisch.
Wenn Sie also dann sehr hochkomplexe Funktionen haben und Sie
entwickeln irgendwie eine Schaltfunktion von einer ALU, wo eben 2 32
-Bit -Zahlen anliegen und Sie haben 64 Variablen, dann ist vielleicht
das nicht unbedingt das Verfahren der Wahl.
Wieder das Dualitätsprinzip.
Ich habe Ihnen jetzt gezeigt, wie Sie die disjunktive Normalform
herleiten können.
Jetzt die konjunktive Normalform.
Da können Sie auch den Schengen-Entwicklungssatz verwenden.
Allerdings brauchen Sie hier die duale Form des Schengen
-Entwicklungssatzes.
Und die sieht wieder so aus.
Wir ersetzen jede Disjunktion durch eine Konjunktion.
Das haben wir also hier gemacht, also die roten und grünen Operatoren.
Wir ersetzen jede 0 durch eine 1.
Genau, und das war's.
Und dann haben wir von einem Gesetz, von dem wir schon wissen, dass es
gültig ist, das duale Gesetz, was dann eben auch automatisch auch
gültig sein muss.
Und das ist unser zweiter Schengen-Entwicklungssatz, mit dem...
Sie sehen es hier nochmal.
Die 1 wird zur 0, die 0 wird zur 1 und die Operatoren werden
umgedreht.
Und dann haben wir die konjunktive Form des Schengen
-Entwicklungssatzes.
Die wird benötigt bei Aufgabe 4.
Und Aufgabe 4 ist... muss ich mal schauen...
Aufgabe 4 ist so gedacht, dass man sie selber hinschreibt.
Auch wenn das relativ viel ist, aber gut.
Also zunächst mal entwickeln wir nach A.
Das heißt, wir gehen hier hin und ersetzen A durch die 0.
Genau, also wir ersetzen A durch die 0.
Und... muss ich ein bisschen aufpassen mit den Klammern.
Also hier ist natürlich auch noch eine Klammer.
Und hier haben wir jetzt A durch die 1 ersetzt.
Ich muss mal kurz... wie ist das denn mit den Klammern hier?
Also wir haben diese große Klammer, wir haben die hier und die hier.
Und hier ist nochmal eine Klammer.
Und jetzt gehen wir hier hin.
Das ist B.
0 oder B ist B.
1 oder B ist immer 1.
0 Antivalent C ist immer C.
1 Antivalent C ist immer nicht C.
Und das setzen wir jetzt ein.
Und gut, jetzt sehen wir hier hinten, 1 Antivalent... äh, 1 Äquivalent
1 ist immer 1.
Können wir auch schon ausrechnen.
Und nicht A oder 1 ist eben auch immer 1.
Und dann haben wir hier noch übrig A oder B Äquivalent C.
Und jetzt muss ich auf die nächste Folie.
Damit geht es dann weiter.
Also A oder B Äquivalent C.
Und dieses B Äquivalent C entwickeln wir jetzt nach B.
D.h.
wir haben hier B oder 0 Äquivalent C und nicht B oder 1 Äquivalent C.
Und da können wir wieder einsetzen, das ist B oder nicht C und nicht B
oder C.
Jetzt setzen wir ein in das da oben.
Dann haben wir hier A oder
B oder C, nicht C und A oder nicht B, C.
Und wenn wir jetzt zählen, wir haben hier wieder die
Variablenreihenfolge.
Dann haben wir hier den Maxterm 2 und 4.
Also hier haben wir unseren Maxterm 4 und hier haben wir den Maxterm
2.
So rum genau.
Hätte ich vielleicht andersrum hinschreiben sollen.
Aber prinzipiell denke ich, ist es nachvollziehbar.
Gibt es dazu Fragen?
Also wir haben hier den Challengen-Entwicklungssatz zweimal
angewendet.
Wir hätten jetzt auch noch ein drittes Mal anwenden können und nach C
entwickeln, aber das war gar nicht notwendig.
Und die zweite Anwendung, die war in dieser Nebenrechnung.
Also in dem, was ich jetzt eingeklammert habe hier, da habe ich
einfach A jetzt mal außen vor gelassen und einfach hier diesen Term
nur noch entwickelt.
Weil ja sowieso der ganze Term schon dieses A oder enthält.
Wenn es hier natürlich noch weitergegangen wäre, jetzt mit und nicht A
oder, wenn wir also auch den anderen Fall gehabt hätten, dann hätten
wir dieses A auch mit entwickeln müssen.
Aber wenn man das sowieso schon ausklammern kann, dann muss man da
natürlich nicht mehr den Entwicklungssatz anwenden.
Okay, dann eine Textaufgabe.
Sie sehen, diese Folie ist eigentlich ein Beispiel, wie man eine
Aufgabe nicht stellen sollte.
Ich lese es Ihnen vielleicht einfach mal vor.
Das ist das sogenannte Ziegenproblem, heißt es glaube ich.
Es geht darum, man möchte Tiere über einen Fluss bringen.
Also Farmer, Wolf, Ziege und ein Kohlekopf befinden sich auf einer
Flussseite.
Der Farmer besitzt ein Boot, welches ihn selbst sowie einen weiteren
Gegenstand trägt.
Er möchte nun mit allen Gütern auf die andere Seite des Flusses
gelangen.
Unglücklicherweise frisst der Wolf die Ziege bzw.
die Ziege den Kohlekopf, wenn er diese unbeaufsichtigt lässt.
Sie sehen schon, worauf das hinausläuft.
Es gibt jetzt dann am Ende eine Budgetfunktion, die eben angibt, was
man machen darf und was man nicht machen darf.
Wir wollen nicht, dass irgendein Tier, ein anderes Tier oder den
Kohlekopf frisst.
Zur Vereinfachung sei angenommen, dass die Überfahrt keine Zeit
benötigt.
Der Bauer also entweder am linken oder am rechten Ufer ist.
Damit nun der Bauer nicht versehentlich Wolf und Ziege bzw.
Ziege und Kohl allein lässt, soll ein Warnsystem aufgebaut werden,
welches in diesen Fällen Alarm auslöst.
Die Buchstaben, also die Buchstaben gemeint sind eigentlich Variablen.
F, W, Z und K bezeichnen Farmer Wolf, Ziege und den Kohlekopf.
Ist der Wert einer solchen Variable 0 bzw.
1, dann befindet sich dieser der entsprechende Gegenstand auf der
linken bzw.
rechten Flussseite.
Geben Sie die Funktionstabelle der Alarmfunktion A an.
So, ich habe die Lösung auf den Folien, keine Sorge.
Das ist vielleicht auch eher etwas, was Sie sich zu Hause dann nochmal
anschauen könnten, ob Sie das logisch finden, ob Sie das
nachvollziehen können.
Ich kann das jetzt nicht komplett hier alles vorrechnen.
Was wir allerdings machen können, ist dann die DNF und die KNF
ablesen.
Also Sie sehen hier Farmer, Wolf, Ziege und Kohlekopf.
Und ein paar Kombinationen gibt es, die eben verboten sind.
Gehen wir es vielleicht mal oben durch.
Hier, also der Farmer ist auf der gleichen Seite wie Wolf und so
weiter, das ist kein Problem.
Im nächsten Fall, also wie gesagt, ich schreibe jetzt nichts hin, weil
es kommt gleich die Animation.
Im nächsten Fall, der Kohlekopf ist schon auf der anderen Seite, das
ist auch kein Problem.
Hier, die Ziege ist alleine auf der anderen Seite.
Das ist auch kein Problem.
Der nächste Fall, Ziege und Kohlekopf sind auf der anderen Seite.
Dann haben wir ein Problem, weil wenn die Ziege und der Kohlekopf auf
der rechten Seite sind und der Farmer ist auf der linken, dann wird
die Ziege den Kohlekopf fressen.
Der Wolf ist alleine auf der anderen Seite, ist kein Problem.
Der Wolf und der Kohlekopf sind alleine auf der anderen Seite, ist
auch kein Problem.
Der Wolf, der scheint den Kohlekopf nicht zu fressen.
Wolf und Ziege sind beide auf der anderen Seite als der Farmer.
Ist ein Problem, der Wolf wird die Ziege fressen, auch wenn der
Kohlekopf dabei ist.
Also hier stellt sich dann die Frage, frisst dann die Ziege zuerst den
Kohlekopf oder zuerst der Wolf die Ziege?
Das müsste man wahrscheinlich dann empirisch ermitteln.
Und so geht es entsprechend weiter.
Und wenn wir uns dann die Einstellen anschauen...
Hier unten gibt es auch noch ein Problem.
Also hier zum Beispiel der Farmer und der Wolf sind schon auf der
anderen Seite und Ziege und Kohlekopf sind noch auf der linken Seite.
Dann wird eben auch die Ziege den Kohlekopf fressen.
Und dann haben wir diese Funktionstabelle bestimmt.
Und diese Funktionstabelle an sich charakterisiert die Funktion schon
eindeutig.
Das heißt, wenn Sie diese Tabelle hinschreiben, dann ist Ihre
Budgetfunktion eindeutig bestimmt.
Trotzdem können wir natürlich noch die dnf und die knf angeben.
Machen wir das Ganze mal für die dnf.
Für die dnf suchen wir jetzt die Einstellen der Funktion.
Dann haben wir also hier unseren Minterm 3, unseren Minterm 6, unseren
Minterm 7, unseren Minterm 8, unseren Minterm 9 und unseren Minterm
12.
Jetzt können wir die Funktion hinschreiben, also a.
Gut, schreiben wir es nochmal mit den Variablen hin.
Das ist also hier f, w, z, k, also nicht f, nicht w.
Das ist also diese Zeile in der Tabelle hier, diese Zeile.
Oder nicht f, w, z, nicht k.
Das ist diese Zeile.
Oder nicht f, w, z, k.
Oder f, nicht
w, nicht z, nicht k.
Oder f, nicht w, nicht z, nicht k.
Oder f, w, nicht z, nicht k.
Sie sehen, das sind die Möglichkeiten.
Jetzt machen wir das Gleiche noch für die knf.
Bei der knf müssen wir jetzt die Maxterme betrachten.
Markieren wir die mal wieder hier rot, auch wenn es ein paar mehr
sind.
Also m0, m1, m2, m4, m5, m10, m11
und m14.
Das ist natürlich Quatsch, das muss dann bis 15 gehen.
Also haben wir hier
die 12 und dann kommt als nächstes die 13, die 14 und die 15.
Und an dieser Stelle sehen Sie jetzt hoffentlich nochmal, was ich
vorhin schon gesagt habe.
Wenn die Funktion vollständig definiert ist, dann steht hier immer
eine 0 oder eine 1.
Bei jeder möglichen Belegung.
Das heißt, wenn Sie die Anzahl Ihrer Minterme und die Anzahl Ihrer
Maxterme addieren, haben Sie genau die Gesamtzahl der möglichen
Belegungen für diese Funktion.
In dem Fall ist es jetzt 16, denn wir haben vier Variablen, vier
Eingabenvariablen.
2 hoch 4 ist 16.
Und jetzt können wir das Ganze nochmal hinschreiben.
Dann haben wir also hier a, f, w, z, k ist Maxterme.
Und zwar die Maxterme 0, 1, 2, 4, 5, 10, 11, 13, 14, 15.
Und schreiben wir es nochmal mit den Variablen hin.
Dann gibt es den kleinen Trick.
Am besten schreibt man es erst mal ohne die Negation hin.
Wir machen dann die Negation hinterher.
Und jetzt müssen wir natürlich noch die Negation machen.
Also 0, da brauchen wir keine Negation bei den Maxterm 0.
Sie müssen sich das nochmal vergegenwärtigen, wenn Sie sich jetzt
überlegen, warum wir bei der 0 hier keine Negation drüber machen.
Wir betrachten ja hier, wir müssen ja einen Term dafür angeben, wann
die Funktion 1 ist.
Und wir sagen, hier vorne dieser Term, dieser Term stellt sicher, dass
wir nicht in dieser Zeile sind.
Das heißt, wir prüfen, ist f, ja, war, oder w, oder z, oder k.
Wenn einer dieser vier Variablen 1 ist, sind wir nicht in dieser
ersten Zeile.
Und das ist das Prinzip, was Sie hier anwenden, wenn Sie Ihre
Konjunktivenormalform aufstellen.
Das heißt, das ist die 1, das ist die 2, das ist die 4, das ist die 5,
das ist die 10 und das ist die 11.
Und, ja gut, dann kommt die 12 und dann sehe ich gerade, es fehlen
noch, das ist die 12.
Und jetzt geht es natürlich noch weiter.
Das sind ja insgesamt 10.
Das ist die, die 12 gibt es gar nicht, das ist die 13.
Dann kommt die 14 und dann kommt die 15.
So, können wir nochmal prüfen.
Das ist immer gefährlich, da kann man natürlich auch mal ganz leicht
irgendwo einen Strich vergessen.
Das ist immer ein bisschen gefährlich, aber im Großen und Ganzen denke
ich, sollte das passen.
Ja, das sieht gut aus.
Okay, und damit kommen wir zur nächsten Aufgabe.
Aufgabe 6.
Wir haben wieder eine Funktion gegeben und wir sollen die beiden
Normalformen bestimmen.
Wir machen das wieder über die Wertetabelle.
Jetzt müssen wir zunächst mal die Funktion selber bestimmen.
Also wir haben hier die Funktion nicht C oder B und nicht A.
Das heißt, wir füllen jetzt erstmal die Wertetabelle aus, also nicht
C, das ist hier oben.
Und B oder nicht A, das ist hier.
Und natürlich ist es streng genommen auch noch hier.
Und hier sind Nullen.
Und jetzt können wir die DNF und die KNF direkt ablesen.
Also unsere DNF.
Nicht C, nicht B, nicht A oder nicht C, nicht B, A oder nicht C, B,
nicht A oder nicht C, B, A oder C, B, nicht A.
Und unsere KNF.
Und die KNF sieht so aus.
Nicht C oder B oder A
oder nicht A.
So, das sind unsere Maxterme der Funktion.
Sieht gut aus.
Jetzt wieder eine Textaufgabe.
Es soll eine Notstoppschaltung für einen mobilen Roboter realisiert
werden.
Der Roboter hat drei Sensoren, die drohende Kollisionen mit
Hindernissen erkennen.
Der Roboter darf weiterfahren, wenn zwei Sensoren keine
Kollisionsgefahr melden.
Geben Sie die Schaltfunktion der Schaltung in disjunktiver Normalform
an.
Vereinfachen Sie die DNF so weit wie möglich.
Sie sehen mit dem Vereinfachen hier, das geht dann schon in Richtung
Minimalform.
Also ich glaube, ich muss hier keine Skizze machen.
Ist eigentlich egal.
Wir haben also hier unsere Wertetabelle wieder.
Und die Frage ist, F ist unsere Kollisionserkennung.
Und wenn zwei der Sensoren eine Kollision melden, mindestens zwei,
dann sagen wir, darf der Roboter nicht weiterfahren.
Das heißt, überall da, wo wir mindestens zwei Einsen haben, ist die
Ausgabe 1.
Also hier und hier und hier und auch hier.
Also mindestens zwei.
Und an den anderen Fällen ist sie 0.
Und jetzt können wir direkt die DNF angeben.
Die DNF können wir direkt wieder ablesen.
Also die Min-Therme, also nicht S2, S1, S0 oder S2, nicht S1, S0
oder S2, S1, S0.
Und dann vereinfachen wir das Ganze.
Was können wir hier vereinfachen?
Wir können natürlich immer Sachen ausklammern, also Distributivgesetz
anwenden.
Das heißt, hier klammern wir zum Beispiel mal S1, S0 aus.
Und dann haben wir hier S2, nicht S2 oder S2 oder...
Und das hier ist ja immer 1.
Und naja, Sie können das selber mal noch nachrechnen.
Ich schreibe Ihnen jetzt mal das Endprodukt hin.
Das ist vielleicht auch für Sie eine ganz gute Übung, wie Sie das
Ganze minimieren können.
Und heraus kommt dann S2, S1 oder S2, S0 oder S1, S0.
Und wenn Sie es noch mal anschauen, das ist natürlich genau das, wie
Sie es intuitiv auch hingeschrieben hätten.
Wir sagen also, die Warnung soll dann ausgelöst werden, wenn
mindestens zwei Sensoren eben 1 sind.
Mindestens zwei Sensoren.
Das ist ja genau das, was wir hier prüfen.
Wir haben also drei Sensoren.
Das heißt, von diesen drei Sensoren gibt es drei Möglichkeiten, zwei
Sensoren von diesen drei Sensoren auszuwählen.
Also entweder 2 und 1, 2 und 0 oder 1 und 0.
Und das ist genau das, was wir hier prüfen.
Die Möglichkeit, dass alle drei Sensoren 1 sind, ist natürlich dann
auch abgedeckt.
Wenn alle drei Sensoren 1 sind, haben Sie hier 3 mal 1, haben Sie 1
oder 1 oder 1, ist auch wieder 1.
Dann schauen wir uns noch die letzte Aufgabe an.
Und hier geht es um ein Bauteil, was Sie schon kennen.
Es soll ein Schaltnetz entworfen werden, das die Summe von zwei
Dualziffern ai und bi addiert und dabei den Übertrag cin aus der
vorhergehenden Stelle berücksichtigt.
Ausgabevariablen sind die Summe si und der bei der Addition eventuell
entstehende Übertrag cout.
Geben Sie die Funktionstabelle an, geben Sie die dnf von si an und
geben Sie die knf von cout an.
Was ist das für ein Bauteil?
Kennen Sie alle aus Rechnerorganisationen?
Keiner eine Idee, was das ist?
Okay, schade.
Also das ist ein sogenannter Volladdierer.
Das hat mich jetzt ein bisschen enttäuscht, weil eigentlich sollte
Ihnen das wirklich bekannt sein.
Wenn Ihnen das nicht bekannt ist, dann müssen Sie unter Umständen auch
nochmal den Stoff aus RO sich ein bisschen anschauen.
Wir haben das schon relativ prominent behandelt in RO, das sollte
eigentlich noch im Gedächtnis sein.
Und dieses c bedeutet carry, also carry Übertrag, carry in und carry
out.
Es ist natürlich die Summe und wenn Sie diese Volladdierer Schaltung
nehmen, die Sie jetzt in dieser Aufgabe haben und Sie schalten die
zusammen, Sie kombinieren mehrere Volladdierer, dann kriegen Sie eine
sogenannte Addierer Schaltung.
Dann können Sie eben Zahlen, z.B.
wenn Sie acht Volladdierer zusammenschalten, dann können Sie acht
Bitzahlen addieren.
Streng genommen brauchen Sie sogar an der einer Stelle gar keinen
Volladdierer, sondern nur einen Halbaddierer, weil Sie dort ja noch
keinen carry in haben, da haben Sie ja noch keinen Übertrag, weil es
ja keine vorhergehende Stelle gibt.
Schauen wir uns das Ganze an, die Funktionstabelle, wie sieht die aus?
Wir addieren also diese drei Zahlen zusammen.
0 plus 0 plus 0 ist 0, Übertrag 0.
0 plus 0 plus 1 ist 1, Übertrag 0.
0 plus 1 plus 0 ist 1, Übertrag 0.
0 plus 1 plus 1 ist 0, Übertrag 1.
1 plus 0 plus 0 ist 1, Übertrag 0.
1 plus 0 plus 1 ist 0, Übertrag 1.
1 plus 1 plus 0 ist 0, Übertrag 1.
Und 1 plus 1 plus 1 ist eben 1, Übertrag 1.
Und
jetzt sollen wir die DNF von SI angeben.
Okay, da steht es auch schon wieder.
Dann...
Also es ist überhaupt nichts anderes als das, was wir den ganzen Tag
hier jetzt schon gemacht haben.
Nur, dass die Variablen jetzt halt hier CIN, BI und AI heißen.
Und das ist die DNF und nun noch die KNF von COUT.
Und hier haben wir dann CIN,
also nochmal hier, das sind die Stellen, die wir brauchen.
Und damit sind wir eigentlich am Ende der heutigen Übung angelangt.
Haben Sie denn noch irgendwelche Fragen zu diesem ganzen
Themenkomplex?
Okay, dann bin ich fertig für heute.
Dann geht es am Montag wieder mit der Vorlesung weiter von Professor Hanebeck.