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

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

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

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

Булева функция принимает форму , где известна как булева область определения и представляет собой неотрицательное целое число, называемое арностью функции. В случае , когда функция является постоянным элементом . Булева функция с несколькими выходами. Это векторная или векторнозначная булева функция ( S-блок в симметричной криптографии ) . ^[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}}$

Примеры

Шестнадцать двоичных логических функций

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

• 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 ).

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

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

Любая булева функция может быть однозначно расширена (интерполирована) в действительную область с помощью полилинейного полинома в , построенного путем суммирования значений таблицы истинности, умноженных на индикаторные полиномы : ${\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}$$

по модулю 2алгебраическая нормальная формаполином Жегалкина ${\displaystyle 1-x}$ ${\displaystyle xy}$ ${\displaystyle x+y-xy}$

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

$${\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)}$$

a,mформыm

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

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

Часто логический домен принимается как , с ложным («0») сопоставлением с 1 и истинным («1») с -1 (см. Анализ логических функций ). Полином, соответствующий тогда, определяется следующим образом: ${\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. «Булева функция - Математическая энциклопедия» . энциклопедияofmath.org . Проверено 03 мая 2021 г.
2. Вайсштейн, Эрик В. «Булева функция». mathworld.wolfram.com . Проверено 03 мая 2021 г.
3. «Функция переключения». TheFreeDictionary.com . Проверено 03 мая 2021 г.
4. Дэвис, DW (декабрь 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 г.
6. Карлет, Клод. «Векторные логические функции для криптографии» (PDF) . Парижский университет . Архивировано (PDF) из оригинала 17 января 2016 г.
7. «Логические функции — Справочное руководство Sage 9.2: Криптография». doc.sagemath.org . Проверено 1 мая 2021 г.
8. Таранников, Юрий; Королев, Петр; Ботев, Антон (2001). «Коэффициенты автокорреляции и корреляционная устойчивость булевых функций». В Бойде, Колин (ред.). Достижения в криптологии — ASIACRYPT 2001 . Конспекты лекций по информатике. Том. 2248. Берлин, Гейдельберг: Springer. стр. 460–479. дои : 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, получено 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.
13. Хейс, Ховард М. «Учебное пособие по линейному и дифференциальному криптоанализу» (PDF) . Архивировано (PDF) из оригинала 17 мая 2017 г.
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 г.

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

• Крама, Ив; Хаммер, Питер Л. (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), Цифровой дизайн , Пирсон