[MaLo] Frage zu Übung 7 Aufgabe 1c

[FoSAP] Formale Systeme, Automaten, Prozesse
[BuK] Berechenbarkeit und Komplexität
[MaLo] Mathematische Logik

Frage zu Übung 7 Aufgabe 1c

Beitragvon Manfred » 29.09.10 12:14

Hallo,

meine eigene Lösung für die Aufgabe würde ungefähr so aussehen:

Bild

Laut Globalübungsmitschrift wird allerdings diese Lösung hier vorgeschlagen:

Bild

Was ich nicht verstehe: Warum soll das funktionieren? Wenn ich das richtig sehe wird hier doch nicht, wie in der Aufgabenstellung gefordert, eine Aussage über alle natürlichen Zahlen gemacht, sondern nur über diejenigen, die <= 13 sind. Außerdem verwirrt mich die Tatsache, dass hier nur verschiedene Potenzen von Funktionen verglichen werden, wie kann man daraus eine Aussage über die Anzahl der Elemente ableiten?

Hier noch mal die zugehörige Aufgabe:

Bild
Benutzeravatar
Manfred
 
Beiträge: 38
Registriert: 03.11.08 20:01
Wohnort: in deiner Nähe
Studiengang: Informatik (M.Sc.)
Studiert seit: WS 09/10
Anwendungsfach: E-Technik

Re: Frage zu Übung 7 Aufgabe 1c

Beitragvon MartinL » 29.09.10 13:19

Der Trick liegt darin, dass es wenn in der Menge maximal 13 Elements sind irgendwann bei der Funktionsanwendung im Kreis geht. Irgendwann muss f auf ein Element abbilden, was bereits in der Menge drin ist und ab diesem Zeitpunkt bildet die funktion dann immer wieder auf Elemente ab die bereits drin waren (das liegt an der Eindeutigkeit des Ziels der Funktion)

Mal ein kleines Beispiel für die +3 Funktion in Z_5:

starten wir einfach mal bei 0
f(0) = 3
f(3) = 1
f(1) = 4
f(4) = 2
f(2) = 0

Und nun gehts wieder bei f(0) los - es dreht sich also im Kreis.
Das muss auch immer der Fall sein, wenn die Menge der Potenzen endlich ist.

Und genau das sagt auch die Formel aus der Lösung. Für alle Werte a in A ist der Funktionswert zweier Potenzen kleiner 13 gleich. Dann gibt es auch nur weniger als 13 Elemente in dieser Potenzenmenge und umgekehrt ist die Formel auch bei beschränkter Potenzenmenge wahr, weil irgendwo vor dem 13ten Element der oben beispielhaft angedeutete Kreis geschlossen wird.
MartinL
 
Beiträge: 531
Registriert: 23.01.07 20:48
Studiert seit: WS 06/07
Anwendungsfach: Mathe

Re: Frage zu Übung 7 Aufgabe 1c

Beitragvon Manfred » 29.09.10 13:43

Gute Erklärung, danke dir :)
Benutzeravatar
Manfred
 
Beiträge: 38
Registriert: 03.11.08 20:01
Wohnort: in deiner Nähe
Studiengang: Informatik (M.Sc.)
Studiert seit: WS 09/10
Anwendungsfach: E-Technik


Zurück zu Theoretische Informatik