2. Формули алгебри висловлень. Таблиця істинності формули.

За допомогою розглянутих логічних зв ’язок (операцій) з простих висловлень можна будувати складені. Якщо висловлення міститю хоча б одну логічну зв’язку, то воно називається складеним. Висловлення, які не містять логічних зв’язок називають елементарними чи атомарними. У логіці висловлень елементарні висловлення розглядаються як неподільні цілі, внутрішня структура їх не аналізується (це робиться в логіці предикатів). Використовуючи символи простих (атомарних) висловлень, логічних операцій та дужки можна як і в звичайній алгебрі за допомогою символів +, - та дужок будувати досить складні логічні вирази (формули). Ці вирази відображатимуть логічну структуру відповідних складених висловлень. Щоб проаналізувати на істинність чи хибність деяке висловлення, досить проаналізувати відповідну йому логічну формулу. У логіці висловлень розроблені формальні методи, які дозволяють досліджувати формули на предмет істинності чи хибності.

Термін формула логіки висловлень або логічна формула застосовується до виразів, побудованих з пропозиційних букв за

допомогою пропозиційних зв’язок. Точніше означення формули таке:

1. Будь - яка пропозиційна буква (велика буква латинського алфавіту або така ж буква з числовим індексом) є формулою логіки висловлень.

2. Якщо A і B – формули логіки висловлень, то (A^B), (˥A), (˥B), (AᴠB), (A→B), (A↔B)також формули логіки висловлень.

3. Інших формул логіки висловлень, крім зазначених у пп. 1 і 2, немає.

Замість «формула логіки висловлень» часто говоритимемо просто «формула». Зазначимо, що пропозиційні букви (вони на основі п.1 є формулами) називаються простими або елементарними, або атомарними формулами.

Синтаксис формул можна також визначити, скориставшись нотацією Бекуса - Наура (БНФ - бекусівська нормальна форма):

Т ут кожне ім’я в кутових дужках - це тип об’єкта.

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

Починаючи з об’єкта <атом> (атомарної формули), можна отримати об’єкти типу <формула >, застосовуючи заперечення або одну з операцій (означення < ОП >) і комбінуючи атом з іншою формулою. Наприклад, формулами будують вирази : (˥B), (BᴠC),(B^C→D).

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

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

1) зовнішні дужки в записі формули опускаються;

2) логічним операціям приписують певний ранг, згідно якого операції в дужках або при їх відсутності виконуються в такому порядку: ˥,^,ᴠ,→,↔.

Нехай, наприклад, задано формулу ɑ(A₁,A_2,…,A_n), в яку входять пропозиційні змінні A₁,A_2,…,A_n.. Неважко знайти значення істинності формули за значеннями істинності пропозиційних змінних. Отже, значення істинності формули можна встановити з врахуванням конкретної інтерпретації. Інтерпретація формули полягає в присвоюванні значень істинності кожному атомарному висловленню, яке входить у формулу. Значення істинності формули при одній інтерпретації може бути 1, при іншій – 0 .

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

Так, для формули A→˥B↔A таблиця істинності матиме вигляд:

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

Таблиця істинності формули ɑ(A₁,A_2,…,A_n), містить 2ⁿ рядків (кожна пропозиційна змінна незалежно від інших може набувати одного з двох значень: 0 або 1 , тобто число всіх можливих різних наборів значень пропозиційних змінних (аргументів) є 2ⁿ ). Таблицю зручно заповнювати так: у стовпчик, що відповідає останній пропозиційній змінній, вписати послідовно пари 0 1 , в той, що відповідає передостанній змінній, - четвірки 0011 , в наступний - вісімки 00001111 і т. д. У першому стовпчику, очевидно, буде записано:

При цьому розподіл нулів і одиниць в кожному рядку задаватиме двійковий запис номера рядка (0-й, 1-й, ... , ( 2ⁿ-1)-й).

Зазначимо також, що кожна формула ɑ(A₁,A_2,…,A_n), визначає певну n-місну булеву функцію, яка є функцією значень істинності цієї формули, а таблиця істинності є табличним заданням цієї функції.