Формули. Р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 = {a1,a2,...,an} кванторнi формули можна перетворити у рiвносильнi їм звичайнi формули логiки висловлень:

xP(x) = P(a1)P(a2) ... P(an),

xP(x) = P(a1)P(a2) ... P(an).

Зам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вносильними.