2-10. ФУНКЦИОНАЛЬНАЯ ДЕКОМПОЗИЦИЯ

С ростом числа аргументов ФАЛ быстро возрастает сложность задачи минимизации. Как показали многочисленные исследования, даже при использовании современных вычислительных машин практически оказывается возможным минимизировать функции с числом аргументов, не превосходящим 30—35. Выходом из этого положения может служить нахождение не минимальной формы данной функции переменных, а представление ее в виде

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

Представление функции в виде (2-33) называется функциональной декомпозицией этой функции.

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

Если функция представима в виде

то функциональная декомпозиция называется простой. Простая функциональная декомпозиция может быть как разделительной, так и неразделительной. Функциональную декомпозицию вида (2-33) будем называть (-кратной функциональной декомпозицией. Простая функциональная декомпозиция при этом может

быть названа однократной функциональной декомпозицией.

Примером функциональной декомпозиции может служить представление функции в виде разложения по аргументу:

которое может быть представлено в виде

где

В полученном представлении обозначим и через — через Через будем обозначать число элементов множества М. В нашем случае

Обобщим функциональную декомпозицию на случай

Значок 0 означает, что пересечение множеств пусто. Как следует из (2-34), рассматриваемый нами случай есть простая разделительная функциональная декомпозиция, отличная от тривиальной декомпозиции такого вида — разложения функции по ее аргументу. Для нахождения декомпозиции такого типа воспользуемся методом, предложенным А. Кертисом.

Пусть мы имеем функцию для которой проверяется возможность ее представления в виде (2-34) при условии, что Зададим некоторое разбиение множества аргументов функции на два ненересекающихся подмножества, содержащих каждое не менее двух аргументов.

Каждому набору из множеств и сопоставим их номера (это сопоставление описано в § 1-7). Тогда множество номеров наборов из содержит все номера от О до включительно, а множество номеров наборов из содержит все номера от 0 до включительно. Построим теперь матрицу размером Строки и столбцы этой матрицы перенумеруем соответственно от 0 до 2 1—1 и от 0 до На пересечении строки с номером и столбца с номером запишем значение исходной функции на наборе аргументов, который является композицией наборов с номерами и При получении этой декомпозиции следует учитывать истинную нумерацию аргументов в X.

Пример 2-24. Записать в матричной форме описанного вида функцию заданную следующей таблицей, при условии, что

Матрица данной функции имеет вид:

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

Будем для удобства обозначать элементы множества как а элементы множества — как При этом Каждый столбец матрицы можно рассматривать как функцию вида

где — фиксированный набор значений аргументов из , номер которого соответствует номеру данного столбца. Аналогично каждую строку матрицы можно рассматривать как функцию вида где — фиксированный набор значений аргументов из номер которого соответствует номеру данной строки. Тогда нетрудно видеть, что возможно представление исходной функции в двух следующих формах:

и

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

Теорема 2-6. Функция алгебры логики допускает простую разделительную функциональную декомпозицию нетривиального вида тогда и только тогда, когда матрица, соответствующая заданному разбиению множества X на подмножества и содержит не более двух различных столбцов.

Докажем сначала необходимость. Пусть функцию можно представить в виде

Из (2-37) следует, что

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

Докажем теперь достаточность условий теоремы. Пусть матрица содержит не более двух различных столбцов. Покажем тогда, что исходная функция может быть представлена в виде (2-34). Так как каждый столбец есть функция вида то сопоставим два различных столбца, имеющихся по условию в матрице, произвольным образом функциям (если в матрице нет различных столбцов, то исходная функция не зависит от аргументов, входящих в множество ).

Определим теперь функцию следующим образом. Она равна нулю на всех наборах для которых имеет место равенство и равна единице для всех наборов для которых имеет место равенство Заменяя после этого на получаем:

Теорема доказана.

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

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

Отметим, что при поиске простой разделительной декомпозиции, отличной от тривиальной или разделительной (-кратной декомпозиции, необходимо просмотреть различные разбиения множества X на множества и процесс перебора таких разбиении

заканчивается либо при нахождении такого разбиения, которое удовлетворяет условиям теоремы 2-6, либо при исчерпании всех возможных способов разбиения, число которых равно

Заметим, что поиск декомпозции некоторой ФАЛ приводит в случае успеха этого поиска к построению некоторой скобочной формы представления данной функции.

Пример 2-25. Найти простую разделительную декомпозицию для функции принимающей значение 1 на наборах аргументов с номерами 0, 6, 7, 8, 13, 15, 17, 19, 22, 23, 24, 25, 27, 28. На остальных наборах функция принимает значение, равное 0.

Произведем разбиение множества X на подмножества . В соответствии с заданием функции стоонм матрицу:

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

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

2-6. Для построенной нами матрицы число различных столбцов равно четырем. Эти столбцы имеют вид:

Как следует из обобщения теоремы 2-6, возможно построение декомпозиции исходной функции в следующем виде:

Определяем для чего сопоставляем этим

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

Отсюда

Следовательно,

Аналогично

Окончательно после упрощений получаем:

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

Будем говорить, что два набора значений переменных из множества совместимы, если , где означает множество переменных, не вошедших в , но содержащихся в X. В

протйвном случае два набора и будем называть несовместимыми. Отношение совместимости разбивает все множество наборов значений переменных из на классы, в каждый из которых попадают лишь совместимые наборы. Число таких классов зависит от вида исходной функции и выбранного множества . Обозначим его как Рассмотрим теперь функцию которая принимает различные значения на различных классах совместимости. Значения этой функции мы будем представлять двоичной записью в разрядах, где если если Каждую компоненту в этой записи будем рассматривать как функцию, определенную на множестве .

Пример 2-26. Пусть имеется функция шести переменных, принимающая значение 1 на наборах с номерами 2, 12, 17, 28, 44, 45, 50, 61, 62. В качестве множества возьмем множество -Выпишем классы совместимых наборов Для удобства запишем наборы, на которых функция по условию принимает значение 1 в двоичном виде:

Если же в качестве множества взять множество аргументов то разбиение на классы совместимых наборов будет выглядеть следующим образом:

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

Если выбрать кодирование, совпадающее с номером класса совместимости, то для первого рассмотренного случая получим:

(кликните для просмотра скана)

Звездочка в этой таблице стоит против тех наборов, на которых функция не определена. Эти наборы никогда не возникают, так как функция не принимает значений, равных 0 и 7. Исходная функция зависящая от шести переменных, сведена нами к функции, зависящей от пяти переменных,

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

Заметим, что при первом способе выбора множества X мы не получили фактически никакого уменьшения числа переменных так как вместо аргументов в ней появились аргументы

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

Мы рассмотрели лишь самый простой вид функциональной декомпозиции. В § 3-8 мы рассмотрим некоторые проблемы, связанные с неразделительной функциональной декомпозицией.