http://pvs.csl.sri.com/index.shtml
(Nach stegner 0.3)
Zeichen | Typ | Beschreibung |
---|---|---|
∧ | Junktor | Zu Beweisen: Beides muss gezeigt werden In Annahme: Beides kann verwendet werden. |
∨ | Junktor | Zu Beweisen: Es reicht eins zu Zeigen In Annahme: ??? |
¬ | Junktor | Beweis per wiederspruch |
⇔ | Junktor | |
⇒ | Junktor | Mit Annahme kann Konklusion gezeigt werden |
∀ | Quantor | Zu Beweisen: „Für ein festes aber belibiges x …“ (Einzige Annahme ist $x \in M$) In Annahme: Belibiges x wählen |
∃ | Quantor | Zu Beweisen: Für ein belibiges x In Annahme: Festes aber belibiges x (Einzige Annahme ist $x \in M$) |
Anstadt A zeige das äquivalente B oder Lösung wird genannt oder deren existenz bewiesen.
Eigenschaften lassen auf Existenz von Lösung schließen \[ (A \Rightarrow B) \Leftrightarrow (\lnot B \Rightarrow \lnot A) \]
Statt A = wahr zeigt man ¬A = falsch
Spezielle form des Induktiven beweises:
(wahr ⇒ A) ⇔ (¬A ⇒ falsch)
Offt verwendet wenn das zu zeigende schon eine Negation ist.
$A = \exists_{x \in S}B$ soll negiert werden:
$\lnot \exists x \in S : B \Leftrightarrow \forall x \in S : \lnot B$
Induktionsanfang/Induktionsvorraussetzung: P(1)
Induktionsschluss: $\forall x \in N : \underbrace{P(n)}_{\text{Induktionsannahme/Induktionshypothese}} \Rightarrow P(n + 1)$
Vereinfachung/veralgemeinerung von der vollständigen Induktion. Man ist nicht mehr auf den direkten vorgänger beim Beweis beschränkt, sondern kann alle vorgänger verwenden.
\[ P(1) \wedge (\forall n: (\forall k \le n : P(k)) \Rightarrow P(n + 1)) \Rightarrow \forall n: P(n) \]
Name ⇔ | Beschreibung |
---|---|
reflexiv | $\forall a \in A : (a, a) \in R$ |
symetrisch | $\forall a, b \in A : (a, b) \in R \Rightarrow (b, a) \in R$ |
transitiv | $\forall a, b, c \in A : (a, b) \in R \wedge (b, c) \in R \Rightarrow (a,c) \in R$ |
antisymetrisch | $\forall a, b \in R : (a, b) \in R \wedge (b, a) \in R \Rightarrow a = b$ |
homogen | $R \subseteq S \times S$ |
Name | ⇔ Foo | ⇒ Bar | Beschreibung | |
---|---|---|---|---|
injektiv | $\forall b \in B : |f^{-1}(b)| \le 1$ | $|A| \le |B|$ | $f(a) = f(a') \Rightarrow a=a'$ | „Jedes Ergebniss kann durch maximal eine Eingabe ausgelöst werden“ |
surjektiv | $\forall b \in B : |f^{-1}(b)| \ge 1$ | $|A| \ge |B|$ | $\forall b \in B \exists a \in A : f(a) = b$ | „Jedes mögliche Ergebniss kommt raus“ |
bijektiv | $\forall b \in B : |f^{-1}(b)| = 1$ | $|A| = |B|$ | f injektiv & f surjektiv | „Jedes Ergebniss wird ausgelöst und das durch verschiedene Eingaben“ |
Auch „Pidginhole principle“
Beispielhaft:
11 Brife für 10 Mitarbeiter ⇒ Mindestens einer bekomm mehr als einen Brief.
$|B| < |A| \Rightarrow \exists a \ne a' : f(a) = f(a')$
„Umkehrfunktion“ ohne Funktionskarakter
$f^{-1}(b) := \{a \in A \mid f(a) = b\}$
$f^{-1}(B) := \bigcup b \in B : f^{-1}(b)$
$f^{-1}(B) := \{a \in A \mid f(a) \in B \}$
(Buch 1.4)
Name | Beschreibung |
---|---|
Quasiordnung | reflexiv, transitiv |
Partielle Ordnung | reflexiv, transitiv, antisymetrisch |
Äquivalenzrelation | reflexiv, transitiv, symetrisch |
$[a]_R$ Äquivalenzklasse mit Representant a
$A/R$ Menge aller Äquivalenzklassen. d.H. $[a]_R \in A/R$
$R^+ \subseteq M \times M$ so ergänzen das R transitiv wird.
Beispiel:
$R = \{(a, b), (b, c)\} \Rightarrow R^+ = \{(a, b), (b, c), (a, c)\}$
$R^+$ y ist über 1..n R-Schritte mit x Verbunden
$R^+ \subseteq M \times M$ so ergänzen das R transitiv und reflexiv wird.
$R^* = R^+ \cup \{(x, x) \mid x \in S\}$
$R^*$ y ist über 0..n R-Schritte mit x Verbunden
(Rein reflexive hüllen gibt es auch, sind aber uninteresant)
Ordnung zweier elemente in einer Partiellen Ordnung: $x \preceq y \Leftrightarrow (x, y) \in R$
Partiell geordnete Menge:
$R^*$ ist eine Partielle Ordnung
$(x, y) \in R \vee (y, x) \in R$ ⇒ x und y sind vergleichbar
sonst unvergleichbar.
$\preccurlyeq \leq \sqsubseteq$ sind häufig verwendete Symbole für partielle Ordnungen.
„Partielle Ordnung“ = partially ordered set = poset
Wenn es ein Min/Maximum gibt ist es eindeutig.
Eindeutig wenn sie existieren
$\forall_{x, y \in S} : (x \preceq y \vee y \preceq x)$
(Alle Parungen sind vergleichbar)
Daraus follgt
Muss man mit ihnen etwas beweisen/umformen kann man wie folgt vorgehen:
Sprich es muss $a \preccurlyeq c \wedge b \preccurlyeq c$ gezeigt werden um $a \sqcup b \preccurlyeq c$ zu beweisen.
Zusätzlich gild:
Sie werden distributiert, verteilt, der Term wird größer.
Die meisten Verbände sind auch distributiv, ausgenommen sin die der form
a a / | \ / \ b c d b | \ | / | d e c | \ / e
Gild $a = q \cdot b + r$ mit $0 \le r < |b|$
so schreibt man $r = a \mod b$ (oder a % b
)
und $ q = \lfloor \frac{a}{b} \rfloor$ (oder a div b
)
-10 mod 3 = 2
da $-10 = (-4) \cdot 3 + 2$
b | a | mod |
---|---|---|
3 | 4 | 1 |
3 | 3 | 0 |
3 | 2 | 2 |
3 | 1 | 1 |
3 | 0 | 0 |
3 | -1 | 2 |
3 | -2 | 1 |
3 | -3 | 0 |
3 | -4 | 2 |
b|a ⇔ a mod b = 0
d.h. $\exists \lfloor \frac{a}{b} \rfloor = q \in Z : a = q \cdot b$
$\forall a \in Z : a|a \wedge 1|a$
„a und b teilerfremd“ ⇔ c|a und c|b nur für c=1
Jede Zahl kann aus Primzahlen zusammenmultipliziert werden. \[ \forall_{n \in N} : n = \prod_{i=1}^k p_i^{e_i} \] mit $p_1 \ldots p_k$ paarweise verschieden.
Unendlich viele Primzahlen
$(\prod_{i=1}^k p_i)+1$ lässt sich nicht aus $p_1 \ldots p_k$ zusammenbauen, aber anders.
Sei $\pi(n) \sim \frac{n}{ln(n)}$ :⇔ Anzahl Primzahlen $\le n$
Es gelten folgende Regeln:
Follgende Aussagen sind äquivalent
Bsp: $4 \equiv -2$ mod 3
Es gelten folgende Regeln:
$7^{66} \mod 13$ \[ \begin{align*} &7^{66} \mod 13 \\ &7^{1} \mod 13 = 7 \\ &7^{2} \mod 13 = 7^2 \mod 13 = 49 \mod 13 = 10 \\ &7^{2} \mod 13 = 10^2 \mod 13 = 100 \mod 13 = 9 \\ &7^{4} \mod 13 = 9^2 \mod 13 = 81 \mod 13 = 3 \\ &7^{8} \mod 13 = 3^2 \mod 13 = 9 \mod 13 = 9 \\ &\vdots \\ &7^{64} \mod 13 = 9^2 \mod 13 = 81 \mod 13 = 3 \\ &7^{66} \mod 13 = 7^{64} \cdot 7^{2} \mod 13 = 90 \mod 13 = 12 \\ \end{align*} \]
größtes $d \in N$ so das gild d|a und d|b
ggT(a, b) = s*a + t*b
Ziel:
Oben links und unten rechts (1, 0) sind start Werte.
a/b | div | x/y |
---|---|---|
24 | -3 | |
15 | 1 | 2 |
9 | 1 | -1 |
6 | 1 | 1 |
3 | 2 | 0 |
0 |
Wenn r = 0:
$a \cdot x \equiv b (\mod m) \text{ mit } a, b \in Z$
Find alle $x \in Z$ so dass gleichung gild.
$5 \cdot x \equiv 2 (\mod 7) \Rightarrow x = \cdots, -1, 6, 13, \cdots$
$\operatorname{ggT}(a, m)|b$
WTF WTF WTF! http://www.inf.fh-flensburg.de/lang/krypto/grund/inverses-element.htm
x ist das Inverse von a mod m, wenn gild $a \cdot x = 1 (\mod m)$.
Vorbedingung: ggT(a, m) = 1
Berechnung:
eggT(a, m) = (1, s, t)
1 = s*a + t*m
⇒ s & m sind das gesuchte Inverse
Beispiel: Inverses zu 5 mod 7 ⇒ 5x $\equiv$ 1 ⇒ x=3
Ziel: Find $0 \le x < m_1 \cdot \ldots \cdot m_k$ vom \[ \begin{align*} x \equiv b_1 \pmod{m_1} \\ \vdots \\ x \equiv b_k \pmod{m_k} \end{align*} \] mit $b_i, m_i \in Z$ und $m_i$ paarweise Teilerfremd [ggT($m_i, m_j$) = 1]
\[ \begin{align*} x \equiv 1 \bmod 2 \\ x \equiv 2 \bmod 3 \\ M = 2 \cdot 3 = 6 \end{align*} \] \[ \begin{array} b_1 = 1 & m_1 = 2 & M_1 = M/m_1 = 3 \\ b_2 = 2 & m_2 = 3 & M_2 = M/m_2 = 2 \end{array} \]
EEA für 1
a/b | div | x/y |
---|---|---|
$M_1$ = 3 | -1 | |
2 | 1 | 1 |
1 | 2 | 0 |
0 |
⇒ $e_2 = 3 \cdot 1 = 3$
EEA für 2
a/b | div | x/y |
---|---|---|
3 | -1 | |
$M_1$ = 2 | 1 | 1 |
1 | 2 | 0 |
0 |
⇒ $e_2 = 2 \cdot -1 = -2$
$x = \left(\sum b_i \cdot e_i \right) \bmod M = (1 \cdot 3) + (2 \cdot -2) \bmod 6 = -1 \bmod 6 = 5$
Beweis: \[ \begin{align*} 5 \equiv 1 \bmod 2 \Rightarrow 2 \cdot 2 + 1 = 5 \\ 5 \equiv 2 \bmod 3 \Rightarrow 1 \cdot 3 + 2 = 5 \end{align*} \]
Polynom != Polynomfunktion
\[ ( \forall x : f_p(x) = f_q(x)) \Rightarrow p = q \]
\[ p(x) = \sum a_i x^i \]
$a_n \cdot x^n + a_{n-1} \cdot x^{n-1} + \ldots + a_1 \cdot x + a_0$
$a_i \ne 0 =$ Koeffizient
n = grad(p) = deg(p)
Regeln:
Spezialfälle:
a(x) : b(x) ⇒
Beispiel:
a(x) = 2x^4 + x^3 +3 b(x) = x^2 + x -1 (2x^4 + x^3 + x + 3) : (x^2 + x - 1) = 2x^2 - x + 3 -(2x^4 + 2x^3 - 2x^2) ===================== -x^3 + 2x^2 + x + 3 -(-x^3 - x^2 + x) =================== 3x^2 + 3 -(3x^2 + 3x - 3) ================ -3x + 6 = r Es follt: a = q * b + r mit q = 2x^2 - x +3 r = -3x + 6
Anzahl Nullstellen $\le$ grad(p)
$\alpha$ Nulstelle ⇒ p(x) : (x - $\alpha$) ohne Rest! ⇒ $p(x) = q(x) \cdot (x - \alpha)$
NOCH EIN ZU SORTIEREN: Prime Restklassengruppe: http://de.wikipedia.org/wiki/Prime_Restklassengruppe#Berechnung_der_inversen_Elemente
$\sigma$ = Tupel, der Stellenwertigkeiten, einer Algebra.
Beispiel: $\sigma = (2, 2, 1)$ ⇒ Algebra mit zwei 2-Stelligen Operationen und einer 1-Stelligen Operation.
Algebra Implementiert Signatur (interface) indem es konkrete Operatoren zur Signatur und eine Arbeitsmenge angibt.
Tupel das beinhaltet
\[ \begin{align*} \sigma = (2, 2) \\ A = R \\ f_1 : A \times A \rightarrow A \\ f_1(x, y) = x \cdot y \\ f_2 : A \times A \rightarrow A \\ f_2(x, y) = x + y \\ \Rightarrow A = (A, f_1, f_2) \end{align*} \]
A mit mindestens einer 2 Stelligen Operation ist
A mit mit mindestens einer 2-Stelligen Operation f
A assoziativ ⇔ $\forall x,y,z \in A : f(x, f(y, z)) = f(f(x, y), z)$
$A = (A, f_1, \cdots, f_m)$ mit $\sigma = (d1, \cdots, d_m)$ sei eine Struktur.
$U \subseteq A$ ist Unterstruktur wenn U abgeschlossen ist. d.h. wenn $a_1, \cdots, a_{d,i} \in U \Rightarrow f_i(a_1, \cdots, a_{d,i}) \in U$ für alle $i = 1, \cdots, m$
Für zwei Strukturen $(A, f_1^A, \cdots, f_m^A)$ und $(B, f_1^B, \cdots, f_m^B)$ unter der gleichen Signatur $(a_1, \cdots, d_m)$ ist $h: A \rightarrow B$ ein Homomorphismus wenn gilt $h(f_i^A(a_1, \cdots, a_{d,i})) = f_i^B(h(a_1), \cdots, h(a_{d,i}))$.