Aus Online Mathematik Brückenkurs 1

Version vom 11:43, 1. Okt. 2009 (bearbeiten) Moni (Diskussion | Beiträge) ← Zum vorherigen Versionsunterschied		Version vom 12:17, 1. Okt. 2009 (bearbeiten) (rückgängig) Moni (Diskussion | Beiträge) Zum nächsten Versionsunterschied →
Zeile 657:		Zeile 657:
	== 6.3 Mathematische Symbole und Formalien ==		== 6.3 Mathematische Symbole und Formalien ==
	== A - Summen - und Produktzeichen ==		== A - Summen - und Produktzeichen ==
		+	Beispiel:
		+	Summe der ersten n natuerlichen Zaheln:
		+	<math>\sum^{n}_{i=1}{i}{1+2+3+...+n}</math>
		+	"Summe von 1 bis n ueber i"
		+
		+	Mehr Beispiele:
		+	Summe der ersten n geraden Zahelen
		+	<math>\sum^{n}_{i=1}{2i}{2+4+6+...+2n}</math>
		+	Summe der ersten n ungeraden Zahlen
		+	<math>\sum^{n}_{i=1}{2i-1}{1+3+5+...+(2n-1)}</math>
		+	Summe von n Einsen
		+	<math>\sum^{n}_{i=1}{1}{1+1+...+1}=n</math> (n-mal 1)
		+	Summe von der 10. bis zur 20. geraden Zahl
		+	<math>\sum^{20}_{i=10}{2i}{20+22+...+40}</math> (11 Summanden)
		+
		+	Rechenregeln bei Summenzeichen:
		+	Ausklammern bei Summen
		+	<math>\sum^{n}_{i=1}{2i}{2\cdot 1+2\cdot 2+2\cdot 3+...+2\cdot n}=2 \sum^{n}_{i=1}{i}</math>
		+	Laufindexverschiebung
		+	<math>\sum^{20}_{i=10}{2i+20}=\sum^{20}_{i=10}{2(i+10)}=\sum^{10}_{i=0}{2i}</math>
		+	Andere Regelen
		+	<math>\sum^{7}_{k=3}{2k+k^2}=2 \sum^{7}_{k=3}{k}+ \sum^{7}_{k=3}{k^2}<math>
		+	<math>\sum^{12}_{k=1}{\dfrac{k^2}{3}}=2 \sum^{12}_{k=1}{\dfrac{k^2}{3}}+ \sum^{12}_{k=1}{\dfrac{k^2}{3}}</math>
		+
		+	Analog Produktzeichen:
		+	z.B.
		+	<math>\prod^{3}_{k=1}{2k+1}{3\cdot 5\cdot 7}=105</math>
		+	<math>n!=\prod^{n}_{i=1}{i}</math>

---

Version vom 12:17, 1. Okt. 2009

Kombinatorik

Inhaltsverzeichnis 1 A - Permutationen 2 A - Stichproben aus n- elementigen Mengen 3 6.1. Logische Grundlagen (Aussagenlogik) 4 A - Aussagen 5 B - Verknuepfung von Aussagen 6 c - Verneinung 7 D - Tautologische Aequivalenzen 8 E - Regel von de Morgan 9 D - Implikationen 10 E - Aequivalenz 11 F - Kontraproition 12 G - Aussageformen 13 6.2. Beweisen und Widerlegen 14 A - Beweisen von Existenaussagen 15 B - Beweisen von Allaussagen 16 c - Widerlegen von Allaussagen/Existenzaussagen 17 D - Widerlegen von Existenzaussagen 18 E - Prinzip der Vollstaendigen Induktion 19 6.3 Mathematische Symbole und Formalien 20 A - Summen - und Produktzeichen

A - Permutationen

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

A - Stichproben aus n- elementigen Mengen

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

6.1. Logische Grundlagen (Aussagenlogik)

A - Aussagen

B - Verknuepfung von Aussagen

c - Verneinung

D - Tautologische Aequivalenzen

Tautologische Aequivalenzen sind Aussagen die immer stimmen. 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.

E - Regel von de Morgan

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

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}

Da die beiden rot markierten Spalten jeweils die gleichen Wahrheitswerte zeigen, sieht man, dass \displaystyle \neg(A\displaystyle \wedgeB) und \displaystyle \negA \displaystyle \vee \negB das gleiche sind. Also gilt

D - Implikationen

Wir definieren A \displaystyle \RightarrowB per Wahrheitswerttabelle. Gesprochen bedeutet A \displaystyle \RightarrowB, dass immer wenn A gilt, dann auch 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

E - Aequivalenz

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

F - Kontraproition

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

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)

G - Aussageformen

Die Aussageform beinhaltet im Gegensatz zur Aussagen eine oder mehrere Variablen.

Man kann ihr so keinen Wahrheitswertzuordnen, allerdings kann man A(x), B(x,y), ... auf zwei Arten zu verifizierbaren Aussagen machen:

1. Werte einsetzen

   Beipiel 6
   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"

      Beipiel 6
      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

      Beipiel 6
      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.

   3. Mischung aus a) und b)
      \displaystyle \forall x \in R \exists y \in R: C(x,y) w
      Sprich: Es gibt fuer alle x in \displaystyle R ein y fuer das C(x,y) gilt.
      (z.B. y=-x+1 dann x+y=x-x+1=1)
      Man muss allerdings sehr auf die Reihenfolge achten. Vertauscht man die Quantoren in dem vorherigen Beipiel, entsteht eine voellig andere Aussage.
      \displaystyle \exists y \in R \forall x \in R: x+y=1 f
      Sprich: Es es gibt ein y in \displaystyle R, mit dem fuer jedes x in \displaystyle R C(x,y) gilt.

6.2. Beweisen und Widerlegen

A - Beweisen von Existenaussagen

Angeben eines Beispiels

z.B. \displaystyle \exists x \in N: x \ge 5 Beweis: Waehle \displaystyle x=5 z.B. \displaystyle \exists x \in R: x^2 =2 Beweis: Waehle \displaystyle x=\sqrt{2}

B - Beweisen von Allaussagen

Schwieriger. Hier reichen keine Beispiele, es muss mit Variablen gerechnet werden. Beispiel \displaystyle \forall a,b \in R :(a,b \ge 0) \Rightarrow \dfrac{a+b}{2} \ge \sqrt{a \cdot b}

Seien $ab,\; b\; \backslash in\; R\; .\; Dann\; gilt\; (*)$\displaystyle (a-b)^2 \ge 0 (wahre Aussage als Start) \displaystyle a^2 - 2ab + b^2 \ge 0 |=4ab \displaystyle a^2 + 2ab + b^2 \ge 4ab \displaystyle (a+b)^2 \ge 4ab |\sqrt{\ \ } \displaystyle a+b \ge 2\sqrt{ab} \displaystyle \dfrac{a+b}{2} \ge \sqrt{ab}

Wie kommt man auf (*)? Probieren Erfahrung

c - Widerlegen von Allaussagen/Existenzaussagen

Zum widerlegen einer Aussage zeigt man, dass ihre Verneinung wahr ist.

z.B. \displaystyle \forall x \in N: (x \ge 5) (*) Verneinung: \displaystyle \neg (\forall x \in N: (x \ge 5)) =\parallel = \exists x \in N: \neg(x\ge 5) =\parallel = \exists x \in N: x<5 Dieses stimmt, zum Beispiel fuer x=3. (*) ist als faslch. Man muss nur ein Gegenbeispiel nennen.

Allgemein: \displaystyle \neg \forall x: A(x) +\parallel = \exists x: \neg A(x) Also Widerlegen von Allaussagen: Zeige Existenz eines Gegenbeispiels.

D - Widerlegen von Existenzaussagen

z.B. \displaystyle \exists x \in N: x^2=2 Verneinung: \displaystyle \exists x \in N: x^2=2 =\parallel = \forall x \in N: \neg (x^2=2 =\parallel = \forall x \in N: x^2 \ne 2 Allgemein: \displaystyle \neg \exists x : A(x) =\parallel = \forall x: \neg A(x) Widerlegen von Existenzaussagen: Zeige, dass fuer alle x (in der jeweiligen Menge) \displaystyle \neg A(x) gilt. Problem von oben: Allaussagen sind schwieriger zu beweisen.)

E - Prinzip der Vollstaendigen Induktion

Beweisprinzip fuer Allaussagen fuer (Teilmengen der) natuerliche(n) Zahlen. z.B. \displaystyle \forall n \in N: n^2\ne 2 \displaystyle \forall n \in N_{\ge 1} : 2^n >n \displaystyle \forall n \in N_{\ge 1} : 1+3+5+...+(2n-1)= n^2 Idee: Zeige in 2 Schritten (IA) Induktionsanfang: Die Aussage gilt fuer das kleinste n (n=0 im ersten Beispiel, n=1 im zweiten Beispiel) (IS) Induktionsschritt: Wenn die Aussage fuer n gilt, zeige dass sie auch fuer n+1 gilt. Induktionsprinzip: Damit ist die Aussage bewiesen! Denn z.B. fuer n=5 (IA) Aussage fuer n=1 \displaystyle \Rightarrow(durch IS) n=2 \displaystyle \Rightarrow(durch IS) n=3 \displaystyle \Rightarrow(durch IS) n=4 \displaystyle \Rightarrow(durch IS) n=5.

Beispiel: Induktion fuer \displaystyle \forall n \in N_{\ge 1} : 2^n >n (IA) Fuer n=1 ist \displaystyle 2^1>n (IV) Wir nehmen fuer ein festes n an: Die Aussage gilt fuer \displaystyle 2^n>n (IS) Zu zeigen ist die Aussage fuer n+1, d.h. zeige \displaystyle 2^{n+1}>n+1. Benutze hier immer das die Induktionsvoraussetzung \displaystyle 2^1>n stimmt. Es ist: \displaystyle 2^{n+1} = 2 \cdot 2^n >^{IV} 2 \cdot n = n+n \ge ^{,da n\ge 1} n+1 Also: \displaystyle 2^{n+1} > n+1

6.3 Mathematische Symbole und Formalien

A - Summen - und Produktzeichen

Beispiel: Summe der ersten n natuerlichen Zaheln: \displaystyle \sum^{n}_{i=1}{i}{1+2+3+...+n} "Summe von 1 bis n ueber i"

Mehr Beispiele: Summe der ersten n geraden Zahelen \displaystyle \sum^{n}_{i=1}{2i}{2+4+6+...+2n} Summe der ersten n ungeraden Zahlen \displaystyle \sum^{n}_{i=1}{2i-1}{1+3+5+...+(2n-1)} Summe von n Einsen \displaystyle \sum^{n}_{i=1}{1}{1+1+...+1}=n (n-mal 1) Summe von der 10. bis zur 20. geraden Zahl \displaystyle \sum^{20}_{i=10}{2i}{20+22+...+40} (11 Summanden)

Rechenregeln bei Summenzeichen: Ausklammern bei Summen \displaystyle \sum^{n}_{i=1}{2i}{2\cdot 1+2\cdot 2+2\cdot 3+...+2\cdot n}=2 \sum^{n}_{i=1}{i} Laufindexverschiebung \displaystyle \sum^{20}_{i=10}{2i+20}=\sum^{20}_{i=10}{2(i+10)}=\sum^{10}_{i=0}{2i} Andere Regelen \displaystyle \sum^{7}_{k=3}{2k+k^2}=2 \sum^{7}_{k=3}{k}+ \sum^{7}_{k=3}{k^2}$$ \backslash sum^\{12\}\_\{k=1\}\{\backslash dfrac\{k^2\}\{3\}\}=2\; \backslash sum^\{12\}\_\{k=1\}\{\backslash dfrac\{k^2\}\{3\}\}+\; \backslash sum^\{12\}\_\{k=1\}\{\backslash dfrac\{k^2\}\{3\}\}$$

Analog Produktzeichen: z.B. \displaystyle \prod^{3}_{k=1}{2k+1}{3\cdot 5\cdot 7}=105 \displaystyle n!=\prod^{n}_{i=1}{i}