Алгоритми за изграждане на полином Zhegalkin

Ние считаме, алгоритми за изграждане на полином функция Zhegalkin Булев даде по различни начини, а именно: перфектен DNF произволна DNF формула, и истина маса.

Алгоритъм за построяване на полином в Zhegalkin SovDNF (въз основа на доказателството на теоремата на съществуването на полином Zhegalkin).

Започнете. Разположен перфектно DNF функция F (x1. ... хп).

Стъпка 1: Замяна на всеки герой от характера на дизюнкция логическо дизюнкцията с изключение.

Етап 2. Ние замени всяка променлива х с инверсия еквивалент формула х 1.

Стъпка 3: Отваряме скобите.

Етап 4. формула заличава от съвпадащите двойки условия.

Край. Zhegalkin получава полином функция е (х1. ..., хп).

Пример. Нека да се намери полином Zhegalkin мнозинство Булева функция на перфектното си DNF.

Алгоритъм за построяване на полином в Zhegalkin DNP (въз основа на равностойността K1 K2 = K1 K2 K1 K2).

Започнете. DNF даден произволна функция е (х1. ..., хп).

Етап 1: Разделете DNP сдвоен съюзи, за предпочитане ортогонална (ако нечетен брой съюзи, един от тях остава двойки).

Етап 2. Замяна на всяка двойка дизюнкция на съюзи формула K1 K2 K1 K2 или K1 K2 формула К1 К2. ако K1 и K2 са ортогонални.

Етап 3. Полученият формула намери друг дизюнкция А1 А2 и да го замени с формула А1 А2 А1 А2. Повторете стъпка 3 възможно най-дълго.

Етап 4. Поставете всяка променлива х с инверсия еквивалент формула х 1.

Стъпка 5. Отваряме скобите.

Етап 6. заличава от формула чифт идентични условия.

Край. Zhegalkin получава полином функция е (х1. ..., хп).

Пример. Нека да се намери полином функция Zhegalkin мнозинство от DNF.

Имайте предвид, че мнозинството полином функция, получена в последните два примера са едни и същи до реда на съюзи, както и че е естествено (за уникалност теорема Zhegalkin полином).