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”