Метод Квайна-Мак-Класки. Выпишем носитель функции по карте Карно (предыдущий метод минимизации).

Выпишем носитель функции по карте Карно (предыдущий метод минимизации).

.

Разобьем наборы носителя по классам по количеству единиц в наборе и применим операцию склейки ко всем наборам из соседних классов. Наборы, участвующие в склейке, помечаем «∗». Получим следующую таблицу:

	(1000) *	(1−00)* (100−)* (10−0)*	(1−0−)* (1−−0)* (1−0−) — дубль (10−−)* (1−−0) — дубль (10−−) — дубль	(1−−−) (1−−−) — дубль (1−−−) — дубль
	(0011)* (0101)* (0110)* (1100)* (1001)* (1010)*	(−011) (−101) (−110) (110−)* (11−0)* (1−01)* (10−1)* (1−10)* (101−)*	(11−−)* (11−−) — дубль (1−−1)* (1−−1) — дубль (1−1−)* (1−1−) — дубль
	(1101)* (1110)* (1011)*	(11−1)* (111−)* (1−11)*
	(1111)*

Найдем простые импликанты, соответствующие непомеченным наборам (дубли не учитываем). Выпишем сокращенную ДНФ.

Составим таблицу покрытия. Обведем единственные в столбце метки, простые импликанты, соответствующие таким меткам, являются ядровыми, а их дизъюнкция ядровой ДНФ.

	(0011)	(0101)	(0110)	(1100)	(1101)	(1111)	(1110)	(1000)	(1001)	(1011)	(1010)

.

Составим по таблице покрытия вспомогательную функцию Патрика.

. Получаем, что ядровая ДНФ совпадает с сокращенной, тупиковой и минимальной ДНФ.

.

Решение:

1) По вектору значений функции составим карту Карно.

				10
01				1
11				1

Отметим на карте максимальные интервалы. Максимальный интервал образуют 4 двоичных набора, стоящие в крайней строке, то есть . Еще 6 пар рядом стоящих вершин с номерами , , , , , соответственно также образуют максимальные интервалы.

2) Найдем простые импликанты, соответствующие максимальным интервалам.

Тогда сокращенная ДНФ есть дизъюнкция всех простых импликантов , то есть

.

Отметим звездочкой на карте Карно вершины, покрытые только одним максимальным интервалом. Интервалы, покрывающие такие вершины, и соответствующие им импликанты являются ядровыми, их дизъюнкция — ядровой ДНФ. На карте Карно есть только две вершины и ( , покрытые ровно одним максимальным интервалом .

.

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

4) Выпишем все тупиковые ДНФ и найдем их ранг. Среди всех тупиковых ДНФ укажем минимальную ДНФ заданной функции.

, ;

, ;

, ;

, ;

, .