Algebras of quasiary and of bi-quasiary relations
The notion of quasiary relation which can be considered generalization of the notion of traditional n-ary relation is proposed. A number of algebras of quasiary relations is built and investigated. Alongside with conventional operations of union, intersection, and complement, special nominative oper...
Gespeichert in:
| Datum: | 2018 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
Інститут програмних систем НАН України
2018
|
| Schlagworte: | |
| Online Zugang: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/165 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Problems in programming |
Institution
Problems in programming| id |
pp_isofts_kiev_ua-article-165 |
|---|---|
| record_format |
ojs |
| resource_txt_mv |
ppisoftskievua/16/b177a24aa2159a96b071bcceb8fe6416.pdf |
| spelling |
pp_isofts_kiev_ua-article-1652021-01-25T15:28:40Z Algebras of quasiary and of bi-quasiary relations Алгебры квазиарных и би-квазиарных реляций Алгебри квазіарних та бі-квазіарних реляцій Nikitchenko, M.S. Shkilniak, S.S. algebra; logic; relation; isomorphism; quasiary predicate УДК 004.42:510.69 алгебра; логика; изоморфизм; реляция; квазиарный предикат УДК 004.42:510.69 алгебра; логіка; ізоморфізм; реляція; квазіарний предикат УДК 004.42:510.69 The notion of quasiary relation which can be considered generalization of the notion of traditional n-ary relation is proposed. A number of algebras of quasiary relations is built and investigated. Alongside with conventional operations of union, intersection, and complement, special nominative operations of renomi-nation and quantification are defined for quasiary relations. The isomorphism between the algebra of quasiary relations and the first-order algebra of total single-valued quasiary predicates is proved. Al-gebras of bi-quasiary relations defined over sets of pairs of quasiary relations are built. The isomorphism between algebras of bi-quasiary relations and alge-bras of quasiary predicates is proved. The following subclasses of algebras of bi-quasiary relations are specified: alge-bras of partial single-valued (functional), total, total many-valued bi-quasiary relations. For all defined subclasses their counterparts of the classes of algebras of quasiary predicates are described. Also subalgebras of the algebra of bi-quasiary relations induced by upward closedness and downward closedness are investigated.Prombles in programming 2016; 1: 17-28 Предложено понятие квазиарной реляции (отношения), введены операции над такими реляциями, описаны ал-гебры квазиарных реляций. Доказан изоморфизм алгебры квазиарных реляций и первопорядковой алгебры тотальных однозначных квазиарных предикатов. Построены алгебры биквазиарных реляций, заданные на множествах пар квазиарных реляций. Определены различные подклассы таких алгебр, иссследованы их связи с алгебрами частичных однозначных, тотальных неоднозначных, частичных неоднозначных, монотонных, антитонных квазиарных предикатов.Prombles in programming 2016; 1: 17-28 Запропоновано поняття квазіарної реляції (відношення), введено операції над такими реляціями, описано алгебри квазіарних реляцій. Доведено ізоморфізм алгебри квазіарних реляцій та першопорядкової алгебри тотальних однозначних квазіарних предикатів. Побудовано алгебри бі-квазіарних реляцій, задані на множинах пар квазіарних реляцій. Визначено різні підкласи таких алгебр та досліджено їх зв’язки з алгебрами часткових однозначних, тотальних неоднозначних, часткових неоднозначних, монотонних, антитонних квазіарних предикатів.Prombles in programming 2016; 1: 17-28 Інститут програмних систем НАН України 2018-11-21 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/165 10.15407/pp2016.01.017 PROBLEMS IN PROGRAMMING; No 1 (2016); 17-28 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 1 (2016); 17-28 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 1 (2016); 17-28 1727-4907 10.15407/pp2016.01 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/165/159 Copyright (c) 2017 ПРОБЛЕМИ ПРОГРАМУВАННЯ |
| institution |
Problems in programming |
| baseUrl_str |
https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| datestamp_date |
2021-01-25T15:28:40Z |
| collection |
OJS |
| language |
Ukrainian |
| topic |
algebra logic relation isomorphism quasiary predicate УДК 004.42:510.69 |
| spellingShingle |
algebra logic relation isomorphism quasiary predicate УДК 004.42:510.69 Nikitchenko, M.S. Shkilniak, S.S. Algebras of quasiary and of bi-quasiary relations |
| topic_facet |
algebra logic relation isomorphism quasiary predicate УДК 004.42:510.69 алгебра логика изоморфизм реляция квазиарный предикат УДК 004.42:510.69 алгебра логіка ізоморфізм реляція квазіарний предикат УДК 004.42:510.69 |
| format |
Article |
| author |
Nikitchenko, M.S. Shkilniak, S.S. |
| author_facet |
Nikitchenko, M.S. Shkilniak, S.S. |
| author_sort |
Nikitchenko, M.S. |
| title |
Algebras of quasiary and of bi-quasiary relations |
| title_short |
Algebras of quasiary and of bi-quasiary relations |
| title_full |
Algebras of quasiary and of bi-quasiary relations |
| title_fullStr |
Algebras of quasiary and of bi-quasiary relations |
| title_full_unstemmed |
Algebras of quasiary and of bi-quasiary relations |
| title_sort |
algebras of quasiary and of bi-quasiary relations |
| title_alt |
Алгебры квазиарных и би-квазиарных реляций Алгебри квазіарних та бі-квазіарних реляцій |
| description |
The notion of quasiary relation which can be considered generalization of the notion of traditional n-ary relation is proposed. A number of algebras of quasiary relations is built and investigated. Alongside with conventional operations of union, intersection, and complement, special nominative operations of renomi-nation and quantification are defined for quasiary relations. The isomorphism between the algebra of quasiary relations and the first-order algebra of total single-valued quasiary predicates is proved. Al-gebras of bi-quasiary relations defined over sets of pairs of quasiary relations are built. The isomorphism between algebras of bi-quasiary relations and alge-bras of quasiary predicates is proved. The following subclasses of algebras of bi-quasiary relations are specified: alge-bras of partial single-valued (functional), total, total many-valued bi-quasiary relations. For all defined subclasses their counterparts of the classes of algebras of quasiary predicates are described. Also subalgebras of the algebra of bi-quasiary relations induced by upward closedness and downward closedness are investigated.Prombles in programming 2016; 1: 17-28 |
| publisher |
Інститут програмних систем НАН України |
| publishDate |
2018 |
| url |
https://pp.isofts.kiev.ua/index.php/ojs1/article/view/165 |
| work_keys_str_mv |
AT nikitchenkoms algebrasofquasiaryandofbiquasiaryrelations AT shkilniakss algebrasofquasiaryandofbiquasiaryrelations AT nikitchenkoms algebrykvaziarnyhibikvaziarnyhrelâcij AT shkilniakss algebrykvaziarnyhibikvaziarnyhrelâcij AT nikitchenkoms algebrikvazíarnihtabíkvazíarnihrelâcíj AT shkilniakss algebrikvazíarnihtabíkvazíarnihrelâcíj |
| first_indexed |
2025-07-17T09:38:38Z |
| last_indexed |
2025-07-17T09:38:38Z |
| _version_ |
1838408962474508288 |
| fulltext |
Теоретичні та методологічні основи програмування
© М.С. Нікітченко, C.С. Шкільняк, 2016
ISSN 1727-4907. Проблеми програмування. 2016. № 1 17
УДК 004.42:510.69
М.С. Нікітченко, С.С. Шкільняк
АЛГЕБРИ КВАЗІАРНИХ ТА БІ-КВАЗІАРНИХ РЕЛЯЦІЙ
Запропоновано поняття квазіарної реляції (відношення), введено операції над такими реляціями, опи-
сано алгебри квазіарних реляцій. Доведено ізоморфізм алгебри квазіарних реляцій та першопорядкової
алгебри тотальних однозначних квазіарних предикатів. Побудовано алгебри бі-квазіарних реляцій, за-
дані на множинах пар квазіарних реляцій. Визначено різні підкласи таких алгебр та досліджено їх
зв’язки з алгебрами часткових однозначних, тотальних неоднозначних, часткових неоднозначних, мо-
нотонних, антитонних квазіарних предикатів.
Ключові слова: алгебра, логіка, ізоморфізм, реляція, квазіарний предикат.
Вступ
Поняття реляції (відношення) нале-
жить до найважливіших понять математи-
ки. Під n-арним відношенням зазвичай ро-
зуміють [1] множину кортежів довжини n.
Водночас низка задач інформатики та про-
грамування вимагають узагальнення цього
поняття.
Скінченне n-арне відношення мож-
на розглядати як таблицю, що має n стовп-
чиків. Рядок таблиці (n-ка базових значень
даних) – це елемент відношення. При цьо-
му в деяких випадках заповненими можуть
бути не всі клітинки таблиці. Наприклад,
якщо розглядати екзаменаційну відомість
як таблицю, то не всі її клітинки заповню-
ються під час іспиту (зокрема, через неяв-
ку студента на іспит).
Формально таку частково заповнену
таблицю можна задати наступним чином.
Нехай V – множина атрибутів (предметних
імен), A – множина предметних значень.
Часткову функцію із V в A назвемо номіна-
тивною (іменною) множиною. Клас всіх
таких множин позначаємо
V
A. Довільну
підмножину R
V
A назвемо квазіарною
реляцією. Тепер номінативна множина, що
входить у реляцію R, може розглядатися як
частково заповнений рядок таблиці.
Мета даної роботи – це побудова та
вивчення алгебр квазіарних реляцій (від-
ношень) та дослідження їх зв’язків із алге-
брами квазіарних предикатів. Доведено
ізоморфізм алгебри квазіарних відношень
та першопорядкових алгебр тотальних од-
нозначних квазіарних предикатів. Побудо-
вано алгебри бі-квазіарних реляцій, задані
на множинах пар квазіарних реляцій.
Визначено різні підкласи таких
алгебр, встановлено їх зв’язки з алгебра-
ми часткових однозначних, тотальних не-
однозначних, часткових неоднозначних,
монотонних, антитонних квазіарних пре-
дикатів.
Поняття, які тут не визначаються,
тлумачимо в сенсі [2, 3]. Для полегшення
читання наведемо необхідні для подаль-
шого викладу визначення.
1. Іменні множини та квазіарні
предикати
V-іменна множина (V-ІМ) над A – це
однозначна функція вигляду
:
V A. По-
даємо V-ІМ у вигляді [v1a1,...,vnan,...],
де vіV, aіA, vі vj при і j.
Клас всіх V-ІМ над A позначимо
AV .
Вводимо функцію asn :
VV A 2
так:
asn(d) = {vV | vad для деякого a A }.
Операцію ||–х видалення компоненти
з іменем х та операцію накладки задамо
таким чином:
d ||–х = [vad | v х];
= [va | vasn()].
Операцію AA VVvv
xx
n
n
:r
,...,
,...,
1
1
реномі-
нації задаємо так:
)](),...,([)(r 11
,...,
,...,
1
1
nn
vv
xx
xdvxdvddn
n
.
Теоретичні та методологічні основи програмування
18
Замість nyy ,...,1 пишемо також y .
Операцію реномінації продовжуємо
на множини ІМ:
ALLddL Vv
x
v
x де },|)(r{)(r .
Введемо відношення x рівності з
точністю до компоненти з іменем х:
21 dd x , якщо
xx
dd
21 .
Послідовне застосування двох опе-
рацій r
v
x (зовнішня) та r
u
y (внутрішня) мо-
жна подати у вигляді однієї операції рено-
мінації, яку назвемо згорткою операцій r
v
x
та r
u
y і позначатимемо r
v
x
u
y .
Нехай маємо послідовне застосу-
вання операцій реномінації kп
kп
uuvv
zzss
,...,,,...
,...,,,...,
11
11
r
та mn
mn
wwvv
yyxx
,...,,,...,
,...,,,...,
11
11
r , де {w1,...,wm}
{u1,...,uk} = . Тоді для кожного d AV
маємо:
mn
mn
wwvv
yyxx
,...,,,...,
,...,,,...,
11
11
r )(
,...,,,...
,...,,,...,
11
11
dkп
kп
uuvv
zzss
))(r(r
,...,,,...
,...,,,...,
,...,,,...,
,...,,,...,
11
11
11
11
dkп
kп
mn
mn
uuvv
zzss
wwvv
yyxx
)(r
,...,,,...,,,...,
,...,,,...,,,...,
111
111
dkmn
kmn
uuwwvv
zzbbaa
,
де кожні ia та jb задаються так:
1 1, якщо { ,... , ,..., },
, якщо для деякого ,
, якщо для деякого ;
i i п k
i l i l l
l i l l
x x v v u u
a s x v v
z x u u
1 1, якщо { ,... , ,..., },
, якщо для деякого ,
, якщо для деякого .
j j п k
j l j l l
l j l l
y y v v u u
b s y v v
z y u u
Під V-квазіарним предикатом на
множині А, або V-А-квазіарним предика-
том, розуміємо довільну часткову неод-
нозначну функцію вигляду P : AV
{T, F}. Тут {T, F} – множина істин-
нісних значень.
Для V-А-квазіарного предиката Р
задаємо області істинності та хибності:
T(P) = {d AV | TP(d)};
F(P) = {d AV | FP(d)}.
Ми трактуємо часткові неоднозначні
квазіарні предикати як відношення між
AV та множиною істиннісних значень
{T, F}. Назвемо їх предикатами реляційно-
го типу, або R-предикатами. Вони форма-
лізують найпростіше уточнення поняття
часткового неоднозначного предиката.
Клас V-A-квазіарних R-предикатів позна-
чимо V
APrR .
Ім’я zV (строго) неістотне для
предиката P, якщо для всіх d1, d2 AV та-
ких, що d1 =–z d2, маємо P(d1) = P(d2).
V-A-квазіарний предикат P:
– однозначний, якщо T(P)F(P) = ;
– тотальний, якщо T(P)F(P) = AV ;
– всюди невизначений, якщо
T(P) = та F(P) = ;
– тотально насичений, якщо
T(P) = AV та F(P) = AV .
Всюди невизначений предикат поз-
начаємо як , тотально насичений – як .
Повний образ предиката P на d поз-
начаємо P[d].
Предикат P :
AV {T, F} монотон-
ний, якщо d h P[d] P[h].
Для однозначних предикатів моно-
тонність стає еквітонністю.
Однозначний предикат P еквітон-
ний, якщо з умови P(d) та d d' випливає
P(d') = P(d).
Для монотонних предикатів маємо:
нехай d h
dT(P) hT(P) та dF(P) hF(P).
Предикат P : AV
{T, F} анти-
тонний, якщо d h P[d] P[h].
Для антитонних предикатів маємо:
нехай d h
hT(P) dT(P) та hF(P) dF(P).
Частково впорядкована [4] множина
R із відношенням порядку називається:
– замкненою вгору, якщо із dR ви-
пливає: hR для всіх h таких, що d h;
Теоретичні та методологічні основи програмування
19
– замкненою вниз, якщо із dR ви-
пливає: hR для всіх h таких, що h d.
У наc – це відношення .
Таким чином.
Твердження 1. Нехай V-А-квазіар-
ний предикат P монотонний, тоді множини
T(P) і F(P) замкнені вгору.
Твердження 2. Нехай V-А-квазіар-
ний предикат P антитонний, тоді множини
T(P) і F(P) замкнені вниз.
Часткові однозначні квазіарні пре-
дикати називатимемо P-предикатами, то-
тальні квазіарні предикати – T-предиката-
ми, тотальні однозначні квазіарні предика-
ти – TS-предикатами. Монотонні R-преди-
кати, антитонні R-предикати, еквітонні
P-предикати, антитоннi T-предикати на-
звемо відповідно RM-предикатами, RА-
предикатами, PE-предикатами, TА-преди-
катами.
Класи V-A-квазіарних P-предикатів,
T-предикатів, TS-предикатів відповідно по-
значимо V
APrP , V
APrT , V
APrTS . Класи V-A-
квазіарних RM-предикатів, RА-предикатів,
PE-предикатів, TА-предикатів відповідно
позначимо
V
A
V
A
V
A
V
A PrTAPrTAPrPEPrRM .
V-A-квазіарний предикат P
~
назвемо
дуальним до V-A-квазіарного предиката P,
якщо )()
~
( );()
~
( PTPFPFPT .
Тут – теоретико-множинна опе-
рація доповнення.
Прикладом пари взаємно дуальних
предикатів є та .
Задамо відображення дуалізації
V
A
V
A PrRPrR : таким чином:
PP
~
)( для кожного V
APrRP .
Це означає:
).())(( );())(( PTPFPFPT
Відображення дуалізації інволюти-
вне: PP ))(( для кожного V
APrRP .
Теорема 1. Маємо властивості:
Q – P-предикат Q
~
– T-предикат;
Q – RM-предикат Q
~
– RA-предикат;
Q – PE-предикат Q – TA-предикат;
Q – TS-предикат Q – TS-предикат.
Теорема 2. Маємо властивості:
;( ,( V
A
V
A
V
A
V
A PrPPrTPrTPrP
;( ,( V
A
V
A
V
A
V
A PrPEPrTAPrTAPrPE
;( ,( V
A
V
A
V
A
V
A PrRMPrRAPrRAPrRM
}{})({ },{})({ ;
V
A
V
A
V
A
V
A PrTSPrTSPrRPrR ( ,( .
2. Композиційні алгебри
квазіарних предикатів
На пропозиційному рівні компози-
ції фактично працюють лише з виробле-
ними предикатами істиннісними значен-
нями. Такі композиції називають логiч-
ними зв’язками. Основними логічними
зв’язками є та . Ми будемо викорис-
товувати , , &. Наведемо визначення
цих зв’язок через області істинності та
хибності відповідних предикатів.
Предикати (P), (P, Q), &(P, Q)
традиційно позначаємо P, PQ, P&Q.
Вони задаються так:
T(P) = F(P);
F(P) = T(P);
T(PQ) = T(P)T(Q);
F(PQ) = F(P)F(Q);
T(P&Q) = T(P)T(Q);
F(P&Q) = F(P)F(Q).
Композиції та назвемо базо-
вими пропозиційними композиціями.
Композиції &, , є похідними,
вони виражаються через та :
P&Q = (P Q);
PQ = PQ;
PQ = (PQ)&(QP).
На рівні чистих першопорядкових
логік (кванторному рівні) до логічних зв’я-
зок додаємо 1-арні параметричні компози-
Теоретичні та методологічні основи програмування
20
ції реномінації v
xR та квантифікації x,
x.
Композиція v
xR задається так.
Для кожного d
V
А маємо
))(r())((R dPdP v
x
v
x .
Композицію v
xR можна визначити
через області істинності та хибності відпо-
відного предиката:
)}()(r|{))((R PTddPT v
x
v
x
))(()(r 1
PTv
x
;
)}()(r|{))((R PFddPF v
x
v
x
))(()(r 1
PFv
x
.
Композиції x і x задамо через об-
ласті істинності та хибності предикатів
xP і xP:
T(xP) = {d
V
A | TР[dxa] для
деякого aA};
F(xP) = {d
V
A | FР[dxa] для
всіх aA};
T(xP) = {d
V
A | TР[dxa] для
всіх aA};
F(xP) = {d
V
A | FР[dxa] для
деякого aA}.
Композиції , , ,Rv
x x – це ба-
зові композиції логік кванторного рівня.
Композиція х є похідною:
хР = хР.
Результатом послідовного виконання
двох композицій w
yR (застосовується пер-
шою) та v
xR (застосовується другою) є їх
згортка – композиція реномінації w
y
v
x R .
Вона визначається так: для кожного d
V
A
w
y
w
y
v
x PdP r())((R ))(dv
x .
Основні властивості композицій ре-
номінації:
– )(R)(R ,
, PP v
x
vz
xz ;
– )(R)(R PP v
x
v
x ;
– )(R)(R)(R QPQP v
x
v
x
v
x ;
– )(R&)(R)&(R QPQP v
x
v
x
v
x ;
– )(R)(R ,
, PP v
x
vz
xy за такої умови:
zV неістотне для Р.
Традиційні властивості x та x:
– xуР = ухР; xуР = ухР;
– хР = хР; хР = хР;
– xхР = хР; xхР = хР;
– xхР = хР; xхР = хР;
– хР хQ = х (РQ);
– хР &xQ = х (Р&Q).
Залучаючи до розгляду реномінації,
маємо властивості:
– )(R)(R ,
, xPxP u
v
xu
yv ;
зокрема: xPxPx
y )(R ;
– )(R)(R ,
, xPxP u
v
xu
yv ;
зокрема: xPxPx
y )(R ;
– ),(R PzyP y
z z неістотне для P;
– ),(R PzyP y
z z неістотне для P;
– ),(R)(R PyyP v
x
v
x де },{ xvy ;
– ),(R)(R PyyP v
x
v
x де },{ xvy ;
– ),(R)(R PzyP y
z
v
x
v
x де z неіс-
тотне для P, },{ xvz ;
– ),(R)(R PzyP y
z
v
x
v
x де z неіс-
тотне для P, },{ xvz .
Теорема 3. Композиції , , &,
,Rv
x x, x зберігають однозначність, то-
тальність, монотонність, антитонність ква-
зіарних предикатів.
Наслідок 1. Класи P-предикатів, T-
предикатів, TS-предикатів, RM-предикатів,
RА-предикатів, PE-предикатів, TА-преди-
катів замкнені відносно композицій , ,
&, ,Rv
x x, x.
Теоретичні та методологічні основи програмування
21
Алгебру }),R,,{,( xPr v
x
V
A , де
V
APr – певний клас V-A-квазіарних преди-
катів, назвемо чистою першопорядковою
композиційною предикатною алгеброю
(алгеброю квазіарних предикатів).
Необхідна умова, щоб клас квазіар-
них предикатів V
APr утворив алгебру – за-
мкненість щодо операцій алгебри, тобто
замкненість класу V
APr щодо композицій
, , ,Rv
x x.
Надалі будемо розглядати компози-
ційні предикатні алгебри із розширеною
множиною базових композицій
},,R,&,,{ xxCQ v
x .
В загальному випадку отримуємо
алгебру ),( CQPrRQR V
A
V
A V-A-квазіарних
R-предикатів.
Згідно наслідку 1, в алгебрі V
AQR
можна виділити такі підалгебри:
– алгебра P-предикатів
),( CQPrPQP V
A
V
A ,
– алгебра T-предикатів
),( CQPrTQT V
A
V
A ,
– алгебра RM-предикатів
),( CQPrRMQRM V
A
V
A ,
– алгебра RА-предикатів
),( CQPrRAQRA V
A
V
A ,
– алгебра PE-предикатів
),( CQPrPEQPE V
A
V
A ,
– алгебра TА-предикатів
),( CQPrTAQTA V
A
V
A ,
– алгебра TS-предикатів
),( CQPrTSQTS V
A
V
A .
Можна також виділити сингулярні
підалгебри з 1-елементним носієм
V-A )},({ CQ , V-A = )},({ CQ .
Предикатні алгебри ),Pr( 1 CQ та
),Pr( 2 CQ дуальні, якщо ( 1Pr ) = 2Pr .
Тут – відображення дуалізації.
Зрозуміло, що тоді ( 2Pr ) = 1Pr .
Визначені вище предикатні алгебри
утворюють такі дуальні пари:
V
AQP та V
AQT , V
AQPE та V
AQTA ,
V
AQRM та V
AQRA , V-A та V-A .
Алгебри V
AQR та V
AQTS є автодуа-
льними.
3. Квазіарні реляції
Під квазіарною реляцією будемо
розуміти [5] довільну L
V
A.
Квазіарні реляції можна трактувати
як області істинності тотальних однознач-
них квазіарних предикатів. Дуальне трак-
тування квазіарних реляцій – це області
хибності таких предикатів.
Для квазіарних реляцій як множин
ІМ вводимо традиційні операції: об’єднан-
ня , перетин , доповнення .
При трактуванні квазіарних реля-
цій як областей істинності тотальних од-
нозначних квазіарних предикатів компо-
зиціям , , & для предикатів відповіда-
ють операції , , для областей істин-
ності відповідних предикатів. При дуаль-
ному трактуванні квазіарних реляцій як
областей хибності зазначених предикатів
композиціям , , & для предикатів від-
повідають операції , , для їх облас-
тей хибності.
Для квазіарних реляцій вводимо та-
кож спеціальні номінативні операції рено-
мінації та квантифікації.
Операція реномінації v
x індукова-
на відповідною операцією реномінації ІМ
:r
v
x
)()(r})(r|{)( 1
LLdAdL v
x
v
x
Vv
x
.
Операції квантифікації x та x ін-
дуковані відповідними композиціями ква-
зіарних предикатів x та x. Задамо їх так:
x(L) = { d
V
A | d xaL для деякого aA};
x(L) = { d
V
A | d xaL для всіх aA}.
При трактуванні L як області істинності
деякого предиката P квазіреляції x(L) та
x(L) трактуємо як області істинності пре-
дикатів xP та xP. При дуальному трак-
туванні L як області хибності предиката P
Теоретичні та методологічні основи програмування
22
трактуємо x(L) та x(L) як області хибно-
сті предикатів xP та xP.
Ім’я zV неістотне для квазіарної
реляції L, якщо для всіх 1d , Ad V2 таких,
що 1d =–z 2d , маємо: Ld 1 Ld 2 .
Послідовне застосування двох опе-
рацій реномінації можна подати у вигляді
однієї, яку назвемо їх згорткою.
Згортка операцій w
y (застосовуєть-
ся першою) та v
x (застосовується другою)
– це операція реномінації, яку позначаємо
.v
x
w
y Ця операція визначається так:
w
y
v
x
w
y
w
y
v
x LL r()())(( )() 1 Lv
x
.
В класі квазіарних реляцій можна
виділити підкласи замкнених вгору квазіа-
рних реляцій та замкнених вниз квазіарних
реляцій.
Твердження 3. Нехай V-А-квазіар-
ний предикат P монотонний, тоді множини
T(P) і F(P) замкнені вгору.
Твердження 4. Нехай V-А-квазіар-
ний предикат P антитонний, тоді множини
T(P) і F(P) замкнені вниз.
Розглянемо властивості квазіарних
реляцій.
Для операцій , , маємо тради-
ційні властивості булевої алгебри множин.
1. Комутативність та :
LM = ML;
LM = ML.
2. Асоціативність та :
(LM)R = L(MR);
(LM)R = L(MR).
3. Дистрибутивність відносно
та відносно :
(LM)R = (LR)(MR);
(LM)R = (LR)(MR).
4. Зняття подвійного заперечення:
L = L.
5. Ідемпотентність та :
L = LL;
L = LL.
6. Закони де Моргана:
(LM) = (M)(L);
(LM) = (M)(L).
Можна вважати базовими операції
та , тоді операція є похідною:
LM = ((M)(L)).
Властивості номінативних операцій
реномінації та квантифікації для квазіар-
них реляцій індуковані відповідними влас-
тивостями квазіарних предикатів.
Для операції реномінації маємо:
– )()(,
, LL v
x
vz
xz ;
– (v
x )L )(Lv
x ;
– )()()( MLML v
x
v
x
v
x ;
– )()()( MLML v
x
v
x
v
x ;
– )()(,
, LL v
x
vz
xy за умови, що zV
неістотне для L.
Для операцій квантифікації маємо:
– x(у(L)) = у(х(L));
– x(у(L)) = у(х(L));
– (х(L)) = х((L));
– (х(L)) = х((L));
– x(x(L)) = x(L);
– x(x(L)) = x(L);
– x(x(L)) = x(L);
– x(x(L)) = x(L);
– х(L)х(M) = х(LM);
– х(L)х(M) = х(LM).
Можна вважати базовою операцію
x, тоді операція х є похідною:
х(L) = х((L)).
Для операції реномінації маємо:
– )),(()( LyLy y
z
якщо z неістотне для L;
– )),(()( LyLy y
z
якщо z неістотне для L;
Теоретичні та методологічні основи програмування
23
– ))(())((,
, LxLx u
v
xu
yv ;
зокрема: )())(( LxLxx
y ;
– ))(())((,
, LxLx u
v
xu
yv ;
зокрема: )())(( LxLxx
y ;
– )),(())(( LyLy v
x
v
x
якщо },{ xvy ;
– )),(())(( LyLy v
x
v
x
якщо },{ xvy ;
– )),(())(( LzLy y
z
v
x
v
x
якщо z неістотне для L, },{ xvz ;
– )),(())(( LzLy y
z
v
x
v
x
якщо z неістотне для L, },{ xvz .
4. Алгебри квазіарних реляцій
Носієм алгебри квазіарних реляцій є
множина квазіарних реляцій, а множина
базових операцій – це {, , ,, v
x x, x},
яку позначимо OQR. Зауважимо, що можна
брати мінімальну множину базових опера-
цій {, , , v
x x}, кожна з яких незалежна
від інших, проте для зручності та виразно-
сті використовуємо саме OQR.
Алгебра квазіарних реляцій – це
об’єкт ) ;2( QR
A
QR OA
V
.
Теорема 4. Алгебра AQR ізоморфна
алгебрі TS-предикатів ).,( CQPrTSQTS V
A
V
A
Можна задати два природних ізо-
морфізми алгебри V
AQTS на алгебру AQR :
AV
AT
V
PrTS 2: , його задаємо
умовою T(P) = T(P);
AV
AF
V
PrTS 2: , його задаємо
умовою F(P) = F(P).
Відображення T зіставляє кожно-
му предикату його область істинності, а
відображення F – його область хибності.
Зауважимо, що для тотального од-
нозначного предиката P його області іс-
тинності та хибності пов’язані так:
)()( );()( PTPFPFPT .
Для T виконуються умови збере-
ження значення базових операцій:
T(¬P) = T(¬P) = F(P) = T(P) = T(P),
T(PQ) = T(PQ) = T(P)T(Q) =
= T(P) T(Q),
T(P&Q) = T(P&Q) = T(P)T(Q) =
= T(P) T(Q),
T ))((R Pv
x = ))((R PT v
x ))(()(r 1
PTv
x
=
= v
x (T(P)) = v
x (T(P)),
T(хР) = T(хР) = x(T(Р)) = x(T(Р)),
T(хР) = T(хР) = x(T(Р)) = x(T(Р)).
Для F теж виконуються умови збе-
реження значення базових операцій:
F(¬P) = F(¬P) = T(P) = F(P) = F(P),
F(PQ) = F(PQ) = F(P)F(Q) =
= F(P) F(Q),
F(P&Q) = F(P&Q) = F(P)F(Q) =
= F(P) F(Q),
F ))((R Pv
x = ))((R PF v
x ))(()(r 1
PFv
x
=
= v
x (F(P)) = v
x (F(P)),
F(хР) = F(хР) = x(F(Р)) = x(F(Р)),
F(хР) = F(хР) = x(F(Р)) = x(F(Р)).
Таким чином, T та F – ізоморфіз-
ми алгебри V
AQTS на алгебру AQR .
Дія композицій , , &, ,R v
x x, x
на предикати при відображенні T відпові-
дає дії операцій , , ,, v
x x, x на ква-
зіарні реляції – області їх істинності.
При відображенні F дія компози-
цій , , &, ,R v
x x, x на предикати від-
повідає дії операцій , ,, , v
x x, x, на
квазіарні реляції – області їх хибності.
Для опису алгебр квазіарних реля-
цій природно використовувати першопо-
рядкову мову із таким алфавітом:
Теоретичні та методологічні основи програмування
24
– множина сигнатурних символів
},,,&,,{ xxRCs v
x ,
– множина Rs символів реляцій,
– множина V предметних імен, в
якій виділена нескінченна підмножина
U V тотально неістотних імен.
Предметні імена xV позначають
елементи множини базових даних A, сиг-
натурні символи позначають відповідні
операції над реляціями, символи Rs позна-
чають (виділяють) базові реляції в множи-
ні квазіарних реляцій.
Формули мови описують побудову
складніших реляцій із базових. Дамо інду-
ктивне визначення множини Fr формул:
– Rs Fr; формули pRs атомарні;
– нехай , Fr, тоді
, Ф, &Ф, ,v
xR x, x Fr.
Інтерпретуємо мову на алгебрах
квазіарних реляцій.
Задамо стандартну інтерпретацію,
коли квазіарні реляції трактуються як об-
ласті істинності тотальних однозначних
квазіарних предикатів. При такій інтерпре-
тації сигнатурні символи , ,&, ,v
xR x,
x відповідно інтерпретуються як операції
, ,,, v
x x, x.
Для позначення базових реляцій за-
даємо тотальне однозначне відображення
A
RT
V
RsI 2: . Далі продовжимо його до
відображення A
RT
V
FrI 2: :
– IRT() = IRT(),
– IRT() = IRT() IRT(),
– IRT(&) = IRT() IRT(),
– ))(())(( RT
v
x
v
xRT IRI ,
– IRT(x) = x(IRT()),
– IRT(x) = x(IRT()).
Задамо тепер дуальну інтерпрета-
цію, коли квазіарні реляції трактуються як
області хибності тотальних однозначних
квазіарних предикатів. При дуальній інте-
рпретації сигнатурні символи , ,&, ,v
xR
x, x інтерпретуються відповідно як опе-
рації , , ,, v
x x, x.
Для позначення базових реляцій за-
дамо тотальне однозначне A
RF
V
RsI 2: .
Продовжимо його до A
RF
V
FrI 2: :
– IRF() = IRF(),
– IRF() = IRF() IRF(),
– IRF(&) = IRF() IRF(),
– ))(())(( RF
v
x
v
xRF IRI ,
– IRF(x) = x(IRF()),
– IRF(x) = x(IRF()).
Таким чином, клас тотальних одно-
значних квазіарних предикатів можна
описати як за допомогою композиційних
предикатних алгебр, так і за допомогою
алгебр квазіарних реляцій. Останнє можна
робити двома способами: трактуючи ре-
ляції як області істинності предикатів і
трактуючи їх як області хибності преди-
катів.
5. Алгебри бі-квазіарних реляцій
Для задання тотального однознач-
ного квазіарного предиката необхідно
вказавати його область істинності або йо-
го область хибності, при цьому області
істинності та хибності пов’язані за допо-
могою операції заперечення. При перехо-
ді до нетотальних чи неоднозначних пре-
дикатів ця залежність зникає. Для задання
нетотального чи неоднозначного квазіар-
ного предиката необхідно вказувати як
область його істинності, так і область хи-
бності.
Дія композицій , , &, ,R v
x x, x
на квазіарні предикати відповідає дії опе-
рацій , , ,, v
x x, x на області їх іс-
тинності та дії операцій , , ,, v
x x, x
на області їх хибності. Таким чином, дія
композиції на квазіарний предикат рівно-
сильна дії відповідної операції та дуальної
до неї до двох квазіарних реляцій – області
Теоретичні та методологічні основи програмування
25
істинності та області хибності.
Побудуємо алгебри, визначені на
множинах пар квазіарних реляцій. Назвемо
їх алгебрами бі-квазіарних реляцій.
Алгебри бі-квазіарних реляцій ма-
ють вигляд ) ;22( BQR
AA
BQR OA
VV
, де
},,,,&,{ BBB
v
xBBBBQR xxRO є мно-
жиною базових операцій.
Операції BBB
v
xBBB xxR ,,,,&,
діють на парах квазіарних реляцій так:
– як операції , , ,, v
x x, x на пе-
ршій компоненті пари (стандартно, як опе-
рації на областях істинності);
– як операції , , ,, v
x x, x на
другій компоненті пари (дуально, як опе-
рації на областях хибності).
Таким чином, на парах квазіарних
реляцій визначаємо:
B(L, M) = (M, L);
(L, M) B (R, S) = (LR, MS);
(L, M) &B (R, S) = (LR, MS);
));(),((),( MLMLR v
x
v
xB
v
x
B x (L, M) = (x(L), x(M));
B x (L, M) = (x(L), x(M)).
Бі-квазіарна реляція (L, M)
V
A
V
A:
– однозначна, якщо L M = ;
– тотальна, якщо L M =
V
A;
– однозначна, якщо L M = ;
– замкненa вгору, якщо L та M замк-
нені вгору;
– замкненa вниз, якщо L та M замк-
нені вниз.
Згідно наслідку 1, класи R-предика-
тів, P-предикатів, T-предикатів, TS-преди-
катів, RM-предикатів, RА-предикатів, PE-
предикатів, TА-предикатів замкнені відно-
сно композицій , , &, ,R v
x x, x.
Звідси отримуємо.
Теорема 5. Класи однозначних, то-
тальних, замкнених вгору, замкнених вниз
бі-квазіарних реляцій замкнені відносно
операцій BBB
v
xBBB xxR ,,,,&, .
Таким чином виділяємо наступні
класи бі-квазіарних реляцій:
– SR – клас однозначних,
– TR – клас тотальних,
– STR – клас однозначних тотальних,
– MR – клас замкнених вгору,
– AR – клас замкнених вниз,
– SER – клас замкнених вгору одно-
значних,
– TAR – клас замкнених вниз тота-
льних бі-квазіарних реляцій.
Ми отримуємо наступні підалгебри
алгебри BQRA :
);( BQRSBQR OSRA – алгебра одно-
значних бі-квазіарних реляцій;
);( BQRTBQR OTRA – алгебра тота-
льних бі-квазіарних реляцій;
);( BQRSTQR OSTRA – алгебра од-
нозначних тотальних бі-квазіарних реля-
цій;
);( BQRMBQR OMRA – алгебра
замкнених вгору бі-квазіарних реляцій;
);( BQRABQR OARA – алгебра
замкнених вниз бі-квазіарних реляцій;
);( BQRSEBQR OSERA – алгебра
замкнених вгору однозначних бі-
квазіарних реляцій;
);( BQRTABQR OTARA – алгебра
замкнених вниз тотальних бі-квазіарних
реляцій.
У випадку TS-предикатів області їх
істинності та хибності пов’язані за допо-
могою операції заперечення. Тому всі еле-
менти STR мають вигляд (L, L).
Для бі-квазіарних реляцій відобра-
ження дуалізації AAAA VVVV
2222:
задамо так: (L, M) = (M, L).
Теорема 6. Відображення дуаліза-
ції:
1) є автоморфізмом алгебри BQRA ;
2) є ізоморфізмом алгебр SBQRA та
TBQRA ;
Теоретичні та методологічні основи програмування
26
3) є ізоморфізмом алгебр MBQRA та
ABQRA ;
4) є ізоморфізмом алгебр SEBQRA та
TABQRA ;
5) є тотожним автоморфізмом алге-
бри STQRA .
Твердження п. 5 очевидне.
Доведемо п. 1. Покажемо, що для
виконуються умови збереження значення
базових операцій. Маємо:
(B(L, M)) = (M, L) = (L, M) =
= B(M, L) = B((L, M));
((L, M) B (R, S)) = (LR, MS) =
= ((MS), (LR)) = (M S, LR) =
= (M, L) B (S, R) = (L, M) B (R, S);
((L, M) &B (R, S)) = (LR, MS) =
=((MS), (LR)) = (M S, LR) =
= (M, L) &B (S, R) = (L, M) &B (R, S);
))(),(()),(( MLMLR v
x
v
xB
v
x
))(),(())(),(( LMLM v
x
v
x
v
x
v
x
)),((),( MLRLMR
B
v
xB
v
x ;
(B x (L, M)) = (x(L), x(M)) =
= (x(M), x(L)) = (x(M), x(L)) =
= B x (M, L) = B x ((L, M));
(B x (L, M)) = (x(L), x(M)) =
= (x(M), x(L)) = (x(M), x(L)) =
= B x (M, L) = B x ((L, M)).
Таким чином, – автоморфізм ал-
гебри BQRA .
Подібним чином доводимо пп.2–4.
Теорема 7. 1) алгебри BQRA і V
AQR
ізоморфні;
2) алгебри SBQRA , TBQRA , V
AQP ,
V
AQT ізоморфні;
3) алгебри MBQRA , ABQRA , V
AQRM ,
V
AQRA ізоморфні;
4) алгебри SEBQRA , TABQRA , V
AQPE ,
V
AQTA ізоморфні;
5) aлгебри STQRA і V
AQTS ізо-
морфні.
Твердження п. 5 очевидне.
Доведемо п. 1. Для цього задамо ві-
дображення ізоморфізму алгебри V
AQR
на алгебру BQRA .
Відображення AAV
A
VV
PrR 22:
задаємо наступною умовою:
(P) = (T(P), F(P)).
Таке відображення зіставляє кож-
ному предикату його область істинності та
область хибності.
Покажемо, що для виконуються
умови збереження значення базових
операцій:
(¬P) = (T(¬P), F(¬P)) =
= (F(P), T(P)) = B (T(P), F(P)) = B ((P));
(PQ) = (T(PQ), F(PQ)) =
= (T(P)T(Q), F(P)F(Q)) =
= (T(P), F(P)) B (T(Q), F(Q)) = (P) B (Q);
(P&Q) = (T(P&Q), F(P&Q)) =
= (T(P)T(Q), F(P)F(Q)) =
= (T(P), F(P)) &B (T(Q), F(Q)) =
= (P) &B (Q);
))((R Pv
x = )))((R)),((R( PFPT v
x
v
x =
= )))(()(r)),(()((r 1
1
PFPT v
x
v
x
=
= )))(()),((( PFPT v
x
v
x = v
x (T(P), F(P)) =
= ));(())(),(( PRPFPTR
B
v
xB
v
x
(хР) = (T(хР), F(хР)) =
= (x(T(Р)), x(F(Р))) = B x (T(Р), F(Р)) =
= B x ((Р));
(хР) = (T(хР), F(хР)) =
= (x(T(Р)), x(F(Р))) = B x (T(Р), F(Р)) =
= B x ((Р)).
Таким чином, – ізоморфізм алгеб-
Теоретичні та методологічні основи програмування
27
ри V
AQR на алгебру BQRA .
Подібним чином доводимо пп. 2–4.
Для опису алгебр бі-квазіарних ре-
ляцій використовуємо описану вище пер-
шопорядкову мову із множиною сигнатур-
них символів },,,&,,{ xxRCs v
x .
Інтерпретуємо цю мову на алгебрах
бі-квазіарних реляцій таким чином.
Кожну бі-квазіарну реляцію тракту-
ємо як пару множин – область істинності
та область хибності певного квазіарного
предиката. Сигнатурні символи &,,,
xxRv
x ,, інтерпретуються відповідно як
операції BBB
v
xBBB xxR ,,,,&, на мно-
жині бі-квазіарних реляцій.
Для позначення базових бі-реляцій
задаємо тотальне однозначне відображен-
ня AA
BR
VV
RsI 22: . Таке BRI далі про-
довжимо до AA
BR
VV
FrI 22: :
– BRI () = B( BRI ()),
– BRI () = BRI () B BRI (),
– BRI (&) = BRI () &B BRI (),
– ))(())(( BRB
v
x
v
xBR IRRI ,
– BRI (x) = B x ( BRI ()),
– BRI (x) = B x ( BRI ()).
Таким чином, класи квазіарних пре-
дикатів можна описати як за допомогою
композиційних предикатних алгебр, так і
за допомогою алгебр бі-квазіарних реля-
цій. Кожна бі-квазіарна реляція визначає
область істинності та область хибності
квазіарного предиката.
Висновки
В роботі побудовано та досліджено
низку алгебр квазіарних реляцій (відно-
шень), розглянуто їх зв’язки із алгебрами
квазіарних предикатів. На множині всіх
квазіарних реляцій природним чином за-
даються булеві операції об’єднання, пере-
тину, доповнення, а також спеціальні но-
мінативні операції реномінації та кванти-
фікації. Встановлено ізоморфізм алгебри
квазіарних реляцій та першопорядкової
алгебри тотальних однозначних квазіарних
предикатів.
Побудовано алгебри бі-квазіарних
реляцій, задані на множинах пар квазіар-
них реляцій. Визначено та досліджено різ-
ні підкласи таких алгебр. Встановлено ізо-
морфізми алгебри бі-квазіарних реляцій і
алгебри квазіарних предикатів; ізоморфіз-
ми алгебр однозначних, тотальних, тота-
льних однозначних бі-квазіарних реляцій
та алгебр часткових однозначних, тоталь-
них, тотальних однозначних квазіарних
предикатів; ізоморфізми алгебр замкнених
вгору, замкнених вниз, замкнених вгору
однозначних, замкнених вниз тотальних
бі-квазіарних реляцій та алгебр монотон-
них, антитонних, однозначних еквітонних,
тотальних антитонних квазіарних предика-
тів.
1. Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л.
Алгебра, языки, программирование. – К.:
Наукова думка, 1974. – 328 с.
2. Нікітченко М.С., Шкільняк С.С. Матема-
тична логіка та теорія алгоритмів. – К.:
ВПЦ Київський університет, 2008. – 528 с.
3. Нікітченко М.С., Шкільняк С.С. Прикладна
логіка. – К.: ВПЦ Київський університет,
2013. – 278 с.
4. Birkhoff G. Lattice theory. – Amer. Math.
Soc., 1967. – 418 p.
5. Нікітченко М.С., Шкільняк С.С. Алгебри
квазіарних відношень // Theoretical and
Applied Aspects of Program Systems
Development (TAAPSD'2014): 11th interna-
tional conference: proceeding. – K., 2014. –
С. 174–181.
References
1. Glushkov V., Ceytlin G., Yuschenko E. (1974).
Algebras, languages, programming. – Кyiv:
Naukova dumka (in Russian).
2. Nikitchenko M., Shkilniak S. (2008). Ma-
thematical logic and theory of algorithms. –
Кyiv: VPC Кyivskyi Universytet (in
Ukrainian).
3. Nikitchenko M. and Shkilniak S. (2013).
Applied logic. – Кyiv: VPC Кyivskyi
Universytet (in Ukrainian).
Теоретичні та методологічні основи програмування
28
4. Birkhoff G. (1967) Lattice theory. Amer.
Math. Soc., 1967.
5. Nikitchenko M. and Shkilniak S. (2014).
Algebras of quasiary relations. In Theoretical
and Applied Aspects of Program Systems
Development (TAAPSD'2014): 11th
international conference: proceeding. – Кyiv.
P. 174–181 (in Ukrainian).
Одержано 09.11.2015
Про авторів:
Нікітченко Микола Степанович,
доктор фізико-математичних наук,
професор, завідувач кафедри теорії
та технології програмування.
Кількість наукових публікацій –
понад 200, у тому числі у фахових
виданнях – 100.
Кількість наукових публікацій в
іноземних виданнях – 30.
Індекс Гірша – 8 (6 з 2010).
http://orcid.org/0000-0002-4078-1062.
Шкільняк Степан Степанович,
доктор фізико-математичних наук,
професор, професор кафедри теорії
та технології програмування.
Кількість наукових публікацій –
понад 200,
у тому числі у фахових виданнях – 90.
Кількість наукових публікацій в
іноземних виданнях – 14.
Індекс Гірша – 4 (3 з 2010).
http://orcid.org/0000-0001-8624-5778.
Місце роботи авторів:
Київський національний університет
імені Тараса Шевченка,
01601, Київ, вул. Володимирська, 60.
Тел.: (044) 259 0519,
(044) 522 0640 (д).
E-mail: ttp@unicyb.kiev.ua
|