tify">. Підставами знайдені коефіцієнти у формулу (3) і знайдемо таким чином многочлен Жегалкина
Відповідь: поліном Жегалкина для даної таблиці істинності має таке значення:.
ПОБУДОВА Полінома Жегалкина ЗА ДОПОМОГОЮ ЕКВІВАЛЕНТНИХ ПЕРЕТВОРЕНЬ ДНФ І КНФ, СДНФ І СКНФ
У тих випадках, коли функція задана логічною формулою, іноді зручніше використовувати не громіздкий метод невизначених коефіцієнтів, а компактний метод еквівалентних перетворень. Для цього необхідно вміти привести функцію в ДНФ або СДНФ, не вдаючись до використання таблиць істинності. Найчастіше використовуються наступні тотожності
а також закон ДеМоргана. Далі слід розкрити дужки по самим звичайним правилам.
Приклад 1: побудувати поліном Жегалкина для функції, заданої у вигляді СДНФ -
Рішення:
. Позбудемося диз'юнкції за допомогою закону ДеМоргана
=
2. Позбудемося заперечень
===
Відповідь: поліном Жегалкина має вигляд) =.
Приклад 2: побудувати поліном Жегалкина для функції, представленої в ДНФ -
Рішення:
. Замінимо диз'юнкцію кон'юнкція і сумою за модулем два
(?) (?)=(??) (??)
. Позбудемося заперечень
(?) (?)=(??) (??) =? ? ? ? ? ? ? =0? ? 0? 0? ? 0? ? ? =? ? ? ? =? ?
Відповідь: поліном Жегалкина має вигляд
) =? ?
МЕТОД ТРИКУТНИКА
Метод трикутника дозволяє перетворити таблицю істинності в поліном Жегалкина за допомогою побудови допоміжної трикутної таблиці у відповідності з наступними правилами:
. Будується повна таблиця істинності, в якій рядки йдуть у порядку зростання двійкових кодів від 000 ... 00 до 111 ... 11.
. Будується допоміжна трикутна таблиця, в якій перший стовпець збігається зі стовпцем значень функції в таблиці істинності.
. Осередок в кожному наступному стовпці виходить шляхом підсумовування по модулю 2 двох осередків попереднього стовпця - стоїть в тому ж рядку і рядком нижче.
. Стовпці допоміжної таблиці нумеруються двійковими кодами в тому ж порядку, що і рядки таблиці істинності.
. Кожному бінарного коду ставиться у відповідність один з членів полінома Жегалкина залежно від позицій коду, в яких стоять одиниці. Наприклад, осередку 111 відповідає член ABC, осередку 101 - член AC, осередку 010 - член B, осередку 000 - член 1 і т. Д.
. Якщо у верхньому рядку якого-небудь стовпця варто одиниця, то відповідний член присутній в поліномі Жегалкина.
Висновок
Математика - наука дуже точна, проте в ній можна проявити фантазію, вирішуючи завдання різними способами. Дискретна математика не є в цьому винятком.
У своїй роботі я розглянула кілька найпоширеніших способів вирішення поставленого мені завдання: приведення логічних функцій до поліномами Жегалкина. Кожний з розглянутих мною способів має свої особливості застосування, але всі вони вимагають безумовної уважності і зосередженості.
На закінчення хочеться сказати, що Іван Іванович Жегалкина зробив велику послугу людству, коли вивів поліном, названий згодом його ім'ям. Поліном, члени якого зв'язуються тільки двома операціями і одиницею, виявився неймовірно корисний і дуже широко застосовується людиною в процесі його життя і діяльності.
Список використаної літератури
1. Яблонський С. В. Введення в дискретну математику: Учеб. посібник для вуов.- 2-е изд., Перераб. і доп.- М .: Наука. Гол. ред. фіз.-мат. лит.- 1986. - 384 с.
2. Марченков С. С. Замкнуті класи булевих функцій.- М .: фіз.-мат. лит.- 2000. - 126 с.
. Дунаєв С. Д., Золотарьов С. Н. Цифрова схемотехніка: Навчальний посібник для технікумів і коледжів ж.-д. транспорту.- М .: ГОУ «Навчально-методичний центр по утворенню на залізничному транспорті», 2007. - 238 с.
4. Супрун В.П. Табличний метод полиномиального розкладання булевих функцій - М .: Кібернетика.- 1987. - № 1
5. Логачёв О.А, Сальников А.А., Ященко В.В. Булеві функції в теорії кодування та криптології - МЦНМО, 2004. - 470с.
. Е.Л Рабкин, Ю.Б. Фарфоровская, дискретна...
