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