Мінімізація логічних функцій методом Квайна – Мак-Класкі

Розділ 1. Основи цифрової техніки

Тема 1.3. Синтез логічних пристроїв у різних базисах

Лекція №1. Форми представлення логічних функцій

 

У алгебрі логіки існують дві основні аналітичні форми представлення функцій:

- досконала диз’юнктивна нормальна форма (ДДНФ);

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

Кожна логічна функція має тільки одну ДДНФ і одну ДКНФ.

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

ДКНФ логічної функції - це кон’юнкція констатуент нуля (макстерми) відповідних наборам вхідних змінних, для яких функція рівна нулю.

У загальному випадку ДДНФ або ДКНФ можна представити за допомогою таблиці істинності (табл..1), яка описує функцію, наприклад f(x₁x₂x₃).

Таблиця 1

Значення аргументу	Значення функції f	ДДНФ	ДКНФ
x3	x2	x1	мінтерм	макстерм
				---
					---
				---
					---
					---
				---
				---
					---

 

Таким чином запишемо логічну функцію F у ДННФ та ДКНФ:

У процесі перетворення логічних виразів ДКНФ використовують рідше за ДДНФ.

 

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

 

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

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

Процес побудови цифрового пристрою називають логічним синтезом.

Основними вимогами до задачі синтезу є: мінімальне число елементарних кон’юнкцій або диз’юнкцій у логічній формі й однорідність використовуваних операцій.

Крім вимог мінімізації є ряд обмежень і умов на вибір елементної бази для синтезованого пристрою.

Найпростіші логічні функції (І, АБО, НЕ, І-НЕ, АБО-НЕ)які описують дію пристрою мають назву – БАЗИС

Мінімальна форма запису (МДНФ так і МКНФ) логічного виразу описує принцип дії логічної схеми. Існує два методи мінімізації:

- метод Квайна – Мак - Класки (аналітичний метод);

- метод Карно - Вейча ( графічний метод );

Мінімізація логічних функцій методом Квайна – Мак-Класкі

 

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

Алгоритм Квайна складається з таких кроків:

1. Записати ДДНФ (ДКНФ) заданої функції.

2. Виконати всі можливі операції неповного диз'юнктивного (кон’юнктивного) склеювання.

3. Виконати всі можливі операції диз'юнктивного (кон’юнктивного) поглинання. Результуюча формула є скороченою МДНФ (МКНФ) даної функції.

Розглянемо процес мінімізації логічної функції методом Квайна:

А) Функція задана в наступній диз’юнктивній формі

(1) (1)(2) (2)

Виконуємо всі можливі операції диз’юнктивного склеювання і поглинання:

Тоді одержуємо таку мінімальну форму:

Б) Функція задана в наступній кон’юнктивній формі

(1) (1) (2) (2)

Виконуємо всі можливі операції кон’юнктивного склеювання і поглинання:

Тоді одержуємо таку мінімальну форму: