Реферат на тему:
Наведемо iндуктивне означення поняття формули логiки предикатiв (предикатної формули абопросто формули ) на предметнiй областi M.
1. Усi предикати P(x1,x2,...,xn) на множинi M є формулами. Такi формули називають елементарними, або атомарними.
2. Якщо A i B - формули, то (ØA), (ØB), (AÙB), (AÚB), (A®B), (A~B) теж є формулами.
3. Якщо A - формула, а x - вiльна змiнна в A, то ("x(A)) i ($x(A)) теж формули.
4. Iнших формул, крiм утворених за правилами 1-3, немає.
Це означення дозволяє твердити, що усi формули алгебри висловлень є формулами логiки предикатiв, оскiльки висловлення - це нульмiснi предикати.
За допомогою наведеного означення неважко також переконатись, що вирази ("x($y(A(x,y))®(B(x)Ú($z(C(x,z))))) i ("x("y(A(x,y)ÙB(x))®($y(C(x,y)))) є формулами логiки предикатiв, а вираз ("x(A(y)®($x(B(x))))) не є формулою, оскiльки у виразi (A(y)®($x(B(x)))), який є правильною формулою, змiнна x є зв'язаною, тобто не є вiльною змiнною 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во).
Нехай 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. Формула $xA(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стинними будуть формули "xP(x)®P(y) 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ки висловлень:
"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вносильними.
Пропонуємо самост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ÎMP(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, $xA(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 не залежить.