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

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

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

Забиваем Сайты В ТОП КУВАЛДОЙ - Уникальные возможности от SeoHammer

Каждая ссылка анализируется по трем пакетам оценки: SEO, Трафик и SMM. SeoHammer делает продвижение сайта прозрачным и простым занятием. Ссылки, вечные ссылки, статьи, упоминания, пресс-релизы - используйте по максимуму потенциал SeoHammer для продвижения вашего сайта.

Что умеет делать SeoHammer

— Продвижение в один клик, интеллектуальный подбор запросов, покупка самых лучших ссылок с высокой степенью качества у лучших бирж ссылок.
— Регулярная проверка качества ссылок по более чем 100 показателям и ежедневный пересчет показателей качества проекта.
— Все известные форматы ссылок: арендные ссылки, вечные ссылки, публикации (упоминания, мнения, отзывы, статьи, пресс-релизы).
— SeoHammer покажет, где рост или падение, а также запросы, на которые нужно обратить внимание.

SeoHammer еще предоставляет технологию Буст, она ускоряет продвижение в десятки раз, а первые результаты появляются уже в течение первых 7 дней.

Зарегистрироваться и Начать продвижение

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

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

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

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

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

Сервис онлайн-записи на собственном Telegram-боте

Попробуйте сервис онлайн-записи VisitTime на основе вашего собственного Telegram-бота:
— Разгрузит мастера, специалиста или компанию;
— Позволит гибко управлять расписанием и загрузкой;
— Разошлет оповещения о новых услугах или акциях;
— Позволит принять оплату на карту/кошелек/счет;
— Позволит записываться на групповые и персональные посещения;
— Поможет получить от клиента отзывы о визите к вам;
— Включает в себя сервис чаевых.

Для новых пользователей первый месяц бесплатно.

Зарегистрироваться в сервисе

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

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

логічного додавання (“ 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)

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

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