Hüllenbildung

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

13.2. Hüllenbildung

Hüllen (closures)

Motivation

Das Aufzählen oder deﬁnieren einer binären Relation kann mühsam sein. Oft reicht es, ein “Skelett” einer Relation zu bilden, welches dann durch Hüllenbildung “automatisch” erweitert wird.

Beispiel 13.2.1 (Direkte und indirekte Nachfahren).

Seien in DV = {〈anna,berta〉,〈berta,carla〉,〈carla,dana〉} alle direkten Nachfahren, d.h. die Beziehung “x ist Kind von y”.
Wie gibt man die Relation aller direkten und indirekten Nachfahren V an? Z.B. durch Aufzählen:
Wie kann man das kürzer schreiben?

Komposition von Relationen (Produkt)

Deﬁnition 13.2.2. Die Komposition von zwei binären Relationen R ⊆ M × M und S ⊆ M × M ergibt wieder eine binäre Relation.

Sie beinhaltet ein Paar 〈u,w〉 genau dann, wenn R ein Paar 〈u,v〉 enthält und S ein Paar 〈v,w〉.

v fungiert zwar als Bindeglied – ist aber im Resultat nicht mehr sichtbar!

RS = { 〈u,w 〉 | ∃v (uRv ∧ vSw ) }

Komposition von Relationen in PROLOG

% kind(KIND,ELTER)
kind(anna,berta).
kind(berta,carla).
kind(carla,dana).

% Komposition der Kind-Relation
kind_comp_kind(U,W):-
kind(U,V),
kind(V,W).

?- kind_comp_kind(X,Y).

Hüllen einer Relation

Potenzschreibweise

R⁰ = {〈x,x〉| x ∈ M} , R¹ = R
Rⁿ = RRⁿ⁻¹ für n ≥ 1

Hüllen

Transitive Hülle : $⋃ R+ = Rn n≥1$
Reﬂexive Hülle : $Rreflexiv = R ∪ R0$
Reﬂexiv-transitive Hülle : $∗ ⋃ n R = R n≥0$

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