Методические указания к самостоятельным (домашней и контрольной) работам по курсу «Математическая логика и теория алгоритмов» (стр. 3 )

Минимизация проводится в классе ДНФ методом минимизирующих карт. Функция должна быть задана её таблицей истинности или её СДНФ. Минимизирующая карта имеет 2строк, где n – число переменных функции, и на единицу меньше столбцов. Например, для n=3:

x	y	z	xy	xz	yz	xyz
x	y	z	xy	xz	yz	xyz
x	y	z	xy	xz	yz	xyz
x	y	z	xy	xz	yz	xyz
x	y	z	xy	xz	yz	xyz
x	y	z	xy	xz	yz	xyz
x	y	z	xy	xz	yz	xyz
x	y	z	xy	xz	yz	xyz

Использование карты основано на следующем: если какая то конъюнкция последнего столбца карты не входит в СДНФ функции, то все конъюнкции этой строки не входят ни в одну ДНФ функции. Возьмём функцию f(x, y,z)=(xz)(yz) с таблицей истинности, представленной выше. Далее убираем из карты строки, соответствующие конъюнкциям, не вошедшим в СДНФ функции:

x	y	z	xy	xz	yz	xyz
x	y	z	xy	xz	yz	xyz
x	y	z	xy	xz	yz	xyz
x	y	z	xy	xz	yz	xyz

Вычеркнутые в этих строках конъюнкции убираем во всех остальных строках карты. В каждой строке оставляем конъюнкции с наименьшим числом сомножителей:

					yz
			xy	xz
			xy		yz
				xz

Видно, что yz и xz обязательно войдут в ответ, так как они остались по одному в строке, они же составят результат.