Основы булевой алгебры и булевых функций

Введение в булеву алгебру и логические значения

Зачем нужна булева алгебра

Булева алгебра — это раздел математики и логики, который работает не с числами в привычном смысле, а с логическими значениями: «истина» и «ложь». Она лежит в основе:

логических рассуждений в формальной логике

схемотехники и цифровой электроники (логические элементы)

булевых условий в программировании (if, фильтры, проверки)

поиска и фильтрации данных (логические запросы)

Исторически булева алгебра связана с работами Джорджа Буля. Для справки можно обратиться к источникам: Булева алгебра, Джордж Буль.

Логические значения и обозначения

В булевой алгебре используется множество из двух значений:

0 — ложь (False)

1 — истина (True)

В дальнейшем мы будем считать, что любая переменная (например, A, B) может принимать только 0 или 1.

Понятие булевой функции

Булева функция — это правило (зависимость), которое принимает на вход одно или несколько логических значений и возвращает одно логическое значение.

Примеры на интуитивном уровне:

«Идёт ли дождь и есть ли у меня зонт?» → результат: да/нет

«Температура выше нормы или есть воспаление?» → результат: да/нет

Если функция зависит от переменных A и B, то иногда говорят: «функция от двух аргументов». В курсах по логике и схемотехнике такие функции часто задаются таблицей истинности.

Справка: Таблица истинности.

Основные булевы операции

В этом курсе базовыми считаются три операции:

И (AND)

ИЛИ (OR)

НЕ (NOT)

Их удобно понимать через таблицы истинности.

Операция НЕ (NOT)

Операция НЕ меняет значение на противоположное.

Обозначение: (читается «не A»), где:

— логическая переменная (0 или 1)

— знак отрицания (операция NOT)

Таблица истинности:

| A | | |---:|---:| | 0 | 1 | | 1 | 0 |

Пример: если A означает «доступ разрешён», то означает «доступ НЕ разрешён».

Операция И (AND)

Операция И даёт 1 только тогда, когда оба аргумента равны 1.

Обозначение: , где:

, — логические переменные

— знак конъюнкции (операция AND)

Таблица истинности:

| A | B | | |---:|---:|---:| | 0 | 0 | 0 | | 0 | 1 | 0 | | 1 | 0 | 0 | | 1 | 1 | 1 |

Интуиция: «условие выполнено и второе условие выполнено».

Операция ИЛИ (OR)

Операция ИЛИ даёт 1, если хотя бы один из аргументов равен 1.

Обозначение: , где:

, — логические переменные

— знак дизъюнкции (операция OR)

Таблица истинности:

| A | B | | |---:|---:|---:| | 0 | 0 | 0 | | 0 | 1 | 1 | | 1 | 0 | 1 | | 1 | 1 | 1 |

Важно: в булевой алгебре ИЛИ обычно понимается как включающее ИЛИ: если оба истинны, результат тоже истина.

!Схема показывает, что AND и OR принимают два входа, а NOT — один

Табличное задание булевой функции

Любую булеву функцию можно описать перечислением всех возможных входов и соответствующего выхода.

Например, функция (читается «A и не B») означает:

сначала вычислить

затем выполнить AND между и результатом

Таблица истинности:

| A | B | | | |---:|---:|---:|---:| | 0 | 0 | 1 | 0 | | 0 | 1 | 0 | 0 | | 1 | 0 | 1 | 1 | | 1 | 1 | 0 | 0 |

Основные законы и тождества булевой алгебры

Тождество — это равенство, которое верно при любых значениях переменных (то есть при любых 0/1 на входе).

Ниже — набор законов, которые постоянно используются при преобразованиях выражений (упрощении логики, оптимизации схем, доказательствах).

Законы перестановки и группировки

| Закон | Для AND | Для OR | |---|---|---| | Коммутативность (перестановка) | | | | Ассоциативность (группировка) | | |

Смысл: порядок и расстановка скобок не меняют результата (если операция одна и та же).

Дистрибутивность (распределение)

| Закон | Формула | |---|---| | AND распределяется относительно OR | | | OR распределяется относительно AND | |

Смысл: можно раскрывать скобки, но в булевой алгебре существуют оба варианта распределения (это отличает её от обычной арифметики, где привычно только распределение умножения относительно сложения).

Нейтральные элементы и «поглощающие» значения

| Свойство | AND | OR | |---|---|---| | Нейтральный элемент | | | | Поглощение «краем» | | |

Интуиция:

в AND единица «ничего не меняет», а ноль «обнуляет всё»

в OR ноль «ничего не меняет», а единица «делает истину гарантированной»

Идемпотентность и двойное отрицание

| Свойство | Формула | |---|---| | Идемпотентность | , | | Двойное отрицание | |

Смысл: повторение одного и того же условия не добавляет новой информации; двойное «НЕ» возвращает исходное.

Законы де Моргана

Законы де Моргана объясняют, как «раскрывать отрицание» над скобками.

| Формулировка | Формула | |---|---| | Отрицание AND превращается в OR отрицаний | | | Отрицание OR превращается в AND отрицаний | |

Практический смысл: если вы переносите отрицание внутрь выражения, операция меняется (AND ↔ OR), а каждое условие тоже получает отрицание.

Справка: Законы де Моргана.

Как читать и проверять равенства в булевой алгебре

Есть два базовых подхода:

Таблица истинности: выписать все варианты входов и убедиться, что выходы слева и справа совпадают во всех строках.

Преобразования по тождествам: шаг за шагом заменять части выражения эквивалентными по законам (как упрощают алгебраические выражения).

В следующих материалах курса эти методы будут использоваться для упрощения булевых выражений и анализа булевых функций.

Понятие булевой функции и способы задания

Что такое булева функция

В предыдущей статье мы ввели два логических значения (0 и 1) и базовые операции НЕ, И, ИЛИ. Теперь зафиксируем, что именно называют булевой функцией и как её можно задавать.

Булева функция — это правило, которое:

принимает на вход логических переменных (каждая равна 0 или 1)

возвращает одно логическое значение (0 или 1)

Чаще всего булеву функцию записывают так:

Разберём обозначения:

— имя функции (результат вычисления)

— множество допустимых значений одной переменной: 0 (ложь) и 1 (истина)

— число входных переменных (входов)

— все возможные наборы из значений 0/1 (например, для двух переменных это пары , , , )

— «отображение»: каждому входному набору сопоставляется один выход (0 или 1)

Арность и число наборов входов

Если функция зависит от переменных, то таких переменных называют аргументами, а число аргументов — арностью.

Сколько существует разных входных наборов?

для 1 переменной: 2 набора (0 и 1)

для 2 переменных: 4 набора

для 3 переменных: 8 наборов

В общем виде число наборов равно .

— потому что у каждой переменной 2 возможных значения (0 или 1)

— потому что переменных , и выбираем значение для каждой

!Схема показывает, что булева функция сопоставляет каждому набору входов один выход

Способы задания булевой функции

Одну и ту же булеву функцию можно задать разными, но эквивалентными способами. Это важно: в логике, программировании и схемотехнике вы будете постоянно переводить одно представление в другое.

Таблица истинности

Таблица истинности перечисляет все возможные наборы входов и соответствующее значение функции.

Пример: функция .

и — входные переменные

— результат операции НЕ над

— результат операции И между и

| A | B | | | |---:|---:|---:|---:| | 0 | 0 | 1 | 0 | | 0 | 1 | 0 | 0 | | 1 | 0 | 1 | 1 | | 1 | 1 | 0 | 0 |

Таблица истинности удобна тем, что полностью определяет функцию и позволяет сравнивать функции «по строкам».

Булево выражение (формула)

Булеву функцию можно задать выражением из переменных и операций НЕ, И, ИЛИ.

Примеры:

- - -

Полезные замечания:

скобки задают порядок вычислений

выражение можно преобразовывать по законам булевой алгебры (коммутативность, дистрибутивность, де Морган и т.д.), не меняя саму функцию

Описание «словами» (правилом)

Часто функция сначала формулируется как условие.

Примеры:

«система выдаёт сигнал тревоги, если датчик дыма или датчик температуры сработал»

«доступ разрешён, если пользователь админ и пароль верный»

Затем это правило переводят в выражение или таблицу истинности.

Логическая схема (схема из элементов)

В цифровой электронике булевы функции реализуют схемами из логических элементов NOT, AND, OR.

Одна и та же функция может быть изображена:

как выражение, например

как схема с двумя входами в AND, одним инвертором для , затем OR на выходе

!Визуализация соответствия булевого выражения и логической схемы

Задание через множество наборов, где функция равна 1

Иногда функцию задают не формулой и не полной таблицей, а списком входов, на которых она равна 1.

Пример: пусть функция от двух переменных равна 1 на наборах:

- -

Во всех остальных случаях функция равна 0.

Такое задание удобно, когда «единичных» наборов мало (или наоборот — когда мало «нулевых» наборов).

Чтобы перейти к выражению, используют идею: составить для каждого «единичного» набора условие, которое истинно только на этом наборе, а затем объединить такие условия через ИЛИ.

Для этого вводят понятие литерала:

литерал — это либо переменная (), либо её отрицание ()

Как построить условие для набора :

означает литерал

означает литерал

вместе:

Для набора условие: .

Тогда функция задаётся выражением:

Далее это выражение можно упростить по законам булевой алгебры:

вынесем как общий множитель по дистрибутивности:

(это всегда истина)

значит

Итог: функция, которая равна 1 на и , на самом деле просто равна .

Равенство (эквивалентность) булевых функций

Две булевы функции считают эквивалентными, если они дают одинаковый результат при любых одинаковых входах.

Как это проверяют на практике:

строят таблицы истинности и сравнивают столбцы результатов

или преобразуют выражение по тождествам, пока не получат такое же выражение (или очевидно эквивалентное)

Эквивалентность особенно важна при упрощении логики: выражение может стать короче, схема — дешевле, а функция при этом останется той же.

Сколько существует булевых функций

Число различных булевых функций от переменных равно:

Почему так:

есть различных входных наборов

на каждом наборе функция может независимо выбрать значение 0 или 1

значит число способов заполнить столбец результатов длины равно

Пример для :

входных наборов (0 и 1)

функций

Это соответствует четырём вариантам поведения: всегда 0, всегда 1, , .

Главное

Булева функция отображает наборы 0/1 входов в один выход 0/1.

Функцию можно задавать таблицей истинности, выражением, словесным правилом, логической схемой или списком наборов, где она равна 1.

Эквивалентность функций означает совпадение результатов на всех входах; её проверяют таблицей истинности или преобразованиями по законам булевой алгебры.

Операция НЕ (NOT): отрицание и его свойства

Роль операции НЕ в булевой алгебре

В предыдущих статьях мы договорились, что логические значения бывают только двух видов: 0 (ложь) и 1 (истина), а булева функция сопоставляет входам 0/1 один выход 0/1.

Операция НЕ (NOT) — это самый простой способ изменить логическое значение: она превращает истину в ложь и наоборот. Несмотря на простоту, отрицание постоянно встречается:

в программировании (проверки вида not condition или !condition)

в логических схемах (инвертор)

в преобразованиях выражений (например, законы де Моргана)

Справка: Логическое отрицание

Определение операции НЕ (NOT)

Операция НЕ применяется к одной переменной.

Запись:

Разберём обозначение:

— булева переменная, то есть принимает значение 0 или 1

— знак отрицания (операция NOT)

— результат отрицания

Смысл: значение всегда противоположно значению .

Таблица истинности

| A | | |---:|---:| | 0 | 1 | | 1 | 0 |

Эта таблица полностью задаёт операцию NOT.

!Инвертор (NOT) и соответствующая таблица истинности

Как читать и вычислять выражения с отрицанием

Отрицание переменной

Если сказано:

(истина), то (ложь)

(ложь), то (истина)

Отрицание сложного выражения

Отрицать можно не только переменную, но и целое выражение, например или . В таких случаях важно помнить:

отрицание относится ко всему выражению в скобках

чтобы преобразовывать такие записи, используют законы де Моргана (они уже упоминались ранее и будут активно применяться дальше)

Справка: Законы де Моргана

Основные свойства отрицания

Ниже — тождества (равенства), верные при любых значениях переменных 0/1. Их можно проверять таблицей истинности или использовать как правила преобразования.

Двойное отрицание

Пояснение символов:

— исходная булева переменная

— отрицание

— отрицание результата

Смысл: если отрицать два раза, вернёмся к исходному значению.

Отрицание констант

- -

Это частный случай определения NOT: константы 0 и 1 тоже можно отрицать.

Дополнение: «или» и «и» с отрицанием

Эти тождества часто называют свойствами дополнения (комплементарности):

- -

Разберём смысл на уровне логики:

выражение истинно всегда, потому что либо истинно , либо истинно его отрицание

выражение ложно всегда, потому что невозможно, чтобы и одновременно не- были истинны

Эти свойства особенно полезны при упрощении булевых выражений.

Отрицание и преобразования выражений

Отрицание — один из главных инструментов упрощения, потому что оно позволяет:

убирать «лишние» отрицания (через двойное отрицание)

переносить отрицание внутрь/наружу скобок, меняя операции AND/OR по законам де Моргана

Напоминание формулировок де Моргана (их удобно держать под рукой):

- -

Смысл: при переносе отрицания внутрь скобок операция меняется (AND ↔ OR), и каждый аргумент получает отрицание.

Отрицание в программировании и схемах

В программировании

Во многих языках встречаются эквивалентные записи отрицания:

!A (часто в C-подобных языках)

not A (например, в Python)

Важно: в булевой алгебре мы работаем строго с 0/1, а в языках программирования иногда есть дополнительные правила приведения типов. Поэтому, когда изучаете булеву алгебру, держите фокус на логике 0/1 и таблицах истинности.

В логических схемах

Операции AND, OR, NOT реализуются логическими элементами. Для NOT используют инвертор: один вход, один выход, и на выходе всегда противоположное значение.

Главное

NOT — унарная операция: она применяется к одному аргументу.

Таблица истинности NOT: , .

Ключевые свойства: , , , а также и .

Для отрицания выражений в скобках используют законы де Моргана: отрицание «переворачивает» AND/OR и добавляет отрицание каждому аргументу.

Операция И (AND): конъюнкция, таблицы истинности, свойства

Место операции И в булевой алгебре

В прошлых статьях мы зафиксировали два логических значения (0 и 1), понятие булевой функции и операцию НЕ. Теперь разберём вторую базовую операцию — И.

Операция И (AND, конъюнкция) используется, когда результат должен быть истинным только при одновременной истинности нескольких условий.

Примеры «из жизни»:

«Доступ разрешён, если пользователь — администратор и пароль верный»

«Сигнал подаётся, если датчик включён и питание есть»

Справка: Конъюнкция

Определение операции И (AND)

Операция И применяется к двум булевым значениям.

Запись:

Расшифровка записи:

— первая булева переменная (может быть 0 или 1)

— вторая булева переменная (может быть 0 или 1)

— знак операции И (AND)

— результат операции AND над и

Смысл:

только если и

иначе

Таблица истинности для AND

Таблица истинности перечисляет все варианты входов и результат операции.

| A | B | | |---:|---:|---:| | 0 | 0 | 0 | | 0 | 1 | 0 | | 1 | 0 | 0 | | 1 | 1 | 1 |

Как читать таблицу:

строка означает «, »

в этой строке , потому что не выполняется условие «оба равны 1»

!Схема элемента AND и его таблица истинности

Как вычислять выражения с AND

AND как «фильтр» истинности

Если в выражении есть , то достаточно, чтобы хотя бы один из множителей оказался 0, и весь результат станет 0.

Это напрямую следует из таблицы истинности: во всех строках, где есть хотя бы один 0 среди и , итог равен 0.

AND для трёх и более переменных

Операцию AND можно применять цепочкой:

читается как « и и »

Такое выражение равно 1 только если все три переменные равны 1.

Технически это опирается на ассоциативность (её мы докажем как тождество ниже):

-

Основные тождества и свойства операции AND

Ниже перечислены тождества, которые верны при любых значениях переменных 0/1. Их можно использовать как правила преобразования при упрощении булевых выражений.

Коммутативность

Пояснение:

слева переменные стоят в порядке , затем

справа порядок поменяли

результат одинаков, потому что важно лишь то, равны ли оба значения 1

Ассоциативность

Пояснение:

слева сначала вычисляется , затем результат AND с

справа сначала вычисляется , затем AND с

в обоих случаях итог равен 1 тогда и только тогда, когда , и

Нейтральный элемент и поглощающее значение

Нейтральный элемент:

Пояснение:

означает «истина»

условие « и истина» эквивалентно просто «»

Поглощающее значение:

Пояснение:

означает «ложь»

условие « и ложь» никогда не выполнится

Идемпотентность

Пояснение:

« и » не добавляет нового ограничения

если , то результат 1; если , то результат 0

Связь AND с отрицанием

Тождество комплементарности:

Пояснение:

означает «не » (операция NOT из предыдущей статьи)

невозможно, чтобы одновременно выполнялись « истинно» и « ложно»

Дистрибутивность AND относительно OR

Пояснение символов:

— операция ИЛИ (OR)

запись означает « истинно или истинно (или оба)»

Интуиция:

слева: « истинно и при этом истинно хотя бы одно из или »

справа: «либо и , либо и »

Это тождество лежит в основе раскрытия скобок и преобразования выражений.

Поглощение (полезное тождество для упрощения)

Почему это верно (интуитивно):

если , то слева , справа тоже 0

если , то слева , справа тоже 1

Это правило часто позволяет убрать «лишние» части выражения.

Мини-пример: таблица истинности для выражения с AND

Пусть дана функция:

Расшифровка:

— отрицание

— AND между и результатом

Таблица истинности:

| A | B | | | |---:|---:|---:|---:| | 0 | 0 | 1 | 0 | | 0 | 1 | 0 | 0 | | 1 | 0 | 1 | 1 | | 1 | 1 | 0 | 0 |

По этой таблице видно: только в случае и .

AND в программировании и схемах

В программировании AND часто записывают как:

A && B во многих C-подобных языках

A and B в Python

В схемотехнике AND реализуется логическим элементом «И». Справка: Логический элемент «И»

Важно: в булевой алгебре мы всегда работаем с чистыми 0 и 1, а в языках программирования иногда есть дополнительные правила вычисления и приведения типов.

Главное

AND (конъюнкция) возвращает 1 только если оба аргумента равны 1.

Таблица истинности полностью задаёт поведение операции.

Ключевые тождества AND: коммутативность, ассоциативность, нейтральный элемент , поглощающее значение , идемпотентность, комплементарность , дистрибутивность относительно OR и поглощение.

Эти свойства — основа для упрощения булевых выражений и анализа булевых функций.

Операция ИЛИ (OR): дизъюнкция, таблицы истинности, свойства

Место операции ИЛИ в булевой алгебре

В предыдущих статьях мы закрепили:

что булевы переменные принимают только значения 0 и 1

что отрицание задаётся операцией НЕ

что операция И требует одновременной истинности условий

Теперь разберём третью базовую операцию — ИЛИ (OR, дизъюнкция). Она используется, когда достаточно, чтобы выполнилось хотя бы одно условие.

Примеры формулировок:

«Сигнал тревоги включается, если сработал датчик дыма или датчик температуры»

«Доступ разрешён, если пользователь — админ или введён одноразовый код»

Термин дизъюнкция означает логическое сложение по правилу “хотя бы одно истинно”. Справка: Дизъюнкция.

Определение операции ИЛИ (OR)

Операция ИЛИ применяется к двум булевым значениям.

Запись:

Пояснение символов:

— первая булева переменная (может быть или )

— вторая булева переменная (может быть или )

— знак операции ИЛИ (OR)

— результат применения OR к и

Смысл:

, если хотя бы одно из значений или равно

только тогда, когда и

Важно: в булевой алгебре по умолчанию используется включающее ИЛИ: если оба аргумента равны , результат тоже равен .

Таблица истинности для OR

Таблица истинности перечисляет все варианты входов и значение результата.

| A | B | | |---:|---:|---:| | 0 | 0 | 0 | | 0 | 1 | 1 | | 1 | 0 | 1 | | 1 | 1 | 1 |

Как читать таблицу:

строка , даёт , потому что второе условие истинно

единственный случай, когда результат , это и

!Схема элемента OR и соответствующая таблица истинности

Как вычислять выражения с OR

Полезная интуиция: OR работает как правило “достаточно одного”.

если в выражении уже известно, что , то весь результат равен независимо от

если , то результат полностью определяется (потому что )

Эта интуиция станет особенно важной, когда вы начнёте упрощать длинные выражения.

Основные тождества и свойства операции OR

Ниже — тождества (равенства), которые верны при любых значениях переменных . Их можно проверять таблицами истинности и применять как правила преобразования.

Коммутативность

Пояснение:

слева и справа участвуют одни и те же значения и

порядок аргументов не влияет на факт “есть ли хотя бы одна единица”

Ассоциативность

Пояснение:

, , — булевы переменные

скобки меняют порядок вычислений, но смысл тот же: результат , если хотя бы одна из переменных равна

Это позволяет писать без скобок: .

Нейтральный элемент и поглощающее значение

Нейтральный элемент для OR:

Пояснение:

означает “ложь”

“ или ложь” эквивалентно просто “”

Поглощающее значение для OR:

Пояснение:

означает “истина”

“что угодно или истина” всегда истинно

Идемпотентность

Пояснение:

повторение одного и того же условия не добавляет нового смысла

Связь OR с отрицанием

Из статьи про НЕ мы уже знаем отрицание . Для OR часто используют два ключевых тождества.

Тождество комплементарности:

Пояснение:

либо истинно, либо истинно “не ”

третьего не дано, поэтому результат всегда

Законы де Моргана (нужны, чтобы “заносить” отрицание внутрь скобок):

-

Пояснение:

слева отрицание применяется ко всему выражению “ или ”

справа операция меняется с OR на AND, и каждое из условий получает отрицание

Справка: Законы де Моргана.

Дистрибутивность OR относительно AND

Пояснение символов:

— операция И (AND)

означает “ и одновременно”

Интуиция:

слева: “истинно , или истинны сразу и ”

справа: “одновременно выполнено: (истинно или ) и (истинно или )”

Это тождество помогает перестраивать выражения и упрощать схемы.

Поглощение (часто упрощает выражения)

Пояснение:

если , то слева уже истинно (неважно, что с ), и результат

если , то , значит слева

Итог: выражение всегда равно , а часть оказывается лишней.

Мини-пример: таблица истинности для выражения с OR и NOT

Рассмотрим функцию:

Что означает запись:

— отрицание

— операция OR между и “не ”

Таблица истинности:

| A | B | | | |---:|---:|---:|---:| | 0 | 0 | 1 | 1 | | 0 | 1 | 0 | 0 | | 1 | 0 | 1 | 1 | | 1 | 1 | 0 | 1 |

Из таблицы видно:

единственный случай, когда , это и

во всех остальных случаях хотя бы одно из условий “” или “не ” истинно

OR в программировании и логических схемах

В программировании OR часто записывают так:

A || B во многих C-подобных языках

A or B в Python

В схемотехнике OR реализуется логическим элементом “ИЛИ”. Справка: Логический элемент «ИЛИ».

Важно: в булевой алгебре мы рассматриваем чистые значения . В языках программирования иногда есть приведение типов и особенности вычисления выражений, поэтому опирайтесь на таблицы истинности как на базовую модель.

Главное

OR (дизъюнкция) возвращает , если хотя бы один аргумент равен .

Таблица истинности OR имеет единственный нулевой случай: .

Ключевые тождества OR: коммутативность, ассоциативность, нейтральный элемент , поглощающее значение , идемпотентность, комплементарность , дистрибутивность относительно AND и поглощение .

Связь с отрицанием часто выражают через законы де Моргана: .

Основные законы и тождества булевых операций

Зачем нужны законы булевой алгебры

В предыдущих статьях мы уже определили булевы значения и , а также операции НЕ (), И () и ИЛИ (). Теперь соберём в одном месте основные законы и тождеcтва для этих операций.

Они нужны, чтобы:

упрощать булевы выражения (делать формулы короче)

доказывать, что две формулы задают одну и ту же булеву функцию

преобразовывать выражения при проектировании логических схем и условий в программах

Официальная справка по теме: Булева алгебра.

Что такое тождество и эквивалентность

Тождество — это равенство двух булевых выражений, которое верно при любых значениях переменных (при любых на входе).

Когда мы пишем, например, , это значит:

— булева переменная (может быть или )

— булева константа (ложь)

выражение слева и выражение справа всегда дают одинаковый результат

Если два выражения тождественно равны, то они задают эквивалентные булевы функции.

Проверяют тождества двумя основными способами:

по таблице истинности (сравнить результаты во всех строках)

преобразованиями по законам (заменяя часть выражения на эквивалентную)

Базовые тождества и законы

Ниже — минимальный набор правил, который покрывает большую часть практических преобразований.

Коммутативность

Коммутативность означает, что аргументы можно менять местами.

Для AND:

Здесь и — булевы переменные, а — операция И.

Для OR:

Здесь — операция ИЛИ.

Ассоциативность

Ассоциативность означает, что при одинаковой операции скобки можно переставлять.

Для AND:

Для OR:

Здесь , , — булевы переменные.

Практический вывод: можно писать и без лишних скобок, если операция одна и та же.

Нейтральные элементы и поглощающие значения

Нейтральный элемент не меняет значение выражения.

Для AND нейтральный элемент — :

Здесь — константа истина.

Для OR нейтральный элемент — :

Поглощающее значение «перебивает» всё выражение.

Для AND поглощающее значение — :

Для OR поглощающее значение — :

Идемпотентность

Идемпотентность означает, что повтор одного и того же условия ничего не меняет.

Для AND:

Для OR:

Дополнение (комплементарность) и двойное отрицание

Эти правила связывают переменную с её отрицанием.

Двойное отрицание:

Здесь — операция НЕ.

«Всегда истина»:

Смысл: либо истинно, либо истинно «не ».

«Всегда ложь»:

Смысл: невозможно, чтобы одновременно выполнялись и «не ».

Дистрибутивность

Дистрибутивность описывает, как раскрывать скобки. В булевой алгебре важны оба направления.

AND распределяется относительно OR:

Слева: сначала вычисляется , потом результат объединяется с через .

Справа: получаются два слагаемых по OR, в каждом из которых присутствует .

OR распределяется относительно AND:

Эта форма часто нужна, когда выражение приводят к произведению сумм.

Поглощение

Поглощение позволяет выкидывать «лишние» части выражения.

Поглощение для OR:

Почему это работает: если , то слева уже истинно; если , то .

Поглощение для AND:

Почему это работает: если , слева ; если , то .

Законы де Моргана

Законы де Моргана объясняют, как заносить отрицание внутрь скобок.

Отрицание AND превращается в OR отрицаний:

Отрицание OR превращается в AND отрицаний:

Здесь важно сразу видеть два действия:

меняется операция:

каждое выражение внутри скобок получает отрицание

Справка: Законы де Моргана.

!Схема-памятка по законам де Моргана и интуиции «отрицание меняет операцию и добавляется к каждому аргументу»

Как применять тождества для упрощения

Цель упрощения — получить более короткое выражение, которое задаёт ту же булеву функцию.

Типовые шаги упрощения

убрать константы через нейтральные и поглощающие значения

убрать повторы через идемпотентность

использовать дополнение (, )

применять поглощение, чтобы избавиться от «лишних» частей

раскрывать и собирать скобки через дистрибутивность

переносить отрицания внутрь/наружу через де Моргана, когда так проще

Пример упрощения через вынесение общего множителя

Рассмотрим выражение:

Обозначения:

— булева функция от двух переменных

и — два условия, объединённые через OR ()

Шаг 1: вынесем общий множитель по дистрибутивности AND относительно OR.

Шаг 2: применим дополнение .

Шаг 3: применим нейтральный элемент для AND: .

Итог:

Смысл результата: исходная формула на самом деле не зависит от .

Пример с отрицанием и де Морганом

Упростим выражение:

Шаг 1: заметим, что по комплементарности.

Шаг 2: (нейтральный элемент для OR).

Итог: не зависит от и равна просто отрицанию .

Как доказывают тождества таблицей истинности

Таблица истинности — универсальный способ: мы проверяем все возможные входы и сравниваем результаты.

Например, проверим тождество поглощения .

| | | | | | |---:|---:|---:|---:|---:| | 0 | 0 | 0 | 0 | 0 | | 0 | 1 | 0 | 0 | 0 | | 1 | 0 | 0 | 1 | 1 | | 1 | 1 | 1 | 1 | 1 |

Столбцы и совпадают во всех строках, значит равенство — тождество.

Главное

Тождества булевой алгебры позволяют преобразовывать выражения без изменения булевой функции.

Базовый набор правил: коммутативность, ассоциативность, нейтральные и поглощающие значения, идемпотентность, дополнение, дистрибутивность, поглощение, законы де Моргана.

Эквивалентность выражений доказывают таблицами истинности или последовательными преобразованиями по тождествам.

Преобразование и упрощение булевых выражений на практике

Зачем упрощать булевы выражения

В предыдущих статьях мы разобрали:

что такое булевы значения и

что такое булева функция

операции НЕ (), И (), ИЛИ ()

основные тождества булевой алгебры (коммутативность, ассоциативность, дистрибутивность, поглощение, де Морган и т.д.)

Теперь применим эти правила на практике: будем превращать выражения в более простые, не меняя саму булеву функцию.

Зачем это нужно:

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

в схемотехнике: уменьшить число логических элементов (дешевле, быстрее, надёжнее)

в математике и логике: доказать эквивалентность выражений

Формально, если два выражения дают одинаковый результат при любых значениях переменных, то они эквивалентны и задают одну и ту же булеву функцию.

Два способа доказать эквивалентность

Проверка таблицей истинности

Таблица истинности — универсальный метод:

выписываем все наборов входов для переменных

считаем значения левой и правой частей

если столбцы результатов совпадают во всех строках — выражения эквивалентны

Плюсы:

не требует “догадок”, работает всегда

Минусы:

при большом числе переменных таблица становится слишком большой

Справка: Таблица истинности.

Преобразования по тождествам

Это основной практический путь:

выбираем подходящее тождество

заменяем часть выражения на эквивалентную

повторяем, пока выражение не станет проще

Плюсы:

хорошо масштабируется, если уметь видеть шаблоны

Минусы:

нужен навык: иногда есть несколько путей, и не все ведут к упрощению

Базовый набор “шаблонов”, которые чаще всего упрощают

Ниже — небольшая памятка из законов, которые в реальных задачах встречаются чаще других.

Константы и нейтральные элементы

- - - -

Здесь:

— булева переменная (может быть или )

— ложь, — истина

Повторы и “противоречия”

,

- -

Здесь означает “не ”.

Поглощение (часто даёт самое быстрое сокращение)

- -

Здесь — ещё одна булева переменная.

Дистрибутивность (чтобы выносить общий множитель или раскрывать скобки)

- -

Здесь , , — булевы переменные.

Законы де Моргана (чтобы “занести” отрицание внутрь)

- -

Справка: Законы де Моргана.

Практическая стратегия упрощения

Обычно удобно идти так:

Упростить очевидные места с константами и .

Убрать повторы (, ).

Найти пары вида или .

Применить поглощение (часто это “мгновенный выигрыш”).

Если есть похожие слагаемые, попробовать вынести общий множитель дистрибутивностью.

Если мешает отрицание над скобками, применить де Моргана.

!Блок-схема типового порядка действий при упрощении

Примеры упрощения “руками”

Пример с вынесением общего множителя

Упростим выражение:

Пояснение записи:

— булева функция от двух переменных и

— операция И

— операция ИЛИ

— отрицание переменной

Шаг 1: вынесем общий множитель по дистрибутивности:

Шаг 2: применим тождество дополнения :

Шаг 3: нейтральный элемент для AND: .

Итог:

Смысл результата: исходное выражение фактически не зависит от .

Пример с поглощением

Упростим:

Здесь:

, — булевы переменные

— результат выражения

По закону поглощения:

Итог:

Интуиция: если , то слева уже истина; если , то и всё равно получаем .

Пример с де Морганом и последующим упрощением

Упростим:

Здесь , , — булевы переменные.

Шаг 1: применим де Моргана к отрицанию OR:

Шаг 2: применим де Моргана к отрицанию AND:

Подставим:

Дальше выражение можно оставить так (оно уже “без отрицаний над скобками”), либо раскрывать дистрибутивностью, если нужно получить сумму произведений:

Практический смысл: вы выбрали форму в зависимости от того, что удобнее — факторизованная запись или раскрытая.

Пример: как не “ухудшить” выражение

Иногда раскрытие скобок делает формулу длиннее. Например:

Если раскрыть:

Это эквивалентно, но длиннее. Поэтому правило практики:

если цель — сделать выражение короче, чаще полезно выносить общий множитель, а не раскрывать скобки

Мини-проверка эквивалентности таблицей истинности (на маленьком примере)

Покажем, как подтверждать упрощение, если есть сомнения.

Пусть мы утверждаем, что:

Построим таблицу истинности:

| | | | | | |---:|---:|---:|---:|---:| | 0 | 0 | 0 | 0 | 0 | | 0 | 1 | 0 | 0 | 0 | | 1 | 0 | 0 | 1 | 1 | | 1 | 1 | 1 | 1 | 1 |

Столбцы и совпадают во всех строках, значит равенство верно для любых и .

Что считать “простым” выражением

Упрощение зависит от цели.

Для читаемости в логике/коде часто лучше факторизованная форма, например .

Для реализации схемой может быть выгодно минимизировать число элементов AND/OR/NOT.

Для сравнения функций полезно привести к стандартной форме и сверить (в дальнейшем в курсах часто используют формы “сумма произведений” и “произведение сумм”).

Главная идея: упрощение — это преобразование без изменения таблицы истинности функции.

Главное

Эквивалентность булевых выражений доказывают таблицей истинности или преобразованиями по тождествам.

В практике чаще всего помогают: нейтральные/поглощающие константы, идемпотентность, дополнение, поглощение, дистрибутивность, де Морган.

Стратегия обычно такая: сначала убрать очевидное (константы, повторы, с ), затем применить поглощение и вынесение общего множителя, и при необходимости переносить отрицания по де Моргану.