Einführung in die Theoretische Informatik


Fachbuch, 2002

122 Seiten


Leseprobe

Inhaltsverzeichnis

0. WARUM SOLLTEN WIR UNS МДШШЕЕГШМ INFORMATIK
0.1 Einige Bemerkungen zu den Begriffen "Theorie" und "Praxis"
0. 2 Bemerkungen zur Theoretischen Informatik

1. GRUNDLAGEN
1.1. Die Grundbegriffe der Aussagelogik
1.2. Mengen
1.3. Grundlagen der Algebra

2 EINFÜHRUNG IN DIE BOOLESCHE ALGEBRA
2.1. DEFINITION UND EINFACHE EIGENSCHAFTEN
2.2. INTERPRETATIONEN DER BOOLESCHEN ALGEBRA
2.2.1. DIE AUSSAGEALGEBRA
2.2.2. DIE MENGENALGEBRA
2.2.3. DIE SCHALTALGEBRA

3·ALGORITHMEN
3.1. DER INTUITIVE ALGORITHMUSBEGRIFF
3.2. DIE TURINGMASCHINE ALS PRÄZISER ALGORITHMUSBEGRIFF
3.3. ALGORITHMISCHE ENTSCHEIDBARKEIT
3.4. GRENZEN DER ALGORITHMISIERUNG: ALGORITHMISCHE NICHTENTSCHEIDBARKEIT
3.5. EINFÜHRUNG IN DIE KOMPLEXITÄTSTHEORIE
3.5.1. PROBLEMSTELLUNG
3.5.2. KOMPLEXITÄTSMASSE
3.5.3. DIE KLASSEN P UND NP
3.5.4. NP-VOLLSTÄNDIGKEIT

LITERATU RHIN WEISE

Vorwort

Die Theorie einer Wissenschaft beschreibt und erklärt die allgemeinen Strukturen, die dieser zugrunde liegen und die die jeweiligen konkreten Anwendungen logisch rechtfertigen. Für die Informatik nennen die grundlegenden Standardwerke (siehe Literaturhinweise) hierzu im Wesentlichen die Formalen Sprachen, die Automatentheorie, sowie hierauf aufbauend die Entscheidungs- und Komplexitätstheorie.

Ziel der vorliegenden Abhandlung ist es, eine Einführung in die schwierige und komplexe Thematik zu geben. Dabei werden hauptsächlich folgende Ziele angestrebt.

1. Den Leser mit den wesentlichen Denk- und Schlussweisen, so wie sie in der Theoretischen Informatik üblich sind vertraut zu machen.
2. Die wichtigsten Ergebnisse der Entscheidungs- und Komplexitätstheorie zu vermitteln.
Hierdurch sollte der Leser dann im Stande sein, sowohl die allgemeinen Ergebnisse der Informatik als auch sein eigenes Tun kritisch zu reflektieren. Darüber hinaus aber auch in der Lage sein, sich die weiterführende Literatur selbständig anzueignen.

Im einzelnen haben wir hierzu folgenden Weg gewählt: Nach einer kurzen allgemeinen Betrachtung über Theorie und Praxis wurden die wichtigsten Grundlagen aus der Logik, Mengenlehre und Algebra zusammengestellt. Diese sind, zumindest vom Inhalt her aus der Schule bekannt, so dass sich hier eine erste Möglichkeit bietet, mit der unter erstens angesprochenen Schlussweise vertraut zu werden.

Um den Zusammenhang zur Thematik nicht all zu sehr aus den Augen zu verlieren, bietet sich im weiteren der konkrete Bezug zur Boole'sehen Algebra und dann als Anwendung die Schaltalgebra an. Für das zweite genannte Ziel haben wir uns exemplarisch auf den Algorithmusbegriff beschränkt. Einerseits wird hiermit auch der "reine" Praktiker täglich konfrontiert, andererseits glauben wir, dass das genannte Ziel hierdurch am "anschaulichsten" vermittelt werden kann. Wer darüber hinaus an Detailfragen interressiert ist, wird auf die weiterführende Literatur verwiesen.

Die Ausarbeitung und Gestaltung der vorliegenden Abhandlung übernahm Herr Rauhut, für die Auswahl und die Richtigkeit des Inhaltes zeichnet Herr Dr. Schlageter verantwortlich.

Heilbronn, im September 2001

T. 0. Rauhut

Dr. W. Schlageter

0. Warum sollten wir uns mit Theoretischer Informatik beschäftigen?

0. 1 Einige Bemerkungen zu «Jen Begriffen "Theorie" und "Praxis".

Wir verstehen unter einer Theorie ein System von Sätzen, die in einem bestimmten wissenschaftlich begründeten Zusammenhang stehen. Konkret wird sich diese auf gewisse Elemente bzw. Fakten beziehen» wobei die Aussagen hierüber mehr oder weniger logisch verknüpft; sind. So analysieren wir in der Physik die Bewegungen von Körpern» die diese unter dem Einfluß» bestimmter Kräfte ausführen. Dabei ergeben sich die Bewegungsgleichungen aus dem allgemeinen Newton ' sehen Kraftgesetz (Körper fallen unter dem Einfluß der Gravitation gemäss der Gleichung s— g/2 * t2 ).

Wir werden nun eine Theorie als umso leistungsfähiger ansehen, je mehr Pakten des betreffenden Problembereichs durch sie erklärt werden. Besonders eindrucksvolle Beispiele finden wir in der Physik: Die Maxwell'sehen Gleichungen erklären das Licht als eine elektromagnetische Welle und erfassen somit das bis dahin getrennte Gebiet der Optik als einen Teil der Elektrodynamik.

Als weiteres Kriterium für die Aussagefähigkeit einer Theorie gilt» in wie weit sie in der Lage ist; zukünftige Ceschehensabläufe vorauszusagen, "Savoir pour prévoir!" (A. Comte[1] ). Auch hier liefert wieder die Physik bewundernswerte Beispiele: 1931 sagte W. Pauli (1900-1958) auf Grund theoretischer Überlegungen die Existenz eines Elementarteilchens, des Neutrinos, voraus und beschrieb dessen Eigenschaften. 1956 wurde es dann tatsächlich in exakt dieser Form entdeckt.

Eine Theorie wird nun die genannten Forderungen umso besser erfüllen, je iweniger konkrete Elemente sie grundsätzlich enthält» anders gesagt: je abstrakter sie in ihrer Anlage ist. Denn sie soli ja gerade für prinzipiell Neues offen sein. So wußte George Boote (1815-1 §64) natürlich nichts von elektronischen Schaltungen, trotzdem beschreibt seine Algebra deren Operationen. Allerdings bedeutet nun gerade dieser hohe Grad von

Abstraktion für denjenigen» der sich in eine solche Theorie neu einarbeitet, ein nicht unbeträchtliches Hindernis und fordert neben dem entsprechenden intellektuellen Vermögen ein grobes Mab an Beharrlichkeit und Konsequenz.

Es ist somit verführerisch, mit dem britischen Ökonomen R. F. Harrod (*1 938) zu sagen: "Stop talking and get on with the job!" und sich der Praxis zuzuwenden. Verstehen wir hierunter allgemein jedes konkrete Handein im Dasein eines bestimmten Lebensvollzuges, so zeigt es sich aber, dass eine derartige Einstellung zu kurz greift. Denn jedes solches Handeln setzt eine bestimmte Theorie, zumindest in einem gewissen Umfang, voraus. Als Robinson auf seine Insel verschlagen wurde hat er beim Bau seiner ersten Hütte sich irgendeine Theorie der Statik zugrunde gelegt. Vermutlich keine sehr gute! Als seine Hütte zusammenbrach wird er sich für seine nächste einen verbesserten Ansatz überlegt haben, bis er schließlich glaubte, über die für ihn bestmögliche Theorie zu verfügen. Damit war er dann in der Lage, bei Bedarf schnell und ohne grössere Komplikationen sich einen neuen Bau zu erstellen. In der Tat: Kein konkretes Handeln geschieht planlos. Auch die einfachste Form der Problemfindung, der Versuch und Irrtum kann nie theorielos erfolgen: Der Versuch erfolgt nicht "blind", sondern nach Maßgabe allgemeiner Regeln, der Irrtum kann nur an Hand eines Kriteriums, das einer Theorie entstammt, überprüft werden.

Es erhebt sich die Frage, inwieweit der Handelnde sich seiner Theorie bewusst sein soll? Der Delphin, bei dem die Gesetze der Strömungslehre ideal realisiert sind, weiss nichts von Physik. Der Mond braucht die Gesetze der Astronomie nicht zu kennen, um seit jeher seine Bahn perfekt durchlaufen zu können. Genügt aber diese Auffassung für den aufgeklärten Menschen? Aristoteles (*384 v. Chr. f322 v. Chr.) sagt, der Baumeister stehe höher als der Arbeiter, denn jener kenne die Gründe seines Tuns, dieser nicht! Natürlich können wir nicht in jedem Augenblick und in jeder Situation das Rad quasi neu erfinden; diejenigen Vorgänge aber, die uns fundamental bestimmen, sollten wir zumindest exemplarisch durchschauen. Hinzu kommt auch wieder ein durchaus praktisches Argument: wer neue Probleme lösen will, wer offen sein will für andere Aufgaben, der kann dies sinnvoll nur tun, wenn er das Beziehungsgeflecht in dem diese stehen durchschaut, wenn er also bewußt über eine Theorie verfügt.

0. 2 Bemerkungen zur Theoretischen Informatik

Wir wollen die obigen allgemeinen Überlegungen in Bezug zur Theoretischen Informatik setzen und diese im Zusammenhang, mit dem Begriff des Algorithmus exemplarisch erläutern:

Es dürfte klar sein, daß hiermit einer der zentralen- Begriffe der Informatik angesprochen ist. Es sollte demzufolge zur "Allgemeinbildung" eines Informatikers gehören, dass er einen Begriff mit dem er quasi täglich arbeitet, theoretisch durchdrungen hat Bedenken wir nun, dass hierbei sämtliche nur irgendwie denkbare Algorithmen erfasst werden sollen, so wird verständlich, dass die präzise Fassung schließlich einen hohen Grad an Allgemeinheit aufweisen muss.

Hierbei schliessen sich dann sofort zwei Fragen an, die sowohl von größtem theoretischen wie auch praktischen Interesse sind:

1. Sind sämtliche Probleme durch einen Algorithmus entscheidbar bzw. berechenbar?
2. Falls ein Problem durch einen Algorithmus entschieden werden kann, erfolgt die Berechnung mit einem vertretbaren Aufwand?

Die erste Frage ist Gegenstand der algorithmischen Entscheidbarkeit, die Zweite führt zur Komplexitätstheorie. Man erhält hierbei überraschende Antworten, die mit dem weitverbreiteten Glauben an die Allmacht des Computers unvereinbar sind.

Neben dem grundsätzlichen philosopisch-theoretischen Interesse an diesen Problemen dürfte aber auch der eingefleischteste Praktiker die Notwendigkeit einer Lösung der selben empfinden. Es zeigt sich dann, dass eine exakte Lösung eben jenen präzisen Algorithmusbegriff erfordert, den die Theorie erarbeiten muss.

Aufgaben:

1. ) Beschreiben Sie die theoretischen Überlegungen Robinsons beim Bau eines Kanus. Welche Phänomene können durch diese Theorie eventuell noch erklärt werden? Welche Prognosen gestattet sie möglicherweise?
2. ) Nehmen Sie Stellung zu der These: "Es gibt keine theoriefreie Beobachtung".
3. ) "Die Wahrheit im Rahmen einer Wissenschaft ist nur innerhalb einer Theorie entscheidbar". Erläutern Sie diesen Satz.

1. Grundlagen

1.1. Die Grundbegriffe der Aussagelogik

Die Logik ist die Lehre vom folgerichtigen Schliessen. Als ihr Begründer gilt Aristoteles, der erkannt hat*, dass. hierbetgewisse&hlussr€î§eln a uf treten, die. unabhängig von der Semantik sind und mit denen formal analog wie bei den Zahlen operiert werden kann.

- Aussage

Unter einer Aussage verstehen wir einen Satz, von dem entscheidbar ist, ob er wahr oder falsch ist.

Bemerkung:

Wir kümmern uns dabei um die philosopisch schwierige F'rage nach der Wahrheit als solcher nicht. Ebensowenig um das Problem, wie die Wahrheit eines Satzes konkret festgestellt werden soll. Tatsächlich liegt hier eine ausserordentlich komplexe Problematik vor: Was bedeutet Wahrheit an sich? Einschränkend können wir beispielsweise zwischen theoretischer und empirischer Wahrheit unterscheiden. Offenbar ist die erste re abhängig von der jeweiligen Theorie. Der Satz: "Die Gleichung x[2] + 1 = 0 ist unlösbar" ist in der Theorie der reellen Zahlen wahr, in der Theorie der komplexen Zahlen falsch. "Die Masse ist unabhängig von der Geschwindigkeit" ist in der Newton'sehen Mechanik wahr, in der Einstein'sehen falsch. Empirische Wahrheit ist letztendlich überhaupt nicht exakt festzustellen: Nach n bestätigenden Experimenten ist prinzipiell nie auszuschliessen, dass das (n+1 )-te ein gegensätzliches Verhalten zeigt.

Demzufolge setzen wir ganz allgemein fest:

Abbildung in dieser Leseprobe nicht enthalten

Bemerkung:

Die Situation ist vergleichbar mit den Zahlen, wenn wir lediglich deren Werte betrachten und von den konkreten Objekten ("Äpfel", "Birnen") abstrahieren!

- Operatoren

Ähnlich wie wir mit Zahlen formale Operationen durchführen können (4 ordnen wir -4 zu, aus 3 und 5 bilden wir die eindeutig bestimmte Zahl 3 + 5) definieren wir Operationen mit Aussagen,

Einstelliger Operator:

Abbildung in dieser Leseprobe nicht enthalten

Offenbar ordnet die Negation der Aussage den "entgegengesetzten" Wahrheitswert zu.

Man beachte: Der Operator bestimmt allgemein den Wahrheitswert der hierdurch definierten neuen Aussage.

Zweistellige Operatoren:

Abbildung in dieser Leseprobe nicht enthalten

Bemerkung:

Die Konjunktion benötigen wir stets dann, wenn wir ausdrücken wollen, dass die aus den ursprünglichen Aussagen gebildete neue Aussage dann und nur dann wahr sein soll, wenn es die beiden gegebenen waren. Analog wird die Disjunktion benötigt, wenn es für die Wahrheit der neuen Aussage genügt, dass mindestens eine gegebene Aussage wahr ist. Die Subjunktion verwendet man um von einer Aussage auf eine andere sicher schließen zu können. Schließlich ist die Bijunktion dann und nur dann wahr, wenn beide hierdurch verknüpften Aussagen den selben Wahrheitsgehalt haben.

- Beispiele:

1. Seien AB, BC, CD und AD Strecken in der Ebene.

Weiter:

Abbildung in dieser Leseprobe nicht enthalten

Dann:

Abbildung in dieser Leseprobe nicht enthalten

2. Es bedeutet:

Abbildung in dieser Leseprobe nicht enthalten

Darm:

Abbildung in dieser Leseprobe nicht enthalten

3. Seien a, b, c Zahlen. Dann gilt:

Abbildung in dieser Leseprobe nicht enthalten

Hierdurch sind wir nun in der Lages beliebige aussagenlogische Ausdrücke zu bilden und mit Hilfe von Wahrheitstafeln den jeweiligen Wahrheitsgehalt festzustellen.

- Beispiele:

Abbildung in dieser Leseprobe nicht enthalten

Wir erhalten folgende Wahrheitstafel:

Abbildung in dieser Leseprobe nicht enthalten

2, <—> (-vM-ff)

Wir erhalten folgende Wahrheitstafe!:

Abbildung in dieser Leseprobe nicht enthalten

Wir erhalten folgende Wahrheitstafel:

Abbildung in dieser Leseprobe nicht enthalten

4. Von drei Personen А, В, C sollen möglichst viele eingeladen werden. Hierbei ist zu beachten:

a) A und В werden nicht gemeinsam eingeladen,
b) A wird genau dann eingeladen, wenn auch C eingeladen wird.
c) Wenn В eingeladen wird, so wird auch C eingeladen.

Wir formulieren hierzu folgende Aussagen:

Abbildung in dieser Leseprobe nicht enthalten

Dann:

Abbildung in dieser Leseprobe nicht enthalten

Da alle drei Aussagen erfüllt sein müssen, haben wir die folgende Aussage zu prüfen:

Abbildung in dieser Leseprobe nicht enthalten

Hierfür erhält man nachstehende Wahrheitstafei:

Abbildung in dieser Leseprobe nicht enthalten

Ergebnis: Die Personen A und C werden eingeladen.

- Tautologie

Offenbar ergeben die Beispiele 1 und 3 bei jeder Belegung der Aussagevariablen A und 'S stets den Wahrheitswert w. Allgemein setzen wir fest:

Definition: Eine Aussage ? heißt Tautologie, genau dann, wenn man bei beliebiger Belegung der Wahrheitswerte stets den Wahrheitswert w erhält. Insbesondere heißt Äquivalenz, falls [Abbildung in dieser Leseprobe nicht enthalten]eine Tautologie ist. Man schreibt dann:[Abbildung in dieser Leseprobe nicht enthalten]. Ebenso heißt Implikation, falls eine Tautologie ist. Man schreibt dann:[Abbildung in dieser Leseprobe nicht enthalten]

- Beispiele:

Abbildung in dieser Leseprobe nicht enthalten

Logische Gesetze:

Anstelle von Tautologie sprechen wir auch von einem logischen Gesetz.

Wichtige logische Gesetze:

Abbildung in dieser Leseprobe nicht enthalten

- Aussagelogische Erfüllbarkeit

Nach Definition hat eine Tautologie bei jeder möglichen Belegung den Wahrheitswert w; offenbar ist also die Negation einer Tautologie bei allen Belegungen stets falsch. Wir fragen, ob es überhaupt eine mögliche Zuweisung der Wahrheitswerte gibt, damit die gebildete Aussage den Wahrheitswert w annimmt.

Definition: Eine Aussage heißt dann, und nur dann erfüllbar, wenn ihre Variablen so belegt werden können, dass sie den Wahrheitswert w annimmt.

Bemerkung:

Das Erfüllbarkeitsproblem der Aussagelogik ist offenbar (in einem noch näher zu beschreibenden Sinn) algorithmisch entscheidbar.

- Beispiel:

Wir prüfen, ob[Abbildung in dieser Leseprobe nicht enthalten] erfüllbar ist.

Folgender Algorithmus entscheidet die Erfüllbarkeit:

Schritt 1 : Bilde für die Aussagen[Abbildung in dieser Leseprobe nicht enthalten]sämtliche möglichen Wahrheitskombinationen.

Schritt 2: Wähle eine beliebige Wahrheitskombination, bilde [Abbildung in dieser Leseprobe nicht enthalten] und prüfe[Abbildung in dieser Leseprobe nicht enthalten]

Frage: Hat hierbei[Abbildung in dieser Leseprobe nicht enthalten]den Wahrheitswert w?

Ja: Stopp "die Aussage ist erfüllbar"

Nein: Frage: Gibt es noch ungeprüfte Wahrheitskombinationen?

Ja: Schritt 2

Nein: Stopp "die Aussage ist nicht erfüllbar"

Bemerkung:

Ist n die Anzahl der Aussagevariablen, so ist der Zeitbedarf hierbei im schlechtesten Fall proportional zu 2n.

- Die Grundbegriffe der Prädikaten logik

Aussaqeform:

Wir verstehen hierunter einen Satz mit einer Leerstelle, die wir durch x ausdrücken. Wird x durch ein passendes Wort ersetzt, so entsteht eine Aussage. Schreibweise: /#(x)

- Beispiel:[Abbildung in dieser Leseprobe nicht enthalten]

Quantoren:

Existenzquantor: Ist die Aussage für mindestens ein Wort wahr, so schreiben wir:

Abbildung in dieser Leseprobe nicht enthalten

(lies: "es gibt ein x, so dass A(x) wahr ist")

- Beispiel;

Abbildung in dieser Leseprobe nicht enthalten

Bemerkung:

Man beachte, dass hierbei die Existenz nicht eindeutig bestimmt zu sein braucht. Will man ausdrücken, dass es tatsächlich nur ein x gibt, so sagt man: "Ein und nur ein x" beziehungsweise "genau ein x".

Allquantor: Ist die Aussage für alle möglichen Einsetzungen richtig, so schreiben wir:

Abbildung in dieser Leseprobe nicht enthalten

- Beispiel:

Abbildung in dieser Leseprobe nicht enthalten

Negation:

Aus der Verallgemeinerung der Regeln von DeMorgan ergibt sich:

Abbildung in dieser Leseprobe nicht enthalten

Bemerkung:

Offenbar ergibt sich die Notwendigkeit der Quantorenschreibweise erst dann, wenn die Anzahl der möglichen Einsetzungen "unendlich" wird (durch welche aussagelogischen Symbole können die Quantoren irm endlichen Fall ersetzt werden?).

Weiter: Aüaussagen sind offenbar nicht algorithmisch positiv entscheidbar (lediglich wenn für eine Einsetzung die Aussage nicht zutrifft, kann die Allaussage als logisch korrekt widerlegt gelten). Ebenso kann eine Existenzaussage nicht algorithmisch bezüglich ihrer Negation entschieden werden. Welche Konsequenzen ergeben sich hieraus für die empirische Überprüfbarkeit?

Aufgaben:

1) Diskutieren Sie die Wahrheitsproblematik anhand folgender Beispiele:

a) 36 ist eine Quadratzahl.
b) 3.333.331 ist eine Primzahl.
c) Jeden Morgen geht die Sonne auf.
d) Joseph Beuys ist kein bedeutender Künstler.
e) Gott ist tot.

2) Zeigen Sie:

Abbildung in dieser Leseprobe nicht enthalten

3) In den Vereinten Nationen soll ein Ausschuß eingerichtet werden. Als Mitglieder kommen die Staaten A, B, C, D und E in Frage. Dabei ist

folgendes zu beachten:

a) Nimmt A teil, so müssen auch C und D teilnehmen.
b) В und D nehmen nur zusammen teil oder keiner von den beiden Staaten beteiligt sich.
c) Wenn A nicht Mitglied wird, so beteiligt sich D.
d) В wird genau dann Mitglied, wenn E nicht Mitglied wird.
e) Wenn sich C beteiligt, dann beteiligt sich auch E.

Welche möglichen Staatenkombinationen können gebildet werden?

1.2. Mengen

Abbildung in dieser Leseprobe nicht enthalten

Beispiele:

Abbildung in dieser Leseprobe nicht enthalten

2. Zahlenmengen:

Abbildung in dieser Leseprobe nicht enthalten

Bemerkung:

Stellt man einen Bruch als Dezimalbruch dar, so bricht dieser entweder ab oder ist periodisch. Die reellen Zahlen umfassen alle Dezimalbrüche, also z.B. auch [Abbildung in dieser Leseprobe nicht enthalten]Odern.

Definition: [Abbildung in dieser Leseprobe nicht enthalten]ist eine wahre Aussage

(lies: "a ist ein Element von A")

- Beispiel:[Abbildung in dieser Leseprobe nicht enthalten]

Definition:[Abbildung in dieser Leseprobe nicht enthalten]

(lies: "a ist kein Element von A")

-Beispiel: [Abbildung in dieser Leseprobe nicht enthalten]

- Operatoren

Definition:[Abbildung in dieser Leseprobe nicht enthalten]

Abbildung in dieser Leseprobe nicht enthalten

- Mengenbeziehungen

Abbildung in dieser Leseprobe nicht enthalten

- Leere Menge

Abbildung in dieser Leseprobe nicht enthalten

- Russel 'sche Antinomie und Potenzmenge

Im Allgemeinen darf man keine Mengen bilden, die als Elemente selbst wieder Mengen enthalten (Mengen höherer Stufen). Insbesondere ist es unzulässig, dass eine Menge sich selbst als Element enthält. Man kommt hierbei unweigerlich zu Widersprüchen.

- Beispiel: Wir bilden die Menge aller Mengen, die sich nicht selbst als

Element enthalten:

P = {X; X ist eine Menge und X d X}

Frage: Was gilt für P?

Fall 1 : P e P. Also muss P die Bedingung der Menge P erfüllen und es folgt: P d P. Widerspruch!

Fall 2: P d P. Also erfüllt P die Bedingung für die Menge P und es folgt: P e P. Widerspruch!

"Rüssel'sehe Antinomie"

Man kann jedoch zeigen, dass die Menge, die die Teilmengen einer gegebenen Menge als Elemente enthält widerspruchsfrei gebildet werden kann.

Abbildung in dieser Leseprobe nicht enthalten

- Produktmenge:

Sin allgemeinen gilt: {a»b} = {b,a} "Ungeordnetes Paar". Geordnete Paare erhält man formal folgendermaßen:

Abbildung in dieser Leseprobe nicht enthalten

Da nach Voraussetzung die beiden Mengen dieselben Elemente enthalten, sind sie auch als Mengen gleich. Hieraus folgt der "nur dann” - Teil.

Abbildung in dieser Leseprobe nicht enthalten

Wegen ai^{a2,b2} muß ai=a2 folgen. Dann gilt aber auch {ai.bi} = {a2,b2}. Wegen ai=a2 ergibt sich hiermit schließlich bi = b2.

Abbildung in dieser Leseprobe nicht enthalten

Definition: ÄxB = {(a,b); a e A a b e B} ’'Produktmenge".

Geometrische Veranschaulichung:

Abbildung in dieser Leseprobe nicht enthalten

Bemerkung:

Die Reflexivität, Symmetrie und Transitivität sind gerade die Axiome der Gleichheit. Zwei Elemente, die In einer Äquivalenzrelation zueinander stehen, sind also in einem gewissen Sinne gleich.

- Funktionen

Abbildung in dieser Leseprobe nicht enthalten

Umkehrfunktion:

Abbildung in dieser Leseprobe nicht enthalten

Bemerkungen:

1. Zu f existiert die Umkehrfunktion f-[1] offenbar dann und nur dann, wenn f bijektiv Ist,
2. Im Koordinatensystem ist die Funktion umkehrbar, wenn jede Parallele zur x-Achse das Schaubild genau einmal schneidet.

Abbildung in dieser Leseprobe nicht enthalten

Bemerkung:

Die Mengenlehre wurde von Georg Cantor (*1 845, fl 91 8) Im Zusammenhang mit der Klärung des Unendlichkeitsbegriffes entwickelt. Nach Überwindung gewisser Schwierigkeiten, die sich im Zusammenhang mit einem zu allgemeinen Mengenbildungsbegriff ergaben (vgl. oben die Russe!'sehe Antinomie, benannt nach ihrem Entdecker Bertrand Russe! (*1872, fl970)) zeigte sich im Folgenden die enorme Tragweite und Allgemeinheit des Cantor'sehen Konzeptes: Die gesamte Mathematik kann hiermit unter einer einheitlichen Struktur erfasst werden. Auch die Theoretische Informatik wird auf dieser Basis beschrieben. Beispielsweise versteht man unter einer Sprache eine Menge, die Wörter dieser Sprache sind dann deren Elemente. Konstruiert werden diese Wörter mit Hilfe von Produktionen, wobei diese durch Relationen dargestellt werden.

[...]


1 Französischer Philosoph» *1798, fl 857» Begründer des Positivismus.

Ende der Leseprobe aus 122 Seiten

Details

Titel
Einführung in die Theoretische Informatik
Autoren
Jahr
2002
Seiten
122
Katalognummer
V207880
ISBN (eBook)
9783656369516
ISBN (Buch)
9783656370017
Dateigröße
52322 KB
Sprache
Deutsch
Schlagworte
einführung, theoretische, informatik
Arbeit zitieren
Dr. Wolfgang Schlageter (Autor)Thorsten Oliver Rauhut (Autor), 2002, Einführung in die Theoretische Informatik, München, GRIN Verlag, https://www.grin.com/document/207880

Kommentare

  • Noch keine Kommentare.
Im eBook lesen
Titel: Einführung in die Theoretische Informatik



Ihre Arbeit hochladen

Ihre Hausarbeit / Abschlussarbeit:

- Publikation als eBook und Buch
- Hohes Honorar auf die Verkäufe
- Für Sie komplett kostenlos – mit ISBN
- Es dauert nur 5 Minuten
- Jede Arbeit findet Leser

Kostenlos Autor werden