Многочлены Жегалкина

Доказать эквивалентности (6)-(9).

Используя основные эквивалентности и тождества (6)-(9), найти эквивалентные приведённые многочлены Жегалкина и доказать эквивалентность следующих пар формул:

При лексикографическом упорядочении наборов аргументов значения булевой функции $f\left(x_{1}, x_{2}, x_{3}\right)$ образуют последовательность (1001 0001). Выписать в явном виде систему уравнений для нахождения многочлена Жегалкина методом неопределённых коэффициентов, найти её решение, построить многочлен Жегалкина для $f$.

Найти многочлены Жегалкина (методом неопределённых коэффициентов и с помощью матрицы $J$) для следующих функций $f(x, y, z)$. Считаем, что наборы аргументов функций упорядочены лексикографически и значения на них задаются последовательностью 8 нулей и единиц:

Найти методом неопределённых коэффициентов многочлены Жегалкина для следующих функций:

Доказать, что для булевой функции $f\left(x_{1}, x_{2}, \ldots , x_{n}\right)$ многочлен Жегалкина можно получить, раскрыв скобки в следующей формуле и упростив её:

Используя предыдущую задачу, найти многочлены Жегалкина для следующих функций. Значения функций $f(x, y, z)$ и $g(x, y, z)$ заданы последовательностями нулей и единиц при лексикографическом упорядочении аргументов:

Доказать, что многочлен Жегалкина тождественно равен нулю тогда и только тогда, когда все его коэффициенты $\alpha_{i}$ в представлении (10) равны нулю.

Длиной многочлена Жегалкина называется количество его слагаемых. Например, многочлен $p\left(x_{1}, x_{2}\right)=1 \oplus x_{1} \oplus x_{1} x_{2}$ имеет длину три. Определить, сколько существует различных многочленов Жегалкина от $n$ переменных длины $k$, которые одновременно обращаются в ноль на наборах $(0,0, \ldots , 0)$ и $(1,1, \ldots , 1)$, состоящих из одних нулей и единиц, соответственно.

Пусть приведённый многочлен Жегалкина $p\left(x_{1}, \ldots , x_{n}\right)$ принимает значение 1 в точности на одном наборе $(\sigma_{1}, \ldots , \sigma_{n})$. Найти его длину.

Найти булеву функцию от $n$ переменных, у которой приведённый многочлен Жегалкина имеет наибольшую длину.

Что произойдёт с булевой функцией, если в многочлене Жегалкина (10) все коэффициенты изменить на противоположные?

Пусть приведённый многочлен Жегалкина $p\left(x_{1}, \ldots , x_{n}\right)$ принимает значение 1 в точности на двух противоположных наборах: $\left(\sigma_{1}, \ldots , \sigma_{n}\right)$ и $(\neg \sigma_{1}, \ldots , \neg \sigma_{n})$. Найти его длину.

Доказать, что приведённый многочлен Жегалкина $p\left(x_{1}, \ldots , x_{n}\right)$ задаёт функцию, которая коммутативна по любой паре аргументов, тогда и только тогда, когда для любого $k=0, \ldots , n$ многочлен или содержит всевозможные слагаемые с $k$ множителями, или не содержит ни одного из них.

Пусть длина многочлена Жегалкина определена как в задаче 184 на противоположной странице. Индукцией по $n \geqslant 1$ доказать, что для всякого $k=0, \ldots , 2^{n}$ существует многочлен Жегалкина $p\left(x_{1}, \ldots , x_{n}\right)$ длины не большей чем $n$, который обращается в единицу в точности на $k$ наборах аргументов.

Пусть многочлен Жегалкина задаётся формулой

Доказать индукцией по $n \geqslant 1$, что этот многочлен обращается в единицу в точности на $\frac{1}{3}\left(2^{n+1}+(-1)^{n}\right)$ наборах аргументов.

Пусть ненулевой многочлен Жегалкина с $n$ переменными не содержит слагаемых с более чем $k$ переменными, $k \leqslant n$. Используя индукцию по $n$, доказать, что количество единиц среди значений этого многочлена не меньше $2^{n-k}$.