Алгебра предикатів. Квантори

Змінна, яка пишеться після знака квантора, є операторною  змінною даного квантора; кажуть, що вона входить в цей квантор. Послідовність знаків кванторів разом з їхніми операторними змінними, виписані на початку деякої (квазі)формули, разом називаються її префіксом. Частина (квазі)формули після префікса називається основою цієї (квазі)формули; основа є областю дії кванторів, що входять у префікс. Змінна, що входить в область дії квантора по цій змінній, називається зв'язаною змінною в даній (квазі)формулі. Формула не залежить від своїх зв'язаних змінних: їм не можна приписувати значення, бо квантор, який зв'язує таку змінну, говорить про всю її область значень.

 

Квантор існування

Нехай, Р(х) – деякий предикат. Під виразом ($ х) Р(х) будемо розуміти  істинне висловлення, коли існує елемент множини М, для якого Р(х) – істинне, та хибне – в іншому випадку. Читається цей вираз так: «існує х таке, що  Р(х)» або «існує х, для якого Р(х)». Символ $  називається квантором існування. Операцію зв’язування квантором можна застосувати також до предикатів більшого числа змінних (детальніше про це йтиметься далі).

Приклад: Для предикатів, наведених у попередньому прикладі, маємо

($ х) (Р⁽¹⁾(х) &  Q⁽¹⁾(х)) – істинне висловлення, а (" х) (Р⁽¹⁾(х) &  Q⁽¹⁾(х)) - хибне.

Важливу роль у  логiцi предикатiв вiдiграє поняття областi дiї квантора, пiд якою розумiтимемо той вираз, до якого вiдноситься цей квантор. Область дiї квантора позначається за допомогою дужок. Лiва дужка, що вiдповiдає початку областi дiї, записується безпосередньо пiсля кванторної змiнної даного квантора, а вiдповiдна їй права дужка означає закiнчення областi дiї цього квантора. Там, де це не викликає невизначенностi, дужки можна опускати i замiсть "x(P(x)) або $x(P(x)) писати вiдповiдно "xP(x) або $xP(x).

Перехiд вiд P(x) до "xP(x) або $xP(x) називається зв’язуванням змiнної x. Iншi назви - навiшування квантора на змiнну x (або на предикат P(x)), або квантифiкацiя змiнної x.

Змiнна x, на яку навiшено квантор, називається зв’язаною, у протилежному випадку змiнна x називається вiльною.

Зв’язана змiнна, як було продемонстровано вище, вже не є  змiнною у класичному розумiннi цього  поняття. Вона потрiбна лише для iдентифiкацiї  терма, вiд якого залежить вiдповiдна пропозицiйна форма. Вираз "xP(x) не залежить вiд x i при фiксованих P i M має певне значення. Звiдси, зокрема, випливає, що можна здiйснювати перейменування зв’язаної змiнної (тобто перехiд вiд "xP(x) до "tP(t)) i воно не змiнює значення iстинностi виразу.

Навiшувати квантори можна й на багатомiснi предикати. Наприклад, застосовуючи квантори " i $ до змiнних x i y двомiсного предиката A(x,y), отримаємо чотири рiзнi одномiснi предикати "xA(x,y), $xA(x,y), "yA(x,y) i $yA(x,y). У перших двох змiнна x є зв’язаною, а змiнна y - вiльною, а у двох останнiх - навпаки.

Вираз "xA(x,y) (читається «для всiх x, A вiд x i y») є одномiсним предикатом B(y). Вiн є iстинним для тих i тiльки тих bÎM, для яких одномiсний предикат A(x,b) є iстинним для всiх x з M.

Приклад: Розглянемо двомiсний предикат A(x,y), визначений на множинi M = {a₁,a₂,a₃,a₄} за допомогою таблицi 1:

 

Таблиця 1

x \ y	a1	a2	a3	a4
a1	0	1	1	0
a2	0	1	1	1
a3	0	0	1	1
a4	0	0	1	0

Таблиці iстинностi для чотирьох вiдповiдних одномісних предикатів, що отримуються з A(x,y) шляхом навішування одного квантора, наведені у наступній таблиці:

 

Таблиця 2

y	"xA(x,y)	y	$xA(x,y)	x	"yA(x,,y)	x	$yA(x,y)
a1 a2 a3 a4	0     0     1     0	a1 a2 a3 a4	0     1     1     1	a1 a2 a3 a4	0      0      0      0	a1 a2 a3 a4	1     1     1     1

 У всіх чотирьох випадках до вільної змінної, що залишилась, можна застосовувати один з кванторів i, зв’язавши таким чином обидві змiннi, перетворити вiдповiднi предикати у висловлювання.

Для предиката з останнього прикладу отримаємо такі висловлювання:

"x("yA(x,y)) = 0,      "y("xA(x,y)) = 0,

$x($yA(x,y)) = 1,     $y($xA(x,y)) = 1,

$y("xA(x,y)) = 1,       $x("yA(x,y)) = 0,

"y($xA(x,y)) = 0,       "x($yA(x,y)) = 1.

Неважко переконатись, що висловлення, якi мiстять однаковi квантори, рiвносильнi. Обидва висловлення "x("yA(x,y)) і "y("xA(x,y)) є iстинними тодi i тiльки тодi, коли предикат A(x,y) приймає значення 1 на всiх кортежах значень (a,b) з M². Висловлення $x($yA(x,y)) i $y($xA(x,y)) iстиннi тодi i тiльки тодi, коли iснує принаймнi одна пара (a,b) така, що A(a,b) = 1.

У той же час  усi чотири висловлення з рiзнойменними  кванторами є, взагалi кажучи, не рiвносильними. Особливо слiд пiдкреслити, що суттєвим є порядок слiдування рiзнойменних кванторiв. Висловлення "x($yA(x,y)) i $y("xA(x,y)), взагалi кажучи, нерiвносильнi. Наприклад, у термiнах табличного задання предиката A(x,y), iстиннiсть першого висловлення "x($yA(x,y)) означає, що кожен рядок таблицi iстинностi мiстить принаймнi одну одиницю. А друге висловлення $y("xA(x,y)), iстинне тодi i лише тодi, коли у таблицi є стовпчик, що складається тiльки з одиниць.

Неважко поширити всi наведенi вище мiркування i висновки на предикати бiльшої арностi. Навiшування  одного квантора завжди зменшує число вiльних змiнних i арнiсть предиката на одиницю. Застосування кванторiв до всiх змiнних предиката перетворює його у висловлення (iнодi таку предикатну формулу називають замкненою формулою). Порядок слiдування рiзнойменних кванторiв у формулi є суттєвим.

 4.Формули логіки предикатів

На мові предикатів можна скласти набагато складніші  речення, ніж на мові логіки висловлень. Введемо поняття формули логіки предикатів. Алфавіт цієї логіки містить  такі символи:

 предметних змінних х₁, х₂, ..., х_n... ;

 предикатів А₁^(t), А₂ ^(t), ..., А_к^(t), ..., де t = 0,1,2,...;

 логічні &, Ú, ®, ~, Ø;

 кванторів $, ";

 дужки і кому ) , (.

Щоб зменшити кількість  індексів, символи предметних змінних  будемо позначати через х, у, z, а символи предикатів – через P, S, Q, R тощо.

Слово в алфавіті логіки предикатів називається формулою, якщо воно задовольняє таке індуктивне означення (одночасно визначаються поняття вільної та зв’язаної змінних у формулі):

1. Якщо А_і^(t) – символ предиката, х_і,1 , х_і,2 , ...,х_і,t – символи предметних змінних, не обов’язково різних, то А_і^(t)( х_і,1 , х_і,2 , ...,х_і,t) – формула, яка називається атомарною. Всі предметні змінні атомарних формул є вільними, зв’язаних змінних немає.
2. Нехай,  А – формула. Тоді Ā – також формула. Вільні й зв’язані змінні формули Ā – це відповідно вільні та зв’язані змінні формули А.
3. Нехай, А і В – формули, причому немає таких предметних змінних, які були б зв’язаними в одній формулі, але вільними в іншій. Тоді  

(А Ú В), (А & В), (А ® В), (А ~ В)

є формулами, в  яких вільні змінні формул А та В залишаються вільними, а зв’язані змінні формул А і В – зв’язаними.

4. Нехай, А – формула, яка містить вільну змінну х. Тоді

 (" х) А, ($ х)А  (1)

також є формулами. Змінна х у них – зв’язана. Інші ж змінні, які є у формулі А є вільними, залишаються й вільними у формулах (1). Змінні, які у формулі А є зв’язаними, залишаються зв’язаними й у формулах (1). У першій із формул (1) формула А називається областю дії квантора " , а в другій – областю дії квантора $.

5. Слово в алфавіті логіки предикатів є формулою тільки в тому випадку, якщо це випливає з правил 1-4. Зазначимо, що за означенням формули жодна змінна не може бути одночасно вільною та зв’язаною.

Приклади:

1) Такі вирази  є формулами логіки предикатів: А₅⁽³⁾ (х₁, х₅, х₇) – атомарна формула, в якій х₁, х₅, х₇ – вільні змінні; ("х₁) ($х₂) А₁⁽³⁾ (х₁, х₂, х₃) ® ("х₁) А₁⁽²⁾ (х₁, х₄) – формула, в якій х₁, х₂ – зв’язані, а х₃, х₄ – вільні змінні.

2) Вираз ($х₂) ("х₂) А₁⁽²⁾ (х₁, х₃) & А₂⁽²⁾ (х₁, х₃) не є формулою.

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

Під інтерпретацією розуміють систему М_f = áМ, fñ, яка складається з не порожньої множини М і відповідності f, що стоять у відповідності кожен з кожним предикатним символом А_j^(t) певний t-місний предикат (будемо позначати предикати, поставлені у відповідність предикатним символам, тими самими символами).

При заданій інтерпретації  вважають, що предметні змінні пробігають множину М, а символи ¯, Ú, &, ®, ~, Ø, і символи кванторів мають своє звичайне значення. Для заданої інтерпретації кожна формула без вільних змінних є висловленням, яке істинне чи хибне, а кожна формула з вільними змінними виражає деякий предикат на множині М, який істинний при одних значеннях змінних з цієї множини та хибний при інших.

Значення формули F на наборі áа₁, ..., а_nñ, а_і є М, своїх вільних змінних х_і,1 ,...,х_і,n позначимо символом Fê_á а_{1, ....,}а_nñ.

Приклади:

1) Розглянемо три формули:

А₁⁽²⁾ (х₁, х₂);

(" х₂) А₁⁽²⁾ (х₁, х₂);

($ х₁) А₁⁽²⁾ (х₁, х₂).

Візьмемо як область  інтерпретації множину цілих  додатних чисел й інтерпретуємо А₁⁽²⁾(х, у) як х £  у. Тоді перша формула – це предикат х₁ £, х₂, який набуває істинного значення для всіх пар (а, b) цілих додатних чисел таких, що а £ b. Друга формула виражає властивість “ для кожного цілого додатного числа у матимемо х £  у ”, яка виконується тільки при х=1. Нарешті, третя формула – це істинне висловлення про існування найменшого цілого додатного числа. Якби як область інтерпретації ми розглядали множину цілих чисел, то третя формула була б хибним висловленням.

2) Нехай, М_f = á N, f ñ, де N – множина натуральних чисел; f – відповідність, що ставить у відповідність із предикатними символами S⁽³⁾ (x, y, z), Р⁽³⁾ (x, y, z) предикати S⁽³⁾ (x, y, z): x + y = z; Р⁽³⁾ (x, y, z): x y = z.

Запишемо формули, істинні  в М тоді й тільки тоді, коли виконано такі умови:

• х = 0;
• х = 1;
• х – парне;
• х – просте число;
• х = у;
• х £ у;
• х ділить у;
• комутативність додавання.

Це відповідно формули:

• F₁ (x) = (" y) S ⁽³⁾ (x, y, y), оскільки х + у = у для будь-якого у тоді й тільки тоді, коли х = 0;
• F₂ (x) = (" y) Р ⁽³⁾ (x, y, y);
• F₃ (x) = ($ y) S ⁽³⁾ (у, y, х);
• F₄ (x) = F₁ (x) & (" y) (" z) (Р ⁽³⁾ (у, z, х)® (F₂ (y)Ú F₂ (z))), де F₁, F₂ – формули, визначені вище;
• F₅ (x) =(" z) (" u) S ⁽³⁾ (x, z, u)® S ⁽³⁾ (y, z, u));
• F₆ (x, y) =($ z) S ⁽³⁾ (x, z, y);
• F₇ (x, y) =($ z) P ⁽³⁾ (x, z, y);
• (" x) (" y) (" z) S ⁽³⁾ (x, y, z)® S ⁽³⁾ (y, x, z)).

5.Рівносильність формул

Нехай, формули F і G мають одну і ту саму множину вільних змінних (зокрема, порожню).

Формули F та G є рівносильними  в заданій інтерпретації, якщо на будь-якому наборі значень вільних змінних вони набувають однокових значень (тобто якщо формули виражають у цій інтерпретації один і той самий предикат). Формули F та G є рівносильними  на множині М, якщо вони рівносильні у всіх інтерпретаціях, заданих на множині М. Формули F та G є рівносильними (в логіці предикатів), якщо вони рівносильні на всіх множинах (тоді писатимемо F º G ).