Praktische Informatik 1

Kapitel 1: Mathematische Grundlagen

1.1 Mengen, Multimengen, Tupel, Funktionen, Halbordnungen

Eine Menge ist eine Zusammenfassung von (endlich oder unendlich vielen) verschiedenen Dingen unserer Umwelt oder Vorstellungswelt, welche Elemente dieser Menge genannt werden. Wir schreiben, um auszusagen, dass das Ding Element der Mengeist.

Andere Sprechweisen: ist inenthalten, oderenthält.

Um auszudrücken, dass nicht inenthalten ist, schreiben wir . Die Schreibweise steht für und … und , und ist die Menge, die genau die Elemente enthält.

Beispiele für Mengen sind:

• 
  N: Die Menge der natürlichen Zahlen 1,2,3,…
  
• 
  N₀: Die Menge der Kardinalzahlen (natürlichen Zahlen einschließlich der Null): 0,1,2,3,…
  
• 
  Z: Menge der ganzen Zahlen …, -3, -2, -1, 0, 1, 2, 3, …
  
• 
  Q, R: Menge der rationalen bzw. reellen Zahlen
  
• 
   oder { }: leere Menge
  
• 
  B oder boolean = {true, false} oder {1,0} oder {tt, ff} oder {w, f} oder {L,O}: Menge der Wahrheitswerte
  
• 
  {Adam, Eva}: Menge der ersten Menschen
  
• 
  {A, B, C, …, Z}: Menge der Großbuchstaben im lateinischen Alphabet
  

In den Programmiersprachen Groovy und Java gibt es die folgenden vordefinierten Mengen:

• 
  Integer oder int: {-2147483648 … 2147483647}
  
• 
  Short: {-32768, …, 32767}
  

• 
  Byte: {-128, …, -127} Menge der ganzen Zahlen zwischen -128 und 127
  

• 
  Long: {-9223372036854775808, …,-9223372036854775808} (Postfix „L“)
  
• 
  BigInteger: „große“ natürliche Zahlen (Postfix „g“, z.B. 45g)
  
• 
  Dezimalzahlen, Gleitkommazahlen,
  
• 
  Characters und Strings, Boolean
  

Die Menge ist eine Teilmenge von (), wenn jedes Element von auch Element von ist. Die Mengen und sind gleich (), wenn sie die gleichen Elemente enthalten (Extensionalitätsaxiom). Für jede (endliche) Mengebezeichnet die Kardinalität, d.h. die Anzahl ihrer Elemente. Neben der Aufzählung ihrer Elemente können Mengen durch eine charakterisierende Eigenschaft gebildet werden (Komprehensionsaxiom). Beispiel: byte = {x∈ Z | -128x und x127}. Auf diese Weise können auch unendliche Mengen gebildet werden.

Die unbeschränkte Verwendung der Mengenkomprehension kann zu Schwierigkeiten führen (Russells Paradox: „die Menge aller Mengen, die sich nicht selbst enthalten“), daher erlaubt man in der axiomatischen Mengenlehre nur gewisse Eigenschaften.

Auf Mengen sind folgende Operationen definiert:

• 
  Durchschnitt: .
  
• 
  Vereinigung: .
  
• 
  Differenz: .
  

Beispiele: NN₀=N₀ , NN₀=N , N – N₀ =, N₀ – N =0. Durchschnitt und Vereinigung sind kommutativ und assoziativ. Daher kann man diese Operationen auf beliebige Mengen von Mengen ausweiten:

• 
  .
  
• 
  .
  

Von Mengen kommt man zu „Mengen höherer Ordnung“ durch die Potenzmengenbildung: Wenneine Menge ist, so bezeichnet oderdie Menge aller Teilmengen von. Cantor bewies, dass die Potenzmenge einer Menge immer mehr Elemente enthält als die Menge selbst. Speziell gilt für jede endliche Menge: Wenn , so ist .

Beispiel: , und .

Multimengen

Während Mengen die grundlegenden Daten der Mathematik sind, hat man es in der Informatik oft mit Multimengen zu tun, bei denen Elemente „mehrfach“ vorkommen können. Beispiele sind

• 
  eine Tüte mit roten, gelben und grünen Gummibärchen,
  
• 
  die Vornamen der Studierenden dieser Vorlesung,
  
• 
  die Multimenge der Buchstaben eines bestimmten Wortes, usw.
  

Multimengen können notiert werden, indem man zu jedem Element die entsprechende Vielfachheit angibt, z.B. ist {A:3, B:1, N:2} die Multimenge der Buchstaben im Wort BANANA. Formal können Multimengen definiert werden als Funktionen von einer Grundmenge in die Menge N₀ der Kardinalzahlen, siehe unten.

Folgen

Aus Mengen lassen sich durch Konkatenation Tupel und Folgen bilden. Der einfachste Fall ist dabei die Paarbildung mit dem kartesischen Produkt. Wenn und Mengen sind, so bezeichnet die Menge aller Paare von Elementen, deren erster Bestandteil ein Element aus und deren zweiter eines aus ist. Da die runden Klammern für vielerlei Zwecke verwendet werden, verwendet man manchmal zur Kennzeichnung von Paaren auch spitze oder, besonders in Programmiersprachen, eckige Klammern.

Beispiele: NB ={(1,tt),(1,ff),(2,tt),(2,ff), (3,tt),…}, N=,
N{0}={(1,0), (2,0), (3,0), …}, NN₀={(1,0), (1,1), (1,2), …, (2,0), (2,1), …}

Eine Verallgemeinerung ist das n-stellige kartesische Produkt, mit dem n-Tupel gebildet werden:

2-Tupel sind also Paare, statt 3-, 4- oder 5-Tupel sagt man auch Tripel, Quadrupel, Quintupel usw. Die zur Produktbildung umgekehrten Operationen, mit denen man aus einem Produkt die einzelnen Bestandteile wieder erhält, bezeichnet man als Projektionen:

Falls alle gleich sind, so schreiben wir statt auchund nennen eine Folge oder Sequenz der Länge über . In Programmiersprachen heißen Folgen auch Arrays, Felder oder Reihungen. Wichtige Spezialfälle sind und . Im ersten Fall ist die einelementige Folge (x) etwas anderes als das Element x. Im zweiten Fall ist die leere Folge () unabhängig von der verwendeten Grundmenge. Achtung: Die leere Folge ist nicht zu verwechseln mit der leeren Menge!

enthält nur Sequenzen einer bestimmten fest vorgegebenen Länge n. Unterverstehen wir die Menge, die alle beliebig langen Folgen über enthält:

.

Wenn wir nur nichtleere Folgen betrachten wollen, schreiben wir :

.

Eine Liste in der Programmiersprache Groovy ist ein Element von , wobei M die Menge aller Objekte (Zahlen, Buchstaben, Listen, …) ist.

Beispiele: [1, 3, 5, 7] oder [17.5, "GP", 1.234f, 'a', 1e99]
Hier sind einige Groovy-Tatsachen zu Listen (http://groovy.codehaus.org/JN1015-Collections). In Java können diese Listen mit dem public interface List nachgebildet werden (http://java.sun.com/j2se/1.4.2/docs/api/java/util/List.html).
assert [0, "a", 3.14].class == java.util.ArrayList

assert [0, 4, 7] + [11] == [0, 4, 7, 11]

assert [0, 4, 7] - [4] == [0, 7]

assert [0, "a", 3.14] * 2 == [0, "a", 3.14, 0, "a", 3.14]

assert [0, 4, 7] != [0, 7, 4]

assert [] != [0]

assert [] != [[]]

assert [[],[]] != [[]]

assert [[],[]].size == 2

assert [0,4,7][2] == 7

x=[0,4,7]; assert x[2] == 7

x=[0,4,7]; x[2]=3; assert x == [0,4,3]

x=[0,4,7]; x[2]=3; x[5]=2; assert x == [0, 4, 3, null, null, 2]

x=[0,4,7]; assert x.contains(4)

x=[0,4,7]; assert (7 in x)

x=[0,4,7]; x.each{println(it + " sq = " + (it*it))}
Mengen können als spezielle (ungeordnete) Listen aufgefasst werden, bei denen jedes Element nur einmal vorkommt und die Reihenfolge egal ist:
Set x=[0,4,7], y= [7,4,0]; assert x == y

Set z=[0,4,7,4,0]; assert z == y

Relationen und Funktionen

Eine Relation zwischen zwei Mengen und ist eine Teilmenge von . Wenn zum Beispiel M={Anna, Beate} und J={Claus, Dirk, Erich}, so ist liebt={(Anna, Claus), (Beate, Dirk), (Beate, Erich)} eine Relation zwischen M und J. Relationen schreibt man meist in Infixnotation, d.h., statt (Beate, Dirk)liebt schreibt man (Beate liebt Dirk). Falls , so sagen wir, dass die Relation überdefiniert ist. Typische Beispiele sind die Relationen  und = über den natürlichen Zahlen, oder die Verbindungsrelation zwischen Städten im Streckennetz der Air Berlin. Eine Relation heißt (links-)total, wenn es zu jedem ein mitgibt. Sie heißt (rechts-)eindeutig, wenn es zu jedem höchstens ein mitgibt. Eine eindeutige Relation nennt man Abbildung oder partielle Funktion, eine totale und eindeutige Relation heißt Funktion. Bei Funktionen schreiben wir und für und . Die Menge der , für die es ein mitgibt, heißt der Definitionsbereich oder Urbildbereich (domain) der Abbildung; die Menge der , für die es ein mitgibt, heißt der Wertebereich oder Bildbereich (range) der Funktion oder Abbildung.

Eine Funktion mit endlichem Definitionsbereich lässt sich angeben durch Auflistung der Menge der Paare (x,y) mit . In Groovy nennt man eine solche Funktion Map und

notiert sie [x₁:y₁, x₂:y₂,....,x_n:y_n], also z.B.

[1:5, 2:10, 3:15] oder

["Name":"Anton", "id":573328], aber auch

[3.14:'a', "a":2010, 10:10, 7e5:0]

Beachte: [1:5, 2:10, 3:15] == [2:10, 3:15, 1:5]
Hier wieder einige Groovy Tatsachen über Maps (http://groovy.codehaus.org/JN1035-Maps):
assert [A:3, B:1, N:2]

assert [A:3, B:1, N:2].B == 1

assert [A:3, B:1, N:2] == [B:1, A:3, N:2]

assert [A:3, B:1, N:2] + [C:5] == [A:3, B:1, N:2, C:5]

assert [A:3, B:1, N:2] + [A:1] == [A:1, B:1, N:2]

// [A:3, B:1, N:2] - [A:1] ist undefiniert

// [97:"a", 98:"b", 99:"c"].98 == 'b' ist ein Syntaxfehler

assert [97:"a", 98:"b", 99:"c"].get(98) == "b"

assert [97:"a", 98:"b", 99:"c"].get(100) == null

x=[:]; x[97]="a"; x[98]="b"; assert x == [97:"a", 98:"b"]

Genau wie oben lassen sich auch die Begriffe Relation und Funktion verallgemeinern. Eine n-stellige Relation zwischen den Mengen ist eine Teilmenge von . Einstellige Relationen heißen auch Prädikate. Auch für Prädikate schreiben wir (Px) anstatt von (x)  P. Eine n-stellige Funktion f von nach ist eine (n+1)-stellige Relation zwischen und , so dass für jedes n-Tupel genau ein existiert mit .
Eine Funktion heißt (n-stellige) Operation auf . Beispiele für zweistellige Operationen sind + und * auf N, Z, Q und R. Die Differenz – ist auf Z, Q und R eine Operation, auf N ist sie nur partiell (nicht total). Die Division ist in jedem Fall nur partiell. Typische Prädikate auf natürlichen Zahlen sind prim oder even.
Wir haben Funktionen als spezielle Relationen definiert, Es gibt auch die Auffassung, dass der Begriff „Funktion“ grundlegender sei als der Begriff „Relation“, und dass Relationen eine spezielle Art von Funktionen sind. Sei. Dann ist die charakteristische Funktion B von in definiert durchtrue falls und false falls . Mit Hilfe der charakteristischen Funktion kann jede Relation zwischen den Mengen als Funktion von nach B aufgefasst werden. Diese Auffassung findet man häufig in Programmiersprachen, bei denen Prädikate als boolesche Funktionen realisiert werden.

Ordnungen

Die Relation überheißt

• 
  reflexiv, wenn für allegilt, dass.
  
• 
  irreflexiv, wenn für keingilt dass.
  
• 
  transitiv, wenn für allemitundgilt, dass.
  
• 
  symmetrisch, wenn für allemitgilt, dass.
  
• 
  antisymmetrisch, wenn für alle mit und gilt.
  

Eine reflexive, transitive, symmetrische Relation heißt Äquivalenzrelation.

Eine reflexive, transitive, antisymmetrische Relation heißt Halbordnung oder partielle Ordnung. Eine irreflexive, transitive, antisymmetrische Relation heißt strikte Halbordnung. Eine partielle Ordnung heißt totale oder lineare Ordnung, wenn für allegilt, dassoder. Bei einer totalen Ordnung lassen sich alle Elemente „der Reihe nach“ anordnen. Die Relation  ist eine totale Ordnung auf natürlichen und reellen Zahlen, nicht aber auf komplexen Zahlen. Ein einfacheres Beispiel für eine Halbordnung über Zahlen ist die Relation „ist Teiler von“.

Beispiel für reflexive, aber nicht antisymmetrische Relation:

Beispiel für eine antisymmetrische, aber nicht reflexive Relation: