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

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

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

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

• логических рассуждений в формальной логике
• схемотехники и цифровой электроники (логические элементы)
• булевых условий в программировании (if, фильтры, проверки)
• поиска и фильтрации данных (логические запросы)

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

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

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

• 0 — ложь (False)
• 1 — истина (True)

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

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

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

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

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

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

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

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

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

• И (AND)
• ИЛИ (OR)
• НЕ (NOT)

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

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

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

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

• $A$ — логическая переменная (0 или 1)
• $\lnot$ — знак отрицания (операция NOT)

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

A	$\lnot A$
0	1
1	0

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

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

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

Обозначение: $A \land B$, где:

• $A$, $B$ — логические переменные
• $\land$ — знак конъюнкции (операция AND)

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

A	B	$A \land B$
0	0	0
0	1	0
1	0	0
1	1	1

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

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

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

Обозначение: $A \lor B$, где:

• $A$, $B$ — логические переменные
• $\lor$ — знак дизъюнкции (операция OR)

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

A	B	$A \lor B$
0	0	0
0	1	1
1	0	1
1	1	1

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

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

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

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

• сначала вычислить $\lnot B$
• затем выполнить AND между $A$ и результатом $\lnot B$

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

A	B	$\lnot B$	$A \land (\lnot B)$
0	0	1	0
0	1	0	0
1	0	1	1
1	1	0	0

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

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

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

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

Закон	Для AND	Для OR
Коммутативность (перестановка)	$A \land B = B \land A$	$A \lor B = B \lor A$
Ассоциативность (группировка)	$(A \land B) \land C = A \land (B \land C)$	$(A \lor B) \lor C = A \lor (B \lor C)$

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

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

Закон	Формула
AND распределяется относительно OR	$A \land (B \lor C) = (A \land B) \lor (A \land C)$
OR распределяется относительно AND	$A \lor (B \land C) = (A \lor B) \land (A \lor C)$

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

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

Свойство	AND	OR
Нейтральный элемент	$A \land 1 = A$	$A \lor 0 = A$
Поглощение «краем»	$A \land 0 = 0$	$A \lor 1 = 1$

Интуиция:

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

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

Свойство	Формула
Идемпотентность	$A \land A = A$, $A \lor A = A$
Двойное отрицание	$\lnot(\lnot A) = A$

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

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

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

Формулировка	Формула
Отрицание AND превращается в OR отрицаний	$\lnot(A \land B) = (\lnot A) \lor (\lnot B)$
Отрицание OR превращается в AND отрицаний	$\lnot(A \lor B) = (\lnot A) \land (\lnot B)$

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

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

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

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

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

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

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

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

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

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

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

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

$F: \{0,1\}^n \to \{0,1\}$

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

• $F$ — имя функции (результат вычисления)
• $\{0,1\}$ — множество допустимых значений одной переменной: 0 (ложь) и 1 (истина)
• $n$ — число входных переменных (входов)
• $\{0,1\}^n$ — все возможные наборы из $n$ значений 0/1 (например, для двух переменных это пары $(0,0)$, $(0,1)$, $(1,0)$, $(1,1)$)
• $\to$ — «отображение»: каждому входному набору сопоставляется один выход (0 или 1)

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

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

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

• для 1 переменной: 2 набора (0 и 1)
• для 2 переменных: 4 набора
• для 3 переменных: 8 наборов

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

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

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

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

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

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

Пример: функция $F(A,B) = A \land \lnot B$.

• $A$ и $B$ — входные переменные
• $\lnot B$ — результат операции НЕ над $B$
• $A \land \lnot B$ — результат операции И между $A$ и $\lnot B$

A	B	$\lnot B$	$F = A \land \lnot B$
0	0	1	0
0	1	0	0
1	0	1	1
1	1	0	0

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

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

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

Примеры:

• $F(A) = \lnot A$
• $F(A,B) = A \lor B$
• $F(A,B,C) = (A \land B) \lor \lnot C$

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

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

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

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

Примеры:

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

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

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

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

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

• как выражение, например $F = (A \land B) \lor \lnot C$
• как схема с двумя входами в AND, одним инвертором для $C$, затем OR на выходе

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

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

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

• $(A,B) = (1,0)$
• $(A,B) = (1,1)$

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

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

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

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

• литерал — это либо переменная ($A$), либо её отрицание ($\lnot A$)

Как построить условие для набора $(1,0)$:

1. $A=1$ означает литерал $A$
2. $B=0$ означает литерал $\lnot B$
3. вместе: $A \land \lnot B$

Для набора $(1,1)$ условие: $A \land B$.

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

$F(A,B) = (A \land \lnot B) \lor (A \land B)$

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

• вынесем $A$ как общий множитель по дистрибутивности: $F = A \land (\lnot B \lor B)$
• $\lnot B \lor B = 1$ (это всегда истина)
• значит $F = A \land 1 = A$

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

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

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

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

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

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

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

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

$2^{2^n}$

Почему так:

• есть $2^n$ различных входных наборов
• на каждом наборе функция может независимо выбрать значение 0 или 1
• значит число способов заполнить столбец результатов длины $2^n$ равно $2^{2^n}$

Пример для $n=1$:

• входных наборов $2^1 = 2$ (0 и 1)
• функций $2^{2^1} = 2^2 = 4$

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

Главное

• Булева функция отображает наборы 0/1 входов в один выход 0/1.
• Функцию можно задавать таблицей истинности, выражением, словесным правилом, логической схемой или списком наборов, где она равна 1.
• Эквивалентность функций означает совпадение результатов на всех входах; её проверяют таблицей истинности или преобразованиями по законам булевой алгебры.

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

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

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

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

• в программировании (проверки вида not condition или !condition)
• в логических схемах (инвертор)
• в преобразованиях выражений (например, законы де Моргана)

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

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

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

Запись: $\lnot A$

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

• $A$ — булева переменная, то есть принимает значение 0 или 1
• $\lnot$ — знак отрицания (операция NOT)
• $\lnot A$ — результат отрицания $A$

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

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

A	$\lnot A$
0	1
1	0

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

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

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

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

• $A=1$ (истина), то $\lnot A=0$ (ложь)
• $A=0$ (ложь), то $\lnot A=1$ (истина)

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

Отрицать можно не только переменную, но и целое выражение, например $\lnot(A \land B)$ или $\lnot(A \lor B)$. В таких случаях важно помнить:

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

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

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

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

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

$$\lnot(\lnot A)=A$$

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

• $A$ — исходная булева переменная
• $\lnot A$ — отрицание $A$
• $\lnot(\lnot A)$ — отрицание результата $\lnot A$

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

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

• $\lnot 0 = 1$
• $\lnot 1 = 0$

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

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

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

• $A \lor \lnot A = 1$
• $A \land \lnot A = 0$

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

• выражение $A \lor \lnot A$ истинно всегда, потому что либо истинно $A$, либо истинно его отрицание
• выражение $A \land \lnot A$ ложно всегда, потому что невозможно, чтобы $A$ и одновременно не-$A$ были истинны

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

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

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

• убирать «лишние» отрицания (через двойное отрицание)
• переносить отрицание внутрь/наружу скобок, меняя операции AND/OR по законам де Моргана

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

• $\lnot(A \land B) = (\lnot A) \lor (\lnot B)$
• $\lnot(A \lor B) = (\lnot A) \land (\lnot B)$

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

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

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

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

• !A (часто в C-подобных языках)
• not A (например, в Python)

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

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

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

Главное

• NOT — унарная операция: она применяется к одному аргументу.
• Таблица истинности NOT: $0 \to 1$, $1 \to 0$.
• Ключевые свойства: $\lnot(\lnot A)=A$, $\lnot 0=1$, $\lnot 1=0$, а также $A \lor \lnot A = 1$ и $A \land \lnot A = 0$.
• Для отрицания выражений в скобках используют законы де Моргана: отрицание «переворачивает» AND/OR и добавляет отрицание каждому аргументу.

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

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

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

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

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

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

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

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

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

Запись: $A \land B$

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

• $A$ — первая булева переменная (может быть 0 или 1)
• $B$ — вторая булева переменная (может быть 0 или 1)
• $\land$ — знак операции И (AND)
• $A \land B$ — результат операции AND над $A$ и $B$

Смысл:

• $A \land B = 1$ только если $A=1$ и $B=1$
• иначе $A \land B = 0$

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

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

A	B	$A \land B$
0	0	0
0	1	0
1	0	0
1	1	1

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

• строка $(0,1)$ означает «$A=0$, $B=1$»
• в этой строке $A \land B=0$, потому что не выполняется условие «оба равны 1»

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

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

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

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

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

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

• $A \land B \land C$ читается как «$A$ и $B$ и $C$»

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

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

• $(A \land B) \land C = A \land (B \land C)$

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

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

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

$$A \land B = B \land A$$

Пояснение:

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

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

$$(A \land B) \land C = A \land (B \land C)$$

Пояснение:

• слева сначала вычисляется $A \land B$, затем результат AND с $C$
• справа сначала вычисляется $B \land C$, затем AND с $A$
• в обоих случаях итог равен 1 тогда и только тогда, когда $A=1$, $B=1$ и $C=1$

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

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

$$A \land 1 = A$$

Пояснение:

• $1$ означает «истина»
• условие «$A$ и истина» эквивалентно просто «$A$»

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

$$A \land 0 = 0$$

Пояснение:

• $0$ означает «ложь»
• условие «$A$ и ложь» никогда не выполнится

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

$$A \land A = A$$

Пояснение:

• «$A$ и $A$» не добавляет нового ограничения
• если $A=1$, то результат 1; если $A=0$, то результат 0

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

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

$$A \land \lnot A = 0$$

Пояснение:

• $\lnot A$ означает «не $A$» (операция NOT из предыдущей статьи)
• невозможно, чтобы одновременно выполнялись «$A$ истинно» и «$A$ ложно»

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

$$A \land (B \lor C) = (A \land B) \lor (A \land C)$$

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

• $\lor$ — операция ИЛИ (OR)
• запись $B \lor C$ означает «$B$ истинно или $C$ истинно (или оба)»

Интуиция:

• слева: «$A$ истинно и при этом истинно хотя бы одно из $B$ или $C$»
• справа: «либо $A$ и $B$, либо $A$ и $C$»

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

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

$$A \land (A \lor B) = A$$

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

• если $A=0$, то слева $0 \land (0 \lor B) = 0 \land B = 0$, справа тоже 0
• если $A=1$, то слева $1 \land (1 \lor B) = 1 \land 1 = 1$, справа тоже 1

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

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

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

$$F(A,B) = A \land \lnot B$$

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

• $\lnot B$ — отрицание $B$
• $A \land \lnot B$ — AND между $A$ и результатом $\lnot B$

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

A	B	$\lnot B$	$F = A \land \lnot B$
0	0	1	0
0	1	0	0
1	0	1	1
1	1	0	0

По этой таблице видно: $F=1$ только в случае $A=1$ и $B=0$.

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

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

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

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

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

Главное

• AND (конъюнкция) возвращает 1 только если оба аргумента равны 1.
• Таблица истинности полностью задаёт поведение операции.
• Ключевые тождества AND: коммутативность, ассоциативность, нейтральный элемент $1$, поглощающее значение $0$, идемпотентность, комплементарность $A \land \lnot A = 0$, дистрибутивность относительно OR и поглощение.
• Эти свойства — основа для упрощения булевых выражений и анализа булевых функций.

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

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

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

• что булевы переменные принимают только значения 0 и 1
• что отрицание задаётся операцией НЕ
• что операция И требует одновременной истинности условий

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

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

• «Сигнал тревоги включается, если сработал датчик дыма или датчик температуры»
• «Доступ разрешён, если пользователь — админ или введён одноразовый код»

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

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

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

Запись: $A \lor B$

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

• $A$ — первая булева переменная (может быть $0$ или $1$)
• $B$ — вторая булева переменная (может быть $0$ или $1$)
• $\lor$ — знак операции ИЛИ (OR)
• $A \lor B$ — результат применения OR к $A$ и $B$

Смысл:

• $A \lor B = 1$, если хотя бы одно из значений $A$ или $B$ равно $1$
• $A \lor B = 0$ только тогда, когда $A=0$ и $B=0$

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

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

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

A	B	$A \lor B$
0	0	0
0	1	1
1	0	1
1	1	1

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

• строка $A=0$, $B=1$ даёт $A \lor B = 1$, потому что второе условие истинно
• единственный случай, когда результат $0$, это $A=0$ и $B=0$

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

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

• если в выражении $A \lor B$ уже известно, что $A=1$, то весь результат равен $1$ независимо от $B$
• если $A=0$, то результат полностью определяется $B$ (потому что $0 \lor B = B$)

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

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

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

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

$$A \lor B = B \lor A$$

Пояснение:

• слева и справа участвуют одни и те же значения $A$ и $B$
• порядок аргументов не влияет на факт “есть ли хотя бы одна единица”

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

$$(A \lor B) \lor C = A \lor (B \lor C)$$

Пояснение:

• $A$, $B$, $C$ — булевы переменные
• скобки меняют порядок вычислений, но смысл тот же: результат $1$, если хотя бы одна из переменных равна $1$

Это позволяет писать без скобок: $A \lor B \lor C$.

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

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

$$A \lor 0 = A$$

Пояснение:

• $0$ означает “ложь”
• “$A$ или ложь” эквивалентно просто “$A$”

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

$$A \lor 1 = 1$$

Пояснение:

• $1$ означает “истина”
• “что угодно или истина” всегда истинно

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

$$A \lor A = A$$

Пояснение:

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

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

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

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

$$A \lor \lnot A = 1$$

Пояснение:

• либо $A$ истинно, либо истинно “не $A$”
• третьего не дано, поэтому результат всегда $1$

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

• $\lnot(A \lor B) = (\lnot A) \land (\lnot B)$

Пояснение:

• слева отрицание применяется ко всему выражению “$A$ или $B$”
• справа операция меняется с OR на AND, и каждое из условий получает отрицание

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

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

$$A \lor (B \land C) = (A \lor B) \land (A \lor C)$$

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

• $\land$ — операция И (AND)
• $B \land C$ означает “$B$ и $C$ одновременно”

Интуиция:

• слева: “истинно $A$, или истинны сразу $B$ и $C$”
• справа: “одновременно выполнено: (истинно $A$ или $B$) и (истинно $A$ или $C$)”

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

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

$$A \lor (A \land B) = A$$

Пояснение:

• если $A=1$, то слева уже истинно (неважно, что с $B$), и результат $1$
• если $A=0$, то $A \land B=0$, значит слева $0 \lor 0 = 0$

Итог: выражение всегда равно $A$, а часть $(A \land B)$ оказывается лишней.

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

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

$F(A,B) = A \lor \lnot B$

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

• $\lnot B$ — отрицание $B$
• $A \lor \lnot B$ — операция OR между $A$ и “не $B$”

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

A	B	$\lnot B$	$F = A \lor \lnot B$
0	0	1	1
0	1	0	0
1	0	1	1
1	1	0	1

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

• единственный случай, когда $F=0$, это $A=0$ и $B=1$
• во всех остальных случаях хотя бы одно из условий “$A$” или “не $B$” истинно

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

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

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

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

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

Главное

• OR (дизъюнкция) возвращает $1$, если хотя бы один аргумент равен $1$.
• Таблица истинности OR имеет единственный нулевой случай: $0 \lor 0 = 0$.
• Ключевые тождества OR: коммутативность, ассоциативность, нейтральный элемент $0$, поглощающее значение $1$, идемпотентность, комплементарность $A \lor \lnot A = 1$, дистрибутивность относительно AND и поглощение $A \lor (A \land B)=A$.
• Связь с отрицанием часто выражают через законы де Моргана: $\lnot(A \lor B) = \lnot A \land \lnot B$.

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

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

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

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

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

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

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

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

Когда мы пишем, например, $A \lor 0 = A$, это значит:

• $A$ — булева переменная (может быть $0$ или $1$)
• $0$ — булева константа (ложь)
• выражение слева и выражение справа всегда дают одинаковый результат

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

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

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

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

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

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

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

• Для AND:

$$A \land B = B \land A$$

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

• Для OR:

$$A \lor B = B \lor A$$

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

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

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

• Для AND:

$$(A \land B) \land C = A \land (B \land C)$$

• Для OR:

$$(A \lor B) \lor C = A \lor (B \lor C)$$

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

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

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

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

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

$$A \land 1 = A$$

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

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

$$A \lor 0 = A$$

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

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

$$A \land 0 = 0$$

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

$$A \lor 1 = 1$$

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

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

• Для AND:

$$A \land A = A$$

• Для OR:

$$A \lor A = A$$

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

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

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

$$\lnot(\lnot A) = A$$

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

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

$$A \lor \lnot A = 1$$

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

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

$$A \land \lnot A = 0$$

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

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

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

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

$$A \land (B \lor C) = (A \land B) \lor (A \land C)$$

Слева: сначала вычисляется $B \lor C$, потом результат объединяется с $A$ через $\land$.

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

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

$$A \lor (B \land C) = (A \lor B) \land (A \lor C)$$

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

Поглощение

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

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

$$A \lor (A \land B) = A$$

Почему это работает: если $A=1$, то слева уже истинно; если $A=0$, то $(A \land B)=0$.

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

$$A \land (A \lor B) = A$$

Почему это работает: если $A=0$, слева $0$; если $A=1$, то $(A \lor B)=1$.

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

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

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

$$\lnot(A \land B) = (\lnot A) \lor (\lnot B)$$

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

$$\lnot(A \lor B) = (\lnot A) \land (\lnot B)$$

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

• меняется операция: $\land \leftrightarrow \lor$
• каждое выражение внутри скобок получает отрицание

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

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

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

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

• убрать константы через нейтральные и поглощающие значения
• убрать повторы через идемпотентность
• использовать дополнение ($A \lor \lnot A = 1$, $A \land \lnot A = 0$)
• применять поглощение, чтобы избавиться от «лишних» частей
• раскрывать и собирать скобки через дистрибутивность
• переносить отрицания внутрь/наружу через де Моргана, когда так проще

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

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

$$F(A,B) = (A \land B) \lor (A \land \lnot B)$$

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

• $F(A,B)$ — булева функция от двух переменных
• $A \land B$ и $A \land \lnot B$ — два условия, объединённые через OR ($\lor$)

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

$$(A \land B) \lor (A \land \lnot B) = A \land (B \lor \lnot B)$$

Шаг 2: применим дополнение $B \lor \lnot B = 1$.

$$A \land (B \lor \lnot B) = A \land 1$$

Шаг 3: применим нейтральный элемент для AND: $A \land 1 = A$.

Итог:

$$F(A,B) = A$$

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

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

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

$$G(A,B) = \lnot(A \lor (B \land \lnot B))$$

Шаг 1: заметим, что $(B \land \lnot B)=0$ по комплементарности.

$$G = \lnot(A \lor 0)$$

Шаг 2: $A \lor 0 = A$ (нейтральный элемент для OR).

$$G = \lnot A$$

Итог: $G(A,B)$ не зависит от $B$ и равна просто отрицанию $A$.

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

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

Например, проверим тождество поглощения $A \lor (A \land B) = A$.

$A$	$B$	$A \land B$	$A \lor (A \land B)$	$A$
0	0	0	0	0
0	1	0	0	0
1	0	0	1	1
1	1	1	1	1

Столбцы $A \lor (A \land B)$ и $A$ совпадают во всех строках, значит равенство — тождество.

Главное

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

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

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

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

• что такое булевы значения $0$ и $1$
• что такое булева функция
• операции НЕ ($\lnot$), И ($\land$), ИЛИ ($\lor$)
• основные тождества булевой алгебры (коммутативность, ассоциативность, дистрибутивность, поглощение, де Морган и т.д.)

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

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

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

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

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

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

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

• выписываем все $2^n$ наборов входов для $n$ переменных
• считаем значения левой и правой частей
• если столбцы результатов совпадают во всех строках — выражения эквивалентны

Плюсы:

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

Минусы:

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

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

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

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

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

Плюсы:

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

Минусы:

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

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

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

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

• $A \land 1 = A$
• $A \lor 0 = A$
• $A \land 0 = 0$
• $A \lor 1 = 1$

Здесь:

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

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

• $A \land A = A$, $A \lor A = A$
• $A \land \lnot A = 0$
• $A \lor \lnot A = 1$

Здесь $\lnot A$ означает “не $A$”.

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

• $A \lor (A \land B) = A$
• $A \land (A \lor B) = A$

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

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

• $A \land (B \lor C) = (A \land B) \lor (A \land C)$
• $A \lor (B \land C) = (A \lor B) \land (A \lor C)$

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

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

• $\lnot(A \land B) = (\lnot A) \lor (\lnot B)$
• $\lnot(A \lor B) = (\lnot A) \land (\lnot B)$

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

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

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

1. Упростить очевидные места с константами $0$ и $1$.
2. Убрать повторы ($A \land A$, $A \lor A$).
3. Найти пары вида $X \lor \lnot X$ или $X \land \lnot X$.
4. Применить поглощение (часто это “мгновенный выигрыш”).
5. Если есть похожие слагаемые, попробовать вынести общий множитель дистрибутивностью.
6. Если мешает отрицание над скобками, применить де Моргана.

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

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

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

$$F(A,B) = (A \land B) \lor (A \land \lnot B)$$

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

• $F(A,B)$ — булева функция от двух переменных $A$ и $B$
• $\land$ — операция И
• $\lor$ — операция ИЛИ
• $\lnot B$ — отрицание переменной $B$

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

$$(A \land B) \lor (A \land \lnot B) = A \land (B \lor \lnot B)$$

Шаг 2: применим тождество дополнения $B \lor \lnot B = 1$:

$$A \land (B \lor \lnot B) = A \land 1$$

Шаг 3: нейтральный элемент для AND: $A \land 1 = A$.

Итог:

$$F(A,B) = A$$

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

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

Упростим:

$$G(A,B) = A \lor (A \land B)$$

Здесь:

• $A$, $B$ — булевы переменные
• $G(A,B)$ — результат выражения

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

$$A \lor (A \land B) = A$$

Итог:

$$G(A,B) = A$$

Интуиция: если $A=1$, то слева уже истина; если $A=0$, то $(A \land B)=0$ и всё равно получаем $0$.

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

Упростим:

$$H(A,B,C) = \lnot\bigl(A \lor (B \land C)\bigr)$$

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

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

$$\lnot\bigl(A \lor (B \land C)\bigr) = (\lnot A) \land \lnot(B \land C)$$

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

$$\lnot(B \land C) = (\lnot B) \lor (\lnot C)$$

Подставим:

$$H = (\lnot A) \land \bigl((\lnot B) \lor (\lnot C)\bigr)$$

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

$$(\lnot A) \land ((\lnot B) \lor (\lnot C)) = ((\lnot A) \land (\lnot B)) \lor ((\lnot A) \land (\lnot C))$$

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

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

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

$$K = A \land (B \lor C)$$

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

$$K = (A \land B) \lor (A \land C)$$

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

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

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

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

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

$$A \lor (A \land B) = A$$

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

$A$	$B$	$A \land B$	$A \lor (A \land B)$	$A$
0	0	0	0	0
0	1	0	0	0
1	0	0	1	1
1	1	1	1	1

Столбцы $A \lor (A \land B)$ и $A$ совпадают во всех строках, значит равенство верно для любых $A$ и $B$.

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

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

• Для читаемости в логике/коде часто лучше факторизованная форма, например $A \land (B \lor C)$.
• Для реализации схемой может быть выгодно минимизировать число элементов AND/OR/NOT.
• Для сравнения функций полезно привести к стандартной форме и сверить (в дальнейшем в курсах часто используют формы “сумма произведений” и “произведение сумм”).

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

Главное

• Эквивалентность булевых выражений доказывают таблицей истинности или преобразованиями по тождествам.
• В практике чаще всего помогают: нейтральные/поглощающие константы, идемпотентность, дополнение, поглощение, дистрибутивность, де Морган.
• Стратегия обычно такая: сначала убрать очевидное (константы, повторы, $X$ с $\lnot X$), затем применить поглощение и вынесение общего множителя, и при необходимости переносить отрицания по де Моргану.