Hi zusammen,
konnte leider diese Woche nicht in die M1-Übung, wüsste aber gerne ob meine Lösungen korrekt sind. Falls jemand Zeit hat, wäre cool!
M1 Blatt 4
Aufgabe 2) Relationen angeben auf {a,b,c,d}
a) reflexiv, nicht symm, transitiv
R = {(a,a),(b,b),(c,c),(d,d),(a,b),(b,c),(a,c)}
b) nicht reflexiv, symmetrisch, nicht transitiv
R = {(a,b),(b,a),(c,d),(d,c)}
c) reflexiv, symmetrisch, nicht transitiv
R = {(a,a),(b,b),(c,c),(d,d),(a,b),(b,a),(c,d),(d,c)}
d) nicht reflexiv, nicht symmetrisch, nicht transitiv
R = {(a,b),(c,d)}
e) Äquivalenz + Ordnungsrelation
R = {(a,a),(b,b),(c,c),(d,d)}
Aufgabe 3)
a)
A = {1,2,3,4}. Es gibt mehr als 2^50 verschiedene ternäre Relationen auf A. Wahr oder falsch?
Lösung… Kombinatorik Grundaufgabe 2 würde ich sagen: wieviele k-Tupel aus n-elementiger Menge kann ich bilden mit mehrfachem Auftreten der Elemtente ? Also n = 4 und k = 3 ==> 4*3*2 = 24
24 < 2^50…
naja, irgendwie bin ich mir hier ziemlich unsicher..
3b) konnte ich auch irgendwie gar nicht..
4) Ziege mit Induktion, dass (n^3 - 7n) / 6 Element Z ist
3. Induktionsschritt:
Zu zeigen:
A(n+1) = (n+1)^3 - 7(n+1) / 6 ist in Z
= (n^3 + 3n^2 + 3n + 1 - 7n -7) / 6
= (n^3 - 7n) / 6 + (3n^2 + 3n -6) / 6
mit der Voraussetzung A(n) = (n^3 - 7n) / 6 folgt:
A(n+1) = A(n) + (3n^2 + 3n -6) / 6
= A(n) + (n^2 + n - 2)/2
= A(n) + (n^2 + n)/2 - 2
An der Stelle bin ich fertig, denn
aus Annahme a) n^2 + n ist gerade folgt n^2 + n / 2 ist gerade
und aus Annahme b) n^2 + n ist ungerade folgt, dass n^2 + n / 2 ebenfalls gerade ist und eine gerade Zahl minus 2 ist wieder gerade, also ist die Behauptung wahr.
Geht dieser Beweis als formal korrekt durch?
Vielen Dank an alle, die mir weiterhelfen!
Wenn ich über die 3a) nochmal nachdenke, dann könnte es auch so sein:
|A| = 4
|AxAxA| = 2^64
hmmm? HILFE! ;)
c) reflexiv, symmetrisch, nicht transitiv
R = {(a,a),(b,b),(c,c),(d,d),(a,b),(b,a),(c,d),(d,c)}
Die ist aber transitiv. Der Rest von 2 sieht richtig aus.
c) reflexiv, symmetrisch, nicht transitiv
R = {(a,a),(b,b),(c,c),(d,d),(a,b),(b,a),(c,d),(d,c)}
Die ist aber transitiv. Der Rest von 2 sieht richtig aus.
Wieso ist die transitiv?
Heisst das, dass {(a,b),(b,c)} automatisch transitiv ist, auch wenn ich kein Tupel (a,c) explizit mit angegeben habe?
aRb und bRa => aRa
bRa und aRb => bRb
cRd und dRc => cRc
dRc und cRd => dRd
Ist bei dir erfüllt, also transitiv.
Ok, verstehe..
reflexiv, symmetrisch, nicht transitiv
reflexiv ist sie, wenn (a,a),(b,b),(c,c),(d,d) enthalten ist… dann gilt doch immer, aRb ^ bRa => aRa oder? Kann es dann überhaupt eine Relation geben, die reflexiv und nicht transitiv ist?
Kann es dann überhaupt eine Relation geben, die reflexiv und nicht transitiv ist?
natürlich, z.b.
(a,a),(b,b),(c,c),(a,b),(b,c)
ok abschliessend kann mir ja vielleicht nochmal jemand eine relation angeben, die reflexiv, symmetrisch, nicht transitiv ist *gg*
ich bin kurz davor, es endgültig verstanden zu haben ;)
ok abschliessend kann mir ja vielleicht nochmal jemand eine relation angeben, die reflexiv, symmetrisch, nicht transitiv ist *gg*
bitte:
(a,a),(b,b),(c,c),(a,b),(b,a),(b,c),(c,b)
ich bin kurz davor, es endgültig verstanden zu haben ;)
na dann herzlichen Glückwunsch [img]
http://www.fb18.de/gfx/23.gif[/img]
(a,a),(b,b),(c,c),(a,b),(b,a),(b,c),(c,b)
hmm ist (a,b) (b,c) nicht transitiv ?
[img]
http://www.fb18.de/gfx/11.gif[/img]
(a,a),(b,b),(c,c),(a,b),(b,a),(b,c),(c,b)
hmm ist (a,b) (b,c) nicht transitiv ?
[img]http://www.fb18.de/gfx/11.gif[/img]
Nein. da es ja kein (a,c) gibt.
Noch mal was zu den anderen Aufgaben:
|A| = 4
|AxAxA| = 2^64
Wohl eher
[img]
http://mokrates.de/cgi-bin/texstring?%7CA%7C%20%3D%204[/img]
[img]
http://mokrates.de/cgi-bin/texstring?%7CA%20%5Ctimes%20A%20%5Ctimes%20A%7C%20%3D%204%5E3%20%3D%2064[/img]
[img]
http://mokrates.de/cgi-bin/texstring?%7C%5Cmathcal%7BP%7D(A%20%5Ctimes%20A%20%5Ctimes%20A)%7C%20%3D%202%5E%7B64%7D[/img]
zu 4:
- Da fehlen Induktionsanfang und -annahme
-
Zu zeigen:
A(n+1) = (n+1)^3 - 7(n+1) / 6 ist in Z
= (n^3 + 3n^2 + 3n + 1 - 7n -7) / 6
<nitpick>Da weiss man nicht, worauf sich das zweite = bezieht. sicherlich nicht auf das "ist in Z", sondern auf das A(n+1). Aber ist das noch "Zu zeigen"? Das ist doch der Anfang des Beweises. </nitpick>
- 2/2 ist 1, nicht 2 :P
Ansonsten ein schöner Beweis!
= A(n) + (n^2 + n)/2 - 2
An der Stelle bin ich fertig, denn
aus Annahme a) n^2 + n ist gerade folgt n^2 + n / 2 ist gerade
und aus Annahme b) n^2 + n ist ungerade folgt, dass n^2 + n / 2 ebenfalls gerade ist und eine gerade Zahl minus 2 ist wieder gerade, also ist die Behauptung wahr.
Hmm, hier ist mir die Argumentation etwas unklar.
Ist das "Annahme a)"/"Annahme b)" eine Fallunterscheidung? Oder Teil der Induktionsannahme?
Im Falle einer Fallunterscheidung:
- Ich nehme an, dass du meinst "wenn n^2+n (un)gerade, dann
ist (n^2+n)/2 _ganz_" (dann passt es zur Gleichung). Es
folgt nämlich nicht, dass dann auch (n^2+n)/2 gerade ist,
Gegenbeispiel: n=5, dann ist (n^2+n)/2=15. (Ebenfalls folgt
nicht, dass n^2+(n/2) ganz ist, denn n^2+n=n(n+1) ist immer
gerade, also auch für ungerade n.)
- Zu "Wenn n^2+n ungerade ist, ist (n^2+n)/2 ganz":
Dies ist strengenommen eine richtige Folgerung, weil die
Voraussetzung nie erfüllt ist, aber im Allgemeinen darf man
natürlich nicht folgern "m ungerade => m/2 ganz".
Falls "n^2+n gerade" Teil der Induktionsannahme sein soll
(du also "unterwegs" gleich mit zeigen willst, dass n^2+n gerade ist), musst du den zugehörigen Induktionsschritt noch machen, also zeigen, dass dann auch (n+1)^2+(n+1) wieder gerade ist.
Im Falle einer Fallunterscheidung:
- Ich nehme an, dass du meinst "wenn n^2+n (un)gerade, dann
ist (n^2+n)/2 _ganz_" (dann passt es zur Gleichung). Es
folgt nämlich nicht, dass dann auch (n^2+n)/2 gerade ist,
Gegenbeispiel: n=5, dann ist (n^2+n)/2=15. (Ebenfalls folgt
nicht, dass n^2+(n/2) ganz ist, denn n^2+n=n(n+1) ist immer
gerade, also auch für ungerade n.)
- Zu "Wenn n^2+n ungerade ist, ist (n^2+n)/2 ganz":
Dies ist strengenommen eine richtige Folgerung, weil die
Prämisse nie erfüllt ist, aber im Allgemeinen darf man
natürlich nicht folgern "m ungerade => m/2 ganz".
Ups, ja, das hatte ich ganz übersehen… /me geht weiter korrigieren
/me geht weiter korrigieren
hmpf, nein, tu ich nicht - wer von euch hat mir meine Mappe geklaut? [img]
http://www.fb18.de/gfx/26.gif[/img]
<edit>gefunden</edit>
Nein, das ist richtig, denn die Potenzmenge ist die "Menge aller Teilmengen" und eine Relation ist eben genau eine Teilmenge, also ein Element der Potenzmenge, folglich kann man 2 hoch 64 ternäre Relationen bilden.
Ansonsten anschaulich gedacht: wenn man die 64 möglichen Tupel hat: eine Relation ist ja eine Menge von Tupeln. Bei jedem der 64 Tupel entscheidet man sich nun: soll das rein oder nicht? Das ist jeweils eine ja/nein-Entscheidung, also 2 Möglichkeiten. Das macht 2*2*2*2*….*2 (64mal) Möglichkeiten, also 2^64
Hi,
ich hätte noch ein paar Fragen zu Aufgabe 2 b), d) und e):
b) nicht reflexiv, symmetrisch, nicht transitiv
R = {(a,b),(b,a),(c,d),(d,c)}
Die Relation soll nicht reflexiv sein, aber diese ist doch irreflexiv, oder nicht?
Das gleiche nochmal bei Aufgabe d).
Und zu Aufgabe e)
e) Äquivalenz + Ordnungsrelation
R = {(a,a),(b,b),(c,c),(d,d)}
Hier sehe ich die Transitivität nicht. Kann mir da jemand bitte weiterhelfen?
b) nicht reflexiv, symmetrisch, nicht transitiv
R = {(a,b),(b,a),(c,d),(d,c)}
Die Relation soll nicht reflexiv sein, aber diese ist doch irreflexiv, oder nicht?
Das gleiche nochmal bei Aufgabe d).
Nicht reflexiv heißt dass sie die Eigenschaft der Reflexivität nicht erfüllt und genau das ist hier der Fall. Ob das Ding dann irreflexiv ist, ist dafür egal, es ist auf jeden Fall nicht reflexiv.
Und zu Aufgabe e)
e) Äquivalenz + Ordnungsrelation
R = {(a,a),(b,b),(c,c),(d,d)}
Hier sehe ich die Transitivität nicht. Kann mir da jemand bitte weiterhelfen?
Transitiv: [img]
http://mokrates.de/cgi-bin/texstring?(x%2Cy)%20%5Cin%20R%20%5Cwedge%20(y%2Cz)%20%5Cin%20R%20%5CRightarrow%20(x%2Cz)%20%5Cin%20R[/img]
Das ist die Bedingung. Nun mal schauen was einsetzbar ist überhaupt. Fangen wir mit nem a an. Sagen wir also fürs x setzen wir ein a sein. Dann ist das einzige was wir in de rBedingung erstmal machen können fürs y auch ein a einsetzen, andere Tupel mti a am Anfang haben wir nicht. Wenn y aber a siensoll können wir auch für das z nur ein a einsetzen. Dann haben wir:
[img]
http://mokrates.de/cgi-bin/texstring?(a%2Ca)%20%5Cin%20R%20%5Cwedge%20(a%2Ca)%20%5Cin%20R%20%5CRightarrow%20(a%2Ca)%20%5Cin%20R[/img]
Und das wird erfüllt. Ebenso mit überall b, c oder d. Jetzt haben wir alle Möglichkeiten ausgeschöft, die es gibt, also ist die Regel unverletzbar, also gilt sie, also ists transitiv.
Transitiv:
Das ist die Bedingung. Nun mal schauen was einsetzbar ist überhaupt. Fangen wir mit nem a an. Sagen wir also fürs x setzen wir ein a sein. Dann ist das einzige was wir in de rBedingung erstmal machen können fürs y auch ein a einsetzen, andere Tupel mti a am Anfang haben wir nicht. Wenn y aber a siensoll können wir auch für das z nur ein a einsetzen. Dann haben wir:
Und das wird erfüllt. Ebenso mit überall b, c oder d. Jetzt haben wir alle Möglichkeiten ausgeschöft, die es gibt, also ist die Regel unverletzbar, also gilt sie, also ists transitiv.
Ok, sehe ich ein. :)
Nicht reflexiv heißt dass sie die Eigenschaft der Reflexivität nicht erfüllt und genau das ist hier der Fall. Ob das Ding dann irreflexiv ist, ist dafür egal, es ist auf jeden Fall nicht reflexiv.
Im M1 Skript von Thomas Andreae steht auf Seite 54 folgendes:
Man beachte: Irreflexiv ist nicht dasselbe wie "nicht reflexiv"; antisymmetrisch ist nicht dasselbe wie "nicht symmetrisch".
Wenn die Aufgabe lautet, dass eine Relation "nicht reflexiv" sein soll, verstehe ich darunter, dass sie nicht "reflexiv" und nicht "irreflexiv" sein soll. Ich hoffe, man versteht, was ich meine.
Im M1 Skript von Thomas Andreae steht auf Seite 54 folgendes:
Man beachte: Irreflexiv ist nicht dasselbe wie "nicht reflexiv"; antisymmetrisch ist nicht dasselbe wie "nicht symmetrisch".
Wenn die Aufgabe lautet, dass eine Relation "nicht reflexiv" sein soll, verstehe ich darunter, dass sie nicht "reflexiv" und nicht "irreflexiv" sein soll. Ich hoffe, man versteht, was ich meine.
Man versteht es, aber nur weil "nicht reflexiv" ungleich "irreflexiv" ist, heißt das ja nicht dass bei "nicht reflexiv" auch irreflexiv drin sein muss. "nicht reflexiv" ist auch was anderes als symmterisch, trotzdem darf eien nicht reflexive Relation symmetrisch sein [img]
http://www.fb18.de/gfx/25.gif[/img]
Also da hab ich dann auch mal eine doofe Frage
= A(n) + (n^2 + n)/2 - 2
An der Stelle bin ich fertig, denn
aus Annahme a) n^2 + n ist gerade folgt n^2 + n / 2 ist gerade
und aus Annahme b) n^2 + n ist ungerade folgt, dass n^2 + n / 2 ebenfalls gerade ist und eine gerade Zahl minus 2 ist wieder gerade, also ist die Behauptung wahr.
Hmm also ich bin kein Übungsgruppenleiter, deshalb muss ich das wohl auch nicht verstehen, aber:
Wenn n^2 + n UNgerade ist dann folgt daraus, dass (n^2 + n)/2 gerade ist ????????
Also ich hab noch nie ne ungerade Zahl halbiert und da ist bei mir was gerades rausgekommen oO
Wichtig ist nur, dass der Term (n^2 + n) durch 2 teilbar ist imo, und das ist er genau in dem moment, wenn n^2 + n gerade ist.
Da eine gerade Zahl ins quadrat genommen immer wieder eine gerade zahl ergibt und dann am Ende noch eine gerade zahl hinzuaddiert wird, macht die Annahme war.
Wenn n ungerade ist —> n^2 ist ungerade.
Ungerade + ungerade = gerade —> n^2 +n ist in jedem fall gerade —> die Behauptung gilt
So würd für mich ne schlüssige Begründung aussehen
Ich gebs ja zu, ich hab da nur "Fallunterscheidung" und "gerade/ungerade" gesehen, und den Rest überlesen…
Wenn die Aufgabe lautet, dass eine Relation "nicht reflexiv" sein soll, verstehe ich darunter, dass sie nicht "reflexiv" und nicht "irreflexiv" sein soll.
M. M. nach würde bei geforderter "nicht reflexiver" Relation auch eine irreflexive gelten, da diese ja ebenfalls "nicht reflexiv" ist und in der Aufgabe nur "nicht reflexiv" gefordert wurde und irreflexiv nicht ausgeschlossen wurde.
Oder sehen das die Übungsleiter anders?
Wenn die Aufgabe lautet, dass eine Relation "nicht reflexiv" sein soll, verstehe ich darunter, dass sie nicht "reflexiv" und nicht "irreflexiv" sein soll.
M. M. nach würde bei geforderter "nicht reflexiver" Relation auch eine irreflexive gelten, da diese ja ebenfalls "nicht reflexiv" ist und in der Aufgabe nur "nicht reflexiv" gefordert wurde und irreflexiv nicht ausgeschlossen wurde.
Oder sehen das die Übungsleiter anders?
Das ist in Ordnung, irreflexiv ist ja nicht reflexiv wie du sagst
