Розділ математичної логіки
Алгебра логіки - розділ математичної логіки, що вивчає будову складних логічних висловлень і способи встановлення їхньої істинності за допомогою алгебраїчних методів. Щоб зрозуміти сутність алгебраїчного підходу до логіки, згадаємо звичайну шкільну алгебру, яку можна назвати алгеброю арифметики. Основні її об'єкти - формули, що складаються з букв, знаків арифметичних операцій і дужок. Букви позначають змінні, які можуть приймати числові значення. З формулами роблять процедури двох видів: обчислення й перетворення. Обчислення формули полягає в тім, що замість букв підставляються числа; знаки вказують дії, а дужки - у якому порядку ці дії з підставленими числами треба виконати. Кожна формула задає деяку арифметичну функцію; число аргументів (змінних) цієї функції дорівнює числу різних букв у формулі. Безліч різних формул і функцій, що задають ними, нескінченно; однак всі вони будуються за допомогою невеликого числа елементарних функцій, називаних арифметичними операціями - додавання, множення й т.д. Перетворення формули полягає в тім, що вихідна формула F1 або її частина заміняється іншою формулою, у результаті чого виходить нова формула F2, що еквівалентна F1 у наступному змісті: формули F1 й F2 задають ту саму функцію, т. е. при будь-яких значеннях змінні обчислення F1 й F2 дають той самий результат. Перетворення формул виробляються на підставі законів арифметики (асоціативного, комутативного й дистрибутивного законів, рівності а - а = 0 й ін.), а також отриманих з них співвідношень типу
.
і т.ін.
На аналогічних принципах будується й алгебра логіки. Різниця полягає в наступному. У формулах алгебри логіки змінні є логічними або двійковими, тобто приймають тільки два значення - "неправда" й "істина", які позначаються або 0 й 1, або Л и П, або false й trие. Знаки операцій позначають логічні операції (логічні зв'язування). Кожна формула задає логічну функцію: функцію від логічних змінних, котра сама може приймати тільки два логічних значення. Будь-яку логічну функцію f(x1, ..., хn) можна задати таблицею, у лівій частині якої виписані всі можливі набори значень її аргументів х1, ..., хп, а права частина
являє собою стовпець значень функції, що відповідають цим наборам(таблиця 1).
Таблиця 1 - Вигляд таблиці для логічних функцій
х1, ..., хп, | f(x1,..., хn) |
Значення аргумента | Значення функції (0 или 1) |
Число рядків у такій таблиці дорівнює 
- числу можливих наборів значень аргументів, тобто числу різних комбінацій довжини п з нулів й одиниць. Число різних функцій п змінних дорівнює 
- числу можливих розміщень нулів й одиниць у стовпці з рядками. Таблиця функції f(х) один змінної містить усього два рядки, а самих функцій
- 
=4
Таблиця 2 - Константа 0
x | f(x) |
0 1 | 0 0 |
Таблиця 3 - Повторення
x | f(x) |
0 1 | 0 1 |
Таблиця 4 - Заперечення
x | f(x) |
0 1 | 1 0 |
Таблиця 5 - Константа 1
x | F(x) |
0 1 | 1 1 |
Таблиця функції f(х1,х2) двох змінних містить чотири рядки, а самих функцій двох змінних - шістнадцять (
=
=16). Укажемо найбільш важливі з них. П'ять функцій відповідають логічним зв'язуванням.
Таблиця 6 - Диз'юнкція (або)
x1 | x2 | x1Vx2 |
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 1 |
Таблиця 7 - Кон'юнкція (і)
x1 | x2 | x1 & x2 |
0 | 0 | 0 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
Таблиця 8 - Імплікація
x1 | x2 | x1 -> x2 |
0 | 0 | 1 |
0 | 1 | 1 |
1 | 0 | 0 |
1 | 1 | 1 |
Таблиця 9 - Еквівалентність (рівнозначність)
x1 | x2 | x1 ` x2 |
0 | 0 | 1 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
Таблиця 10 - Нерівнозначність (додавання за модулем 2)
x1 | x2 |
|
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
Крім того,часто використовуються ще дві функції двох змінних.
Таблиця 11 - Штріх Шеффера (не і)
x1 | x2 | x1 | x2 |
0 | 0 | 1 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
Таблиця 12 - Стрілка Пірса (не або)
x1 | x2 |
|
0 | 0 | 1 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 0 |
