2.9. Минимизация слабоопределенных бф

В п. 1.1 было введено понятие слабоопределенных функций, для которых характерно большое число переменных, а число наборов, на которых функция определена, невелико. Из-за большого числа переменных метод карт Вейча неприменим, а метод Квайна-Мак-Класки требует записи большого числа выражений соответствующих неопределенным наборам.

В таких случаях целесообразнее использовать сопоставление множества единичных наборов с множеством нулевых наборов . В п. 2.8 мы оперировали с множествами наборов и (множество неопределенных наборов). Но в данном случае множество может быть значительно больше множества ( ). Поэтому для слабоопределенных функций удобнее задавать их в виде двоичных кодов, соответствующих множествам и . Рассмотрим для начала простой пример:

Пример 2.18. Функция задана наборами множеств в виде двоичных кодов:

; .

Применив к этой функции минимизацию по методу Квайна-Мак-Класки или карт Вейча, легко находим минимальные ДНФ и КНФ, которые совпадают .

Попробуем применить к этому примеру метод сопоставления множеств наборов и . Сравнивая элементы множеств, можно заметить, что:

- все элементы множества начинаются с нуля. Два элемента множества начинаются с единицы. Их можно заменить одним элементом (1---), так как ни один из элементов множества не входит в эту группу;

- первые два элемента отличаются от всех элементов значением нуля во втором (слева) разряде, поэтому их можно заменить выражением (-0--).

Можно сделать вывод, что заданную функцию можно представить наборами

,

или в виде минимальной ДНФ:

.

Анализируя множество можно получить тот же результат. Все элементы множества начинаются с начальных цифр 01, значит, набор (01--) покрывает все члены и не покрывает ни одного из элементов множества , следовательно,

- минимальная КНФ.

В общем случае упрощение слабоопределенных БФ заключается в анализе множеств и и поиске выражений, состоящих из элементов, отличающих наборы одного множества от другого. Алгоритм может быть записан в следующей последовательности:

1. Составляется таблица, строки которой суть наборы , а столбцы – множество (или наоборот);

2. В таблицу вписываются десятичные числа, соответствующие номерам разрядов, отсчитываемых слева направо, в которых отличается двоичный код строчки и столбца (например, на пересечении строки (0011) и столбца (1001), запишем 1,3).

3. В последний столбец для каждой строчки и в последнюю строчку для каждого столбца записываются минимальные наборы таких чисел, которые присутствуют во всех столбцах данной строки (во всех строчках данного столбца).

Например, в строке 1,2 – 2,3 – 2,4 таким минимальным набором будет 2, а в строке 1,2 – 2,5 – 3,4 минимальными наборами будут 1,3; 2,3; 2,4;

4. Если среди выписанных минимальных наборов чисел есть наборы с меньшим (чем остальные) числом символов, нужно проверить, нельзя ли их заменить другими наборами из числа выписанных.

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

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

Пример 2.19.

; .

Составляем таблицу различий наборов.

Таблица 2.24. Таблица различий наборов

№	1000101	1011110	1101110	1110111
0100101	12	1234 67	1 4 67	1 3 6	1; (26)
1000110	67	34	2 4	23 7	4,7
1010000	3 5 7	456	23456	2 567	5; (1,7)
1010110	3 67	4	234	2 7	4,7
1110101	23	2 4 67	34 67	6	2,6;3,6
	2 7	4	4	26; 67

Найдем для каждого столбца минимальные наборы чисел, содержащихся во всех его строчках (п. 3).

Получим числа 2,7 – 4 – 4 – 2,6; 6,7.

Им соответствуют выражения:

2,7 – (-0----1)

4 – (---1---)

4 – (---1---)

2,6 – (-1---1-); 6,7 – (------11)

Набор 4 не может быть заменен другим. Имеем два варианта минимизации.

, или

и , или .

Запись в ДНФ, т.к. мы анализировали столбцы ( ). Попробуем записать в КНФ. Анализируем строки таблицы. Минимальными наборами чисел будут 1-4,7-5-4,7-2,6;3,6.

Но вместо набора (1) можно использовать набор (2,6) из последней строки, а вместо набора 5 – использовать набор (4,7), т.к. он есть еще во 2-й и 4-й строках. Тогда совокупность наборов будет 2,6-4,7-4,7-2,6.

Этим наборам соответствует

или .

Это выражение проще, чем предыдущие.

Эта минимизация является приближенной. Для поиска минимизации выражений необходим перебор всех вариантов минимальных наборов чисел (по п. 3) и выбор из них минимального, покрывающего все элементы множества или . Но на практике обычно такие переборы не делаются, т.к. полученная форма удовлетворяет.