русс | укр

Мови програмуванняВідео уроки php mysqlПаскальСіАсемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование


Linux Unix Алгоритмічні мови Архітектура мікроконтролерів Введення в розробку розподілених інформаційних систем Дискретна математика Інформаційне обслуговування користувачів Інформація та моделювання в управлінні виробництвом Комп'ютерна графіка Лекції


Склеювання виконують всі можливі, як і в методі Квайна. Непозначені після склеювання номери являються простими імплікантами.


Дата додавання: 2014-04-05; переглядів: 1032.


Пошук мінімальних ДНФ далі здійснюється по імплікантній матриці, як і в методі Квайна.

Детальніше розглянемо метод на прикладі розв’язку наступної задачі: мінімізувати методом Квайна – Мак-Класкі булеву функцію 4-х змінних, задану ДДНФ вигляду

 

.

 

1. В ДДНФ функції замінимо всі конституенти одиниці їх двійковими номерами:

.

2. Утворюємо групи двійкових номерів, Ознакою утворення -ї являється наявність одиниць в двійковому номері конституенти одиниці.

В даному випадку всі номери функції упорядковуються у чотири групи:

- перша група містить номери з однією одиницею -- ;

- друга група містить номери з двома одиницями

--, - - ;

- третя група містить номери з трьома одиницями

--, - - ;

- четверта група містить номери з чотирма одиницями - -.

3. Виконуємо всі можливі склеювання між номерами цих груп. Номери, що склеюються, позначимо значком „ - -„.

Запишемо результати склеювання. При цьому в двійкових номерах простих імплікант поставимо зірочки на позиціях, по яких відбувалося склеювання: 00*1, 0*01, 0*11, 01*1, *111, 111*.

Перша проста імпліканта одержана в результаті склеювання номерів 0001 і 0011, друга – номерів 0001 і 0101, третя – номерів 0011 і 0111, четверта – номерів 0101 і 0111, п’ята – номерів 0111 і 1111, шоста – номерів 1110 і 1111.

Утворюємо групи із результатів склеювання, тобто із двійкових номерів імплікант. Одержимо три групи:

- перша група містить номери імплікант з однією одиницею

- 00*1- , - 0*01- ;

- друга група містить номери імплікант з двома одиницями

- 0*11- , - 01*1- ;

- третя група містить номери імплікант з трьома одиницями

*111, 111*.

Склеюємо номери імплікант із сусідніх груп. При цьому склеюватися можуть тільки номери, що мають зірочки в однакових позиціях. Склеювані номери позначимо значком „- -„. Результатом склеювання являється імпліканта 0**1.

4. Маємо три прості імпліканти: *111, 111*, 0**1.

5. Будуємо імплікантну матрицю (табл. 1. 14. По таблиці визначаємо сукупність простих імплікант – 0**1 і 111*, що відповідає мінімальній ДНФ.

 

Таблиця 1. 14

Двійкові номери простих імплікант Двійкові номери конституент одиниці
0 * * 1 + + + +    
* 1 1 1       +   +
1 1 1 *         + +

 

Для відновлення буквеного вигляду простої імпліканти досить виписати добутки тих змінних, які відповідають двійковим цифрам, що збереглися після склеювань

0 ** 1 ; 1 1 1 * .

Зазначимо, що розбивання конституент на групи дозволяє зменшити число попарних порівнювань при склеюванні.

 

1. 4. 4. Графічний метод мінімізації функцій

Одержати МДНФ перемикальної функції, минаючи етапи формування скороченої і тупикової ДНФ, можна, застосувавши діаграми Вейча або карти Карно.

Діаграми Вейча і карти Карно для перемикальних функцій двох, трьох і чотирьох аргументів відповідно зображені на рис. ,а, б. Усередині клітинок вказані номери наборів.

Графічні методи призначені для ручної мінімізації. Наочність цих методів зберігається за невеликої кількості аргументів. При цьому відшукання імплікант не формалізоване, і успіх мінімізації цілком визначається кваліфікацією оператора.

Кожна клітинка відповідає конституенті. Прямокутник, що містить клітинок (), відповідає імпліканті. Прямокутник максимального розміру відповідає простій імпліканті.

Обґрунтуванням графічного методу мінімізації є той факт, що розташовані поруч клітинки відповідають сусіднім наборам аргументів, що відрізняються значенням однієї змінної і, таким чином. Можуть бути склеєні за методом Квайна. За змінних кожна клітинка має сусідніх клітинок.

Чим більше клітинок містить прямокутник, тим менше букв входить у записі імпліканти. Імпліканта містить тільки ті змінні, котрі приймають однакові значення для всіх клітинок прямокутника.

Наведемо етапи мінімізації перемикальних функцій графічним методом.


<== попередня лекція | наступна лекція ==>
 | Заповнити діаграму Вейча або карту Карно. Значення функцій записують у клітинки, що відповідають номерам наборів.


Онлайн система числення Калькулятор онлайн звичайний Науковий калькулятор онлайн