Wiederholen:

Aufgabe 0-3

FSKO-1 Fundamentale Beweisstrategien

Aufgabenstellung

In dieser Aufgabe diskutieren wir fundamentale Beweisstrategien. Diese Strategien sollten aus anderen Kursen bekannt sein, aber da FSK sehr beweislastig ist, wiederholen wir sie hier.

a) Die folgende Tabelle fasst zusammen, wie man mit Aussagen, die bestimmte logische Operationen enthalten, umgeht.

Formel	Um eine Aussage dieser Form zu beweisen…	Wenn eine Aussage dieser Form angenommen wird…
$P \land Q$	beweise sowohl $P$ also auch $Q$	nimm $P$ und $Q$ an
$P \lor Q$	beweise entweder $P$ oder $Q$	beweise die gewünschte Aussage sowohl under der Annahme $P$ also auch under der Annahme $Q$ (Fallunterscheidung)
$P \Rightarrow Q$	beweise, dass under der Annahme $P$ $Q$ folgt	beweise $P$ und nimm dann $Q$ an
$\neg P$	beweise, dass under der Annahme $P$ ein Widerspruch folgt	beweise $P$ , um einen Widerspruch herzuleiten
$\forall x, P (x)$	beweise, dass $P (a)$ für ein beliebiges $a$ gilt	nimm $P (a)$ für jedes konkrete $a$ an
$\exists x, P (x)$	gib ein konkretes $a$ an und beweise $P (a)$	nimm ein beliebiges $a$ an, für das $P (a)$ gilt

Die Implikation $P \Leftrightarrow Q$ („genau dann wenn Q” oder „gdw. Q”) ist definiert also $(P \Rightarrow Q) \land (Q \Rightarrow P)$ .

Außerdem kann man, unabhängig von der zu beweisenden Aussage, immer folgende Regeln anwenden:

Widerspruchsbeweis: um $P$ zu beweisen nimm an, dass $\neg P$ gilt, und leite daraus einen Widerspruch ab.
Satz vom ausgeschlossenen Dritten: für jede beliebige Aussage $P$ nimm $P \lor \neg P$ an.

Häufig nützlich sind auch folgende Regeln:

\neg (A \land B) \neg (A \lor B) \neg\forall x, P (x) \neg\exists x, P (x) A \land (B \lor C) A \lor (B \land C) (\forall x, P (x)) \land (\forall x, Q (x)) (\exists x, P (x)) \lor (\exists x, Q (x)) \neg\neg A \Leftrightarrow \neg A \lor \neg B \Leftrightarrow \neg A \land \neg B \Leftrightarrow \exists x, \neg P (x) \Leftrightarrow \forall x, \neg P (x) \Leftrightarrow (A \land B) \lor (A \land C) \Leftrightarrow (A \lor B) \land (A \lor C) \Leftrightarrow \forall x, (P (x) \land Q (x)) \Leftrightarrow \exists x, (P (x) \lor Q (x)) \Leftrightarrow A

i) Zeigen Sie: $(\forall n, \exists k, k > n) \Leftrightarrow (\neg\exists n, \forall k, n \geq k)$

Linke Seite: trivial wahr für $R$ und $N$ Rechte Seite: $(\neg\exists n, \forall k, n \geq k)$ = ( $\forall n, \exists k, n > k$ ) Gesamtaussage : $(\forall n, \exists k, k > n) \Leftrightarrow (\forall n, \exists k, k > n)$

Erklärung für Dummies

i) Zeigen Sie: $(\forall n, \exists k, k > n) \Leftrightarrow (\neg\exists n, \forall k, n \geq k)$

Stellen Sie sich die Menge aller natürlichen Zahlen vor, die Sie auf einer endlosen Linie anordnen können, wobei jede Zahl einen festen Platz hat, beginnend mit der kleinsten, der 1. Die natürlichen Zahlen hören nie auf; es gibt immer eine Zahl, die um eins größer ist also die vorherige.

Linke Seite: $(\forall n, \exists k, k > n)$

Diese Aussage ist wie ein Spiel, bei dem Sie eine beliebige Zahl nennen, und ich muss eine größere Zahl finden. Ganz gleich, welche Zahl Sie auch wählen, ich kann immer gewinnen, indem ich einfach die nächstgrößere Zahl nenne. In der Welt der Zahlen, equal ob wir über reelle Zahlen (alle Zahlen auf dem Zahlenstrahl) oder nur über natürliche Zahlen (die Zahlen, die Sie zum Zählen verwenden) sprechen, gibt es immer eine größere Zahl also die, die Sie gerade genannt haben. Dies ist eine grundlegende Eigenschaft der Zahlen, die wir also “unendlich” bezeichnen. In diesem Sinne ist die linke Seite trivial wahr.

Rechte Seite: $(\neg\exists n, \forall k, n \geq k)$

Diese Aussage ist ein bisschen wie ein umgekehrtes Spiel. Hier behaupten wir, dass es keine Zahl gibt, die größer oder gleich jeder anderen Zahl ist. Wenn Sie versuchen würden, eine solche Zahl zu finden, würden Sie scheitern, denn equal welche Zahl Sie auch wählen, ich kann immer eine größere Zahl finden. Diese Aussage ist wie ein Beweis dafür, dass es keine “größte” Zahl gibt – eine Tatsache, die auch wahr ist.

Gesamtaussage: $(\forall n, \exists k, k > n) \Leftrightarrow (\forall n, \exists k, k > n)$

Wenn wir nun beide Seiten betrachten, können wir sehen, dass sie im Grunde dasselbe sagen, nur aus verschiedenen Blickwinkeln. Auf der linken Seite sagen wir, dass es immer eine größere Zahl gibt, und auf der rechten Seite sagen wir, dass es keine größte Zahl gibt. Das klingt vielleicht widersprüchlich, aber in der Welt der Zahlen ergänzen sich diese beiden Aussagen. Daher können wir schließen, dass die Gesamtaussage wahr ist.

In einfachen Worten: Stellen Sie sich eine Reihe von Personen in einer Warteschlange vor, die sich endlos weit erstreckt. Die linke Seite der Gleichung sagt, dass es immer eine Person gibt, die weiter hinten in der Schlange steht also Sie, equal wo Sie stehen. Die rechte Seite sagt aus, dass es unmöglich ist, jemanden zu finden, der weiter vorne steht also jeder andere, weil die Schlange niemals endet. Beide Situationen bestätigen, dass die Schlange unendlich lang ist.

Erklärung

i) Zeigen Sie: $(\forall n, \exists k, k > n) \Leftrightarrow (\neg\exists n, \forall k, n \geq k)$

Die linke Seite der Äquivalenz, $(\forall n, \exists k, k > n)$ , ist eine direkte Folge der Eigenschaft, dass die natürlichen Zahlen unendlich sind. Für jede natürliche Zahl $n \) können wir eine größere natürliche Zahl$ k ) finden, indem wir einfach $ k = n + 1 ) wählen. Dies funktioniert auch im Bereich der reellen Zahlen.

Die rechte Seite, $(\neg\exists n, \forall k, n \geq k)$ , beinhaltet eine Verneinung und eine universelle Aussage. Die direkte Übersetzung dieser mathematischen Logik in Worte sagt, dass es keine Zahl $n \) gibt, die größer oder gleich jeder anderen Zahl$ k ) ist. Das ist gleichbedeutend damit zu sagen, dass für jede gewählte Zahl $n \) immer eine andere Zahl$ k ) existieren wird, die größer ist, da keine Zahl die Eigenschaft erfüllen kann, die größte zu sein. In der Welt der natürlichen Zahlen bedeutet das, dass es keine größte natürliche Zahl gibt.

Die Umformung von der rechten zur linken Seite und umgekehrt kann wie folgt mathematisch gerechtfertigt werden:

Beginnen wir mit der rechten Seite, $(\neg\exists n, \forall k, n \geq k)$ . Die Verneinung einer Existenzaussage kann umgeformt werden in eine universelle Aussage mit einer verneinten Bedingung: $(\forall n, \neg (\forall k, n \geq k))$ .

Die Verneinung der Bedingung $(\forall k, n \geq k)$ wird zu $(\exists k, \neg (n \geq k))$ . Nach den Gesetzen der Logik ist $\neg (n \geq k)$ äquivalent zu $(n < k)$ .

Somit erhalten wir die äquivalente Aussage $(\forall n, \exists k, n < k)$ , welche identisch ist mit der linken Seite der Äquivalenz.

Diese Schritte zeigen, dass die linke und die rechte Seite der ursprünglichen Gleichung tatsächlich das Gleiche ausdrücken. Die Unendlichkeit der natürlichen Zahlen (oder reellen Zahlen) bedeutet, dass es immer eine Zahl gibt, die größer ist also eine andere gegebene Zahl, und es kann nie eine Zahl geben, die größer oder gleich allen anderen Zahlen ist.

ii) Gilt die Aussage $\forall n, \exists k, k > n$

- für $n, k \in N$ ?

Ja, gilt da man für jedes $n$ das $k$ also $n + 1$ wählen kann und $n < n + 1$ gilt. Somit ist die Aussage wahr.

- für $n, k \in R \cup {\infty}$ , wobei $\infty > x$ für alle $x \in R$ ?

Fall n = $\infty$ :

Es gibt kein k was grösser ist also n, da $\infty$ definitionsgemäß ( $\infty > x$ für alle $x \in R$ ) größer ist also alle reellen Zahlen $⟹$ Für diesen Fall gibt es kein k > n, weshalb die Aussage nicht stimmt.

■

iii) Zeigen Sie: Es gibt unendlich viele Primzahlen. Satz des Euklids

ZZ: Es gibt unendlich viele Primzahlen

Beweis per Widerspruch:

Beweis:

Angenommen es gäbe nur endlich viele Primzahlen (Genauer: n Primzahlen)
Bezeichne diese mit $p_{1}, p_{2}, \dots, p_{n - 1}, p_{n}$
Betrachte nun die Zahl $q = p_{1}, p_{2}, \dots, p_{n - 1}, p_{n} + 1 = i = 1 Π n p_{i} + 1$
$q$ ist nun ebenfalls eine Primzahl (Erklärung: Da alle nicht Primzahlen durch die Primfaktorzerlegung darstellbar sind, aber q nicht, da q durch Primzahlen und einem +1 am Ende dargestellt wird. Das +1 macht also q selbst zu einer Primzahl)
Dies ist jedoch ein Widerspruch in der Annahme, dass es nur die Primzahlen $p_{1}, p_{2}, \dots, p_{n - 1}, p_{n}$ gibt.

Additum aus der Übung:

Satz des Ausschlusses $A \lor \neg A$

■

b) Die Gleichheit von Mengen ist wie folgt definiert:

Aufgabenstellung

$S \subseteq T g.d.w. \forall x, x \in S ⟹ x \in T$ $S = T g.d.w. S \subseteq T \land T \subseteq S$
Zeigen sie:

i) Für alle Mengen $S$ und $T$ gilt: $S = T$ g.d.w. $\forall x, x \in S \Leftrightarrow x \in T$ .

ii) Für alle Sprachen $A, B, C$ über einem Alphabet $Σ$ gilt: $A \cdot (B \cup C) = A \cdot B \cup A \cdot C$ .

iii) ${n \in N ∣ n$ ist prim und $n \geq 3} = {n \in N ∣ n$ ist prim und ungerade $}$ .

i) Für alle Mengen $S$ und $T$ gilt: $S = T$ g.d.w. $\forall x, x \in S \Leftrightarrow x \in T$ .

ZZ: S = T unter der Annahme $\forall x, x \in S \Leftrightarrow x \in T$

Beweis:

1.Schritt: Zeige $S \subseteq T$
- $\forall x g i lt w e nn x in S i s t, i s t es a u c h in T$ $⟹$ $S \subseteq T$
1. Schritt: Zeige $T \subseteq S$
- $\forall x g i lt w e nn x in T i s t, i s t es a u c h in S$ $⟹$ $T \subseteq S$

$⟹$ Aus der Definition ergibt sich $S = T g.d.w. S \subseteq T \land T \subseteq S$ dies ist hier gegeben also ist der Beweis abgeschlossen

■

ii) Für alle Sprachen $A, B, C$ über einem Alphabet $Σ$ gilt: $A \cdot (B \cup C) = A \cdot B \cup A \cdot C$ .

Konkatenation Def.: $L_{1} L_{2} = {w_{1} w_{2} ∣ w_{1} \in L_{1}, w_{2} \in L_{2}}$

ZZ: $A \cdot (B \cup C) = A \cdot B \cup A \cdot C$

Definitionen(Grundlegende Operationen auf formalen Sprachen):

Konkatenation $(A \cdot B)$ : Die Sprache, die aus allen möglichen Kombinationen von Strings besteht, wobei ein String aus $A$ $d i re k t g e f o l g t v o n e in e m St r in g a u s$ B$$ ist. Das heißt, für jedes $(x \in A)$ und jedes $(y \in B)$ , gehört der String $(x \cdot y)$ zu $(A \cdot B)$ .
Vereinigung $(B \cup C)$ : Die Sprache, die alle Strings enthält, die in $(B)$ oder $(C)$ sind. Ein String $(y)$ gehört zu $(B \cup C)$ , wenn $(y \in B)$ oder $(y \in C)$ .

Beweis:

Teil 1:
- Sei $w$ ein beliebiges Element aus $A \cdot B \cup C$
- Nach Definition der Konkatenation gibt es einen String $x \in A$ und einen String $y \in (B \cup C)$ , sodass $w = x \cdot y$
- Da $y \in (B \cup C)$ , ist $y$ entweder in $B$ oder in $C$
  - wenn $y$ in $B$ bedeutet es also für $w$ folgendes: $w = x \cdot y \in A \cdot B$
  - wenn $y$ in $C$ bedeutet es also für $w$ folgendes: $w = x \cdot y \in A \cdot C$ $⟹$ Jedes Element $w$ was in $A \cdot (B \cup C)$ ist also auch in $A \cdot B \cup A \cdot C$ enthalten $⟹$ Daraus lässt sich herleiten, dass: $A \cdot (B \cup C) \subseteq (A \cdot B \cup A \cdot C)$
Teil 2:
- Sei $w$ ein beliebiges Element aus $A \cdot B \cup A \cdot C$
- Das bedeutet $w$ ist entweder in $A \cdot B$ oder $A \cdot C$
  - wenn $w \in A \cdot B$ , dann gibt es einen String $x \in A$ und $y \in B$ , sodass $w = x \cdot y$
  - wenn $w \in A \cdot C$ , dann gibt es einen String $x \in A$ und $y \in C$ , sodass $w = x \cdot y$
- In beiden Fällen ist $y \in B$ oder $y \in C$ , also $y \in (B \cup C)$
- Daher gilt $w = x \cdot y \in A \cdot (B \cup C)$ $⟹$ Daher schließt sich $(A \cdot B \cup A \cdot C) \subseteq (A \cdot (B \cup C))$

Schlussfolgerung: $A \cdot (B \cup C) = A \cdot B \cup A \cdot C$

■

iii) ${n \in N ∣ n$ ist prim und $n \geq 3} = {n \in N ∣ n$ ist prim und ungerade $}$

Z.Z.: Alle Primzahlen größer gleich 3 sind ungerade

Definitionen:

1. Sei d (n) definiert als die Teileranzahlfunktion d (n) := ∣ {d \in N : d ∣ d} ∣ 2. So wird P Primzahlen wie folgt definiert: P = {n \in N \ {1} ∣ d (n) = 2} 3. Definition gerade Zahlen: 2 k

Beweis: Beweis durch Widerspruch

Angenommen, $x$ ist eine gerade Primzahl größer als 2
Dann gilt: $\exists k \in N : 2 k = x$
Für die gerade Primzahl $x$ würde dies bedeuten, dass: $d (x) = 3$ , da $1$ , $2$ , und $x$ Teiler von $x b z w .2 k$ sind.
Dies widerspricht jedoch der Definition $P$ wo gilt, dass: $P = {n \in N ∣ d (n) = 2}$

$⟹$ Da $x$ mehr als zwei Teiler hat, kann $x$ keine Primzahl sein. Somit sind alle Primzahlen größer als 2 ungerade, was die zu zeigende Behauptung bestätigt.

■

c) Die Konkatenation $v \cdot w$ (alternativ $v w$ ) zweier Wörter über einem Alphabet $Σ$ ist rekursiv definiert durch:

Aufgabenstellung

$ε \cdot w = w$ $a v \cdot w = a (v \cdot w)$
Alternativ kann man diese Definition auch so schreiben:
$v \cdot w = {w a (v^{'} \cdot w) falls v = ε falls v = a v^{'}$
Zeigen Sie, dass für alle Wörter $u, v, w$ gilt: $u \cdot (v \cdot w) = (u \cdot v) \cdot w$ . Verwenden Sie vollständige Induktion (siehe Skript, Kapitel 2) über die Länge von $u$ .

Z.Z:

u \cdot (v \cdot w) = (u \cdot v) \cdot w

Induktionsanfang:

ε \cdot (v \cdot w) (ε \cdot v) \cdot w = v \cdot w = v \cdot w

Da das leere Wort $ε$ das neutrale Element der Konkatenation ist, sind die beiden Ausdrücke gleich.

Induktionsschritt:

Induktionsannahme: - Angenommen, die Gleichung: $u \cdot (v \cdot w) = (u \cdot v) \cdot w$ gilt für alle $u$ der Länge $n$ .

Nun müssen wir zeigen, dass die Gleichung auch für alle $u$ der Länge $n + 1$ gilt

Sei $u$ ein Wort der Länge $n + 1$ . Dann lässt sich $u$ schreiben als $u = a u^{'}$ , wobei $a$ ein Buchstabe aus $Σ$ und $u^{'}$ ein Wort der Länge $n$ ist.

Wir verwenden die rekursive Definition der Konkatenation und die Induktionsannahme:

u \cdot (v \cdot w) = a u^{'} \cdot (v \cdot w)

= a (u^{'} \cdot (v \cdot w))

(gemäß der rekursiven Definition)

Nun wenden wir die Induktionsannahme auf $u^{'}$ an, da $∣ u^{'} ∣ = n$ :

= a ((u^{'} \cdot v) \cdot w)

= (a u^{'} \cdot v) \cdot w

(wieder rekursive Definition)

Und da $a u^{'} = u$ ist, haben wir:

= (u \cdot v) \cdot w

Damit ist der Induktionsschritt bewiesen und die Eigenschaft, dass die Konkatenation assoziativ ist, gilt für alle Wörter $u$ , $v$ , und $w$ über einem Alphabet $Σ$ .

■

FSK0-2 Wörter, Sprachen

a) Seien $Σ = {a, b}$ , $U = {aab, baa}$ und $V = {aa, bb}$

Aufgabenstellung

Geben Sie Wörter $u, v, w, x \in Σ^{*}$ an, sodass

$u \in U^{*}$ und $u \in / V^{*}$ ;

$v \in / U^{*}$ und $v \in V^{*}$ ;

$w \in U^{*}$ und $w \in V^{*}$ ;

$x \in / U^{*}$ und $x \in / V^{*}$ .

Hinweis: Für eine Menge von Symbolen $S$ bezeichnen wir mit $S^{*}$ die Menge aller endlichen Folgen von Symbolen aus $S$ (z.B. ${a, b}^{*} = {ϵ, a, b, aa, ab, ba, bb, aaa, \dots}$ ).

Antworten

Wähle $u = aab$ . Dieses Wort ist in $U^{*}$ , da es direkt in $U$ vorkommt, jedoch nicht in $V^{*}$ , weil es nicht durch eine gerade Anzahl von $a$ s und $b$ s gebildet werden kann.
Wähle $v = aa$ . Dieses Wort ist in $V^{*}$ , da es direkt in $V$ vorkommt, jedoch nicht in $U^{*}$ , weil es nicht in $U$ vorkommt oder durch Elemente von $U$ gebildet werden kann.
Wähle $w = aabaabaa$ . Dieses Wort ist sowohl in $U^{*}$ als auch in $V^{*}$ , weil es durch Konkatenation der Elemente von $U$ sowie $V$ gebildet werden kann. Besser das leere Wort, da dies in beides ist $ε$
Wähle $x = aba$ . Dieses Wort ist in keiner der beiden Mengen $U^{*}$ oder $V^{*}$ , weil es nicht durch Konkatenation der Elemente von $U$ oder $V$ gebildet werden kann.

b) Sei $w = ababababbbb cc baaaaabaa c aaabbbbbaba$

Aufgabenstellung

Geben Sie alle Teilwörter $v$ von $w$ an, auf die alle der folgenden Eigenschaften zutreffen:

$∣ v ∣ = 4$ , die Länge von $v$ ist 4;

$v [1] = a$ , das erste Symbol in $v$ ist a;

$#_{b} (v) > 0$ , die Anzahl von Vorkommen von $b$ in $v$ ist größer als 0.

Um die Aufgabe zu lösen, suchen wir nach allen Teilwörtern ( v ) des gegebenen Wortes ( w ), die folgende Bedingungen erfüllen:

Die Länge von ( v ) beträgt 4 Zeichen (( |v| = 4 )).
Das erste Zeichen von ( v ) ist ( a ) (( v[1] = a )).
( v ) enthält mindestens ein ( b ) ((_b(v) > 0 )).

Wir beginnen, indem wir das gegebene Wort ( w ) betrachten: [ w = ababababbbbccbaaaaabaacaaabbbbbaba ]

Schritte zur Lösung:

Identifizierung aller möglichen 4-Zeichen-Teilwörter von ( w ): Wir extrahieren jedes mögliche 4-Zeichen-Teilwort beginnend mit jedem Index in ( w ), solange die Länge des Teilworts 4 Zeichen beträgt.
Filterung der Teilwörter: Jedes gefundene Teilwort wird daraufhin überprüft, ob es mit einem ( a ) beginnt und mindestens ein ( b ) enthält.

Beispielhafte Durchführung:

Extrahiere 4-Zeichen-Teilwörter und prüfe die Bedingungen.

Angenommen, wir beginnen beim ersten Index:

( w[0:4] = abab )
- Beginnt mit ( a ): ja
- Enthält ( b ): ja
- Dieses Teilwort wird behalten.

Ein weiteres Beispiel beim zweiten Index:

( w[1:5] = baba )
- Beginnt mit ( a ): nein
- Dieses Teilwort wird nicht behalten.

Wir führen diesen Prozess für das gesamte Wort durch.

Alle gültigen Teilwörter:

Nach Überprüfung aller Teilwörter erhält man folgende gültige 4-Zeichen-Teilwörter:

abab
abab
abab
abab
abbb
abbc
aaba
aaab
aaca
acaa
abbb
bbbb
bbba

Diese Liste gibt alle möglichen Teilwörter an, die die gegebenen Bedingungen erfüllen.

FSK0-3 Äquivalenzrelationen

Aufgabenstellung

Eine Relation zwischen zwei Mengen $M, N$ ist eine Menge $R \subseteq M \times N$ von Paaren bestehend je aus einem Element aus $M$ und einem aus $N$ . $M$ und $N$ können hierbei beliebige Mengen sein. Ist $(p, q) \in R$ , so schreibt man auch $R (p, q)$ , $pRq$ oder $p \sim q$ .

Ist klar, um welche Relation es sich handelt, kann man auch $p \sim q$ schreiben.

Eine Relation $R$ heißt Äquivalenzrelation, wenn

die zugrundeliegenden Mengen gleich sind: $M = N$ ;

für alle $x \in M$ gilt $x R x$ (d.h. $R$ ist reflexiv);

für alle $x, y \in M$ gilt $x R y$ impliziert $y R x$ (d.h. $R$ ist symmetrisch);

für alle $x, y, z \in M$ gilt $x R y$ und $y R z$ impliziert $x R z$ (d.h. $R$ ist transitiv).

Eine Äquivalenzklasse $K$ einer Äquivalenzrelation $R$ ist eine maximale Menge von Elementen $u, v, w, \dots \in M$ sodass alle Elemente von $K$ durch $R$ in Beziehung stehen: $u R v$ , $v R u$ , $v Rw$ , etc. “Maximal” bedeutet, dass es kein Element $x \in M$ gibt, das nicht in $K$ ist, aber mit allen Elementen von $K$ in Beziehung steht. Der Index einer Äquivalenzrelation ist die Anzahl ihrer Äquivalenzklassen.

Beispiel: Die Relation
${(u, v) ∣ u, v \in N und u geteilt durch 3 hat denselben Rest wie v geteilt durch 3}$
ist eine Äquivalenzrelation. Ihre Äquivalenzklassen sind ${0, 3, 6, \dots}$ , ${1, 4, 7, \dots}$ und ${2, 5, 8, \dots}$ . Sie hat somit Index 3.

Geben Sie für die folgenden Relationen jeweils an, ob sie Äquivalenzrelationen sind. Berechnen Sie außerdem den Index von mindestens zwei der Äquivalenzrelationen.

Aufgabenstellungen falsch muss ausgebessert werden von mir

a) $R_{1} \subseteq {0, 1, 2, 3} \times {0, 1, 2, 3}$ Mit $0 R 1, 2 R 1, 3 R 1$ (und sonst $\neg x R y$ ).

b) $R_{2} \subseteq {0, 1, 2} \times {0, 1, 2}$ Mit $0 R 2, 1 R 2, 2 R 2$ (und sonst $\neg x R y$ ).

c) $R_{3} \subseteq {0, 1, 2} \times {0, 1, 2}$ Mit $0 R 3, 1 R 3, 2 R 3, 1 R 3, 2 R 3, 2 R 3, 1 R 3$ (und sonst $\neg x R y$ ).

d) $R_{4} = {(p, q) ∣$ Die Personen $p, q$ haben das gleiche Geburtsjahr $}$ .

e) $R_{5} = {(u, v) ∣$ Die Wörter $u$ und $v$ über dem Alphabet ${a, b}$ stimmen in den ersten $k$ Positionen überein, wobei $k$ die Länge des kürzeren Wortes ist $}$ .

🎓 MyUniNotes

Explorer

FSK-ÜB-0

Wiederholen:

FSKO-1 Fundamentale Beweisstrategien

a) Die folgende Tabelle fasst zusammen, wie man mit Aussagen, die bestimmte logische Operationen enthalten, umgeht.

i) Zeigen Sie: $(\forall n, \exists k, k > n) \Leftrightarrow (\neg\exists n, \forall k, n \geq k)$

i) Zeigen Sie: $(\forall n, \exists k, k > n) \Leftrightarrow (\neg\exists n, \forall k, n \geq k)$

Linke Seite: $(\forall n, \exists k, k > n)$

Rechte Seite: $(\neg\exists n, \forall k, n \geq k)$

Gesamtaussage: $(\forall n, \exists k, k > n) \Leftrightarrow (\forall n, \exists k, k > n)$

i) Zeigen Sie: $(\forall n, \exists k, k > n) \Leftrightarrow (\neg\exists n, \forall k, n \geq k)$

ii) Gilt die Aussage $\forall n, \exists k, k > n$

- für $n, k \in N$ ?

- für $n, k \in R \cup {\infty}$ , wobei $\infty > x$ für alle $x \in R$ ?

iii) Zeigen Sie: Es gibt unendlich viele Primzahlen. Satz des Euklids

Additum aus der Übung:

b) Die Gleichheit von Mengen ist wie folgt definiert:

i) Für alle Mengen $S$ und $T$ gilt: $S = T$ g.d.w. $\forall x, x \in S \Leftrightarrow x \in T$ .

ii) Für alle Sprachen $A, B, C$ über einem Alphabet $Σ$ gilt: $A \cdot (B \cup C) = A \cdot B \cup A \cdot C$ .

iii) ${n \in N ∣ n$ ist prim und $n \geq 3} = {n \in N ∣ n$ ist prim und ungerade $}$

c) Die Konkatenation $v \cdot w$ (alternativ $v w$ ) zweier Wörter über einem Alphabet $Σ$ ist rekursiv definiert durch:

FSK0-2 Wörter, Sprachen

a) Seien $Σ = {a, b}$ , $U = {aab, baa}$ und $V = {aa, bb}$

Antworten

b) Sei $w = ababababbbb cc baaaaabaa c aaabbbbbaba$

Schritte zur Lösung:

Beispielhafte Durchführung:

Alle gültigen Teilwörter:

FSK0-3 Äquivalenzrelationen

a) $R_{1} \subseteq {0, 1, 2, 3} \times {0, 1, 2, 3}$ Mit $0 R 1, 2 R 1, 3 R 1$ (und sonst $\neg x R y$ ).

b) $R_{2} \subseteq {0, 1, 2} \times {0, 1, 2}$ Mit $0 R 2, 1 R 2, 2 R 2$ (und sonst $\neg x R y$ ).

c) $R_{3} \subseteq {0, 1, 2} \times {0, 1, 2}$ Mit $0 R 3, 1 R 3, 2 R 3, 1 R 3, 2 R 3, 2 R 3, 1 R 3$ (und sonst $\neg x R y$ ).

d) $R_{4} = {(p, q) ∣$ Die Personen $p, q$ haben das gleiche Geburtsjahr $}$ .

e) $R_{5} = {(u, v) ∣$ Die Wörter $u$ und $v$ über dem Alphabet ${a, b}$ stimmen in den ersten $k$ Positionen überein, wobei $k$ die Länge des kürzeren Wortes ist $}$ .

f) $R_{6} = {(p, q) ∣ p, q \in N, P + q$ ist gerade $}$ .

Graph View

Table of Contents

Backlinks

🎓 MyUniNotes

Explorer

FSK-ÜB-0

Wiederholen:

FSKO-1 Fundamentale Beweisstrategien

a) Die folgende Tabelle fasst zusammen, wie man mit Aussagen, die bestimmte logische Operationen enthalten, umgeht.

i) Zeigen Sie: (∀n,∃k,k>n)⇔(¬∃n,∀k,n≥k)

i) Zeigen Sie: (∀n,∃k,k>n)⇔(¬∃n,∀k,n≥k)

Linke Seite: (∀n,∃k,k>n)

Rechte Seite: (¬∃n,∀k,n≥k)

Gesamtaussage: (∀n,∃k,k>n)⇔(∀n,∃k,k>n)

i) Zeigen Sie: (∀n,∃k,k>n)⇔(¬∃n,∀k,n≥k)

ii) Gilt die Aussage ∀n,∃k,k>n

- für n,k∈N?

- für n,k∈R∪{∞}, wobei ∞>x für alle x∈R?

iii) Zeigen Sie: Es gibt unendlich viele Primzahlen. Satz des Euklids

Additum aus der Übung:

b) Die Gleichheit von Mengen ist wie folgt definiert:

i) Für alle Mengen S und T gilt: S=T g.d.w. ∀x,x∈S⇔x∈T.

ii) Für alle Sprachen A,B,C über einem Alphabet Σ gilt: A⋅(B∪C)=A⋅B∪A⋅C.

iii) {n∈N∣n ist prim und n≥3}={n∈N∣n ist prim und ungerade }

c) Die Konkatenation v⋅w (alternativ vw) zweier Wörter über einem Alphabet Σ ist rekursiv definiert durch:

FSK0-2 Wörter, Sprachen

a) Seien Σ={a,b}, U={aab,baa} und V={aa,bb}

Antworten

b) Sei w=ababababbbbccbaaaaabaacaaabbbbbaba

Schritte zur Lösung:

Beispielhafte Durchführung:

Alle gültigen Teilwörter:

FSK0-3 Äquivalenzrelationen

a) R1​⊆{0,1,2,3}×{0,1,2,3} Mit 0R1,2R1,3R1 (und sonst ¬xRy).

b) R2​⊆{0,1,2}×{0,1,2} Mit 0R2,1R2,2R2 (und sonst ¬xRy).

c) R3​⊆{0,1,2}×{0,1,2} Mit 0R3,1R3,2R3,1R3,2R3,2R3,1R3 (und sonst ¬xRy).

d) R4​={(p,q)∣ Die Personen p,q haben das gleiche Geburtsjahr}.

e) R5​={(u,v)∣ Die Wörter u und v über dem Alphabet {a,b} stimmen in den ersten k Positionen überein, wobei k die Länge des kürzeren Wortes ist}.

f) R6​={(p,q)∣p,q∈N,P+q ist gerade}.

Graph View

Table of Contents

Backlinks

i) Zeigen Sie: $(\forall n, \exists k, k > n) \Leftrightarrow (\neg\exists n, \forall k, n \geq k)$

i) Zeigen Sie: $(\forall n, \exists k, k > n) \Leftrightarrow (\neg\exists n, \forall k, n \geq k)$

Linke Seite: $(\forall n, \exists k, k > n)$

Rechte Seite: $(\neg\exists n, \forall k, n \geq k)$

Gesamtaussage: $(\forall n, \exists k, k > n) \Leftrightarrow (\forall n, \exists k, k > n)$

i) Zeigen Sie: $(\forall n, \exists k, k > n) \Leftrightarrow (\neg\exists n, \forall k, n \geq k)$

ii) Gilt die Aussage $\forall n, \exists k, k > n$

- für $n, k \in N$ ?

- für $n, k \in R \cup {\infty}$ , wobei $\infty > x$ für alle $x \in R$ ?

i) Für alle Mengen $S$ und $T$ gilt: $S = T$ g.d.w. $\forall x, x \in S \Leftrightarrow x \in T$ .

ii) Für alle Sprachen $A, B, C$ über einem Alphabet $Σ$ gilt: $A \cdot (B \cup C) = A \cdot B \cup A \cdot C$ .

iii) ${n \in N ∣ n$ ist prim und $n \geq 3} = {n \in N ∣ n$ ist prim und ungerade $}$

c) Die Konkatenation $v \cdot w$ (alternativ $v w$ ) zweier Wörter über einem Alphabet $Σ$ ist rekursiv definiert durch:

a) Seien $Σ = {a, b}$ , $U = {aab, baa}$ und $V = {aa, bb}$

b) Sei $w = ababababbbb cc baaaaabaa c aaabbbbbaba$

a) $R_{1} \subseteq {0, 1, 2, 3} \times {0, 1, 2, 3}$ Mit $0 R 1, 2 R 1, 3 R 1$ (und sonst $\neg x R y$ ).

b) $R_{2} \subseteq {0, 1, 2} \times {0, 1, 2}$ Mit $0 R 2, 1 R 2, 2 R 2$ (und sonst $\neg x R y$ ).

c) $R_{3} \subseteq {0, 1, 2} \times {0, 1, 2}$ Mit $0 R 3, 1 R 3, 2 R 3, 1 R 3, 2 R 3, 2 R 3, 1 R 3$ (und sonst $\neg x R y$ ).

d) $R_{4} = {(p, q) ∣$ Die Personen $p, q$ haben das gleiche Geburtsjahr $}$ .

e) $R_{5} = {(u, v) ∣$ Die Wörter $u$ und $v$ über dem Alphabet ${a, b}$ stimmen in den ersten $k$ Positionen überein, wobei $k$ die Länge des kürzeren Wortes ist $}$ .

f) $R_{6} = {(p, q) ∣ p, q \in N, P + q$ ist gerade $}$ .