Изменения

Первый способ - по таблице истинности. Пусть для функции <math>f(x_{1},x_{2},..,x_{n})</math> задана таблица истинности. Запишем сначала данную функцию в виде полинома Жегалкина с неопределенными коэффициентами. Затем по очереди подставляем всевозможные наборы переменных и находим коэффициенты. Легко видеть, что за каждую подстановку находим только один коэффициент.

Второй способ - преобразование Дизъюнктивной нормальной формы. Этот способ основан на том, что <math> X \oplus 1 = \bar{X} </math>. Если функция задана в виде ДНФ, то сначала убираем дизъюнкцию, используя при этом правило Де-Моргана, а все отрицания заменяем прибавлением единицы. После этого раскрываем скобки по обычным правилам, при этом учитываем, что четное число одинаковых слагаемых равно нулю (так как <math> X \oplus X = 0 </math>), а нечетное число одинаковых слагаемых равно одному такому слагаемому.