Методы получения полиномов Жегалкина.

1. Метод равносильных преобразований. Используется для функций, заданных формулой. Метод состоит в выполнении следующих действий.

1) В формуле все функции, кроме суммы Жегалкина и эквиваленции, выражаются через отрицание, конъюнкцию и дизъюнкцию. Эквиваленция заменяется отрицанием операции : .

2) Дизъюнкция исключается с помощью закона Моргана: .

3) Отрицание исключается с помощью свойства суммы Жегалкина: .

4) Раскрываются скобки, приводятся подобные с помощью законов:

, , , .

Пример. = = = = = = .

2. Метод неопределенных коэффициентов. Используется для функций, заданных таблицей. Метод состоит в том, что сначала записывается полином Жегалкина для заданной функции в общем виде с неопределенными коэффициентами, затем эти коэффициенты определяются на основе таблицы значений функции от конъюнкции наименьшего ранга к конъюнкциям больших рангов.

Пример. Пусть функция задана таблицей 2.14. Запишем полином Жегалкина для f:

f (, ) = (2.5)

Табл. 2.14
		f( , )

f (0,0) = ·0 ·0 ·0 =1 (Значение f (0,0) = 1 выбирается из таблицы).

f (1,0) = ·0 ·1 ·0 =0 =0 1=0 =1.

Аналогично, f (0,1) = ·0 ·0 ·1 =0 =0 1=0 =1.

f (1,1) = ·1 ·1 ·1 =1 =1

1 1 1=1 =0.

Теперь можно записать выражение (2.5) с определенными коэффициентами: f (, ) = 1.

Теорема. Любая функция алгебры логики представима в виде полинома Жегалкина единственным образом с точностью до порядка следования слагаемых.