Формулі. 
Рівносильність формул. 
Тотожно істинні формули (реферат)

РЕФЕРАТ На тему:

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

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

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

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

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

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

За допомогою наведеного означення неважко також переконатись, що вирази ((x, y))x)(x, z))))) i ((x, y)))(x, y)))) є формулами логiки предикатiв, а вираз ((y)(x))))) не є формулою, оскiльки у виразi (A (y)(x)))), який є правильною формулою, зм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дують один за одним. При цьому виконання таких кванторних операцiй вiдбувається в порядку, зворотньому до їх написання (справа налiво).

Нехай F (x1,x2,…, xn) — деяка формула лог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стю.

Приклад 5.7. Формула x, y) xA (x, y) є виконуваною i вона ж є тотожно iстинною в усiх одноелементних областях M. Формула F (x1,x2,…, xn) F (x1,x2,…, xn) тотожно iстинна, а формула F (x1,x2,…, xn) F (x1,x2,…, xn) тотожно хибна. Тотожно iстинними будуть формули x)) i P (y)xP (x).

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

Наприклад, усi тотожно iстиннi (усi тотожно хибнi) формули рiвносильнi мiж собою. Очевидно також, що коли F1 i F2 рiвносильнi, то формула F1~F2 є тотожно 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 = {a1,a2,…, an} кванторнi формули можна перетворити у рiвносильнi їм звичайнi формули логiки висловлень:

x) = P (a1)2). n),.

x) = P (a1)2). 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, y)~x, y) i x, y)~x, y).

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

(x))) = x) xB (x).

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

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

(x))) = x) xB (x).

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

x)xB (x)x (A (x))),.

(x)))xA (x)xB (x).

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

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

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

x)) =)).

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

(x) = x) BxA (x) =)),.

(x) = x) BxA (x) =)),.

(x) = x) x)= (x).

(x) = x) (x)= (x).

Ц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.