Введение
Функция, возвращающая одно из двух значений. В математике булева функция — это функция, аргументы и результат которой принимают значения из множества, состоящего из двух элементов (обычно {true, false}, {0,1} или {1,1}). Альтернативные названия — переключающая функция, используемая особенно в старой литературе по компьютерным наукам, и функция истинности (или логическая функция), используемая в логике. Булевы функции являются предметом булевой алгебры и теории переключений. Булева функция имеет вид , где известна как булева область, а — неотрицательное целое число, называемое арностью функции. В случае, когда , функция является постоянной. Булева функция с несколькими выходами, с , является векторной или векторнозначной булевой функцией (S-блок в симметричной криптографии). Постоянная: всегда истинна или всегда ложна, независимо от её аргументов. Монотонная: для каждой комбинации значений аргументов изменение аргумента с ложного на истинное может привести только к переключению выхода с ложного на истинное, но не с истинного на ложное. Функция называется унитатной по определённой переменной, если она монотонна относительно изменений в этой переменной. Линейная: для каждой переменной инвертирование значения переменной либо всегда влияет на истинность, либо никогда не влияет (функция чётности). Симметричная: значение не зависит от порядка её аргументов. Прочитанная один раз: может быть выражена с помощью конъюнкции, дизъюнкции и отрицания с единственным экземпляром каждой переменной. Сбалансированная: если её таблица истинности содержит одинаковое количество нулей и единиц. Вес Хэмминга функции — это количество единиц в таблице истинности. Искривлённая (Bent): все её производные сбалансированы (спектр автокорреляции равен нулю). Иммунная к корреляции m-го порядка: если выход не коррелирует со всеми (линейными) комбинациями не более чем m аргументов. Уклоняющаяся (Evasive): если вычисление функции всегда требует значения всех аргументов. Булева функция является функцией Шеффера, если её можно использовать для создания (путем композиции) любой произвольной булевой функции (см. функциональная полнота). Алгебраическая степень функции — это порядок монома наивысшей степени в её алгебраической нормальной форме. Сложность схемы пытается классифицировать булевы функции по размеру или глубине схем, которые могут их вычислить.
In mathematics, a Boolean function is a function whose arguments and result assume values from a two element set (usually {true, false}, {0,1} or { 1,1}). Alternative names are switching function, used especially in older computer science literature, and truth function (or logical function), used in logic. Boolean functions are the subject of Boolean algebra and switching theory. A Boolean function takes the form , where is known as the Boolean domain and is a non negative integer called the arity of the function. In the case where , the function is a constant element of A Boolean function with multiple outputs, with is a vectorial or vector valued Boolean function (an S box in symmetric cryptography). Constant: Is always true or always false regardless of its arguments. Monotone: for every combination of argument values, changing an argument from false to true can only cause the output to switch from false to true and not from true to false. A function is said to be unate in a certain variable if it is monotone with respect to changes in that variable. Linear: for each variable, flipping the value of the variable either always makes a difference in the truth value or never makes a difference (a parity function). Symmetric: the value does not depend on the order of its arguments. Read once: Can be expressed with conjunction, disjunction, and negation with a single instance of each variable. Balanced: if its truth table contains an equal number of zeros and ones. The Hamming weight of the function is the number of ones in the truth table. Bent: its derivatives are all balanced (the autocorrelation spectrum is zero)
Correlation immune to mth order: if the output is uncorrelated with all (linear) combinations of at most m arguments
Evasive: if evaluation of the function always requires the value of all arguments
A Boolean function is a Sheffer function if it can be used to create (by composition) any arbitrary Boolean function (see functional completeness)
The algebraic degree of a function is the order of the highest order monomial in its algebraic normal form
Circuit complexity attempts to classify Boolean functions with respect to the size or depth of circuits that can compute them.
Выведенные функции
Булева функция может быть разложена с помощью теоремы расширения Буля на положительные и отрицательные кофакторы Шеннона (расширение Шеннона), которые представляют собой (k-1)-арные функции, получаемые путем фиксации одного из аргументов в 0 или 1. Общие (k-арные) функции, полученные путем наложения линейного ограничения на набор входов (линейное подпространство), называются подфункциями. Булева производная функции по одному из аргументов – это (k-1)-арная функция, которая принимает значение «истина», когда выход функции чувствителен к выбранной входной переменной; она является XOR двух соответствующих кофакторов. Производная и кофактор используются в расширении Рида — Мюллера. Это понятие можно обобщить до k-арной производной в направлении dx, которая вычисляется как разность (XOR) значений функции в точках x и x + dx. Совпадающие булевы функции равны своему преобразованию Мёбиуса, то есть значения их таблицы истинности (минимальных термов) равны их алгебраическим (мономиальным) коэффициентам. Существует 2^(2^(k-1)) совпадающих функций от k аргументов.
Криптографический анализ
Трансформация Уолша булевой функции — это функция, принимающая целочисленные значения, которая дает коэффициенты разложения на линейные функции (функции Уолша), аналогично разложению функций вещественных значений на гармоники преобразованием Фурье. Ее квадрат является спектром мощности, или спектром Уолша. Коэффициент Уолша для отдельного битового вектора является мерой корреляции этого бита с выходным значением булевой функции. Максимальный по абсолютной величине коэффициент Уолша известен как линейность функции. Коэффициенты автокорреляции играют ключевую роль в дифференциальном криптоанализе. Коэффициенты Уолша булевой функции и ее коэффициенты автокорреляции связаны соотношением, являющимся эквивалентом теоремы Винера — Хинчина, которая утверждает, что автокорреляция и спектр мощности образуют пару преобразований Уолша. Множество преобразований Уолша компонентов известно как таблица линейных приближений (LAT) или матрица корреляции; она описывает корреляцию между различными линейными комбинациями входных и выходных битов. Множество коэффициентов автокорреляции компонентов представляет собой таблицу автокорреляции, в то время как более широко используемая таблица распределения разностей (DDT) перечисляет корреляции между разностями во входных и выходных битах (см. также: S-блок).
На гиперкубе
Любая булева функция может быть уникально расширена (интерполирована) в реальной области многолинейным полиномом в , построенным путем суммирования значений таблицы истинности, умноженных на индикаторные полиномы: Например, расширение бинарной функции XOR равно , что эквивалентно. Другие примеры – отрицание , И и ИЛИ. Когда все операнды независимы (не имеют общих переменных), полиномиальную форму функции можно найти, последовательно применяя полиномы операторов в булевой формуле. Если коэффициенты вычисляются по модулю 2, получается алгебраическая нормальная форма (полином Жегалкина). Непосредственные выражения для коэффициентов полинома можно получить, взяв соответствующую производную: это обобщается как инверсия Мёбиуса частично упорядоченного множества битовых векторов: где обозначает вес битового вектора. При взятии по модулю 2 это становится булевым преобразованием Мёбиуса, дающим коэффициенты алгебраической нормальной формы: В обоих случаях суммирование производится по всем битовым векторам a, покрываемым m, то есть "единицы" вектора a являются подмножеством "единиц" вектора m.
Когда область определения ограничена n-мерным гиперкубом , полином дает вероятность положительного исхода при применении булевой функции f к n независимым случайным (бернуллиевским) переменным с индивидуальными вероятностями x. Частным случаем этого факта является лемма накопления для функций чётности. Полиномиальная форма булевой функции также может быть использована в качестве естественного расширения для нечёткой логики.
На симметричном гиперкубке
Часто булевый домен принимается как , где ложь ("0") отображается на 1, а истина ("1") – на 1 (см. Анализ булевых функций). Полином, соответствующий , тогда задается следующим образом: Использование симметричного булевого домена упрощает некоторые аспекты анализа, поскольку отрицание соответствует умножению на -1, а линейные функции являются мономами (XOR – это умножение). Эта полиномиальная форма, таким образом, соответствует преобразованию Уолша (в данном контексте также известному как преобразование Фурье) функции (см. выше). Полином также имеет ту же статистическую интерпретацию, что и в стандартном булевом домене, за исключением того, что теперь он оперирует с математическими ожиданиями (см. лемму о наслоении для примера).
Приложения
Булевы функции играют фундаментальную роль в вопросах теории сложности, а также в проектировании процессоров для цифровых компьютеров, где они реализуются в электронных схемах с помощью логических элементов. Свойства булевых функций критически важны в криптографии, особенно при разработке алгоритмов с симметричным ключом (см. S-блок). В теории кооперативных игр монотонные булевы функции называются простыми играми (играми голосования); эта концепция применяется для решения задач в теории общественного выбора.