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

...

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

Мінімізація методом Квайна





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

Вихідною формою подання функції для мінімізації за методом Квайна є досконала диз'юнктивна нормальна форма (ДДНФ). Метод забезпечує одержання скороченої ДНФ (СДНФ), тобто сукупності всіх простих імплікант. Метод базується на використанні співвідношення неповного склеювання і співвідношення поглинання , де A і B - довільні кон'юнктивні терми, x - змінна.

Для мінімізації необхідно виконати такі етапи:

1) запис функції у початковій формі - ДДНФ;

2) застосування співвідношення склеювання послідовно до конституент одиниці, потім до імплікант n-1 рангу, n-2 рангу і так далі, поки можливе формування нових імплікант;

3) виконання всіх можливих поглинань, в результаті чого визначаються всі прості імпліканти;

4) побудова таблиці покриттів (імплікантної матриці) і знаходження тупикових ДНФ (ТДНФ);

5) вибір мінімальної ДНФ (МДНФ) з числа ТДНФ.

Виконаємо мінімізацію функції, заданої табл. 5.

 

Таблиця 5 – Параметри функції

x3 x2 x1 y

 

Функція у досконалій диз'юнктивній нормальній формі (ДДНФ) має вигляд

Виконавши попарне склеювання конституент одиниці, одержуємо множину імплікант 2-го рангу: . Подальше склеювання імплікант неможливе. Тоді функцію можна записати у вигляді:

Виконавши поглинання, одержуємо скорочену ДНФ:

Будуємо таблицю покриттів (табл. 6).

 


Таблиця 6 – Таблиця покриттів

  Конституенти
Імпліканти
+   +    
+     +  
  + +    
  +     +

 

Знаходимо ядро функції - сукупність імплікант відповідних однократно покритим конституентам.

В даному випадку ядро складають імпліканти і . Як правило, ядро варто доповнити ще декількома імплікантами, для одержання повного покриття всіх конституент вихідної функції. Різні варіанти покриття є тупиковими ДНФ. Серед ТДНФ форма з мінімальною ціною буде мінімальною ДНФ (МДНФ). Для розглянутої функції, існують дві рівноцінні ТДНФ:

та

Як МДНФ вибираємо, наприклад,

 

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



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







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