ПРЕДИКАТНІ КОМПОЗИЦІЙНІ СИСТЕМИ Предикати та iх різновиди

Нехай на D можна ввести відношення порядку за включенням даних
Предикат P монотонний:
d ⊆ d' ⇒ P(d) ⊆ P(d').
Предикат P антитонний:
d ⊆ d' ⇒ P(d') ⊇ P(d).
Для однозначних предикатів монотонність стає еквітонністю.
Однозначний предикат P еквітонний:
d '⊇ d та P(d)↓ ⇒ P(d') ↓ = P(d).
Для однозначного часткового предиката монотонність означає, що його інформативність не зменшується при збільшенні інформативності вхідних даних. Для монотонних тотальних предикатів при розширенні вхідних даних інформативність може тільки зменшуватися, для них поняття монотонності малозмістовне, а змістовним (не зменшення інформативності предиката при збільшенні інформативності вхідних даних) є дуальне поняття антитонності.
Водночас для однозначних предикатів поняття антитонності малозмістовне, адже для них антитонними можуть бути лише майже константні предикати:
P(d) ≅ T для всіх d∈D або P(d) ≅ F для всіх d∈D

Іменні множини
V-ІМ над A – це довільна часткова однозначна функція d : V→A
V-ІМ подаємо як [v1a1,...,vnan,...], де vі∈V, aі∈A, vі ≠ vj при і ≠ j.
Введемо функцію asn : VA→2V: asn(d) = {v∈V | va∈d для деякого a∈A}.
Множину всіх V-ІМ над A будемо позначати VA.
V-ІМ δ V-повна (максимальна), якщо asn(δ) = V.
V-повна ІМ над A – це тотальна однозначна функція V→A.
Множину всіх V-повних ІМ над A будемо позначати AV.
Для V-ІМ вводимо теоретико-множинні операції ∩ та \.
Параметрична операція ║Х звуження V-ІМ за множиною Х ⊆ V:
d║Х = {va∈d | v∈X}.
Операція ║–Х видалення компонент з іменами із Х ⊆ V: d║–Х = d║(V\Х)
Замість d║–{х} пишемо d║–х
Введемо відношення =–х рівності з точністю до компоненти з іменем х:
d1 =–х d2, якщо d1║–х = d2║–х
Операція ∇ накладки V-ІМ δ2 на V-ІМ δ1: δ1∇δ2 = δ2∪ (δ1║(V \ asn(δ2)))

Операцію реномінації задамо так:
Скорочено пишемо
Операцію реномінації ІМ продовжимо на множини ІМ
Монотонність операції реномінації: якщо d1 ⊆ d2, то
Елімінація тотожних перейменувань:
Маємо
Послідовне застосування двох операцій реномінації (внутрішня) та (зовнішня) можна подати у вигляді однієї операції реномінації, яку назвемо згорткою цих операцій і позначимо

Нехай маємо послідовне застосування двох операцій реномінації
де {w1,...,wm} ∩ {u1,...,uk} = ∅. Тоді для всіх d∈VA
де кожні ai та bj задаються так:
Згортка операцій реномінації асоціативна та некомутативна

Квазіарні функції та предикати
Функції (зокрема, предикати), задані на ІМ, називають квазіарними
V-квазіарна функція – функція вигляду f : VA → R
V-квазіарна функція на A – функція вигляду f : VA → А
V-квазіарний предикат на A – функція вигляду Р : VA → {T, F}
Ім’я z∈V строго неістотне для V-квазіарнoї функції (предиката) g, якщо
для всіх d1, d2 ∈VA таких, що d1 =–z d2, маємо g(d1) = g(d2).
Ім'я z неістотне для однозначної V-квазіарнoї функції (предиката) g, якщо для всіх d1, d2 ∈VA таких, що d1 =–z d2, маємо g(d1) ≅ g(d2).
Для однозначних еквітонних функцій маємо еквівалентне визначення.
Ім'я x неістотне для однозначної еквітонної функції (предиката) g, якщо
для кожних d∈VA та a, b∈A маємо g(d∇xa) ≅ g(d∇xb).
Для однозначних функцій (зокрема, предикатів) маємо:
1) x∈V неістотне для еквітонної g ⇔ g(d) ≅ g(d∇xa) ∀ d∈VA, a∈A
2) x∈V неістотне для еквітонної повнототальної g ⇔
g(d) = g(d∇xa) ∀ d∈AV, a∈A

Композиційні предикатні системи
Семантична основа КНЛ – композиційні предикатні системи.
Це трійки вигляду (D, PF, C), де
D – множина даних
PF – множина предикатів (та функцій) на D
C – множина композицій над PF.
Композиційна система (D, PF, C) задає дві алгебри:
алгебру (алгебраїчну систему) даних (D, PF)
композиційну алгебру предикатів (та функцій) (PF, C).
Побудова композиційної алгебри визначає мову логіки відповідного рівня.
Терми такої алгебри будуть формулами мови.
Для логік квазіарних предикатів D – це множина VA всіх V-ІМ над певною множиною базових даних A (вважаємо A ≠ ∅).

Для логік реномінативного і кванторних рівнів PF конкретизуємо як PrА
C конкретизується як множина композицій на PrА.
Тоді КС набувають вигляду (VА, PrА, C).
Це композиційні системи V-квазіарних предикатів.
(PrА, C) – це композиційні алгебри V-квазіарних предикатів.
Для логік функціональних рівнів PF конкретизується як FnА∪PrА,
C – як множина композицій на FnА∪PrА.
Тоді КС набувають вигляду (VА, FnА∪PrА, C)
Це композиційні системи V-квазіарних функцій та предикатів.
(FnА∪PrА, C) – композиційні алгебри V-квазіарних функцій та предикатів

Композиції квазіарних предикатів
Пропозиційний рівень: композиції називають логiчними зв’язками, вони працюють лише з виробленими предикатами істиннісними значеннями
Визначення логічних зв’язок ¬, ∨, &, →, ↔. через області істинності та хибності відповідних предикатів ¬P, P∨Q, P→Q, P&Q, P↔Q:
T(¬P) = F(P)
F(¬P) = T(P);
T(P∨Q) = T(P)∪T(Q);
F(P∨Q) = F(P)∩F(Q);
T(P&Q) = T(P)∩T(Q);
F(P&Q) = F(P)∪F(Q);
T(P→Q) = F(P)∪T(Q);
F(P→Q) = T(P)∩F(Q);
T(P↔Q) = (F(P)∪T(Q))∩(F(Q)∪T(P))
F(P↔Q) = (T(P)∩F(Q))∪(F(P)∩T(Q))

Основні властивості пропозиційних композицій:
P∨Q = Q∨P
P&Q = Q&P (P∨Q)∨R = P∨(Q∨R)
(P&Q)&R = P&(Q&R)
(P∨Q)&R = (P&R)∨(Q&R)
(P&Q)∨R = (P∨R)&(Q∨R)
¬¬P = Р
Р = Р∨Р та Р = Р&Р
¬(P∨Q) = (¬P)&(¬Q)
¬(P&Q) = (¬P)∨(¬Q)
Композиції ¬ та ∨ – базові пропозиційні композиції.
Композиції →, &, ↔ є похідними, вони виражаються через ¬ та ∨:
P→Q = ¬P∨Q;
P&Q = ¬(¬P∨¬Q);
P↔Q = (P→Q)&(Q→P).

На реномінативному рівні до логічних зв'язок додамо параметризовану за множиною пар імен композицію реномінації
Композиція реномінації задається так. Для кожного d∈VА маємо
Композицію реномінації можна визначити через області істинності та хибності відповідного предиката:
Результатом послідовного виконання двох композицій реномінації є
їх згортка, яка визначається так. Для кожного d∈VA маємо
Згортка композицій реномінації асоціативна та некомутативна

Основні властивості композицій реномінації:
за умови: z∈V строго неістотне для Р.
за умови: z∈V неістотне для Р.
Композиція реномінації зберігає монотонність (еквітонність) і антитонність квазіарних функцій та предикатів.

На реномінативному рівні з рівністю додатково можна ототожнювати й розрізняти значення предметних імен за допомогою спеціальних 0-арних композицій – параметризованих за іменами предикатів рівності.
Розглядаємо дві різновидності таких предикатів:
– слабкої (з точністю до визначеності) рівності =ху та
– строгої (точної) рівності ≡xy .
Предикати рівності =ху та ≡xy задамо через області істинності й хибності:
T(=xy) = {d∈VA | d(x)↓ = d(y)↓};
F(=xy) = {d∈VA | d(x)↓ ≠ d(y)↓};
T(≡xy) = {d∈VA | d(x)↓ = d(y)↓} ∪ {d∈VA | d(x)↑ та d(y)↑};
F(≡xy) = {d∈VA | d(x)↓ ≠ d(y)↓} ∪ {d∈VA | d(x)↓, d(y)↑ або d(x)↑, d(y)↓}.
Множиною строго неістотних для =ху та ≡xy предметних iмен є V \{х, у}.

Предикати =xy часткові однозначні, вони монотонні й еквітонні.
Водночас предикати ≡xy тотальні однозначні, немонотонні й нееквітонні.
Приклад. ≡xy ([za] = T, ≡xy([za, xa]) = F, ≡xy ([za, xa, ya,]) = T.
Тому на рівні РНЛРС логіки еквітонних предикатів розглядати не можна.
Предикати ≡xy подаються через =xy i спеціальні предикати-індикатори εz:
Теорема. Маємо ≡xy = (=xy & ¬εx & ¬εy) ∨ (εx & εy).
Предикат-індикатор εz наявності значення для z∈V визначаємо так:
T(εz) = {d | d(z)↑} = {d∈VA | z∉asn(d)};
F(εz) = {d | d(z)↓} = {d∈VA | z∈asn(d)}.
Предикати εz не є монотонними та не є антитонними.
Маємо співвідношення:
T(=xy) ⊂ F(εx) ∩ F(εy);
F(=xy) ⊂ F(εx) ∩ F(εy).
Предикати рівності =xy та ≡xy також позначаємо x = y та x ≡ y.

Властивості предикатів =xy та ≡xy .
– кожний предикат =xx є неспростовним
– кожний предикат ≡xx є тотожно істинним
– для предикатів =xy та ≡xy маємо рефлексивність та симетричність:
=xy(d) = =xy(d) та ≡xy(d) = ≡xy(d) кожного d∈VA
– для предикатів =xy та ≡xy маємо транзитивність: для кожного d∈VA
≡xy(d) = T т а ≡yz(d) = T ⇒ ≡xz(d) = T.
Водночас для предикатів =xy транзитивності по окремих даних немає.
Приклад 1. Для d = [xa, zb], де a ≠ b, маємо =xy(d)↑, =yz(d)↑, =xz(d) = F.
Це означає: =xy та =yz на такому d неспростовні, =xz на такому d хибний.
Для предикатів =xy маємо властивість заміни рівних:
для кожних P∈PrА та d∈VA ≡xy(d) = T ⇒
Для предикатів =xy заміни рівних по окремих даних вже немає.
Приклад 2. Для d = [xa, zb] маємо =xy(d)↑ – =xy на d неспростовний.
Задамо P([zb, va,]) = T, P([zb]) = F, тоді

На безкванторно-функціональних рівнях з рівністю додатково можна ототожнювати й розрізняти предметні значення, що дає змогу ввести спеціальну композицію рівності вигляду FnA×FnA→PrA.
Розглядаємо дві її різновидності:
– слабкої (з точністю до визначеності) рівності =
– строгої (точної) рівності ≡ .
Композиції = та ≡ задаються так:
Композиції суперпозиції та = зберігають еквітонність квазіарних функцій та предикатів.
Композиція ≡ еквітонність не зберігає.
Тому на рівні БКНЛРС логіки еквітонних предикатів розглядати не можна

Властивості композицій суперпозиції
S¬) Дистрибутивність суперпозиції щодо ¬:
S∨) Дистрибутивність суперпозиції щодо ∨:
Аналогічно властивості дистрибутивності суперпозиції щодо →, & та ↔:
Згортка суперпозицій (тут ϕ∈FnA∪PrA, введені позначення відповідно для u1,..., un; t1,..., tn; х1,..., хk; r1,..., rk; w1,..., wk; v1,...,vm; s1,..., sm ):

SS) Згортка суперпозицій (тут ϕ∈FnA ∪PrA):
ZS) Згортка імен (тут ϕ∈FnA ∪PrA ):
Зокрема,
DD) Згорткa неістотних імен для ф-ій розіменування (тут х∉{v1,..., vn}):
DS) Cпрощення для функцій розіменування:
Зокрема, Sx('x, f) = f.
ZN) Згортка за неістотним іменем (тут ϕ∈FnA ∪PrA, x неістотне для ϕ):
Зокрема, Sx(ϕ, f) ≅ ϕ.

ZS) Згортка імен (тут ϕ∈FnA∪PrA ):
Зокрема, маємо
DD) Згорткa неістотних імен для функцій розіменування:
DS) Cпрощення для функцій розіменування:
Зокрема, маємо
ZN) Згортка за неістотним іменем (тут ϕ∈FnA∪PrA)
якщо x строго неістотне для ϕ
Зокрема, маємо
якщо x неістотне для ϕ.
Зокрема, маємо

Властивості слабкої рівності
Тут P∈PrA та h, f, f1,..., fn, g, g1,..., gn ∈FnA.
Rf) рефлексивність:
кожний предикат вигляду f = f істинний
Sm) cиметричність:
f = g ⇔ g = f ; більш того, T(f = g) = T(g = f) та F(f = g) = F(g = f)
Tr) транзитивність:
f = g & g = h ⇨ f = h; більш того, T(f = g)∩T(g = h) ⊆ T(f = h)
EF)
EP)
SЕ) дистрибутивність суперпозиції щодо рівності:
=

Композиція еквіваленції ↔ для предикатів є аналогом відношення слабкої рівності для функцій.
Введемо композицію ↔s строгої еквіваленції, яка є аналогом відношення звичайної (строгої) рівності для функцій. Для кожного d∈D задамо:
(P ↔s Q)(d) = T ⇔ P(d) = Q(d),
(P ↔s Q)(d) = F ⇔ P(d) ≠ Q(d).
Тут P(d) = Q(d) означає, що значення P(d) та Q(d) збігаються, тобто обидва рівні та визначені або обидва невизначені.
Для логік часткових чи неоднозначних предикатів ↔s незалежна від ¬ і ∨.
Властивості строгої рівності
Rfs) кожний предикат вигляду f ≡ f тотожно істинний;
Sms) f ≡ g ⇔ g ≡ f;
Trs) f ≡ g та g ≡ h ⇒ f ≡ h тотожно істинний;
EsF) f1 ≡ g1, ..., fn ≡ gn тотожно істинні ⇒
тотожно істинний;
EsP) f1 ≡ g1, ..., fn ≡ gn тотожно істинні ⇒
SsЕ) = ≡

Композиції квантифікації. Визначальні для першопорядкових логік
Дамо визначення 1-арних композицій ∃x та ∀x для однозначних предикатів. Предикати ∃x(P) та ∀x(P) позначаємо ∃xP та ∀xP.
Для кожного d∈VА задамо:
Визначення предикатів ∃xP та ∀xP через їх області істинності й хибності
T(∃xP) = {d∈VA | T∈Р(d∇xa) для деякого a∈A}.
F(∃xP) = {d∈VA | F∈Р(d∇xa) для всіх a∈A}.
T(∀xP) = {d∈VA | T∈Р(d∇xa) для всіх a∈A}.
F(∀xP) = {d∈VA | F∈Р(d∇xa) для деякого a∈A}.
Композиція ∀x є похідною, вона подається так: ∀хР = ¬∃х¬Р.

Наведемо основні властивості композицій ∃x та ∀x.
1) Комутативність однотипних кванторів:
∃x∃уР = ∃у∃хР;
∀x∀уР = ∀у∀хР.
2) Закони де Моргана для кванторів:
¬∃хР = ∀х¬Р;
¬∀хР = ∃х¬Р.
3) Неістотність квантифікованих імен:
∃x∃хР = ∃хР;
∃x∀хР = ∀хР;
∀x∃хР = ∃хР;
∀x∀хР = ∀хР.
4) Закони дистрибутивності кванторів щодо ∨ та &:
∃хР ∨∃хQ = ∃х (Р∨Q);
∀хР &∀xQ = ∀х (Р&Q).

Властивості кванторів, пов'язані з неістотністю імен:
– ім’я х∈V строго неістотне для предикатів ∃хР та ∀хР;
– ім’я х∈V строго неістотне для Р ⇔ P = ∀хР ⇔ Р = ∃хР;
– ім’я х∈V неістотне для Р ⇔ P ≅ ∀хР ⇔ Р ≅ ∃хР.
Залучаючи до розгляду реномінації та суперпозиції, маємо:
Ці властивості можна переформулювати для ∀х.
За умови неістотності імені z в Ren та R∃∃ маємо слабку рівність
Неістотність верхніх імен в реномінаціях:

S∃b) Обмежена дистрибутивність суперпозиції щодо ∃x:
S∀b) Обмежена дистрибутивність суперпозиції щодо ∀x:
Для S∃b та S∀b умови: х∉{v1,..., vn} та х неістотне для f1, ..., fn.
S∃) Спеціальна дистрибутивність суперпозиції щодо ∃x ( х∉{v1,..., vn}):
S∀) Спеціальна дистрибутивність суперпозиції щодо ∀x ( х∉{v1,..., vn}):
Rm1. Oбмежувальні умови дистрибутивності та спеціальної дистрибутивності суперпозиції щодо кванторів є істотними.
Rm2. Рівність з точністю до визначеності ≅ для S∃b та S∀b.
Задамо еквітонні f та P: P(d)↑ при v∉asn(d) та P([x0, y0, v0]) = T;
f(d)↑ при x∉asn(d) та f(d) = 0 при x∈asn(d).
Тоді х неістотне для f, ∃xSv(P, f)([y0]) = T та Sv(∃xP, f)([y0])↑.
Rm3. Для аналогічних властивостей R∃ та R∀ рівність строга !

Властивості квазіарних предикатів
Теорема 1. Композиції ¬, ∨, ∃x зберігають:
– монотонність та антитонність квазіарних предикатів
– еквітонність однозначних квазіарних предикатів
– повнототальність і фінарність квазіарних предикатів
Наслідок 1. Класи монотонних та антитонних квазіарних предикатів замкнені відносно композицій ¬, ∨, →, &, ↔, ∃x, ∀x.
Класи еквітонних і повнототальних однозначних квазіарних предикатів замкнені відносно композицій ¬, ∨, →, &, ↔, ∃x, ∀x.
Теорема 2. Композиції =, ≡ зберігають:
– еквітонність однозначних квазіарних фукцій та предикатів
– повнототальність і фінарність квазіарних фукцій та предикатів
Наслідок 2. Класи еквітонних і повнототальних однозначних квазіарних фукцій та предикатів замкнені відносно композицій =, ≡

Приклад 1. Розглянемо наступні предикати.
Р1 та Р2 тотальні однозначні немонотонні (нееквітонні) й неантитонні,
Р3 та Р5 монотонні (еквітонні) однозначні,
Р4 та Р6 монотонні тотальні неоднозначні,
Р7 та Р9 антитонні часткові однозначні,
Р8 та Р10 антитонні тотальні неоднозначні.

Неспростовними чи невиконуваними можуть бути лише однозначні предикати. При цьому властивості неспростовності й виконуваності природно пов'язані:
Твердження. Предикат P неспростовний ⇔ ¬P невиконуваний.
P неспростовний ⇔ F(P) = ∅ ⇔ T(¬P) = ∅ ⇔ ¬P невиконуваний.
Для часткових предикатів невірні деякі важливі закони класичної логіки.
Приклад 2. modus ponens невірне для загального випадку квазіарних предикатів.
Задамо P як ⊥, Q – як тотожно хибний предикат. Тоді P→Q теж ⊥.
Отже, P та P→Q частково істинні, водночас Q – тотожно хибний.
Приклад 3. Задамо предикат P як тотожно істинний, Q – як ⊥, S – як тотожно хибний. Тоді P↔Q та Q↔S частково істинні, водночас P↔S тотожно хибний.
Приклад 4. Нехай для предикатів p, q, s маємо p(d) = T, q(d)↑, s(d) = F;
тоді p(d) ≅ q(d) та q(d) ≅ s(d), але невірно, що p(d) ≅ s(d).
Приклади 3, 4 заперечують транзитивність еквіваленції та слабкої рівності. Саме ця нетранзитивність є причиною невиконання деяких законів класичної логіки для класів часткових предикатів, які використовують слабко рівні клінієві зв'язки.
Необхідною й достатньою умовою коректності modus ponens у таких класах часткових предикатів є еквітранзитивність – транзитивність відношення  слабкої рівності предикатів, тобто транзитивність еквіваленції

Отже, відмінність логіки часткових предикатів і логіки класичної виявляється вже на пропозиційному рівні. Більш того, предикати прикладів 3 та 2 еквітонні.
Для класу еквітонних предикатів умова еквітранзитивності не виконується. Водночас вона справджується для класу повнототальних еквітонних предикатів.
Приклад 5. Для загального випадку квазіарних предикатів
традиційні закони T(Р) ⊆ T(∃хР) та T(∀хР) ⊆ T(Р) невірні
Задамо предикат P так:
P(d) = T при x∉asn(d) та P(d) = F при x∈asn(d).
Тоді для таких d, що x∉asn(d), маємо P(d) = T та ∃хР(d) = F.
Задамо тепер предикат P так:
P(d) = F при x∉asn(d) та P(d) = T при x∈asn(d).
Тоді для таких d, що x∉asn(d), маємо ∀хР(d) = T та P(d) = F.
Для еквітонних предикатів закони T(Р) ⊆ T(∃хР) та T(∀хР) ⊆ T(Р) вірні

Приклад 6. Існують квазіарні предикати: Р  ∀xР і невірно Р  ∃xР.
Нехай A = {a, b}. Задамо предикат P так:
P(d) = F при x∉asn(d), P(d∇xa) = T та P(d∇xb)↑.
Тоді для всіх d∈VA маємо ∀xР(d)↑, тому Р  ∀xР.
Водночас P(d) = F при x∉asn(d), але ∃xР(d) = T для всіх d∈VA,
тому невірно Р  ∃xР.
Приклад 7. Існують квазіарні предикати: Р  ∃xР і невірно Р  ∀xР.
Нехай A = {a, b}. Задамо предикат P так:
P(d) = T при x∉asn(d), P(d∇xa) = F та P(d∇xb)↑.
Тоді для всіх d∈VA маємо ∃xР(d)↑, тому Р  ∃xР.
Водночас P(d) = T при x∉asn(d), але ∀xР(d) = F для всіх d∈VA,
тому невірно Р  ∀xР

Наведені співвідношення здаються цілком очевидними, хоча це не так.
(TR∃)
(FR∃)
(TR∀)
(FR∀)
Теорема. 1) Для загального випадку квазіарних предикатів невірне кожне із співвідношень TR∃, FR∃, TR∀, FR∀;
2) для монотонних предикатів:
– вірні TR∃ та FR∀,
– невірні FR∃ та TR∀;
3) для антитонних предикатів:
– вірні FR∃ та TR∀,
– невірні TR∃ та FR∀.