Формули. Рiвносильнiсть формул. Тотожно 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чної або нормальної форми.

Формула, що має вигляд Q1x1Q2x2...QnxnF, де Q1,Q2,...,Qn - квантори, а 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.