ПЕРШОПОРЯДКОВІ КОМПОЗИЦІЙНО-НОМІНАТИВНІ ЛОГІКИ ІЗ УЗАГАЛЬНЕНИМИ РЕНОМІНАЦІЯМИ МСНікітченко ОСШкільняк ССШкільняк ПЕРШОПОРЯДКОВІ КОМПОЗИЦІЙНО-НОМІНАТИВНІ ЛОГІКИ ІЗ УЗАГАЛЬНЕНИМИ РЕНОМІНАЦІЯМИ 9C7A5A556F5CD8DEED2D8C951006CD88 GROBID - A machine learning software for extracting information from scholarly documents

Досліджено першопорядкові композиційно-номінативні логіки часткових однозначних, тотальних неоднозначних та часткових неоднозначних квазіарних предикатів. Запропоновано розширення цих логік узагальненими реномінаціями та спеціальними предикатами-індикаторами наявності значення для предметних змінних. Описано мови та семантичні моделі таких логік, досліджено їх семантичні властивості, зокрема, властивості відношень логічного наслідку.

First-order composition-nominative logics of partial single-valued, total multi-valued, and partial multi-valued quasiary predicates are investigated. It is proposed to extend these logics with generalized renominations and special predicates that detect if the subject variables have assigned values. Languages and semantic models of such logics are defined, their semantic properties, in particular, the properties of relations of logical consequence are studied.

Вступ

Розвиток інформаційних технологій зумовлює невпинне розширення сфери застосування математичної логіки. Розроблено багато різноманітних логічних систем (див., напр., [1]), які доводять свою ефективність при розв'язанні широкого кола задач інформатики й програмування. В основі таких систем зазвичай лежить класична логіка предикатів. Водночас поява нових застосувань логіки в інформатиці й програмуванні висвітила принципові обмеження класичної логіки предикатів, які ускладнюють її використання. Така логіка недостатньо враховує неповноту, частковість інформації про предметну область, її структурованість. Обмеження класичної логіки роблять вельми актуальною проблему побудови програмно-орієнтованих логічних формалізмів. Таку побудову природно вести на базі спільного для логіки і програмування композиційно-номінативного підходу (див. [2]). Композиційно-номінативні логіки (КНЛ) -це логічні формалізми, збудовані на основі цього підходу. Передумовою їх виникнення стала необхідність посилення можливостей класичної логіки для розв'язання нових задач інформатики й програмування. КНЛ базуються на загальних класах часткових відображень, заданих на довільних наборах іменованих значень. Такі відображення названо квазіарними.

Метою даної роботи є побудова нових класів КНЛ квазіарних предикатів. Пропонується розширення чистих першопорядкових КНЛ (ЧКНЛ) шляхом введення узагальнених реномінацій та спеціальних предикатівіндикаторів наявності значення для предметних імен (змінних).

ЧКНЛ з узагальненими (розширеними) реномінаціями названо ЧКНЛРР, вони запропоновані в [3]. Використання композицій розширеної реномінації (перейменування) дає змогу явно задавати відсутність значення для предметних імен, тобто вилучати з вхідних даних компоненти з певними іменами. За допомогою композицій розширеної реномінації визначаємо композиції розширеної квантифікації (розширені квантори).

Характерною особливістю КНЛ є те, що значення предиката P(d) може бути різним залежно від того, входить чи не входить до d компонента з певним іменем. Тому при інтерпретаціях формул варто явно вказувати означені та неозначені предметні імена. Для цього запропоновано [4] спеціальні 0-арні композиції -предикатиіндикатори z, які визначають наявність в даних компоненти з відповідним іменем z, тобто наявність значення для z. Предикати-індикатори використовуються (див. [3,[5][6][7]) для дослідження КНЛ. Чисті першопорядкові КНЛ з виділеними предикатами-індикаторами названі -ЧКНЛ.

Логіки, пропоновані в даній роботі, поєднують можливості ЧКНЛРР та -ЧКНЛ. Такі логіки будемо називати -ЧКНЛРР. Ми досліджуємо -ЧКНЛРР часткових однозначних, тотальних неоднозначних і часткових неоднозначних предикатів. Розглянуто семантичні властивості -ЧКНЛРР, особливу увагу приділено вивченню відношень логічного наслідку. Властивості таких відношень є семантичною основою побудови для пропонованих логік числень секвенційного типу, що буде зроблено в наступних роботах.

Поняття, які в роботі не визначаються, тлумачимо в сенсі [2, 3, 5]. Для полегшення читання наведемо деякі визначення, необхідні для подальшого викладу. V-іменна множина (V-ІМ) над A -це довільна однозначна часткова функція  : VA. Тут V і A -множини предметних імен і предметних значень. V-ІМ подаємо у вигляді [v 1 a 1 ,...,v n a n ,...]. Тут v і V, a і A, v і  v j при і  j. Для V-ІМ введемо функцію asn : V A2 V : asn() = {vV | va для деякого aA}. Введемо параметричну операцію || -х видалення компоненти з іменем х:  || -х = {va  | v  х}.

Операцію  накладки V-ІМ  на V-ІМ  задаємо так:  =   ( || -asn() ). V-квазіарний предикат на А -це довільна (часткова неоднозначна, взагалі кажучи) функція вигляду P : V A  {T, F}, де {T, F} -множина істиннісних значень.

Ми трактуємо часткові неоднозначні предикати на множині V A як відповідності (відношення) між V A та множиною {T, F}. Такі предикати називаємо предикатами реляційного типу, вони формалізують найпростіше уточнення поняття часткового неоднозначного предиката. Ми використовуємо позначення P(d) для множини тих значень, які предикат P : V А  {T, F} може прийняти на d V A. Зрозуміло, що P(d)  {T, F}.

Область істинності та область хибності предиката P : V A  {T, F} -це множини

T(P) = {d V A | TP(d)}, F(P) = {d V A | FP(d)}. V-квазіарний предикат P на A:

-неспростовний, якщо F(P) = ;

-виконуваний, якщо T(P)  ; -тотально істинний, якщо T(P) = V A;

-тотально хибний, якщо F(P) = V A; -тотожно істинний, якщо T(P) = V A і F(P) = ;

-тотожно хибний, якщо T(P) =  і F(P) = V A;

-всюди невизначений, якщо T(P) = F(P) = ; -тотально насичений, якщо T(P) = V A та F(P) = V A. Надалі тотожно істинний предикат позначаємо як T, тотожно хибний -як F, всюди невизначений -як .

Композиції першопорядкових КНЛ із узагальненими реномінаціями

Введемо операції розширеної реномінації, які дають змогу явно задавати відсутність значення для предметних імен, тобто вилучати компоненти з певними іменами. Відсутність значення для імені x задаємо парою, де верхнє ім'я -x, a відповідне нижнє ім'я -спеціальний символ .

Операція розширеної реномінації. Операція 1 1 1 ,..., , ,..., ,..., , ,...,

n m n v v u u x x r   : V А  V A визначається так: 1 1 1 1 1

,..., , ,..., { ,..., , ,..., } ,..., , ,..., ( ) ||

n m n m n v v u u v v u u x x r        [v 1 (x 1 ),...,v n (x n )].

Зокрема, ( ) || . Зокрема: , , , , , , , , r ( ) r ( ); r ( ) r ( ).

y v u y u v u u x y x y d d d d       Із визначення операції , , v z y r  випливає її монотонність: якщо d 1  d 2 , то , , ,v z v z y y r d r d    .

Нехай , , , , , u s w t v z задають попарно диз'юнктні (такі, що попарно не перетинаються) множини імен.

Послідовне застосування двох операцій реномінації

u s w t v s z t x a y c r      Справді, для кожного d V A маємо ( ( ) ) ( ) u s w t v s z t u s v w z t x a y c p q y r r d r d         , де кожне { } i p p  та кожне { } i q q  задаються так: , якщо для деякого { }, , якщо для деякого { }, , якщо { , , , }, , якщо для деякого { }, , якщо для деякого { }; j i j j j i j j i i i i j j i j j y x v v v q x s s s p x x v s z t x z z z x t t t                    , якщо для деякого { }, , якщо для деякого { }, , якщо { , , , }, , якщо для деякого { }, , якщо для деякого { }. j i j j j i j j i i i i j j i j j y a v v v q a s s s q a a v s z t a z z z a t t t                   

Так визначену операцію реномінації , , , , , , , , , , u s v w z t p q y r    назвемо згорткою операцій реномінації

u s w t v s z t x a y c r      Таким чином, для кожного d V A маємо: , , ,u s w t v s z t x a y c r r d ( ) ( ). u s v w z t u s w t v s z t p q y x a y c r d r d           Композиції -ЧКНЛРР. Базовими композиціями -ЧКНЛРР є пропозиційні зв'язки заперечення  та диз'юнкція , композиції розширеної реномінації , , R v u x  , квантифікації x та спеціальні 0-арні композиції -пре- дикати-індикатори z. Композиції реномінації R v x є окремим випадком композицій , ,

R v u 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(xP) = {d V A | TР(dxa) для деякого aA}; F(xP) = {d V A | FР(dxa) для всіх aA}. Композиція розширеної реномінації. Композицію розширеної реномінації (розширену реномінацію) , , R v u x  визначаємо за допомогою операції розширеної реномінації , , v u x r  традиційним чином: , , , , R ( )( ) ( ( )) v u v u x x P d P r d    . Композицію , , R v u x  можна визначити через області істинності та хибності предиката , , R ( ) v u x P  : T , , (R ( )) v u x P  = {d V A | , , r ( ) v u x d  T(P)} = , 1 , (r ) v u x   (T(P)); F , , (R ( )) v u x P  = {d V A | , , r ( ) v u x d  F(P)} = , 1 , (r ) v u x   (F(P)). Твердження 1. Нехай zV неістотне для Р. Тоді , , , , , , R ( ) R ( ) z v u v u y x x P P    . Твердження 2. Ім'я хV неістотне для , , , , R ( ) v u x y P   , якщо { } x y  . При { } x y  для всіх d V A та aA маємо: , , , , R ( ) v u x y P   (dxa) = , , , , R ( ) v u x y P   (d || -х ).

До основних властивостей композицій

, , R v u x  також належать: R  T) , ,

)

z v u v u z x x P P    -згортка тотожної пари імен у реномінації; зокрема, , , R ( ) R ( ) z u u z P P    ; R  ) , , , , R ( ) R ( ) v u v u x x P P      -R-дистрибутивність; R  ) , , , , , , R ( ) R ( ) R ( ) v u v u v u x x x P Q P Q       -R-дистрибутивність; R  U) нехай zV (строго) неістотне для предиката Р, тоді , , , , , , R ( ) R ( ) z v u v u y x x P P    ; R  R) , , , , R (R ( )) v z u t y x P   = , , , , R ( ) v z u t y x P    -згортка реномінацій.

Згортка композицій реномінації задається через згортку операцій реномінації:

, , , , R ( ) v z u t y x P    (d) = ( , , R v z y  ( , , R ( )))( ) u t x P d  = ( , , , , R ( ))( ( )) u t v z x y P r d   = , ,) u t v z x y P r r d   = , , , ,

.

u t v z x y P r d   R  ) y , , R ( ) v u x P   , , R ( ) v u x yP   за умови { , , } y v x u  -обмежена R-дистрибутивність; R  ) , , , , R ( ) R ( ), v u v u y x x z yP z P      якщо z неістотне для P та z{ , , } v x u -R-дистрибутивність.

Якщо z неістотне для Р, то маємо R ( )

y z yP z P   . Звідси , , , , R ( ) R ( R ( )). v u v u y x x z yP z P      При z{ , , } v x u згідно R   та R  R маємо , , , , , , R ( R ( )) R (R ( )) R ( ). v u y v u y v u y x z x z x z z P z P z P        Згортка пари імен реномінації за квантифікованим верхнім іменем: R  R) , , , , R ( u w x v y  хР) = , , R ( u w v  хР) та , , , , R ( u w x v   хР) = , , R ( u w v  хР) (тут { , } x u w  за визначенням реноміна- ції). Подібним чином можна додатково записати властивості R  , R  &, R  ; R  , R  , R  R.

Неістотність верхніх імен в реномінаціях:

NR  ) y , , , , R ( ) y v u z x P   , , , , R ( ) y v u z x P  та , , , , R ( ) y v u z x y P    , , , , R ( ) y v u z x P  при умові y{ , z x }.

Предикати-індикатори наявності значення для предметних імен. Cпеціальні 0-арні композиції -предикати-індикатори z наявності значення для відповідних zV, -визначаємо так:

T(z) = {d | d(z)} = {d V A | zasn(d)}; F(z) = {d | d(z)} = {d V A | zasn(d)}.

Із визначення випливає, що предикати z не є монотонними та не є антитонними.

Кожне xV таке, що x  z, (строго) неістотне для предикатa z. Розглянемо основні семантичні властивості предикатів-індикаторів. 1. Властивості предикатів z, пов'язані з їх квантифікацією за тим же іменем z.

z z =  z z = F, z z =  z z = T.

2. Властивості предикатів z, пов'язані з їх квантифікацією за іншим іменем x: x z =  x z = z; x z =  x z = z.

3. Властивості предикатів z, пов'язані із зв'язками та кванторами за тим же іменем z.

z(z&P) =  z(z&P) = F; z(zP) =  z(zP) = T; z(zP) = z(z&P) = zP;  z(zP) =  z(z&P) =  zP.

4. Властивості предикатів z, пов'язані із зв'язками та кванторами за іншим іменем x:

x(Pz) = xPxz = xPz; x(Pz) = xPxz = xPz; x(P&z) = xP&xz = xP&z; x(P&z) = xP&xz = xP&z;  x(Pz) =  xP  xz =  xPz;  x(Pz) =  xP  xz =  xPz;  x(P&z) =  xP&xz =  xP&z;  x(P&z) =  xP&  xz =  xP&z. 5. Властивості реномінації предикатів-індикаторів z: a) , , , , R ( ) v u z x y z y     ; зокрема: , , R ( ) , x z y u z u    R ( ) ; z y z y    b) , , R ( ) , v u x z z     якщо { , }; z v u  зокрема: R ( ) , x y z z    якщо { }; z x  c) R ( ) ; v x z z    R ( ) ; u z z     d) , , , , R ( ) T; v u z x z     зокрема: , , R ( ) T, v z x z    R ( ) T. z z   

Збереження монотонності, антитонності, тотальності предикатів. Пропозиційні зв'язки, реномінації та квантори зберігають [5,8] монотонність і антитонність предикатів. Це вірно і для розширеної реномінації.

Твердження 3. Композиції , , R v u y  зберігають монотонність і антитонність предикатів. Нехай d 1  d 2 та предикат Р монотонний, предикат Q антитонний. Із d 1  d 2 отримуємо , ,) ( ), v z v z y y r d r d    звідки за монотонністю Р маємо , ,( ( )), v z v z y y P r d P r d    за монотонністю Q маємо , ,( ( )). v z v z y y Q r d Q r d    Отже, якщо Р монотонний, то , , R v u y P  монотонний; якщо Q антитонний, то , , R v u y Q  антитонний.

Наслідок 1. Базові композиції -ЧКНЛРР (окрім спеціальних 0-арних композицій -предикатів-індикаторів z) зберігають монотонність і антитонність предикатів.

Твердження 4. Композиції , , R v u y  зберігають тотальність предикатів. Нехай Р тотальний. Для кожного d V A маємо , , , , R ( )( ) ( ( )), v u v u y y P d P r d    але за тотальністю Р маємо , ,) v u y P r d   для кожного d V A, тому , , R ( )( ) v u y P d   для кожного d V A, тобто , , R ( ) v u y P  -тотальний.

Як наслідок можна отримати, що композиції R v y зберігають тотальність предикатів. Твердження 5. Композиції , , xP зберігають тотальність предикатів. Для пропозиційних композицій твердження очевидне. Нехай Р тотальний. Маємо xP(d), якщо немає таких aA, що P(dxa) = T, та P(dxс) для деяких сA. За тотальностю P неможливо P(dxс). Отже, xP(d) для кожного d V A, тобто xP -тотальний.

u w x v y T P   F(y)  , , (R ( )) u w v T x P   (TR  d) , , (R ( )) u w v F xP    F(y)  , , , , (R ( )) u w x v y F P  (FR  d) Твердження 6. A  F(z)  B  A  B  T(z); A  T(z)  B  A  B  F(z).

Враховуючи твердження 7, із теореми 1 отримуємо:

Наслідок 4. Для -ЧКНЛРР справджуються наступні співвідношення: , , , , (R ( )) u w x v y T P   T(y)  , , (R ( )) u w v T x P   (TR  u) , , (R ( )) u w v F xP    T(y)  , , , , (R ( )) u w x v y F P  (FR  u)

Як окремий випадок TR  d, FR  d, TR  u, FR  u отримуємо властивості (фактично вже на рівні ЧКНЛ):

(R ( ))

x y T P  F(y)  T(xР); F(xР)  F(y)  (R ( ))

x y F P ;

(R ( ))

x y T P  T(y)  T(xР); F(xР)  T(y)  (R ( ))

x y F P .

Розширені квантори. Введемо композиції узагальненої (розширеної) квантифікації, або розширені квантори, які враховують відсутність значення для квантифікованого імені. Для обґрунтування визначення цих композицій задамо множини істинності та хибності предиката Р на даних із доданою компонентою xa:

( ) x a T P = {d V A | Р(dxa = T} = {d V A | Р(d || -х + xa) = T}; ( ) x a F P = {d V A | Р(dxa = F} = {d V A | Р(d || -х + xa) = F}.

Тоді визначення композицій x та x можна подати так:

T(xP) = ( ) x a a A T P   ; F(xP) = ( ) x a a A F P   ; T(xP) = ( ) x a a A T P   ; F(xP) = ( ) x a a A F P   .

Введемо множини істинності та хибності предиката Р на даних, які не містять компоненти з іменем х:

( ) x T P  = {d V A | Р(d || -х ) = T}; ( ) x F P  = {d V A | Р(d || -х ) = F}. Враховуючи, що ( ) || , x x r d d    тоді маємо ( ) { | ( ( )) } { | R ( )( ) } (R ( )) x V x V x x T P d A P r d T d A P d T T P            ; ( ) { | ( ( )) } { | R ( )( ) } (R ( )) x V x V x x F P d A P r d F d A P d F F P            .

Композиції розширеної квантифікації   x та   x задаємо так:

T(  xP) = T(xP) ( ) x T P   = ( ) ( ) x x a a A T P T P     ; F(  xP) = F(xP) ( ) x F P   = ( ) ( ) x x a a A F P F P     ; T(  xP) = T(xP) ( ) x T P   = ( ) ( ) x x a a A T P T P     ; F(  xP) = F(xP) ( ) x F P   = ( ) ( ) x x a a A F P F P     . Враховуючи, що ( ) (R ( )) x x T P T P    та ( ) (R ( )) x x F P F P    , маємо еквівалентні визначення   x та   x:   xP = xP  R ( ); x P    xP = xP &R ( ). x P  Отже, при наявності розширених реномінацій композиції   x та   x є похідними.

Для розширених кванторів справджуються закони де Моргана:

  xP =   xP;   xP =   xP.

Розглянемо властивості розширеної квантифікації предикатів-індикаторів.

1. Властивості квантифікації предикатів-індикаторів x за тим же іменем x:

  x x = x x R ( ) x x    = F  T = T;   x x = x x R ( ) x x    = T  F = T;   x x = x x &R ( ) x x   = F  T = F;   x x = x x &R ( ) x x   = T  F = F. 2.

Для предикатів-індикаторів z, квантифікованих за іншим іменем x, отримуємо:

  x z = x z R ( ) x z    = z  z = z;   x z = x z R ( ) x z    = z  z = z;   x z = x z &R ( ) x z   = z  z = z;   x z = x z &R ( ) x z   = z  z = z. Порівняємо властивості розширеної квантифікації предикатів-індикаторів. 1)   x x = T, водночас x x = F; 2)   x x = x x = F;   x x = x x = T; 3)   x x = F, водночас x x = T; 4) x z = x z = z та   x z =   x z = z; 5) x z = x z = z та   x z =   x z = z.

Із визначення композицій розширеної квантифікації та наслідків 1 і 2 отримуємо: Наслідок 5. Композиції   x та   x зберігають монотонність, антитонність і тотальність предикатів. Позначимо nm() множину всіх імен із V, які фігурують у символах реномінації та квантифікації, що входять до складу формули . Таку nm() назвемо множиною імен формули .

Семантичні моделі та мови -ЧКНЛРР

Позначимо q() множину всіх імен із V, які фігурують у символах квантифікації формули . Таку q() назвемо множиною кванторних імен формули .

Природним чином (за об'єднанням) розширимо пт та q на множини формул. Інтерпретуємо мову на композиційних системах ( V A, ( )

n m n v v u u x x R    = ((){v 1 ,...,v n , u 1 ...,u m }) \ {x i | v i (), i{1,…, n}}.

Множина тотально неістотних імен -це множина V T = ( )

p Ps p    . Теорема 2.

Нехай х (); тоді х неістотне для .

Для виконання еквівалентних перетворень формул та пронесення реномінацій через квантори необхідно мати наперед необмежену множину тотально неістотних імен (див. властивість R  ). Тому для -ЧКНЛРР постулюємо нескінченність множини V T .

Квазівільні предметні імена. Поняття квазівільних предметних імен та квазізамкненої формули для -ЧКНЛРР вводимо подібно випадку ЧКНЛ [2]. Входження в формулу нижнього імені х символа реномінації зв'язане, если воно знаходиться в області дії кванторного префікса x, інакше таке входження вільне.

Множину fr() квазівільних імен формули  визначимо за допомогою функції fr : Fr2 V . Маємо fr(р) =  для кожного рPs; далі fr визначаємо так:

fr(z) = {z} для кожного zV; fr() = fr(); fr() = fr()fr(); fr(x) = fr()\{x}; , ,)\{ , }) { } v u x fr R fr v u x      .

Квазівільні імена є певним аналогом вільних змінних класичної логіки. Формула  квазізамкнена, якщо fr() = . Квазізамкнені формули є синтаксичними аналогами замкнених формул класичної логіки [2,9], проте семантичними аналогами таких формул їх вважати не можна (див. [2]). До складу формули мови -ЧКНЛРР можуть входити предикатні символи, для яких множини істотних імен необов'язково скінченні. Можливість для формули бути залежною від наперед необмеженої множини предметних імен -визначальна властивість логік квазіарних предикатів, що істотно їх відрізняє від класичної.

Дуальні моделі мови. Поняття дуальних моделей мови та дуальних семантик для випадку -ЧКНЛРР вводимо так, як для ЧКНЛ. Модель мови B = (A, I B ) назвемо дуальною до моделі мови A = (A, I A ), якщо для кожного Ps маємо ( ) ( )

B A T F    та ( ) ( ) B A F T    . Якщо B дуальна до A, то ( ) ( ) A B T F    та ( ) ( ) A B F T    , тобто A дуальна до B.

Якщо модель мови A = (A, I A ) -АС з частковими однозначними предикатами, то дуальна модель мови B = (A, I B ) -АС з тотальними неоднозначними предикатами, та навпаки.

Теорема 3. Нехай B = (A, I B ) дуальна до A = (A, I A ). Тоді для кожної формули :

1) ( ) ( ) B A T F    та ( ) ( ) B A F T    ; 2) A  монотонний  B  антитонний; A  антитонний  B  монотонний.

П.1 теореми доводимо індукцією за побудовою формули, п.2 безпосередньо випливає з визначень.

Наслідок 6. A  неспростовний на A із частковими однозначними предикатами (неокласична семантика)  B

 тотально істинний на дуальній B із тотальними неоднозначними предикатами (пересичена семантика).

Цей факт можна сформулювати так: неокласична семантика та пересичена семантика дуальні.

Теорема 4. 1) У випадку неокласичної семантики множина тотально істинних формул порожня;

2) у випадку пересиченої семантики множина неспростовних формул порожня;

3) у випадку загальної семантики множини тотально істинних та неспростовних формул порожні.

Семантичні властивості формул -ЧКНЛРР

Відношення логічного наслідку. Введемо відношення наслідку для двох формул мови -ЧКНЛРР при інтерпретації на фіксованій моделі мови A (це робиться аналогічно випадку ЧКНЛ [8]):

1) Істиннісний наслідок A |= T : A  |= T   T( A  )  T( A ). 2) Хибнісний наслідок A |= F : A  |= F   F( A )  F( A  ). 3) Cильний наслідок A |= TF : A  |= TF   T( A )  T( A ) та F( A )  F( A  ). 4) Неспростовнісний (неокласичний) наслідок A |= Cl : A  |= Cl   T( A )F( A ) = . 5) Насичений наслідок A |= Cm : A  |= Cm   F( A  )T( A ) = V A.A    , якщо A  |=   та  A |=  .

Звідси, зокрема, отримуємо:

A   TF   T( A  ) = T( A ) та F( A  ) = F( A ). Отже, A   TF  означає, що A  та  A -це один і той же предикат. Відношення логічної еквівалентності  T ,  F ,  TF ,  Cl ,  Cm визначаємо за схемою:    , якщо  |=   та  |=  .

Зрозуміло, що      A     для кожної моделі мови A. Для відношень  T та  F теорема 5, взагалі кажучи, невірна (див. [5,8]).

На пропозиційному рівні властивості відношень логічного наслідку та логічної еквівалентності в різних семантиках для формул мови -ЧКНЛРР такі ж, як для формул мови ЧКНЛ (див. [5,8]).

Властивості формул, пов'язані з реномінаціями. На базі відповідних властивостей предикатів маємо:

R  T) , ,z v u v u z x TF x R R      ; зокрема, ,z u u z T F R R      ; R  U) нехай zV неістотне для Ф, тоді , ,z v u v u y x TF x R R      ;

Ren) нехай zV неістотне для Ф, тоді ( )

x TF z x z R      ; R  ) , ,v u v u x T F x R R       ; R  ) , ,( ) v u v u v u x T F x x R R R           ; R  R) , ,( ) v z u t v z u t y x T F y x R R R         ; R  ) , ,v u v u x T F x R y yR        за умови { , , } y v x u  ; R  ) , , ,v u v u y x T F x z R y zR         за умови zV T та z , ,)) v u x nm R x    . Подібним чином можна записати властивості R  , R  &, R  , R  R, R  , R  . R  R) , ,u w x u w v y TF v R x R x        та , ,u w x u w v T F v R x R x         (тут { , } x u w  ); NR  ) При y{ , z x } маємо , ,y v u y v u TF z x z x yR R       та , ,y v u y v u TF z x z x yR R       .

Основні властивості формул мови -ЧКНЛРР, які пов'язані з кванторами та не використовують реномінації, такі ж, як для формул в мови ЧКНЛ (див. [5,8]).

Властивості формул, пов'язані з предикатами-індикаторами. Зазначені властивості індуковані наведеними вище відповідними властивостями предикатів. Формули, які задають предикати T та F, назвемо константними. Такими є формули:

R  ) , , ( ) , v u x T F R z z     якщо { , }; z v u  dR  ) , , , , ( ) ; v u z x y TF R z y     зокрема,x x A = x x A = T; x(x) A = x(x) A = T; x x A = x x A = F; x(x) A = x(x) A = F; , , , , ( ) T; v u z x A R z     зокрема: , , ( ) T, v z x A R z    ( ) T; z A R z   

Також маємо: x(x) A = x(x&) A = x(x&) A = T; x(x) A = x(x&) A = x(x&) A = F.

Формули вигляду x x, x x, x(x), x(x), , , , , ( )

v u z x R z    назвемо T-формулами.

Формули вигляду x x, x x, x(x), x(x),

Предикат P : V A{T, F} монотонний, якщо з умови d  d' випливає P(d)  P(d'). Предикат P : V A  {T, F} антитонний, якщо з умови d  d' випливає P(d)  P(d'). Предметне ім'я zV (строго) неістотне для предиката P, якщо з умови d 1 || -х = d 2 || -х випливає P(d 1 ) = P(d 2 ).
Ввівши позначення y для y 1 ,..., y n , будемо також скорочено писати ,
Наслідок 2 .Базові композиції -ЧКНЛРР зберігають тотальність предикатів. Наслідок 3. Предикат  не може бути виражений через предикати y за допомогою , , , , R v u y  , x. Елімінація кванторів. Розглянемо властивості -ЧКНЛРР, пов'язані з елімінацією кванторів. Теорема 1. Справджуються наступні співвідношення:
Семантичними моделями -ЧКНЛРР є композиційні системи квазіарних предикатів кванторного рівня вигляду ( V A, A P r , C), де C задана множиною базових композицій {, , , z}. Така композиційна система задає неокласичну алгебру (алгебраїчну систему) даних (A, A P r ) та композиційну алгебру предикатів ( A P r , C). Побудова композиційної системи визначає мову логіки: терми алгебри предикатів трактуємо як формули мови.-ЧКНЛРР можна трактувати як окремий підрівень ЧКНЛ із базовими композиціями , , , z. Враховуючи, що предикати-індикатори не є монотонними та не є антитонними, поняття -ЧКНЛРР не розглядаємо для логік еквітонних та логік антитонних предикатів.Алфавіт мови -ЧКНЛРР: множина V предметних імен; множина Ps предикатних символів (ПС) -сигнатура мови; символи базових композицій , , , z. Множина Fr формул мови визначається так:-Ps  Fr та {z | zV}  Fr; формули вигляду pPs та z -атомарні; -, Fr  , Ф,
на основі тотального однозначного відображення I : Ps  A P r , яке позначає символами множини Рs базові предикати. Кожна формула вигляду z, де zV, інтерпретується як відповідний предикат-індикатор z. Такі формули z завжди інтерпретуються однаково, тому ці формули та самі предикатиіндикатори, які є їх значенням, ми позначаємо однаково; про що саме йдеться, має бути зрозумілим з контексту. Для складних формул відображення I : Fr  A P r задається згідно побудови формул із простіших за допомогою символів базових композицій: -I() = (I()), I() = (I(), I()), x) = x(I()). Відображення I пов'язує алгебру даних (А, Pr) із мовою -ЧКНЛРР. Отримуємо об'єкт ((A, A P r ), I) -алгебраїчну систему (АС) з доданою сигнатурою, яка визначає композиційну систему ( V A, A P r , C). АС з доданою сигнатурою є інтегрованими семантичними моделями, які пов'язують мови КНЛ із алгебрами даних. Називаємо їх моделями мови та скорочено позначаємо A = (A, I). Предикат I() -значення формули  при інтерпретації на A, -далі позначаємо A  . Водночас предикати-індикатори позначаємо z, опускаючи індекс, який позначає модель мови. Ім'я xV неістотне для формули , якщо для кожної моделі мови A ім'я x неістотне для предиката A  . Для -ЧКНЛРР традиційним чином (так, як для ЧКНЛ) визначаємо наступні важливі семантичні поняття. Формула  частково істинна при інтерпретації на A = (A, I), або A-неспростовна, якщо A  -частково істинний (неспростовний) предикат. Формула  частково iстинна, або неспростовна, якщо  A-неспростовна на кожній моделі мови A. Формула  виконувана при інтерпретації на моделі мови A, або A-виконувана, якщо A  -виконуваний предикат. Формула  виконувана, якщо  A-виконувана на кожній моделі мови A. Подібним чином даємо визначення: -тотально істинної на A та тотально істинної формули; -тотально хибної на A та тотально хибної формули; -тотожно істинної на A та тотожно істинної формули; -тотожно хибної на A та тотожно хибної формули. Синтетично неістотні предметних імена. Для кожного рPs множину синтетично неістотних предметних імен задамо за допомогою тотальної функції  : Ps2 V . Продовжимо її до  : Fr2 V : (z) = V\{z} для кожного zV; () = (Ф); () = ()(); (x) = (){x};
Теорема 7 .та F-формули назвемо виділеними константними -формулами.Нормальні форми. Кожну формулу -ЧКНЛРР можна звести до класичноподібної нормальної форми. Формулу Ψ назвемо варіантою формули Ξ, якщо Ψ утворена з Ξ послідовними замінами підформул вигляду х на підформули у ( )x у R  за умови у(). Згідно теореми 2, Ren та теореми 5 отримуємо:Теорема 6 (про варіанту). Нехай Ψ -варіанта формули Ξ. Тоді Ψ  TF Ξ.Формула Ψ різнокванторна, якщо всі входження кванторних префіксів у Ψ (якщо вони є) -по різних тотально неістотних іменах, та кожне уq(Ψ) не лежить в області дії символу , , в нормальній формі, або нормальна, якщо вона різнокванторна та всі символи реномінації формули Ψ (якщо вони є) застосовані тільки до ПС. Для кожної формули  можна збудувати нормальну формулу Ψ таку, що   TF Ψ.Кожному входженню кванторного префікса у  зіставимо нове уV T , причому різним таким входженням зіставимо різні тотально неістотні імена. Далі замінюємо кожну підформулу вигляду хА на у (Α)x у R , де уV T зіставлене такому входженню х у . Отримуємо різнокванторну Ξ, яка є варіантою формули , тому   TF Ξ. За Ξ будуємо формулу Ψ. Використовуючи R  R, R   та R  , проносимо всі символи реномінації вглиб до рівня атомарних підформул, принагідно виконуючи спрощення згідно R  T, R  U, R  , dR  . Отримуємо нормальну формулу Ψ таку, що Ξ  TF Ψ. Враховуючи   TF Ξ, звідси   TF Ψ.
4 .RВідношення логічного наслідку для множин формул Відношення логічного наслідку для множин формул -ЧКНЛРР визначаються так, як для випадку ЧКНЛ. Нехай  Fr та   Fr -деякі множини формул, АС A -модель мови. Надалі у випадку  A |=  скорочено позначаємо: як F( A ). Відношення A |= T , A |= F , A |= TF , A |= Cl , A |= Cm наслідку для пари множин формул в моделі мови A задаємо так:  A |= T , якщо T( A )  T( A );    |= ;
Тепер визначаємо відповідні відношення логічного наслідку |= T , |= F , |= TF , |= Cl , |= Cm за наступною схемою: |=   для кожної моделі мови A. Тут і надалі, якщо інше не вказане,  -це одне з Cl, Cm, T, F, TF. Відношення логічного наслідку індукують на множині формул відношення логічної еквівалентності. Відношення еквівалентності A  T , A  F , A  TF , A  Cl , A  Cm в моделі мови A визначаємо за такою схемою: |=   
A
Для відношень  Cl ,  Cm та  TF справджується (тут  -це одне з Cl, Cm, TF):Теорема 5 (семантичної еквiвалентностi). Нехай ' отримана з  замiною деяких входжень 1 ,..., n   на  1 ,...,  n вiдповiдно. Якщо 1     1 , ..., n     n , то    '.
TF z; x z  TF z; ) x(x)  TF x; x(x)  TF x; d) x(y)  TF x  y; x(y)  TF x  y.Аналогічно властивості , для квантора x маємо: ) x z  TF z; x z  TF z;Подібно до  та d можна додатково записати: TF x&y; x(&y)  TF x&y.
)    R z z y y x(x)  TF x; x(x&)  TF x; ; x(y)  TF x&y; x(y)  TF x&y; x(&y)  TF x&y; x(&y)  TF x&y; x(y)  TF xy; x(y)  TF xy; ) x z  x(x&)  TF x; x(x&)  TF x; x(&y) 

, , ( )

, , ( ), ();

, , ( )

R   за умови у ();

,

;

,

Наведемо основні властивості відношень логічного наслідку для множин формул, пов'язані з предикатами-індикаторами. Вони індуковані відповідними властивостями формул.

, , ( ),

, , ( ),

, , ( )

Пов'язані з виділеними константними -формулами умови, які гарантують наявність логічного наслідку:

;

Властивості елімінації кванторів фактично успадковуються від ЧКНЛ (див. [5]):

Висновки

Досліджено першопорядкові композиційно-номінативні логіки часткових однозначних, тотальних неоднозначних та часткових неоднозначних квазіарних предикатів. Запропоновано розширення цих логік узагальненими реномінаціями та спеціальними предикатами-індикаторами наявності значення для предметних змінних. Описано мови та семантичні моделі таких логік, досліджено їх семантичні властивості. Особливу увагу приділено вивченню відношень логічного наслідку, зокрема, відношень логічного наслідку для множин формул. Властивості таких відношень є семантичною основою побудови для пропонованих логік числень секвенційного типу, що планується зробити в наступних роботах.

<author> <persName><forename type="first"> A</forename><surname>|= F , Якщо F ; A )  F ;  A</surname></persName> </author> <imprint/> </monogr> <note></note> </biblStruct> <biblStruct xml:id="b1"> <monogr> <title level="m" type="main">якщо  A |= T  та  A  A |= Tf  ;|= F   A |=Cl якщо T A ) Cm логічного наслідку для пари множин формул вводимо за наступною схемою  A |=Cm Якщо F( A )  T( A ) = V A TВідповідні F|= |=Tf |= Cl ; Cl TCm FTf     A |=   для кожної моделі мови A. Теорема 8. Нехай модель мови B = (A, I B ) дуальна до моделі мови A =
A, A I
 <author> <persName><forename type="first"> A</forename><surname>|= T    B |= F  Та</surname></persName> </author> <author> <persName><forename type="first"></forename><surname>|= F    B |= T </surname></persName> </author> <imprint/> </monogr> </biblStruct> <biblStruct xml:id="b5"> <monogr> <author> <persName><forename type="first"> A |=</forename><surname>Cl</surname></persName> </author> <author> <persName><forename type="first">   B |=</forename><surname>Cm</surname></persName> </author> <author> <persName><forename type="first"></forename></persName> </author> <author> <persName><forename type="first"> A |=</forename><surname>Cm</surname></persName> </author> <author> <persName><forename type="first"> ; B |=</forename><surname>Cl</surname></persName> </author> <title level="m">Випливає з того, що загальній семантиці кожна модель мови B є дуальною до деякої Tf  випадку загальної семантики. моделі мови A. Наслідок 8. 1. Cl  в неокласичній семантиці   B |= Cm  в пересиченій |= T  неокласичній семантиці   |= F  в пересиченій неокласичній семантиці   |= T  в пересиченій |= F  Cm у відповідних семантиках. Теорему 9 можна переформулювати |=TCl F|= |=Tf ; Для Пересиченої -|= Cm T|= F|= |=Tf ; Для Загальної -|= Tf . U) Нехай    Та    |=  |=   |=   y, . |=  та  |= , y (-розподіл) С |=  Властивість С гарантує наявність кожного з наслідків у всіх семантиках. У відповідних семантиках маємо властивості, які додатково гарантують наявність логічного наслідку  |=  для неокласичної семантики |= -це |= T , |= Cl ; для пересиченої -|= F , |= Cm |=  для неокласичної семантики |= -це |= F , |= Cl ; для пересиченої -|= T , |= Cm <author> <persName><surname>Сlr</surname></persName> </author> <imprint/> </monogr> </biblStruct> <biblStruct xml:id="b12"> <monogr> <author> <persName><forename type="first"></forename></persName> </author> <author> <persName><forename type="first"></forename></persName> </author> <author> <persName><forename type="first"></forename><surname>|= Tf </surname></persName> </author> <author> <persName><forename type="first"></forename></persName> </author> <title level="m">Властивості пропозиційного рівня:  L ) ,  |=     для неокласичної семантики чи пересиченої семантики  R )  |=     |=   L )  |=  та   |=    )|=     |=   L )   |=     |=   R )  |=    |= ,  та  |=  Для |= Cl (неокласична семантика) та |= Cm (пересичена семантика) додатково маємо (тут |= -це |= Cl , |= Cm )  L )     |=  )|=      |=  Тому для |= Cl і |= Cm можна знімати заперечення, переносячи формулу з лівої частини відношення у праву і навпаки TДля F|= |=Tf Властивості  L Та  R Невірні ; Робити Для ; T F|= |=Tf терпретації предикати, що є значеннями виділених формул, збігаються, тому наведені властивості справджуються для |= TF , вони вірні також Cm R  T L ) Розглянемо основні властивості, пов'язані з розширеними реномінаціями та кванторами. При кожній ін- Handbook of Logic in Computer Science SAbramsky DovMGabbay TS EMaibaum Oxford Univ. Press 1 МСНікітченко СШкільняк Математична логіка та теорія алгоритмів 2008 528 МСНікітченко ОСШкільняк СШкільняк фіз.-мат. науки. -2013. -Вип. 2. -C. 210-215 Логіки часткових предикатів з розширеними реномінаціями та кванторами // Вісник Київського ун-ту Satisfability and Validity Problems in Many-sorted Composition-Nominative Pure Predicate Logics // Comm MNikitchenko VTymofieiev . in Comp. and Inf. Science. 347 2012 -Springer МСНікітченко СШкільняк фіз.-мат. науки. -2012. -Вип. 4. -C Композиційно-номінативні логіки квазіарних предикатів: семантичні аспекти // Вісник Київського ун-ту СШкільняк -Вип. 3. -C Семантичні властивості логік часткових предикатів з розширеними реномінаціями // Вісник Київського ун-ту фіз.-мат. науки. -2013 HНикитченко СШкильняк Cемантические свойства и секвенциальные исчисления чистых композиционно-номинативных логик первого порядка // Information Theories and Applications
Sofia, Bulgaria
 2013 20 СШкільняк 1. -C. 15-38 Відношення логічного наслідку в композиційно-номінативних логіках // Проблеми програмування 2010 Математическая логика 1973 480 Клини С