Lösung

Wir beweisen die Gaußsche Summenformel durch vollständige Induktion.

IA: \(n = 0\)

\[ \sum_{k=1}^{0} k = 0 = \frac{0(0+1)}{2} \]

IS: \(n > 0\), (\(n-1 → n\))

Angenommen, die Formel gilt für \(n-1\), also \[ \sum_{k=1}^{n-1} k = \frac{(n-1)n}{2} \tag{IV} \]

Dann gilt:

\[ \begin{aligned} \sum_{k=1}^{n} k &= \sum_{k=1}^{n-1} k + n\\ &\stackrel{(IV)}{=} \frac{(n-1)n}{2} + n\\ &= \frac{n(n-1+2)}{2}\\ &= \frac{n(n+1)}{2}\\ \end{aligned} \]

Aufgabe: Fibonacci Folge - Induktionsbeweis

Die Fibonacci Folge ist definiert durch: \[ F_0 = 0, \quad F_1 = 1, \quad F_n = F_{n-1} + F_{n-2} \text{ für } n \geq 2 \]

Beweisen Sie die folgende Aussage für alle \(n \geq 0\) durch vollständige Induktion: \[ F_n \leq 2^{n-1} \]

Lösung

Wir beweisen die Aussage durch vollständige Induktion.

IA: \(n = 0, 1\)

\[ F_0 = 0 \leq 2^{-1} = \frac{1}{2} \]

\[ F_1 = 1 \leq 2^{0} = 1 \]

IS: \(n > 1\), (\(n-2 ∧ n-1 → n\))

Angenommen, die Aussage gilt für \(n-2\) und \(n-1\), also \[ F_{n-2} \leq 2^{n-3}, \qquad F_{n-1} \leq 2^{n-2} \tag{IV} \]

Dann gilt: \[ \begin{aligned} F_n &= F_{n-1} + F_{n-2}\\ &\stackrel{(IV)}{≤} 2^{n-2} + 2^{n-3}\\ &= 2^{n-3}(2 + 1)\\ &= 2^{n-3} \cdot 3\\ &\leq 2^{n-1} \end{aligned} \]

Aufgabe: Teilbarkeit - Induktionsbeweis

Zeige, dass \(n^3 + 5n\) durch 6 teilbar ist für alle \(n \in \mathbb{N}\)

Lösung

Wir nutzen die Äquivalenz relation \(≡_{\text{mod } 6}\)(modulo 6) über \(ℕ\).

dh: \(n^3 + 5n \equiv_{\text{mod } 6} 0 \qquad \forall n \in \mathbb{N}\)

Wir zeigen dies durch vollständige Induktion.

Induktionsanfang (IA): \(n = 0\)

Für n = 0 gilt: \[0^3 + 5 \cdot 0 = 0 \equiv_{\text{mod }6} 0\]

Induktionsschritt (IS): \(n > 0\), \((n-1 \; → \; n)\)

Angenommen, die Aussage gilt bereits für n-1, also: \[(n-1)^3 + 5(n-1) \equiv_{\text{mod }6} 0 \tag{IV}\] Wir zeigen, dass die Aussage dann auch für n gilt: \[ \begin{aligned} n^3 + 5n &= (n-1+1)^3 + 5(n-1+1)\\ &= (n-1)^3 + 3(n-1)^2 + 3(n-1) + 1 + 5(n-1) + 5\\ &= (n-1)^3 + 5(n-1) + 3(n-1)^2 + 3(n-1) + 6\\ &\stackrel{IV}{\equiv_{\text{mod } 6}} 3(n-1)^2 + 3(n-1) + 6\\ &\equiv_{\text{mod } 6} 3(n-1)^2 + 3(n-1)\\ &\equiv_{\text{mod } 6} 3(n-1)((n-1)+1)\\ &\equiv_{\text{mod } 6} 3(n-1)n\\ &\stackrel{n(n-1)\equiv_{2} 0}{\equiv_{\text{mod } 6}} 0 \quad \end{aligned} \]

Aussagenlogik

Betrachten Sie die Funktion f(x) definiert als:

function f(x::Number) ::Number
    if x > 0
        return x
    else
        return 5
    end
end

Dies kann durch die folgende logische Formel dargestellt werden: \[ (\underbrace{A}_{x > 0} → \underbrace{R_x}_{\text{return }x}) ∧ (\underbrace{¬A}_{x ≤ 0} → \underbrace{R_5}_{\text{return }5}) \]

Dies kann in eine disjunktive Normalform überführt werden:

\[ A ∧ R_x ∨ ¬A ∧ R_5 \]

Überprüfen Sie, ob die disjunktive Normalform äquivalent zur ursprünglichen logischen Formel ist, mittels einer Wahrheitstabelle.

Lösung

um Platz zu sparen, definieren wir:

\(H_1 := A ∧ R_x\)
\(H_2 := ¬A ∧ R_5\)
\(L_1 := A → R_x\)
\(L_2 := ¬A → R_5\)

\(A\)	\(R_x\)	\(R_5\)	\(H_1\)	\(H_2\)	\(H_1 ∨ H_2\)	\(L_1\)	\(L_2\)	\(L_1 ∧ L_2\)
0	0	0	0	0	0	1	0	0
0	0	1	0	1	1	1	1	1
0	1	0	0	0	0	1	0	0
0	1	1	0	1	1	1	1	1
1	0	0	0	0	0	0	1	0
1	0	1	0	0	0	0	1	0
1	1	0	1	0	1	1	1	1
1	1	1	1	0	1	1	1	1

We can see that \(H_1 ∨ H_2\) and \(L_1 ∧ L_2\) have the same truth values for all possible combinations of \(A\), \(R_x\), and \(R_5\), hence the disjunctive normal form is equivalent to the original logical formula.

Überprüfen Sie, ob die disjunktive Normalform äquivalent zur ursprünglichen logischen Formel ist, mittels logischer Äquivalenzen.

Lösung

\[ \begin{aligned} A ∧ R_x ∨ ¬A ∧ R_5 &\equiv \underbrace{(A ∨ ¬A)}_{\equiv w} ∧ (A ∨ R_5) ∧ (¬A ∨ R_x) ∧ (R_x ∨ R_5) &(2×\text{Distributivgesetz})\\ &\equiv (A ∨ R_5) ∧ (¬A ∨ R_x) ∧ \big((R_x ∨ R_5) ∨ \underbrace{(A ∧ ¬A)}_{\equiv f}\big) &(2×\text{tertium non datur, } 2×\text{Dominanzgesetze})\\ &\equiv (A ∨ R_5) ∧ (¬A ∨ R_x) ∧ (A ∨ R_5 ∨ R_x) ∧ (¬A ∨ R_x ∨ R_5) &(\text{Distributivgesetz})\\ &\equiv \underbrace{(A ∨ R_5) ∧ \big((A ∨ R_5) ∨ R_x\big)}_{\equiv\, A ∨ R_5} ∧ \underbrace{(¬A ∨ R_x) ∧ \big((¬A ∨ R_x) ∨ R_5\big)}_{\equiv\, ¬A ∨ R_x} &(\text{Kommutativität})\\ &\equiv (A ∨ R_5) ∧ (¬A ∨ R_x) &(\text{Absorption})\\ &\equiv (¬A → R_5) ∧ (A → R_x) &(\text{Implikationsumformung})\\ &\equiv (A → R_x) ∧ (¬A → R_5) &(\text{Kommutativität}) \end{aligned} \]