EssayAI
Блог
Блог
Естественные науки

Мажоритарная функция: формула и таблица истинности

8 ноября 2026Время чтения: 9 минут
#мажоритарная функция#булева функция#таблица истинности#логические элементы#дискретная математика
Мажоритарная функция: формула и таблица истинности

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

Определение и порог большинства

Пусть каждый вход xix_i принимает значение 00 или 11, а всего входов nn. Обозначим количество единиц через k=x1+⋯+xnk=x_1+\dots+x_n. Для строгого большинства определим

Mn(x1,…,xn)={1,k>n/2,0,k≤n/2.M_n(x_1,\dots,x_n)=\begin{cases}1,&k>n/2,\\0,&k\leq n/2.\end{cases}

Иными словами, порог равен ⌊n/2⌋+1\lfloor n/2\rfloor+1: единиц должно быть больше половины, а не просто половина. Для трёх входов порог равен двум, для пяти - трём, для семи - четырём. Сумма здесь обычная арифметическая: например, 1+1+1=31+1+1=3, а не сложение по модулю два.

Число единиц среди пяти входов растёт от нуля до пяти и снова уменьшается: выход меняется при переходе через порог в три единицы.

При нечётном nn ничьи не бывает: значение большинства всегда либо 0, либо 1. При чётном числе входов ситуация k=n/2k=n/2 требует соглашения. В приведённом определении при ничьей выход равен нулю; в другой задаче могут задать отдельное значение или разрешить ничью специальным правилом. Поэтому сначала проверьте условие: запись «хотя бы половина» задаёт другую функцию при чётном nn.

Рассмотрим два соседних набора для пяти входов: 1100011000 и 1110011100. В первом есть две единицы и три нуля, поэтому большинство равно нулю. Во втором одна позиция изменилась с нуля на единицу: теперь единиц три, а нулей две, и выход переключается на единицу. Именно между этими значениями суммы проходит порог. Изменение порядка самих позиций на результат не повлияет, пока число единиц остаётся прежним.

Для четырёх входов сравните определения на наборе 11001100. Строгое большинство отсутствует, поэтому принятое выше правило выдаёт ноль. Правило «не менее половины» выдало бы единицу. Ни один ответ нельзя считать правильным без уточнения условия; при проектировании схемы это соглашение должно быть частью её спецификации. Калькулятор ограничен нечётным числом входов, чтобы показать основное правило без отдельного случая ничьей.

Таблица истинности для трёх переменных

Обозначим входы AA, BB, CC. Переберём все 23=82^3=8 наборов и для каждого посчитаем сумму. Выход равен единице, когда единиц хотя бы две.

AABBCCЧисло единицM3M_3
00000
00110
01010
01121
10010
10121
11021
11131

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

Формула через И и ИЛИ

Для трёх переменных достаточно проверить, нашлась ли пара единиц:

M3(A,B,C)=(A∧B)∨(A∧C)∨(B∧C).M_3(A,B,C)=(A\land B)\lor(A\land C)\lor(B\land C).

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

Например, для A=1A=1, B=0B=0, C=1C=1 получаем (1∧0)∨(1∧1)∨(0∧1)=1(1\land0)\lor(1\land1)\lor(0\land1)=1. Для 100100 все три конъюнкции равны нулю. Выражение называют сокращённой дизъюнктивной нормальной формой: в отличие от совершенной ДНФ, каждому слагаемому здесь не нужно содержать все три переменные.

Формулу можно реализовать тремя двухвходовыми элементами И и одним элементом ИЛИ на три входа. Если доступны только двухвходовые элементы ИЛИ, соедините два таких элемента последовательно. Каждая пара входов должна поступать на свой элемент И; затем результаты объединяются. Подробнее сам переход от выражения к соединениям разобран в статье о построении логической схемы.

Пять входов: сколько наборов дают единицу

Для пяти переменных всего 25=322^5=32 набора. Результат равен единице при k=3k=3, 44 или 55. Число наборов с ровно kk единицами равно числу способов выбрать их позиции, то есть (5k)\binom{5}{k}. Получаем:

(53)+(54)+(55)=10+5+1=16.\binom{5}{3}+\binom{5}{4}+\binom{5}{5}=10+5+1=16.

Остальные 16 наборов дают ноль. На рисунке высота столбца показывает количество наборов с данным kk: например, десять разных наборов содержат ровно три единицы. Золотые столбцы соответствуют выходу 1.

Распределение 32 наборов пяти входов: при трёх, четырёх и пяти единицах мажоритарная функция равна единице
Распределение 32 наборов пяти входов: при трёх, четырёх и пяти единицах мажоритарная функция равна единице

Равенство числа единичных и нулевых результатов справедливо для любого нечётного nn. Каждому набору можно сопоставить противоположный, заменив в нём все нули на единицы и наоборот. Если в первом единиц больше половины, то во втором их меньше половины. Так наборы разбиваются на пары с разными результатами. Для чётного nn наборы с ничьей нарушают этот аргумент, если всем им назначить ноль.

Можно проверить результат другим способом, не перечисляя все строки. Для ровно трёх единиц выбираются три позиции из пяти; оставшиеся две автоматически становятся нулями. Для четырёх единиц проще выбрать позицию единственного нуля - это даёт пять вариантов. Наконец, все пять входов равны единице только в одном наборе. Сумма этих трёх непересекающихся групп и составляет шестнадцать.

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

Свойства и связь с другими функциями

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

Для нечётного числа входов выполняется самодвойственность: если инвертировать все входы, то инвертируется и выход. Для трёх аргументов она записывается как M3(¬A,¬B,¬C)=¬M3(A,B,C)M_3(\neg A,\neg B,\neg C)=\neg M_3(A,B,C). При чётном числе входов с правилом «ничья даёт 0» это свойство на ничьей не работает: противоположный набор тоже останется ничьей.

Не путайте большинство с исключающим ИЛИ. Для трёх входов XOR равен единице при нечётном числе единиц, то есть при одной или трёх; большинство - при двух или трёх. Это различие важно, например, в полном сумматоре: бит переноса равен M3(A,B,C)M_3(A,B,C), а бит суммы вычисляется как A⊕B⊕CA\oplus B\oplus C.

Где применяется правило большинства

В тройном модульном резервировании три канала выполняют одну задачу, а голосующий элемент выбирает большинство результатов. Если два канала дают правильный бит, один неверный бит маскируется. Такой способ описан в обзоре NIST по отказоустойчивым системам. Само голосование не устраняет причину сбоя: два одинаково ошибающихся канала или неисправность голосующего элемента могут привести к ошибке на выходе.

Для количественного примера предположим, что каналы ошибаются независимо с вероятностью p=0,1p=0{,}1, а голосующий элемент идеален. Ошибка большинства возникает при ошибке ровно двух или всех трёх каналов:

Pош=(32)p2(1−p)+p3=0,028.P_{\text{ош}}=\binom32p^2(1-p)+p^3=0{,}028.

Это 2,8 % в заданной модели, а не универсальная надёжность реальной системы. Зависимые ошибки, общие причины отказов и собственный отказ голосующего элемента меняют расчёт. Мажоритарный элемент также является комбинационной схемой: выход определяется текущими входами. Для хранения состояния нужна другая конструкция, например RS-триггер.

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

Частые ошибки

  • Считают половину большинством. При чётном числе входов ровно половина единиц даёт ничью; правило для неё нужно задать отдельно.
  • Используют XOR вместо большинства. На наборе 110110 XOR равен 0, а M3M_3 равна 1.
  • Забывают набор 111111. Формула с парами включает его: каждое из трёх слагаемых истинно.
  • Смешивают наборы и суммы. Значению k=3k=3 при пяти входах соответствуют десять разных наборов, а не один.
  • Считают резервирование безусловной защитой. Формула вероятности выше опирается на независимость ошибок и исправное голосование.

FAQ

Что такое мажоритарная функция простыми словами?

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

Как записать мажоритарную функцию трёх переменных?

Как (A∧B)∨(A∧C)∨(B∧C)(A\land B)\lor(A\land C)\lor(B\land C). Формула истинна тогда и только тогда, когда найдутся хотя бы две единицы.

Сколько единиц нужно для большинства из пяти?

Не менее трёх. Подходят наборы с тремя, четырьмя или пятью единицами; всего таких наборов 16 из 32.

Коротко

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

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Логические элементы И, ИЛИ, НЕ: таблица истинности

Логические элементы И, ИЛИ, НЕ: таблица истинности

Как работают логические элементы И, ИЛИ и НЕ: таблицы истинности, обозначения, примеры расчёта схем и типичные ошибки при работе с двоичными сигналами.

8 ноября 20269 минут
Приоритет логических операций в выражении: порядок и правила

Приоритет логических операций в выражении: порядок и правила

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

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

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

Сколько существует булевых функций от n переменных и почему ответ равен 2 в степени 2ⁿ? Вывод по таблице истинности, примеры и задачи с ограничениями.

8 ноября 20269 минут
Минимизация булевой функции: карта Карно

Минимизация булевой функции: карта Карно

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

8 ноября 20268 минут
СДНФ: совершенная дизъюнктивная нормальная форма

СДНФ: совершенная дизъюнктивная нормальная форма

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

11 июня 20268 минут
Булев куб: вершины, рёбра и расстояние Хэмминга

Булев куб: вершины, рёбра и расстояние Хэмминга

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

8 ноября 20268 минут