Implikationsalgebren


Unter einer (linksseitigen) Implikationsalgebra (G,*) versteht man ein Gruppoid (G,*), in dem die folgenden Axiome für alle a, b, c aus A, erfüllt sind:

(1) (a * b) * a = a,

(2) (a * b) * b = (b * a) * a,

(3) a * (b * c) = b * (a * c).

Man nennt (1) auch das (linksseitige) Kontraktionsaxiom, (2) die (linksseitige) Quasi-Kommutativität (man beachte aber (13)) und (3) das (rechtsseitige) Vertauschungsaxiom für Implikationsalgebren. Dual dazu sind (rechtsseitige) Implikationsalgebren durch die folgenden Axiome definiert:

(1') a * (b * a) = a,

(2') a * (a * b) = b * (b * a),

(3') (a * b) * c = (a * c) * b.

Definiert man in einer Booleschen Algebra (B,,,',0,1) die beiden Verknüpfungen und - durch

  a b = a' b   und   a - b = a b',

so ist (B,) linksseitige Implikationsalgebra und (B,-) rechtsseitige. Das erste Beispiel entspricht dem Implikationsbegriff für die Booleschen Algebren, die bei der Betrachtung aussagenlogischer Formeln eingeführt werden, das zweite Beispiel entspricht der mengentheoretischen Differenz in den Booleschen Algebren, die sich als Potenzmengen ergeben. Daher könnte man die rechtsseitigen Implikationsalgebren auch als Subtraktionsalgebren bezeichnen. Diese ganz unterschiedlichen Beispiele sind der Grund dafür, daß hier das Verknüpfungssymbol * dem für Implikationsalgebren sonst eher üblichen vorgezogen wird. Da jede Boolesche Algebra in natürlicher Weise zwei Implikationsalgebren liefert, werden diese auch als Semi-Boolesche Algebren bezeichnet. Wenn im folgenden einfach von Implikationsalgebren gesprochen wird, so sind stets linksseitige gemeint.


Satz In jeder Implikations-Algebra (G,*) gelten die folgenden Aussagen für alle a, b aus G.

(4) a * (a * b) = a * b,

(5) a * a = (a * b) * (a * b),

(6) es gibt ein eindeutig bestimmtes Element 1 aus G mit a * a = 1 für alle a,

(7) 1 * a = a und a * 1 = 1,

(8) a * (b * a) = 1,

(9) a * ((a * b) * b) = 1,

(10) (a * b) * (b * a) = b * a,

(11) ((a * b) * b) * a = b * a,

(12) ((a * b) * b) * b = a * b,

(13) a * b = b * a genau dann, wenn a = b, d. h. (G,*) ist antikommutativ,

(14) a * b = a impliziert a = 1,

(15) a * b = b genau dann, wenn b * a = a,

(16) a * b = 1 impliziert (c * a) * (c * b) = 1 und (b * c) * (a * c) = 1,

(17) (a * b) * ((b * c) * (a * c)) = 1.

Beweis: (4): a*(a*b) = ((a*b)*a)*(a*b) = a*b, wobei zweimal das Kontraktionsaxiom verwendet wurde.
(5): a*a = ((a*b)*a)*a =(a*(a*b))*a = (a*b)*(a*b), wobei der Reihe nach (1), (2) und (4) verwendet wurde.
(6): a*a = (a*b)*(a*b) = ((a*b)*b)*((a*b)*b) = ((b*a)*a)*((b*a)*a) = (b*a)*(b*a) = b*b für beliebige Elemente a, b unter mehrmaliger Verwendung von (5) und (2). Dieses eindeutig bestimmte Element a*a werde im folgenden 1 genannt.

(7): 1*a = (a*a)*a = a nach (1). a*1 = a*(a*a) = a*a = 1 nach (4).

(8): a*(b*a) = b*(a*a) = b*1 = 1 nach (3), (6) und (7).

(9): a*((a*b)*b) = (a*b)*(a*b) = 1 nach (3) und (6).

(10): (a*b)*(b*a) = b*((a*b)*a) = b*a nach (3) und (1).

(11): ((a*b)*b)*a = ((b*a)*a)*a = (a*(b*a))*(b*a) = 1*(b*a) = b*a( mit Hilfe von (2), nochmals (2), (8) und (7).

(12): ((a*b)*b)*b = (b*(a*b))*(a*b) = 1*(a*b) = a*b, mit Hilfe von (2), (8) und (7).

(13): Aus a*b = b*a folgt a = (a*b)*a = (b*a)*a = (a*b)*b = (b*a)*b = b mit (1) und (2). Die Umkehrung ist trivial.

(14): Aus a*b = a folgt a = (a*b)*a = a*a = 1 nach (1) und (6).

(15): Aus a*b = b folgt b*a = (a*b)*a = a nach (1). Die Umkehrung folgt analog.

(16): Es gilt zunächst b = 1 * b = (a * b) * b = (b * a) * a wegen (7) und (2). Hieraus folgt dann mit (3) (c * a) * (c * b) = (c * a) *(c * ((b * a) * a)) = (c * a) * ((b * a) * (c * a)) = 1, die letzte Gleichheit mit (8). Weiterhin gilt (b * c) * (a * c) = a * ((b * c) * c) = a * ((c * b) * b) = (c * b) * (a * b) = (c * b) * 1 = 1 wegen (3), (2) und (7).

(17): Mit (3) (2) und schließlich (8) folgt (a * b) * ((b * c) * (a * c)) = (a * b) * (a * ((b * c) * c)) = (a * b) * (a * ((c * b) * b)) = (a * b) * ((c * b) * (a * b)) = 1

In rechtsseitigen Implikationsalgebren wird das eindeutig bestimmte Element a * a zweckmäßigerweise mit 0 bezeichnet. Es gelten dann die zu (7) - (9), (14) und (17) dualen Gleichungen

(7') a * 0 = a und 0 * a = 0,

(8') (a * b) * a = 0,

(9') (a * (a * b)) * b = 0.

(14') a * b = b impliziert b = 0,

(17') ((a * b) * (a * c)) * (c * b) = 0,

und aus (13) folgt insbesondere

(13') a * b = 0 und b * a = 0 impliziert a = b.

Daher ist jede rechtsseitige Implikationsalgebra eine implikative BCK-Algebra. Da die Umkehrung offensichtlich ebenfalls gilt, sind die (rechtsseitigen) Implikationsalgebren genau die implikativen BCK-Algebren.


Beispiele für Implikationsalgebren sind:

  • Wie oben bereits angegeben, liefert jede Boolesche Algebra eine linksseitige und eine rechtsseitige Implikationsalgebra.

  • Der oben bewiesene Satz gestattet es, eine Implikationsalgebra anzugeben, die von den beiden Elementen a und b erzeugt wird. Sie besteht aus 6 Elementen und entsteht daher nicht aus einer Booleschen Algebra in der oben beschriebenen Weise.

    * 1 a b a*b b*a (a*b)*b
    1 1 a b a*b b*a (a*b)*b
    a 1 1 a*b a*b 1 1
    b 1 b*a 1 1 b*a 1
    a*b 1 a (a*b)*b 1 b*a (a*b)*b
    b*a 1 (a*b)*b b a*b 1 (a*b)*b
    (a*b)*b 1 b*a a*b a*b b*a 1