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

5.2. Каноническая система преобразований универсальных дискретных модулей

Из приведенных выше данных видно: для полного описания работы МПЭ требуется формальная модель, которая включает некоторую процедуру перечисления либо всех функций из фиксированного класса \[ (F_{\alpha}\in\{F_{\alpha}\} \] - универсальный дискретный модуль (УДМ)), либо только из некоторого подкласса ( \[ F_{\alpha} \in \{\tilde{F}_{\alpha}\} \subset \{F_{\alpha}\}(F_{\alpha} \in \{\tilde{F}_{\alpha}\} \subset \{F_{\alpha}\} \] - многофункциональный дискретный модуль (МДМ)). В любом случае исходным для такого перечисления является класс или множество функций и задаваемые ими отношения эквивалентности. Поэтому раскроем роль и место преобразований, сохраняющих отношение в классах произвольнозначных логических и дискретных функций, заданных (5.2).

Определение 5.1. Подмножество \[ \{X^{s}_n\} _{b_j}\subset \{X^{s}_n\} \] наборов значений аргументов функции \[ F_{\alpha} \] называется эквизначным, если функция принимает на нем одно и то же значение \[ b_j \] : \[ F_{\alpha} (\{X_n^s\}_{b_j}) = const = b_j \]

Например, двузначная ЛФ двух переменных \[ F_{1}(x_2, x _{1}) = x _{2}*x _{1} \] принимает значение "ноль" на наборах \[ X_2^0 = (0,0), X^1_2 = (0,1), X_{2}^{2} = (1,0) \] и значение "единица" на наборе \[ X_{2}^{3} = (1,1) \] , то есть ЛФ "И" разбивает все векторное пространство \[ \{X_{2} ^{S}\} \] на два подмножества \[ \{X_{2} ^{S}\}_{0} \] и \[ \{X_{2} ^{S}\}_1 \] мощности \[ 3 \] и \[ 1 \] соответственно.

Для произвольных \[ \gamma \] -значных функций ( \[ \gamma = \overline{1,k} \] ) число эквизначных подмножеств равно \[ \gamma \] .

Обозначим через \[ r_j = \{X_n^s\}_{b_j}| \] мощность \[ j \] -го эквизначного подмножества ( \[ r_j =\overline{0,Q + 1} \] ; \[ j = \overline{1,\gamma } \] ; \[ \sum_j{r_j}=Q + 1 \] ).

Из определения 5.1 и (5.2) следует, что каждый вектор \[ X^{s}_n \] принадлежит только одному "эквизначному" подмножеству и поэтому отношение эквизначности является отношением эквивалентности, так как оно разбивает все множество \[ \{X^{s}_n\} \] на непересекающиеся подмножества \[ \{X^s_n\} _{b_j}. \]

Справедливо утверждение 5.2: функция \[ F_{\alpha} \] и задаваемое ею отношение \[ R_{\alpha 1} \] эквизначности на множестве входных векторов \[ \{X^{s}_n\} \] инвариантны перестановкам \[ \{Ф_{w}\}_{R_{\alpha 1}} \] элементов внутри эквизначных подмножеств.

Следствие 5.1. Функция \[ F_{\alpha} \] инвариантна множеству перестановок мощности:

\[ |\{Ф_w\}_{R_{\alpha 1}}| = \prod_{j=1}^{\gamma}{r_j!} \]

Для простоты будем считать, что преобразования \[ \{Ф_w\}_{R_{\alpha 1}} \] определены на множестве индексов \[ \{s\} \] , а \[ \lambda \] -разбиения на эквизначные подмножества формируются вектором порогов \[ H_{\chi} \] с целочисленными компонентами \[ h_j (j\overline{1,\chi}) \] заданными на \[ \{s\} \] .

Из определения 5.1 и (5.2) следует утверждение 5.3: отношение эквизначности, задаваемое фиксированным разбиением \[ \lambda \] , инвариантно подмножеству функций \[ \{F_{\alpha}\}_{\lambda}\subset \{F_{\alpha}\} \] , отличающихся только порядком размещения своих у значений над эквизначными подмножествами этого разбиения.

Следствие 5.2.1-разбиение заданной функции \[ F_{\alpha} \] инвариантно множеству функций \[ \{F_{\alpha}\}_{\lambda} \] мощности:

\[ |\{F_{\alpha}\}_{\lambda}| = A^{\gamma}_{\chi+1} \]

где \[ A^{\gamma}_{\chi+1} \] - размещения (возможно с повторениями) \[ \gamma \] значений \[ F_{\alpha} \] над \[ (\chi+1) \] эквизначным множеством.

Утверждения 5.2 и 5.3 говорят о том, что эквизначные подмножества \[ \{s\}^{\lambda}_{m_j} \] в одном и том же разбиении \[ \lambda \] можно рассматривать как неупорядоченное множество неупорядоченных подмножеств, отличающихся только количеством \[ r_{j} \] элементов в каждом.

Отсюда следует утверждение 5.4: фиксированное отношение эквизначности инвариантно перестановкам собственных равномощных подмножеств.

Обозначим через \[ \rho^{\lambda}_m \] мощность множества эквизначных подмножеств, имеющих в фиксированном \[ \lambda \] -разбиении одну и ту же мощность

\[ r_j^{\lambda} =m(\rho^{\lambda}_m=\overline{0,Q+1}, m=\overline{0,Q+1}) \]

Следствие 5.3. Отношение эквизначности инвариантно множеству перестановок \[ \{Ф_{\аlpha}\}_{R_{\аlpha 2}} \] собственных равномощных подмножеств, мощность которого:

\[ |\{Ф_{\аlpha}\}_{R_{\аlpha 2}} | = \prod_m{\rho^{\lambda}_m!} \]

В комбинаторике [90] числа \[ \{r^{\lambda}_m\} \] и \[ \{\rho^{\lambda}_m\} \] называют соответственно первичной и вторичной спецификациями, характеризующими с количественной стороны фиксированное \[ \lambda \] - разбиение. Чтобы учесть качественные отличия \[ \lambda \] -разбиений с одной и той же первичной и вторичной спецификациями, необходимо отличать эквизначные подмножества по составу входящих в них элементов.

Введем множество \[ G \] всевозможных перестановок векторов \[ X^{s}_n \] по индексу \[ s \] , такое, что мощность \[ |G| = (Q+1) \] !. Тогда мощность \[ M_{w} \] множества \[ \lambda \] -разбиений, отличающихся только составом элементов в соответствии с (5.5 2.11) и (5.7 2.13) будет:

\[ M_w=\cfrac{(Q+1)!}{\prod_j{r_j^{\lambda}!}\prod_m{\rho_m^{\lambda}!}} \]

С учетом (5.6 2.12) мощность только \[ \gamma \] -значных функций \[ \{F_{\alpha}\}_{\gamma} \] (из класса \[ k \] -значных), инвариантных фиксированному \[ \lambda \] -разбиению, будет:

\[ M_{\gamma}^{\lambda} = | \{F_{\alpha}\}_{\gamma}^{\lambda}| = \cfrac{(Q+1)!k!}{\prod_j{r_{j}^{\lambda}!}\prod_j{\rho_{m}^{\lambda}!}(k-\gamma)!} \]

где вектор порогов \[ Н_{\chi} \] всегда имеет минимальную размерность \[ \chi = \gamma - 1 \] .

Мощность всего \[ \gamma \] -значного (под)класса функций:

\[ M_{\gamma}= \sum_{\lambda}{M_{\gamma}^{\lambda}} \]

где суммирование ведется по всем допустимым \[ \lambda \] -разбиениям.

Мощность всего \[ k \] -значного класса функций:

\[ M_k = \sum_{\gamma}{M_{\gamma}} = \sum_{\gamma}\sum_{\lambda}{\cfrac{(Q+1)!}{\prod_j{r_j^{\lambda}!}\prod_m{\rho_m^{\lambda}!}}} \]

где суммирование ведется по всем минимально пороговым \[ \lambda \] -разбиениям числа \[ (Q+1) \] , удовлетворяющим условию \[ \chi \le \gamma - 1 \] .

В таблицах 5.1, 5.2 приведены примеры расчета мощностей соответствующих (5.8)-(5.11) подклассов функций \[ F_{\alpha} \] . При анализе этих таблиц следует помнить: \[ М_w \] - мощность множества неупорядоченных подмножеств. С этих позиций разбиения со спецификациями \[ (r_0, r_1) = (2,6) \] и \[ (r_0, r_1) = (6,2) \] являются эквивалентными, и поэтому при определении мощности соответствующего подкласса учитывается только одно из них (см. табл. 5.2).

При построении (5.11) фактически использовано три оператора:

• перестановок входных векторов, мощность которого: \[ |G| = (Q+1)!; \]
• разбиений упорядоченного множества векторов \[ \{X^{s}_n\} \] на эквизначные подмножества, мощность которого: \[ |\Lambda | = \prod_j{r_j^{\lambda}!}\prod_m{\rho_m^{\lambda}!} \]
• размещений \[ \gamma \] -значных функций (с выбором из \[ k \] возможных) над эквизначными подмножествами, мощность которого: \[ |K|=\cfrac{k!}{(k-\gamma)!} \]

Именно оператор \[ K \] позволяет рассматривать \[ \lambda \] -разбиения как неупорядоченное множество неупорядоченных подмножеств, так как при любом порядке перечисления эквизначных подмножеств в фиксированном \[ \lambda \] -разбиении всегда найдется порядок размещения \[ \gamma \] значений функции, отвечающий заданному отображению \[ F_{\alpha} \] : \[ X^{s}_n \to f_s \] .

Таким образом, используя преобразования, сохраняющие отношение эквизначности, удалось показать:

1. Комбинаторное соотношение (5.11) обеспечивает перечисление классов функций (5.2), причем перечислительный (а не вычислительный [118]) характер (5.11) и отвечающих ему преобразований следует из того, что в них входит индекс разбиения \[ \lambda \] .
2. Устойчивость реализации функций типа (5.2) вообще и динамическая устойчивость в частности обеспечивается флуктуацией или блужданием "рабочей точки" по множеству перестановок входных векторов, сохраняющих отношение эквизначности, причем мощность "рабочей области" равна \[ |\Lambda| \] .
3. Напротив, адаптация МДМ на одну из функций типа (5.2) связана с перечислением соответствующих параметров в операторах \[ G \] , \[ \Lambda \] , \[ K \] , изменяющих отношение эквизначности.
4. Полученные комбинаторные соотношения позволяют ввести формальную модель работы и настройки универсальных дискретных модулей (УДМ), которая базируется не на операциях булевой алгебры, а на общих теоретико-групповых преобразованиях.

Принятая в работе форма задания функции (5.2) идентична форме задания дискретных объектов в комбинаторике [90], и поэтому процесс адаптации УДМ, состоящий в переходе от одной функции к другой, оказывается идентичен процессу перечисления дискретных объектов,

который исследуется в рамках самостоятельной теории перечислимости Дж. Пойя [118].

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

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

Перечислительный процесс типа (5.11) исходит из общей комбинаторной схемы [90], преобразования которой можно представить [119]:

\[ (K * G) : \Lambda, \]

где:

• \[ K \] , \[ G \] , \[ \Lambda \] - определенные в (5.12) соответственно группы подстановок значений реализуемой функции над эквизначными подмножествами и перестановок входных векторов и их разбиения на эквизначные подмножества;
• \[ K*G \] - (полу)прямое произведение группы \[ K \] и \[ G \] ;
• \[ \Lambda \] - подгруппа "эквизначности", заданная на (полу)прямом произведении \[ K*G \] с порядком \[ |\Lambda | = \prod_j{r_j^{\lambda}!}\prod_m{\rho_m^{\lambda}!(k-\gamma)!} \]
• \[ (K*G):\Lambda \] - разложение (полу)прямого произведения групп \[ K \] и \[ G \] по факторгруппе "эквизначности" \[ \Lambda \] [119].

Если общая комбинаторная схема исследует классы дискретных объектов с количественной стороны и в предположении, что отношение эквивалентности на множестве объектов задается произвольным образом, то система преобразований (5.13) интересует нас с качественной стороны и в предположении, что отношение эквивалентности задается функциями (5.2).

Из (5.13) видно, что система преобразований, перечисляющая все \[ F_{\alpha} \] из \[ \{F_{\alpha}\} \] , основана на преобразованиях конечной симметрической группы [103, 120, 121] (группы подстановок), которые выполняются в следующем порядке:

• вначале реализуется (полу)прямое произведение \[ K*G \] , учитывающее всевозможные способы упорядочения \[ \{ X^{s}_n\} \] и \[ f_{s} \] в двойках \[ \{(X^{s}_n, f_{s} )\} \] ;
• затем с помощью факторгруппы \[ \Lambda \] из множества полученных таким образом пар \[ \{(X^{s}_n, f_s)\} \] устраняются все эквивалентные отображения \[ \{F_{\alpha} : X^{s}_n \to f_s\}_{\alpha} \] , отвечающие заданной \[ F_{\alpha} \] .

Поэтому (5.13) описывает процесс реализации заданной функции \[ F_{\alpha} \] , если вариации параметров \[ G \] , \[ \Lambda \] , \[ K \] не нарушают заданное этой функцией отношение "эквизначности". В противном случае (5.13) описывает процесс адаптации УДМ, в результате чего происходит выбор, а значит, и последовательное перечисление \[ F_{\alpha} \] из заданного класса.

Физическому порядку выполнения преобразований (5.13) обычно отвечает последовательность "перестановки - разбиения - подстановки":

\[ G*\Lambda*K, \]

где входные ( \[ G \] ), внутренние ( \[ \Lambda \] ) и выходные ( \[ K \] ) преобразования отвечают теоретико-групповым соотношениям (5.13), возможно, с некоторыми ограничениями, как это имеет место в МПЭ [79, 80].

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