1.2 Beweisen oder Widerlegen

[tonico]

Hier ein Lösungsvorschlag, bin mir aber nicht sicher ob die Beweise ausreichend, korrekt oder nachvollziehbar sind :rolleyes: :

a) Aussage ist falsch, indirekter Beweis:

f(n)=\mathcal{O}(n\cdot g(n))\ \Rightarrow\ g(n)=\Theta(f(n))\ \Leftrightarrow\ f(n)=\Theta(g(n))\ \Rightarrow\ f(n)=\mathcal{O}(g(n)) :omg: Widerspruch!

EDIT: Der obige Beweis ist mit Vorsicht zu genießen, ehrlich gesagt bin ich mir inzwischen nicht mehr sicher ob damit irgendwas bewiesen ist. Am einfachsten ist es ein Gegensbeispiel anzugeben.

b) Aussage ist richtig, direkter Beweis:

a(n)=\mathcal{O}(b(n))\ \wedge\ b(n)=\mathcal{O}(c(n))

\Leftrightarrow\ \exists\ c_{1},c_{2},n_{0,1},n_{0,2}>0;\ \forall n\ge\max(n_{0,1},n_{0,2}):\ 0\leq\frac{a(n)}{c_{1}}\leq b(n)\ \wedge\ 0\leq b(n)\leq c_{2}c(n)

\Rightarrow\ 0\leq a(n)\leq c_{1}c_{2}c(n)\ \Leftrightarrow\ a(n)=\mathcal{O}(c(n))

[hebi]

ich hab eigentlich b) auch als richtige aussage rausbekommen, aber anders bewiesen --> aber als aussage stimmts!

[tonico]

ich hab eigentlich b) auch als richtige aussage rausbekommen, aber anders bewiesen --> aber als aussage stimmts!

Jetzt hast mich neugierig gemacht, welchen Ansatz hast für b) verwendet?

a) kann man ja auch einfach durch ein Gegenbeispiel mit f(n) = 1 und g(n) = n zeigen.

[LordNecro]

Ich komm eigentlich auf das selbe nur ob das wirklich als beweis zählt weiß ich net da ich ja eigentlich nur aus der abgeleiteten Seite die Obergrenze folge und mit der linken gar nichts mache. Logisch is es ja das es net stimmt weil n ja net konstant ist aber erklären könnt ichs net so richtig vielleicht könnten andere noch ihre meinung dazu äussern?

mfg

[Lillipip]

Also ich werde b) so erklären:

Wenn a(n) eine Obergrenze von b(n) ist UND b(n) eine Obergrenze von c(n), dann folgt a(n) ist auch eine Obergrenze von c(n)........Inhaltlich, logisch die Angabe nochmal erklärt!

O(c(n)) <= O(b(n)) <= a(n)... also ist a(n) auch eine O(c(n))........ ich hätte das einfach so banal erklärt, ohne mit Rechenregeln zu beweisen, weils doch logisch ist, oder?!

[LordNecro]

Naja wenn steht beweisen oder wiederlegen sie würd ichs schon auch formal herleiten, is bei b) ja auch net wirklich ein Problem. Schwerer tu ich mich da mit a) ich weiß einfach net ob man mir das als beweis durchgehen lässt^^

mfg

[IRBaboon]

.... Schwerer tu ich mich da mit a) ich weiß einfach net ob man mir das als beweis durchgehen lässt^^


Eine wahre Aussage muss auch wirklich formal bewiesen werden, ist die angegebene Aussage aber falsch, dann genuegt ein Gegenbeispiel als Beweis. D.h., wenn man/frau der Meinung ist, dass Punkt a) falsch ist, dann reicht es, die jeweiligen Definitionen hinzuschreiben und dann ein Beispiel zu bringen, das die Aussage widerlegt, fertig.

Aber nochmals ganz klar: Ein Beispiel ist kein Beweis, nur ein Gegenbeispiel!

I.R.Baboon

[Ali K]

a) kann man ja auch einfach durch ein Gegenbeispiel mit f(n) = 1 und g(n) = n zeigen.

verstehe ich das dann richtig, dass es ein gegenbeispiel ist weil dann gilt: g(n) = theta(n) und f(n) = theta(1) => g(n) ist nicht theta(f(n))

[tonico]

verstehe ich das dann richtig, dass es ein gegenbeispiel ist weil dann gilt: g(n) = theta(n) und f(n) = theta(1) => g(n) ist nicht theta(f(n))

Wenn man einsetzt bekommt man

1 = O(n²) ⇒ n = ϴ(1)

was offensichtlich falsch ist.

[hebi]

Jetzt hast mich neugierig gemacht, welchen Ansatz hast für b) verwendet?

a) kann man ja auch einfach durch ein Gegenbeispiel mit f(n) = 1 und g(n) = n zeigen.

bei a hab ich mich schwer getan, aber bei b) hab ich folgendes gemacht:

0<= a(n) <= c1*b(n) & 0<=b(n) <= c2*c(n) --> 0<=a(n) <=c*c(n)
0<=a(n) <?c1(c2*c(n)) --> 0<=a(n) <=c*c(n) | c=c1*c2
0<= a(n) <= c*c(n) --> 0<=a(n) <=c*c(n)

hoffe es ist verständlich!

[michaelllll]

bei a hab ich mich schwer getan, aber bei b) hab ich folgendes gemacht:

0<= a(n) <= c1*b(n) & 0<=b(n) <= c2*c(n) --> 0<=a(n) <=c*c(n)
0<=a(n) <?c1(c2*c(n)) --> 0<=a(n) <=c*c(n) | c=c1*c2
0<= a(n) <= c*c(n) --> 0<=a(n) <=c*c(n)

hoffe es ist verständlich!
habs auch so gemacht. nur, 0<=a(n) <=c*c(n) hab ich nich 2x hingeschrieben ;-)
EDIT: Hab ich doch gemacht!! :-)

[onuris]

Beschäftige mich gerade auch mit a:

Ich habe mir folgendes überlegt:

0(n*g(n)) = {f(n)| (c1, n0 > 0): 0 <= f(n) <= c3*n*g(n)}
Θ(f(n) = {g(n)|(c2, c3, n0 > 0): 0 <= c1*f(n) <= g(n) <= c2* f(n)}


Dann habe ich mir ein Ungleichungssystem aufgestellt:


1. f(n) <= c1*n*g(n)
2. c2*f(n) <= g(n)
3. c3*f(n) >= g(n)


Im nächsten Schritt: 1. = 1.+2. und 2. = 3.*(-1)

1: f(n) * (c2+1) <= g(n) * (c1*n+1)
2: -(c3 * f(n)) <= -g(n)

Dann: 1./2.

-(c2+1) / c3 <= -c1*n + 1

--> für große n wäre dann diese Ungleichung nicht mehr richtig

[onuris]

hat jemand eine andere Lösung oder kann meine lösung bestätigen bzw. widerlegen. Bitte um Rückmeldung
lg

[Lillipip]

Bin mir aber sehr unsicher bei meinen Lösungswegen...

a) f(n) = O(n*g(n)) -> g(n) = theta f(n)

Wenn gilt: f(n) = O (n*g(n))
-> existieren c, n0 > 0, sodass
f(n) < c*(n*g(n)) für alle n > n0

Wenn gilt: g(n) = theta f(n)
-> existieren c1,c2,n0 > 0, sodass
c1*g(n) < g(n) < c2*g(n) für alle n > n0

Jetzt ist aber c2*g(n) eine obere Schranke von g(n) und sicher kleiner als c(n*g(n)), was somit auch eine obere Schranke von g(n) sein muss.

b) Wenn i(n) eine untere Schranke von k(n) ist und j(n) eine untere Schranke von i(n), dann ist sicher j(n) auch eine untere Schranke von h(n).

.........i(n) < k(n)
j(n) < i(n)
j(n) ....<..... k(n)

Wie gesagt bin mir da aber sehr unsicher...

[michaelllll]

naja, das b würd schon stimmen, nur das du halt statt Obere Schranke eine Untere Schranke bewiesen hast (warum auch immer).
Aber grundsätzliclh sollte es so gehen, wie wir oben schon gemacht haben. Also wenn 0<c1*a(n)<c2*b(n) gilt, muss auch 0<c1*a(n)<c3*c(n) gelten, da ja 0<c1*b(n)<c2*c(n) (wenn es für das kleinere gilt, muss es ja fürs größere gelten).

Bei Beispiel a bleibe ich beim Gegenbeispiel ( f(n)=1 und g(n)=n ). Ich habe heute eine Mathematikerin (4. Semester) und Physikerin gefragt (5. Semester) und die sagt es genügt. Also wenn sie das meint, dann kann ich auch dazu stehen.

[Lillipip]

naja, das b würd schon stimmen, nur das du halt statt Obere Schranke eine Untere Schranke bewiesen hast (warum auch immer).
Aber grundsätzliclh sollte es so gehen, wie wir oben schon gemacht haben. Also wenn 0<c1*a(n)<c2*b(n) gilt, muss auch 0<c1*a(n)<c3*c(n) gelten, da ja 0<c1*b(n)<c2*c(n) (wenn es für das kleinere gilt, muss es ja fürs größere gelten).

Bei Beispiel a bleibe ich beim Gegenbeispiel ( f(n)=1 und g(n)=n ). Ich habe heute eine Mathematikerin (4. Semester) und Physikerin gefragt (5. Semester) und die sagt es genügt. Also wenn sie das meint, dann kann ich auch dazu stehen.

Sorry, hab mich mit dem < und > vertan...

Selbst wenn du mich jetzt für dumm erklärst, ich checks immer noch ned mit den Gegenbeispiel...

[michaelllll]

warum soll ich dich als dumm erklären?
ja, es wurde halt einfach nur ein Beispiel gesucht, wo die 1. Teil gilt (0<=n*c<=n*1 für n0>=1 und c=1/2), aber der 2. Teil nicht (0<=n*c1<=1<=n*c2)).

[Defiler]

bei a) ist mir etwas unklar:
kann ich für f(n) = O(n*g(n))
folgendes schreiben: 0<= f(n)<= c*n*g(n). ?

[0110]

naja, das b würd schon stimmen, nur das du halt statt Obere Schranke eine Untere Schranke bewiesen hast (warum auch immer).
Aber grundsätzliclh sollte es so gehen, wie wir oben schon gemacht haben. Also wenn 0<c1*a(n)<c2*b(n) gilt, muss auch 0<c1*a(n)<c3*c(n) gelten, da ja 0<c1*b(n)<c2*c(n) (wenn es für das kleinere gilt, muss es ja fürs größere gelten).

Bei Beispiel a bleibe ich beim Gegenbeispiel ( f(n)=1 und g(n)=n ). Ich habe heute eine Mathematikerin (4. Semester) und Physikerin gefragt (5. Semester) und die sagt es genügt. Also wenn sie das meint, dann kann ich auch dazu stehen.

ein gegenbeispiel ist kein beweis! Man sollte beweisen dass es gehen KANN! Selbst wenn du 100000 Gegenbeispiele bringst kanns noch immer einen Fall geben wos geht!!

[tonico]

ein gegenbeispiel ist kein beweis! Man sollte beweisen dass es gehen KANN! Selbst wenn du 100000 Gegenbeispiele bringst kanns noch immer einen Fall geben wos geht!!
Stimmt schon, aber ein Gegenbeispiel genügt um eine Aussage zu widerlegen.

[michaelllll]

Stimmt schon, aber ein Gegenbeispiel genügt um eine Aussage zu widerlegen.

ja, es stimmt. (angabe steht, beweise oder widerlege und nicht: ...oder gib einen gegenbeweis)
(ja, ich spamme) :zwinker:

[michaelllll]

bei a) ist mir etwas unklar:
kann ich für f(n) = O(n*g(n))
folgendes schreiben: 0<= f(n)<= c*n*g(n). ?


ja, warum nicht?

[matte]

1) f(n) = O(n*g(n))
0<= f(n)<= c*n*g(n)
dh.: Ungleichung ist sicher erfüllt, wenn theta(f(n)) <= theta(g(n))

es soll folgen:
2) g(n) = theta (f(n))
c1*f(n) <= g(n) <= c2*f(n)
dh.: Ungleichung ist nur dann erfüllt, wenn theta f(n) = theta g(n)

[matte]

Könnte das event. stimmen???

[cherrybonbon]

einen guten morgen wünsche ich :)

Also ich werde b) so erklären:

Wenn a(n) eine Obergrenze von b(n) ist UND b(n) eine Obergrenze von c(n), dann folgt a(n) ist auch eine Obergrenze von c(n)........Inhaltlich, logisch die Angabe nochmal erklärt!

O(c(n)) <= O(b(n)) <= a(n)... also ist a(n) auch eine O(c(n))........ ich hätte das einfach so banal erklärt, ohne mit Rechenregeln zu beweisen, weils doch logisch ist, oder?!
also mit dem komme ich nicht klar.
a(n)=O(b(n)) \wedge b(n)=O(c(n)) \Rightarrow a(n)=O(c(n))
heißt doch: O(b(n)) ist die Menge aller Funktionen a(n) die größergleich 0 und kleinergleich c*b(n) sind. Also ist nicht a(n) eine Obergrenze von b(n) sondern umgekehrt.

naja, imho ist die Behauptung richtig. weil [tex]0 \leq a(n) \leq b(n) \leq c(n) \Rightarrow 0 \leq a(n) \leq c(n)[\tex]

ob das jetzt als beweis reicht.. ich mach ja lieber gegenbeispiele bei falschen aussagen ^^

was mich etwas irritiert ist die aussage von IRBaboon

Aber nochmals ganz klar: Ein Beispiel ist kein Beweis, nur ein Gegenbeispiel!
und das Beispiel 1 im Skriptum auf Seite 21 wo durch ein Beispiel eine Behauptung bewiesen wurde.

[Klaudia]

heute hatten ja einpaar die übung.. mich würde interessieren was jetzt bei a stimmt?

[Defiler]

:D uns wurde gesagt das ein Gegenbeispiel ausreichend ist etwas zu Wiederlegen.

[michaelh]

hm, und was wäre dann jetz die richtige lösung bei a? :D

[Defiler]

:D na ja

ich wurde nur f(n) = n und g(n) = n² nehmen weil ich finde das es besser aussieht und dann kommt man auf die Schlussfolgerung dass a) wiederlegt ist also nicht wahr ist.

0<= n<= n²|n -> 0<= 1<= n

0<= c1n<= n²<= c2n| n

0<= c1<= n<= c2 und weil n zu unendlich geht(auch laut Skriptum) und c2 nur eine Konstante ist bekommt man ein wiederspruch un das wars. ieee :D

[michaelh]

:D na ja

ich wurde nur f(n) = n und g(n) = n² nehmen weil ich finde das es besser aussieht und dann kommt man auf die Schlussfolgerung dass a) wiederlegt ist also nicht wahr ist.

0<= n<= n²|n -> 0<= 1<= n

0<= c1n<= n²<= c2n| n

0<= c1<= n<= c2 und weil n zu unendlich geht(auch laut Skriptum) und c2 nur eine Konstante ist bekommt man ein wiederspruch un das wars. ieee :D
da es schon spät is frag ich lieber nach ob du dich vl verschrieben hast :D

0<= n<= n²|n -> 0<= 1<= n ist definitiv so, hab ich auch

0<= c1n<= n²<= c2n| n hab ich anders
0<= c1n²<= n<= c2n²| n ist definitiv falsch
weil es heisst ja 0<=c1*g(n)<=f(n)<=c2*g(n)

hm....

[tonico]

hm, und was wäre dann jetz die richtige lösung bei a? :D

Gegenbeispiel: Einsetzen von f(n) = 1, g(n) = n ergibt

1 = O(n²) ⇒ n = ϴ(1) ⇔ 0 ≤ c1·1 ≤ n ≤ c2·1,

und das ist offensichtlich falsch weil man für jede Konstante c2 ein größeres n finden kann.

[FloW07]

Ich sag einfach, dass es eine Implikation ist und dass diese nur wahr sein kann ,wenn Aussage A wahr ist und Aussage B wahr ist und das widerlege ich mittels gegenbsp.


Wir wählen beliebige Wert für f(n) und g(n)
f(n) = n^4 und g(n) = n^7

danach setzen wir das in unsere Angabe ein:


n^4 = O(n*n^7) ==> n^7 = theta(n^4)

A ==> B

Ist Wahr, da die Obereschranke von n^4 O(n*n^7) ist aber B ist falsch. Daraus schließen wir das die Implikation falsch ist und haben es somit widerlegt.