Файл: 1.5-к Мінімізація логічних функцій.pdf

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

Логічні функції, що являють собою диз'юнкції окремих членів, кожен з яких є деякою функцією, що містить тільки кон'юнкції та інверсії, називаються логічними функціями диз'юнктивної

форми.

Наприклад, F = A B + A C

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

Якщо кожен член ДНФ від п аргументів містить всі ці п аргументів (з інверсією або без неї), то така форма вираження функції називається досконалою диз'юнктивною нормальною

формою (ДДНФ).

Наприклад, F =A B C + A B C + A B C + A B C

Логічні функції, що являють собою кон'юнкцію окремих членів, кожен з яких є функцією, що містить тільки диз'юнкції та інверсії, називаються логічними функціями кон'юнктивної форми.

Наприклад, F =(A+B )( A+ C)

По аналогії з диз'юнктивними формами можливі кон'юнктивні нормальні форми (КНФ) та

досконалі кон'юнктивні нормальні форми (ДКНФ).

Для отримання ДДНФ і ДКНФ вводяться поняття мінтермів і макстермів.

Мінтерм (конституєнта 1) – це функція n змінних, яка дорівнює одиниці тільки на одному наборі.

Мінтерм отримують як кон’юнкцію n змінних, що входять до нього у прямому вигляді, якщо значення даної змінної в наборі Xi = 1, або в інверсному вигляді, якщо Xi = 0.

Макстерм (конституєнта 0) – це функція n змінних, яка дорівнює нулю тільки на одному наборі.

Макстерм отримують як диз’юнкцію всіх змінних, що входять до нього у прямому вигляді, якщо значення Xi = 0, або в інверсному вигляді, якщо значення Xi = 1.

Перехід від таблиці істинності функції до запису у вигляді ДДНФ виконується в такій послідовності:

1)у таблиці істинності функції вибираються всі набори аргументів, при яких функція дорівнює 1;

2)виписуються кон'юнкції, які відповідають цим наборам аргументів. Якщо аргумент в даному наборі дорівнює 1, то він записується без зміни, якщо ж аргумент в даному наборі дорівнює 0, то у відповідну кон'юнкцію записується його заперечення;

3)всі отримані кон'юнкції з'єднуються між собою знаками диз'юнкції.

Приклад 1. Функція f (х1, х2, х3) задана наступною таблицею:

Потрібно отримати для неї ДДНФ.

Для знаходження ДДНФ вибираємо з таблиці тільки ті набори значень аргументів, при яких функція дорівнює 1, тобто третій, четвертий і шостий. Виписуємо кон'юнкції, які відповідають вибраним наборам: x1 x2 x3 ; x1 x2 x3 ; x1 x2 x3

Сполучаючи ці кон'юнкції знаками диз'юнкції, остаточно отримуємо: f (х1, х2, х3) = ( x1 x2 x3 ) +(x1 x2 x3 ) + (x1 x2 x3 )

Аналогічно виконується перехід від таблиці істинності функції до запису у вигляді ДКНФ:

1)у таблиці істинності функції вибираються всі набори аргументів, при яких функція дорівнює 0;

2)виписуються диз'юнкції, відповідні цим наборам аргументів. Якщо аргумент в даному наборі дорівнює 0, то він записується без зміни, якщо ж аргумент в даному наборі дорівнює 1, то у відповідну диз'юнкцію записується його заперечення;

3)всі отримані диз'юнкції з'єднуються між собою знаками кон'юнкції.

Приклад 2. Записати ДКНФ для функції, заданою наступною таблицею:

Таким чином, будь-яку функцію алгебри логіки можна записати у вигляді ДДНФ або ДКНФ, тобто виразити за допомогою системи з трьох елементарних функцій: інверсії, диз'юнкції та кон'юнкції.

Набір логічних елементів І, АБО, НЕ називають основним базисом або основною функціонально повною системою елементів. Останнє означає, що за допомогою цих елементів можна реалізувати пристрій, що здійснює будь-яку складну логічну операцію.

Кожен з елементів І-НЕ та АБО-НЕ також володіє функціональною повнотою.

Базиси І-НЕ та АБО-НЕ називають універсальними. Ці базиси набули важливого значення у зв'язку зшироким використанням інтегральних логічнихелементівпри побудові логічних пристроїв.

Структури логічних елементів НЕ, І, АБО, побудованих з елементів І-НЕ, наведені на рис. 1.

Рис. 1. Реалізація схем: НЕ (а); І (б); АБО (в).

Схема заперечення НЕ реалізована на використанні наступного співвідношення:

y = x x =x

Схема логічного множення використовує принцип подвійної інверсії:

y =x1 x2 =x1 x2

Схема логічного додавання базується на використанні закону інверсії:

y =x1 x2 =x1 +x2

3. Мінімізація логічних функцій.

Важливим етапом проектування комп'ютерних схем є мінімізація булевих функцій, тобто знаходження їх виражень з мінімальною кількістю букв і операцій над ними. Мінімізація забезпечує побудову економічних схем комп'ютерів.

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

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

Для мінімізації функцій із кількістю букв n ≤ 6 застосовують карти Карно. Карта Карно є копією таблиці істинності для функції n змінних.

Наведемо загальні правила мінімізації.

1.Зображають карту Карно для n змінних і розмічають її рядки та стовпчики. У клітинки таблиці, які відповідають мінтермам функції, записують одиницю.

2.Склеюють прямокутні конфігурації, які заповнені одиницями та містять 1, 2, 4 або 8 клітинок. Верхні та нижні рядки, крайні ліві та праві стовпчики карти теж ніби склеюються, створюючи поверхню циліндра.

3.Множина прямокутників, які покривають усі одиниці, називається покриттям. Чим менше прямокутників і чим більше клітинок у прямокутниках, тим краще покриття. З декількох варіантів вибирають той, у якого менший коефіцієнт покриття z = r / s, де r – загальна кількість прямокутників; s – їх сумарна площа в клітинках.

4.Формули, отримані в результаті мінімізації, містять r елементарних кон’юнкцій (за кількістю прямокутників у покритті). Кожна кон’юнкція містить тільки ті змінні, які не змінюють свого значення в наборах, що склеюються у відповідному прямокутнику.

Приклад 3. Дано таблицю істинності функції F.

ДляданоїфункціїнеобхіднозаписатиДДНФтапровестиїїмінімізаціюзадопомогоюкартиКарно. Розв’язання: ДДНФ для даної функції має вигляд:

ПобудуємокартуКарно:

Результатимінімізації:

Для побудови схеми на універсальних логічних елементах І-НЕ рівняння перетворюються на основіправилаподвійноїінверсіїтаправиладеМорганадотакоговигляду:

Контрольні запитання.

1.Сформулюйте основні закони алгебри логіки.

2.Сформулюйте правило де Моргана.

3.Сформулюйте аксіоми алгебри Буля.

4.Сформулюйте правила алгебри Буля.

5.Сформулюйте наслідки правил де Моргана.

6.Які функції називаються логічними функціями диз'юнктивної форми?

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

8.Розшифруйте та дайте означення ДДНФ.

9.Які функції називаються логічними функціями кон'юнктивної форми?

10.Розшифруйте поняття КНФ та ДКНФ.

11.Дайте означення мінтерма.

12.Дайте означення макстерма.

13.Яким чином одержують мінтерм?

14.Яким чином одержують макстерм?

15.В якій послідовності виконується перехід від таблиці істинності функції до запису

увигляді ДДНФ?

16.В якій послідовності виконується перехід від таблиці істинності функції до запису

увигляді ДКНФ?

17.Що називають основним базисом або основною функціонально повною системою елементів?

18.Які базиси називають універсальними?

19.Наведіть приклади логічних елементів НЕ, І, АБО, побудованих з елементів І-НЕ.

20.Дайте означення мінімізації логічних функцій.

21.Які методи застосовують для мінімізації логічних функцій?

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

Література.

1.Шарапов А.В. Микроэлектроника: Учебное пособие. — Томск: Томский межвузовский центр дистанционного образования, 2007. — 158 с.

2.Келим Ю. М. Вычислительная техника: Учеб. пособие для студ. сред. проф. образования. - М.: Издательский центр «Академия», 2005. - 384 с.

3.Бабич М. П., Жуков І. А., Яременко К.П. та ін. Комп’ютерна схемотехніка. Курсове проектування: Навчально-методичний посібник. – К.: НАУ, 2004. – 160 с.