Реферат: Формули Рiвносильнiсть формул Тотожно iстинн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 1 x 1 Q 2 x 2 ...Qn xn F , де Q 1 ,Q 2 ,...,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 .