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

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

Булева функция — функция, аргументы и значение которой принимают только значения 0 или 1. Она описывает зависимость результата от двоичных условий. Такое описание нужно для анализа логики программ, электронных схем и высказываний.

Булевы переменные — переменные, принимающие значения 0 или 1 и используемые как аргументы булевой функции. Например, x = 1 может означать выполнение условия, а x = 0 — его невыполнение. С помощью таких переменных записывают исходные данные логической задачи.

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

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

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

Если функция имеет n двоичных аргументов, каждый аргумент может независимо принять 0 или 1. Для первого аргумента есть два выбора, для второго — ещё два, поэтому общее число комбинаций равно 2 · 2 · ... · 2 = 2ⁿ. Именно поэтому таблица истинности функции от n переменных содержит конечное число строк: по одной строке для каждого набора.

Операция НЕ работает с одним значением и меняет его на противоположное: НЕ 0 = 1, НЕ 1 = 0. Операция И объединяет два условия и даёт 1 только при одновременной истинности обоих. Операция ИЛИ даёт 1, если хотя бы одно из условий равно 1, поэтому из этих трёх операций можно строить выражения почти любой нужной сложности.

Чтобы вычислить составную функцию, сначала выписывают значения переменных в конкретном наборе. Затем выполняют действия внутри скобок, после чего переходят к оставшимся операциям с учётом приоритета: сначала НЕ, затем И, затем ИЛИ. Промежуточные результаты лучше записывать в отдельные столбцы, чтобы не потерять порядок вычислений и легче заметить ошибку.

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

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

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

Разбор задач

1. Построение таблицы истинности

Условие: построить таблицу истинности функции F = (x И y) ИЛИ НЕ z. В формуле три переменные, поэтому нельзя ограничиться несколькими удобными примерами. Нужно проверить все возможные сочетания их значений.

1. Записываем восемь наборов x, y, z: от 000 до 111.
2. Для каждого набора вычисляем столбец x И y.
3. Отдельно находим НЕ z, а затем применяем ИЛИ к двум промежуточным результатам.
4. Например, для 101 получаем x И y = 0, НЕ z = 0, поэтому F = 0. Для 110 получаем x И y = 1, НЕ z = 1, поэтому F = 1.

Ответ: итоговый столбец строится после двух промежуточных столбцов, а таблица содержит ровно 8 строк. Полностью его значения: 1, 0, 1, 0, 1, 1, 1, 1 для наборов 000, 001, 010, 011, 100, 101, 110, 111.

2. Проверка равенства двух формул

Условие: определить, задают ли одну функцию формулы F = x ИЛИ (y И z) и G = (x ИЛИ y) И (x ИЛИ z). Скобки показывают разные пути вычисления, поэтому внешний вид формул ответа не даёт.

1. Составляем восемь наборов переменных x, y, z.
2. Для F сначала вычисляем y И z, затем объединяем результат с x.
3. Для G находим x ИЛИ y и x ИЛИ z, после чего применяем И к этим столбцам.
4. Сравниваем последние столбцы. На каждом наборе они совпадают, значит, формулы равносильны.

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

3. Построение формулы по таблице

Условие: по заданной таблице истинности составить формулу функции. Например, пусть единицы стоят в строках 001 и 110 для переменных x, y, z. Каждая такая строка должна быть отдельно описана условием, при котором функция равна 1.

1. Для строки 001 записываем x = 0, y = 0, z = 1, то есть НЕ x И НЕ y И z.
2. Для строки 110 записываем x = 1, y = 1, z = 0, то есть x И y И НЕ z.
3. Объединяем полученные условия операцией ИЛИ: F = (НЕ x И НЕ y И z) ИЛИ (x И y И НЕ z).
4. Проверяем формулу по всем строкам: в выбранных двух строках она даёт 1, в остальных — 0.

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

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

Частая ошибка — воспринимать 0 и 1 как обычные числа и складывать или умножать их вместо применения И и ИЛИ. Так происходит из-за похожести обозначений, но смысл операций другой. Проверка: сверяйте результат с правилами — И даёт 1 только при двух единицах, а ИЛИ даёт 0 только при двух нулях.

Некоторые пропускают наборы аргументов в таблице. Причина обычно в невнимательном перечислении комбинаций, особенно при трёх и более переменных. Проверяйте себя формулой 2ⁿ и удобно располагайте наборы как двоичный счёт от 00...0 до 11...1.

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

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

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

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

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

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

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