О многообразии алгебр отношений с операцией двойной цилиндрофикации

ЧЕБЫШЕВСКИЙ СБОРНИК

Том 15 Выпуск 1

УДК 501.1

О МНОГООБРАЗИИ АЛГЕБР ОТНОШЕНИЙ С ОПЕРАЦИЕЙ ДВОЙНОЙ ЦИЛИНДРОФИКАЦИИ

Д. А. Бредихин

Аннотация

Множество бинарных отношений, замкнутое относительно некоторой совокупности операций над ними, образует алгебру, называемую алгеброй отношений. Альфред Тарский был первым из математиков, кто начал рассматривать алгебры отношений с точки зрения теории универсальных алгебр. Одним из важных направлений в исследованиях алгебр отношений является изучение их свойств, выраженных в виде тождеств. Это приводит к необходимости изучения многообразий, порожденных различными классами алгебр отношений.

Для заданного множества О операций над бинарными отношениями обозначим через Е{О} класс алгебр, изоморфных алгебрам отношений с операциями из О. Пусть Уат{О} - многообразие, порожденное классом Е{О}.

Как правило, операции над отношениями задаются с помощь формул логики предикатов первого порядка. Такие операции называются логическими. Важным классом логических операций является класс диофанто-вых операций. Операция называется диофантовой (в другой терминологии

- примитивно-позитивной), если она может быть задана с помощью формулы, которая в своей предваренной нормальной форме содержит лишь операцию конъюнкции и кванторы существования. Диофантову операцию назовем атомарной, если она может быть задана с помощью формулы, которая в своей предваренной нормальной форме содержит лишь кванторы существования. Ясно, что такие формулы могут содержать лишь одну атомарную подформулу, и, следовательно, всякая атомарная операция является унарной. Существует девять атомарных диофантовых операций (исключая тождественную).

Сосредоточим свое внимание на диофантовой операции умножения отношений о и атомарной операции двойной цилиндрофикации, определяемых следующим образом. Для заданных отношений р и а на множестве и, положим

Р о а = {(и, V) : (З'^)(и, -ш) € р(,ш, V) € а}, У(р) = {(и, V) : (З'ш, г)(,ш, г) € р}.

В работе найден базис тождеств многообразия Var{o, V}: алгебра (A, , *) типа (2,1) тогда и только тогда принадлежит многообразию Var{o, V}, когда она удовлетворяет тождествам: (xy)z = x(yz), x** = x*, (x*)2 = x*, x*y* = y*x*, x*(xy)* = (xy)*y* = (xy)*,

(xy*z)* = x*y*z* = x*yz, xyz* = xyx*z*, x*yz = x*z*yz.

Ключевые слова: алгебра отношений, многообразия, базисы тождеств, операции цилиндрофикации.

ON VARIETIES OF ALGEBRAS OF RELATIONS WITH OPERATION OF DOUBLE CYLINDROFICATION

D. A. Bredikhin

Abstract

A set of binary relations closed with respect to some collection of operations on relations forms an algebra called an algebra of relations. The first mathematician who treated algebras of relations from the point of view of universal algebra was Alfred Tarski. In the investigation of algebras of relations, one of the most important directions is the study of those of their properties which can be expressed by identities. This leads us to the consideration of varieties generated by classes of algebras of relations.

For any set Q of operations on binary relations, let R{Q} denote the class of all algebras isomprphic to ones whose elements are binary relations and whose operations are members of Q. Let Var{Q} be the variety generated by R{Q}.

As a rule, operations on relations are defined by formulas of the first-order predicate calculus. These operations are called logical. One of the most important classes of logical operations on relations is the class of Diophantine operations (in other terminology - primitive-positive operations). An operation on relations is called Diophantine if it can be defined by a formula containing in its prenex normal form only existential quantifiers and conjunctions. A Diophantine operation is called atomic if it can be defined by a first order formula containing in its prenex normal form only existential quantifiers. It is clear that such formulas contain only one atomic subformula. Hence atomic operations are unary operations. There exist nine atomic operations (excepting identical).

We concentrate our attention on the Diophantine operation of relation product o and on the atomic operation of double cylindrification V that are defined as follows. For any relations p and a on U, put

P o a = {(u, v) : (3w)(u, w) € p(w, v) € a}, V(p) = {(u, v) : (3w, z)(w, z) € p}.

In the paper, the bases of identities for the variety Var{o, V} is found: an algebra (A, , *) of the type (2,1) belongs to the variety Var{o, V} if and only

if it satisfies the identities: (xy)z = x(yz), x** = x*, (x*)2 = x*, x*y* = y*x*, x*(xy)* = (xy)*y* = (xy)*, (xy*z)* = x*y*z* = x*yz, xyz* = xyx*z*,

x*z = x*z*yz.

Keywords: algebra of relations, varieties, basis of identities, operations cylindrification.

1. Введение

Под алгеброй отношений мы понимаем пару (Ф, П), где П - некоторая совокупность операций над отношениями и Ф - множество бинарных отношений, замкнутое относительно операций из П. Исследование операций над отношениями восходит к работам Де Моргана, Пирса, Фреге и Шредера. Тарским был предложен аксиоматический подход к изучению алгебр отношений [1,2]. Им был рассмотрен класс алгебр отношений, в число операций которых наряду с булевыми операциями входят операции умножения o и обращения -1 отношений. В настоящее время теория алгебр отношений является существенной составной алгебраической логики [3] и имеет многочисленные приложения в различных областях современной общей алгебры [4].

Как правило, операции над отношениями задаются с помощь формул логики предикатов. Такие операции называются логическими. Логические операции могут быть классифицированы по виду задающих их формул. Важным классом операций над отношениями является класс диофантовых операций. Операция называется диофантовой1 [5,6] (в другой терминологии - примитивнопозитивной [7]), если она может быть задана с помощью формулы, которая в своей предваренной нормальной форме содержит лишь операцию конъюнкции и кванторы существования. К числу диофантовых, в частности, относится упомянутые выше операции умножения и обращения отношений. Эквациональные и квазиэквациональные теории алгебр отношений с диофантовыми операциями описаны в [5,6,8].

Диофантову операцию назовем атомарной, если она может быть задана с помощью формулы, которая в своей предваренной нормальной форме содержит лишь кванторы существования. Ясно, что такие формулы могут содержать лишь одну атомарную подформулу, и, следовательно, всякая атомарная операция является унарной. Существует девять атомарных диофантовых операций (исключая тождественную). Это:

F1(p) = р-1 = {(u,v) : (v,u) € р} — операция обращения;

F2(p) = {(u,v) : (3w)(u,w) € р} и F3(p) = {(u,v) : (3w)(w,v) € p} - операции цилиндрофикации [9];

F4(p) = {(u,v) : (3w)(w,u) € p} и F5(p) = {(u,v) : (3w)(v,w) € p} - домино

операции [10,11];

1 Термин диофантова операция был предложен автору Л. Н. Шевриным.

^б(р) = |(м,^) : (и, и) € р} и ^7(р) = {(м,г>) : (г>,г>) € р} - операции рефлексивной цилиндрофикации [11];

^в(р) = |(м,^) : (Зад,г)(ад,г) € р} - операция двойной цилиндрофикации;

ВД = {(и,а) : (Зад)(ад,ад) € р} — операция двойной рефлексивной цилиндро-фикации.

Рассмотрение алгебр отношений в рамках аксиоматического подхода предполагает изучение их свойств, выразимых на языке логики предикатов первого порядка и, в частности, на языке тождеств. Это приводит к необходимости изучения многообразий, порожденных различными классами алгебр отношений.

Для заданного множества П операций над бинарными отношениями обозначим через Я{П} класс алгебр, изоморфных алгебрам отношений с операциями из П. Пусть Уаг{П} ) — многообразие, порожденное классом Я{П}.

Предметом нашего рассмотрения будут алгебры отношений с операцией умножения отношений и с одной из перечисленных выше атомарных диофанто-вых операций. Известно, что многообразие Уаг{о, -1} совпадает с классом всех инволютированных полугрупп [12]. Конечные базисы тождеств многообразий Уаг{о,^2} и Уаг{о,^з} найдены в [13]. Некоторые результаты в этом направлении, касающиеся алгебр отношений, упорядоченных отношением теоретикомножественного включения, можно найти в [14,15]. В настоящей работе находится базис тождеств многообразия Уаг{о, ^8}.

2. Формулировка основного результата

Сосредоточим свое внимание на операциях умножения отношений о и двойной цилиндрофикации, определяемых следующим образом:

р о а = {(и, V) : (Зад)(и, ад) € р(ад, V) € а},

У(р) = ^8(р) = {(и,г>) : (Зад,г)(ад,г) € р}.

Теорема 1. Алгебра (А, , *) типа (2,1) принадлежит многообразию Уаг{о, V} тогда и только тогда, когда она удовлетворяет тождествам:

* * * х — х

х*у* = у*х*

х*

/ * \ * * * * * *

* ^ ^ хуг = хух г

* ^ ^ х уг = х г уг

3. Доказательство теоремы

Разобьем доказательство теоремы на ряд последовательных шагов.

ШАГ 1. Доказательство теоремы основывается на результатах работы [8]. Приведем ряд определений и обозначений, необходимых для формулировки этого результата и используемых в дальнейшем изложении.

Всякая формула <p(z0, zi, ri,..., rm) логики предикатов первого порядка с равенством, содержащая m бинарных предикатных символов r1,..., rm и две свободные индивидуальные переменные zo, z1, определяет m-арную операцию Fv на множестве Re/(U) всех бинарных отношений, заданных на U:

F,(pi, . . . ,Pm) = {(u,v) е U X U : <p(u,V,pb . . . ,Pm)},

где <p(u, v,Ri,..., Rm) означает, что формула <p выполняется, если z0, z1 интерпретируются как u, v и r1,..., rm интерпретируются как отношения p1,..., pm из Re/(U).

Пусть N - множество всех натуральных чисел и [1, n] = {k е N : 1 ^ k ^ n}. Помеченным графом назовем пару (V, E), где V - конечное множество, называемое множеством вершин, и E С V X N X V - тернарное отношение. Тройку (u, k, v) е E будем называть ребром графа, идущим из вершины u в вершину v,

помеченным меткой k, и графически изображать следующим образом: u- — •v. Мы также будем говорить, что вершины u и v инцидентны ребру (u, k, v).

Под двухполюсником мы понимаем помеченный граф с парой выделенных вершин, то есть систему вида G = (V, E, in, out), где (V, E) - помеченный граф; in и out - две выделенные вершины (не обязательно различные), называемые входом и выходом двухполюсника соответственно.

Понятие изоморфизма помеченных графов и двухполюсников определяется естественным образом. В дальнейшем все графы будут рассматриваться с точностью до изоморфизма.

Пусть F = Fv - диофантова операция, задаваемая формулой <р. С этой операцией может быть ассоциирован двухполюсник G = G(<p), определяемый следующим образом [7]): G = (V, E, in, out), где V - множество всех индексов индивидуальных переменных, входящих в формулу <р; in = 0, out =1; (i, k, j) е E тогда и только тогда, когда атомарная формула r&(zi,zj-) входит в <р; если формула Zi = Zj входит в <р, то вершины i и j отождествляются.

Заметим, что графы, соответствующие операции умножения отношений о и операции двойной цилиндрофикации V, имеют следующий вид:

1 2 д. 1 4

in —У • —У •out ; in • • — • • out

Пусть G = (V, E, in, out) и Gk = (Vk, Ek, ink, outk) (k = 1,..., m)- двухполюсники с попарно непересекающимися множествами вершин. Назовем композицией этих двухполюсников новый двухполюсник G(G1,... , Gm), определяемый следующим образом [7]: возьмем двухполюсник G и заменим каждое его ребро (u,k,v) е E на двухполюсник G^, отождествляя при этом вершину in с вершиной u и вершину outfc с вершиной v.

Рассмотрим множество диофантовых операций над отношениями П = {F(^1,..., F^n}, и пусть A = (A, f1,..., fn) - универсальная алгебра соответствующего типа. Положим G1 = G(^1),..., Gn = G(^n).

Для всякого терма p алгебры A определим следующим индуктивным образом двухполюсник G(p) = (Vp, Ep, in(p), out(p)) :

1) если p = xk, то G(p) представляет собой двухполюсник вида in -— •out;

2) если p = fk(p1,... ,pm), то G(p) есть композиция Gk(G(p1),... , G(pm)).

Обозначим через pr(E) множество всех вершин помеченного графа, которые инцидентны хотя бы одному ребру. Пусть даны два помеченных графа (V1, E1) и (V2,E2). Отображение f : pr(E2) — pr(E1) называется гомоморфизмом E2 в E1, если (f (u), k, f (v)) е E1 для всякой тройки (u, k, v) е E2.

Пусть G1 = (V1, E1, in1, out1) и G2 = (V2, E2, in2, out2) - двухполюсники. Отображение f : V2 — V1 называется гомоморфизмом G2 в G1, если f(in2) = in1, f (out2) = out1 и (f (u), k, f (v)) е E1 для всякой тройки (u, k, v) е E2.

Мы будем писать E1 X E2 (G1 X G2), если существует гомоморфизм E2 в E1 ( G2 в G1), и E1 = E2 (G1 ^ G2), если E1 X E2 и E2 X E1 (G1 X G2 и G2 X G1).

Обозначим через Eq{H} эквациональную теорию класса Я{П}. Теперь мы готовы сформулировать основной результат работы [8]:

Тождество p = q принадлежит эквациональной теории Eq{H} тогда и только тогда, когда G(p) = G(q).

ШАГ 2. Заметим, что в том случае, когда алгебра (A, •, *) удовлетворяющих тождествам (1)-(8), она также удовлетворяет тождеству

Действительно, используя тождества (1-3) и (6), получаем (x*y)* = (x*x*y*)* = x**x*y** = x*x*y* = x*y*. Аналогично, (xy*)* = x*y*.

Обозначим через E эквациональную теорию алгебр, удовлетворяющих тождествам (1)-(8), и пусть £ - множество всех термов алгебры (A, •, *) типа (2,1). Назовем термы p1 и p2 эквивалентными p1 = p2, если тождество p1 = p2 принадлежит E. В том случае, когда эквивалентность термов устанавливается с

k

использованием тождества с номером (k), будем использовать запись p1 = p2. Ссылки на тождество ассоциативности (1) будут опускаться.

Пусть Л - множество слов над алфавитом {x1,... , xn,... }, © - пустое слово, и Л = Л U {©}.

Лемма 1. Для любого терма p е £ существуют такие а0, а1,..., ап (n ^ 0), что p = а0а1*... ап-1*ап, где а1,..., ап-1 е Л, а0, ап-1 е Л, и а0 = ©, если n = 0.

ДОКАЗАТЕЛЬСТВО. Доказательство проводится индукцией по определению терма. Очевидно, что утверждение леммы справедливо для p = Xk. Предполо-

жим, что оно справедливо для терма р, то есть р = о^о^*... ага-1*ага. Покажем его справедливость и для р*.

Если п = 0, то р* = а0*. Если п = 1, то (р)* = (а0а1*)* = а0*а1*. Предположим теперь, что п > 1.

9 9 9

Пусть а0 = ап = ©. Тогда р* = (а1*... «п-1*)* = а1*(а2*... «п-1*)* = ... =

2

«1*«2*... ап-1** = «1*... ап-1*.

Пусть «0 = © и ап = ©. Тогда р* = («0«1*... «п-1*)* = ^*(«1*... «п-1*)* =

«1*«2* ... «п-1*.

Пусть а0 = © и ап = ©. Тогда р* = (а1*... ап-1*ап)* =

((«1*«2* . . . «п-1*)*«п)* = («1*«2* . . . «п-1*)*«п* = «1*«2* . . . «п-1*«п*.

Пусть а0 = © и ап = ©. Тогда

р* = («0«1* . . . «п-1*«п)* = «0*(«1* . . . «п-1*)*«п* = «0*«1* . . . «п-1*«п*.

Далее, предположим, что утверждение справедливо для р1 и р2, то есть р1 = а0(а1)*... (ап-1)*ап и р2 = в0(в1)*... (вп-1)*вт. Покажем что оно справедливо и для р1р2.

Если т = 0, то р1р2 = («0«1*... «п-1*«п)в0 = «0«1*... ап-1*)(«п^0).

Если т = 1, то р1р2 = («0«1*... ап-1*ап)(в0^1*) = «0«1*... «п-1*(ап^0)в1*. Случаи п = 0 и п =1 рассматриваются аналогично.

Пусть теперь т, п > 1. Если ап = в0 = ©, то

р1р2 = «0«1* . . . «п-1*в1* . . . вп-1*вт.

Если «п = © или в0 = ©, то р1р2 = («0«1* . . . «п-1*ап)(в0^1* . . . вп-1*вт) = «0«1* ... ап-1*(апв0)в1*... вп-1*вт

Лемма 1 доказана.

Лемма 2. Пусть р = а0а1*... ап-1*ап и « = в1вв2 для некоторого к € [0,п] и некоторых във2 € Л, в € Л, причем п > 1, если к = 0. Тогда

>к >к >к Г) >к

р = «0«1 «2 ... «п в «п.

Доказательство. Если к = 0, то, согласно условию п > 1. Отсюда получаем

р = «0«1* . . . «п-1*«п = в1вв2«1* . . . «п-1*«п = в1вв2в*«1* . . . «п-1*«п =

«0в*«1* . . . «п-1*«п = «0«1* . . . «п-1*в*«п.

8

Если к = п, то р = «0«1*... «п-1*«п = «0«1*... «п-1*в1вв2 =

«0«1* . . . «п-1*в * в 1 в в2 = «0«1* . . . «п-1*в*«п.

5 5

Предположим, что к = 0,п. Тогда «* = (в1вв2)* = (в1вв2)*(вв2)* = (в1вв2)в*(вв2)* = (в1вв2)*в*(вв2)* = (в1вв2)*в* = «*в*. Следовательно, р =

«0«1* ...«й* ... «п-1*«п = «0«1* . . . «*в* . . . «п-1*«п =

«0«1 . . . . . . «п-1 в «п.

Лемма 2 доказана.

Шаг 3. Согласно определению, граф С(р) = (^, Ер, т(р), ом^(р)) для р € 5 может быть описан следующим образом.

Пусть р = « = ж^2 ... ж^п € Л. Тогда ^ = К = {^1,... ,^п+1>, Ер = Е« = {(^,4,^+1) : к € [1,п]}, и гп(р) = гп(«) = ^1, ом^(р) = ом^(«) = ^п+1:

гп

Пусть р = «*. Тогда = К* = К и {зд, гп+2}, Ер = Е«* = Е«, и гп(р) = т(«*) = г>0, ом^(р) = ом^(«*) = ^п+2:

т

Если р = « = ©, то положим по определению ^ = К = {^0}, Ер = Еа = 0, и гп(р) = гп(«) = ои£(р) = ом^(«) = г>0.

Пусть р = «0(«1)*... , («п1 )*«п и п > 1. Мы будем предполагать, что множества к0, Уа1*,... , Кп-1*, Уа„ попарно не пересекаются. Тогда

V, = У„0 и рг(Е„1*) и ... и рг(Еап_1*) и Кп, Ер = Еод и Е„1 и ... и Еап_1 и Е«п

и т(р) = гп(«0), ом^(р) = ом£(о!п). Заметим, что в этом случае двухполюсник С(р) имеет п +1 компоненту связности.

Лемма 3. Пусть Еа -< Е^. Тогда существуют в1,в2 € Л такие, что « = в1вв2. В частности, если Еа = Е^, то « = в.

Доказательство. Пусть « = ж^ ж^2 ... жг„, в = ж^2 ... ж^т и

V* = {г;ь ..., ^п+1}, V? = {V7!,..., ^+1}. Предположим, что /(^) = ад. Тогда легко видеть, что /(V.) = V* и ж^ = ж^, где £ = I + к — 1. Следовательно,

достаточно положить в1 = ж^1 . . . Ж^ (или в1 = ©, если I = 1) и в2 = . . . Жгп

(или в1 = ©, если I + т = п), где в = I и ад = I + т +1.

Лемма 3 доказана.

Шаг 4. Легко проверить, что операции о и V удовлетворяют тождествам (1)-(8). Следовательно, Е С Ед{о, V}. Таким образом, для доказательства теоремы достаточно показать, что Ед{о, V} С Е.

Предположим, что тождество р1 = р2 принадлежит эквациональной теории Ед{о, V}. Согласно сформулированному выше результату из [8] имеем С(р1) = С(р2), то есть существует гомоморфизмы / из С(р2) в С(р1) и д из С(р1) в С(р2). По лемме 1 мы можем предположить, что р1 = «0«1*... «п-1*«п и р2 = в0в1* . . .вт-1*вт.

Предположим, что «0 = ©. Тогда существует ребро, графа С(р1) идущее из гп(р1). Следовательно, существует ребро графа С(р2), идущее из д(*п(р1)) = *п(р2), откуда в0 = ©. Аналогично, условие в0 = © влечет «0 = ©.

Аналогично показываем, что «п = © влечет вш. = ©, и вт = © влечет

«п = ©.

Пусть n = 0, то есть p = а0. Тогда согласно определению в графе G(pi) существует путь из in(p1) в out(p1). Следовательно, в графе G(p2) также существует путь из g(in(p1)) = in(p2) в g(out(p1)) = out(p2), что возможно лишь в случае, если р2 = во, то есть m = 0. Таким образом, условие n = 0 влечет m = 0. Аналогично, m = 0 влечет n = 0.

Предположим, что а0 = © и в0 = ©. Так как f (in(p2)) = f (т(в0)) = in(p1) = in(ao) и g(in(p1)) = g(in(«0)) = in(p2) = in^), имеем f (V^) С Vao и g(Vao) С Vs0. Отсюда по лемме 3 получаем а0 = в0. Аналогично, если ап = © и вт = ©, то а„ = вт.

Предположим, что n,m ^ 1. Так как при гомоморфизме компонента связности графа переходит в компоненту связности, для любого к = 1,..., m — 1 имеем f (Vgfc) С Vafc/ для некоторого к' и для любого к = 1,..., n — 1 имеем g(V^fc) С Vsfc// для некоторого к!/. Отсюда по лемме 3 получаем ак/ = вквквд/ и вк// = аДака// для некоторых аД, аД/, вк, вк из TV. Следовательно, используя лемму 2, получаем p1 = а0а1*... ага-1*ага = а0а1*... ага-1*в1* • • • вт-1*ап =

в0а1* . . . а„_1*в1* . .. вт-1*вт ^ в0в1* ... вт-1*а1*... а„_1*вт =

в0в1* . . . вт_1*вт = Р2.

Таким образом, тождество p1 = p2 принадлежит Е, то есть Eq{o, V} С Е. Теорема доказана.

4. Заключение

Доказанная теорема дает еще один пример, иллюстрирующий эффективность полученного в работах [2,3,5] описания эквациональных теорий алгебр отношений с диофантовыми операциями.

СПИСОК ЦИТИРОВАННОЙ ЛИТЕРАТУРЫ

1. Tarski A. On the calculus of relations // J. Symbolic Logic. - 1941. - Vol. 6. -P. 73-89.

2. Tarski A. Some methodological results concerning the calculus of relations // J. Symbolic Logic. - 1953. - Vol. 18. - P. 188-189.

3. Andr^eka H., NVemeti I. and Sain, I. Algebraic Logic // In: Handbook of Philosophical Logic. Vol. 2, second edition, P.133-247, Kluwer Academic publishers (2001).

4. Schein B. M. Relation algebras and function semigroups // Semigroup Forum.

- 1970. - Vol. 1. - P. 1-62.

5. Бредихин Д. А. О квазитождествах алгебр отношений с диофантовыми операциями // Сибирский мат. журн. - 1997. - N 1. - С. 29-41.

6. Бредихин Д. А. Об алгебрах отношений с диофантовыми операциями // Доклады Российской Академии Наук. - 1998. - Т. 360. - С. 594-595.

7. Boner F., Poschel F. R. Clones of operations on binary relations // Contributions to general algebras. - 1991. - Vol. 7. - P. 50-70.

8. Бредихин Д. А. Эквациональная теория алгебр отношений с позитивными операциями // Известия вузов. Математика. - 1993. - N 3. - С. 23-30.

9. Henkin L., Monk J. D., Tarski A. Cylindric algeras. North-Holland, Amsterdam, 1971. 311 pp.

10. Kuhn S. The domino relations: flattening a two-dimensional logic // Journal of Philosophical Logic. - 1989. - Vol. 18. - P. 173-195.

11. Venema Y. Many-dimensional modal logic. Universiteit van Amsterdam, Amsterdam, 1989. 178 pp.

12. Schein B. M. Representation of involuted semigroups by binary relations // Fundamenta Math. - 1974. - Vol. 82. - P. 121-141.

13. Bredikhin D. A. On the varieties generated by partially ordered involuted semigroups of binary relations // Contributions to genera algebra. - 2001. -Vol. 13. - P. 70-77.

14. Andreka H., Bredikhin D. A. The equational theory of union-free algebras of relations // Alg. Univers. 1994. Vol. 33. P. 516-532 .

15. Bredikhin D. A. On varieties of partial ordered semigroups of relations with operations of cylindrification // Izv. Sarat. Univ. N.S. Ser. Math. Mech. Inform. 2009. Vol. 9. iss. 3 P. 3-7.

Саратовский государственный технический университет им. Гагарина Ю.А.

Поступило 7.02.2014