Information Technology Reference
In-Depth Information
g
1
0
1
g
3
g
2
1
ac
d
c
1
0
1
1
0
b
=
x
2
x
2
a
b
0
0
d
x
1
x
1
0
1
0
1
Abbildung 3.11: Geometrische Deutung des Zusammenschaltens mehrerer Schwel-
lenwertelemente zur Berechnung der Biimplikation.
tretenden Teilfunktionen linear separabel sind. Mit Hilfe der disjunktiven Normal-
form (oder auch der konjunktiven) kann man sogar zeigen, dass Netze mit nur zwei
Schichten notwendig sind:
Algorithmus 3.1 (Darstellung Boolescher Funktionen)
Sei y
=
f
(
x
1
,...,
x
n
)
eine Boolesche Funktion von n Variablen.
(i) Stelle die Boolesche Funktion f
(
x
1
,...,
x
n
)
in disjunktiver Normalform dar. D. h., be-
stimme D
f
=
K
1
...
K
m
,wobeialleK
j
Konjunktionen von n Literalen sind, also
K
j
=
l
j
1
...
l
jn
mit l
ji
=
x
i
(positives Literal) oder l
ji
= ¬
x
i
(negatives Literal).
(ii) Lege für jede Konjunktion K
j
der disjunktiven Normalform ein Neuron an (mit n Ein-
gängen — ein Eingang für jede Variable) wobei
n
i
=
1
w
ji
.
2,
falls l
ji
=
x
i
,
j
=
n
1 +
1
w
ji
=
und
2,
falls l
ji
= ¬
x
i
,
2
(iii) Lege ein Ausgabeneuron an (mit m Eingängen — ein Eingang für jedes in Schritt (ii)
angelegte Neuron) wobei
w
(
n
+
1
)
k
=
2,
k
=
1, . . . ,
m
,
und
n
+1
=
1.
In dem so konstruierten Netz berechnet jedes in Schritt 2 angelegte Neuron eine
Konjunktion und das Ausgabeneuron deren Disjunktion.
Anschaulich wird durch jedes Neuron in der ersten Schicht eine Hyperebene be-
schrieben, die die Ecke des Hypereinheitswürfels abtrennt, für die die Konjunktion
den Wert 1 liefert. Die Gleichung dieser Hyperebene lässt sich leicht bestimmen: Der
Normalenvektor zeigt von der Mitte des Hypereinheitswürfels zur abzutrennenden
Ecke, hat also in allen Komponenten, in denen der Ortsvektor der Ecke den Wert 1
hat, ebenfalls den Wert 1, in allen Komponenten, in denen der Ortsvektor der Ecke
den Wert 0 hat, den Wert
1. (Zur Veranschaulichung betrachte man den dreidi-
mensionalen Fall.) Wir multiplizieren den Normalenvektor jedoch mit 2, um einen
ganzzahligen Schwellenwert zu erhalten. Der Schwellenwert ist so zu bestimmen,
dass er nur dann überschritten wird, wenn alle mit Gewicht 2 versehenen Eingaben
den Wert 1 und alle anderen den Wert 0 haben. Einen solchen Wert liefert gerade die
in Schritt 2 angegebene Formel.
