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

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

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Induktiver Beweis mittels Operation und Anfangsmenge (?)

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

Kadeos
Grünschnabel

Dabei seit: 21.11.2006
Beiträge: 4

Induktiver Beweis mittels Operation und Anfangsmenge (?)

Zitatantwort auf diesen Beitrag erstellen

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.

21.11.2006 16:13

Nehmen Sie Kadeos in Ihre Freundesliste auf

Kadeos
Grünschnabel

Dabei seit: 21.11.2006
Beiträge: 4

Ich hoffe, ihr habt alle ein "Helfergen" Augenzwinkern

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

21.11.2006 16:46

mercany mercany ist männlich

Jungspund

Dabei seit: 06.09.2006
Beiträge: 21
Herkunft: Bielefeld

Hallo,

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

Gruß, mercany

__________________
"Dummheiten sind nie überflüssig

21.11.2006 19:29

Nehmen Sie mercany in Ihre Freundesliste auf

Kadeos
Grünschnabel

Dabei seit: 21.11.2006
Beiträge: 4

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

22.11.2006 11:06

David1979
Mitglied

Dabei seit: 26.09.2006
Beiträge: 27

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

22.11.2006 13:17

Nehmen Sie David1979 in Ihre Freundesliste auf

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

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.

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Tobias: 22.11.2006 22:28.

22.11.2006 22:28

Nehmen Sie Tobias in Ihre Freundesliste auf

David1979
Mitglied

Dabei seit: 26.09.2006
Beiträge: 27

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

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von David1979: 22.11.2006 23:52.

22.11.2006 22:47

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

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

23.11.2006 12:04

David1979
Mitglied

Dabei seit: 26.09.2006
Beiträge: 27

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

23.11.2006 13:15

David1979
Mitglied

Dabei seit: 26.09.2006
Beiträge: 27

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

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von David1979: 23.11.2006 13:26.

23.11.2006 13:19

Baumstruktur | Brettstruktur

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