Проверка на линейность булевой функции

Проверка на линейность булевой функции

Определение. Булева функция называется линейной (принадлежит классу L), если ее полином Жегалкина линеен.

Примеры. Мажоритарная функция не является линейной: степень ее полинома Жегалкина (xy xz yz) равна 2. Из элементарных булевых функций линейными являются, например, инверсия и эквивалентность. Не являются линейными, например, штрих Шеффера и стрелка Пирса. •

Утверждение о числе булевых функций класса L. Число различных линейных булевых функций, зависящих от n переменных, равно 2 n+1 .

Доказательство. Полином Жегалкина линейной функции f(x1, …, xn) имеет вид:

где a, …, an – булевы константы. Таким образом, каждый линейный полином определяется булевым вектором a… an длины n+1, и наоборот, каждый булев вектор длины n+1 задает линейный полином Жегалкина некоторой функции n аргументов. Следовательно, число линейных полиномов (а значит, и число различных линейных функций n аргументов) равно числу булевых векторов длины n+1, то есть равно 2 n+1 . •

Пример. Из всех 16 булевых функций двух аргументов x1, x2 8 функций (2 2+1 ) принадлежат классу L: 0, 1, , , тождественные функции x1 и x2 и их инверсии x 1 и x 2. •

Теорема о замкнутости класса L. Множество всех линейных булевых функций является замкнутым классом.

Доказательство. Рассмотрим суперпозицию любых булевых функций из L, то есть функцию

и покажем, что она является линейной. Представим каждую из функций, образующих суперпозицию, полиномом Жегалкина:

Подставив эти полиномы в суперпозицию, получим:

Поскольку в последней формуле каждая скобка есть булева константа, то получен линейный полином Жегалкина. Значит, функция f(x1, …, xn) линейная, и класс L замкнут. •

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

Доказательство. Рассмотрим полином Жегалкина нелинейной функции f(x1, …, xn). Выберем в нем конъюнкцию K ранга больше единицы (такая конъюнкция существует, так как функция нелинейна). Не умаляя общности, можно считать, что K содержит переменные x1 x2 . Разобьем множество конъюнкций полинома на четыре группы: – первую образуем из конъюнкций, содержащих x1 и x2, – вторую – из конъюнкций, содержащих x1 и не содержащих x2, – третью – из конъюнкций, содержащих x2 и не содержащих x1 – остальные конъюнкции отнесем к четвертой группе.

Читайте также:  На экране появляются черные квадратики и пропадают

В первых трех группах вынесем за скобки соответственно x1x2, x1 и x2 :

Первая группа не пуста, так как есть по крайней мере одна конъюнкция K, содержащая x1 и x2 . Значит, найдется набор a3 … an такой, что p(a3, …, an) = 1. Подставим его в функцию f(x1, …, xn) (подстановка констант допустима по условию теоремы):

где a, b, c – булевы константы.

Если a=b=c=0, конъюнкция получена. Иначе положим в последней формуле x1= x b, и x2 = y a (подстановка переменных x, y и их инверсий x 1, y 1 допустима по условию теоремы), раскроем скобки и удалим пары одинаковых конъюнкций:

Если булева константа d=0, конъюнкция xy получена. Иначе функция g(x,y)= x y. Тогда, инвертировав исходную функцию (что допустимо по условию теоремы), получим конъюнкцию xy. •

Пример. Рассмотрим нелинейную булеву функцию, заданную полиномом Жегалкина.

[ выберем первую конъюнкцию x1x2 x3x4, в ней выберем переменные x1, x2 и сгруппируем конъюнкции ]

[ p(x3,x4)=1 при x3=1, x4=0, подставим эти значения переменных в формулу ]

[ положим x1=x b = x, x2 =y a=y 1 ]

Инвертировав исходную функцию, получим конъюнкцию xy. •

Математик Юрий Таранников о булевых функциях и их свойствах, важных для современной криптографии

unsplash.com

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

Функция, отображающая множество наборов из нулей и единиц длины n во множество <0,1>, где n — натуральное число, называемое числом переменных или числом входов булевой функции.

Отрицание булевой функции

Функция, принимающая на всех наборах противоположное значение. На всех наборах, где функция f принимает значение 0, отрицание функции f принимает значение 1, и, наоборот, на всех наборах, где функция f принимает значение 1, отрицание функции f принимает значение 0.

Уравновешенная булева функция

Полином функции

Представление функции в виде суммы мономов. Для булевой функции наиболее часто используется полином Жегалкина (называемый в англоязычной литературе алгебраической нормальной формой), представляющий собой сумму по модулю 2 произведений переменных. Представление булевой функции полиномом Жегалкина единственно.

Степень булевой функции

Длина самого длинного монома в ее полиноме Жегалкина.

Аффинная булева функция

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

Читайте также:  Холодильник хайер греются боковые стенки

Линейная булева функция

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

Нелинейная булева функция

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

Оператор

Так иногда называют совокупность из нескольких булевых функций, — например, m функций от n переменных каждая. При m=n такие операторы часто используются в блочных шифрах.

Корреляционная иммунность

Свойство булевой функции, при которой выход функции статистически не зависит от совокупности любых m ее входов. В этом случае функция называется корреляционно-иммунной порядка m.

Псевдослучайная последовательность

Последовательность, генерируемая детерминированным устройством или программой, но выглядящая как случайная. Широко используется в криптографии для шифрования данных (например, в поточных шифрах). Как правило, противнику известен алгоритм шифрования, но неизвестны начальные данные (секретный ключ).

Ортогональный массив

Кодовое расстояние

Минимальное расстояние между наборами кодового множества. Чем больше кодовое расстояние, тем большее количество ошибок можно гарантированно исправить.

Ортогональный код

Код, являющийся ортогональным подпространством к исходному коду, представляющему собой линейное подпространство.

Поточный шифр

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

Блочный (или блоковый) шифр

Способ шифрования, при котором последовательность, которую надо зашифровать, разбивается на блоки, а каждый блок шифруется отдельно по некоторому алгоритму.

Алгебраическая атака

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

Алгебраическая иммунность

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

Функция голосования

Функция, принимающая то значение, которое принимают большинство ее аргументов.

Конечное поле

Поле с конечным числом элементов, то есть алгебраическая структура с конечным числом элементов, для которых определены двуместные операции, называемые сложением и умножением, удовлетворяющие ряду аксиом, напоминающих свойства сложения и умножения обычных чисел. Конечное поле с q элементами существует тогда и только тогда, когда q — степень простого. Если q простое, то поле с q элементами эквивалентно кольцу вычетов по модулю q, то есть множеству из чисел 0, 1, q-1, на котором сложение и умножение определены как сложение и умножение чисел по модулю q.

Читайте также:  Тексты для стилистического анализа

x1 x2 x3 f
0 0 0 1
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 1

Такое решение:
Если выполняется условие:
f2 = АЛЬФА0 + АЛЬФА1*x1+АЛЬФА2*x2+.АЛЬФАn*xn
то функция линейная
В моем случае
АЛЬФА0 = 1
АЛЬФА1 = 1
АЛЬФА2 = 1
АЛЬФА3 = 0
f2 = 1+x1+x2(выполняется, значит линейная)

Я не пойму, что такое АЛЬФА1,АЛЬФА2, как ее находить?

Полином Жегалкина у булевой функции от трёх переменных x₁, x₂ и x₃ будет иметь вид:
f(x₁, x₂, x₃) = a₀ + a₁x + a₂x₂ + a₃x₃ + a₁₂x₁x₂ + a₁₃x₁x₃ + a₂₃x₂x₃ + a₁₂₃x₁x₂x₃, где:
коэффициенты a₀, a₁, a₂, a₃, a₁₂, a₁₃, a₂₃, a₁₂₃ ∈ <0; 1>.

Чтобы найти эти коэффициенты, нужно подставить в полином Жегалкина (написанный выше) значения функции на различных наборах переменных и решить систему уравнений. Далее, подставив найденные коэффициенты в полином, убеждаемся в его линейности.

f(000) = 1 → a₀ = 1
f(001) = 1 → a₀ + a₃ = 1 → 1 + a₃ = 1 → a₃ = 0
f(010) = 0 → a₀ + a₂ = 0 → 1 + a₂ = 0 → a₂ = 1
f(011) = 0 → a₀ + a₂ + a₃ + a₂₃ = 0 → 1 + 1 + 0 + a₂₃ = 0 → a₂₃ = 0
f(100) = 0 → a₀ + a₁ = 0 → 1 + a₁ = 0 → a₁ = 1
f(101) = 0 → a₀ + a₁ + a₃ + a₁₃ = 0 → 1 + 1 + 0 + a₁₃ = 0 → a₁₃ = 0
f(110) = 1 → a₀ + a₁ + a₂ + a₁₂ = 1 → 1 + 1 + 1 + a₁₂ = 1 → a₁₂ = 0
f(111) = 1 → a₀ + a₁ + a₂ + a₃ + a₁₂ + a₁₃ + a₂₃ + a₁₂₃ = 1 → 1 + 1 + 1 + 0 + 0 + 0 + 0 + a₁₂₃ = 1 → a₁₂₃ = 0

Тогда f(x₁, x₂, x₃) = 1 + x₁ + x₂ — линейный.

За вас это решать никто не будет. Если при разложении в полином Жигалкина функция не будет содержать конъюнкций нескольких переменных, то функция линейная. Для примера:

1) ПЖ линейной ф-ции: A0+A1x+A2y+A3z+A4j+A5k
2) ПЖ нелинейной ф-ции: A0+A1x+A2y+A3z+A4xy+A5yz+A6xz

http:// apollyon1986. narod. ru/docs/dm/FILES/9.html здесь почитайте

Ссылка на основную публикацию
Приложение ims service остановлено что делать
Ошибка «Приложение остановлено» может возникнуть по разным причинам, но получится ли избавиться от нее зависит не только от вас, но...
При установке континент ап не работает интернет
В свойствах вашего основного соединения нужно снять галку с компонента Continent 3 MSE Filter. Ошибка обычно возникает при использовании Континент-АП...
Прижать текст к низу div
Здравствуйте! В сегодняшней короткой и сугубо практической статье я расскажу, как прижать, к примеру, div к низу другого div. Всё...
Принтер самсунг ml 1210 как подключить
Страница 20 2.6 Установка вашего принтера ШАГ 4: Подсоединитесь к компьютеру с помощью кабеля для параллельного интерфейса (только модель ML-1210)...
Adblock detector