Основні поняття та закони бульової алгебри

У зв’язку з двійковим зображенням цифрових сигналів, що набувають тільки двох значень (0 і 1), найзручнішим математичним апаратом для аналізу та синтезу цифрових систем є алгебра логіки (бульова алгебра). У бульовій алгебрі символи 0 і 1 характеризують стани змінних та їх функцій і тому не можна розглядати ці символи як арифметичні числа. Алгебра логіки – це алгебра станів, а не алгебра чисел, і їй властиві на відміну від звичайної алгебри логічні дії над станами.

Основне поняття алгебри логіки – висловлення, тобто речення, в якому міститься суть (сенс) твердження істинності або його заперечення (хибності). Будь-яке висловлення можна позначити символом, наприклад, або , і вважати, що або , якщо висловлення істинне, а або , якщо висловлення неістинне (хибне). Оскільки будь-яка змінна (або її функція) може мати стан 0 або 1, в алгебрі логіки кожній двійковій змінній ставиться у відповідність обернена до неї (інверсна) змінна, така, що якщо , то , а якщо , то . Подвійне заперечення дав аргумент, тобто . Риска “–” над змінною означає, що над змінною здійснено операцію логічного заперечення. Ця елементарна і дуже важлива у бульовій алгебрі логічна операція називається інверсією (логічним запереченням). Вона означає якщо висловлення () істинне, то висловлення “НЕ X” () – хибне (), а якщо висловлення – хибне (), то висловлення – істинне ().

Логічна функція – це складне висловлення з кількох простих, які пов’язані між собою логічними операціями. Логічна функція набуває значення 0 або 1 ( є {0, 1}) при наборі логічних двійкових змінних (аргументів) є {0, 1}.

Якщо кожному значенню аргументу відповідає тільки одне значення логічної функції, така функція називається однозначною, якщо два або більше – багатозначною. Однозначна функція може бути зображена тільки двома аргументами (0 і 1) і двома своїми значеннями (0 і 1). Отже, число однозначних функцій у цьому випадку може бути тільки . Особливо цікава одна з них – інверсія , решта – тривіальні.

Вхідний набір – це певна комбінація значень двійкових змінних у логічній функції . Максимальне число вхідних наборів визначається як (де – число змінних), максимальне число логічних функцій змінних – як .

Двозначні функції мають можливих значень аргументів i два різних значення функцій ( i ), що в результаті дає різних двозначних бульових функцій. Число наборів аргументів , а їх значення такі: { }, { }, { }, { }. У випадку функції трьох змінних різних наборів аргументів буде : { }, { }, { }, { }, { }, { }, { }, { }, а різних значень тризначної функції буде вже .

Логічна функція, яка має певні значення 0 або на всіх вхідних наборах, називаєтеся повністю визначеною функцією. Якщо логічна функція має значення, які на деяких вхідних наборах не визначені, їх називають байдужими (або непевними). Частково визначену логічну функцію можна зробити повністю визначеною (до визначеного) приписуванням байдужим наборам довільних значень функції.

Множину логічних функцій змінних можна утворити з допомогою трьох основних логічних операцій:

логічного заперечення (“ – “) – інверсії;

логічного додавання (“ V “) – диз’юнкції;

логічного множення (“. “) – кон’юнкції.

Для згаданих операцій справедливі такі аксіоми (тотожності або правила):

універсальна множина –

нульова множина –

повторення (тавтологія) –

доповнення –

подвійна інверсія – .

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

правило К.Шеннона стверджує, що для одержання алгебраїчного виразу інверсної функції необхідно у згаданій функції всі змінні замінити на інверсні їм, всі знаки кон’юнкції – на знаки диз’юнкції, а всі знаки диз’юнкції – на знаки кон’юнкції;

правило де Моргана стверджує, що інверсія кон’юнкції дорівнює диз’юнкції інверсій, а інверсія диз’юнкції – кон’юнкції інверсій.

У бульовій алгебрі також діють закони, за якими можна встановити аналітичні зв’язки між різними логічними функціями і виконувати відповідні перетворення для спрощення складних виразів. Основні закони бульової алгебри зведені в табл.3. Справедливість аксіом і законів легко перевірити прямою підстановкою нуля або одиниці на місце конкретного аргументу.

Таблиця 3

Закон комутативності (переміщення)	X X =X X X X =X X
Закон асоціативності (сполучення)	X (X X )=(X X )X =X X X X (X X )=(X X ) X =X X X
Закон дистрибутивності (розподілу)	X (X X )=X X X X X X X =(X X )(X X )
Закон склеювання	(X X )(X )=X X X X =X
Закон поглинання	X (X X )=X X X X =X
Закон дуальності (правило де Моргана)	= =

Застосовуючи аксіоми (тотожності) та закони бульової алгебри, можна отримати нові логічні формули, а також довести справедливість того чи іншого закону на основі інших.

Особливої уваги заслуговують закони дуальності (правило де Моргана), з допомогою яких кон’юнкцію можна виразити через диз’юнкцію, і навпаки. Таку операцію часто треба здійснювати при перетвореннях логічних виразів. Корисними для практики можуть бути також наслідки законів дуальності, зокрема:

(1.3) (1.4)

Закони дуальності та наслідки з них справедливі для довільного числа змінних:

(1.5) (1.6)

Приклад. Довести справедливість закону дистрибутивності для диз’юнкції, тобто рівності

Розв’язання. Застосовуючи закон поглинання, отримуємо: