Informatiker Board | Druckvorschau: Induktiver Beweis mittels Operation und Anfangsmenge (?)

Geschrieben von Kadeos am 21.11.2006 um 16:13:

Induktiver Beweis mittels Operation und Anfangsmenge (?)

Hallo,

ich bin gerade dabei, mich für eine Klausur vorzubereiten und gehe einige , vorher nicht gelöste Aufgaben durch.Nun verzweifle ich gerade an einer Aufgabe des ersten Übungsblattes und hoffe, dass ihr mir helfen könnt.
(http://www-pscb.informatik.tu-cottbus.de/%7Ewwwpscb/lehre/Inf1/ueb/blatt1.pdf)
helfen könnt. Es ist die Nummer 6, an der ich so verzweifle.

Geschrieben von Kadeos am 21.11.2006 um 16:46:

Ich hoffe, ihr habt alle ein "Helfergen" Augenzwinkern

Da gibt es nämlich so einige andere Aufgaben, die ich nicht ganz verstehe...

Geschrieben von mercany am 21.11.2006 um 19:29:

Hallo,

wo hängst du denn? Bekommst du die Definition aufgeschrieben?

Gruß, mercany

Geschrieben von Kadeos am 22.11.2006 um 11:06:

Ich blick da einfach nicht durch......die Definition bekomme ich auch nicht aufgeschrieben

Geschrieben von David1979 am 22.11.2006 um 13:17:

Hallo,

das sieht für mich so aus als müsstest du die induktiv definierte Menge nach folgendem rekursiven Schema von unten nach oben aufbauen:

$[latex]Z_{0} & = & \{0\} \\ Z_{i+1} & = & Z_{i} \cup \{R(i) \}[/latex]$

wobei [latex]$R$[/latex]

ein Regelwerk (Operationen) zur Erzeugung neuer Wörter in [latex]Z[/latex]

ist und $[latex]i, i \in N[/latex]$ ein Index anhand dessen das neue Wort eindeutig bestimmt werden kann.

So ergibt sich hieraus nach jeder i-ten Schicht ein neues Wort für [latex]Z[/latex]

. Die Angabe $[latex]F_{i}[/latex]$ stellt dann jeweils alle Elemente der i-ten Schicht dar.

Das ist nur eine Idee. Vielleicht hilft dir das ja weiter Augenzwinkern

Gruß, David

Geschrieben von Tobias am 22.11.2006 um 22:28:

Du musst also A und die Operation so wählen, dass $[latex]Z = A \cup \mathcal{O}(Z)[/latex]$ gilt.

Mein Vorschlag wäre:

$[latex] Z_0 = A := \{0 \}, \quad Z_{i+1} = \mathcal{O}(Z_i) = Z_i \cup \{ 2x+1 \; | \; x \in Z_i \}[/latex]$ .

Hier ist dann $[latex] Z = Z_\infty[/latex]$ der Fixpunkt der Operation und somit die erste (und kleinste) Iterierte, die die Gleichung erfüllt (du kannst leicht zeigen, dass $[latex] \mathcal{O}(Z) = Z[/latex]$ ).

Die nachfolgene Induktion geht nach 08/15-Schema:

Induktionsanfang:
$[latex]0 \in Z, 0 \in \mathbb{N}: 2^0 - 1 = 0[/latex]$ .

Induktionshypothese:
$[latex]x \in Z[/latex]$ und es existiere $[latex]n \in \mathbb{N}[/latex]$ , so dass gelte: [latex]x = 2^n - 1[/latex]

.

Induktionsschluss:
x geht über in 2x + 1. Verwende hier die Induktionshypothese für x.

Geschrieben von David1979 am 22.11.2006 um 22:47:

Zitat:

Original von Tobias
$[latex] Z_{i+1} = \mathcal{O}(Z_i) = Z_i \cup \{ 2x+1 \; | \; x \in Z_i \}[/latex]$ .

Hmm..., müsste das nicht $[latex] Z_{i+1} = \mathcal{O}(Z_i) = Z_i \cup \{ 2x+1 \; | \; x = max(Z_i) \ \}[/latex]$ , oder so ähnlich sein , wobei man natürlich noch genauer beschreiben muss, wie der Operator max() definiert ist. Denn nur das größte Element liefert ein neues Wort für $[latex]Z_{i+1}[/latex]$ zurück, oder nicht? verwirrt

Gruß, David

Geschrieben von Tobias am 23.11.2006 um 12:04:

Deine und meine Definition liefern dieselbe Menge.

Es gilt:

$[latex]\{2x+1 \; | \; x \in Z_i\} = Z_i\backslash\{0\} \cup \{ 2x+1 \; | \; x = \max(Z_i) \}[/latex]$

Bei der Vereinigung mit [latex]Z_i[/latex]

erhält man dann Mengengleichheit:

$[latex]Z_i \cup \{2x+1 \; | \; x \in Z_i\} = Z_i \cup \big( Z_i\backslash\{0\} \cup \{ 2x+1 \; | \; x = \max(Z_i)\} \big) = Z_i \cup \{ 2x+1 \; | \; x = \max(Z_i)\}[/latex]$

Geschrieben von David1979 am 23.11.2006 um 13:15:

Vielleicht habe ich das doch noch nicht so gut verstanden, wie ich gedacht habe, deshalb schreib ich es noch mal detaillierter auf:

Es ist doch:

$[latex]Z_{0} & = & \{0\}, \mbox{nach Def.} \\ Z_{1} & = & Z_0 \cup \{2x+1 | x \in Z_0 \} = \{0\} \cup \{2 \cdot 0 + 1\} \ = \{0,1\}, \mbox{bis hier noch alles klar, weil} \ Z_0 \ \mbox{nur ein Element hat}[/latex]$

An dem Punkt hänge ich jetzt, weil [latex]Z_1[/latex]

eine Menge ist und kein einzelnes Wort, somit ist doch die Aussage für die nächste Zeile nicht genau beschrieben ist, wenn es heisst

$[latex]Z_2 & = & Z_1 \cup \{2x+1 \ | \ x \in \ Z_1\} = \{0,1\} \cup \ \{2x+1 \ | \ x \in \ \{0,1\} \}[/latex]$

Woher weiss man denn welches x aus Z ich nehmen muss? verwirrt

Geschrieben von David1979 am 23.11.2006 um 13:19:

Ahhhh, Zunge raus

jetzt seh ichs!!!! Alles klar Prost

!!

Manchmal hilft es, wenn man es einfach aufschreibt. Augenzwinkern

\\EDIT: Kurze Erklärung: Man macht die Vereinigung ja über alle x aus [latex]Z_i[/latex]

und nicht nur über eins.

Gruß und sorry, David

P.S: Kann man hier auch Beiträge herauslöschen großes Grinsen