Klassische boolesche Funktionen und Schaltkreise

This video belongs to the openHPI course Einführung in das Quantencomputing - Teil 2. Do you want to see more?

Klassische boolesche Funktionen und Schaltkreise

Time effort: approx. 18 minutes

An error occurred while loading the video player, or it takes a long time to initialize. You can try clearing your browser cache. Please try again later and contact the helpdesk if the problem persists.

Scroll to current position

00:00ein herzliches Willkommen meine Damen und Herren zum Kurs Grundlagen
00:03des Quantencomputings Teil zwei und jetzt kommen wir zu klassischen
00:08booleschen Funktionen und Schaltkreisen wir gucken zunächst
00:13mal wo wir im Kurs eigentlich sind es geht jetzt darum wie
00:18man klassische Funktionen auf Quantencomputern berechnen kann
00:23für diejenigen die schon wissen an die anderen kriegen es erklärt
00:25in dem Kurs man kann die Disjunktive Normalform einer Funktion
00:29auf Quantencomputer übersetzen was ist der Hintergrund dieses
00:34Videos es wird oft gesagt dass Quantencomputer Dinge
00:39können die klassische Computer nicht können oder schneller
00:42können so lax gesprochen dass Quantencomputer mehr können
00:46als klassische Computer und man kann sich natürlich fragen
00:51na ja wenn die mehr können dann müssen sie doch zumindestens
00:54das können was klassische Computer können klassische Computer
00:59berechnen sogenannte boolesche Funktionen klassische Computer
01:03rechnen auf Wahrheitswerten es kommen irgendwelche Bits die
01:06Wahrheitswerte haben rein und es kommt dann ein oder mehrere
01:10Bits die auch Wahrheitswerte haben raus das machen klassische
01:13Computer und man fragt sich können das Quantencomputer auch
01:17und wenn ja - wie das Ziel dieses Videos ist ihnen zu zeigen
01:26dass es klassische Computer können und wie sie es im Prinzip
01:29können muss gleich ein Disclaimer vorwegschicken in der Praxis
01:33wird es anders gemacht das was hier vorkommt sind was ich ihnen
01:36jetzt zeigen werde sind mit Sicherheit nicht die besten Schaltkreise
01:39für klassische Funktionen aber für diejenigen unter ihnen
01:43die sagen naja ich kenne doch so boolesches UND ja was zwei Inputbit
01:47nimmt und eins ist wenn beide eins sind wie würde das auch
01:51in Quantenschaltkreisen gemacht für diejenigen ist das jetzt
01:55hier die Information wie man es im Prinzip machen kann also klassische
02:03boolesche Funktionen und Schaltkreise klassische Computer berechnen
02:06klassische boolesche Funktionen Input und Output bestehen aus
02:11den Wahrheitswerten null und eins und in diesem ganzen Video
02:15hier werden wir auch nur über klassische Funktionen berechnen
02:19das heißt das Thema Quanten, Superposition und so können sie
02:22für den Moment mal weglassen wir reden nur von Nullen und
02:25Einsen und bei Quantencomputern sind es natürlich die Basis-
02:28Zustände eines QuBits die im Zustand null oder eins sind
02:35okay auf dem klassischen Computer der kriegt also hier als Beispiel
02:40kriegt der drei Inputbits und er liefert ein Outputbit die
02:46Inputbits können im Zustand x1 x2 x3 000 001 010
02:51und so weiter bis eins eins eins sein und viele
02:54von ihnen sagen natürlich das sieht schon fast aus wie Basis-
02:56Zustände eines Quantenregisters aus drei QuBits stimmt auch
03:00ok aber klassisch gedacht ist das so zu lesen dass wenn
03:03zum Beispiel in der Zeile x eins ist null x zwei ist eins x drei
03:07ist null dann soll das Ergebnis null sein die Funktion hat keine
03:12besondere Bedeutung sind einfach nur zur Illustration
03:15das was ich ihnen hier zeige ist eine Wertetabelle einer Funktion
03:20hier steht für jeden Input x eins x zwei x drei was der Output
03:24der Funktion ist die Darstellung als Wertetabelle ist
03:29immer möglich bei einer Funktion aber kann sehr lang sein also
03:36sie sehen schon hier wenn drei
03:40wenn drei normale Bits reingehen dann gibt es acht mögliche
03:45Inputs und ganz allgemein wer möchte hält kurz das Video an
03:49und überlegt sich was passiert wenn bei zehn oder bei n Input-
03:54Möglichkeiten ja bei n Inputbits hat die Tabelle zwei hoch n Zeilen
04:03bei zehn Inputbits also 1024 und bei 100 Inputbits ist die Tabelle
04:09schon so lang dass man das überhaupt nicht mehr hinschreiben
04:11kann aber wir wollen nur wissen wie man die Funktion im Prinzip
04:15berechnen kann und im Prinzip kann man die Tabelle hinschreiben
04:20kann man natürlich sagen ja also ich brauche nicht nur einen
04:22Outputbit ich brauche doch mehrere dann hat man halt
04:27mehrere Funktionen hier kommt ein Beispiel drei Input Bits
04:32wieder die Wertetabelle hat also 8 Zeilen und wir haben jetzt zwei
04:36Output Bits hier x eins plus x drei
04:42das linke Bit und x eins plus x drei das rechte Bit zum Beispiel
04:45null plus null ist null linkes Bit ist null rechtes Bit ist null
04:52dann hat man halt wenn sie möchten können sie Tabelle nachvollziehen
04:54ich möchte jetzt nicht vorlesen aber das heißt wenn man mehr
04:58Output Bits braucht dann heißt das man hat einfach mehr Funktionen
05:02das uns aber nur darum geht ganz grundsätzlich über die Funktionen
05:05zu sprechen reicht es zu betrachten was man hat wenn man nur
05:08ein einziges Outputbit braucht klassische Computer verschlüsseln
05:15alles was sie tun in die Form von solchen Wertetabellen letztlich
05:18die Input Bits können natürlich irgendetwas kodieren
05:21also zum Beispiel Kontostände Routenplan-Probleme Optimierungs-
05:24Probleme alles und die Output Bits die kodieren dann die Antwort
05:31auf die Fragestellung also das Modell mit der Wertetabelle
05:38boolescher Funktionen (n Input-Bits, ein Output-Bit) ist ein allgemeines Modell dafür,
05:42welche Funktionen von klassischen
05:45Computern überhaupt berechnet werden können mehr können
05:48klassische Computer nicht und wir wollen
05:51als Fernziel sehen wie man das jetzt so eine Wertetabelle auf
05:54den Quantencomputer bringt und dafür gucken wir zunächst
05:57einmal wie man eine Wertetabelle auf den klassischen Computer
06:00bringt also wir beschränken uns darauf
06:04wie man prinzipiell mit klassischen Schaltkreisen boolesche Funktionen
06:08berechnen kann die durch eine Wertetabelle gegeben sind also
06:12gegeben also eine Wertetabelle Frage: Welcher klassische Schaltkreis
06:17berechnet die Funktion die Basisbausteine Basis-Gatter
06:23eines klassischen Schaltkreises sind drei Stück NICHT englisch
06:29NOT, UND engl AND, und ODER engl OR fortgeschrittene Hörer
06:35sagen wahrscheinlich da gibt es auch noch andere Modelle das
06:37stimmt auch aber wir betrachten jetzt mal das das ist ein
06:40sehr weit verbreitetes Modell okay was macht das NICHT
06:46es kriegt ein Bit x eins das kann null oder eins sein und
06:50es liefert ein anderes Bit ein Outputbit das ist das Gegenteil
06:54also eins oder null es klappt das Bit der klassische Schaltkreis
07:02dafür wird so dargestellt hier ist es Input Bit x eins
07:06und das wird dann mit einem NOT genommen und
07:09ja gequert verneint negiert in sein Gegenteil umgedreht wenn
07:17sie solche Bilder mit klassischen Schaltkreisen noch nie gesehen
07:20haben macht nichts das werden sie im Laufe der Zeit einfach
07:22so verstehen was macht das UND das UND kriegz zwei Bits als Input x1 und x2
07:30und sie können 00 01 10 11 sein
07:36und als Output liefert es den Funktionswert der genau dann eins ist
07:39wenn die beiden eins waren x eins ist eins und x zwei ist eins dann
07:44ist der Output eins ansonsten ist der Output null
07:48der klassische Schaltkreis der das berechnet sieht so aus hier
07:52kommen die beiden Input Bits und dann haben wir hier ein
07:56UND-Gatter das ist ein UND-Gatter das greift sich x eins und greift sich
08:00x zwei und macht daraus ein UND so wird es symbolisiert als
08:06Schaltkreis das ODER das macht das was sie erwarten würden
08:14wahrscheinlich es kriegt auch zwei Input Bits x1 und x2
08:18sie können wieder null null null eins eins null oder eins eins
08:21sein und ODER ist wenn mindestens eins von den x-en eins war
08:26also x eins ist eins oder x zwei ist eins oder beides, es ist nicht
08:30das Exklusiv ODER wo genau eins eins sein muss sondern na ja
08:33mindestens eins davon soll halt eins sein von den Inputs der klassische
08:37Schaltkreis dazu sieht so aus hier kommen wieder x eins und
08:41x zwei die werden abgegriffen von dem ODER-Gatter und das ODER-Gatter
08:45wird symbolisiert mit so größer gleich eins also mindestens
08:48eins von den Inputs muss eins sein dann kommt das ODER raus
08:55und das Ziel ist es jetzt mit diesen drei Bausteinen
09:00jede beliebige Wertetabelle zu bauen mit UND, ODER und NICHT
09:06will man eine beliebige boolesche Funktion bauen das machen
09:10wir in zwei Schritten
09:14der Schritt eins ist wir hoffen mal dass die Funktion eine ganz
09:17spezielle Funktion ist die bei genau einem Input eins ist und
09:21sonst überall null also hier sind Beispiel wir haben
09:27Funktion mit drei Input Bits und das auch der Output ist überall
09:31null außer an einer einzigen Stelle hier da wo x1 null ist und x2 ist
09:37null und x3 ist eins das die Funktion eins ansonsten überall
09:44soll die Funktion heißen Minterme und die kann man mit
09:48UND und NICHT bauen das geht so eigentlich übersetzt ist das
09:54was ich gerade gesagt habe es muss x eins null sein
10:00mit anderen Worten das negierte von x eins muss eins sein und
10:04das muss x2 null sein also das negierte von x zwei muss eins sein und
10:09x drei muss eins sein genau das ist dieser Ausdruck nicht x1
10:12und nichtig x2 und x3 wenn wir in den Ausdruck diese
10:18Zeile einsetzen kommt tatsächlich eins raus ist ja alles erfüllt
10:22und wenn wir irgendeine andere Zeile einsetzen dann ist eins
10:27von den drei Dingern von den UNDs nicht erfüllt das heißt
10:29das Ganze UND ist null also man sieht wenn die Funktion bei
10:39genau einem Input eins ist dann kann man sie bauen
10:42mit UND und NICHT ist nochmal ein anderes Beispiel haben wir
10:47wieder eine Funktion mit drei Variablen die ist jetzt hier
10:50an der Stelle eins wo x 1 eins ist und x2 und
10:53und x3 sind beide null und wenn sie möchten
10:57halten sie kurz das Video an und bauen für sich den Minterm
11:01was steht hier oben wie kann man die Funktion nicht
11:05in der langen Wertetabelle sondern mit dem kurzen Ausdruck
11:08mit UND und NICHT darstellen
11:18haben sie es gemacht naja man muss einfach das hinschreiben was
11:23hier steht x eins muss eins sein und x zwei muss null sein
11:27also x zwei quer muss eins sein x eins und x zwei quer und
11:32x drei quer also sie sehen bei den Mintermen geht es
11:42sogar mit UND und NICHT man braucht gar kein ODER wir haben
11:46schon gesehen dass wir boolesche Funktionen die an genau einer
11:49Stelle in der langen Wertetabelle eins sind mit UND und ODER
11:51bauen können mit UND und NICHT und ODER
11:54also bauen können mit und und oder und nicht oder
11:59braucht man gar nicht was machen wir jetzt mit einer Funktion
12:03die an mehreren Stellen eins ist wie baut man jetzt die klassischen
12:08Schaltkreise für Minterme ich zeige ihnen ein Beispiel
12:11dann sehen sie wie es geht wir haben den Minterm der
12:17an einer Stelle eins ist an der Stelle wo x eins null ist x2 null ist
12:26und x drei eins ist hier ist es und da ist der Minterm eins
12:29und so sieht der klassische Schaltkreis aus man nimmt x eins
12:33das wird negiert und muss dann eins sein x zwei wird auch negiert
12:38und muss dann eins sein dann wird es und gebildet hier in diesem
12:42Draht kommt nur eins raus genau dann wenn die beiden negiert
12:46eins ergeben das heißt wenn x1 nicht und x zwei nicht
12:50beide eins sind dann nimmt man x drei und verbindet es noch
12:54mit und mit dem Ergebnis aus den ersten beiden was da
12:57rauskommt ist genau die Funktion die eins ist wenn x eins
13:03quer als x1 negiert und x zwei negiert und x3 als wenn sie
13:07alle drei eins sind ein Beispiel für sie ist jetzt der andere
13:14Minterm den wir vorhin betrachtet haben x eins ist eins x
13:17zwei und x drei jeweils null da ist die Funktion eins ansonsten
13:20null und wenn sie möchten halten sie kurz das Video an und
13:23malen für sich selber den Schaltkreis wie sieht der Schaltkreis
13:28aus der besteht aus nicht und und der diesen Minterm
13:33berechnet x eins muss eins sein
13:46x zwei negiert muss auch eins sein und dann muss auch noch
13:51x drei negiert eins sein und herauskommt x eins und nicht
13:55x zwei und nicht x drei jetzt haben wir gesehen wie man
13:59mit nicht und und boolesche Funktionen bauen kann
14:06die an genau einer Stelle eins sind und die meisten Funktionen sind
14:10aber an mehr als an einer Stelle eins und jetzt kommt der zweite
14:16Schritt wie man das macht Funktionen die bei mehr als einem
14:22Input “1” sind, sind ODERs von Mintermen wird sich herausstellen
14:27wir gucken uns zum Beispiel an haben wir eine Funktion mit drei Input
14:32Bits und die ist jetzt an zwei Stellen eins da wo vorhin unser
14:36einer Minterm eins war und aber auch noch da wo vorhin unser anderer
14:40Minterm eins war also nochmal zur Erinnerung unser
14:46erster Minterm war dies gab es hier eins und der zweite
14:50Minterm war das und er ist hier eins und wir hätten jetzt gerne
14:54eine Funktion die es halt eins wenn der Input dieses und erfüllt
14:59oder dieses und erfüllt und sie sehen schon oder heißt wir
15:06müssen die beiden Minterme verodern das heißt wirklich
15:09so und dann kommt die Funktion raus versuchen sie es mal versuchen
15:16sie mal diese Funktion als ja so als Ausdruck mit Unds und
15:21oder hinzuschreiben bevor ich weitermache
15:36ja die Funktion die wir suchen ist das oder aus diesemn Mintermen
15:42Funktion ist eins wenn der Input diesen Minterm erfüllt
15:47entweder diesen aber oder diesen beide gleichzeitig kann er
15:50nicht erfüllen die Darstellung einer booleschen Funktion als oder
15:59über ihre ganzen Minterme heißt Disjunktive Normalform
16:02der Funktion und ich hoffe sie haben Gefühl dass es tatsächlich
16:07immer geht man nimmt die Wertetabelle
16:09guckt wo ist die Funktion eins schreibt den inzwischen
16:13entsprechenden Minterm hin mit und und nicht und alle Minterme
16:19werden dann verodert und dann hat man einen Ausdruck wie
16:22diesen her der die Funktion darstellt mit und oder und nicht als
16:29Schaltkreis im Beispiel sieht auch so aus man bildet die
16:33Minterme und bindet dann das oder über die Minterme also
16:38hier haben wir die Minterme gebildet die beiden und jetzt
16:41verteilt ein oder gebildet und dann hat man die Funktion berechnet
16:44mit und oder und nicht wenn mehr Minterme eins gewesen wären
16:48hätte man hier noch mehr oders anhängen müssen die
16:54disjunktive Normalform hat nicht die minimale Anzahl von Gattern
16:58also das ist eine Art und Weise wie man Funktionen berechnen
17:01kann ganz sicherlich nicht die optimale Art aber hier geht
17:04es darum zu sehen wie es überhaupt geht und im nächsten Video
17:08werden uns anschauen wie man jetzt diesen Schaltkreis hier
17:14auf Quantenschaltkreise übersetzt