Многочлен Жегалкина – это представление булевой функции в виде арифметического выражения, а точнее – в виде многочлена 
, причём значения переменных x, y, z и значения полученных выражений рассматриваются в кольце вычетов по модулю 2. При этом каждое чётное число заменяют 0, а каждое нечётное – 1.
Есть несколько способов вычисления этих коэффициентов, мы рассмотрим два способа.
Первый способ: метод неопределённых коэффициентов.
Подставим в многочлен все возможные наборы x, y, z и получим 8 условий на 8 коэффициентов. При этом матрица системы будет содержать много нулей.
Например, f (0, 0, 0) = a0 = 0 (значение берём из таблицы истинности).
Далее, f (0, 0, 1) = a0 + a3 = 1, поэтому a3 = 1. И так далее, на каждом уравнении будем получать новый коэффициент.
В итоге получим: a3 = 1, a12 = 1, a23 = 1.
Тогда многочлен Жегалкина имеет вид: z + xy + yz.
Второй способ: использование СДНФ.
Как и следовало ожидать, ответ для второго способа вычисления многочлена Жегалкина совпал с ответом для первого способа.
Если эти ответы различаются, необходимо проверить выкладки.
В ответе с многочленом Жегалкина принято записывать слагаемые в лексикографическом порядке.
