Diskrete Strukturen GrundlagenMengen in der Informatik 10. Reihenfolge der Objekte, mehrfache...

transcript

Diskrete StrukturenGrundlagen

c© F. Brandt, J. Esparza und M. Luttenberger

Fakultat fur InformatikTechnische Universitat Munchen

19. November 2019

1 Grundlagen

Einfuhrung

Mengen

Relationen

Funktionen

Kardinalitat: Vergleiche von unendlichen Mengen

Zusammenfassung

Einfuhrung

Ziel und Motivation 4

•”Grundvokabular“ der Mathematik lernen.

• Naturliche Sprache ist oft mehrdeutig.

• Mathematische Sprache erlaubt die prazise Definition von mathematischenObjekten und die exakte Formulierung von Satzen und Resultaten.

Ziele und Motivation 5

. In der Informatik: Mengen, Relationen, Funktionen etc. Grundlage fur

• Beschreibung von Algorithmen,

• Definition, was ein Programm”tut“ (Semantik),

• Definition, welche Zeichenketten Programme sind (Syntax),

• Definition, was ein Programm”tun soll“ (Spezifikation),

• Datenstrukturen (Arrays, Listen, Baume, Hash-Tabellen, . . . )

1 Grundlagen

Einfuhrung

Mengen

Basisvokabular und -konzepte

Vergleiche von Mengen

Operationen auf Mengen

Potenzmenge und Partitionen

Visualisierung von Mengen: Venn- und KV-Diagramme

Mengenterme

Tupel, Sequenzen, Folgen und Worter

Relationen

Funktionen

Zusammenfassung

Mengen

Mengenlehre 9

[Quelle]

Unter einer”Menge“ verstehen wir jede Zusammenfassung M von be-

stimmten wohlunterschiedenen Objekten m unserer Anschauung oder un-seres Denkens (welche die

”Elemente“ von M genannt werden) zu einem

Ganzen (Georg Cantor)

Mengen in der Informatik 10

. Reihenfolge der Objekte, mehrfache Nennung von Objekten, etc. spielen keineRolle.

So kennt eine Menge kein erstes, zweites, usw. Objekt.

. Daneben sind noch die Basisoperationen wichtig, um aus zwei oder mehrMengen eine neue Menge zu

”konstruieren“: Vereinigung, Schnitt, Differenz.

. Im Folgenden Wiederholung dieser Begriffe und deren Abkurzungen(”Schulwissen“).

Mengen: Basisvokabular 11

• Ein gegebenes Objekt x ist entweder in einer gegebenen Menge M enthaltenoder nicht.

.”x ∈M“ kurz fur

”Objekt x ist in Menge M enthalten“.

.”x 6∈M“ kurz fur

”Objekt x ist nicht in der Menge M enthalten“.

• Die Objekte x mit x ∈M nennt man die Elemente von M .

. Entsprechend liest man”x ∈M“ auch als

”x (ist) Element von M“ und

x 6∈M als”x (ist) kein Element von M“.

• Um Mengen zu definieren, kann man entweder alle Elemente der Mengeexplizit aufzahlen oder man definiert die Menge implizit durch Angabe einercharakterisierenden Eigenschaft der Elemente.

. Dabei verwendet man nach Konvention die Zeichen und zum Einleitenbzw. Beenden einer Mengendefinition.

. Beispiel: explizite (auch: extensionale) Definition

M := a, 2, $

d.h. M enthalt genau die drei Objekte”a“,

”2“,

”$“

. Beispiel: implizite (auch: intensionale) Definition

x |”x ist deutscher Staatsburger mit Wohnsitz in Munchen“

. Abkurzungen fur Mengen, die sehr oft vorkommen:

• N = 1, 2, 3, . . . Menge der naturlichen/positiven ganzen Zahlen;

• N0 = 0, 1, 2, . . . naturliche Zahlen inkl. 0;

• Z = . . . ,−2,−1, 0, 1, 2, . . . ganze Zahlen;

• Q = p/q | p ∈ Z, q ∈ N rationale Zahlen;

• R reelle Zahlen.

• Die leere Menge ist durch definiert, wofur man haufig auch ∅ schreibt. D.h.es gibt kein Objekt x mit x ∈ ∅, oder i.a.W. fur jedes Objekt x gilt x 6∈ ∅.

• Mengen sind auch Objekte und konnen damit selbst Elemente von Mengensein, z.B.

1, 1, 2, 1, , 1, 2, 3

. Das kann allerdings auch zu Problemen bei impliziten Definitionen fuhren,siehe Russelsche Antinomie:

R := x |”x ist Menge mit der Eigenschaft x 6∈ x“

Weder R ∈ R noch R 6∈ R”macht Sinn“. Losungen: ZFC-Mengenlehre oder

Typentheorie.

Mengen

Vergleiche von Mengen

Mengen: Vergleiche von Mengen 15

• M1 ist eine Teilmenge von M2 (kurz: M1 ⊆M2), falls jedes Element von M1

auch Element von M2 ist.

. Entsprechend schreibt man kurz”M1 6⊆M2“, falls M1 keine Teilmenge von

M2 ist, d.h. falls mindestens ein Element x von M1 kein Element von M2 ist.

• Fur die Menge der Objekte, die nur Elemente von M2, aber nicht von M1

sind, schreibt man kurz M2 \M1 (oder auch: M2 −M1).

. Man schreibt M1 (M2, falls zwar M1 ⊆M2, jedoch auch M2 \M1

mindestens ein Element besitzt.

. Beispiele:

• Fur jede beliebige Menge M gilt stets ∅ ⊆M .

• Fur eine Menge M gilt M ⊆ ∅ nur und nur dann, wenn M = ∅.

• Es gilt M1 ⊆M2 genau dann, wenn M1 \M2 = ∅.

• M1 und M2 werden genau dann als gleich (identisch) angesehen (kurz:

”M1 = M2“), wenn jedes Element von M1 auch Element von M2 ist, und

jedes Element von M2 auch Element von M1 ist.

. Kurz: M1 = M2 genau dann, wenn sowohl M1 ⊆M2 als auch M2 ⊆M1.

. Mit anderen Worten, um zu zeigen, dass zwei Mengen verschieden sind (kurz:

”M1 6= M2“) muss man ein Objekt x finden, das Element genau einer der

beiden Mengen ist.

• Man schreibt kurz M1∆M2 fur die Menge, welche genau die Objektezusammenfasst, welche Element genau einer der beiden Mengen M1,M2

(aber nicht beider) sind.

. M2 \M1 nennt man die Differenz von M2 und M1,

M1∆M2 nennt man die symmetrische Differenz von M1,M2.

. Beachte:

Im Allgemeinen M2 \M1 6= M1 \M2, aber stets M1∆M2 = M2∆M1.

• Als Machtigkeit/Kardinalitat (kurz: |M |) einer Menge M bezeichnet man dieZahl der (unterschiedlichen) Elemente in M .

• Eine Menge M ist endlich (kurz: |M | <∞), falls es eine naturliche Zahl kgibt und eine entsprechende Anzahl von verschiedenen Objektenx1, x2, . . . , xk, so dass M = x1, x2, . . . , xk gilt.

. Ansonsten bezeichnet man M als unendlich (kurz: |M | =∞).

. Weitere Einteilung von unendlichen Mengen folgt spater.

Mengen

Operationen auf Mengen

Mengen: Operationen auf Mengen 19

• Standardoperationen fur zwei Mengen M1,M2:

Schnitt und Vereinigung

. Man schreibt kurz M1 ∩M2 fur die Menge mit der Eigenschaft:

”Ist x ein Objekt, dann ist x ein Element von M1 ∩M2 genau dann, wenn x

sowohl Element von M1 als auch von M2 ist.“

M1 ∩M2 wird der Schnitt von M1 und M2 genannt.

Gilt M1 ∩M2 = ∅, dann sagt man, dass M1 und M2 disjunkt sind.

. Entsprechend schreibt man kurz M1 ∪M2 fur die Menge mit der Eigenschaft

”Ist x ein Objekt, dann ist x ein Element von M1 ∪M2 genau dann, wenn x

Element von mindestens einer der beiden Mengen M1,M2 ist.“

M1 ∪M2 wird die Vereinigung von M1 und M2 genannt.

• Haufig benotigt man auch den Schnitt und die Vereinigung von mehrerenMengen.

• Fur eine Menge S, deren Elemente selbst Mengen sind, definiert man:

∩S :=⋂

M∈S M:= x |

”fur jedes M ∈ S gilt x ∈M“

∪S :=⋃

M∈S M:= x |

”es gibt mindestens ein M ∈ S mit x ∈M“

. Damit gilt M1 ∩M2 = ∩M1,M2 und M1 ∪M2 = ∪M1,M2.• Gilt S = M1, . . . ,Mk fur ein k ∈ N, dann schreibt man auch

k⋃i=1

Mi := ∪Sk⋂

Mi := ∩S

• Ist eine Menge Ω fest vorgegeben (fixiert) und betrachtet man ausschließlichTeilmengen von Ω, so schreibt man fur eine Menge A ⊆ Ω statt Ω\A kurz A.

. Ω nennt man dann das Universum oder die Grundmenge und

A das Komplement von A (bzgl. Ω).

. Wichtig: Ohne Angabe, welches Universum gewahlt wurde, macht A keinenSinn.

Mengen

Potenzmenge und Partitionen

Mengen: Potenzmenge 23

• Bezeichnet M eine Menge, so schreibt man 2M oder P(M) fur diePotenzmenge von M :

P(M) := 2M := A | A ⊆M

Die Potenzmenge von M enthalt alle Teilmengen von M als Elemente.

. Beispiele:P(1, 2) = ∅, 1, 2, 1, 2

P(1, 2, 3) = ∅, 1, 2, 3,1, 2, 1, 3, 2, 3, 1, 2, 3

P(∅) = ∅

P(∅, ∅) = ∅, ∅, ∅, ∅, ∅

• Die Potenzmenge einer Menge mit k Elementen hat Kardinalitat . . . 2k.

. Intuitiv: um eine Teilmenge zu konstruieren muss fur jedes Elemententschieden werden, ob es zur Teilmenge gehort oder nicht.

. damit k ja/nein (binare) Entscheidungen.

. also 2k mogliche Teilmengen (”richtiger“ Beweis spater).

Mengen: Partitionen 24

• Eine Partition einer Menge M ist eine Menge P ⊆ P(M) von disjunkten,nicht leeren Teilmengen von M , deren Vereinigung genau M ergibt.

Etwas formaler:

• M = ∪P , d.h. die Elemente von P uberdecken M .

• Fur beliebige A,B ∈ P gilt entweder A = B oder A ∩B = ∅.

• Fur beliebiges A ∈ P gilt A 6= ∅.

. Beispiel: Die moglichen Partitionen von 1, 2, 3 sind:

1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 3, 2, 1, 2, 3

. Einige mogliche Partitionen von N0:

2N0, 2N0 + 1, x | x ∈ N0, N0 . . .

Mengen

Visualisierung von Mengen: Venn- und

KV-Diagramme

Mengen: Veranschaulichung 26

• Die Beziehungen zwischen mehreren Mengen veranschaulicht man z.B.mittels Venn-Diagrammen oder Karnaugh-Veitch-Diagramme.

. Wichtig: Allgemeine Lage aller Mengen. (Bildquelle: [wikipedia])

• Venn-Diagramme und KV-Diagramme fur 4 allgemeine Mengen

(Bildquelle: [wikipedia])

• Venn-Diagramme und KV-Diagramme fur 5 allgemeine Mengen

(Bildquelle: [wikipedia])

Mengen

Mengenterme

Mengenausdrucke/-terme 30

• Stehen A,B,C, . . . fur beliebige Mengen, sind also Variablenbezeichner vom

”Typ Menge“, dann konnen wir mittels ∩,∪,P(•), \,∆

Mengenterme/-ausdrucke aufstellen, die die Konstruktion von weiteren,komplexeren Mengen beschreiben.

. Ist ein Universum Ω definiert, dann steht auch das Komplement A einerMenge A ⊆ Ω zur Verfugung.

• Werten sich zwei Mengenterme fur jede konkrete Wahl von MengenA,B,C, . . . stets zur selben Menge aus, dann nennt man die Mengentermeaquivalent.

• Die Aquivalenz von Mengentermen lasst sich entweder mittelsKV-Diagrammen uberprufen (fur bis zu ca. 5 Variablen) oder mittelsAquivalenzumformungen unter Verwendung vonStandardaquivalenzen/-identitaten.

. Zunachst: alles entsprechend zur Umformung von arithmetischenAusdrucken/Termen, spater formale Definition fur logische Formeln.

• Standardaquivalenzen fur Mengenvariablen A,B,C.

A = A ∪AA = A ∩AA = A ∪ ∅∅ = A ∩ ∅

A ∪B = B ∪AA ∩B = B ∩A

A ∪ (B ∪ C) = (A ∪B) ∪ CA ∩ (B ∩ C) = (A ∩B) ∩ C

• Noch mehr Standardaquivalenzen fur Mengenvariablen A,B,C.

A ∩ (B ∪ C) = (A ∩B) ∪ (A ∩ C)A ∪ (B ∩ C) = (A ∪B) ∩ (A ∪ C)

A \ (B ∪ C) = (A \B) ∩ (A \ C)A \ (B ∩ C) = (A \B) ∪ (A \ C)

A = A ∪ (A ∩B)A = A ∩ (A ∪B)

A∆B = (A \B) ∪ (B \A)

. Mit definiertem Universum Ω:

A ∩A = ∅A ∪A = ΩA \B = A ∩B

A ∪B = A ∩BA ∩B = A ∪B

• Uberprufen/Beweisen z.B. durch Aufstellen des KV-Diagramms einmal fur dielinke und einmal fur die rechte Seite einer Aquivalenz.

. Beispiel: A \ (B ∩ C) = (A \B) ∪ (A \ C)

. Linke Seite: v.l.n.r. A, B ∩ C, A \ (B ∩ C)

. Rechte Seite: v.l.n.r. A \B, A \ C, (A \B) ∪ (A \ C)

Mengen

Tupel, Sequenzen, Folgen und Worter

Tupel, Sequenzen, Folgen und Worter 35

• Mengen: Zusammenfassung von Objekten ohne Beachtung von Anordnungoder Vielfachheiten von beliebig vielen Objekten.

a, b, ∅, b, a, a = ∅, a, b, a, b

. Tupel: Zusammenfassung einer festen, endlichen Anzahl von Objekten unterBeachtung der Anordnung/Auflistung der Objekte und Beachtung vonVielfachheiten.

(a, b, ∅, b, a, a) 6= (∅, a, b, a, b)

. Definitionen von Tupeln durch ( und ) eingeleitet bzw. beendet.

• Sequenz/Folge: Ist fur jede naturliche Zahl i ∈ N (oder auch i ∈ N0) einObjekt ai gegeben, dann bezeichnet man die unendliche Auflistung(a1, a2, . . .) (bzw. (a0, a1, . . .)), die die Objekte nach ansteigendem Indexauflistet/zusammenfasst, als Sequenz/Folge.

Kurzschreibweise: (ai)i∈N (bzw. (ai)i∈N0)

. Beispiel: (i)i∈N0 = (0, 1, 2, 3, . . .), (1/i)i∈N = (1, 1/2, 1/3, 1/4, . . .)

• Haufig sagt man statt Tupel auch endliche Sequenz oder Folge und fasst dieDefinitionen zusammen:

Gilt I ⊆ N0 und ist fur jedes i ∈ I ein Objekt ai gegegeben, so schreibt(ai)i∈I fur das Tupel, welches die Objekte ai nach ansteigendem Indexauflistet.

. Notation: Fur k ∈ N definiert man [k] := 1, 2, . . . , k mit [0] = ∅.

. Dann gilt (ai)i∈[k] = (a1, a2, . . . , ak) mit (ai)i∈[0] = ().

• Lange |t| eines Tupels t oder auch Anzahl #t der Komponenten/Eintrageeines Tuples ist die Anzahl der Objekte (einschließlich Vielfachheiten) derzusammengefassten Objekte.

. Beispiele: |(a, (b, c))| = 2

|(a, a, a, a, a, a)| = 6

|( a, b, b, a, ∅, (a, (b, ∅)) )| = 4

. Synonyme: k-Tupel fur Tupel der Lange k, Paar fur 2-Tupel

. Zwei Tupel sind identisch, wenn sie dieselbe Lange haben und sie an jederPosition denselben Eintrag besitzen.

. Beispiele:

(a, (b, c)) 6= (a, (c, b))

(a, b, c) = (a, c, b) 6= (c, b, a) 6= () 6= (a, b, c)

• Sind A,B Mengen, so schreibt man A×B fur das kartesische Produkt vonA und B: die Menge aller Paare, deren erste Komponente ein Element aus Aund deren zweite Komponente ein Element aus B ist:

A×B = (a, b) | a ∈ A, b ∈ B

. Entsprechend definiert man

• A1 ×A2 × . . .×Ak = (a1, a2, . . . , ak) | a1 ∈ A1, a2 ∈ A2, . . . , ak ∈ Ak

(fur k = 0 ist das Produkt die Menge () ).

• Beachte: (A×B)× C 6= A×B × C 6= A× (B × C) da

• A×B × C = (a, b, c) | a ∈ A, b ∈ B, c ∈ C

• (A×B)× C = ((a, b), c) | a ∈ A, b ∈ B, c ∈ C

• A× (B × C) = (a, (b, c)) | a ∈ A, b ∈ B, c ∈ C

• Graphisch veranschaulicht (entspricht Speicherstruktur):

(a, b, c) entspricht

((a, b), c) entspricht

(a, (b, c)) entspricht

• Man schreibt Ak = A× . . .×A︸︷︷︸k mal

fur alle k-Tupel mit Komponenten aus A:

Ak = (a1, . . . , ak) | a1 ∈ A, a2 ∈ A, . . . , ak ∈ A

. Beachte: A0 := () und A1 := (a) | a ∈ A 6= A

. Programmiersprachen machen auch diesen Unterschied, z.B. Python:

[′a′] ist die Liste, die das Zeichen a enthalt, und nicht einfach das Zeichen a;entsprechend ist [] die leere Liste.

• Tupel konnen prinzipiell durch Mengen”simuliert“ werden z.B. (a, b) durch

0, a, 1, b oder (ohne Zahlen aber umstandlicher) durch∅, a, ∅, b.

Worter und Sprachen 41

• Fur die Informatik bilden Tupel die konzeptuelle Grundlage fur Zeichenketten(strings).

• Ublicherweise ist eine Menge von Grundzeichen (Alphabet) vorgegeben.

• z.B. ASCII, UTF-8, alphanumerisch a, . . . , z, A, . . . , Z, 0, . . . , 9

. Haufig wird ein Alphabet mit Σ oder Γ bezeichnet und man betrachtet nurTupel mit Eintragen aus diesem Alphabet.

. Fur die Menge aller (endlichen) Tupel mit Eintragen aus einem Alphabet Σschreibt man kurz Σ∗ :=

⋃k∈N0

Σk = ∪Σk | k ∈ N0.

. Man nennt Σ∗ auch die Menge aller endlichen Worter uber Σ, undbezeichnet die Elemente von Σ∗ als (endliche) Worter (uber Σ).

Worter und Sprachen 42

• Solange keine Missverstandnisse entstehen konnen, schreibt man fur ein Wort(a1, a2, . . . , ak) einfach kurz a1a2 . . . ak.

. Fur das leere Tupel () benotigt man dann ein spezielles Symbol, meistens ε(empty word) oder λ (leeres Wort), das man dann das leere Wort nennt.

• Ist Σ ein Alphabet, so bezeichnet man eine Teilmenge L ⊆ Σ∗ als Sprache(uber Σ).

• Fur Worter und Tupel definiert man noch die Konkatenation (”Verkettung“):

• Die Konkatenation uv zweier Worter u = u1 . . . uk und v = v1 . . . vl(ui, vj ∈ Σ) ist uv := u1 . . . ukv1 . . . vl.

. Beachte: uε = εu = u und |uv| = |u|+ |v|.

• Entsprechend ist die Konkatenation zweier Tupel (u1, . . . , uk) und (v1, . . . , vl)das neue Tupel (u1, . . . , uk, v1, . . . , vl).

1 Grundlagen

Einfuhrung

Mengen

Relationen

Binare Relationen und Graphen

Relationales Produkt

Binare Relationen auf einer Menge

Aquivalenzrelationen

Ordnungsrelationen

Funktionen

Zusammenfassung

Relationen

Relationen 46

• Gegeben Mengen A1, A2, . . . , Ak, so nennt man R ⊆ A1 ×A2 × . . .×Ak

eine (k-stellige) Relation oder eine Relation der Stelligkeit/Aritat k.

. Gilt (a1, a2, . . . , ak) ∈ R, dann sagt man, dass die Objekte a1, a2, . . . , akbzgl. R in Relation stehen.

• Relationen bilden die Grundlage fur Datenbanken: Vereinfacht gesprochen isteine (klassische) Datenbank eine Menge von Datenbanktabellen, wobei jedeTabelle eine Relation abspeichert, z.B.

AId ANachname AVorname

1 Man Spider2 Brot Bernd3 Woman Wonder4 Gaga Lady

AId AMatrikelnummer

1 31412 2718283 17014 3694

AId AGeschlecht

1 m2 b3 w4 w

Relationen: Join und Projektion 47

• Die wichtigste Datenbankoperation sind Join und Projektion.

• Der Join R ./i=j S konkateniert (”verkettet“) jedes Tupel (r1, . . . , rk) ∈ R

mit jedem Tupel (s1, . . . , sl) ∈ S, soweit ri = sj gilt:

R ./i=j S =

(r1, . . . , rk, s1, . . . , sl) |(r1, . . . , rk) ∈ R,(s1, . . . , sl) ∈ S,

ri = sj

• Die Projektion πi1,i2,...,ij reduziert jedes Tupel (r1, . . . , rk) ∈ R auf die

Eintrage an den Positionen 1 ≤ i1, i2, . . . , ij ≤ k:

πi1,i2,...,ij (R) = (ri1 , ri2 , . . . , rij ) | (r1, . . . , rk) ∈ R

. Hiermit lassen sich die Datenbanktabellen verknupfen und filtern, um damitDatenbankanfragen zu beantworten.

. Mehr dazu in Datenbanken.

Relationen 48

• Beispiel: Relationen/Tabellen R,S, T

AId ANachname AVorname

1 Man Spider2 Brot Bernd3 Woman Wonder4 Gaga Lady

AId AMatrikelnummer

1 31412 2718283 20174 3694

AId AGeschlecht

1 m2 b3 w4 w

. Datenbankanfragen entsprechen Verknupfen der Tabellen mittels Join undProjektion z.B. Anfrage

”Vornamen aller weiblichen Personen“:

π3(R ./1=1 (T ./2=1 (w)))

(Selbst auswerten mit R,S, T von oben.)

Relationen

Binare Relationen und Graphen

Binare Relationen 50

• Im Weiteren: binare, d.h. 2-stellige Relationen R ⊆ A×B. Grundlage fur alle verzeigerten Datenstrukturen in der Informatik (z.B. Listen,

Baume, Graphen).

. Binare Relationen auf Zahlen aus der Schule bekannt:

”kleiner-gleich“ ≤,

”kleiner“ <,

”gleich“ =,

”ungleich“ 6=, usw.

Notationsproblem: = = (x, x) | x ∈ R ⊆ R× R (?!)

. Daher ≤R bzw. =N usw. fur bessere Unterscheidbarkeit.

. Infixnotation: aR b fur (a, b) ∈ R• Vgl.: 3 ≤N 5 statt (3, 5) ∈ ≤N

. Fur spater: inverse Relation R−1 := (b, a) | (a, b) ∈ R.. Z.B. ≤−1

R = ≥R.

Binare Relationen: Graphen 51

. Veranschaulichung von binaren Relationen mittels Graphen.

• Ein gerichteter Graph (kurz: Digraph) G = (V,E) besteht aus

• einer Menge V – genannt Knotenmenge, Elemente von V entsprechendKnoten von G.

• einer binaren Relation E ⊆ V × V – genannt Kantenrelation/-menge,Elemente von E entsprechend Kanten von G.

. Ein Digraph G ist endlich, falls V endlich ist; ansonsten ist G unendlich.

. Ein Digraph G ist bipartit, falls V = A ∪B mit A ∩B = ∅ undE ⊆ A×B ∪B ×A (es gibt nur Kanten zwischen A und B).

• Visualisierung eines (endlichen) Digraphen G = (V,E):

• Fur jeden Knoten v ∈ V”male“ einen

”Knubbel“ mit Namen

”v“

• Fur jede Kante (s, t)”male“ einen

”Pfeil“ vom

”Knubbel“ fur s zum

”Knubbel“ fur t (s fur

”source“, t fur

”target“).

Falls s = t, dann”male Schleife“.

Falls G unendlich, nur schematische Skizze moglich.

• Beispiel: G = (V,E) mit

V = 1, 2, a, b

E = (1, b), (2, b), (2, a), (1, 2), (b, b), (b, 2), (a, 1)

alternativ

Nicht bipartit.

• Beispiel: G = (V,E) mit

V = 1, 2, a, b

E = (1, b), (2, b), (2, a), (b, 2), (a, 1)

alternativ

Bipartit.

• Visualisierung von R ⊆ A×B als Digraph GR := ((A ∪B), R).

. Beispiel: Visualisierung von (x, y) | x, y ∈ 0, 1, 2, 3, x ≤N0y

0 1 2 3

. Beispiel: Skizze zu ≤N0⊆ N0 × N0

0 1 2 3 . . .

• Ein Tupel (v0, v1, . . . , vl) (oder einfach v0, v1, . . . , vl) von Knoten vi ∈ Vheißt Weg/Pfad, falls (vi−1, vi) ∈ E fur jedes i ∈ [l] gilt, d.h. wenn je zweiaufeinanderfolgende Knoten durch eine Kante aus E verbunden sind.

• Die Lange eines Pfades (v0, v1, . . . , vl) ist l, d.h. die Anzahl der Kanten(”Schritte“), von v0 bis vl.

. Ein Pfad heißt einfach, falls kein Knoten mehrmals in dem Pfad vorkommt(”besucht“ wird).

. Fakt: In einem endlichen Digraphen hat ein einfacher Pfad maximal Lange|V | − 1.

• Beispiel:

v0 v1 v2 v3

Einige Pfade:

v0 v0, v0 v0, v1 v0, v1, v0 v0, v1, v2, v3, v1

Relationen

Relationales Produkt

Relationales Produkt 57

• Sind R ⊆ A×B sowie S ⊆ C ×D binare Relationen, dann ist das relationaleProdukt von R und S die binare Relation RS ⊆ A×D gegeben durch

RS = (a, d) | es gibt x ∈ B ∩ C mit (a, x) ∈ R und (x, d) ∈ S

oder kurz: RS = π1,4(R ./2=1 S).

• Wenn B ∩ C = ∅, dann gilt also RS = ∅.• Man nennt RS auch die Verkettung von R und S.

• Visualisierung des relationalen Produkts:

Der Graph zu RS enthalt eine Kante (u, v) genau dann, wenn (gdw.) eseinen

”Verbindungsknoten w“ und eine R-Kante (u,w) und eine S-Kante

(w, v) gibt.

Bedeutung von”A gdw. B“: Wenn A dann B und wenn B dann A.

Relationales Produkt 58

R S RR

RS SR SS

Relationen

Binare Relationen auf einer Menge

Binare Relationen auf einer Menge 60

• Weiterer wichtiger Spezialfall:

Binare Relationen R ⊆ A×A, die auf einer Menge A definiert sind.

. Konnen mit sich selbst mittels relationalem Produkt mehrfach verknupftwerden:

”Zusammenziehen der k-Schritt-Pfade“

• R0 := IdA := (a, a) | a ∈ A

• R1 := R = R0R

• R2 := RR = R1R

• Rk+1 := RkR = RRk = RR . . . R︸︷︷︸k + 1 mal

fur beliebiges k ∈ N0.

. Bemerkung: Obige Definition wird als induktive Definition bezeichnet.

Die Definition ist (fast) ein Algorithmus, wie man Rk+1 mittels R und Rk

rekursiv”berechnen“ kann.

• Sei R gegeben durch:

. v.l.n.r. R0, R2, R3:

. v.l.n.r. R0 ∪R1 ∪R2, R0 ∪R1 ∪ · · · ∪R3, R0 ∪R1 ∪ · · · ∪R4:

• Transitive Hulle einer binaren Relation R ⊆ A×A:

R+ :=⋃

k∈NRk (

”alle Pfade, die mindestens einen Schritt machen“)

• Reflexiv-transitive Hulle einer binaren Relation R ⊆ A×A:

R∗ :=⋃

k∈N0Rk = R0 ∪R+

. v ist von u”erreichbar“, falls uR∗v.

. Weitere Notation:

R≤k :=⋃k

i=0Ri (

”Erreichbarkeit in hochstens k Schritten“)

• Hinweis: Bedeutung von ∗ uberladen, unterscheide von z.B. Menge allerendlichen Worter Σ∗.

. v.l.n.r. R+, R∗:

• Es gilt: Ist A endlich und n = |A|, dann gilt R∗ = R≤n−1.

Exkurs: Beweise 66

• Es gilt: Ist A endlich und n = |A|, dann gilt R∗ = R≤n−1:

• Wir wollen diese Aussage beweisen.

• Beweis: Sequenz von Aussagen, die von einer Hypothese (A endlich undn = |A|) zu einer Konklusion oder einem Ziel (R∗ = R≤n−1) fuhren.

• Hypothese: A endlich und n = |A|. Ziel: R∗ = R≤n−1.

Um zu zeigen, dass R∗ = R≤n−1 gilt, zeigen wir:

• Jedes Element von R∗ gehort zu R≤n−1, d.h. R∗ ⊆ R≤n−1.Hypothese: A endlich und n = |A|. Ziel: R∗ ⊆ R≤n−1.

• Jedes Element von R≤n−1 gehort zu R∗, d.h. R≤n−1 ⊆ R∗.Hypothese: A endlich und n = |A|. Ziel: R∗, d.h. R≤n−1 ⊆ R∗.

• Wir haben die Aufgabe in zwei Teilaufgaben zerlegt.

Exkurs: Beweise 67

• Teil I: Hypothese: A endlich und n = |A|. Ziel: R∗ ⊆ R≤n−1.

Um zu zeigen, dass jedes Element von R∗ zu R≤n−1 gehort, betrachten wirein beliebiges Paar (s, t) ∈ A×A, nehmen (s, t) ∈ R∗ an, und zeigen(s, t) ∈ R≤n−1.

• Hypothese: A endlich und n = |A| und (s, t) ∈ R∗. Ziel: (s, t) ∈ R≤n−1.

Um zu zeigen, dass (s, t) ∈ R≤n−1 gilt, ersetzen wir (s, t) ∈ R∗ und(s, t) ∈ R≤n−1 durch aquivalente Aussagen:

• (s, t) ∈ R∗: Es gibt einen Pfad von s nach t in Digraph GR.

• (s, t) ∈ R≤n−1: Es gibt einen Pfad von s nach t in Digraph GR, der hochstensn− 1 Schritte macht.

• Hypothese: A endlich und n = |A| und es gibt einen Pfad von s nach t in GR.

Ziel: Es gibt einen Pfad von s nach t in GR, der hochstens n− 1 Schrittemacht.

Exkurs: Beweise 68

• Hypothese: A endlich und n = |A| und (s, t) ∈ R∗ und es gibt einen Pfadvon s nach t in GR.

Ziel: Es gibt einen Pfad von s nach t in GR, der hochstens n− 1 Schrittemacht.

Kern des Beweises: Sei s, . . . , u, . . . , u, . . . , t ein Pfad von s nach t, der denKnoten u zweimal enthalt. Dann erhalt man durch Entfernen des

”nutzlosen“

Teilpfads von u nach u, einen neuen, kurzeren Pfad s, . . . , u, . . . , t, der ueinmal weniger enthalt. Durch wiederholte Anwendung dieser Regel enthaltman einen einfachen Pfad von s nach t.

Jeder einfache Pfad von GR besteht aus hochstens n− 1 Schritten, da ersonst mindestens einen Knoten zweimal besucht.

Exkurs: Beweise 69

• Teil II: Hypothese: A endlich und n = |A|. Ziel: R≤n−1 ⊆ R∗.

Um zu zeigen, dass jedes Element von R∗ zu R∗ gehort, betrachten wir einbeliebiges Paar (s, t) ∈ A×A, nehmen (s, t) ∈ R≤n−1 an, und zeigen(s, t) ∈ R∗.

• Hypothese: A endlich und n = |A| und (s, t) ∈ R≤n−1. Ziel: (s, t) ∈ R∗.

Um zu zeigen, dass (s, t) ∈ R∗ gilt, ersetzen wir (s, t) ∈ R∗ und(s, t) ∈ R≤n−1 durch aquivalente Aussagen:

• (s, t) ∈ R∗: Es gibt einen Pfad von s nach t in Digraph GR.

• (s, t) ∈ R≤n−1: Es gibt einen Pfad von s nach t in Digraph GR, der hochstensn− 1 Schritte macht.

• Hypothese: A endlich und n = |A| und es gibt einen Pfad von s nach t inGR, der hochstens n− 1 Schritte macht.Ziel: Es gibt einen Pfad von s nach t in GR.

Es ist offensichtlich, dass das Ziel aus der Hypothese folgt.

• Es gilt: Ist A endlich und n = |A|, dann gilt R∗ = R≤n−1:

Beweisskizze: Wir zeigen fur alle s, t ∈ A

(s, t) ∈ R∗ gdw. (s, t) ∈ R≤n−1

(s, t) ∈ R∗

gdw es gibt einen Pfad von s nach t in GR

gdw es gibt einen einfachen Pfad von s nach t in GR

gdw es gibt einen Pfad von s nach t in GR der hochstens n− 1 Schritte macht

gdw (s, t) ∈ R≤n−1.

. Weitere Eigenschaften (zur Ubung):

• (R∗)∗ = (R+)∗ = (R∗)+ = R∗

• (R+)+ = R+

• Eine binare Relation R ⊆ A×A auf einer Menge A ist

• reflexiv falls: IdA ⊆ R

”Jeder Knoten hat eine Schleife“

• symmetrisch falls: Wann immer (s, t) ∈ R, dann auch (t, s) ∈ R

”Zwischen je zwei Knoten entweder beide Kanten oder gar keine Kante“

• asymmetrisch falls: Wann immer (s, t) ∈ R, dann immer (t, s) 6∈ R

”Keine Schleifen und zwischen je zwei verschiedenen Knoten hochstens eine

Kante“

• antisymmetrisch falls: Wann immer (s, t) ∈ R und auch (t, s) ∈ R, dann giltimmer s = t

”Zwischen zwei verschiedenen Knoten existiert hochstens eine Kante“

• transitiv falls: Wann immer (s, t) ∈ R und auch (t, u) ∈ R, dann auch(s, u) ∈ R

”Kommt man mit genau zwei Schritten von s nach u, dann auch mit genau

einem.“

• Eigenschaften der folgenden Relationen?

• Weitere Beispiele:

. =Z: reflexiv; symmetrisch; transitiv

. ≤Z: reflexiv; antisymmetrisch; transitiv

. <Z: nicht reflexiv; asymmetrisch; transitiv

. 6=Z: nicht reflexiv; symmetrisch; nicht transitiv

. |Z ⊆ Z× Z mit”a|b“ definiert durch

”ba∈ Z“ (sprich

”a teilt b“)

nicht reflexiv; nicht symmetrisch; nicht asymmetrisch; nicht antisymmetrisch;transitiv

. |N ⊆ N× N (Einschrankung von”teilt“ auf positive ganze Zahlen)

reflexiv; antisymmetrisch; transitiv

. ≡m⊆ Z× Z mit”a ≡m b“ definiert durch

”m|(a− b)“ fur festes m ∈ N

reflexiv; symmetrisch; transitiv

. ⊆ auf P(Z): reflexiv; antisymmetrisch; transitiv

. Kongruenzbegriff auf Dreiecken: reflexiv; symmetrisch; transitiv

• Noch mehr Beispiele fur Worter u, v ∈ Σ∗

. u ist ein Prafix von v (kurz: u p v),

falls es ein w ∈ Σ∗ mit uw = v gibt.

p: reflexiv; antisymmetrisch; transitiv

. u ist ein Suffix von v (kurz: u s v),

falls es ein w ∈ Σ∗ mit wu = v gibt.

s: reflexiv; antisymmetrisch; transitiv

. u ist ein Infix (Faktor) von v (kurz: u i v),

falls es w,w′ ∈ Σ∗ mit wuw′ = v gibt.

f : reflexiv; antisymmetrisch; transitiv

. u und v sind konjugiert (kurz: u ∼=c v),

falls es w,w′ ∈ Σ∗ mit u = ww′ und v = w′w gibt.

∼=c: reflexiv; symmetrisch; transitiv

• Klassifikation:

• ≤Z, |N,⊆,p,s,i werden als partielle Ordnungen bezeichnet:

reflexiv, antisymmetrisch, transitiv

• =Z,≡m,∼=c,”Kongruenz von Dreiecken“ werden als Aquivalenzrelationen

bezeichnet:

reflexiv, symmetrisch, transitiv

Relationen

Aquivalenzrelationen

Aquivalenzrelationen 77

• Betrachte die Relationen =Z, ≡k (Kongruenz modulo k), ∼=c

. Gemeinsamkeiten: reflexiv, symmetrisch, transitiv

Unterteilen/partitionieren die Objekte des Universums nach verschiedenen

”Aquivalenzbegriffen“

• a =Z b:”a und b dieselbe/identische Zahl“

”Feinste“ Partitionierung: x | x ∈ Z

• a ≡m b:”a und b derselbe Rest bei Division durch m“

Partitionierung: Menge der Restklassen mZ,mZ + 1, . . . ,mZ + (m− 1) mitmZ = mz | z ∈ Z

”Grobste“ Partitionierung fur m = 1: Z (

”alles gleich“)

• Allgemeine Definition: Eine binare Relation R ⊆ A×A uber einer Menge Aheißt Aquivalenzrelation (auf A), falls:

• R reflexiv und symmetrisch und transitiv.

. Fur R ⊆ A×A eine Aquivalenzrelation definiert man:

• Aquivalenzklasse eines Objekts a bzgl. R:

[a]R = b ∈ A | aRb

Bsp.: [1]=Z = 1, [−5]≡3 = 3Z + 1

. Fakt: Es gilt a ∈ [a]R und [a]R = [b]R fur aRb und [a]R ∩ [b]R = ∅ fur(a, b) 6∈ R

• Quotient von A bzgl. R als die Menge aller Aquivalenzklassen:

A/R = [a]R | a ∈ A

Bsp.: Z/=Z = x | x ∈ Z, Z/≡3 = 3Z, 3Z + 1, 3Z + 2

. Fakt: A/R ist eine Partition von A

• Weitere wichtige Aquivalenzrelationen:

Aquivalenzen auf Termen/Formeln/Programmen

. (x+ y)2 und x2 + 2xy+ y2 verschiedene Zeichenketten/arithmetische Terme,aber werten sich fur alle reellen Zahlen x, y ∈ R stets zu demselben Wert aus,weswegen man (ungenau) einfach (x+ y)2 = x2 + 2xy + y2 schreibt.

. Entsprechend (A ∩ C) \B und (A ∩ (B ∪ C)) im mengentheoretischen Sinnaquivalent, aber verschiedene Terme.

. Wichtig fur die Informatik: Entscheiden, ob zwei (als Zeichenkette)verschiedene Programme dasselbe tun.

Z.B. prototypische Implementierung vs. optimierte Implementierung.

. Ausblick: Im Allgemeinen kann man kein Programm schreiben, das dieAquivalenz von zwei anderen Programmen entscheidet.

Siehe Einfuhrung in die theoretische Informatik.

Relationen

Ordnungsrelationen

Ordnungsrelationen 81

• Beispiele: ≤Z, |N,⊆,p,s,i

. Gemeinsamkeiten: reflexiv, antisymmetrisch, transitiv

Ordnen Objekte zumindest teilweise (partiell) an.

. Unterschiede:

• Fur zwei beliebige a, b ∈ Z gilt mindestens a ≤Z b oder b ≤Z a,

d.h. bzgl. ≤Z sind alle ganzen Zahlen vergleichbar.

• Es gibt a, b ∈ N, so dass weder a|Nb noch b|Na gilt,

d.h. bzgl. |N gibt es unvergleichbare positive ganze Zahlen, z.B. die Primzahlen.

• Man definiert daher:

. R ⊆ A×A ist eine partielle Ordnung (Halbordnung) auf A, falls

• R reflexiv und antisymmetrisch und transitiv.

. R ⊆ A×A ist eine totale Ordnung (Totalordnung) auf A, falls

• R eine partielle Ordnung auf A ist, und

• je zwei beliebige a, b stets bzgl. R in Relation stehen, d.h. mindestens aRboder bRa gilt.

• Man definiert entsprechend noch strikte/strenge Varianten, indem man dieReflexivitat durch die Irreflexivitat ersetzt, womit die Antisymmetrie zurAsymmetrie wird.

• R ist irreflexiv, falls (a, a) 6∈ R fur jedes a ∈ A, d.h. R ∩ IdA = ∅.

. Bsp.: <Z =≤Z \IdZ

• Visualisierung einer (partiellen) Ordnung R ⊆ A×A:

Statt R bzw. den zugehorigen Digraphen GR,

stellt man nur eine moglichst”kleine“ Relation S ⊆ R dar,

fur die S∗ = R gilt. GS wird dann Hasse-Diagramm von R genannt.

. Beispiel: ≤N0

0 1 2 3 . . .

. Beispiel: Hasse-Diagramm zu |N ∩ ([10]× [10])

2 3 5 7

4 6 9 10

. Beispiel: Hasse-Diagram zu ⊆ auf P([3])

1, 2 1, 3 2, 3

1, 2, 3

. Beispiel: Hasse-Diagramm zur Ordnung auf Aquivalenzrelationen uber1, 2, 3:R S falls:

• wann immer a R b, dann a S b,

• oder aquivalent R ⊆ S

1, 2, 3

1, 2, 3 1, 3, 2 1, 2, 3

1, 2, 3

• Noch ein paar Standardbegriffe bzgl. einer Ordnung R ⊆ A×A:

• m ∈ A ist ein maximales Element bzgl. R, falls:

Gilt mRa fur ein a ∈ A, dann auch aRm und damit a = m.

.”Keine Kanten zu einem anderen Element“

. Erinnerung: bzgl. partieller Ordnungen kann es auch unvergleichbare Objektegeben.

• m ∈ A ist das großte Element bzgl. R, falls aRm fur jedes a ∈ A gilt.

•”Keine Kanten zu einem anderen Element, aber von jedem anderen Element

eine Kante.“

. Ist R total, dann ist ein maximales Element sofort auch das großte Element.

• Entsprechend definiert man ein minimales und das kleinste Element bzgl. R.

• Erinnerung: Fur eine binare Relation R ⊆ A×A haben wir die transitive HulleR+ :=

⋃k∈NR

k und die reflexiv-transitive Hulle R∗ =⋃

k∈N0Rk definiert.

• Die Teilmengenrelation ⊆ ist eine Halbordnung auf der Menge aller binarenRelationen auf A.

• Bzgl. ⊆ lassen sich R∗ und R+ auch wie folgt charakterisieren:

• R+ ist das kleinste Element bzgl. ⊆ in

S ⊆ A×A | R ⊆ S und S ist transitiv

d.h. ist S transitiv mit R ⊆ S, dann gilt R+ ⊆ S.

• R∗ ist das kleinste Element bzgl. ⊆ in

S ⊆ A×A | R ⊆ S und S ist reflexiv und transitiv

d.h. ist S reflexiv und transitiv mit R ⊆ S, dann gilt R∗ ⊆ S.

• Fakt: Mit R ist auch R−1 eine Ordnung. (”Pfeile umdrehen“)

• Begriffe”minimal“ und

”maximal“ bzw.

”kleinstes“ und

”großtes“ dual, d.h.

beim Wechsel von R zu R−1 vertauschen sie sich.

• Beispiele:

• Bzgl. |N ist 1 das kleinste Element, es gibt keine maximalen Elemente.

• Bzgl. |−1N (

”ist Vielfaches“) ist 1 das großte Element.

• Bzgl. |N\1 sind die Primzahlen die minimalen Elemente.

• Bzgl. ≤Z gibt es keine minimalen/maximalen Elemente

• Bzgl. ≤N0 ist 0 das kleinste Element

• Bzgl. ≥N0 ist 0 das großtes Element

1 Grundlagen

Einfuhrung

Mengen

Relationen

Funktionen

Visualisierung

Operationen auf Funktionen

Eigenschaften von Funktionen

Zusammenfassung

Funktionen

Funktionen 92

• Eine Relation R ⊆ A×B ist eine Funktion (Abbildung), falls:

Fur jedes a ∈ A gibt es genau ein b ∈ B mit (a, b) ∈ R• D.h. es gibt mindestens ein b ∈ B mit aRb UND

• wann immer auch aRb′, dann gilt b = b′.

. Konventionen/Anmerkungen (wie in der Schule):

• f, g, h, . . . als Funktionenbezeichner.

•”f : A→ B“ um zu sagen, dass f ⊆ A×B eine Funktion von A nach B ist.

•”f(a)“ steht fur das eindeutige b ∈ B mit (a, b) ∈ f .

Beachte: Schreibrichtung dreht sich damit um:”afb“ vs.

”b = f(a)“

In manchen Fallen ist”af“ praktischer als

”f(a)“.

• Definition von Funktionen mittels”7→“ z.B.: f : R→ R, x 7→ x2 + 1

Funktionen 93

• Weitere Konventionen/Anmerkungen:

• Fur die Menge aller Funktionen von A nach B schreibt manBA := f : A→ B.

• Gilt A =×k

i=1Ai, dann schreibt man einfach f(a1, . . . , ak) statt

f((a1, . . . , ak)).

. k bezeichnet man dann als Stelligkeit oder Aritat von f .

. Entsprechend bezeichnet man f :×k

i=1Ai → B auch als k-are Funktion z.B.

nullar, unar, binar, tertiar usw.

. Spezialfall nullare Funktion: f : () → B

Ist nur fur das leere Tupel (=”kein Argument“) definiert und ordnet diesem

immer denselben Wert zu.

Funktionen 94

• Weitere Konventionen/Anmerkungen:

• Die Urbildmenge Dom(f) einer Funktion f : A→ B ist die Menge A.

Die Bildmenge Rng(f) von f ist die Menge f(a) | a ∈ A.

Allgemeiner definiert man fur X ⊆ A und Y ⊆ B:

• f−1(Y ) = a ∈ A | f(a) ∈ Y ⊆ Dom(f) (Urbilder von Y )

• f(X) = f(a) | a ∈ X ⊆ Rng(f) (Bilder von X)

. Nach unserer Definition muss eine Funktion f : A→ B jedem a ∈ A ein Bildf(a) zuweisen. Solche Funktionen werden auch als total bezeichnet.

• Als partielle Funktion bezeichnet man entsprechend eine Relation f ⊆ A×Bbzgl. der jedes a ∈ A mit hochstens einem b ∈ B in Relation steht.

. Kurz”f : A → B“, um darauf hinzuweisen, dass f nur partiell ist.

• f : A→ B (totale) Funktion: Dom(f) = A

• f : A → B partielle Funktion: Dom(f) ⊆ A

. Partielle Funktionen werden in der Informatik haufig benutzt, um u.U. nichtterminierende Programme zu beschreiben.

Funktionen

Visualisierung

Funktionen: Visualisierung 96

• Visualisierung einer Funktion f : A→ B (wie in der Schule) durch einenbipartiten Graphen mit

”Knubbel“ fur A links und

”Knubbel“ fur B rechts.

. Beispiel: f = (a, 1), (b, 1), (c, 2) ⊆ A×B fur A = a, b, c und B = [3]

Als Funktion: Als Relation:

Funktionen: Visualisierung 97

• Visualisierung einer Funktion f : A→ B (wie in der Schule) durch einenbipartiten Graphen mit

”Knubbel“ fur A links und

”Knubbel“ fur B rechts.

. Beispiel: f = (a, a), (b, a), (c, b) ⊆ A×A fur A = a, b, c

Als Funktion: Als Relation:

. Fur A = B Darstellungen unterschiedlich; Darstellung als Relation nutzlich,falls man an der Sequenz x, f(x), f(f(x)), . . . interessiert ist (siehePermutationen).

Funktionen

Operationen auf Funktionen

Funktionen: Operationen 99

• Abbildungen der Form f : Ak → A werden auch als k-stellige Operationenauf A bezeichnet.

• Beispiele: Addition und Multiplikation +R, •R : R× R→ R auf R

• Fur binare Operationen verwendet man ublicherweise die Infixnotation:

(x +R y) statt +R(x, y); (x • Ry) statt •R(x, y)

. Haufig verwendet man ⊕,,⊗, u.a. Symbole als Bezeichner fur binareOperationen.

. Meistens lasst man auch die außersten Klammern weg, falls keineMissverstandnisse entstehen konnen, also z.B. nur a b statt (a b)

• Eine binare Operation : A×A→ A ist

• assoziativ falls (a b) c = a (b c) fur alle a, b, c ∈ A.

• kommutativ falls a b = b a fur alle a, b ∈ A.

• idempotent falls a a = a fur alle a ∈ A.

Funktionen: Komposition 100

• Komposition (Nacheinanderausfuhrung) (g f)(a) := g(f(a)) vonFunktionen f : A→ B und g : B → C

(g f) : A→ C, a 7→ g(f(a))

. Anmerkungen:

• Lies”g f“ als

”g nach f“

• Komposition ist assoziativ (als Operation auf die Menge der Funktionen), abernicht kommutativ:

(h (g f))(a) = h((g f)(a))

= h(g(f(a)))

= (h g)(f(a)) = ((h g) f)(a)

Funktionen: Komposition 101

• Komposition (Nacheinanderausfuhrung) (g f)(a) := g(f(a)) vonFunktionen f : A→ B und g : B → C

(g f) : A→ C, a 7→ g(f(a))

. Beachte umgekehrte Lese/Schreibrichtung im Vergleich zu Relationen:

Relationales Produkt Komposition

fg = (a, g(f(a))) | a ∈ A = (g f)

Funktionen

Eigenschaften von Funktionen

Injektive, surjektive und bijektive Funktionen 103

• Erinnerung:

Fur f : A→ B und Y ⊆ B bezeichnet f−1(Y ) = a ∈ A | f(a) ∈ Y dieMenge der Urbilder von Y .

• Eine Funktion f : A→ B ist

• injektiv, falls aus f(a) = f(a′) stets a = a′ folgt.

Aquivalent:∣∣f−1(b)

∣∣ ≤ 1 fur jedes b ∈ B

• surjektiv, falls fur jedes b ∈ B ein a ∈ A mit f(a) = b gibt.

Aquivalent: f(A) = B, Rng(f) = B,∣∣f−1(b)

∣∣ ≥ 1 fur jedes b ∈ B.

• bijektiv, falls sie sowohl injektiv als auch surjektiv ist.

Aquivalent:∣∣f−1(b)

∣∣ = 1 fur jedes b ∈ B.

. Eine bijektive Funktion f : A→ A nennt man Permutation.

Funktionen: Eigenschaften 104

• Beispiele:

Funktionen: Umkehrfunktion 105

• Ist f bijektiv, dann ist auch (b, a) | b ∈ B, a ∈ f−1(b) ∈ AB eineFunktion, die man als Umkehrfunktion/Inverse von f bezeichnet, und fur dieman ebenfalls die Notation

”f−1“ verwendet.

. Beweis, dass R := (b, a) | b ∈ B, a ∈ f−1(b) ∈ AB .

Zu zeigen: Jedes b ∈ B steht mit genau einem a ∈ A bzgl. R in Relation.

• Jedes b ∈ B hat ein Bild.

Fixiere ein beliebiges b ∈ B

Da f surjektiv, gibt es ein a ∈ A mit f(a) = b bzw. a ∈ f−1(b).

Also (b, a) ∈ R.

• Falls (b, a) ∈ R und (b, a′) ∈ R, dann a = a′.

Nach Definition von R: a, a′ ∈ f−1(b), also f(a) = b = f(a′).

Da f(a) = b = f(a′) und f injektiv gilt a = a′.

• Einige Eigenschaften und erste Beweise:

• Ist f : A→ B eine bijektive Funktion, dann auch f−1.

Exkurs: Indirekte Beweise 107

Die Aussage”wenn A dann B“ ist aquivalent zu

”wenn nicht B, dann nicht A“.

Die Aussage”wenn nicht B, dann nicht A“ heisst die Kontraposition der Aussage

”wenn A dann B“.

In einem indirekten Beweis wird die Kontraposition der Aussage bewiesen.Die Hypothese ist

”nicht B“ und das Ziel

”nicht A“.

• Ist f : A→ B eine bijektive Funktion, dann ist f−1 injektiv.

. Zu zeigen: Ist f : A→ B eine bijektive Funktion und b, b′ ∈ B mit b 6= b′,dann gilt f−1(b) 6= f−1(b′).

. Kontraposition: Gilt f−1(b) = f−1(b′) dann entweder b = b′ oder f : A→ Bist keine bijektive Funktion (oder beides).

. Beweis der Kontraposition: Wenn f−1(b) = f−1(b′) := a und b 6= b′, dann istf : A→ B sogar keine Funktion, da b und b′ zwei verschiedene Bilder von asind.

• Ist f : A→ B eine bijektive Funktion, dann auch f−1.

. Beweis:

. f−1 ist injektiv.

Erledigt.

. f−1 ist surjektiv.

Sei a ∈ A beliebig. Setze b := f(a). Dann gilt bereits f−1(b) = a.

• Sei f : A→ B eine bijektive Funktion. Dann ist f−1 die einzige Funktion gaus AB mit der Eigenschaft (g f) = IdA und (f g) = IdB .

. Beweis:

• Es gilt (f−1 f) = IdA.

Sei a ∈ A beliebig fixiert. Sei b = f(a). Dann gilt a ∈ f−1(b), alsoa = f−1(b) = f−1(f(a)).

• Hat g : B → A die Eigenschaft (g f) = IdA, dann gilt g = f−1.

f−1 = IdA f−1 = (g f) f−1 = g (f f−1) = g IdB = g

• (f f−1) = IdB . Selber machen!

• Hat g : B → A die Eigenschaft (f g) = IdB , dann gilt g = f−1. Selbermachen!

• Fur f : A→ B und g : B → A gelte (g f) = IdA und (f g) = IdB .

Dann sind f, g bijektiv mit f−1 = g und g−1 = f .

. Beweis:

• f ist injektiv, da fur a, a′ ∈ A mit f(a) = f(a′) gilt:

a = IdA(a) = (g f)(a) = g(f(a)) = g(f(a′)) = (g f)(a′) = IdA(a′) = a′

• f ist surjektiv, da g(b) ein Urbild fur b ∈ B bzgl. f ist:

b = IdB(b) = (f g)(b) = f(g(b))

• Entsprechend folgt, dass g bijektiv ist.

• Da f−1, g−1 eindeutig, folgt f = g−1 und g = f−1.

• Konsequenz: Ist f bijektiv, dann gilt f = (f−1)−1.

• Sind f : A→ B und g : B → C bijektiv, dann auch (g f) : A→ C und es gilt(g f)−1 = (f−1 g−1).

. Beweis:

• Bereits gezeigt: Da f und g bijektiv, existieren f−1, g−1.

• Es gilt: (g f) (f−1 g−1) = IdC und (f−1 g−1) (g f) = IdA.

(g f) (f−1 g−1) = g f f−1 g−1 = g IdB g−1 = g g−1 = IdC

Entsprechend: (f−1 g−1) (g f) = IdA

• Wie auf letzter Folie gezeigt:

Damit sind (g f), (f−1 g−1) bijektiv mit (g f)−1 = (f−1 g−1).

• Ist (g f) : A→ C bijektiv, dann ist f : A→ B injektiv und g : B → Csurjektiv.

. Beweis:

• Setze h := (g f). Da h bijektiv, existiert h−1.

(Das bedeutet nicht, dass f−1 : B → A, g−1 : C → B existieren.)

• f ist injektiv, da:

Mit f(a) = f(a′) ergibt sich h(a) = h(a) =: c und daher aucha = h−1(c) = a′.

• g ist surjektiv, da b = f(h−1(c)) ein Urbild von c ∈ C ist.

• Weitere Eigenschaften (Beweise zur Ubung):

• Ist f injektiv, dann ist g : A→ f(A), a 7→ f(a) bijektiv.

• Ist f : A→ A injektiv und A endlich, dann ist f bijektiv.

• Ist f : A→ A surjektiv und A endlich, dann ist f bijektiv.

• Sind f : A→ B und g : B → C injektiv/surjektiv, dann auch (g f).

• Ist (g f) surjektiv, dann auch g.

• Ist (g f) injektiv, dann auch f .

• f−1(X ∪ Y ) = f−1(X) ∪ f−1(Y ) und f−1(X ∩ Y ) = f−1(X) ∩ f−1(Y ).

• f(X ∪ Y ) = f(X) ∪ f(Y ), aber f(X ∩ Y ) ⊆ f(X) ∩ f(Y ).

f ist genau dann injektiv, wenn stets f(X ∩ Y ) = f(X) ∩ f(Y ) gilt.

1 Grundlagen

Einfuhrung

Mengen

Relationen

Funktionen

Multimengen

Zusammenfassung

Kardinalitat von Mengen 116

. Grundlage fur den Vergleich von unendlichen Mengen:

• Eine Injektion f : A→ B erlaubt es jedes Element aus a ∈ A eindeutig mitf(a) ∈ B zu identifizieren. B hat damit anschaulich

”mindestens so viele

Elemente“ wie A.

• Eine Bijektion f : A→ B erlaubt es, die Elemente von A und B eindeutig zu

”paaren“. B hat damit anschaulich

”genau so viele“ Elemente wie A.

. Man definiert daher:

•”|A| ≤ |B| (lies: B mindestens so machtig wie A)“ durch

”es gibt eine injektive Funktion f : A→ B“

•”|A| = |B| (lies: A,B gleichmachtig)“ durch

”es gibt eine bijektive Funktion f : A→ B“

• Entsprechend bedeutet”|A| < |B| (echt machtiger)“, dass es zwar eine

Injektion f : A→ B, aber keine Bijektion g : A→ B gibt.

. Gefahr: Machen diese Definitionen uberhaupt Sinn?

• Wenn |A| ≤ |B| und |B| ≤ |C|, gilt auch |A| ≤ |C| ?

Ja, da die Komposition injektiver Funktionen wieder injektiv ist.

• Gilt fur beliebige Mengen: wenn |A| ≤ |B| und |A| ≥ |B|, dann |A| = |B| ?

Ohne Beweis: Satz von Cantor-Bernstein-Schroder

Sind f : A→ B und g : B → A injektiv, dann gibt es h : A→ B bijektiv.

• Es folgt: |A| = |B| wenn es injektive Funktionen f : A→ B und g : B → Agibt.

• Es folgt: |A| < |B| wenn es eine injektive Funktion f : A→ B aber keineinjektive Funktion g : B → A gibt.

• Beispiele:

• |N| = |2N| mittels der Injektionen N→ 2N, n 7→ 2n und 2N→ N, n 7→ n, oderder Bijektion 2N→ N, n 7→ n/2

• |N| = |Z| mittels der Bijektion

f : Z→ N, z 7→

2z + 1 falls z ≥ 0−2z sonst

• |N| ≤ |N0| ≤ |Z| ≤ |N|, also N,N0,Z gleichmachtig.

• |N| = |N× N| mittels der Bijektion

f : N× N→ N, (n,m) 7→ 1

2(m + n− 1)(m + n− 2) + m

. Damit auch: |Q| = |N|

• Man nennt eine Menge A abzahlbar, falls |A| ≤ |N|; ansonsten nennt man Auberabzahlbar.

Bemerkungen:

• Man bezeichnet |A| als Kardinalzahl (fur eine Menge A).

• Der Satz von Cantor-Bernstein-Schroder sagt, dass ≤ auf den Kardinalzahlenantisymmetrisch ist.

• Intuition: A ist abzahlbar wenn es moglich ist, jedes Element von A mit einereindeutigen Identifikationsnummer (aus N) zu versehen.

• Aquivalente Intuition: A ist abzahlbar wenn es eine (endliche oderunendliche) Liste gibt, die alle Elemente von A enthalt.

Kardinalitat von Mengen: Uberabzahlbare Mengen 120

• Es gilt stets |A| < |P(A)| (Satz von Cantor).

• Mit f : A→ P(A), a 7→ a folgt |A| ≤ |P(A)|.

Es muss noch gezeigt werden, dass es keine Bijektion f : A→ P(A) gibt.

. Beweis mittels Diagonalisierung:

Wir nehmen an, dass g : A→ P(A) bijektiv ist.

Setze M = a ∈ A | a 6∈ g(a) ∈ P(A).

Da g angeblich bijektiv, gibt es ein m ∈ A mit g(m) = M .

Aber: m ∈M genau dann, wenn m 6∈ g(m) = M , was nicht mit unserenAnnahmen uber Mengen vereinbar ist.

• Noch mehr Beispiele:

• |0, 1∗| = |N| wegen Bijektion 0, 1∗ → N, w 7→ (1w)2, wobei (w)2 die Zahlmit binarer Darstellung w bezeichnet.

• |A∗| = |N| fur jede endliche Menge A.

• Die Menge der C/Java/Python-Programme ist abzahlbar.

• |N| < |[0, 1]| wegen |N| < |P(N)| =∣∣0, 1N∣∣ = |[0, 1]|

• |(0, 1]| = |[1,∞)| wegen Bijektion [1,∞)→ (0, 1], x→ 1/x

• |(0, 1]| = |R|

• |R| < |P(R)| =∣∣RR∣∣

• |N| < |P(N)| = |R| < |P(P(N))| < . . .

Kardinalitat von Mengen: Beweistechniken 122

• Fur |A| = |B|:• Direkt: gebe eine Bijektion A→ B oder B → A an.

• Mit Hilfe des Satzes von Cantor-Bernstein-Schroder: gebe Injektionen A→ Bund B → A an. (I.d.R. viel einfacher!)

• Fur |A| < |B|: bilde eine Ungleichungskette

|A| ≤ |C1| ≤ · · · ≤ |Cn| ≤ |B|

wobei mindestens ein Glied nicht nur ≤ sondern auch < erfullt.

• Fur |Ci| ≤ |Ci+1| gebe eine Injektion an (Spezialfall: Ci ⊆ Ci+1).

• Fur |Ci| < |Ci+1| benutze den Satz von Cantor.

Multimengen

Multimengen 124

• Menge”=“ Zusammenfassung von Objekten ohne Beachtung von

Vielfachheiten und Reihenfolge

• Multimenge”=“ Zusammenfassung von Objekten ohne Beachtung der

Reihenfolge, aber unter Beachtung von Vielfachheiten.

. In Datenbanken werden Multimengen auch als”Bags“ bezeichnet: eine

Tasche beachtet die Vielfachheit eines Objekts, aber eben nicht dieReihenfolge (

”set semantics“ vs.

”bag semantics“)

. Haufig verwendet man auch”“ zur Notation von Multimengen, wenn klar

ist, dass eine Multimenge gemeint ist.

Im Folgenden jedoch”M“ fur Multimengen:

. Beispiel:

a, b, c, aM = b, c, a, aM 6= b, a, cM

= a, b, c = a, b, b, c 6= a, b, b, cM

Multimengen 125

• Fur ein festes Universum (Grundmenge) Ω lassen sich Multimengen mittelsZahlfunktionen m ∈ NΩ

0 darstellen

. Z.B. fur Ω = a, b, c, d:

a, b, c, aM = (a, 2), (b, 1), (c, 1), (d, 0)

. Eine Menge A ⊆ Ω lasst sich entsprechend als Funktion 0, 1Ω auffassen;diese Funktion nennt man die charakteristische Funktion von A (aus diesemGrund schreibt man auch haufig 2Ω fur P(Ω)).

• Die Vereinigung zweier Multimengen ist dann einfach die punktweise Additionder Zahlfunktionen.

. Der Schnitt zweier Multimengen kann z.B. als das punktweise Minimum derZahlfunktionen definiert werden.

1 Grundlagen

Einfuhrung

Mengen

Relationen

Funktionen

Zusammenfassung

Grundlagen – Zusammenfassung 128

• Mengen:

• Grundlage fur alle anderen Zusammenfassungen, Relationen, Funktionen

• Operationen: Schnitt, Vereinigung, Differenz, sym. Differenz, Komplement(bzgl. Grundmenge), Potenzmenge

• Visualisierung: Venn-Diagramme, KV-Diagramme

• Relationen: R ⊆ A1 ×A2 × . . .×Ak

• Grundlage fur relationale Datenbanken, Funktionen, Ordnungen

• Operationen (neben Mengenoperationen): Join, Projektion, Konkatenation,relationales Produkt, (reflexive-)transitive Hulle

• Visualisierung: Digraph

• Ordnungen: R ⊆ A×A• R reflexiv, antisymmetrisch und transitiv

• Grundlage fur Optimierung/Maximierung/Minimierung, Anordnung vonSuchergebnissen, etc.

• Visualisierung: Hasse-Diagramm

• Aquivalenzrelationen: R ⊆ A×A• R reflexiv, symmetrisch und transitiv

• Grundlage fur Abstraktion

• Visualisierung: Digraph, Aquivalenzklassen

• Funktionen: f : A→ B = BA ⊆ A×B• Grundlage fur Beschreibung von Eingabe-Ausgabe-Verhalten von Programmen

• Visualisierung: Funktionsgraph (manchmal Digraph als Relation)

• Kardinalitat:

• Vergleich von Mengen bzgl. der Anzahl der zusammengefassten Objekte

• |A| ≤ |B|, falls f : Ainjektiv−−−−→ B existiert.

• |A| = |B|, falls |A| ≤ |B| und |B| ≤ |A|,

oder falls f : Abijektiv−−−−→ B existiert.

Diskrete Strukturen GrundlagenMengen in der Informatik 10. Reihenfolge der Objekte, mehrfache...

Documents