§ 21. Булевы функции

Определения и обозначения

Булева переменная — величина, принимающая только два значения: 0 и 1. Их связывают соответственно с ложью и истиной. Такая запись позволяет представить ответ на вопрос с двумя вариантами, например «включено или выключено», и выполнять над ним логические действия.

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

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

Логическая операция — правило получения нового высказывания или значения из одного либо нескольких исходных. К основным операциям относятся отрицание, конъюнкция и дизъюнкция. Они позволяют объединять простые условия в более сложные и точно определять, когда такое условие истинно.

Как это устроено

У булевой переменной только два значения, потому что она моделирует ситуацию с двумя взаимоисключающими ответами: условие выполнено или нет. Значение 1 обозначает истину, а 0 — ложь; это условное соглашение, удобное для вычислений и хранения информации. Поэтому с булевой переменной нельзя обращаться как с обычной числовой, у которой возможны, например, 2 или −1.

Функцию задают числом аргументов и результатом для каждого возможного набора их значений. У каждой из n переменных два варианта, и каждый вариант можно сочетать с каждым вариантом остальных переменных. Поэтому всего получается 2ⁿ наборов: например, для A и B это 2² = 4 набора. Если не указать результат хотя бы для одного набора, описание функции будет неполным.

Смысл операции подсказывает, как получить результат. Отрицание меняет значение на противоположное: из истины получается ложь и наоборот. Конъюнкция означает «и», поэтому она истинна лишь тогда, когда истинны оба условия; дизъюнкция означает «или» и истинна, если истинно хотя бы одно условие. Эти правила применяются к значениям 0 и 1, а не к привычному сложению или умножению чисел.

Чтобы составить таблицу истинности выражения, сначала выписывают все наборы аргументов без пропусков. Затем по каждому набору вычисляют выражение, при необходимости добавляя столбцы для промежуточных операций. Скобки показывают, какую часть нужно выполнить первой; в остальных случаях учитывают принятый порядок операций. Такой способ помогает видеть, откуда получился итог, и не смешивать этапы вычисления.

Одна и та же функция может быть задана формулой или таблицей: формула описывает правило, а таблица перечисляет все его результаты. Формула часто короче, но таблица наглядно показывает поведение функции при каждом входном наборе. Чтобы проверить, равносильны ли две формулы, вычисляют обе для одинаковых наборов аргументов. Совпадение всех результатов означает, что формулы задают одну функцию; одного совпавшего результата для такого вывода недостаточно.

Основные логические операции

При чтении таблицы проверяйте, какое условие делает каждую операцию равной 1. Для отрицания достаточно значения A, а для остальных операций нужно учитывать оба аргумента. Исключающее ИЛИ, в отличие от обычной дизъюнкции, не даёт 1, когда оба аргумента равны 1.

Разбор задач

Задача 1. Составить таблицу истинности функции F(A, B) = A ∧ ¬B. Переменных две, значит, нужно рассмотреть четыре набора. Удобно сначала вычислить ¬B, а затем выполнить конъюнкцию с A.

1. Запишем наборы A и B: 00, 01, 10, 11.
2. Для каждого набора найдём ¬B: 1, 0, 1, 0.
3. Вычислим A ∧ ¬B: 0 ∧ 1 = 0, 0 ∧ 0 = 0, 1 ∧ 1 = 1, 1 ∧ 0 = 0.

Ответ: значения F для наборов 00, 01, 10, 11 соответственно равны 0, 0, 1, 0. Единица появляется только при A = 1 и B = 0, поскольку оба аргумента итоговой конъюнкции тогда равны 1.

Задача 2. Для функции F(A, B, C) = (A ∨ B) ∧ ¬C определить значение при A = 0, B = 1, C = 0. В выражении есть скобки, поэтому сначала вычислим дизъюнкцию внутри них. После этого найдём отрицание C и объединим результаты конъюнкцией.

1. Вычислим A ∨ B: 0 ∨ 1 = 1.
2. Найдём ¬C: при C = 0 получаем ¬C = 1.
3. Выполним конъюнкцию: 1 ∧ 1 = 1.

Ответ: F(0, 1, 0) = 1. Промежуточные результаты показывают, что оба аргумента последней конъюнкции истинны, поэтому итог тоже равен 1.

Задача 3. Проверить, задают ли F(A, B) = A → B и G(A, B) = ¬A ∨ B одну и ту же функцию. Чтобы решить это, сравним значения формул на всех четырёх наборах. Для каждой строки отдельно применим правила импликации и дизъюнкции.

1. В порядке 00, 01, 10, 11 значения F равны 1, 1, 0, 1: импликация ложна только при A = 1 и B = 0.
2. Для тех же наборов ¬A равно 1, 1, 0, 0, а значения G = ¬A ∨ B равны 1, 1, 0, 1.
3. Сравним полученные последовательности: в каждой позиции стоит одинаковое значение.

Ответ: функции равносильны. Совпадение во всех четырёх строках показывает, что формулы задают одинаковый результат при любом наборе A и B.

Типичные ошибки

Ошибка: считать, что булева переменная может принимать любые числовые значения. Так происходит, когда обозначения 0 и 1 воспринимают просто как числа, а не как два логических состояния. Проверяйте, что каждый аргумент и результат выражения принадлежит только множеству {0, 1}; значение 2 в булевой переменной недопустимо.

Ошибка: путать конъюнкцию и дизъюнкцию. Обе операции объединяют два условия, поэтому их названия или обозначения легко смешать; однако конъюнкция истинна только при двух единицах, а дизъюнкция — уже при одной. Для самопроверки проверьте наборы 1, 0 и 1, 1: результаты операций на них различаются.

Ошибка: пропускать наборы аргументов при составлении таблицы. Иногда перечисляют лишь очевидные случаи или не замечают, что комбинации должны быть полными. Сначала вычислите число строк как 2ⁿ, затем проверьте, что каждый набор встретился ровно один раз; для трёх переменных должно быть восемь наборов.

Ошибка: вычислять составное выражение без скобок и порядка операций. Если выполнить действие не в том порядке, промежуточный результат изменится, а вместе с ним может измениться и вся функция. Отмечайте скобки и записывайте промежуточные столбцы; после вычисления проверьте, что каждый шаг соответствует структуре формулы.

Связь с другими темами

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

Что запомнить

• Булева переменная принимает только значения 0 и 1.
• Булева функция возвращает 0 или 1 для каждого набора аргументов.
• Для n переменных существует 2ⁿ наборов значений.
• Таблица истинности полностью задаёт булеву функцию.
• Конъюнкция истинна, только когда истинны оба аргумента.
• Дизъюнкция истинна, когда истинен хотя бы один аргумент.
• Функции равносильны, если совпадают на всех наборах аргументов.