Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
-- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
--- Induktiver Beweis mittels Operation und Anfangsmenge (?) (http://www.informatikerboard.de/board/thread.php?threadid=78)
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"
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:
wobei
ein Regelwerk (Operationen) zur Erzeugung neuer Wörter in
ist und
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
. Die Angabe
stellt dann jeweils alle Elemente der i-ten Schicht dar.
Das ist nur eine Idee. Vielleicht hilft dir das ja weiter
Gruß, David
Geschrieben von Tobias am 22.11.2006 um 22:28:
Du musst also A und die Operation so wählen, dass
gilt.
Mein Vorschlag wäre:
.
Hier ist dann
der Fixpunkt der Operation und somit die erste (und kleinste) Iterierte, die die Gleichung erfüllt (du kannst leicht zeigen, dass
).
Die nachfolgene Induktion geht nach 08/15-Schema:
Induktionsanfang:
.
Induktionshypothese:
und es existiere
, so dass gelte:
.
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
.
|
Hmm..., müsste das nicht
, 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
zurück, oder nicht?
Gruß, David
Geschrieben von Tobias am 23.11.2006 um 12:04:
Deine und meine Definition liefern dieselbe Menge.
Es gilt:
Bei der Vereinigung mit
erhält man dann Mengengleichheit:
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:
An dem Punkt hänge ich jetzt, weil
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
Woher weiss man denn welches x aus Z ich nehmen muss?
Geschrieben von David1979 am 23.11.2006 um 13:19:
Ahhhh,
jetzt seh ichs!!!! Alles klar
!!
Manchmal hilft es, wenn man es einfach aufschreibt.
\\EDIT: Kurze Erklärung: Man macht die Vereinigung ja über alle x aus
und nicht nur über eins.
Gruß und sorry, David
P.S: Kann man hier auch Beiträge herauslöschen
Forensoftware: Burning Board, entwickelt von WoltLab GmbH