Aus Online Mathematik Brückenkurs 1

Kombinatorik

Inhaltsverzeichnis 1 A - Permutationen 2 A - Stichproben aus n- elementigen Mengen 3 6. Mathematische Formalismen 4 6.1. Logische Grundlagen (Aussagenlogik) 5 A - Aussagen 6 B - Verknüpfung von Aussagen 7 c - Verneinung 8 D - Tautologische Aequivalenzen 9 E - Regel von de Morgan 10 D - Implikationen 11 E - Äquivalenz 12 F - Kontraposition 13 G - Aussageformen 14 6.2. Beweisen und Widerlegen 15 A - Beweisen von Existenzaussagen 16 B - Beweisen von Allaussagen 17 c - Widerlegen von Allaussagen 18 D - Widerlegen von Existenzaussagen 19 E - Prinzip der Vollständigen Induktion 20 6.3 Mathematische Symbole und Formalien 21 A - Summen - und Produktzeichen 22 B - Analog Produktzeichen 23 D - Summenzeichen und Induktion 24 E - Einige mathematische Symbole 25 F - ....

A - Permutationen

Permutationen sind die Anzahl der Möglichkeiten, die Anordnung von Gegenständen zu Vertauschen, also die Anzahl der Möglichkeiten 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)

Dieser Abschnitt braucht noch besonders viel Überarbeitung. Viele Aussagen sind unscharf formuliert und Beispiele aus der VL (von Thorsten Rohwedder) fehlen.

A - Aussagen

B - Verknüpfung von Aussagen

c - Verneinung

D - Tautologische Aequivalenzen

Zwei Aussagen heissen tautologisch äquivalent, wenn ihre Wahrheitstafeln übereinstimmen, z.B. \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 für jeden Wahrheitswert von A denselben Wert.

E - Regel von de Morgan

\displaystyle \neg (A \wedge B) =\parallel = \neg A \vee \neg B ( =\parallel = (\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 tautologisch äquivalent sind. Also gilt

D - Implikationen

Dieser Abschnitt braucht besonders viel Überarbeitung.

Wir definieren A \displaystyle \RightarrowB per Wahrheitstafeln. 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 - Äquivalenz

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

F - Kontraposition

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 B \ne \neg A \displaystyle \Rightarrow \neg B)

Hier (bei Vorsicht) waere ein Beispiel sinnvoll.

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 10
   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. Mit dem Quantor \displaystyle \forall "für alle"
      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

      
      Für 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 hängt (über den Quantor (\displaystyle \forall) ) von der Menge ab.

   2. Mit dem Quantor \displaystyle \exists "es existiert"
      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

      
      Es existieren ein \displaystyle x \in N und ein \displaystyle y \in N die addiert 1 ergeben.

      Kurz \displaystyle \exists x \in N \exists y \in N: C(x,y) w z.B. x=0, y=1

      Der Wahrheitswert hängt 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 für alle x in \displaystyle R ein y für 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 (Beispiel einfügen!). Vertauscht man die Quantoren in dem vorherigen Beipiel, entsteht eine völlig 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 für jedes x in \displaystyle R C(x,y) gilt.
3. Oft werden All-Quantoren weggelassen. Z.B. schreibt man \displaystyle {{n}\choose{k}} = {{n}\choose{n-k}} und meint \displaystyle \forall n \in N , \displaystyle \forall k \in N : \displaystyle k \leq n \Rightarrow { n \choose k } = {{n}\choose{n-k}} .

6.2. Beweisen und Widerlegen

In VL: Wichtigkeit von "All-Aussagen" und "Existenz-Aussagen" in der Mathematik.

A - Beweisen von Existenzaussagen

Beim Beweisen von Existenzaussagen reicht es ein Beispiel anzugeben.

B - Beweisen von Allaussagen

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

c - Widerlegen von Allaussagen

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

D - Widerlegen von Existenzaussagen

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

E - Prinzip der Vollständigen Induktion

Vollständige Induktion ist ein Beweisprinzip für Allaussagen für (Teilmengen der) natürliche(n) Zahlen.

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

1. (IA) Induktionsanfang: Die Aussage gilt für das kleinste n (n=0 im ersten Beispiel, n=1 im zweiten Beispiel)
2. (IS) Induktionsschritt: Wenn die Aussage für n gilt, zeige dass sie auch für n+1 gilt. Induktionsprinzip: Damit ist die Aussage bewiesen!
   Denn z.B. für n=5 (IA) Aussage für 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.

6.3 Mathematische Symbole und Formalien

A - Summen - und Produktzeichen

Bei dem Summenzeichen \displaystyle \sum^{n}_{i=k} werden alle Zahlen addiert von k bis n über i.

B - Analog Produktzeichen

Bei dem Produktzeichen gelten die gleichen Regeln wie auch schon bei dem Summenzeichen.

D - Summenzeichen und Induktion

Das dritte Beispiel bei Induktion war
\displaystyle \sum^{n}_{i=1}{2i-1}=1+3+5+...+(2n-1). Diese Summe kann man auch mit \displaystyle n^2 darstellen. Um dieses zu beweisen, kann man die Vollständige Induktion verwenden.

Beweis:
(IA)
Für n=1 ist
\displaystyle \sum^{1}_{i=1}{2i-1}{2\cdot 1-1}=1=1^2=n^2 w
(IV)
Wir nehmen an, die Aussage stimmt für 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 du (*) verwendest.
\displaystyle \sum^{n+1}_{i=1}{2i-1}=\left(\sum^{n}_{i=1}{2i-1}\right ) +(2(n+1)-1)= n^2+2n+1=(n+1)^2.

E - Einige mathematische Symbole

Mengen

• Mengenklammer { , }
  Beispiel: A={1,2,3} (eine Menge die 1,2,3 enthält)
• Element von \displaystyle \in
  Beispiel: 1\displaystyle \inA
• nicht Element von \displaystyle \not \in
  Beispiel: 4\displaystyle \not \inA
• Teilmenge \displaystyle \subset , \subseteq
  Beispiel: {1,2} \displaystyle \subseteqA , {1,2,3} \displaystyle \subseteq A
• leere Menge {}\displaystyle \not \circ
  Beispiel: x\displaystyle \in \not \circ: ist eine falsche Aussage

Intervalle

• abgeschlossenes Intervall [a,b] = {x|\displaystyle a \le x \le b }
  In einem abgeschlossenen Intervall sind beide Intervallgrenzen(a und b) enthalten.
• halboffne Intervall ]a,b]= {x|\displaystyle a< x\le b}=(a,b] [a,b[= {x|\displaystyle a\le x< b }=[a,b)
  In einem halboffenen Intervall ist eine der beiden Grenzen enthalten.
• offene Intervalle ]a,b[= {x|\displaystyle a< x < b }=(a,b)
  In einem offenen Intervall sind beide Grenzen nicht enthalten.

Mengenoperationen
Für Mengen A, B heißt

• Vereinigung
  \displaystyle A \cup B= {\displaystyle x|x \in A \vee x \in B}
  In der Vereinigung zweier Mengen sind alle Elemente aus den A und B enthalten.
• Schnitt
  \displaystyle A \cap B= {\displaystyle x|x \in A \wedge x \in B}
  In dem Schnitt zweier Mengen sind alle Elemente enthalten, die sowohl in A als auch in B enthalten sind.
• Mengensubtraktion
  \displaystyle A \backslash B = {\displaystyle x| x\in A \wedge \neg (x\in B) }
  Bei der Mengensubraktion werden aus der Menge A alle Elemente gestrichen, die in der Menge B enthalten sind.

F - ....

Über den typisch mathematischen Aufbau einer VL / von Wissen als Definitionen, Sätze, Theoreme, ggf. auch Lemmata.