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

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

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

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

Есть $2^{2^{k}}$ различные логические функции с $k$ аргументы; равно числу различных таблиц истинности с $2^{k}$ записи.

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

Примеры

Простейшими симметричными булевыми функциями ( логическими связками или логическими элементами ) являются:

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

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

Представительство

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

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

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

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

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

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

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

Анализ

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

Логическая функция может иметь множество свойств: ^[7]

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

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

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

Булеву функцию можно разложить с помощью теоремы Буля о разложении по положительным и отрицательным Шеннона кофакторам ( разложение Шеннона ), которые представляют собой (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 ).

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

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

Любая булева функция $f(x):\{0,1\}^{n}\rightarrow \{0,1\}$ может быть однозначно расширен (интерполирован) на действительную область с помощью полилинейного полинома от $\mathbb {R} ^{n}$ , построенный путем суммирования значений таблицы истинности, умноженных на индикаторные полиномы : $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})$ Например, расширение двоичной функции XOR $x\oplus y$ является $0(1-x)(1-y)+1x(1-y)+1(1-x)y+0xy$ что равно $x+y-2xy$ Некоторые другие примеры являются отрицанием ( $1-x$ ), И ( $xy$ ) и ИЛИ ( $x+y-xy$ ). Когда все операнды независимы (не имеют общих переменных), полиномиальную форму функции можно найти путем многократного применения полиномов операторов в булевой формуле. При вычислении коэффициентов по модулю 2 получается алгебраическая нормальная форма ( полином Жегалкина ).

Прямые выражения для коэффициентов многочлена можно получить, взяв соответствующую производную: ${\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}}$ это обобщается как инверсия Мёбиуса битовых частично упорядоченного набора векторов: $f^{*}(m)=\sum _{a\subseteq m}(-1)^{|a|+|m|}f(a)$ где $|a|$ обозначает вес битового вектора $a$ . По модулю 2 это булево преобразование Мёбиуса , дающее коэффициенты алгебраической нормальной формы : ${\hat {f}}(m)=\bigoplus _{a\subseteq m}f(a)$ В обоих случаях сумма берется по всем битовым векторам a, охватываемым m , т.е. «единичные» биты формы образуют подмножество одних битов m .

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

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

Часто логический домен принимается как $\{-1,1\}$ , с отображением false («0») на 1 и true («1») на -1 (см. Анализ логических функций ). Полином, соответствующий $g(x):\{-1,1\}^{n}\rightarrow \{-1,1\}$ тогда дается: $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}}$ Использование симметричной логической области упрощает некоторые аспекты анализа , поскольку отрицание соответствует умножению на -1, а линейные функции являются мономами (XOR — умножение). Таким образом, эта полиномиальная форма соответствует преобразованию Уолша (в этом контексте также известному как преобразование Фурье ) функции (см. выше). Полином также имеет ту же статистическую интерпретацию, что и в стандартной логической области, за исключением того, что теперь он имеет дело с ожидаемыми значениями. $E(X)=P(X=1)-P(X=-1)\in [-1,1]$ ( см . в лемме о накоплении пример ).

Приложения

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

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

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

См. также

Ссылки

^ «Булева функция — Математическая энциклопедия» . энциклопедияofmath.org . Проверено 03 мая 2021 г.
^ Вайсштейн, Эрик В. «Булева функция» . mathworld.wolfram.com . Проверено 03 мая 2021 г.
^ «функция переключения» . TheFreeDictionary.com . Проверено 03 мая 2021 г.
^ Дэвис, Д.В. (декабрь 1957 г.). «Функции переключения трех переменных» . IRE-транзакции на электронных компьютерах . ИС-6 (4): 265–275. дои : 10.1109/TEC.1957.5222038 . ISSN 0367-9950 .
^ Маккласки, Эдвард Дж. (01 января 2003 г.), «Теория переключения» , Энциклопедия компьютерных наук , GBR: John Wiley and Sons Ltd., стр. 1727–1731, ISBN 978-0-470-86412-8 , получено 3 мая 2021 г.
↑ Перейти обратно: Перейти обратно: ^а ^б Карлет, Клод. «Векторные логические функции для криптографии» (PDF) . Парижский университет . Архивировано (PDF) из оригинала 17 января 2016 г.
↑ Перейти обратно: Перейти обратно: ^а ^б «Бульевы функции — Справочное руководство Sage 9.2: Криптография» . doc.sagemath.org . Проверено 1 мая 2021 г.
↑ Перейти обратно: Перейти обратно: ^а ^б ^с ^д ^и ^ж Таранников Юрий; Королев, Петр; Ботев, Антон (2001). «Коэффициенты автокорреляции и корреляционная устойчивость булевых функций». В Бойде, Колин (ред.). Достижения в криптологии — ASIACRYPT 2001 . Конспекты лекций по информатике. Том. 2248. Берлин, Гейдельберг: Springer. стр. 460–479. дои : 10.1007/3-540-45682-1_27 . ISBN 978-3-540-45682-7 .
^ Карлет, Клод (2010), «Булевы функции для криптографии и кодов, исправляющих ошибки» (PDF) , Булевы модели и методы в математике, информатике и инженерии , Энциклопедия математики и ее приложений, Кембридж: Издательство Кембриджского университета, стр. 257–397, ISBN 978-0-521-84752-0 , получено 17 мая 2021 г.
^ Пепшик, Йозеф; Ван, Хуасюн; Чжан, Сянь-Мо (01 мая 2011 г.). «Преобразования Мебиуса, совпадающие булевы функции и свойство несовпадения булевых функций» . Международный журнал компьютерной математики . 88 (7): 1398–1416. дои : 10.1080/00207160.2010.509428 . ISSN 0020-7160 . S2CID 9580510 .
^ Нитадж, Абдеррахман; Сусило, Вилли; Тониен, Джозеф (01 октября 2017 г.). «Произведение Дирихле для булевых функций» . Журнал прикладной математики и вычислений . 55 (1): 293–312. дои : 10.1007/s12190-016-1037-4 . ISSN 1865-2085 . S2CID 16760125 .
^ Канто, Энн; Карлет, Клод; Шарпен, Паскаль; Фонтейн, Кэролайн (14 мая 2000 г.). «Характеристики распространения и корреляционная устойчивость сильно нелинейных логических функций» . Материалы 19-й Международной конференции по теории и применению криптографических методов . ЕВРОКРИПТ'00. Брюгге, Бельгия: Springer-Verlag: 507–522. ISBN 978-3-540-67517-4 .
↑ Перейти обратно: Перейти обратно: ^а ^б Привет, Ховард М. «Учебное пособие по линейному и дифференциальному криптоанализу» (PDF) . Архивировано (PDF) из оригинала 17 мая 2017 г.
↑ Перейти обратно: Перейти обратно: ^а ^б ^с «S-Box и их алгебраические представления — Справочное руководство Sage 9.2: Криптография» . doc.sagemath.org . Проверено 4 мая 2021 г.
^ Дэмен, Джоан; Говертс, Рене; Вандевалле, Йоос (1994). «Корреляционные матрицы». В Прениле, Барт (ред.). Быстрое программное шифрование: Второй международный семинар. Левен, Бельгия, 14-16 декабря 1994 г., Слушания . Конспекты лекций по информатике. Том. 1008. Спрингер. стр. 275–285. дои : 10.1007/3-540-60590-8_21 .
^ Дэмен, Джоан (10 июня 1998 г.). «Глава 5: Распространение и корреляция — Приложение к предложению AES Rijndael» (PDF) . НИСТ . Архивировано (PDF) из оригинала 23 июля 2018 г.
^ Нюберг, Кайса (1 декабря 2019 г.). «Расширенные таблицы автокорреляции и бумеранга и связи между свойствами нелинейности векторных логических функций» (PDF) . Архивировано (PDF) из оригинала 2 ноября 2020 г.

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

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

[1] «Булева функция — Математическая энциклопедия» . энциклопедияofmath.org . Проверено 03 мая 2021 г.

[2] Вайсштейн, Эрик В. «Булева функция» . mathworld.wolfram.com . Проверено 03 мая 2021 г.

[3] «функция переключения» . TheFreeDictionary.com . Проверено 03 мая 2021 г.

[4] Дэвис, Д.В. (декабрь 1957 г.). «Функции переключения трех переменных» . IRE-транзакции на электронных компьютерах . ИС-6 (4): 265–275. дои : 10.1109/TEC.1957.5222038 . ISSN 0367-9950 .

[5] Маккласки, Эдвард Дж. (01 января 2003 г.), «Теория переключения» , Энциклопедия компьютерных наук , GBR: John Wiley and Sons Ltd., стр. 1727–1731, ISBN 978-0-470-86412-8 , получено 3 мая 2021 г.

[:2-6] Перейти обратно: Перейти обратно: ^а ^б Карлет, Клод. «Векторные логические функции для криптографии» (PDF) . Парижский университет . Архивировано (PDF) из оригинала 17 января 2016 г.

[:0-7] Перейти обратно: Перейти обратно: ^а ^б «Бульевы функции — Справочное руководство Sage 9.2: Криптография» . doc.sagemath.org . Проверено 1 мая 2021 г.

[:1-8] Перейти обратно: Перейти обратно: ^а ^б ^с ^д ^и ^ж Таранников Юрий; Королев, Петр; Ботев, Антон (2001). «Коэффициенты автокорреляции и корреляционная устойчивость булевых функций». В Бойде, Колин (ред.). Достижения в криптологии — ASIACRYPT 2001 . Конспекты лекций по информатике. Том. 2248. Берлин, Гейдельберг: Springer. стр. 460–479. дои : 10.1007/3-540-45682-1_27 . ISBN 978-3-540-45682-7 .

[9] Карлет, Клод (2010), «Булевы функции для криптографии и кодов, исправляющих ошибки» (PDF) , Булевы модели и методы в математике, информатике и инженерии , Энциклопедия математики и ее приложений, Кембридж: Издательство Кембриджского университета, стр. 257–397, ISBN 978-0-521-84752-0 , получено 17 мая 2021 г.

[10] Пепшик, Йозеф; Ван, Хуасюн; Чжан, Сянь-Мо (01 мая 2011 г.). «Преобразования Мебиуса, совпадающие булевы функции и свойство несовпадения булевых функций» . Международный журнал компьютерной математики . 88 (7): 1398–1416. дои : 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] Канто, Энн; Карлет, Клод; Шарпен, Паскаль; Фонтейн, Кэролайн (14 мая 2000 г.). «Характеристики распространения и корреляционная устойчивость сильно нелинейных логических функций» . Материалы 19-й Международной конференции по теории и применению криптографических методов . ЕВРОКРИПТ'00. Брюгге, Бельгия: Springer-Verlag: 507–522. ISBN 978-3-540-67517-4 .

[:3-13] Перейти обратно: Перейти обратно: ^а ^б Привет, Ховард М. «Учебное пособие по линейному и дифференциальному криптоанализу» (PDF) . Архивировано (PDF) из оригинала 17 мая 2017 г.

[:4-14] Перейти обратно: Перейти обратно: ^а ^б ^с «S-Box и их алгебраические представления — Справочное руководство Sage 9.2: Криптография» . doc.sagemath.org . Проверено 4 мая 2021 г.

[15] Дэмен, Джоан; Говертс, Рене; Вандевалле, Йоос (1994). «Корреляционные матрицы». В Прениле, Барт (ред.). Быстрое программное шифрование: Второй международный семинар. Левен, Бельгия, 14-16 декабря 1994 г., Слушания . Конспекты лекций по информатике. Том. 1008. Спрингер. стр. 275–285. дои : 10.1007/3-540-60590-8_21 .

[16] Дэмен, Джоан (10 июня 1998 г.). «Глава 5: Распространение и корреляция — Приложение к предложению AES Rijndael» (PDF) . НИСТ . Архивировано (PDF) из оригинала 23 июля 2018 г.

[17] Нюберг, Кайса (1 декабря 2019 г.). «Расширенные таблицы автокорреляции и бумеранга и связи между свойствами нелинейности векторных логических функций» (PDF) . Архивировано (PDF) из оригинала 2 ноября 2020 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]