Поняття та логіка предикатів

     РЕФЕРАТ

     На  тему:

     Поняття та логіка предикатів 
1.Поняття предиката 

     Числення  висловлень, що розглядалось у попередн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в починається з аналізу  граматичної будови простих висловлень i ґрунтується на такому висновку: простi висловлення виражають той факт, що деякi об’єкти (або окремий об’єкт) мають певнi властивостi, або що цi об’єкти знаходяться мiж собою у певному вiдношеннi.

     Наприклад, в iстинному висловленнi «3 є просте число» пiдмет «3» - це об’єкт, а присудок «є просте число» виражає деяку його властивiсть.

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

     Наприклад, замiнюючи у наведеному вище висловленнi 3 на 1, 5, 9 або 12, матимемо вiдповiдно такi висловлення: «1 є просте число», «5 є  просте число», «9 є просте число», «12 є просте число», з яких друге є iстинним, а решта - хибними висловленнями.

     Таким чином, можна розглянути вираз «x є просте число», який не є висловленням, а є так званою пропозицiйною (висловлювальною) формою. Тобто формою (або формуляром), пiсля пiдстановки в яку замiсть параметра (змiнної) x об’єктiв (значень) з певної множини M, дiстаємо висловлення.

     Аналогiчно  можна трактувати, наприклад, пропозицiйнi форми «a є українцем», «b i c є однокурсники», «c важче d», або «точка x лежить мiж точками y i z». У першi двi з них можна пiдставляти замiсть параметрiв a, b i c прiзвища конкретних людей. У третю замiсть c i d назви будь-яких об’єктiв (предметiв), якi мають вагу. Для четвертої множиною M значень змiнних x, y i z є множина точок певної прямої.

     Перша з цих пропозицiйних форм задає, як i в наведенiй ранiше формi, певну властивiсть для об’єкта a. Iншi три форми описують деякi вiдношення мiж вiдповiдними об’єктами.

     Розглянувши конкретнi приклади i коротко зупинившись  на мотивацiї та змiстовнiй iнтерпретацiї подальших понять, перейдемо до формальних математичних означень.

     n-мiсним  предикатом P(x₁,x₂,...,x_n) на множинi M називається довiльна функцiя типу Mⁿ®B, де B = {0,1} - бульовий (двiйковий) алфавiт.

     Множина M називається предметною областю, або унiверсальною множиною, а x₁,x₂,...,x_n - предметними змiнними, або термами предиката P.

     Множина елементiв (a₁,a₂,...,a_n)ÎMⁿ таких, що P(a₁,a₂,...,a_n) = 1 називається областю iстинностi (або характеристичною множиною) предиката P.

     Якщо  P(a₁,a₂,...,a_n) = 1, то згiдно з логiчною iнтерпретацiєю будемо говорити, що предикат P є iстинним на (a₁,a₂,...,a_n). У противному разi, казатимемо, що предикат P є хибним.

     Взагалi кажучи, можна означити так званий багатосортний предикат, як функцiю типу M₁´M₂´...´M_n®B, дозволивши різним його аргументам приймати значення з рiзних множин. Iнодi це буває доцiльним; однак частiше в логiцi предикатiв використовують наведене ранiше означення.

     Неважко зрозумiти, що пропозицiйна форма  є одним зi способiв задання  предиката.

     Для n = 1 предикат P(x) називається одномiсним або унарним, для n = 2 P(x,y) - двомiсним або бiнарним, для n = 3 P(x,y,z) - трьохмiсним або тернарним предикатом.

     Очевидно, що коли в n-арному предикатi P(x₁,x₂,...,x_n) зафiксувати деякi m змiнних (тобто надати їм певних значень з множини M), то отримаємо (n-m)-мiсний предикат на множинi M. Це дозволяє вважати висловлення нульмiсними предикатами, якi утворено з багатомiсних предикатiв пiдстановкою замiсть усiх їхнiх параметрів певних значень з предметної областi. Таким чином, висловлення можна розглядати як окремий випадок предиката.

     Для довiльної множини M i довiльного n iснує взаємно однозначна вiдповiднiсть мiж сукупнiстю всiх n-мiсних предикатiв на M i множиною всiх n-арних вiдношень на M. А саме, будь-якому предикату P(x₁,x₂,...,x_n) вiдповiдає вiдношення R таке, що (a₁,a₂,...,a_n)ÎR тодi i тiльки тодi, коли P(a₁,a₂,...,a_n) = 1. Очевидно, що при цьому R є областю iстинностi предиката P.

     Крiм  того, за будь-якою вiдповiднiстю C мiж множинами A i B (тобто CÍA´B) можна побудувати бiнарний двосортний предикат P(x,y) таким чином: P(a,b) = 1 тодi i тiльки тодi, коли (a,b)ÎC для aÎA i bÎB.

     Зокрема, будь-якiй функцiональнiй вiдповiдностi або функцiї f: Mⁿ®M можна поставити у вiдповiднiсть (n+1)-мiсний предикат P на M такий, що P(a₁,a₂,...,a_n,a_n+1) = 1 тодi i тiльки тодi, коли f(a₁,a₂,...,a_n) = a_n+1.

     Отже, такi фундаментальнi математичнi поняття  як вiдповiднiсть (зокрема, функцiя), вiдношення, висловлення можна розглядати як окремi випадки бiльш загального поняття предиката. 

      2.  Лог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д тих самих змiнних.

     Нехай P(x₁,x₂,...,x_n) i Q(x₁,x₂,...,x_n) - n-мiснi предикати на множинi M.

     Кон’юнкцiєю P(x₁,x₂,...,x_n)ÙQ(x₁,x₂,...,x_n) називають предикат R(x₁,x₂,...,x_n), який набуває значення 1 на тих i тiльки тих наборах значень термiв, на яких обидва предикати P(x₁,x₂,...,x_n) i Q(x₁,x₂,...,x_n) дорiвнюють 1.

     Очевидно, що область iстинностi предиката R(x₁,x₂,...,x_n) =  P(x₁,x₂,...,x_n)ÙQ(x₁,x₂,...,x_n) збiгається з теоретико-множинним перетином областей iстинностi предикатiв P(x₁,x₂,...,x_n) i Q(x₁,x₂,...,x_n).

     Диз’юнкцiєю P(x₁,x₂,...,x_n)ÚQ(x₁,x₂,...,x_n) називають предикат T(x₁,x₂,...,x_n), який набуває значення 1 на тих i тiльки тих наборах значень термiв, на яких або предикат P(x₁,x₂,...,x_n), або предикат Q(x₁,x₂,...,x_n) дорiвнює 1.

     Областю iстинностi предиката T(x₁,x₂,...,x_n) буде об’єднання областей iстинностi предикатiв P(x₁,x₂,...,x_n) i Q(x₁,x₂,...,x_n).

     Запереченням ØP(x₁,x₂,...,x_n) предиката P(x₁,x₂,...,x_n) називають предикат S(x₁,x₂,...,x_n), який дорiвнює 1 на тих i лише тих значеннях термiв, на яких предикат P(x₁,x₂,...,x_n) дорiвнює 0.

     Область iстинностi предиката S(x₁,x₂,...,x_n) = ØP(x₁,x₂,...,x_n) - це доповнення (до множини Mⁿ) областi iстинностi предиката P(x₁,x₂,...,x_n).

     Аналогiчним чином вводять й iншi логiчнi операцiї ®, ~ тощо. Як правило, кожнiй iз цих операцiй вiдповiдає певна теоретико-множинна операцiя над областями iстинностi предикатiв-операндiв. Неважко узагальнити означення всiх введених операцiй для предикатiв P(x₁,x₂,...,x_n) i Q(y₁,y₂,...,y_m), що залежать вiд рiзних змiнних i мають рiзну мiснiсть.

     Знаючи, як виконуються окремi операцiї, можна  утворювати вирази або формули, операндами яких є предикати. Наприклад розглянемо формулу P₁(x)Ú(ØP₃(x,z)®P₂(y,x,z)), що задає деякий предикат Q(x,y,z). Значення предиката Q неважко обчислити для будь-якого набору значень його термiв x, y, z, виходячи зi значень предикатiв P₁, P₂, P₃ на цьому наборi.