Борис Цирлин

Определяется понятие изоморфности схем, построенных из логических элементов. Предлагаются алгоритмы подсчета таких схем.

Введение

В статье "Полумодулярные схемы" рассматривались схемы из nлогических элементов, заданные системами из n логических уравнений. Для каждого элемента в каждом состоянии схемы определялось понятие "возбуждения" - когда значение его выхода не соответствовало значению определяющей его логической функции в уравнении. Было введено понятие "векто возбуждений", как последовательность Q из G = 2**n чисел, где G очевидно равно числу состояний схемы (** символ возведения в степень - как и раньше будем использовать систему обозначения для математических операций, принятую в алгоритмическом языке Питон). Каждая компонента Q[i] вектора возбуждение может иметь одно из G возможных значений, т.е. 0=<G<2**n, откуда понятно, что число таких схем определяется формулой:

N = G**G = (2**n)**(2**n)

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

Пронумеруем переменные, соответствующие выходам схемы, т.е. имеем набор x1, x2,...,xn. Теперь обозначим выход x1 через x2, а выход, ранее бывший x2 - через x1. Фактически схема останется идентичной исходный, но вектор возбуждения очевидным образом изменится. Из школьного курса известно, что число таких перестановок n переменных равно n! (n факториал), что, в принципе, и определяет число изоморфных схем полученных таким образом.

Второй способ получения изоморфных схем не столь прозрачен. Он заключается в использовании, вместо какой-либо переменной xk, ее инверсии ~xk. Напомним, что инверсия переменной имеет значение противоположное значению самой переменной, т.е. если xk = 1, то ~xk = 0 и наоборот, если xk = 0, то ~xk = 1, так что значение xk, вырабатываемое схемой, будет инверсно, по сравнению с исходной, что, естественно, изменит и ее вектор возбуждения. Но использоваться-то теперь будет ~xk вместо xk, т.е. фактически в схеме ничего не поменяется. Каждая из n переменных при этом способе может либо остаться в натуральном виде , либо инвертирована, что дает знакомые

G = 2**n

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

K = (n!)*G = (n!)*(2**n)

изоморфных и, казалось бы, поделив число N на К, наконец, узнаем сколько всего различных схем из n элементов имеют место:

N/K = ((2**n)**(2**n))/((n!)*(2**n)) = (2**n)*(2**n - 1)/n!

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

В качестве примера рассмотрим уникальную схему, не имеющую изоморфных вообще. Для n = 3 она задается системой логических уравнений:

x1 = x1; x2 = x2; x3 = x3.

Все ее переменные устойчивы во всех ее 8 состояниях, т.е. она имеет нулевой вектор возбуждений.

Формализация получения изоморфных схем перестановками

Начнем с самих перестановок, которые, для заданного n, определим, используя готовую программу (обычно она называется permutation), образцы которой имеются интернете. Результат работы такой программы для n = 3 - это список вида:

pertmutation(3) = [[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]],

не требует пояснений. Далее построим двумерный список s измененных состояний, в которые преобразуются состояния исходной схемы в результате применения перестановок. При этом первой координатой в s будут номера перестановок из permutation, а второй - номера состояний (или компонент вектора Q возбуждений). Два состояния схемы, а именно такие, в которых значения всех выходов ее элементов одинаковы и равны 0 или 1 - инвариантны к перестановкам, остальные же легко вычислить, представив состояния исходной схемы в двоичном коде, а затем, изменив веса компонент этого кода в соответствии с выбранной перестановкой, сложить эти модифицированные компоненты.
Заметим, что список s справедлив и для измененных компонент векторов возбуждений. На рисунке приведен список s для n = 3.

Для любой i-й перестановки из permutation, j-й компоненте вектора Q возбуждения некоторой схемы соответствует s[j][i]-я компонента вектора возбуждений, для изоморфной схемы. При этом соответствие это взаимно однозначное, что следует хотя бы из того, что в каждом столбце в s нет повторяющихся цифр. Значение этой компоненты определяется тоже с помощью списка s и равно s[Q[j]][i], а ее вес в составе номера схемы M[i] равен G**s[j][i]. Т.е. номер M[i] схемы, соответствующей данной для перестановки i, вычисляется циклом:

for j in range(G): M[i]+=s[(Q[j])][i]*G**s[j][i]

Формализация получения изоморфных схем инверсией

Для реализации этого способа получения изоморфных схем достаточно вспомнить, что для нумерации всех возможных способов инвертирования использовалось кодирование - 1 наличие инверсии переменной в данном варианте и 0 - если переменная не инвертируется. В булевой алгебре именно так определяется операция "исключающее или". Т.е. при j-м
способе инвертирования, i-е состояние исходной схемы (номер компоненты Q) трансформируется в состояние i^j ("исключающее или" i и j)изоморфной схемы с номером N[j], что сделает ее вес в этом номере равным G**(i^j). При этом значение самой компоненты не измениться, а этот номер вычисляется циклом:

for i in range (G): N[j]+=Q[i]*G**(i^j)

Замечания к программной реализации

В главном цикле программа перебирает номера I схем по возрастанию - от 0 до G**G. Для каждой определяется сначала список М изоморфных по перестановкам, а потом, для каждого его члена M[i] - по инверсии. Результат последнего действия сводится в общий список N схем, изоморфных данной.

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

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

l=len(set(N))

Подсчитав количество, полученных таким образом, списков N изоморфных схем, как раз и определим искомое число различных (не изоморфных) схем из n элементов. Заодно появляется возможность рассортировать списки изоморфных схем по длине, что интересно с точки зрения понимания структуры этого феномена.
Листинг обсуждаемой программы приведен ниже.

Заключение

В статье "Полумодулярные схемы" были определены формальные признаки принадлежности схемы этому классу, позволившие подсчитать количество таких схем для n = 1, 2 и 3, где n, как всегда, число ее элементов. Добавив в обсуждаемую программу такую же проверку (место для вставки выделено комментариями), получим число не изоморфных полумодулярных схем и их распределение по различной длины спискам изоморфных.

Такую же процедуру можно проделать с проверкой схемы на принадлежность ее классу последовательных, признаком нарушения которой является значение компоненты Q[i] вектора возбуждения соответствующее возбуждению более одного элемента, т. е. при n = 2:

Q[i] == 3,

а при n = 3:

(Q[i] == 3) or (Q[i] == 5) or (Q[i] == 6) or (Q[i] == 7)

Такие эксперименты были проделаны и все результаты сведены в табл. 1 и табл. 2.

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

Назовем последовательности изоморфных схем ущербными, если число членов этих последовательностей меньше максимально возможного K, напомним:

K = (n!)*(2**n)

Из сравнения табл. 1 и 2 видно, что хотя с ростом n число ущербных последовательностей растет, их доля по сравнению с количеством не ущербных падает. Это позволяет предположить, что число не изоморфных схем с ростом n приближается (сверху) к предложенной оценке N/K.

Такой же вывод можно сделать и для последовательных и полумодулярных схем.