Vertiefungsstoff
1. Mathematische Grundlagen
Der Foliensatz ruft wichtige, in der Vorlesung „Computersysteme und
Algorithmen“ benötigte mathematische Begriffe (u.a. Menge, Funktion)
und die dazugehörenden formale Notationen in Erinnerung.
Themen
Mengen
Relationen
Funktionen
Quantoren und logische Opertoren
Ordnungen
induktiv definierte Mengen
Maßeinheiten
1
Wofür braucht man eine Formelsprache?
Viele Jahrhunderte betreib man Mathematik
ohne eine spezielle Formelsprache.
Aufgaben wie
3*27 +x² = 106
wurden verbal formuliert. Lösungen wurden
häufig durch Ausprobieren und schrittweise
Näherungen ermittelt.
Doppelter falscher Ansatz (Regula falsi):
Rate für x zwei Werte und setze diese ein. Mache
abhängig von den Abweichungen neue
Schätzungen. (Iterationsverfahren!!)
Heute: Formelsprache
• verständlicher
• Formelmanipulation möglich
Mathematik:
Musik:
Chemie:
Tanzen:
Schach:
…
Adam Ries: Rechenbüchlein
folgt noch
Noten
Formeln
Tanzschritte
Schachnotation
La Cachucha, F. A. Zorn: Wikimedia Commons
Mengen
Definition: Menge
Eine Menge ist eine Zusammenfassung von (endlich oder unendlich vielen)
verschiedenen Dingen, welche Elemente dieser Menge genannt werden.
xM
das Ding x ist Element der Menge M
x ist Element von M
x ist in M
M enthält x
xM
x ist kein Element von M
x ist nicht in M
M enthält x nicht
x1 , ... , xn  M
x1  M und ... und xn  M
Notation von Mengen
M = { x1 , ... , xn }
falls die Menge M genau die Elemente x1 , ... , xn enthält.
M = { x | p(x) }
Das heißt, M ist die Menge, die all diejenigen Objekte x
enthält, welche die Bedingung p(x) erfüllen.
Beispiele:
 = {}
die leere Menge
Bool = { T, F }
Menge der Wahrheitswerte
Nat =  = { 1, 2, 3, ... }
Menge aller natürlichen Zahlen
UInt = 0 = { 0,1, 2, 3, ... } (unsigned int)
Menge aller natürlichen Zahlen mit 0
Int =  = { ... , -3, -2, -1, 0, 1, 2, 3, ... }
Menge der ganzen Zahlen
Rational =  = { <alle Brüche> }
Menge aller rationalen Zahlen
Real =  = { <alle rationalen und irrationalen Zahlen> } Menge aller reellen Zahlen
Even = { x | x   und x gerade }
= { 2x
| x   }
Odd = { x | x  und x ungerade }
= { 2x + 1 | x   }
Mengenoperationen
Vereinigung
M1  M2 = { x | x  M1 oder x  M2 }
Durchschnitt
M1  M2 = { x | x  M1 und x  M2 }
Differenz
M1 \ M2 = { x | x  M1 und x  M2 }
Beispiele
Even  Odd = Int
Even Odd = { }
Nat = UInt \ { 0 }
{ 2,3,5,7 }  { 2,4,6,8 } = { 2,3,4,5,6,7,8 }
{ 2,3,5,7 }  { 2,4,6,8 } = { 2 }
M1  M2
M1
M 1 \ M2
M2
M1  M2
M2 \ M1
Teilmengen und Gleichheit
Definition: Teilmenge / Obermenge
Eine Menge M ist eine Teilmenge einer Menge N, wenn jedes
Element von M auch zu N gehört.
Notation: M  N
M ist eine Teilmenge von N, N ist Obermenge von M.
Definition: Gleichheit von Mengen
Zwei Mengen M und N sind gleich, geschrieben M = N,
wenn sowohl M  N als auch N  M gilt.
Anmerkung
Um nachzuweisen, dass zwei Mengen M und N gleich sind, zeigt man:
i) N  M (d.h., jedes Element aus N ist auch in M enthalten)
und
ii) M  N (d.h., jedes Element aus M ist auch in N enthalten)
Teilmengen und Gleichheit
Beispiele : Für k Nat, k  0, sei kNat = { x Nat | k teilt x }
2Nat= { 2, 4, 6, 8, .... }
3Nat= { 3, 6, 9, 12 .... }
6Nat= { 6, 12, 18, 24, .... }
Dann gilt:
 6Nat  3Nat
 6Nat  2Nat
 und somit 6Nat 3Nat 2Nat
es gilt aber auch:
 3Nat  2Nat  6Nat
 und somit 6Nat = 3Nat 2Nat
x ist Vielfaches von k.
Kartesische Produkte
Definition: n-Tupel (Array, Liste mit n Elementen)
Sind x1 M1 , ... , xn Mn Elemente von Mengen M1 , ... ,Mn , so lässt sich ein
neuartiges zusammengesetztes Element (x1 , ... ,xn) bilden, ein n-Tupel.
Im Fall n = 2 heißt das aus x und y gebildete Paar (x,y) Tupel oder geordnetes Paar.
Im Fall n = 3 sagt man Tripel, im Fall n=4 von Quatrupel, im Fall n=5 Quintupel.
Definition: Gleichheit zwischen n-Tupel
(x1 , ... ,xn ) = (y1 , ... ,ym )
genau dann, wenn
n = m und x1 = y1 und
x2 = y2 und ... und xn = ym
Definition: Kartesisches Produkt (Produktmenge)
Sind M1 , ... ,Mn Mengen, so heißt die Menge:
M1  ...  Mn = { (x1 , ... ,xn ) | x1 M1 , ... , xn Mn }
das kartesische Produkt von M1 , ... ,Mn
Beispiel :
UInt  Bool = { (0,T), (0,F), (1,T), (1,F), (2,T), (2,F), ... }
Mengenpotenzen
Definition: Mengenpotenz
Ist M1 = M2 = ... = Mn = M , so heißt die Menge Mn mit
M  M  ...  M = Mn
die n-te Potenz von M. Die Elemente von
Mn heißen auch Folgen der Länge n über M.
n-mal
Beispiele:
 M0 ist eine einelementige Menge, die nur das 0-Tupel () enthält,
also ist M0 = { ( ) } für jede Menge M.
 Bool3 = { (F,F,F), (F,F,T), (F,T,F), (F,T,T), (T,F,F), (T,F,T), (T,T,F), (T,T,T) }
 2
= 2-dimensionaler Raum, 3 = 3-dimensionaler Raum
 2
= { (1,1), (1,2), (1,3), ...
(2,1), (2,2), (2,3), ...
…
}
Potenzmenge
Definition: Potenzmenge
Ist M eine Menge, so ist die Menge aller Teilmengen von M die
Potenzmenge (M) von M, also: (M) := { N | N  M }.
Beispiele
– ( {1,2,3} ) = { {1} {2} {3} {1,2}  {1,3} , {2,3} , {1,2,3} }
– (Bool) = { { }  { T } , { F } , { T, F } }
Achtung: Potenzmenge ist nicht zu verwechseln mit Mengenpotenz !!!
Mächtigkeit von Mengen
Definition: Mächtigkeit einer Menge
Die Mächtigkeit oder Kardinalität einer Menge ist M ein Maß für deren
Größe. Sie gibt an wie viele Elemente M besitzt.
Fall 1: M hat nur endlich viele Elemente. Dann kann man M eine
natürliche Zahl n zuordnen, wobei n die Anzahl der Elemente von M
angibt. Schreibweise: |M| = n.
Fall 2: M hat unendlich viele Elemente. Dann gibt es keine natürliche
Zahl n, die die Anzahl der Elemente von M angibt.
Aber: Oft kann man durch Angabe einer 1:1-Zuordnung die Menge M mit
der Menge der natürlichen Zahlen  oder der Menge reellen Zahlen 
vergleichen.
Findet man z.B. eine derartige Abbildung zwischen M und , dann hat M
genauso viele Elemente wie , d.h.: gilt |M| = ||.
Wenn |M| = || heißt M abzählbar, wenn |M| = || heißt M
überabzählbar.
Mächtigkeit von Mengen
Beispiele
– |{a,b,c}| = 3
– ||
– |Bool| = |{T,F}|= 2, |SQLBool| = |{T,F,U}| = 3 (U=Unknown, 3-wertige Logik)
– || ist abzählbar
– || = ||
– || ist überabzählbar, ||  ||
– | ({1,2,3}) | = 8 = 23 ;;; Mächtigkeit der Potenzmenge ({1,2,3})
Relationen
Definition: k-stellige Relation
Eine k-stellige Relation R ist eine Teilmenge eines kartesischen
Produktes M1  M2  ...  Mk.
Ist R  Mk , so heißt R eine k-stellige Relation auf M.
Beispiel: R  {1,2,3} x {a,b,c,d}
mit R = {(1,a), (1,d), (2, b), (2,d), (4,b), (4,d)}
M1
Beziehung zwischen Elementen
M2
1
a
2
b
3
c
4
d
Relationen
Definition: Charakteristisches Prädikat
Ist R  M1  M2  ...  Mk eine Relation, so können wir das
Prädikat R dieser Relation definieren:
R (m1 , ... , mk ) =
{
charakteristische
T falls (m1 , ... , mk )  R
F sonst
Ist umgekehrt  ein Prädikat auf M1  M2 ...  Mk , dann können wir
diesem Prädikat gehörende Relation RP definieren:
R = { (m1 , ... , mk ) | (m1 , ... , mk ) = T }
Beispiel
R  {1,2,3} x {a,b,c,d} , mit R = {(1,a), (1,d), (2, b), (2,d), (3,b), (3,d)}
dann gilt u.a.: R (1,a) = T aber R (1,c) = F
eine zu
Funktionen
Definition: Funktion (auch „eindeutige Abbildung“ oder Operation)
Es seien A und B Mengen. Eine Funktion f von A nach B ordnet
jedem Element x aus A genau ein Element y aus B zu.
A heißt Definitionsbereich (oder Urbildbereich) von f und
B heißt Wertebereich (oder Bildbereich) von f.
Notation
und
f: A  B
f(x) = y
xy
Sprechweise:
„f ist eine Funktion von A nach B“
„f angewandt auf x liefert den Wert y“
„x wird auf y abgebildet“
Beispiel 1
Beispiel 2
Es seien A=Nat und B=Nat:
even : Nat  Bool
succ : Nat  Nat
succ(x) = x+1 bzw. x  x+1
even(n) =
T, falls n gerade
{ F, falls n ungerade
Funktionen
Bemerkung
Eine Funktion ist eine spezielle Relation,
das heißt eine Menge von Paaren:
– f  Df  Wf
– Für jedes Element aus Df enthält f genau ein Element aus Df  Wf.
Beispiel
f:  , f(x) = x²
Das heißt: f = {(1,1), (2,4), (3,9), (4,16), (5, 25), …}    .
Eigenschaften von Funktionen
Definition: surjektive Funktion
Eine Funktion f : A  B ist surjektiv, (oder f ist eine Surjektion)
genau dann, wenn gilt:
Für jedes y B gibt es stets ein x A mit f(x) = y.
A
B
x
f
x
x
x
Jedes Element
aus B bekommt
mindestens
einen Pfeil ab.
x
Beispiele

abs: Int  UInt, abs(x) = x>0 ? x : -x

mod2 : Int  {0, 1},
mod2(x) =
0, falls x gerade
1, falls x ungerade
Eigenschaften von Funktionen
Definition: injektive Funktion
Eine Funktion f : A  B ist injektiv, (oder f ist eine Injektion)
genau dann, wenn gilt:
für x1, x2 A gilt: ist f(x1) = f(x2), dann ist auch x1 = x2.
A
x
B
f
x
Jedes Element
aus B bekommt
höchstens
einen Pfeil ab.
x
x
x
x
x
nachfolger : UInt  UInt, mit nachfolger(x) = x + 1
0 bekommt keinen Pfeil ab!
Wenn f injektiv ist, ist f ist umkehrbar: f-1: f(A)A, f(A) := {f(a): a  A}, d.h., man kann
die Pfeile umdrehen. Der Wertebereich ist die Menge der blauen Kästchen.
Wichtig z.B. für Codes: Nur injektive Codes können dekodiert werden.
Beispiel
Eigenschaften von Funktionen
Definition: bijektive Funktion
Eine Funktion f : A  B ist bijektiv (oder f ist eine Bijektion)
genau dann, wenn gilt:
f ist surjektiv und f ist injektiv
A
x
B
f
x
x
x
Alle Elemente aus B
werden von genau
einem Pfeil getroffen.
x
Eigenschaften bijektiver Funktionen: Ist f : A  B bijektiv, dann:
 lässt sich zu f eine Umkehrfunktion f -1 : B  A angeben (d.h., man kann die
Pfeile auch umdrehen); der Wertebereich ist B.
 müssen die Mengen A und B gleich viele Elemente umfassen.
Mächtigkeit von Mengen
Frage:
Wie überprüft man, ob eine Menge M genauso viele
Elemente hat wie Nat?
Antwort: Man prüft, ob eine Bijektion f : M   existiert.
Falls es solch eine Bijektion gibt, dann gilt: |M| = ||
d.h., M hat genauso viele Elemente wie , d.h. M ist abzählbar.
Beispiel
Behauptung: Die Menge der geraden natürlichen Zahlen GNat ist
ebenso mächtig wie die Menge der natürlichen Zahlen Nat.
Die Behauptung ist richtig, da es eine Bijektion gibt:
f : GNat  Nat: f(x) = ½ * x
21=½*2
42=½*4
63=½*6
84=½*8
…
Partielle Funktionen
Definition: partielle Funktion
Eine partielle Funktion aus A nach B ist eine Funktion
f : Df  B, wobei Df  A.
Ax
B
x
f
x
x
x
x
Df
x
x
Beispiele

pred : Nat  Nat,
Dpred = { x Nat | x > 0 }, pred(x) = x - 1

log : Real  Real, Dlog = { x  Real | x > 0 }
Wichtig für Programmiersprachen, da diese nicht so viele Datentypen kennen.
Gleichheit von Funktionen
Definition
Sind f1 : A1  B1 und f2 : A2  B2 Funktionen, dann gilt f1 = f2 gdw:
(i)
D(f1) = D( f2)
(ii) W(f1) = W( f2)
(iii) Für jedes x  D( f1) gilt : f1(x) = f2(x).
Beispiel
min1 : Int  Int  Int
x falls x < y
min1(x,y) =
y sonst
{
min2 : Int  Int  Int
x falls x ≤ y
min2(x,y) =
y sonst
{
Es gilt min1 = min2, da min1(x,y) = min2(x,y) für alle x, y  Int.
Funktionen/Operationen/Abbildungen
Definition: n-stellige Funktion/Operation/Abbildung
Eine Funktion f : A1  A2  ...  An  B heißt auch n-stellige
Operation oder Abbildung.
Funktion,
Die Stelligkeit einer solchen Funktion/Operation/Abbildung ist n. Man sagt
auch, f hat n Argumente.
Eine Abbildung f : An  A
heißt n-stellige innere Funktion/Operation/Abbildung auf A.
Beispiele :
+ : Nat  Nat  Nat
+(x,y) bzw. x+y
Funktions-/Operatorschreibweise
if : Bool  Nat  Nat  Nat
x falls b=T
if(b,x,y) =
y falls b=F
{
min : Int  Int  Int
x falls x < y
min(x,y) =
y sonst
{
 : Real  Real
x = y, wenn y² = x
D( ) = { x | x >= 0 }
Schreibweisen für Funktionsaufrufe
Präfix-Schreibweise:
f(x,y,z)
(übliche Funktionsschreibweise)
Infix-Schreibweise:
xfy
x f 1 y f2 z
(z. B.: x+y)
(z. B.: b ? x : y = if(b,x,y))
Postfix-Schreibweise:
x y z f
(z. B.: die Fakultätsfunktion n!, x‘ = NOT(x) )
Gemischte Schreibweise: x f (y, z)
(z. B.: wolfgang.alter('2009/10/15'))
f1 x f2 y f3 z (z. B.: if b then x else y = if(b,x,y))
Anmerkungen
 Je nach Schreibweise bevorzugt man den Begriff Funktion oder Operation.
 Darüber hinaus gibt es weitere Spezialformen. Zum Beispiel:
x (sprich „x quer“) für NOT(x) oder ¬x.
Funktionen in Programmiersprachen
Funktionen sind ein zentraler Bestandteil so gut wie aller
Programmiersprachen.
Vorteile
– der Code wird kürzer
(Eine Funktion wird einmal definiert und beliebig oft aufgerufen.)
– Abstraktion
(Details der Funktionsdefinition werden „gekapselt“.)
– Mächtigkeit
(Eine Funktion kann rekursiv (induktiv) definiert werden, Funktionen
können an andere Funktionen als Argumente übergeben werden.)
Funktionen in Programmiersprachen
Eine Funktion besteht aus zwei Teilen:
Signatur und Implementierung.
Beispiel
Signatur
sin:   [-1,1]
(Mathe)
Name der Funktion
double sin(double x) (JAVA)
Typen der Parameter (= Definitionbereich)
sin(x: Number): Number (AS3)
meist auch Namen der Parameter
Ergebnistyp der Funktion (= Wertemenge)
Implementierung
Festlegung der Berechnungsvorschrift,
d.h. Angabe eines Algorithmuses zur
Berechnung der Funktionswerte.
Taylorreihe (für Sinusberechnung, es gibt bessere Algorithmen):
x1 x 3 x 5 x 7 x 9
sin(x)  -  -  - ...
1! 3! 5! 7! 9!
Beispiel (AS3)
{
var result: Number = 0.0;
var s:
Number = 1.0;
var i:
int = 1;
while (i < 12)
{ result += s*pow(x,i)/fak(i);
i +=2; s=-s;
};
return result;
}
Große/negative x-Werte sollten ins Intervall [0,p/2]
verschoben werden: sin(x+np) = sin(x), sin(p+x) = sin(p-x), sin(-x) = -sin(x).
Funktionen, Prozeduren, Methoden
Definition Seiteneffekt: Der Zustand des Programms wird geändert.
Beispiele: Variableninhalt, Dateiinhalt, Bildschirmausgabe ändern.
In Programmiersprachen gibt es:
– Funktion: Ergebnis, keine Seiteneffekte (z.B. sin(x))
Signatur: function sin(x: double): double;
(Delphi)
– Prozedur: kein Ergebnis, Seiteneffekte (z.B. print("Hallo"))
Signatur: procedure print(const x: String); (Delphi)
– gemischt: Funktion+Prozedur: Ergebnis und/oder Seiteneffekt
Meist erlaubt (JAVA, C/C++, AS3 …), Trick: Datentyp void.
Signatur: void print(String x)
(JAVA)
print(x: String): void
(AS3)
– Methode: Funktion/Prozedur mit Extraparameter (this, self, me).
Die Definition einer Methode erfolgt innerhalb einer Klassen oder
innerhalb eines bestimmten Objektes.
Funktionen, Prozeduren, Methoden
Definitionen
Deklaration einer …
Definition einen …
=
=
Angabe der Signatur von …
Angabe der Signatur und der
Implementierung von …
Beispiel
„Deklarieren Sie eine Funktion/Methode/…“
heißt „Geben Sie die Signatur der Funktion/Methode/… an.“
„Definieren Sie eine Funktion/Methode/…“
heißt „Geben Sie Signatur und Implementierung der Funktion/Methode/… an“.
Alternativbezeichungen
– (Funktions-/Prozedur-/Methoden-)Kopf = Header = Signatur
– (Funktions-/Prozedur-/Methoden-)Rumpf = Body = Implementierung
Funktionen, Prozeduren, Methoden
Definitionen
Parameter = Name einer Variablen in einer Funktions/…-Signatur.
Argument = Wert der bei einem Funktions/…-Aufruf übergeben wird.
Beispiele
Gegeben sei die Signatur sin(x: Number): Number.
x ist ein (der) Parameter der Funktion.
3*PI ist das Argument des Funktionsaufrufes sin(3*PI).
Das heißt, die Variable x hat während der Berechnung des Ergebnisses den Wert
9.4247778.
sin(2) ist das Argument des Funktionsaufrufes cos(sin(2)).
Die Prozedur void move(int x, int y) hat zwei Parameter: x und y.
Wenn a=4 gilt, so sind 50 und 8 die Argumente des Aufrufes move(50,2*a).
Projektionen
Definition: Projektion
Es seien folgende Funktionen gegeben:
p1 : M1  M2  ...  Mm  M1
. . .
pm : M1  M2  ...  Mm  M m
Wenn pi das i-te Element aus dem Tupel extrahiert
pi (x1 , ... , xm)  xi Mi
heißt pi die i-te Projektion des n-Tupels (x1 , ... , xm).
Beispiel
p2 : Int  Int  Int
(x,y)  y
Anwendung: z.B. Bestimmung der y-Koordinate eines Bildschirmpunktes.
Komposition von Funktionen
Definition: Komposition von Funktionen
Sind f : A  B und g : B  C Funktionen, so ist die Komposition
definiert als Hintereinanderausführung von f und g:
gf
g  f : m  g(f(m)) (m A, g(f(m))C)
Dgf = { x | x  Df und f(x)  Dg }
Die Komposition ist auch eine Funktion.
A
B
x
f
g
C
x

x
x

x
x
x
x
f :AB
g:BC
g  f : A  C
g(f(x))  y C


Erst alle Elemente x
aus A mit f nach B
abbilden, dann die f(x)
aus B mit g nach C
abbilden.
Komposition von Funktionen
Definition: Verallegemeinerte Komposition
Es seien f1 : A1  A2  A3  ...  Am  B1
. . .
fk : A1  A2  A3  ...  Am  Bk
und
g : B1  B2  ... Bk  C
Funktionen. Dann definiert man durch die Zuordnung
(x1 , ... , xm)  g(f1 (x1 , ... , xm), ... , fk (x1, ... , xm))
eine Funktion mit der Funktionalität A1  A2  ...  Am  C
Beispiel
Aus den Operationen
f1 : Nat  Nat+  Nat
(x,y)  x div y
f2 : Int  Int  Int
(x,y)  y
g : Int  Int  Int
(x,y)  x * y
erhält man die zweistellige Operation : (x,y)  (x div y) * y.
Spezialfall: Prädikate (Boole‘sche Funktionen)
Definition: Prädikat
Eine Funktion p : A1  A2 ...  An  Bool heißt Prädikat auf A1  A2 ...  An.
Ist A1 = A2 = ... = An = A , so heißt P ein n - stelliges Prädikat auf A.
Ist p ein Prädikat, und gilt p(x1 , ... , xn ) = T (True),
so schreibt man auch nur p(x1 ... , xn ).
Beispiele
pyth : Nat  Nat  Nat  Bool
pyth(x,y,z) =
{
T falls x2 + y2 = z2
F sonst
Es gilt z.B.: pyth(3, 4, 5); es gilt nicht: pyth (7, 11, 13)
= : Nat  Nat  Bool
even : Nat  Bool
T falls x = y
=(x,y) =
{ F sonst
Es gilt =(3, 3) bzw. 3 = 3
T falls x gerade
even(x) =
{ F sonst
Es gilt even(42) und ¬even(43).
Quantoren und logische Operatoren
Definition:
Es seien M eine Menge und p ein Prädikat, dann bezeichnet:
 x  M : p(x) den All-Quantor
(„Für alle x  M gilt p(x)“)
 x  M : p(x) den Existenz-Quantor („Es gibt ein x  M mit p(x)“)
Definition
Es seien M eine Menge und P und Q Prädikate,
dann definiert man die logischen Operatoren:
logisch UND
 : Bool x Bool  Bool P  Q
logisch ODER  : Bool x Bool  Bool P  Q
logisch NICHT  : Bool x Bool  Bool  P
Q
Q
 F
T
 F
T
P
F
F
F
P F F
T
T
F
T
T
T
T
P
 F
T
T
F
Logische Operatoren
Alternative Darstellung der Wahrheitstafel einer Verknüpfung:
Q
P Q PQ
 F
T
gleiche
F
F F
F
P F F
Bedeutung
T
F
T
Weitere Notationen für logische Operatoren
Gebräuchlich ist auch die Verwendung folgender
alternativer Schreibweisen:
– logisch UND
P•Q oder nur PQ statt PQ
– logisch ODER
P + Q" statt PQ
– logisch NICHT
P' oder P statt P
F
T
F
T
F
F
T
T
T
Logische Operatoren
Definition: Implikation P  Q
Es seien M eine Menge und P und Q Prädikate dann impliziert
Prädikat P das Prädikat Q falls gilt:
Wenn P = T dann Q = T
Notation: P  Q
 F
Q
Q
T
P F T
T
T
T
F
das
P
 F
T
F
T
F
T
F
T
Definition: Äquivalenz P  Q
Die Prädikate P und Q heißen äquivalent, genau dann wenn gilt:
P  Q und Q  P
Vorsicht!
Aus P  Q folgt NICHT die Gültigkeit von Q  P.
Ordnungen
Definition:
Sei p: M  M  Bool ein 2-stelliges Prädikat in (Infix-Notation).
p heißt:
i) reflexiv
genau dann, wenn  x  M : x p x
ii) antisymmetrisch gdw  x,y  M : x p y  y p x  x = y
iii) transitiv
gdw  x, y, z  M : x p y  y P z  x p z
– Eine partielle Ordnung ist eine Relation, die von einem
reflexiven, anti-symmetrischen und transitiven Prädikat induziert wird.
– Eine totale Ordnung ist eine partielle Ordnung, in der zusätzlich gilt:
x,y  M : x p y y p x
Ordnungen
 : Nat  Nat  Bool
induziert eine totale Ordnung auf Nat
< : Nat  Nat  Bool
induziert keine Ordnung auf Nat
(„<„ ist nicht reflexiv)
| : Nat+  Nat+  Bool
induziert eine partielle Ordnung auf
mit x | y = „x teilt y“
Nat+, aber keine totale Ordnung
 : P(M) x P(M)  Bool
induziert eine partielle Ordnung auf
P(M), aber keine totale Ordnung
 : A *  A *  Bool
A lexikographische Ordnung zwischen Wörtern
(z.B. Aachen Berlin Zwickau)
= {a, ..., z, A,…, Z, 0, ..., 9}
Induktive Definitionen von Mengen
 In der Informatik hat man es häufig mit Mengen zu tun, die nach einem
Baukastenprinzip konstruiert sind. Man bezeichnet diese dann als induktiv
definierte Mengen.
 Man beginnt mit einer Menge von Basiselementen und gibt eine Methode
an, mit der aus bereits vorrätigen Elementen neue erzeugt werden können.
 Die Elemente der Menge sind dann genau alle diejenigen Objekte, die man in
endlich vielen Schritten so gewinnen kann.
Beispiel: Lego mit etwas eigenartigen Spielregeln:
– A sei eine Menge von „Bauklotztypen“ (von jedem Klotztyp
gibt es beliebig viele Exemplare).
– Die Erzeugungsmethode entspricht dem Zusammenstecken von
einzelnen Klötzen bzw. von bereits konstruierten Gebilden. Im
letzteren Fall hat man sowohl dieTeilgebilde als auch das neu
entstandene.
– Als Ergebnis erhält man die Menge aller mit den Bauklötzen und
der Erzeugungsmethode konstruierbaren Gebilde.
Induktiv definierte Mengen von Zeichenketten
Definition: A+
A+ ist die Menge aller nichtleeren Zeichenketten über A und wird
induktiv definiert:
1. Basiselemente: Menge A. Jedes Element von A ist in A+.
2. Erzeugungsmethode: Sind w  A+ und a  A , dann ist auch
die konkatenierte Zeichenkette wa in A+.
Statt wa schreibt man oft auch nur wa.
Definition: A*
A* ist die Menge aller Zeichenketten über A.
Zu A+ wird die leere Zeichenreihe  hinzugenommen: A* := A+ {  }.
Beispiel: Ist A die Menge {L,R} , dann ist z.B. die Zeichenkette LRRLR sowohl in
A* als auch in A+.
Induktiv definierte Mengen
Anmerkung
 Viele induktiv definierte Mengen haben unendlich viele Elemente, da man aus
den bereits konstruierten mit der Erzeugungsmethode weitere konstruieren
kann.
Beispiel: Induktive Konstruktion der Menge der natürliche Zahlen (ohne Null)
1. Induktionsanfang
1 ist eine natürliche Zahl.
;;; die Menge der Basiselemente ist: { 1 }
2. Induktionsschritt
Ist k eine natürliche Zahl,
dann auch k+1.
;;; Erzeugungsmethode für k+1 aus k
 Es kann jedoch auch sein, dass nach endlich vielen Schritten keine neuen
Konstruktionen mehr entstehen können. In diesem Fall hat die erzeugte Menge
dann auch nur endlich viele Elemente.
Induktionsprinzip/Induktionsbeweise
Um eine Eigenschaft p (also ein Prädikat) für alle Elemente einer
induktiv definierten Menge M zu beweisen, muss man zeigen:
1.
2.
p gilt für alle Basiselemente.
Wird das Element e aus den Elementen e1 , ... , ek erzeugt, und
gelten p(e1), ... , p(ek ), so gilt auch p(e) .
Beispiel: Induktionsbeweis für eine Eigenschaft P der natürliche Zahlen
Aus dem
Induktionsanfang, d.h., p(1)
und
dem Induktionsschritt p(k)  p(k+1) für alle kNat
folgt, dass p für alle nNat gilt.
Induktionsbeweise: Beispiel
n(n  1)
i

2
i 1
n
Satz: Für n   gilt:
Beispiel
1+2+3+4+…+100 (Aufgabe für C.-F. Gauß in der ersten Klasse)
= (1+100) + (2+99) + … + (50+51)
= 50 * 101 = 5050 = 100*(100+1)/2
Beweis
Induktionsanfang:
1
i  1 
i 1
1(1  1)
2
Induktionsschritt:
k 1
k
k (k  1)
k (k  1) 2(k  1)
(k  1)(k  2)
i


i

(
i
)

(
k

1
)






2
2
2
2
i 1
i 1
i 1
k
Induktionsprinzip/Induktionsbeweise
Beispiel: Sei A die Menge der Legosteine Q = quaderförmig (8 Noppen)
und W = würfelförmig (4 Noppen)
Von den Bauklotztypen Q und W gibt es jeweils beliebig viele Exemplare.
Sei weiter + die Operation „Anfügen“, mit der ein Baustein auf einen anderen oder
eine Teilkonstruktion voll aufgesetzt wird.
Aufgabe: Beweise die Eigenschaft p, die besagt, dass alle aus Legosteinen gebauten
materiellen Gebilde mindestens 4 Ecken haben.
Induktionsbeweis:
Induktionsanfang: Offenbar gilt p(
) und p(
).
Induktionsschritt:
Annahme: Für das aus k Steinen bestehende Gebilde Gk gilt P.
Zeige: Aus p(Gk)  p(Gn+1) für alle möglichen Konstruktionen, die man erhalten
kann, wenn man an Konstruktion Kn einen weiteren Baustein aus A anhängt.
Fertigstellung des Beweises als Übung.
Hinweis: Überlegen Sie, welche Konstruktionen überhaupt möglich sind.
Anwendungen des Induktionsprinzips
Induktionsprinzip für Wörter aus A* und Prädikat p
Aus
1. p() (d.h. das leere Wort erfüllt p) und
2. wA*, aA: p(w)  p(wa)
(d.h. falls w ein Wort ist, das p erfüllt, dann erfüllt auch wa p).
folgt, dass p für alle Elemente von A* gilt.
Induktionsprinzip für Binärbäume
Aus
1. p() und
2. Für beliebige Binärbäume B1 und B2
gilt: p( B1 ) p( B2 )  p(  )
B1
folgt, dass p für alle Binärbäume gilt.

Beispiel:




 

B2



Maßeinheiten

Die Angabe von Speichergröße, Rechengeschwindigkeit, Fläche, usw. erfolgt im Allgemeinen durch
Angabe von Werten in Vielfachen von 10er Potenzen. Folgende Bezeichnungen sind gebräuchlich:
1000n
10n
Präfix
Symbol Name
als Dezimalzahl
10008
1024
yotta
Y
Quadrillion
1 000 000 000 000 000 000 000 000
10007
1021
zetta
Z
Trilliarde
1 000 000 000 000 000 000 000
10006
1018
exa
E
Trillion
1 000 000 000 000 000 000
10005
1015
peta
P
Billiarde
1 000 000 000 000 000
10004
1012
tera
T
Billion
1 000 000 000 000
10003
109
giga
G
Milliarde
1 000 000 000
10002
106
mega
M
Million
1 000 000
10001
103
kilo
k
Tausend
1 000
10002/3
102
hecto
h
Hundert
100
10001/3
101
deca,
da
Zehn
10
10000
100
-
-
Eins
1
1000−1/3
10−1
deci
d
Zehntel
0.1
1000−2/3
10−2
centi
c
Hunderstel
0.01
1000−1
10−3
milli
m Tausendstel
0.001
1000−2
10−6
micro
µ (u) Milllionstel
0.000 001
1000−3
10−9
nano
n
Milliardstel
0.000 000 001
1000−4
10−12
pico
p
Billionstel
0.000 000 000 001
1000−5
10−15
femto
f
Billiardstel
0.000 000 000 000 001
1000−6
10−18
atto
a
Trillionstel
0.000 000 000 000 000 001
1000−7
10−21
zepto
z
Trilliardstel
0.000 000 000 000 000 000 001
1000−8
10−24
yocto
y
Quadrillionstel
0.000 000 000 000 000 000 000 001
Bezugsgröße
Einheiten für Datenmengen
Unterscheidung zwischen :
Kilobyte (kB)
Kibibyte (KiB)
103 Byte = 1000 Byte
210 Byte = 1024 Byte
z.B. A4-Buchseite ~ 4KB
Megabyte (MB) 106 Byte = 1.000.000 Byte
Mebibyte (MiB) 220 Byte = 1.048.576 Byte
z.B. Bibel ~ 5MB
Gigabyte (GB)
Gibibyte (GiB)
109 Byte = 1.000.000.000 Byte
230 Byte = 1.073.741.824 Byte
Terabyte (TB)
Tebibyte (TiB)
1012 Byte = 1000 GB
gut sortierte Bibliothek
240 Byte = 1.099.511.627.776 Byte
Petabyte (PB)
Pebibyte (PiB)
1015 Byte = 1.000.000 GB
250 Byte = 1.125.899.906.842.624 Byte
Exabyte (EB)
Exbibyte (EiB)
1018 Byte Gesamtheit aller gedruckten Werke ~ 0.2EB
260 Byte = 1.152.921.504.606.846.976 Byte
Zettabyte (ZB)
Zebibyte (ZiB)
1021 Byte
270 Byte = 1.180.591.620.717.411.303.424 Byte
Yottabyte (YB)
Yobibyte (YiB)
1024 Byte
280 Byte = 1.208.925.819.614.629.174.706.176 Byte
z.B. Spielfilm 10GB
47

Document