Information Technology Reference
In-Depth Information
x
1
x
2
y
1
0
0
1
x
2
1
0
0
0
1
0
0
1
1
1
x
1
0
1
Abbildung 3.9: Das Biimplikationsproblem: Es gibt keine Trenngerade.
Eingaben
Boolesche Funktionen
linear separable Funktionen
2
2
1
1
=
4
4
2
2
2
2
=
16
14
2
2
3
3
=
256
104
2
2
4
4
=
65536
1774
2
2
5
4.3 · 10
9
5
94572
2
2
6
1.8 · 10
19
5.0 · 10
6
6
Tabe l l e 3 . 1 : Ge samt zahl und Zahl de r l i nea r sepa r ab l en Boo l e s chen Funk t i onen von
n
Eingaben (Widner [1960] zitiert nach Zell [1996]).
Den formalen Beweis führt man durch
reductio ad absurdum
.Wirnehmenan,es
gäbe ein Schwellenwertelement mit Gewichten
w
1
und
w
2
und Schwellenwert
,das
die Biimplikation berechnet. Dann gilt
wegen (0, 0) 1:
,
(1)
0
wegen
(
1, 0
)
0:
w
1
<
,
(
2
)
wegen
(
0, 1
)
0:
w
2
<
,
(
3
)
wegen
(
1, 1
)
1:
w
1
+
w
2
.
(
4
)
Aus (2) und (3) folgt
w
1
+
w
2
<
2
,waszusammenmit(4)2
>
,also
>
0ergibt.
Das ist aber ein Widerspruch zu (1). Folglich gibt es kein Schwellenwertelement, das
die Biimplikation berechnet.
Die Tatsache, dass nur linear separable Funktionen darstellbar sind, erscheint
auf den ersten Blick als nur geringe Einschränkung, da von den 16 möglichen Boole-
schen Funktionen von zwei Variablen nur zwei
nicht
linear separabel sind (nämlich
die Biimplikation und das Exklusive Oder). Nimmt jedoch die Zahl der Eingaben
zu, so sinkt der Anteil der linear separablen an allen Booleschen Funktionen rapide
(siehe Tabelle 3.1). Für eine größere Anzahl von Eingaben können (einzelne) Schwel-
lenwertelemente daher „fast keine“ Funktionen berechnen.
3.4 Netze von Schwellenwertelementen
Zwar sind Schwellenwertelemente, wie der vorangehende Abschnitt zeigte, in ih-
rer Ausdrucksmächtigkeit beschränkt, doch haben wir bis jetzt auch nur einzelne
