Реферат на тему:
Формули. Рiвносильнiсть формул. Тотожно iстиннi формули
Наведемо 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дносно кон’юнeц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.
Нашли опечатку? Выделите и нажмите CTRL+Enter
