Логическая функция - Boolean function

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

Логическая функция принимает форму , которая называется логической областью и представляет собой неотрицательное целое число, называемое арностью функции. В случае , когда «функция» является постоянным элементом . Функция Логической с несколькими выходами, с представляет собой векторная или вектор- булева функция (ые S-окно в криптографии ). ${\ 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 или Sheffer stroke - истина, если не все входные данные верны («не оба»)
• ИЛИ или логическое ни - истина, когда ни один из входов не является истиной ("ни один")
• XNOR или логическое равенство - истина, когда оба входа одинаковы ("равны")

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

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

Логическая функция может быть указана разными способами:

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

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

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

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

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

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

Анализ

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

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

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

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

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

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

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

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

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

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

Автокорреляции булевой функции является к-ичных целочисленная функция дает корреляцию между определенным набором изменений входов и функцией Ouput. Для данного битового вектора это связано с весом Хэмминга производной в этом направлении. Максимальный коэффициент автокорреляции (по абсолютной величине) известен как абсолютный показатель . Если все коэффициенты автокорреляции равны 0 (т. Е. Производные сбалансированы) для определенного числа битов, то говорят, что функция удовлетворяет критерию распространения в этом порядке; если все они равны нулю, то функция является бент-функцией . Коэффициенты автокорреляции играют ключевую роль в дифференциальном криптоанализе .

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

Эти концепции можно естественным образом расширить до векторных булевых функций, рассматривая их выходные биты ( координаты ) по отдельности, или, более тщательно, рассматривая набор всех линейных функций выходных битов, известных как его компоненты . Набор преобразований Уолша компонентов известен как таблица линейного приближения (LAT) или корреляционная матрица ; он описывает корреляцию между различными линейными комбинациями входных и выходных битов. Набор коэффициентов автокорреляции компонентов представляет собой таблицу автокорреляции , связанную преобразованием Уолша компонентов с более широко используемой таблицей распределения различий (DDT), в которой перечислены корреляции между различиями входных и выходных битов (см. Также: S-блок ).

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

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

Любая логическая функция может быть однозначно расширена (интерполирована) на реальную область с помощью полилинейного полинома в , построенного путем суммирования значений таблицы истинности, умноженных на индикаторные полиномы :${\ Displaystyle е (х): \ {0,1 \} ^ {n} \ rightarrow \ {0,1 \}}$${\ Displaystyle \ mathbb {R} ^ {п}}$

Например, расширение двоичной функции XOR :${\ displaystyle x \ oplus y}$что равноНекоторые другие примеры - отрицание ( ), AND ( ) и OR ( ). Когда все операнды независимы (не имеют общих переменных), полиномиальная форма функции может быть найдена путем многократного применения полиномов операторов в булевой формуле. Когда коэффициенты вычисляются по модулю 2, получается алгебраическая нормальная форма ( многочлен Жегалкина ). ${\ displaystyle 1-x}$${\ displaystyle xy}$${\ Displaystyle х + у-ху}$

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

$${\ 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 {массив}}}$$

Это обобщает как Мёбиус инверсия в частично упорядоченном множестве битовых векторов:

$${\ displaystyle f ^ {*} (m) = \ sum _ {a \ substeq m} (- 1) ^ {| a | + | m |} f (a)}$$

где обозначает вес битового вектора . По модулю 2 это булево преобразование Мёбиуса , дающее коэффициенты алгебраической нормальной формы :${\ displaystyle | a |}$${\ displaystyle a}$

$${\ Displaystyle {\ шляпа {е}} (м) = \ bigoplus _ {а \ субстек м} е (а)}$$

В обеих случаях сумма берется по всем битовым векторам , охватываемых м , то есть «один» бит в форме подмножество одного бит м .

Когда область ограничена n-мерным гиперкубом , многочлен дает вероятность положительного результата, когда булева функция

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

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

Часто булевский домен принимается равным , с ложным («0») сопоставлением с 1 и истинным («1») с -1 (см.

Анализ булевых функций ). Полином, соответствующий тогда, определяется следующим образом:${\ displaystyle \ {- 1,1 \}}$${\ Displaystyle г (х): \ {- 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}}}$$

Использование симметричной логической области упрощает некоторые аспекты анализа , поскольку отрицание соответствует умножению на -1, а линейные функции являются мономами (XOR - это умножение). Таким образом, эта полиномиальная форма соответствует преобразованию Уолша (в этом контексте также известному как преобразование Фурье ) функции (см. Выше). Полином также имеет ту же статистическую интерпретацию, что и в стандартной булевой области, за исключением того, что теперь он имеет дело с ожидаемыми значениями (см. Пример леммы о накоплении ). ${\ Displaystyle E (X) = P (X = 1) -P (X = -1) \ in [-1,1]}$

Приложения

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

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

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

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

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

использованная литература

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

• Крама, Ив; Хаммер, Питер Л. (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 г.). Логика и булева алгебра . Курьерская корпорация. ISBN 978-0-486-48385-6.
• Мано, ММ; Силетти, доктор медицины (2013), цифровой дизайн , Pearson