Тема 5.5. Логіка предикатів

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

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

Вихід за межі логіки висловлень здійснюється в логіці предикатів.

Внутрішню структуру висловлення тут називають суб’єктно-предикатною. Суб’єкт – назва предмету, а предикат – назва властивості предмету чи відношення між предметами.

Суб’єктно-предикатну структуру висловлення виражають відповідною символікою. Вихідним пунктом тут є поняття предиката. Для символічного позначення предиката вживають великі латинські літери, а для позначення суб’єктів – малі.

Наприклад, висловлення “3 – просте число” можна записати як А(11), а “Ігор вищий від Юрія” – С(i, j).

Отже, А(х) означає, що х – просте число, а С(x, y) – що х вищий за у. У розглянутих прикладах 11, i, j – предметні константи, а х та у – предметні змінні.

Вираз, яким записано предикат – це висловлювальна форма.

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

Одномісні виражають властивості відповідних елементів універсальної множини.

Наприклад, обравши за універсальну множину натуральних чисел для предиката А(х) (х – просте число), одержимо: А(1)=0, А(2)=1, А(3)=1, А(4)=0, А(5)=1, А(6)=0,...

п-місні предикати при п>1 виражають відношення між елементами універсальної множини. Наприклад, “4 ділить х” на множині натуральних чисел означає кратність х четвірці.

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

Задати предикат можна за допомогою таблиці. Наприклад, для згадуваного предиката А(х) (х – просте число), таблиця матиме вигляд:

х	1	2	3	4	5	6	7	8	9	10	...
А(х)	0	1	1	0	1	0	1	0	0	0	...

У загальному випадку для п-місного предиката, означеного на множині з т елементів, кількість елементів таблиці обчислюють за формулою кількості розміщень з повтореннями :

.

Тоді кількість різних п-місних логічних функцій (предикатів) на т-елементній універсальній множині становитиме кількість розміщень з повтореннями з двох елементів (0,1) по т^п: .

Отже, застосування таблиць для зображення предикатів обмежене невеликими значеннями т і п.

Предикат називають тотожно істинним або загальнозначущим, якщо при всіх допустимих значеннях змінних він набуває лише істинісних значень.

Наприклад, ;

.

Оскільки значеннями предикатів є висловлення, то над предикатами можна виконувати такі логічні операції: , , , , . Означимо їх.

Нехай х – довільний, але зафіксований елемент універсальної множини Е, P і Q – позначення довільних предикатів, заданих на Е.

тоді і тільки тоді, коли і , в інших випадках .

тоді і тільки тоді, коли і , в інших випадках .

тоді і тільки тоді, коли і навпаки.

тоді і тільки тоді, коли і , в інших випадках .

тоді і тільки тоді, коли , в інших випадках .

Предикатам і логічним операціям над ними надають теоретико-множинного змісту.

Предикат – це підмножина універсальної множини Е, а саме та, на якій істиннісне значення предиката тотожно дорівнює 1 – множина істинності предиката.

Кон’юнкції предикатів відповідає переріз тих підмножин , які відповідають предикатам P і Q окремо: .

Диз’юнкції предикатів відповідає об’єднання підмножин .

Запереченню предиката відповідає доповнення до підмножини .

Теоретико-множинний зміст  та  випливає з того, що їх можна подати через  і .

Наочно це зображують на діаграмах Ейлера-Венна (згаданих у розділі 1):

PQ – область ІІ;

PQ – області І, ІІ і ІІІ;

– області ІІІ і IV;

PQ – області ІІ, III i IV;

PQ – області ІІ i IV.

Аналогічну картину матимемо і для 3-х предикатів, де універсальну множину Е розбивають на 2³=8 частин.

У випадку 4-х предикатів універсальну множину Е розбивають на 2⁴=16 частин, замінюючи круги еліпсами.