§15. Предикати та квантори

Предикатом називається функціональне висловлювання. Логіка предикатів – це розширення логіки висловлювань за рахунок використання предикатів в ролі логічних функцій.

Нехай маємо ряд простих висловлювань:

{1 ділиться на 5}

{2 ділиться на 5}

{3 ділиться на 5}

{50 ділиться на 5}.

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

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

Предикат називається тотожно істинним (тотожно хибним), якщо на всіх наборах своїх змінних він приймає значення 1 (0).

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

Навішуючи квантори перед предикатами, ми їх або посилюємо , або послаблюємо .

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

Якщо предикат такий, що , то:

,

.

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

Для будь-якого предиката справедливі формули:

,

.

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

Розв’язання. За властивостями предикатів, які визначені на скінченних множинах, маємо:

§16. Методи доведень

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

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

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

3. Метод «від супротивного». Припустивши, що висловлювання істинне, а хибне, використовуючи аргументоване судження, отримуємо протиріччя. Цей спосіб знову-таки оснований на тому, що імплікація приймає хибне значення тільки тоді, коли істинне, а хибне.

§17. Метод математичної індукції

В багатьох розділах арифметики, алгебри, геометрії, аналізу потрібно доводити істинність тверджень , які залежать від натуральної змінної.

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

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

1. Твердження істинне для .

2. З припущення, що істинне для (де – будь-яке натуральне число), випливає, що воно істинне і для наступного значення .

Цей принцип називається принципом математичної індукції.

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

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

Приклад 22. Методом математичної індукції довести, що рівність , справедлива для всі N.

Розв’язання. У випадку отримаємо . Отже, при рівність виконується.

Тепер припустимо, що рівність виконується для будь-якого натурального числа . Тоді:

.

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

Приклад 23. Методом математичної індукції довести, що число ділиться на 6 при будь-якому натуральному .

Розв’язання. При отримаємо ділиться на 6. Припустимо, що число ділиться на 6 для будь-якого натурального числа . Тоді:

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

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