• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

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

Метод Карно і Вейча дозволяє виконати мінімізацію функцій графічно. Карта Карно для ДДНФ (діаграма Вейча — для ДКНФ) є аналогом таблиці істинності, зображеній у спеціальній формі. Кількість клітинок у карти визначається за виразом 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.)

Читайте також:

1. V. Етичні правила психологічних досліджень
2. VII. Нахождение общего решения методом характеристик
3. Аденогіпофіз, його гормони, механізм впливу, прояви гіпер- та гіпофункцій.
4. Антенатальна профілактика стоматологічних захворювань
5. Аутентифікація з використанням односторонніх функцій
6. Банку за методом кумулятивного гепу, (тис. грн.)
7. Важкість праці: Динамічні, статичні навантаження. Напруженість праці. Увага, напруженість аналізаторних функцій, емоційна та інтелектуальна напруженість, монотонність праці.
8. Варіанти неврологічних і мовних порушень залежно від характеру перинатального ураження головного мозку.
9. Вивчення психологічних особливостей сенсомоторної та мисленнєвої діяльності школяра
10. Види геологічних зйомок
11. Види договорів і контрактів. Розподіл функцій учасників проекту
12. Види карного процесу

Переглядів: 1994