Поняття предиката

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

($ х) (Р⁽¹⁾(х) &  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 зм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: 

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

     У всiх чотирьох випадках до вiльної змiнної, що залишилась, можна застосовувати один з кванторiв i, зв’язавши таким чином обидвi зм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 є суттєвим. 

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

   Наведемо iндуктивне означення поняття  формули логiки предикатiв (предикатної формули або просто формули ) на предметнiй областi M.

   1. Усi предикати P(x₁,x₂,...,x_n) на множинi M є формулами. Такi формули називають елементарними, або атомарними.

   2. Якщо A i B - формули, то (ØA), (ØB), (AÙB), (AÚB), (A®B), (A~B) теж є формулами.

   3. Якщо A - формула, а x - вiльна змiнна в A, то ("x(A)) i ($x(A)) теж формули.

   4. Iнших формул, крiм утворених за  правилами 1-3, немає. 

   Це  означення дозволяє твердити, що усi формули алгебри висловлень є  формулами логiки предикатiв, оскiльки висловлення - це нульмiснi предикати.

   За  допомогою наведеного означення  неважко також переконатись, що вирази ("x($y(A(x,y))®(B(x)Ú($z(C(x,z))))) i ("x("y(A(x,y)ÙB(x))®($y(C(x,y)))) є формулами логiки предикатiв, а вираз ("x(A(y)®($x(B(x))))) не є формулою, оскiльки у виразi (A(y)®($x(B(x)))), який є правильною формулою, змiнна x є зв'язаною, тобто не є вiльною змiнною i квантор "x до неї застосувати не можна.

   Для зручност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во).

   Нехай F(x₁,x₂,...,x_n) - деяка формула логiки предикатiв на множинi M. При логiчнiй (iстинностнiй) iнтерпретацiї формули F можливi такi три основнi ситуації.

   1. Iснує набiр значень змiнних, для  якого формула F перетворюється на iстинне висловлення. У цьому разi формула F називається виконуваною в областi M.

   Якщо  для F iснує область M, в якiй F є виконуваною, то формула F називається просто виконуваною.

   2. Якщо формула F приймає значення 1 (тобто є виконуваною) для всiх наборiв значень з M, то вона називається тотожно iстинною в M. Формула, тотожно iстинна у будь-яких M, називається тотожно iстинною або логiчно загальнозначущою (скорочено - лзз).

   3. Якщо формула F є невиконуваною в M, то вона називається тотожно хибною в M. Формула, невиконувана в усiх M, називається тотожно хибною, або суперечнiстю.

   Приклад. Формула $xA(x,y)®"xA(x,y) є виконуваною i вона ж є тотожно iстинною в усiх одноелементних областях M. Формула F(x₁,x₂,...,x_n)ÚØF(x₁,x₂,...,x_n) тотожно iстинна, а формула F(x₁,x₂,...,x_n)ÙØF(x₁,x₂,...,x_n) тотожно хибна. Тотожно iстинними будуть формули "xP(x)®P(y) i P(y)®$xP(x).

   Формули F₁ i F₂ називаються рiвносильними (еквiвалентними), якщо при всiх можливих пiдстановках значень замiсть їх змiнних вони набувають однакових значень; позначається F₁ = F₂.