Diskrete Mathematik

Term	Definition
Aussage	Feststellender Satz, dem eindeutig “wahr” oder “falsch” zugeordnet werden kann. Symbole wie werden dafür verwendet
Aussagenlogische Form	Kombination von Aussagen, verknüpft durch Junktoren
Aussageform	Aussagen verknüpft mit Variablen
Normalform	Standartisierte Aussagenlogische Formen (Formeln)
Negationsnormalform	steht ausschliesslich direkt vor Aussagen oder Konstanten
Verallgemeinerte Disjunktion	Einzelne Aussage oder Negation wahr oder falsch Disjunktion , falls und selbst verallgemeinerte Disjunktionen sind
Verallgemeinerte Konjunktion	Einzelne Aussage oder Negation wahr oder falsch Konjunktion , falls und selbst verallgemeinerte Konjunktionen sind
Disjunktive Normalform	Disjunktion von (oder eine einzelne) verallgemeinerten Konjunktionen Beispiel:
Konjunktive Normalform	Konjunktion von (oder eine einzelne) verallgemeinerten Disjunktionen Beispiel:
Kontradiktion	Immer falsch
Tautologie	Immer wahr
Junktoren (/Konnektoren)	Negation Konjunktion Disjunktion (einschliessliches oder!) Implikation Äquivalenz
Bindungsstärke	vor vor

Term	Definition
Abtrennungsregel
Kommutativität
Assoziativität
Distributivität
Absorption
Idempotenz
Doppelte Negation
Konstanten
de Morgan

Term	Definition
Subjekt	“Konkretes Ding” / Stellvertreter einer Variable
Prädikat	“Eigenschaft”, zB “ist eine Primzahl” Prädikate werden oft wie Funktionen geschrieben. Ist ein Prädikat, dann bedeutet , dass das Prädikat erfüllt. ist eine Aussageform.
Quantor	Allquantor (Für alle) Existenzquantor (Es existiert)

1. Direkter Beweis
2. Dfferenz gleich Null
3. Äquivalenzumformung
4. Dritte Grösse (vereinfachen)

Term	Definition
Folge	Nummerierte Liste von Objekten (Folgegliedern)
Reihe	Summe von Folgegliedern einer Zahlenfolge

Term	Definition
Aufzählend
Beschreibend
Mächtigkeit	Anzahl Elemente einer Menge
Potenzmenge	Menge aller Teilmengen einer Menge
Teilermenge	Menge der Teiler der Zahl
Kartesisches Produkt

Für die Mengen A und B in der Obermenge M gelten die folgenden Aussagen:			Weiteres:

Term	Definition
Funktion/Abbildung	Zuordnung, die jedem Elemend der Definitionsmenge genau ein Element einer Zielmenge zuordnet. Injektive Relation Abbildungen mit mehreren Argumenten: ,
Graph	Menge von Paaren
Relation	Teilmenge des Kartesischen Produktes mehrerer Mengen Kleiner-Relation: Gleich-Relation: Kleiner-Gleich-Relation:
Surjektiv	Alle Elemente der Definitions- und Zielmenge sind “verknüpft” / jedes Element der Bildmenge kommt als Bild vor
Injektiv	Alle Inputs haben eindeutige Outputs
Bijektiv	Surjektiv und Injektiv
Reflexiv	Alle Elemente von A stehen zu sich selbst in Beziehung
Symmetrisch
Transitiv
Äquivalenzrelation	reflexiv, symmetrisch und transitiv
Irreflexiv
Asymmetrisch
Antisymmetrisch
Ordnungsrelation	reflexiv, antisymmetrisch und transitiv
Symmetrische Differenz

Die Modulo-Relation ist eine Äquivalenzrelation auf .

Term	Definition
Teiler-Relation	Für ist die Teiler-Relation Ordnungsrelation auf
Modulo-Relation	Für ist die Modulo-Relation
	“relates to”
Quotient, Rest	Zu jeder Zahl und jeder Zahl gibt es eindeutig bestimmte Zahlen mit Bsp: heisst Quotient heisst Rest
Restklassen
Multiplikatives Inverses	Für ist das multiplikative inverse von a, wenn
Nullteiler	Wenn für und , heissen Nullteiler

Term	Definition
Teilerfremd	Zwei Zahlen heissen Teilerfremd, wenn Sei eine Primzahl und dann ist

Seien
Initialisierung: Setze und (d.h. bestimme q und r so, dass ist)
Wiederhole bis ist
Ergebnis:

Seien
Initialisierung: Setze (d.h. bestimme q und r so, dass ist)
Wiederhole bis ist
Ergebnis:
Wenn ist, dann folgt:

Sei eine Primzahl und mit Dann ist: Daraus folgend:

Sei und mit . Dann ist .

Sei und .
Dann heisst :

1. Sei eine Primzahl, dann
2. Sei eine Primzahl und , dann
3. Seien und , dann

1. Wähle 2 Primzahlen
2. Berechne
3. Berechne
4. Wähle so, dass
5. Vergesse . Brauchen wir nicht und riskieren nur, dass uns jemand hackt

Public key ist nun , Private key ist
Verschlüsseln:
Entschlüsseln:
Sidenote: Fürs Alphabet muss grösser sein als

3b1b <3

Term	Definition
Homogenes LGS
Inhomogenes LGS
Lineare Abbildung	ist injektiv
Kern	Lösungsmenge des Homogenen LGS =

	1	1	1	−6
	1	2	3	−10
	2	3	6	−18
	1	1	1	−6
	0	1	2	−4
	0	1	4	−6
	1	1	1	−6
	0	1	2	−4
	0	0	2	−2
	1	1	1	−6
	0	1	2	−4
	0	0	1	−1

Koeffizientenmatrix

	1	1	0	−5
	0	1	0	−2
	0	0	1	−1
	1	0	0	−3
	0	1	0	−2
	0	0	1	−1

Ergebnisvektor Lösungsvektor Lineares Gleichungssystem

= Anzahl Pivot-Variablen.
Wenn dann ist das LGS lösbar (homogenes Gleichungssystem), sonst unlösbar.
Wenn dann hat LGS genau eine Lösung.
Wenn dann hat LGS unendlich viele Lösungen.

Term	Definition
Vektor	Liste von Zahlen
Nullvektor
Ortsvektor	Ortsvektor vom Nullpunkt des Koordinatensystems zum Punkt
Richtungsvektor	Richtungsektor vom Punkt zum Punkt ist
Linearkombination	Linearkombination der Variabeln (Bsp. ). Vektoren werden jeweils mit einer Zahl mutlipliziert und miteinander summiert
Lineare Unabhängigkeit	heissen linear unabhängig, wenn die Gleichung genau eine Lösung hat, nämlich eindeutig lösbar sind linear unabhängig
Skalarprodukt
Betrag/Länge eines Vektors

Addition:

Multiplikation mit reellen Zahlen (=Skalare):

Falls die Vektoren senkrecht zueinanderstehen, ist das Skalarprodukt gleich 0

Anti-kommutativ: . Konsequenz:

Distributiv:

Gemischt-assoziativ:

Das Kreuzprodukt ist nicht assoziativ. darf man nicht!

steht immer senkrecht auf und auf . bilden ein Rechtssystem Flächeninhalt des durch und aufgespannten Parallelogramms

Ein Vektorraum ist eine Menge mit den Rechenoperationen:

Mit den Eigenschaften:

• Vektoraddition:

  • Assoziativgesetz:
  • Existenz eines neutralen Elements mit
  • Existenz eines zu inversen Elements mit
  • Kommutativgesetz:

• Skalarmultiplikation:

  • für das Einselement des Skalarkörpers

Gelten diese Eigenschaften für die Teilmenge eines grösseren Vektorraums , so nennt man Untervektorraum von . Heisst: Man hat nur dann einen Untervektorraum , wenn die Produkte der Multiplikation oder Addition der Elemente dieses Raumes auch in liegen. Untervektorräume sind also unendliche Räume mit n Dimensionen weniger, zB = 3-Dimensionaler Vektorraum, = 2-Dimensionaler Untervektorraum.

Kern von ist ein Untervektorraum von .

Eine Lineare Abbildung ist eine Funktion mit den Eigenschaften Für jede lineare Abbildung gibt es eine (Abbildungs) Matrix mit der Eigenschaft, dass

Term	Definition
Spaltenvektoren	Spalten der Matrix als Vektoren
Zeilenvektoren	Zeilen der Matrix als Vektoren
Rang	Wieviele Spaltenvektoren einer Matrix linear unabhängig sind
Nullmatrix
Quadratische Matrix	Gleichviele Zeichen und Spalten
Diagonalmatrix	(immer quadratisch und symmetrisch):
Einheitsmatrix	(immer diagonal):
Symmetrische Matrix	(immer quadratisch):
Obere Dreiecksmatrix
Kovarianzmatrix	immer symmetrisch
Reguläre Matrix	Quadratische Matrix mit höchstem Rang (Rang = Anzahl Spalten/Reihen)
Singuläre Matrix	Quadratische Matrix mit kleinerem Rang (Rang < Anzahl Spalten/Reihen)
Invertierbare Matrix	Für heisst invertierbar, wenn es eine Matrix gibt, so dass . Dies ist der Fall, wenn Regulär ist.

Matrix mit 2 Zeilen und 3 Spalten

Komponenten von :
: Zeilenindex, : Spaltenindex. Bsp:

ist ein 6-Dimensionaler VR (Vektorraum)

Zu gehörige Zeilenvektore

Zu gehörige Spaltenvektore

Transponierte Matrix wäre: Rolle von Zeile und Spalte vertauscht:

Meistens nicht kommutativ ()
muss genau gleich viele Zeilen haben wie Spalten

Determinante einer quadratischen Matrix ist eine reelle Zahl

Definition der Determinante:

Definition über Eigenschaften:

wenn M 2 nicht linear unabhängige Zeilen hat. Heisst: Transformierte Vektoren auch linear abhängig.

Weitere Eigenschaften:

• Die Determinante wechselt beim Vertauschen von Zeilen ihr Vorzeichen
• Wenn wir zu einer Zeile einer Matrix ein Vielfaches einer anderen Zeile dazuzählen, ändert die Determinante ihren Wert nicht

Weiteres:

Volumen eines Spats =

Volumen = Grundfläche Höhe

Determinante im 2D-Raum sagt aus, wie stark eine Fläche auf dem Koordinatensystem skaliert wird sobald durch die Matrix transformiert. Beispiel: bedeutet, dass die Fläche vervierfacht wird.

Gegeben:

heisst Eigenvektor zum Eigenwert

Gegeben: Matrix

Ein Vektor heisst Eigenvektor zum Eigenvenwert , wenn ist.

Wenn gegeben ist, ist das ein homogenes lineares Gleichungssystem in . Davon suchen wir nicht-triviale Lösungen ().

heisst Eigenwert von ist singulär

Wenn , dann ist ein Polynom von Grad . (Charakteristisches Polynom). Eigenwerte sind Nullstellen des charakteristischen Polynoms.

Nullstelle des char. Polynoms

Eigenwerte von sind und

Für diese Zahlen ist die Matrix singulär, d.h. die Gleichung hat nicht-triviale Lösungen. Diese heissen Eigenvektoren.

Matrizen haben Rang von 1
1 −1 1 0 −2 2 0 Für alle ist ein Eigenvektor zum Eigenwert	1 −2 1 0 −2 1 0 ist ein Eigenvektor zum Eigenwert .

heisst diagonalisierbar, wenn es eine invertierbare Matrix gibt, so dass ( ist eine Diagonalmatrix )

Wenn diagonalisierbar ist, dann sind die Spalten von linear unabhängige Eigenvektoren, also eine Basis von , die nur aus Eigenvektoren von besteht.

Das umgekehrte gilt auch. Das erlaubt uns, zu konstruieren.

beste playlist

Parameterform (Punktrichtungsform) Aus Koordinatenform umwandeln: Richtungsvektor steht senkrecht zum Normalenvektor Koordinatenform Aus Parameterform umwandeln:

Aus Koordinatenform umwandeln ( bleibt gleich):

= Abstand der Geraden vom Ursprung.

Abstand von Punkt zur Geraden

Aus Parameterform umwandeln ( bleibt gleich):

Aus Normalenform umwandeln (ausmultiplizieren):

Aus Koordinatenform umwandeln:

Aus Normalenform umwandeln:

Abstand von Punkt zur Ebene

Abstand von Punkt zur Ebene

Gegeben:

Diagonale

Fläche

Gegeben:

Note:

Multiplikationstabelle?

Können nicht Teilerfremd zu sein.

Multiplikationstabelle?

… 1 0 2 3 0 1 1 0 0 0 0 4	Unlösbar
… 1 0 2 3 0 1 1 0 0 0 0 0

Wahrheitstafel. Für konjunktive Normalform zuerst disjunktive erstellen, danach negieren und umformen. Beispiel:

Kleiner Fermat:

Satz von Euler:

Falls gibt kein mult. Inv. Ansonsten: Euklidscher Algorithmus.

Beispiel:

x	y	q	r	u	s	v	t
32	21	1	11	1	0	0	1
21	11	1	10			1	−1
11	10	1	1			−1	2
10	1	10	0			2	−3

Beispiel:

gibt kein mult. Inv.

Gegeben:

Welche Gerade liegt näher an Punkt :

Hessesche Normalenform
Abstand
Hessesche Normalenform
Abstand

Wo schneiden sich die Geraden: Koordinatengleichung

Für welche Gerade liegt auf derselben Seite wie der Ursprung: Ursprung in HNF einsetzen

Abstand
Abstand

Schnittpunkt mit x-Achse berechnen:

X-Achse einsetzen:

Schnittpunkt zweier Geraden berechnen:

Einen der Parameter berechnen:

Einsetzen:

Gegeben: Punkte

Ebene verläuft durch oben genannte Punkte. Gib sie in Parameterform unter Verwendung des Ortsvektors zum Punkt als Stützvektor an:

Hessesche Normalenform der Ebene :

Abstand des Punktes von der Ebene :

Für welchen Wert von liegt auf der Ebene :

Befindet sich Punkt auf derselben Seite wie der Ursprung: Ja, falls Abstand von und Abstand von gleiches Vorzeichen haben

Steht der Vektor senkrecht auf der Ebene: Ja, falls vielfaches vom Normalenvektor

Gegeben:

Abstand:

Gegeben:

Punkt wählen:

Normalenvektor der Ebene finden:

einsetzen:

Abstand:

Gegeben:

Vereinfachte Normalenform:

Vereinfachte Normalenform mit eingesetzt:

Hessesche Normalenform:

Gegeben:

Zahlen angeben, die als Schlüssel infrage kommen: Teilerfremd zu

Zum Schlüssel den Schlüssel berechnen: Euklidscher Algorithmus mit

Mit dem Schlüssel die Zahl ent- / verschlüsseln:

Falls teilerfremd zu : Multiplikationstabelle mit Fremdteilern zu erstellen. Beispiel:

1 5 7 11 1 1 5 7 11 5 5 1 11 7 7 7 11 1 5 11 11 7 5 1