Marzena Łebedowska

Algebry relacji Tarskiego

Alfred Tarski wraz ze współautorami w latach 1947-1951 podał trzy różne definicje algebr 

relacji. Pierwsza pochodzi z pracy zatytułowanej "Problem reprezentacji w algebrach relacyjnych" 

napisanej   wspólnie   z   Jonssonem   w   1947   roku.  Algebra   relacji   zdefiniowana   została   tam   jako 

algebra Boole'a wraz z operacją konwersji x=x oraz operacjami binarnymi:

x = {<a, b>: <a  b> є x}

x = {<a, b>: <a, b> ȼ x}

x = {<a, b>: <b, a> є x}

x∙y = {<a, b>: <a, b> є x i <a, b> є y}

x+y = {<a, b>: <a, b> є x i <a, b> є y}

x;y = {<a,c>: dla pewnego b є U, <a, b> є x i <b, c> є y}

x†y = {<a,c>: dla każdego b є U, <a, b> є x  lub  <b, c> є y}

Przyjęto ponadto następujące zależności:

x;(y;z) = (x;y);z,

(x+y);z = x;z + y;z  i  x;(y+z) = x;y + x;z,

 (x+y) =x+y,  x;1'=x=1';x,

x;(x;y) ≤ y.

(Jedynie ostatnia nierówność nie wystąpiła wcześniej u Peirce'a, choć da się ją wyprowadzić z 

podanych przezeń praw rachunku relacji.)

Język aksjomatyzacji Tarskiego składał się z:

•

zmiennych oznaczających dowolne relacje

•

symboli relacji wyróżnionych: 0, 1, 1', 0'

•

sześciu operacji zaczerpniętych od Peirce'a: +, , ;, †,   oraz - 

•

symboli równości

•

spójników zdaniowych

Strukturą dla podanego języka musi być zatem algebra postaci:

A=  A, +,  ,  , 0, 1, ;, †,  , 1', 0'  . 

W  swej   drugiej   definicji   algebr   relacji  Tarski   przy  współpracy  z   Chinem  w  roku   1951 

określił wyraźnie typ algebry relacji:

A=  A, +,  , ;,   , gdzie   A, +, -  to algebra Boole'a.

Uznawane są tu:

x=x,

x;(y;z) = (x;y);z,

(x+y);z = x;z + y;z  i  x;(y+z) = x;y + x;z,

(x+y) =x+y,

(x;y) =y;x,

x;(x;y) ≤ y.

Operacje:   , 0, 1 uzyskać można z + i   . Nie występuje tu 1' jako element wyróżniony. 

Wymagany jest natomiast egzystencjalny aksjomat stwierdzający, że dla pewnego uєA  x;u=x dla 

wszystkich  xєA.

W roku 1951 Tarski wraz z Jonssonem po raz kolejny podjęli próbę zdefiniowania algebr 

relacji:

A=  A, +, 0, , 1, ;,  , 1'  , gdzie   A, +, -  jest algebrą boolowską.

Uznawane są:

x;(y;z) = (x;y);z,

x;1' = x = 1';x,

oraz następująca wersja Teorii K Augusta De Morgana:

x;y z=0 <-> x;z y=0 <-> z;y x=0.

Jak widać  algebry Tarskiego  stopniowo  ewoluowały.   Ostatecznie  przyjął  on następującą 

definicję:

A=  A, +, 0, , 1, ;,  , 1'  , gdzie   A, +, -  jest algebrą Boole'a.

Uznawane są:

x=x,

x;(y;z) = (x;y);z,

(x+y);z = x;z + y;z  i  x;(y+z) = x;y + x;z,

(x+y) =x+y,

(x;y) =y;x,

x;(x;y) ≤ y,

x;1' = x,

x+y=y+x,

x+(y+z)=(x+y)+z,

x+y +x+y=x.

Bibliografia:

Roger D. Maddux, „The Orgin of Relation Algebras in the Development and Axiomatization of the 

Calculus of Relations”