Материал: discrete_mathematics

Знаючи, як виконуються окремі операції предикатів, можна утворювати вирази або формули, операндами яких є предикати.

Наприклад, формула P1(x) (← P3(x, z) → P2(y, x, z)) задає деякий предикат Q(x, y, z). Значення предиката Q неважко обчис-

лити для будь-якого набору значень його змінних x, y, z, виходячи зі значень предикатів P1, P2, P3 на цьому наборі.

Додатково в логіці предикатів використовують дві спеціальні операції предикатів, які називають кванторами. Ці операції роблять теорію предикатів значно гнучкішою, глибшою й багатшою, ніж теорія висловлень. Саме тому логіку предикатів іноді називають теорією квантифікації.

Найпопулярнішими й найуживанішими виразами в математиці є фрази або формулювання типу для всіх та існує. Вони входять до більшості математичних міркувань і доведень, висновків, лем і теорем. Наприклад: Для всіх дійсних чисел x вико-

нується рівність sіn2x + cos2x = 1; Для заданих натуральних a та b завжди існує натуральне число d, яке ділить числа a та b; Для всіх натуральних n справедливе твердження: якщо n ділиться на 6 і на 15, то n ділиться на 30 тощо.

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

Нехай P(x) – предикат на множині M. Тоді квантор загаль ності (із параметром x) – це операція, що ставить у відповідність P(x) висловлення для всіх x із M P(x) істинне; для позначення цієї операції використовують знак , записують xP(x) (чита-

ють для всіх x P від x).

Іншу операцію називають квантором існування та позначають її знаком . Якщо Q(x) – деякий предикат на множині M, то висловлення існує в множині M елемент x такий, що Q(x) іс-

тинне записують у вигляді xQ(x) і читають існує такий x, що Q

від x або є такий x, що Q від x.

Походження обраних позначень пояснюється тим, що символ– це перевернута велика перша літера німецького слова alle або англійського слова all, що перекладають як усі. А символ відповідає першій літері слів exіstіeren (нім.) або exіst (англ.)

– існувати.

61

Вираз x читають також як усі x; для кожного x; для довільного x; для будь-якого x; а вираз x – як деякий x; для деякого x; знайдеться такий x тощо.

Зазначимо, що, крім уведених символічних позначень кванторів, використовують також інші позначення. Наприклад, за-

мість x іноді пишуть (x), (x) або x, а замість x – відповідно

(x), (Ex) або x.

Приклад 1.19.

1. Розглянемо два бінарні предикати на множині натуральних чисел N: предикат x менше y та предикат x ділить y. Перший із них записуватиме у традиційній формі x < y, а другий – у вигляді x | y. Тоді неважко переконатись, що висловлення:

x y(x < y) та x y(x | y) є істинними,y x(x < y) та y x(x | y) є хибними.

Істинними будуть, наприклад, висловлення

x(0 < x2 – x + 1),x((x | 1) (← (1 < x))),

x((x < 1) → (x < 2)),

x(((2 | x) (3 | x)) → (6 | x)),

а хибними –

x(2| x), x(x2 < 0), x((3 | x) → (6 | x)).

2.Записати формулою логіки предикатів такі твердження: (а) Існує таке x, що P(x) – хибне;

(б) Існує таке x, що P(x) – хибне. (а) x(← P(x)); (б) ← xP(x).

3.У цій вправі предметна область є множиною R дійсних чисел. Визначити, чи є даний вираз висловленням або пропозиційною формою. У першому випадку вказати, істинним чи хибним

євисловлення; у другому – здійснити квантифікацію так, щоб одержати істинне висловлення:

(а) y (x < y); (б) x y z (xy = z).

Розглянемо (а). Це пропозиційна форма. Перетворити її на істинне висловлення можна, наприклад, так:

x y (x < y) (або x y (x < y)).

Розглянемо (б). Це істинне висловлення. У ньому виражено твердження, що для будь-яких дійсних чисел x та y існує дійсне число z, яке є їхнім добутком. ◄

62

Важливу роль у логіці предикатів відіграє поняття області дії квантора у заданій формулі, під якою розумітимемо той вираз (підформулу), до якого належить квантор. Область дії квантора позначають за допомогою дужок. Ліва дужка, що відповідає початку області дії, записується безпосередньо після кванторної змінної даного квантора, а відповідна до неї права дужка означає закінчення області дії цього квантора. Там, де це не викликає невизначеності, дужки можна опускати й замість x(P(x)) або x(P(x)) писати відповідно xP(x) або xP(x). Це означає, що операції квантифікації мають більший пріоритет, ніж логічні операції.

Приклад 1.20. В усіх нижченаведених кванторних виразах область дії квантора підкреслено:

x((3 | x) → (6 | x)), x(3 | x) → (6 | x),x((x2 < 9) → (x < 3)), x(x2 < 9) → (x < 3).

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

Розглянемо на універсальній множині R дійсних чисел вирази: x2 < 10 та x(x2 < 10).

Перший із них є предикатом, що залежить від змінної x. Замість x до нього можна підставляти різні дійсні значення й отримувати певні висловлення (істинні чи хибні). Та сама предметна змінна x входить до другого виразу інакше. Якщо замість неї підставити будь-яке дійсне значення, то дістанемо беззмістовний вираз.

Нехай P(x) – деякий предикат на M. Перехід від P(x) доxP(x) або xP(x) називають зв'язуванням змінної x. Інші назви

– навішування квантора на змінну x у предикаті P(x) (або на предикат P(x)), квантифікацією змінної x. Змінну x, на яку навішено квантор, називають зв'язаною, інакше змінну x назива-

ють вільною.

Зауважимо, що така ситуація не виняткова й доволі часто зустрічається в інших розділах математики. Наприклад, у виразах

Неважко переконатися, що перестановка однакових кванторів зумовлює рівносильні висловлення. Дійсно, обидва висловлення x( yA(x, y)) і y( xA(x, y)) істинні тоді й тільки тоді, коли предикат A(x, y) набуває значення 1 на всіх кортежах значень (a, b) з M 2. Висловлення x( y A(x, y)) і y( x A(x, y)) істинні тоді й тільки тоді, коли існує принаймні одна пара (a, b) така,

що A(a, b) = 1.

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

Висловлення x( yA(x, y)) і y( xA(x, y)) нерівносильні. Наприклад, у термінах табличного задання предиката A(x, y) істинність першого висловлення x( yA(x, y)) означає, що кожен рядок таблиці істинності містить принаймні одну одиницю. Друге ж висловлення y( xA(x, y)) істинне тоді й лише тоді, коли в таблиці є стовпчик, що складається тільки з одиниць. ◄

Неважко поширити всі наведені вище міркування й висновки на предикати більшої арності. Навішування одного квантора завжди зменшує кількість вільних змінних і арність предиката на одиницю. Застосування кванторів до всіх змінних предиката перетворює його на висловлення (іноді таку предикатну формулу називають замкненою).

Зауваження. Треба звернути увагу на те, що термін "предикат" має різні тлумачення в лінгвістичному та математичному контекстах. У лінгвістичному (синтаксичному) контексті він тлумачиться як присудок-властивість у певному реченні; математичне (семантичне) тлумачення (яке є абстракцією від лінгвістичного) полягає в тому, що термін предикат визначається як функція в множину булевих значень, яка задана на множині предметних значень (це питання буде розглянуто детальніше в останньому розділі посібника).

Завдання для самостійної роботи

1. Записати формулою логіки предикатів таке твердження:

Для кожного x P(x) – хибне; P(x) – хибне для кожного x.

65