ZusatzStoffTUB

Aus Online Mathematik Brückenkurs 1

(Unterschied zwischen Versionen)
Wechseln zu: Navigation, Suche
Zeile 590: Zeile 590:
== 6.2. Beweisen und Widerlegen ==
== 6.2. Beweisen und Widerlegen ==
== A - Beweisen von Existenaussagen ==
== A - Beweisen von Existenaussagen ==
-
Angeben eines Beispiels
+
Beim Beweisen von Existenzaussagen reicht es ein Beispiel anzugeben.
-
 
+
<div class="exempel">
-
z.B. <math>\exists x \in N: x \ge 5</math>
+
'''Beispiel 1'''
 +
<ol type="a">
 +
<li>
 +
<math>\exists x \in N: x \ge 5</math>
Beweis:
Beweis:
Waehle <math>x=5 </math>
Waehle <math>x=5 </math>
-
z.B. <math>\exists x \in R: x^2 =2</math>
+
</li>
 +
<li><math>\exists x \in R: x^2 =2</math>
Beweis:
Beweis:
Waehle <math>x=\sqrt{2} </math>
Waehle <math>x=\sqrt{2} </math>
 +
</li>
 +
</ol>
 +
</div>
== B - Beweisen von Allaussagen ==
== B - Beweisen von Allaussagen ==
-
Schwieriger. Hier reichen keine Beispiele, es muss mit Variablen gerechnet werden.
+
Allaussagen sind schwerer zu beweisen. Hier reichen keine Beispiele, es muss mit Variablen gerechnet werden.
-
Beispiel
+
-
<math>\forall a,b \in R :(a,b \ge 0) \Rightarrow \dfrac{a+b}{2} \ge \sqrt{a \cdot b}
+
-
Seien <math> ab, b \in R </math>. Dann gilt
+
<div class="exempel">
-
(*)<math> (a-b)^2 \ge 0 </math> (wahre Aussage als Start)
+
'''Beispiel 2'''
-
<math>a^2 - 2ab + b^2 \ge 0 |=4ab</math>
+
<br><math>\forall a,b \in R :(a,b \ge 0) \Rightarrow \dfrac{a+b}{2} \ge \sqrt{a \cdot b}</math>
-
<math>a^2 + 2ab + b^2 \ge 4ab</math>
+
-
<math>(a+b)^2 \ge 4ab |\sqrt{\ \ }</math>
+
-
<math>a+b \ge 2\sqrt{ab}</math>
+
-
<math>\dfrac{a+b}{2} \ge \sqrt{ab}</math>
+
-
Wie kommt man auf (*)? Probieren Erfahrung
+
Seien <math> a, b \in R </math>. Dann gilt
 +
<br>(*)<math> (a-b)^2 \ge 0 </math> (wahre Aussage als Start)
 +
<br><math>a^2 - 2ab + b^2 \ge 0 |=4ab</math>
 +
<br><math>a^2 + 2ab + b^2 \ge 4ab</math>
 +
<br><math>(a+b)^2 \ge 4ab |\sqrt{\ \ }</math>
 +
<br><math>a+b \ge 2\sqrt{ab}</math>
 +
<br><math>\dfrac{a+b}{2} \ge \sqrt{ab}</math>
-
== c - Widerlegen von Allaussagen/Existenzaussagen ==
+
Auf (*) zu kommen ist nicht immer ganz leicht. Man kann durch probieren darauf kommen oder weiss es aus Erfahrung.
-
Zum widerlegen einer Aussage zeigt man, dass ihre Verneinung wahr ist.
+
</div>
-
z.B. <math>\forall x \in N: (x \ge 5)</math> (*)
+
== c - Widerlegen von Allaussagen ==
-
Verneinung: <math>\neg (\forall x \in N: (x \ge 5)) =\parallel = \exists x \in N: \neg(x\ge 5) =\parallel = \exists x \in N: x<5 </math>
+
Zum Widerlegen einer Aussage zeigt man, dass ihre Verneinung wahr ist.
-
Dieses stimmt, zum Beispiel fuer x=3. (*) ist als faslch. Man muss nur ein Gegenbeispiel nennen.
+
-
Allgemein:
+
<div class="regel">
-
<math>\neg \forall x: A(x) +\parallel = \exists x: \neg A(x)</math>
+
'''Allgemein'''
-
Also Widerlegen von Allaussagen: Zeige Existenz eines Gegenbeispiels.
+
<br><math>\neg \forall x: A(x) =\parallel = \exists x: \neg A(x)</math>
 +
<br>Also reicht zum Widerlegen von Allaussagen, die Existenz eines Gegenbeispiels zu zeigen.
 +
</div>
 +
 
 +
<div class="exempel">
 +
'''Beispiel 3'''
 +
<br><math>\forall x \in N: (x \ge 5)</math> (*)
 +
<br>Verneinung:
 +
<br><math>\neg (\forall x \in N: (x \ge 5)) \ \ \ =\parallel = \ \ \ \exists x \in N: \neg(x\ge 5) \ \ \ =\parallel = \ \ \exists x \in N: x<5 </math>
 +
<br>Dieses stimmt, zum Beispiel fuer x=3. (*) ist als faslch. Man muss nur ein Gegenbeispiel nennen.
 +
</div>
== D - Widerlegen von Existenzaussagen ==
== D - Widerlegen von Existenzaussagen ==
-
z.B. <math>\exists x \in N: x^2=2</math>
+
<div class="exempel">
-
Verneinung: <math>\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</math>
+
'''Beispiel 4'''
-
Allgemein:
+
<br><math>\exists x \in N: x^2=2</math>
-
<math>\neg \exists x : A(x) =\parallel = \forall x: \neg A(x)</math>
+
<br>Verneinung:
-
Widerlegen von Existenzaussagen: Zeige, dass fuer alle x (in der jeweiligen Menge) <math>\neg A(x)</math> gilt.
+
<br><math>\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</math>
-
Problem von oben: Allaussagen sind schwieriger zu beweisen.)
+
</div>
 +
 
 +
<div class="regel">
 +
'''Allgemein'''
 +
<br><math>\neg \exists x : A(x) \ \ =\parallel = \ \ \forall x: \neg A(x)</math>
 +
<br>Existenzaussagen koennen widerlegt werden, indem man zeigt, dass fuer alle x (in der jeweiligen Menge) <math>\neg A(x)</math> gilt.
 +
</div>
 +
Allerdings gilt auch hier wieder das Problem wie in Teil B - Beweisen von Allaussagen, dass Allaussagen schwieriger zu beweisen sind.
 +
 
== E - Prinzip der Vollstaendigen Induktion ==
== E - Prinzip der Vollstaendigen Induktion ==
-
Beweisprinzip fuer Allaussagen fuer (Teilmengen der) natuerliche(n) Zahlen.
+
Vollstaendige Induktion ist ein Beweisprinzip fuer Allaussagen fuer (Teilmengen der) natuerliche(n) Zahlen.
-
z.B.
+
<div class="exempel">
-
<math>\forall n \in N: n^2\ne 2</math>
+
'''Beispiel 5'''
-
<math>\forall n \in N_{\ge 1} : 2^n >n</math>
+
<br><math>\forall n \in N: n^2\ne 2</math>
-
<math>\forall n \in N_{\ge 1} : 1+3+5+...+(2n-1)= n^2</math>
+
<br><math>\forall n \in N_{\ge 1} : 2^n >n</math>
-
Idee: Zeige in 2 Schritten
+
<br><math>\forall n \in N_{\ge 1} : 1+3+5+...+(2n-1)= n^2</math>
 +
</div>
 +
Die Idee ist in 2 Schritten zu zeigen, dass die Aussage fuer alle <math>N</math> ab einem bestimmten n gilt. Die beiden Schritte sind
 +
<ol>
 +
<li>
(IA) Induktionsanfang: Die Aussage gilt fuer das kleinste n (n=0 im ersten Beispiel, n=1 im zweiten Beispiel)
(IA) Induktionsanfang: Die Aussage gilt fuer das kleinste n (n=0 im ersten Beispiel, n=1 im zweiten Beispiel)
 +
</li>
 +
<li>
(IS) Induktionsschritt: Wenn die Aussage fuer n gilt, zeige dass sie auch fuer n+1 gilt.
(IS) Induktionsschritt: Wenn die Aussage fuer n gilt, zeige dass sie auch fuer n+1 gilt.
Induktionsprinzip: Damit ist die Aussage bewiesen!
Induktionsprinzip: Damit ist die Aussage bewiesen!
Denn z.B. fuer n=5 (IA) Aussage fuer n=1 <math>\Rightarrow</math>(durch IS) n=2 <math>\Rightarrow</math>(durch IS) n=3 <math>\Rightarrow</math>(durch IS) n=4 <math>\Rightarrow</math>(durch IS) n=5.
Denn z.B. fuer n=5 (IA) Aussage fuer n=1 <math>\Rightarrow</math>(durch IS) n=2 <math>\Rightarrow</math>(durch IS) n=3 <math>\Rightarrow</math>(durch IS) n=4 <math>\Rightarrow</math>(durch IS) n=5.
 +
</li>
 +
</ol>
-
Beispiel:
+
<div class="exempel">
-
Induktion fuer <math>\forall n \in N_{\ge 1} : 2^n >n</math>
+
'''Beispiel 6'''
-
(IA) Fuer n=1 ist <math>2^1>n</math>
+
<br>Induktion fuer <math>\forall n \in N_{\ge 1} : 2^n >n</math>
-
(IV) Wir nehmen fuer ein festes n an: Die Aussage gilt fuer <math>2^n>n</math>
+
<br>(IA) Fuer n=1 ist <math>2^1>n</math>
-
(IS) Zu zeigen ist die Aussage fuer n+1, d.h. zeige <math>2^{n+1}>n+1</math>.
+
<br>(IV) Wir nehmen fuer ein festes n an: Die Aussage gilt fuer <math>2^n>n</math>
-
Benutze hier immer das die Induktionsvoraussetzung <math>2^1>n</math> stimmt.
+
<br>(IS) Zu zeigen ist die Aussage fuer n+1, d.h. zeige <math>2^{n+1}>n+1</math>.
-
Es ist:
+
<br>Benutze hier immer das die Induktionsvoraussetzung <math>2^1>n</math> stimmt.
-
<math>2^{n+1} = 2 \cdot 2^n >^{IV} 2 \cdot n = n+n \ge ^{,da n\ge 1} n+1</math>
+
<br>Es ist:
-
Also: <math>2^{n+1} > n+1</math>
+
<br><math>2^{n+1} = 2 \cdot 2^n >^{IV} 2 \cdot n = n+n \ge ^{,da n\ge 1} n+1</math>
 +
<br>Also: <math>2^{n+1} > n+1</math>
 +
</div>
== 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)
 
-
==B - Rechenregeln bei Summenzeichen==
+
<div class="exempel">
-
Ausklammern bei Summen
+
'''Beispiel 1'''
-
<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>
+
<br>Summe der ersten n natuerlichen Zaheln:
-
Laufindexverschiebung
+
<br><math>\sum^{n}_{i=1}{i}={1+2+3+...+n}</math>
-
<math>\sum^{20}_{i=10}{2i+20}=\sum^{20}_{i=10}{2(i+10)}=\sum^{10}_{i=0}{2i}</math>
+
<br>"Summe von 1 bis n ueber i"
-
Andere Regelen
+
<br>Summe der ersten n geraden Zahelen
-
<math>\sum^{7}_{k=3}{2k+k^2}=2 \sum^{7}_{k=3}{k}+ \sum^{7}_{k=3}{k^2}<math>
+
<br><math>\sum^{n}_{i=1}{2i}={2+4+6+...+2n}</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>
+
<br>Summe der ersten n ungeraden Zahlen
 +
<br><math>\sum^{n}_{i=1}{2i-1}={1+3+5+...+(2n-1)}</math>
 +
<br>Summe von n Einsen
 +
<br><math>\sum^{n}_{i=1}{1}={1+1+...+1}=n</math> (n-mal 1)
 +
<br>Summe von der 10. bis zur 20. geraden Zahl
 +
<br><math>\sum^{20}_{i=10}{2i}={20+22+...+40}</math> (11 Summanden)
 +
</div>
-
==C - Analog Produktzeichen==
+
<div class="regel">
-
z.B.
+
'''Rechenregeln bei Summenzeichen'''
-
<math>\prod^{3}_{k=1}{2k+1}{3\cdot 5\cdot 7}=105</math>
+
<br>Ausklammern bei Summen
-
<math>n!=\prod^{n}_{i=1}{i}</math>
+
<br><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>
 +
<br>Laufindexverschiebung
 +
<br><math>\sum^{20}_{i=10}{2i+20}=\sum^{20}_{i=10}{2(i+10)}=\sum^{10}_{i=0}{2i}</math>
 +
<br>Andere Regelen
 +
<br><math>\sum^{7}_{k=3}{2k+k^2}=2 \sum^{7}_{k=3}{k}+ \sum^{7}_{k=3}{k^2}<math>
 +
<br><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>
 +
</div>
 +
 
 +
==B - Analog Produktzeichen==
 +
<div class="exempel">
 +
'''Beispiel 2'''
 +
<br><math>\prod^{3}_{k=1}{2k+1}{3\cdot 5\cdot 7}=105</math>
 +
<br><math>n!=\prod^{n}_{i=1}{i}</math>
 +
</div>
==D - Summenzeichen und Induktion==
==D - Summenzeichen und Induktion==
Beispiel 3 bei Induktion war
Beispiel 3 bei Induktion war
-
<math>sum^{n}_{i=1}{2i-1}{1+3+5+...+(2n-1)}=n^2</math>.
+
<br><math>\sum^{n}_{i=1}{2i-1}={1+3+5+...+(2n-1)}=n^2</math>.
-
Beweis:
+
<br>Beweis:
-
(IA)
+
<br>(IA)
-
Fuer n=1 ist
+
<br>Fuer n=1 ist
-
<math>\sum^{1}_{i=1}{2i-1}{2\cdot 1-1}=1</math> w
+
<br><math>\sum^{1}_{i=1}{2i-1}{2\cdot 1-1}=1</math> w
-
<math>n^2=1^2=1</math> w
+
<br><math>n^2=1^2=1</math> w
-
(IV)
+
<br>(IV)
-
Wir nehmen an, die Aussage stimmt fuer ein festes n aus <math>N</math>
+
<br>Wir nehmen an, die Aussage stimmt fuer ein festes n aus <math>N</math>
-
d.h. <math>sum^{n}_{i=1}{2i-1}{n^2}</math> (*) kann benutzt werden
+
<br>d.h. <math>\sum^{n}_{i=1}{2i-1}{n^2}</math> (*) kann benutzt werden
-
(IS)
+
<br>(IS)
-
Zeige nun, dass
+
<br>Zeige nun, dass
-
<math>sum^{n+1}_{i=1}{2i-1}{(n+1)^2}</math> gilt, indem man (*) verwendet.
+
<br><math>\sum^{n+1}_{i=1}{2i-1}{(n+1)^2}</math> gilt, indem man (*) verwendet.
-
<math>sum^{n+1}_{i=1}{2i-1}=sum^{n}_{i=1}{2i-1}+(2(n+1)-1)</math>
+
<br><math>\sum^{n+1}_{i=1}{2i-1}=\sum^{n}_{i=1}{2i-1}+(2(n+1)-1)</math>
-
<math>n^2+2n+2=(n+1)^2</math>.
+
<br><math>n^2+2n+2=(n+1)^2</math>.

Version vom 13:29, 1. Okt. 2009

Inhalt:

  • erster Punkt
  • zweiter Punkt
  • dritter Punkt

Lernziele

Nach diesem Abschnitt sollten Sie folgendes können:

  • erstes Ziel
  • zweites Ziel

Kombinatorik

Inhaltsverzeichnis

A - Permutationen

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

Beispiel 1 Wie viele Möglichkeiten gibt es die drei Objekte \displaystyle \star \diamond \bigcirc
in verschiedenen Reihenfolgen an zu ordnen?

\displaystyle \star \ \ \diamond \ \ \bigcirc
\displaystyle \star \ \ \bigcirc \ \ \diamond
\displaystyle \diamond \ \ \bigcirc \ \ \star
\displaystyle \diamond \ \ \star \ \ \bigcirc
\displaystyle \bigcirc \ \ \star \ \ \diamond
\displaystyle \bigcirc \ \ \diamond \ \ \star


Es gibt \displaystyle 3 \cdot 2 \cdot 1 = 3! = 6 (3! = „3 Fakultät“) Möglichkeiten die Objekte anzuordnen. Hierbei gilt, dass für den ersten Gegenstand drei verschiedene Positionen vorhanden sind, f&uume;r den zweiten nur noch zwei Postionen, da schon eine besetzt ist und dementsprechend nur noch eine Position f&uume;r den dritten Gegenstand.


Allgemein:
Für eine Gruppe von n Elementen gibt es \displaystyle n! := n (n-1) (n-2) … \cdot 3 \cdot 3 \cdot 2 \cdot 1 Möglichkeiten („n Fakultät“) die Objekte hintereinander anzuordnen (n! Permutationen). Mit der zusätzlichen Definition \displaystyle 0! := 1 .

Beispiel 2

  1. Möglichkeiten der Anordnung von \displaystyle a, m, b, u ? \displaystyle 4! = 4 \cdot 3 \cdot 2 \cdot 1 = 24
  2. \displaystyle \dfrac{5!}{3!} = \dfrac{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{3 \cdot 2 \cdot 1} = 5 \cdot 4
  3. \displaystyle \dfrac{(n+1)!}{(n-1)!} = \dfrac {(n+1) n (n-1) (n-2) \cdot ... \cdot 2 \cdot 1}{(n-1)(n-2) \cdot …. \cdot 2 \cdot 1} = (n+1) n
  4. \displaystyle 2n! = 2 \cdot n \cdot (n-1) \cdot … \cdot 2 \cdot 1 \displaystyle (2n)! = 2n \cdot (2n-1) \cdot (2n-2) \cdot ... \cdot n \cdot (n-1) \cdot ... \cdot 2 \cdot 1

A - Stichproben aus n- elementigen Mengen

Beispiel 3

Wie viele Worte mit 4 Buchstaben kann man mit den Buchstaben A, R, T, E, N und S bilden? (mit Doppelbenutzung)
1. Buchstabe: 6 Möglichkeiten
2. Buchstabe: 6 Möglichkeiten
3. Buchstabe: 6 Möglichkeiten
4. Buchstabe: 6 Möglichkeiten

Also gibt es \displaystyle 6 \cdot 6 \cdot 6 \cdot 6 = 6^4 Möglichkeiten.


Allgemein:
Es gibt \displaystyle n^k Möglichkeiten der Anordnung, die beim k- maligen Auswählen aus n Objekten mit Wiederholung und mit Berücksichtigung der Reihenfolge entstehen können.

Beispiel 4

Wie zuvor bei Beispiel 3 nur ohne Doppelbenutzung der Buchstaben.


1.Ziehen : 6 Möglichkeiten
2.Ziehen : 5 Möglichkeiten
3.Ziehen : 4 Möglichkeiten
4.Ziehen : 3 Möglichkeiten
insgesamt: \displaystyle 6 \cdot 5 \cdot 4 \cdot 3 Möglichkeiten. \displaystyle 6 \cdot 5 \cdot 4 \cdot 3 = \dfrac{6!}{2!} = \dfrac{6!}{(6-4)!}


Allgemein:
Es gibt \displaystyle n \cdot (n-1) \cdot (n-2) \cdot ... \cdot (n-k+1) = \dfrac{n!}{(n-k)!} Möglichkeiten aus n Objekten k Stück unter Berücksichtigung der Reihenfolge und ohne Zurücklegen auszusuchen.

Beispiel 5

„Lotto“ mit Reihenfolge

Anzahl der Möglichkeiten: \displaystyle \dfrac{49!}{(49-6)!} = 49 \cdot 48 \cdot 47 \cdot 46 \cdot 45 \cdot 44 \approx 10 \cdot 10^9 (*)

Aber: Die Reihenfolge ist bei echtem Lotto unwichtig. Für sechs feste Zahlen sind 6! Kombinationen in (*) enthalten.

Beispiel 6

Also: „echtes“ Lotto \displaystyle \dfrac{49!}{(49-6)!} \cdot \dfrac{1}{6!} = \dfrac{49!}{(49-6)!6!} = \binom{49}{6} \approx 13 \cdot 10^6 Möglichkeiten.

Auswahlmöglichkeiten für k aus n Elementen ohne Zurücklegen und ohne Reihenfolge:

\displaystyle \binom{n}{k} = \dfrac{n!}{(n-k)!k!}

Hierf&u ume;r ben&oome;tigt man den Binomialkoeffizient der hier noch einmal ausf&u ume;rlicher erkl&a ume;rt wird.

mit \displaystyle n \in N , k \in N , n \ge k

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 \displaystyle n^k

(Beispiel 3)

\displaystyle \dfrac{n!}{(n-k)!}

(Beispiel 4)

Reihenfolge unwichtig \displaystyle \binom{n+k-1}{k}

(wird selten gebraucht, hier ist es aber der Vollständigkeit halber aufgeführt)

\displaystyle \binom{n}{k} = \dfrac{n!}{(n-k)!k!}

(Beispiel 6)

Beispiel 7

Wähle 3 Personen aus 10 aus. Wie viele Möglichkeiten gibt es?

Nach Urnenmodell: Ziehe 3 aus 10, ohne Zurück legen und ohne Reihenfolge.

Es gilt \displaystyle \binom{10}{3} = \dfrac{10 \cdot 9 \cdot 8}{3 \cdot 2 \cdot 1} = 120 Möglichkeiten

Beispiel 8

Wie viele Möglichkeiten gibt es beim Skat spielen 32 Karten auf 3 Spieler (10 Karten) zu und Skat (2 Karten) zu verteilen?

Kombinationen f&ume;r den 1.Spieler \displaystyle \cdot Kombinationen f&ume;r den 2. Spieler \displaystyle \cdot Kombinationen f&ume;r den 3. Spieler \displaystyle \cdot Kombinationen f&ume;r den 4. Spieler \displaystyle = \binom{32}{10} \cdot \binom{22}{10} \cdot \binom{12}{10} \cdot \binom{2}{2} \displaystyle =\dfrac{32!}{22! \cdot 10!} \cdot \dfrac{22!}{12! \cdot 10!} \cdot \dfrac{12!}{2! \cdot 10!} \cdot \dfrac{2!}{2! \cdot 0!} \displaystyle =\dfrac{32!}{10! \cdot 10! \cdot 10! \cdot 2!}.

(Bemerkung: Es gibt auch noch andere Rechnungen, die auf das gleiche Ergebnis führen.)

Allgemein:
Es gibt \displaystyle \dfrac{n!}{k_1! k_2! … k_i!} Möglichkeiten, n Objekte auf i Gruppen zu verteilen, wobei jede Gruppe \displaystyle k_j Elemente haben soll. (im Beispiel: \displaystyle n=32, j=4 \mbox{Gruppen,} k_1=10, k_2=10, k_3=10, k_4=2)


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.

Beispiel 1
"7 ist gerade" f
"7 ist eine Primzahl" w
"7 teilt 42" w
"7 < 3" f

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

B - Verknuepfung von Aussagen

Logisches "und" ( \displaystyle \wedge ) Das logische "und" ist wie "und" im normalen Sprachgebrauch. Eine Verknuepfung zweier Aussagen mit einem logischen und ist nur dann wahr wenn beide Aussagen auch wahr sind.

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

Beispiel 2
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

Logisches "oder" (\displaystyle \vee ) (lat. vel = oder) Auch das logische "oder" ist wie "oder" im normalen Sprachgebrauch. Eine Verknuepfung zweier Aussagen mit einem logischen oder ist nur dann wahr wenn mindestens eine der Aussagen auch wahr ist.

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

Beispiel 3
A: "\displaystyle \pi > 0 " w
B: "7 teilt 42 " w
A \displaystyle \vee B w


c - Verneinung

Das mathematische Zeichen fuer Verneinung ist \displaystyle \neg . Es bedeutet ausgeprochen "nicht" und veraendert den Wahrheitswert jeder Aussage zum jeweiligen Gegenteil.

A \displaystyle \neg A
w f
f w

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


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.

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))

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

\displaystyle \neg (A \wedge B) =\parallel = \neg A \vee \neg B (= (\neg A) \vee (\neg B))
Und analog dazu
\displaystyle \neg (A \vee B) =\parallel = \neg A \wedge \neg B

Beispiel 5
A: "Ich bin schlecht in Mathe."
B: "Ich bin schlecht in Deutsch." \displaystyle \neg (A \wedge B) =\parallel = \neg A \vee \neg B
Hier bedeutet \displaystyle \neg (A \wedge B) ich bin nicht schlecht in Mathe und Deutsch, \displaystyle \neg A \vee \neg B dass man entweder weder in Mathe noch in Deutsch schlecht ist, oder nur in einem von beiden. Aber nicht in beiden.

Beispiel 6
A: "Ich bin besoffen."
B: "Ich bin muede." \displaystyle \neg (A \vee B) =\parallel = \neg A \wedge \neg B
Hier bedeutet \displaystyle \neg (A \vee B) ich bin nicht besoffen oder muede, \displaystyle \neg A \wedge \neg B dass man nicht besoffen und nicht muede ist.

D - Implikationen

Wir definieren A \displaystyle \RightarrowB per Wahrheitswerttabelle. Gesprochen bedeutet A \displaystyle \RightarrowB, dass immer wenn A gilt, dann auch B.

\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

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}

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

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

G - Aussageformen

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

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

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

Beim Beweisen von Existenzaussagen reicht es ein Beispiel anzugeben.

Beispiel 1

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

B - Beweisen von Allaussagen

Allaussagen sind schwerer zu beweisen. Hier reichen keine Beispiele, es muss mit Variablen gerechnet werden.

Beispiel 2
\displaystyle \forall a,b \in R :(a,b \ge 0) \Rightarrow \dfrac{a+b}{2} \ge \sqrt{a \cdot b}

Seien \displaystyle a, b \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}

Auf (*) zu kommen ist nicht immer ganz leicht. Man kann durch probieren darauf kommen oder weiss es aus Erfahrung.

c - Widerlegen von Allaussagen

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

Allgemein
\displaystyle \neg \forall x: A(x) =\parallel = \exists x: \neg A(x)
Also reicht zum Widerlegen von Allaussagen, die Existenz eines Gegenbeispiels zu zeigen.

Beispiel 3
\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.

D - Widerlegen von Existenzaussagen

Beispiel 4
\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)
Existenzaussagen koennen widerlegt werden, indem man zeigt, dass fuer alle x (in der jeweiligen Menge) \displaystyle \neg A(x) gilt.

Allerdings gilt auch hier wieder das Problem wie in Teil B - Beweisen von Allaussagen, dass Allaussagen schwieriger zu beweisen sind.


E - Prinzip der Vollstaendigen Induktion

Vollstaendige Induktion ist ein Beweisprinzip fuer Allaussagen fuer (Teilmengen der) natuerliche(n) Zahlen.

Beispiel 5
\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

Die Idee ist in 2 Schritten zu zeigen, dass die Aussage fuer alle \displaystyle N ab einem bestimmten n gilt. Die beiden Schritte sind

  1. (IA) Induktionsanfang: Die Aussage gilt fuer das kleinste n (n=0 im ersten Beispiel, n=1 im zweiten Beispiel)
  2. (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 6
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 1
Summe der ersten n natuerlichen Zaheln:
\displaystyle \sum^{n}_{i=1}{i}={1+2+3+...+n}
"Summe von 1 bis n ueber i"
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}
\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}}

B - Analog Produktzeichen

Beispiel 2
\displaystyle \prod^{3}_{k=1}{2k+1}{3\cdot 5\cdot 7}=105
\displaystyle n!=\prod^{n}_{i=1}{i}

D - Summenzeichen und Induktion

Beispiel 3 bei Induktion war
\displaystyle \sum^{n}_{i=1}{2i-1}={1+3+5+...+(2n-1)}=n^2.
Beweis:
(IA)
Fuer n=1 ist
\displaystyle \sum^{1}_{i=1}{2i-1}{2\cdot 1-1}=1 w
\displaystyle n^2=1^2=1 w
(IV)
Wir nehmen an, die Aussage stimmt fuer ein festes n aus \displaystyle N
d.h. \displaystyle \sum^{n}_{i=1}{2i-1}{n^2} (*) kann benutzt werden
(IS)
Zeige nun, dass
\displaystyle \sum^{n+1}_{i=1}{2i-1}{(n+1)^2} gilt, indem man (*) verwendet.
\displaystyle \sum^{n+1}_{i=1}{2i-1}=\sum^{n}_{i=1}{2i-1}+(2(n+1)-1)
\displaystyle n^2+2n+2=(n+1)^2.

Von „http://wiki.sommarmatte.se/wikis/2009/bridgecourse1-TU-Berlin/index.php/ZusatzStoffTUB“