Обчислення логічних формул
Значення будь-якої логічної формули, що містить знаки цих функцій, на заданому наборі значень змінних можна обчислити, використовуючи ці таблиці. Нехай, наприклад, функція f(х1,х2,х3) трьох змінних задана формулою(1).
(1)
Обчислимо цю функцію на наборі x1 = 1, х2 = 1, x3=0. (Логічно це значить: визначимо значення істинності складного висловлення (1) за умови, що складові його прості висловлення х1 і х2 істинни, а х3 - ложно.) Підстановка значень у формулу (1) дає 0.
Обчисливши цю формулу на інших 7 наборах значень х1, х2, х3, повністю відновимо таблицю цієї функції.
Таблиця 13 - Значення функції
х1 | х2 | х3 | f(х1,х2,х3) |
0 | 0 | 0 | 0 |
0 | 0 | 1 | 0 |
0 | 1 | 0 | 0 |
0 | 1 | 1 | 0 |
1 | 0 | 0 | 1 |
1 | 0 | 1 | 1 |
1 | 1 | 0 | 0 |
1 | 1 | 1 | 1 |
Таким чином, від функції, заданої у вигляді формули (вираження), завжди можна перейти до табличного завдання. Відповідь на зворотне питання: чи завжди від таблиці функції можна перейти до формули - не настільки однозначна і залежить від того, які операції передбачається використати у формулах. Формула, що задає функцію, фактично визначає її через набір інших функцій, які обрані в якості вихідних і позначені знаками операцій. (У формулі (1) операціями є конъюнкция, диз'юнкція, заперечення й імплікація.). Існують набори логічних функцій, за допомогою яких можна виразити будь-які інші логічні функції. Такі набори називаються функціонально повними наборами або базисами. Найбільш відомий і вивчений базис - набір "И", "АБО", "НЕ" (конъюнкция, диз'юнкція, заперечення). Безліч всіх логічних функцій, на якій визначені ці три операції, називається булевой алгеброю; операції й формули булевой алгебри також часто називають булевими. Функціональна повнота булевой алгебри означає, що перехід від табличного завдання до булевой формули завжди можливий. Метод переходу полягає в наступному: для кожного набору значень змінних х1,...,хn на якому функція f(х1, ..., хn) дорівнює 1, виписується кон'юнкцiя всіх змінних; над тими змінними, які в цьому наборі рівні 0, ставляться заперечення; усі такі кон'юнкції з'єднуються знаками диз'юнкції. Отримана формула називається зробленою диз'юнктивною нормальною формою (ЗДНФ) логічної функції f(x1, ..., хn). ЗДНФ для кожної функції єдина, як говорять в математиці, з точністю до перестановок змінних або кон'юнкцій. Це означає, що дві різні СДНФ однієї функції можуть відрізнятися тільки порядком коніюнкцій і розміщенням змінних у кон'юнкцiях. Для функції, заданої вище, ЗДНФ має вигляд:
, (2)
а для імплікації
. (3)
При написанні формул булевой алгебри з кон'юнкцією прийнято звертатися так само, як у звичайній алгебрі - із множенням: знак кон'юнкції й дужки, її навколишні, опускаються. ЗДНФ звичайно досить громіздка формула. Спрощення формул у булевой алгебрі (як й у будь-якій іншій алгебрі) виконується на основі еквівалентних перетворень, що опираються на основні закони (еквівалентні співвідношення), які в кожній алгебрі - свої. У булевой алгебрі ці закони - наступні.
1. Асоциативність диз'юнкції й кон'юнкції:
;
.
2. Комутативність диз'юнкції й кон'юнкції:
;
.
3. Дистрибутивність кон'юнкції щодо диз'юнкції:
.
4. Дистрибутивність диз'юнкції відносно кон'юнкції:
).
5. Ідемпотентність (відсутність ступенів і коефіцієнтів) :
; 
.
6. Закон подвійного заперечення:
.
7. Властивості констант 0 й 1:
;
;
;
;
8. Правила де Моргана:
;
.
 | (1) |
9. Закон протиріччя:
.
10. Закон виключеного третього:
.
Закони 1, 2, 3, 7 показують, що властивості кон'юнкції дуже схожі на властивості множення; тому її часто називають логічним множенням. Із законів 6 й 8 слідує, що, використовуючи заперечення, диз'юнкцію можна виразити через кон'юнкцiю, і навпаки:
;
.
Це означає, що набори {І, НЕ} й {АБО, НЕ} також є функціонально повними. Еквівалентні співвідношення, тобто дві формули, з'єднані знаком рівняння, - це твердження про те, що дані формули виражають ту саму функцію, тобто при будь-яких значеннях, що входять у них змінних, приймають рівні значення. Оскільки число різних наборів значень логічних змінних кінцево, еквівалентні співвідношення алгебри логіки можна доводити, перебравши всі ці набори (тобто власне кажучи побудувати таблиці функцій для лівої й правої формул і переконатися, що вони збігаються). Такий спосіб доказу громіздкий; однак без нього не можна обійтися тільки при доказі основних законів (1 - 10). Інші співвідношення, які часто застосовуються в перетвореннях булевих формул, простіше виводити за допомогою основних законів. Приведемо три найпоширеніші співвідношення.
1. Поглинання:
.
2. Склеювання:
.
.
Наприклад, співвідношення перше виводиться з основних законів у такий спосіб (послідовно використаються закони 7, 3, 7, 7):
.
У свою чергу, використовуючи основні закони й співвідношення (4) - (6), можна помітно спростити формули:
;
.