Boo­le­sche Funk­tio­nen und ihre Nor­mal­for­men

Man be­trach­tet die Boo­le­sche Al­ge­bra mit der Trä­ger­men­ge B={0,1}. Die Funk­tio­nen f mit
f : {0, 1}ⁿ → {0, 1}, n ≥ 1 wer­den als Boo­le­sche Funk­tio­nen be­zeich­net. Die An­zahl n der Ar­gu­men­te (Va­ria­blen) einer Boo­le­schen Funk­ti­on heißt ihre Stel­lig­keit. Für n = 1 spricht man von unä­ren (unary), für n = 2 von bi­nä­ren (bi­na­ry) und für n = 3 von ter­nä­ren (tern­ary) Funk­tio­nen.
Eine Boo­le­sche Funk­ti­on ist damit eine Ab­bil­dung, die je­weils n bits auf ein ein­zi­ges bit ab­bil­det.  Alle sech­zehn bi­nä­ren Boo­le­schen Funk­tio­nen sind hier in glei­cher Num­me­rie­rung wie auf Seite 12 (in mo­di­fi­zier­ter Ta­bel­len­form) noch­mals auf­ge­führt:

Jede n-stel­li­ge Boo­le­sche Funk­ti­on kann durch ihre Wahr­heits­ta­fel dar­ge­stellt wer­den. Rechts ist z.B. die Wahr­heits­ta­fel einer tenä­ren Boo­le­schen Funk­ti­on f mit f: y = f(a, b, c) zu sehen. Jede sol­che Wahr­heits­ta­fel ent­hält je eine Spal­te für die Funk­ti­ons­ar­gu­men­te (ato­ma­re Va­ria­blen), je­weils eine Zeile für jede Kom­bi­na­ti­on der Wahr­heits­wer­te und eine zu­sätz­li­che letz­te Spal­te, in der der zu­ge­hö­ri­ge Funk­ti­ons­wert an­ge­ge­ben wird.

 Die ab­ge­bil­de­te Wahr­heits­ta­fel hat 

Zei­len, die Wahr­heits­ta­fel einer n-stel­li­gen Boo­le­schen Funk­ti­on hat 2ⁿ Zei­len.
Es gibt drei­stel­li­ge (tenä­re) und n-stel­li­ge Boo­le­sche Funk­tio­nen.

Die Dar­stel­lung mit­hil­fe einer Wahr­heits­ta­fel kommt folg­lich mit wach­sen­der Va­ria­blen­zahl schnell an ihre Gren­zen. Für die Her­stel­lung elek­tro­ni­scher Schal­tun­gen ist es in der Pra­xis daher sehr be­deut­sam, dass zu jeder Wahr­heits­ta­fel ein äqui­va­len­ter lo­gi­scher Term ge­ne­riert wer­den kann. Statt die Wahr­heits­ta­fel mit viel Re­chen­auf­wand auf­zu­stel­len, kann dann der äqui­va­len­te Term nach den Re­chen­ge­set­zen der Boo­le­schen Al­ge­bra um­ge­formt und auf der Grund­la­ge des ver­ein­fach­ten Terms eine Schal­tung kon­stru­iert wer­den.

Beim Auf­stel­len von äqui­va­len­ten Ter­men zu vor­ge­ge­be­nen Wahr­heits­ta­feln spie­len die  Nor­mal­for­men von Boo­le­schen Funk­tio­nen eine ent­schei­den­de Rolle. Nor­mal­for­men von Boo­le­schen Funk­tio­nen wer­den im In­for­ma­tik­un­ter­richt der Kurs­stu­fe be­han­delt und sol­len daher hier nicht im Mit­tel­punkt ste­hen.²⁶ Viel­mehr soll im nächs­ten Ka­pi­tel ein an­schau­li­cher Zu­gang er­läu­tert wer­den, der im Rah­men einer op­tio­na­len Ver­tie­fung in einer neun­ten Klas­se denk­bar wäre und sich dabei haupt­säch­lich auf bi­nä­re Boo­le­schen Funk­tio­nen be­schränkt.  

Ka­no­ni­sche Dis­junk­ti­ve und Kon­junk­ti­ve Nor­mal­form (KDNF, KKNF)

Den aus­sa­ge­lo­gi­schen Funk­ti­ons­term zu einer durch ihre Wahr­heits­ta­fel vor­lie­gen­den Boo­le­schen Funk­ti­on kann man auf zwei fun­da­men­ta­le Arten ge­ne­rie­ren. In der kon­junk­ti­ven Nor­mal­form (KNF) als Kon­junk­ti­on von Dis­junk­tio­nen der be­tei­lig­ten Va­ria­blen bzw. ihrer Ne­ga­tio­nen und in der dis­junk­ti­ven Nor­mal­form (DNF) als Dis­junk­ti­on von ent­spre­chen­den Kon­junk­tio­nen.²⁷ Wir be­schäf­ti­gen uns hier nur mit ka­no­ni­schen Nor­mal­for­men. An­mer­kun­gen zur Un­ter­schei­dung von Nor­mal­for­men  (DNF und KNF) und den ka­no­ni­schen Nor­mal­for­men (KDNF und KKNF) fol­gen am Ende die­ses Ab­schnit­tes.

Was sich hin­ter den Nor­mal­for­men ver­birgt, soll hier zu­nächst am Bei­spiel einer bi­nä­ren Boo­le­schen Funk­ti­on er­läu­tert wer­den. Dis­junk­ti­ve und kon­junk­ti­ve Nor­mal­for­men las­sen sich mit Venn-Dia­gram­men auch an­schau­lich mo­ti­vie­ren. Jeder Voll­kon­junk­ti­on²⁸ der ato­ma­ren Aus­sa­gen (bzw. ihrer Ne­ga­tio­nen) in den ein­zel­nen Zei­len der Wahr­heits­ta­bel­le ent­spricht dabei eine der Teil­flä­chen im Venn-Dia­gramm, was hier für den Fall n=2 am Bei­spiel der Bi­junk­ti­on a↔b er­läu­tert wird.

a) Wir be­gin­nen mit der KDNF, die vier mög­li­chen Voll­kon­junk­tio­nen sind hier dar­ge­stellt.

Man bil­det die Dis­junk­ti­on aus den Voll­kon­junk­tio­nen, bei denen in der Spal­te von f eine "1" ein­ge­tra­gen ist. Im Bei­spiel wählt man also (1) und (4) aus und kann so­fort die ka­no­ni­sche dis­junk­ti­ve Nor­mal­form (KDNF) von f no­tie­ren:  (a∧b)∨(¬a∧¬b).
Die­ser Term lie­fert nur bei den Kom­bi­na­tio­nen (1) und (4) eine "1", an­der­falls eine "0".
Im an­schau­li­chen Mo­dell der Men­ge­nal­ge­bra geht man dabei von den Schnitt­men­gen in den ers­ten vier Spal­ten aus und setzt durch Ver­ei­ni­gung der pas­sen­den Schnitt­men­gen das ge­such­te Venn-Dia­gramm zu­sam­men.
Die Dis­junk­ti­on (in der Aus­sa­gen­al­ge­bra) ent­spricht der Ver­ei­ni­gung (in der Men­ge­nal­ge­bra) bzw. einer Ad­di­ti­on (in der Boo­le­schen Al­ge­bra). Die Kon­junk­ti­on (in der Aus­sa­gen­al­ge­bra) ent­spricht dem Durch­schnitt (in der Men­ge­nal­ge­bra) bzw. dem Pro­dukt (in der Boo­le­schen Al­ge­bra). Ab­stra­hiert man dies in der kon­text­frei­en Struk­tur der Boo­le­schen Al­ge­bra, so wer­den beim Auf­stel­len der KDNF also Sum­men von Pro­duk­ten ge­bil­det, wes­halb das Ver­fah­ren im engl. Sprach­raum auch als sum of pro­ducts (SOP) be­zeich­net wird.  

b) Das Vor­ge­hen zum Auf­stel­len der KKNF ist dual zu dem bei der KDNF. Die vier mög­li­chen Voll­dis­junk­tio­nen er­hält man durch Ne­ga­ti­on der Voll­kon­junk­tio­nen von oben:

Nun geht man nach dem Dua­li­täts­prin­zip vor. Wäh­rend oben die "Summe von Pro­duk­ten" ge­bil­det wurde, bil­det man nun das "Pro­dukt von Sum­men" (engl. pro­duct of sums (POS)).
Man bil­det also die Kon­junk­ti­on aus den Voll­dis­junk­tio­nen, bei denen in der Spal­te von f eine "0" ein­ge­tra­gen ist. Im Bei­spiel wählt man (2) und (3) aus und kann damit die ka­no­ni­sche kon­junk­ti­ve Nor­mal­form (KKNF) von f no­tie­ren: ((¬a∨b)∧(a∨¬b).
Die­ser Term lie­fert nur bei den Kom­bi­na­tio­nen (2) und (3) eine "0", an­dern­falls eine "1".
Im an­schau­li­chen Mo­dell der Men­ge­nal­ge­bra geht man dabei von Ver­ei­ni­gungs­men­gen der  ers­ten vier Spal­ten aus und bil­det deren Schnitt­men­ge, um das ge­such­te Venn-Dia­gramm zu er­hal­ten, eben ge­ra­de "an­ders herum", dual im Sinne der Boo­le­schen Al­ge­bra.

Di­dak­ti­scher Hin­weis: Würde man die Venn-Dia­gram­me auf Folie dru­cken und über­ein­an­der legen, so könn­te man die Schnitt­men­ge daran er­ken­nen, dass sie am dun­kels­ten ge­färbt wäre. Dazu müss­te man die Farb­in­ten­si­tät der ge­färb­ten Aus­gangs­men­gen re­la­tiv nied­rig wäh­len, was in der mit­ge­lie­fer­ten Geo­Gebra­da­tei M9au­g02_VENN-2Var.ggb mit­hil­fe des Schie­be­reg­lers DK ("Deck­kraft") rea­li­siert wer­den könn­te. Ge­schick­ter ist al­ler­dings das In­ver­tie­ren der Far­ben, dann bleibt die der Schnitt­men­ge ent­spre­chen­de Teil­flä­che weiß.
 

Zur Dua­li­tät von KDNF und KKNF in der Wahr­heits­ta­fel

Be­trach­tet man die Wahr­heits­ta­feln der vier Voll­kon­junk­tio­nen, so ent­hal­ten diese je­weils genau eine "1" und 4-1=3 Nul­len. Durch die Dis­junk­ti­on der Voll­kon­junk­tio­nen wer­den alle Ein­sen in die Spal­te von f "über­tra­gen". Es wird ge­wis­ser­ma­ßen die Summe ge­bil­det.
Bei der dua­len Vor­ge­hens­wei­se der KNF nimmt jede der vier Voll­dis­junk­tio­nen nur genau ein­mal den Wert "0" an, sonst immer "1". Durch die Kon­junk­ti­on der Voll­dis­junk­tio­nen wer­den alle Nul­len in die Spal­te von f "über­tra­gen", es wird das Pro­dukt ge­bil­det.

Be­trach­tet man dies in der Wahr­heits­ta­fel, so las­sen sich die bei­den dua­len Vor­ge­hens­wei­sen auch auf nu­me­ri­scher Ebene der Ta­bel­len gut nach­voll­zie­hen:

Ka­no­ni­sche Ka­no­ni­sche
Dis­junk­ti­ve Nor­mal­form Kon­junk­ti­ve Nor­mal­form
"Summe von Pro­duk­ten" "Pro­dukt von Sum­men"
   
Diese duale Sicht soll nun ab­schlie­ßend noch am Bei­spiel einer ter­nä­ren Boo­le­schen Funk­ti­on
er­läu­tert wer­den, wobei auf eine aus­führ­li­che Dar­stel­lung ver­zich­tet wird.

Bei­spiel:  y = f(a, b, c) (Es liegt nur die Wahr­heits­ta­fel vor, ein Term ist nicht be­kannt)

Ana­log zum vor­an­ge­gan­ge­nen Bei­spiel der bi­nä­ren Funk­ti­on sind auch hier die Wahr­heits­ta­feln der Voll­kon­junk­tio­nen (C2, C3, C5 und C7) und der
Voll­dis­junk­tio­nen  (¬C1, ¬C4, ¬C6 und ¬C8) zu sehen:

Un­ter­schied zwi­schen Nor­mal­for­men und ka­no­ni­schen Nor­mal­for­men

Wie be­reits an­ge­merkt, spricht man bei einer Kon­junk­ti­on, in der alle auf­tre­ten­den Va­ria­blen (oder ihre Ne­ga­tio­nen) ein­mal ein­ge­bun­den sind, von einer Voll­kon­junk­ti­on (Min­term). Bei einer Voll­dis­junk­ti­on (Max­term) ver­hält es sich ana­log. Wenn in einer DNF nur Voll­kon­junk­tio­nen auf­tre­ten, so wie das hier der Fall war, so han­delt es sich um eine ka­no­ni­sche dis­junk­ti­ve Nor­mal­form (KDNF). Ent­spre­chend spricht man von einer ka­no­ni­schen kon­junk­ti­ven Nor­mal­form (KKNF), wenn nur Voll­dis­junk­tio­nen auf­tre­ten. Bei der KDNF (KKNF) sind also alle Va­ria­blen (bzw. ihre Ne­ga­tio­nen) in allen Klam­mern genau ein­mal ent­hal­ten.
Die DNF ist da­ge­gen "nur" als dis­junk­ti­ve Ver­knüp­fung kon­junk­ti­ver Terme de­fi­niert, des­we­gen kön­nen bei einer DNF auch Va­ria­blen (bzw. ihre Ne­ga­tio­nen) feh­len, z.B. wäre
f(a, b, c) = (a∧b∧c) v (a∧¬b) v ¬c eine DNF. Ana­log ver­hält es sich bei der KNF.

In Klas­se 9 ist diese Un­ter­schei­dung nicht er­for­der­lich. Man kann ver­ein­fa­chend von der DNF bzw. KNF spre­chen, da jede KDNF (KKNF) gleich­zei­tig eine DNF (KNF) ist, nur um­ge­kehrt ist dies nicht der Fall.²⁹

²⁶ Zum Ein­le­sen eig­net sich z.B. [BEU], S. 245 ff. Dort ist u.a. ein von Karn­augh und Veitch ent­wi­ckel­tes gra­fi­sches Ver­fah­ren zur Vein­fa­chung boo­le­scher Aus­drü­cke be­schrie­ben, bei dem sog. KV-Dia­gram­me ein­ge­setzt wer­den.  [AIG], S. 217ff und [LES], S. 116 ff bie­ten eben­falls kom­pak­te überli­cke.  

²⁷Vgl. Auf­ga­be 2.26 , [AHR], S. 48

²⁸ Von einer Voll­kon­junk­ti­on spricht man, wenn alle auf­tre­ten­den Va­ria­blen (oder ihre Ne­ga­tio­nen) ein­ge­bun­den sind.

²⁹ Eine Mög­lich­keit zur Ver­tie­fung bie­tet die im Un­ter­richts­gang näher be­schrie­be­ne Lern­platt­form Lo­gic­Traf­fic von Ruedi Ar­nold, bei der auch zwi­schen DNF und KDNF un­ter­schie­den wer­den könn­te.

 

Hin­ter­grund: Her­un­ter­la­den [odt][601 KB]

Hin­ter­grund: Her­un­ter­la­den [pdf][698 KB]

 

Wei­ter zu His­to­ri­sche An­mer­kun­gen