Минимизация системы булевых функций. Синтез ПЛМ с заданной выходной матрицей, страница 6

упрощаемое затем описанным выше методом минимизации числа единиц и нулей в матрице X* до следующего ее значения.

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

Поиск приближений к оптимальному решению. С ростом числа столбцов в матрицах Х и Y нахождение точного решения рассматриваемой задачи может стать практически невозможным из-за огромного числа различных интервальных миноров системы (X, Y). В этом случае приходится отказываться от рассмотрения всех их и переходить к конструированию некоторых приближений к кратчайшей ДНФ.

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

По аналогии с методами минимизации одной булевой функции методы минимизации системы (X, Y) можно разбить на два класса, включив в первый из них такие, когда интервальные миноры, из которых конструируется решение, находятся последовательно, а во второй — параллельно.

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