Булева функция

Функция, возвращающая одно из двух значений

Диаграмма бинарных решений и таблица истинности троичной булевой функции

В математике булева функция — это функция , аргументы и результат которой принимают значения из двухэлементного набора (обычно {истина, ложь}, {0,1} или {-1,1}). ^{[1] [2]} Альтернативные названия — функция переключения , используемая особенно в старой литературе по информатике , ^{[3] [4]} и функция истины (или логическая функция) , используемая в логике . Булевы функции являются предметом булевой алгебры и теории переключения . ^[5]

Булева функция принимает форму , где известна как булев домен и является неотрицательным целым числом, называемым арностью функции. В случае, когда , функция является постоянным элементом . Булева функция с несколькими выходами, с является векторной или векторнозначной булевой функцией ( S-box в симметричной криптографии ). ^[6] ${\displaystyle f:\{0,1\}^{k}\to \{0,1\}}$ ${\displaystyle \{0,1\}}$ ${\displaystyle k}$ ${\displaystyle k=0}$ ${\displaystyle \{0,1\}}$ ${\displaystyle f:\{0,1\}^{k}\to \{0,1\}^{m}}$ ${\displaystyle m>1}$

Существуют различные булевы функции с аргументами, равными количеству различных таблиц истинности с записями. ${\displaystyle 2^{2^{k}}}$ ${\displaystyle k}$ ${\displaystyle 2^{k}}$

Каждая -арная булева функция может быть выражена в виде пропозициональной формулы от переменных , а две пропозициональные формулы логически эквивалентны тогда и только тогда, когда они выражают одну и ту же булеву функцию. ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle x_{1},...,x_{k}}$

Примеры

Шестнадцать бинарных булевых функций

Элементарные симметричные булевы функции ( логические связки или логические вентили ) следующие:

• НЕ , отрицание или дополнение — которое получает один вход и возвращает истину, когда этот вход ложный («не»).
• И или конъюнкция — истина, когда все входные данные истинны («оба»).
• ИЛИ или дизъюнкция — истина, когда любой из входных данных истинен («либо»).
• XOR или исключающая дизъюнкция — истина, когда один из входов истинен, а другой — ложен («не равно»).
• NAND или ход Шеффера — истина, когда не все входные данные истинны («не оба»).
• NOR или логическое «ни то, ни другое» — истинно, когда ни один из входных сигналов не является истинным («ни то, ни другое»).
• XNOR или логическое равенство — истинно, когда оба входа одинаковы («равны»).

Примером более сложной функции является функция большинства (нечетного числа входов).

Представление

Булева функция, представленная в виде булевой схемы

Булеву функцию можно задать различными способами:

• Таблица истинности : явное перечисление ее значений для всех возможных значений аргументов
  • Диаграмма Маркванда: значения таблицы истинности, расположенные в двумерной сетке (используется в карте Карно )
  • Диаграмма двоичных решений , перечисляющая значения таблицы истинности в нижней части двоичного дерева.
  • Диаграмма Венна , изображающая значения таблицы истинности в виде раскраски областей плоскости.

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

• Нормальная форма отрицания , произвольная смесь И и ИЛИ аргументов и их дополнений
• Дизъюнктивная нормальная форма , как ИЛИ И аргументов и их дополнений
• Конъюнктивная нормальная форма , как И над ИЛИ аргументов и их дополнений
• Каноническая нормальная форма — стандартизированная формула, которая однозначно идентифицирует функцию:
  • Алгебраическая нормальная форма или многочлен Жегалкина , как XOR AND аргументов (дополнения не допускаются)
  • Полная (каноническая) дизъюнктивная нормальная форма , ИЛИ операторов И, каждый из которых содержит каждый аргумент или дополнение ( минтермы )
  • Полная (каноническая) конъюнктивная нормальная форма , И операторов ИЛИ, каждый из которых содержит каждый аргумент или дополнение ( maxterms )
  • Каноническая форма Блейка , ИЛИ всех основных импликант функции

Булевы формулы также можно отобразить в виде графика:

• Пропозициональный ориентированный ациклический граф
  • Цифровая схема логических вентилей , булева схема
  • График И-инвертора , использующий только И и НЕ

Для оптимизации электронных схем булевы формулы можно минимизировать с помощью алгоритма Куайна–Маккласки или карты Карно .

Анализ

Характеристики

Булева функция может иметь ряд свойств: ^[7]

• Константа : всегда истинна или всегда ложна независимо от аргументов.
• Монотонный : для каждой комбинации значений аргументов изменение аргумента с false на true может вызвать только переключение вывода с false на true, а не с true на false. Говорят, что функция является унированной относительно определенной переменной, если она монотонна относительно изменений этой переменной.
• Линейная : для каждой переменной изменение ее значения либо всегда приводит к изменению истинного значения, либо никогда не приводит к изменению ( функция четности ).
• Симметричный : значение не зависит от порядка аргументов.
• Однократное чтение : может быть выражено с помощью конъюнкции , дизъюнкции и отрицания с одним экземпляром каждой переменной.
• Сбалансированная : если ее таблица истинности содержит одинаковое количество нулей и единиц. Вес Хэмминга функции — это количество единиц в таблице истинности.
• Изогнутая : все ее производные сбалансированы (спектр автокорреляции равен нулю)
• Корреляция, невосприимчивая к m -му порядку: если выход не коррелирует со всеми (линейными) комбинациями не более m аргументов
• Уклончивый : если оценка функции всегда требует значения всех аргументов
• Булева функция является функцией Шеффера, если ее можно использовать для создания (путем композиции) любой произвольной булевой функции (см. функциональная полнота ).
• Алгебраическая степень функции — это порядок монома наивысшего порядка в его алгебраической нормальной форме.

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

Производные функции

Булеву функцию можно разложить, используя теорему разложения Буля по положительным и отрицательным сомножителям Шеннона ( разложение Шеннона ), которые являются (k-1)-арными функциями, полученными путем фиксации одного из аргументов (на ноль или единицу). Общие (k-арные) функции, полученные путем наложения линейного ограничения на набор входных данных (линейное подпространство), известны как подфункции . ^[8]

Булева производная функции по одному из аргументов является (k-1)-арной функцией, которая истинна, когда выход функции чувствителен к выбранной входной переменной; это XOR двух соответствующих сомножителей. Производная и сомножитель используются в разложении Рида-Мюллера . Концепция может быть обобщена как k-ичная производная в направлении dx, полученная как разность (XOR) функции в x и x + dx. ^[8]

Преобразование Мёбиуса (или преобразование Буля-Мёбиуса ) булевой функции — это набор коэффициентов ее полинома ( алгебраической нормальной формы ) как функции векторов показателей мономиалов. Это самообратное преобразование. Его можно эффективно вычислить с помощью алгоритма бабочки (« быстрое преобразование Мёбиуса »), аналогичного быстрому преобразованию Фурье . ^[9] Совпадающие булевы функции равны своим преобразованиям Мёбиуса, т. е. их значения таблицы истинности (минтерм) равны их алгебраическим (мономиальным) коэффициентам. ^[10] Существует 2^2^( k −1) совпадающих функций от k аргументов. ^[11]

Криптографический анализ

Преобразование Уолша булевой функции — это k-ичная целочисленная функция, дающая коэффициенты разложения на линейные функции ( функции Уолша ), аналогично разложению вещественных функций на гармоники с помощью преобразования Фурье . Его квадрат — это спектр мощности или спектр Уолша . Коэффициент Уолша отдельного битового вектора — это мера корреляции этого бита с выходом булевой функции. Максимальный (по абсолютной величине) коэффициент Уолша называется линейностью функции . ^[8] Наибольшее число бит (порядок), для которого все коэффициенты Уолша равны 0 (т. е. подфункции сбалансированы), называется устойчивостью , и говорят, что функция корреляционно невосприимчива к этому порядку. ^[8] Коэффициенты Уолша играют ключевую роль в линейном криптоанализе .

Автокорреляция булевой функции — это k-ичная целочисленная функция, задающая корреляцию между определенным набором изменений на входах и выходом функции. Для заданного битового вектора она связана с весом Хэмминга производной в этом направлении. Максимальный коэффициент автокорреляции (по абсолютной величине) известен как абсолютный индикатор . [ ^{7] [8]} Если все коэффициенты автокорреляции равны 0 (т. е. производные сбалансированы) для определенного числа бит, то говорят, что функция удовлетворяет критерию распространения до этого порядка; если они все равны нулю, то функция является изогнутой функцией . ^[12] Коэффициенты автокорреляции играют ключевую роль в дифференциальном криптоанализе .

Коэффициенты Уолша булевой функции и ее коэффициенты автокорреляции связаны эквивалентом теоремы Винера–Хинчина , которая утверждает, что автокорреляция и спектр мощности являются парой преобразований Уолша. ^[8]

Таблица линейной аппроксимации

Эти концепции могут быть естественным образом расширены до векторных булевых функций, рассматривая их выходные биты ( координаты ) по отдельности, или более тщательно, рассматривая набор всех линейных функций выходных битов, известных как его компоненты . ^[6] Набор преобразований Уолша компонентов известен как таблица линейной аппроксимации (LAT) ^{[13] [14]} или матрица корреляции ; ^{[15] [16]} он описывает корреляцию между различными линейными комбинациями входных и выходных битов. Набор коэффициентов автокорреляции компонентов является таблицей автокорреляции , ^[14] связанной преобразованием Уолша компонентов ^[17] с более широко используемой таблицей распределения разностей (DDT) ^{[13] [14]} , которая перечисляет корреляции между различиями во входных и выходных битах (см. также: S-box ).

Действительная полиномиальная форма

На единичном гиперкубе

Любая булева функция может быть однозначно расширена (интерполирована) до действительной области с помощью полилинейного полинома в , построенного путем суммирования значений таблицы истинности, умноженных на индикаторные полиномы : Например, расширение двоичной функции XOR равно , что равно Некоторые другие примеры - отрицание ( ), И ( ) и ИЛИ ( ). Когда все операнды независимы (не имеют общих переменных), полиномиальную форму функции можно найти, многократно применяя полиномы операторов в булевой формуле. Когда коэффициенты вычисляются по модулю 2, получается алгебраическая нормальная форма ( полином Жегалкина ). ${\displaystyle f(x):\{0,1\}^{n}\rightarrow \{0,1\}}$ ${\displaystyle \mathbb {R} ^{n}}$ $${\displaystyle f^{*}(x)=\sum _{a\in {\{0,1\}}^{n}}f(a)\prod _{i:a_{i}=1}x_{i}\prod _{i:a_{i}=0}(1-x_{i})}$$ ${\displaystyle x\oplus y}$ $${\displaystyle 0(1-x)(1-y)+1x(1-y)+1(1-x)y+0xy}$$ $${\displaystyle x+y-2xy}$$ ${\displaystyle 1-x}$ ${\displaystyle xy}$ ${\displaystyle x+y-xy}$

Прямые выражения для коэффициентов многочлена можно получить, взяв соответствующую производную: это обобщается как инверсия Мёбиуса частично упорядоченного набора битовых векторов: где обозначает вес битового вектора . Взятое по модулю 2, это булево преобразование Мёбиуса , дающее коэффициенты алгебраической нормальной формы : В обоих случаях сумма берется по всем битовым векторам a , покрытым m , т. е. «единичные» биты a образуют подмножество единичных битов m . $${\displaystyle {\begin{array}{lcl}f^{*}(00)&=&(f^{*})(00)&=&f(00)\\f^{*}(01)&=&(\partial _{1}f^{*})(00)&=&-f(00)+f(01)\\f^{*}(10)&=&(\partial _{2}f^{*})(00)&=&-f(00)+f(10)\\f^{*}(11)&=&(\partial _{1}\partial _{2}f^{*})(00)&=&f(00)-f(01)-f(10)+f(11)\\\end{array}}}$$ $${\displaystyle f^{*}(m)=\sum _{a\subseteq m}(-1)^{|a|+|m|}f(a)}$$ ${\displaystyle |a|}$ ${\displaystyle a}$ $${\displaystyle {\hat {f}}(m)=\bigoplus _{a\subseteq m}f(a)}$$

Когда область ограничена n-мерным гиперкубом , полином дает вероятность положительного результата, когда булева функция f применяется к n независимым случайным ( бернуллиевским ) переменным с индивидуальными вероятностями x . Частным случаем этого факта является лемма о нагромождении для функций четности . Полиномиальная форма булевой функции также может быть использована в качестве ее естественного расширения для нечеткой логики . ${\displaystyle [0,1]^{n}}$ ${\displaystyle f^{*}(x):[0,1]^{n}\rightarrow [0,1]}$

О симметричном гиперкубе

Часто булева область принимается как , с отображением false ("0") на 1 и true ("1") на -1 (см. Анализ булевых функций ). Полином, соответствующий тогда задается как: Использование симметричной булевой области упрощает некоторые аспекты анализа , поскольку отрицание соответствует умножению на -1, а линейные функции являются мономами (XOR - умножение). Эта полиномиальная форма, таким образом, соответствует преобразованию Уолша (в этом контексте также известному как преобразование Фурье ) функции (см. выше). Полином также имеет ту же статистическую интерпретацию, что и в стандартной булевой области, за исключением того, что теперь он имеет дело с ожидаемыми значениями (см. лемму о нагромождении для примера). ${\displaystyle \{-1,1\}}$ ${\displaystyle g(x):\{-1,1\}^{n}\rightarrow \{-1,1\}}$ $${\displaystyle g^{*}(x)=\sum _{a\in {\{-1,1\}}^{n}}g(a)\prod _{i:a_{i}=-1}{\frac {1-x_{i}}{2}}\prod _{i:a_{i}=1}{\frac {1+x_{i}}{2}}}$$ ${\displaystyle E(X)=P(X=1)-P(X=-1)\in [-1,1]}$

Приложения

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

Свойства булевых функций имеют решающее значение в криптографии , особенно при разработке алгоритмов симметричного ключа (см. поле подстановки ).

В кооперативной теории игр монотонные булевы функции называются простыми играми (играми с голосованием); это понятие применяется для решения задач в теории общественного выбора .

Смотрите также

• Философский портал

• Псевдобулева функция
• Булева функция
• Темы Булевой алгебры
• Алгебра множеств
• Модель дерева решений
• Функция индикатора
• Подписанный набор

Ссылки

1. "Булева функция - Энциклопедия математики". encyclopediaofmath.org . Получено 2021-05-03 .
2. Weisstein, Eric W. "Булева функция". mathworld.wolfram.com . Получено 2021-05-03 .
3. "функция переключения". TheFreeDictionary.com . Получено 2021-05-03 .
4. Дэвис, Д. У. (декабрь 1957 г.). «Переключение функций трех переменных». Труды IRE по электронным компьютерам . EC-6 (4): 265–275. doi :10.1109/TEC.1957.5222038. ISSN  0367-9950.
5. МакКласки, Эдвард Дж. (2003-01-01), «Теория переключения», Энциклопедия компьютерных наук , Великобритания: John Wiley and Sons Ltd., стр. 1727–1731, ISBN 978-0-470-86412-8, получено 2021-05-03
6. Carlet, Claude. "Векторные булевы функции для криптографии" (PDF) . Парижский университет . Архивировано (PDF) из оригинала 2016-01-17.
7. "Булевы функции — Справочное руководство Sage 9.2: Криптография". doc.sagemath.org . Получено 01.05.2021 .
8. Таранников, Юрий; Королев, Петр; Ботев, Антон (2001). «Коэффициенты автокорреляции и корреляционная устойчивость булевых функций». В Boyd, Colin (ред.). Advances in Cryptology — ASIACRYPT 2001 . Lecture Notes in Computer Science. Vol. 2248. Berlin, Heidelberg: Springer. pp. 460–479. doi : 10.1007/3-540-45682-1_27 . ISBN 978-3-540-45682-7.
9. Карле, Клод (2010), «Булевы функции для криптографии и кодов исправления ошибок» (PDF) , Булевы модели и методы в математике, информатике и инженерии , Энциклопедия математики и ее приложений, Кембридж: Cambridge University Press, стр. 257–397, ISBN 978-0-521-84752-0, получено 2021-05-17
10. Pieprzyk, Josef; Wang, Huaxiong; Zhang, Xian-Mo (2011-05-01). «Преобразования Мёбиуса, совпадающие булевы функции и свойство несовпадения булевых функций». International Journal of Computer Mathematics . 88 (7): 1398–1416. doi :10.1080/00207160.2010.509428. ISSN  0020-7160. S2CID  9580510.
11. Нитадж, Абдеррахман; Сусило, Вилли; Тониен, Джозеф (01 октября 2017 г.). «Произведение Дирихле для логических функций». Журнал прикладной математики и вычислений . 55 (1): 293–312. дои : 10.1007/s12190-016-1037-4. ISSN  1865-2085. S2CID  16760125.
12. Канто, Энн; Карле, Клод; Шарпен, Паскаль; Фонтен, Каролин (2000-05-14). "Характеристики распространения и корреляционно-иммунитет высоконелинейных булевых функций". Труды 19-й Международной конференции по теории и применению криптографических методов . EUROCRYPT'00. Брюгге, Бельгия: Springer-Verlag: 507–522. ISBN 978-3-540-67517-4.
13. Heys, Howard M. "Учебник по линейному и дифференциальному криптоанализу" (PDF) . Архивировано (PDF) из оригинала 2017-05-17.
14. "S-блоки и их алгебраические представления — Справочное руководство Sage 9.2: Криптография". doc.sagemath.org . Получено 04.05.2021 .
15. Дэмен, Джоан; Говертс, Рене; Вандевалле, Йоос (1994). «Корреляционные матрицы». В Прениле, Барт (ред.). Быстрое программное шифрование: Второй международный семинар. Левен, Бельгия, 14-16 декабря 1994 г., Слушания . Конспекты лекций по информатике. Том. 1008. Спрингер. стр. 275–285. дои : 10.1007/3-540-60590-8_21 .
16. Daemen, Joan (10 июня 1998 г.). "Глава 5: Распространение и корреляция - Приложение к предложению AES Rijndael" (PDF) . NIST . Архивировано (PDF) из оригинала 2018-07-23.
17. Nyberg, Kaisa (1 декабря 2019 г.). "Расширенные таблицы автокорреляции и бумеранга и связи между свойствами нелинейности векторных булевых функций" (PDF) . Архивировано (PDF) из оригинала 2020-11-02.

Дальнейшее чтение

• Крама, Ив; Хаммер, Питер Л. (2011), Булевы функции: теория, алгоритмы и приложения , Cambridge University Press, doi : 10.1017/CBO9780511852008, ISBN 9780511852008
• «Булева функция», Энциклопедия математики , EMS Press , 2001 [1994]
• Янкович, Драган; Станкович, Радомир С.; Морага, Клаудио (ноябрь 2003 г.). «Оптимизация арифметических выражений с использованием свойства двойной полярности». Сербский журнал электротехники . 1 (71–80, номер 1): 71–80. doi : 10.2298/SJEE0301071J .
• Арнольд, Брэдфорд Генри (1 января 2011 г.). Логика и булева алгебра. Courier Corporation. ISBN 978-0-486-48385-6.
• Мано, ММ; Силетти, МД (2013), Цифровой дизайн , Pearson