Предикати. Логічні операції над предикатами

У кожному висловленні є підмет і присудок (або об’єкт* і предикат). Прості висловлення виражають певні властивості деяких об’єктів (об’єкта) або ж певні відношення, в яких вони перебувають між собою. При цьому поняття «властивість» і поняття «відношення» розглядаються як окремі випадки загального поняття «предикат».

Розглянемо приклади.

1. Нехай N = {1, 2, 3,...} - множина натуральних чисел і буквою Р позначено властивість натурального числа бути простим. Тоді висловлення «Натуральне число 2 є просте число» можна записати як Р (2). В наведеному висловленні підмет є найменуванням конкретного об’єкта (числа 2), присудок виражає його властивість; це висловлення істинне. Хибне висловлення «Натуральне число 4 є просте число» можна записати як Р (4).

Більш загально можна розглядати вирази вигляду «Натуральне число x є просте число». Цей вираз символічно можна подати у вигляді Р (х). Тут х позначає об’єкт, а символ Р - предикат. Якщо замінити символ х значенням конкретного натурального числа, отримаємо висловлення - істинне чи хибне. Сам вираз «Натуральне число x є просте число» чи його символічний запис Р (х) не є висловленням. Це так звана висловлювальна форма, вона стає висловленням лише після заміни символа змінної, яка входить у цей вираз, назвою відповідного об’єкта (натурального числа). А.Тарський у відомій книзі «Введение в логику и методологию дедуктивных наук» [57] образно порівнює подібну відмінність між висловлювальною формою і висловленням з відмінністю між формуляром для анкети і анкетою. Формуляр для анкети є заготовленою формою, що містить певне число порожніх місць, в які слід вписати конкретні дані, в результаті чого одержується те, що називається анкетою. Зокрема, замінюючи символ х конкретними натуральними числами, матимемо

.

Отже, по суті вираз Р (х) (або відповідний йому «Натуральне число х є просте число») є функцією, яка визначена на множині натуральних чисел, і значеннями її є висловлення.

Враховуючи те, що, вивчаючи висловлення, абстрагуються від їх змісту і беруть до уваги лише значення їх істинності, можна вважати, що предикат Р (х) визначає логічну функцію, аргументами якої є елементи множини натуральних чисел N, а значеннями - 1 і 0 («істинне», «хибне»). Іншими словами, предикат Р є відображенням множини N в двоелементну множину {0,1}**.

2. Нехай маємо вираз «х брат у». Тут букви х і у позначають чоловічі імена. При цьому вважатимемо, що ім’ям людина однозначно визначається. Якщо буквою В позначити відношення «брат», то вираз символічно можна записати як В (х, у). Тоді висловлення «Іван - брат Миколи» можна записати як В (i, m), де через i, m позначено Іван, Микола відповідно. Відношення «брат» можна розглядати як функцію двох змінних, які пробігають незалежно одна від одної множину людей чоловічої статі, і яка приймає значення 0 і 1 («хибне», «істинне») в залежності від того, є вказані дві людини братами чи ні. Отже, предикат В залежить від двох аргументів і є відображенням множини всіх пар чоловічих імен в двоелементну множину {0, 1}.

3. Нехай маємо бінарне відношення, яке визначається на множині натуральних чисел і описується словом «більше». В цьому випадку маємо висловлювальну форму «х більше у». Якщо розглядати цю форму як функцію двох змінних х і у (які пробігають множину натуральних чисел), яка приймає значення 1 чи 0 (в залежності від того, буде відповідне висловлення істинним чи хибним), то ця форма визначає предикат >(х, у). Тут використали запис для відзначення того, що предикат - це функція. А, взагалі, предикат >(х, у) записується переважно у вигляді х > у.

Аналогічно можна було б розглянути предикат xRy (або у функціональному виді R (х, у)), де R позначення деякого бінарного відношення між елементами деяких множин.

У розглянутих прикладах «2», «4», «і», «m» - це імена конкретних значень (певних предметів; вони називаються предметними константами), а «х», «у», «R» - імена змінних (“ х ” і “ у ” – предметні зміні, замість яких можна підставляти назви предметів із певної множини, на якій визначено даний предикат; “R” – предикатний символ (предикатна змінна)).

А зараз дамо визначення предиката в загальному випадку.

Нехай М - непорожня підмножина прямого добутку множин (n ³ 1). Зокрема, множини можуть бути рівними D₁ = D₂ =¼= D_n = D, тоді M Ì Dⁿ.

Означення. n -місним предикатом, визначеним на множині М, називається n-місна функція, визначена на М, яка приймає значення в множині висловлень.

Для n -місних предикатів використовуються позначення Р (х₁, х₂, ¼, х_n), Q (x₁, x₂, ¼, x_n) і т.д.

Якщо хочуть підкреслити, що предикат Р є n -місним, замість Р пишуть Рⁿ.

Для загальності вводиться поняття 0-місного предиката, під яким розуміють просто висловлення.

Змінні x₁, x₂, ¼, x_n називаються предметними змінними; елементи множин D₁, D₂, …, D_n, які можуть приймати ці змінні, називаються предметними константами.

Враховуючи те, що кожне висловлення є або істинним, або хибним (має значення істинності 1 або 0), то n -місний предикат, заданий на множині М, можна розглядати як функцію n аргументів, задану на множині М, яка приймає значення із множини {0,1}.

Очевидно, можна дати й таке визначення предиката: n- місним предикатом, визначеним на множині М, називається кожне однозначне відображення множини М в двоелементну множину {0, 1}.

Якщо для набору елементів висловлення Р (а₁, а₂, ¼, а_n) істинне, то будемо записувати , і якщо для набору (а₁, а₂, ¼, а_n) висловлення Р (а₁, а₂, ¼, а_n) хибне, то записуватимемо .

Як уже зазначалося, одномісні предикати виражають властивості відповідних елементів множини М, n -місні предикати (n > 1) виражають відношення між її елементами.

Наприклад, нехай Р (х) – «х -просте число», заданий на множині натуральних чисел і Q (x₁, x₂) – «х₁ > х₂», заданий на множині пар натуральних чисел. Тоді значення істинності цих предикатів при деяких значеннях предметних змінних наведено в таблицях:

х

х2 х1

Нехай М = R ´ R і Р (х, у) = «». Тоді значення істинності предиката Р (х, у) при всіх допустимих значеннях предметних змінних х і у дорівнює 1 (предикат тотожно істинний).

Аналогічно вводяться поняття тотожно хибного, виконуваного, спростовного предикатів.

Зокрема, предикат Р (х₁, х₂, ¼, х_n), заданий на множині М Ì , називається виконуваним, якщо існує такий набір предметних констант (а₁, а₂, ¼, а_n)Î М, що .

Наприклад, предикат Q (x₁, x₂) = «х₁ > х₂», заданий на множині М Ì N ´ N, є виконуваним і спростовним одночасно.

Кожному предикату відповідає певна множина (область) істинності. Множиною істинності або екстенсионалом предиката Р (х₁, х₂, ¼, х_n), заданого на множині М Ì , називають множину всіх елементів (а₁, а₂, ¼, а_n)Î М, для яких . Цю множину позначатимемо через Е_Р.

Для свого екстенсионала предикат є характеристичною функцією. Це пов’язано з тим фактом, що у предикатів є тільки два можливі значення (1 і 0). Тому, якщо відома множина всіх елементів M, на яких предикат істинний, то на всіх останніх елементах він повинен приймати значення “хибне”.

Зв’язок між типом предиката і його екстенсионалом можна подати таким чином:

предикат Р (х₁, х₂, ¼, х_n), заданий на М Ì , буде:

тотожно істинним тоді і тільки тоді, коли Е_Р = М;

тотожно хибним тоді і тільки тоді, коли Е_Р =Æ;

виконуваним тоді і тільки тоді, коли Е_Р ¹Æ;

спростовним тоді і тільки тоді, коли Е_Р ¹ М.

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

Запереченням предиката Р (х₁, х₂, ¼, х_n), заданого на множині М Ì , називається предикат, заданий на тій же множині, і який перетворюється в хибне висловлення для всіх наборів (а₁, а₂, ¼, а_n)Î Е_Р (Е_Р - екстенсионал предиката) і в хибне висловлення для всіх наборів з множини М \ Е_Р.

Заперечення предиката Р (х₁, х₂, ¼, х_n) позначається ù Р (х₁, х₂, ¼, х_n) або і читається «не Р (х₁, х₂, ¼, х_n)» або «неправильно, що Р (х₁, х₂, ¼, х_n)».

Визначення бінарних логічних операцій розпочнемо з найпростішого випадку: обидва предикати одномісні і визначені на одній і тій самій множині.

Нехай х - довільний, але фіксований елемент множини М, а Р і Q довільні предикати, задані на М. Тоді тоді і тільки тоді, коли , у решти випадках .

Аналогічно визначаються інші логічні операції.

Наприклад, кон’юнкцією одномісних предикатів Р (х)=«х -парне число» і Q (x) = «х > 5», заданих на множині натуральних чисел, є одномісний предикат P (x)Ù Q (x) = «х - парне число і х >5», заданий на N, причому тільки для тих натуральних чисел, які парні і більші ніж 5.

Кон’юнкцією одномісних предикатів Р (х) = «х - парне число» і Q (у) = «у > 5» є вже двомісний предикат P (x)Ù Q (у) = «х - парне число і у > 5». Тут хоча обидва предикати одномісні, але мають різні змінні, причому множини змінних не перетинаються.

Взагалі, кон’юнкцією n -місного і m -місного предикатів є s -місний предикат, де .

Отже, кон’юнкцією предикатів Р (х₁, х₂, ¼, х_n), заданого на М Ì , і Q (y₁, y₂, ¼, y_m), заданого на L Ì L₁ ´ L₂ ´¼´ L_m, причому

, називається n + k – місний предикат, заданий на множині , який перетворюється в істинне висловлення для всіх тих і тільки тих значень змінних, при яких істинні значення обох предикатів.

Аналогічно визначаються інші логічні операції.

Якщо Р (х₁, х₂, ¼, х_n) і Q (х₁, х₂, ¼, х_n) визначені на множині М Ì , то множинами істинності предикатів P Ù Q, P Ú Q, P ® Q, P «Q (для скорочення записів змінні опущено) відповідно будуть:

.

Тут для визначення множин істинності імплікації і еквіваленції скористалися рівносильностями

P ® Q ºù P Ú Q i P «Q º(ù P Ú Q)Ù(ù Q Ú P).

Якщо, наприклад, скористатися означеннями операцій імплікації і еквіваленції, то можна одержати для множин істинності дещо інші вирази (звичайно, вони еквівалентні попереднім). Так, за означенням імплікація P ® Q істинна завжди за виключенням випадку . Оскільки на множині E_P \ E_Q, то множиною істинності предиката P ® Q буде: M \(E_P \ E_Q).

Аналогічно отримаємо множину істинності еквіваленції. За означенням еквіваленція тоді і тільки тоді, коли або . Тому шукана множина істинності буде об’єднанням множин, що відповідає першому і другому випадку. Оскільки на множині , а на множині , то для множини істинності еквіваленції маємо: .