binäre Relationen < Relationen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:42 Do 23.10.2014 | | Autor: | infostu |
| Aufgabe | | [Dateianhang nicht öffentlich] |
Hay!
Ich studiere Informatik und muss für Mathematik für Informatiker 1 ein Übungsblatt lösen. Doch leider komme ich da so überhaupt nicht weiter.
Ich weiss, dass es selbstverständlich nicht klug wäre, einfach eine komplett fertige Lösung zu verlangen, aber ich wäre für jede Hilfe dankbar!
Ich habe bereits das kartesische Produk MxM gebildet und die Umkehrrelation von R, also R^-1.
Doch viel weiter weiss ich leider nicht, da egal wie oft und intensiv ich mir das Skript anschaue, es will einfach nicht "klick" machen...
Besonders verstehe ich nicht so recht wie sich die Produktrelation zusammensetzt.
Oder generell die Aussagen zur Links-, Rechtseindeutigkeit, Links- und Rechtstotalität erscheinen mir ziemlich fremd...
Bin gerade echt verzweifelt.. Hoffe mir kann jemand helfen! Vielen Dank schon einmal im Vorraus!
mfg
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt:
http://www.matheboard.de/thread.php?threadid=547389
http://www.onlinemathe.de/forum/Aussagenlogik-Praedikatenlogik-Umformung
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
|
|
| |
|
> Ich habe bereits das kartesische Produk MxM gebildet und
> die Umkehrrelation von R, also R^-1.
> Doch viel weiter weiss ich leider nicht, da egal wie oft
> und intensiv ich mir das Skript anschaue, es will einfach
> nicht "klick" machen...
> Besonders verstehe ich nicht so recht wie sich die
> Produktrelation zusammensetzt.
> Oder generell die Aussagen zur Links-,
> Rechtseindeutigkeit, Links- und Rechtstotalität erscheinen
> mir ziemlich fremd...
Hallo infostu,
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
ich hab mir das Aufgabenblatt bei matheboard angeschaut.
Für die erste Aufgabe musst du wohl einfach die Paare, die
in den Mengen [mm] R^{-1}, [/mm] S und T vorkommen, quasi wie
Dominosteine auf alle möglichen Arten aneinanderreihen
und so die Paare der gesuchten Relation $\ U\ =\ [mm] \left( R^{-1} \odot S\,\right) \odot [/mm] T $
erzeugen. So ist beispielsweise $\ [mm] (4,2)\in R^{-1}\ [/mm] ,\ [mm] (2,5)\in [/mm] S$ und $\ [mm] (5,6)\in [/mm] T$
und folglich $\ [mm] (4,6)\in [/mm] U$ . Hoffentlich habe ich da bei der
Reihenfolge in der Schreibweise nichts durcheinandergebracht ...
Für die Prüfung auf Links- und Rechts- -Eindeutigkeit bzw.
-Totalität solltest du dir einfach mal die ![[]](/images/popup.gif) Definitionen
dieser Begriffe exakt vergegenwärtigen und dann auf das
Beispiel der Teilbarkeitsrelation in [mm] \IN \times \IN [/mm] anwenden.
(Mit [mm] \IN [/mm] ist hier sicher die Menge der natürlichen Zahlen
ohne die Null gemeint).
Auch für die 3. Aufgabe gilt es, sich die Definitionen
der Begriffe " Relation $\ R [mm] \subseteq A\times [/mm] B$ " und
" Identitätsrelation [mm] I_A [/mm] einer Menge A "
genau anzuschauen.
LG , Al-Chwarizmi
|
|
|
| |
|
Hallo nochmals,
vermutlich bin ich genau der Verwechslung bei der Notation
erlegen, die ich schon halbwegs befürchtet hatte:
Bei Wikipedia findet man unter "Verkettung von Relationen" :
Als Verallgemeinerung des bekannteren Konzepts der Verkettung
von Funktionen können sogar zwei beliebige Relationen R [mm] \subseteq [/mm] A [mm] \times [/mm] B
und S [mm] \subseteq [/mm] C [mm] \times [/mm] D miteinander verkettet werden.
Das Ergebnis ist das relative Produkt oder Relationenprodukt
S [mm] \circ [/mm] R := RS := [mm] \{(a,d) \in A \times D \mid \exists ~ b \in B \cap C\colon (a,b) \in R \land (b,d) \in S\}.
[/mm]
Nochmals :
[mm] $\Huge {\red{\text{S } {^\text{\large O}} \text{ R}\ \text{ := }\ \text{R}\ \text{S} }}$
[/mm]
Irgendwie fand ich diese Notationskonvention schon immer
etwas doof, hier aber erst recht ...
LG , Al-Chw.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:25 Do 23.10.2014 | | Autor: | infostu |
Vielen Dank für die Antwort! Doch leider ist genau dies mein Problem... Die Definitionen habe ich ja auch im Skript, aber leider wollen die nicht so richtig sitzen bzw. ich verstehe sie gar nicht so richtig. Ich schaffe es einfach nicht, dass was da steht auf meine Aufgabe anzuwenden.
|
|
|
| |
|
> Vielen Dank für die Antwort! Doch leider ist genau dies
> mein Problem... Die Definitionen habe ich ja auch im
> Skript, aber leider wollen die nicht so richtig sitzen bzw.
> ich verstehe sie gar nicht so richtig. Ich schaffe es
> einfach nicht, dass was da steht auf meine Aufgabe
> anzuwenden.
Verstehe.
Zweitens hoffe ich, dass die neue Interpretation des
Relationsproduktes, von der ich jetzt ausgehen möchte
(aufgrund der Definition bei Wikipedia), nun wirklich
dem entspricht, was bei deiner Aufgabe gemeint war.
Wir müssten also jetzt den Term
$ \ U\ =\ [mm] \left( R^{-1} \odot S\,\right) \odot [/mm] T $
interpretieren als $\ T S [mm] R^{-1}$ [/mm] , wenn wir die in die
Rechnung eingehenden Paare in "natürlicher" Reihenfolge
von links nach rechts aneinander fügen wollen.
Damit gilt mein altes Beispiel natürlich nicht mehr, und
wir hätten als neues Beispiel etwa:
$\ (5,2) [mm] \in [/mm] T [mm] \wedge [/mm] (2,6) [mm] \in [/mm] S [mm] \wedge [/mm] (6,2) [mm] \in R^{-1}\ \Rightarrow (5,2)\in [/mm] U$
Soweit ich sehe, kommt als Ergebnis heraus, dass
$\ U\ =\ [mm] \{\ (x,2)\ |\ x\in M\ \}$ [/mm]
(dies aber ohne Gewähr !)
Zur 2. Aufgabe:
Zunächst müsste man noch wissen, was genau mit der
"bekannten Teilbarkeitsrelation" gemeint sein soll. In Frage
kämen die Relationen
[mm] $\{\ (x,y)\,\in \IN \times \IN\ |\ x\ ist\ Teiler\ von\ y\ \}$
[/mm]
oder
[mm] $\{\ (x,y)\,\in \IN \times \IN\ |\ x\ ist\ durch\ y\ teilbar\ \}$
[/mm]
Da muss man sich entscheiden, denn aus der Aufgabenstellung
geht nicht hervor, was von beiden gemeint sein soll.
Ich nehme mal die erste Interpretation, d.h. für (positive)
natürliche Zahlen x und y gelte:
$\ [mm] (x,y)\in [/mm] T\ \ [mm] \gdw\ [/mm] \ x\ ist\ Teiler\ von\ y$
Nun stellt sich z.B. bei der Frage nach der Rechtseindeutigkeit die
Frage: Falls x,y,z natürliche Zahlen sind und x sowohl Teiler von y
als auch von z ist, muss dann notwendigerweise y=z sein ?
Dass dies nicht zutrifft, kann man leicht durch ein einziges
gegenbeispiel zeigen. Damit ist klar, dass die so definierte
Relation T nicht rechtseindeutig ist.
Die Frage nach der Linkstotalität könnte man auf einfach
verständliche Weise z.B. so ausdrücken: "Ist jede natürliche
Zahl x Teiler von (mindestens) einer natürlichen Zahl y ?"
LG , Al-Chw.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:45 Do 23.10.2014 | | Autor: | infostu |
Zu 2:
Die Teilbarkeit ist definiert durch n|m [mm] \gdw [/mm] df [mm] \exists [/mm] k [mm] \in \IN [/mm] . n * k = m.
Doch ich weiss leider nicht einmal genau wie ich vorgehen muss.
|
|
|
| |
|
> Zu 2:
> Die Teilbarkeit ist definiert durch n|m [mm]\gdw[/mm] df [mm]\exists[/mm] k
> [mm]\in \IN[/mm] . n * k = m.
Wenn du nun also definierst: $\ (n,m) [mm] \in [/mm] T\ [mm] \gdw\ n\,|\,m$
[/mm]
dann entspräche dies der ersten der beiden von mir angegebenen
Möglichkeiten: " n ist Teiler von m "
> Doch ich weiss leider nicht einmal genau wie ich vorgehen
> muss.
Also nochmals die Frage nach der Rechtseindeutigkeit:
Falls diese für die betrachtete Relation vorläge, müsste
aus $\ [mm] n\, |\, m_1$ [/mm] und $\ [mm] n\, |\, m_2$ [/mm] folgen, dass [mm] m_1 [/mm] = [mm] m_2 [/mm] .
Doch schon ein Beispiel wie $\ n=3$ , [mm] m_1=6 [/mm] und [mm] m_2 [/mm] = 15 zeigt
sofort:
$\ [mm] n\, |\, m_1$ [/mm] und $\ [mm] n\, |\, m_2$ [/mm] sind erfüllt , aber es ist $\ [mm] m_1\not= m_2$
[/mm]
Also ist offensichtlich die Rechtseindeutigkeit verletzt.
LG , Al-Chw.
|
|
|
|
