Relationen

[ Weiter ] [ Zurück ] [ Zurück (Seitenende) ] [ Seitenende ] [ Überkapitel ] [ Bitte Skript-Fehler melden ]

12.2. Relationen

Geordnete Paare

Deﬁnition 12.2.1 (Geordnetes Paar). Ein geordnetes Paar besteht aus einer ersten und einer zweiten Komponente (Koordinate). Diese werden zwischen spitzen Klammern notiert: 〈a,b〉. Oft aber auch in runden: (a,b).

Deﬁnition 12.2.2 (Gleichheit von geordneten Paaren). Zwei geordnete Paare sind gleich , wenn sie in ihren beiden Komponenten gleich sind. Formal: 〈a,b〉 = 〈c,d〉 = _df.a = c ∧ b = d

Beispiel 12.2.3 (Unterschied von geordneten Paaren und Zweier-Mengen).
Sei a ⁄= b. Dann gilt {a,b} = {b,a}, aber 〈b,a〉 = 〈a,b〉 gilt nicht.

Kreuzprodukt

Deﬁnition 12.2.4 (Produktmenge, kartesisches Produkt). Ein Kreuzprodukt zweier Mengen besteht aus der Menge der geordneten Paare, welche sich aus deren Elementen kombinieren.

M × N = { 〈x,y 〉 | x ∈ M ∧y ∈ N }

Beispiel 12.2.5 (Kreuzprodukt).
Sei A = {a,b,c} und B = {1,2}:

A × B = {〈a,1〉,〈a,2〉,〈b,1〉,〈b,2〉,〈c,1〉,〈c,2〉}

B × B = {〈1,1〉,〈1,2〉,〈2,1〉,〈2,2〉}

$pict$

Frage

Welche Menge ergibt sich, wenn B = ∅?

Binäre Relationen

Deﬁnition 12.2.6 (Zweistellige Relation). Eine binäre Relation R zwischen Elementen zweier Mengen M und N ist eine Teilmenge des Kreuzproduktes von M und N.

R ⊆ M × N

Notationsvarianten

Anstelle von 〈a,b〉∈ R schreibt man gerne in Inﬁx-Notation aRb oder in Präﬁx-Notation R(a,b).

Beispiel 12.2.7 (Kleiner-Gleich-Relation).
Anstelle von 〈1,3〉∈ ≤ notiert man 1 ≤ 3.

Beispiel: Tagger-Lexikon

Die Menge der Token TOK = {“eine”, “der”, …}
Die Menge der STTS-Tags TAG = {“ADJ“,“ART”, …,“XY”}
Das Lexikon L ⊆ TOK × TAG:
L = {〈“eine”,“ART”〉,〈“eine”,“VVIMP”〉,…}

Eigenschaften binärer Relationen
Für eine Relation R ⊆ M × M gilt:

R ist reﬂexiv genau dann, wenn für alle x ∈ M gilt, 〈x,x〉∈ R
R ist irreﬂexiv genau dann, wenn für alle x ∈ M gilt, 〈x,x〉⁄∈ R
R ist symmetrisch genau dann, wenn für alle x,y ∈ M gilt, xRy → yRx
R ist antisymmetrisch genau dann, wenn für alle x,y ∈ M gilt, (xRy ∧ yRx) → x = y
R ist asymmetrisch genau dann, wenn für alle x,y ∈ M gilt, xRy →¬yRx
R ist total genau dann, wenn für alle x,y ∈ M gilt, xRy ∨ yRx
R ist transitiv genau dann, wenn für alle x,y,z ∈ M gilt, (xRy ∧ yRz) → xRz

Beispiele von Eigenschaften binärer Relationen
Sei M die Menge aller Menschen.

Die Relation ’x ist verheiratet mit y’ auf M ist
- symmetrisch (wenn a mit b verheiratet ist, dann auch b mit a)
- irreﬂexiv (niemand ist mit sich selbst verheiratet)
- aber nicht total (es gibt unverheiratete Menschen)
Die Relation ’x hat dieselben Eltern wie y’ auf M ist
- reﬂexiv (jeder hat dieselben Eltern wie er selbst)
- symmetrisch (wenn a dieselben Eltern hat wie b, dann hat auch b dieselben Eltern wie a)
- transitiv (wenn a dieselben Eltern hat wie b und b dieselben Eltern hat wie c, dann hat auch a dieselben Eltern wie c)
Die Relation ’x ist Vorfahre von y’ auf M ist
- transitiv (wenn a Vorfahre von b ist und b Vorfahre von c ist, dann ist a Vorfahre von c)
- irreﬂexiv (niemand ist Vorfahre von sich selbst)

n-Tupel und n-stelliges kartesisches Produkt

Deﬁnition 12.2.8 (n-Tupel). Ein n-Tupel ist die Verallgemeinerung des geordneten Paares auf endlich viele Komponenten: 〈x₁,x₂,…,x_n〉

Zwei n-Tupel sind gleich , wenn sie in jeder Komponente übereinstimmen: 〈x₁,x₂,…,x_n〉 = 〈y₁,y₂,…,y_m〉 = _df. x₁ = y₁ ∧ x₂ = y₂ ∧… ∧ x_n = y_m ∧ n = m

Deﬁnition 12.2.9 (n-stelliges kartesisches Produkt). Ein n-stelliges kartesisches Produkt besteht aus der Menge der n-Tupel, welche sich aus den n Mengen bilden lassen.

M₁ × M₂ × ⋅⋅⋅ × M_n = _df. { 〈x₁,x₂,…,x_n〉| x₁ ∈ M₁ ∧ x₂ ∈ M₂ ∧… ∧ x_n ∈ M_n }

[ Weiter ] [ Zurück ] [ Zurück (Seitenende) ] [ Seitenbeginn ] [ Überkapitel ] [ Bitte Skript-Fehler melden ]