Diskrete Mathematik
Semester 1: Begriffe
Semester 1: Begriffe
-
- 1 / 56
-
Flashcards
Mengenlehre: A n B
Durchschnitt. {x | x eA und x eB}
Mengenlehre: A u B
Vereinigung. {x | x eA oder x eB} kann auch beides sein.
Mengenlehre: A c B
Teilmenge. jedes Element aus A ist auch in B enthalten.
A c B und B c A dann A=B
Mengenlehre: A \ B
Differenz. {x | x eA und nich x eB}
Menge A ohne Elemente der Menge B.
Mengenlehre: A x B
karthesisches Produkt. {(x,y) | x eA, y eB}
Alle Zahlenpaare aus x mit y (jedes x mit jedem y)
Zahlenbereiche: N
natürliche Zahlen {1, 2, 3, ...}
Zahlenbereiche: Nv0
Natürliche Zahlen mit 0 {0, 1, ...}
Zahlenbereiche: Z
ganze Zahlen {-3, -2, -1, 0, 1, 2, ...}
Zahlenbereiche: Q
rationale Zahlen {p/q | p eZ, q eN}
Relation
Teilmenge von Paaren da: R c MxN
(a, b) eR -> aRb ("R gilt zwischen a und b)
Relation: reflexiv
wenn aRa gilt.
Relation: symmetrisch
aRb -> bRa für alle a,b eM
Relation: antisymmetrisch
aRb -> bRa nur für a=b (a, b eM).
Relation: transitiv
aRb und bRc -> aRc (a, b, c eM)
Relation: Äquivalenzrelation
reflexiv, symmetrisch und transitiv
Relation: Ordnungsrelation
R ist reflexiv, antisymmetrisch und transitiv
Eigenschaften von Rechenoperationen:
Kommutativität
x+y = y+x
x*y = y*x
Eigenschaften von Rechenoperationen:
Assoziativität
(x+y)+z = x+(y+z)
(x*y)*z = x*(y*z)
Eigenschaften von Rechenoperationen:
Distributivität
(x+y)*z = x*z + y*z
Eigenschaften von Rechenoperationen:
neutrales Element Multiplikation/Addition
x*1 = x / x+0=x
Eigenschaften von Rechenoperationen:
inverses Element bezüglich Addition / Multiplikation
x+(-x) = 0
x* 1/x =1 (1/x = x^-1)
Funktion: Injektiv
x1, x2 eA -> f(x1) ungleich f(x2)
unterschiedliche Funktionswerte x ergeben nicht den gleichen y Wert
Funktion: surjektiv
f(A) = B
d.h. es werden alle Werte aus dem Wertebereich angenommen
Funktion: bijektiv
sowohl injektiv als auch surjektiv
Halbgruppe (G, o)
(x o y) o z = x o (y o z)
Assoziativität
Gruppe (G, o)
- (xoy)oz = xo(yoz) Assoziativität
- e =neutrales Element für jedes x
- x^-1 = Inverses zu jedem x
abelsche Gruppe
Wie Gruppe (Assoziativ, neutrales e, inverses)
zusätzlich Kommutativität x o y = y o x
Symmetrische Gruppe
Abbilden einer Menge auf sich selbst f(g(x))
hintereinanderausführen von rechts nach links
Untergruppe H c G
- x, y eH -> x o y eH
- x eH -> x^-1 eH
Ring (R, +, *):
- Assoziativität (x o y) o z = x o (y o z)
- Distributivität (x+y)*z = x*z + y/z
- Kommutativität bezgl +: x+y = y+x
- neutrales element und inverses bezgl +
kommutativer Ring
wie Ring zusätzlich Kommutativität bzgl. *
x*y = y*x
Ring mit Einselement
Wie Ring zusätzlich neutrales Element bzgl. *
Körper
kommutativer Ring mit Einselement zusätzlich:
Inverses bzgl. * (ergibt Einselement)
Graphentheorie: Adjazent
2 Knoten mit einer Kante verbunden (benachbart)
Graphentheorie: Inzident
2 Kanten mit einem Endknoten
oder eine Kante mit einem Knoten als Endpunkt
Graphentheorie: Grad
deg(v1)= Anzahl seiner Kanten
Graphentheorie: Kantenzug
Folge in einem Graphen die jede Kante einmal besucht (Knoten mehrfach).
Graphentheorie: geschlossener Kantenzug
Folge in einem Graph: Jede Kante wird einmal besucht und Startknote = Endknoten
Graphentheorie: geschlossener Kantenzug
Folge in einem Graph: Jede Kante wird einmal besucht und Startknote = Endknoten
Graphentheorie: Weg
Kantenzug mit verschiedenen Knoten
