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

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

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

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

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

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

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

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

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

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

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

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

Існує поняття 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 частин, замінюючи круги еліпсами.

5.4.2. Квантифікація предикатів. Квантор існування і квантор загальності

Крім операцій алгебри висловлень над предикатами виконують ще 2 логічні операції, які називають кванторами.

Розглянемо два висловлення:

р = “існує х, що х>3” і q = “х>3 для деякого х”.

Вони істинні, рівносильні між собою, відрізняються лише побудовою речення, що з погляду алгебри логіки не так вже й істотно. Логічна структура їх визначається виразами “існує» і “для деякого”. Символічно цей вираз записують так:

($х).Р(х) або ($х)[Р(х)].

Читають: “існує таке х, що Р(х)”.

Наприклад, наведене висловлення р можна записати так:

($х). х>3 або ($х)[х>3].

Символ $ називають квантором існування. Записуючи квантор перед предикатом, здійснюють квантифікацію предиката. Очевидно, висловлення ($х).Р(х) істинне тоді і тільки тоді, коли існує принаймні одне значення а змінної х, при якому Р(а)º1.

Можна здійснювати повторну квантифікацію виразу, що містить більше, ніж одну змінну:

($х)($y)[х+у=2] – тут спочатку квантифікують предикат за змінною х, а потім – за у;

($у)($х)[х+у=2] – тут квантифікують спочатку за змінною у, а потім – за х.

У даному випадку порядок здійснення квантифікації – неістотний.

Іноді при застосування квантора існування вказують, що значення змінної беруть з деякої множини або накладають умову:

($хÎМ).Р(х) або ($х).(хÎМ)ÙР(х),

($х>a).Р(х) або ($х).(х>a)ÙР(х).

Деколи доцільно підкреслити, що існує єдиний елемент хÎА такий, що Р(х). Для цього використовують такі позначення:

($₁хÎА).Р(х) або ($!хÎА).Р(х).

Розглянемо висловлення:

s = ”при будь-якому х: х²–х+1>0”;

r = ”при кожному х: х²–х+1>0”;

t = ”для довільного х: х²–х+1>0”.

Замість цих фраз записують:

("х).Р(х) або ("х)[Р(х)].

Для наведених висловлень: ("х).(х²–х+1>0) або ("х)[ х²–х+1>0].

Символ " (початкова буква від англ. All перевернута) називають квантором загальності.

Квантифікація при цьому п-місного предиката дає (п–1)-місний предикат, а одномісного – дає нуль-місний предикат, тобто висловлення.

Порядок повторного застосування квантора загальності не має значення:

("х)("у).Р(х,у)= ("у) ("х).Р(х,у).

Квантори існування і загальності можна по-черзі застосувати до предиката. Проте тут порядок квантифікації має істотне значення. Наприклад,

Р(х,у) = “х+у=2”, х, у Î R.

Р= ("у)($х) [х+у=2] – при довільному дійсному у існує таке х, що х+у=2. |P|=1;

Q= ($х)("у) [х+у=2] – існує таке х, що при довільному дійсному у х+у=2. |Q|=0.

Отже, у загальному випадку ("у)($х). Р(х,у) ¹ ($х)("у). Р(х,у).

Принцип заперечення. Щоб дістати заперечення предиката (зокрема висловлення), який містить квантори існування та загальності, досить змінити квантори загальності на квантори існування і навпаки, а замість предиката взяти його заперечення.