Основні положення алгебри логіки були сформульовані англійським математиком та філософом Джорджем Булем(1815-1864) (рис. 2.44). У 1854 році вийшла його основна праця «Дослідження законів думки, на яких засновані математичні теорії логіки й імовірності». Ця книга нині зараховується до математичної класики. У ній досліджується система алгебри, яку сьогодні називають «алгеброю висловлень» або «булевою логікою». Булева логіка стала основним математичним інструментом для створення комп’ютерів.
В алгебрі логіки використовується поняттялогічна змінна.
Запам’ятайте!
Логічна змінна – це змінна, яка може набувати лише значень true або false.
Завданням алгебри логіки є визначення істинності логічних виразів– виразів, що складаються з логічних констант, логічних змінних, логічних операцій, дужок, наприклад,`(A \/ B ) /\ (A \/ В).
Зрозуміло, що значенням логічного виразу може бути лише trueабоfalse.
Для логічних операцій, розглянутих вище, визначений такий пріоритет операцій: заперечення, кон’юнкція, диз’юнкція. Для змінення цього порядку виконання логічних операцій використовують дужки.
Для обчислення значення істинності логічного виразу можна використати таблиці істинності.
Для складання та заповнення таблиці істинності потрібно:
1. Обчислити кількість можливих наборів значень логічних змінних. Якщо формула містить n різнихлогічних змінних, то можливих наборів значень цих змінних буде 2n . Це число визначає кількість рядків у таблиці істинності.
2. Обчислити кількість логічних операцій у логічному виразі. Ця кількість плюс кількість логічних змінних визначає кількість стовпців таблиці.
3. Заповнити перші n стовпців усіма можливими наборами значень логічних змінних.
4. Заповнити кожний наступний стовпець значеннями, отриманими при виконанні чергової логічної операції. Черговість встановлюється згідно названого пріоритету операцій.
В останньому стовпці таблиці будуть отримані усі можливі значення істинності заданого логічного виразу.
Наприклад, вираз `A \/ B /\ A містить дві логічні змінні, тобто n=2. Значить, усього існує 4 набори можливих значень цих змінних (2n = 22 =4). Вираз містить 3 логічні операції: заперечення, диз’юнкція і кон’юнкція. Таким чином, таблиця істинності буде складатися з 4 рядків та 5 стовпців. Першою згідно пріоритету буде виконуватись операція заперечення, другою – кон’юнкція, останньою – диз’юнкція, в якій потрібно використовувати результати перших двох операцій.
Отримаємо таку таблицю істинності:
| А
| В
|
|
|
|
| `A
| B /\ A
| (`A) (B /\ A)
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Аналізуючи останній стовпець таблиці істинності, робимо висновок, що вираз буде мати значення false лише у випадку, коли логічні змінні мають такі значення: А = true, B = false. У всіх інших випадках значенням логічного виразу буде true.
Запам’ятайте!
Два логічні вирази називаються рівними, якщо вони набувають однакових значень при одних і тих самих наборах значень логічних змінних, що входять до цих виразів.
Рівність двох логічних виразів утворюють логічну формулу.
Наведемо кілька цікавих і корисних логічних формул:
1. 
– формула подвійного заперечення
2. А \/ А = А – формула поглинання
3. 
= 
– формула заперечення диз’юнкції (закон де Моргана)
Для доведення цих рівностей можна скласти і порівняти таблиці істинності логічних виразів у правій і лівій частинах. Пропонуємо вам зробити це самостійно.
Цікаві факти з історії
Аугустус де Морган (1806 - 1871) (рис. 2.45) – шотландський математик і логік, професор математики Лонднського університетського коледжу, перший президент Лондонського математичного товариства. Результати своїх досліджень з логіки одержав незалежно від Джорджа Буля і виклав у 1847 році.
