Предикати та їх різновиди

1.

ПРЕДИКАТИ ТА ЇХ РІЗНОВИДИ
Предикат на множині D – це часткова неоднозначна, взагалі кажучи, функція
P : D {T, F}
Часткові неоднозначні предикати трактуємо як відношення між D та {T, F},
назвемо їх предикатами реляційного типу. P(d) – множина значень, які предикат
P може прийняти на d D. P(d) {T, F} P(d) – однe із { }, {T}, {F}, {T, F}.
Предикат P : D {T, F} задається областю істинності та областю хибності
T(P) = {d VA | T P(d)}
F(P) = {d VA | F P(d)}.
Предикат P однозначний, якщо T(P) F(P) =
Предикат P тотальний, якщо T(P) F(P) = D
Предикат P : D {T, F} назвемо:
– неспростовним, або частково істинним, якщо F(P) =
– виконуваним, якщо T(P)
– всюди невизначеним, якщо T(P) = F(P) =
– тотально істинним, якщо T(P) = D
– тотально хибним, якщо F(P) = D
– тотожно істинним, якщо T(P) = D і F(P) =
– тотожно хибним, якщо T(P) = і F(P) = D
– тотально насиченим, якщо T(P) = F(P) = D
1

2.

Для однозначних предикатів області істинності й хибності:
T(P) = {d D | P(d) = T} F(P) = {d D | P(d) = F}
Нехай на 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 монотонність означає: його інформативність
не зменшується при збільшенні інформативності вхідних даних.
Для монотонних тотальних предикатів при розширенні вхідних даних
інформативність може тільки зменшуватися, для них поняття монотонності
малозмістовне, а змістовним є дуальне поняття антитонності.
Якщо P антитонний, то P( ) складається з усіх значень, які P може приймати
на D, тобто P( ) = EP. Тому для тотальних предикатів антитонність означає:
“інформативність” предиката не зменшується при збільшенні “інформативності”
вхідних даних.
Водночас для однозначних предикатів поняття антитонності малозмістовне,
адже для них антитонними можуть бути лише майже константні предикати:
P(d) T для всіх d D або P(d) F для всіх d D
2

3.

Іменні множини
V-A-ІМ – це довільна часткова однозначна функція d : V A
V-A-ІМ подаємо як [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-A-ІМ повна (максимальна), якщо asn( ) = V
повна V-A-ІМ – це тотальна однозначна функція V A.
Множину всіх повних V-A-ІМ будемо позначати AV.
Для V-A-ІМ вводимо теоретико-множинні операції та \.
Параметрична операція ║Х звуження V-A-ІМ за множиною Х V:
d║Х = {v a d | v X}.
Операція ║–Х видалення компонент з іменами із Х V: d║–Х = d║(V\Х)
Замість d║–{х} пишемо d║–х
Введемо відношення =–х рівності з точністю до компоненти з іменем х:
d1 =–х d2, якщо d1║–х = d2║–х
Операція накладки ІМ 2 на ІМ 1: 1 2 = 2 ( 1║(V \ asn( 2)))
3

4.

,...,vn V
V
:
A
A задамо так:
Операцію реномінації rxv1,...,
x
1
n
Скорочено пишемо y замість y1,..., yn
Операцію реномінації ІМ продовжимо на множини ІМ
r vx ( L) {r vx (d ) | d L}, де L V A
Монотонність операції реномінації: якщо d1 d2, то r vx (d1 ) r vx (d2 )
Елімінація тотожних перейменувань: r zz ,,vx (d ) r vx (d )
Маємо r zy,,vx (d ) z r zu,,vx (d ) та r zy,,vx (d ) z r vx (d )
Тотожна реномінація r діє як тотожне відображення: r(d) = d.
Послідовне застосування двох операцій реномінації r uy (внутрішня) та r vx
(зовнішня) можна подати у вигляді однієї операції реномінації, яку назвемо
згорткою цих операцій і позначимо r vx uy
r vx (r uy (d )) r vx
u
y (d )
4

5.

Нехай маємо послідовне застосування двох операцій реномінації
vп ,u1 ,...,uk
r vs1 ,...
,..., s , z ,..., z
1
п
1
k
vn ,w1 ,...,wm
та r vx1 ,...,
,..., x , y ,..., y ,
n
1
1
m
де {w1,...,wm} {u1,...,uk} = . Тоді для всіх d VA
vn ,w1 ,..., wm
v1 ,...vп ,u1 ,...,uk
v1 ,...,vn , w1 ,..., wm ,u1 ,...,uk
r vx1 ,...,
(r
(
d
))
r
,..., x , y ,..., y
s ,..., s , z ,..., z
a ,...,a ,b ,...,b , z ,..., z ( d )
1
n
1
m
1
п
1
k
1
n
1
m
1
k
де кожні ai та bj задаються так:
xi , якщо xi {v1 ,...vп , u1 ,..., uk },
ai sl , якщо xi vl для деякого vl ,
zl , якщо xi ul для деякого ul ;
y j , якщо y j {v1 ,...vп , u1 ,..., uk },
b j sl , якщо y j vl для деякого vl ,
zl , якщо y j ul для деякого ul .
Згортка операцій реномінації асоціативна та некомутативна
5

6.

Квазіарні функції та предикати
Функції (зокрема, предикати), задані на ІМ, називають квазіарними
V-квазіарна функція – функція вигляду f : VA R
V-A-квазіарна функція – функція вигляду f : VA А
V-A-квазіарний предикат – функція вигляду Р : VA {T, F}
Ім’я z V строго неістотне для V-A-квазіарнoї функції (предиката) g,
якщо для всіх d1, d2 VA таких, що d1 =–z d2, маємо g(d1) = g(d2).
Ім'я z неістотне для однозначної V-A-квазіарн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
6

7.

V-A-квазіарний предикат P:
– неспростовний (частково істинний), якщо F(P) =
– виконуваний, якщо T(P)
– тотально істинний, якщо T(P) = VА
– тотально хибний, якщо F(P) = VА
– тотожно істинний, якщо T(P) = VА та F(P) = (позначаємо T)
– тотожно хибний, якщо T(P) = та F(P) = VА (позначаємо F)
– всюди невизначений, якщо T(P) = та F(P) = (позначаємо )
– тотально насичений, якщо T(P) = VА та F(P) = VА (позначаємо ).
Часткові неоднозначні квазіарні предикати назвемо R-предикатами
часткові однозначні – P-предикатами
тотальні – T-предикатами
тотальні однозначні – TS-предикатами.
7

8.

Класи R-предикатів, P-предикатів, T-предикатів, TS-предикатів відповідно
позначаємо
PrRVA , PrPAV , PrTAV , PrTS VA
Монотонні R-предикати назвемо RM-предикатами
антитонні R-предикати назвемо RА-предикатами
антитоннi T-предикати назвемо TА-предикатами
еквітонні P-предикати назвемо PE-предикатами
Класи RM-предикатів,
позначаємо .
RА-предикатів,
TА-предикатів,
PE-предикатів
PrRM VA , PrRAVA , PrPEVA , PrTAVA
Константні предикати , T, F, є монотонними й антитонними.
В класі TS-предикатів монотонними й антитонними є лише константні
предикати T та F.
8

9.

Приклад 1. Розглянемо наступні предикати.
{F }, якщо x asn(d ),
P (d )
, якщо x asn( d ).
{T }, якщо x asn(d ),
P (d )
, якщо x asn(d ).
F , якщо x asn( d ),
P (d )
, якщо x asn( d ).
{T }, якщо x asn(d ),
P (d )
, якщо x asn(d ).
P1 (d )
3
5
7
9
{F }, якщо x asn(d ),
{T }, якщо x asn(d ).
{T , F }, якщо x asn(d ),
P (d )
{T }, якщо x asn(d ).
{T , F }, якщо x asn(d ),
P (d )
{F }, якщо x asn(d ).
{T , F }, якщо x asn(d ),
P (d )
{T }, якщо x asn(d ).
{T , F }, якщо x asn(d ),
P (d )
{F }, якщо x asn(d ).
P2 (d )
{T }, якщо x asn( d ),
{F }, якщо x asn(d ).
4
6
8
10
Р1 та Р2 тотальні однозначні немонотонні (нееквітонні) й неантитонні,
Р3 та Р5 монотонні (еквітонні) однозначні,
Р4 та Р6 монотонні тотальні неоднозначні,
Р7 та Р9 антитонні часткові однозначні,
Р8 та Р10 антитонні тотальні неоднозначні.
9

10.

Приклад 2. Спеціальні 0-арні композиції – параметризовані за
предметними іменами предикати-індикатори z, які визначають наявність в
d VA компоненти з відповідним z V. Предикати z визначаємо так:
T , якщо d ( z ) ,
εz (d )
F , якщо d ( 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, неістотне для z
Використовують також дуальні до z предикати-індикатори Ez.
Предикати Ez визначаються так:
T(Ez) = {d | d(z) } = {d VA | z asn(d)};
F(Ez) = {d | d(z) } = {d VA | z asn(d)}.
Предикати-індикатори Ez та z пов’язані так: Ez = z.
10

11.

Предикат P дуальний до предиката P, якщо T ( P) F ( P) та F ( P ) T ( P )
Доповнення до V-A-квазіарного предиката P як реляції P VА Bool – це
P : T ( P ) T ( P) та F ( P ) F ( P )
Маємо T ( P) F ( P ), F ( P) T ( P )
Приклад пари взаємно дуальних та взаємно доповнених предикатів: та
Твердження 1. Q монотонний Q та Q антитонні;
Q антитонний Q та Q монотонні.
Твердження 2. Q PrPAV Q PrTAV Q PrTAV ;
Q PrTAV Q PrPAV Q PrPAV ;
Q PrTS VA Q PrTS VA ;
Q PrTS VA Q Q
11

12.

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

13.

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

14.

Композиції пропозиційного рівня
На пропозиційному рівні композиції називають лог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))
14

15.

Основні властивості пропозиційних композицій:
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).
15

16.

Безкванторні композиційно-номінативні логіки
Безкванторні логіки квазіарних предикатів займають проміжне
становище між пропозиційною логікою і першопорядковими КНЛ.
В безкванторних логіках не використовуємо композиції квантифікації,
характерні для першопорядкових логік.
Безкванторний рівень розпадається на низку підрівнів (в дужках назва):
– реномінативний (РНЛ);
– реномінативний з рівністю (РНЛР);
– реномінативний з строгою рівністю (РНЛРС);
– безкванторно-функціональний (БКНЛ);
– безкванторно-функціональний з рівністю (БКНЛР);
– безкванторно-функціональний з строгою рівністю (БКНЛРС).
16

17.

На реномінативному рівні до логічних зв'язок додамо параметризовану
за множиною пар імен композицію реномінації R vx : Pr A Pr A
Композиція реномінації задається так. Для кожного d VА маємо
R vx ( P)(d ) P(r vx (d ))
Композицію реномінації можна визначити через області істинності та
хибності відповідного предиката:
T (R vx ( P)) {d V A | r vx (d ) T ( P)} (r vx ) 1 (T ( P))
F (R vx ( P)) {d V A | r vx (d ) F ( P)} (r vx ) 1 ( F ( P))
Композиція R без параметрів діє як тотожне відображення: R(P) = P
Результатом послідовного виконання двох композицій реномінації є їх
згортка, яка визначається так. Для кожного d VA маємо
R vx
w
y
( P)(d ) R vx (R wy ( P))(d ) P(r wy vx (d ))
Згортка композицій реномінації асоціативна та некомутативна
17

18.

Основні властивості композицій реномінації:
R(P) = P
R zz ,,vx ( P) R vx ( P)
R vx ( P) R vx ( P)
R vx ( P Q) R vx ( P) R vx (Q)
R vx ( P & Q) R vx ( P) & R vx (Q)
R vx ( P Q) R vx ( P) R vx (Q)
R zy,,vx ( P) R vx ( P)
за умови: z V строго неістотне для Р.
R zy,,vx ( P) R vx ( P)
за умови: z V неістотне для Р.
Композиція реномінації зберігає монотонність
антитонність квазіарних функцій та предикатів.
(еквітонність)
18
і

19.

На реномінативному рівні з рівністю додатково можна ототожнювати й
розрізняти значення предметних імен за допомогою спеціальних 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 \{х, у}.
19

20.

Предикати =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).
Маємо співвідношення:
T(=xy) F( x) F( y);
F(=xy) F( x) F( y).
Предикати рівності =xy та xy також позначаємо x = y та x y.
20

21.

Властивості предикатів =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 Rzu,,xv ( P)(d ) Rzu,,yv ( P)(d )
Для предикатів =xy заміни рівних по окремих даних вже немає.
Приклад 2. Для d = [x a, z b] маємо =xy(d) – =xy на d неспростовний.
Задамо P([z b, v a,]) = T, P([z b]) = F, тоді
Rxv ( P)(d ) T , Ryv ( P)(d ) F
21

22.

На безкванторно-функціональному рівні можна формувати нові
аргументи для функцій і предикатів. Це дозволяє ввести
параметризовану за іменами композицію суперпозиції.
(n+1)-арна композиція суперпозиції Sv1 ,...vn V-квазіарним функціям
f, g1, ..., gn зіставляє V-квазіарну функцію Sv1 ,...vn ( f , g1,..., g n ),
значення якої d VА обчислюється так:
Sv1 ,...vn ( f , g1,..., g n )(d ) = f([v1 g1(d),...,vn gn(d)] (d║(V\{v1,...,vn}))).
Зрозуміло, що в інших позначеннях
Sv1 ,...vn ( f , g1,..., g n )(d ) = f(d [v1 g1(d),...,vn gn(d)]).
Виділення квазіарних функцій на A та квазіарних предикатів на A
індукує виділення суперпозицій двох типів:
– (FnA)n+1 FnA функцій у функції (результатом є функція);
– PrA (FnA)n PrA функцій у предикати (результатом є предикат).
Суперпозицію без параметрів S трактуємо як тотожне відображення
Виділимо множину функцій деномінації NfА = {'v| v V}: 'v(d) = d(v)
Тоді реномінації можна промоделювати за допомогою суперпозицій:
v ,...,v
R x1 ,..., xn ( f ) Sv1 ,...vn ( f ,'x1,...,'xn )
1
n
22

23.

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

24.

Властивості композицій суперпозиції
S ) Дистрибутивність суперпозиції щодо :
Sv ( P, f ) Sv ( P, f )
S ) Дистрибутивність суперпозиції щодо :
Sv ( P Q, f ) Sv ( P, f ) Sv (Q, f )
Аналогічно – властивості дистрибутивності суперпозиції щодо , &, :
S&) Sv ( P & Q, f ) Sv ( P, f ) & Sv (Q, f )
S ) Sv ( P Q, f ) Sv ( P, f ) Sv (Q, f )
S ) Sv ( P Q, f ) Sv ( P, f ) Sv (Q, f )
SІ) Елімінація суперпозиції без параметрів (тут FnA PrA): S( ) =
SS) Згортка суперпозицій (тут FnA PrA, позначення u , t , x , r , w, v , s
відповідно для u1,..., un; t1,..., tn; х1,..., хk; r1,..., rk; w1,..., wk; v1,...,vm; s1,..., sm
):
Su , x (Sx ,v ( , r , s ), t , w)
Su , x ,v ( , t ,Su , x (r1, t , w),...,Su , x (rk , t , w),Su , x (s1, t , w),...,Su , x (sm , t , w))
24

25.

CN) Згортка імен (тут FnA PrA ):
Sx1 ,..., xm ,v1 ,..., vn ( ,'x1 ,...,'xm , g1 ,..., g n ) Sv1 ,..., vn ( , g1,..., g n )
Зокрема, маємо Sx1 ,..., xm ( ,'x1 ,...,'xm )
SD) Згорткa неістотних імен для функцій розіменування:
Sv1 ,..., vn ('x, g1 ,..., g n ) 'x за умови x {v }
DF) Cпрощення для функцій розіменування:
Sx,v1 ,..., vn ('x, f , g1 ,..., g n ) f
Зокрема, маємо Sx ('x, f ) f
CU) Згортка за неістотним іменем (тут FnA PrA)
Sx,v1 ,..., vn ( , f , g1 ,..., g n ) Sv1 ,..., vn ( , g1,..., g n ) якщо x строго неістотне для
Зокрема, маємо Sx ( , f )
Sx,v1 ,..., vn ( , f , g1 ,..., g n ) Sv1 ,..., vn ( , g1,..., g n ) якщо x неістотне для .
Зокрема, маємо Sx ( , f )
25

26.

Властивості слабкої рівності
Тут P PrA та h, f, f1,..., fn, g, g1,..., gn FnA.
Rf) рефлексивність:
кожний предикат вигляду f = f неспростовний
Sm) cиметричність: T(f = g) = T(g = f) та F(f = g) = F(g = f)
це означає: предикати f =g та g = f збігаються
Tr) транзитивність: T(f = g) T(g = h) T(f = h)
EF) неспростовним є кожний предикат вигляду
=(f , g ) =(Sz ,v (h, f , r ), S z ,v ( h, g , r ))
EP) неспростовним є кожний предикат вигляду
=(f , g ) (Sz ,v ( P, f , r ) S z ,v ( P, g , r ))
SЕ) дистрибутивність суперпозиції щодо рівності:
Sv1 ,...vn ( ( f , h), f1,..., f n ) = (Sv1 ,...vn ( f , f1,..., f n ),Sv1 ,...vn (h, f1,..., f n ))
Із Tr: кожний предикат вигляду =(f, g) & =(g, h) =(f, h) неспростовний
26

27.

Композиція еквіваленції для предикатів – аналог відношення слабкої
рівності для функцій.
Введемо композицію 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 тотожно істиннi f h тотожно істинний;
EsF) f1 g1, ..., fn gn тотожно істинні
Sv1 ,..., vn (h, f1 ,..., f n ) Sv1 ,..., vn (h, g1,..., g n ) тотожно істинний;
EsP) f1 g1, ..., fn gn тотожно істинні
Sv1 ,..., vn ( P, f1 ,..., f n ) s Sv1 ,..., vn ( P, g1,..., g n )
v ,..., v
v ,..., v
SsЕ) Sv1 ,..., vn ( ( g , h), f1 ,..., f n ) = (S 1 n ( g , f1 ,..., f n ), S 1 n (h, f1,..., f n ))
Із Trs: кожний предикат (f, g) & (g, h) (f, h) тотожно істинний
Твердження. (f, g) та (g, h) тотож. істинні (f, h) тотож. істинний
27

28.

Першопорядкові композиційно-номінативні логіки
Композиції квантифікації є визначальними для першопорядкових логік
Дамо визначення 1-арних композицій x та x для однозначних
предикатів. Предикати x(P) та x(P) позначаємо xP та xP.
Для кожного d VА задамо:
T , якщо існує b A : P(d x b) T ,
xP(d ) F , якщо P(d x a ) F для всіх a A,
невизначене в усіх інших випадках.
F , якщо існує b A : P(d x b) F ,
xP(d ) T , якщо P(d x a) T для всіх a A,
невизначене в усіх інших випадках.
Визначення предикатів 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 є похідною, вона подається так: хР = х Р.
28

29.

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

30.

Властивості кванторів, пов'язані з неістотністю імен
– ім’я х V строго неістотне для предикатів хР та хР;
– ім’я х V строго неістотне для Р P = хР Р = хР;
– ім’я х V неістотне для Р P хР Р хР.
Залучаючи до розгляду реномінації та суперпозиції, маємо:
Ren) yP zR zy ( P), якщо z строго неістотне для P
R s) R vx ( yP) yR vx ( P), якщо y {v , x }
R ) R vx ( yP) zR vx
y
z
( P), якщо z строго неістотне для P та z {v , x }
R R) R uv ,, xy ( xP) R uv ( xP)
зокрема, R xy ( xP) xP
Ці властивості можна переформулювати для х.
За умови неістотності імені z в Ren та R маємо слабку рівність
Неістотність верхніх імен в реномінаціях:
yR zy,,xv ( P) R zy,,xv ( P) та yR zy,,xv ( P) R zy,,xv ( P) при y {v , x}
30

31.

S b) Обмежена дистрибутивність суперпозиції щодо x:
Sv ( xP, f ) xSv ( P, f )
S b) Обмежена дистрибутивність суперпозиції щодо x:
Sv ( xP, f ) xSv ( P, f )
Для S b та S b умови: х {v1,..., vn} та х неістотне для f1, ..., fn.
S ) Спеціальна дистрибутивність суперпозиції щодо x ( х {v1,..., vn}):
Sv1 ,...vn ( xP,S x ( f1, v1 ),...,S x ( f n , vn )) xSv1 ,...vn ( P,S x ( f1, v1 ),...,S x ( f n , vn ))
S ) Спеціальна дистрибутивність суперпозиції щодо x ( х {v1,..., vn}):
Sv1 ,...vn ( xP,Sx ( f1, v1 ),...,S x ( f n , vn )) xSv1 ,...vn ( P,S x ( f1, v1 ),...,S x ( f n , 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 s та R s рівність строга !
31

32.

Теорема 1. Композиції , , R vx , x зберігають:
– монотонність та антитонність квазіарних предикатів
– еквітонність однозначних квазіарних предикатів
– повнототальність і фінарність квазіарних предикатів
Наслідок 1. Класи монотонних та антитонних квазіарних предикатів
замкнені відносно композицій , , , &, , R vx , x, x.
Класи еквітонних і повнототальних однозначних квазіарних предикатів
замкнені відносно композицій , , , &, , R vx , x, x.
Теорема 2. 1. Композиції Sv , = зберігають:
– еквітонність однозначних квазіарних фукцій та предикатів
– повнототальність і фінарність квазіарних фукцій та предикатів
2. Композиції зберігають повнототальність і фінарність квазіарних
фукцій та предикатів
Наслідок 2. Класи еквітонних і повнототальних однозначних квазіарних
фукцій та предикатів замкнені відносно композицій Sv , =
32

33.

ЧИСТІ ПЕРШОПОРЯДКОВІ КОМПОЗИЦІЙНІ АЛГЕБРИ
Композиції , , R vx , x зберігають:
1) однозначність та тотальність квазіарних предикатів;
2) монотонність та антитонність квазіарних предикатів
Твердження 1. P P та P P
Твердження 2. 1) = , = ; = , = ;
2) T = F, F = T, T T = T, T F = F T = T, F F = F;
3) T = T = T, F = F = ;
T = T = , F = F = ; = = T.
v
v
Твердження 3. 1) R x ( ) , x( ) , R x (• ) • , x(• ) • ;
2) R vx (T) T, x(T) T; R vx (F) F, x(F) F
Теорема. Наступні класи предикатів замкнені щодо композицій
, , &, , , R vx , x, x
1) класи P-предикатів, T-предикатів, TS-предикатів
2) класи монотонних, антитонних, еквітонних предикатів
3) множини { }, { }, {T, F}, { , T, F} }, { , T, F} }, { , , T, F}
33

34.

Композиційну алгебру QRVA ( PrRVA , CQ), де CQ { , , R vx , x},
назвемо чистою першопорядковою алгеброю квазіарних предикатів.
Таким чином, можна виділити підалгебри алгебри QRVA
QPAV ( PrPAV , CQ) – алгебра P-предикатів;
QTAV ( PrTAV , CQ) – алгебра T-предикатів;
QTS VA ( PrTS VA , CQ) – алгебра TS-предикатів;
маємо QTS VA
QPAV та QTS VA
QTAV
QRM VA ( PrRM VA , CQ) – алгебра монотонних R-предикатів;
QRAVA ( PrRAVA , CQ) – алгебра антитонних R-предикатів;
QPEVA ( PrPEVA , CQ) – алгебра еквітонних P-предикатів;
маємо QPEVA
QPAV та QPEVA
QRM VA
QTAVA ( PrTAVA , CQ) – алгебра антитонних T-предикатів;
маємо QTAVA
QTAV та QTAVA
QRAVA
34

35.

Сингулярні алгебри
V A ({ VA}, CQ) та • V A ({• AV }, CQ)
для них маємо V A QPEVA та • V A QTAVA
алгебра BV A ({TAV ,FAV }, CQ)
маємо BV A
QTS VA , BV A
алгебри BLV A
BPV A
QPEVA , BV A
QTAVA
({ VA , • AV ,TAV ,FAV }, CQ)
({ VA ,TAV ,FAV }, CQ) та BTV A
({• AV ,TAV ,FAV }, CQ)
маємо V-A, BV-A BPV-A BLV-A ; V-A, BV-A BTV-A BLV-A ;
BPV A
QPEVA , BTV A
QTAVA , BLV A
QRM VA , BLV A
QRAVA
Тут позначає: є підалгеброю алгебри
35

36.

Задамо відображення дуалізації : PrRVA ® PrRVA так: ( P) P
Відображення дуалізації інволютивне: ( ( P)) P
Твердження 4. (T) = T, (F) = F, ( ) = , ( ) = ;
( PrPAV ) PrTAV , ( PrTAV ) PrPAV , ( PrTS VA ) PrTS VA ;
( PrPEVA ) PrTAVA , ( PrTAVA ) PrPEVA ,
( PrRAVA ) PrRM VA , ( PrRM VA ) PrRAVA
Алгебри Pr1 та Pr2 дуальні, якщо (Pr1) = Pr2 та (Pr2) = Pr1.
Маємо пари дуальних алгебр
QPAV та QTAV , QPEVA та QTAVA , QRM VA та QRAVA ,
V-A та V-A , BPV-A та BTV-A
Алгебри QRVA , QTS VA , BV-A , BLV-A автодуальні
36

37.

ОСОБЛИВОСТІ КВАЗІАРНИХ ПРЕДИКАТІВ
Неспростовними чи невиконуваними можуть бути лише однозначні предикати.
При цьому властивості неспростовності й виконуваності природно пов'язані:
Твердження. Предикат P неспростовний P невиконуваний.
P неспростовний F(P) = T( P) = P невиконуваний.
Для часткових предикатів невірні деякі важливі закони класичної логіки.
Приклад 1. modus ponens невірне для загального випадку квазіарних предикатів.
Задамо P як , Q – як тотожно хибний предикат. Тоді P Q теж .
Отже, P та P Q частково істинні, водночас Q – тотожно хибний.
Приклад 2. Задамо предикат P як тотожно істинний, Q – як , S – як тотожно
хибний. Тоді P Q та Q S частково істинні, водночас P S тотожно хибний.
Приклад 3. Нехай для предикатів p, q, s маємо p(d) = T, q(d) , s(d) = F;
тоді p(d) q(d) та q(d) s(d), але невірно, що p(d) s(d).
Приклади 2, 3 заперечують транзитивність еквіваленції та слабкої рівності. Саме
ця нетранзитивність є причиною невиконання деяких законів класичної логіки для
класів часткових предикатів, які використовують слабко рівні клінієві зв'язки.
37

38.

Необхідною й достатньою умовою коректності modus ponens у таких класах
часткових предикатів є еквітранзитивність – транзитивність відношення слабкої
рівності предикатів, тобто транзитивність еквіваленції
Отже, відмінність логіки часткових предикатів і логіки класичної виявляється вже
на пропозиційному рівні. Більш того, предикати прикладів 3 та 2 еквітонні.
Для класу еквітонних предикатів умова еквітранзитивності не виконується.
Водночас вона справджується для класу повнототальних еквітонних предикатів.
Приклад 4. Для загального випадку квазіарних предикатів
традиційні закони 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(Р) вірні
38

39.

Приклад 5. Існують квазіарні предикати: Р 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Р.
Приклад 6. Існують квазіарні предикати: Р 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Р
39

40.

Наведені співвідношення, пов’язані з елімінацією кванторів, видаються цілком
очевидними, хоча це не так.
T (R xy ( P)) T ( x( P))
(TR )
F ( x( P)) F (R xy ( P))
(FR )
T ( x( P)) T (R xy ( P))
(TR )
F (R xy ( P)) F ( x( P))
(FR )
Теорема 1. 1) Для загального випадку квазіарних предикатів невірне кожне із
співвідношень TR , FR , TR , FR ;
2) для монотонних предикатів:
– вірні TR та FR ,
– невірні FR та TR ;
3) для антитонних предикатів:
– вірні FR та TR ,
– невірні TR та FR .
40

41.

Окремий випадок співвідношень TR , FR , TR , FR :
T(Р) T( x(Р))
F( x(Р)) F(Р)
T( x(Р)) T(Р)
F(Р) F( x(Р))
(T )
(F )
(T )
(F )
Наслідок. 1) Для загального випадку квазіарних предикатів невірне кожне із
співвідношень T , F , T , F невірні;
2) для монотонних предикатів:
– вірні T та F ,
– невірні F та T ;
3) для антитонних предикатів:
– вірні F та T ,
– невірні T та F .
41

42.

Для адекватного опису властивостей елімінації кванторів використaємо
спеціальні предикати-індикатори z.
Теорема 2. Справджуються наступні співвідношення:
T ( Rvu,,yx ( P)) F (εy) T ( Rvu ( xP))
F ( Rvu ( xP)) F (εy) F ( Rvu,,yx ( P))
T (R uv ,, xy ( P)) T ( y) T (R uv ( xP))
F (R uv ( xP)) T ( y) F (R uv ,, xy ( P))
Використовуючи предикати-індикатори Ez, це можна переписaти так:
T (R uv ,, xy ( P)) T ( Ey) T (R uv ( xP))
F (R uv ( xP)) T ( Ey) F (R uv ,, xy ( P))
T (R uv ,, xy ( P)) F ( Ey) T (R uv ( xP))
F (R uv ( xP)) F ( Ey) F (R uv ,, xy ( P))
Як окремі випадки, а також використовуючи х, отримуємо:
T ( Ryx ( P)) F (εy) T ( xP)
T ( xP) F (εy) T ( Ryx ( P))
F ( xP) F (εy) F ( Ryx ( P))
F ( Ryx ( P)) F (εy) F ( xP)
42