Аналіз теорії цифрових автоматів
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
пліканти g не є імплікантою функції f.
Приведемо без доведень два твердження, корисні при отриманні мінімальної ДНФ.
Дизьюнкція будь-якої кількості імплікант булевої ф-ції f також є імплікантою цієї функції.
Будь-яка булева функція f еквівалентна дизюнкції всіх своїх простих імплікант. Така форма представлення булевої ф-ції називається скороченою ДНФ.
Отримання скорочених ДНФ є першим етапом відшукання мінімальних форм булевих функцій. В скорочену ДНФ входять всі прості імпліканти булевої функції. Іноді з скороченої ДНФ можна забрати одну, або декілька простих імплікант, не порушуючи еквівалентності початкової функції. Такі прості імпліканти називаються лишніми. Виключення лишніх простих імплікант з скорочених ДНФ - другий етап мінімізації.
Визначення: Скорочена ДНФ булевої ф-ції називається тупіковою, якщо в ній відсутні лишні прості імпліканти.
Виключення лишніх простих імплікант в скорочених ДНФ булевої функції не є однозначним поцесом, тобто булева функція може мати декілька тупікових ДНФ.
Твердження. Тупікові ДНФ булевої функції f, що містять мінімальну кількість букв, являються мінімальними. Мінімальних ДНФ також може бути декілька.
Розглянемо декілька методів мінімізації. Всі вони практично відрізняються тільки на першому етапі - етапі отримання скорочених ДНФ. Слід відмітити, що, на жаль, пошук мінімальної ДНФ завжди звязаний з деяким перебором рішень. Існують методи зменшення цього перебору, проте він завжди залишається.
Метод квайна оснований на використанні двох основних співвідношень:
Співвідношення склеювання:
AxA=A,
де А - любе елементарне походження.
Співвідношення поглинання:
АА=А, {x, }.
Справедливість обидвох співвідношень легко перевіряється. Суть методу в послідовному виконанні всіх можливих склеювань і потім всіх поглинань, що приводять до скороченої ДНФ.
Приклад. Нехай є булева ф-ція, задана таблицею істиності (табл.1).
Таблиця 1
x1 x2 x3 x4F 0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
0 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 11
0
0
1
1
0
1
1
1
0
0
0
0
0
1
0
Її ДДНФ має вигляд
f=
Для зручності помітимо кожну конституєнту одиниці з ДДНФ ф-ції f яким-небудь десятковим номером (довільно). Виконаємо склеювання. Конституєнта 1 склеюється тільки з конституєнтою2 (по змінній х3) і з конституєнтою 3 (по змінній х2), конституєнта 2 з конституєнтою 4. В результаті отримуємо
1-2: ; 3-4: ;
1-3: ; 4-6: ;
2-4: ; 5-6: .
Далі проводимо склеювання отриманих елементарних перетворень. Склеюються тільки ті перетворення, які містять одинакові змінні. Має місце два випадки склеювання:
=;
=,
з появою одного і того ж .
Подальші склеювання неможливі. Провівши поглинання, отримаємо скорочену ДНФ
.
Переходимо до наступного етапу. Для отримання мінімальної ДНФ необхідно забрати з скороченої ДНФ всі лишні прості імпліканти. Це робиться за допомогою спеціальної імплікантної матриці Квайна. Рядки такої матриці відмічаються простими імплікантами булевої ф-ції, тобто членами скороченої ДНФ, а стовбці - конституєнтами одиниці, тобто членами ДДНФ булевої ф-ції. Приклад (продовження). Імплікантна маириця має вигляд (табл.2)
Таблиця 2.
Прості імплікантиКонституенти одиниці x2 x3 x4 x1 x2 x3Відповідна клітка імплікантної матриці на перетині рядка (з розглядуваною простою імплікантою) і стовбця (з конституєнт одиниці) відмічається хрестиком (табл.2). Мінімальні ДНФ будуються по імплікантній матриці наступним чином:
1. Шукаються стовбці матриці, які мають тільки один хрестик. Відповідні цим хрестикам прості імпліканти називаються базисами і складають так зване ядро булевої ф-ції. Ядро обовязково входить в мінімальну ДНФ.
2. Розглядаються різні варіанти вибору сукупності простих імплікант, які накриють хрестиками решту стовбців матриці, і вибираються варіанти з мінімальним сумарним числом букв в такій сукупності імплікант.
Ядром нашої ф-ції є імпліканти x1x2x3. Імпліканта x2x3x4 -лишня. Тому ф-ція має єдину тупікову і мінімальну ДНФ:
Метод квайна-мак-класкі
Метод представляє собою формалізований на етапі знаходження простих імплікант метод Квайна. Формалізація проводиться таким чином:
Всі конституанти одиниці з ДДНФ булевої функцію f записуються їх двійковими номерами.
Всі номери розбиваються на групи, що не перетинаються. Ознака утворення і-ї групи: і одиниць в кожному двійковому номері конституєнти одиниці.
Склеювання проводять тільки між номерами сусідніх груп. Склеювані номери відмічається будь-яким знаком (закреслюванням).
Склеювання проводять всеможливі, як і в методі Квайна.
Невідмічені після склеювання номера є простими імплікантами.
Знаходження мінімальних ДНФ дальше проводяться на імплікантній матриці, як і в методі Квайна.
Метод дозволяє швидко отримати мінімальні ДНФ булевої функції f невеликого числа змінних. В основі методу лежить задання булевих функцій діаграмами деякого спеціального виду, які дістали назву діаграм Вейча. Для булевої ф-ції двох змінних діаграма Вейча має вигляд (табл.3) Кожна клітка діаграми відповідає набору змінних булевої функції в її таблиці істиності. В клітці діаграми ставиться одиниця, якщо булева функція приймає одиничне значення на відповідному наборі.