Разложение Шеннона: формула и пример для булевой функции

Булеву функцию можно изучать по частям: сначала выяснить, чему она равна при , а затем при . Разложение Шеннона собирает эти два результата обратно в исходную функцию. Приём помогает переходить от формулы или таблицы истинности к цифровой схеме и дереву решений.
Ниже калькулятор начинает с функции большинства трёх переменных. Измените любое значение в таблице, выберите переменную и сравните две получившиеся строки. Для исходного примера они различаются на двух наборах из четырёх.
Формула разложения по переменной
Для булевой функции , где обозначает остальные переменные, разложение по имеет вид
Здесь черта означает НЕ, соседство множителей - И, а - ИЛИ. Выражения и называют остаточными функциями, или кофакторами: в исходной функции переменную фиксируют соответственно нулём и единицей. В каждом остатке могут сохраниться все остальные переменные или только некоторые из них. Иногда остаток оказывается константой.
Формула верна для любой булевой функции и любой выбранной входной переменной. Её записывают также через знак для ИЛИ и точку для И. Это операции булевой алгебры: например, . Обозначения важно согласовать до вычислений, особенно когда в условии смешаны несколько систем записи. Такое представление и его связь с мультиплексором приведены в конспекте Oakland University.
На видео выбор переключает ветвь при фиксированных и . Значения обеих остаточных функций уже известны, а выбранная ветвь определяет выход.
Почему равенство работает
Достаточно проверить два возможных значения . При имеем : первое слагаемое равно , а второе обнуляется. Это и есть значение исходной функции при нулевом входе. При первое слагаемое равно нулю, второе - . Других значений у булевой переменной нет, поэтому равенство выполнено для каждого набора остальных входов.
Такой разбор по случаям одновременно даёт практический алгоритм. Выберите переменную, подставьте в исходное выражение ноль, упростите его по правилам булевой алгебры. Затем отдельно подставьте единицу и упростите второй остаток. Умножьте первый на отрицание выбранной переменной, второй - на саму переменную и соедините результаты операцией ИЛИ. Приоритет операций и расстановка скобок разобраны отдельно в статье о приоритете логических операций.
Если функция задана таблицей, подстановка превращается в отбор строк. Для оставьте строки с нулём в столбце , а для - строки с единицей. В обеих группах расположите остальные переменные в одном и том же порядке. Иначе одинаковые позиции двух остатков будут соответствовать разным входам, и сравнение окажется неверным.
Пример: функция большинства трёх входов
Пусть единица появляется, если хотя бы два из трёх входов равны единице:
Это мажоритарная функция. Разложим её по . При первые два произведения исчезают, поэтому . При получаем : последнее слагаемое поглощается двумя предыдущими.
Следовательно,
Смысл выражения легко проверить словами. Если , для большинства нужны одновременно и . Если , достаточно хотя бы одной единицы среди двух оставшихся входов. Например, для активна вторая ветвь: , значит, . Для активна первая: , значит, .
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 |

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

Минимизация булевой функции: карта Карно
Как построить карту Карно по таблице истинности, объединить соседние клетки и получить минимальную ДНФ. Подробный пример для трёх переменных и интерактивная проверка.

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

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

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

СДНФ: совершенная дизъюнктивная нормальная форма
СДНФ функции: как по таблице истинности выделить минтермы, собрать их в дизъюнкцию элементарных конъюнкций и проверить результат на интерактивном калькуляторе с готовыми примерами.

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