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

Для минимизации логических функций возможно использовать метод карт Карно (диаграмм Вейча)

Карта Карно или карта (диаграмма) Вейча – графический способ минимизации функций алгебры логики.

Отличие метода карт Карно от карт Вейча заключается в способе обозначения строк и столбцов карт. Однако, принципиальной разницы между ними нет.

Метод минимизационных карт Карно (или карт Вейча) хорошо работает при числе аргументов 3,4 и даже 5 и обеспечивает простоту получения результата. Этот метод основан на зрительном анализе таблиц (карт) и не может быть применен для обработки вычислительной техникой.

Карта Карно строится в соответствии с таблицей истинности логической функции. Столбцы и строки карты Карно обозначаются прямыми и инверсными переменными данной функции.

Правила построения Карты Карно:

1. Для формирования карты необходимо определить размер карты. Размер зависит от количества переменных: 2ⁿ, где n – количество переменных.

2. Склеивать можно соседние клетки в количестве равном 2m.

3. Соседними считаются также клетки крайних строк и столбцов, т.е. карта представляет собой тор или "бублик".

4. Диагональные клетки соседними не считаются.

5. Одна и та же элементарная конъюнкция может участвовать в нескольких склейках

Пример1

С помощью Карт Карно минимизировать логическую функцию:

F(x_1,x_2,x₃)=

Имеем две склейки:

 

		X	X
			X	X

 

В результате которых получаем минимизированную функцию:

F(x_1,x_2,x₃)=

Пример 2

С помощью Карт Карно минимизировать логическую функцию:

 

	Х	Х	Х
	Х	Х

Пример 3

С помощью Карт Карно минимизировать логическую функцию:

 

 

		X	X
		X	X
		X	X

 

А как поступать в том случае, когда логическая функция представлена в ДНФ?

Пример 4

С помощью Карт Карно минимизировать логическую функцию:

В данном случае необходимо преобразовать ДНФ в СКНФ, для чего домножить элементарные конъюнкции на 1.

Используем аксиому 1 алгебры Буля, т.к. при умножении на 1 исходное выражение не меняется: 

Раскроем скобки:

Построим карту Карно:

	X	X	X
	X	X	X