Compositional-nominative logics over hierarchical data
New logics more adequate for property descriptions of functions and predicates over hierarchical data are constructed. A characteristic fea-ture of such logics is use of composite names in their languages. Semantic properties of such logics are investigated, corresponding sequent calculi are defined...
Gespeichert in:
| Datum: | 2026 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Ukrainisch |
| Veröffentlicht: |
PROBLEMS IN PROGRAMMING
2026
|
| Schlagworte: | |
| Online Zugang: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/864 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Problems in programming |
| Завантажити файл: |  |
Institution
Problems in programming| _version_ | 1866844880388489216 |
|---|---|
| author | Nikitchenko, M.S. Shkilniak, S.S. |
| author_facet | Nikitchenko, M.S. Shkilniak, S.S. |
| author_institution_txt_mv | [
{
"author": "M.S. Nikitchenko",
"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 | 2026-06-01T06:02:58Z |
| description | New logics more adequate for property descriptions of functions and predicates over hierarchical data are constructed. A characteristic fea-ture of such logics is use of composite names in their languages. Semantic properties of such logics are investigated, corresponding sequent calculi are defined.Problems in programming 2010; 2-3: 48-57 |
| first_indexed | 2026-06-02T01:00:15Z |
| format | Article |
| fulltext |
Теоретичні та методологічні основи програмування
© М.С. Нікітченко, С.С. Шкільняк, 2010
48 ISSN 1727-4907. Проблеми програмування. 2010. № 2–3. Спеціальний випуск
УДК 004.4
КОМПОЗИЦІЙНО-НОМІНАТИВНІ ЛОГІКИ
НАД ІЄРАРХІЧНИМИ ДАНИМИ
М.С. Нікітченко, С.С. Шкільняк
Київський національний університет імені Тараса Шевченка,
01601, Київ, вул. Володимирська, 60
Тел.: (044) 259 0519
E-mail: ttp@unicyb.kiev.ua
Будуються нові логіки, які дозволяють більш адекватно описувати властивості предикатів та функцій, визначених над ієрархічними
даними. Характерною властивістю цих логік є використання в їх мовах складних імен. Вивчаються семантичні властивості таких
логік та визначаються відповідні числення секвенційного типу.
New logics more adequate for property descriptions of functions and predicates over hierarchical data are constructed. A characteristic fea-
ture of such logics is use of composite names in their languages. Semantic properties of such logics are investigated, corresponding sequent
calculi are defined.
Вступ
Математична логіка є одним з наріжних каменів, на яких грунтується теорія програмування. Це означає,
що поняття і методи логіки знаходять своє найширше використання у дослідженнях програм, що яскраво
підтверджують багатомні видання із застосувань логіки в інформатиці (див., напр., [1]). Таке використання
логіки має і зворотній вплив, а саме, теорія програмування вимагає змін в логіці щоб зробити її більш близькою
та адекватною до програмування. Одним з підходів у цьому напрямку є композиційно-номінативний підхід
(КНП) до побудови моделей програм та орієнтованих на них логік [2–5]. Підхід задає принципи визначення та
дослідження формальних мов програм та логік. Суть підходу, стисло кажучи, полягає в наступному:
– семантичний аспект мови є провідним, синтаксичний – похідним; тому спочатку визначаються та
досліджуються семантичні аспекти, а потім – синтаксичні;
– семантичні аспекти уточнюються за допомогою композиційно-номінативних систем, які визначають
структури даних, функцій (зокрема, предикатів) та композицій; такі системи можна подавати у вигляді двох
семантичних алгебр – алгебри даних та алгебри функцій (предикатів);
– дані уточнюються як номінативні – ієрархічні дані, побудовані на базі відношення ім‟я значення;
– основні структури даних мов програмування можна подати як конкретизації номінативних даних [6];
– властивості семантичних алгебр індукують синтаксичні аспекти мов;
– побудова мов іде в напрямку від абстрактного до конкретного, що приводить до мов різного рівня
абстракції та загальності.
Для розбудови нових типів логік на підставі КНП слід проаналізувати структуру класичної логіки. Такий
аналіз проведено в [4]. Його результати (стосовно теми статті) можна подати таким чином:
– у мові логіки виділяються два типи символів: логічні, до яких належать символи логічних зв‟язок і
кванторів, та дескриптивні (предметні), до яких належить символи предметних змінних, предикатів та функцій;
– предметна область подається алгебраїчною системою, носієм якої є множина предметних констант
(атомів), а операціями – предметні функції та предикати; таку систему можна розглядати як алгебру даних;
інтерпретація дескриптивних символів задається окремо для кожної предметної області;
– логічні символи мають фіксовану інтерпретацію, незалежну від вибору предметної області, тому в КНП
логічні символи інтерпретуються як композиції, які є операціями алгебри предикатів.
Таким чином, логіки першого порядку фактично засновані на алгебрах атомарних, неструктурованих
даних. Тому при застосуванні класичної логіки першого порядку до програм над складними, ієрархічними
даними виникає певна невідповідність між мовою логіки, яка дозволяє працювати лише з атомарними даними,
та мовою програм, яка працює з ієрархічними даними. Для подолання такої невідповідності класична логіка має
певні механізми, які дозволяють промоделювати складні дані через атомарні. Але при цьому значні зусилля
витрачаються на саме моделювання, а також на дослідження його властивостей, які потрібно подати за
допомогою певної аксіоматики, визначити її коректність, повноту тощо. Цих складнощів можно уникнути,
побудувавши логіку, безпосередньо засновану на алгебрах ієрархічних даних. Це і є метою даної статті.
Стаття побудована наступним чином: у першому розділі вводяться поняття на визначення ієрархічних
даних, у другому – операції над такими даними, третій розділ присвячено композиціям. У четвертому розділі
описуються семантичні моделі та відповідні мови логік, п‟ятий розділ присвячено визначенню секвенційного
числення для однієї з побудованих логік. Поняття, які тут не визначаються, будемо тлумачити в сенсі роботи [5].
Теоретичні та методологічні основи програмування
49
1. Основні поняття та визначення
Основним поняттям логіки з семантичного погляду є поняття предиката.
У загальному випадку під предикатом на множині D будемо розуміти довільну часткову функцію вигля-
ду P : D {T, F}. У даній роботі будемо розглядати однозначні часткові предикати.
Областю істинності та областю хибності однозначного предиката Р на D назвемо множини
T(P) = {dD | P(d) = T} та F(P) = {dD | P(d) = F}.
Предикат P на D неспростовний, або частково істинний, якщо F(P) = .
Номінативні дані можна трактувати як ієрархічно побудовані об‟єкти, в основі яких лежить бінарне від-
ношення ім’я значення. Найпростішим випадком номінативних даних є однорівневі номінативні дані, які
звичайно називають [5] іменними множинами.
Нехай A та V – непорожні множини, які трактуємо як множину базових імен та множину базових значень.
V-іменною множиною (V-ІМ) над A називають [5] довільну однозначну функцію
:
V
A.
V-ІМ подаємо у вигляді [v1a1,...,vnan,...]. Тут vіV, aіA, vі vj при і j.
У загальному випадку номінативних даних іменування можна продовжити на складні дані, а не тільки
базові. На відміну від [6], при побудові складніших номінативних даних із простіших тут не будемо використо-
вувати кроки побудови за типом множини.
Множину ієрархічних номінативних даних ND(V, A) над множиною базових імен V та множиною базових
значень A визначаємо індуктивно наступним чином.
ND0(V, A) = { }A – номінативні дані рангу 0;
NDk+1(V, A) = ( ( , ))
n
kA V ND V A – номінативні дані рангу k+1.
Тоді ND(V, A) =
0
( ( , ))
n
k
k
V ND V A
.
Тут ( , )
n
kV ND V A – множина всіх однозначних відображень із V в NDk(V, A).
Однозначність таких відображень гарантує однозначність іменування.
Визначимо також множину HD(V, A) = ND(V, A) \ A іменованих ієрархічних номінативних даних.
Для складного імені u = y1.y2. … .yn запис d(u) буде означати (…(d(y1)(y2))…(yn). Надалі для більшої вираз-
ності замість d(u) будемо в стилі функцій розіменування писати u(d). Таке u(d) – це ієрархічне дане, що є ком-
понентою даного d, яка поіменована в d іменем u. Для складного імені u = y1.y2. … .yn запис u(d) означатиме
yn(…(y2(y1(d)))…).
Компоненту ієрархічного даного, подану у вигляді xu(), у випадку невизначеності значення імені u
(позначаємо u()) будемо опускати.
Ієрархічні номінативні дані можна подавати різними способами. Будемо використовувати тут текстовий,
або лінійний спосіб, та графічний спосіб.
Приклад 1. Розглянемо ієрархічне дане, текстовий запис якого має наступний вигляд:
[ x [ x [ x 0, y 2, z 0], z 1], y 0, z [ x 1, y [ x 1, y 2], z 3]].
Таке дане можна записати в структурованішому вигляді:
[ x [ x [ x 0,
y 2,
z 0],
z 1],
y 0,
z [ x 1,
y [ x 1,
y 2],
z 3]].
При графічному способі ієрархічне дане подаємо у вигляді орієнтованого дерева, ребра якого помічаємо
іменами, а кінцеві вершини (листки) помічаємо базовими значеннями. Однозначність іменування означає, що
всі ребра, які виходять з однієї вершини, помічаються різними іменами.
Фактично таке дерево прочитується із другого запису: корінь дерева – зліва, листки – справа.
Ієрархічні дані можна трактувати як номінативні дані зі складними іменами – елементами множини V
+
.
Інакше кажучи, складними іменами є непорожні слова в алфавіті V, вони утворюються конкатенацією базових
імен при русі по дереву з кореня до листків. Операцію конкатенації будемо позначати символом ”.”.
Приклад 2. Ієрархічне дане прикладу 1 можна перетворити у такі дані зі складними іменами:
[ x.x [ x 0, y 2, z 0], x.z 1, y 0, z.x 1, z.y [ x 1, y 2], z.z 3];
[ x.x.x 0, x.x.y 2, x.x.z 0, x.z 1, y 0, z.x 1, z.y.x 1, z.y.y 2, z.z 3].
Останнє, 1-рівневе подання – це, фактично, іменна множина зі складними іменами.
Форму подання ієрархічних даних у вигляді іменної множини зі складними іменами назвемо лінійною
нормальною формою (ЛНФ).
Теоретичні та методологічні основи програмування
50
Зважаючи на однозначність іменування для кожного ієрархічного даного всі (складні) імена його лінійної
нормальної форми мусять бути різними, більше того, вони будуть непорівнянними (визначення див. далі).
Формально кажучи, ієрархічне дане прикладу 1 та ієрархічні дані прикладу 2 мають різну структуру іме-
нування, проте в даній роботі будемо абстрагуватись від такої структури і вважатимемо всі наведені в цих при-
кладах ієрархічні дані еквівалентними, а дослідження таких даних та предикатів над ними будемо проводити з
точністю до еквівалентності ієрархічних даних.
Ієрархічні дані d1 та d2 назвемо еквівалентними, якщо d1 та d2 мають однакові ЛНФ.
Приймаючи таку еквівалентність, замість x.y можна писати x y і навпаки.
Для складних імен природним чином вводиться поняття префікса. Префіксом слова uV
+
назвемо кожне
слово x таке, що u = x.y для деякого yV*. Якщо при цьому u x, то x назвемо власним префіксом слова u.
Будемо писати x u, якщо x є префіксом слова u. Якщо x є власним префіксом слова u., то пишемо x u.
Слова x та u назвемо префікс-порівнянними, або просто порівнянними, якщо x u або u x; інакше такі
слова назвемо префікс-непорівнянними, або просто непорівнянними.
Будемо писати xu, якщо x та u – порівнянні; пишемо x u, якщо x та u – непорівнянні.
Поширимо непорівнянність на множини імен: писатимемо X Y, якщо x y для всіх xX та yY.
Для складних імен як слів можна ввести операцію x / ділення на ім‟я x зліва:
x / u – це ім‟я y таке, що u = x.y, якщо x є префіксом u, інакше x / u невизначене.
Для ієрархічних даних визначимо множини головних та термінальних імен.
Неформально кажучи, головне ім‟я – це складне ім‟я ієрархічного даного, які прочитуємо при русі по де-
реву від кореня. Якщо при цьому добираємось до листка, то таке ім‟я – термінальне.
Множиною головних імен ієрархічного даного d назвемо множину hn(d) = {u | u(d)}.
Множиною термінальних імен ієрархічного даного d назвемо множину tn(d) = {u | u(d)A}.
Інакше кажучи, tn(d) скдадається з усіх імен лінійної нормальної форми даного d, потрактованої як ІМ;
hn(d) складається з усіх імен лінійної нормальної форми даного d та їх префіксів.
Ієрархічні дані d1 та d2 назвемо диз‟юнктними, якщо для довільних xtn(d1) та ytn(d2) маємо x y.
Надалі “+” будемо позначати операцію об‟єднання двох диз‟юнктних ієрархічних даних.
Тоді можна записати наступну властивість ієрархічних даних: [ x ( + ), ] = [ x , x , ].
2. Операції над ієрархічними даними
Над ієрархічними номінативними даними введемо операції видалення компонент із заданою умовою на
імена, накладення та реномінації.
Параметричну операцію |–х видалення компонент з префікс-іменем х задамо так:
|–х (d) = [u d | х не є префіксом u].
Узагальнимо операцію |–х до операції
1,...,|
nx x :
1,...,| ( )
nx x d = [u d | жодне з імен х1,..., хn не є префіксом u].
Для ієрархічних даних в ЛНФ це означає видалення компонент, для імен яких принаймі одне з х1,..., хn є
префіксом.
Окрім операції
1,...,|
nx x видалення компонент за умовою на префікси імен, задамо операції видалення
компонент за більш сильною умовою префікс-порівнянності імен. Необхідність їх введення зумовлена тим, що
не завжди додавання до |–х (d) компоненти з іменем х є можливим через порушення однозначності іменування.
Приклад 3. Нехай d = [ x 1, z.x 0, z.y 1]. Тоді |–х.y (d) = d, але додавання до d компоненти з іменем х.y
не є коректним.
Параметричну операцію ||–х видалення компонент з іменами, порівнянними з іменем х, задамо так:
||–х (d) = [ ua d | х та термінальне u не є порівнянними].
Узагальнимо операцію ||–х до операції
1,...,||
nx x :
1,...,|| ( )
nx x d = [ ua d | жодне з імен х1,..., хn не є порівнянним з термінальним іменем u].
Для базових даних aA будемо вважати
1,...,|| ( )
nx x a невизначеним.
Замість ||–х (d) та
1,...,|| ( )
nx x d будемо надалі писати d ||–х та
1,...,||
nx xd .
Приклад 4. Нехай d – ієрархічне дане прикладу 1. Тоді:
||–х (d) = [ y 0, z [ x 1, y [ x 1, y 2], z 3]]; ||–х.х, y.z, z.z (d) = [ x [z 1], z [ x 1, y [ x 1, y 2]]].
При поданні d в ЛНФ маємо:
||–х (d) = [ y 0, z.x 1, z.y.x 1, z.y.y 2, z.z 3]; ||–х.х, y.z, z.z (d) = [ x.z 1, z.x 1, z.y.x 1, z.y.y 2].
Неважко переконатись, що додавання до
1,...,|| ( )
nx x d компонент з іменами х1,..., хn є коректним, воно не
порушує однозначність іменування.
Теоретичні та методологічні основи програмування
51
Надалі для спрощення запису при використанні символа операції “+” будемо опускати зрозумілі з кон-
тексту дужки “[” та “]”. Наприклад, замість d ||–u + [uu(d) ||–v] будемо писати d ||–u + uu(d) ||–v .
Розглянемо властивості операції
1,...,||
nx x . Для такої операції, зокрема, маємо “поглинання” конкретнішо-
го імені загальнішим, яке є префіксом конкретнішого імені.
Твердження 1. Для ієрархічних даних маємо:
1) нехай z u; тоді
1, , ,...,||
nz u x xd
1, ,...,||
nz x xd ;
2) (d ||–х)||–х.y = (d ||–х.y)||–х = d ||–х ;
3) (d1 + d2)||–u = d1||–u + d2||–u ;
4) d ||–u.v = d ||–u + [uu(d) ||–v];
5) d d ||–u + uu(d);
6) для простого імені xV маємо d = d ||– x + xx(d).
Приклад 5. Для складного імені u властивість d = d ||–u + uu(d) може не виконуватись. Справді, нехай
d = [ u 1, y.x 1, y.y 2]. Тоді d ||–u.v = [ y.x 1, y.y 2], u.v(d), адже u(d)A, звідки d ||–u.v + u.vu.v(d) = d ||–u.v d.
Для ієрархічних даних можна переходити від послідовного до паралельного видалення та навпаки. Для
випадку видалення порівнянних імен маємо ефект “поглинання”, див. твердження 1. В інших випадках маємо
Твердження 2. Нехай u {х1,..., хn}; тоді
1 1, ,..., ,...,|| ( || ) ||
n nu x x u x xd d .
Зокрема, якщо z u, то d ||–u, z = (d ||–u)||–z = (d ||–z)||–u .
Твердження 3. Для ієрархічних даних маємо
1 1,..., / ,..., /( ) || ||
n z z nx x x xz d z d .
Приклад 6. Нехай y та z відрізняються префіксами – простими іменами; тоді d ||–x.y, x.z = d ||–x + xx(d) ||–y, z .
Твердження 4. Для ієрархічних даних маємо:
1)
1,...,( || )
nz zx d x h h ;
2)
1,...,( || ) ( )
nz zx d x d , якщо x {z1,..., zn};
3)
1, ,...,( || )
nx z zx d .
Для кожного ієрархічного даного d можна подати
1,...,||
nx xd в певній стандартній формі, використовуючи
тільки операції видалення компонент вигляду
1,...,||
mv v із простими іменами v1,..., vmV, а також операції +, іме-
нування v та застосування d до імені, яке можна трактувати як розіменування u1(u2(... uk(d)…), де u1,..., ukV.
Для цього спочатку виділяємо в іменах х1,..., хn прості імена-префікси та розписуємо згідно тверджень
2, 4, 5, проводячи спрощення згідно твердження 1.
Наприклад, нехай х1 = v.y. Тоді маємо
2 2 2. , ,..., . ,..., ,...,|| ( || ) || ( || ( ) || ) ||
n n nv y x x v y x x v y x xd d d v v d =
2 2 2 2, ,..., ,..., , ,..., , / ,..., /|| ( ( ) || ) || || ( ) ||
n n n v v nv x x y x x v x x y x xd v v d d v v d . Далі розписуємо аналогічно згідно ви-
ділених простих імен-префіксів для х2,..., хn , після чого поступово розписуємо операції видалення компонент в
поіменованих цими префіксами даних, таких як отримане на першому кроці
2, / ,..., /( ) ||
v v ny x xv d , і т.д. Принагід-
но проводимо спрощення згідно твердження 1.
Приклад 7. d ||–v.x, v.y, u.x.y = (d ||–v + vv(d)||–x)||–v.y, u.x.y = d ||–v, v.y, u.x.y + (vv(d))||–x, y = d ||–v, u.x.y + vv(d)||–x, y =
= (d ||–u.x.y)||–v + vv(d)||–x, y = (d ||–u + uu(d)||–x.y)||–v + vv(d)||–x, y = d ||–u, v + (uu(d)||–x.y)||–v + vv(d)||–x, y =
= d ||–u, v + u(u(d)||–x + xx(u(d))||–y) + vv(d)||–x, y = d ||–u, v + vv(d)||–x, y + uu(d)||–x + uxx(u(d))||–y .
Операцію накладення для випадку ієрархічних даних задамо так: d h = h + d ||–tn(h) .
Це означає, що для кожного термінального імені x ієрархічного даного h із d видаляємо всі компоненти
вигляду ua, де aA, x u чи u x, після отримане ієрархічне дане об‟єднуємо із h.
Задамо тепер на множині ієрархічних даних важливу операцію реномінації.
Параметризовану за іменами операцію реномінації 1
1
,...,
,...,
n
n
v v
x x
r : HD(V, A) HD(V, A) визначимо так:
1
11
,...,
,..., 1 1,...,
( ) || ( ) ... ( )n
nn
v v
v v n nx x
r d d v x d v x d .
При цьому має виконуватися така умова коректності: усі імена v1,..., vn попарно не є порівнянними.
Операція реномінації монотонна в наступному смислі: якщо d h, то 1 1
1 1
,..., ,...,
,..., ,...,
( ) ( )n n
n n
v v v v
x x x x
r d r h .
Приклад 8. Не завжди .
. ( )u v
u vr d d : . .
. . .([ 1, . 0]) ([ 1, . 0]) [ 1, . 0] ||u v u v
u v u v u vr u x y r u x y u x y
. . ([ 1, . 0]) [ . 0] . . ([ 1, . 0] [ . 0],u v u v u x y x y u v u v u x y x y адже . ([ 1, . 0])u v u x y .
Теоретичні та методологічні основи програмування
52
Використовучи подання
1,...,||
nx xd в стандартній формі, операцію реномінації теж подамо в аналогічному
стандартному вигляді, використовуючи операції
1,...,||
mv v із простими іменами v1,..., vmV, операції +, іменуван-
ня v та потрактоване як розіменування u1(u2(... uk(d)…), де u1,..., ukV, а також застосування d до імені.
Приклад 9. Використовуючи (приклад 7) стандартне подання d ||–v.x, v.y, u.x.y , отримуємо: . , . , . .
. , . , . ( )v x v y u x y
u y y x v xr d
= d ||–u, v + vv(d)||–x, y + uu(d)||–x + uxx(u(d))||–y + vxy(u(d)) + vyx(y(d)) + uxyx(v(d)).
Для логіки квазіарних предикатів, заданими над іменними множинами з простими іменами можна вико-
нувати згортку композицій реномінації. Фактично це означає, що ми можемо описати застосування операції
реномінації до даного, утвореного застосуванням операції реномінації, у вигляді однієї операції реномінації,
1 1 1 1
1 1 1 1
,..., ,..., ,..., ,...,
,..., ,..., ,..., ,...,
( ( )) ( )n m n m
n n n n
v v u u v v u u
x x y y x x y y
r r d r d . Детальніше про згортку реномінацій див. [5]. Проте використання в ре-
номінаціях складних імен робить в загальному випадку таке подання неможливим, про що легко пересвідчи-
тись, розглядаючи приклад 9. Обійтися тут однією операцією вигляду 1
1
,...,
,...,
n
n
v v
x x
r без використання операцій
1,...,||
my y неможливо, адже складні імена v1,..., vn та x1,..., xn можуть складатися тільки з простих імен x, u, v, z.
Для запису згортки реномінацій зі складними іменами будемо використовувати подання операції реномі-
нації в стандартній формі.
Приклад 10. Маємо . .( ( )) ( || ( )) ( || ( )) || ( ( || ( )))z u z
u v x u v u u z ur r d r d u x d d u x d z v u d u x d
,
, . ,|| ( )) ( ( )) ( )z u
u z x v xd u x d z v x d r d .
Приклад 11.
.
.( ( )) ( || . ( )) ( || ( ) || . ( )) || ( ),z u v z z
u x u u v u u v zr r d r d u v x d r d u u d u v x d z u
де || ( ) || . ( )u vd u u d u v x d .
Далі маємо ,|| ( ) || ( ) ( ) || ( )z u z vz u d u v x d z u d z v x d . Подати цей вираз у
вигляді однієї реномінації неможливо.
Приклад 12. Розпишемо . , .
, . .( ( ))u v z x v
x x y z yr r d : . , . . ,
, . . , .( ( )) ( || ( ) || . ( ))u v z x v u v z
x x y z y x x y x vr r d r d x x d x v z y d
. ,|| ( ) . ( ),u v z u v x z x y де || ( ) || . ( )x vd x x d x v z y d . Тоді маємо ( ) ( )u u d ,
( ( )) ( ( )).y x y x d Стандартне подання: . , .
, . . ,( ( )) || ( ) || ( ) ( ( ))u v z x v
x x y z y u z zr r d u u u v x z y x
, ,|| ( ) || ( ) || ( ( )) ( ( )) ( ) || ( ( )).u z x z v vd u u d u v x d u v v y z d z y x x x d x v y z d
3. Композиції предикатів над ієрархічними даними
Композиції визначають універсальні методи побудови предикатів, вони виступають ядром логіки певно-
го типу. Згідно композиційно-номінативного підходу [2] композиції уточнюємо як функції (операції) над іме-
нованими предикатами.
Hа пропозиційному рівні дані трактуються як абстрактні, тому предикати також трактуються як абстра-
ктні, тобто як функції вигляду Р : D {T, F}, де D – абстрактна множина.
Композиції пропозиційного рівня називають логiчними зв‟язками. Основними логічними зв‟язками є 1-
арна композиція заперечення та бінарні диз‟юнкція , кон‟юнкція &, імплікація , еквіваленція .
Композиції та називають базовими пропозиційними композиціями.
На номінативних рівнях дані будуються із множин предметних імен та предметних значень. Такі дані на-
зивають номінативними. Функції та предикати, задані на номінативних даних, називають квазіарними.
Логіки квазіарних предикатів, заданих на іменних множинах – однорівневих номінативих даних – деталь-
но досліджені в [5]. Для таких логік були виділені наступні підрівні: реномінативний, кванторний, кванторно-
екваційний, функціональний та функціонально-екваційний.
У даній роботі досліджуються логіки часткових предикатів, заданих на описаних в попередньому розділі
ієрархічних номінативних даних. Такі предикати теж називатимемо квазіарними.
Функцію вигляду Р : HD(V, A) {T, F} назвемо квазіарним предикатом на HD(V, A).
Квазіарні предикати на HD(V, A) будемо також називати (V, A)-квазіарними.
Множину квазіарних предикатів на HD(V, A) позначимо Pr
V_А
.
Ім'я xV строго неістотне для квазіарного предиката P на HD(V, A), якщо для довільних d, HD(V, A)
маємо P(d ||–x + x) = P(d ||-х).
V-квазіарний предикат P :
HD(V, A) {T, F} назвемо еквітонним, якщо для довільних d, d'HD(V, A) із
умови d d' та P(d) випливає P(d') = P(d).
Будемо тут розглядати логіки квазіарних предикатів над ієрархічними номінативними даними на реномі-
нативному та кванторному рівнях.
На реномінативному рівні базовими композиціями є , та реномінація 1
1
,...,
,...,
n
n
v v
x x
R .
Теоретичні та методологічні основи програмування
53
Відмінність композиції реномінації 1
1
,...,
,...,
n
n
v v
x x
R для предикатів над ієрархічними номінативними даними від
традиційної композиції реномінації [5] для предикатів над однорівневими номінативними даними (іменними
множинами) полягає найперше у тому, що імена v1,..., vn та x1,..., xn можуть бути складними. Як і в традиційному
випадку [5], композицію реномінації визначаємо через операцію реномінації на даних.
1-арна параметрична композиція реномінації 1
1
,...,
,...,
n
n
v v
x x
R кожному (V, A)-квазіарному предикату Q зіставляє
(V, A)-квазіарний предикат 1
1
,...,
,...,
( ),n
n
v v
x x
R Q значення якого для кожного dHD(V, A) задається так:
1 1
1 1
,..., ,...,
,..., ,...,
( )( ) ( ( ))n n
n n
v v v v
x x x x
R Q d Q r d .
Зрозуміло, що тоді 1
11
,...,
,..., 1 1,...,
( )( ) ( || ( ) ... ( ))n
nn
v v
v v n nx x
R Q d Q d v x d v x d .
Введемо позначення вигляду y для y1,..., yn . Тоді замість 1
1
,...,
,...,
n
n
v v
x x
r та 1
1
,...,
,...,
n
n
v v
x x
R будемо писати v
xr та v
xR .
Розглянемо основні властивості композицій v
xR .
R) ( ) ( )v v
x xR P R P ;
R) ( ) ( ) ( )v v v
x x xR P Q R P R Q .
Аналогічно записуються властивості R, R&, R.
RR) ( ( )( ) ( ( ( )))v u u v
x y y xR R P d P r r d для кожного dHD(V, A).
RSN) Нехай ім„я уV строго неістотне для предиката Р; тоді
,
, ( ) ( )
y v v
xz xR P R P .
RT) ,
, ( ) ( )z v v
z x xR P R P при умові zV.
Враховуючи п. 5 твердження 1, у випадку еквітонних предикатів для складних імен маємо:
RTE) ,
, ( ) ( )u v v
u x xR P R P (тут означає рівність з точністю до визначеності, див. [5]).
На кванторному рівні базовими композиціями є , , 1
1
,...,
,...,
n
n
v v
x x
R , x.
Дамо визначення 1-арних параметричних композицій квантифікації x та x. На відміну від традиційно-
го випадку [5], кванторне ім‟я x може бути складним, крім того, квантифікацію можна вести як за всіма ієрархі-
чними даними, так і за базовими даними. В даній роботі розглядаємо тільки квантифікацію за базовими даними.
Предикати x(P) та x(P) будемо позначати xP та xP. Зазначені предикати задамо так:
, якщо існує : ( || ) ,
( ) , якщо ( || ) для всіх ,
невизначене в усіх інших випадках.
x
x
T b A P d x b T
xP d F P d x a F a A
, якщо існує : ( || ) ,
( ) , якщо ( || ) для всіх ,
невизначене в усіх інших випадках.
x
x
F b A P d x b F
xP d T P d x a T a A
Наведемо основні властивості композицій x та x.
1. Якщо x та у непорівнянні, то xуР = ухР та xуР = ухР.
2. хР = хР; хР = хР.
3. хР хQ = х (РQ); хР & xQ = х (Р&Q).
4. Поглинання зовнішнього квантора внутрішнім за тим же іменем:
xхР = хР; xхР = хР; xхР = хР; xхР = хР.
Вищенаведені властивості справджуються як для простих, так і для складних імен.
Наведемо специфічні властивості поглинання для складних порівнянних імен.
5. Поглинання зовнішнього квантора внутрішнім за загальнішим іменем:
x.ухР = хР; x.ухР = хР; x.ухР = хР; x.ухР = хР.
6. xх.уР = xх.уР хР; xх.уР х.уР; xх.у Р = xх.уР хР; xх.у Р х.уР.
Залучаючи до розгляду композицію реномінації, отримуємо такі закони.
7. ( ) ( ),x x
y yz R P R zP якщо z у та z x.
Узагальнення: ( ) ( ),u u
v vz R P R zP якщо { , }.z u v
8. Поглинання кванторного імені загальнішим верхнім іменем реномінації:
. ( ) ( ),x x
z zx y R P R P якщо x.y z.
Водночас . ( ) ( . )x x
z zx y R P R x yP та . . . .. ( ) ( ).x x
x y v x y vx y R P R P
Узагальнення: , ,
, ,. ( ) ( ),x u x u
z v z vx y R P R P якщо . { , , }.x y z u v
Теоретичні та методологічні основи програмування
54
9. Поглинання верхнього імені реномінації загальнішим кванторним іменем: . ( ) .x y
uR xP xP
Водночас . . . .
. .( ) ( ( )), ( ) ( ), ( ) ( ).x y x y x y x y z z
u u u u x u x uR xP x R P R xP R P x R P R xP
Узагальнення:
,
, ( ) ( ),
y u u
vz vR xP R xP якщо x є префіксом імен із y та { }.x u
Властивості 7–9 відповідним чином переформульовуються для z.
4. Семантичні моделі та мови логік квазіарних предикатів над ієрархічними даними
Семантичними моделями композиційно-номінативних логік над ієрархічними номінативними даними
(скорочено КНЛІ) є композиційні системи квазіарних предикатів вигляду (HD(V, A), Pr
V_А
, C).
Для КНЛІ кванторного рівня множина C задається множиною базових композицій {, , ,v
xR x}, для
КНЛІ реномінативного рівня – множиною {, , v
xR }.
При зафіксованій C система (HD(V, A), Pr
V_А
, C) однозначно визначається об'єктом вигляду
(HD(V, A), Pr
V_А
) – алгебраїчною системою (АС) з квазіарними предикатами над ієрархічними номінативними
даними. Такі алгебраїчні системи будемо скорочено позначати (A, Pr
V_А
).
Розгляд композиційних систем передбачає наявність мови логіки, індукованої відповідними інтенсіона-
льними моделями (рівнями розгляду). Це означає необхідність позначення базових предикатів, із яких за допо-
могою композицій будуються складніші предикати.
Алфавiт мови КНЛІ кванторного рівня: символи базових композицій, множина Ps предикатних символів
(сигнатура мови), множина V базових предметних імен.
Дамо визначення множини Fr формул мови КНЛІ кванторного рівня:
1) кожний предикатний символ (ПС) є формулою; такі формули атомарні;
2) якшо та – формули, то та Ф – формули;
3) якшо – формула, то v
xR – формула;
4) якшо – формула, то x – формула.
Для випадку КНЛІ реномінативного рівня у цьому визначенні опускаємо п. 4.
Позначимо nm() множину всіх імен, які фігурують у символах реномінації та квантифікації формули ,
snm() – множину всіх простих імен, які фігурують у символах реномінації та квантифікації формули .
Щоб відрізнити символи базових композицій як елементів алфавіту мови від позначень цих композицій у
виразах, які подають складніші предикати через простіші, останні позначення записуватимемо жирним текстом.
Конкретна інтерпретація мови визначається АС (A, Pr
V_А
) та значеннями ПС на HD(V, A), які задаємо за
допомогою тотального однозначного відображення I : Ps Pr
V_А
. Тому моделями мови КНЛІ будемо вважати
об'єкти вигляду ((A, Pr
V_А
), I) –АС із квазіарними предикатами над ієрархічними номінативними даними з дода-
ною сигнатурою. Будемо їх скорочено позначати у вигляді (A, I).
Відображення інтерпретації формул J : FrPr
V_А
визначається за допомогою I так:
1) J(р) = I(p) для кожного рPs;
2) J() = (J()), J() = (J(), J());
3) J ( )v
xR = R
v
x (J());
4) J(x) = x(J()).
Для випадку КНЛІ реномінативного рівня опускаємо п. 4.
Предикат J() – значення формули при інтерпретації на A = (A, I), – позначаємо A.
Формула частково істинна при інтерпретації на A = (A, I), або A-неспростовна, якщо A – частково іс-
тинний (неспростовний) предикат. Це позначаємо A
|=
.
Формула всюди (частково) iстинна, або неспростовна, якщо частково iстинна при кожній інтерпре-
тації. Це позначаємо |=
.
На множинi формул мови КНЛІ введемо відношення логiчного наслiдку |= слабкого логiчного наслiдку
||= та логiчної еквiвалентностi .
Формула є логiчним наслiдком формули , що позначимо |= , якщо формула неспростовна.
Формула є слабким логiчним наслiдком формули , що позначимо ||= , якщо для кожної A = (A, I)
iз умови A |= випливає A |= .
Формули та логiчно еквiвалентнi, що позначимо , якщо |= та |= .
та логiчно еквiвалентнi (позначаємо ), якщо |= та |= .
та логiчно строго еквiвалентнi [7] (позначаємо TF ), якщо T(A) = T(A) та F(A) = F(A) для
кожної АС A. TF означає, що та завжди інтерпретуються як один і той же предикат.
Розглянемо наслідки з порожньої множини формул.
|= означає, що F(A) = для кожної АС A, тобто всюди частково iстинна, або неспростовна.
Поширимо відношення логічного наслідку на довільні множини формул.
Теоретичні та методологічні основи програмування
55
Нехай та – множини формул мови сигнатури Ps. Нехай A = (А, I) – АС сигнатури Ps.
Скажемо, що є логічним наслідком в АС A, якщо для всіх dHD(V, A) із того, що А(d) = T для всіх
, випливає, що неможливо А(d) = F для всіх . Цей факт позначаємо А|= .
Скажемо, що є логічним наслідком , якщо А|= для всіх АС A = (А, I) сигнатури Ps .
Те, що є логічним наслідком , позначаємо |= .
Як і для випадку композиційно-номінативних логік над однорівневими іменними множинами [5], відно-
шення логічного наслідку для множин формул рефлексивне, але нетранзитивне.
Для КНЛІ справджуються теореми семантичної еквівалентності та заміни еквівалентних.
Теорема 1 (семантичної еквівалентності). Нехай ' отримано з формули замiною деяких входжень
формул 1,..., n на 1,..., n вiдповiдно. Якщо 1 1, ..., n n, то '.
Теорема 2 (семантичної еквівалентності, сильна форма). Нехай ' отримано з формули замiною
деяких входжень формул 1,..., n на 1,..., n вiдповiдно. Якщо 1 TF 1, ..., n TF n, то TF '.
Доведення теорем еквівалентності – індукцією за побудовою формули.
Теорема 3 (заміни еквівалентних). Нехай . Тоді , |= , |= та |= , |= , .
Ім'я xV строго неістотне для формули , якщо при інтерпретації на кожній A = (A, I) і м'я x строго
неістотне для предиката A.
Твердження 5. Нехай уV строго неістотне для формули . Тоді x TF
x
yyR .
Для кожного рPs множину строго неістотних предметних імен задамо за допомогою тотальної функції
: Ps2
V
. Для КНЛІ постулюємо нескінченність множини VTs = ( )
p Ps
p
тотально строго неістотних імен.
Наведемо властивості формул, пов'язані з композицією реномінації. Зазначені властивості записуються
згідно відповідних властивостей композиції реномінації для квазіарних предикатів над ієрархічними номінати-
вними даними і мають таку ж назву. Властивості, не пов‟язані з кванторами, справджуються вже для КНЛІ
реномінативного рівня. При кожній інтерпретації предикати, що є значеннями виділених формул, збігаються,
тобто в цих властивостях маємо відношення строгої еквівалентності.
RsN) Нехай ім„я уV строго неістотне для . Тоді
,
, ( ) ( )
y v v
TF xz xR R .
RT) ,
, ( ) ( )z v v
z x TF xR R при умові zV; зокрема, ( )z
z TFR .
R) ( ) ( )v v
x TF xR R .
R) ( ) ( ) ( )v v v
x TF x xR R R .
Узагальнюючи R та R, отримуємо RR та RR.
RR) ( (... ( )...) ( (... ( )...)u v w u v w
x y z TF x y zR R R R R R .
RR) ( (... ( )...) ( (... ( )...) ( (... ( )...)u v w u v w u v w
x y z TF x y z x y zR R R R R R R R R .
Подібним чином можна записати властивості R&, R, R, RR&, RR, RR.
Записати властивість RR для згортки реномінацій в аналогічному вигляді, із використанням TF, вже не-
можливо. Можна лише переписати властивість RR композиції реномінації:
RR_С) для кожних A = (A, I), dHD(V, A) маємо ( ( )( ) ( ( ( )))v u u v
x y A A y xR R d r r d .
Залучаючи до реномінації квантори, отримуємо такі властивості:
ANQ) , , , ,
, , , ,. ( ) ( ) та . ( ) ( ),x u x u x u x u
z v TF z v z v TF z vx y R R x y R R якщо . { , , }.x y z u v
Зокрема, . ( ) ( ) та . ( ) ( ),x x x x
z TF z z TF zx y R R x y R R якщо x.y z.
ANR)
, ,
, ,( ) ( ) та ( ) ( ),
y u y uu u
TF v TF vz v z vR x R x R x R x якщо x є префіксом імен із y та x непорів-
нянне із кожним з імен .u Зокрема, . .( ) та ( )x y x y
u TF u TFR x x R x x .
R) ( ) ( ),u u
v TF vR y y R якщо { , }.y u v
R) ( ) ( ( ))v v y
x TF x zR y zR R за умови, що z тотально строго неістотне та ( ( )).v
xz snm R y
Властивість R використовуємо, якшо y порівнянне хоча б із одним з імен та u v .
Подібним чином можна записати R та R. Властивості R, R, R, R узагальнюються до RR,
RR, RR, RR аналогічно тому, як R та R узагальнюються до RR та RR.
Для логік еквітонних предиктів RT узагальнюється із певним ослабленням ( замість TF) до RTE:
RTE)
,
, ( ) ( )u v v
u x xR R ; зокрема, ( )u
uR .
Теоретичні та методологічні основи програмування
56
Формулу вигляду ( (... ( )...))u v w
x y zR R R p , де рPs та в реномінаціях згорнуті тотожні пари простих імен, на-
звемо слабко примітивною. Якщо при цьому в реномінаціях згорнуті тотожні пари як простих, так і складних
імен, таку формулу назвемо примітивною.
Для логік еквітонних предикатів будемо розглядати примітивні формули.
Із кожною примітивною формулою ( (... ( )...))u v w
x y zR R R p зв‟яжемо вираз вигляду р(), де – подана в ста-
ндартній формі згортка реномінацій ( (... ( )...))u v w
x y zr r r , – символ, який позначає довільне дане, VPs.
Такий вираз назвемо субреномінантою примітивної формули ( (... ( )...))u v w
x y zR R R p .
Для врахування строго неістотності предметних імен у стандартній формі згортки реномінацій вида-
лимо усі компоненти зі старшими простими іменами z такими, що z(р). Тоді вираз р() назвемо реномінан-
тою примітивної формули ( (... ( )...))u v w
x y zR R R p .
Наведемо тепер основні властивості композицій квантифікації.
Q1. xy TF yx та xy TF yx, якщо x та у непорівнянні.
Q2. x TF x та x TF x.
Q3. x TF xx, x TF xx; x TF xx, x TF xx.
Q4. x TF x.уx, x TF x.уx; x TF x.уx, x TF x.уx.
Q5. xx.у TF xx.у, xx.у TF xx.у.
Q6. xx TF x() та x&x TF x(&).
На додаток до властивостей, які описують строгу еквівалентність формул, наведемо також властивості,
пов‟язані з відношенням логічного наслідку; вони аналогічні відповідним властивостям логіки квазіарних пре-
дикатами над однорівневими іменними множинами.
Q7. x(&)|= x&x та xx|= x().
Q8. yx |= xy; водночас не завжди xy|= yx.
Q9. ||= x та ||= x.
Q10. |= yxxy, але не завжди |= xyyx.
Q11. |= x (x) та |= x (x); |= x (x) та |= x (x).
Розглянемо властивості відношення логічного наслідку |= для множин формул.
Властивості відношення |= на пропозиційному рівні ідентичні відповідним властивостям логіки квазіар-
них предикатами над однорівневими іменними множинами (див. [5]).
Розглянемо властивості відношення логічного наслідку для множин формул, пов„язані з композицією ре-
номінації. Не пов‟язані з кванторами властивості справджуються вже для логік реномінативного рівня. При ін-
терпретації на кожній A = (A, I), предикати, що є значеннями виділених формул, збігаються (за винятком RTE).
RTE|–)
,
, ( ),u v
u xR А|= ( ),v
xR А|= .
RTE–|) А|= ,
,
, ( )u v
u xR А|= , ( )v
xR .
RsN|–)
,
, ( ),
y v
z xR А|= ( ),v
xR А|= за умови, що уV строго неістотне для .
RsN–|) А|= ,
,
, ( )
y v
z xR А|= , ( )v
xR за умови, що уV строго неістотне для .
RR|–) ( (... ( )...)),u v w
x y zR R R А|= ( (... ( )...)),u v w
x y zR R R А|= .
RR–|) , ( (... ( )...))u v w
x y zR R R А|= , ( (... ( )...))u v w
x y zR R R А|= .
RR|–) ( (... ( )...)),u v w
x y zR R R А|= ( (... ( )...)) ( (... ( )...)),u v w u v w
x y z x y zR R R R R R А|= .
RR–|) , ( (... ( )...))u v w
x y zR R R А|= , ( (... ( )...)) ( (... ( )...))u v w u v w
x y z x y zR R R R R R А|= .
Аналогічно записуються властивості RR|– , RR–| , RR&|– , RR&–| .
R|–) ( ),v
xR y А|= ( ),v
xyR А|= за умови, що { , }.y u v
R–|) А|= , ( )v
xR y А|= , ( )v
xyR за умови, що { , }.y u v
R|–) ( ),v
xR y А|= ( ( )),v y
x zzR R А|= .
R–|) А|= , ( )v
xR y А|= , ( ( ))v y
x zzR R .
Для R|– та R–| умова: z тотально строго неістотне та ( ( )).v
xz snm R y
Аналогічно записуються властивості R|– , R–| , R|– , R–| .
Властивості типу R, R, R, R узагальнюються до властивостей типу RR, RR, RR, RR.
Теоретичні та методологічні основи програмування
57
5. Секвенційні числення логік квазіарних предикатів над ієрархічними даними
Для логік еквітонних квазіарних предикатів над ієрархічними даними побудуємо числення секвенційного
типу. Обмежимося тут розглядом секвенційних числень для логік реномінативного рівня. Секвенції трактуємо
як множини специфікованих формул. Кожна формула секвенції відмічена (специфікована) зліва одним з двох
символів – |– чи –|. Секвенції позначаємо у вигляді |––|, де усі формули множини специфіковані |– , усі формули
множини – символом –| . Не деталізуючи, секвенції позначатимемо .
Секвенційне числення будується так, що секвенція |––| має виведення тоді й тільки тоді, коли |= .
Секвенція замкнена, якщо існує така, що |– та –|, або якщо існують примітивні та з однако-
вими реномінантами такі, що |– та –|. Отже, якщо |––| замкнена, то |= .
Виведення в секвенційних численнях має вигляд дерева, вершинами якого є секвенції. Такі дерева нази-
вають секвенційними (див. [5]). Cеквенційне дерево замкнене, якщо кожний його листок – замкнена секвенція.
Секвенція вивідна, або має виведення, якщо існує замкнене секвенційне дерево з коренем . Таке дере-
во назвемо виведенням секвенції .
Семантичним властивостям відношення |= зіставимо їх синтаксичні аналоги – секвенційні форми.
Наведемо секвенційні форми для реномінативних логік еквітонних квазіарних предикатів над ієрархіч-
ними даними.
|
|
|
,
,
A
A
|
|
|
,
,
A
A
|
| |
|
, ,
,
A B
A B
|
| |
|
, ,
,
A B
A B
|–RTE
|
,
| ,
( ),
( ),
v
x
u v
u x
R A
R A
–|RTE
|
,
| ,
( ),
( ),
v
x
u v
u x
R A
R A
|–RR
|
|
( (... ( )...)),
( (... ( )...)),
u v w
x y z
u v w
x y z
R R R A
R R R A
–|RR
|
|
( (... ( )...)),
( (... ( )...)),
u v w
x y z
u v w
x y z
R R R A
R R R A
|–RR
|
|
( (... ( )...)) ( (... ( )...)),
( (... ( )...)),
u v w u v w
x y z x y z
u v w
x y z
R R R A R R R B
R R R A B
–|RR
|
|
( (... ( )...)) ( (... ( )...)),
( (... ( )...)),
u v w u v w
x y z x y z
u v w
x y z
R R R A R R R B
R R R A B
Секвенційні числення із вищенаведеними базовими секвенційними формами назвемо RID-численнями.
Для побудованих секвенційних RID-числень справджуються теореми коректності та повноти.
Теорема 4 (коректності). Нехай секвенція |––| вивідна. Тоді |= .
Доведення теореми проводиться індукцією за побудовою замкненого секвенційного дерева для |––|.
Теорема 5 (повноти). Нехай |= . Тоді секвенція |––| вивідна.
Для доведення повноти секвенційних RID-числень використовується метод модельних множин.
Висновки
У роботі будуються нові логіки, що дозволяють більш адекватно описувати властивості предикатів та
функцій, визначених над ієрархічними даними. Характерною властивістю таких логік є використання в їх мовах
складних імен. Дається визначення ієрархічних номінативних даних, вводяться та досліджуються операції над
такими даними. Будуються композиційно-номінативні логіки часткових предикатів реномінативного та кванто-
рного рівнів над ієрархічними номінативними даними. Вивчаються семантичні властивості цих логік, для таких
логік еквітонних квазіарних предикатів реномінативного рівня пропонуються числення секвенційного типу.
Дослідження логік квазіарних предикатів над ієрархічними даними кванторного рівня та побудову відповідних
секвенційних числень планується продовжити в наступних роботах.
1. Handbook of Logic in Computer Science. Edited by S. Abramsky, Dov M. Gabbay and T. S. E. Maibaum.– Oxford University Press.– Vol. 1–5,
1993–2000.
2. Никитченко Н.С. Композиционно-номинативный подход к уточнению понятия программы // Проблеми програмування.– 1999.– № 1.
– C. 16–31.
3. Никитченко Н.С. Предикатные композиционно–номинативные системы // Проблеми програмування. – 1999. – № 2. – С. 3–19.
4. Никитченко Н.С., Шкильняк С.С. Неоклассические логики предикатов // Проблеми програмування. – 2000. – № 3–4.
5. Нікітченко М.С., Шкільняк С.С. Математична логіка та теорія алгоритмів. – К., 2008. – 528 с.
6. Басараб И.А., Никитченко Н.С., Редько В.Н. Композиционные базы данных.– К.: Либiдь, 1992.– 191 с.
7. Нікітченко М.С., Шкільняк С.С. Семантичні властивості композиційно-номінативних логік. // Тези доп. Міжнар. конф. "Теоретичні та
прикладні аспекти побудови програмних систем" – TAAPSD'2009.– Київ, 2009. – С. 50–59.
|
| id | pp_isofts_kiev_ua-article-864 |
| institution | Problems in programming |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2026-06-02T01:00:15Z |
| publishDate | 2026 |
| publisher | PROBLEMS IN PROGRAMMING |
| record_format | ojs |
| resource_txt_mv | ppisoftskievua/88/8a1166e09c4b6cc62d107a09ce742688.pdf |
| spelling | pp_isofts_kiev_ua-article-8642026-06-01T06:02:58Z Compositional-nominative logics over hierarchical data Композиційно-номінативні логіки над ієрархічними даними Nikitchenko, M.S. Shkilniak, S.S. UDC 004.4 УДК 004.4 New logics more adequate for property descriptions of functions and predicates over hierarchical data are constructed. A characteristic fea-ture of such logics is use of composite names in their languages. Semantic properties of such logics are investigated, corresponding sequent calculi are defined.Problems in programming 2010; 2-3: 48-57 Будуються нові логіки, які дозволяють більш адекватно описувати властивості предикатів та функцій, визначених над ієрархічними даними. Характерною властивістю цих логік є використання в їх мовах складних імен. Вивчаються семантичні властивості таких логік та визначаються відповідні числення секвенційного типу.Problems in programming 2010; 2-3: 48-57 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2026-06-01 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/864 PROBLEMS IN PROGRAMMING; No 2-3 (2010); 48-57 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 2-3 (2010); 48-57 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 2-3 (2010); 48-57 1727-4907 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/864/916 Copyright (c) 2026 PROBLEMS IN PROGRAMMING |
| spellingShingle | UDC 004.4 Nikitchenko, M.S. Shkilniak, S.S. Compositional-nominative logics over hierarchical data |
| title | Compositional-nominative logics over hierarchical data |
| title_alt | Композиційно-номінативні логіки над ієрархічними даними |
| title_full | Compositional-nominative logics over hierarchical data |
| title_fullStr | Compositional-nominative logics over hierarchical data |
| title_full_unstemmed | Compositional-nominative logics over hierarchical data |
| title_short | Compositional-nominative logics over hierarchical data |
| title_sort | compositional-nominative logics over hierarchical data |
| topic | UDC 004.4 |
| topic_facet | UDC 004.4 УДК 004.4 |
| url | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/864 |
| work_keys_str_mv | AT nikitchenkoms compositionalnominativelogicsoverhierarchicaldata AT shkilniakss compositionalnominativelogicsoverhierarchicaldata AT nikitchenkoms kompozicíjnonomínativnílogíkinadíêrarhíčnimidanimi AT shkilniakss kompozicíjnonomínativnílogíkinadíêrarhíčnimidanimi |