Метод неопределенных коэффициентов

Допустим, необходимо найти полином для некоторой булевой функции f(`хⁿ). Для этого выполняем следующие действия.

1. Представляем полином в общем виде: f = a₀Åa₁P₁Å ... Åa_k P_k, где (P₁,..., P_k ) —все возможные (с точностью до перестановок) произведения над множеством переменных функции Х = (х₁, ... , х_n), a₀, a₁, ...,a_k —неопределенные коэффициенты.

2. Рассматриваем таблицу истинности функции. Поочередно подставляем в формулу полинома значения переменных. При этом получаем уравнения относительно неопределенных коэффициентов. Решая их поочередно, находим все значения коэффициентов.

Пример 5. Найти коэффициенты полинома Жегалкина функции f = (01101111).

х	у	z	f

Решение. Обозначим переменные функции через х,у,z и построим ее таблицу истинности.

В общем виде полином имеет вид:

f =a₀Å a₁х Å a₂у Å a₃z Å a₄ху Å a₅хz Å a₆уz Å a₇хуz.

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

ШАГ 0. (х,у,z) = (0,0,0). f (0,0,0)=a₀Å a₁·0 Å a₂·0 Å a₃·0 Å a₄·0·0 Å a₅·0·0Å a₆·0·0Å a₇·0·0·0= 0. Отсюда следует: a₀=0.

ШАГ 1. (х,у,z) = (0,0,1). f (0,0,1)=a₁·0Å a₂·0Å a₃·1Å a ₄·0·0Å a₅·0·1Å a₆·0·1 Å a₇·0·0·1=1. Отсюда: a₃= 1.

ШАГ 2. (х,у,z) = (0,1,0). f(0,1,0)=a₁·0Å a₂·1 Å1·0 Å a₄·0·1 Å a₅·0·0Å a₆·1·0Å a₇·0·1·0 =1. Получим: a ₂= 1.

ШАГ 3. (х,у,z) = (0,1,1). f (0,1,1) = 1·0Å1·1Å1·1Å a₄·0·1Å a₅·0·1Å a₆·1·1Åa₇·1·1 = 0. Получим: a ₆= 0.

ШАГ 4. (х,у,z) = (1,0,0). f(1,0,0)=a₁·1Å1·0Å1·0Å a₄·1·0Å a₅·1·0Å a₆·0·0Å a₇·1·0·0 =1. Получим:a ₁= 1.

ШАГ 5. (х,у,z) = (1,0,1). f (1,0,1) =1·1Å1·0Å1·1Å a ₄·1·0Å a₅·1·1Å0·0·1Å a₇·1·0·1=1. Получим: a ₅= 1.

ШАГ 6. (х,у,z) = (1,1,0). f (1,1,0) =1·1Å1·1Å1·0Å a ₄·1·1Å1·1·0 Å1·1·0 Å a₇·1·1·0 =1. Получим: a ₄= 1.

ШАГ 7. (х,у,z) = (1,1,1). f (1,1,1) =1·1Å1·1Å1·1 Å1·1·1Å1·1·1 Å1·1·1 Å a₇·1·1·1 =1. Получим: a ₇= 1.

Подставляя поочередно найденные значения коэффициентов a₀, a₃, a₂, a₆, a₁, a₅, a₄, a₇в первоначальную формулу, получим искомое представление функции в виде полинома Жегалкина: f = х Å у Å z Å ху Å хz Å хуz.

В методе неопределенных коэффициентов используется прямое вычисление значений коэффициентов из уравнений. Для булевых функций c малым числом единиц в векторе значений проще использовать СДНФ либо СВНФ.

Метод построения полинома Жегалкина по СДНФ (СВНФ)

Для построения полинома для заданной булевой функции f(хⁿ). выполняют следующие действия.

1. Вначале строят СДНФ (СВНФ) функции f(`хⁿ), в которых используется базисный набор {Ø,&,Ú} ({Ø , ¯ }).

2. Преобразуются внутренние функции построенной формы. С использованием эквивалентных преобразований

а) Ø х = х Å1,

б) х ¯ у = 1Å хÅ у Å ху,

осуществляется переход к базису {0, 1, &, Å}во всех внутренних функциях формы.

3. Заменяется внешняя функция формы. СДНФ и СВНФ представляют собой суммы конституент единицы, которые никогда не принимают значение 1 на одинаковых наборах. Поэтому для соединения данных конституент вместо эквивалентного правила x Ú y = х Å у Å ху и вышеприведенной для функции Вебба формулы б) можно использовать неэквивалентные в общем случае правила замены:

Ú (К₁ , ... , К_р) = К₁Å ... Å К_р,

Ø ¯ ( К₁ , ... , К_р) = К₁Å ... Å К_р.

4. После раскрытия скобок в произведениях, получаемых во внутренних функциях, их общая сумма упрощается путем устранения из нее парных слагаемых. При этом используется эквивалентное преобразование:

а) х Å х = 0.

5. Полученная в итоге сумма произведений над множеством переменных Х=(х₁, ... , х_n)является искомым полиномом Жегалкина функции f(`хⁿ).

Пример 6. Построить полином Жегалкина для функции f = (01010010)из Примера 1 с использованием ее СДНФ.

Решение. Внутренние конъюнкции элементарных наборов и СДНФ будут следующие:

К ₁= `x `y z, К ₂= `x y z , К ₃= x y`z.

СДНФ имеет вид:

f =`x `y z Ú`x y z Ú x y`z = Ú (`x `y z , x y z, x y`z).

Преобразуем внутренние конъюнкции, выполняя замену Ø х = х Å1 и раскрывая скобки в произведениях:

К₁= (x Å1)(y Å1) z = (ху Å х Å у Å 1) z = х у z Å х z Å у z Å z,

К₂= (x Å1) y z = х у z Å у z ,

К₃= x y (z Å1) = х у z Å х у .

Заменяя внешнюю функцию логического сложения конституент единицы сложением по модулю 2, получим сумму произведений следующего вида:

f = х у z Å х z Å у z Å z Å х у z Å у zÅ х у z Å х у .

Устраняя из нее парные слагаемые по правилу х Å х = 0, получим в итоге искомый полином Жегалкина:

f = z Å х у Å х z Å х у z.

Замечание. Булевы функции могут быть разложены в полином Жегалкина, в отличие от нормальных форм, единственным способом. Это несложно доказать от противного.

ЗАДАЧИ

1. Привести пример задания одной и той же булевой функции при помощи двух различных ДНФ.

2. Построить СДНФ и СВНФ следующих функций:

а) ((х® у)® z)&х; б) (х½ у) Å z; в) Ø(ху® уz);г) (01101000); д) (1001101000001001); е) (0001001001010001) ; ж) (0100101000101001).

3. Построить СКНФ и СШНФ следующих функций:

а) ((хÚ у)® z);б) (х¯у)Å z; в) (ху ® уz); г) (11101001);д) (0111101011101101) ; е) (1011001101110111) ; ж) (1100110001011111).

4. Доказать эквивалентность в общем случае правил:

а)Ø х = х Å 1;

б) х ¯ у = 1Å хÅ у Å х у;

в) x Ú y = х Å у Å х у;

г) x Å х = 0.

5. Доказать справедливость для конституент К₁ , ... , К_рСДНФ и СВНФ правил замены:

а)Ú (К₁ , ... , К_р) = К₁Å ... Å К_р;

б) Ø ¯ ( К₁ , ... , К_р) = К₁Å ... Å К_р.

6. Построить методом неопределенных коэффициентов полиномы Жегалкина следующих функций: а)`х½у Å z;б)( х º у )® (`у ®`х);в)(хÚ у)Å (х® у);г)(х¯у х)® х у ;д) х ®(у ® z) ; е)(х½у)Å (х® z); ж)(х º у)® (х º z).

7. Построить при помощи СДНФ полиномы Жегалкина функций 6а) — ж).

8. Построить при помощи СВНФ полином Жегалкина функций 6 а) —ж).

9. Доказать единственность разложения булевых функций в полином Жегалкина.

<1011 12 13 14 15 16 >

Дата добавления: 2015-10-05; просмотров: 6099;