Композиційно-номітативні логіки часткових та неоднозначних предикатів
Досліджено чисті першопорядкові логіки часткових однозначних, тотальних неоднозначних та часткових неоднозначних предикатів. Розглянуто низку розширень цих логік за допомогою узагальнених реномінацій та спеціальних предикатів-індикаторів наявності значення для змінних. Описано мови та семантичні мод...
Saved in:
| Published in: | Компьютерная математика |
|---|---|
| Date: | 2014 |
| Main Author: | |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2014
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/84814 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Композиційно-номітативні логіки часткових та неоднозначних предикатів / С.С. Шкільняк // Компьютерная математика. — 2014. — № 1. — С. 93-102. — Бібліогр.: 11 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860264096624017408 |
|---|---|
| author | Шкільняк, С.С. |
| author_facet | Шкільняк, С.С. |
| citation_txt | Композиційно-номітативні логіки часткових та неоднозначних предикатів / С.С. Шкільняк // Компьютерная математика. — 2014. — № 1. — С. 93-102. — Бібліогр.: 11 назв. — укр. |
| collection | DSpace DC |
| container_title | Компьютерная математика |
| description | Досліджено чисті першопорядкові логіки часткових однозначних, тотальних неоднозначних та часткових неоднозначних предикатів. Розглянуто низку розширень цих логік за допомогою узагальнених реномінацій та спеціальних предикатів-індикаторів наявності значення для змінних. Описано мови та семантичні моделі таких логік, досліджено їх семантичні властивості, для різних класів цих логік запропоновано числення секвенційного типу.
Исследованы чистые первопорядковые логики частичных однозначных, тотальных неоднозначных и частичных неоднозначных предикатов. Рассмотрен ряд расширений этих логик с помощью обобщенных реноминаций и специальных предикатов-индикаторов наличия значения для переменных. Описаны языки и семантические модели таких логик, для разных классов этих логик предложены исчисления секвенциального типа.
We study pure fisrt-order logics of partial single-valued, total multi-valued and partial multi-valued predicates. Various extensions of the introduced logics with generalized renominations and special variable definedness predicates are considered. For such logics, we define languages and semantic models, investigate their semantic properties and specify sequent calculi.
|
| first_indexed | 2025-12-07T18:58:31Z |
| format | Article |
| fulltext |
Компьютерная математика. 2014, № 1 93
Экспертные системы,
методы индуктивного
вывода
Досліджено чисті першопорядкові
логіки часткових однозначних, то-
тальних неоднозначних та част-
кових неоднозначних предикатів.
Розглянуто низку розширень цих
логік за допомогою узагальнених
реномінацій та спеціальних преди-
катів-індикаторів наявності зна-
чення для змінних. Описано мови
та семантичні моделі таких ло-
гік, досліджено їх семантичні вла-
стивості, для різних класів цих
логік запропоновано числення сек-
венційного типу.
© C.C. Шкільняк, 2014
УДК 004.42:510.69
С.С. ШКІЛЬНЯК
КОМПОЗИЦІЙНО-НОМІНАТИВНІ
ЛОГІКИ ЧАСТКОВИХ
ТА НЕОДНОЗНАЧНИХ
ПРЕДИКАТІВ
Вступ. Розвиток інформаційних технологій
та їх проникнення в усі сфери діяльності лю-
дини роблять особливо актуальною задачу
створення ефективних і надійних програм-
них систем. Успішне вирішення цієї задачі
неможливе без широкого використання по-
нять і методів математичної логіки.
Логіка тісно пов'язана з програмуванням із
самого початку його виникнення. В рамках
математичної логіки запропоновано перші
формалізації поняття алгоритму, мови про-
грамування базуються на тих чи інших уточ-
неннях цього поняття. Апарат математичної
логіки (алгебра логіки) лежить в основі схе-
мотехніки комп'ютерів. Подальший розвиток
програмування та пов'язана з цим поява но-
вих задач і проблем характеризуються залу-
ченням до їх розв'язку все нових понять і за-
собів математичної логіки (теорія доведень,
модальні, темпоральні, епістемічні, динаміч-
ні, алгоритмічні, програмні логіки тощо).
На даний момент створено [1] багато
різноманітних логічних систем, які успішно
використовуються в програмуванні. Такі си-
стеми зазвичай базуються на класичній логі-
ці предикатів. Проте поява нових застосувань
логіки в інформатиці та програмуванні висві-
тлила принципові обмеження класичної логі-
ки, які ускладнюють її використання. Ця
логіка базується на традиційних математич-
них структурах однозначних тотальних скін-
Т.М. Провотар, К.Д. Протасова
Компьютерная математика. 2010, №
94
ченно-арних відображень,
тому недостатньо враховує
неповноту, частковість, структу-рованість
інформації про предметну область.
Таким чином, на перший план висувається проблема побудови нових, про-
грамно-орієнтованих логік. Природною основою такої побудови є спільний для
логіки й програмування композиційно-номінативний підхід (КНП). На його базі
розроблено низку різноманітних логічних систем, що знаходяться на різних рів-
нях абстрактності й загальності (див., напр., [2–7]). Логіки, збудовані на основі
КНП, названо композиційно-номінативними (КНЛ). Вони базуються на загаль-
них класах часткових відображень, заданих на довільних наборах іменованих
значень – квазіарних відображень.
Мета даної роботи – дослідження різних класів чистих першопорядкових
КНЛ (ЧКНЛ) часткових однозначних, тотальних неоднозначних і часткових не-
однозначних предикатів. Поряд із ЧКНЛ базового рівня розглянуто їх розши-
рення: ЧКНЛРР – це ЧКНЛ із розширеними реномінаціями; ε-ЧКНЛ – це ЧКНЛ
із предикатами-індикаторами наявності значення для змінних; ε-ЧКНЛРР – це
логіки, які поєднують можливості ЧКНЛРР та ε-ЧКНЛ. Описано мови та семан-
тичні моделі таких логік, досліджено їх семантичні властивості. Для розгляну-
тих класів ЧКНЛ запропоновано числення секвенційного типу.
Поняття, які тут не визначаються, тлумачимо в сенсі робіт [2, 4, 5].
Основи композиційно-номінативного підходу. КНП задає принципи ви-
значення і дослідження формальних мов програм та логічних систем (див. [2]).
Він опирається на принцип розвитку як сходження від абстрактного до конкрет-
ного i базується на принципах композиційності та номінативності. Принцип ком-
позиційності трактує засоби побудови програм (функцій, предикатів) як алгебра-
їчні операції. Для логіки це означає зведення логічних зв'язок і кванторів до ком-
позицій предикатів. Принцип номінативності означає необхідність використання
відношень іменування для побудови семантичних моделей програм і даних.
Згідно КНП програмні поняття формалізуємо за допомогою композиційно-
номінативних систем. Центральним поняттям логіки є поняття предиката. З ма-
тематичного погляду предикати – це спеціальні функції вигляду D→ {T, F}, де
{T, F} – множина істиннісних значень. Тому класи предикатів теж можна зада-
вати за допомогою композиційно-номінативних систем. Це дозволяє подавати
і вивчати логічні та програмні системи в єдиному стилі.
Логіки, збудовані на основі КНП, названо композиційно-номінативними.
Передумовою їх виникнення стала необхідність посилення можливостей класич-
ної логіки для вирішення нових задач програмування й моделювання.
КНЛ будуємо за семантико-синтаксичною схемою. Це означає наступне.
1. Задаємо інтенсіональні (змістовні) моделі логік. Такі моделі найперше визна-
чаються рівнями розгляду даних, тому для їх задання фіксуємо рівень абстракції
розгляду. Інтенсіональні моделі індукують мову логіки відповідного рівня.
2. Будуємо відповідні розглянутому рівню екстенсіональні семантичні моде-
лі – предикатні композиційні системи. Це трійки вигляду (D, Pr, C), де D – мно-
КОМПОЗИЦІЙНО-НОМІНАТИВНІ ЛОГІКИ ЧАСТКОВИХ ТА НЕОДНОЗНАЧНИХ ПРЕДИКАТІВ
Компьютерная математика. 2014, № 1 95
жина (клас) даних, Pr – множина (клас) предикатів, заданих на D, C – множина
(клас) композицій (операцій) породження нових предикатів, вона задається
множиною базових композицій відповідного рівня. Така система задає алгебру
(алгебраїчну систему) даних (D, Pr) та алгебру предикатів (Pr, C), терми якої
трактуються як формули мови логіки. Композиції визначають універсальні ме-
тоди побудови предикатів, виступаючи ядром логіки певного типу.
3. Будуємо формально-аксіоматичні числення, які задають синтаксичні ас-
пекти логік. Основні їх класи – формальні системи гільбертівського типу і систе-
ми ґенценівського типу (секвенційні числення, системи натурального виведення).
Побудову КНЛ починаємо з гранично-абстрактних рівнів, поступово їх кон-
кретизуючи. На пропозиційному рівні дані трактуються гранично абстрактно.
Предикати мають вигляд A → {T, F}, де A – сукупність абстрактних даних.
На номінативних рівнях дані будуються із більш простих на базі відношень
іменування. Найважливішими з номінативних є рівень іменних множин та ієрар-
хічно-номінативний рівень. Іменні множини (ІМ) – це множини пар, перша ком-
понента яких – ім’я, а друга – його значення. Предикати, задані на ІМ, названо
квазіарними. На ієрархічно-номінативному рівні дані будуються індуктивно із
множин предметних імен та предметних значень.
На рівні ІМ виділяємо реномінативний та першопорядкові (кванторний, кван-
торно-екваційний, функціональний, функціонально-екваційний) рівні. Визначаль-
ною для першопорядкових КНЛ є наявність композицій квантифікації (кванто-
рів). Характерні особливості першопорядкових КНЛ проявляються вже на кван-
торному рівні, за аналогією з класичною логікою його називають рівнем чистих
КНЛ першого порядку. Тому дана робота присвячена дослідженню саме ЧКНЛ.
Іменні множини. V-іменна множина (V-ІМ) над A – це довільна однозначна
часткова функція δ : V→A. Тут V і A – множини предметних імен і предметних
значень. V-ІМ подаємо у вигляді [v1aa1,...,vnaan,...], де vі∈V, aі∈A, vі ≠ vj при і ≠ j.
Bведемо функцію asn :
VA→2V так: asn(δ) = {v∈V | vaa∈δ для деякого a∈A}.
Операцію ||–х видалення компоненти з іменем х для V-ІМ вводимо таким чином:
δ ||–х = {vaa ∈δ | v ≠ х}. Поширимо її на множини Х⊆V: δ ||–Х = {vaa ∈δ | v∉Х}.
Операцію ∇ накладки V-ІМ δ на V-ІМ η задаємо так: η∇δ = δ ∪ (η ||–asn(δ)).
Операція реномінації 1
1
,...,
,...,
n
n
v v
x xr : V
А
→ VA визначається [2] так:
1
11
,...,
{ ,..., } ,..., ( ) ||n
nn
v v
v vx xr −δ = δ + [v1aδ(x1),...,vnaδ(xn)].
Узагальненням операції реномінації є операція розширеної реномінації, яка
дає змогу явно задавати відсутність значення для предметних імен, тобто вилу-
чати компоненти з певними іменами. Відсутність значення для імені x задаємо
парою, де верхнє ім'я – x, a відповідне нижнє ім'я – спеціальний символ ⊥.
Операція розширеної реномінації 1 1
1
,..., , ,...,
,..., , ,...,
n m
n
v v u u
x xr ⊥ ⊥ : V
А
→ VA визначається [5] так:
1 1
1 11
,..., , ,...,
{ ,..., , ,..., } ,..., , ,..., ( ) ||n m
n mn
v v u u
v v u ux xr −⊥ ⊥ δ = δ + [v1aδ(x1),...,vnaδ(xn)].
С.С. ШКІЛЬНЯК
96 Компьютерная математика. 2014, № 1
Ввівши позначення y для y1,...,
yn, замість 1
1
,...,
,...,
n
n
v v
x xr та 1 1
1
,..., , ,...,
,..., , ,...,
n m
n
v v u u
x xr ⊥ ⊥ скорочено
пишемо
v
xr та ,
,
v u
xr ⊥ .
Операції
v
yr та ,
,
v z
yr ⊥ монотонні: d ⊆ d' ⇒ , ,
, ,( ) ( ')v z v z
y yr d r d⊥ ⊥⊆ та ( ) ( ')v v
y yr d r d⊆ .
Послідовне застосування двох операцій реномінації можна подати у вигляді
однієї операції реномінації, яку назвемо згорткою початкових (див. [2, 5]).
Згортку операцій ,
,
v t
xr ⊥ (застосовується першою) та ,
,
z u
yr ⊥ (застосовується дру-
гою) позначаємо , ,
, ,
z u v t
y xr ⊥ ⊥� . Тоді маємо: , , , ,
, , , ,( ( )) ( )z u v t z u v t
y x y xr r d r d⊥ ⊥ ⊥ ⊥= � .
Згортку операцій
v
xr та
z
yr позначаємо
z v
y xr � . Маємо: ( ( )) ( )z v z v
y x y xr r d r d= � .
Квазіарні предикати та їх композиції. V-квазіарним предикатом на А на-
звемо довільну (часткову неоднозначну, взагалі кажучи) функцію вигляду
P : VA → {T, F}. Часткові неоднозначні предикати на множині VA ми трактуємо як
відношення між VA та {T, F}. Такі предикати назвемо предикатами реляційного
типу, вони формалізують найпростіше уточнення поняття часткового неодно-
значного предиката. У цьому випадку P(d) позначає множину тих значень, які
предикат P : V
А → {T, F} може прийняти на d∈VA.
Областю істинності та областю хибності предиката P назвемо множини
T(P) = {d∈VA | T∈P(d)} та F(P) = {d∈VA | F∈P(d)}.
Кожний квазіарний предикат однозначно задається своїми областями істин-
ності та хибності.
V-квазіарний предикат P : VA→{T, F} назвемо:
– неспростовним, якщо F(P) = ∅;
– виконуваним, якщо T(P) ≠ ∅;
– тотально істинним, якщо T(P) = VA;
– тотально хибним, якщо F(P) = VA;
– тотожно істинним, якщо T(P) = VA та F(P) = ∅ (позначаємо його як T);
– тотожно хибним, якщо T(P) = ∅ та F(P) = VA (позначаємо його як F);
– всюди невизначеним, якщо T(P) = ∅ та F(P) = ∅ (позначаємо його як ⊥);
– тотально насиченим, якщо T(P) = VA та F(P) = VA.
Квазіарний предикат P монотонний, якщо d ⊆ d' ⇒ P(d) ⊆ P(d').
Квазіарний предикат P антитонний, якщо d ⊆ d' ⇒ P(d) ⊇ P(d').
Ім'я z∈V неістотне для предиката P, якщо d1||–х = d2||–х ⇒ P(d1) = P(d2).
Базовими композиціями ЧКНЛ є логічні зв'язки ¬ і ∨, реномінації R ,v
x кван-
тори ∃x. Задамо їх через області істинності та хибності відповідних предикатів:
T(¬P) = F(P); F(¬P) = T(P);
T(P∨Q) = T(P)∪T(Q); F(P∨Q) = F(P)∩F(Q);
T (R ( ))v
x P = {d∈VA | ( )v
xr d ∈T(P)}; F (R ( ))v
x P = {d∈VA | ( )v
xr d ∈F(P)};
T(∃xP) = {d∈VA | T∈Р(d∇xaa) для деякого a∈A};
КОМПОЗИЦІЙНО-НОМІНАТИВНІ ЛОГІКИ ЧАСТКОВИХ ТА НЕОДНОЗНАЧНИХ ПРЕДИКАТІВ
Компьютерная математика. 2014, № 1 97
F(∃xP) = {d∈VA | F∈Р(d∇xaa) для всіх a∈A}.
Подібним чином можна задати [2] логічні зв'язки →, &, ↔ та квантори ∀x.
Логічні зв'язки →, &, ↔ є похідними, вони виражаються ¬ та ∨.
Композиція ∀х є похідною: кожний предикат вигляду ∀хР подамо як ¬∃х¬Р.
Основні властивості наведених пропозиційних композицій (логічних зв’язок)
¬, ∨, →, &, ↔ в цілому аналогічні властивостям відповідних класичних [8]
логічних зв’язок. Основні властивості композицій ∃x та ∀x теж аналогічні вла-
стивостям відповідних кванторів класичної логіки (див. [2, 8]).
Теорема 1. 1) ім’я х∈V неістотне для предикатів ∃хР та ∀хР;
2) ім’я х∈V неістотне для Р ⇔ P = ∀хР ⇔ Р = ∃хР.
ЧКНЛ із узагальненими (розширеними) реномінаціями запропоновано в [5],
вони названі ЧКНЛРР. Базовими композиціями ЧКНЛРР є ¬, ∨, ∃x та розширені
реномінації ,
,Rv u
x ⊥ . Композиції ,
,Rv u
x ⊥ визначаються так:
T ,
,(R ( ))v u
x P⊥ = {d∈VA | ,
,r ( )v u
x d⊥ ∈T(P)}; F ,
,(R ( ))v u
x P⊥ = {d∈VA | ,
,r ( )v u
x d⊥ ∈F(P)}.
Композиції R v
x та ,
,R v u
x ⊥ можна визначити через операції
v
xr та ,
,
v u
xr ⊥ тради-
ційним чином: R ( )( ) ( ( ))v v
x xP d P r d= ; , ,
, ,R ( )( ) ( ( ))v u v u
x xP d P r d⊥ ⊥= .
За допомогою композицій розширеної реномінації визначаємо похідні ком-
позиції розширеної квантифікації (розширені квантори).
∃⊥xP = ∃xP ∨ R ( );x P⊥ ∀⊥xP = ∀xP &R ( ).x P⊥
Основні властивості розширених кванторів наведено в [5, 6].
Характерною особливістю логік квазіарних предикатів є те, що значення
предиката P(d) може бути різним залежно від того, входить чи не входить до d
компонента з певним іменем. Це веде до того, що для цих логік вже невірні деякі
важливі закони класичної логіки (див. [2, 4]). Наприклад, не завжди неспростов-
ні предикати вигляду ∀хР→Р та Р→∃хР, існують виконувані предикати вигляду
¬∃xР&Р. Тому доцільно явно вказувати означені й неозначені предметні імена.
Для цього використовуємо спеціальні 0-арні композиції – предикати-індикатори
εz, які визначають наявність у даних компоненти з відповідним іменем (змін-
ною) z, тобто наявність значення для z. Предикати-індикатори εz визначаємо так:
T(εz) = {d | d(z)↑} = {d∈VA | z∉asn(d)}; F(εz) = {d | d(z)↓} = {d∈VA | z∈asn(d)}.
Предикати-індикатори εz не є монотонними та не є антитонними.
Кожне x∈V таке, що x ≠ z, неістотне для предикатa εz.
ЧКНЛ з виділеними предикатами-індикаторами розглянуто в [7], такі логіки
названі ε-ЧКНЛ. Базовими композиціями ε-ЧКНЛ є ¬, ∨, R ,v
x ∃x та εz.
Можливості ЧКНЛРР та ε-ЧКНЛ поєднують ε-ЧКНЛРР. Такі логіки запро-
поновані в [9]. Базовими композиціями ε-ЧКНЛРР є ¬, ∨, ,
,R ,v u
x ⊥ ∃x та εz.
ЧКНЛРР, ε-ЧКНЛ та ε-ЧКНЛРР утворюють окремі підрівні ЧКНЛ.
С.С. ШКІЛЬНЯК
98 Компьютерная математика. 2014, № 1
Теорема 2. 1) композиції ¬, ∨, R ,v
x ,
,R ,v u
x ⊥ ∃x зберігають монотонність і ан-
титонність предикатів;
2) композиції ¬, ∨, R ,v
x ,
,R ,v u
x ⊥ ∃x, εz зберігають тотальність предикатів.
Наслідок 1. Всюди невизначений предикат ⊥ не може бути виражений пре-
дикатами εy за допомогою ¬, ∨, R ,v
x ,
,R ,v u
x ⊥ ∃x.
Отже, можна отримати нетривіальні розширення ЧКНЛ, ЧКНЛРР, ε-ЧКНЛ та
ε-ЧКНЛРР шляхом додавання ⊥ як спеціальної 0-арної композиції. Дослідження
таких розширень буде зроблено в наступних роботах.
Семантичні моделі та мови ЧКНЛ. Семантичними моделями ЧКНЛ є [2]
композиційні системи квазіарних предикатів (V
А, PrA, C), де PrA – клас V-квазіар-
них предикатів на A, C визначається базовими композиціями відповідного підрів-
ня. Терми композиційної алгебри (PrA, C) трактуємо як формули мови ЧКНЛ.
Алфавіт мови: символи базових композицій, множина Ps предикатних символів
(сигнатура мови), множина V предметних імен (змінних). Символи базових ком-
позицій такі: ¬, ∨, ,v
xR ∃x для ЧКНЛ базового рівня; ¬,∨, ,
, ,v u
xR ⊥ ∃x для ЧКНЛРР;
¬, ∨, ,v
xR ∃x, εz для ε-ЧКНЛ; ¬, ∨, ,
, ,v u
xR ⊥ ∃x, εz для ε-ЧКНЛРР.
Множина Fr формул мови ε-ЧКНЛРР визначається індуктивно:
– Ps ⊆ Fr та {εz | z∈V} ⊆ Fr; формули вигляду p∈Ps та εz – атомарні;
– Φ, Ψ∈Fr ⇒ ¬Φ, ∨ФΨ, ,
, ,v u
xR ⊥Φ ∃xΦ∈Fr.
Множини формул мови ЧКНЛ, ε-ЧКНЛ, ЧКНЛРР визначаємо аналогічно.
Інтерпретуємо мову на композиційних системах (VA, PrA, C). Відображення
інтерпретації формул I : Fr → PrA визначаємо за допомогою тотального однозна-
чного відображення I : Ps → PrA, яке позначає символами із Рs базові предикати.
Кожна формула вигляду εz, де z∈V, інтерпретується як предикат-індикатор εz.
Для складних формул відображення I : Fr → PrA задається згідно побудови
формул із простіших за допомогою символів базових композицій:
– I(¬Φ) = ¬(I(Φ)); I(∨ΦΨ) = ∨(I(Φ), I(Ψ));
– , ,
, ,( ) R ( ( ));v u v u
x xI R I⊥ ⊥Φ = Φ I(∃xΦ) = ∃x(I(Φ)).
Відображення I пов'язує алгебру даних (А, Pr) із мовою. Отримуємо об'єкт
((A, PrA), I) – алгебраїчну систему (АС) з доданою сигнатурою, яка визначає
композиційну систему (VA, PrA, C). АС з доданою сигнатурою є інтегрованими
семантичними моделями, які пов'язують мови КНЛ із алгебрами даних. Назива-
ємо їх моделями мови та скорочено позначаємо A = (A, I).
Предикат I(Φ) – значення формули Φ при інтерпретації на A, – далі познача-
ємо ΦA. Формули εz завжди інтерпретуються однаково, тому предикати-індика-
тори, які є їх значенням, ми теж позначаємо εz, опускаючи індекс моделі мови.
Формула Φ частково істинна при інтерпретації на A = (A, I), або A-неспрос-
товна, якщо ΦA – неспростовний предикат.
КОМПОЗИЦІЙНО-НОМІНАТИВНІ ЛОГІКИ ЧАСТКОВИХ ТА НЕОДНОЗНАЧНИХ ПРЕДИКАТІВ
Компьютерная математика. 2014, № 1 99
Формула Φ неспростовна, якщо Φ A-неспростовна на кожній моделі мови A.
Формула Φ виконувана при інтерпретації на моделі мови A, або A-виконува-
на, якщо ΦA – виконуваний предикат.
Формула Φ виконувана, якщо Φ A-виконувана на кожній моделі мови A.
Характерним для програмування і моделювання є широке використання ча-
сткових та необов'язково однозначних відображень над складними даними.
Тому постає проблема дослідження КНЛ із нетрадиційними семантиками.
Класична логіка – це логіка тотальних однозначних предикатів. КНЛ одно-
значних часткових предикатів – це логіки з неокласичною семантикою, КНЛ
тотальних неоднозначних предикатів – логіки з пересиченою семантикою, КНЛ
часткових неоднозначних предикатів – логіки із загальною семантикою.
Модель мови B = (A, IB) дуальна до моделі мови A = (A, IA), якщо для кожно-
го p∈Ps маємо ( ) ( )B AF p T p= .
Якщо B дуальна до A, то ( ) ( )A BT p F p= та ( ) ( )A BF p T p= , тобто A дуальна
до B. Якщо A = (A, IA) – АС з частковими однозначними предикатами, то дуаль-
на B = (A, IB) – АС з тотальними неоднозначними предикатами та навпаки.
Теорема 3. Якщо B = (A, IB) дуальна до A = (A, IA), то для кожної формули Φ:
1) ( ) ( )B AT FΦ = Φ та ( ) ( )B AF TΦ = Φ ;
2) ΦA монотонний ⇒ ΦB антитонний; ΦA антитонний ⇒ ΦB монотонний.
Наслідок 2. ΦA неспростовний на A із частковими однозначними предика-
тами (неокласична семантика) ⇔ ΦB тотально істинний на дуальній B із тоталь-
ними неоднозначними предикатами (пересичена семантика).
Це означає: неокласична семантика та пересичена семантика дуальні.
Відношення логічного наслідку. Введемо відношення наслідку для двох
формул при інтерпретації на фіксованій моделі мови A. Це робиться однаково
для ЧКНЛ базового рівня (див. [3, 4]) та для їх розширень:
– неспростовнісний наслідок A|=Cl : Φ A|=Cl Ψ ⇔ T(ΦA)∩F(ΨA) = ∅;
– насичений наслідок A|=Cm : Φ A|=Cm Ψ ⇔ F(ΦA)∪T(ΨA) = VA;
– істиннісний наслідок A|=T : Φ A|=T Ψ ⇔ T(ΦA) ⊆ T(ΨA);
– хибнісний наслідок A|=F : Φ A|=F Ψ ⇔ F(ΨA) ⊆ F(ΦA);
– сильний наслідок A|=TF : Φ A|=TF Ψ ⇔ T(ΦA) ⊆ T(ΨA) та F(ΨA) ⊆ F(ΦA).
Відповідні відношення логічного наслідку |=Cl, |=Cm, |=T, |=F, |=TF визначаємо
за наступною схемою: Φ |=∗ Ψ ⇔ Φ A|=∗ Ψ для кожної моделі мови A.
Відношення логічного наслідку індукують на множині формул відношення
логічної еквівалентності. Відношення еквівалентності A∼Cl, A∼Cm, A∼T, A∼F, A∼TF в
моделі мови A визначаємо за такою схемою: Φ A∼∗ Ψ, якщо Φ A|=∗ Ψ та Ψ A|=∗ Φ.
Звідси: Φ A∼TF Ψ ⇔ T(ΦA) = T(ΨA) та F(ΦA) = F(ΨA), тобто Φ A∼TF Ψ ⇔ ΦA = ΨA.
Відношення логічної еквівалентності ∼Cl, ∼Cm, ∼T, ∼F, ∼TF визначаємо за та-
кою схемою: Φ ∼∗ Ψ, якщо Φ |=∗ Ψ та Ψ |=∗ Φ.
Зрозуміло, що Φ ∼∗ Ψ ⇔ Φ A∼∗ Ψ для кожної моделі мови A.
С.С. ШКІЛЬНЯК
100 Компьютерная математика. 2014, № 1
Для відношень ∼Cl, ∼Cm та ∼TF справджується (тут ∗ – це одне з Cl, Cm, TF):
Теорема 4 (семантичної еквiвалентностi). Нехай Φ' отримана з Φ замiною
деяких входжень Φ1,..., Φn на Ψ1,..., Ψn . Якщо Φ1 ∼∗ Ψ1, ..., Φn ∼∗ Ψn, то Φ ∼∗ Φ'.
Для відношень ∼T та ∼F теорема 4, взагалі кажучи, неправильна (див. [3, 4]).
Семантичні властивості формул мови ЧКНЛ в різних семантиках дослідже-
но в [3, 4]. Для розширень ЧКНЛ додаються властивості, пов’язані з розширени-
ми реномінаціями та взаємодією предикатів-індикаторів із кванторами та рено-
мінаціями (див. [5–7]). Наведемо основні з цих властивостей:
R⊥T) , , ,
, , ,( ) ( )z v u v u
z x TF xR R⊥ ⊥Φ ∼ Φ ; зокрема, ,
, ( ) ( )z u u
z TFR R⊥ ⊥Φ Φ� ;
R⊥U) нехай z∈V неістотне для Ф, тоді , , ,
, , ,( ) ( )z v u v u
y x TF xR R⊥ ⊥Φ Φ� ;
Ren) нехай z∈V неістотне для Ф, тоді ( )x
TF zx zR∃ Φ ∃ Φ� ;
R⊥¬) , ,
, ,( ) ( )v u v u
x TF xR R⊥ ⊥¬Φ ∼ ¬ Φ ;
R⊥∨) , , ,
, , ,( ) ( ) ( )v u v u v u
x TF x xR R R⊥ ⊥ ⊥Φ ∨ Ψ Φ ∨ Ψ� ;
R⊥R) , , , ,
, , , ,( ( )) ( )v z u t v z u t
y x TF y xR R R⊥ ⊥ ⊥ ⊥Φ Φ� o ; тут ( ) ( ) ( ( ))A df AR d r dα σ σ α
β η η βΦ = Φo � ;
R⊥∃) , ,
, ,( ) ( )v u v u
x TF xR y yR⊥ ⊥∃ Φ ∃ Φ� за умови { , , }y v x u∉ ;
R⊥∃∃) , ,
, ,( ) ( )v u v u y
x TF x zR y zR⊥ ⊥∃ Φ ∃ Φ� o за умови z∈VT та z∉ ,
,( ( ))v u
xnm R x⊥ ∃ Φ ;
εR⊥) ,
, ( )v u
x TFR z z⊥ ε ε� за умови { , };z v u∉ , ,
, , ( ) ,v u z
x y TFR z y⊥ ε ε� ( ) ;z
y TFR z yε ε�
ε∃) ∃x εz ∼TF εz; ∃x ¬εz ∼TF ¬εz;
∨ε∃) ∃x(εx∨Φ) ∼TF ∃xΦ; ∃x¬(εx∨Φ) ∼TF ∃x¬Φ;
CnT) ∃x ¬εxA = ¬∃x εxA = T; ∃x(¬εx∨Φ)A = ¬∃x¬(¬εx∨Φ)A = T;
CnF) ∃x εxA = ¬∃x ¬εxA = F; ∃x¬(¬εx∨Φ)A = ¬∃x(¬εx∨Φ)A = F.
Тепер задамо відношення логічного наслідку для множин формул.
Нехай Γ⊆ Fr та ∆ ⊆ Fr, A – модель мови. У випадку Γ A|= ∆ позначаємо:
( )AT
Φ∈Γ
ΦI як T(ΓA), ( )AT
Ψ∈∆
ΨU як T(∆A), ( )AF
Φ∈Γ
ΦU як F(ΓA), ( )AF
Ψ∈∆
ΨI як F(∆A).
Відношення A|=Cl, A|=Cm, A|=T, A|=F, A|=TF наслідку для пари множин формул в
моделі мови A задаємо подібно тому, як це робиться для пар формул:
Γ A|=Cl ∆, якщо T(ΓA) ∩ F(∆A) = ∅; Γ A|=Cm ∆, якщо F(ΓA) ∪ T(∆A) =
VA; Γ A|=T ∆,
якщо T(ΓA) ⊆ T(∆A); Γ A|=F ∆, якщо F(∆A) ⊆ F(ΓA); Γ A|=TF ∆, якщо Γ A|=T ∆ і Γ A|=F ∆.
Відповідні відношення |=Cl, |=Cm, |=T, |=F, |=TF логічного наслідку для пари
множин формул вводимо за схемою: Γ |=∗ ∆ ⇔ Γ A|=∗ ∆ для кожної моделі мови A.
Теорема 5. Нехай моделі мови A = (A, IA) та B = (A, IB) дуальні. Тоді:
1) Γ A|=T ∆ ⇔ Γ B|=F ∆ та Γ A|=F ∆ ⇔ Γ B|=T ∆;
2) Γ A|=Cl ∆ ⇔ Γ B|=Cm ∆ та Γ A|=Cm ∆ ⇔ Γ B|=Cl ∆.
Наслідок 3. У випадку загальної семантики Γ |=T ∆ ⇔ Γ |=F ∆ ⇔ Γ |=TF ∆.
Наслідок 4. 1) Γ |=Cl ∆ в неокласичній семантиці ⇔ Γ B|=Cm ∆ в пересиченій;
КОМПОЗИЦІЙНО-НОМІНАТИВНІ ЛОГІКИ ЧАСТКОВИХ ТА НЕОДНОЗНАЧНИХ ПРЕДИКАТІВ
Компьютерная математика. 2014, № 1 101
2) Γ |=T ∆ в неокласичній семантиці ⇔ Γ |=F ∆ в пересиченій;
3) Γ |=F ∆ в неокласичній семантиці ⇔ Γ |=T ∆ в пересиченій.
Теорема 6 (заміни еквівалентних). Нехай Φ ∼TF Ψ, тоді Φ, Γ |=∗ ∆ ⇔ Ψ, Γ |=∗ ∆
та Γ |=∗ ∆, Φ ⇔ Γ |=∗ ∆, Ψ (∗ – одне з Cl, Cm, T, F, TF у відповідних семантиках).
Властивості відношень логічного наслідку для множин формул ЧКНЛ у різ-
них семантиках наведено в [3, 4], для випадків їх розширень – в [5–7, 10]. Влас-
тивості, пов'язані з (розширеними) реномінаціями, кванторами та предикатами-
індикаторами, індуковані відповідними властивостями для формул.
Секвенційні числення. Для розв'язання низки задач, що виникають у су-
часних інформаційних і програмних системах, необхідний ефективний пошук
виведень. Потужним апаратом побудови виведень є числення секвенційного
типу. Такі числення формалізують відношення логічного наслідку для множин
формул. Ми пропонуємо спектр секвенційних числень для різних відношень
логічного наслідку в різних семантиках для ЧКНЛ та їх розширень (таблиця).
Секвенційні числення ЧКНЛ, зокрема, ЧКНЛ монотонних предикатів та
ЧКНЛ антитонних предикатів, описано в [11]. Секвенційні числення ε-ЧКНЛ та
ЧКНЛРР описано відповідно в [7] та [10]. Детальний опис числень ε-ЧКНЛРР
буде зроблено в наступних роботах.
ТАБЛИЦЯ. Секвенційні числення ЧКНЛ, ЧКНЛРР, ε-ЧКНЛ, ε-ЧКНЛРР
|=Cl |=Cm |=T |=F |=TF
Неокласична семантика ЧКНЛ QSC – QSL QSR QSR
Неокласична семантика ЧКНЛРР Q⊥C – Q⊥L Q⊥R Q⊥LR
Неокласична семантика ε-ЧКНЛ QεC – QεL QεR QεLR
Неокласична семантика ε-ЧКНЛРР Q⊥εC – Q⊥εL Q⊥εR Q⊥εLR
Пересичена семантика ЧКНЛ – QSC QSR QSL QSLR
Пересичена семантика ЧКНЛРР – Q⊥C Q⊥R Q⊥L Q⊥LR
Пересичена семантика ε-ЧКНЛ – QεC QεR QεL QεLR
Пересичена семантика ε-ЧКНЛРР – Q⊥εC Q⊥εR Q⊥εL Q⊥εLR
Загальна семантика ЧКНЛ – – QSG QSG QSG
Загальна семантика ЧКНЛРР – – Q⊥G Q⊥G Q⊥G
Загальна семантика ε-ЧКНЛ – – QεG QεG QεG
Загальна семантика ε-ЧКНЛРР – – Q⊥εG Q⊥εG Q⊥εG
Для пропонованих секвенційних чисел справджуються теореми коректності
та повноти. Для різних числень та логічних наслідків ці теореми формулюються
однотипно. Поєднуючи теореми коректності та повноти, маємо:
Теорема 7. Γ |= ∆ у семантиці α ⇔ секвенція |–Γ–|∆ вивідна в численні β.
Назву β числення читаємо на перетині стовпця |= та рядка α (таблиця).
Висновки. Досліджено чисті першопорядкові композиційно-номінативні
логіки часткових однозначних, тотальних неоднозначних та часткових неодно-
значних предикатів. Розглянуто розширення цих логік за допомогою уза-
С.С. ШКІЛЬНЯК
102 Компьютерная математика. 2014, № 1
гальнених реномінацій та предикатів-індикаторів наявності значення для змін-
них. Описано мови та семантичні моделі таких логік, досліджено їх семантичні
властивості, розглянуто різні формалізації відношення логічного наслідку. Для
різних класів досліджених логік запропоновано числення секвенційного типу.
C.C. Шкильняк
КОМПОЗИЦИОННО-НОМИНАТИВНЫЕ ЛОГИКИ
ЧАСТИЧНЫХ И НЕОДНОЗНАЧНЫХ ПРЕДИКАТОВ
Исследованы чистые первопорядковые логики частичных однозначных, тотальных неоднознач-
ных и частичных неоднозначных предикатов. Рассмотрен ряд расширений этих логик с помощью
обобщенных реноминаций и специальных предикатов-индикаторов наличия значения для пе-
ременных. Описаны языки и семантические модели таких логик, для разных классов этих
логик предложены исчисления секвенциального типа.
S.S. Shkilniak
COMPOSITION-NOMINATIVE LOGICS OF PARTIAL AND MULTI-VALUED PREDICATES
We study pure fisrt-order logics of partial single-valued, total multi-valued and partial multi-valued predi-
cates. Various extensions of the introduced logics with generalized renominations and special variable
definedness predicates are considered. For such logics, we define languages and semantic models, inves-
tigate their semantic properties and specify sequent calculi.
1. Handbook of Logic in Computer Science. Edited by S. Abramsky, Dov M. Gabbay and
T. S. E. Maibaum. – Oxford Univ. Press. – Vol. 1–5, 1993–2000.
2. Нікітченко М.С., Шкільняк С.С. Математична логіка та теорія алгоритмів. – К., 2008. – 528 с.
3. Шкільняк С.С. Відношення логічного наслідку в композиційно-номінативних логіках //
Проблеми програмування. – 2010. – № 1. – C. 15–38.
4. Нікітченко М.С., Шкільняк С.С. Композиційно-номінативні логіки квазіарних предикатів:
семантичні аспекти // Вісник Київ. ун-ту. Серія: фіз.-мат. науки. – 2012. – Вип. 4. – C. 165–172.
5. Нікітченко М.С., Шкільняк О.С., Шкільняк С.С. Логіки часткових предикатів з роз-
ширеними реномінаціями та кванторами // Там само. – 2013. – Вип. 2. – C. 210 – 215.
6. Шкільняк С.С. Семантичні властивості логік часткових предикатів з розширеними рено-
мінаціями // Там само. – 2013. – Вип. 3. – C. 297–302.
7. Нікітченко М.С., Шкільняк C.С. Композиційно-номінативні логіки із спеціальними
предикатами наявності значення для змінних // Там само. – 2013. – Cпецвипуск. –
C. 128–133.
8. Клини С. Математическая логика. – М., 1973. – 480 с.
9. Нікітченко М.С., Шкільняк О.С., Шкільняк С.С. Першопорядкові логіки, розширені рено-
мінаціями з невизначеним значенням змінних та предикатами-індикаторами наявності
значення // PDMU-2013: int. conf.: abstracts. – Yalta-Foros, Ukraine, 2013. – C. 116 –1 17.
10. Шкільняк О.С. Секвенційні числення логік часткових предикатів з розширеними реномі-
націями // Вісник Київ. ун-ту. Серія: фіз.-мат. науки. – 2013. – Cпецвипуск. – C. 199 –204.
11. Шкільняк С.С. Спектр секвенційних числень першопорядкових композиційно-
номінативних логік // Проблеми програмування. – 2013. – № 3 – C. 22 – 37.
Одержано 30.01.2014
КОМПОЗИЦІЙНО-НОМІНАТИВНІ ЛОГІКИ ЧАСТКОВИХ ТА НЕОДНОЗНАЧНИХ ПРЕДИКАТІВ
Компьютерная математика. 2014, № 1 103
Про автора:
Шкільняк Степан Степанович,
доктор фізико-математичних наук, професор кафедри теорії та технології програмування
факультету кібернетики Київського національного університету імені Тараса Шевченка.
|
| id | nasplib_isofts_kiev_ua-123456789-84814 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | ХХХХ-0003 |
| language | Ukrainian |
| last_indexed | 2025-12-07T18:58:31Z |
| publishDate | 2014 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Шкільняк, С.С. 2015-07-15T19:56:09Z 2015-07-15T19:56:09Z 2014 Композиційно-номітативні логіки часткових та неоднозначних предикатів / С.С. Шкільняк // Компьютерная математика. — 2014. — № 1. — С. 93-102. — Бібліогр.: 11 назв. — укр. ХХХХ-0003 https://nasplib.isofts.kiev.ua/handle/123456789/84814 004.42:510.69 Досліджено чисті першопорядкові логіки часткових однозначних, тотальних неоднозначних та часткових неоднозначних предикатів. Розглянуто низку розширень цих логік за допомогою узагальнених реномінацій та спеціальних предикатів-індикаторів наявності значення для змінних. Описано мови та семантичні моделі таких логік, досліджено їх семантичні властивості, для різних класів цих логік запропоновано числення секвенційного типу. Исследованы чистые первопорядковые логики частичных однозначных, тотальных неоднозначных и частичных неоднозначных предикатов. Рассмотрен ряд расширений этих логик с помощью обобщенных реноминаций и специальных предикатов-индикаторов наличия значения для переменных. Описаны языки и семантические модели таких логик, для разных классов этих логик предложены исчисления секвенциального типа. We study pure fisrt-order logics of partial single-valued, total multi-valued and partial multi-valued predicates. Various extensions of the introduced logics with generalized renominations and special variable definedness predicates are considered. For such logics, we define languages and semantic models, investigate their semantic properties and specify sequent calculi. uk Інститут кібернетики ім. В.М. Глушкова НАН України Компьютерная математика Экспертные системы, методы индуктивного вывода Композиційно-номітативні логіки часткових та неоднозначних предикатів Композиционно-номинативные логики частичных и неоднозначных предикатов Composition-nominative logics of partial and multi-valued predicates Article published earlier |
| spellingShingle | Композиційно-номітативні логіки часткових та неоднозначних предикатів Шкільняк, С.С. Экспертные системы, методы индуктивного вывода |
| title | Композиційно-номітативні логіки часткових та неоднозначних предикатів |
| title_alt | Композиционно-номинативные логики частичных и неоднозначных предикатов Composition-nominative logics of partial and multi-valued predicates |
| title_full | Композиційно-номітативні логіки часткових та неоднозначних предикатів |
| title_fullStr | Композиційно-номітативні логіки часткових та неоднозначних предикатів |
| title_full_unstemmed | Композиційно-номітативні логіки часткових та неоднозначних предикатів |
| title_short | Композиційно-номітативні логіки часткових та неоднозначних предикатів |
| title_sort | композиційно-номітативні логіки часткових та неоднозначних предикатів |
| topic | Экспертные системы, методы индуктивного вывода |
| topic_facet | Экспертные системы, методы индуктивного вывода |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84814 |
| work_keys_str_mv | AT škílʹnâkss kompozicíinonomítativnílogíkičastkovihtaneodnoznačnihpredikatív AT škílʹnâkss kompozicionnonominativnyelogikičastičnyhineodnoznačnyhpredikatov AT škílʹnâkss compositionnominativelogicsofpartialandmultivaluedpredicates |