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

   Наприклад, усi тотожно iстиннi (усi тотожно хибнi) формули рiвносильнi мiж собою. Очевидно також, що коли F₁ i F₂ рiвносильнi, то формула F₁~F₂ є тотожно 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снує процедура розв’язання другої з цих проблем, то на її основi можна  сформулювати такий тривiальний алгоритм, що породжує шукану множину T тотожно iстинних формул. Послiдовно будуємо всi формули, кожну з них за вiдомою процедурою перевiряємо на тотожну iстиннiсть i вносимо до множини T т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 певних формул. Для цього достатньо пiдiбрати одну вiдповiдну пiдстановку. Застосовувати цей метод можна також, коли предметна область M є скiнченною. Пов’язано це з тим, що для скiнченної множини M = {a₁,a₂,...,a_n} кванторнi формули можна перетворити у рiвносильнi їм звичайнi формули логiки висловлень:

   "xP(x)  =  P(a₁)ÙP(a₂)Ù ... ÙP(a_n),

   $xP(x)  =  P(a₁)ÚP(a₂)Ú ... ÚP(a_n).

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

   Для доведення ж рiвносильностi предикатних  формул, що заданi на нескiнченних предметних областях, прямий перебiр виключається i доводиться використовувати рiзнi опосередкованi методи.

   Наприклад, вище шляхом простих мiркувань було доведено рiвносильнiсть формул, що описує переставнiсть однойменних кванторiв у двомiсних предикатах, тобто доведено iстиннiсть формул

   "x"yA(x,y)~"y"xA(x,y) i $x $yA(x,y)~$y$xA(x,y).

   Аналогiчними  мiркуваннями доведемо рiвносильнiсть, що описує дистрибутивнiсть квантора "x вiдносно кон’юнêцiї:

   "x(A(x)ÙB(x)) = "xA(x)Ù"xB(x).

   Нехай лiва частина цього співвiдношення є iстинною для деяких предикатiв  A i B. Тодi для будь-якого aÎM iстинною буде кон’юнкцiя A(a)ÙB(a), тому A(a) i B(a) одночасно iстиннi для довiльних a, отже, формула "xA(x)Ù"xB(x) є iстинною. Якщо ж лiва частина хибна, то це означає, що для деякого aÎM хибним є або A(a), або B(a). Тому хибним буде або "xA(x), або "xB(x), а отже, хибною буде i права частина.

   Подiбним методом можна довести дистрибутивнiсть квантора $x вiдносно диз’юнкцiї:

   $x(A(x)ÚB(x))  =  $xA(x)Ú$xB(x).

   У той же час аналогiчнi простi мiркування дозволяють переконатись, що квантори "x i $x є, взагалi кажучи, недистрибутивними вiдносно диз’юнкцiї i кон’юнкцiї вiдповiдно. Насправдi, iстинними є лише такi iмплiкацiї:

   "xA(x)Ú"xB(x)®"x(A(x)ÚB(x)),

   $x(A(x)ÙB(x))®$xA(x)Ù$xB(x).

   Якщо  один з предикатiв A(x) чи B(x) є тотожно iстинним, то лiва i права частини першої iмплiкацiї одночасно будуть iстинними. Якщо ж iснуватимуть такi значення a,bÎM, що A(a) i B(b) є хибними, то лiва частина буде хибною, а права - може бути хибною або iстинною. Для її iстинностi достатньо, щоб для кожного aÎM 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дношення: Ø($xP(x))  =  "x(ØP(x)).

   Нехай для деякого предиката P i предметної областi M лiва частина iстинна. Тодi не iснує aÎM, для якого P(a) iстинно. Отже, для всiх aÎM P(a) хибне, тобто ØP(a) iстинно. Таким чином, права частина є iстинною. Якщо ж лiва частина хибна, то iснує bÎM, для якого P(b) iстинно, тобто ØP(b) - хибне. Отже, права частина буде також хибною.

   Аналогiчно  доводиться рiвносильнiсть 

   Ø("xP(x))  =  $x(ØP(x)).

   Наведемо  без доведень ще декiлька важливих рiвносильних спiввiдношень. Нехай B предикатна формула, що не мiстить вiльних входжень змiнної x, тодi справедливi такi рiвносильностi:

   "x(A(x)ÚB)  =  "xA(x)ÚB,  B®"xA(x)  =  "x(B®A(x)),

   $x(A(x)ÚB)  =  $xA(x)Ú B,  B®$xA(x)  =  $x(B®A(x)),

   "x(A(x)ÙB)  =  "xA(x)ÙB,  "xA(x)®B  =  $x(A(x)®B),

   $x(A(x)ÙB)  =  $xA(x)ÙB,   $x A(x)®B  =  "x(A(x)®B).

   Цi спiввiдношення означають, що формулу, яка не мiстить вiльних входжень x, можна виносити за межi областi дiї квантора, що зв’язує x. З iншого боку цi ж рiвносильностi дозволяють включати або вносити вiдповiдну формулу B до областi дiї квантора за змiнною x, вiд якої B не залежить.

   Можливiсть  проведення зазначених рiвносильних перетворень для предикатних формул дозволяє означити в логiцi предикатiв поняття певної канонiчної або нормальної форми.

   Формула, що має вигляд Q₁x₁Q₂x₂...Q_nx_nF, де Q₁,Q₂,...,Q_n - квантори, а F формула, яка не мiстить кванторiв i є областю дiї всiх n кванторiв, називається випередженою (пренексною) нормальною формулою, або формулою у випередженiй формi.

   Формула, яка знаходиться в пренекснiй  формi i рiвносильна формулi P, називається випередженою (пренексною) формою P.

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

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

    Очевидно, для формул логіки предикатів зберігаються всі рівносильності правила рівносильних перетворень логіки висловлень. Крім того, можна довести такі правила.

 
       

1. Зв’язок кванторів із запереченням.

    Нехай, А – формула, що містить вільну змінну х. Тоді справджуються рівносильності: 

(" х) А(х) º ($ х) Ā(х)                                    (2)

($ х) А(х) º (" х) Ā(х)                                    (3)

    Доведемо  спочатку рівносильність (2). Нехай  х₁,...., х_n – множина (може бути порожньою) всіх вільних змінних формули А, відмінних від х. Нехай М_¦=áМ, ¦ñ - довільна інтерпретація. Доведемо, що на будь-якому наборі значень своїх вільних змінних á а₁,...., а_nñ,  а_і є М, формули (" х) А(х) й    ($ х) Ā(х) набувають однакових значень істинності.