Seite 3 von 4
Verfasst: 10.01.2009 17:26
von DarkDragon
Also ich hab erstmal die Übung gemacht die pflicht ist.
q.e.d.
Daraus kann man eigentlich auch gleich das rechtstotal und linkseindeutig schließen. Aber ich glaub das ist noch recht schwammig oder nicht?
Verfasst: 21.04.2009 17:24
von DarkDragon
Hallo,
Ich hab wieder mal ein Problem damit. Nach einigen Stunden nachdenken komm ich immernoch nicht weiter. Wir sollen die funktionalität des Euklidischen Algorithmus zur Bestimmung des größten gemeinsamen Teilers Beweisen.
Das hier habe ich bereits:
Code: Alles auswählen
Fallunterscheidung bei ggT(m, n) und r = m mod n:
r = 0
==> n ist ggT, da es keinen größeren Teiler für n als n selbst gibt und n | m.
r != 0
==> ggT(n, r) ist ggT, denn ...
Aber ich verstehe einfach nicht warum der letzte Fall eigentlich gilt. Ich weiß dass es gilt, aber nicht warum.
Ich hätte in so einem Fall einfach k = 1 bis n durchgetestet und den letzten Wert, der m und n teilt genommen.
Ich habe es auch schon über das abziehen versucht irgendwie zu beweisen, aber ich lande immer in einer Sackgasse:
Code: Alles auswählen
r = m mod n = m - n * k ; n * (k + 1) > m, n * k < m, k in N
Warum muss ich dann nurnoch mit n und ausgerechnet dem Divisionsrest suchen?
Verfasst: 21.04.2009 18:33
von Kaeru Gaman
mal ganz ins blaue....
check mal die alte Faustregel für den ggT...
(summe aller gemeinsamen primfaktorpotenzen mit dem niedrigsten exponenten oder irgendwie so was)
dieses
> dann nurnoch mit n und ausgerechnet dem Divisionsrest suchen
könnte mit diesen primfaktorgeschichten zusammenhängen...
Verfasst: 21.04.2009 19:38
von DarkDragon
Kaeru Gaman hat geschrieben:mal ganz ins blaue....
check mal die alte Faustregel für den ggT...
(summe aller gemeinsamen primfaktorpotenzen mit dem niedrigsten exponenten oder irgendwie so was)
dieses
> dann nurnoch mit n und ausgerechnet dem Divisionsrest suchen
könnte mit diesen primfaktorgeschichten zusammenhängen...
Euh, 6. oder 7. Klasse. Ich werd glaub schon vergesslich. Graue Haare hab ich ja schon. Danke, aber für heute mach ich schluss.
[EDIT]
Hab doch noch etwas weitergemacht:
m = p * q
n = p * r
p = primfaktoren die gemeinsam sind
q, r = unterschiedliche primfaktoren
m / n = q / r
m mod n = m - int(m / n) * n = p * q - int(q / r) * p * r
Doch jetzt weiß ich wieder nicht weiter. Ich kanns noch zu einer riesigen Kette umformen, aber wirklich weiterbringen tut mich das leider nicht.
Verfasst: 21.04.2009 21:41
von gnasen
hmm genau bei dem Beweis hat unser Prof letzte Stunde aufgehört, weil die Zeit um war.
Nach der nächsten Analysis Sitzung (Freitag) kann ich dir da vllt was zu erzählen.
Verfasst: 22.04.2009 09:09
von DarkDragon
gnasen hat geschrieben:hmm genau bei dem Beweis hat unser Prof letzte Stunde aufgehört, weil die Zeit um war.
Nach der nächsten Analysis Sitzung (Freitag) kann ich dir da vllt was zu erzählen.
Das wär nicht schlecht, danke.
Aber erkennt man jetzt wenigstens wo ich immer hänge bei den Beweisen?
Verfasst: 22.04.2009 11:37
von alter Mann
geg.: m,n
r=mod(m,n)
x=int(m/n)
p=GGT(m,n)
m=x*n+r
Wenn die Summe m den Teiler p hat und ein Summand (x*n) den Teiler p hat, dann muss auch der Zweite Summand r den Teiler p haben.
Verfasst: 22.04.2009 12:07
von DarkDragon
alter Mann hat geschrieben:geg.: m,n
r=mod(m,n)
x=int(m/n)
p=GGT(m,n)
m=x*n+r
Wenn die Summe m den Teiler p hat und ein Summand (x*n) den Teiler p hat, dann muss auch der Zweite Summand r den Teiler p haben.
Hmm echt? Gibts dazu ein Mathematisches Gesetz?
[EDIT]
Achja stimmt, bei Bruchrechnung kann das gleiche gekürzt werden von Summanden, durchs Ausfaktorisieren.
Danke, das hilft mir sehr. Aber wie merkt man sich denn das ganze Zeug wenn man so sehr vergesslich ist?
Verfasst: 22.04.2009 13:44
von alter Mann
Vergesslich ist man ja nur bei Sachen, die einen nicht besonders interessieren. Also vergessen. Und wenn man es mal wieder braucht, jemanden fragen, oder wissen, wo man nachschlagen kann. Beweise führen braucht man im späteren (Berufs-)Leben so gut wie nie (wenn man nich Mathematikforschung o.ä betreibt).
Verfasst: 22.04.2009 20:06
von Karl
Hallo,
der Beweis zur Injektivität unter Komposition lässt sich über die Definition der Injektivität selbst beweisen:
all(y1,y2) (y1=y2=>x1=x2)
Hier setzt man die beiden Funktion nacheinander ein. Fertig.
Wichtige Beweisverfahren sind
vollständige Induktion (gerade bei Mengen)
direkter Beweis
indirekter Beweis
Beim indirekten Beweis darf man etwas zusätzlich etwas annehmen (dessen Unrichtigkeit man durch Widerspruch zeigt).
Wichtiges Hilfsmittel ist weiterhin die Kontrapositionsregel:
A=>B äquivalent zu -B=>-A
Mengen werden meist über eine charakteristische Funktion definiert (jedenfalls in der theoretischen Informatik).
Das Problem bei Beweis ist, dass man zum Teil "kreativ" sein muss.
Gruß
Der Karl