В курсе линейные булевы функции рассматриваются в аффинной форме \(f(x)=a_0\oplus a_1x_1\oplus\cdots\oplus a_nx_n\). Для функции, заданной таблицей истинности, коэффициенты такой формы однозначно восстанавливаются по значениям в нуле и единичных векторах: \(a_0=f(0)\),
После этого достаточно проверить равенство восстановленной аффинной функции исходной таблице на всех наборах. Любой набор, где значения различаются, является свидетельством нелинейности. Эквивалентный короткий сертификат — пара \(x,y\), нарушающая тождество \(f(x\oplus y)=f(x)\oplus f(y)\oplus f(0)\).
Что важно запомнить
- Аффинно-линейная ФАЛ имеет вид
- Коэффициенты определяются значениями \(f(0)\) и \(f(e_i)\).
- После восстановления кандидата нужно сравнить его с \(f\) на всей таблице истинности.
- Одного несовпадения достаточно для доказательства нелинейности.
- Для линейной функции обязательно выполняется \(f(x\oplus y)=f(x)\oplus f(y)\oplus f(0)\). Нарушение этого равенства даёт локальный сертификат нелинейности.
Восстановление линейного кандидата
Пусть функция \(f:B^n\to B\) задана таблицей. Если она принадлежит классу аффинных линейных функций, то
\(f(x_1,\ldots,x_n)=a_0\oplus a_1x_1\oplus\cdots\oplus a_nx_n.\)
Подставляя нулевой набор, получаем \(a_0=f(0)\). Для единичного вектора \(e_i\) имеем \(f(e_i)=a_0\oplus a_i\), значит \(a_i=f(e_i)\oplus f(0)\). Поэтому возможная линейная функция определяется всего \(n+1\) значениями исходной таблицы.
Детерминированный тест
- Вычислить \(a_0=f(0)\).
- Для всех \(i\) вычислить \(a_i=f(e_i)\oplus a_0\).
- Для каждого \(x\in B^n\) вычислить \(g(x)=a_0\oplus\bigoplus_i a_ix_i\) и сравнить с \(f(x)\).
Если все значения совпали, функция линейна в принятом аффинном смысле. Если найден набор \(x\) с \(f(x)\ne g(x)\), функция нелинейна. Прямая реализация требует порядка \(O(n2^n)\) элементарных операций при явной таблице из \(2^n\) строк. Если обозначить размер таблицы через \(N=2^n\), то это \(O(N\log N)\), то есть полиномиальное время по размеру явного входа.
Короткое доказательство нелинейности
Для любой аффинной функции
\(f(x\oplus y)=f(x)\oplus f(y)\oplus f(0).\)
Это непосредственно следует из аффинного представления и свойств сложения по модулю 2. Поэтому достаточно предъявить одну пару \(x,y\), для которой тождество нарушается. Такой контрпример доказывает, что в полиноме Жегалкина присутствует нелинейный член.
Пример простыми словами
Для функции \(f(x_1,x_2)=x_1x_2\) имеем \(f(0,0)=f(1,0)=f(0,1)=0\), поэтому восстановленный линейный кандидат равен нулю. Но \(f(1,1)=1\), значит функция нелинейна. То же видно из пары \(x=(1,0)\), \(y=(0,1)\): левая часть тождества равна 1, а правая — 0.
Частые ошибки
- Проверять только значения в нуле и единичных векторах. Они определяют линейного кандидата, но не доказывают совпадение с функцией на остальных наборах.
- Забывать свободный коэффициент \(a_0\). В принятом в теории ФАЛ классе \(L\) допускаются аффинные функции.
- Считать любое несовпадение с однородной формой \(a_1x_1\oplus\cdots\oplus a_nx_n\) доказательством нелинейности: функция может отличаться только константой.
