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

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

Карта заповнюється за допомогою таблиці істинності чи логічних виразів ДДНФ або ДКНФ.

У відповідну клітинку необхідно записати «0» якщо логічна функція типу МКНФ, «1» якщо логічна функція типу МДНФ. Одиниці чи нулі об’єднуються в області, в кожну область можуть входити одна, дві, чотири, вісім, …, 2ⁿ одиниць (чи нулів).

Чим більше одиниць чи нулів у середині області, тим меншою кількістю змінних буде описуватись ця область.

Якщо змінна в середині області змінює своє значення, то вона не буде описувати цю область.

Розглянемо приклад складання карти Карно для функції двох змінних.

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

Нехай функція f задана у вигляді таблиці істинності (табл.2.).

Запишемо її ДДНФ та заповнимо карту Карно (рис.2) відповідно до рис.1: в ті комірки, що відповідають мінтермам функції f ставимо 1, всі інші комірки заповнюються 0.

					Таблиця 2
				Значення	Значення	ДДНФ
	аргументу	функції
				x2	x1	f	мінтерм
				---
Рис. 1.					---		Рис.2

В побудованій карті Карно виділимо області, що об’єднують 1. В нашому випадку це одна область - правий стовпчик карти Карно.

Аналізуємо, які змінні всередині області змінюють своє значення, а які ні.

Як видно з рис.2. змінна x₁ для верхньої 1 приймає значення , а для нижньої 1 - . Тобто ця змінна змінює своє значення всередині області, тому вона не характеризує цю область. Змінна x₂ для обох одиниць приймає значення , тому вона цю область характеризує.

Отже тоді мінімізована функція f буде записана в наступному вигляді:

За однією і тією ж картою Карно можна записувати як МДНФ так і МКНФ, але для них беруться інверсні значення:

- якщо карта заповнена по 1, то МДНФ – записується з прямими змінними, а МКНФ – з інверсними;

- якщо карта заповнена по 0, то МКНФ – записується з прямими значеннями, а МДНФ – з інверсними.

Наприклад, для функції f (рис.2) МКНФ (область виділена пунктиром) буде записана в наступному вигляді:

Як бачимо, для даної функції записи МДНФ та МКНФ співпали.

Структура карти Карно для функцій трьох змінних має вид таблиці 2х4, рис.3.

Рис. 3.

Рис.4.

Розглянемо приклад мінімізації функції від трьох змінних, якщо вже задана карта Карно (рис.4.)