http://pvs.csl.sri.com/index.shtml
====== Logik und Diskrete Strukturen ======
===== VL 1 =====
[[https://pads.ccc.de/oVmo9thGzL|EtherPad]]
===== Beweise =====
(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$) |

==== Arten ====
=== Äquivalenzbeweis ===
Anstadt A zeige das äquivalente B oder Lösung wird genannt oder deren existenz bewiesen.

=== Indirekter Beweis ===
Eigenschaften lassen auf Existenz von Lösung schließen
\[
(A \Rightarrow B) \Leftrightarrow (\lnot B \Rightarrow \lnot A)
\]

=== Wiederspruchsbeweis ===
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$

=== Vollständige Induktion ===
Induktions//anfang//%%/%%Induktions//vorraussetzung//:
P(1)

Induktions//schluss//:
$\forall x \in N : \underbrace{P(n)}_{\text{Induktionsannahme/Induktionshypothese}} \Rightarrow P(n + 1)$

=== Allgemeine Induktion ===
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)
\]

===== Mengen =====
==== Relationen ====
^ 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$ |

==== Funktionen ====
^ Name ^ <=> Foo ^ => Bar ^ LOL ^ 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" |


=== Schubfachprinzip ===
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')$

=== Urbild ===
"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 \}$

===== Ordnungen und Verbände =====
(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$


==== Transitive Hülle ====
$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


==== Reflexive, transitive Hülle ====
$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)

==== Partielle Ordnung ====
Ordnung zweier elemente in einer Partiellen Ordnung: $x \preceq y \Leftrightarrow (x, y) \in R$

Partiell geordnete Menge:
  * Menge $S$ über die es eine
  * Partielle ordnung $R \subseteq S \times S$ gibt.

$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

  * $z \in A \text{Maximum} \Leftrightarrow \forall_{y \in A} : y \preccurlyeq z$
  * $z \in A \text{Minimum} \Leftrightarrow \forall_{y \in A} : z \preccurlyeq y$
Wenn es ein Min/Maximum gibt ist es eindeutig.

  * Menge an $z \in A \text{obere Schranke von} x, y \Leftrightarrow x \preccurlyeq z \wedge y \preccurlyeq z$
  * Menge an $z \in A \text{untere Schranke von} x, y \Leftrightarrow z \preccurlyeq x \wedge z \preccurlyeq y$

  * Element $z \in A \text{kleinste obere Schranke (sup) von} x, y \Leftrightarrow z \in \text{obere Schranke} \wedge \forall_{w \in \text{obere Schranke}} : z \preccurlyeq w$
  * Element $z \in A \text{kleinste untere Schranke (inf) von} x, y \Leftrightarrow z \in \text{untere Schranke} \wedge \forall_{w \in \text{untere Schranke}} : z \preccurlyeq w$
  * $\sup(x, y) = x \sqcup y$
  * $\inf(x, y) = x \sqcap y$
Eindeutig wenn sie existieren
==== Hassediagramm ====
  * reflexive Verbindungen weglassen
  * transitive Verbindungen weglassen
  * "unten was kleiner"
==== Totale/Vollständige/Lineare Ordnung ====
$\forall_{x, y \in S} : (x \preceq y \vee y \preceq x)$\\
(Alle Parungen sind vergleichbar)

==== Verband ====
  * Partielle ordnung
    * reflexiv
    * transitiv
    * antisymetrisch
  * besitzt min/max ($\perp / \top$)
  * $\forall_{x,y \in A} : \exists : \sup(x, y) \wedge \inf(x, y)$

Daraus follgt
  * sup(), inf() sind assoziativ [a+(b+c) = (a+b)+c] und kommutativ [a+b = b+a]
  * $\sup(\top, x) = \top$
  * $\sup(\perp, x) = x$
  * $\inf(\top, x) = x$
  * $\inf(\perp, x) = \perp$

Muss man mit ihnen etwas beweisen/umformen kann man wie folgt vorgehen:
  * $a \preccurlyeq a \sqcup b \Rightarrow \checkmark$
  * $b \preccurlyeq a \sqcup b \Rightarrow \checkmark$
  * $a \sqcup b \preccurlyeq c \Rightarrow a \preccurlyeq c \wedge b \preccurlyeq c$
  * $a \sqcap b \preccurlyeq a \Rightarrow \checkmark$
  * $a \sqcap b \preccurlyeq b \Rightarrow \checkmark$
  * $c \preccurlyeq a \sqcap b \Rightarrow c \preccurlyeq a \wedge c \preccurlyeq b$

Sprich es muss $a \preccurlyeq c \wedge b \preccurlyeq c$ gezeigt werden um $a \sqcup b \preccurlyeq c$ zu beweisen.
==== Distributiver verband ====
Zusätzlich gild:
  * $x \sqcap (y \sqcup z) = (x \sqcap y) \sqcup (x \sqcap z)$
  * $x \sqcup (y \sqcap z) = (x \sqcup y) \sqcap (x \sqcup z)$

> Sie werden distributiert, verteilt, der Term wird größer.

Die meisten Verbände sind auch distributiv, ausgenommen sin die der form
<code>
   a          a
 / | \      /   \
b  c  d    b    |
 \ | /     |    d
   e       c    |
            \   /
              e
</code>

===== Aritmetik =====
==== Ganzzahlige division ====
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'')

=== Negativ ===
  * ''-10 mod 3 = 2''
  * $\lfloor \frac{-10}{3} \rfloor = -4$
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  |

==== Teilbarkeit ====
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

==== Primzahl ====
=== Definition ===
  * d|p nur für d=1 und d=p
  * 1 ist keine Primzahl

=== Primfaktorzerlegung ===
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.

=== Satz von Euklid ===
> Unendlich viele Primzahlen
$(\prod_{i=1}^k p_i)+1$ lässt sich nicht aus $p_1 \ldots p_k$ zusammenbauen, aber anders.

[[http://de.wikipedia.org/wiki/Satz_von_Euklid|wiki]]

=== Primzahlsatz ===
Sei $\pi(n) \sim \frac{n}{ln(n)}$ :<=> Anzahl Primzahlen $\le n$

==== Modulare Arithmetik ====
Es gelten folgende Regeln:
  * %%(a + b) mod m = (a mod m + b mod m)%% mod m
  * %%(a * b) mod m = ((a mod m) * (b mod m))%% mod m

=== Kongurenzklassen ===
Follgende Aussagen sind äquivalent
  * $a \equiv b (\mod m)$ :<=> a ist //kongurent// zu b modulo m
  * a mod m = b mod m
  * $\exists_{t \in Z} : a = b + t \cdot m$
  * m|(a-b)

Bsp: $4 \equiv -2$ mod 3

Es gelten folgende Regeln:
  * $(a \equiv b) \mod m \wedge (c \equiv d) \mod m \Rightarrow a + c \equiv b + d$ (mod m)
  * $(a \equiv b) \mod m \wedge (c \equiv d) \mod m \Rightarrow a \cdot c \equiv b \cdot d$ (mod m)

=== Schnelles Potenzieren (use-case) ===
$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*}
\]

=== ggT ===
größtes $d \in N$ so das gild d|a und d|b

ggT(a, b) = s*a + t*b

=== Euklidischer Algorithmus ===
Ziel: ggT berechnen

Methode: ggT(A, a) = ggT(A mod a, a) [mit kleineren Zahlen rechnen]

{{:users:skruppy:ext:uni:2:foo.png?direct&300|}}

=== Erweiterter euklidischer Algorithmus ===
Ziel:
  * ggT berechnen
  * $s, t \in Z$ mit ggt$(a, b) = s\cdot a + t \cdot b$ finden
== Methode 1 ==
Oben links und unten rechts (1, 0) sind start Werte.
  * Nach unten: div/modulo
  * Nach oben: $x_i = y_{i-1} - x_{i-1} \cdot \text{div}_{\ \ i}$

ggT(24, 15) = 3 = b*x + a*y = 15*-3 + 24*2\\
{{:users:skruppy:ext:uni:2:eea1.png?direct&300|}} \\

== Methode 2 ==
^ a/b ^ div ^ x/y ^
|  **24** |   |     -3 |
|  **15** | 1 |      2 |
|       9 | 1 |     -1 |
|       6 | 1 |  **1** |
|       3 | 2 |  **0** |
|       0 |   |        |

== Alt ==
  * gehe in die nächste Zeile
  * $r = r_{-2} - r_{-1} \cdot q_{-1}$
  * $s = s_{-2} - s_{-1} \cdot q_{-1}$
  * $q = r_{-1} \div r$

Wenn r = 0:
  * s
  * $(r - s \cdot a) \div b$
===== Lineare Kongurente Gleichungen =====
==== Gegeben ====
$a \cdot x \equiv b (\mod m) \text{ mit } a, b \in Z$

==== Ziel ====
Find alle $x \in Z$ so dass gleichung gild.

==== Beispiel ====
$5 \cdot x \equiv 2 (\mod 7) \Rightarrow x = \cdots, -1, 6, 13, \cdots$

==== Vorbedingung ====
$\operatorname{ggT}(a, m)|b$

==== Inverses ====
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

==== Chinesischer Reste Satz ====
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]

=== Methode ===
  * $M = m_1 \cdots m_k$
  * $M_i = \frac{M}{m_i}$
  * Erweiterter Euklidischer Algorithmus mit $m_i$ und $M_i$
    * [$M_i$ kann größer oder kleiner $m_i$ sein!]
    * $e_i = M_i \cdot x/y_i$ [Diagonal bei Methode 2]
  * $x = \left(\sum b_i \cdot e_i \right) \bmod M$


=== Beispiel ===
\[
\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*}
\]
===== Polynome =====
Polynom != Polynomfunktion

\[
( \forall x : f_p(x) = f_q(x)) \Rightarrow p = q
\]

\[
p(x) = \sum a_i x^i
\]

==== Normalform & Grad ====
$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:
  * grad(p*q) = grad(p) + grad(q) [wenn $p \ne 0 \wedge q \ne 0$]
  * grad(p+q) $\le$ max(grad(p), grad(q))

Spezialfälle:
  * p = 7 => n = 0 => grad(p) = 0
  * p = 0 => n = -1 => grad(p) = -1

==== Division ====
a(x) : b(x) =>
  * a(x) = q(x) * b(x) + r(x)
  * grad%%(r)%% < grad(b)

Beispiel:
<code>
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
</code>

==== Nullstellen ====
Anzahl Nullstellen $\le$ grad(p)

$\alpha$ Nulstelle => p(x) : (x - $\alpha$) //ohne Rest!// => $p(x) = q(x) \cdot (x - \alpha)$


===== Algebraische Struktur =====
NOCH EIN ZU SORTIEREN: Prime Restklassengruppe: http://de.wikipedia.org/wiki/Prime_Restklassengruppe#Berechnung_der_inversen_Elemente
==== Signatur ====
$\sigma$ = Tupel, der Stellenwertigkeiten, einer Algebra.

Beispiel: $\sigma = (2, 2, 1)$ => Algebra mit zwei 2-Stelligen Operationen und einer 1-Stelligen Operation.

==== (Universelle) Algebra ====
Algebra Implementiert Signatur (interface) indem es konkrete Operatoren zur Signatur und eine Arbeitsmenge angibt.

Tupel das beinhaltet
  * Eine Menge //A//
  * Opeationen über die Menge //A//

\[
\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*}
\]

==== Neutrales Element ====
A mit mindestens einer 2 Stelligen Operation ist
  * $a \in A$ linksneutral <=> $\forall x : a \circ x = x$
  * $a \in A$ rechtsneutral <=> $\forall x : x \circ a = x$
  * $a \in A$ neutral <=> Rechtsneutral

==== Assoziativgesetz ====
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)$

==== Unterstruktur ====
$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$

==== Homomorphismus ====
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}))$.
===== Logik =====
http://cms.uni-kassel.de/unicms/fileadmin/groups/w_222000/TIL-WS1011/03-Aussagenlogik-07.pdf