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

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

Основне поняття алгебри логіки - висловлення, тобто речення, в якому міститься суть (сенс) твердження істинності або його заперечення (хибності). Будь-яке висловлення можна позначити символом, наприклад, X або У , і вважати, що, Х = 1 або У = 1, якщо висловлення істинне, а X = 0 або У=0, якщо висловлення неістинне (хибне). Оскільки будь-яка змінна (або її функція) може мати стан 0 або 1, в алгебрі логіки кожній двійковій змінній ставиться у відповідність обернена до неї (інверсна) змінна, така, що якщо Х=0, то Основні поняття та закони бульової алгебри - №1 - открытая онлайн библиотека , а якщо Основні поняття та закони бульової алгебри - №2 - открытая онлайн библиотека , то Основні поняття та закони бульової алгебри - №3 - открытая онлайн библиотека . Подвійне заперечення дав аргумент, тобто Основні поняття та закони бульової алгебри - №4 - открытая онлайн библиотека . Риска "-" над змінною Х означає, що над змінною Основні поняття та закони бульової алгебри - №5 - открытая онлайн библиотека здійснено операцію логічного заперечення. Ця елементарна і дуже важлива у бульовій алгебрі логічна операція називається інверсією (логічним запереченням). Вона означає, що якщо висловлення ( Основні поняття та закони бульової алгебри - №2 - открытая онлайн библиотека ) істинне, то висловлення "НЕ X" ( Основні поняття та закони бульової алгебри - №7 - открытая онлайн библиотека ) - хибне ( Основні поняття та закони бульової алгебри - №3 - открытая онлайн библиотека ), а якщо висловлення X - хибне ( Основні поняття та закони бульової алгебри - №9 - открытая онлайн библиотека ), то висловлення Основні поняття та закони бульової алгебри - №7 - открытая онлайн библиотека - істинне ( Основні поняття та закони бульової алгебри - №1 - открытая онлайн библиотека ).

Логічна функція Основні поняття та закони бульової алгебри - №12 - открытая онлайн библиотека - це складне висловлення з кількох простих, які пов’язані між собою логічними операціями. Логічна функція Основні поняття та закони бульової алгебри - №13 - открытая онлайн библиотека набуває значення 0 або 1 ( Основні поняття та закони бульової алгебри - №14 - открытая онлайн библиотека ) при наборі логічних двійкових змінних (аргументів) Основні поняття та закони бульової алгебри - №15 - открытая онлайн библиотека .

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

Вхідний набір - це певна комбінація значень двійкових змінних Основні поняття та закони бульової алгебри - №18 - открытая онлайн библиотека . у логічній функції У . Максимальне число вхідних наборів визначається як Основні поняття та закони бульової алгебри - №19 - открытая онлайн библиотека (де n - число змінних), максимальне число логічних функцій n змінних - як Основні поняття та закони бульової алгебри - №20 - открытая онлайн библиотека .

Двозначні функції Основні поняття та закони бульової алгебри - №21 - открытая онлайн библиотека мають N=4 можливих значень аргументів / Основні поняття та закони бульової алгебри - №22 - открытая онлайн библиотека / і два різних значення функцій ( Основні поняття та закони бульової алгебри - №13 - открытая онлайн библиотека і Основні поняття та закони бульової алгебри - №24 - открытая онлайн библиотека ), що в результаті дає 24=16 різних двозначних бульових функцій. Число наборів аргументів 22=4. а їх значення такі: Основні поняття та закони бульової алгебри - №25 - открытая онлайн библиотека , Основні поняття та закони бульової алгебри - №26 - открытая онлайн библиотека , Основні поняття та закони бульової алгебри - №27 - открытая онлайн библиотека , Основні поняття та закони бульової алгебри - №28 - открытая онлайн библиотека . У випадку функції трьох змінних Основні поняття та закони бульової алгебри - №29 - открытая онлайн библиотека різних наборів аргументів буде

Основні поняття та закони бульової алгебри - №30 - открытая онлайн библиотека а різних значень тризначної функції буде вже 28=256.

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

Множину логічних Функцій Основні поняття та закони бульової алгебри - №31 - открытая онлайн библиотека змінних можна утворити з допомогою трьох основних логічних операцій:

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

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

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

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

· універсальна множина –{ Основні поняття та закони бульової алгебри - №32 - открытая онлайн библиотека ; 1vX=1;}

· нульова множина -{ Основні поняття та закони бульової алгебри - №33 - открытая онлайн библиотека ; 0vX=X;}

· повторення (тавтологія) -{ Основні поняття та закони бульової алгебри - №34 - открытая онлайн библиотека XvXv…vX=X;}

· доповнення –{Ошибка! Объект не может быть создан из кодов полей редактирования.; XvОшибка! Объект не может быть создан из кодов полей редактирования.;}

· подвійна інверсія - Основні поняття та закони бульової алгебри - №4 - открытая онлайн библиотека .

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

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

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

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

Таблиця 1.4 Основні закони булевої алгебри

Закони комутативності /переміщення/ Основні поняття та закони бульової алгебри - №37 - открытая онлайн библиотека Основні поняття та закони бульової алгебри - №38 - открытая онлайн библиотека v Основні поняття та закони бульової алгебри - №39 - открытая онлайн библиотека v Основні поняття та закони бульової алгебри - №38 - открытая онлайн библиотека
Закони асоціативності /сполучення/ Основні поняття та закони бульової алгебри - №41 - открытая онлайн библиотека Основні поняття та закони бульової алгебри - №38 - открытая онлайн библиотека v Основні поняття та закони бульової алгебри - №43 - открытая онлайн библиотека v Основні поняття та закони бульової алгебри - №44 - открытая онлайн библиотека v Основні поняття та закони бульової алгебри - №45 - открытая онлайн библиотека v Основні поняття та закони бульової алгебри - №46 - открытая онлайн библиотека v Основні поняття та закони бульової алгебри - №47 - открытая онлайн библиотека v Основні поняття та закони бульової алгебри - №48 - открытая онлайн библиотека
Закони дистрибутивності /розподілу/ Основні поняття та закони бульової алгебри - №49 - открытая онлайн библиотека v Основні поняття та закони бульової алгебри - №50 - открытая онлайн библиотека v Основні поняття та закони бульової алгебри - №51 - открытая онлайн библиотека Основні поняття та закони бульової алгебри - №38 - открытая онлайн библиотека v Основні поняття та закони бульової алгебри - №53 - открытая онлайн библиотека v Основні поняття та закони бульової алгебри - №54 - открытая онлайн библиотека v Основні поняття та закони бульової алгебри - №55 - открытая онлайн библиотека
Закони склеювання   Основні поняття та закони бульової алгебри - №56 - открытая онлайн библиотека v Основні поняття та закони бульової алгебри - №54 - открытая онлайн библиотека v Основні поняття та закони бульової алгебри - №58 - открытая онлайн библиотека Основні поняття та закони бульової алгебри - №59 - открытая онлайн библиотека v Основні поняття та закони бульової алгебри - №60 - открытая онлайн библиотека
Закони поглинання   Основні поняття та закони бульової алгебри - №61 - открытая онлайн библиотека v Основні поняття та закони бульової алгебри - №62 - открытая онлайн библиотека Основні поняття та закони бульової алгебри - №38 - открытая онлайн библиотека v Основні поняття та закони бульової алгебри - №64 - открытая онлайн библиотека
Закони дуальності /правило де Моргана/ Основні поняття та закони бульової алгебри - №65 - открытая онлайн библиотека v Основні поняття та закони бульової алгебри - №66 - открытая онлайн библиотека Основні поняття та закони бульової алгебри - №67 - открытая онлайн библиотека

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

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

Основні поняття та закони бульової алгебри - №38 - открытая онлайн библиотека v Основні поняття та закони бульової алгебри - №69 - открытая онлайн библиотека ; ( 1.0)

Основні поняття та закони бульової алгебри - №70 - открытая онлайн библиотека ; ( 1.0)

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

Основні поняття та закони бульової алгебри - №71 - открытая онлайн библиотека ; Основні поняття та закони бульової алгебри - №72 - открытая онлайн библиотека ;