Композиційно-номінативні логіки квазіарних предикатів та багатозначні логіки
Досліджено композиційно номінативні логіки часткових однозначних, тотальних неоднозначних і часткових неоднозначних квазіарних предикатів на пропозиційному і реномінативному рівнях. Встановлено зв’язки між цими логіками та 3-значними і 4-значними логіками тотальних однозначних предикатів. Исследован...
Gespeichert in:
| Veröffentlicht in: | Штучний інтелект |
|---|---|
| Datum: | 2012 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
Інститут проблем штучного інтелекту МОН України та НАН України
2012
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/56424 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Композиційно-номінативні логіки квазіарних предикатів та багатозначні логіки / С.С. Шкільняк // Штучний інтелект. — 2012. — № 1. — С. 66-74. — Бібліогр.: 7 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-56424 |
|---|---|
| record_format |
dspace |
| spelling |
Шкільняк, С.С. 2014-02-18T11:45:52Z 2014-02-18T11:45:52Z 2012 Композиційно-номінативні логіки квазіарних предикатів та багатозначні логіки / С.С. Шкільняк // Штучний інтелект. — 2012. — № 1. — С. 66-74. — Бібліогр.: 7 назв. — укр. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/56424 004.42:510.69 Досліджено композиційно номінативні логіки часткових однозначних, тотальних неоднозначних і часткових неоднозначних квазіарних предикатів на пропозиційному і реномінативному рівнях. Встановлено зв’язки між цими логіками та 3-значними і 4-значними логіками тотальних однозначних предикатів. Исследованы композиционно-номинативные логики частичных однозначных, тотальных неоднозначных и частичных неоднозначных квазиарных предикатов на пропозициональном и реноминативном уровнях. Установлены связи этих логик с 3-значными и 4-значными логиками тотальных однозначных предикатов. Composition nominative logics of quasiary predicates are studied at propositional and renominative levels. Connections between 2-valued logics of partial single-valued, total multiple-valued and partial multiple-valued quasiary predicates with the 3-valued and 4-valued logics of total single-valued predicates are established. uk Інститут проблем штучного інтелекту МОН України та НАН України Штучний інтелект Алгоритмическое и программное обеспечение параллельных вычислительных интеллектуальных систем Композиційно-номінативні логіки квазіарних предикатів та багатозначні логіки Композиционно-номинативные логики квазиарных предикатов и многозначные логики Сomposition Nominative Logics of Quasiary Predicates and Many-Valued Logics Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Композиційно-номінативні логіки квазіарних предикатів та багатозначні логіки |
| spellingShingle |
Композиційно-номінативні логіки квазіарних предикатів та багатозначні логіки Шкільняк, С.С. Алгоритмическое и программное обеспечение параллельных вычислительных интеллектуальных систем |
| title_short |
Композиційно-номінативні логіки квазіарних предикатів та багатозначні логіки |
| title_full |
Композиційно-номінативні логіки квазіарних предикатів та багатозначні логіки |
| title_fullStr |
Композиційно-номінативні логіки квазіарних предикатів та багатозначні логіки |
| title_full_unstemmed |
Композиційно-номінативні логіки квазіарних предикатів та багатозначні логіки |
| title_sort |
композиційно-номінативні логіки квазіарних предикатів та багатозначні логіки |
| author |
Шкільняк, С.С. |
| author_facet |
Шкільняк, С.С. |
| topic |
Алгоритмическое и программное обеспечение параллельных вычислительных интеллектуальных систем |
| topic_facet |
Алгоритмическое и программное обеспечение параллельных вычислительных интеллектуальных систем |
| publishDate |
2012 |
| language |
Ukrainian |
| container_title |
Штучний інтелект |
| publisher |
Інститут проблем штучного інтелекту МОН України та НАН України |
| format |
Article |
| title_alt |
Композиционно-номинативные логики квазиарных предикатов и многозначные логики Сomposition Nominative Logics of Quasiary Predicates and Many-Valued Logics |
| description |
Досліджено композиційно номінативні логіки часткових однозначних, тотальних неоднозначних і часткових неоднозначних квазіарних предикатів на пропозиційному і реномінативному рівнях. Встановлено зв’язки між цими логіками та 3-значними і 4-значними логіками тотальних однозначних предикатів.
Исследованы композиционно-номинативные логики частичных однозначных, тотальных неоднозначных и частичных неоднозначных квазиарных предикатов на пропозициональном и реноминативном уровнях. Установлены связи этих логик с 3-значными и 4-значными логиками тотальных однозначных предикатов.
Composition nominative logics of quasiary predicates are studied at propositional and renominative levels. Connections between 2-valued logics of partial single-valued, total multiple-valued and partial multiple-valued quasiary predicates with the 3-valued and 4-valued logics of total single-valued predicates are established.
|
| issn |
1561-5359 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/56424 |
| citation_txt |
Композиційно-номінативні логіки квазіарних предикатів та багатозначні логіки / С.С. Шкільняк // Штучний інтелект. — 2012. — № 1. — С. 66-74. — Бібліогр.: 7 назв. — укр. |
| work_keys_str_mv |
AT škílʹnâkss kompozicíinonomínativnílogíkikvazíarnihpredikatívtabagatoznačnílogíki AT škílʹnâkss kompozicionnonominativnyelogikikvaziarnyhpredikatovimnogoznačnyelogiki AT škílʹnâkss sompositionnominativelogicsofquasiarypredicatesandmanyvaluedlogics |
| first_indexed |
2025-11-25T17:27:00Z |
| last_indexed |
2025-11-25T17:27:00Z |
| _version_ |
1850520667453128704 |
| fulltext |
«Искусственный интеллект» 1’201266
2Ш
УДК 004.42:510.69
С.С. Шкільняк
Київський національний університет імені Тараса Шевченка, м. Київ, Україна
Україна, 01601, м. Київ, вул. Володимирська, 60, sssh@unicyb.kiev.ua
Композиційно-номінативні логіки квазіарних
предикатів та багатозначні логіки
S.S. Shkilniak
Taras Shevchenko National University of Kiyv, Ukraine
Ukraine, 01601, c. Kiev, Volodymyrs’ka st., 60
Сomposition Nominative Logics of Quasiary
Predicates and Many-Valued Logics
С.С. Шкильняк
Киевский национальный университет имени Тараса Шевченко, г. Киев, Украина
Украина, 01601, г. Киев, ул. Владимирская, 60
Композиционно-номинативные логики квазиарных
предикатов и многозначные логики
Досліджено композиційно номінативні логіки часткових однозначних, тотальних неоднозначних і часткових
неоднозначних квазіарних предикатів на пропозиційному і реномінативному рівнях. Встановлено зв’язки
між цими логіками та 3-значними і 4-значними логіками тотальних однозначних предикатів.
Ключові слова: композиційно-номінативна логіка, багатозначна логіка, предикат.
Composition nominative logics of quasiary predicates are studied at propositional and renominative levels.
Connections between 2-valued logics of partial single-valued, total multiple-valued and partial multiple-valued
quasiary predicates with the 3-valued and 4-valued logics of total single-valued predicates are established.
Key words: composition nominative logic, many-valued logic, predicate.
Исследованы композиционно-номинативные логики частичных однозначных, тотальных неоднозначных и
частичных неоднозначных квазиарных предикатов на пропозициональном и реноминативном уровнях.
Установлены связи этих логик с 3-значными и 4-значными логиками тотальных однозначных предикатов.
Ключевые слова: композиционно-номинативная логика, многозначная логика, предикат.
Вступ
Розвиток інформаційних технологій та пов’язана з цим поява нових задач і про-
блем веде до розширення сфери застосування математичної логіки. На даний момент
створено низку різноманітних логічних систем, які з великим успіхом використо-
вуються в програмуванні та моделюванні. В основі таких систем, як правило, лежить
класична логіка предикатів. Проте така логіка має низку принципових обмежень, які
ускладнюють її використання. Класична логіка базується на традиційних математичних
структурах однозначних тотальних скінченно-арних відображень, вона недостатньо вра-
ховує неповноту, частковість інформації про предметну область, її структурованість.
Таким чином, на перший план виходить проблема побудови нових, програмно-орієн-
тованих логік. Природною основою такої побудови є спільний для логіки і програму-
mailto:sssh@unicyb.kiev.ua
Композиційно-номінативні логіки квазіарних предикатів та багатозначні логіки
«Штучний інтелект» 1’2012 67
2Ш
вання композиційно-номінативний підхід [1]. На базі цього підходу розроблено [2]
низку логічних формалізмів, що знаходяться на різних рівнях абстрактності й загаль-
ності. Логіки, будовані на основі композиційно-номінативного підходу, названо компо-
зиційно-номінативними (КНЛ). Такі логіки базуються на загальних класах часткових
відображень над іменними (номінативними) даними – квазіарних відображень.
Розповсюдженість в програмуванні та моделюванні часткових, не завжди одно-
значних відображень спонукає дослідження КНЛ з нетрадиційними семантиками. Логіки
часткових однозначних предикатів називають логіками з неокласичною семантикою,
тотальних неоднозначних предикатів – логіками з пересиченою семантикою, частко-
вих неоднозначних предикатів – логіками з загальною семантикою. КНЛ часткових
однозначних, тотальних неоднозначних та часткових неоднозначних квазіарних пре-
дикатів досліджувались в [3]. Для пропозиційної логіки нестандартні семантики ви-
чались О.Д. Смирновою [4].
Метою даної роботи є дослідження КНЛ часткових однозначних, тотальних не-
однозначних і часткових неоднозначних квазіарних предикатів пропозиційного та
реномінативного рівнів і встановлення зв’язків між цими логіками та 3-значними і 4-
значними логіками тотальних однозначних предикатів.
Поняття, які в роботі не визначаються, будемо тлумачити в сенсі [2], [3].
Предикати та їх композиції
Під 2-предикатом на множині D будемо розуміти довільну (часткову неодно-
значну) функцію вигляду P : D {T, F}
Тут {T, F} – 2-елементна множина істиннісних значень.
Аналогічно можна визначити n-предикати, в яких множина істиннісних значень
n-елементна, n 3.
Термін «n-предикат», а не загальноприйнятий «n-значний предикат», в роботі ви-
користовуємо для уникнення плутанини, адже ми розглядаємо предикати, які можуть
бути неоднозначними функціями.
Надалі, якщо інше явно не вказано, «предикат» означатиме «2-предикат».
Областю істинності та областю хибності предиката Р на D назвемо множини:
T(P) = P–1(T) = {dD | TP(d)};
F(P) = P–1(F) = {dD | FP(d)}.
Якщо Р однозначний, то T(P)F(P) = ; якщо Р тотальний, то T(P)F(P) = D.
Композиції пропозиційного рівня (логічні зв’язки) , , &, , задамо через
області істинності та хибності предикатів (P), (P, Q) (P, Q), &(P, Q) (P, Q).
Такі предикати традиційно позначаємо P, PQ, PQ, P&Q, PQ.
T(P) = F(P); F(P) = T(P).
T(PQ) = T(P)T(Q); F(PQ) = F(P)F(Q).
T(P&Q) = T(P)T(Q); F(P&Q) = F(P)F(Q).
T(PQ) = F(P)T(Q); F(PQ) = T(P)F(Q).
T(PQ) = (T(P)T(Q))(F(P)F(Q)); F(PQ) = (T(P)F(Q))(F(P)T(Q)).
Для логічних зв’язок маємо наступні відомі властивості: комутативність і асоціа-
тивність , & та ; дистрибутивність відносно & та & відносно ; ідемпотентність
та &; закони контрапозиції, зняття подвійного заперечення, де Моргана. Ці власти-
вості вірні для загального випадку часткових неоднозначних предикатів.
Шкільняк С.С.
«Искусственный интеллект» 1’201268
2Ш
Водночас властивість PQ = (PQ)&(QP) справджується тільки для одно-
значних предикатів [3].
На реномінативному та першопорядкових рівнях предикати називаються квазі-
арними, вони задаються на іменних множинах. Це множини пар, перша компонента
яких – ім’я, а друга – його значення. Поняття іменної множини під різними назвами
дуже поширене в математиці й програмуванні.
V-іменна множина (V-ІМ) над A – це довільна однозначна функція : VA.
A і V трактуємо як множину предметних значень і множину предметних імен.
ІМ подаємо у вигляді [v1a1,...,vnan,...], де vіV, aіA, vі vj при і j.
Множину всіх V-ІМ над A позначаємо VA.
Параметричну операцію реномінації r 1
1
,...,
,...,
n
n
v v
x x : VА VA можна задати так:
r 1
1
,...,
,...,
n
n
v v
x x () = [v1(x1),...,vn(xn)] [va | v{v1,...,vn}].
Замість запису вигляду y1, …, yn також скорочено пишемо y .
Предикат вигляду P : VA{T, F} назвемо V-квазіарним предикатом на А.
Множину V-квазіарних предикатів на A позначимо PrА.
Композицію реномінації v
xR : PrА PrА задамо, визначаючи предикат v
xR (P):
T( v
xR (P)) = r v
x (T(P)); F( v
xR (P)) = r v
x (F(P)).
Властивості композицій реномінації наведені в [2], [3]. Властивості реномінатив-
ного рівня (згортка тотожної пари імен, згортка реномінацій, дистрибутивність рено-
мінацій щодо пропозиційних композицій) формулюються однаково для різних класів
логік квазіарних предикатів.
Семантичними моделями КНЛ є предикатні композиційні системи – трійки ви-
гляду (D, Pr, C), де D – множина даних, Pr – множина предикатів, заданих на D, C –
множина композицій (операцій) породження нових предикатів, вона задається множи-
ною базових композицій відповідного рівня абстракції розгляду. Предикатна компо-
зиційна система задає дві алгебри: алгебру даних (D, Pr) та композиційну алгебру
предикатів (Pr, C), терми якої трактуються як формули мови логіки.
Для композиційних предикатних алгебр пропозиційного та реномінативного рів-
нів множини їх композицій CP та CR задаються відповідно множинами базових компо-
зицій {, } та {, , v
xR }.
Множини тотальних однозначних, часткових однозначних, тотальних неодно-
значних та часткових неоднозначних предикатів будемо зазвичай позначати у вигляді
TSPr, PSPr, TMPr, PMPr.
Логіки тотальних неоднозначних і часткових
однозначних предикатів та 3-значні логіки
Розглянемо взаємозв’язок логіки тотальних неоднозначних 2-предикатів та логіки
тотальних однозначних 3-предикатів – сильної 3-значної логіки Кліні [5]. Істиннісні
значення такої логіки позначаємо T, F, TF. Логічні зв’язки цієї логіки позначаємо ін-
дексною відміткою K. Клінієві зв’язки K, K, &K, K задаються так.
(K Р)(d) =
, якщо ( ) ,
, якщо ( ) ,
, якщо ( ) .
T P d F
F P d T
TF P d TF
Композиційно-номінативні логіки квазіарних предикатів та багатозначні логіки
«Штучний інтелект» 1’2012 69
2Ш
(РK Q)(d) =
, якщо ( ) або ( ) ,
, якщо ( ) та ( ) ,
, в усіх інших випадках.
T P d T Q d T
F P d F Q d F
TF
(Р &K Q)(d) =
, якщо ( ) та ( ) ,
, якщо ( ) або ( ) ,
, в усіх інших випадках.
T P d T Q d T
F P d F Q d F
TF
(РK Q)(d) =
, якщо ( ) або ( ) ,
, якщо ( ) та ( ) ,
, в усіх інших випадках.
T P d F Q d T
F P d T Q d F
TF
Маємо P &K Q = K (K PKK Q) та РK Q = K PK Q.
Отже, за базові можна взяти композиції K та K, тоді &K та K є похідними.
Пропозиційною композиційною алгеброю Кліні тотальних 3-предикатів назвемо
композиційну предикатну алгебру (PrK, CK), де PrK – множина тотальних однозначних
3-предикатів на D, а CK задається базовими композиціями K та K .
Кожному тотальному неоднозначному 2-предикату Р : D {T, F} зіставимо
тотальний однозначний 3-предикат РK : D{T, F, TF} таким чином:
РK(d) =
, якщо ( ) та ( ),
, якщо ( ) та ( ),
, якщо ( ) та ( ).
T d T P d F P
F d F P d T P
TF d T P d F P
Враховуючи тотальність предиката P, це можна переписати так:
РK(d) =
, якщо ( ),
, якщо ( ),
, якщо ( ) та ( ).
T d F P
F d T P
TF d T P d F P
З іншого боку, кожному тотальному однозначному 3-предикату РK зіставляємо
тотальний неоднозначний 2-предикат Р:
T(P) = {dD | РK(d) = T або РK(d) = TF};
F(P) = {dD | РK(d) = F або РK(d) = TF}.
Тоді маємо T(P) F(P) = {dD | РK(d) = T або РK(d) = F або РK(d) = TF} = D,
тобто 2-предикат Р справді тотальний.
Тепер для K маємо:
(K РK)(d) =
, якщо ( ) ,
, якщо ( ) ,
, якщо ( ) ,
K
K
K
T P d F
F P d T
TF P d TF
=
, якщо ( ),
, якщо ( ),
, якщо ( ) та ( ).
T d T P
F d F P
TF d T P d F P
=
=
, якщо ( ),
, якщо ( ),
, якщо ( ) та ( ),
T d F P
F d T P
TF d F P d T P
= (Р)K(d).
Таким чином, K РK = (Р)K.
Для K маємо:
(РKK QK)(d) =
, якщо ( ) або ( ) ,
, якщо ( ) та ( ) ,
, в усіх інших випадках,
K K
K K
T P d T Q d T
F P d F Q d F
TF
=
=
, якщо ( ) або ( ),
, якщо ( ) та ( ),
, в усіх інших випадках,
T d F P d F Q
F d T P d T Q
TF
=
, якщо ( ) ( ),
, якщо ( ) ( ),
, в усіх інших випадках,
T d F P F Q
F d T P T Q
TF
=
=
, якщо ( ),
, якщо ( ),
, в усіх інших випадках,
T d F P Q
F d T P Q
TF
= (РQ)K(d).
Шкільняк С.С.
«Искусственный интеллект» 1’201270
2Ш
Таким чином, РKK QK = (РQ)K .
Аналогічно показуємо РСС QK = (РQ)K та РK &K QK = (Р&Q)K .
Звідси отримуємо:
Теорема 1. Пропозиційна композиційна алгебра Кліні тотальних однозначних
3-предикатів (PrK, CK) та пропозиційна композиційна алгебра тотальних неоднозначних
2-предикатів (TMPr, CP) ізоморфні.
Трактуючи невизначеність як спеціальне значення , на основі відповідних ви-
значень пропозиційних композицій отримуємо ізоморфізм пропозиційної композиційної
алгебри часткових однозначних 2-предикатів (PSPr, CP) та алгебри Кліні (PrK, CK).
Зауважимо, що це є підставою для традиційного переходу від часткових до тотальних
відображень. Водночас такий перехід порушує адекватність подання багатьох власти-
востей часткових відображень, зокрема, обчислюваності.
Беручи до уваги дуальність неокласичної та пересиченої семантик [3], отримуємо
ізоморфізм алгебр (PSPr, CP) та (TMPr, CP). При цьому дуальні предикати QPSPr та
Q’TMPr пов’язані так: T(Q’) ( )F Q та F(Q’) ( ).T Q
Таким чином:
Наслідок 1. Композиційні алгебри (PrK, CK), (TMPr, CP), (PSPr, CP) ізоморфні.
Зауважимо, що сильна 3-значна логіка Кліні природно отримується [6] з кла-
сичної 2-значної логіки шляхом застосування конструкції розповсюдження 1-арних
та 2-арних операцій з множини на її булеан.
Наведені результати можна поширити на номінативні рівні. Обмежимось тут роз-
глядом реномінативних логік. Композиція реномінації однотипно визначається для
функцій різних класів, зокрема, для 2-предикатів, 3-предикатів, 4-предикатів.
Далі розглядаємо квазіарні предикати на A, вони задаються на множині D = VA.
Реномінативною композиційною алгеброю Кліні тотальних однозначних 3-пре-
дикатів назвемо предикатну алгебру (KPrA, CKR), де KPrA – множина тотальних одно-
значних 3-предикатів на A, а CKR задається базовими композиціями K, K, v
xR .
Теорема 2. Реномінативна композиційна алгебра Кліні тотальних однозначних
3-предикатів (KPrA, CKR), реномінативна композиційна алгебра тотальних неоднознач-
них 2-предикатів (TMPrA, CR) та реномінативна композиційна алгебра часткових одно-
значних 2-предикатів (PSPrA, CR) ізоморфні.
Логіки часткових однозначних і неоднозначних
предикатів та 4-значні логіки
Логікам часткових однозначних та тотальних неоднозначних 2-предикатів відпо-
відає певна логіка тотальних однозначних 3-предикатів – сильна 3-значна логіка Кліні.
Постає питання, яка саме логіка тотальних однозначних 4-предикатів буде відповідати
логікам часткових неоднозначних 2-предикатів. Істиннісні значення такої логіки при-
родно позначити T, F, TF, . Логічні зв’язки цієї 4-значної логіки будемо позначати
B, B, &B, B (чому саме так, стане зрозумілим пізніше).
Кожному частковому неоднозначному 2-предикату Р : D {T, F} природним
чином зіставимо тотальний однозначний 4-предикат РB : D{T, F, TF, }:
РB (d) =
, якщо ( ) та ( ),
, якщо ( ) та ( ),
, якщо ( ) та ( ),
, якщо ( ) та ( ).
T d T P d F P
F d F P d T P
TF d T P d F P
d T P d F P
Композиційно-номінативні логіки квазіарних предикатів та багатозначні логіки
«Штучний інтелект» 1’2012 71
2Ш
З іншого боку, кожному тотальному однозначному 4-предикату РB зіставляємо
частковий неоднозначний 2-предикат Р:
T(P) = {dD | РB(d) = T або РB(d) = TF};
F(P) = {dD | РB(d) = F або РB(d) = TF}.
Тут маємо T(P) F(P) = {dD | РB(d) = T або РB(d) = F або РB(d) = TF} D,
тобто 2-предикат Р може бути нетотальним.
Тепер отримуємо:
(Р)B (d) =
, якщо ( ) та ( ),
, якщо ( ) та ( ),
, якщо ( ) та ( ),
, якщо ( ) та ( ),
T d T P d F P
F d F P d T P
TF d T P d F P
d T P d F P
=
=
, якщо ( ) та ( ),
, якщо ( ) та ( ),
, якщо ( ) та ( ),
, якщо ( ) та ( ).
T d F P d T P
F d T P d F P
TF d F P d T P
d F P d T P
Це відповідає такому визначенню логічної зв’язки B :
(B S)(d) =
, якщо ( ) ,
, якщо ( ) ,
, якщо ( ) ,
, якщо ( ) .
T S d F
F S d T
TF S d TF
S d
Отже, для так заданої B маємо B РB = (Р)B .
Шляхом нескладних, але громіздких викладок, для диз’юнкції отримуємо:
(РQ)B (d) =
, якщо ( ) та ( ),
, якщо ( ) та ( ),
, якщо ( ) та ( ),
, якщо ( ) та ( ),
T d T P Q d F P Q
F d F P Q d T P Q
TF d T P Q d F P Q
d T P Q d F P Q
=
=
, якщо ( ( ) або ( )) та ( ( ) або ( )),
, якщо ( ) та ( ) та ( ) та ( ),
, якщо ( ( ) або ( )) та ( ) та ( ),
, якщо ( ) та ( )
T d T P d T Q d F P d F Q
F d F P d F Q d T P d T Q
TF d T P d T Q d F P d F Q
d T P d T Q
та ( ( ) або ( )), d F P d F Q
=
=
, якщо ( ) або ( ) або
( ( ) та ( ) ) або ( ( ) та ( ) ),
, якщо ( ) та ( ) ,
, якщо ( ( ) та ( ) ) або
B B
B B B B
B B
B B
T P d T Q d T
P d TF Q d P d Q d TF
F P d F Q d F
TF P d TF Q d TF
( ( ) та ( ) ) або ( ( ) та ( ) ),
, якщо ( ( ) та ( ) ) або
( ( ) та ( ) ) або ( ( ) та ( ) ).
B B B B
B B
B B B B
P d TF Q d F P d F Q d TF
P d F Q d
P d Q d F P d Q d
Це відповідає наступному визначенню логічної зв’язки B :
(RB S)(d) =
, якщо ( ) або ( ) або
( ( ) та ( ) ) або ( ( ) та ( ) ),
, якщо ( ) та ( ) ,
, якщо ( ( ) та ( ) ) або
( (
T R d T S d T
R d TF S d R d S d TF
F R d F S d F
TF R d TF S d TF
R d
) та ( ) ) або ( ( ) та ( ) ),
, якщо ( ( ) та ( ) ) або
( ( ) та ( ) ) або ( ( ) та ( ) ).
TF S d F R d F Q d TF
R d F S d
R d Q d F R d S d
Таким чином, РBB QB = (РQ)B.
Шкільняк С.С.
«Искусственный интеллект» 1’201272
2Ш
Діючи аналогічно, для кон’юнкції отримуємо:
(Р&Q)B (d) =
, якщо ( & ) та ( & ),
, якщо ( & ) та ( & ),
, якщо ( & ) та ( & ),
, якщо ( & ) та ( & ),
T d T P Q d F P Q
F d F P Q d T P Q
TF d T P Q d F P Q
d T P Q d F P Q
=
=
, якщо ( ) та ( ) ,
, якщо ( ) або ( ) або
( ( ) та ( ) ) або ( ( ) та ( ) ),
, якщо ( ( ) та ( ) )
B B
B B
B B B B
B B
T P d T Q d T
F P d F Q d F
P d TF Q d P d Q d TF
TF P d TF Q d TF
або
( ( ) та ( ) ) або ( ( ) та ( ) ),
, якщо ( ( ) та ( ) ) або
( ( ) та ( ) ) або ( ( ) та ( ) ).
B B B B
B B
B B B B
P d TF Q d T P d T Q d TF
P d T Q d
P d Q d T P d Q d
Це відповідає наступному визначенню логічної зв’язки &B :
(R &B S)(d) =
, якщо ( ) та ( ) ,
, якщо ( ) або ( ) або
( ( ) та ( ) ) або ( ( ) та ( ) ),
, якщо ( ( ) та ( ) ) або
T R d T S d T
F R d F S d F
R d TF S d R d S d TF
TF R d TF S d TF
( ( ) та ( ) ) або ( ( ) та ( ) ),
, якщо ( ( ) та ( ) ) або
( ( ) та ( ) ) або ( ( ) та ( ) ).
R d TF S d T R d T S d TF
R d T S d
R d S d T R d S d
Таким чином, РB &K QB = (Р&Q)B.
&B традиційним способом виразна через B та B : P &B Q = B (B PBB Q).
Діючи подібним чином, можна ввести логічну зв’язку імплікацію B .
Імплікація B тех виражається через B та B : РB Q = B PB Q.
Ми отримали логіку тотальних однозначних 4-предикатів із логіки часткових
неоднозначних 2-предикатів природним чином: логічні зв’язки , , &, індукують
відповідні зв’язки B, B, &B, B . Виявляється, така 4-значна логіка фактично є відо-
мою логікою Л. Белнапа [7]. Ця логіка має сильний епістемічний відтінок, вона є зруч-
ним засобом формалізації відповідей на питання, якщо інформаційна система містить
суперечливі дані. При описі епістемічного стану системи треба брати до уваги як мож-
ливу суперечливість інформації, так і її відсутність. Як зазначає Белнап, можна виділити
4 випадки: отримане системою повідомлення підтверджено і не було спростовано;
повідомлення спростовано і не було підтверджено; про істиннісне значення повідом-
лення нічого не відомо; повідомлення було підтверджено і було спростовано. Цим ви-
падкам відповідають істиннісні значення T, F, , TF. Зрозуміло, що та TF мають
різний статус, тому традиційні 3-значні логіки тут неадекватні.
Виходячи з мінімальних припущень – монотонності, стандартних визначень кла-
сичних , , & на {T, F} та природних обмежень для і &: P&Q = P PQ = Q і
P&Q = Q PQ = P, отримано [7] єдине продовження , , & на {T, F, TF, }.
Виявилось, що так визначені в [7] зв’язки – це якраз описані вище B, B, &B .
Таким чином, діючи різними способами, приходимо до одного і того ж результату.
Це засвідчує особливу роль логіки Белнапа серед 4-значних логік, подібно до особ-
ливої ролі сильної логіки Кліні серед 3-значних логік.
Пропозиційною композиційною алгеброю Белнапа тотальних однозначних 4-пре-
дикатів назвемо предикатну алгебру (PrB, CB), де PrB – множина тотальних однозначних
4-предикатів на D, а CB задається базовими композиціями B та B .
Композиційно-номінативні логіки квазіарних предикатів та багатозначні логіки
«Штучний інтелект» 1’2012 73
2Ш
Реномінативною композиційною алгеброю Белнапа тотальних однозначних 4-пре-
дикатів назвемо предикатну алгебру (BPrA, CBR), де BPrA – множина тотальних одно-
значних 4-предикатів на A, а CBR задається базовими композиціями B, B, v
xR .
Трактуючи невизначеність як спеціальне значення , маємо повну відповідність
логіки часткових однозначних 3-предикатів та логіки тотальних однозначних 4-преди-
катів. Композиціям B та B тоді відповідають S та S.
Предикатну алгебру (SPr, CSP), де SPr – множина часткових однозначних 3-пре-
дикатів, а CSP задається базовими композиціями S та S, назвемо пропозиційною ком-
позиційною алгеброю часткових однозначних 3-предикатів.
Предикатну алгебру (SPrA, CSR), де SPrA – множина часткових однозначних квазі-
арних 3-предикатів на A, а CSR задається базовими композиціями S, S, ,v
xR назвемо
реномінативною композиційною алгеброю часткових однозначних 3-предикатів.
Нехай (PMPr, CP) та (PMPrA, CR) – пропозиційна та реномінативна композиційні
алгебри часткових неоднозначних 2-предикатів.
Отримані результати можна сформулювати так.
Теорема 3. Композиційні алгебри (PrB, CB), (SPr, CSP), (PMPr, CP) ізоморфні.
Теорема 4. Композиційні алгебри (BPrA, CBR), (SPrA, CSR), (PMPrA, CR) ізоморфні.
Висновки
У роботі досліджено композиційно номінативні логіки часткових однозначних,
тотальних неоднозначних і часткових неоднозначних квазіарних предикатів на пропо-
зиційному і реномінативному рівнях. Встановлено зв’язки між цими логіками та 3-знач-
ними і 4-значними логіками тотальних однозначних предикатів. Доведено ізоморфізм
композиційної алгебри Кліні тотальних однозначних предикатів 3-значної логіки та
композиційних алгебр тотальних неоднозначних і часткових однозначних предикатів
2-значної логіки, ізоморфізм композиційної алгебри Белнапа тотальних однозначних
предикатів 4-значної логіки та композиційних алгебр часткових неоднозначних преди-
катів 2-значної логіки і часткових однозначних предикатів 3-значної логіки. Це під-
креслює особливу роль сильної логіки Кліні серед 3-значних логік та логіки Белнапа
серед 4-значних.
Проведене дослідження планується продовжити для першопорядкових логік.
Література
1. Никитченко Н.С. Композиционно-номинативный подход к уточнению понятия программы / Н.С. Ни-
китченко // Пробл. программирования. – 1999. – № 1. – С. 16-31.
2. Нікітченко М.С. Математична логіка та теорія алгоритмів / М.С. Нікітченко, С.С. Шкільняк. – К. :
ВПЦ Київський університет, 2008. – 528 с.
3. Шкільняк С.С. Відношення логічного наслідку в композиційно-номінативних логіках / С.С. Шкіль-
няк // Пробл. програмування. – 2010. – № 1. – C. 15-38.
4. Смирнова Е.Д. Логика и философия / Смирнова Е.Д. – М.: РОССПЕН, 1996. – 304 с.
5. Клини С. Введение в метаматематику / Клини С. – М. : ИЛ, 1957. – 526 с.
6. Буй Д.Б. Загальнозначні теоретико-множинні конструкції повного образу, обмеження, сумісності: влас-
тивості та застосування / Д.Б. Буй, Н.Д. Кахута, Л.М. Сільвейструк // Пробл. програмування. – 2010. –
№ 2-3 – C. 80-88.
7. Белнап Н. Логика вопросов и ответов / Н. Белнап, Т. Стил. – М. : Прогресс, 1981. – 288 с.
Lіteratura
1. Nikitchenko N.S. Probl. programmirovanija. 1999. № 1. S. 16-31.
2. Nіkіtchenko M.S. Matematychna logіka ta teorіja algorytmіv. K. : VPC Kyivs’kyj unіversytet. 2008. 528 s.
3. Shkіl’njak S.S. Probl. programuvannja. 2010. №1. S. 15-38.
Шкільняк С.С.
«Искусственный интеллект» 1’201274
2Ш
4. Smirnova E.D. Logika i filosofija.M.: ROSSPEN. 1996. 304 s.
5. Klini S. Vvedenie v metamatematiku. M. : IL, 1957. 526 s.
6. Buj D.B. Probl. programuvannja. 2010. № 2-3. S. 80-88.
7. Belnap N. Logika voprosov i otvetov. M. : Progress. 1981. 288 s.
S.S. Shkilniak
Сomposition Nominative Logics of Quasiary
Predicates and Many-Valued Logics
Classical predicate logic has a number of fundamental limitations, which complicate
its application in informatics and programming. All this makes topical the problem of
construction and investigation of new program oriented logical formalisms. Composition
nominative approach is common for logic and programming, therefore it is a natural basis
for such a construction. Partial, not always single-valued mappings are rather common in
programming and modelling. Thus, it makes important to study logics with non-traditional
semantics. In this paper we investigate composition nominative logics of partial single-
valued, total multiple-valued and partial multiple-valued quasiary predicates. As a main
result, we establish a connection between the studied logics and many-valued logics of
total single-valued predicates at propositional and renominative levels.
We consider connections between two-valued logics of total multiple-valued and
partial single-valued predicates and Kleene’s strong ternary logic of total single-valued
predicates.
Theorem 1. Kleene’s propositional compositional algebra of total single-valued 3-
predicates (PrK, CK) and propositional compositional algebra of total multiple-valued 2-
predicates (TMPr, CP) are isomorphic.
As a corollary, the following algebras are isomorphic: (PrK, CK), (TMPr, CP), and
(PSPr, CP), where (PSPr, CP) is a propositional compositional algebra of partial single-
valued 2-predicates.
Theorem 2. Kleene’s renominative compositional algebra of total single-valued 3-
predicates (KPrA, CKR), renominative compositional algebra of total multiple-valued 2-
predicates (TMPr A, CR), and renominative compositional algebra of partial single-valued 2-
predicates (PSPr A, CR) are isomorphic.
There is a close connection between two-valued logic of partial multiple-valued
predicates and the well-known Belnap’s four-valued logic of total single-valued predicates.
This logic was presented to describe epistemic states of an information system with possibly
inconsistent data.
Let (PrB, CB) and (BPrA, CBR) are Belnap’s propositional and renominative
compositional algebras, (SPr, CSP) and (SPrA, CSR) are propositional and renominative
compositional algebras of partial single-valued 3-predicates, (PMPr, CP) and (PMPrA, CR) are
propositional and renominative compositional algebras of partial multi-valued 2-predicates.
Theorem 3. Compositional algebras (PrB, CB), (SPr, CSP), (PMPr, CP) are isomorphic.
Theorem 4. Compositional algebras (BPrA, CBR), (SPrA, CSR), (PMPrA, CR) are isomorphic.
The obtained results emphasize the special role of Belnap’s logic among four-valued
logics, similar to the role of Kleene’s strong logic among ternary logics.
Стаття надійшла до редакції 02.12.2011.
|