Методы получения полиномов Жегалкина.1. Метод равносильных преобразований. Используется для функций, заданных формулой. Метод состоит в выполнении следующих действий. 1) В формуле все функции, кроме суммы Жегалкина и эквиваленции, выражаются через отрицание, конъюнкцию и дизъюнкцию. Эквиваленция заменяется отрицанием операции : . 2) Дизъюнкция исключается с помощью закона Моргана: . 3) Отрицание исключается с помощью свойства суммы Жегалкина: . 4) Раскрываются скобки, приводятся подобные с помощью законов: , , , . Пример. = = = = = = . 2. Метод неопределенных коэффициентов. Используется для функций, заданных таблицей. Метод состоит в том, что сначала записывается полином Жегалкина для заданной функции в общем виде с неопределенными коэффициентами, затем эти коэффициенты определяются на основе таблицы значений функции от конъюнкции наименьшего ранга к конъюнкциям больших рангов. Пример. Пусть функция задана таблицей 2.14. Запишем полином Жегалкина для f: f (, ) = (2.5)
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. Теорема. Любая функция алгебры логики представима в виде полинома Жегалкина единственным образом с точностью до порядка следования слагаемых.
|