4.8.3. Визуально-матричный метод минимизации

Логическая функция может быть представлена на матричной форме (рис. 4.7). Матричная форма - таблица, каждая клетка которой соответствует одному из наборов таблицы истинности. Множество переменных разбито на подмножество младших и старших переменных. Столбцам таблицы сопоставляются различные комбинации значений младших (старших) переменных. Единичное значение переменной отмечено чертой над соответствующими столбцами или строкой, нулевое – отсутствием черты. В клетки матрицы заносятся значения логической функции на соответствующем наборе – единичные значения функции отмечаются точкой, нулем – отсутствие точки.

Рис. 4.7

На каждой матричной форме выделены оси симметрии той или иной переменной х_i (линии смены значения этой переменной). Каждой оси симметрии соответствует зона симметрии, серединной линией которой является ось симметрии, а ширина зоны равна 2^r, где r – ранг оси симметрии.

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

Интервал – множество наборов значений переменных, на которых элементарная конъюнкция принимает значений «1», т.е. характеристическим множеством элементарной конъюнкции.

Интервал, соответствующий элементарной конъюнкции k-го ранга, получаем путём пересечений опорных интервалов, соответствующих k конъюнкциям 1-го ранга.

Задание булевых функций в ДНФ сводится к размещению точек (единиц) по клеткам матричной формы ее элементарных конъюнкций.

Например, на данной матричной форме функции 4-х переменных представлена элементарная конъюнкция 2-го ранга х₁х₂ (рис. 4.8).

Рис. 4.8.

На данной матричной форме функции 4-х переменных представлена элементарная конъюнкция 2-го ранга (рис. 4.9).

Рис. 4.9.

На данной матричной форме функции 4-х переменных представлена элементарная конъюнкция 3-го ранга (рис. 4.10).

Рис. 4.10.

Если две элементарные конъюнкции - соседние по переменной х_i, то их можно склеить по этой переменной х₁х₂х₃ V х₁х₂х₃ = х₁х₂ и получить элементарную конъюнкцию меньшего ранга. На матричной форме это соответствует тому, что интервалы, соседние по переменной х_i, можно покрыть интервалом, более крупным (т.е. найти покрывший их интервал).

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