4. Übungsblatt

MATHEMATIK FÜR INFORMATIKER I (WS 2000/01)

Abgabe: Montag, 20.11.2000 bis 13.30 Uhr

Der Abgabeort wird noch bekanntgegeben

Internet–Adresse der Vorlesung:

http://math–www.uni–paderborn.de/~chris/index9.html

14. Aufgabe: Auf der Menge IN × IN sei die Relation R definiert durch

(m, n) R (m′, n′) :⟺ m ≤ m′ und n ≤ n′ ((m, n), (m′, n′) ∈ IN × IN)

a) Beweise, daß R eine partielle Ordnung auf IN × IN ist. Untersuche, ob R linear ist.

b) Sei M := {∅, {5}, {6}, {1, 3}, {2, 3}, {1, 2, 3}, {1, 3, 4}, {2, 3, 4}}. Stelle das Hasse–Diagramm für die partiell geordnete Menge (M, ⊆) auf und bestimme alle minimalen Elemente und alle maximalen Elemente in (M, ⊆). Gibt es ein größtes bzw. ein kleinstes Element in (M, ⊆) ? Ist (M, ⊆) eine linear geordnete Menge ? (5)

15. Aufgabe: a) Sei M = {a, b, c, d, e}. Die Relation R auf M sei durch die nebenstehende Tabelle definiert. Zeige, daß R eine Äquivalenzrelation auf M ist.

b) Bestimme für jedes x ∈ M die Äquivalenzklasse [x]_{R} von x bzgl. R. Welches ist die Quotientenmenge von M nach R?

R a b c d e_{a 1 0 1 0 1}_{b 0 1 0 1 0}_{c 1 0 1 0 1}_{d 0 1 0 1 0}_{e 1 0 1 0 1}

(4)

16. Aufgabe: Definiere auf der Menge M := {a, b, c, d} eine Relation R, die reflexiv und symmetrisch, nicht aber transitiv ist (R definiert man am besten durch eine Tabelle. Es ist zu begründen, daß R die geforderten Eigenschaften besitzt) (3)

17. Aufgabe: Die Relation R auf der Menge IR × IR sei definiert durch

(x, y)R(x′, y′) :⟺ x − x′ = y − y′.

a) Beweise, daß R eine Äquivalenzrelation auf IR × IR ist.

b) Welche Elemente haben die Äquivalenzklassen von (0, 0) bzw. (2, 5) ? Stelle diese Äquivalenzklassen anschaulich in der Ebene dar. (4)