Unterabschnitte

© 1999 François Bry
Dieses Lehrmaterial wird ausschließlich zur privaten Verwendung angeboten. Eine nichtprivate Nutzung (z.B. im Unterricht oder eine Veröffentlichung von Kopien oder Übersetzungen) dieses Lehrmaterials bedarf der Erlaubnis des Autors.


3.1 Boole'sche Funktionen

Die Bezeichnung geht zurück auf George Boole (Lincoln 1815 - Cork 1864).

Nullstellige Boole'sche Funktionen

Für die nullstelligen Junktoren ist die zuzuordnende Boole'sche Funktion ebenfalls nullstellig, also einfach ein Wahrheitswert, und natürlich w für und f für .

Bemerkung:   Die Formeln und sollten nicht mit den Wahrheitswerten w und f verwechselt werden, obwohl manchmal das gleiche Symbol für einen nullstelligen Junktor und seinen Wahrheitswert verwendet wird.

Einstellige Boole'sche Funktionen

Die einfachste einstellige Boole'sche Funktion {w,f} → {w,f} ist die Identität Id, aber sie entspricht keinem einstelligen Junktor. Welche einstellige Boole'sche Funktion zum einstelligen Junktor ¬ gehört, ergibt sich unmittelbar, weil nur zwei Wahrheitswerte vorausgesetzt wurden (wie die Negation in mehrwertigen Logiken zu interpretieren wäre, ist dagegen im allgemeinen nicht so offensichtlich):
{w,f} → {w,f}
w → f
f → w
Üblicherweise hat diese Boole'sche Funktion den Namen NOT und wird durch eine sogenannte ,,Wahrheitstabelle`` angegeben:

 oder 
X NOT X
w f
f w

Bemerkung:   In der Variante der Tabelle auf der rechten Seite ist das X nicht etwa eine Aussagenvariable, denn die Definition einer Boole'schen Funktion enthält keine syntaktischen Bestandteile von Formeln einer Logik, sondern eine Variable im üblichen mathematischen Sinn, die für einen der Werte w bzw. f steht. Im Kontext von Boole'schen Funktionen spricht man von Boole'schen Variablen.

Zweistellige Boole'sche Funktionen

Zweistellige Boole'sche Funktionen {w,f}x{w,f} → {w,f} können in gleicher Weise durch Wahrheitstabellen angegeben werden wie einstellige. Zum Beispiel ist die zweistellige Boole'sche Funktion namens OR durch folgende Wahrheitstabelle definiert:

     oder     
X    Y X OR Y
w    w w
w    f w
f    w w
f    f f

Welche zweistelligen Boole'schen Funktionen den zweistelligen Junktoren zuzuordnen sind, ist weniger unmittelbar als bei den null- und einstelligen. Kombinatorisch gibt es 24 = 16 zweistellige Boole'sche Funktionen:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
w   w w w w w w w w w f f f f f f f f
w   f w w w w f f f f w w w w f f f f
f   w w w f f w w f f w w f f w w f f
f   f w f w f w f w f w f w f w f w f

Davon sind aber einige uninteressant, da sie gar nicht von allen ihren Argumenten abhängen. Diese uninteressanten Boole'schen Funktionen sind:
1: die konstante Funktion TRUE
4: die Funktion Id1 (auch π1 oder 1. Projektion genannt)
6: die Funktion Id2(auch π2 oder 2. Projektion genannt)
11: die Negation des 2. Arguments
13: die Negation des 1. Arguments
16: die konstante Funktion FALSE
Es verbleiben also noch zehn interessante zweistellige Boole'sche Funktionen. Sie haben folgende Namen:

Die Namensgebung suggeriert natürlich - zumindest in einigen Fällen - welchen zweistelligen Junktoren diese zweistelligen Boole'schen Funktionen wohl zugeordnet werden. Allerdings stehen den zehn zweistelligen Boole'schen Funktionen nur vier zweistellige Junktoren gegenüber, die in Kapitel 2 für die Aussagenlogik oder Prädikatenlogik eingeführt wurden. Tatsächlich hätte man aber auch genauso viele zweistellige Junktoren einführen können wie es Boole'sche Funktionen gibt.

Die Schreibweisen der zusätzlichen Junktoren und die Zuordnung zwischen Junktoren und Boole'schen Funktionen ergibt sich aus folgender Tabelle:

∧ ∨ ⇒ ⇐ ↑ ↓ ⇔
AND OR IMP RIMP NAND NOR NIMP NRIMP EQU NEQU  XOR
w   w w w w w f f f f w f
w   f f w f w w f w f f w
f   w f w w f w f f w f w
f   f f f w w w w f f w f

Aus der Systematik dieser Tabelle erkennt man auch, warum meistens nicht alle diese Junktoren eingeführt werden: In vielen Fällen lassen sich ihre Boole'schen Funktionen auf die Boole'schen Funktionen anderer Junktoren zurückführen und damit als überflüssig ansehen. Zum Beispiel erhält man RIMP (,,reverse implication``) einfach durch Vertauschen der Argumente von IMP. Die Boole'sche Funktion NIMP entsteht durch Negation von IMP, d.h., X NIMP Y = NOT(X IMP Y) oder NIMP = NOT ° IMP.

Mehrstellige Boole'sche Funktionen

Junktoren einer Stelligkeit größer als zwei werden selten eingeführt. Der Grund ist, dass ihre Boole'schen Funktionen {w,f}n → {w,f} im gleichen Sinne überflüssig sind wie einige der zweistelligen: Man kann sie stets auf Boole'sche Funktionen zurückführen, deren Stelligkeit höchsten zwei ist.

Um etwas systematischer klären zu können, wie sich Boole'sche Funktionen aufeinander zurückführen lassen, benötigen wir zunächst einige Begriffe.

Definition 3.1.2  
AND, OR, IMP, RIMP, NAND, NOR, NIMP, NRIMP heißen primäre Boole'sche Funktionen. EQU, NEQU heißen sekundäre Boole'sche Funktionen.

Eine Menge B von Boole'schen Funktionen heißt eine vollständige Basis, falls jede Boole'sche Funktion als Komposition von Funktionen in B definiert werden kann.

Eine vollständige Basis B heißt minimal, falls keine echte Teilmenge von B eine vollständige Basis ist.

Bemerkungen:  
  1. Primär sind die zweistelligen Boole'schen Funktionen, deren Spalten in der obigen Wahrheitstabelle entweder ein einziges w oder ein einziges f enthalten. Sekundär sind die zweistelligen Boole'schen Funktionen, deren Spalten in der obigen Wahrheitstabelle zwei w und zwei f enthalten.

  2. Die obigen Tabellen definieren, wie gesagt, zweistellige Boole'sche Funktionen. Offensichtlich kann jede n-stellige Boole'sche Funktion durch eine Wahrheitstabelle mit n+1 Spalten und 2n Zeilen definiert werden.

    Beispiel: die dreistellige Boole'sche Funktion, die w liefert genau dann wenn alle ihre Argumente gleich sind, wird durch folgende Wahrheitstabelle mit 8 Zeilen angegeben:

                          
    w w w w
    w w f f
    w f w f
    w f f f
    f w w f
    f w f f
    f f w f
    f f f w

  3. Die Komposition bedeutet wie üblich die Hintereinanderausführung. Zum Beispiel kann die Boole'sche Funktion OR wie folgt als Komposition von NOT und AND definiert werden:
    X OR Y = NOT(NOT X AND NOT Y).

Satz 3.1.3  
  1. Für jede primäre Boole'sche Funktion F ist {F,NOT} eine vollständige Basis.
  2. {NAND} und {NOR} sind minimale vollständige Basen.

Beweis:  (skizziert)
    • (a)  Jede zweistellige Boole'sche Funktion kann als Komposition von AND und NOT definiert werden.

      Die Boole'schen Funktionen F1,F2,F3,F4, seien wie folgt definiert:

      F1 F2 F3 F4
      w     w f w w w
      w     f w f w w
      f     w w w f w
      f     f w w w f

      Sei F eine zweistellige Boole'sche Funktion mit Wahrheitstabelle:

      X   Y X F Y
      w     w z1
      w     f z2
      f     w z3
      f     f z4

      Ist I die Teilmenge von {1, 2, 3, 4} mit zi = f für i∈I, und ist AND*{Fi1,...,Fin}(X,Y) definiert als Abkürzung für die rechtsassoziativ geklammerte Form von [X Fi1 Y] AND ... AND [X Fin Y], so gilt:

      F = AND*{Fi | i∈I}


      weil die Wahrheitstabelle der zweistelligen Boole'schen Funktion AND*{Fi | i∈I} genau in denselben Zeilen den Wert f hat wie die Wahrheitstabelle von F.

      Wir haben also F als Komposition von {AND,F1,F2,F3,F4} dargestellt. Jetzt stellen wir noch {F1,F2,F3,F4} als Komposition von {AND,NOT} dar. Es gilt

      X F1 Y =  NOT( X AND Y)
      X F2 Y =  NOT( X AND NOT Y)
      X F3 Y =  NOT( NOT X AND Y)
      X F4 Y =  NOT( NOT X AND NOT Y)






      Man beachte das systematische Muster: Die Funktion Fi hat genau in der i-ten Zeile den Wert f. Seien (a,b) die (X,Y)-Werte dieser i-ten Zeile. Dann hat die Definition von Fi die Form

      X Fi Y = NOT(A(X) AND B(Y))






      Id falls b = w
      B =  {
      NOT falls b = f

      Bemerkung: Die Notation 0 für f, 1 für w und x für AND macht das Obige anschaulicher.

    • (b)  Jede n-stellige Boole'sche Funktion mit n ≥ 3 kann als Komposition von zweistelligen Boole'schen Funktionen und NOT definiert werden.

      Das unter 1 (a) beschriebene Muster kann auch auf drei oder mehr Argumente übertragen werden.

    • (c)  Aus 1 (a) und 1 (b) folgt, dass eine vollständige Basis ist.

    • (d)  Ist F eine primäre Boole'sche Funktion, so kann AND als Komposition von F und NOT definiert werden.

      Das ist für jede primäre Boole'sche Funktion F durch eine geeignete Definition zu zeigen.

    • (e)  AND lässt sich nicht als Komposition von einer sekundären Boole'schen Funktion und NOT definieren.

  2. Anhand der Wahrheitstabelle überprüft man leicht, dass NOT X = X NAND X = X NOR X gilt. Das Ergebnis folgt dann aus 1 (a), 1 (d) und der Tatsache, dass ∅ keine vollständige Basis ist.

Es ist üblich, die gleiche Notation für Junktoren und für die ihnen zugeordneten Boole'schen Funktionen zu verwenden. Wir werden uns von nun an diesem Brauch anschließen. Dabei darf aber der Unterschied zwischen Junktor und Boole'scher Funktion nicht übersehen werden!

Validierung