So, ich würde sagen, wir beginnen.
Grüße also zur heutigen Vorlesung der TI-DT.
Wir werden uns heute mit Booleschen Funktionen befassen.
Wir haben ja in den letzten Vorlesungen alles dafür vorbereitet, dass
wir also heute zu den Booleschen Funktionen kommen können.
Die Frage ist jetzt, worum geht es denn eigentlich hier?
Wir haben also gegeben so ein Tupel von binären Variablen x1 bis xn.
Ich habe ja gesagt, von der Reihenfolge, ob wir jetzt sozusagen von
rechts nach links oder von links nach rechts gehen, das werde ich in
Sitzungen jedes Mal dazu sagen.
Hier gehen wir jetzt von links nach rechts, x1 bis xn.
Wir haben eine endstellige Boolesche Funktion und die soll jetzt einer
bestimmten Wahrheitsbelegung als Eingang einen bestimmten Ausgangswert
zuweisen.
Das heißt also, wir haben eine Funktion, die einen skalaren
Ausgangswert als Wahrheitswert produziert.
Die Frage ist jetzt natürlich, oder wir können uns einige Fragen
stellen, wie viele mögliche Belegungen gibt es denn?
Das ist ziemlich klar.
Dann ist auch die Frage, wie viele mögliche Funktionen gibt es denn?
Wie viele Boolesche Funktionen kann ich mir denn überhaupt überlegen?
Und wie viele Belegungen gibt es denn?
Sehen Sie das?
Ja.
Genau.
Und wie viele Funktionen gibt es?
Nein.
Nein, noch nicht ganz.
Gibt es weitere Tipps?
Wie viele Funktionen kann es geben?
Wie viele Boolesche Funktionen, die endstellig sind, kann es geben?
Okay, dann gehen wir mal.
Also erstmal 2hochn-Belegung, das wurde ja gerade gesagt, das ist
richtig.
Und dann gibt es 2hoch2hochn-Funktion.
Und das wollen wir jetzt mal an einem Beispiel schnell belegen.
Gebe ich Ihnen dafür mal ein kleines Beispiel.
Und zwar, wenn wir n gleich 3 betrachten, also wir haben n gleich 3,
dann haben wir doch so etwas wie, wenn ich jetzt x2, x1 und x0 habe.
Und das habe ich Ihnen ja mehrfach schon vorgeführt.
Wie zähle ich jetzt da einfach durch?
Ich sage ja, bei x0 haben wir dann 0, 1, 0, 1, 0, 1, 0, 1.
Bei x1 haben wir 0, 0, 1, 1, 0, 0, 1, 1.
Und dann haben wir oben 0, 0, 0, 0, 1, 1, 1, 1.
Also das heißt, hier können wir ziemlich klar sehen, was gerade schon
gesagt wurde, dass wir hier, ich kürze das mal ab als w, das ist
offenbar 2 hoch 3, weil an jeder Stelle haben wir 2 Möglichkeiten und
wir haben 3 Variablen.
Das heißt also, wir haben 2 hoch 3 und das sind 8 Belegungen.
Das heißt also, was wir in die Funktion reinstecken können.
Und jetzt können wir zu jeder Belegung, können wir natürlich jetzt
einen Ausgabewert produzieren.
Das heißt, Sie müssen sich die Funktion so vorstellen, dass die für
jede Belegung, die wir am Eingang haben können, dann auch einen
entsprechenden Wert, wie ein Speicher, wir werden sehen, wir können
das über Speicher realisieren, dann dazu etwas zuweisen.
Das heißt also, wir haben jetzt zu jeder Belegung,
haben wir 2 mögliche Ausgabewerte, nämlich 0 oder 1.
Naja und was kommt dann wohl raus?
Wenn ich zu jeder Belegung eben diese 2 Ausgabewerte habe, dann muss
ich praktisch die möglichen Belegungen, die ich habe, also dann kommt
heraus, ich habe 2 hoch w und das ist ja in dem Fall 2 hoch 2 hoch 3
und das wären 256, jetzt hier in dem Beispiel, 256 unterschiedliche
Funktionen.
Ja und die werden wir uns ja gleich nochmal anschauen, verschiedene
Funktionen, Typen, die es da gibt.
Okay, ich hoffe das ist klar, das war jetzt ein Beispiel.
Und ja, machen wir mal Einstellungen.
Bei Einstellungen ist ziemlich klar, bei Einstellungen, die bilden ab
von 0,1 nach 0,1 und dann kann ich 4 Funktionen haben.
Entweder die 0-Funktion, die 1-Funktion oder die Funktion, die sagt,
es ist a oder a nicht und das wäre die entsprechende Wertetabelle.
Ich glaube, das ist klar, das wären einstellige Funktionen.
Bei zweistelligen sieht es schon nicht mehr ganz so einfach aus.
Da müssen wir uns auch überlegen, wie stellen wir das denn eigentlich
dar?
Wir können ja sagen, wir haben so eine Funktion, das ist das
Kreuzprodukt, also kathetisches Produkt von 0,1 und 0,1, bildet ab auf
0,1 und jetzt können wir das durch eine Funktionentabelle darstellen,
wie hier dargestellt.
Oder durch einen algebraischen Ausdruck.
Aber ich denke, das ist klar.
Und das wären jetzt 16 mögliche zweistellige bool'sche Funktionen.
Und so wie wir es gerade diskutiert haben, ich habe hier vorne die
Eingänge.
Das verwirrt es vielleicht am Anfang erstmal, aber ich habe ja als
Eingang immer x0, x1.
Ich kann jetzt jeweils einen Wert hier nehmen, z.B.
1,1, 0,1, 1,0 oder 0,0.
Und die würde ich jetzt hier entsprechend eingeben.
Und dann gibt es halt die entsprechenden Funktionen.
Wir haben nur eine einzige nicht benannt.
Die würde ich hier als Nullfunktion bezeichnen.
Die gibt konstant Null aus.
Und für alle anderen finden Sie hier die entsprechenden Namen.
Das wären jetzt zweistellige bool'sche Funktionen.
Das können Sie jetzt weiter treiben, dreistellig, vierstellig und so
weiter.
Die Frage ist jetzt, wenn ich so einen symbolischen Ausdruck habe, wie
komme ich denn zur Funktionentabelle?
Das ist auch ziemlich einfach.
Ich muss ja den Ausdruck nur interpretieren sozusagen.
Ich muss den auswerten.
Ich muss also da entsprechend Werte einsetzen.
Ich muss also für die Variablen Werte einsetzen.
Ich bekomme dann Werte raus.
Und jetzt haben wir eine Konvention und die werden wir ab jetzt
sozusagen auch durchhalten.
Dass wir sagen, die Negation kommt vor der Konjunktion.
Die Konjunktion kommt vor der Disjunktion.
Und wenn wir irgendwas anderes haben wollen, benutzen wir Klammern.
Und das ist übrigens total willkürlich.
Sie haben ja gesehen bei der bool'schen Algebra, dass das Ganze
symmetrisch ist.
Das heißt, wir hätten die Klammern auch anders setzen können.
Da spricht überhaupt nichts dagegen.
Also das heißt, die Intuition, die wir normalerweise jetzt haben, mal
und plus und so weiter, die würde hier gar nicht greifen.
Das heißt, wir können auch eine ganz andere Konvention verwenden.
Aber wir verwenden die, die uns am nächsten liegt.
Und die werden wir jetzt hier auch durchziehen.
Also Negation vor Konjunktion und Konjunktion vor Disjunktion.
So, jetzt kommen wir zu einem ganz wichtigen Thema, nämlich
vollständige Operatoren-Systeme.
Wir wollen ja im Prinzip alle möglichen Operationen, die wir haben,
alle bool'schen Operatoren, die wollen wir irgendwie darstellen.
Und die Frage ist jetzt halt, wenn ich bestimmte Bausteine habe, ich
habe meinetwegen nicht immer die Möglichkeit, Bausteine zu haben, die
und, oder und nicht darstellen, sondern ich habe vielleicht nur
Bausteine, die können ein and darstellen.
Da kommen wir gleich dazu.
Ja, und was mache ich dann?
Ich möchte im Prinzip nicht nur mit den Operatoren alle bool'schen
Funktionen darstellen können, sondern ich möchte beispielsweise mit
einer Äquivalenz oder mit einer Antivalenz und so weiter, damit möchte
ich auch alle bool'schen Funktionen darstellen können.
Die Frage ist halt, geht das?
Da kann man schon sagen, nein, die reine Äquivalenz geht nicht, aber
Antivalenz und das und geht.
Das heißt also, man kann im Prinzip jetzt versuchen, diese
Grundoperationen, die wir da haben, zu ersetzen durch entsprechende
praktikablere Operationen, die wir mit unserer Technologie auch
abdecken können.
Da gebe ich Ihnen jetzt vielleicht mal ein paar Beispiele, die
vielleicht sogar überraschend sind.
Wenn ich eine Funktion habe, zum Beispiel ein Y, das Y wäre A nicht
oder B nicht.
Dann kann ich das natürlich schreiben, die morgensche Gesetze, bitte
prägen Sie sich die ein, das wäre das Gleiche wie A und B nicht.
Und das ist aber, wenn ich jetzt in eine Technologie hineingehe, ist
ein NAND-Glied.
Das heißt, das würden wir schreiben als A NAND B.
Also nicht und.
Und dann können wir aber auch sagen, wenn ich zum Beispiel so etwas
ganz Simples habe wie Y, ist A nicht.
Fragt man sich, okay, wie implementiere ich denn eine Negation?
Und dann gibt es ein paar Möglichkeiten, ich kann das eben unter
Ideenpotenzialgesetz bemühen.
Ich kann sagen, also A und A nicht.
Dann kann ich jetzt wieder sagen, das ist ja dann NAND, das ist also A
NAND A.
Das heißt, mit dem NAND-Gatter kann ich hier schon einige Dinge
machen, wie man sieht.
Kann ich mal schauen, ob das auch mit dem NOR geht, nehme ich wieder
das Ideenpotenzgesetz, also A oder A nicht ist das Gleiche und das
wäre dann praktisch A NOR A.
Das heißt also, mit NAND und NOR kann ich viel machen und wir werden
das auch noch kennenlernen.
Das sind auch entsprechend die Grundbausteine, die wir gerne verwenden
wollen.
Wir werden am Ende sehen, genau das sind die, die uns zur Verfügung
stehen.
Das heißt, wir möchten es doch ganz gerne zurückführen auf NAND und
NOR.
Das kommt gleich in der nächsten Stunde und dann werden Sie sehen,
warum wir jetzt hier schon so einen Aufwand treiben, um das zu
motivieren.
Okay, vollständige Operatoren-Systeme.
Wir können da jetzt verschiedene haben.
Wir können sagen, das Einfachste war natürlich, dass wir haben UND
oder NICHT.
Dann können wir sowas haben wie UND und NICHT, ODER und NICHT, kann
man entsprechend darstellen.
Wir können ein reines NAND haben, wir können ein reines NOR haben, was
schon mal interessant ist.
Das heißt, mit reinen NAND-Gliedern können Sie alles abdecken und wir
können sowas Verrücktes haben wie ein UND und eine Antivalenz.
Das werden wir gleich mal beweisen im nächsten Schritt, dass Sie mal
ein Gefühl dafür bekommen, wie man denn überhaupt von diesem Ausdruck
tatsächlich auf eine Disjunktion kommt.
Wir werden sehen, dass diese ganzen Darstellungen praktisch sind, also
wir brauchen die auch wirklich.
Dann gehen wir hier mal los und sagen uns jetzt mal, wir haben solche
vollständigen Operatoren-Systeme.
Also vollständige Operatoren-Systeme.
Machen wir mal NAND.
NAND ist ziemlich einfach darzustellen.
Wir sagen also, wir hätten jetzt nur NAND zur Verfügung.
Was wollen wir machen?
Wir wollen ja sagen, wir wollen die Negation darstellen, haben wir
gerade schon gemacht.
Also das ist ziemlich einfach.
Also A NAND A, das ist ja A und A nicht und das ist A nicht.
Das war ziemlich simpel.
Dann ist die Frage, wie kriege ich jetzt UND und ODER repräsentiert?
Das ist vielleicht nicht mehr ganz so simpel.
Das UND, das sagen wir jetzt, wir haben sowas wie A NAND B.
Das Ganze dann NAND A NAND B.
Das sieht ja schon mal etwas verwirrend aus.
Wieso sollte das ein UND sein?
Und da können wir uns jetzt gleich helfen.
Wir schreiben das wieder um.
Wir schreiben das also um in den normalen Operatoren, sage ich mal
normalen Anführungsstrichen.
Also UND oder NICHT.
Und das heißt, wir bekommen jetzt sowas wie, das ist ja A UND B NICHT.
UND A UND B NICHT.
Und das Ganze nochmal NICHT.
Und was kann ich da wohl sagen?
Jetzt wissen wir ja, die tauchen zweimal auf.
Das heißt, ich kann jetzt hier zusammenfassen.
Ich kann also sagen A UND B NICHT und darüber wieder NICHT.
Und das Ganze ist natürlich A UND B.
Ich glaube, das ist klar.
Dann die Frage ODER.
Kriegen wir ein ODER hin?
Beim ODER sieht es ganz verrückt aus.
Da wäre man sogar gewillt zu sagen, muss man das so kompliziert
machen?
Geht es nicht einfacher?
Das ODER wäre nämlich tatsächlich A NÄHNT A.
Dann NÄHNT B NÄHNT B.
Also genau dual, geradezu dem UND.
Und warum ist das so?
Da können wir auch wieder hinschreiben.
Das ist also A UND A NICHT oder B UND B NICHT.
Das Ganze NICHT.
Und jetzt können wir sagen, A UND A ist A.
Das heißt, wir bekommen jetzt hier ein A NICHT und ein B NICHT.
Das Ganze NICHT.
Na ja, und da können wir jetzt die morgigen Gesetze wieder bemühen.
Und da würden wir jetzt sagen, das Ganze ist natürlich offensichtlich
A oder B.
Ich hoffe, das ist klar.
Also ich denke, solche Sachen sollten Sie rechnen können.
Das sind Fragen, die wir dann hinterher von Ihnen erwarten, dass Sie
so etwas beantworten können.
Und das war jetzt noch trivial.
Jetzt kommen wir zu etwas Komplizierterem.
Also erstmal das NOIR.
Das mache ich jetzt nicht mehr.
Bei dem NOIR schreibe ich einfach hin, das ist analog.
Und dann wäre jetzt die Frage, wir nehmen jetzt UND und die
Antivalenz.
Das heißt also, wir haben ein UND und die Antivalenz.
Und das ist jetzt, glaube ich, schon etwas schwieriger.
Ja, jetzt schreiben wir uns mal hin, was heißt denn überhaupt
Antivalenz?
Antivalenz bedeutet doch Folgendes.
Wir sagen, wir haben A, Antivalent und B.
Das ist so etwas wie A NICHT und B.
Und da müsste ich gar keine Klammern setzen.
Sie erinnern sich an unsere Konvention.
Ich mache es jetzt einfach nur pro forma.
Müsste ich keine Klammern setzen.
Oder A und B NICHT.
Das wäre die Antivalenz.
Mit der wollen wir jetzt rechnen.
Wir wollen jetzt sagen, kann ich zum Beispiel eine Negation darstellen
mit der Antivalenz.
Also die Negation wird sein A Antivalent 1.
Warum ist das so?
Nehmen wir einfach die entsprechende Formalisierung davon.
Dann wäre das also A NICHT und 1.
Oder A und 1 NICHT.
Ich nehme also im Prinzip einfach genau das her, was wir hier gerade
hingeschrieben haben.
Und dann sieht man natürlich, dass das hier die Null ist.
Und dann bekomme ich hier wirklich nur raus A QUER.
Damit wären wir fertig.
Das ist einfach.
Jetzt kommen wir aber dazu, wie wäre denn jetzt eine Veroderung.
Die Verunderung ist ja ziemlich einfach, weil das UND ist ja in
unserem Operatoren-System.
Das müssen wir gar nicht diskutieren.
Das ODER ist also wichtig.
Und das ODER sieht jetzt also folgendermaßen aus.
Und das ist ziemlich verrückt.
Also A, Antivalent B und das ganze Antivalent dann nochmal zu A und B.
UND war ja mit in unseren Operatoren drin.
Und das ist natürlich jetzt ziemlich mühsam.
Jetzt müssen wir mal gucken, wie löse ich das denn auf.
Und dann müssen wir immer wieder auf diese Gleichung zurückgreifen.
Das heißt also, wenn ich jetzt sowas hier hinschreibe, dann muss ich
sozusagen hier immer diese Definition verwenden, um das hier
entsprechend einzusetzen.
Und was kommt denn draus?
Also jetzt fangen wir mal an.
Wir sagen mal, dass A bleibt stehen und die Antivalenz davon.
Und jetzt lösen wir den Rest auf.
Und das Ganze wäre dann, muss ich mit den Klammern aufpassen, nochmal
eine große Klammer.
So, und jetzt lösen wir auf B, Antivalent A und B.
Das wäre doch B nicht und die Klammern A und B.
Wie gesagt, Klammern setze ich jetzt zu viele.
Denken Sie sich die teilweise weg, wenn Sie meinen, Sie können sich
sowieso wegdenken.
Oder, jetzt kommt der zweite Teil, haben wir dann noch ein B und A und
B nicht.
Auch das setze ich jetzt mal in Klammern.
So, und das wäre jetzt...
Ja, und jetzt, was kann ich jetzt hier sagen für den ersten Teil?
Was gilt wohl hierfür?
Was kann ich hier sofort sagen?
Ist Null, ja?
Das heißt, hier kommt Null raus.
Das ist immer Null.
Und das heißt, ich kann das Ganze jetzt so hinschreiben.
Ich sage jetzt, das ist A, Antivalent mit...
Was habe ich geschrieben?
B und A und B nicht.
Klammern oder Null.
Die Null habe ich nochmal hingeschrieben, das Ganze jetzt nochmal in
eckige Klammern gesetzt.
Das ist sozusagen der Ausdruck hier.
Das heißt also, der Ausdruck wandert hier runter, der Ausdruck wandert
hier hin.
So, und jetzt müssen wir uns mal überlegen, das hier unten kann ich
doch jetzt umschreiben.
Was ist das denn hier?
Die bauernschwere Gesetze müssten Sie inzwischen auswendig daherbeten
können.
Was ist denn das?
Ja.
Genau, das heißt also, wir haben jetzt hier A nicht oder B nicht.
Und jetzt gehe ich mal auf die nächste Seite.
Da brauchen wir jetzt doch noch ein bisschen Platz.
Und dann haben wir ja, das Ganze ist jetzt also A, Antivalent mit, was
wir gerade rausbekommen haben, B und A nicht.
Und das in Klammern.
So, und jetzt kann ich da wieder meine Antivalenzbeziehung anwenden.
Ich kann ja sagen, das ist jetzt A nicht und B und A nicht.
Oder A und B und A nicht.
Und das Ganze muss ich jetzt dann halt entsprechend negieren, so wie
es halt die Antivalenzbeziehung vorschreibt.
Und da kann ich jetzt auch wieder sagen, das ist natürlich ziemlich
einfach.
Hier kann ich jetzt ja sagen, das kann ich alles zusammenfassen, die
Klammern sind unnötig.
Also ich habe A nicht und B.
Und das schreiben wir jetzt einfach mal erstmal hin.
Also wir schreiben hier hin, das wäre jetzt hier gleich A nicht und B.
Und dann kommt noch ein oder.
Ja, und wie machen wir das jetzt mit dem Rest?
Wir können da wieder das dem morgens schon Gesetz anwenden.
Das wäre also A und B nicht oder A.
Das dann aber in Klammern.
So, und jetzt muss ich aufpassen.
Habe ich eigentlich hier genug Klammern gesetzt?
Hier kommt noch eine hin.
Und dann kann ich das Ganze auflösen und sage ich das also A nicht und
B.
Und jetzt kann ich natürlich hier versuchen, das Ganze
auszumultiplizieren mit den Distributivgesetzen.
Die haben wir ja schon kennengelernt.
Also A und B nicht oder A und A.
Und dann kommt natürlich raus, das Ganze ist dann A und B nicht oder
A.
Und jetzt brauchen wir etwas, das nennen wir Absorption.
Das heißt also mit dem Absorptionsgesetz, das brauchen wir hier
dringend.
Und zwar sagt das ja X oder XY gleich X, diese Absorption.
Und dann bekomme ich hier raus, das ist dann A nicht und B.
Ja, und ich muss gar keine Klammern setzen.
Ich könnte jetzt noch welche setzen und dann wäre das hier hinten
einfach nur noch oder A.
Und dann kann ich das hier wieder mit den Distributivgesetzen
ausmultiplizieren.
Ja, dann kommt dann raus A nicht oder A.
Jetzt brauche ich Klammern.
Und A oder B.
Ja, und hier kann ich jetzt einfach sagen, das ist ja offenbar die
Eins.
Und dann bekomme ich hier einfach raus, das ist also A oder B.
Ja, und das Ganze dann, also ich bleibe mir hier simpel, für A und B.
Ist das soweit klar?
Sind die Fragen soweit?
Ist klar, oder?
Okay, also das heißt, wir konnten das jetzt, wir konnten im Prinzip
mit einem, ja mit sehr ungewöhnlichen Operatoren, konnten wir jetzt
die Standard-Operationen nachbilden.
Was sehr wichtig ist.
Jetzt gibt es eine Tautologie.
Wir haben das schon kennengelernt.
Tautologie war, glaube ich, Anfang letzter Stunde schon dran.
Bedeutet, wann sind denn eigentlich zwei Ausdrücke A und B genau
gleich?
Ja, da können wir uns fragen, da können wir auch sagen, A-äquivalent B
ist eine Tautologie.
Tautologie heißt, es muss immer eine Eins ergeben.
Und das macht ja auch Sinn, wenn ich jetzt zwei bulgische Funktionen
gegeben habe.
Ja, F1, F2.
Und ich frage mich jetzt, sind die beiden eigentlich genau
gleichwertig?
Ist also F1 identisch mit F2?
Und da kann ich auch sagen, ist nicht vielleicht F1-äquivalent F2 eine
Tautologie?
Das heißt, ich bekomme immer nur noch Einsen als Endergebnis.
Und das kann man jetzt in zwei Hinsichten machen.
Wir können sagen, wir bauen uns so eine Funktionstabelle.
Ja, und bei der Funktionstabelle, also jetzt das X ist das F1, das Y
ist das F2.
Ja, und hier X-äquivalent Y, das sollte jetzt immer Eins sein.
Wir sehen, das ist auch so.
Das heißt, bei den Eingangsbelegungen, die wir hier haben, kommt auch
immer das Gleiche raus.
Das heißt, wir haben immer den gleichen Wert am Ausgang.
Das wäre eine Möglichkeit.
Ist aber vielleicht gar nicht so geschickt.
Wir müssten ja die Funktion dann komplett auswerten.
Und das ist bei einer Funktion vielleicht mit zehn Eingangsvariablen
gar nicht so praktisch.
Und dann kann man das Ganze aber auch jetzt machen mit einer
algebraischen Überführung.
Und das will ich mir jetzt nochmal schnell zeigen, wie man das macht.
Und das mache ich jetzt, sage ich mal, sehr explizit.
Und Sie können mal schauen, ob Sie die ganzen Aktionen noch im Kopf
haben.
Also wir wollen doch sagen A und B.
Oder A nicht und B nicht.
Das soll doch gleich sein.
A nicht oder B und A oder B nicht.
Das war ja die Fragestellung.
Dann machen wir das folgendermaßen, dass wir jetzt sagen, wir führen
das wirklich.
Also es gab ja verschiedene Techniken, die haben wir ja schon
teilweise angesprochen.
Ich möchte jetzt einfach wirklich von der linken Seite so lange
umformen, bis ich die rechte Seite bekomme.
Und mit entsprechenden Theorien und Aktionen, die wir schon
kennengelernt haben.
Also A und B oder A nicht und B nicht.
Dann können wir jetzt hier sagen, wir nutzen die Disputivgesetze und
sagen jetzt, das wäre jetzt A und B oder A nicht.
Und das Ganze dann in eckigen Klammern.
Und A und B oder B nicht.
Also die Klammern könnte ich mir auch wieder sparen um das Und.
Haben wir ja gerade diskutiert.
Ich setze die sozusagen nur zur Sicherheit hier rein, weil wir gesagt
haben, wir könnten das Ganze auch dual betrachten.
Und das Ganze machen wir hier mit dem Disputivgesetz A2.
Dann kann ich mich fragen, was mache ich denn damit jetzt?
Jetzt kann ich ja nochmal ausmultiplizieren.
Da kann ich jetzt sagen, das ist ja sowas wie A oder A nicht in
Klammern und B oder A nicht.
Ich hoffe, Sie sehen das.
Und da kann ich auch gleich was vereinfachen.
Kann ich nämlich gleich hier vorne sagen, A oder A nicht gibt halt
immer Eins.
Das heißt, das hier ist eine Eins.
Und jetzt kommt der zweite Term dran.
Jetzt will ich den hier ausrechnen.
Ich will also den Term hier ausrechnen.
Das ist also dann A oder B nicht und B oder B nicht und so weiter.
Das heißt, ich habe hier ein Und.
Dann sage ich dann, wir haben also A oder B nicht und B oder B nicht.
Das Ganze wieder in Klammern.
Und hier hinten, das ist natürlich wieder eine Eins.
Und dann kann ich natürlich jetzt die inversen Elemente nutzen.
Das ist also Eins und B oder A nicht.
Ich habe gesagt, ich mache es sehr explizit.
In Klammern und A oder B nicht und Eins.
Also das heißt, nach hier brauchen wir das Distributivgesetz.
A2.
Hierüber brauchen wir jetzt die inversen Elemente.
Wir haben H4.
Und jetzt wollen wir das dann noch vereinfachen.
Dann kommt er hier wohl raus.
Das ist B oder A nicht.
Und A und B nicht.
Und da haben wir jetzt gesagt, das sind jetzt hier die neutralen
Elemente.
Und das ist H3.
Und jetzt kommt nur noch ein Schritt.
Das Ganze ist jetzt dann A nicht oder B.
Und das Ganze dann und A oder B nicht.
Na gut, jetzt erkennen wir genau das wieder.
Das wäre jetzt das Kommutativgesetz.
Kommutativgesetz A1.
Und damit haben wir natürlich sofort den Ausdruck, den wir eigentlich
erreichen wollten.
Wir haben jetzt also diesen Ausdruck hier unten.
Das ist genau der, den wir eigentlich zeigen wollten.
Damit ist klar, es ist eine Tautologie, es passt.
Ja, wir können die ineinander überführen.
Soweit klar?
Okay, dann kommen wir zu Normalformen.
Normalformen, da können wir jetzt sagen, wir können die Bool'sche
Funktion durch verschiedene Bool'sche Ausdrücke beschreiben.
Und eine Standarddarstellung wäre jetzt, dass wir das UND oder NICHT
verwenden.
Das wäre dann die konjunktive Normalform oder die disjunktive
Normalform.
Mit denen werden wir noch einiges arbeiten.
Und jetzt brauchen wir Literal.
Literal bedeutet, wir haben eine Variable XI oder ihre Negation.
Und das heißt, das Literal kann sozusagen aus den beiden Elementen
bestehen.
Das Literal I.
Und ein Produktterm ist jetzt die Konjunktion von Literalen.
Das heißt also, wir haben einfach hier die Konjunktion von diesen M
-Literalen oder wir haben eine konstante 0 oder 1.
Also ein paar Beispiele, was sind Literale?
Jeder Produktterm kann jetzt so dargestellt werden, dass eine Variable
höchstens in einem Literal vorkommt.
Und wir kommen gleich noch dazu, zu Min-Termen, wo wir dann sagen, es
muss genau einmal vorkommen.
Warum ist das so?
Wenn die beiden doppelt auftauchen, kann ich die mit dem
Idempotenzgesetz streichen, tauchen sie sozusagen jetzt hier gemischt
auf, dann kann ich durch die Negation das Ganze nullen.
Ach ja, hier haben wir schon gleich ein Beispiel mit dem Implikant.
Wenn wir einen Produktterm haben, K, dann heißt der Produktterm
Implikant, wenn er das KY impliziert.
Implikation bedeutet, wenn ich eine Eingangsbelegung habe und K ist 1,
dann soll auch Y1 sein.
Das heißt also, wir haben hier so ein Beispiel, wenn K A und B ist und
Y wäre jetzt A und B oder C, dann impliziert K auch das Y.
Wenn das 1 ist, bekomme ich auch eine 1.
Nicht aber, dass Y2, wenn ich A und B habe und C, kann ja sein, dass
das C sich unkooperativ verhält, dann wird das nicht impliziert.
Das heißt also, ein Implikant einer Boltzscher-Funktion, der heißt
jetzt Minterm, wenn jede Variable der Funktion Y im Implikanten genau
einmal vorkommt.
Das heißt, es muss auch vorkommen, dann sprechen wir von einem
Minterm.
Das wären Minterme, also hier tatsächlich alles kommt vor, also wir
haben eine Funktion mit vier Eingangsvariablen, dann kommen hier zum
Beispiel X1 bis X4 vor, das wäre ein Minterm, das wäre natürlich auch
ein Minterm, das wäre keiner.
Der mag zwar korrekt sein, wir werden doch gleich zu Minimaltermen
oder zu einer Minimalrepräsentation kommen, darum geht es jetzt
erstmal nicht, sondern wir wollen jetzt hier bei den Mintermen
tatsächlich alle Variablen vertreten haben.
Also das wären hier keine.
Und hier kommt ja X3 zweimal vor, insofern wäre das auch kein Minterm.
Eine disjunktive Normalform, die will ich Ihnen jetzt mal kurz
erklären.
Und wir werden dann sehen, durch Dualität können wir auch eine
konjunktive Normalform erklären.
Und ich würde sagen, für die Vorlesung, und das schlage ich Ihnen auch
dringend vor, gucken Sie sich bitte die disjunktiven Dinge an und die
konjunktiven, zum Beispiel Normalform hier, die kommen dann einfach
durch die Dualität heraus.
Das müssen Sie sich nicht extra merken und ich will es auch in der
Vorlesung deswegen gar nicht so vertiefen.
Das machen wir jetzt vertieft und den Rest mache ich gleich ziemlich
schnell.
Wenn wir eine bool'sche Funktion haben, das heißt also ein Y von X1
bis Xn, dann nennen wir den bool'schen Ausdruck für diese Funktion
disjunktive Normalform, wenn wir eine disjunktive Verknüpfung von eben
diesen Mintermen haben.
Und Minterme, wie gesagt, wo ich alle Variablen ja wirklich in diesem
Term drin habe.
Das Ganze sind 2 hoch n Stück, es geht von 0 bis 2 hoch n minus 1,
also wir haben 2 hoch n Minterme.
Warum?
Weil wir eben 2 hoch n Belegungen haben können.
Und die Konjunktionen sollten nicht gleich sein.
Das heißt also, wir wollen hier wirklich exklusiv unterschiedliche
Konjunktionen Ki und Kj haben.
Beispiel.
Das hier ist eine disjunktive Normalform.
Das hier ist offenbar nicht in disjunktiver Normalform.
Warum?
Wir haben hier hinten so einen komischen Term, das ist keine richtige
Konjunktion.
Das heißt, das A, B nicht, enthält noch nicht mal alle Variablen, da
fehlt ja das C.
A, B, C und C, A, B sind äquivalent, haben wir gesagt, das wollen wir
verbieten, das passt also nicht.
Das haben wir ja gerade gesagt, das ist keine reine Konjunktion.
Ja, was sind hier Minterme?
Offenbar ist das hier ein Minterm und das hier hinten macht keinen
Sinn.
Das sind keine Minterme, damit ist es keine disjunktive Normalform.
Das B nicht C, enthält nicht alle Variablen, ist auch kein Minterm.
Die beiden sind äquivalent, das heißt, den kann ich streichen.
Und das ist sowieso hier kein Minterm, also nur der eine hier ist ein
Minterm.
Wir werden auch gleich sehen, was so ein Minterm auszeichnet.
Die Frage ist jetzt, wir möchten jetzt mal so einen Term überführen in
eine disjunktive Normalform.
Und da können wir ja folgendes machen.
Wir können ja sagen, wir fassen das hier zusammen, das ist natürlich
mit dem Idempotenzgesetz.
Wir haben hier das Idempotenzgesetz, damit können wir das
zusammenfassen.
Und wir brauchen jetzt gleich nochmal die Absorption.
Wir können ja sagen, das ist auf jeden Fall jetzt dann A, B nicht C
oder A, B nicht C oder B nicht C.
So, und jetzt können wir sagen, die beiden sind gleich, die können wir
schon mal weglassen.
Das heißt, wir haben also A, B nicht C oder B nicht C.
So, und jetzt gibt es da eine Technik, wie die wir gerade schon
angesprochen haben.
Wenn wir sagen,
Moment, das korrigieren.
Also wir haben hier A, B nicht C.
Ich nenne das jetzt hier Y, nenne das X und nenne das wieder X und
habe dann wieder meine Absorption.
Das wäre also dann Y, X oder X gleich X.
Das wäre mein Absorptionsgesetz.
Dann kann ich doch jetzt sagen, dann habe ich hier B nicht C.
So, und jetzt kommt ein Trick, den Sie sich einfach einprägen sollten,
weil den werden wir noch mehrfach brauchen.
Und der ist, glaube ich, ziemlich hilfreich.
Sie können jetzt einfach immer so ein A oder A nicht oder B oder B
nicht und sowas können Sie immer ergänzen.
Weil das ja im Prinzip jetzt hier genau mal 1 wäre.
Das heißt, wir haben so ein A oder A nicht.
Das kann ich hier sofort ergänzen, mal B nicht C.
Und das Ganze wäre dann A, B nicht C oder A nicht, B nicht C.
Und damit haben wir sofort unsere entsprechend gewünschte Form auch
hergeleitet.
Ist das klar soweit?
Das heißt, Sie können einfach das A, A nicht ergänzen.
Jetzt mit der Dualität, da würde ich jetzt sagen, machen wir das eben
schnell.
Da ist nicht viel dahinter.
Wir sagen einfach, alles das, was wir bisher kennengelernt haben,
können wir jetzt per Dualität einfach übersetzen.
Zum Beispiel in statt disjunktiven Normalformen haben wir einfach
konjunktive Normalformen.
Und man ersetzt jetzt einfach die Veroderung durch eine Verundung, 0
durch eine 1, der Rest bleibt gleich.
Und dann können wir das natürlich auch hier sehen, auch bei den
handtätigen Aktionen bleibt das Ganze dann natürlich erhalten.
Und da haben wir jetzt ein Implikat statt einem Implikanten.
Ich denke, da muss man nicht lange darüber diskutieren.
Das impliziert halt einfach D nicht, impliziert Y nicht.
Wir haben einen Max-Termen statt einem Min-Termen.
Ich denke, da muss man auch nicht lange darüber diskutieren.
Also genau das gleiche Dual.
Hier haben wir entsprechende Beispiele dafür.
Wir haben eine konjunktive Normalform statt einer disjunktiven
Normalform.
Das heißt, bei der disjunktiven Normalform hatten wir eine Veroderung
von Produkttermen.
Hier haben wir eine Verundung von entsprechenden Summentermen.
Das ist, glaube ich, klar.
Und jetzt ist die Frage, wir können jetzt in einer Funktion mit n
Variablen bis zu 2n Min-Terme haben, wegen der 2n Belegungen.
Für n gleich 3 haben wir also 8 Min-Terme und 8 Max-Terme.
Die werden wir nicht typischerweise voll ausschöpfen, weil wenn wir
die ausschöpfen, bedeutet das ja, wenn wir alle Min-Terme hätten, wäre
es eine Funktion, die nur Einser ausgibt.
Alle Max-Terme würde bedeuten, wir hätten eine Funktion, die gibt nur
Nuller aus.
Das heißt, typischerweise werden wir irgendwo so dazwischen drin
liegen.
Und das sollten wir uns aber trotzdem nochmal klar machen, dass wir
hier diese Dualität haben.
Ich schreibe das nochmal da dran.
Also wir haben hier diese Dualität, das ist ganz wichtig, dass wir die
hier haben.
Und ja, die Min-Terme, was produzieren die?
Die Min-Terme, die produzieren Einser.
Die Min-Terme produziert also jeweils eine Eins und so ein Max-Term
produziert jetzt Nuller.
Und das ist also ganz wichtig, dass wir das hier haben.
Sie können also jetzt, das werden wir gleich sehen, eine Funktion
komplett beschreiben durch Min-Terme und durch Max-Terme.
Okay, gehen wir mal einen Schritt weiter.
Warum heißen die überhaupt so?
Man kann sich natürlich fragen, warum heißen die eigentlich Min- und
Max -Terme?
So ein Min-Term, wenn man einen einzelnen Min-Term betrachtet,
bedeutet ja, der wird genau für eine einzige Belegung eins.
Deswegen ist sozusagen die minimale Aussage, der wird genau nur für
eine Belegung eins.
Das heißt, der hat die maximale Anzahl an Nullen und die minimale
Anzahl an Einsen.
Deswegen Min-Term.
Beim Max-Term genau das Gleiche, der ist genau für eine Belegung Null
und hat also die maximale Anzahl an Einsen und die minimale Anzahl an
Nullen.
Deswegen nehmen wir den Max-Term.
Und Sie können sich jetzt einfach aussuchen, und das ist eben wieder
dual, wollen Sie jetzt eine Funktion darstellen durch eine Veroderung
von Min-Termen oder eine Verundung von Max-Termen.
Und beides ist in Ordnung.
Und jetzt wollen wir uns mal anschauen, wenn wir so eine disjunktive
oder eine konjunktive Normalform haben, sind die eindeutig.
Das ist wichtig, wir haben also eine eindeutige Darstellung.
Wir werden sehen, die haben auch Nachteile, weil die vielleicht eben
nicht minimal sind, aber sie sind immerhin als Normalform eindeutig.
Und schauen wir uns mal sowas an, was wir jetzt hier haben, A mal B
nicht oder C.
Was kommt da raus?
Das ist natürlich nicht eindeutig, weil ich könnte jetzt sagen, ich
nehme einfach A, B nicht oder C, negiere das zweimal und dann bekomme
ich ja wieder mit den demorgenschen Gesetzen, bekomme ich jetzt raus,
dass ich habe A nicht oder B und C und das Ganze nicht.
Das heißt also, wir können sagen, diese beiden Formen sind nicht
eindeutig.
Ich konnte das ja jetzt beliebig ineinander umrechnen.
Also das heißt, die sind nicht eindeutig.
Jetzt wollen wir mal sagen, wie komme ich denn jetzt auf eine
eindeutige Form, wenn ich das A, B nicht oder C habe.
Und jetzt wieder der Trick.
Und der Trick ist gar nicht so schlecht, den sollten Sie sich mal
einprägen.
Und jetzt sage ich, ich mache eine rein algebraische Umformung.
Wir werden das gleich noch formalisieren.
Mit Hilfe dieses Challengen-Entwicklungssatzes.
Aber das ist schon mal gar nicht so schlecht, was Sie jetzt hier
sehen.
Also eine algebraische Umformung, die Ihnen immer hilft.
Also eine disjunktive Normalform.
Wie machen wir denn das?
Wir sagen also, wir haben Y ist A, B nicht.
Und jetzt fehlt mir da ein C.
Jetzt nehme ich ein C mit rein.
Dann sage ich das also und C oder C nicht.
Das darf ich ja machen.
Oder C und bei dem C fehlen mir jetzt dummerweise aber A und B.
Dann sage ich also A oder A nicht und B oder B nicht.
Und Sie sehen, mit diesem total simplen Trick können Sie das Ganze
jetzt auflösen.
Sie rechnen jetzt einfach mal aus, was denn da rauskommt mit den
Distributivgesetzen.
Also da haben wir ja A, B nicht, C.
Oder A, B nicht, C nicht.
Jetzt sortiere ich aber gleich.
Dann haben wir sowas wie A, B, C.
Oder A, B nicht, C.
Oder A nicht, B, C.
Oder A nicht, B nicht, C.
So und jetzt, der taucht schon mal auf.
Dieser hier taucht schon auf.
Das heißt, da dürfen wir jetzt mit den Idempotenzgesetzen sagen, den
lassen wir einfach weg.
So und dann kann ich da jetzt weiterrechnen.
Und da sehen Sie das Ergebnis schon unten stehen.
Das Ganze wäre jetzt, wenn ich das weglasse, diesen Term, der zweimal
auftaucht, wäre das also A nicht, B nicht, C.
Oder A nicht, B, C.
Oder A, B nicht, C nicht.
Oder A, B nicht, C.
Oder A, B, C.
Und das Ganze ist eindeutig.
Da gibt es nur diese eine Form nach der Definition, die wir bisher
gebracht haben.
Und das Ganze kann ich jetzt machen auch analog für die konjunktive
Normalform.
Kann ich natürlich genauso machen.
Da spricht nichts dagegen.
Und die beiden Ergebnisse sind hier unten angegeben.
Das heißt, Sie sehen, das wäre die disjunktive Normalform, wie gerade
besprochen, eindeutig.
Und das wäre die konjunktive Normalform.
Und jetzt wäre die Frage, können wir das formalisieren?
Können wir damit noch etwas einfacher umgehen?
Und die Frage war ja gerade, wenn ich jetzt eine Funktion habe, die
jetzt beliebig irgendwie gegeben ist, wie kann ich die denn jetzt
überführen in eine konjunktive oder disjunktive Normalform?
Und ich habe Ihnen ja gerade schon diesen Trick gesagt.
Ja gut, der Trick ist jetzt natürlich so, dass er relativ mühsam wird,
wenn Sie viele Variablen haben.
Aber trotzdem, warum nicht?
Der ist nicht schlecht.
Und das Ganze kann man jetzt ein bisschen formalisieren, indem man
sagt, man nimmt diesen Chain Engine Entwicklungssatz.
Der funktioniert so, wir entwickeln nach einer Variablen xi.
Das heißt also, wenn ich jetzt drei Variablen habe, kann ich zum
Beispiel nach der Variable x2 entwickeln.
Die wird jetzt in der Funktion auf den Wert 1 gesetzt.
Dann wird der entstehende Term konjunktiv mit xi verknüpft.
Genauso habe ich dann sozusagen auf der anderen Seite die Variable in
der Funktion mit dem Wert 0 und ich verknüpfe konjunktiv mit xi quer.
Kann man natürlich auch wieder dualisieren, wenn wir gleich sehen.
Das heißt, der Chain Engine Entwicklungssatz sagt nichts anderes, als
wenn ich jetzt eine Funktion habe, y ist f von x1 bis xn, dass ich
sagen kann für eine beliebige Variable darin, zum Beispiel xi, dass
ich sagen kann xi und f mit xi 1 gesetzt oder xi nicht und f und dann
die entsprechende Variable 0 gesetzt.
Da kann man sich fragen, warum ist das denn so?
Und da gibt es einen ganz trivialen Beweis, der ist so trivial, dass
Sie wahrscheinlich gleich sich wundern, wieso man das überhaupt
diskutieren muss.
Aber ich glaube, wir sollten es mal diskutieren.
Also, wir schauen uns mal diesen Entwicklungssatz gerade an.
Wir setzen aber jetzt für das xi 1 oder 0 ein.
Und zwar jetzt einfach durch einsetzen können wir jetzt ganz schön
diesen Satz beweisen.
Wir sagen also, wenn ich jetzt eine Funktion hätte, die hat n
Variable, also x1 bis xi und für das xi setze ich 1 ein.
Und danach gehe ich wieder bis xn.
Und dann kann ich doch jetzt einfach sagen, wenn das xi gleich 1 ist.
Ich habe ja gerade gesagt, ich verknüpfe konjunktiv die Variable mit
der Funktion, wo ich das xi gleich einsetze.
Dann hätte ich doch sowas wie 1 und dann jetzt einfach das f von x1
bis xi gleich 1 bis xn.
Setzen wir das jetzt nochmal vorsichtshalber in Klammern.
Ich habe ja gesagt, die Klammern müssten wir dann nicht machen, aber
das ist ja nicht schlecht, wenn wir sie trotzdem machen.
Oder, dann haben wir die 0.
Das heißt also, wir nehmen jetzt den Wert xi gleich 1, den müssen wir
dann negieren, also wäre dann die 0.
Und f von x1 bis xi gleich 0 in dem Fall, bis xn.
Na gut, und dann zeigt sich jetzt, wenn sie es einmal gesehen haben,
sollten sie sofort sagen, ach das ist ja so trivial, hätten wir gar
nicht diskutieren müssen.
Ich hoffe, das ist der Effekt.
Aber zwei Minuten früher hätten sie es vielleicht nicht gesagt.
Aber sie sehen doch jetzt, dass natürlich hier das 0 und das fliegt
jetzt raus.
Das heißt, bleibt nur genau das stehen.
Und das haben wir hier ja schon stehen gehabt, also das heißt, so
selbsterfüllend.
Wir haben also jetzt f von x1 bis xi gleich 1 bis xn.
Also es stimmt.
Die Frage ist halt, gilt es jetzt auch für 0?
Das heißt also, wir nehmen jetzt f von x1 bis xi gleich 0 bis xn und
dann machen wir das gleiche.
Jetzt müssen wir ja sagen, wir nehmen die Variable, negieren die.
Jetzt setzen wir ja xi gleich 0.
Das heißt also, wir müssen jetzt hier 0 für die Originalvariable
haben.
So, jetzt haben Sie eine Frage.
Haben Sie eine Frage?
Also das heißt, Sie nehmen jetzt einfach das xi gleich 0, setzen das
hier entsprechend ein, verunden das jetzt natürlich wieder mit der
entsprechenden Funktion und bekommen jetzt raus, wir haben also 0 und
f von x1 bis xi und jetzt hier wieder gleich 1 bis xn.
Und das Ganze wieder in Klammern.
Und dann verodern wir das wieder.
Und jetzt natürlich, dass xi gleich 0 negiert, gibt eine 1 und f von
x1 bis xi gleich 0 bis xn.
Und das gibt ja wieder, und das haben wir hoffentlich auch erwartet,
gibt dann wieder, weil wir hier eine 0 haben, gibt dann wieder diesen
Term, das heißt also die 1 und kann ich ja weglassen.
Das heißt also, der Term bleibt über.
Das heißt, ich habe jetzt hier wieder f von x1 bis xi gleich 0 und so
weiter bis xn.
Das ist mein Ergebnis.
Und wie gesagt, ich hoffe, dass das ein klarer und einfacher Beweis
ist.
Und jetzt machen wir ein Beispiel.
Wir wollen jetzt mal ein Beispiel verdeutlichen an diesem hier, wie
man den vorgeht.
Wenn man jetzt sagt, wir haben sowas wie a, b nicht c oder a nicht b
nicht oder bc.
Wie gehe ich jetzt vor?
Und das ist gar nicht so einfach.
Da wird man ganz schön viel schreiben müssen.
Wir werden jetzt mal entwickeln nach a, b, c in der Reihenfolge.
Das heißt, wir fangen mal an mit der Entwicklung mit dem a.
Ich mache das immer, wonach ich entwickle, mache ich rot.
Das heißt, wir haben jetzt ein rotes a.
Und dann bekomme ich, jetzt muss ich für das a einsetzen, die 1.
Ich habe ja sozusagen das a in der Entwicklung.
Dann brauche ich jetzt in der Funktion für jedes a, was auftaucht,
eine 1.
Das heißt, ich habe jetzt sowas wie 1, b nicht c.
Oder 1 nicht, b nicht oder bc.
Da taucht kein a auf.
Und jetzt haben wir hier wieder ein a.
Und zwar ein a nicht.
Und jetzt setze ich wieder ein.
In die entsprechende Funktion haben wir dann eine 0, b nicht c.
Oder 0 nicht, was eine 1 ist, b nicht oder bc.
Das wäre die erste Entwicklung.
Und jetzt können wir uns da ein bisschen das Ganze vereinfachen.
Und ich streiche Ihnen sozusagen immer dieses und an, damit Sie nicht
durcheinander kommen, bei wem wir gerade sind.
Weil wir jetzt sukzessive, wie ein Baum, das Ganze erweitern werden.
Das heißt also, wir haben jetzt hier ein a.
Und dann können wir jetzt hier oben vereinfachen.
Wir haben jetzt hier b nicht c.
Das ist hier eine 0.
Das heißt, wir haben b nicht c und bc.
Also das heißt, wir können hinschreiben, b nicht c oder bc.
Dann wieder unser oder.
Und dann kommt hier ein a nicht.
Und dann haben wir hier hinten noch stehen, b nicht oder bc.
Weil wir hier ein 0 nicht hatten.
Das heißt, das b nicht bleibt stehen oder das bc.
Und jetzt können wir weiterentwickeln.
Jetzt mache ich die Entwicklung weiter und jetzt werde ich die nächste
Variable rot schreiben.
Das heißt, wir haben jetzt ein a mal.
Und jetzt haben wir als rote Variable ein b mal.
Und jetzt muss ich praktisch bei dem b in diesem Term einsetzen.
Eine 1 und gleich bei dem b nicht eine 0.
Das heißt, ich bekomme jetzt 1 nicht c oder 1 c.
Und jetzt habe ich hier wieder ein b nicht.
Und dann bekomme ich ein 0 c oder 0 c.
Und jetzt die Veroderung.
Ich habe ja gesagt, die streiche ich Ihnen mal an, welche das ist.
Das wäre jetzt diese hier, die korrespondieren zueinander.
Das heißt, diese Veroderung korrespondiert zu der, dass wir das klar
haben.
Und dann geht es weiter in der nächsten Zeile.
Da habe ich ein a nicht mal.
Und jetzt bekomme ich wieder ein b und dann ein 1 nicht oder 1 c oder
dann wieder ein b nicht.
Und ich glaube, jetzt wird es ziemlich klar.
Ein b nicht und jetzt bekomme ich dann halt ein 0 nicht oder 0 c.
Das heißt also einfach hier eingesetzt, es gibt ja 0 nicht oder 0 c.
Und dann kann ich das so weiter treiben.
Dann kann ich jetzt sagen, das Ganze ist jetzt vereinfacht.
a mal und jetzt kann ich einfach alles mal rausschmeißen, was
offensichtlich ist.
a mal b c oder b nicht c.
Und dann hier wieder mein oder, was ich gerade gekennzeichnet habe
oder a nicht.
Dann b c oder b nicht.
Und dann gehen wir weiter.
Wir brauchen ein bisschen mehr Platz.
Jetzt kann ich das nochmal entwickeln, jetzt nach c.
Dann wäre die Frage, wie entwickle ich nach c.
Das heißt, ich habe jetzt ein a mal große Klammer b.
Jetzt kommt die kleinere Klammer.
Und dann haben wir jetzt ein c.
Und bei dem c bekomme ich jetzt noch eine 1 oder c nicht 0 oder b
nicht.
Das war ja von gerade, das b nicht.
Und dann bekommen wir hier noch ein c mal 1 oder c nicht mal 0.
Moment, jetzt muss ich das hier noch schön in rot schreiben, sonst
passt das nicht.
Oder c nicht mal die 0.
Dann hätten wir schon mal den ersten Term abgedeckt.
Und jetzt kommt wieder unser oder.
Das war ja dieses gekennzeichnete oder.
Dann haben wir jetzt hier noch ein a nicht.
Und Sie sehen, wie kompliziert das dann wird.
Haben wir dann b mal.
Und jetzt bekommen wir hier wieder ein c mal 1 oder c nicht.
Auch da muss ich wieder gucken, dass ich das in rot mache.
Oder c nicht mal 0.
Oder b nicht mal c mal 1.
Oder c nicht.
Jetzt möchte ich das mal ein bisschen schöner machen.
Also hier die 1.
Und dann oder c nicht mal die 1.
Und dann kann ich das ausrechnen.
Kann das Ganze sozusagen ausmultiplizieren.
Und dann bekomme ich raus a, b, c.
Und das sehen Sie jetzt hier.
Ich kann das jetzt einfach hier der Reihe nach auslesen.
Also a, b, c.
Oder dann a, b, c nicht.
Fällt weg, weil da ein 0 drin steht.
Also a, b nicht, c.
Der fällt wieder weg.
Und so weiter kann ich also diese ganzen Terme auslesen.
Also a, b, c.
Oder a, b nicht, c.
Oder a nicht, b, c.
Oder a nicht, b nicht, c.
Oder a nicht, b nicht, c nicht.
Und das sind jetzt die Terme, die wir da rausbekommen.
Moment,
ich glaube, ich verstehe Ihre Frage nicht.
Ich glaube, ich habe auch gerade ein Menü eingeblendet, was ich gar
nicht haben will.
Sagen Sie es nochmal.
Das ist doch dieser Term, ja?
Der hier.
Mal 1 würde doch bedeuten, dass ich das c nicht stehen lasse.
Oder was ist Ihre Frage?
Ich will doch diesen Term hier haben, ja?
Den hier.
Den, den, den.
Das wäre der hier, ja?
Moment, da gehen wir gleich mal zurück.
Moment, das können wir gleich vielleicht mal versuchen hier.
Ich glaube, ich bin etwas gehemmt jetzt gerade mit dem Menü.
Das kriegen wir sofort hin.
Eine Sekunde.
Ich kann jetzt nicht mehr klicken.
So.
Was wir doch machen wollen ist...
Klappt das?
Okay, ich versuche mal, ob ich jetzt zurückgehen kann, ja?
Genau.
Und wir wollen doch jetzt hier unten einsetzen, ja?
Wir wollen doch jetzt bei dem c einsetzen.
Wir wollen jeweils das c nach vorne schreiben.
Und wenn ich das c positiv nach vorne schreibe, bekomme ich in jedem
Term eine Eins für das c.
Und sonst eine Null.
Und deswegen bekommen wir jetzt...
Ah ja, hier ist es wieder, ja?
Genau.
Bekommen wir jetzt hier sozusagen die Eins hin, ja?
Also ich glaube, das ist ganz vernünftig.
Und dann bekommen wir, wenn ich die alle zusammenzähle, dann haben wir
hier das a, b, c.
Ja, a, b nicht c.
Das wäre der und so weiter.
Können wir die alle zusammenzählen, ja?
Gibt es weitere Fragen?
Okay.
Jetzt können wir Folgendes machen.
Wir können sagen, das war ja wie ein Baum.
Wir konnten im Prinzip, ja, indem wir sukzessive das Ganze erweitert
haben, konnten wir jetzt wie durch so einen Baum durchlaufen.
Und jetzt können wir uns das mal hinmalen, wenn wir sagen, wenn wir
nach allen Variablen entwickeln, wir fangen bei a an, gehen dann nach
b und c und so weiter, dann können wir jetzt im Prinzip Folgendes
machen.
Wir können jetzt sagen, dass wir hier oben eine Entwicklung machen.
Hier haben wir eine Entwicklung nach dem a.
Dann haben wir hier, und Sie sehen, jetzt haben wir natürlich dann
schon zwei Äste mehr, ja, eine Entwicklung nach dem b.
Und hier unten haben wir eine Entwicklung nach c.
Und jetzt können wir ja doch ganz schön ablesen, ja.
Wir können jetzt eigentlich diese ganzen Pfade von oben nach unten
verfolgen.
Wir können jetzt sagen, wenn ich so eine Pfade habe, a, b, c, ja, dann
bekomme ich bei dieser 1 hier unten tatsächlich raus, y ist a, b, c.
Bei der 0 kommt nichts raus, ja, das heißt also bei der nächsten 1
hätte ich jetzt a, b, nicht, c.
Hätte ich also hier a, b, nicht, c.
Dann bei der nächsten 1 wäre es dann a, nicht, b, c.
Und bei der wäre es dann a, nicht, b, nicht, c, a, nicht, b, nicht, c,
und dann a, nicht, b, nicht, c, nicht.
Und die kann ich jetzt alle verodern und dann habe ich damit schon
meine Funktion entsprechend etabliert, ja.
Das heißt, ich kann mir das vorstellen wie so eine Baumentwicklung.
Das heißt, dieser Schengen-Entwicklungssatz, den kann ich mir als so
eine Art Baumentwicklung vorstellen, ja.
Was ja, glaube ich, ganz witzig ist.
Und ja, erst mal dazu fragen.
Jetzt könnt ihr natürlich fragen, ich kann ja auch bei c anfangen,
klar.
Wir können auch bei c anfangen, ja.
Dann entwickeln wir erst nach c, ja, oder erst nach b und so weiter.
Aber das ist ja jetzt im Prinzip gar nicht mal die Frage.
Sie bekommen halt unterschiedliche Bäume, aber das Ergebnis ist immer
das Gleiche.
Das Ergebnis ist ja eindeutig.
Das waren jetzt eindeutige Formen, ja, diese disjunktive Normalform
und die konjunktive Normalform und so weiter, die waren jetzt
eindeutig.
Und jetzt kommen wir dann im nächsten Schritt zu Formen, die nicht
mehr eindeutig sind, wo wir Minimalität haben wollen.
Das machen wir gleich, ja.
Erst mal noch ganz kurz, Dualität, auch das werde ich jetzt wieder
ganz schnell machen.
Sie können immer wieder durch die Dualität jetzt auch einen ständigen
Entwicklungssatz herleiten in konjunktiver Form.
Das ist trivial, ja.
Normalformen können wir jetzt so deuten, dass wir sagen, so ein
Minterm entspricht genau einer Zeile in unserer Funktionstabelle, ja.
Also genau eine Eins wird jetzt durch so ein Minterm realisiert.
Oder ein Maxterm realisiert eben eine Null.
Das heißt also, das ist ganz wichtig, dass Sie jetzt ganz simpel eine
Funktion darstellen können, indem Sie einfach die Minterme aufzählen
oder die entsprechenden Maxterme.
Das ist ganz wichtig, ja.
Und das können wir jetzt also so machen.
Wir hätten jetzt zum Beispiel hier, ich klicke die mal alle auf, wir
hätten eine Funktion, die kann ich jetzt mit den Mintermen, mit diesen
vier Mintermen, beschreiben.
Und das wäre dann so gegeben.
Da hätte ich eine Funktion, die kann ich genau mit den vier Mintermen
beschreiben.
Oder, ich hätte eine Funktion, die kann ich jetzt, oder die gleiche
Funktion, die kann ich jetzt mit den vier Maxtermen beschreiben.
Das heißt, ich hätte genau das.
Das ist jetzt ein schön gewähltes Beispiel, klar, aber trotzdem,
glaube ich, ist es sinnvoll, dass man sagt, man kann jetzt entweder
mit vier Mintermen oder mit vier Maxtermen diese Funktion alternativ
beschreiben.
Und die Frage ist jetzt, wenn ich mich jetzt darauf einige, wie ich
die Reihenfolge angebe, dann kann ich ja eigentlich nur die Nummern
angeben.
Das heißt, ich kann jetzt sagen, zum Beispiel hier so etwas wie 0, 3,
4, 7, das wäre meine Funktion.
Das heißt, ich kann die Funktion alleine in Mintermen
charakterisieren.
Oder in Maxtermen sage ich, das ist 1, 2, 5, 6, hätte ich die
entsprechenden Maxterme.
Damit ist meine Funktion eindeutig charakterisiert, wenn wir uns nur
darauf einigen, warum wir sozusagen jetzt hier die Sortierung
vornehmen.
Und ich glaube, das ist ganz witzig.
Das heißt, wir können so eine verkürzte Schreibweise anführen, dass
wir sagen, nur die Indizes sind wichtig.
Und dann kann ich sagen, das Y wäre so etwas wie MinT, wie ich gerade
gesagt habe, oder MaxT von den entsprechenden Maxtermen, die ich dann
damit angeben möchte.
Und die Reihenfolge der Variablen wäre jetzt von rechts gelesen ABC.
Ist das klar?
Damit kann ich jetzt eine Funktion eindeutig, wenn vielleicht auch
nicht besonders effizient, darstellen.
Weil es eben eine Normalform ist.
So, jetzt bin ich eigentlich mit meinem Stoff schon für heute fast
durch, aber jetzt machen wir noch ein paar Dinge, weil wir eine
Vorlesung weniger haben in diesem Semester, werde ich versuchen, so
ein bisschen was aufzuholen.
Dann machen wir jetzt mal die Minimalformen.
Und zwar jetzt nicht Normalformen, sondern Minimalformen.
Und da können wir uns jetzt überlegen, wir möchten möglichst kurze
Bullshit -Ausdrücke haben.
Gerade haben wir gesagt, wir möchten in der Normalform alle Variablen
in den entsprechenden Produkttermen drin haben usw.
Das werden wir jetzt nicht mehr haben.
Wir wollen jetzt eine technische Realisierung einer Schaltung
durchführen können, mit möglichst geringen Kosten.
Und wir werden jetzt genau wie zu den Normalformen, werden wir jetzt
haben eine disjunktive Minimalform und eine konjunktive Minimalform.
Nicht mehr Normalform.
Und wie funktioniert das?
Wir haben also eine Bullshit-Funktion, die ist also y ist x1 bis xn,
jetzt von links gelesen, und wir haben Kostenfunktionen für die
Verundung und für die Veroderung.
Und so ein Ausdruck, der ist jetzt in so einer disjunktiven
Minimalform oder auch DMF.
Ja, wenn er jetzt eine Disjunktion von Konjunktion wäre, und jetzt
müssen Sie mal genau hingucken.
Wir haben jetzt hier vorne eine Konjunktion l11 bis l1k, dann kommen
ein paar Veroderungen und dann geht das bis lm1 bis lmj.
Das heißt, wir haben also m Veroderungen und jeweils hier dann k bis j
Verundungen.
Und das heißt, ich kann jetzt sagen, die Literale enthalten also diese
entsprechenden Terme und meine Kosten sind jetzt die Veroderungen, das
heißt, ich muss diese ganzen Veroderungen nehmen, das sind m Stück,
und dann die Verundungen in den einzelnen Verundungstermen, die muss
ich auch nochmal aufsummieren.
Das kann man jetzt sehr schön machen, wenn man sich mal ein Beispiel
anschaut.
Wir hätten jetzt so eine disjunktive Minimalform und wir sagen jetzt,
wir hätten als Kosten die Anzahl der Gatter.
Und wenn ich jetzt sage, ich habe so ein Term y1, ist a nicht b oder a
b nicht, dann habe ich ja sowas wie psi y1 das wäre ja, jetzt muss ich
schauen, die Veroderungen, da haben wir zwei Terme.
Das heißt, wir haben also hier eine 2.
In jeder Verundung habe ich nochmal zwei Terme, also 2 plus 2 plus 2,
das wären jetzt hier 6.
Das heißt also, dieser Ausdruck hätte 6 als Kostenmaß und die Frage
wäre jetzt, wenn ich jetzt also das wäre disjunktiv Minimal.
Die Frage ist jetzt, ist dieser Term disjunktiv Minimal?
Nein, weil hier könnte ich jetzt sagen, ich hätte so ein psi y2.
Wenn ich das jetzt mal naiv mache, dann wäre das ja auch wieder 6.
Ja, genau wie oben.
Aber ich kann ja jetzt hier das a, also ich kann das b rausklammern,
dann bleibt da stehen a nicht oder a, dann bleibt hier b übrig und für
das b bekomme ich jetzt hier als psi y2 bekomme ich jetzt hier den
Wert 1.
Ja, das heißt also, das war keine disjunktive Minimal Form, was wir
hier hatten, sondern diese ist hier kleiner.
Und wir werden sehen, das wird uns also noch ein paar Mal zwicken.
Wie können wir jetzt eigentlich eine disjunktive Minimal Form auch
wirklich generieren?
Das wird uns noch ein paar Stunden kosten.
Wir werden also dazu ein paar Dinge kennenlernen, KV-Diagramme und so
weiter.
Wie man denn jetzt überhaupt so eine Minimal Form bekommt.
Konjunktive Minimal Form, ich gesagt, machen wir wieder analog.
Wir machen das also wirklich dual.
Da müssen wir gar nicht drüber nachdenken.
Hier vertauschen wir einfach und und oder.
Wir vertauschen praktisch alles genau dual.
Diese ist jetzt hier in konjunktiver Minimal Form.
Das können wir nochmal hinschreiben.
Da können wir jetzt sagen, dass natürlich hier das psi y1, das ist
jetzt wieder 2 plus 2 plus 2, das ist 6.
Das ist in konjunktiver Minimal Form.
Währenddessen dieses hier nicht in konjunktiver Minimal Form ist.
Denken Sie mal darüber nach, warum nicht.
Frage ich Sie gleich mal.
Das hat doch jetzt hier auf jeden Fall den Aufwand, y2 wäre ja 3 plus
1 plus 2 plus 2, das ist ziemlich offensichtlich, wäre 8.
Und wie kann ich das Ganze jetzt vereinfachen?
Wie kann ich den Term hier vereinfachen?
Sehen Sie das?
Das müssten Sie eigentlich bisher, ja.
Aber warum?
Was muss ich hier tun?
Wir können ja hier vorne was vereinfachen, aber was ist die
Begründung?
Sehen Sie das?
Ja, aber Absorption.
Wir können wieder die Absorption verwenden.
Das heißt, es wäre jetzt hier A nicht und A nicht ist A nicht und dann
oder A nicht und C und dann kann ich im Prinzip hier ausklammern und
das heißt das können wir jetzt auch entsprechend hinschreiben, dann
kann ich das als A nicht schreiben, so wie Sie gesagt haben und dann
das B oder C bleibt stehen und das heißt von den Kosten her ist es
jetzt ja so, dass das hier unten natürlich kleiner ist, also das y2
ist also 2 plus 1 plus 2 in den Gatterlängen.
Das wäre jetzt also 5 und damit ist das also eine kürzere Form und die
Frage ist jetzt halt, wie komme ich drauf?
Typischerweise würde man vielleicht nicht so ohne weiteres drauf
kommen und deswegen brauchen wir dafür noch entsprechende Formalismen.
Das werden wir auch noch machen.
Aber ich denke, das ist soweit klar, dass man sagt, wir wollen eine
Minimalform.
Okay.
Es sind nicht eindeutig, es kann jetzt mehrere disjunktive und
konjunktive Minimalformen geben für die gleiche Funktion.
Wir sehen hier unten gibt es also zwei Beispiele, das ist die gleiche
Funktion, die sehen aber unterschiedlich aus.
Die sind sogar von der Komplexität genau gleich.
Das heißt also, mit beiden wären wir zufrieden und auch das werden wir
noch sehen, dass wir dann eben gucken müssen, wie komme ich denn auf
diese beiden Formen.
Wenn ich sage, ich mache das disjunktiv oder konjunktiv, dann werden
die Kosten typischerweise unterschiedlich sein.
Also beispielsweise hier, wenn ich jetzt sage, ich habe so eine etwas
kompliziertere Kostenfunktion, zweimal K plus 1, also wo K die Anzahl
der Gatter ist, dann habe ich hier einmal eine disjunktive
Minimalform, die hätte die Kosten 22 und die konjunktive Minimalform,
die ja eigentlich vernünftig aussieht, hätte aber die Kosten 26.
Das heißt also, auch da müssen wir überlegen, ja, wie kommen wir
eigentlich am Ende drauf?
Das heißt also, das mal als Motivation, wie rechne ich mir so was her?
Ja, wie komme ich jetzt auf eine optimale Darstellung von einer
Schaltung mit geringen Kosten?
Also hier ist offenbar so, dass ich mich sogar wirklich für die
disjunktive Minimalform entscheiden muss, um da die geringsten Kosten
zu bekommen.
Okay.
Also vielleicht hier als Anmerkung, das wird uns jetzt wie gesagt ein
paar Stunden noch beschäftigen, das Auffinden einer Minimalform ist
nicht trivial.
Wir werden typischerweise suboptimale Lösungen haben, Heuristiken
vielleicht sogar verwenden.
Und wie geht man eigentlich vor?
Wir suchen Implikanten oder Implikate und wir haben gerade gesehen,
auch da muss man sich entscheiden, was man eigentlich davon nehmen
möchte, mit einer möglichst geringen Anzahl von Literalen.
Und dann suchen wir daraus die möglichst geringe Anzahl von Implikaten
oder Implikanten aus, um dann aus einer Disjunktion oder Konjunktion
die Funktion Y zu realisieren.
Das wird uns wie gesagt, wir werden drei Verfahren kennenlernen dazu
und das wird uns ein bisschen beschäftigen.
So, jetzt würde ich sagen, ich nutze die restliche Zeit noch, um Ihnen
eine Kleinigkeit noch mitzugeben, die wir noch dringend brauchen
werden und zwar die Funktionsdarstellung im Würfelkalkül.
Das springt jetzt so ein bisschen raus aus der Vorlesung.
Das heißt also, wir haben hier so einen kleinen Sprung, aber wir
brauchen das später noch und deswegen ist es ganz gut, wir machen das
einfach mal jetzt.
Würfelkalkül, was bedeutet das?
Wir sagen, wir haben Produktterme, die haben wir gerade kennengelernt.
Bei Produkttermen können wir jetzt sagen, dass wir einen sogenannten
Würfel haben.
Und ein Würfel, der hat entsprechend Einträge, die aus der Menge
kommen, 0, 1 oder Strich.
Und Strich bedeutet, es könnte 0 oder 1 sein.
Ja, und das Ganze natürlich als kathesisches Produkt, also mit Hoch-N.
Und das Ci ist jetzt 0, falls das Literal xi quer in K vorkommt.
1, wenn das xi vorkommt und Strich, wenn die Variable nicht vorkommt.
Dann bedeutet es ja, wenn wir gleich Beispiele sehen, dass ja beides
möglich ist.
Und das sehen wir jetzt hier gleich.
Ja, wir haben jetzt die Variablen x1 bis x6 und wir haben jetzt so ein
Produkt, wir haben K, der ist jetzt x2, x3 nicht, x5 nicht, x6.
Und dem ordnen wir jetzt den Würfel zu.
x1 taucht nicht auf, kann beides sein.
x2 taucht auf, positiv, gibt eine 1.
x3 gibt eine 0.
x4, ja, ist ein Strich, taucht nicht auf.
x5 ist eine 0, x6 ist eine 1.
Ja, damit kann ich im Prinzip jetzt alles beschreiben.
Und die Frage ist jetzt halt, was hilft mir das?
Ich kann jetzt sagen, dass wenn ich ein n-Tupel habe, das an keiner
Stelle so einen Strich hat, dann ist ein 0-dimensionaler Würfel also
ein Punkt.
Ein n-Tupel, was an m Stellen, also m kleine gleich n, einen Strich
besitzt, das ist ein m-dimensionaler Würfel.
Und für n gleich 3 können wir das sehr schön darstellen.
Dann haben wir nämlich diesen Würfel, das bedeutet, wir haben hier auf
den Ecken jeweils die entsprechenden Minterme stehen.
Dazwischen haben wir praktisch also zum Beispiel 00 Strich, bedeutet
ich kann hier eine 1 oder eine 0 haben.
Das heißt also, diese Kante beschreibt die Zusammenfassung dieser
beiden Minterme.
Und jetzt kann man das weiter treiben, zum Beispiel mit Strich, 1
Strich oder sowas wie Strich, Strich, Strich, bedeutet das wäre der
gesamte Würfel.
Das heißt also, die acht möglichen Minterme sind jeweils die Ecken.
Dazwischen haben wir eine Kante und dann habe ich sechs Flächen, die
ich daraus bilde und der gesamte Kubus hat natürlich Strich, Strich,
Strich.
Der wäre damit komplett beschrieben.
Und da werde ich fragen, dann nenne ich ja sowas, was nur Striche
enthält, das nenne ich Universum.
Wenn ich m kleiner gleich n habe, habe ich einen m-dimensionalen
Unterraum.
Das ist ebenfalls ein Würfel, der eben kleiner ist und eingebettet ist
in diesen großen Würfel.
Und ich habe die Minterme und zum Beispiel der Würfel 1 Strich 1
entspricht diesen beiden Mintermen.
Also x1, x2, x3 und x1, x2 nicht und x3.
Damit kann ich also rechnen.
Und das brauchen wir eben.
Und dann kann ich jetzt Funktionen darstellen.
Das heißt also, die Eckpunkte sind die Minterme und ich kann jetzt ein
Konsensusverfahren, das werden wir noch kennenlernen, zur Minimierung
anwenden und damit spanne ich jetzt einen Unterraum auf.
Wenn ich zum Beispiel sage, ich habe 1, 1, 1 und 1, 0, 1 dann kann ich
den natürlich so darstellen, weil ich hier einen Strich habe.
Es ist ja hier eine 1 oder eine 0.
Und jetzt können wir so etwas definieren, wie man enthält etwas oder
man überdeckt etwas.
Das ist wichtig.
Ein Würfel enthält einen anderen Würfel, also das heißt b, sozusagen
Teilmenge von a.
Sieht man hier ein Beispiel.
Der enthält den.
Und eine Überdeckung ist jetzt, wenn ich jetzt verschiedene Würfel
habe, dann überdecken die vielleicht Würfel, die sogar solche Striche
enthalten.
Haben wir gleich ein Beispiel.
Und so eine Überdeckung ist als Budgetfunktion eine Disjunktion von
Produkttermen.
Und das heißt, wir sehen das jetzt mal hier.
Dieser Würfel in dem Beispiel enthält den.
Diese Würfelmenge, diese zwei Stück, die überdecken den.
Völlig klar.
Und wir brauchen eine Schnittmenge von zwei Würfeln.
Wir wollen also sagen, wann schneiden sich denn zwei Würfel.
Und wenn ich jetzt sage, ich habe diese Würfel a und b, ja mit a1 bis
an, b1 bis bn, dann möchte ich jetzt sowas wie c1 bis cn bekommen.
Und wenn jetzt a gleich 1 ist und b 1 oder eben ein Strich oder das b
ist 1 und das a ist 1 oder ein Strich, dann bekomme ich 1.
0 und 0 ein Strich und 0 und 0 ein Strich, bekomme ich dann 0.
Strich, Strich gibt ein Strich.
Ist ja auch klar.
0 oder 1 kann vorkommen.
Dann bekomme ich hier auch wieder 0 oder 1 raus.
Sonst existiert die Schnittmenge nicht.
Und das heißt, kann man sich jetzt hier mal vorstellen.
Ich mache mal diese drei Beispiele.
Was passiert hier?
Wenn ich jetzt 1 Strich, Strich 1, 1, 1 habe.
Ist ziemlich einfach.
Dann bekomme ich hier 1, 1, 1.
So haben wir es ja gerade definiert.
Bei dem hier, bekommen wir jetzt hier 0, Strich, 0.
Hier unten haben wir einen Widerspruch.
Das funktioniert nicht.
Hier bekommen wir zwar vielleicht was raus.
Hier bekommen wir was raus.
Aber hier bekommen wir nichts raus.
Also 1 und 0 sind nicht kompatibel.
Das heißt, die Schnittmenge existiert hier einfach nicht.
Und jetzt sind wir auch durch.
Das war sozusagen die letzte Folie, die ich hier zeigen wollte.
Gibt es Fragen zum Würfelkalkül?
Okay.
Dann würde ich sagen, am nächsten Dienstag gibt es eine Übung zu den
Normalformen.
Und nächsten Donnerstag sehen wir uns wieder hier im Audimax.
Dann gibt es sozusagen die Fortsetzung der Vorlesung.
Also vielen Dank.
Tschüss.