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

Образование тупиковых покрытий на заключительном этапе формализуется с помощью алгебраического метода. Простые импликанты обозначаются какими-либо символами (обычно прописными буквами латинского алфавита) и по столбцам таблицы покрытий записываются дизъюнкции тех импликант, которые отмечены в данном столбце. Смысл этой записи вытекает из того, что любая из отмеченных импликант покрывает весь данный минтерм. Покрытие функции выражается конъюнкцией всех записанных дизъюнкций. Упрощая это выражение на основе тождеств булевой алгебры, переходим к дизъюнктивной форме, каждый член которой представляет собой конъюнкцию простых импликант и соответствует тупиковому покрытию рассматриваемой функции.

Рассмотрим в качестве примера функцию четырех переменных из предыдущего параграфа. Тогда таблица покрытий имеет вид: F(A+C)(B+F)(D+E)F(A+B)(C+D)(E+F) = F(A+C)(A+B)(D+E)(C+D) = F(A+BC)(D+CE) = ADF+ACEF+BCDF+BCEF. Замещая в каждом конъюнктивном члене простые импликанты их сиволами, получаем выражение четырех тупиковых покрытий в символическом виде

С1=			´	;		С2=		´		´	;
´				´		´
	´
		´					´
С3=		´		´	;	С4=		´		´	;
						´
´		´		´
			´				´

которым соответствуют равносильные тупиковые формы:

y₁ =`х<sub>1</sub> х<sub>3</sub> х<sub>4</sub> + х<sub>1</sub>`х₂ х₄ + х₂`х<sub>3</sub>; у<sub>2</sub> = `х₁ х₃ х₄ +`х<sub>2</sub> х<sub>3</sub> х<sub>4</sub> + х<sub>1</sub>`х₃ х₄ + х₂`х₃;

у₃ =`х<sub>1</sub> х<sub>2</sub> х<sub>4</sub> +`х₂ х₃ х₄ + х₁`х<sub>2</sub> х<sub>4</sub> + х<sub>2</sub>`х₃; у₄ =`х<sub>1</sub> х<sub>2</sub> х<sub>4</sub> +`х₂ х₃ х₄ + х₁`х<sub>3</sub> х<sub>4</sub> + х<sub>2</sub>`х₃.

Каждая форма характеризуется числом входжений переменных, называемых ценой покрытия. Для первой тупиковой формы цена покрытия равна 8, а для трех остальных 11, поэтому первая форма является минимальной.

Алгебраические преобразования упрощаются, если исходить из таблицы порытий, получаемой после извлечения экстремалей до тупиковых покрытий. Сравнивая эти множества по их цене, выбираем минимальные дополнения, которые совместно с множеством экстермалей образуют минимальные покрытия. Так, в рассматриваемом примере после извлечения импликанты F на основе упрощенной таблицы покрытий записываем (A+C)(D+E)(A+B)(C+D) = (A+BC)(D+CE) = AD+ACE+BCD+BCE. Отсюда находим минимальное дополнение `х<sub>1</sub> х<sub>3</sub> х<sub>4</sub> + х<sub>1</sub>`х₂ х₄, которое совместно с экстремалью х₂`х₃ и дает минимальную форму.