Мои Конспекты
Главная | Обратная связь

...

Автомобили
Астрономия
Биология
География
Дом и сад
Другие языки
Другое
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Металлургия
Механика
Образование
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Туризм
Физика
Философия
Финансы
Химия
Черчение
Экология
Экономика
Электроника

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





Помощь в ✍️ написании работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

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

1. Представляем полином в общем виде: f = a0Åa1P1Å ... Åak Pk, где (P1,..., Pk ) —все возможные (с точностью до перестановок) произведения над множеством переменных функции Х = (х1, ... , хn), a0, a1, ...,ak —неопределенные коэффициенты.

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

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

х у z f

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

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

f =a0Å a1х Å a2у Å a3z Å a4ху Å a5хz Å a6уz Å a7хуz.

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

ШАГ 0. (х,у,z) = (0,0,0). f (0,0,0)=a0Å a1·0 Å a2·0 Å a3·0 Å a4·0·0 Å a5·0·0Å a6·0·0Å a7·0·0·0= 0. Отсюда следует: a0=0.

ШАГ 1. (х,у,z) = (0,0,1). f (0,0,1)=a1·0Å a2·0Å a3 ·1Å a 4·0·0Å a5·0·1Å a6·0·1 Å a7·0·0·1=1. Отсюда: a3= 1.

ШАГ 2. (х,у,z) = (0,1,0). f(0,1,0)=a1·0Å a2·1 Å1·0 Å a4·0·1 Å a5·0·0Å a6·1·0Å a7·0·1·0 =1. Получим: a 2= 1.

ШАГ 3. (х,у,z) = (0,1,1). f (0,1,1) = 1·0Å1·1Å1·1Å a4 ·0·1Å a5·0·1Å a6·1·1Åa7·1·1 = 0. Получим: a 6= 0.

ШАГ 4. (х,у,z) = (1,0,0). f(1,0,0)=a1·1Å1·0Å1·0Å a4·1·0Å a5·1·0Å a6·0·0Å a7·1·0·0 =1. Получим:a 1= 1.

ШАГ 5. (х,у,z) = (1,0,1). f (1,0,1) =1·1Å1·0Å1·1Å a 4·1·0Å a5·1·1Å0·0·1Å a7·1·0·1=1. Получим: a 5= 1.

ШАГ 6. (х,у,z) = (1,1,0). f (1,1,0) =1·1Å1·1Å1·0Å a 4·1·1Å1·1·0 Å1·1·0 Å a7·1·1·0 =1. Получим: a 4= 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 Å a7·1·1·1 =1. Получим: a 7= 1.

Подставляя поочередно найденные значения коэффициентов a0, a3, a2, a6, a1, a5, a4, a7 в первоначальную формулу, получим искомое представление функции в виде полинома Жегалкина: f = х Å у Å z Å ху Å хz Å хуz.

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

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

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

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

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

а) Ø х = х Å1,

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

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

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

Ú (К1 , ... , Кр ) = К1Å ... Å Кр ,

Ø ¯ ( К1 , ... , Кр ) = К1Å ... Å Кр .

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

а) х Å х = 0.

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

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

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

К 1= `x `y z, К 2= `x y z , К 3= x y`z.

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

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

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

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

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

К3 = 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;

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

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

г) x Å х = 0.

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

а)Ú (К1 , ... , Кр ) = К1Å ... Å Кр ;

б) Ø ¯ ( К1 , ... , Кр ) = К1Å ... Å Кр .

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

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

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

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

 

Доверь свою работу ✍️ кандидату наук!
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой



Поиск по сайту:







©2015-2020 mykonspekts.ru Все права принадлежат авторам размещенных материалов.