You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
2684 lines
107 KiB
2684 lines
107 KiB
\documentclass[11pt]{scrartcl}
|
|
\usepackage[utf8]{inputenc}
|
|
\usepackage[ngerman]{babel}
|
|
\usepackage{amsmath}
|
|
\usepackage{amssymb}
|
|
\usepackage{multicol}
|
|
\usepackage{booktabs}
|
|
%\usepackage{pstricks}
|
|
%\usepackage{pst-node}
|
|
\usepackage[paper=a4paper,left=30mm,right=20mm,top=20mm,bottom =25mm]{geometry}
|
|
\usepackage[
|
|
pdftitle={Grundlagen der Mathematik},
|
|
pdfsubject={Mitschrift der Vorlesung "Grundlagen der Mathematik" an der HTW-Aalen, bei Herrn Arnold.},
|
|
pdfauthor={Thomas Battermann},
|
|
pdfkeywords={Grundlagen der Mathematik,Logik,Mengen,Relationen,Funktion,Vollstaendige Induktion},
|
|
pdfborder={0 0 0}
|
|
]{hyperref}
|
|
\usepackage{tabularx}
|
|
\usepackage{graphicx}
|
|
\usepackage{color}
|
|
\usepackage{lastpage}
|
|
\usepackage{fancyhdr}
|
|
\setlength{\parindent}{0ex}
|
|
\setlength{\parskip}{2ex}
|
|
\setcounter{secnumdepth}{4}
|
|
\setcounter{tocdepth}{4}
|
|
\definecolor{darkgreen}{rgb}{0,0.5,0}
|
|
\definecolor{darkblue}{rgb}{0,0,0.5}
|
|
|
|
\pagestyle{fancy} %eigener Seitenstil
|
|
\fancyhf{} %alle Kopf- und Fußzeilenfelder bereinigen
|
|
\fancyhead[L]{Grundlagen der Mathematik} %Kopfzeile links
|
|
\fancyhead[C]{Semester 1} %zentrierte Kopfzeile
|
|
\fancyhead[R]{WS 2010/2011} %Kopfzeile rechts
|
|
\renewcommand{\headrulewidth}{0.4pt} %obere Trennlinie
|
|
\fancyfoot[C]{Seite \thepage\ von \pageref{LastPage}}
|
|
\renewcommand{\footrulewidth}{0.4pt} %untere Trennlinie
|
|
|
|
\newcommand{\spa}{\hspace*{4mm}}
|
|
\newcommand{\defin}{\textcolor{darkgreen}{\textbf{Def.: }}}
|
|
\newcommand{\rrfloor}{\right\rfloor}
|
|
\newcommand{\llfloor}{\left\lfloor}
|
|
|
|
|
|
\title{Grundlagen der Mathematik}
|
|
\author{Mitschrift von Thomas Battermann}
|
|
\date{1. Semester}
|
|
\begin{document}
|
|
\pagestyle{empty}
|
|
|
|
\maketitle\thispagestyle{empty}
|
|
\tableofcontents\thispagestyle{empty}
|
|
|
|
\newpage
|
|
\pagestyle{fancy}
|
|
\setcounter{page}{1}
|
|
|
|
\section{Logik}
|
|
|
|
\begin{itemize}
|
|
\item Grundlage (Mathematischer und anderer Beweise)
|
|
\item interessante Problemstellungen in der Informatik:\\
|
|
Besitzt eine logische Formel eine Lösung?
|
|
\item Kontrollstrukturen in Computerprogrammen arbeiten nach den Gesetzen der Logik
|
|
\end{itemize}
|
|
|
|
\subsection{Formeln}
|
|
|
|
\underline{Aussagen} sind Sätze, die wahr oder falsch sind.\\
|
|
Beispiele:
|
|
\begin{itemize}
|
|
\item „3 ist eine Primzahl“ ist eine (wahre) Aussage
|
|
\item „4 ist eine Primzahl“ ist eine (falsche) Aussage
|
|
\item „Wieviel Uhr ist es?“ ist keine Aussage, sondern eine Frage
|
|
\item „Sagen sie mir bitte wieviel Uhr es ist.“ ist eine Aufforderung, keine Aussage
|
|
\end{itemize}
|
|
|
|
\underline{Formeln} entstehen durch Verknüpfung einzelner Aussagen (oder Formeln).\\
|
|
Beispiele: Seien A und B Aussagen.\\
|
|
Dann sind
|
|
\begin{itemize}
|
|
\item nicht $A$
|
|
\item $A$ oder $B$
|
|
\item entweder $A$ oder $B$
|
|
\item wenn $A$, dann $B$
|
|
\end{itemize}
|
|
Formeln.
|
|
|
|
Die Verknüpfungen nicht, oder usw. heißen Junktoren.
|
|
|
|
Formeln nehmen (wie die Aussage) einen der Wahrheitswerte wahr oder falsch an; dieser hängt ab von den Wahrheitswerten enthaltenen Aussagen.\\
|
|
Diese Abhängigkeiten stellen wir in einer Wahrheitstabelle dar, die für jede Kombination der Aussagen den zugehörigen Wahrheitswert der Formel enthält.
|
|
|
|
\begin{tabular}{ll}
|
|
Abkürzungen: & \( 0 \widehat{=} \) falsch \\
|
|
& \( 1 \widehat{=} \) wahr
|
|
\end{tabular}
|
|
|
|
\underline{Negation} (nicht \(A =: \neg A =: \overline{A}\)
|
|
|
|
\begin{tabular}{c|c}
|
|
\(A\) & \(\overline{A}\) \\
|
|
\hline
|
|
0 & 1\\
|
|
1 & 0
|
|
\end{tabular}
|
|
|
|
\underline{Konjunktion} ( \(A \text{ und } B =: A \land B =: A \cdot B \))
|
|
|
|
\begin{tabular}{cc|c}
|
|
\(A\) & \(B\) & \(A \land B\)\\
|
|
\hline
|
|
0&0&0\\
|
|
0&1&0\\
|
|
1&0&0\\
|
|
1&1&1
|
|
\end{tabular}
|
|
|
|
\underline{Disjunktion} (\( A \text{ oder } B =: A \lor B =: A + B\))
|
|
|
|
\begin{tabular}{cc|c}
|
|
\(A\) & \(B\) & \( A \lor B \)\\
|
|
\hline
|
|
0&0&0\\
|
|
0&1&1\\
|
|
1&0&1\\
|
|
1&1&1
|
|
\end{tabular}
|
|
|
|
\underline{Exklusive Disjunktion} (entweder \(A\) oder \(B =: A \oplus B\))
|
|
|
|
\begin{tabular}{cc|c}
|
|
\(A\) & \(B\) & \(A \oplus B\)\\
|
|
\hline
|
|
0&0&0\\
|
|
0&1&1\\
|
|
1&0&1\\
|
|
1&1&0
|
|
\end{tabular}
|
|
|
|
\underline{Implikation} (wenn \(A\), dann \(B =: A \leftarrow B \))
|
|
\begin{multicols}{2}
|
|
\begin{tabular}{cc|c}
|
|
\(A\) & \(B\) & \(A \rightarrow B\)\\
|
|
\hline
|
|
0&0&1\\
|
|
0&1&1\\
|
|
1&0&0\\
|
|
1&1&1
|
|
\end{tabular}
|
|
\columnbreak\\
|
|
A: Voraussetzung\\
|
|
B: Folgerung
|
|
\end{multicols}
|
|
|
|
\underline{Äquivalenz} (\(A\) genau dann, wenn \( B =: A \leftrightarrow B\))
|
|
|
|
\begin{tabular}{cc|c}
|
|
\(A\) & \(B\) & \(A \leftrightarrow B\)\\
|
|
\hline
|
|
0&0&1\\
|
|
0&1&0\\
|
|
1&0&0\\
|
|
1&1&1
|
|
\end{tabular}
|
|
|
|
Formeln können zu komplexeren Formeln verknüpft werden.\\
|
|
Beispiel: \( ( A \oplus B ) \rightarrow ( C \lor B ) \)
|
|
|
|
Eine Formel heißt \underline{erfüllbar}, wenn es eine Belegung der enthaltenen Aussagen gibt, so dass eine Formel wahr wird.\\
|
|
Eine Formel, die nicht erfüllbar ist, heißt \underline{unerfüllbar}.\\
|
|
Eine Formel, die bei jeder Belegung wahr wird, heißt \underline{gültig} oder \underline{tautologisch}.
|
|
|
|
Beispiel:
|
|
\begin{itemize}
|
|
\item \( A \lor B\) ist erfüllbar.
|
|
\item \( A \land \overline{A} \) ist unerfüllbar.
|
|
\item \( A \lor \overline{A}\) ist tautologisch.
|
|
\item
|
|
Sei \(F\) eine Formel.\\
|
|
\(F\) ist genau dann tautologisch, wenn \(\overline{F}\) unerfüllbar ist.
|
|
\end{itemize}
|
|
|
|
\subsection{Äquivalenz von Formeln}
|
|
|
|
Zwei Formeln \(F\) und \(G\) heißen \underline{äquivalent}, wenn \(F\) und \(G\) bei jeder Variablenbelegung denselben Wahrheitswert annehmen (d.\,h. die Wahrheitstabellen sind identisch).\\
|
|
\hspace*{4mm} \( F \equiv G, \quad F \Leftrightarrow G\)\\
|
|
(\(F\),\(G\) heißen gleich, wenn ihre Definitionen Zeichen für Zeichen übereinstimmen, \(F = G\))
|
|
|
|
Beispiel:\\
|
|
\(\quad F := A \land B, \quad G := B \land A\)\\
|
|
\(\Rightarrow F \equiv G, \quad F \ne G \)
|
|
|
|
in Analogie zu \(\Leftrightarrow\):\\
|
|
\( \quad F \Rightarrow G \)
|
|
|
|
(G wird bei jeder wahr, bei der auch \(F\) wahr ist.)\\
|
|
Beispiel:\\
|
|
\(A \land B \Rightarrow A \)
|
|
|
|
\subsubsection{Rechengesetze:}
|
|
|
|
\begin{itemize}
|
|
\item\underline{Kommutativgesetze}\\
|
|
Vertauschungsgesetze
|
|
|
|
\begin{align*}
|
|
A \lor B &\equiv B \lor A\\
|
|
A \land B &\equiv B \land A\\
|
|
A \oplus B &\equiv B \oplus\\
|
|
A \leftrightarrow B &\equiv B \leftrightarrow A
|
|
\end{align*}
|
|
|
|
\item\underline{Assoziativgesetze}\\
|
|
(Klammergesetze)
|
|
|
|
\begin{align*}
|
|
A \lor (B \lor C) &\equiv (A \lor B) \lor C\\
|
|
A \land ( B \land C) &\equiv (A \land B) \land C\\
|
|
A \oplus ( B \oplus C) & \equiv (A \oplus B) \land C\\
|
|
A \leftrightarrow (B \leftrightarrow C) &\equiv (A \leftrightarrow B) \leftrightarrow C
|
|
\end{align*}
|
|
|
|
\item\underline{Distributivgesetze}\\
|
|
(Ausklammern)
|
|
|
|
Vgl. mit Arithmetik:\\
|
|
\(a \cdot (b+c) = a \cdot b + a \cdot c\)\\
|
|
i.\,a. \( a + (b \cdot c) \ne (a +b)(a+c) \)
|
|
|
|
In der Logik:\\
|
|
\begin{align*}
|
|
A \land ( B \lor C) &\equiv (A \land B) \lor (A\land C)\\
|
|
A \lor ( B \land C) &\equiv (A \lor B) \land (A \lor C)\\
|
|
A \land ( B \oplus C ) &\equiv (A \land B) \oplus (A \land C)
|
|
\end{align*}
|
|
|
|
\item\underline{doppelte Negation}
|
|
|
|
\( \overline{\overline{A}} = A \)
|
|
|
|
\item\underline{deMorgansche Gesetze}\\
|
|
\( \neg ( A \land B) \equiv \overline{A} \lor \overline{B} \)\\
|
|
\( \neg ( A \lor B) \equiv \overline{A}\land \overline{B} \)
|
|
|
|
\item\underline{weitere Negation-Gesetze}\\
|
|
\( \overline{A \oplus B} \equiv A \leftrightarrow B \equiv \overline{A} \leftrightarrow \overline{B} \)\\
|
|
\( \overline{A \leftrightarrow B} \equiv A \oplus B \equiv \overline{A} \oplus \overline{B} \)
|
|
|
|
\begin{tabular}{cc|ccc}
|
|
A & B & \( A \oplus B \) & \( \overline{a \oplus }\) & \(A \leftrightarrow B\)\\
|
|
\hline
|
|
0&0&0&1&1\\
|
|
0&1&1&0&0\\
|
|
1&0&1&0&0\\
|
|
1&1&0&1&1
|
|
\end{tabular}
|
|
|
|
\item\underline{Absorptionsgesetze}\\
|
|
|
|
\begin{align*}
|
|
(A \land B) \lor A &\equiv A\\
|
|
(A \lor B) \land A &\equiv A
|
|
\end{align*}
|
|
|
|
\item\underline{Idempotenzgesetze}\\
|
|
\( A \land A \equiv A \equiv A \lor A \)
|
|
|
|
\item\underline{ausgeschlossenes Drittes}\\
|
|
\begin{align*}
|
|
A \land \overline{A} \equiv 0 \\
|
|
A \lor \overline{A} \equiv 1
|
|
\end{align*}
|
|
|
|
\item\underline{Gesetze für 0 und 1}\\
|
|
\begin{align*}
|
|
A \land 1 &\equiv A & A \lor 1 &\equiv 1\\
|
|
A \land 0 &\equiv 0 & A \lor 0 &\equiv A\\
|
|
A \oplus 0 &\equiv A & A \oplus 1 &\equiv \overline{A}
|
|
\end{align*}
|
|
|
|
\item\underline{Kontraposition}\\
|
|
\( A \rightarrow B \equiv \overline{B} \rightarrow \overline{A}\)\\
|
|
(verwendet man z.\,B. beim Widerspruchsbeweis)
|
|
|
|
\item\underline{auch noch wichtig}\\
|
|
\begin{multicols}{2}
|
|
\( A \rightarrow B \equiv \overline{A} \lor B \)\\
|
|
\( \overline{C} \lor D \equiv C \rightarrow D\)
|
|
\columnbreak\\
|
|
\begin{tabular}{cc|cc}
|
|
A & B & \(A \rightarrow B \) & \( \overline{A} \lor B \)\\
|
|
\hline
|
|
0 & 0 & 1\\
|
|
0&1&1\\
|
|
1&0&0\\
|
|
1&1&1
|
|
\end{tabular}
|
|
\end{multicols}
|
|
\end{itemize}
|
|
|
|
Beispiel:\\
|
|
Beweis der Kontrapositionsgesetzes
|
|
\begin{multicols}{2}
|
|
\begin{align*}
|
|
A \rightarrow B \underset{12}{\equiv} \overline{A} \lor B
|
|
\underset{1}{\equiv} B \lor \overline{A}
|
|
\underset{4}{\equiv} \overline{\overline{B}} \lor \overline{A}
|
|
\underset{12}{\equiv} \overline{B} \rightarrow \overline{A}
|
|
\end{align*}
|
|
\columnbreak\\
|
|
\begin{tabular}{cc|ccc}
|
|
A & B & \(\overline{A}\) & \(\overline{B}\) & \( \overline{B} \rightarrow \overline{A} \)\\
|
|
\hline
|
|
0&0&1&1&1\\
|
|
0&1&1&0&1\\
|
|
1&0&0&1&0\\
|
|
1&1&0&0&1
|
|
\end{tabular}
|
|
\end{multicols}
|
|
|
|
\subsection{Normalformen}
|
|
Konstruktion einer zu F Äquivalenten Formel:
|
|
|
|
Idee: Suche eine Formel , die genau bei den 1-Zeilen wahr wird.
|
|
|
|
\begin{tabular}{ccc|ccl}
|
|
A&B&C& F & \hspace*{5mm}\\
|
|
\hline
|
|
0&0&0& 0\\
|
|
0&0&1& 1 && \( \overline{A} \land \overline{B} \land C\)\\
|
|
0&1&0& 1 && \( \overline{A} \land B \land \overline{C}\)\\
|
|
0&1&1& 0\\
|
|
1&0&0& 1 && \( A \land \overline{B} \land \overline{C}\)\\
|
|
1&0&1& 0\\
|
|
1&1&0& 1 && \( A \land B \land \overline{C}\)\\
|
|
1&1&1& 0\\
|
|
\end{tabular}
|
|
|
|
\( F' := \overline{A B} C \lor \overline{A} B \overline{C} \lor A \overline{BC} \lor A B \overline{C} \)
|
|
|
|
\begin{multicols}{2}
|
|
Die entstandene Formel ist also eine Disjunktion von Konjunktionen von Variablen der negierten Variablen.\\
|
|
(Variablen und negierte Variablen bezeichnet man als \underline{Literale}, Konjunktionen von Literalen als (Und-)\underline{Klauseln})\\
|
|
Solche Formeln heißen \underline{disjunktive Normalformen} (DNF).
|
|
\columnbreak\\
|
|
\begin{tabular}{ccc|ccl}
|
|
A&B&C& F\\
|
|
\hline
|
|
0&0&0& 0\\
|
|
0&0&1& 1\\
|
|
0&1&0& 1\\
|
|
0&1&1& 0\\
|
|
1&0&0& 1\\
|
|
1&0&1& 0\\
|
|
1&1&0& 1\\
|
|
1&1&1& 0\\
|
|
\end{tabular}
|
|
\end{multicols}
|
|
|
|
|
|
2. Idee: Suche eine Formel für \(F''\), die genau bei den 0-Zeilen in der Wahrheitstabelle falsch wird.
|
|
|
|
\begin{align*}
|
|
F'' &= \neg ( \overline{A}\overline{B}\overline{C} ) \land
|
|
\neg ( \overline{A} B C ) \land
|
|
\neg ( A \overline{B} C ) \land
|
|
\neg ( A B C ) & (*)\\
|
|
&= \left(A \lor B \lor C\right) \land
|
|
\left(A \lor \overline{B} \lor \overline{C}\right) \land
|
|
\left(\overline{A} \lor B \lor \overline{C}\right) \land
|
|
\left(\overline{A} \lor \overline{B} \lor \overline{C}\right)
|
|
\end{align*}
|
|
|
|
Eine solche Konjunktion von (Oder-)Klauseln heißt \underline{Konjunktive Normalform} (KNF).\\
|
|
An der Formel \((*)\) sieht man, daß es zu jeder Formel eine äquivalente Formel gibt, die nur die Junktoren \( \land, \neg \) enthält.\\
|
|
Junktorenmenge mit dieser Eigenschaft nennt man Basen.
|
|
|
|
Beispiel: Auch \( \{ \lor, \neg \} \) ist eine Basis.\\
|
|
Es gibt zwei Basen aus nur einem Junktor:
|
|
\begin{itemize}
|
|
\item NAND ( \( A \text{ NAND } B = \neg ( A \land B ) \) )
|
|
\item NOR (weder-noch),\\
|
|
\( A \text{ NOR } B = \overline{A} \land \overline{B} \)
|
|
|
|
Beweisidee:\\
|
|
\( \{\lor, \neg\} \) ist eine Basis;\\
|
|
\( A \lor B \equiv \overline{\overline{A\lor B}} \equiv \overline{\overline{A} \land \overline{B}} \equiv \neg (A \text{ NOR } B ) \)\\
|
|
\( \neg A \equiv \overline{A} \land \overline{A} \equiv A \text{ NOR } A \equiv (A \text{ NOR } B ) \text{ NOR } ( A \text{ NOR } B )\)
|
|
\end{itemize}
|
|
|
|
Beispiel: Logik-Rätsel Banküberfall
|
|
\begin{itemize}
|
|
\item[a)]
|
|
Es kommen nur drei Personen, Herbert, Klaus und Fritz, in Frage.\\
|
|
\(G_a = H \lor K \lor F\)
|
|
\item[b)]
|
|
Wenn Herbert schuldig und Klaus unschuldig ist, dann ist Fritz schuldig.\\
|
|
\( G_b = (H \land \overline{K}) \rightarrow F \)
|
|
\item[c)]
|
|
Fritz „arbeitet“ niemals alleine.\\
|
|
\( G_c = F \rightarrow (H \lor K ) \)
|
|
\item[d)]
|
|
Herbert arbeitet nie mit Fritz zusammen.\\
|
|
\( G_d = H \rightarrow \overline{F} ( = F \rightarrow \overline{H}) \)
|
|
\end{itemize}
|
|
|
|
\begin{tabular}{ccc|ccccc}
|
|
H&K&F&\(G_a\)&\(G_b\)&\(G_c\)&\(G_d\) & \(G_a \land G_b \land G_c \land G_d\)\\
|
|
\hline
|
|
0&0&0& 0& 1& 1& 1& 0\\
|
|
0&0&1& 1& 1& 0& 1& 0\\
|
|
0&1&0& 1& 1& 1& 1& 1\\
|
|
0&1&1& 1& 1& 1& 1& 1\\
|
|
1&0&0& 1& 0& 1& 1& 0\\
|
|
1&0&1& 1& 1& 1& 0& 0\\
|
|
1&1&0& 1& 1& 1& 1& 1\\
|
|
1&1&1& 1& 1& 1& 0& 0
|
|
\end{tabular}
|
|
|
|
Antwort: Klaus war auf jeden Fall beteiligt.
|
|
|
|
DNF: \( \overline{H} F \overline{K} \lor \overline{H} K F \lor H K \overline{F} \)\\
|
|
KNF: \( (H \lor K \lor F) \land
|
|
(H \lor K \lor \overline{F}) \land
|
|
(\overline{H} \lor K \lor F) \land
|
|
(\overline{H} \lor K \lor \overline{F}) \land
|
|
(\overline{H} \lor \overline{K} \lor \overline{F}) \)
|
|
|
|
\subsection{Die Länge der Normalformen}
|
|
Mit dem Verfahren aus 1.3 erhält man Normalformen, bei denen alle Klauseln jede Variable (negiert oder nicht negiert) enthalten.\\
|
|
Solche Normalformen bezeichnet man als \underline{vollständige} oder \underline{kanonische} DNF, bzw. KNF.
|
|
|
|
Wahrheitstabelle, kanonische DNF und kanonische KNF sind eineindeutige Dartsellung äquivalenter Formeln.\\
|
|
Diese Darstellungen besitzen i.\,a. unterschiedliche Länge. Bei \(n\) Variablen und \(k\) erfüllende Belegungen enthält
|
|
\begin{itemize}
|
|
\item[-] die Wahrheitstabelle \(2^n\) Zeilen
|
|
\item[-] die kanonische DNF \(k\) Klauseln
|
|
\item[-] die kanonische KNF \(2^n - k\) Klauseln.
|
|
\end{itemize}
|
|
|
|
Häufig kann man die Normalformen verkürzen.
|
|
|
|
Beispiel von vorhin:
|
|
|
|
\begin{align*}
|
|
\text{DNF: }&\quad \overline{H} F \overline{K} \lor \overline{H} K F \lor H K \overline{F}\\
|
|
&\equiv \overline{H} F \overline{K} \lor \overline{H} K F \lor \overline{H} K F \lor H K \overline{F}\\
|
|
&\equiv \overline{H} K \underbrace{( \overline{F} \lor F)}_{\equiv1} \lor \underbrace{( \overline{H} \lor H )}_{\equiv1} K \overline{F}\\
|
|
&\equiv \overline{H} K \lor K \overline{F} &\text{(verkürzte DNF)}\\
|
|
&\equiv K ( \overline{H} \lor \overline{F} ) &\text{(verkürzte KNF)}
|
|
\end{align*}
|
|
|
|
Bem.: In manchen Fällen kann die kanonische DNF (oder KNF) nicht mehr verkürzt werden.\\
|
|
Beispiel:\\
|
|
\( F_n := (A_1 \oplus A_2) \land (A_3 \oplus A_4 ) \land ... \land (A_{n-1} plus A_n) \)\\
|
|
\(n\) gerade.\\
|
|
Kann nicht gekürzt werden.\\
|
|
Beweis durch Widerspruch:\\
|
|
Sei \(\hat F_n\) die kanonische DNF von \(F_n\), \(\tilde F_n\) eine verkürzte DNF von \(F_n\)\\
|
|
\( \Rightarrow \) \(\tilde F_n\) enthält eine Klausel K, die nicht alle Variablen enthält. Sei \(A_j\) in K nicht enthalten.
|
|
|
|
Wähle \(A_1, ..., A_n\) so, dass K den Wert 1 annimmt.\\
|
|
( \( \Rightarrow \hat F_n, F_n, \tilde F_n\) sind wahr.)
|
|
|
|
Ändere den Wert von \(A_j\)\\
|
|
Der Wert von K (und \(\tilde F_n\)) ändert sich nicht, aber der Wert von \(F_n\) wird 0.\\
|
|
\( \rightarrow \) Widerspruch!\\
|
|
\( \rightarrow \) \(\tilde F_n\) gibt es nicht.
|
|
|
|
\newpage
|
|
\section{Mengen}
|
|
\subsection{Definition von Mengen}
|
|
|
|
Wir definieren hier eine \underline{Menge} als Zusammenfassung wohldefinierter, unterscheidbarer Objekte.\\
|
|
Ein Objekt \(x\) heißt \underline{Element} der Menge \(M\) (\(x \in M \)), wenn \(x\) in \(M\) enthalten ist.. (anderfalls \(x \not\in M\))
|
|
|
|
Anmerkung: Diese „naive“ Definition von Mengen kann zu Widersprüchen führen. Keine Widersprüche treten auf, wenn man nur Teilmengen einer zuvor Definierten Grundmenge betrachtet.
|
|
|
|
Zwei Mengen \(M,N\) sind gleich, wenn sie dieselben Elemente enthalten:\\
|
|
\hspace*{5mm}\(M=N \Leftrightarrow \) Für alle Objekte \(x\) gilt: \( x \in M\) genau dann, wenn \(x \in N\)
|
|
|
|
Bem.: Insbesondere sind keine Konzepte wie die Häufigkeit der Elemente in einer Menge oder die Reihenfolge der Elemente in einer Menge definiert.\\
|
|
z.\,B.:
|
|
\begin{align*}
|
|
\{1,2,3\} &= \{ 3,2,1\}\\
|
|
&= \{1,2,2,3,3,3\}\\
|
|
|\{1,2,3\}| &= 3
|
|
\end{align*}
|
|
|
|
Die Anzahl der verschiedenen Elemente einer Menge \(M\) heißt die \underline{Mächtigkeit} von M (Abk.: \( |M|\))
|
|
|
|
\subsection{Notation von Mengen}
|
|
|
|
\begin{itemize}
|
|
\item
|
|
Aufzählung (bei endlich vielen Elementen).\\
|
|
\( T_{10} = \{1,2,5,10\} \) (Menge der Teiler von 10)
|
|
\item
|
|
Aufzählung mit Auslassungszeichen:\\
|
|
\( \{ 1,2,...,n\} =: [n]\) (alle natürlichen Zahlen von 1 bis n)
|
|
\item
|
|
Bei unendlichen Mengen:
|
|
\begin{align*}
|
|
\mathbb N := &\{ 0,1,2,...\} &\text{(Menge der natürlichen Zahlen)}\\
|
|
&\{ 1,3,5,7,...\} &\text{(ungerade natürliche Zahlen)}\\
|
|
Q = &\{ 0,2,4,9,16 \} &\text{(Quadratzahlen)}
|
|
\end{align*}
|
|
\item
|
|
ganz allgemein: Angabe einer Eigenschaft:
|
|
\begin{align*}
|
|
Q &= \{ x \in \mathbb N \mid x \text{ ist Quadratzahl} \}\\
|
|
&= \{ x \in \mathbb N \mid \text{ es gibt } y\in \mathbb N: y^2 = x\}\\
|
|
&= \{ x \in \mathbb N \mid \sqrt(x) \in \mathbb N \}\\
|
|
\mathbb Q &= \left\{ \frac{a}{b} \mid a,b \in \mathbb Z \text{ und } b \ne 0 \right\} &\text{(Menge der Natürlichen Zahlen)}
|
|
\end{align*}
|
|
\end{itemize}
|
|
|
|
\subsection{Teilmengen}
|
|
|
|
Enthält \(M\) alle Elemte der Menge \(N\), dann heißt, dann heißt \(N\) \underline{Teilmenge} von \(M\) (\(N \subseteq N\))\\
|
|
\( N \subseteq M \)\\
|
|
und \(M\) \underline{Obermenge} von \(N\).\\
|
|
Wenn \(M\) ein Element enthält, das nicht in \(N\) vorkommt \(N \subseteq, aber N \ne M \), dann heißt \(N\) \underline{echte Teilmenge} von \(M\) ( \( N \subset M, N \subsetneq M \)).
|
|
|
|
Jede Menge hat zwei triviale Teilmengen:
|
|
\begin{align*}
|
|
M &\subseteq M \\
|
|
\emptyset &\subseteq M
|
|
\end{align*}
|
|
Die Teilmengenbeziehung nennt man auch \underline{Inklusion}.\\
|
|
Die Inklusion hat folgende Eigenschaften:
|
|
\begin{enumerate}
|
|
\item
|
|
Reflexivität:\\
|
|
\(M \subseteq M \) für jede Menge \(M\)
|
|
\item
|
|
Transivität:\\
|
|
\( A \subseteq B \text{ und } B \subseteq C \)\\
|
|
\( \Rightarrow A \subseteq C \)
|
|
\item
|
|
Antisymmetrie:\\
|
|
\(A \subseteq B\quad\land\quad B \subseteq A \Leftrightarrow A = B \)
|
|
\end{enumerate}
|
|
Beispiel:\\
|
|
\begin{align*}
|
|
A &:= \{ 2\cdot x \mid x \in \mathbb Z \} \\
|
|
B &:= \{ y+z \mid y+z \in\mathbb Z, y \text{ und } z \text{ ungerade } \}\\
|
|
A &\overset{?}{=} B\\
|
|
A &\overset{!}{=} B\\
|
|
\text{Sei } &2x \in A, x \in \mathbb Z\\
|
|
&\Rightarrow 2x = \underbrace{(2x +1)}_{=y}\underbrace{-1}_{=z} \in B\\
|
|
&\Rightarrow A \subseteq B\\
|
|
B \subseteq A:\\
|
|
\text{Sei } &y+z \in B \text{ y,z ungerade}\\
|
|
y &= 2n +1 \text{ für ein } n \in \mathbb Z\\
|
|
z &= 2n + 1\\
|
|
&\Rightarrow y + 2 = 2 (n+m+1) \text{ ist gerade}\\
|
|
&\Rightarrow y + z \in A, B \subseteq A
|
|
\end{align*}
|
|
Antisymmetrie:\\
|
|
\( \Rightarrow A = B \)
|
|
|
|
Die \underline{Potenzmenge} \(\mathcal P(M)\) einer Menge \(M\) ist die Menge aller Teilmegen von \(M\).
|
|
|
|
Bsp.:\\
|
|
\(\mathcal P(T_q) = \mathcal P(\{1,3,9\})\)\\
|
|
\( = \{ \emptyset, \{1\},\{3\},\{9\},\{1,3\},\{1,9\},\{3,9\},\{1,3,9\} \} \)\\
|
|
\( |\mathcal P(M)| = 2^{|M|} \)
|
|
|
|
\subsection{Operationen auf Mengen}
|
|
|
|
Es seien \(A,B\) zwei beliebige Mengen.
|
|
%TODO% Venn-Diagramme…
|
|
\begin{itemize}
|
|
\item
|
|
Vereinigungsmenge:\\
|
|
\( A \cup B := \{ x \mid x \in A \text{ oder } x \in B \}\)
|
|
\item
|
|
Schnittmenge:\\
|
|
\( A \cap B := \{ x \mid x \in A \text{ und } c \in B \}\)
|
|
\item
|
|
Differenzmenge:\\
|
|
\(A -B := A \backslash B := \{ x \mid x \in A \text{ und } x \not\in B \}\)
|
|
\item
|
|
Symmetrische Differenz:\\
|
|
\(A \triangle B := (A \backslash B) \lor (B \backslash A) \)\\
|
|
\( = \{ x \mid \text{entweder } x \in A \text{ oder } x \in B \} \)
|
|
\end{itemize}
|
|
|
|
\subsection{Rechenregeln}
|
|
(Folgen direkt aus den Regeln für logische Formeln.)
|
|
|
|
\( A \cup B = \{ x \mid x\in A \text{ oder } x \in B \} \underset{(1)}{=} \{ x \mid x\in B \text{ oder } x \in A \} = B \cup A \)\\
|
|
{\small \((1)\) Kummutativgesetz für\( \land \)}
|
|
|
|
\begin{enumerate}
|
|
\item
|
|
\underline{Kommutativgesetz} \((*)\)\\
|
|
\( A \cup B = B \cup A \)\\
|
|
\( A \cap B = B \cup A \)\\
|
|
\( A \triangle B = B \triangle A \)
|
|
\item
|
|
\underline{Assoziotivgesetze} \((*)\)\\
|
|
\(A \cup ( B \cup C ) = ( A \cup B ) \cup C\)\\
|
|
\( A\cap ( B \cap C ) = ( A \cap C ) \cap C \)\\
|
|
\( A\triangle ( B \triangle C ) = ( A \triangle C ) \triangle C \)\\
|
|
\item
|
|
\underline{Distributivgesetze} \((*)\)\\
|
|
\( A \cup ( B \cap C ) = (A \cup B) \cap (A \cup C) \)\\
|
|
\( A \cap ( B \cup C ) = (A \cap B) \cup (A \cap C) \)\\
|
|
\( A \cap ( B \triangle C ) = (A \cap B) \triangle (A \cap C)\)
|
|
\item
|
|
\underline{Doppeltes Komplement}\\
|
|
\( \overline{\overline{A}} = A \)
|
|
\item
|
|
\underline{de Morgansche Gesetze}\\
|
|
\( \overline{ A \cup B } = \overline{A} \cap \overline{B} \)\\
|
|
\( \overline{ A \cap B } = \overline{A} \cup \overline{B} \)\\
|
|
\item
|
|
\underline{weiteres Gesetz mit Komplement}\\
|
|
\( A \triangle B = \overline{A} \triangle \overline{b} \)
|
|
\item
|
|
\underline{Verschmelzungsgesetze} \((*)\)\\
|
|
\(A \cap ( A \cup B ) = A \)\\
|
|
\( A \cup ( A \cap B ) = A \)
|
|
\item
|
|
\underline{Idempotenzgesetze}\\
|
|
\( A \cup A = A \)\\
|
|
\( A \cap A = A \)
|
|
\item
|
|
\underline{Existenz des komplementären Elements} \((*)\)\\
|
|
\( A \cup \overline{A} = M\)\\
|
|
\( A \cap \overline{A} = \emptyset\)
|
|
\item
|
|
\underline{Gesetze für \(M, \emptyset\)}
|
|
\begin{align*}
|
|
A \cup M &= M & A \cup \overbrace{\emptyset}^{1} &= A \\
|
|
A \cap \underbrace{M}_{2} &= A & A \cap \emptyset &= \emptyset
|
|
\end{align*}
|
|
{\small \((1)\) neutrales Element bzgl. \(\cup\)}\\
|
|
{\small \((2)\) neutrales Element bzgl. \(\cap\)}
|
|
\item
|
|
\underline{Kontraposition}\\
|
|
\( A \backslash B = \overline{B} \backslash \overline{A} \)
|
|
\item
|
|
\underline{weitere}\\
|
|
\( A \backslash B = A \cap \overline{B} = \overline{\overline{A} \cup B} \)
|
|
\end{enumerate}
|
|
|
|
\textcolor{darkgreen}{\underline{Def.:}} Sei \(M\) eine beliebige Menge, \( A \subseteq M \).\\
|
|
Dann heißt\\
|
|
\hspace*{4mm} \(\overline{A} = M \backslash A = \{ x \mid x \in M \text{ und }x \not\in A \}\)\\
|
|
das \underline{Komplement} von A bzgl. M.
|
|
|
|
\subsection{Kreuzprodukte}
|
|
Bei vielen Anwendungen hat man mit geordneten Paaren von Objekten zu tun.
|
|
|
|
\underline{Beispiel:} kartesische Koordinaten in der Ebene.
|
|
%TODO% koordinatensystem; punkte: P(sqrt(3),1); Q(1,sqrt(3))
|
|
|
|
Mengen sind ungeeignet zur Darstellung geordneter Paare.\\
|
|
\( \left( \left\{ 1,\sqrt{3} \right\} = \left\{ \sqrt{3},1 \right\} \right) \)
|
|
|
|
\textcolor{darkgreen}{\underline{Definition:}}\\
|
|
Seien A und B beliebige Mengen.\\
|
|
Die Menge:\\
|
|
\vspace*{4mm}\( A \times B := \{(a,b) \mid a \in A \text{ und } b \in B \} \)\\
|
|
der geordneten Paare mit erster Komponente in A und zweiter Komponente in B heißt das \underline{Kreuzprodukt} (oder \underline{kartesische Produkt}) von A und B.
|
|
|
|
Abkürzung: \( A \times A =: A^2\)
|
|
|
|
\underline{Beispiel:}\\
|
|
\begin{itemize}
|
|
\item
|
|
Koordinatenmenge der Eben:\\
|
|
\( \mathbb R \times \mathbb R = \mathbb R^2\)
|
|
\item
|
|
Seien \( [x_{min}; x_{max}] \subset \mathbb R, [y_{min}; y_{max}] \subset \mathbb R \) (mit
|
|
\( x_{min} < x_{max}, y_{min} < y_{max} \)) zwei Intervalle.\\
|
|
\( [x_{min},x_{max}] \times [y_{min}, y_{max}] \)
|
|
\item
|
|
\underline{Polarkoordinaten (in der Ebene)}\\
|
|
\( (r,\phi) \in \mathbb R_{0}^+ \times {[0,2\pi)} \)\\
|
|
\( = \{r', \phi' \mid 0 \le r', 0 \le \phi' <2\pi \} \)
|
|
\end{itemize}
|
|
|
|
Allgemeiner:\\
|
|
Für beliebige Mengen \( A_1, ... A_n \) bezeichnet das n-fache Kreuzprodukt\\
|
|
\hspace*{4mm} \( A_1\times ... \times A_n:= \{ (a_1, a_2, ..., a_n) \mid a_i \in A_i \text{ für } i=1, ... , n \} \)\\
|
|
die Menge aller n-Tupel mit i-ter Komponente in \(A_i \).
|
|
|
|
\underline{Beispiel:} kartesische Koordinaten in 3D:\\
|
|
Koordinaten von P:\\
|
|
\includegraphics{bilder/2-6_koordinatensystem_3d_punkt.pdf}\\
|
|
\( (x_P,Y_P,Z_P) \in \mathbb R \times \mathbb R \times \mathbb R \) \\
|
|
\( (1, \sqrt{3}, 5) \)
|
|
|
|
\underline{Beispiel:} Zylinderkoordinaten\\
|
|
%TODO% Koordinatensystem
|
|
\( (r_P, \phi_P, Z_P) \in \mathbb R_{0}^+ \times {[0,2\pi)} \times \mathbb R \)
|
|
|
|
\( (r, \phi, Z) \in {[0,R]} \times {[0,2\pi)} \times {[0,Z]} ,\quad R,Z \in \mathbb R^+ \)
|
|
%TODO% Zylinder [=,R] x [0,2pi) x [0,Z]
|
|
|
|
\underline{Beispiel:}
|
|
\begin{align*}
|
|
\mathbb B := \{0,1\} &\widehat= 1 \text{ Bit}\\
|
|
\mathbb B^8 = \underbrace{\mathbb B \times ... \times \mathbb B}_{\text{8-mal}} &\widehat= 1\text{ Byte} = 8 \text{ Bit}
|
|
\end{align*}
|
|
\(\mathbb B^n \widehat= \) Menge aller Bitstrings von Länge \(n\).
|
|
|
|
\( \underbrace{\{ \}}_{\text{Leeres Wort}} \cup \mathbb B \cup \mathbb B^2 \cup \mathbb B^3 \cup ...
|
|
=: \bigcup^{\infty}_{i=0} \mathbb B^i \)\\
|
|
\( = B^* \)\\
|
|
( \(B^*\) enthält alle Bitstrings von endlicher Länge)
|
|
|
|
Mit einem Bit lassen sich zwei Zahlen darstellen, mit einem Byte \( \left| \mathbb B^8 \right | = 2^8 = 256 \).
|
|
|
|
Allgemein gilt:\\
|
|
Wenn \(A_1, ... A_n \) endliche Mengen sind, ist \( \left| A_1 \times ... \times A_n \right| = \left| A_1 \right| \cdot ... \cdot \left| A_n \right| \)
|
|
|
|
\newpage
|
|
\section{Relationen}
|
|
\subsection{Relationen}
|
|
Das Kreuzprodukt \( A \times B \) enthält alle Kombinationen von Elementen aus \(A\) mit Elementen aus der Menge \(B\). Häufig ist man nur an einer Teilmenge dieser Kombinationen interessiert.
|
|
|
|
\underline{Beispiel:} Kategorisierung von Objekten, etwa:\\
|
|
\begin{itemize}
|
|
\item Bücher: Autor, Vertrag, Genre, Themengebiet
|
|
\item Online-Shop:\\
|
|
Artikel nach Produkttyp, Hersteller, Preisklasse, Sonderangebote\\[3mm]
|
|
\begin{tabular}{r|cccl}
|
|
Artikel: && Produkttyp: &\\
|
|
\textbf{T} & Bügeleisen & Fernseher & DVD-Player & ...\\
|
|
\hline
|
|
1023 & X\\
|
|
0815 & & X & X\\
|
|
923 & X
|
|
\end{tabular}
|
|
\end{itemize}
|
|
|
|
\textbf{T} \( \subseteq \) Menge aller Artikel \(\times\) Menge aller Produkttypen
|
|
|
|
\textcolor{darkgreen}{\underline{Definition:}} Seien \(A, B\) zwei Mengen, \( R \subseteq A \times B \)\\
|
|
Dann heißt \(R\) eine \underline{Relation zwischen \(A\) und \(B\)}. Falls \(A=B\), d.\,h. \(R \subseteq A^2\), dann heißt \(R\) auch \underline{Relation} auf \(A\)\\
|
|
\((A^2 = A \times A )\)
|
|
|
|
\underline{Beispiel:}\\
|
|
\( T = \{ (1023, \text{ Bügeleisen}), (0815, \text{ Fernseher}), (0815, \text{ DVD-Player}), ... \}\)\\
|
|
Schreibweise: statt \((a,b) \in \mathbb R \) schreibt man häufig \( a\mathbb R b \)
|
|
|
|
Allgemeiner:\\
|
|
Jede Teilmenge \(\mathbb R \le A_1 \times ... \times A_n \) eines n-fachen Kreuzprodukts heißt \underline{n-stellige Relation}.
|
|
|
|
\underline{Beispiel:} Vater-Mutter-Kind-Relation:\\
|
|
\((x,y,z) \in B \Leftrightarrow \) x ist Vater von z und y ist Mutter von z.
|
|
|
|
\underline{Beispiel Online-Shop:}\\
|
|
\( T' \subseteq \) Menge der Artikel \(\times\) Menge der Produkttypen \(\times\) Menge der Preisklassen \(\times\) Menge der Hersteller.
|
|
|
|
Besodners häufig hat man es mit binären Relationen R auf eine endliche Menge A zu tun; solche Relationen ann man auch durch einen \underline{Graphen} darstellen:\\
|
|
\includegraphics{bilder/3-1.pdf}\\
|
|
Graph \(G = (V,E)\)\\
|
|
\(V\): Menge der Knoten („Punkte“, vertices)\\
|
|
\(E\): Menge der Kanten („Pfeile“, edges)\\
|
|
\( R = E \subseteq V \times V = A \times A \)
|
|
|
|
alternative Darstellung von Graphen:\\
|
|
(z.\,B. Algorithmen)
|
|
|
|
\underline{Adjazenzmatrix:}\\
|
|
\( M = \begin{pmatrix}
|
|
1&1&0&0\\
|
|
1&0&1&0\\
|
|
0&0&0&0\\
|
|
0&1&1&0
|
|
\end{pmatrix}\)\\
|
|
Der Eintrag \(M_{ij}\) in Zeile i, Spalte j von M ist 1, wenn es im Graphen eine Kante vom Knoten i zum Knoten j gibt, sonst 0.
|
|
|
|
Die Adjazenzmatrix läßt sich also mit \( |V| ^2\) vielen Bits abspeichern.
|
|
|
|
\textcolor{darkgreen}{\underline{Definition:}}\\
|
|
Sei \( R \subseteq A \times B \) eine binäre Relation.\\
|
|
\(D(R) := \{ a \in A \mid \text{ es gibt ein } b \in B \text{ mit } a R b \} \)\\
|
|
\hspace*{4mm}(\underline{Definitionsbereich} von R)\\
|
|
\( W(R) := \{ b \in B \mid \text{ es gibt ein } a \in A \text{ mit } a R b \} \)\\
|
|
\hspace*{4mm}(\underline{Definitionsbereich} von R)
|
|
|
|
\underline{Obiges Beispiel:}\\
|
|
\(D(R) = \{1,2,5\} \)\\
|
|
\hspace*{4mm}(Zeile 3 ist eine Nullzeile in M)\\
|
|
\(W(R) = \{1,2,3\} \)\\
|
|
\hspace*{4mm}(Spalte 4 in M ist eine Nullspalte)
|
|
|
|
\underline{Einschub: Quantoren}\\
|
|
Sei \(F(x)\) eine Formel, die von einer Variablen \(x\) abhängt.\\
|
|
Wir führen zwei Quantoren, den \underline{Allquantor} \(\forall\) und den \underline{Existenzquantor} \(\exists\) ein:\\
|
|
\( \forall x: F(x)) \) bedeutet „für alle x gilt F(x)“\\
|
|
\( \exists x: F(x) \) bedeutet „es gibt ein x, so dass F(x) gilt“
|
|
|
|
Für eine Formel \( G(x_1,..., x_n) \) definiert man analog:\\
|
|
\(Q_1 x_1 : Q_2 x_2 : ... : Q_n x_n : G(x_1 , ... x_n) \)\\
|
|
wobei die \(Q_i\) jeweils ein Allquantor oder ein Existenzquantor sind.\\
|
|
\underline{Beispiel:} „Es gibt jemanden, der alles versteht.“\\
|
|
entspricht: \( \exists x : \forall y : x \text{ versteht } y\).\\
|
|
Die Reihenfolge der Quantoren ist wichtig:\\
|
|
\( \forall y : \exists x : x \text{ versteht } y \)\\
|
|
„Jede Sache wird von jemandem verstanden.“
|
|
|
|
Negation quantisierter Formeln:\\
|
|
\( \neg \forall x : F(x) \) („nicht für alle \(x\) gilt \(F(x)\))\\
|
|
\( \equiv \exists x : \neg F(x) \) („es gibt ein \(x\), so dass \(F(x)\) nicht gilt.“)\\
|
|
\( \neg \exists x : F(x) \) („es gibt kein \(x\), so dass \(F(x)\) gilt“)\\
|
|
\( \equiv \forall x : \neg F(x) \) („für alle \(x\) gilt \(F(x)\) nicht“)
|
|
|
|
\underline{Beispiel:}\\
|
|
„Niemand versteht alles“\\
|
|
\( \neg \exists x : \forall y : x \text{ versteht } y \)\\
|
|
\( \equiv \forall x : \neg ( \forall y : x \text{ versteht } y) \) („Jeder versteht nicht alles.“)\\
|
|
\( \equiv \forall x : \exists y : \neg ( x \text{ versteht } y )\) („Für jedes x gibt es etwas, was x nicht versteht“)
|
|
|
|
\subsection{Zusammengesetzte Relationen}
|
|
Seien \(R,S\) zwei Relationen \((R \subseteq A \times B, S \subseteq B \times C )\)
|
|
\begin{itemize}
|
|
\item
|
|
Die \underline{Umkehrrelation} \(R^{-1} \subseteq B \times A \) ist definiert als\\
|
|
\(R^{-1} = \{ (a,b) \mid (a,b) \in R \} \)
|
|
\begin{itemize}
|
|
\item Rollen der Zeilen und Spalten vertauscht
|
|
\item für die Matrixeinträge gilt:\\
|
|
\((A_{R^{-1}})_{ij} = (A_R)_{ji} \) für \(i,j = a,...,e\)
|
|
\item \(A_{R^{-1}}\) ist also die Transponierte von \((A_R)^T\) von \(A_R\)
|
|
\item \(A_{R^{-1}}\) geht durch Spiegelung an der Hauptdiagonalen aus \(A_R\) hervor
|
|
\item \( (A_{(R^{-1})^{-1}})_{ij} = (A_{R^{-1}})_{ji}\)\\
|
|
\( \Rightarrow ( A_{(R^{-1})^{-1}} ) = (A_R)_{ij} \)
|
|
\end{itemize}
|
|
\item
|
|
Die \underline{Verkettungsrelation} \( S \circ R \subseteq A \times C \) (S nach R)\\
|
|
ist \( S \circ R := \{ (a,c) \in A \times C \mid \exists v \in B : a R b \land b S c \} \)
|
|
\end{itemize}
|
|
\underline{Beispiel:} Online-Shop:\\
|
|
„Heute 20\% Rabatt auf Tiernahrung und Fernseher.“\\
|
|
\begin{tabular}{c|ccc}
|
|
S & „-20\%“ & „-10\%“ & „\(\pm\)0\% \\
|
|
\hline
|
|
Tiernahrung & X\\
|
|
Fernseher & X\\
|
|
Bügeleisen & & & X
|
|
\end{tabular}\\
|
|
Frage: „Wieviel Rabatt gibt es auf Artikel 0815?“\\
|
|
Lösung:\\
|
|
Betrachte \(S \circ T \)\\
|
|
wir finden: (0815, Fernseher) \( \in T \),\\
|
|
(0815, DVD-Player) \( \in T \),\\
|
|
(Fernseher,„-20\%) \( \in S\)\\
|
|
\( \Rightarrow\) (0815, „-20\%“) \( \in S \circ T \)\\
|
|
(wähle b=Fernseher in der Definition von \(S \circ T\)
|
|
|
|
Beispiel für die Umkehrrelation:\\
|
|
\begin{itemize}
|
|
\item
|
|
Kleiner-gleich-Relation auf \(\mathbb R \):\\
|
|
\( y \leqslant^{-1} x \Leftrightarrow x \leqslant y \Leftrightarrow y \geqslant x\)\\
|
|
\( (y,x) \in \leqslant^{-1} \quad (x,y) \in \leqslant \quad (y,x) \in \geqslant\)\\
|
|
\( \Rightarrow \) Die Umkehrrelation von \( \leqslant \) ist \( \geqslant \).
|
|
\end{itemize}
|
|
|
|
\underline{am Beispiel von Graphen:}\\
|
|
\begin{itemize}
|
|
\item
|
|
\underline{Umkehrrelation:}\\
|
|
Es ändert sich lediglich die Richtung der Pfeile.
|
|
\item
|
|
\underline{Verkettungsrelation:}\\
|
|
\( G^2 = G \circ G := (V, E \circ E) \)\\
|
|
wenn \( G = (V, E )\)
|
|
\end{itemize}
|
|
\includegraphics{bilder/3-2.pdf}
|
|
|
|
\underline{\underline{\textbf{Eigenschaften von Umkehr- und Verkettungsrelationen}}}
|
|
|
|
\textbf{Einschub: Umkehrrelation}
|
|
|
|
\( R \subseteq A \times B , C \subseteq B \times C , R \subseteq B \times A \)\\
|
|
\( b(R^{-1})a \Leftrightarrow aRb\)\\
|
|
\(b \in B, a \in A\)
|
|
|
|
Bsp.:\\
|
|
\( x \le y \Leftrightarrow y \ge x \)\\
|
|
\( \le^{-1} \Leftrightarrow \ge \)
|
|
|
|
Adjezenzmatrix von \(\mathbb R \):
|
|
|
|
\includegraphics[width=6cm]{bilder/3-3_adjezenzmatrix.pdf}
|
|
|
|
\textbf{Einschub Verkettungsrelation:}
|
|
|
|
\( S \circ R \subseteq A \times C, \quad a \in A \quad c \in C \)\\
|
|
\(a(A \circ R)c \Leftrightarrow \exists b \in B: aRb \land bSc\)
|
|
|
|
Eigenschaften:\\
|
|
\begin{itemize}
|
|
\item
|
|
\textcolor{yellow}{\underline{\textcolor{black}{\( (R^{-1})^{-1} = R \subseteq A \times B\)}}} \( : a \in A, b \in B \) beliebig gewählt.\\
|
|
\( a(R^{-1})^{-1}b \Leftrightarrow b(R^{-1})a \Leftrightarrow aRb \)
|
|
\item
|
|
\textcolor{yellow}{\underline{\textcolor{black}{\( (S \circ R)^{-1} = R^{-1} \circ S^{-1} \)}}}\\
|
|
Beweis: siehe Übungsaufgabe
|
|
\end{itemize}
|
|
|
|
\subsection{Die Klassifikation von Relationen}
|
|
|
|
Eine Relation \( R \subseteq A \times A \) kann folgende Eigenschaften besitzen:\\
|
|
\begin{itemize}
|
|
\item Reflexivität: \( \forall a \in A : aRa\,(R) \)
|
|
\item Symmetrie: \( \forall a,b \in A : aRb \leftrightarrow bRa\,(S) \)
|
|
\item Antisymmetrie: \( \forall a,b \in A : aRb \land bRa \rightarrow a=b\,(AS) \)
|
|
\item Transitivität: \( \forall a,b,c \in A : aRb \land bRc \rightarrow aRc\,(TR) \)
|
|
\item Totalität: \( \forall a,b \in A : aRb \lor bRa\,(TO) \)
|
|
\end{itemize}
|
|
|
|
Von besonderer Bedeutung sind folgende Kombinationen dieser Eigenschaften:
|
|
\begin{enumerate}
|
|
\item \(R\) ist eine Äquivalenzrelation, wenn \(R\) die Eigenschaften \((R),(S),(TR)\) besitzt.
|
|
\item \(R\) ist eine Halbordnung, wenn \(R\) die Eigenschaften der \((R),(AS),(TR)\) besitzt.
|
|
\item Eine Halbordnung, für die zusätzlich \((TO)\) gilt, heißt totale Ordnung.
|
|
\end{enumerate}
|
|
|
|
Bsp.:
|
|
\begin{itemize}
|
|
\item
|
|
Die Äquivalenz aussagen logischer Formeln (\(\equiv\)) ist ein Bsp für eine Äquivalenzrelation
|
|
\item
|
|
Definiere \(\cong\) als Relation auf \(\mathbb Z\) als:\\
|
|
\( a \cong b : \Leftrightarrow a,b\) sind beide gerade oder beide Ungerade\\
|
|
\( a \cong a \) (R)\\
|
|
\( a \cong b \land b \cong c \rightarrow a \cong c\,(TR)\)\\
|
|
\( \Rightarrow \cong \) ist eine Äquivalenzrelation
|
|
\item
|
|
Die Kleiner-Gleich-Relation \(\le\) auf \(\mathbb R\) ist eine totale Ordnung:\\
|
|
\begin{align*}
|
|
x &\le x &(R)\\
|
|
x &\le y \land y \le x \rightarrow x = y & (AS)\\
|
|
x &\le y \land y \le z \rightarrow y \le z & (TR)\\
|
|
\text{Es gilt auch immer:}\\
|
|
x &\le y \lor y \le x & (TO)
|
|
\end{align*}
|
|
\item
|
|
Eine Halbordnung, die keine totale Ordnung ist:\\
|
|
Die Inklusion als Relation auf \(\mathcal P(M) \) für eine Menge.\\
|
|
Seien \( A,B,C \in \mathcal P(M) \) (d.\,h. \( A \subseteq M, B \subseteq M, C \subseteq M\))\\
|
|
\begin{align*}
|
|
&\Rightarrow A \subseteq A & (R)\\
|
|
&\Rightarrow A \subseteq B \land B \subseteq A \rightarrow A = B & (AS) \\
|
|
&\Rightarrow A \subseteq B \land B \subseteq C \rightarrow A \subseteq C & (TR)\\
|
|
\end{align*}
|
|
Wenn \( |M| \ge 2 \), dann gibt es \( x \in M, y\in M \text{ mit } x \ne y \)\\
|
|
\( \Rightarrow \{x\} \not\subseteq \{y\} \quad \{y\} \not\subseteq \{x\}\) \\
|
|
\(\Rightarrow \) Die Inklusion ist nicht total, wenn \(M\) als 2 Elemente.
|
|
\end{itemize}
|
|
|
|
Darstellung einer Halbordnung auf einer endlichen Menge Hasse-Diagramm (am Bsp. einer Inklusion auf \(\{1,2,3\}\))
|
|
|
|
\includegraphics[height=5cm]{bilder/3-3_hasse-diagramm.pdf}
|
|
|
|
neue Klasse\\
|
|
\begin{itemize}
|
|
\item zum Hinzufügen in eine Menge: Äquivalenzrelation!
|
|
\item zum Hinzufügen in eine sortierte Datenstruktur Totale Ordnung
|
|
\end{itemize}
|
|
|
|
%% 2010-11-05 %%
|
|
|
|
\subsubsection{Transitive Hülle}
|
|
|
|
Transitivität: \( aRb \land bRc \rightarrow aRc \)\\
|
|
Veranschaulichung an deinem Graphen\\
|
|
\( G:= (V,E):\)
|
|
|
|
\includegraphics[height=4cm]{bilder/3-3_transitive_huelle.pdf}
|
|
|
|
Fragestellung:\\
|
|
Welche Knoten sind von eine gegebenen Knoten aus erreichbar?\\
|
|
\( G^+ := \bigcup\limits^{\infty}_{i=1} G^i = G^1 \cup G^2 \cup G^3 \cup ... \)
|
|
|
|
\underline{transitive Hülle} von G:\\
|
|
Relation R:\\
|
|
\( R^+ := \bigcup\limits^{\infty}_{i=1} R^i = R^1 \cup R^2 \cup R^3 \cup ... \) \\
|
|
\(R^+\) ist die kleinste transitive Relation die \(R\) enthält.
|
|
|
|
reflexiv-transitive Hülle einer Relation R:\\
|
|
\( R^* := R^0 \cup R^+ = \bigcup\limits_{i \in \mathbb N} R^i\)\\
|
|
(Falls R Relation auf der Menge M ist:\\
|
|
\hspace*{4mm}\(R^0 := \{ (x,x) \mid x \in M \} \))\\
|
|
\(R^*\) ist die kleinste Relation, die \(R\) enthält und (R) sowie (TR) erfüllt.
|
|
|
|
\includegraphics[height=4cm]{bilder/3-3_transitive_huelle_2.pdf}
|
|
|
|
Falls R bereits transitiv ist:\\
|
|
\hspace*{4mm}\( R^+ = R \)\\
|
|
(Falls R bereits reflexiv und Transitiv ist:\\
|
|
\hspace*{4mm}\( R^* = R \)
|
|
|
|
\subsubsection{Äquivalenzrelationen, Partitionen, Äquivalenzklassen}
|
|
|
|
Gegeben sei eine beliebige Menge A.\\
|
|
\includegraphics[height=3cm]{bilder/3-3_unterteile.pdf}\\
|
|
Unterteile A in dijunkte Teilmengen \(A_i\) (für alle \(i \ne j: A_i \cap A_j = \emptyset\))\\
|
|
\( \bigcup\limits_i A_i = A\)\\
|
|
Die Teilmengen \(A_i\) bilden also eine \underline{Partition} von A.
|
|
|
|
Dann ist die Relation R:\\
|
|
\hspace*{4mm}\(aRb \Leftrightarrow \exists i: a \in A_i \land b \in A_i\)\\
|
|
eine Äquivalenzrelation auf A.
|
|
|
|
\underline{Beispiele:}\\
|
|
\begin{itemize}
|
|
\item
|
|
Unterteile \(\mathbb Z\) in Teilmengen\\
|
|
\(A_i = \{ x \in \mathbb Z \mid x \text{ hat Rest } i \text{ bei Division durch } n\}\)
|
|
mit \( n \in \mathbb N, n > 0 \).\\
|
|
\includegraphics[height=15mm]{bilder/3-3_zahlenstrahl.pdf}\\
|
|
Äquivalenzrelation:\\
|
|
\(x \equiv y (mod n) \)\\
|
|
(Sprechweise: „x ist kongruent zu y modulo n“)
|
|
\(x \equiv y (mod n) \) genau dann, wenn \( \underbrace{x \text{ mod } n}_{=\text{ Divisionsrest}} = y \text{ mod } n \)
|
|
|
|
\item
|
|
Rundung reeller Zahlen \((A = \mathbb R)\):\\
|
|
\( A_i := \{ x \in \mathbb R \mid x \in {(i-\frac{1}{2} , i+\frac{1}{2} ]} \} \)\\
|
|
%% Zahlenstrahl
|
|
x und y sind also äquivalent genau dann, wenn x und y auf dieselbe ganze Zahl gerundet werden.
|
|
\end{itemize}
|
|
|
|
umgekehrt:\\
|
|
Es sei R eine Äquivalenzrelation auf einer Menge M. Für \(x \in M\) ist\\
|
|
\hspace*{4mm}\([x]_R := \{y \in M \mid xRy \} \)\\
|
|
die \underline{Äquivalenzklasse} von x bzgl. R.
|
|
|
|
Der „Quotient“\\
|
|
\hspace*{4mm}\( M / R := \{ [x]_R \mid x \in M \} \)
|
|
|
|
Behauptung:\\
|
|
Die Äquivalenzklassen von R bilder eine Partition von M.\\
|
|
Beweis:\\
|
|
\begin{itemize}
|
|
\item
|
|
Die Äquivalenzklassen überdecken M:\\
|
|
Sei \( x \in M \) beliebig.\\
|
|
Dann ist \( x \in [x]_R\), denn:\\
|
|
\( xRx \) (folgt aus (R))\\
|
|
\(\Rightarrow \bigcup\limits_{x \in M} [x]_R = M \)
|
|
\item
|
|
Verschiedene Äquivalenzklassen sind disjunkt:\\
|
|
Sei \([x]_R \ne [y]_R \),\\
|
|
Annahme: \( [x]_R \cap [y]_R \ne \emptyset \)\\
|
|
Dann gibt es ein \( c \in [x]_R \cap [y]_R\).\\
|
|
Wähle \( z \in [x]_R\), zeige: \( z \in [y]_R\):\\
|
|
\( xRz \land xRc \underset{(S)}{\Rightarrow} cRx \land xRz \underset{(TR)}{\Rightarrow} cRz, yRc \underset{(TR)}{\Rightarrow} yRz \Leftrightarrow z \in [y]_R\)\\
|
|
also: \( [x]_R \subseteq [y]_R, [y]_R \subseteq [x]_R \rightarrow [x]_R = [y]_R \) Widerspruch!!
|
|
\end{itemize}
|
|
|
|
Sei G der Graph einer reflexiv-transitiven Relation R.\\
|
|
R ist eine Halbordnung \( \leftrightarrow \) G enthält keine Kreise.
|
|
|
|
\includegraphics[height=2cm]{bilder/kreis_5ele.pdf}\\
|
|
(G enthält einen Kreis \( \Leftrightarrow \) R ist keine Halbordnung.
|
|
|
|
\(\overset{\text{Beweis}}{\Leftarrow}\) (R),(TR) gelten laut Voraussetzung.\\
|
|
\( \rightarrow \) (AS) ist Verletzt.
|
|
|
|
\( \Rightarrow \exists x,y : xRy \land yRx\)
|
|
|
|
in G: \includegraphics[height=1cm]{bilder/kreis_2ele.pdf}\\
|
|
|
|
\( \Rightarrow \) Sei %%TODO x1,x2,...,xn
|
|
ein Kreis in G.
|
|
|
|
\( \Rightarrow x_{1}Rx_{2}, x_{2}Rx_{3}, ..., x_{n-1}Rx_{n}, x_{n}Rx_{1} \)\\
|
|
\( \Rightarrow x_{1}Rx_{n}, x_{n}Rx_{1} \)\\
|
|
\( \quad x_1 \ne x_n \rightarrow \) (AS) ist verletzt.
|
|
|
|
Einbettung einer Halbordnung in eine totale Ordnung.
|
|
|
|
Algorithmus:
|
|
\begin{enumerate}
|
|
\item Wähle ein minimales x (d.\,h. \(\neg \exists y : y \le x \))\\
|
|
(im zugehörigen Graphen führt also keine Kante zu x.)
|
|
\item Setze \( x_1 := x \), entferne x aus dem Graphen, ebenso alle Kanten von x.
|
|
\item Fahre bei 1. fort und wähle nacheinander \( x_1,x_2,...,x_n \) bis der Graph leer ist.
|
|
\end{enumerate}
|
|
\( \Rightarrow \) Definiere:\\
|
|
\hspace*{4mm} \( x_1 \le x_2 \le ... \le x_n \)
|
|
|
|
Beispiel:\\
|
|
\(\subseteq \) auf der Menge \( \mathcal P(\{1,2\}) \)\\
|
|
\begin{multicols}{2}
|
|
\( x_1 := \{\} \)\\
|
|
\( x_2 := \{2\} \)\\
|
|
\( x_3 := \{1\} \)\\
|
|
\( x_4 := \{1,2\} \)\\
|
|
\columnbreak\\
|
|
\includegraphics[height=4cm]{bilder/3-3_bsp.pdf}
|
|
\end{multicols}
|
|
|
|
\( \Rightarrow \)Gefundene totale Ordnung.\\
|
|
\( \{\} \le \{2\} \le \{1\} \le \{1,2\} \)
|
|
|
|
\newpage
|
|
\section{Funktionen}
|
|
|
|
Sei R eine Relation zwischen A und B. R heißt \underline{eindeutig}, wenn es zu jedem \( a \in A \) höchstens ein \(b \in B\) gibt, so dass \(aRb\). Eine eindeutige Relation \( R \subseteq A \times B \) heißt \underline{Funktion} oder \underline{Abbildung}, wenn \(D(R) = A\)
|
|
|
|
Veranschaulichung:\\
|
|
\includegraphics[height=3cm]{bilder/4-0_ver1.pdf}\\
|
|
eindeutige Relation\\
|
|
\includegraphics[height=3cm]{bilder/4-0_ver2.pdf}\\
|
|
Funktion\\
|
|
|
|
Schreibweise:\\
|
|
\( f\colon A \to B \) „d ist eine Funktion von A nach B“\\
|
|
\( f\colon a \to b \) oder \( f(a) = b \)\\
|
|
„f bildet a auf b ab.“\\
|
|
„Der Funktionswert von f an der Stelle a ist b.“\\
|
|
(„a und b stehen in Relation bzgl. f.“)
|
|
|
|
\underline{Frage:} „Wann ist die Umkehrrelation von f wieder eine Funktion?“
|
|
\begin{itemize}
|
|
\item \(f^{-1} \) muss eindeutig sein, d.\,h.\\
|
|
\( \forall b \in B: \exists \) höchstens ein \(a \in A : f(a) = b\)
|
|
oder gleichbedeutend:\\
|
|
\(\forall a_1,a_2 \in A \text{ mit } a_1 \ne a_2 \)\\
|
|
\( \Rightarrow f(a_1) \ne f(a_2) \)\\
|
|
Funktionen mit dieser Eigenschaft heißen \underline{injektiv}.
|
|
\item Es muss gelten:\\
|
|
\(D(f^{-1}) = B\).\\
|
|
\(D(f^{-1}) = W(F)\)\\
|
|
\(f\colon Y \to X \)\\
|
|
\(\forall y \in Y \exists x \in X : f(x)=y\)\\
|
|
Funktionen mit dieser Eigenschaft heißen \underline{surjektiv}.
|
|
\end{itemize}
|
|
Also \(f^{-1}\) ist eine Funktion (von B nach A), wenn \(f\) injektiv und surjektiv ist. (Dann heißt \(f\) \underline{bijektiv}.)
|
|
|
|
Beispiele:\\
|
|
\begin{itemize}
|
|
\item[a)] \(f(x) := 2x \) ist surjektiv auf \( \mathbb Q\), aber nicht auf \(\mathbb Z \) und injektiv auf \(\mathbb Q \) und auf \(\mathbb Z\).
|
|
\item[b)] \(f(x) := x^2\) ist nicht surjektiv auf \(\mathbb N\), ist injektiv auf \(\mathbb N \)
|
|
\end{itemize}
|
|
|
|
\textcolor{darkgreen}{\underline{Definition:}} Zwei Mengen A,B heißen \underline{gleichmächtig}, wenn es eine bijektion zwischen A und B gibt.\\
|
|
\underline{Bem.:} Eine Menge A ist endlich, wenn es ein \( n \in \mathbb N \) gibt mit\\
|
|
\hspace*{4mm}\( A \sim [n] \).\\
|
|
(Dann hat A die Mächtigkeit n.)
|
|
|
|
A ist unendlich, wenn A nicht endlich ist.\\
|
|
\textcolor{darkgreen}{\underline{Definition:}}\\
|
|
A heißt \underline{abzählbar unendlich}, wenn \( A \sim \mathbb N\).\\
|
|
A heißt \underline{überabzählbar unendlich}, wenn A unendlich, aber nicht abzählbar unendlich ist.
|
|
|
|
Beispiele:
|
|
\begin{itemize}
|
|
\item \(\mathbb N \backslash \{0\} \)\\
|
|
Bijektion\(f\colon \mathbb N \to \mathbb N \backslash \{0\} , f(x) := x+1 \)\\
|
|
\(f\) ist injektiv: seien \(x,y \in \mathbb N, x \ne y \)\\
|
|
\( f(x) = x+1 , f(y) = y+1\)\\
|
|
\( x \ne y \)\\
|
|
\(x+1 \ne y+1\)\\
|
|
also: \( f(x) \ne f(y) \)\\
|
|
f ist surjektiv:\\
|
|
Sei \( z \in \mathbb N \backslash \{0\} \) beliebig:\\
|
|
Wähle \( x := z-1 \in \mathbb N \)\\
|
|
\( \rightarrow f(x) = z \)\\
|
|
d.\,h. \(W(f) = \mathbb N \backslash \{0\} \).
|
|
\item \(\mathbb Z \) ist auch abzählbar unendlich:\\
|
|
Nummerierung:\\
|
|
\( 5 3 1 0 2 4 6 \)\\
|
|
Bijetkion: \( f\colon \mathbb N \to \mathbb Z, f(x) := (-1)^x \lceil \frac{x}{2} \rceil \)
|
|
\item \(\mathbb Q\) ist abzählbar:\\
|
|
\(\mathbb Q \sim \mathbb Z^2 \sim \mathbb N^2 \)
|
|
\item allgemeiner:\\
|
|
Es seien \(A_n, n\in \mathbb N\), abzählbar unendliche Mengen. Dann ist auch\\
|
|
\( \bigcup\limits_{n \in \mathbb N} A_n\) abzählbar.
|
|
|
|
Konstruiere eine Bijektion\\
|
|
\( f\colon \mathbb N \to \bigcup\limits_{n \in \mathbb N} A_n\)\\
|
|
\hspace*{4mm}\(a_n\) ist abzählbar unendlich\\
|
|
\(\rightarrow\) es gibt eine Bijektion\\
|
|
\hspace*{4mm}\(g_{n}\colon \mathbb N \to A_N \)
|
|
|
|
Definiere \(f\):
|
|
\begin{align*}
|
|
f(0) &:= g_{0}(0) & f(4) &:= g_{1}(1)\\
|
|
f(1) &:= g_{0}(1) & f(5) &:= g_{2}(0)\\
|
|
f(2) &:= g_{1}(0) & f(6) &:= g_{0}(3)\\
|
|
f(3) &:= g_{0}(2)
|
|
\end{align*}
|
|
|
|
Falls einer der \(g_{i}(j)\) schon vorher in dieser Liste auftaucht, wird es übersprungen.
|
|
\item \(\mathbb R\) ist überabzählbar unendlich\\
|
|
Widerspruchsbeweis mit Diagonalargument:\\
|
|
Annahme: \(\mathbb R\) ist abzählbar unendlich (offensichtlich: \(\mathbb R\) ist nicht endlich)\\
|
|
\(\rightarrow\) es gibt eine Bijektion\\
|
|
\hspace*{4mm} \(r\colon \mathbb N \to \mathbb R\)\\
|
|
Wir zeigen: \( \exists c \in \mathbb R : c \not\in W(r)\)\\
|
|
Konstruiere c:\\
|
|
Es sei \(R_{i}(n)\) die i-te Nachkommastelle von \(r(n)\);\\
|
|
setze \(c := c_0,c_1 c_2 c_3 c_4 ...\) (c = Dezimalziffer)\\
|
|
wobei \(c_0 \ne r_{0}(0), c_1 \ne r_{1}(1), c_2 \ne r_{2}(2) \)\\
|
|
allgemein: \(c_n \ne r_{n}(n) \)\\
|
|
\(\Rightarrow c \ne r(0), c \ne r(1), c \ne r(2) \)\\
|
|
\(\forall n \in \mathbb N : c \ne r(n) \)\\
|
|
weil c und \(r(n)\) sich in der n-ten Nachkommastelle underscheiden.\\
|
|
\(\Rightarrow c \not\in W(r) \text{ aber } c \in \mathbb R \)\\
|
|
\hspace*{2mm}\(\Rightarrow \) r ist keine Bijektion\\
|
|
\hspace*{4mm}\( \rightarrow \mathbb R \not\sim \mathbb N\)
|
|
\item ähnlich:\\
|
|
\(\mathcal P(\mathbb N) \not\sim \mathbb N \) (s. Übungsaufgabe)
|
|
\end{itemize}
|
|
|
|
\subsection{Permutation}
|
|
|
|
Zufallsexperiment:\\
|
|
n Kugeln mit Nummern \(1,...,n\);\\
|
|
ziehe Kugeln ohne zurücklegen, beachte die Reihenfolge:\\
|
|
\begin{tabular}{c|c|c|c|c|c}
|
|
n & 1 & 2 & 3 &4 & 5\\ \hline
|
|
\(f(n)\) & 2 & 3 & 5 & 4 & 1
|
|
\end{tabular}\\
|
|
(mögliches Ergebnis für \(n=5\))
|
|
|
|
\(\rightarrow\) \(f\) ist eine Bijektion.\\
|
|
Eine Bijektion auf einer endlichen Menge heißt \underline{Permutation}.\\
|
|
Die Menge aller Permutationen auf \([n] =: S_n\)
|
|
|
|
Algorithmus zum Erzeugen aller Permutationen auf \([n]\):
|
|
\begin{itemize}
|
|
\item Interpretiere die Permutationen als Zahlen
|
|
\item generiere alle Permutationen „der Größe nach“ geordnet
|
|
\begin{enumerate}
|
|
\item 12345 (id = „Identität“)
|
|
\end{enumerate}
|
|
nächst größere Zahl (von 23541 aus):\\
|
|
\hspace*{3mm} \(a := 2 \underbrace{3}_{j} 5 4 1\)\\
|
|
\hspace*{3mm} \(b := 2 4 1 3 5\)\\
|
|
\end{itemize}
|
|
|
|
\underline{Graphen zu Permutationen}
|
|
\begin{align*}
|
|
n & 1\,2\,3\,4\,5 & n 1\,2\,3\,4\,5\\
|
|
\sigma(n) & 2\,3\,5\,4\,1 & id(n) & 1\,2\,3\,4\,5
|
|
\end{align*}
|
|
|
|
\includegraphics[height=3cm]{bilder/4-1_permut.pdf}
|
|
|
|
Allgemein gilt: Jeder Knoten besitzt genau einen Nachfolger und genau einen Vorgänger.\\
|
|
\(\rightarrow\) Der Graph besteht aus unzusammenhängenden Kreisen, d.\,h. jeder Knoten ist in genau einem Kreis enthalten.
|
|
|
|
Zyklenschreibweise:\\
|
|
\((1\,2\,3\,5) (4) \)\\
|
|
Letzteres wird oft weggelassen.
|
|
|
|
\( \sigma := (1\,2\,3\,5) (4) \)\\
|
|
\( \tau := (1\,2\,4) (3\,5)\)\\[2mm]
|
|
\( \sigma \circ \sigma = (1 \, 3) (2\,5) (5)\) \\
|
|
\( \sigma \circ \tau = (1\,3) (2\,4) (5) \)\\[2mm]
|
|
\(\sigma^{-1} = (5\,3\,2\,1) (4) = (1 \, 5 \, 3 \,2 ) (4)\)\\[2mm]
|
|
\(\sigma^{-1} \circ \sigma = (1) (2) (3) (4) (5) = \) id
|
|
|
|
\newpage
|
|
\section{Vollständige Induktion}
|
|
|
|
\subsection{Einführung des Beweisverfahrens}
|
|
|
|
\( 1+2+...+100 = ? \)\\
|
|
\begin{tabular}{ccccc}
|
|
1&2&...&50 &\\
|
|
+100&99&...&51&\\\hline
|
|
101+ & 101+ &...+& 101 &= \(50 \cdot 101 = \frac{100 \cdot (100+1)}{2}\)
|
|
\end{tabular}
|
|
|
|
allgemeiner Beweis mit vollständiger Induktion: \( \sum\limits_{k=1}^{n} k \overset{!}{=} \frac{n \cdot ( n+1)}{2} \)\\
|
|
Induktionsanfang: \(n=1\)\\
|
|
\( \sum\limits_{k=1}^{1} k = 1 = \frac{1 \cdot 2}{2} \quad \checkmark\)\\
|
|
Induktionsschritt:\\
|
|
Zeige die Behauptung „für n+1“, unter der Vorraussetzung, dass sie „für n“ gilt.\\
|
|
\( \sum\limits_{k=1}^{n+1} k = \sum\limits_{k=1}^{n} k + (n+1)\)\\
|
|
\( \sum\limits_{k=1}^{n+1} k \overset{!}{=} \frac{(n+1)(n+2)}{2} \)\\
|
|
\( \underset{\text{Induktionsvorraussetung}}{=} \frac{n\cdot (n+1)}{2} + (n+1) = \frac{(n+1)(n+2)}{2}\)
|
|
|
|
Allgemeine Struktur eines Beweises mit \underline{vollständiger} Induktion:\\
|
|
Wir möchten alle Aussagen \(A_i, i \in \mathbb N\), beweisen. Das funktioniert (u.\,U.) mit diesen zwei Schritten:
|
|
\begin{enumerate}
|
|
\item
|
|
Induktionsanfang:\\
|
|
Beweise \(A_0\)
|
|
\item
|
|
Induktionsschritt:\\
|
|
Beweise \(A_{n+1}\) (für beliebiges \(N \in \mathbb N\)\\
|
|
unter der sog. Induktionsvorraussetzung, dass \(A_n\) gilt.
|
|
|
|
\(A_0 \land (A_0 \rightarrow A_1) \land (A_1 \rightarrow A_2) \land (A_2 \rightarrow A_3) \)\\
|
|
\( \Rightarrow A_0 \land A_1\)
|
|
\end{enumerate}
|
|
|
|
\underline{Geometrische Reihe}
|
|
|
|
wenn der Summationsindex im Exponenten steht:\\
|
|
\( \sum\limits_{i=0}^{n} q^i , \text{ mit } q \in \mathbb R \)\\
|
|
\( q \sum\limits_{i=0}^{n} q^i = \sum\limits_{i=0}^{n} q^{i+1} = \sum\limits_{j=1}^{n+1} q^j = \sum\limits_{i=0}^{n} + q^{n+1} - 1\)
|
|
\begin{align*}
|
|
(q-1) \sum\limits_{i=0}^{n} q^i &= q^{n+1} - 1 &\mid :(q-1) \text{ falls } q\ne 1\\
|
|
\sum\limits_{i=0}^{n} q^i &= \frac{q^{n+1} - 1}{1-q} \\
|
|
\sum\limits_{i=0}^{n} q^i &= \frac{1-q^{n+1}}{1-q}
|
|
\end{align*}
|
|
\underline{Bemerkung:}
|
|
|
|
Für \(q \in \mathbb Z\) ist also \(1-q^{n+1}\) teilbar duch \(1-q\).
|
|
|
|
Beispiel:
|
|
\begin{itemize}
|
|
\item \( 12^{17} -1 \) ist teilbar duch 11.
|
|
\item \( 2^{24} - 1 = (2^3)^8 -1 = 8^8 - 1 \) ist durch 7 teilbar.
|
|
\end{itemize}
|
|
|
|
\(q = 1\):\\
|
|
\( \sum\limits_{i=0}{n} q^i = \sum\limits_{i=0}^{n} = n+1\).
|
|
|
|
alternativ: Beweis mit vollständiger Induktion (für \(q\ne 0\))\\
|
|
IA: \(n=0\),\\
|
|
\(\sum\limits_{i=0}^{0} q^i = 1 = \frac{1-q^{0+1}}{1-q}\)
|
|
|
|
IS: \( \sum\limits_{i=0}{n+1} q^i = \sum\limits_{i=0}^{n} q^i + q^{n+1} \)\\
|
|
\( \underset{\text{I.V.}}{=} \frac{1-q^{n+1}}{1-q} + \frac{q^{n+1}-q^{n+2}}{1-q}\)
|
|
|
|
\(\sum\limits_{k=0}^{n} q^k = \frac{1-q^{n+1}}{1-q}\)\\
|
|
kleine Verallgemeinerung:\\
|
|
\( \sum\limits_{k=0}^{n} p^{n-k} \cdot q^k = \sum\limits_{k=0}^{n} \frac{p^n}{p^k} \cdot q^k\)\\
|
|
%TODO% \( = p^n \frac{(1-(\frac{p}{q})^{n+1}) \cdot p\)\\
|
|
\( = \frac{ p{n+1} - q^{n+1} }{ p-q} \)
|
|
|
|
Folgerung falls \(p,q \in \mathbb Z\), ist \\
|
|
\( p^{n+1} - q^{n+1} \) teilbar durch p-q.\\
|
|
z.B. \(12^100 - 5^100 \) ist teilbar duch 7.
|
|
|
|
\underline{Einschub: Summen und Produkte}
|
|
|
|
\begin{enumerate}
|
|
\item Definition (rekursiv):\\
|
|
\( \sum\limits_{k=1}^{0} a_k := 0\) „leere Summe“ \\
|
|
\( \prod\limits_{k=1}{0} a_k := 1\) „leeres Produkt“
|
|
|
|
\( \sum\limits_{k=1}{n+1} a_k := \sum\limits_{k=1}{n} a_k + a_{n+1}\)\\
|
|
\( \prod\limits_{k=1}{n+1} a_k :=a_{n+1} \prod\limits_{k=1}{n} a_k \)
|
|
|
|
\item \underline{Präzendent der Operatoren}\\
|
|
\( \sum\limits_{k=1}^{n} a_k = \left( \sum\limits_{k=1}^{n} a_k \right) + b \)\\
|
|
\( \sum\limits_{k=1}^{n} a_k \cdot b = \sum\limits_{k=1}^{n}\left( a_k \cdot b \right)\)\\
|
|
\( \prod\limits_{k=1}^{n} a_k + b = \left( \prod\limits_{k=1}^{n} a_k \right) +b \)\\
|
|
\( \prod\limits_{k=1}^{n} a_k \cdot b = \left( \prod\limits_{k=1}^{n} a_k \right) \cdot b \)
|
|
|
|
\( \sum \) bindet geringfügig stärker als „+“ und „-“\\
|
|
\( \prod \) bindet geringfügig stärker als „\(\cdot\)“
|
|
|
|
\item \underline{konstante Faktoren}\\
|
|
\( \sum\limits_{k=1}^{n} a_k \cdot c = c \cdot \sum\limits_{k=1}^{n} a_k \)\\
|
|
\( a_1 \cdot c + a_2 \cdot c + ... = c \cdot ( a_1 + a_2 + ...) \)\\
|
|
\( \prod\limits_{k=1}^{n} \left( a_k \cdot c \right) = c^n \cdot \prod\limits_{k=1}^{n} a_k \)
|
|
|
|
\item \underline{Aufspaltung}\\
|
|
\( \sum\limits_{k=1}^{n} a_k = \sum\limits_{k=1}^{l} a_k + \sum\limits_{k=l+1}^{n} a_k \)\\
|
|
mit \( l \in \{ 1 , ..., n \} \)\\
|
|
\( \prod\limits_{k=1}^{n} a_k = \prod\limits_{k=1}^{l} a_k \cdot \prod\limits_{k=l+1}^{n} a_k \)\\
|
|
\( \sum\limits_{k=1}^{n} ( a_k + b_k ) = \sum\limits_{k=1}^{n} a_k + \sum\limits_{k=1}^{n} b_k \)\\
|
|
\( \prod\limits_{k=1}^{n} ( a_k + b_k ) = \prod\limits_{k=1}^{n} a_k \cdot \prod\limits_{k=1}^{n} b_k \)
|
|
|
|
\item \underline{Umnummerierung}\\
|
|
\( \sum\limits_{k=1}^{n} a_k = \sum\limits_{k=1}^{n} a_{\sigma(k)} \)\\
|
|
\( \prod\limits_{k=1}^{n} a_k = \prod\limits_{k=1}^{n} a_{\sigma(k)} \)\\
|
|
mit einer Permutation \( \sigma \in S_n\)
|
|
|
|
\item \underline{Mehrfachsummen/-produkte}\\
|
|
\( \sum\limits_{k=1}^{m}\sum\limits_{l=1}^{n} a_{k l} = \sum\limits_{l=1}^{n}\sum\limits_{j=1}^{m} a_{k l} \)\\
|
|
\( \prod\limits_{k=1}^{m}\prod\limits_{l=1}^{n} a_{k l} = \prod\limits_{l=1}^{n}\prod\limits_{j=1}^{m} a_{k l} \)\\
|
|
|
|
\end{enumerate}
|
|
|
|
\subsubsection{Die Türme von Hanoi}
|
|
|
|
Aufgabe: Bringe $n$ Scheiben von A nach C, so dass jederzeit keine Scheibe auf einer kleineren Scheibe liegt.
|
|
|
|
Lösung: Bringe $n-1$ Scheiben von A nach B; lege anschließend Scheibe $n$ von A nach B. Bringe zuletzt die $n-1$ Scheiben von B nach C.
|
|
|
|
Die minimale Anzahl an Operationen um das Problem zu lösen, sei $T_n$
|
|
|
|
\( T_n = T_{n - 1} + 1 + T_{n -1} = 2 T_{n-1} + 1 \)\\
|
|
\( T_1 = 1 \)
|
|
|
|
\begin{tabular}{l|ccccc}
|
|
n & 1 & 2 & 3 & 4 & 5 \\
|
|
\hline
|
|
$T_n$ & 1 & 3 & 7 & 15 & 31
|
|
\end{tabular}\\
|
|
\( T_n \overset{\text{?}}{=} 2^n - 1 \) Beweis
|
|
|
|
Beweis von $2^n - 1$
|
|
|
|
\textbf{IA:} n = 1\\
|
|
\( T_1 = 1 = 2^1 - 1\)
|
|
|
|
\textbf{IS}\\
|
|
\begin{align*}
|
|
T_{n+1} &= 2 \cdot T_n + 1\\
|
|
&\underset{\text{IV}}{=} 2 \cdot (2^n - 1) +1\\
|
|
&=2^{n+1} - 1 & \text{q.e.d.}
|
|
\end{align*}
|
|
|
|
Wenn sie für $n$ gilt, sollte sie auch für $n+1$ gelten, ziel der Vollständigen Induktion.
|
|
|
|
\subsection{Anwendung: Analyse von Algorithmen}
|
|
|
|
Dec2Bin(n)
|
|
\begin{enumerate}
|
|
\item k = 0
|
|
\item while \(n > 0\) do
|
|
\item \hspace*{3mm}b[k] = n mod 2
|
|
\item \hspace*{3mm}n = \(\lfloor n/n \rfloor\)
|
|
\item \hspace*{3mm}k = k + 1
|
|
\item return b
|
|
\end{enumerate}
|
|
|
|
Bei erreichen von Zeile 2 gilt jedesmal die Invariante\\
|
|
\( m = 2^k \cdot n + \sum_{j=0}^{k-1} b[j] \cdot 2^j \quad (*)\)
|
|
|
|
Bei verlassen der Schleife (n=0) ist \( m = \sum_{j=0}^{k-1} b[j] \cdot 2^j\).\\
|
|
Also enthält b die Binärziffern von m.
|
|
|
|
Beweis von \((*)\) mit vollständiger Induktion:
|
|
|
|
\textbf{IA:} (vor dem ersten Schleifendurchlauf)\\
|
|
\(m=nm k=0 \Rightarrow 2^k \cdot n + \sum_{j=0}^{k-1} b[j] \cdot 2^j = n+0 = m \)
|
|
|
|
\textbf{IS:} \((*)\) gelte vor einem Schleifendurchlauf (I.V.)\\
|
|
Nach dem Durchlauf:\\
|
|
\( k' = k+1, n' = \lfloor n/2 \rfloor\)\\
|
|
\(2^{k+1} \lfloor n/2 \rfloor + \sum_{j=0}^{k} b[j] \cdot 2^j \)\\
|
|
\( \underset{\text{i.V.}}{=} 2^{k+1} \cdot \lfloor n/2 \rfloor + (m - 2^k \cdot n) + \underbrace{b[k]}_{n \mod 2} \cdot 2^k \)\\
|
|
\( = m + 2^k ( 2\cdot \lfloor n/2 \rfloor + n \mod 2 - n) \)
|
|
|
|
Der Wert der Klammer is 0:\\
|
|
\( n = c \cdot \lfloor n/c \rfloor + n \mod c \) für beliebiges \( c \in \mathbb N, c > 0\)
|
|
|
|
denn der Devisionsrest ist definiert als \( n \mod c := n -c \cdot \lfloor n/c \rfloor\)\\
|
|
\( \rightarrow 2^{k'} \cdot n' + \sum_{j=0}^{k'-1} b[j] \cdot 2^j = m \) q.e.d
|
|
|
|
\underline{Laufzeitabschätzung:}\\
|
|
Es sei T(n) die Anzahl der Schleifendurchläufe bei Eingabe n.\\
|
|
\( T(1) = 1\)\\
|
|
\( T(n) = 1 + T( \lfloor n/2 \rfloor ) \)\\
|
|
Das ist eine Rekursionsgleichung ähnlich wie bei Aufgabe 5.4\\
|
|
\( \Rightarrow T(n) = \lfloor \log_2 n \rfloor + 1 \)
|
|
|
|
\underline{Schnelle Exponentation}
|
|
|
|
berechne \( a^n = \underbrace{a \cdot ... \cdot a}_{\text{n-mal}} \) -> Aufwand O(n).
|
|
|
|
mit einem Aufwand von O(log n)
|
|
|
|
In Zeile 3 gilt die Invariante:\\
|
|
\( d = a^{(b_{k-1} ... b_{i+1})_2} \)\\
|
|
am Ende: \( i=-1, d=a^{b_{k-1} ...b_0} = a^n \)
|
|
|
|
\textbf{IA:} (vor dem ersten Durchlauf)\\
|
|
\( 1 = d, i = k-1\)\\
|
|
\( \Rightarrow a ^{(b_{k-1} ... b_{i+1})_2} \)\\
|
|
\( = a^{()_z} = a^0 = ^ = d\) q.e.d
|
|
|
|
\textbf{IS:} Werte nach dem schleifen Durchlauf:\\
|
|
\(i' = i-1 \)\\
|
|
Fall 1: \(b_i = 0\)\\
|
|
\(d' = d \cdot d = [a ^{(b_{k-1} ... b_{i+1})_2}] ^ 2 \)\\
|
|
\( = a^{(b_{k-1} ... b_{i+1})_2 + (b_{k-1} ... b_{i+1})_2 } \)
|
|
\( = a ^ {(b_{k-1} ... b_{i+1} 0)_2} \)\\
|
|
\( = a^{(b_{k-1} ... b_{i})_2}\)\\
|
|
\( = a ^ {(b_{k-1} ... b_{i'+1})_2} \)
|
|
|
|
\(a^n\)\\
|
|
Invariante in Zeile 3:\\
|
|
\( d = a^{(b_{m-1} ... b_{i+1})_2}\)\\
|
|
Fall 2: \( b_i = 1 \)\\
|
|
nach der Ausführung des Schleifendurchlaufs:\\
|
|
\( i' = i-1\)\\
|
|
\( d' = d^2 \cdot a \underset{\text{i.V.}}{=} a^{2 \cdot (b_{k-1} ... b_{i+1})_2 + 1} \)\\
|
|
\( = a ^ {(b_{k-1} ... b_{i+1} 1)_2}\)\\
|
|
\( = a ^ {(b_{k-1} ... b_{i'+1})_2}\) \\
|
|
q.e.d.
|
|
|
|
\subsection{Anwendungen in der Graphentheorie}
|
|
|
|
In diesem Abschnitt ist stets \( G = (V,E) \) ein ungerichteter Graph ohne Schleifen, über der Knotenmenge \( V := [n] \text{ mit } |E| =: e \) vielen Kanten. Bei Ungerichteten Graphen:\\
|
|
\( E \subseteq \{\{u,v\} \mid u,v \in V, u \ne v \} \)
|
|
|
|
\defin Der \underline{Grad} (degree, engl.) deg(v) eines Knotens ist die Anzahl der Kanten, die bei v beginnen.
|
|
|
|
\defin Ein \underline{Baum} ist ein zusammenhängender, azyklischer Graph. (G heißt zusammenhängend, wenn man von einem jedem Knoten in G zu jedem anderen Knoten gelangen kann. Zusammenhangskomponenten: größte zusammenhängende Teilgraphen.)
|
|
|
|
Ein \underline{Wald} ist ein azyklischer Graph. (d.\,h. die Zusammenhangskomponenten eines solchen Graphen sind Bäume)
|
|
|
|
Die Knoten vom Grad 1 (oder 0) eines Baumes heißen \underline{Blätter}, alle anderen Knoten sind \underline{innere Knoten}.
|
|
|
|
\includegraphics[height=4cm]{bilder/5-3_graphen.pdf}
|
|
|
|
\begin{enumerate}
|
|
\item nicht azyklisch, nicht zusammenhängend
|
|
\item azyklisch, nicht zusammenhängend, ein Wald aus zwei Bäumen.
|
|
\item enthält einen Kreis, weder Baum noch Wald.
|
|
\item Ein Baum: azyklisch und zusammenhängend.
|
|
\end{enumerate}
|
|
|
|
\underline{Beh.:} Jeder Baum hat Blätter.\\
|
|
\underline{Beweis:} Starte bei einem beliebigen Knoten, gehe entlang beliebiger Kanten, ohne bereits besuchte Knoten nochmals zu besuchen. Da \(|V|\) endlich ist, endet dieser Vorgang nach spätestens n Schritten.\checkmark
|
|
|
|
\textcolor{darkblue}{\underline{Satz:}} Jeder Baum hat \(e = n-1\) viele Kanten.
|
|
|
|
Beweis mit Vollständiger Induktion übder n:\\
|
|
\textbf{IA:} \( n = 1 \rightarrow e = 0 \) \checkmark \\
|
|
\textbf{IS:} \(G'\) habe $n+1$ Knoten. Sei v ein Blatt von \(G'\). es sei \(G\) der Teilgraph von \(G'\), den man durch Entfernen von v (und der Kante v) erhält.\\
|
|
\( \Rightarrow \) $G$ hat $n$ Knoten\\
|
|
\( \overset{\text{i.V.}}{\Rightarrow} \) $G$ hat $n-1$ Kanten\\
|
|
\( \Rightarrow \) $G'$ hat \((n-1)+1 = n\) Kanten \checkmark
|
|
|
|
Folgerung: Hat G n oder mehr Kanten, dann enthält G einen Kreis.
|
|
|
|
\defin Ein \underline{Wurzelbaum} ist ein Baum mit einem ausgezeichneten Knoten, der sog. \underline{Wurzel}.
|
|
|
|
\defin Die \underline{Tiefe} eines Knotens in einem Wurzelbaum ist sein Abstand zur Wurzel.\\
|
|
Die \underline{Tiefe} eines Wurzelbaumes ist die größte Tiefe eines Knotens in diesem Baum.
|
|
|
|
\underline{Bsp.:}\\
|
|
\includegraphics[height=2cm]{bilder/5-3_tiefe.pdf}
|
|
|
|
\defin Ein \underline{Binärbaum} ist ein Wurzelbaum, in dem jeder Knoten Grad \(\le 3\) hat, die Wurzel hat Grad 2.
|
|
|
|
\textcolor{darkblue}{\underline{Satz:}} Ein Binärbaum der Tiefe t hat höchstens \(2^t\) viele Blätter.
|
|
|
|
\includegraphics[height=2cm]{bilder/5-3_planar.png}
|
|
|
|
\defin Ein Graph ist \underline{planar}, wenn man ihn so in der Ebene zeichnen kann, dass sich keine Kanten überschneiden.
|
|
|
|
\includegraphics[height=3cm]{bilder/5-3_planar_bsp.pdf}
|
|
|
|
Bem.: Jeder planare Graph unterteilt die Ebene in disjunkte Gebiete.
|
|
|
|
|
|
\underline{Eulersche Polyederformel:}
|
|
|
|
\(n + \underbrace{g}_{\text{anzahl der Gebiete}} = e +2\)\\
|
|
Gilt für zusammenhängende planare Graphen.
|
|
|
|
Beweis mit vollständiger Induktion über g:
|
|
|
|
\textbf{IA:} Es sei G ein zusammenhängender planarer Graph mit nur einem Gebiet.\\
|
|
Jeder planare Graph mit min. einem Kreis hat min. ein inneres Gebiet.\\
|
|
\(\rightarrow\) G kann keinen Kreis enthalten, G ist also ein Baum.
|
|
\(\Rightarrow e = n-1\),\\
|
|
\( \quad n +g = n+1 = e+2 \) \checkmark
|
|
|
|
\textbf{IS:} Es sei \(G'\) ein zusammenhängender, planarer Graph mit $g+1$ Gebieten, $n'$ Knoten und $e'$ Kanten.\\
|
|
z.z. \( n' + (g+1) \overset{!}{=} e' + 2 \)\\
|
|
$G'$ enthält min ein inneres Gebiet, also auch einen Kreis. Wähle eine Kante auf dem Kreis, entferne diese.\\
|
|
\(\Rightarrow\) Es entsteht der zusammenhängende, planare Graph $G$ mit $g$ Gebieten.
|
|
\(\underset{\text{I.V.}}{\Rightarrow}\) für $G$ gilt:\\
|
|
\( n + g = e+2\),\\
|
|
\( n' = n, e' = e+1\)\\
|
|
\(\Rightarrow\) für $G'$ gilt:
|
|
\( n' + (g+1) = (n+g) +1 = e+ 3 = e' +2 \) q.e.d.
|
|
|
|
gesucht: Zusammenhang zwischen e und n (oder Schranke für e)
|
|
\begin{itemize}
|
|
\item edes innere Gebiet ist von mindestens drei Kanten umgeben.
|
|
\item Jede Kante trennt höchstens zwei Gebiete.
|
|
\end{itemize}
|
|
Zähle paare von Gebieten und Kanten:
|
|
\( M := \{ (\gamma, \kappa \mid \gamma \text{ ein inneres Gebiet, }\kappa\text{ eine Kante, die J begrenzt} \} \)\\
|
|
\begin{align*}
|
|
g \cdot 3 \le |M| \le 2 \cdot e
|
|
\Rightarrow g &\le \frac{2}{3} e \Leftrightarrow g+n \le \frac{2}{3} e + n\\
|
|
n + \frac{2}{3} \cdot e &\ge n + g \underset{\text{Euler}}{=} e + 3 &| -\frac{2}{3} \cdot e\\
|
|
n &\ge \frac{1}{3} e + 2 &| -2\\
|
|
n-2 &\ge \frac{1}{3} e &| \cdot 3\\
|
|
3n - 6 &\ge e
|
|
\end{align*}
|
|
gilt für alle zusammenhängenden planaren Graphen.
|
|
|
|
\subsubsection{Färbung von Graphen}
|
|
|
|
Eine \underline{Färbung} von G ist eine Zuordnung von Knoten auf Farben, sodass benachbarte Kanten unterschiedliche Farben besitzen.
|
|
|
|
Bem.: Als „Farben“ können können die Elemente beliebiger endlicher Mengen dienen.
|
|
|
|
Bsp.: \\
|
|
\begin{multicols}{2}
|
|
\includegraphics[height=2cm]{bilder/5-3-1_bsp_2.pdf}
|
|
\columnbreak\\
|
|
3-färbbar (d.\,h. es gibt eine Färbung mit 3 Farben)
|
|
\end{multicols}
|
|
|
|
K3,3\\
|
|
\begin{multicols}{2}
|
|
\includegraphics[height=2cm]{bilder/5-3-1_k3.pdf}
|
|
\columnbreak\\
|
|
2-Färbbar\\
|
|
\( \chi(K_{3,3}) = 2 \)
|
|
\end{multicols}
|
|
|
|
K5\\
|
|
\begin{multicols}{2}
|
|
\includegraphics[height=2cm]{bilder/5-3-1_k5.pdf}
|
|
\columnbreak\\
|
|
5-Färbbar\\
|
|
\( \chi(K_{5}) = 5 \)
|
|
\end{multicols}
|
|
|
|
Die minimale Anzahl an Farben einer Färbung von G heißt \underline{chromatische Zahl} \( \chi(G) \) von G.
|
|
|
|
\textbf{Vier-Farben-Satz}
|
|
|
|
Jede politische Landkarte kann mit vier Farben so gefärbt werden, dass benachbarte Länder verschiedene Farbe besitzen.
|
|
|
|
Beweis des Vier-Farben-Satzes 1971 von Appel und Haken. (Reduktion auf ca. 2000 einzelne Graphen, Untersuchung derselben in ca. 1200 Rechnerstunden).
|
|
|
|
\textbf{Fünf-Farben-Satz (Heowood)}
|
|
|
|
Jeder planare Graph ist 5-färbbar
|
|
|
|
Beweis: Induktion über n:\\
|
|
\textbf{IA:} n = 1,2,3,4,5 \checkmark\\
|
|
\textbf{IS:} n > 5\\
|
|
(Graph $G'$ mit n+1 Kanten)\\
|
|
\( \Rightarrow \) Es gibt einen Knoten mit \(deg(v) \le 5\)\\
|
|
$G'$ ist planarer Graph.
|
|
|
|
Konstruiere Teilgraph G um $G'$ durch entfernen von V.\\
|
|
\( \Rightarrow \) G hat n Knoten und ist planar\\
|
|
\( \Rightarrow \) G ist 5-färbbar
|
|
|
|
\textbf{I.V.} Falls die Nachbarn von V weniger als 5 verschiedene Farben besitzen, kann V mit der fünften Farbe gefüllt werden. Sonst (d.\,h. die Nachbarn haben fünf versch. Farben)\\
|
|
Beweisidee:\\
|
|
\includegraphics[height=3cm]{bilder/5-3-1_beweis.pdf}
|
|
Farben \( = \{A,B,C,D,E\} \)\\
|
|
\underline{Fall 1:} Es gibt keinen „A-C, weg $V_1$ nach $V_3 \Rightarrow $ Vertausche die Farben A und C inder Umgebung von $V_3 \rightarrow$ Färbe V mit C.
|
|
|
|
\underline{Fall 2}(sonst): Es gibt keinen „B-D“ Weg von $V_2$ nach $V_4$ Verfahre analog zu Fall 1.
|
|
|
|
%TODO - Farben%
|
|
\newpage
|
|
\section{Kombinatorik}
|
|
|
|
Zufallsexperiment:
|
|
\begin{itemize}
|
|
\item Gegeben ist eine Urne mit n Kugeln, die von 1 bis n durchnummeriert sind.
|
|
\item Ziehe k Kugeln, wieviele mögliche Ergebnisse gibt es?
|
|
\end{itemize}
|
|
|
|
mögliche Modi:
|
|
\begin{itemize}
|
|
\item mit zurücklegen oder ohne zurücklegen
|
|
\item die Reihenfolge der gezogenen Kugeln wird beachtet, oder nicht.
|
|
\end{itemize}
|
|
|
|
\underline{Bsp.:} Ziehe zwei Zahlen aus \( \{ 1,2,3 \} \).
|
|
|
|
%TODO%
|
|
|
|
%\begin{tabular}{l|ll}
|
|
% & mit zurücklegen & ohne zurücklegen\\
|
|
% \hline
|
|
% geordnet & \( (1,1), (1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3) \) & \( (1,2),(1,3),(2,1),(2,3),(3,1),(3,2) \)\\
|
|
% & \( \rightarrow 9 \) & \( \rightarrow 6 \)
|
|
% ungeordnet & \begin{tabular}{l|l} & \( \{1,2\},\{1,3\},\{2,3\} \\
|
|
% &\( \rightarrow 9 \) & \( \rightarrow 3 \)
|
|
%\end{tabular}
|
|
|
|
\begin{enumerate}
|
|
\item \underline{geordnet, mit zurücklegen}\\
|
|
ziehe k Zahlen aus \( [n] \)\\
|
|
Menge möglicher Ergebnisse: \( [n]^k \)\\
|
|
Anzahl: \(\left| [n]^k \right| = \left| [n] \right|^k = n^k \)\\
|
|
\underline{Bsp.:} Mögliche Zustände eines Bytes:\\
|
|
\( \left| \{0,1\} \right|^8 = 2^8 = 256 \)
|
|
\underline{Bsp.:} Anzahl der Wörter mit fünf Buchstaben über dem Alphabet \( C := \{ a, ..., z \} \):\\
|
|
\( | \{a,...,z\}^5| = |C|^5 = 26^5 \)
|
|
\item \underline{geordnet, ohne zurücklegen}
|
|
Anzahl insgesamt:\\
|
|
\( n \cdot (n-1) \cdot (n-2) \cdot (n-k+1) \)
|
|
\( = \prod\limits_{j=0}{k-1} ( n-j ) \)\\
|
|
\( n^{\underline{k}} = \underbrace{n\cdot (n-1) ... ( n-k+1)}_{\text{k Faktoren}} \)\\
|
|
„fallende Faktorielle“
|
|
Zusammenhang mit der Fakultät:\\
|
|
\( n^{\underline{k}} = n! \)\\
|
|
\( n^{\underline{n}} = \frac{n(n-1) ... 1}{(n-k)(n-k-1) ... 1} \)\\
|
|
\( = \frac{n!}{(n-k)!}\)\\
|
|
Bsp.: \( 5^{\underline{3}} = 5 \cdot 4 \cdot 3 = \frac{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{2 \cdot 1} = \frac{5!}{3!} = 60 \)
|
|
\item \underline{ungeordnet, ohne zurücklegen}\\
|
|
\includegraphics[width=10cm]{bilder/6-0_ung_ohne_zur.pdf}\\
|
|
Jedes Ergebnis im Fall (1) entspricht $k!$ Ergebnissen im Fall (2), nämlich allen $k!$ Permutationen dieser k Objekte.\\
|
|
Anzahl möglicher Ergebnisse im Fall (1)\\
|
|
= Anzahl möglicher Ergebnisse im Fall (2) \( \cdot \frac{1}{k!}\)\\
|
|
\( = \frac{n^{\underline{k}}}{k!} = \frac{n!}{(n-k)! \cdot n!} =: \binom{n}{k} \)\\
|
|
Binomialkoeffizient, „k aus n“
|
|
\underline{Bsp.: von oben:} „Zwei aus Drei“
|
|
\( \binom{2}{3} = \frac{3!}{1! \cdot 2!} = \frac{3 \cdot 2 \cdot 1}{1 \cdot 2 \cdot 1} = 3 \) \checkmark\\
|
|
\underline{Bsp. Lotto:}\\
|
|
\( \binom{49}{6} = \frac{49!}{43! \cdot 6!} = \frac{49 \cdot 48 \cdot 47 \cdot 46 \cdot 45 \cdot 44}{6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = 13.983.816\) mögliche Ergebnisse\\
|
|
\(\Rightarrow\) Warhscheinlichkeit für sechs richtige \(\approx \frac{1}{14.000.000}\)
|
|
|
|
Wahrscheinlichkeit für drei Richtige:\\
|
|
Anzahl günstiger Ergebnisse:\\
|
|
\( \binom{6}{3} \cdot \binom{43}{3} \)
|
|
|
|
Wahrscheinlichkeit für genau drei Richtige:\\
|
|
\( \frac{\binom 6 3 \cdot \binom{43}{3}}{\binom{49}{6}} = \frac{6!^2 \cdot 43!^2}{3!^3 \cdot 40! \cdot 49!} = \frac{8815}{499422} \)
|
|
|
|
\underline{Bem.:} \(\binom n k\) ist die Anzahl der Möglichkeiten, eine k-elementige Teilmenge aus einer n-elementigen Menge zu wählen.
|
|
|
|
\underline{Bsp.:} Wieviele Bitstrings der Länge 8 mit fünf Einsen (und drei Nullen) gibt es?\\
|
|
Menge der Indizes = \( \{0,1,...,7\} \)\\
|
|
Ergebnis = Anzahl fünfelementiger Teilmengen von \(\{ 0,1,...,7\}\)\\
|
|
= \(\binom 8 5 = \binom{8}{8-5} = \binom{8}{3} = 56\)\\
|
|
\( \binom 8 5 = \frac{n!}{k! \cdot (n-k)!} = \frac{n!}{(n-k)! \cdot (n-(n-)k)!} = \binom{n}{n-k} \)
|
|
\item \underline{ungeordnet, mit zurücklegen}\\
|
|
mit \( x_i \in \mathbb N, \sum\limits_{i=1}^{n} = k\) (Gesamtzahl gezogener Objekte)\\
|
|
Bsp.: 5 Objekte, ziehe 8\\
|
|
\begin{tabular}{c|c}
|
|
Objekt & Anzahl\\
|
|
1 & 3\\
|
|
2 & 0\\
|
|
3 & 1\\
|
|
4 & 2\\
|
|
5 & 2
|
|
\end{tabular}
|
|
\( \Rightarrow \) \begin{tabular}{|c|c|c|c|c|c|c|c|}\hline1&1&1&3&4&4&5&5\\\hline\end{tabular}\\
|
|
Anzahl der Ergebnisse = \( \binom{k+n-1}{n-1} = \binom{k+n-1}{n} \)
|
|
\end{enumerate}
|
|
|
|
\underline{Zusatz:} Ziehen aus einer Menge von Objekten, die nicht alle verschieden sind, am Beispiel des Algorithmus Permutations.\\
|
|
Eingabe: l Ziffern mit Häufigkeiten \( n_9,...,n_l \) mit \( \sum\limits_{i=1}^{l} n_i = n \).\\
|
|
Gesucht: Anzahl der der Zahlen, die sich aus diesen Ziffern bilden lassen.\\
|
|
Das entspricht dem Fall „geordnet, ohne zurücklegen“.\\
|
|
Nehme zunächst an, dass alle Ziffern unterscheidbar sind. Zähle diese Möglichkeiten und vergesse anschließend die Idendität gleicher Ziffern.\\
|
|
Anzahl der Möglichkeiten im Zwischenschritt:\\
|
|
\( n ^ {\underline{n}} = n! \)\\
|
|
\underline{Bsp.:} alle Ziffern \( 1,1,2,...,n-1\) (nur die 1 kommt doppelt vor)\\
|
|
Zwischenschritt:
|
|
\begin{itemize}
|
|
\item ersetze \( 1,1 \) durch \( 1a,1b\)
|
|
\item zu jeder Kombination \(X\) der Ziffern gibt es genau eine Kombination \(X'\), bei der lediglich $1a$ und $1b$ vertauscht sind.
|
|
\item Vergisst man die Identität von \(1a,1b\) dann führen $X$ und $X'$ auf dieselbe Kombination des ursprünglichen Problems
|
|
\item[\(\Rightarrow\)] Anzahl der möglichkeiten im Ursprünglichen Problem \( = \frac{1}{2} \cdot n! \)
|
|
\end{itemize}
|
|
Im allgemeinen Fall:\\
|
|
Ziffern i mit Häufigkeit $n_i$ können beliebig untereinander ausgetauscht werden \(\rightarrow n_i!\) Permutationen\\
|
|
\(\Rightarrow \) Endergebnis: \( \frac{n!}{n_1! n_2! ... n_l!} = \frac{n!}{\prod\limits_{i=1}^{l} n_i! } \)
|
|
|
|
\underline{Bsp.:} Aufgabe 7.1\\
|
|
\(1,1,3,3,3\)\\
|
|
\( \Rightarrow \frac{5!}{2! 3!} = \frac{5 \cdot 4}{2 \cdot 1} = 10 \) \checkmark
|
|
|
|
\underline{Bsp.:} John hat 4 Büchsen Gulaschsuppe, 2 Dosen Ravioli und eine Fertigpizza. Wieviele Wochenspeisepläne sind möglich?\\
|
|
\( \rightarrow \) Ziehen ohne zurücklegen, geordnet, mit ununterscheidbaren Objekten.
|
|
|
|
Bei Unterscheidbaren Mahlzeiten:\\
|
|
\spa Anzahl Speisepläne \( = 7^{\underline{7}} = 7! \)\\
|
|
bei Unterscheidbaren Mahlzeiten:\\
|
|
\spa Anzahl der Speisepläne \( = \frac{7!}{4! 2! 1!} = 7 \cdot 3 \cdot 5\)\\
|
|
\spa \( = 105\)
|
|
|
|
\underline{einige Eigenschaften der Binomialkoeffizienten}\\
|
|
fall \( n,j \in \mathbb N, n \ge k\):
|
|
\spa \( \binom n k := \frac{n!}{k! (n-k)!} \)\\
|
|
allgemeiner:\\
|
|
\spa \( \alpha \in \mathbb R , k \in \mathbb N \)\\
|
|
\spa \( \binom \alpha k := \prod\limits_{j=1}^{k} \frac{\alpha + 1 - j}{j} = \frac{\alpha \cdot (\alpha -1) \cdot ... \cdot (\alpha +1 - k) }{k \cdot (k-1) \cdot ... \cdot 1} \)
|
|
|
|
im Folgenden ist jeweils \( \alpha \in \mathbb R; k,n \in \mathbb N\)
|
|
|
|
\begin{enumerate}
|
|
\item \( \binom n k = 0 \quad \text{ falls } 0 \le n < k \)\\
|
|
z.\,B. \( \binom 3 5 = \frac{3\cdot 2 \cdot 1 \cdot 0 \cdot (-1)}{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = 0 \)
|
|
\item \( \binom n k = \binom n {n-k} \) \spa (Symmetrie)
|
|
\item \( \binom \alpha k = \frac{\alpha \cdot ... \cdot ( \alpha +1-k)}{k ... 1} \)\\
|
|
\( = \frac{\alpha + 1 - k }{k} \frac{\alpha ... (\alpha+2-k)}{(k-1) ... 1} \)\\
|
|
\( = \frac{\alpha + 1 -k}{k} \cdot \binom \alpha {k-1} \)
|
|
\item \( \binom \alpha k = \frac{\alpha}{k} \cdot \frac{(\alpha-1) ... ( \alpha +1-k)}{(k-1) ... 1} \)\\
|
|
\( = \frac{\alpha}{k} \binom{\alpha-1}{k-1} \)
|
|
\item Summenformel:\\
|
|
\( \binom \alpha k + \binom \alpha {k-1} \underset{3.}{=} \frac{\alpha + 1-k}{k} \binom{\alpha}{k-1} + \binom{\alpha}{k-1} \)\\
|
|
\( = \frac{\alpha + 1}{k} \binom \alpha {k-1} \underbrace{-\frac{k}{k} \binom \alpha {k-1} + \binom \alpha {k-1}}_{=0} \)\\
|
|
\( \underset{4.}{=} \binom {\alpha+1} k \)
|
|
|
|
\( \rightarrow \) Pascalsches Dreieck
|
|
%% TODO pascalsches dreieck %%
|
|
\end{enumerate}
|
|
|
|
\underline{Binomealtheorem}\\
|
|
\((a+b)^2 = a^2 + 2ab + b^2 \)\\
|
|
\((a+b)^3 = a^3 + 3a^2b + 3ab^2 + b^3 \)\\
|
|
\((a+b)^n = (a+b)(a+b) ... (a+b) \)
|
|
|
|
Ausmultiplizieren von \( (a+b)^n\) liefert eine Summe von Termen der Form\\
|
|
\spa \( x_1 x_2 ... x_n \text{ mit } x_i = a \text{ oder } x_i = b \);\\
|
|
jede Kombination kommt einmal vor.\\
|
|
\(\Rightarrow\) Der Wert von \( x_1 x_2 ... x_n \) hängt nur von der \underline{Anzahl} der enthaltenen a's und b's ab.\\
|
|
\( (a + b )^n = \sum\limits_{k=0}^{n} a^{n-k} b^k \)
|
|
|
|
Folgerung:\\
|
|
\( (1+x)^n = \sum\limits_{k=0}^{n} 1^{n-k} x ^ k \) \\
|
|
\( = \sum\limits_{k=0}^{n} \binom n k \cdot x^k \)\\
|
|
\( \Rightarrow \sum\limits_{k=0}^{n} \binom n k = \sum\limits_{k=0}^{n} \binom n k 1^k = (1+1)^n = 2^n \)\\
|
|
\spa \( \sum\limits_{k=0}^{n} (-1)^k \binom n k = \sum\limits_{k=0}^{n} \binom n k \cdot (-1)^k = (1+(-1))^n = 0\)
|
|
|
|
\underline{Monotone Gitterwege}
|
|
|
|
Gegeben sein ein Rechtwinkliges Gitter.\\
|
|
\includegraphics[height=3cm]{bilder/5-3-1_monotone_gitterwege.pdf}\\
|
|
Gesucht: Anzahl der kürzesten Wege von (0,0) nach (b,a); die Länge der kürzesten Wege ist \( l = a + b \).\\
|
|
Die Anzahl kürzester Wege sei\( w(a,l) \)
|
|
|
|
falls \( a = 0 : w(0,l) = 1 \)\\
|
|
falls \( b = 0 : w(a,a) = 1 \)\\
|
|
falls \( a >0, b>0 \)
|
|
|
|
\( w(a,l) = w(a,l-1) + w(a-1,l-1) \)\\
|
|
Beh.:\\
|
|
\( w(a,l) \overset{!}{=} \binom l a \underset{\text{symmetrie}}{=} \binom l b\)
|
|
|
|
Beweis mit vollständiger Induktion, Induktionsschritt:\\
|
|
\( w(a,l-1) + w(a-1,l-1) \)\\
|
|
\( \underset{\text{I.V.}}{=} \binom {l-1} a + \binom {l-1}{a-1} \)\\
|
|
\( = \binom l a \) \checkmark
|
|
|
|
\newpage
|
|
|
|
\section{Zahlentheorie}
|
|
|
|
\subsection{Teilbarkeit}
|
|
|
|
\defin Es seien \( m,n \in \mathbb Z \).\\
|
|
\begin{enumerate}
|
|
\item \(m|n : \Leftrightarrow m\) ist Teiler $n$.\\
|
|
:\( \Leftrightarrow \exists t \in \mathbb Z: m\cdot t = n\).
|
|
\item \(T_m := \{ k \mid k \in \mathbb Z, k >0 , k|m \} \)\\
|
|
ist die Menge aller positiven Teiler von $m$
|
|
\item \( T_{m,n} := T_m \cap T_n\)\\
|
|
ist die Menge der gemeinsamen (positiven) Teiler von $m$ und $n$.\\
|
|
\underline{Bsp.:}
|
|
\begin{itemize}
|
|
\item \( 3|12, \text{ denn } 3 \cdot 4 = 12 \)
|
|
\item \( 5 \not| 12 \)
|
|
\item \( T_{12} = \{1,2,3,4,6,12 \} \)\\
|
|
\( T_{18} = \{1,2,3,6,9,18\} \)
|
|
\item \( \forall m \in \mathbb Z : 1|m, \text{ denn } 1 \cdot m = m\)\\
|
|
\( m | m \)
|
|
\item \( \forall m \in Z : m|0, \text{ denn } 0 \cdot m = 0 \)\\
|
|
\( \rightarrow T_0 = \{ t \in \mathbb Z \mid t > 0 \} \)\\
|
|
\( T_{0,n} = T_0 \cap T_n = T_n \)
|
|
\end{itemize}
|
|
\end{enumerate}
|
|
|
|
\defin Divisionsrest\\
|
|
Es seien \( m,n \in \mathbb Z, m>0 \).\\
|
|
Der \underline{Rest} bei Division $n$ durch $m$ ist \( n \mod m := n-\lfloor \frac{n}{m} \rfloor m\).\\
|
|
(\( \lfloor x \rfloor \) bedeutet Abrunden, also:\\
|
|
\( \lfloor x \rfloor\) ist die größte ganze Zahl $y$ mit \( y \le x \);\\
|
|
\(\lceil x \rceil \) ist die kleinste Zahl \( z \in \mathbb Z \text{ mit } z \ge x \))
|
|
|
|
\underline{Bez.:} \( n \mod m\) „n modulo m“\\
|
|
\underline{Bsp.:}
|
|
\begin{itemize}
|
|
\item \( 7 \mod 3 = 7 - \lfloor \frac{7}{3} \rfloor \cdot 3 = 7 - \lfloor 2+\frac{1}{3} \rfloor \cdot 3 = 7 - 2 \cdot 3 = 1 \)
|
|
\item \(-7 \mod 3 = -7 - \lfloor -2-\frac{1}{3} \rfloor \cdot 3 \)\\
|
|
\( = -7 - (-3) \cdot 3 = -7 + 9 = 2 \)
|
|
\end{itemize}
|
|
|
|
\underline{Folgerung:}
|
|
\begin{itemize}
|
|
\item falls \( m|n, t \cdot m = n \)\\
|
|
\( n \mod m = n - \lfloor \frac{n}{m} \rfloor \cdot m \)\\
|
|
\( = n -m \lfloor t \rfloor m = n - t \cdot m = 0 \)
|
|
\item \( r := n \mod m \in \{ 0, ... m-1 \} \):\\
|
|
\begin{enumerate}
|
|
\item \( r \ge 0 \):
|
|
\( \lfloor \frac{n}{m} \rfloor \le \frac n m \rightarrow r = \lfloor \frac n m \rfloor m \overset{m>0}{\ge} n - \frac n m \cdot m = 0 \)
|
|
\item \( r <m \):\\
|
|
Setze \( t := \lfloor \frac n m \rfloor \)\\
|
|
\( r = n -t \cdot m \quad | +tm -r\)\\
|
|
\( t \cdot m = n -r \quad | :m \)\\
|
|
\( t = \frac{n-r}{m} \)
|
|
\end{enumerate}
|
|
Annahme: \( r \ge m \)\\
|
|
\begin{align*}
|
|
\Rightarrow t+1 &= \frac{n-r}{m} + \frac{n}{m}\\
|
|
&= \frac{n-\overset{\ge 0}{(r-m)}}{m} \le \frac n m
|
|
\end{align*}
|
|
also \( t+1 \in \mathbb Z, t+1 \le \frac n m \)\\
|
|
\( \Rightarrow t\) ist \underline{nicht} die größte ganze Zahl \( \le \frac n m \), widerspruc zu \( t:= \lfloor \frac n m \rfloor \).\\
|
|
\( \Rightarrow r < m \)
|
|
\item Falls \( n = t \cdot m +r \text{ mit } r \in \{ 0, ..., m-1 \} \), dann gilt \( t = \lfloor \frac n m \rfloor, r = n \mod m \) . (ohne Beweis)
|
|
\end{itemize}
|
|
|
|
\defin Es seien \( m,n \in \mathbb Z, (m,n) \ne (0,0) \).\\
|
|
Dann ist ggT(m,n) der \underline{größte gemeinsame Teiler} von m und n, d.\,h. ggT(m,n) = max. \(T_{m,n}\)
|
|
|
|
kgV(m,n) :=\( min\{ k \in \mathbb N \mid k > 0, m|k und n|k \} \) ist das \underline{kleinste gemeinsame Vielfache} von m und n.\\
|
|
\underline{Bsp.:}\\
|
|
ggT(12,18) = max( \( T_{12} \cap T_{18} \) ) = max(\(\{1,2,3,5\}\)) = 6\\
|
|
kgV(12,18) = \( 36 ( 12 \cdot 3 = 35, 18 \cdot 2 = 36) \)
|
|
|
|
\textbf{Beh.:} Für alle \( a \in \mathbb Z \) ist \(T_{min} = T_{m,n-a\cdot m} \)
|
|
\begin{enumerate}
|
|
\item \( T_{m,n} \le T_{m,n-m\cdot a} \)\\
|
|
Es sei \(x \in T_{m,n} \);\\
|
|
\( t,s \in \mathbb Z \text{ mit } t\cdot x = m, s\cdot x = n. \)\\
|
|
\( x|m \) \checkmark \\
|
|
\( x|n-a\cdot m \):\\
|
|
\( (s - a \cdot t) \cdot x = n -a \cdot m \)\\
|
|
\( \Rightarrow x \in T_{m,n-a\cdot m}\) ,\\
|
|
d.\,h. \( T_{m,n} \le T_{m,n - a\cdot m} \)
|
|
\item \( T_{m,n} \ge T_{m,n-a\cdot m} \)\\
|
|
Es sei \( x \in T_{m,n-a\cdot m}\),\\
|
|
\( t,s \in \mathbb Z \text{ mit } x \cdot t = , x \cdot s = n-a\cdot m \)\\
|
|
\( x \in T_{m,n}\):\\
|
|
\( x|m \) \checkmark\\
|
|
\( x|n: ( s +a \cdot t ) \cdot x = n \)\\
|
|
\( \rightarrow T_{m,n} \supseteq T_{m,n-a\cdot m}\),\\
|
|
\( T_{m,n} = T_{m,n-a\cdot m} \)
|
|
|
|
Folgerung: \( T_{m,n} = T_{m,n- \lfloor \frac n m \rfloor \cdot m} \)\\
|
|
\( = T_{m,n \mod m} \),\\
|
|
\(ggT(m,n) =max T_{m,n} \)\\
|
|
\( = max T_{m,n \mod m} \)\\
|
|
\( = max T_{n \mod m,m} \)\\
|
|
\( ggT(n \mod m , m )\)
|
|
\end{enumerate}
|
|
|
|
\underline{Anwendung:} Euklidscher Algorithmus zur Bestimmung des ggT.
|
|
|
|
\begin{itemize}
|
|
\item rekursive Formulierung:\\
|
|
Eingabe: \( m,n \in \mathbb Z, m,n \ge 0, (m,n) \ne (0,0) \)\\
|
|
E{\tiny UKLID}(m,n)\\
|
|
\spa if \( m = 0\) then return n\\
|
|
\spa else return E{\tiny UKLID}(\( n \mod m, m \))\\
|
|
\underline{Bsp.:} ggT(18,12)\\
|
|
\( = ggt( \underbrace{12 \mod 18}_{=12}, 18) \)\\
|
|
\( = ggt( \underbrace{18 \mod 12}_{=6}, 12) \)\\
|
|
\( = ggt( \underbrace{12 \mod 6}_{=0}, 6) \)\\
|
|
\( = 6 \)
|
|
\item iterative Formulierung:\\
|
|
E{\tiny UKLID1}(m,n)\\
|
|
\spa while $m \ne 0$ \\
|
|
\spa\spa tmp := m\\
|
|
\spa\spa m := n mod m\\
|
|
\spa\spa n := tmp\\
|
|
\spa return n
|
|
\end{itemize}
|
|
|
|
\textbf{Beh.:} Für alle Zahlen \( m,n \in \mathbb Z, (m,n) \ne (0,0), 0 \le m \le n \le 2^c\) (für ein \( c \in \mathbb N \)) sei \( R(m,n)\) die Anzahl rekursiver Aufrufe bei der Berechnung E{\tiny UKLID}(n mod m,m)\\
|
|
Dann ist \( R(m,n) \le 2\cdot c + 1\).\\
|
|
Beweis mit vollständiger Induktion über $c$:\\
|
|
\textbf{IA}: \( c = 0 \)
|
|
\begin{itemize}
|
|
\item[\(\Rightarrow\)] \( n = 1, m \in 0,1 \).
|
|
\item[1.] \( ggT(0,1) = 1 \)\\
|
|
\(\rightarrow R(0,1) = 0\)
|
|
\item[2.] \( ggt(1,1) = ggT(0,1) = 1\) \\
|
|
\( \rightarrow R(1,1) = 1 \le 2 \cdot 0 + 1 \) \checkmark
|
|
\end{itemize}
|
|
\textbf{IS}: \( 0 \le m \le n \le 2^{c+1}\)\\
|
|
z.z. \( R(m,n) \le (2(c+1) +1) \)\
|
|
\( ggT(m,n) = ggT(n \mod m, m)\)\\
|
|
\( = ggT(\underbrace{m \mod (n \mod m)}_{=:m'}, \underbrace{n \mod m}_{=: n'}) \)\\
|
|
\( \Rightarrow m' < m \);\\
|
|
\( \quad n' \le \frac n 2 \le 2^c\)\\
|
|
\underline{Fall 1:} \( 2m > n \):\\
|
|
\spa \( n < 2m \rightarrow n \mod m = n-m < n - \frac n 2 = \frac n 2\)\\
|
|
\underline{Fall 2:} \( 2m < n \):\\
|
|
\spa \( \Rightarrow n \mod m \le m-1 < m \le \frac n 2\)
|
|
|
|
Also: Nach den ersten zwei rekursiven Aufrufen gilt: \( 0 \le m' \le n' \le \frac n 2 \le 2^c\).\\
|
|
Wegen Induktionsvorraussetzung gilt also
|
|
\begin{align*}
|
|
R(m',n') &\le 2\cdot c +1\\
|
|
\Rightarrow R(m,n) &\le 2 + R(m',n')\\
|
|
&\le 2 \cdot (c + 1) +1. \quad \checkmark
|
|
\end{align*}
|
|
|
|
Die Laufzeit von E{\tiny UKLID}(m,n) ist also \( \le 2 \cdot \lceil \log_2 max\{m,n\} \rceil + 2\)
|
|
|
|
\underline{Der erweiterte Euklidsche Algorithmus}\\
|
|
\underline{Beh.:} \( \exists x,y \in \mathbb Z : ggT(m,n) = x \cdot m + y \cdot n \)\\
|
|
Beweis:\\
|
|
\underline{Fall 1:} \( m = 0 \Rightarrow ggT(m,n) = ggT(0,n) = n = 0 \cdot m + 1 \cdot n\), d.\,h. wähle \( x:= 0, y:= 1\).\\
|
|
\underline{Fall 2:} \( m > 0 \Rightarrow ggT(m,n) = ggT(n \mod m, m) \)
|
|
|
|
Beweis mit volständiger Induktion:\\
|
|
\textbf{IA:} \( m = 0\) \checkmark (s.\,o.)\\
|
|
\textbf{IS:} IV: \( \forall m' < m : \exists x,y \in \mathbb Z : ggT(m',n) = x \cdot m' + y \cdot n \).\\
|
|
z.\,z.: Dann gilt:\\
|
|
\spa \(\exists x', y' \in \mathbb Z: x' \cdot m + y' \cdot n = ggT(m,n) \)\\
|
|
\(ggT(m,n) = ggT(\underbrace{n \mod m}_{=: m', m'<m},m) \)\\
|
|
\( \overset{\text{.V.}}{=} x \cdot m' + y \cdot m \)\\
|
|
\( = x \cdot (n - \lfloor \frac n m \rfloor \cdot m ) + y \cdot m \)\\
|
|
\( = \underbrace{(y - x \cdot \lfloor \frac n m \rfloor )}_{=x'} \cdot m + \underbrace{x}_{=y'} \cdot m \) \checkmark
|
|
|
|
erweiterter Euklidscher Algorithmus:\\
|
|
Eingabe (wie zuvor), \( m,n \in \mathbb N, (m,n) \ne (0,0)\)\\
|
|
Ausgabe: \( d,x,y) \) mit \(d = ggT(m,n) = x \cdot m + y \cdot n \) \\
|
|
E{\tiny XTENDED}E{\tiny UKLID}(m,n)\\
|
|
\spa if m = 0 then return (n,0,1)\\
|
|
\spa else\\
|
|
\spa\spa (d,x,y):= E{\tiny XTENDED}E{\tiny UKLID}(n mod m, m)\\
|
|
\spa\spa return (d, \( y -x \lfloor \frac n m \rfloor, x\))
|
|
|
|
Bsp. (für die Ausführung des erweiterten Euklidischen Algorithmus).
|
|
|
|
\( ggT(48,27) = x \cdot 48 + y \cot 27 \)\\
|
|
\( m_0 = 48, n_0 = 27;\)\\
|
|
\( m_{i+1} = n_i, n_{i+1} = m_i \mod n_i = m_i - \lfloor \frac{m_i}{n_i} \rfloor \cdot n_i\)\\
|
|
\( x_{i-1},y_{i-1} = ? \)\\
|
|
\(ggT(m_{i+1},n_{i+1}) = x_{i+1} m_{i+1} + y_{i+1} n_{i+1} \)\\
|
|
\spa\( = y_{i+1} m_i + (x_{i+1} - \lfloor \frac{m_i}{n_i} \rfloor y_{i+1}) n_i \)\\
|
|
\( = ggT(m_0,n_0) \)
|
|
|
|
\begin{tabular}{ccc|cc}
|
|
$i$ & $n_i$ & $m_i$ & $y_i$ & $x_i$\\
|
|
\hline
|
|
0 & 48 & 27 & 4 & \(-3 - \lfloor \frac{48}{27} \rfloor \cdot 4 = -7\) \\
|
|
1 & 27 & 21 & -3 & \(1 - \lfloor \frac{27}{21} \rfloor \cdot (-3) = 4\)\\
|
|
2 & 21 & 6 & 1 & \(0 - \lfloor \frac{21}{6} \rfloor \cdot 1 = -3\)\\
|
|
3 & 6 & 3 & 0 & \(1 - \lfloor \frac{6}{3} \rfloor \cdot 0 = -1\)\\
|
|
4 & 3 & 0 & 1 & 0
|
|
\end{tabular}
|
|
|
|
\( 4 \cdot 48 - 7 \cdot 27 = 160 + 32 - 140 - 40 = 3 = ggT(48,27)\)
|
|
|
|
Den ggT braucht man z.B. zum Vollständigen lürzen von Brüchen.
|
|
|
|
Anwendungsbeispiel für den erweiterten Euklidischen Algorithmus:\\
|
|
geg. zwei Meßlatten der Längen\\
|
|
\spa \( l_1 = 48 \text{cm } , l_2 = 27 \text{cm}\)\\
|
|
Damit kann man die Länge l = 3cm (ggt(48,27)=3) vermessen:\\
|
|
\( \underset{=4}{x} \cdot 48 + \underset{=-7}{y} \cdot 27 = 3 \)\\
|
|
\(\rightarrow\) \( 4 \cdot l_1\) abmessen, \(7 \cdot l_2\) abziehen.
|
|
|
|
\subsection{Primzahlen}
|
|
|
|
Jede ganze Zahl \(n\) hat min. die \underline{trivialen} Teiler 1 und n.\\
|
|
\defin \( p \in \mathbb N\) heißt Primzahl, wenn p genau zwei positive Teiler besitzt (1 und p).
|
|
|
|
Die kleinsten Primzahlen sind:\\
|
|
\(2,3,5,7,11,13,17,19\)
|
|
|
|
\underline{Beh.:} Jede natürliche Zahl \(\ge 1\) kann als Produkt von Primzahlen geschrieben werden.
|
|
|
|
Beweis mit vollst. Induktion:\\
|
|
alternative Formulierung der Beh.:\\
|
|
Alle positiven natürlichen Zahlen \( \le n\) lassen sich als Primzahlprodukt schreiben. (\( n \ge 1\) beliebig)
|
|
|
|
\textbf{IA:} \( n = 1 \rightarrow 1 \) ist der Wert des leeren Produkts. \checkmark\\
|
|
\textbf{IS:} IV.: alle Zahlen \( \le n\) sind Primzahlprodukte\\
|
|
zu zeigen: alle Zahlen \( \le n+1\) sind Primzahlprodukte\\
|
|
Es genügt, zu zeigen:
|
|
\spa \(n+1\) ist Primzahlprodukt\\
|
|
Fall 1:\\
|
|
\( \rightarrow \) n+1 ist Primzahlprodukt mit nur einem Faktor.
|
|
Fall 2:\\
|
|
\spa \(n+1\) ist keine Primzahl,\\
|
|
\spa \(n+1 = k \cdot l \text{ mit } 1 < k,l < n+1 \) \\
|
|
\( \overset{\text{IV.}}{\Rightarrow} k \text{ und } l \) sind Primzahlprodukte\\
|
|
\( \Rightarrow n+1 = k \cdot l \) ist auch Primzahlprodukt. \(\square\)
|
|
|
|
Die Darstellung einer Zahl \( n \in \mathbb N\) als Primzahlprodukt \( n = p_1 p_2 \dots p_k \) heißt auch \underline{Primfaktorzerlegung} von n (PFZ), die \(p_i\) sind \underline{Primfaktoren} von n.
|
|
|
|
\underline{Satz:} Die Primfaktorzerlegung\\
|
|
\spa \( n = p_1 p_2 \dots p_k , \quad p_1 \le p_2 \le \dots \le p_k \)
|
|
|
|
\underline{Beweis:}\\
|
|
\textbf{IA:} n = 1 (leeres Produkt) ist eindeutig \checkmark\\
|
|
\textbf{IS:} n+1 habe zwei verschiedene PFZ, \( n+1 = p_1 \dots p_r = q_1 \dots q_s \) mit \( p_1 \le \dots \le p_r, q_1 \le \dots \le q_s \)\\
|
|
1. Fall: \( p_1 = q_1 \Rightarrow \frac{n+1}{p_1} = p_2 \dots p_r = q_2 \dots q_s = \frac{n+1}{q_1} \)\\
|
|
\spa IV: \(\rightarrow\) PFZ von \( \frac{n+1}{p_1} \le n\) ist eindeutig\\
|
|
\spa \( \Rightarrow r=s , p_i = q_i \) \\
|
|
\spa \( \Rightarrow \) Die PFZen von \( p_1, \dots , p_r\) und \( q_1, \dots , q_r\) sind gar nicht verschieden, Widerspruch.
|
|
|
|
2. Fall: \( p_1 < q_1 \)\\
|
|
\spa \( p_1 | n+1 = q_1 \dots q_s \)\\
|
|
\spa \( p_1 | p_1 q_2 \dots q_s \)\\
|
|
\spa \( \Rightarrow p_1 | (q_1 - p_1) q_2 \dots q_s \)\\
|
|
\spa \( q_2, \dots , q_s\) sind nicht durch \(p_1\) teilbar, denn \( q_2, \dots, q_s \ge q_1 > p_1 \).\\
|
|
\spa \( \curvearrowright p_1 | q_1 - p_1 \curvearrowright p_1 | q_1\), aber \( p_1 < q_i \Rightarrow \) Widerspruch.
|
|
|
|
3. Fall: \( p_1 > q_1 \): analofg zu Fall 2.
|
|
|
|
\( \Rightarrow \) PFZ von \(n+1\) ist eindeutig. \(\square\)
|
|
|
|
Häufig faßt man gleiche Primfaktoren zu Potenzen zusammen:\\
|
|
\( n = \sum\limits_{i=1}^{n} p_{i}^{e_i} \quad \text{ mit } p_1 < p_2 < \dots < p_k \)\\
|
|
Ist \( p_i \not | n\), muss natürlich \(e_i = 0\) sein.
|
|
|
|
Es ist nützlich, \underline{alle} Primzahlen in das Produkt aufzunehmen:\\
|
|
\( n = \prod\limits_{i=1}^{\infty} p_i^{e_i} \)\\
|
|
Wir können jede Zahl \( n \in \mathbb N, n > 0 \) durch die unendliche folge \( e_1,e_2,e_3, \dots\) von Exponenten in der PFZ darstellen.
|
|
|
|
Definiere die Hilfsfunktion\\
|
|
\( P(n) := (e_1,e_2,e_3,\dots \)\\
|
|
(„P liefert die PFZ einer beliebigen Zahl“)
|
|
|
|
P ist eine Bijektion, da die PFZ eineindeutig ist.\\
|
|
\underline{Rechenregeln für P:}\\
|
|
(Es seien \(P(m) = ( m_1,m_2,m_3,\dots) \)\\
|
|
\spa und \( P(n) = ( n_1,n_2,n_3,\dots) \))
|
|
\begin{itemize}
|
|
\item \(P(m \cdot n) = ? \) \\
|
|
\(m \cdot n = (\prod\limits_{i=1}^{\infty} p_i ^{m_i})(\prod\limits_{i=1}^{\infty} p_i ^{n_i})\) \\
|
|
\( = \prod\limits_{i=1}^{\infty} p_i ^{m_i + n_i} \)\\
|
|
\( \Rightarrow P(m \cdot n) = (m_1 + n_1, m_2+n_2, m_3+n_3, \dots) \)
|
|
\item falls \( n | m: P(\frac{m}{n}) = (m_1-n_1,m_2-n_2,m_3-n_3)\) (analog)
|
|
\item \( P( ggT(m,n) ) = ? \)\\
|
|
\( ggT(m,n) = ggT(\prod\limits_{i=1}^{\infty} p_i^{m_i},\prod\limits_{i=1}^{\infty} p_i^{n_i}) \)\\
|
|
\( = \prod\limits_{i=1}{\infty} p_i^{min(m_i,n_i)} \)
|
|
\( \curvearrowright P(ggT(m,n)) = (min(m_1,n_1),min(m_2,n_2),min(m_3,n_3),\dots )\)
|
|
\item \( P(kgV(m,n)) = (max(m_1,n_1),max(m_2,n_2),max(m_3,n_3),\dots )\)
|
|
\item \(P(ggT(m,n) \cdot kgV(m,n)) = (min(m_1,n_1) + max(m_1,n_1),min(m_2,n_2) + max(m_2,n_2),min(m_3,n_3) + max(m_3,n_3),\dots )\)\\
|
|
\( = (m_1 + n_1, m_2+n_2, \dots) \)\\
|
|
\( = P(m,n)\)
|
|
\end{itemize}
|
|
P ist injektiv \( \Rightarrow ggT(m,n) \cdot kgV(m,n) = m \cdot n \)\\
|
|
\( kgV(m,n) = \frac{m \cdot n}{ggT(m,n)} \)\\
|
|
(Kann mit E{\tiny UKLID} berechnet werden.)
|
|
|
|
Anwendung der PFZ:\\
|
|
\( \sqrt{2} \) ist irrational (d.\,h. nicht rational, d.\,h. kein Bruch)\\
|
|
Annahme: \( \exists \frac{a}{b} \in \mathbb Q: \left( \frac{a}{b} \right) ^2 = 2 \)\\
|
|
\( \Rightarrow \underbrace{a^2}_{\text{gerade..}} = \underbrace{2 b^2}_{\text{ungerade..}} \)\\
|
|
.. Anzahl an Zweiern in der PFZ\\
|
|
aber PFZ ist eindeutig\\
|
|
\( \Rightarrow a^2 \ne 2b^2\)\\
|
|
\( \rightarrow\) Widerspruch, \( \sqrt{2} \not\in \mathbb Q \)
|
|
|
|
\defin Zwei Zahlen \(m,n \in \mathbb N; m,n > 0\) mit \(ggT(m,n) = 1\) heißen \underline{teilerfremd}. (Abk.: \( m \perp n \) )
|
|
|
|
\underline{Bsp.:} Ein Bruch \( \frac{a}{b} \) ist vollständig gekürtzt, wenn \( a \perp b\).\\
|
|
\( \frac{16}{9} \) ist vollständig gekürzt, \( 16 \perp 9 \).
|
|
|
|
Frage: Warum gibt es unendlich viele Primzahlen?\\
|
|
Annahme: Es gibt nur k verschiedene Primzahlen \(p_1, \dots, p_k \)\\
|
|
Konstruiere eine weitere Prizahl \( P := p_1 \cdot p_2 \cdot \dots \cdot p_k + 1 \)\\
|
|
\begin{itemize}
|
|
\item p ist nicht teilbar durch \( p_1,p_2, \dots, p_k \)
|
|
\item also: Die PFZ von p enthält keine der Primzahlen \( p_1, \cdot , p_k\), also muss sie aus „neuen“ Primzahlen bestehen.
|
|
\end{itemize}
|
|
\(\Rightarrow \) Widerspruch. \(\square\)
|
|
|
|
\underline{Primzahlsatz:}\\
|
|
\( \pi(n) := \left| \{ p \le n \mid p \text{ ist Primzahl } \} \right| \)\\
|
|
(Anzahl Primzahlen \( \le n \))\\
|
|
\( \pi(n) \underset{\text{asymptotisch äquivalent}}{\sim} \frac{n}{\log n} \left( \pi(n) \cdot \frac{\log n}{n} \underset{n \to \infty}{\longrightarrow} 1 \right)\)
|
|
|
|
\subsection{Kongruenzen}
|
|
|
|
Es seien \( a,b,m \in \mathbb Z, m > 0 \).\\
|
|
\( a \equiv b (\mod m) : \Leftrightarrow a \mod m = b \mod m \Leftrightarrow m | (a-b) \)\\
|
|
„a ist kongruent zu b modulo m“
|
|
|
|
Wir haben bereits gesehen (Aufgabe 3.5 zur Vorlesung) dass \(\equiv\) (mod m) eine Äquivalenzrelation ist. Diese hat m verschiedene Äquivalenzklassen:\\
|
|
\( [0]_{\equiv \mod m} = \{ t \cdot m + 0 \mid t \in \mathbb Z \} \)\\
|
|
\( [1]_{\equiv \mod m} = \{ t \cdot m + 1 \mid t \in \mathbb Z \} \)\\
|
|
...\\
|
|
\( [m-1]_{\equiv \mod m} = \{ t \cdot m + (m-1) \mid t \in \mathbb Z \} \)
|
|
|
|
\underline{zum Rechnen mit Resten:}\\
|
|
\((a+b) \mod m = (a + (b \mod m) ) \mod m\):\\
|
|
\(a + (b \mod m) = a + b - \lfloor \frac{b}{m} \rfloor m \)\\
|
|
\( \curvearrowright (a + (b \mod m)) \mod m \)\\
|
|
\( = (a + b - \lfloor \frac{b}{m} \rfloor m) - \lfloor \frac{a + b - \lfloor \frac{b}{m} \rfloor m}{m} \rfloor m \)\\
|
|
\( = a+b-\lfloor \frac{b}{m} \rfloor m - (-\lfloor\frac{b}{m} + \lfloor\frac{a+b}{m}\rfloor)m \)\\
|
|
\( = a+b- (\lfloor\frac{a+b}{m}\rfloor)m \)\\
|
|
\( = (a+b) \mod m \)
|
|
|
|
\( \Rightarrow (a+b) \mod m = (a + (b \mod m))\mod m \)\\
|
|
\( = ((a \mod m) + (b \mod m) ) \mod m\)\\
|
|
vertausche Rollen von a und b\\
|
|
\begin{itemize}
|
|
\item analog: \( (a-b) \mod m = ( (a\mod m) - (b\mod m) ) \mod m \)
|
|
\item \((a \cdot b) \mod m = ( \underbrace{a + \dots + a}_{\text{b-mal}} ) \mod m \)\\
|
|
\( = ( \underbrace{(a\mod m) + \dots + (a\mod m)}_{\text{b-mal}} ) \mod m\)\\
|
|
\( = ( (a\mod m) \cdot b ) \mod m\)\\
|
|
\( = ( (a\mod m) \cdot(b\mod m)) \mod m\)
|
|
\end{itemize}
|
|
|
|
\underline{Bsp.:}
|
|
\( (3.8 \dot 10^9 + 378956743) \mod 5 \) \\
|
|
\( = ((3.8 \dot 10^9 \mod 5) + (378956743 \mod 5)) \mod 5 \)\\
|
|
\( = (0+3) \mod 5 = 3 \)
|
|
|
|
\underline{Rechenregeln für Kongruenzen}\\
|
|
Es seien \( a \equiv b (\mod m), c \equiv d (\mod m)\)\\
|
|
\( \Rightarrow (a+c) \equiv b+d (\mod m)\)\\
|
|
\spa\( (a-c) \equiv b-d (\mod m)\)\\
|
|
\spa\( (a\cdot c) \equiv b\cdot d (\mod m)\)\\
|
|
Beweis:\\
|
|
\spa\( a \pm c \equiv a \pm d (\mod m)\)\\
|
|
\(\Leftrightarrow m | \underbrace{(a \pm b) - (c \pm d)}_{= (a-b) \pm (c-d)} \)\\
|
|
\( m | (a-b), m | (c-d) \)\\
|
|
\( \Rightarrow m | \left[ (a-b) \pm (c-d) \right] \) \checkmark
|
|
|
|
\( a\cdot c \equiv b \cdot d (\mod m)\)\\
|
|
\( \Leftrightarrow m | \underbrace{a\cdot c - b \cdot d}{} \)\\
|
|
\( = a\cdot c - b \cdot c + b \cdot c - b\cdot d \)\\
|
|
\( = \underbrace{(a-b)}{}\cdot c + b \cdot \underbrace{(c-d)}{} \quad \Box \)\\
|
|
\spa\spa Vielfache von m
|
|
|
|
\underline{Inverse modulo m}\\
|
|
Wann gibt es \( x \in \mathbb Z \) mit\\
|
|
\spa \( a\cdot x \equiv 1 (\mod m)\) ?
|
|
\begin{itemize}
|
|
\item falls ggT(a,m) = 1:\\
|
|
erweiterter Euklidischer Algorithmus liefert \(x,y \in \mathbb Z\) mit\\
|
|
\spa \( a\cdot x + m \cdot y = ggT(a,m) = 1\)\\
|
|
\( \Rightarrow \underbrace{a\cdot x = m\cdot y}_{\equiv 1} = a\cdot x (\mod m) \)\\
|
|
\( \Rightarrow x\) aus dem erw. Eukl. Alg. ist genau das Inverse von a.\\
|
|
Bez.: \( x = a^{-1} \) oder \( x = a^{-1}_{\mod m} \)
|
|
\item falls \( d := ggt(a,m) > 1 \):\\
|
|
\( (a\cdot x) \mod m = \underbrace{a\cdot x - \llfloor \frac{a\cdot x}{m} \rrfloor m}_{\text{teilbar durch d}} \)\\
|
|
\( \Rightarrow d | (a\cdot x) \mod m\),\\
|
|
aber \( d \not| 1\)\\
|
|
\( \Rightarrow (a\cdot x) \mod m \ne 1 \mod m \)\\
|
|
\( \Leftrightarrow a \cdot x \not\equiv 1 (\mod m) \)\\
|
|
Also hat a kein Inverses modulo m.
|
|
\end{itemize}
|
|
Man kann zeigen:\\
|
|
Falls \(a \perp m\), dann gibt es ein eindeutiges Inverses \(a^{-1}_{\mod m} \in \mathbb Z_m := \{0,1,\dots,m-1\} \)
|
|
|
|
Menge der Zahlen mit Inversen modulo m:\\
|
|
\( \mathbb Z^x_m := \{ a \in \mathbb Z_m \mid a \perp m \} \)
|
|
|
|
\underline{Bsp.:}\\
|
|
\( \mathbb Z^x_2 =\{ 1 \}, Z^x_3 = \{ 1,2 \} \)\\
|
|
\( ( 1^{-1} = 1, 2^{-1} = 2 : 2 \cdot 2 \mod 3 = 1 ) \)\\
|
|
\( \mathbb Z^x_4 = \{1,3\}, \mathbb Z^x_5 = \{1,2,3,4\} \) \\
|
|
\( \mathbb Z^x_6 = \{1,4,5\} \)
|
|
|
|
Damit lassen sich lineare Kongruenzen lösen:\\
|
|
\spa \( a\cdot x \equiv b (\mod m) \)\\
|
|
mit \( a \in \mathbb Z^x_m, b \in \mathbb Z_m \)\\
|
|
\spa \( x:= a^{-1} \cdot b \mod m \)\\
|
|
\(\rightarrow a\cdot x = a(a^{-1} \cdot b) \mod m\)\\
|
|
\spa \(\equiv \underbrace{(a\cdot a^{-1})}_{\equiv 1} \cdot b \equiv b (\mod m) \)\\
|
|
Diese Lösung für \(x\) ist eindeutig in \(\mathbb Z_m\).
|
|
|
|
„Wie groß ist \(\mathbb Z^x_m\)?“\\
|
|
\defin \( \phi(m) := | \mathbb Z^x_m | \)
|
|
|
|
\underline{Eulersche Phi-Funktion}\\
|
|
Wir wissen:
|
|
\begin{itemize}
|
|
\item falls p Primzahl ist: \( \phi(p) = | \{1,...,p-1\} | = p-1 \).
|
|
\item für Primzahlpotenzen gilt:\\
|
|
\( \phi(p^k) = | \mathbb Z_{p^k} \backslash \{0,p,2\cdot p, 3 \cdot p,... , p^k-p\} | \)\\
|
|
größtes Vielfaches von \( p \le p^k \) ist \(p^k\); ... \(p < p^k\) ist \( p^k - p\)\\
|
|
\( \curvearrowright \phi(p^k) = | \mathbb Z_{p^k} | - | \{ 0,p,2p, ... , p^k - p \}| \)\\
|
|
\spa \( = p^k - \frac{p^k}{p} = p^k - p^{k-1} = p^k(1-\frac{1}{p}) \)\\
|
|
\underline{Bsp.:}\\
|
|
\(|\mathbb Z^x_{125}| = \phi(125) \)\\
|
|
\( = \phi(5^3) = 5^3(1-\frac{1}{5}) = 100 \)
|
|
\item allgemeiner Fall: \( m = \prod\limits_{i=1}^{k} p_i^{m_i} \leftarrow \) Primfaktorzerlegung\\
|
|
\(\phi(m) = \phi\left( \prod\limits_{i=1}^{k} p_i^{m_i}\right) = ? \)\\
|
|
Zusammenhang zwischen\\
|
|
\( \mathbb Z_{p_1^{m_k} ... p_k^{m_k} }^x \) und \( \mathbb Z_{p_1^{m_k} }, ...,\mathbb Z _{p_k^{m_k} }^x \) ?
|
|
\end{itemize}
|
|
|
|
\underline{Chinesischer Restsatz}\\
|
|
Gibt es eine Lösung \(x\) des Systems von Kongruenzen?\\
|
|
\( c_1 \cdot x \equiv d_1 (\mod m) \)\\
|
|
\( c_2 \cdot x \equiv d_2 (\mod n ) \)\\
|
|
(Hierbei seien \(c_1 \in \mathbb Z^x_m, c_2 \in \mathbb Z^x_n, d_1,d_2 \in\mathbb Z\) )\\
|
|
Multipliziere mit \( c_1^{-1} , c_2^{-1} \)\\
|
|
\spa \(x \equiv c_1^{-1} d_1 (\mod m) \)\\
|
|
\spa \(x \equiv c_2^{-1} d_2 (\mod m) \)\\
|
|
setze:\\
|
|
\spa \( a := c_1^{-1} \cdot d_1 \in \mathbb Z_m,\)\\
|
|
\spa \( b := c_2^{-1} \cdot d_2 \)\\
|
|
Ansatz: \(x = y \cdot m + z \cdot n \) mit \( y,z \in \mathbb Z\)\\
|
|
\(\rightarrow x \mod m = z \cdot n \mod m \overset{!}{\equiv} a \)\\
|
|
\spa \( x \mod n = y \cdot m \mod n \overset{!}{\equiv} b \)\\
|
|
löse also \( z \cdot n \equiv a (\mod m) \) nach z\\
|
|
auf, \( y \cdot m \equiv b (\mod n) \) nach y.\\
|
|
|
|
Falls \(m \perp n\):\\
|
|
\spa \(z = a \cdot n^{-1}_{\mod m}, y = b \cdot m^{-1}_{\mod n} \)\\
|
|
\( \Rightarrow x = b \cdot m^{-1}_{\mod n} \cdot m + a \cdot n^{-1}_{\mod m} \cdot n \)\\
|
|
Man kann zeigen: x ist eindeutig bis auf Vielfache von \( m \cdot n \).\\
|
|
Zu jedem Paar \((a,b) \in \mathbb Z_m \times \mathbb Z_n \) gibt es eine eindeutige Lösung \( x \in \mathbb Z_{m\cdot n}\).\\
|
|
Definiere die Funktion \( \psi: \mathbb Z_{m\cdot n} \to \mathbb Z_m \times \mathbb Z_n \);\\
|
|
\( \psi(x) := ( x \mod m, x \mod n) \).\\
|
|
\(\psi\) ist also bijektiv.\\
|
|
\( \curvearrowright | \mathbb Z_{m \cdot n} | = | \mathbb Z_m \times \mathbb Z_n | = |\mathbb Z_m| \cdot |\mathbb Z_n| \)
|
|
|
|
Eigenschaften vo \(\psi\):
|
|
\begin{itemize}
|
|
\item \(\psi\) ist bijektiv
|
|
\item \(\psi(1) = (1,1)\) \\
|
|
\(\psi(0) = (0,0)\)
|
|
\item \(\psi((x+y) \mod (m\cdot n)) = \psi(x) +\psi(y) \),\\
|
|
wobei \( (a,b) + (c,d) := (a+c \mod m, b+d \mod n) \)
|
|
\item \(\psi(x \cdot y) \mod (m\cdot n) = \psi(x)\cdot \psi(y) \),
|
|
mit \((a,b)(c,d) = ( (a\cdot c) \mod m, (b\cdot d) \mod n) \)
|
|
\end{itemize}
|
|
\spa \( (x \cdot y ) \mod (m\mod n) = x \cdot y - \llfloor \frac{x\cdot y}{m \cdot n} \rrfloor \cdot m \cdot n \)\\
|
|
\( \curvearrowright (x \cdot y ) \mod (m\mod n) \equiv x \dot y (\mod m) \)\\
|
|
\spa \( (x \cdot y ) \mod (m\mod n) \equiv x \cdot y (\mod n) \)\\
|
|
\( \Rightarrow \psi( (x\cdot y) \mod (m\cdot n) ) = ( (x\cdot y) \mod m, (x\cdot y) \mod n ) \)\\
|
|
\spa\spa\( = ( (x \mod m)(y\mod m) \mod m, (x \mod n)(y\mod n) \mod n) \)\\
|
|
\spa\spa\( = \psi(x) \cdot \psi(x) \)\\
|
|
\begin{tabular}{ccc}
|
|
Eingaben \( \in \mathbb Z_{m\cdot n} \) & \spa \( \underset{\psi}{\longrightarrow} \)\spa & Eingabe \( \in \mathbb Z_m \times \mathbb Z_n \)\\[5mm]
|
|
Richtung in \( \mathbb Z_{m\cdot n} \downarrow\) & & \(\downarrow\)Richtung in \( \mathbb Z_m \times \mathbb Z_n\)\\[5mm]
|
|
Ergebnis in \( \mathbb Z_{m\cdot n } \) & \spa\( \underset{\psi^{-1}}{\longleftarrow} \)\spa & Ergebnis in \(\mathbb Z_m \times \mathbb Z_n\)
|
|
\end{tabular}
|
|
|
|
\( (x\cdot y ) \mod (m \cdot n) = 1\)\\
|
|
\( \Leftrightarrow \psi(x) \cdot \psi(y) = \psi( (x\cdot y) \mod (m\cdot n) ) = (1,1) \)\\
|
|
Also: \( (x_1,x_2) := \psi(x), (y_1,y_2) := \psi(y)\)\\
|
|
\( \Rightarrow x_1 \dot y_1 \mod m = 1 \),\\
|
|
\spa \( x_2 \dot y_2 \mod m = 1 \)\\
|
|
also: \( x_1 \in \mathbb Z^x_m\)\\
|
|
\spa \(x_x \in \mathbb Z^x_n\).
|
|
|
|
\(\psi\) ist also auch eine Bijektion zwischen \(\mathbb Z^x_{m\cdot n} \) und \( \mathbb Z^x_m \times \mathbb Z^x_n \).\\
|
|
\( \Rightarrow | \mathbb Z^x_{m\cdot n} | = | \mathbb Z^x_m \times \mathbb Z^x_n | = |\mathbb Z^x_m| \cdot |\mathbb Z^x_n| \)\\
|
|
Konsequenz für \( \phi\left( \prod\limits_{i=1}^{k} p_i^{m_i} \right) \):\\
|
|
\spa \( p_i^{m_i} \perp p_j^{m_j} \quad \text{ für } i \ne j \)\\
|
|
\( \curvearrowright | \mathbb Z^x_{p_1^{m_1} ... p_k^{m_k}} | = | \mathbb Z^x_{p_1^{m_1}} | ... | \mathbb Z^x_{p_k^{m_k}} | \)\\
|
|
\( = p_1^{m_1} \left( 1-\frac{1}{p_1} \right) ... p_k^{m_k} \left( 1-\frac{1}{p_k} \right) \)\\
|
|
\( m \prod\limits_{p | m} \left(1 - \frac{1}{p}\right) \)
|
|
|
|
\underline{Bsp.:} \( \phi(100) = | \mathbb Z_{100}^x | \)\\
|
|
\( = \phi(2^2 \cdot 5^2) = 100 \cdot \underbrace{(1 - \frac{1}{2})}_{=\frac{1}{2}} \cdot \underbrace{(1 - \frac{1}{5})}_{=\frac{4}{5}} \)\\
|
|
\( = 40 \)
|
|
|
|
\( \phi(2) = 2\cdot \left(1-\frac{1}{2}\right) = 1 \)\\
|
|
\( \phi(3) = 3\cdot \left(1-\frac{1}{3}\right) = 2 \)\\
|
|
\( \phi(4) = 4\cdot \left(1-\frac{1}{2}\right) = 2 \)\\
|
|
\( \phi(5) = 5\cdot \left(1-\frac{1}{5}\right) = 4 \)\\
|
|
\( \phi(6) = 6 \cdot \left(1-\frac{1}{2}\right) \cdot \left(1-\frac{1}{3}\right) = 2 \)
|
|
|
|
\newpage
|
|
\section{Algebra}
|
|
|
|
algebraische Strukturen, Beispiele:\\
|
|
\begin{tabular}{l|l}
|
|
Gruppe: & \( (S_n, \circ), (\mathbb Z^x_m, \cdot ), (\mathbb Z, +) \)\\
|
|
\hline
|
|
Ring: & \( (\mathbb Z,+, \cdot) , \mathbb Z, + , \cdot ) \)\\
|
|
\hline
|
|
Körper & \( \mathbb R, \mathbb Q, \mathbb Z_p \) (p Primzahl)\\
|
|
\hline
|
|
Vektorräume & \( \mathbb R^3 \)\\
|
|
\end{tabular}
|
|
|
|
\subsection{Gruppen}
|
|
|
|
\defin Gegeben seien eine Menge G und eine binäre Operation \(*\): \( G \times G \mapsto G \).\\
|
|
(G,\(*\)) heißt \underline{Gruppe}, falls folgende Axiome gelten:\\
|
|
\begin{tabular}{lll}
|
|
(G1) & \( \forall a,b,c \in G: (a * b) * c = a * ( b * c ) \) & (assoziativgesetz)\\
|
|
(G2) & \( \exists e\in G: \forall a \in G: a * e = a \) & (neutrales Element)\\
|
|
(G3) & \( \forall a \in G: \exists a^{-1} \in G: a \cdot a^{-1} = e \) & (Inverses)\\
|
|
\multicolumn{3}{l}{(G,\(*\)) heißt \underline{Abelsche} oder \underline{kommutative Gruppe}, wenn zusätzlich gilt:}\\
|
|
(G4) & \( \forall a,b \in G: a * b = b * a \). &
|
|
\end{tabular}
|
|
|
|
\underline{Bem.:} Wenn die Verknüpfung \(*\) aus dem Kontext hervorgeht, bezeichnet man auch G als Gruppe.
|
|
|
|
\underline{Beispiele:}
|
|
\begin{enumerate}
|
|
\item \((\mathbb Z,+)\) ist eine Kommutative Gruppe:\\
|
|
\begin{tabular}{lll}
|
|
(G1) & \( (a+b) + c = a + (b+c) \) & \checkmark\\
|
|
(G2) & \( a + 0 = a \) & \checkmark\\
|
|
(G3) & \( a^{-1} := -a; a + (-a) = 0 \) & \checkmark\\
|
|
(G4) & \( a + b = b + a \) & \checkmark
|
|
\end{tabular}
|
|
\item \( (\mathbb Z^x_m, \cdot) \)\\
|
|
\begin{tabular}{lll}
|
|
(G1) & \( ( (a\cdot b) \mod m \cdot c ) \mod m = (a \cdot ((b\cdot c )\mod m)) \mod m \) & \checkmark\\
|
|
(G2) & \( a \cdot 1 \mod m = a \) & \checkmark\\
|
|
(G3) & \( \exists a^{-1} \in \mathbb Z^x_m: a\cdot a^{-1} \mod m = 1 \) & \checkmark\\
|
|
(G4) & \( (a\cdot b) \mod m = (b\cdot a)\mod m \) & \checkmark\\
|
|
\( \rightsquigarrow \) & \( (\mathbb Z^x_m, \cdot) \) ist eine kommutative Gruppe
|
|
\end{tabular}
|
|
\item aber: \((\mathbb Z_m,\cdot)\) ist keine Gruppe, weil z.\,B. \( 0 \in \mathbb Z_m \) kein Inverses besitzt.
|
|
\item \( (S_n, \circ)\) ist eine Gruppe, aber nicht Kommutativ:\\
|
|
\begin{tabular}{lll}
|
|
(G1) & & \checkmark\\
|
|
(G2) & \(id: x \mapsto x, \sigma \circ id = \sigma \) & \checkmark\\
|
|
(G3) & \( \exists \sigma^{-1} \in S_n: \sigma \circ \sigma^{-1} = id \) & \checkmark\\
|
|
(G4) & \( (12) \circ (23) = (123) \ne (23) \circ (12) = (132) \) &
|
|
\end{tabular}
|
|
\end{enumerate}
|
|
|
|
Es gilt stets:\\
|
|
\begin{enumerate}
|
|
\item \( a^{-1} * a = e \)
|
|
\item \( e * a = a^{-1} \)
|
|
\item \( ( a^{-1})^{-1} = a \)
|
|
\item \( (a*b )^{-1} = b^{-1} * a^{-1} \)
|
|
\end{enumerate}
|
|
|
|
%TODO
|
|
%\begin{enumerate}
|
|
% \item \( a^{-1} * a = a^{-1} * \underbrace{a *
|
|
%\end{enumerate}
|
|
|
|
Eindeutigkeit des Inversen\\
|
|
\( \curvearrowright (a * b)^{-1} = b^{-1} * a^{-1} \Box\)\\
|
|
|
|
Die Gleichungen\\
|
|
\( a * x = b, \quad y * a = b\)\\
|
|
besitzen die eindeutigen Lösungen:\\
|
|
\( x = a^{-1} * b, \quad y = b * a^{-1} \).\\
|
|
(Es sei \( a * x= b = a * x' \) )\\
|
|
\( \Rightarrow x = a^{-1} * (a * x) = a^{-1} * (a * x') = x' \)\\
|
|
Die Eindeutigkeit von y folgt analog.\\
|
|
Folgerung: Das neutrale Element und die inversen Elemente sind Eindeutig
|
|
|
|
\underline{Untergruppen}
|
|
|
|
\defin \((G,*), (U,*)\) seien Gruppen, \( U \subseteq G\)
|
|
Dann heißt U \underline{Untergruppe} von G\\
|
|
(Schreibweise: \(U \le G\))
|
|
|
|
\underline{Bsp.:}\\
|
|
\( (\mathbb Z,+) \le (\mathbb Q,+) \le (\mathbb R,+) \)
|
|
\begin{itemize}
|
|
\item Es sei G eine endliche Gruppe, \( a \in G \).\\
|
|
\( <a> := \{a^0,a,a^2,a^3,... \} \)\\
|
|
( \( a^n = \underbrace{a * ... * a}_{\text{n-mal a}} \) )\\
|
|
\( a^0 = e \)
|
|
\( <a> \) heißt die von a \underline{erzeugte Gruppe}.\\
|
|
\( <a> \) ist die kleinste Untergruppe von G, die a enthält.\\
|
|
Beispiel: \( G = \mathbb Z_7^* = \{1,2,3,4,5,6\} \)\\
|
|
\( \curvearrowright <2> = \{1,2,2^2=4,2^3\equiv 1 (\mod 7)\} = \{1,2,4\} \),\\
|
|
\( <2> \le \mathbb Z_7^* \)\\
|
|
Bem.: Jede Gruppe G hat zwei triviale Untergruppen, \( G \le G \) und \( \{e\} \le G \). Alle anderen Untergruppen von G sind nichttrivial.
|
|
|
|
\end{itemize}
|
|
|
|
\underline{Satz von Lagrange}\\
|
|
Es seien \(U \le G\) Gruppen , \(G\) endlich. Dann ist \( |U|\, \big|\, |G| \) ,
|
|
|
|
\defin Für \( x \in G \) definiert man die \underline{Nebenklasse} von U in G,\\
|
|
\( x * U := \{ x * a \mid a \in U \} \)\\
|
|
\underline{Bsp.:} \((Z_6,+) \ge <3> = \{0,3\} \)\\
|
|
Nebenklassen von \(<3>\) in \(\mathbb Z_6 \):\\
|
|
\( 0 + <3> = \{0+0,0+3\} = \{0,3\} = 3 + <3> \)\\
|
|
\( 1 + <3> = \{1+0,1+3\} = \{1,4\} = 4 + <3> \)\\
|
|
\( 2 + <3> = \{2+0,2+3\} = \{2,5\} = 5 + <3> \)
|
|
|
|
Die Nebenklassen von \( U \text{ in } G\)bilden eine Partition von \(G\):\\
|
|
\begin{enumerate}
|
|
\item Überdeckung: \( \underset{x \in G}{\cup} (x*U) \overset{!}{=}G \)\\
|
|
Es sei \( x\in G\) beliebig gewählt.\\
|
|
\( \Rightarrow x \in x * U\), denn \( x = x * e \in x * U\)\\
|
|
\( \curvearrowright G \subseteq \underset{c \in G}{\cup} (x * U) \) \checkmark
|
|
\item Disjunktheit:\\
|
|
Es sei \( z \in (x * U ) \land (y * U) \ne \emptyset \)\\
|
|
zu zeigen: \( x * U = y * U\)\\
|
|
(wir zeigen: \(x * U \subseteq y * U; x * U \supseteq y * U \) folgt analog )\\
|
|
Es sei \( a \in x * U, a = x * a_x\) mit \( a_x \in U \).\\
|
|
\( z = x * z_x = y * z_y, \text{ wobei } x_z,z_y \in U. \)\\
|
|
\( a = x * a_x = ( x * z_x) * z_x^{-1} * a_x \)\\
|
|
\( = (x* \underbrace{z_y) * z_x^{-1} * a_x}_{\in U } \)\\
|
|
\( \Rightarrow a \in y + U. \quad \Box\)
|
|
\item Alle Nebenklassen \( x * I \) sind gleichmächtig.\\
|
|
(Beweisidee: Finde eine Bijektion zwischen \(x * U \) und \(e*U, |e*U| = |U|\))
|
|
\end{enumerate}
|
|
|
|
\underline{Beweis des Satzes von Lagrange}
|
|
|
|
Wähle \( M \subseteq G\), so dass:\\
|
|
\spa \( G = \underset{x\in M}{\uplus} (x*U) \) d.\,h. \( x_1 * U \ne x_2 * U, \text{ für } x_1 \ne x_2\)\\
|
|
\( |G| = \sum\limits_{x\in M} |x*U| = \sum\limits_{x \in M} |U| = |M| \cdot |U|\)\\
|
|
\( \rightarrow |U| \cdot |G| \quad \Box \)
|
|
|
|
Es sei G eine endliche Gruppe, \( a \in G \).\\
|
|
Betrachte \(<a> := \{a^0,a^1,a^2,...\} \)\\
|
|
G ist endlich. \( \Rightarrow \exists s,t \in \mathbb N: a^s = a^t , s < t \).\\
|
|
\(\Rightarrow a^{t-s} = e \)\\
|
|
D.\,h. \( \exists n>0: a^n = e \quad (n=t-s) \)
|
|
|
|
\defin Die \underline{Ordnung} von \(a\), \(ord(a)\) ist die kleinste Zahl \( n>0 \), so dass \(a^n = e\).\\
|
|
\(\Rightarrow <a> = \{ a^1,a^2,a^3,...,a^{ord(a)} = e \}\)\\
|
|
also: \(|<a>| = ord(a) \)
|
|
|
|
\underline{Folgerung:}\\
|
|
\( <a> \le G \overset{\text{Lagrange}}{\Rightarrow} |G| = m \cdot |<a>|, \)\\
|
|
\( a^{|G|} = \left(a^{|<a>|}\right)^m = \underbrace{\left( a^{ord(a)} \right)^m}_{=e} = e. \)
|
|
|
|
\underline{Beispiele:}
|
|
\begin{itemize}
|
|
\item \underline{Satz von Fermat}\\
|
|
Es sei p eine Primzahl, \( a \in \{ 1,...,p-1\} \).\\
|
|
\( \Rightarrow a^{p-1} = a^{|\mathbb Z_p^x|} \equiv 1 (\mod p)\).
|
|
\item \underline{Satz von Euler}:\\
|
|
Es sei \( n>1; |\mathbb Z_n^x| = \phi(n), a \in \mathbb Z_n^x \)\\
|
|
\(\rightarrow a^{\phi(n)} = a^{|\mathbb Z_n^x|} \equiv 1 (\mod n)\)
|
|
\end{itemize}
|
|
|
|
\underline{Beispiel:}\\
|
|
\( 7^{243} \mod 300 = ? \)\\
|
|
\( |\mathbb Z_{300}^x| = \phi(300) = \phi(2^2 \cdot 3 \cdot 5^2) \)\\
|
|
\( = 300 \cdot (1-\frac 1 2) \cdot (1-\frac 1 3) \cdot (1-\frac 1 5) \)\\
|
|
\( = 300 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} = 10 \cdot 2 \cdot 4 = 80 \)\\
|
|
\( \underset{7 \perp 300}{\overset{\text{Euler}}{\rightarrow}} 7^{80} \equiv 1 ( \mod 300),\)\\
|
|
\( 7^{243} = \underbrace{(7^{80})^3}_{\equiv 1} \cdot 7^3 \equiv 7^3\equiv 343 (\mod 300) \equiv 43 (\mod 300) \)
|
|
|
|
n zusammengesetz, keine Camichael-Zahl:\\
|
|
\( U:= \{ a\in \mathbb Z_n^x \mid a^{n-1} \equiv 1 (\mod n) \} \ne \mathbb Z_n^x\)\\
|
|
Falls \( U\le \mathbb Z_n^x \):\\
|
|
\( |u| \big| | \mathbb Z_n^x| \rightarrow | \mathbb Z_n^x | = m \cdot |U| \)\\
|
|
\( \rightarrow |U| \le \frac 1 2 | \mathbb Z_n^x| \)
|
|
|
|
Ist \( U \le \mathbb Z_n^x \)?\\
|
|
\( \mathbb Z_n^x\) ist endlich \(\Rightarrow\) Prüfe (G0) !\\
|
|
Wähle \(a,b \in U\) beliebig.\\
|
|
\( \Rightarrow (ab)^{n-1} = \underbrace{a^{n-1}}_{\equiv 1} \cdot \underbrace{b^{n-1}}_{\equiv 1} \equiv 1 (\mod n) \)\\
|
|
\(\Rightarrow ab \in I\), also: \( U \le G = \mathbb Z_n^x\)
|
|
|
|
\underline{RSA-Public-Key-Kryptosystem}
|
|
|
|
geheime Nachricht: \(m \in \mathbb Z_n\)\\
|
|
verschlüsselte Nachricht: \( c \in \mathbb Z_n \)
|
|
|
|
Schlüsselkonstruktion:\\
|
|
\begin{enumerate}
|
|
\item Primzahlen \(p\ne q, n := p\cdot q\)\\
|
|
\( \phi(n) = n(1-\frac 1 p)(1- \frac 1 q) = (p-1)(q-1)\)
|
|
\item geheimer Schlüssel:\\
|
|
Zufallszahl \(d\) (für „decryption“)\\
|
|
\(\in \mathbb Z_{\phi(n)}^x\)
|
|
\item öffentlicher Schlüssel:\\
|
|
\( (\underbrace{d^{-1}_{\mod \phi(n)}}_{mit Euklid} , n) \)\\
|
|
„encryption“ := e
|
|
\end{enumerate}
|
|
Protokoll:\\
|
|
\begin{tabular}{ccc}
|
|
A & & B\\
|
|
&& \(m\)\\
|
|
&& \( \rightarrow c := m^e (\mod n)\)\\
|
|
& \(\swarrow\) & \\
|
|
berechtet && \\
|
|
\(c^d \mod n = m\) &&
|
|
\end{tabular}
|
|
|
|
\underline{1. Fall:}\\
|
|
\begin{align*}
|
|
m \perp n, m \in \mathbb Z_n^x\\
|
|
\Rightarrow c^d \equiv (m^e)^d &\equiv m^{e\cdot d} (\mod n)\\
|
|
m^{\mathbb Z_n^x} = m^{\phi(n)} &\equiv 1 (\mod n)\\
|
|
\rightarrow c^d \equiv m^{e\cdot d} &\equiv m^{(e\cdot d) \mod \phi(n)} \equiv m^1 (\mod n)
|
|
\end{align*}
|
|
|
|
\underline{2. Fall:}\\
|
|
\(ggT(m,n) > 1, \text{ entweder } ggT(m,n) = p \text{ oder } ggT(m,n) = q\)\\
|
|
hier: \( ggT(m,n) = p \)
|
|
|
|
Chinesischer Restsatz:\\
|
|
Der Lösung von \(x \equiv m^{e\cdot d} (\mod n) \) (t) \\
|
|
entspricht genau einer Lösung von\\
|
|
\( x \equiv m^{e\cdot d} (\mod p) (*)\)\\
|
|
\( x \equiv m^{e\cdot d} (\mod q) (*)\)\\
|
|
Wir zeigen, dass \( x = m \) die von \((*)\) ist, und deshalb auch von (t)
|
|
|
|
\( p | m \Rightarrow m \equiv0 (\mod p) \)\\
|
|
\( \curvearrowright m^{e\cdot d} \equiv 0^{e\cdot d} = 0 (\mod p)\)\\
|
|
\(\Rightarrow m \equiv m^{e\cdot d} (\mod p) \);\\
|
|
\( m \perp q; ed = 1(\mod (p-1)(q-1) )\)\\
|
|
\(\rightarrow \exists k \in \mathbb Z: ed = 1 + k \cdot (p-1)(q-1) \)\\
|
|
modulo \( |\mathbb Z_q^x| = \phi(q) = q-1\):
|
|
\( ed = 1 + [ k(p-1) ] \cdot (q-1) \)\\
|
|
\( \Rightarrow ed \equiv 1 (\mod (q-1))\)\\
|
|
\( m^{ed} \equiv m^{ed \mod q-1} \equiv m^1 (\mod q) \)\\
|
|
also: m ist die eindeutige Lösung \( \in \mathbb Z_n\) von \((*)\).
|
|
|
|
\( \rightarrow \) Entschlüsselung liefert tatsächlich m.
|
|
|
|
|
|
Entschlüsselung ist möglich, wenn \(\phi(n)\) bekannt ist. Warum ist \(\phi(n)\) schwierig zu bestimmen?\\
|
|
Primfaktor \( \overset{\text{leicht}}{\rightarrow} \phi(n)\) \\
|
|
Primfaktor \( \underset{\text{leicht?}}{\leftarrow} \phi(n)\) \\
|
|
\(\phi(n) = (p-1)(q-1) \)\\
|
|
\(\Rightarrow\) betrachte:\\
|
|
\(f(x) = x^2 - (n-\phi(n)+1) x + n = x^2 - (pq- [ pq - p - q +1] +1 ) x + n \)\\
|
|
\( = x^2 - (n-\phi(n)+1) x + n = x^2 - (p + q) x + pq \)\\
|
|
\( = (x-p)(x-q) \)\\
|
|
f(x) hat genau die Nullstellen p und q, \( \phi(n) \) zu berechnen ist also ebenso schwierig wie die PFZ zu bestimmen.
|
|
|
|
\section{Exkurs: Polynome}
|
|
|
|
Polynom: \( p(x) := \sum\limits_{i=0}^{n} a_i \cdot x^i \) mit \( a_0, ... , a_n \in \mathbb R \)\\
|
|
Der \underline{Grad} von \(p\) ist \(n\), falls \(a_n \ne 0 \).\\
|
|
Abkürzung: \( n = grad(p) \)
|
|
|
|
Aufwand zur Berechnung von \(p(x_0)\):\\
|
|
\( p(x_0) = a_n \cdot x_0^n + a_{n-1} \cdot x_0^{n-1} + ... + a_1 \cdot x_0^1 + a_0 \)\\
|
|
\( \Rightarrow\) Aufwand: \(n\) Additionen, \(2n-1\) Multiplikationen.\\
|
|
effizienter: Horner-Schema\\
|
|
\begin{align*}
|
|
p(x_0) &= \underbrace{a_n \cdot x_0^n + a_{n-1} \cdot x_0^{n-1}} + a_{n-2} \cdot x_0^{n-2} + ... + a_0\\
|
|
&= \underbrace{ (a_n \cdot x_0 + a_{n-1} ) \cdot x_0^{n-1} + a_{n-2} \cdot x_0^{n-2} } + ... + a_0\\
|
|
&= \underbrace{ ((a_n \cdot x_0 + a_{n-1} ) \cdot x_0 + a_{n-2} ) x_0^{n-2} + ... + a_0}\\
|
|
&= (( ... (a_n\cdot x_0 + a_{n-1})x_0 + ... ) +a_1) x_0 + a_0
|
|
\end{align*}
|
|
\( \Rightarrow \) Aufwand: n Additionen, n Multiplikationen
|
|
|
|
Rechnen mit Polynomen:\\
|
|
es seien \(a(x) := \sum\limits_{i=0}^m a_i \cdot x^i, b(x) = \sum\limits_{i=0}^n n_i \cdot x^i \)\\
|
|
zwei Polynome, \( a_m \ne 0 \ne b_n (m \ge n) \)
|
|
\begin{itemize}
|
|
\item Summe: \(a(x) + b(x) = \sum\limits_{i=0}^m (a_i + b_i) x^i \)\\
|
|
\((b_{n+1}, ... b_m := 0\)
|
|
\item DIfferenz: analog
|
|
\item Produkt: \(a(x) \cdot b(x) = ( \sum\limits_{i=0}^m a_i \cdot x^i)( \sum\limits_{i=0}^n b_i \cdot x^i) \)\\
|
|
\( = \sum\limits_{i=0}^{m+n} c_i \cdot x^i \) mit \( c_i = \sum\limits_{j=0}^m a_j b_i-j\) \\
|
|
\( b_i := 0 \text{ für } i < 0 \)
|
|
\item Division?\\
|
|
\underline{Satz:} Es seien \(a(x), b(x)\) Polynome, \(b\ne 0\). Dann existieren Polynome \(q(x) \text{ und } r(x) \), so dass gilt:\\
|
|
\(a(x) = q(x) \cdot b(x) + r(x) \)\\
|
|
wobei \( r = 0\) oder \( grad(r) < grad(b) \).\\
|
|
Beweis: ohne.\\
|
|
\end{itemize}
|
|
\underline{Bsp.:} \( p(x) := 3x^3 + 4x^2 -5x + 1\)\\
|
|
\( \Rightarrow ((3x+4)x-5)x+1 \)\\
|
|
\( p(2) = \left(\left(3 \cdot 2 + 4 \right) \cdot 2 -5 \right) \cdot 2 + 1 \)\\
|
|
\spa \( = (10 \cdot 2 - 5) \cdot 2 +1 = 15 \cdot 2 +1 = 31 \)
|
|
|
|
\( \frac{(3x^3 + 4x^2 - 5x +1) }{x^2 - x + 1} = 3x+7 (=q(x)) \quad \text{ Rest } -x-6 (=r(x)) \)
|
|
|
|
Häufig interessiert man sich für die Nullstellen eines Polynoms.\\
|
|
\underline{Bsp.:}\\
|
|
\begin{align*}
|
|
p(x) := 2x^2 - 4x +1 &\overset{!}{=} 0\\
|
|
\Leftrightarrow x^2 - 2x + \frac 1 2 &\overset{!}{=} 0\\
|
|
\curvearrowright x_{1/2} &= +1 \pm \sqrt{1^2 - \frac 1 2}\\
|
|
&= 1 \pm \sqrt{\frac 1 2}
|
|
\end{align*}
|
|
|
|
Wieviele Nullstellen kann ein Polynom \(p \ne 0\) vom Grad n besitzen?\\
|
|
Höchstens \(n\) Nullstellen!
|
|
|
|
Beweis: mit vollständiger Induktion nach n\\
|
|
\textbf{I.A.} \(n=0: p(x) = a_0 \ne 0\)\\
|
|
\( \curvearrowright \) Keine Nullstellen \checkmark
|
|
|
|
\textbf{I.S.} Es sei \(grad(p) = n+1\):
|
|
\begin{labeling}[:]{x. Fall}
|
|
\item[1. Fall] p hat keine Nullstelle \( \rightarrow \) \checkmark
|
|
\item[2. Fall] p besitzt eine Nullstelle \(x_0\).\\
|
|
Es sei \(p(x) = q(x)(x-x_0) +r(x) \) mit \( r\ne 0 \lor grad(r) < grad(x-x_0) = 0\)\\
|
|
\( \curvearrowright grad(r) = 0\)\\
|
|
\(x_0\) ist Nullstelle von \(p \rightsquigarrow\)\\
|
|
\(p(x_0) = q(x_0)\underbrace{(x_0-x_0)}_{=0} + r(x_0) \overset{!}{=} 0 \)\\
|
|
\( \Rightarrow r(x_0) = 0 \lor grad(r)=0 \Rightarrow r = a_0 \ne 0 \)\\
|
|
\( \Rightarrow r = 0\),\\
|
|
\( p(x) = q(x)(x-x_0) \), wobei \(grad(q) = grad(p) - 1 = n \)\\
|
|
Alle weiteren Nullstellen von \(p\) sind Nullstellen von \(q\); Induktionsvorraussetzung:\\
|
|
\spa q hat höchstens n Nullstellen.\\
|
|
\(\Rightarrow p\) hat höchstens \(n+1\) Nullstellen \(\Box\)
|
|
\end{labeling}
|
|
|
|
\end{document}
|