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

Мінімізацію по Квайну потрібно починати із ДДНФ функції. Якщо функція задається в довільній формі, то її необхідно перетворити до ДДНФ.

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

Розглянемо етапи мінімізації логічної функції , заданій в ДДНФ.

В даній функції - об'єднуємо елементарні добути, отримаємо - , маємо .

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

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

Мінімізація функцій Буля за допомогою карт Карно (табличний метод).

Карта Карно — це прямокутник, розбитий на квадрати (комірки), число яких дорівнює 2ⁿ , де n- число логічних змінних. Структура карт Карно для 2-х, 3-х, 4-х змінних показана на рис. 1.

Рис.3 Карти Карно: а) для функції 2-х аргументів;

б) для функції 3-х аргументів;

в) для функції 4-х аргументів;

Комірки карти відповідають значенням вхідних змінних. Наприклад, верхній рядок карти для функції 3-х змінних відповідає "1", тобто значення х₁=1, а нижній рядок - нульовому значенню х₁=0 кожний стовпчик характеризується значенням двух змінних х₂ і х₃.

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

Пошуки мінімальної форми функції зводяться до визначення областей, які містять по 2k комірок, де 2- число, k-ціле число (0, 1, 2...). В області об'єднуються сусідні комірки, які відповідають сусіднім елементарним добуткам рис.2.

Рис. 2

Такій мінімізації відповідає вираз: . Карти Карно можна уявно звертати, що дасть змогу побачити найбільш короткі імплеканти результуючі кон'юнкції, рис.3.

Рис. 3. Карти Карно і мінімальний запис логічних функцій:

а) для 3-х змінних; б),в) для 4-х змінних

Аналізуючи карти Карно, рис. 3, бачимо, що одна і таж комірка (наприклад, комірка з координатами х₂х₃) може покриватися два або декілька разів. Таким чином, формула, одержана в результаті мінімізації логічної функції за допомогою карт Карно, містить суму стількох елементарних добутків, скільки областей є в карті. Чим більше комірок в області, тим меньше змінних міститься у відповідному йому симентарному добутку.

3. Домашнє завдання.

3.1. Вивчити за опорним конспектом способи мінімізації логічних функцій.

3.2.Довести тотожність, відмічаючи закон і правила алгебри логіки застосовувані на кожному кроці перетворення: .

3.3. Логічна функція задана картою Карно. Вибрати правильну відповідь, що відповідатиме мінімізованій формі. На карті Карно проставити відповідні змінні та виділити відповідні області при мінімізації. .

А)