Processing Math: 24%

Aus Online Mathematik Brückenkurs 1

Kombinatorik

Inhaltsverzeichnis [Verbergen] 1 A - Permutationen 2 A - Aussagen 3 B - Verknuepfung von Aussagen 4 c - Verneinung 5 D - Tautologische Aequivalenzen 6 E - Regel von de Morgan 7 D - Implikationen 8 E - Aussageformen

A - Permutationen

Permutationen sind die Anzahl der Möglichkeiten, die Anordnung von Gegenständen zu Vertauschen, also die Anzahl der Weisen Objekte anzuordnen.

Stichproben aus n- elementigen Mengen:

Zusammenfassung Urnenmodell: Das Urnenmodell ist ein allgemeines Beispiel für die Kombinatorik. Hier ist die Idee ein Behältnis mit n Kugeln zu haben aus dem man k mal zieht. Die Beispiele von oben lassen sich durch das Modell und die dazugehörigen Formeln alle rechnen.

	Mit Zurücklegen	Ohne Zurücklegen
Reihenfolge wichtig	nk (Beispiel 3)	n!(n−k)! (Beispiel 4)
Reihenfolge unwichtig	kn+k−1  (wird selten gebraucht, hier ist es aber der Vollständigkeit halber aufgeführt)	kn=n!(n−k)!k!  (Beispiel 6)

6. Mathematische Formalismen 6.1. Logische Grundlagen 6.2. Beweise 6.3. Mathematische Zeichen, Formeln und Texte

6.1. Logische Grundlagen (Aussagenlogik)

A - Aussagen

Aussagen (im mathematischen Sinne) haben einen Wahrheitswert, n&aume;mlich wahr(w, 1) oder falsch(f, 0). Das heisst bei einer Aussage muss sicher fest stehen ob sie wahr oder falsch ist. S&aume;tze wie "Mathe ist doof" oder "Es regnet" sind daher im mathematischen Sinne keine Aussagen, da sie nicht eindeutig wahr oder falsch sind.

Aussagen koennen mit A, B, C, ... bezeichnet werden. z.B. A: "3 < 7"

B - Verknuepfung von Aussagen

logisches "und" ( \displaystyle \wedge )

A : "\displaystyle 5 \le 7 " w B : "\displaystyle 7 \ge 3 " w

\displaystyle A \wedge B : "5 \le 7" und "\displaystyle 7 \ge 3 " w

A	B	A \displaystyle \wedge B
w	w	w
w	f	f
f	w	f
f	f	f

logisches "oder" (\displaystyle \vee ) (lat. vel = oder)

A	B	A \displaystyle \vee B
w	w	w
w	f	w
f	w	w
f	f	f

c - Verneinung

\displaystyle \neg "nicht" z.B. A: "\displaystyle 3 < 7 " \displaystyle \neg A: "\displaystyle 3 \ge 7 "

A	\displaystyle \neg A
w	f
f	w

D - Tautologische Aequivalenzen

Betrachte \displaystyle \neg A und \displaystyle \neg \neg \neg A

A	\displaystyle \neg A	\displaystyle \neg \neg A	\displaystyle \neg \neg \neg A
w	f	w	f
f	w	f	w

\displaystyle \neg A und \displaystyle \neg \neg \neg A liefern fuer jeden Wahrheitswert von A denselben Wert. Dafuer schreibt man \displaystyle \neg A \displaystyle =\parallel = \neg \neg \neg A.

E - Regel von de Morgan

\displaystyle \neg (A \wedge B) =\parallel = \neg A \vee \neg B (= (\neg A) \vee (\neg B)) Beweis:

A	B	A \displaystyle \wedge B	\displaystyle \neg(A\displaystyle \wedgeB)	\displaystyle \negA	\displaystyle \negB	\displaystyle \negA \displaystyle \vee \negB
w	w	w	\displaystyle \color{red}{f}	f	f	\displaystyle \color{red}{f}
w	f	f	\displaystyle \color{red}{w}	f	w	\displaystyle \color{red}{w}
f	w	f	\displaystyle \color{red}{w}	w	f	\displaystyle \color{red}{w}
f	f	f	\displaystyle \color{red}{w}	w	w	\displaystyle \color{red}{w}

\displaystyle \neg (A \wedge B) =\parallel = \neg A \vee \neg B (= (\neg A) \vee (\neg B)) A: "Ich bin schlecht in Mathe." B: "Ich bin schlecht in Deutsch."

\displaystyle \neg (A \vee B) =\parallel = \neg A \wedge \neg B A: "Ich bin besoffen." B: "Ich bin muede." \displaystyle \color{red}{test}

D - Implikationen

Wir definieren A \displaystyle \RightarrowB (immer wenn A gilt, dann auch B) per Wahrheitswerttabelle.

\displaystyle A \Rightarrow B := \neg(A \wedge \neg B) (=\neg A \vee \neg \neg B = \neg A \vee B

A	B	\displaystyle \neg B	A \displaystyle \wedge \neg B	\displaystyle \neg (A \displaystyle \wedge \neg B)
w	w	f	f	w
w	f	w	w	f
f	w	f	f	w
f	f	w	f	w

Aequivalenz

A \displaystyle \Leftrightarrow B:= (A \displaystyle \Rightarrow B) \displaystyle \wedge (B\displaystyle \RightarrowA)

Kontraproition

A \displaystyle \Rightarrow B \displaystyle =\parallel = \displaystyle \negB \displaystyle \Rightarrow\displaystyle \negA

Beipiel: "Wenn x \displaystyle \in N durch 4 teilbar isr, dann auch durch 2." "Wenn x \displaystyle \in N nicht durch 2 teilbar isr, dann auch nicht durch 4."

A	B	A\displaystyle \RightarrowB	\displaystyle \neg A	\displaystyle \neg B	\displaystyle \neg B \displaystyle \Rightarrow \negA
w	w	\displaystyle \color{red}{w}	f	f	\displaystyle \color{red}{w}
w	f	\displaystyle \color{red}{f}	w	f	\displaystyle \color{red}{f}
f	w	\displaystyle \color{red}{w}	f	w	\displaystyle \color{red}{w}
f	w	\displaystyle \color{red}{w}	f	w	\displaystyle \color{red}{w}
f	f	\displaystyle \color{red}{w}	w	w	\displaystyle \color{red}{w}

(Vorsicht: A \displaystyle \Rightarrow \ne \neg A \displaystyle \Rightarrow \neg B)

E - Aussageformen

beinhaltet im Gegensatz zu Aussagen belegbare Variablen.

Abbkuerzung A(x) : "x gerade" B(x,y): "x ist kleiner als y" C(x,y): "x+y=1" D(x): "x<9"

Man kann keinen Wahrheitswertzuordnen.

Man kann A(x), B(x,y), ... auf zwei Arten zu verifizierbaren Aussagen machen:

1. Werte einsetzen: z.B. A(5): "5 ist gerade" f A(10): "10 ist gerade" w C(10,9): "10+9=1" f
2. Auswerten ueber einer Menge
   1. "fuer alle" z.B. Fuer alle x \displaystyle \in N gilt A(x). ("alle x \displaystyle \in N sind gerade")

      Kurz: \displaystyle \forall x \in N : A(x) f

      Beispiel 2: Fuer alle x \displaystyle \in R_{<0} und alle y \displaystyle \in R_{\ge 0} gilt B(x,y).

      Kurz: \displaystyle \forall x \in R_{<0} \forall y \in R_{\ge 0}: B(x,y) w

      Der Wahrheitswert haengt (ueber den Quantor (\displaystyle \forall) ) von der Menge ab.

   2. "es existiert" z.B es existiert ein x \displaystyle \in N das gerade ist (d.h. A(x) gilt.).

      Kurz \displaystyle \exists x \in N : A(x) w z.B. x=2 oder z.B. \displaystyle \exists x \in N \exists y \in N: c(x,y) w z.B. x=0, y=1

      Der Wahrheitswert haengt wieder (ueber den Quantor (\displaystyle \exists) ) von der Menge ab.

   Mischung aus a) und b) \displaystyle \forall x \in R \exists y \in R: C(x,y) w (z.B. y=-x+1 dann x+y=x-x+1=1) nicht vertauschen

   \displaystyle \exists y \in R \forall x \in R: x+y=1 f