Information Technology Reference
In-Depth Information
16.2 Anwendung von Relationen und Inferenz
Bisher haben wir Relationen nur deskriptiv verwendet. Relationen lassen sich aber
auch ähnlich wie Funktionen auf Elemente oder Mengen anwenden. Ist
R
X
Y
eine Relation zwischen den Mengen
X
und
Y
und
M
X
eine Teilmenge von
X
,
dann ist das Bild von
M
unter
R
die Menge
R
[
M
]={
y
Y
| (
x
X
)
(
x
,
y
)
R
x
M
}
.
(16.1)
R
[
M
]
enthält diejenigen Elemente aus
Y
,diezumindestenseinemElementausder
Menge
M
in Relation stehen.
Ist
f
:
X
Y
eine Abbildung, ergibt die Anwendung der Relation graph
(
f
)
auf
eine einelementige Menge
{
x
}
X
die einelementige Menge, die den Funktions-
wert von
x
enthält:
graph
(
f
)[{
x
}]={
f
(
x
)}
.
Allgemein gilt
graph(
f
)[
M
]=
f
[
M
]={
y
Y
| (
x
X
)(
x
M
f
(
x
)=
y
)}
für beliebige Teilmengen
M
X
.
Beispiel 16.3
Wir benutzen die Relation
R
aus dem Beispiel 16.1, um zu bestimmen,
welche Türen sich öffnen lassen, wenn man im Besitz der Schlüssel
s
1
,...,
s
4
ist. Da-
zumüssen wir alle Elemente (Türen) berechnen, die zumindestens einemder Schlüs-
sel
s
1
,...,
s
4
in der Relation „passt zu“ stehen, d. h.,
R
[{
s
1
,...,
s
4
}]={
t
1
,...,
t
5
}
ist die gesuchte Menge von Türen.
Die Menge
R
[{
s
1
,...,
s
4
}] kann sehr einfach mit Hilfe der Matrix in Tabelle 16.1
bestimmt werden. Dazu kodieren wir die Menge
M
= {
s
1
,...,
s
4
} als Zeilenvektor
mit fünf Komponenten, der an der
i
-ten Stelle eine 1 als Eintrag erhält, wenn
s
i
M
gilt, bzw. eine 0 im Falle
s
i
M
.SoergibtsichderVektor
(
1, 1, 1, 1, 0
)
.Wiebeidem
Falk-Schema für die Matrixmultiplikation eines Vektors mit einer Matrix schreiben
wir den Vektor links unten neben die Matrix. Danach transponieren wir den Vektor
und führen einen Vergleich mit jeder einzelnen Spalte der Matrix durch. Tritt bei
dem Vektor und einer Spalte gleichzeitig eine 1 auf, notieren wir unter der entspre-
chenden Spalte eine 1, ansonsten eine 0. Der sich auf diese Weise ergebende Vektor
(
1, 1, 1, 1, 1, 0
)
unterhalb der Matrix gibt in kodierter Form die gesuchte Menge
R
[
M
]
an: Er enthält an der
i
-ten Stelle genau dann eine 1, wenn
t
i
R
[
M
]
gilt. Tabelle 16.2
verdeutlicht dieses „Falk-Schema“ für Relationen.
Beispiel 16.4
Wir greifen das Beispiel 16.2 wieder auf und nehmen an, dass wir die
Information haben, dass das Messgerät einen Wert zwischen 0.2 und 0.4 angezeigt
hat. Daraus können wir folgern, dass der wahre Wert in der Menge
R
[
0.2, 0.4
]
=
[
0.1, 0.5
]
enthalten ist. Abbildung 16.2 veranschaulicht diesen Sachverhalt.
