Logik und Diskrete Strukturen

EtherPad

(Nach stegner 0.3)

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

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)

$[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:

• 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

• reflexive Verbindungen weglassen
• transitive Verbindungen weglassen
• „unten was kleiner“

$\forall_{x, y \in S} : (x \preceq y \vee y \preceq x)$
(Alle Parungen sind vergleichbar)

• 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.

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

   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
• $\lfloor \frac{-10}{3} \rfloor = -4$

da $-10 = (-4) \cdot 3 + 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

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

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.

wiki

Sei $\pi(n) \sim \frac{n}{ln(n)}$ :⇔ Anzahl Primzahlen $\le n$

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

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)

$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: ggT berechnen

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

Ziel:

• ggT berechnen
• $s, t \in Z$ mit ggt$(a, b) = s\cdot a + t \cdot b$ finden

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

• 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$

$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]

• $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$

\[ \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

⇒ $e_2 = 3 \cdot 1 = 3$

EEA für 2

⇒ $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:

• 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

a(x) : b(x) ⇒

• a(x) = q(x) * b(x) + r(x)
• grad(r) < grad(b)

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

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

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

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}))$.

http://cms.uni-kassel.de/unicms/fileadmin/groups/w_222000/TIL-WS1011/03-Aussagenlogik-07.pdf