Алгебра висловлювань, Дискретна математика

Висловлювання та їх істинні значення. Логічні операції ∨, ∧, →, ∼, ¬. Пропозиційні операції та зв'язки. Пропозиційні формули: пропозиційні змінні та крок індукції (X ∨ Y , X ∧ Y , X → Y , ¬X). Мова та метамова. Істиннісні функції та пропозиційні формули. Твердження: кожна істинна функція відповідає деякій формулі формули.

Нагадаю, що під висловлюванням розуміється будь-яке речення, щодо якого можна сказати істинно воно чи ні, тобто. стверджувальне речення. Строго кажучи, сказане годі було розглядати як справжнє математичне визначення — лише як вказівку на тереальні об'єкти, які можуть бути ілюстрацією до точної математичної теорії. Формування речень у природній мові вказує на те, що висловлювання можуть об'єднуватися за допомогою сполучних спілок. З математичної точки зору ці спілки реалізують операції над висловлюваннями. Виділимо п'ять таких операцій:

диз'юнкція (відповідає союзу чи“);
кон'юнкція (відповідає союзу "і");
імплікація (відповідає фразі типу "якщо. то");
еквіваленція (відповідає фразі типу ". Тоді і тільки тоді", коли.);
заперечення (відповідає союзу не). ”

Перші чотири з цих операцій бінарні, остання унарна. Щодо зазначених операцій можна сказати лише, що вони формують новий вислів. При цьому, знаючи, істинні чи хибні вихідні висловлювання, можна сказати, чи є істинним новостворене висловлювання. Введені п'ять операцій ми називатимемо логічними або пропозиційними. Ми маємо справу з деякою системою алгебри, і для неї можна ввести свою математичну мову - мову алгебри висловлювань. Уцією мовою із заданого набору символів - алфавіту мови - за певними правилами складаються послідовності, які називаються словами або фразами, формулами. Алфавіт мови алгебри висловлювань складають безліч пропозиційних змінних, безліч функціональних символів (символів операцій, або логічних зв'язок) ∨, ∧, →, ~, ¬ і безліч службових символів (дві круглі дужки). Формули мови вводяться індуктивно. База індукції: пропозиційні змінні є формулами.

Крок індукції: якщо X та Y — формули, то формулами є (X ∨Y ), (X ∧Y ), (X →Y ), (X ∼ Y ), (¬X). Договоримося про такі позначення. Позначатимемо: пропозиційні змінні — малими латинськими літерами кінця алфавіту (x, y, z і т.д.); будь-які формули - великими латинськими літерами кінця алфавіту (X, Y, Z і т.д.). Як і теорії булевих функцій, для скорочення кількості дужок у формулах домовимося про такий же пріоритет операцій. Ця угода не відноситься до самої мови служить лише для зручності. У наших міркуваннях будуть зустрічатися формули, які відносяться до введеної мови, але, крім того, доведеться використовувати і додаткові позначення та символіку, щоб міркувати не в рамках мови, а про саму мову та її формули. Так, позначення змінних - це елемент мови алгебри висловлювань, а позначення формул вже виходять за межі мови.

Додаткова угода про пріоритет операцій також виходить за межі мови. У цьому випадку говорять про розширення мови або про метамову. На практиці мова та метамова тісно переплітаються, і поділити їх не просто. Слова мови алгебри висловлювань, які називаються пропозиційними формулами, — лише ланцюжки символів, складені за певними правилами. Вони отримуютьзмістовний зміст, якщо запровадити якусь інтерпретацію мови. Природна інтерпретація — ввести область зміни кожної змінної пропозиції як безліч всіх висловлювань і зіставити кожному символу відповідну логічну операцію. Тоді кожна формула визначатиме правило, яким з деякого набору вихідних висловлювань, позначених змінними, ми отримаємо нове висловлювання. Сама підстановка замість змінних конкретних висловлювань вже виходить за рамки мови, що розглядається. Зазначимо, що формули алгебри висловлювань мають інші інтерпретації. Наприклад, пропозиційні змінні можна розглядати як булеві змінні, а функціональні символи пов'язати з відповідними булевими операціями. Така інтерпретація дозволяє отримати, виходячи з істинності висловлювань, істинність складного висловлювання. Формула визначатиме булеву функцію, яку називають істиннісною функцією. Саме істиннісні функції слід розглядати як головну мету вивчення в алгебрі висловлювань, оскільки вона дозволяє судити про істинність складних, заплутаних висловлювань.

Теорема2.1. Кожна булева функція є істиннісною функцією деякої формули алгебри висловлювань.

◀ Мова алгебри висловлювань збігається з мовою булевої алгебри, побудованою на множині та з п'яти булевих функцій ∨, ∧, →, ∼, ¬. Оскільки це безліч містить стандартний базис B і, отже, повно, будь-яка булева функція може бути представлена формулою над заданим безліччю. Цю формулу можна як формулу алгебри висловлювань. При цьому функція булева буде істиннісною функцією зазначеної формули. ▶