TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 104

Aus VoWi
Zur Navigation springen Zur Suche springen

Man untersuche nachstehend angeführte Relationen R\subseteq{M^2} im Hinblick auf die Eigenschaften Reflexivität (R), Symmetrie (S), Antisymmetrie (A) und Transitivität (T):

a) M = \text{Menge aller Einwohner von Wien (Volkszählung 2001)}, a R b \Leftrightarrow a \text{ ist verheiratet mit } b

b) M \text{ wie oben}, a R b \Leftrightarrow a \text{ ist nicht aelter als }b

c) M \text{ wie oben}, a R b \Leftrightarrow a \text{ ist so gross wie }b

d) M = \mathbb R, a R b\Leftrightarrow a-b\in\mathbb Z

e) M = \mathbb R^n, (x_1,...,x_n) R (y_1,...,y_n) \Leftrightarrow x_i\leq y_i \forall i=1,...,n

Hilfreiches

Reflexivität
Reflexivität[Bearbeiten, WP, 1.55 Definition]

\forall a\in M:\quad aRa

Symmetrie
Symmetrie[Bearbeiten, WP, 1.55 Definition]

\forall a,b \in M: aRb \Rightarrow bRa

Antisymmetrie
Antisymmetrie[Bearbeiten, WP, 1.60 Definition]

\forall a,b\in M:\quad aRb\wedge bRa\Longrightarrow a=b

Transitivität
Transitivität[Bearbeiten, WP, 1.55 Definition]

\forall a,b,c\in M:\quad a\circ b\wedge b\circ c\Rightarrow a\circ c

Lösung von Baccus

(naiv, bitte nochmal überprüfen!): (\top= wahr, \bot= falsch):

Beispiel (a) a R b\Leftrightarrow a ist verheiratet mit b

(R) \forall x\in A: xRx:\bot Man kann (noch) nicht mit sich selbst verheiratet sein.

(S) \forall x,y\in A: xRy\Rightarrow yRx:\top Wenn Gattin mit Gatte verheiratet, dann auch Gatte mit Gattin.

(A) \forall x,y\in A: xRy\wedge yRx\Rightarrow x=y: \bot Im Endeffekt wie (R).

(T) \forall x,y,z\in A: xRy\wedge yRz\Rightarrow xRz: \bot Drei Leute müßten untereinander verheiratet sein; möglich, aber (zumindest) der Papst mag das nicht.

Beispiel (b) a R b\Leftrightarrow a ist nicht älter als b

(R) \forall x\in A: xRx:\top ich bin nicht älter als ich

(S) \forall x,y\in A: xRy\Rightarrow yRx:\bot

(A) \forall x,y\in A: xRy\wedge yRx\Rightarrow x=y: \top (*)

(T) \forall x,y,z\in A: xRy\wedge yRz\Rightarrow xRz: \top

Beispiel (c) a R b\Leftrightarrow a ist so groß wie b

(R) \forall x\in A: xRx:\top

(S) \forall x,y\in A: xRy\Rightarrow yRx:\top

(A) \forall x,y\in A: xRy\wedge yRx\Rightarrow x=y: \bot (*)

(T) \forall x,y,z\in A: xRy\wedge yRz\Rightarrow xRz: \top

Beispiel (d) a R b\Leftrightarrow a-b\in\mathbb Z

(R) \forall x\in A: xRx:\top

Beispiel: x-x=0\in\mathbb Z

(S) \forall x,y\in A: xRy\Rightarrow yRx:\top

(A) \forall x,y\in A: xRy\wedge yRx\Rightarrow x=y: \bot

(T) \forall x,y,z\in A: xRy\wedge yRz\Rightarrow xRz: \top

Beispiel (e) (x_1,...,x_n) R (y_1,...,y_n)\Leftrightarrow x_i\leq y_i \forall i=1,...,n

(R) \forall x\in A: xRx:\top

(S) \forall x,y\in A: xRy\Rightarrow yRx:\bot

Gegenbeispiel: (1,1)\leq (1,2); (1,1)\ngeq(1,2)

(A) \forall x,y\in A: xRy\wedge yRx\Rightarrow x=y: \top

(T) \forall x,y,z\in A: xRy\wedge yRz\Rightarrow xRz: \top

Beweis: x_i\leq y_i\wedge y_i\leq z_i\Rightarrow x_i\leq z_i

(*) Die Antisymmetrie ist bei Beispiel (b) und (c) eine Definitionsfrage. Es kommt darauf an, wie genau das Alter bzw, die Größe gemessen werden.

Vorsicht: Das hier nur abzuschreiben, ohne es durchzudenken, gibt Ärger. An der Tafel muß man auf Aufforderung dazu bereit sein, für alle Punkte Beweise oder Gegenbeispiele anzuführen (und beim UE-Test sowieso!).

Außerdem ist in einem Punkt da oben ein Hund drin, den ich mir vom Adrenalinrausch an der Tafel nicht mehr gemerkt habe :-).

Nachdenker erwünscht! (bitte auch gleich ausbessern, danke)

--Baccus 05:31, 26. Nov 2006 (CET)


Der Fehler war bei c) (A): x=y bedeutet hier nicht, dass beide gleich groß sind, sondern, dass es die gleichen Personen sind. Daher ist die Aussage falsch.

mick: naja, beim unteren beispiel wurde anhand einer funktion das alter ermittelt, was anscheinend das alter in zahlen wiedergibt. wenn man dem ansatz folgt, könnte man genausogut hier auch z.b. größe(a) = größe(b) anwenden mit den rückgabewerten true/false. dann wäre die aussage wahr.


andihi: Bei b) war auch ein Fehler bei der Antisymmetrie: Da die Angabe a ist nicht älter als b lautet, ist das gleichbedeutend mit Alter(a) \leq Alter(b) Daraus folgt für mich: (Alter(a) \leq Alter(b)) \wedge (Alter(b) \leq Alter(a)) \Rightarrow Alter(a) = Alter(b)


Bsp d ist glaube ich auch falsch: sollte lauten: (A) \forall x,y\in A: xRy\wedge yRx\Rightarrow x=y: \top wegen a R b\Leftrightarrow a-b\in\mathbb Z kann a R b immer falsch sein, ausser a=b \Rightarrow a-a = 0 und 0\in\mathbb Z Wenn laut Def. der Implikation diese immer wahr ist, wenn die erste Aussage falsch ist, so müßte die gesamte Aussage doch wahr sein und somit die Antisymmetrie ebenso


Zu letzter Behauptung: Beispiel: Bei (1.4,2.4)\in R gilt ja auch (2.4,1.4)\in R, aber a \neq b, deswegen keine Antisymmetrie. Andreas (Diskussion) 16:37, 2. Apr. 2015 (CEST)