1. Определение сокращенной формы множества m (сокращенного множества m).

2. Определение тупиковой формы множества m (минимального множества m).

1 Этап. Воспользуемся гиперкубом, построенным для заданного множества в примере 1 п.2 (рис.2.3).

Найдем объединение конституант, выраженных двоичными наборами, сопоставленных заштрихованным вершинам гиперкуба, которые соединены ребром, т.е. объединение конституант, отличающихся только в одном разряде:

Здесь в результирующем двоичном наборе прочерк (-) стоит на том месте, на котором в объединяемых двоичных наборах стоят 0 и 1 (рис.3.2).

Рис.3.2

Определенные конституанты отличаются друг от друга более чем в одном разряде.

Учитывая, что в двоичных наборах 0 соответствует , а 1 соответствует , и прочерк (-) означает, что множество, соответствующие этому разряду, в пересечение отсутствует, объединяем полученные двоичные наборы (конституанты). Тем самым мы получим сокращенное множество:

2 Этап. Построение минимального множества m min сводится к покрытию двумерной таблицы Квайна.

Покрытием столбцов стоками в двумерной таблице называется такое множество строк, при котором для каждого столбца найдется хотя бы одна строка из этого множества, на пересечении с которой этот столбец имеет единицу, причем при вычеркивании хотя бы одного элемента из этого множества строк указанное свойство не выполняется.

Строим таблицу Квайна. В ней столбцами являются заданные конституанты, а строками – конституанты, полученные после объединения заданных конституант:

Новые конституанты	Конституанты
	000	100	110	011	111
-00	1	1
1-0		1	1
11-			1		1
-11				1	1

Каждая конституанта строки после подстановки вместо прочерка нуля сравнивалась с конституантами столбцов. Если существует столбец с такой же конституантой, то на пересечении рассматриваемых строки и столбца ставилась единица. После этого в той же конституанте строки вместо прочерка ставилась единица и проводилась аналогичная процедура сравнения.

Если в таблице покрытий Квайна удалить вторую строку сверху, то покрытие столбцов строками будет осуществляться, т.к. в каждом столбце будет по крайней мере одна единица.

Если дополнительно удалить еще одну строку, например, третью сверху, то покрытия не будет, т.к. третий столбец не будет иметь ни одной единицы.

Если удалить в таблице одну третью строку сверху, то покрытие столбцов строками будет осуществляться.

Удаляя строки, не влияющие на покрытие столбцов строками, и объединяя оставшиеся новые конституанты, получим минимальное множество M _min .

В нашей задачи таких множеств будет два. Удаляем вторую строку сверху, тогда

Удаляем третью строку сверху, тогда

Для определения сложности заданного множества M запишем его аналитическое выражение

Тогда L(M) = 15,

Дальнейшее уменьшение сложности выражения, определяющее заданное множество, возможно с использованием скобок. Используя закон дистрибутивности пересечения относительно объединения, получим

В этом случае

Пример 4.В трехмерном пространстве J = {M₁,M₂,M₃} задано множество

Минимизировать данное множество методом Квайна.

Определить сложность заданного множества и минимизированного множества.

Построим гиперкуб, соответствующий заданному множеству M. Он изображен на рис.3.3.

Рис.3.3