Елементи логіки

Той факт, що формула B є логічним висновком формул AB і A, відіграє в математиці дуже важливу роль. Він дозволяє з уже відомих істинних тверджень AB і A одержати нове істинне твердження B. Зауважимо, що такий спосіб одержання, або виведення нових тверджень у математичній логіці є одним із основних. Таке виведення задається спеціальним правилом виведення, яке має вигляд і назву modus ponens (правило відокремлення). Воно дозволяє одержати висновок B твердження AB як окреме висловлення, тобто відокремити його вид засновку A. У математичній логіці існують і інші правила виведення, але тут ми їх не розглядаємо.

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

Другий спосіб одержання нових істинних висловлень полягає в застосуванні згаданих правил виведення до вже відомих істинних висловлень. При цьому формулюється система висловлень-тавтологій, що складає основу для виведення інших. Вони називаються аксіомами, а висловлення, що виводяться, – теоремами. Прикладом аксіоми може служити висловлення AA, яке називається законом виключеного третього. Такий спосіб породження висловлень називається численням висловлень.

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

5. Неформальне знайомство з кванторами

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

Кожна людина смертна.

Сократ – людина.

Звідси випливає, що Сократ смертний.

Очевидно, що висловлення "Сократ смертний" не є логічним висновком засновків "Кожна людина смертна" і "Сократ – людина". Проте коректність наведених міркувань ні в кого не викликає сумніву. Очевидно, що вона зумовлена якимсь особливим змістом слова "кожна".

Введемо додаткові позначення. Нехай x позначає деяку змінну, значення якої можуть мати деяку властивість P. Такі змінні називаються предметними. Висловлення "x має властивість P" позначимо P(x). Наприклад, висловлення "Ціле число x є парним" позначимо E(x). Значення такого висловлення залежить від значення цієї змінної. При x=1 висловлення E(x) хибне, при x=2 – істинне. Замість літери x можна записати її значення, наприклад, E(2).

Речення "Кожне значення x має властивість P", або "Всі значення x мають властивість P", або "Всі x мають властивість P", або "При всіх x справджується властивість P" позначимо записом x P(x). У цьому записі частина x називається квантором загальності. Слово "квантор" походить від слова "квантифікація", що означає "кількісне вираження". Продовжуючи приклад про парні числа, зауважимо, що твердження x E(x) є хибним.

Речення "Існує значення x, що має властивість P", або "Деякі значення x мають властивість P", або "При деякому значенні x справджується властивість P", або "Деякі x мають властивість P" позначимо записом x P(x). У цьому записі частина x називається квантором існування. Очевидно, що у прикладі про парні числа твердження x E(x) є істинним.

Очевидно, що

x P(x)  x P(x),