РЕФЕРАТ

На тему:

Поняття та логіка предикатів 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(x1,x2,…,xn) на множинi M називається довiльна
функцiя типу Mn(B, де B = {0,1} — бульовий (двiйковий) алфавiт.

Множина M називається предметною областю, або унiверсальною множиною, а
x1,x2,…,xn — предметними змiнними, або термами предиката P.

Множина елементiв (a1,a2,…,an)(Mn таких, що P(a1,a2,…,an) = 1
називається областю iстинностi (або характеристичною множиною) предиката
P.

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

Взагалi кажучи, можна означити так званий багатосортний предикат, як
функцiю типу M1(M2(…(Mn(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(x1,x2,…,xn) заф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(x1,x2,…,xn) вiдповiдає вiдношення R таке, що (a1,a2,…,an)(R тодi i
тiльки тодi, коли P(a1,a2,…,an) = 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: Mn(M
можна поставити у вiдповiднiсть (n+1)-мiсний предикат P на M такий, що
P(a1,a2,…,an,an+1) = 1 тодi i тiльки тодi, коли
f(a1,a2,…,an) = an+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(x1,x2,…,xn) i Q(x1,x2,…,xn) — n-мiснi предикати на множинi
M.

Кон’юнкцiєю P(x1,x2,…,xn)(Q(x1,x2,…,xn) називають предикат
R(x1,x2,…,xn), який набуває значення 1 на тих i тiльки тих наборах
значень термiв, на яких обидва предикати P(x1,x2,…,xn) i
Q(x1,x2,…,xn) дорiвнюють 1.

Очевидно, що область iстинностi предиката R(x1,x2,…,xn) = 
P(x1,x2,…,xn)(Q(x1,x2,…,xn) збiгається з теоретико-множинним
перетином областей iстинностi предикатiв P(x1,x2,…,xn) i
Q(x1,x2,…,xn).

Диз’юнкцiєю P(x1,x2,…,xn)(Q(x1,x2,…,xn) називають предикат
T(x1,x2,…,xn), який набуває значення 1 на тих i тiльки тих наборах
значень термiв, на яких або предикат P(x1,x2,…,xn), або предикат
Q(x1,x2,…,xn) дорiвнює 1.

Областю iстинностi предиката T(x1,x2,…,xn) буде об’єднання областей
iстинностi предикатiв P(x1,x2,…,xn) i Q(x1,x2,…,xn).

Запереченням (P(x1,x2,…,xn) предиката P(x1,x2,…,xn) називають
предикат S(x1,x2,…,xn), який дорiвнює 1 на тих i лише тих значеннях
термiв, на яких предикат P(x1,x2,…,xn) дорiвнює 0.

Область iстинностi предиката S(x1,x2,…,xn) = (P(x1,x2,…,xn) — це
доповнення (до множини Mn) областi iстинностi предиката P(x1,x2,…,xn).

Аналогiчним чином вводять й iншi логiчнi операцiї (, ~ тощо. Як правило,
кожнiй iз цих операцiй вiдповiдає певна теоретико-множинна операцiя над
областями iстинностi предикатiв-операндiв. Неважко узагальнити означення
всiх введених операцiй для предикатiв P(x1,x2,…,xn) i Q(y1,y2,…,ym),
що залежать вiд рiзних змiнних i мають рiзну мiснiсть.

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

Похожие записи