Algebras of general non-deterministic predicates
Logics of general nondeterministic qua-siary predicates, called GND-predicates, are defined and investigated. These logics are program-oriented logical for-malisms that reflect such properties of programs as partiality, nondeterminism, and non-fixed arity. GND-predicates generalize partial predicate...
Saved in:
| Date: | 2018 |
|---|---|
| Main Authors: | , , |
| Format: | Article |
| Language: | English |
| Published: |
PROBLEMS IN PROGRAMMING
2018
|
| Subjects: | |
| Online Access: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/227 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Problems in programming |
| Download file: |  |
Institution
Problems in programming| _version_ | 1865435922825216000 |
|---|---|
| author | Nikitchenko, M.S. Shkilniak, O.S. Shkilniak, S.S. |
| author_facet | Nikitchenko, M.S. Shkilniak, O.S. Shkilniak, S.S. |
| author_institution_txt_mv | [
{
"author": "M.S. Nikitchenko",
"institution": "Kiev Taras Shevchenko National University"
},
{
"author": "O.S. Shkilniak",
"institution": "Kiev Taras Shevchenko National University"
},
{
"author": "S.S. Shkilniak",
"institution": "Kiev Taras Shevchenko National University"
}
] |
| author_sort | Nikitchenko, M.S. |
| baseUrl_str | https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| collection | OJS |
| datestamp_date | 2024-12-15T19:12:21Z |
| description | Logics of general nondeterministic qua-siary predicates, called GND-predicates, are defined and investigated. These logics are program-oriented logical for-malisms that reflect such properties of programs as partiality, nondeterminism, and non-fixed arity. GND-predicates generalize partial predicates of the rela-tional type. The main attention is paid to the construction of composition algebras of GND-predicates. Compositions of GND-predicates are described, their properties are formulated. For these predicates, such important laws of tradi-tional logic as the law of absorption and the law of distributivity for for and are not valid. Various types of GND-predicates are identified. GND-predicates can be modeled as 7-value total deter-ministic predicates (TD7-predicates). A 7-element algebra of truth values of TD7-predicates is defined and all of its subalgebras are described. Each such subalgebra induces a corresponding al-gebra of TD7-predicates, which then in-duces the algebra of GND-predicates. This makes possible to identify a number of important composition algebras of general nondeterministic predicates. The languages of pure first-order logics of GND-predicates and their interpretations are described. The relations of a logical G-consequence and a logical G-equivalence are introduced. The relation of the logical G-consequence is mono-tonic, reflexive, and transitive; for it the properties of the decomposition of for-mulas are satisfied. On the basis of these properties, it is planned to construct cal-culi of sequential type for the logic of GND-predicates.Problems in programming 2018; 1: 05-21 |
| doi_str_mv | 10.15407/pp2018.01.005 |
| first_indexed | 2026-03-12T23:16:57Z |
| format | Article |
| fulltext |
Теоретичні та методологічні основи програмування
© М.С. Нікітченко, О.С. Шкільняк, С.С. Шкільняк, 2018
ISSN 1727-4907. Проблеми програмування. 2018. № 1 5
УДК 004.42:510.69
М.С. Нікітченко, О.С. Шкільняк, C.С. Шкільняк
АЛГЕБРИ ЗАГАЛЬНИХ НЕДЕТЕРМІНОВАНИХ
ПРЕДИКАТІВ
Запропоновано та досліджено логіки загальних недетермінованих квазіарних предикатів – GND-преди-
катів. Такі предикати є узагальненням часткових неоднозначних предикатів реляційного типу. Основна
увага приділена побудові композиційних алгебр GND-предикатів. Виділено різновиди GND-предикатів,
показано їх зв'язок із 7-значними тотальними детермінованими предикатами. Виділено 7-елементну ал-
гебру істиннісних значень цих предикатів, описано усі її підалгебри. Такі підалгебри індукують відпо-
відні алгебри GND-предикатів. Описано мови чистих першопорядкових логік GND-предикатів та їх ін-
терпретації. Введено та досліджено відношення логічного G-наслідку.
Ключові слова: логіка, алгебра, недетермінований предикат, логічний наслідок.
Вступ
Апарат математичної логіки з вели-
ким успіхом використовується при розв’я-
занні широкого кола задач інформатики й
програмування. Для цього зазвичай вико-
ристовується класична логіка предикатів
та будовані на її основі спеціальні логіки
(модальні, темпоральні, алгоритмічні, про-
грамні тощо). Водночас класична логіка
має низку принципових обмежень, що ус-
кладнює її застосування. Така логіка базу-
ється на традиційних математичних струк-
турах однозначних тотальних скінченно-
арних відображень, а для інформатики й
програмування характерним є використан-
ня часткових недетермінованих відобра-
жень над неповними даними. Тому особ-
ливого значення набуває проблема побу-
дови нових, програмно-орієнтованих логі-
чних формалізмів, базованих на цих відо-
браженнях. Такими є композиційно-номі-
нативні логіки (КНЛ) квазіарних предика-
тів. Широкий спектр різноманітних КНЛ
описано та досліджено в [1–6]. В даній ро-
боті ми пропонуємо нові класи програмно-
орієнтованих логічних формалізмів: КНЛ
загальних недетермінованих предикатів.
Дослідження композиційних предикатних
алгебр таких логік є метою даної роботи.
B роботах [2–6] часткові недетермі-
новані (неоднозначні) предикати ми трак-
тували як відповідності (відношення) між
множиною даних VA та множиною істинні-
сних значень {T, F}. Їх названо V-A-квазі-
арними предикатами реляційного типу,
або R-предикатами. Тут VA – множинa всіх
V-A-іменних множин (V-A-ІМ). Нагадаємо,
що V-A-ІМ – це однозначна функція ви-
гляду d : V A, де V – множина предмет-
них імен (змінних), A – множина пред-
метних (базових) значень.
Кожний класичний предикат при за-
стосуванні до певного даного приймає од-
не з двох значень: T чи F. Кожний R-пре-
дикат P : VA {T, F} на даному dVА може
приймати лише значення T, лише значення
F, обидва значення T та F, а також може
бути невизначеним. Отже, для R-предиката
маємо 4 можливості для прийняття зна-
чення при застосуванні до певного даного.
Нехай P[d] – множина значень, які R-пре-
дикат P : VA {T, F} може прийняти на
dVА. Тоді P[d] – це одне із {}, {T}, {F},
{T, F}. Таким чином, кожний R-предикат P
однозначно задається за допомогою 2-х
множин: область істинності T(P) =
= {dVA | TP[d]}, область хибності
F(P) = {dVA | FP[d]}.
В загальному випадку поняття не-
детермінованого предиката можна ввести
наступним чином. Недетермінований пре-
дикат P : VA {T, F} при застосуванні до
даного dVА може приймати значення T,
приймати значення F, а також може не
приймати жодного значення (бути неви-
значеним). Для кожного dVА має бути
принаймні одна з цих ситуацій, що загалом
дає 7 можливостей для прийняття значення
при застосуванні до певного даного. Нехай
P[d] – множина значень, які недетерміно-
Теоретичні та методологічні основи програмування
6
ваний предикат P може прийняти на dVА,
тоді P[d] може бути одним із {}, {T},
{F}, {T, F}, {T, }, {F, }, {T, F, }.
Загальні недетерміновані квазіарні
предикати назвемо GND-предикатами.
Поняття загального недетерміно-
ваного предиката можна пояснити насту-
пним чином. Уявімо собі складний преди-
кат-механізм, утворений із базових пре-
дикатів-механізмів за допомогою певних
засобів (композицій). Такий складний
предикат може містити багато екземпля-
рів одного і того ж базового предиката.
На деяких даних через нечіткість та неви-
значеність інформації базовий предикат
може функціонувати недетермінованим
чином: на одному і тому ж даному одні
екземпляри можуть приймати значення T,
інші екземпляри – значення F, а деякі йо-
го екземпляри можуть не приймати жод-
ного значення. Зрозуміло, що композиції
таких недетермінованих предикатів як за-
соби побудови складніших предикатів із
простіших мають враховувати ці особли-
вості.
Загальні недетерміновані квазіарні
предикати запропоновано в [7]. Огляд не-
детермінованих пропозиційних логік та
логік недетермінованих n-арних предика-
тів наведено в [8].
Поняття, які в цій статті не визна-
чаються, будемо тлумачити в сенсі [2, 5].
1. Недетерміновані квазіарні
предикати та їх композиції
Кожний V-A-квазіарний GND-пре-
дикат P можна однозначно описати за до-
помогою 3-х множин: областi істинності
T(P), області хибності F(P) та області не-
визначеності (P). Вони задаються так:
– T(P) = {d | P може приймати на d
значення T},
– F(P) = {d | P може приймати на d
значення F},
– (P) = {d | P може бути невизна-
ченим на d}.
Кожне dVА має бути принаймні в
одній з цих множин, звідки загальна умова
F(P) T(P) (P) = VA (G)
Клaс V-А-квазіарних GND-предика-
тів позначимо PrGV–A.
Визначення неістотного предметно-
го імені для GND-предикатів таке ж, як для
R-предикатів (див. [2, 5]).
Ім’я хV неістотне для предиката P,
якщо для довільних d1, d2
VA маємо:
d1||–х = d2 ||–х P(d1) = P(d2).
Опишемо тепер композиції квазіа-
рних GND-предикатів.
Традиційні пропозиційні композиції
(логічні зв’язки) , , & та задамо через
області істинності, хибності та невизначе-
ності відповідних предикатів:
T(P) = F(P),
F(P) = T(P),
(P) = (P);
T(PQ) = T(P) T(Q),
F(PQ) = F(P) F(Q),
(PQ) = ((P) (Q))
((P) F(Q)) (F(P) (Q));
T(P&Q) = T(P) T(Q),
F(P&Q) = F(P) F(Q),
(P&Q) = ((P) (Q))
((P) T(Q)) (T(P) (Q));
T(PQ) = F(P) T(Q),
F(PQ) = T(P) F(Q),
(PQ) = ((P) (Q))
((P) F(Q)) (T(P) (Q)).
При визначенні (PQ) беремо до
уваги таке: PQ невизначений на d P
та Q невизначені на d або P невизначений
на d та Q хибний на d або Q невизначе-
ний на d та P хибний на d.
Подібним чином обґрунтовуємо ви-
значення (P&Q) та (PQ).
та – це базові композиції GND-
предикатів на пропозиційному рівні.
Композиції та & є похідними, во-
ни задаються через та :
PQ = P Q;
P&Q = (P Q).
Теоретичні та методологічні основи програмування
7
Розглянемо характерні властивості
GND-предикатів.
Твердження 1. Із визначень отри-
муємо такі співвідношення:
– T(PQ) (PQ) =
= T(P) (P) T(Q) (Q);
– F(PQ) (PQ) =
= (F(P) (P)) (F(Q) (Q));
– T(P&Q) (P&Q) =
= (T(P) (P)) (T(Q) (Q));
– F(P&Q) (P&Q) =
= F(P) (P) F(Q) (Q).
Збіжність областей істинності та
хибності предикатів не означає збіжності
областей невизначеності.
Приклад 1. Маємо
T(P&Q P) = T((PQ) & P) = T(P),
F(P&Q P) = F((PQ) & P) = F(P);
водночас (P&Q P) = ((PQ) & P) =
= (P) (F(P) T(P) (Q)).
Це можна трактувати так, що при
ускладненні опису предиката зростає неви-
значеність його функціонування (наростає
ентропія опису). При переході від просто-
го опису P до складнішого із залученням Q
до опису P, до області невизначеності (P)
додається компонента F(P) T(P) (Q),
яка може бути ≠ .
Таким чином, в класі R-предикатів
P, (PQ) & P, P&Q P збігаються, водно-
час в класі GND-предикатів (PQ) & P та
P&Q P збігаються, проте вони не збіга-
ються із P.
Приклад 2. Можна показати:
((P&R)(Q&R)) = ((PQ)&R)
(((P)(Q)) F(R) T(R)).
Твердження 2. Для GND-предика-
тів маємо такі закони традиційної логіки.
1) Комутативність та &:
PQ = QP; P&Q = Q&P.
2) Асоціативність та &:
(PQ)R = P(QR);
(P&Q)&R = P&(Q&R).
3) Зняття подвійного заперечення:
P = Р.
4) Ідемпотентність та &:
Р = РР; Р = Р&Р.
5) Закони де Моргана:
(PQ) = P & Q;
(P&Q) = P Q.
Водночас, як засвідчують приклади
1 та 2, для GND-предикатів не виконують-
ся такі важливі закони традиційної логіки,
як закони поглинання та закони дистрибу-
тивності для та &.
Композицію реномінації R v
x для
GND-предикатів можна задати традиційно:
R ( )[ ] [r ( )]v v
x xP d P d для всіх dVА.
Таку композицію можна визначити
через області істинності, хибності та неви-
значеності відповідного предиката R ( )v
x P :
T (R ( ))v
x P = {d |
r ( ) ( )v
x d T P };
F (R ( ))v
x P = {d | r ( ) ( )v
x d F P };
(R ( ))v
x P = {d | r ( ) ( )v
x d P }.
Опишемо для GND-предикатів ком-
позиції квантифікації x та x.
Задамо предикат xP через його об-
ласті істинності, хибності, невизначеності.
T(xP) = {d | d x a T(Р) для де-
якого aA};
F(xP) = {dVA | d x a F(Р) для
всіх aA};
(xP) = {d | dx a(Р)F(Р) для
всіх aA та dx b(Р) для деякого
bA}.
Композиція х є похідною, її зада-
ємо традиційним чином: хР = хР.
Твердження 3. d (xP) T(xP)
d x b T(Р) (P) для деякого bA.
d (xP) F(xP)
d x a F(Р) (P) для всіх aA.
Основні властивості композицій ре-
номінації та квантифікації GND-предикатів
такі ж, як для R-предикатів (див. [2–6]).
Теоретичні та методологічні основи програмування
8
Наведемо властивості, пов’язані з
реномінацією.
R) R( ) P P – тотожна реномінація.
RI) ,
,R ( ) R ( )z v v
z x xP P .
RR) ,
,R (u x
v y хP) = R (u
v хP).
RU) ,
,R ( ) R ( )z v v
y x xP P , якщо z неісто-
тне для P.
Ren) R ( ), y
zyP z P якщо z неістот-
не для P.
R) R ( ) R ( ) v v
x xP P .
R) R ( ) R ( ) R ( ) v v v
x x xP Q P Q .
RR) R (R ( )) R ( )v w v w
x y x yP P – згорт-
ка реномінацій (див. [2, 5]).
Rs) R ( ) R ( ), v v
x xyP y P { , }y v x .
R) R ( ) R ( ), v v y
x x zyP z P якщо z
неістотне для P та { , }z v x .
Для опису властивостей елімінації
кванторів використовують [5] спеціальні
предикати-індикатори Ez наявності в да-
них компоненти з відповідним zV. Такі
предикати Ez тотальні та однозначні, на
рівні GND-предикатів задаємо їх так:
T(Ez) = {d | d(z)},
F(Ez) = {d | d(z)},
(Ez) = .
Твердження 4.
(Ez) = () F(Ez) = () {d | d(z)};
(Ez) = () T(Ez) = () {d | d(z)};
(Ez) F(Ez) =
= () F() {d | d(z)}.
Властивості елімінації кванторів
для GND-предикатів опишемо в наступних
роботах.
Композиції , , R ,v
x x – це базові
композиції чистих першопорядкових КНЛ
квазіарних предикатів (ЧКНЛ). Позначимо
CQ = {, , R ,v
x x}.
Алгебру AQGV–A = (PrGV–A, CQ) на-
звемо чистою першопорядковою компози-
ційною алгеброю GND-предикатів.
Опишемо різновиди GND-предика-
тів. Відносна незалежність області неви-
значеності від областей істинності та хиб-
ності (лише умова F(P) T(P) (P) = VA)
дає змогу виділити низку різноманітних
класів GND-предикатів.
V-A-квазіарний GND-предикат P:
– R-предикат, якщо ( ) ( ) ( ) P T P F P ;
– однозначний, якщо T(P)F(P) = ;
– однозначний R-предикат, якщо
T(P)F(P) = та ( ) ( ) ( ) P T P F P ;
– тотальний, якщо T(P)F(P) =
VA;
– тотальний R-предикат, якщо (P) = ;
– виконуваний, якщо T(P) ;
– неспростовний, якщо F(P) = ;
– неспростовний R-предикат, якщо
F(P) = та ( ) ( )P T P ;
– тотально істинний, якщо T(P) = VА,
– тотально істинний R-предикат, якщо
T(P) = VА та (P) = ;
– тотожно істинний (позн. T), якщо
F(P) = (P) = (тоді T(P) = VА);
– тотально хибний, якщо F(P) = VА;
– тотально хибний R-предикат, якщо
F(P) = VА та (P) = ;
– тотально невизначений, якщо (P) = VА;
– тотожно хибний (позн F), якщо
T(P) = (P) = (тоді F(P) = VА);
– тотально істинно-невизначений (позн.
T), якщо T(P) = (P) = VА та F(P) = ;
– тотально хибно-невизначений (позн. F),
якщо F(P) = (P) = VА та T(P) = ;
– тотожно невизначений (позн. ), якщо
T(P) = F(P) = (тоді (P) = VА);
– тотально амбівалентний, якщо
T(P) = F(P) = VА;
– тотально амбівалентний R-предикат
(позн. ), якщо T(P) = F(P) = VА та
(P) = ;
– тотально недетермінований (позн. ),
якщо T(P) = F(P) = (P) = VА.
В класі GND-предикатів можна ви-
ділити 7 константних: T, F, , T, F, , .
Теоретичні та методологічні основи програмування
9
Однозначні GND-предикати, тота-
льні GND-предикати, тотальні однозначні
GND-предикати, однозначні R-предикати,
тотальні R-предикати, тотальні однозначні
R-предикати назвемо відповідно SG-пре-
дикатами, TG-предикатами, TSG-предика-
тами, P-предикатами, T-предикатами, TS-
предикатами. Класи V-A-квазіарних SG-
предикатів, TG-предикатів, TSG-предика-
тів, P-предикатів, T-предикатів, TS-преди-
катів будемо позначати PrSGV–A, PrTGV–A,
PrTSGV–A, PrPV–A, PrTV–A, PrTSV–A .
Можину F(P) T(P) назвемо об-
ластю амбівалентності GND-предиката P.
Беручи до уваги області невизначе-
ності та амбівалентності, можна також ви-
ділити специфічні класи GND-предикатів.
V-A-квазіарний GND-предикат P:
– AU-предикат, якщо F(P) T(P) (P);
– UA-предикат, якщо (P) F(P) T(P);
– U=A-предикат, якщо (P) = F(P) T(P);
– AnU-предикат, якщо ( ) ( ) ( );T P F P P
– ImG-предикат, якщо ( ) ( ) ( ).P T P F P
ImG-предикати – це GND-предикати
з неточними (imprecise) істиннісними зна-
ченнями. Це означає, що не існує даних на
яких ImG-предикат приймає значення ли-
ше T або лише F. Для відповідного TD7-
предиката маємо відсутність T та F у мно-
жині істиннісних значень. Безпосередньо
ImG-умова формулюється так:
T(P) \ F(P) T(P) \ F(P) (P) (Im)
Водночас за умови (G) умова (Im)
спрощується до наведеної вище.
Твердження 5. За умови (G) маємо
(Im) ( ) ( ) ( ).P T P F P
Маємо T(P) \ F(P) T(P) \ F(P) (P)
( ) \ ( ) ( ) \ ( ) ( )T P F P F P T P P
( ( ) ( )) ( ( ) ( )) ( )T P F P F P T P P
( ( ) ( )) ( ( ) ( )) ( )T P F P F P T P P .
Звідси ( ) ( ) ( )P T P F P (Im).
Тепер (Im) ( ) ( ) ( ).P T P F P
Нехай супротивне: (Im) i для деякого dVА
маємо ( )d P та dF(P) T(P); згідно
(Im) тоді необхідно ( ) ( )d T P F P . От-
же, ( ) ( ) ( ),d P T P F P звідки маємо
d F(P) T(P) (P), що суперечить(G).
Кожний тотально невизначений та
кожний тотально амбівалентний предикат
є ImG-предикатом.
Для R-предикатів ImG-умова дає
вироджений клас із умовою T(P) = F(P).
Умова ( ) ( ) ( )T P F P P рівно-
сильна умові T(P) F(P) (P) = , яка
гарантована для R-предикатів, тому кож-
ний R-предикат є AnU-предикатом. Кож-
ний SG-предикат є AnU-предикатом, проте
є SG-предикати, які не є R-предикатами.
Неоднозначні AU-предикати не є R-
предикатами. SG-предикати гарантовано є
AU-предикатами.
Тотальні R-предикати є UA-преди-
катами, водночас кожний UA-предикат та
кожний U=A-предикат з умовою (P) ≠
не є R-предикатом.
AU-предикати та U=A-предикати із
умовою (P) = є TS-предикатами.
2. Алгебри TD7-предикатів
Множиною значень, які GND-
предикат приймає на конкретному даному,
може бути одна з {}, {T}, {F}, {T, F},
{T, }, {F, }, {T, F, }. Скорочено поз-
начимо ці значення , T, F, TF, T, F,
TF.
Таким чином, GND-предикати мо-
жна моделювати як 7-значні тотальні де-
терміновані предикати. Назвемо їх TD7-
предикатами. Клас V-А-квазіарних TD7-
предикатів позначимо PrTD7V–A. Множи-
ною істиннісних значень TD7-предикатів є
TV7 = {, T, F, TF, T, F, TF}.
На пропозиційному рівні значення
складного предиката цілком визначається
значеннями його компонент, тому пропо-
зиційні композиції TD7-предикатів можна
задавати традиційним чином – за допомо-
гою таблиць істинності.
Композиції заперечення та ди-
з’юнкції задаємо так (табл. 1, 2):
Теоретичні та методологічні основи програмування
10
Таблиця 1. Композиція
P T F TF T F TF
P F T TF F T TF
Таблиця 2. Композиція
T F TF T F TF
T T T T T T T T
F T F TF T F TF
TF T TF TF T T TF TF
T T T T
T T T T T T T T
F T F TF T F TF
TF T TF TF T T TF TF
Композиції кон’юнкції & та імплі-
кації через таблиці істинності можна
подати так (табл. 3, 4):
Таблиця 3. Композиція &
& T F TF T F TF
T T F TF T F TF
F F F F F F F F
TF TF F TF F TF F TF
F F F F
T T F TF T F TF
F F F F F F F F
TF TF F TF F TF F TF
Таблиця 4. Композиція
Q
P T F TF T F TF
T T F TF T F TF
F T T T T T T T
TF T TF TF T T TF TF
T T T T
T T F TF T F TF
F T T T T T T T
TF T TF TF T T TF TF
Композиції та – це базові про-
позиційні композиції TD7-предикатів.
Алгебру (PrTD7V–A, {, }) назве-
мо пропозиційною композиційною ал-
геброю TD7-предикатів
Композиції та & є похідними,
вони виражаються через та :
P Q = P Q;
P & Q = (P Q).
Зрозуміло, що множина істиннісних
значень TV7 замкнена щодо базових компо-
зицій , та щодо похідних , .
Алгебру ATV7 = (TV7, {, }) на-
звемо пропозиційною алгеброю істинніс-
них значень TD7-предикатів.
Для множини TV7 природним чином
задамо впорядкування щодо та .
Впорядкування щодо задамо так:
, якщо = .
Діаграма Хассе для TV7 щодо :
F T T
F TF TF
Впорядкування щодо задамо так:
, якщо = .
Діаграма Хассе для TV7 щодо :
T T
F F TF TF
Таким чином TV7 не утворює реші-
тки істиннісних значень.
Причиною цього є специфічна пове-
дінка TF та TF щодо і :
TF TF = TF TF = TF.
Це означає, що та на множині
істиннісних значень {TF, TF} невідмінні.
Згідно інволютивності TF і TF тоді
(TF TF) = (TF TF) =
= TF TF = TF TF = TF.
Алгебра ATV7 індукує композиційні
алгебри GND-предикатів на різних рівнях.
Далі обмежимось розглядом алгебр
пропозиційного рівня. Таким чином, буде-
Теоретичні та методологічні основи програмування
11
мо розглядати алгебру GND-предикатів
APGV–A = (PrGV–A, {, }) та її підалгебри.
Зв’язок алгебри істиннісних значень
ATV7 та композиційної предикатної алгебри
APGV–A встановлюється так.
Наявність певного істиннісного зна-
чення в TV7 означає, що існують преди-
кат PPrGV–A та dVA такі, що P[d].
Звідси отримуємо:
TV7 існують PPrGV–A та
dVA такі: d(P), dT(P), dF(P);
TTV7 існують PPrGV–A та
dVA такі: dT(P), d(P), dF(P);
FTV7 існують PPrGV–A та
dVA такі: dF(P), d(P), dT(P);
TFTV7 існують PPrGV–A та
dVA такі: dT(P), dF(P), d(P);
TTV7 існують PPrGV–A та
dVA такі: dT(P), d(P), dF(P);
FTV7 існують PPrGV–A та
dVA такі: dF(P), d(P), dT(P);
TFTV7 існують PPrGV–A та
dVA такі: dT(P), dF(P), d(P).
3. Підалгебри APGV–A, індуковані
підалгебрами ATV7
Спочатку описуємо підалгебри ал-
гебри ATV7 . Для цього виділяємо підмно-
жини TV7, замкнені щодо {, }.
Кожна підалгебра алгебри ATV7 ін-
дукує відповідну підалгебру алгебри TD7-
предикатів AТD7V–A = (PrTD7V–A, {, }).
Кожна така підалгебра алгебри AТD7V–A
індукує відповідну підалгебру алгебри
GND-предикатів APGV–A .
6-значні предикати. Видалення в
TV7 одного з T, F, T, F без видалення ві-
дповідного дуального F, T, F, T веде до
незамкненості щодо , тому видаляти
можна лише парами T, F чи T, F. Тому
для утворення 6-елементних підалгебр TV7
можна видаляти лише один із , TF, TF.
Підмножина {, T, F, TF, T, F} не-
замкнена щодо : TF F = TF.
Таким чином, маємо дві 6-елементні
підмножини TV7, замкнені щодо :
TV6_1 = {, T, F, T, F, TF};
TV6_2 ={ T, F, TF, T, F, TF}.
Множина TV6_1 ґенерує пропозицій-
ну алгебру істиннісних значень ATV6_1.
Діаграма Хассе для TV6_1 щодо та
така:
F T T
F TF
ATV6_1 індукує підалгебру A1ТD6V–A
алгебри AТD7V–A . Далі, A1ТD6V–A індукує
підалгебру AP6_1GV–A алгебри APGV–A .
Для AP6_1GV–A маємо загальну умову
F(P) T(P) (P) = VA (G)
Відсутність TF у множині TV6_1 за-
дає обмеження на клас GND-предикатів:
F(P) T(P) (P).
Таким чином, AP6_1GV–A – це алгебра
AU-предикатів. Тому AP6_1GV–A далі буде-
мо називати APAUV–A .
Множина TV6_2 ґенерує пропозицій-
ну алгебру істиннісних значень ATV6_2.
Діаграма Хассе для TV6_2 щодо :
F T T
F TF TF
Діаграма Хассе для TV6_2 щодо :
T T
F F TF TF
ATV6_2 індукує підалгебру A2ТD6V–A
алгебри AТD7V–A . Далі, A2ТD6V–A індукує
підалгебру AP6_2GV–A алгебри APGV–A .
Відсутність у множині TV6_2 задає
таке обмеження на клас GND-предикатів:
F(P) T(P) = VA.
Це гарантує виконання умови (G).
Таким чином, AP6_2GV–A – це алгеб-
ра ТG-предикатів. Тому AP6_2GV–A далі бу-
демо називати APTGV–A .
5-значні предикати. Замкненість
щодо вимагає для носія алгебри істин-
нісних значень одночасної наявності чи
відсутності пари T, F та пари T, F. Тому
для утворення 5-елементних підалгебр мо-
Теоретичні та методологічні основи програмування
12
жна в TV7 видаляти: два з елементів , TF,
TF; або пару T, F; або пару T, F. Отже,
маємо 5 варіантів 5-елементних підалгебр.
Підмножина {T, F, T, F, TF} не-
замкнена щодо : TF F = TF.
Підмножина {, T, F, TF, TF} не-
замкнена щодо : TF = TF = T
Залишаються три 5-елементні підм-
ножини TV7, які замкнені щодо :
TV5_1 = {, T, F, T, F};
TV5_2 = {T, F, T, F, TF};
TV5_3 = {, T, F, TF, TF}.
Множина TV5_1 ґенерує пропозицій-
ну алгебру істиннісних значень ATV5_1.
Діаграма Хассе для множини TV5_1
щодо та така:
F F T T
ATV5_1 індукує підалгебру A1ТD5V–A
алгебри AТD7V–A . Далі, A1ТD5V–A індукує
підалгебру AP5_1GV–A алгебри APGV–A .
Відсутність TF та TF у TV5_1 задає
таке обмеження на клас GND-предикатів:
F(P) T(P) = .
Таким чином, AP5_1GV–A – це алгеб-
ра SG-предикатів. Тому AP5_1GV–A далі бу-
демо називати APSGV–A .
Множина TV5_2 ґенерує пропозицій-
ну алгебру істиннісних значень ATV5_2.
Діаграма Хассе для множини TV5_2
щодо та така:
F F TF T T
ATV5_2 індукує підалгебру A2ТD5V–A
алгебри AТD7V–A . Далі, A2ТD5V–A індукує
підалгебру AP5_2GV–A алгебри APGV–A .
Відсутність TF та у TV5_2 задає та-
кі обмеження на алгебру AP5_2GV–A :
F(P) T(P) (P);
F(P) T(P) = VA.
Умова F(P) T(P) = VA гарантує ви-
конання загальної умови (G).
Отже, AP5_2GV–A – це алгебра тота-
льних AU-предикатів. Тому AP5_2GV–A далі
будемо називати APTAUV–A .
Те, що алгебри A та B ізоморфні,
будемо позначати A iz B.
Твердження 6. АTV5_1 iz АTV5_2 .
Наслідок 1. APSGV–A iz APTA_UV–A .
Множина TV5_3 ґенерує пропозицій-
ну алгебру істиннісних значень ATV5_3.
Діаграма Хассе для TV5_3 щодо :
F T
TF TF
Діаграма Хассе для TV5_3 щодо :
T
F TF TF
ATV5_3 індукує підалгебру A3ТD5V–A
алгебри AТD7V–A . Далі, A3ТD5V–A індукує
підалгебру AP5_3GV–A алгебри APGV–A .
Відсутність T та F у TV5_3 задає таке
обмеження на клас GND-предикатів:
( ) ( ) ( )P T P F P .
Отже, AP5_3GV–A – це алгебра ImG-
предикатів; далі її називаємо APImGV–A .
4-значні предикати. Необхідність
замкненості щодо вимагає для носія ал-
гебри істиннісних значень одночасної ная-
вності чи відсутності пар T, F та T, F.
Невключення обох цих пар для 4-елемент-
них носіїв неможливе. Тому для утворення
4-елементних підалгебр можна в TV7 вида-
ляти: трійку , TF, TF; або пару T, F з од-
ним із , TF, TF; або пару T, F з одним
із , TF, TF. Тому до розгляду на замкне-
ність щодо маємо 7 варіантів.
Підмножина {, T, F, TF} незамк-
нена щодо : TF = T
Підмножина {, T, F, TF} незамк-
нена щодо : TF = T
Підмножина {, T, F, TF} неза-
мкнена щодо : TF F = TF
Залишаються чотири 4-елементні
підмножини TV7, вони замкнені щодо :
TV4_1 = {T, F, T, F};
TV4_2 = {T, F, TF, TF};
TV4_3 = {TF, T, F, TF};
TV4_4 = {, T, F, TF}.
Множина TV4_1 ґенерує пропозицій-
ну алгебру істиннісних значень ATV4_1.
Теоретичні та методологічні основи програмування
13
Діаграма Хассе для множини TV4_1
щодо та така:
F F T T
ATV4_1 індукує підалгебру A1ТD4V–A
алгебри AТD7V–A . A
1ТD4V–A індукує підал-
гебру AP4_1GV–A алгебри APGV–A .
Відсутність , TF, TF у TV4_1 задає
обмеження на клас GND-предикатів:
F(P) T(P) = VA;
F(P) T(P) = .
Таким чином, AP4_1GV–A – це алгеб-
ра TSG-предикатів. Алгебру AP4_1GV–A далі
називаємо APТSGV–A .
Множина TV4_2 ґенерує пропозицій-
ну алгебру істиннісних значень ATV4_2.
Діаграма Хассе для TV4_2 щодо :
F TF TF T
Діаграма Хассе для TV4_2 щодо :
F TF TF T
ATV4_2 індукує підалгебру A2ТD4V–A
алгебри AТD7V–A . A
2ТD4V–A індукує підал-
гебру AP4_2GV–A алгебри APGV–A .
Відсутність , T та F і наявність
TF у множині TV4_2 задає такі обмеження
на клас GND-предикатів:
F(P) T(P) = VA;
(P) F(P) T(P).
Отже, AP4_2GV–A – це алгебра тота-
льних UA-предикатів, або ТUA-предикатів.
Алгебру AP4_2GV–A назвемо APТUAV–A .
Множина TV4_3 ґенерує пропозицій-
ну алгебру істиннісних значень ATV4_3.
Діаграма Хассе для TV4_3 щодо :
F TF T
TF
Діаграма Хассе для TV4_3 щодо :
F TF T
TF
ATV4_3 індукує підалгебру A3ТD4V–A
алгебри AТD7V–A . A3ТD4V–A індукує підал-
гебру AP4_3GV–A алгебри APGV–A .
Відсутність , T, F у множині TV4_3
задає обмеження на клас GND-предикатів:
F(P) T(P) = VA.
( ) ( ) ( )P T P F P .
AP4_3GV–A – це алгебра тотальних
ImG-предикатів, або ТImG-предикатів. Ал-
гебру AP4_3GV–A назвемо APТІmGV–A .
Множина TV4_4 ґенерує пропозицій-
ну алгебру істиннісних значень ATV4_4. Ді-
аграма Хассе для TV4_4 щодо та така:
F T
TF
ATV4_4 індукує підалгебру A4ТD4V–A
алгебри AТD7V–A . A
4ТD4V–A індукує підал-
гебру AP4_4GV–A алгебри APGV–A .
Множина TV4_4 задає дуже просте
обмеження на клас GND-предикатів:
(P) = VA.
Отже, AP4_4GV–A – це алгебра тота-
льно невизначених GND-предикатів, які
можна трактувати як предикати з тільки
неточними (only imprecise) істиннісними
значеннями. Назвемо їх OIG-предикатами.
Алгебру AP4_4GV–A називаємо APOIGV–A .
Зауваження. Множина {, T, F, TF}
незамкнена щодо : TF = T. Тому
вона не утворює підалгебри алгебри ATV7 .
Водночас {, T, F, TF} замкнена щодо
композиції В 4-значної логіки Белнапа [2].
Це дає змогу виділити в алгебрі GND-пре-
дикатів APGV–A підалгебру APOIGV–A, ізо-
морфну алгебрі R-предикатів APRV–A (клас
R-предикатів виділяється в класі GND-пре-
дикатів умовою ( ) ( ) ( ) P T P F P ).
Твердження 7. Алгебра АTV4_4 ізо-
морфна алгебрі Белнапа.
Твердження 8. АTV4_4 ізоморфна
алгебрі істиннісних значень R-предикатів.
Наслідок 2. APOIGV–A iz APRV–A .
3-значні предикати. Необхідність
замкненості щодо вимагає для носія ал-
гебри істиннісних значень одночасної ная-
вності чи відсутності пар T, F та T, F.
Теоретичні та методологічні основи програмування
14
Тому для утворення 3-елементних підал-
гебр можна: до пари T, F додавати одне з
, TF, TF; до пари T, F додавати одне з
, TF, TF; взяти трійку , TF, TF. Отже,
до розгляду маємо 7 варіантів.
Підмножина {TF, T, F} незамкне-
на щодо : TF F = TF.
Підмножина {TF, , TF} незамк-
нена щодо : TF = T.
Залишаються п’ять 3-елементних
підмножин TV7, вони замкнені щодо :
TV3_1 = {T, F, };
TV3_2 = {T, F, TF};
TV3_3 = {T, F, TF};
TV3_4 = {T, F, TF};
TV3_5 = {, T, F}.
Множина TV3_1 ґенерує пропозицій-
ну алгебру істиннісних значень ATV3_1. Для
TV3_1 діаграма Хассе щодо та така:
F T
ATV3_1 індукує підалгебру A1ТD3V–A
алгебри AТD7V–A . A
1ТD3V–A індукує підал-
гебру AP3_1GV–A алгебри APGV–A .
Відсутність T, F, TF, TF в TV3_1
задає такі обмеження на GND-предикати:
F(P) T(P) = .
( ) ( ) ( ) P T P F P .
AP3_1GV–A – це пропозиційна алгебра
часткових однозначних R-предикатів, тоб-
то Р-предикатів. Позначимо її APРV–A .
Множина TV3_2 ґенерує пропозицій-
ну алгебру істиннісних значень ATV3_2. Для
TV3_2 діаграма Хассе щодо та така:
F TF T
ATV3_2 індукує підалгебру A2ТD3V–A
алгебри AТD7V–A . A2ТD3V–A індукує підал-
гебру AP3_2GV–A алгебри APGV–A .
Відсутність , T, F, TF у TV3_1
задає обмеження на клас GND-предикатів:
(P) = ;
F(P) T(P) = VA.
Зауважимо, що в силу (G) з умови
(P) = випливає F(P) T(P) = VA. От-
же, виконується умова ( ) ( ) ( ) P T P F P .
Тому AP3_2GV–A – це пропозиційна алгебра
тотальних R-предикатів, тобто Т-предика-
тів. Цю алгебру позначимо APTV–A .
Множина TV3_3 ґенерує пропозицій-
ну алгебру істиннісних значень ATV3_3. Для
TV3_3 діаграма Хассе щодо та така:
F TF T
ATV3_3 індукує підалгебру A3ТD3V–A
алгебри AТD7V–A . A
3ТD3V–A індукує підал-
гебру AP3_3GV–A алгебри APGV–A .
Множина TV3_3 задає такі обмежен-
ня на клас GND-предикатів:
F(P) T(P) = VA.
F(P) T(P) = (P).
Таким чином, AP3_3GV–A – це алгеб-
ра тотальних U=A-предикатів. Назвемо їх
TU=A-предикатами. Алгебру AP3_3GV–A бу-
демо називати APTU=AV–A .
Множина TV3_4 ґенерує пропозицій-
ну алгебру істиннісних значень ATV3_4. Ді-
аграма Хассе для TV3_4 щодо та така:
F TF T
ATV3_4 індукує підалгебру A4ТD3V–A
алгебри AТD7V–A . A
4ТD3V–A індукує підал-
гебру AP3_4GV–A алгебри APGV–A .
Множина TV3_4 задає такi обмежен-
ня на клас GND-предикатів:
(P) = VA;
F(P) T(P) = VA.
Отже, AP3_4GV–A – це алгебра тоталь-
них OIG-предикатів. Назвемо їх TOIG-пре-
дикатами. Алгебру AP3_4GV–A будемо нази-
вати APTOIGV–A .
Множина TV3_5 ґенерує пропозицій-
ну алгебру істиннісних значень ATV3_5. Ді-
аграма Хассе для TV3_5 щодо та така:
F T
ATV3_5 індукує підалгебру A5ТD3V–A
алгебри AТD7V–A . A
5ТD3V–A індукує відпо-
відну AP3_5GV–A алгебри APGV–A .
Множина TV3_5 задає такi обмежен-
ня на клас GND-предикатів:
(P) = VA;
F(P) T(P) = .
Теоретичні та методологічні основи програмування
15
Отже, AP3_5GV–A – це алгебра одноз-
начних OIG-предикатів. Назвемо їх назве-
мо SOIG-предикатами. Алгебру AP3_5GV–A
називатимемо APSOIGV–A .
Ми отримали п’ять 3-елементних
підалгебр алгебри TV7 , всі ці підалгебри
попарно ізоморфні:
Твердження 9. АTV3_1 iz АTV3_2 iz
iz АTV3_3 iz АTV3_4 iz АTV3_5 .
Ці алгебри ізоморфні алгебрі силь-
ної 3-значної логіки Кліні та алгебрам іс-
тиннісних значень логіки Р-предикатів та
логіки Т-предикатів. Тому маємо 5 попарно
ізоморфних підалгебр алгебри APGV–A :
Наслідок 3. APPV–A iz APTV–A iz
iz APTU=AV–A iz APTOIGV–A iz APSOIGV–A .
2-значні предикати. Для утворення
2-елементних підалгебр алгебри TV7 мож-
на: взяти пару T, F; взяти пару T, F; виб-
рати пару з трійки , TF, TF. До розгляду
на замкненість щодо маємо 5 варіантів.
Підмножина {TF, } незамкнена
щодо : TF = T.
Підмножина {TF, } незамкнена
щодо : TF = T.
Залишаються три 2-елементні підм-
ножини TV7, вони замкнені щодо :
TV2_1 = {T, F};
TV2_2 = {T, F};
TV2_3 = {TF, TF}.
Множина TV2_1 ґенерує класичну
булеву алгебру істиннісних значень ATV2_1.
Діаграма Хассе для TV2_1 щодо та :
F T
ATV2_1 індукує підалгебру A1ТD2V–A
алгебри AТD7V–A . A1ТD2V–A індукує підал-
гебру AP2_1GV–A алгебри APGV–A .
Множина TV2_1 задає таке обмеження
на клас GND-предикатів:
F(P) T(P) = ;
(P) = .
Умова (P) = дає F(P) T(P) = VA.
Отже, AP2_1GV–A – це пропозиційна алгебра
TS-предикатів. Цю підалгебру будемо поз-
начати APTSV–A .
Множина TV2_2 ґенерує пропозицій-
ну алгебру істиннісних значень ATV2_2. Ді-
аграма Хассе для TV2_2 щодо та така:
F T
ATV2_2 індукує підалгебру A2ТD2V–A
алгебри AТD7V–A . A2ТD2V–A індукує підал-
гебру AP2_2GV–A алгебри APGV–A .
Множина TV2_2 задає наступні об-
меження на клас GND-предикатів:
F(P) T(P) = ;
F(P) T(P) = (P) = VA.
Отже, AP2_2GV–A – це алгебра тота-
льних однозначних OIG-предикатів. На-
звемо їх TSOIG-предикатами. Алгебру
AP2_2GV–A будемо називати APTSOIGV–A .
Множина TV2_3 ґенерує пропозицій-
ну алгебру істиннісних значень ATV2_3.
Діаграма Хассе для TV2_3 щодо :
TF TF
Діаграма Хассе для TV2_3 щодо :
TF TF
Невідмінність та на {TF, TF}
та інволютивність TF і TF робить алгебру
АTV2_3 дуже специфічною, а базовану на
ній логіку виродженою, в цілому тривіаль-
ною.
ATV2_3 індукує підалгебру A3ТD2V–A
алгебри AТD7V–A . A
3ТD2V–A індукує підал-
гебру AP2_3GV–A алгебри APGV–A .
Множина TV2_3 задає єдине обме-
ження на клас GND-предикатів:
F(P) = T(P) = VA.
GND-предикати з такою умовою –
це тотально амбівалентні предикати, вони
відрізняються лише областями невизначе-
ності. Назвемо їх TAmG-предикатами.
Клас TAmG-предикатів вироджений. Ал-
гебру AP2_3GV–A назвемо APTAmGV–A .
Твердження 10. АTV4_2 iz АTV4_3 .
Наслідок 4. APТSV–A iz APTSOIGV–A .
1-значні предикати. Тут маємо
три 1-елементних підалгебри ATV1_1,
ATV1_2 та ATV1_3 , вони відповідно зада-
Теоретичні та методологічні основи програмування
16
ються 1-елементними множинами з інво-
люційними елементами: {}, {TF}, {TF}.
Зрозуміло, що ці підалгебри попарно ізо-
морфні.
ATV1_1, ATV1_2, ATV1_3 індукують 1-
елементні підалгебри A1ТD1S
V–A, A2ТD1S
V–A,
A3ТD1S
V–A алгебри AТD7V–A , які далі інду-
кують сингулярні 1-елементні підалгебри
AP1_1GS
V–A, AP1_2GS
V–A, AP1_3GS
V–A алгебри
APGV–A . Ці підалгебри позначимо V–A ,
V–A , V–A , вони попарно ізоморфні.
Відношення між підалгебрами.
Те, що алгебра A є підалгеброю алгебри B,
будемо позначати A B.
Для підалгебр алгебри ATV7 маємо:
ATV6_1 ATV7 , ATV6_2 ATV7 ;
ATV5_1 ATV6_1 , ATV5_2 ATV6_1 ,
ATV5_2 ATV6_2 , ATV5_3 ATV7 ;
ATV4_1 ATV5_1 , ATV4_1 ATV5_2 ,
ATV4_2 ATV6_2 , ATV4_3 ATV6_2 ,
ATV4_3 ATV5_3 , ATV4_4 ATV5_3 ,
ATV4_4 ATV6_1 ;
ATV3_1 ATV5_1 , ATV3_2 ATV4_2 ,
ATV3_3 ATV4_2 , ATV3_3 ATV5_2 ,
ATV3_4 ATV5_2 , ATV3_4 ATV4_3 ,
ATV3_4 ATV4_4 , ATV3_5 ATV4_4 ,
ATV3_5 ATV5_1 ;
ATV2_1 ATV3_1 , ATV2_1 ATV3_2 ,
ATV2_1 ATV3_3 , ATV2_1 ATV4_1 ,
ATV2_2 ATV3_4 , ATV2_2 ATV3_5 ,
ATV2_2 ATV4_1 , ATV2_3 ATV4_2 ,
ATV2_3 ATV4_3 ;
ATV1_1 ATV3_1 , ATV1_1 ATV3_5 ,
ATV1_2 ATV2_3 , ATV1_2 ATV3_2 ,
ATV1_3 ATV2_3 , ATV1_3 ATV3_3 ,
ATV1_3 ATV3_4 .
Такі ж відношення маємо для від-
повідних підалгебр алгебри APGV–A та пі-
далгебр алгебри APGV–A , індукованих за-
значеними вище підалгебрами алгебри
ATV7 .
Подібним чином підалгебри алге-
бри ATV7 індукують відповідні підалгебри
першопорядкової алгебри AQGV–A .
4. Мови чистих першопорядкових
логік GND-предикатів
Семантичними моделями чистих
першопорядкових логік GND-предикатів є
чисті першопорядкові композиційні сис-
теми GND-предикатів (A, PrGV–A, CQ). Ко-
жна така композиційна система задає ал-
гебру даних (A, PrGV–A) та композиційну
алгебру (PrGV–A, CQ). Терми композицій-
ної алгебри трактуємо як формули мови,
це добре відома [2, 5] мова ЧКНЛ.
Алфавіт мови: множина V предмет-
них імен (змінних), в якій виділена мно-
жина U V тотально неістотних імен; мно-
жина { , , , }v
xCs R x символів базових
композицій; множина Ps предикатних си-
мволів (ПС) – сигнатура мови. Розширена
сигнатура мови – це = (V, U, Cs, Ps).
Для запису формул використовуємо
(див. [1]) префіксну форму запису.
Індуктивне визначення множини Fr
формул:
– Ps Fr; формули pPs – атомарні;
– , Fr , Ф, ,v
xR xFr.
Для зручності вживаємо скорочення
формул, користуючись символами похід-
них композицій та інфіксною формою за-
пису для бінарних композицій (див. [1]).
Інтерпретуємо мову на композицій-
них системах CS = (A, PrGV–A, CQ) GND-
предикатів. Символи композицій познача-
ють відповідні композиції, імена xV –
елементи множини базових даних A. Сим-
воли Рs позначають базові предикати в
множині PrGV–A , для опису цього позна-
чення задамо тотальне однозначне відо-
браження :I Ps PrGV–A . Відображення
інтерпретації формул :I Fr PrGV–A за-
дамо як розширення відображення
Теоретичні та методологічні основи програмування
17
:I Ps PrGV–A згідно побудови формул із
простіших за допомогою символів Cs:
I() = (I()), I() = (I(), I()),
( ) R ( ( ));v v
x xI R I I(x) = x(I()).
Трійки J = (CS, , I) називають ін-
терпретаціями мови (сигнатури ). Cкоро-
чено позначаємо їх (A, , I) чи (A, I).
Предикат J() – значення формули
при інтерпретації J – позначимо J.
Виділення підалгебр квазіарних
предикатів виділяє відповідні класи інтер-
претацій – семантики. Можна говорити
про загальний клас GND-інтерпретацій та
про низку його підкласів, індукованих опи-
саними вище підалгебрами.
Відношення логічного наслідку.
Спочатку введемо відношення G-наслідку
J|=G для двох формул при фіксованій інте-
рпретації J: J|=G
T(J) T(J) та F(J) F(J)
та (J) (J) T(J)
та (J) (J) F(J).
Неформально те, що є наслідком
означає: при переході від J до J іс-
тинність може лише збільшитися, а хиб-
ність лише зменшитися, невизначеність пе-
реходить у невизначеність або істинність, у
невизначеність переходить невизначеність
або хибність.
Відношення логічного G-наслідку
визначаємо так: |=G , якщо J|=G
для кожної інтерпретації J.
Теорема 1. Відношення J|=G та J|=G
є рефлексивними й транзитивними.
Рефлексивність відношень J|=G та
|=G очевидна. Покажемо їх транзитивність.
Покажемо: J|=G та J|=G J|=G .
Для областей істинності та хибності
умови транзитивності очевидні. Перевіри-
мо ці умови для областей невизначеності.
Маємо (J) (J) T(J) та
(J) (J) T(J), звідки отримуємо
(J) (J) T(J) T(J), проте
T(J) T(J), тому (J) (J) T(J).
Маємо (J) (J) F(J) та
(J) (J) F(J), звідки отримуємо
(J) (J) F(J) F(J), проте
F(J) F(J), тому (J) (J) F(J).
Тепер: |=G та |=G |=G .
Маємо: |=G та |=G для
всіх J маємо J|=G та для всіх J маємо
J|=G для всіх J маємо J|=G та
J|=G J|=G для всіх J |=G .
Для J|=G та |=G справджується закон
контрапозиції.
Твердження 11. Маємо
J|=G J|=G та
|=G |=G .
Відношення G-наслідку та логічно-
го G-наслідку наслідку індукують відно-
шення G-еквівалентності та логічної екві-
валентності.
Відношення G-еквівалентності при
інтерпретації J визначаємо так:
JG , якщо J|=G та J|=G .
Відношення логічної G-еквівалент-
ності визначаємо так:
G , якщо |=G та |=G .
Твердження 12. G JG
для кожної інтерпретації J.
Твердження 13. G & та
G () & .
Покажемо |=G & . Для ко-
жної інтерпретації J маємо:
(J) (J & J J) T(J & J J) =
= (J) (F(J) T(J) (J)) T(J);
(J & J J) = (J) (F(J) T(J)
(J)) (J) F(J).
Покажемо & |=G . Для ко-
жної інтерпретації J маємо:
(J & J J) = (J) (F(J) T(J)
(J)) (J) T(J);
(J) (J & J J) F(J & J J) =
= (J) (F(J) T(J) (J)) F(J).
Теоретичні та методологічні основи програмування
18
Таким чином, G & . Поді-
бним чином показуємо: G () & .
Твердження 14. Для GND-предика-
тів умова G ще не означає повну збі-
жність предикатів J та J
Нехай JG . Тоді T(J) = T(J) та
F(J) = F(J), позначимо T(J) та T(J) як
А, F(J) та F(J) як В. Із J|=G маємо:
(J) (J) T(J), (J) (J) F(J).
Із J|=G маємо: (J) (J) T(J),
(J) (J) F(J). Звідси отримуємо
(J) (J) T, (J) (J) F,
(J) (J) T, (J) (J) F. Тому:
(J) (А \ В) = (J) (А \ В) та
(J) (В \ А) = (J) (В \ А).
Таким чином, якщо JG , то
(J) та (J) можуть відрізнятися лише в
перетині їх областей істинності та хибнос-
ті. Як приклад такої відмінності див. (J)
та (J & J J).
Теорема 3. Відношення J|=G та |=G
монотонні: J|=G &A J|=G B та
|=G &A |=G B
Маємо: T(J) T(J) T(&AJ) =
= T(J) T(AJ) T(J) T(BJ) = T(BJ);
F(J) F(J) F(BJ) =
= F(J) F(BJ) F(J) F(AJ) = F(&AJ).
Перевіримо умови для областей не-
визначеності. Маємо (J) (J) T(J)
та (J) (J) F(J). Звідси маємо
(&AJ) = (T(J)(AJ)) ((J)T(AJ))
((J) (AJ)), (BJ) T(BJ) =
= T(J) (J) T(BJ) (BJ),
(BJ) = (F(J) (BJ)) ((J) F(BJ))
((J) (BJ)), (&AJ) F(&AJ) =
= F(J) (J) F(AJ) (AJ).
Покажемо (&AJ) (BJ) T(BJ).
Маємо (T(J) (AJ)) T(J) T(J),
((J) T(AJ)) ((J) (AJ)) (J),
(J) (J) T(J), звідки (&AJ) =
= (T(J) (AJ)) ((J) (AJ))
((J) (AJ)) T(J) (J) T(J)
(J) T(J) T(BJ) (BJ) =
= (BJ) T(BJ).
Покажемо (BJ) (&AJ) F(&AJ).
Маємо F(J) (BJ)) F(J) F(J),
((J) F(BJ)) ((J) (BJ)) (J),
(J) (J) F(J), звідки (BJ) =
= (F(J) (BJ)) ((J) F(BJ))
((J) (BJ)) F(J) (J) F(J)
F(J) (J) F(AJ) (AJ) =
= (&AJ) F(&AJ).
Звідси отримуємо монотонність ві-
дношення |=G .
Зауважимо, що для формул A&A
та BB завжди виконується умова G-на-
слідку для областей невизначеності.
Твердження 15. Маємо
(A&AJ) (BBJ) T(BBJ);
(BBJ) (A&AJ) F(A&AJ).
Справді, (BBJ) T(BBJ) =
= (BJ) T(BJ) F(BJ) = VA згідно (G);
(A&AJ) F(A&AJ = (AJ) F(AJ)
T(BJ) ) = VA згідно (G).
Декомпозиції формул. Для відно-
шень J|=G та |=G виконуються властивості
декомпозиції формул.
Теорема 4. AB J|=G
A J|=G та B J|=G .
Для областей істинності та хибності
доведення традиційне. Наведемо доведен-
ня для областей невизначеності.
Покажемо:
AB J|=G A J|=G та B J|=G .
Згідно AB J|=G маємо:
(ABJ) (J) T(J)
(J) (ABJ) F(ABJ).
Маємо (ABJ) = (F(AJ) (BJ))
((AJ) F(BJ)) ((AJ) (BJ)), звідки
Теоретичні та методологічні основи програмування
19
(F(AJ) (BJ)) ((AJ) F(BJ))
((AJ) (BJ)) (J) T(J).
Проте T(AJ) (BJ) T(AJ)
T(AJ) T(BJ) T(J), тому отримуємо
(F(AJ) (BJ) ) ((AJ) F(BJ))
((AJ) (BJ)) (T(AJ) (BJ))
(J) T(J)
((F(AJ) (AJ) T(AJ)) (BJ))
((AJ) F(BJ)) (J) T(J)
(BJ) ((AJ) F(BJ)) (J) T(J).
Звідси (BJ) (J) T(J).
Аналогічно маємо T(BJ) (AJ)
T(BJ) T(AJ) T(BJ) T(J), тому
(F(AJ) (BJ)) ((AJ) F(BJ))
((AJ) (BJ)) (T(BJ) (AJ))
(J) T(J)
((F(BJ) (BJ) T(BJ)) (AJ))
(F(AJ) (BJ)) (J) T(J)
(AJ) (F(AJ) (BJ)) (J) T(J),
звідки (AJ) (J) T(J).
Маємо (J) (ABJ) F(ABJ)
= (F(AJ) (AJ)) (F(BJ) (BJ)). Звідси
(J) (AJ)F(AJ), (J) (BJ)F(BJ).
Отже, AB J|=G A J|=G та B J|=G .
Тепер покажемо:
A J|=G та B J|=G AB J|=G .
Згідно A J|=G та B J|=G маємо:
(AJ) (J)T(J), (J) (AJ)F(AJ),
(BJ) (J)T(J), (J) (BJ) (BJ).
Покажемо (ABJ) (J) T(J)
та (J) (ABJ) F(ABJ).
Маємо (BJ) (J) T(J)
F(AJ) (BJ) (J) T(J) та
(AJ) (BJ) (J) T(J);
(AJ) (J) T(J)
(AJ) F(BJ) (J) T(J).
Звідси (ABJ) = (F(AJ) (BJ))
((AJ) F(BJ)) ((AJ) (BJ))
(J) T(J).
Із умови (J) (AJ) F(AJ) та
(J) (BJ) F(BJ) отримуємо (J)
((AJ) F(AJ)) ((BJ) F(BJ)).
Водночас (ABJ) F(ABJ) =
= ((AJ) F(AJ)) ((BJ) F(BJ)), тому
(J) (ABJ) F(ABJ).
Подібним чином доводиться
Теорема 5. J|=G (PQ)
J|=G P та J|=G Q.
Звідси отримуємо
Наслідок 5. Маємо
AB |=G A |=G та B |=G ;
|=G (PQ) |=G P та |=G Q.
Теорема еквівалентності є осно-
вою еквівалентних перетворень формул.
Для її доведення використовується
Теорема 6. 1) G G ;
2) G та G G ;
3) G v v
x G xR R ;
4) G x G x.
Доведемо для прикладу п. 4. Нехай
J – довільна інтерпретація. Із умови G
маємо: T(J) = T(J), F(J) = F(J);
(J) T(J)(J), (J) F(J)(J),
(J) T(J)(J), (J) F(J)(J).
Треба показати:
(xJ) T(xJ) (xJ),
(xJ) F(xJ) (xJ),
(xJ) T(xJ) (xJ),
(xJ) F(xJ) (xJ).
Покажемо перше співвідношення,
інші доводяться подібним чином.
Маємо d(xJ) для всіх aA
маємо d x a (J) F(J) та для де-
якого bA маємо d x b (J)
d x b (J) для деякого bA
згідно (J) T(J) (J) тоді маємо
d x b T(J) (J)) для деякого bA
dT(xJ) (xJ). Таким чином,
(xJ) T(xJ) (xJ).
Теоретичні та методологічні основи програмування
20
Теорема 7 (еквівалентності). Нехай
' отримана з формули заміною деяких
входжень 1,..., n на 1,..., n відповідно.
Якщо 1 G 1, ..., n G n, то G '.
Доводимо індукцією за побудовою
формули із використанням теореми 6.
Властивості декомпозиції формул
індукують відповідні властивості відно-
шення логічного наслідку для множин фо-
рмул, що дає змогу будувати для логік
GND-предикатів числення секвенційного
типу. Властивості такого відношення, зок-
рема, властивості елімінації кванторів, бу-
дуть описані в наступних роботах.
Висновок
В роботі запропоновано та дослі-
джено новий клас програмно-орієнтованих
логічних формалізмів – логіки загальних
недетермінованих квазіарних предикатів,
які названо GND-предикатами. Вони є уза-
гальненням відомих часткових неодно-
значних предикатів реляційного типу. Ос-
новна увага в роботі приділена побудові
композиційних алгебр GND-предикатів.
Описано композиції GND-предикатів, на-
ведено їх характерні властивості. Виділено
низку різновидів GND-предикатів.
GND-предикати можна моделювати
як 7-значні тотальні детерміновані преди-
кати – ТD7-предикати. Виділено 7-елемен-
тну алгебру істиннісних значень TD7-пре-
дикатів, описано усі її підалгебри. Кожна
така підалгебра індукує відповідну алгебру
TD7-предикатів, яка в свою чергу індукує
алгебру GND-предикатів. Це дало змогу
виділити низку важливих композиційних
алгебр загальних недетермінованих преди-
катів.
Описано мови чистих першопоряд-
кових логік GND-предикатів та їх інтер-
претації. Введено відношення логічного G-
наслідку та логічної G-еквівалентності. Ві-
дношення логічного G-наслідку є моно-
тонним, рефлексивним і транзитивним,
для нього виконуються закон контрапози-
ції та властивості декомпозиції формул. На
цій основі в наступних роботах для логік
GND-предикатів планується побудова чис-
лень секвенційного типу.
Література
1. Нікітченко М.С., Шкільняк С.С. Матема-
тична логіка та теорія алгоритмів. К.: ВПЦ
Київський університет, 2008. 528 с.
2. Нікітченко М.С., Шкільняк С.С. Приклад-
на логіка. К.: ВПЦ Київський університет,
2013. 278 с.
3. Nikitchenko М., Shkilniak S. Semantic
Properties of Logics of Quasiary Predicates.
Workshop on Foundations of Informatics:
Proceedings FOI-2015. Chisinau, Moldova.
P. 180–197.
4. Шкільняк С.С., Волковицький Д.Б. Рено-
мінативні логіки квазіарних предикатів.
Компьютерная математика. 2016. Вып. 1.
C. 46–57.
5. Нікітченко М.С., Шкільняк О.С., Шкільняк
С.С. Чисті першопорядкові логіки квазіа-
рних предикатів. Проблеми програмуван-
ня. 2016. № 2–3. C. 73–86.
6. Мykola S. Nikitchenko and Stepan S.
Shkilniak. Algebras and logics of partial
quasiary predicates. Algebra and Discrete
Mathematics. 2017. Vol. 23. N 2. P. 263–278.
7. Nikitchenko М.S., Shkilniak O.S. and
Shkilniak S.S. Logics of partial non-
deterministic predicates. PDMU-2017:
international conference: abstracts. Vilnius,
Lithuania. P. 94–95.
8. Avron A., Zamansky A. Non-deterministic
semantics for logical systems, in Handbook of
Philosophical Logic, D.M. Gabbay, F.
Guenthner (eds.), 2nd ed., vol. 16, (2011),
Springer Netherlands. P. 227–304.
References
1. Nikitchenko M. and Shkilniak S. (2008).
Mathematical logic and theory of algorithms.
Кyiv: VPC Кyivskyi Universytet (in ukr).
2. Nikitchenko M. and Shkilniak S. (2013).
Applied logic. Кyiv: VPC Кyivskyi
Universytet (in ukr).
3. Nikitchenko M. and Shkilniak S. (2015).
Semantic Properties of Logics of Quasiary
Predicates. In Workshop on Foundations of
Informatics: Proceedings FOI-2015.
Chisinau, Moldova. P. 180–197.
4. Shkilniak S. and Volkovytskyi D. (2016).
Renominative logics of quasiary predicates. In
Computer mathematics. 1, P. 46–57 (in ukr).
5. Nikitchenko M., Shkilniak O. and Shkilniak
S. (2016). Pure first-order logics of quasiary
predicates. In Problems in Progamming. N 2–
3. P. 73–86 (in ukr).
Теоретичні та методологічні основи програмування
21
6. Nikitchenko M. and Shkilniak S. (2017).
Algebras and logics of partial quasiary
predicates. In Algebra and Discrete
Mathematics. Vol. 23. N 2. P. 263–278.
7. Nikitchenko M., Shkilniak O. and
Shkilniak S. (2017). Logics of partial non-
deterministic predicates. In International
conference PDMU-2017: abstracts. Vilnius,
Lithuania. P. 94–95.
8. Avron A. and Zamansky A. (2011). Non-
deterministic semantics for logical systems. In
Handbook of Philosophical Logic,
D.M. Gabbay, F. Guenthner (eds.), 2nd ed.,
vol. 16, Springer Netherlands. P. 227–304.
Одержано 01.12.2017
Про авторів:
Нікітченко Микола Степанович,
доктор фізико-математичних наук,
професор, завідувач кафедри Теорії
та технології програмування.
Кількість наукових публікацій в
українських виданнях – понад 250,
у тому числі у фахових виданнях –
понад 110.
Кількість наукових публікацій в
зарубіжних виданнях – понад 50.
Scopus Author ID: 6602842336.
H-індекс (Google Scholar): 10 (8 з 2012).
http://orcid.org/0000-0002-4078-1062.
Шкільняк Оксана Степанівна,
кандидат фізико-математичних наук,
доцент, доцент кафедри
інформаційних систем.
Кількість наукових публікацій в
українських виданнях – 90, у тому числі
у фахових виданнях – 33.
Кількість наукових публікацій в
зарубіжних виданнях – 10.
http://orcid.org/0000-0003-4139-2525.
Шкільняк Степан Степанович,
доктор фізико-математичних наук,
професор, професор кафедри Теорії
та технології програмування.
Кількість наукових публікацій в
українських виданнях – понад 230,
у тому числі у фахових виданнях –
понад 100.
Кількість наукових публікацій в
зарубіжних виданнях – 17.
H-індекс (Google Scholar): 6 (6 з 2012).
http://orcid.org/0000-0001-8624-5778.
Місце роботи авторів:
Київський національний університет
імені Тараса Шевченка,
01601, Київ, вул. Володимирська, 60.
Тел.: (044) 259 05 19.
E-mail: me.oksana@gmail.com
http://orcid.org/0000-0001%20-8624-5778
|
| id | pp_isofts_kiev_ua-article-227 |
| institution | Problems in programming |
| keywords_txt_mv | keywords |
| language | English |
| last_indexed | 2026-03-12T23:16:57Z |
| publishDate | 2018 |
| publisher | PROBLEMS IN PROGRAMMING |
| record_format | ojs |
| resource_txt_mv | ppisoftskievua/39/ab1daa29cca1f2dab2f77afc00351539.pdf |
| spelling | pp_isofts_kiev_ua-article-2272024-12-15T19:12:21Z Algebras of general non-deterministic predicates Алгебры общих недетерминированных предикатов Алгебри загальних недетермінованих предикатів Nikitchenko, M.S. Shkilniak, O.S. Shkilniak, S.S. logic; algebra; non-deterministic predicate; logical consequence UDC 004.42:510.69 логика; алгебра; недетерминированный предикат; логическое следствие УДК 004.42:510.69 логіка; алгебра; недетермінований предикат; логічний наслідок УДК 004.42:510.69 Logics of general nondeterministic qua-siary predicates, called GND-predicates, are defined and investigated. These logics are program-oriented logical for-malisms that reflect such properties of programs as partiality, nondeterminism, and non-fixed arity. GND-predicates generalize partial predicates of the rela-tional type. The main attention is paid to the construction of composition algebras of GND-predicates. Compositions of GND-predicates are described, their properties are formulated. For these predicates, such important laws of tradi-tional logic as the law of absorption and the law of distributivity for for and are not valid. Various types of GND-predicates are identified. GND-predicates can be modeled as 7-value total deter-ministic predicates (TD7-predicates). A 7-element algebra of truth values of TD7-predicates is defined and all of its subalgebras are described. Each such subalgebra induces a corresponding al-gebra of TD7-predicates, which then in-duces the algebra of GND-predicates. This makes possible to identify a number of important composition algebras of general nondeterministic predicates. The languages of pure first-order logics of GND-predicates and their interpretations are described. The relations of a logical G-consequence and a logical G-equivalence are introduced. The relation of the logical G-consequence is mono-tonic, reflexive, and transitive; for it the properties of the decomposition of for-mulas are satisfied. On the basis of these properties, it is planned to construct cal-culi of sequential type for the logic of GND-predicates.Problems in programming 2018; 1: 05-21 Предложены и исследованы новые программно-ориентированные логические формализмы – логики общих недетерминированных квазиарных предикатов, названных GND-предикатами. Эти предикаты являются обобщением частичных неоднозначных предикатов реляционного типа. Основное внимание уделено построению композиционных алгебр GND-предикатов. Выделены разновидности таких предикатов, описаны их композиции. GND-предикаты можно моделировать как 7-значные тотальные детерминированные – ТD7-предикаты. Выделена 7-элементная алгебра истинностных значений TD7-предикатов, описаны все ее подалгебры. Каждая такая подалгебра индуцирует соответствующую алгебру TD7-предикатов, которая далее индуцирует алгебру GND-предикатов. Это позволило выделить ряд важных композиционных алгебр общих недетермини-рованных предикатов. Описаны языки чистых первопорядковых логик GND-предикатов, их интерпретации. Введены отношения логического G-следствия и логической G-эквивалентности. Отношение логического G-следствия является монотонным, рефлексивным и транзитивным, для него выполняются свойства декомпозиции формул. На основе этих свойств для логик GND-предикатов планируется построение исчислений секвенциального типа.Problems in programming 2018; 1: 05-21 Запропоновано та досліджено логіки загальних недетермінованих квазіарних предикатів – GND-предикатів. Такі предикати є узагальненням часткових неоднозначних предикатів реляційного типу. Основна увага приділена побудові композиційних алгебр GND-предикатів. Виділено різновиди GND-предикатів,показано їх зв'язок із 7-значними тотальними детермінованими предикатами. Виділено 7-елементну алгебру істиннісних значень цих предикатів, описано усі її підалгебри. Такі підалгебри індукують відповідні алгебри GND-предикатів. Описано мови чистих першопорядкових логік GND-предикатів та їх інтерпретації. Введено та досліджено відношення логічного G-наслідку.Problems in programming 2018; 1: 05-21 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2018-10-09 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/227 10.15407/pp2018.01.005 PROBLEMS IN PROGRAMMING; No 1 (2018); 5-21 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 1 (2018); 5-21 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 1 (2018); 5-21 1727-4907 10.15407/pp2018.01 en https://pp.isofts.kiev.ua/index.php/ojs1/article/view/227/222 Copyright (c) 2018 PROBLEMS OF PROGRAMMING |
| spellingShingle | logic algebra non-deterministic predicate logical consequence UDC 004.42:510.69 Nikitchenko, M.S. Shkilniak, O.S. Shkilniak, S.S. Algebras of general non-deterministic predicates |
| title | Algebras of general non-deterministic predicates |
| title_alt | Алгебры общих недетерминированных предикатов Алгебри загальних недетермінованих предикатів |
| title_full | Algebras of general non-deterministic predicates |
| title_fullStr | Algebras of general non-deterministic predicates |
| title_full_unstemmed | Algebras of general non-deterministic predicates |
| title_short | Algebras of general non-deterministic predicates |
| title_sort | algebras of general non-deterministic predicates |
| topic | logic algebra non-deterministic predicate logical consequence UDC 004.42:510.69 |
| topic_facet | logic algebra non-deterministic predicate logical consequence UDC 004.42:510.69 логика алгебра недетерминированный предикат логическое следствие УДК 004.42:510.69 логіка алгебра недетермінований предикат логічний наслідок УДК 004.42:510.69 |
| url | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/227 |
| work_keys_str_mv | AT nikitchenkoms algebrasofgeneralnondeterministicpredicates AT shkilniakos algebrasofgeneralnondeterministicpredicates AT shkilniakss algebrasofgeneralnondeterministicpredicates AT nikitchenkoms algebryobŝihnedeterminirovannyhpredikatov AT shkilniakos algebryobŝihnedeterminirovannyhpredikatov AT shkilniakss algebryobŝihnedeterminirovannyhpredikatov AT nikitchenkoms algebrizagalʹnihnedetermínovanihpredikatív AT shkilniakos algebrizagalʹnihnedetermínovanihpredikatív AT shkilniakss algebrizagalʹnihnedetermínovanihpredikatív |