Informatiker Board | Theoretische Informatik | Induktiver Beweis mittels Operation und Anfangsmenge (?)

Informatiker Board » Themengebiete » Theoretische Informatik » Induktiver Beweis mittels Operation und Anfangsmenge (?) » Antwort erstellen

» Hallo Gast [Anmelden|Registrieren]

Antwort erstellen

Benutzername:

(du bist nicht eingeloggt!)

Thema:

Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33

einfacher Modus erweiterter Modus

aktuellen Tag schließen

alle Tags schließen

Spamschutz:
Text aus Bild eingeben

URLs automatisch umwandeln: fügt automatisch [url] und [/url] in Internet-Adressen ein.
Smilies in diesem Beitrag deaktivieren.
BBCode in diesem Beitrag deaktivieren.
Bilder in diesem Beitrag deaktivieren.
Signatur anzeigen: Soll die im Profil eingestellte Signatur an den Beitrag angehangen werden?
Nachrichtenlänge überprüfen

Die letzten 10 Beiträge

David1979

Ahhhh,

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

David1979

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

Tobias

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

David1979

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

Tobias

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.

David1979

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

Kadeos

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

mercany

Hallo,

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

Gruß, mercany

Kadeos

Ich hoffe, ihr habt alle ein "Helfergen" Augenzwinkern

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

Kadeos

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.../ueb/blatt1.pdf)
helfen könnt. Es ist die Nummer 6, an der ich so verzweifle.