8.3.4. Построение минимальных покрытий для функций, имеющих экстремали
Для большинства переключательных функций, как уже было отмечено в 8.3.1, покрытие, определяемое совокупностью минималей, не является покрытием минимального ранга. Ранг такого покрытия может быть уменьшен за счет удаления из него некоторых кодов. Напомним, что покрытием является такая совокупность кодов, которая покрывает все наборы множества Cn(φ). Назовем покрытие Н неизбыточным, если при удалении из него хотя бы одного кода оставшаяся совокупность кодов не покрывает всех наборов множества Cn(φ). Связь неизбыточных покрытий с минимальными устанавливается следующей теоремой.
| Теорема 3.2. | Любое минимальное покрытие является неизбыточным. |
Доказательство теоремы является очевидным, поскольку ранг всякого избыточного покрытия может быть уменьшен путем удаления избыточных кодов.
Для иллюстрации образования неизбыточных покрытий приведем следующий пример.
Пример 3.3.
Рассмотрим образование неизбыточных покрытий функции, приведенной в примере 3.1. Согласно примеру 3.2, множество минималей этой
функции имеет вид P = { 0zz1, 110z, 1z00, z101, z000, 000z }. Элементы множества Р изображены на рис. 8.27.
Выбирая различные способы покрытия наборов, определяющих заданную функцию, нетрудно найти все ее неизбыточные покрытия:
H2 = {0zz1, 1z00, z101, z000},
H3 = {0zz1, 110z, 1z00, 000z},
H4 ={0zz1, 1z00, z101, 000z},
Сравнивая неизбыточные покрытия, построенные в примере, нетрудно заметить, что код 0zz1 обязательно входит в каждое такое покрытие. Последнее обстоятельство объясняется тем, что наборы 0011 и 0111 покрываются только этим кодом 0zz1, и поэтому его удаление из любой совокупности кодов Hj привело бы к появлению непокрытых наборов из Cn(φ).
Назовем набор 
существенным набором, если он покрывается только одним кодом “е” из множества минималей Р, а код “е”, покрывающий хотя бы один существенный набор, назовем экстремалью. В приведенном примере код 0zz1 является экстремалью, а наборы 0011 и 0111 являются существенными наборами. Основное свойство экстремалей может быть сформулировано в виде теоремы.
| Теорема 3.3. | Все экстремали входят в любое неизбыточное покрытие заданной функции. |
Доказательство теоремы очевидно, поскольку каждая экстремаль покрывает хотя бы один набор , который не покрывается никаким другим кодом из Р.
Из последней теоремы вытекают два важных следствия.
Следствие 1.
Все экстремали входят в любое минимальное покрытие заданной функции.
Следствие 2.
Если минимальное покрытие состоит из экстремалей, то такое покрытие является единственным.
Основываясь на теореме 3.3 и следствии 1, второй этап минимальных покрытий имеет смысл начать с выделения обязательной части любого минимального покрытия, т. е. с нахождения множества экстремалей Е.