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

Число булевых функций от переменных равно . В показателе здесь стоит не , а число всех возможных входных наборов. Для каждой строки таблицы истинности можно независимо выбрать результат: ноль или единицу. Например, две переменные дают четыре строки, а значит, разных функций.
Попробуйте изменить число переменных в калькуляторе: он покажет оба этапа подсчёта. Затем разберём, почему разные формулы не всегда задают разные функции и как считать функции с дополнительными условиями.
Что считается булевой функцией
Булева функция каждому упорядоченному набору из нулей и единиц сопоставляет одно значение, тоже равное или . Коротко это записывают так: . Переменные можно понимать как логические значения «ложь» и «истина», но для подсчёта достаточно двух символов.
Функция определена полностью, когда указан результат на каждом входном наборе. Поэтому таблица истинности - не просто способ проверить отдельные примеры: её столбец результатов однозначно задаёт функцию. Две записи описывают одну функцию, если значения совпадают во всех строках, даже когда формулы выглядят по-разному.
Например, и - две записи одной функции: перестановка аргументов конъюнкции не меняет ни одного результата. А и различаются уже на наборе , поэтому это разные функции.
Сначала считаем входные наборы
У каждой из переменных два возможных значения. Чтобы составить набор, выбираем значение первой переменной, затем второй и так далее. По правилу произведения число упорядоченных наборов равно
При получаем , , и . Их именно четыре: наборы и различны, поскольку позиции переменных фиксированы. При к каждому из четырёх наборов можно дописать ноль или единицу - получится восемь строк.
Важно не останавливаться на : это число входных наборов, а не число функций. В каждой из полученных строк ещё предстоит выбрать значение .
Затем считаем столбцы значений
Зафиксируем порядок строк. На первом наборе функция может принимать два значения. Независимо от этого на втором наборе снова есть два выбора; так продолжается для всех строк. Следовательно, число возможных столбцов равно
Каждый такой столбец действительно задаёт функцию: у каждой строки ровно одно значение. Два разных столбца различаются хотя бы в одной строке и задают разные функции. Мы установили взаимно однозначное соответствие между функциями и двоичными столбцами длины : ничего не пропущено и ничего не посчитано дважды.
Тот же результат получается через множества. Каждой функции соответствует множество входов, на которых она равна единице. Любое подмножество множества из наборов допустимо, а таких подмножеств . Связь функций с подмножествами и двоичными последовательностями помогает понять и теорему Кантора о мощности множества.
Примеры для небольшого числа переменных
| Число переменных | Наборов | Функций |
|---|---|---|
| 0 | 1 | 2 |
| 1 | 2 | 4 |
| 2 | 4 | 16 |
| 3 | 8 | 256 |
| 4 | 16 | 65 536 |
| 5 | 32 | 4 294 967 296 |

Случай может показаться необычным. Нулевых переменных нет, но есть ровно один пустой набор; на нём функция выбирает одно из двух значений. Поэтому нульместных булевых функций две: константы и .
При одной переменной столбец имеет две позиции. Возможны , , и : это соответственно константа , функция , отрицание и константа , если строки идут в порядке . Для двух переменных столбцов уже шестнадцать; среди них конъюнкция, дизъюнкция и исключающее И.
Подробный пример: две переменные
Рассмотрим конкретный столбец значений для входов, выписанных в порядке от нулевого набора к единичному:
| Входной набор | Значение функции |
|---|---|
| 0 | |
| 1 | |
| 1 | |
| 0 |
Этот столбец задаёт исключающее И: результат равен единице, когда значения переменных различны. Поменяем только последнее значение с нуля на единицу. Теперь получим столбец дизъюнкции: она равна единице, когда хотя бы одна переменная равна единице. Остальные три строки сохранились, но функции уже различны, поскольку на последнем входе ответы не совпадают.
Теперь представим, что ни одно значение не задано заранее. На первой строке есть два решения; каждому соответствует два решения для второй строки. Уже получаются четыре частично заполненных столбца. После третьей строки их восемь, а после четвёртой - шестнадцать. На каждом шаге мы удваиваем количество частичных таблиц, а не увеличиваем число входных наборов. Такой последовательный подсчёт удобен, если сложно сразу увидеть степень.
Можно проверить ответ и перечислением. Двоичные столбцы длины четыре идут от до . Если читать их как двоичные записи чисел, это все значения от нуля до пятнадцати включительно, всего шестнадцать. Начальные нули при этом обязательны: столбцы и имеют одинаковую длину, но описывают разные функции.
Как проверить решение задачи
Сначала выпишите, что именно требует условие: число входов, таблиц значений или функций с ограничениями. Затем отдельно отметьте число строк и количество разрешённых значений в каждой. Если значения строк независимы, перемножьте числа вариантов; если условие связывает строки между собой, простое произведение может уже не работать.
Полезно также проверить крайние случаи. Когда все строки заранее заполнены без противоречий, допустима ровно одна функция. Когда зафиксирована только часть строк, каждому заполнению оставшихся строк соответствует одна функция. А требование «ровно две единицы» связывает выборы: поставив две единицы, остальные места нужно заполнить нулями. Поэтому здесь подходит выбор двух позиций, а не степень двойки.
Наконец, не заменяйте переменные входными наборами. Дополнительная переменная создаёт новые строки, но каждая новая строка всё ещё имеет лишь два возможных результата. Разделение этих двух уровней делает вывод надёжным и для больших значений, когда перечислить таблицы уже невозможно.
Почему рост такой быстрый
Когда добавляется переменная, каждый старый входной набор разделяется надвое: новая переменная равна либо нулю, либо единице. Значит, число строк удваивается. Можно независимо задать поведение функции на двух половинах таблицы, поэтому
Например, . Ещё одно увеличение даёт . Это согласуется с общей формулой и показывает, почему рост называют дважды экспоненциальным: показатель степени сам растёт экспоненциально.
График в калькуляторе показывает не само , а . Так значения от до остаются различимыми; высота столбца равна числу строк таблицы истинности. Для точного количества смотрите числовой результат над графиком.
Какие функции входят в подсчёт
Формула считает все отображения , включая константы и функции, которые игнорируют некоторые аргументы. Например, считается функцией двух указанных переменных, хотя изменение не влияет на её результат. Переменная называется существенной, если существует набор остальных аргументов, при котором её переключение меняет результат.
Если условие требует существенной зависимости от обеих переменных, ответ уже не 16. Из всех 16 исключим две функции, зависящие только от и не являющиеся константами, две аналогичные функции от и две константы. Остаётся . Здесь удобно считать непересекающиеся категории: константы не следует вычитать дважды.
Общая формула также не считает число синтаксических выражений. К одной таблице можно построить много равносильных формул, в том числе добавляя избыточные операции. Например, СДНФ по таблице истинности даёт систематическую запись функции, а не новую функцию для каждого способа записи.
Задачи с ограничениями на значения
Дополнительное условие уменьшает число свободных выборов. Если значения на различных входных наборах заранее зафиксированы и не противоречат друг другу, остаётся свободных строк. Ответ равен
Пусть функция трёх переменных должна равняться нулю на наборе . Всего строк восемь, одна заполнена, семь свободны: получаем функций. Если задано ровно два единичных значения, выбирать нужно уже не сами значения по строкам, а позиции единиц. Число вариантов равно .
Эти задачи отличаются от вопроса о том, какие функции можно выразить заданным набором операций. Для него важны свойства операций и классы Поста. Например, штрих Шеффера позволяет выразить все булевы функции, но это свойство базиса, а не дополнительный множитель в формуле подсчёта.
Частые ошибки
- Отвечать . Это количество входных наборов; для каждого ещё выбирается результат.
- Писать . В показателе нужно , а не . При ответы случайно совпадают, поэтому проверяйте также .
- Считать формулы вместо функций. Равносильные выражения имеют одинаковую таблицу и учитываются один раз.
- Исключать константы без условия. Они входят в общее число, как и функции с несущественными переменными.
- Игнорировать фиксированные строки. Для них выбор уже сделан; независимые варианты остаются только в остальных строках.
FAQ
Сколько булевых функций от трёх переменных?
Восемь входных наборов и два выбора на каждом дают функций.
Почему у функций от нуля переменных есть входной набор?
Декартова степень с нулевым числом множителей содержит один элемент - пустой кортеж. На нём можно задать ноль или единицу, поэтому функций две.
Сколько функций равно единице ровно на наборах?
Нужно выбрать строк из : ответ при . Каждому выбору соответствует ровно одна функция.
Коротко
При булевых переменных есть входных наборов. Независимый выбор нуля или единицы на каждом даёт функций. Для задач с условиями сначала выделяйте свободные строки или выбирайте позиции единиц, а различные записи одной функции не считайте повторно.
Читайте также

Декартово произведение множеств: примеры и формула
Декартово произведение множеств: что такое упорядоченная пара, как перечислить все элементы A x B, найти мощность и применить к координатной плоскости - с разбором типовых задач.

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

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

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

Булев куб: вершины, рёбра и расстояние Хэмминга
Булев куб простыми словами: как двоичные наборы становятся вершинами, когда они соседствуют, сколько в кубе рёбер и как найти расстояние между вершинами.

Мажоритарная функция: формула и таблица истинности
Мажоритарная функция определяет результат по большинству двоичных входов. Разбираем таблицу истинности, формулу для трёх переменных, порог и применение в схемах.