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

2016 Теоретические основы прикладной дискретной математики №2

УДК 512.13

ПОСТРОЕНИЕ ПОДСТАНОВОК НА ОСНОВЕ ПОРОГОВЫХ ФУНКЦИЙ МНОГОЗНАЧНОЙ ЛОГИКИ

Д. А. Сошин ФГУП «НИИ «Квант», г. Москва, Россия

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

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

DOI 10.17223/20710410/32/2

CONSTRUCTING SUBSTITUTIONS ON THE BASIS OF THRESHOLD FUNCTIONS OF MULTIVALUED LOGIC

D. A. Soshin

Technology Federal State Unitary Enterprise "Research Institute Kvant", Moscow, Russia

E-mail: danil_re@list.ru

An algorithm for building one-to-one mappings (substitutions) with the help of coordinate threshold k-valued logic functions is presented. The algorithm includes a geometric way of generating balanced threshold functions and two ways to produce substitutions from these functions — by forming triangular systems and by algorithmic searching. Results of experimental testing the algorithms are given.

Keywords: threshold functions, multiple-valued logic, balanced functions, regular systems.

Введение

Работа посвящена построению подстановок на основе пороговых функций k-знач-ной логики [1-4]. Для этого на первом этапе, в соответствии с требованиями критерия Хаффмана, строится класс сбалансированных пороговых k-значных функций от n переменных, для любых n ^ 3 и k ^ 2. Сбалансированные функции представляют и самостоятельный интерес при синтезе узлов переработки дискретной информации с точки зрения своих статистических свойств [5]. На втором этапе при помощи сбалансированных функций описанного класса строятся компактно реализуемые подстановки [4, 6]. В работе предложены два способа построения подстановок. Первый основан на формировании треугольных систем с использованием пороговых функций, которые заведомо порождают подстановки. Второй способ применяет алгоритмический поиск подстановки на базе одной из сбалансированных функций с помощью легко реализуемых операций, обобщающих преобразования движения или вращения. Доказаны утверждения, позволяющие сократить количество проверяемых вариантов. В заключение приведены результаты применения построенного алгоритма поиска регулярных систем.

1. Геометрический метод синтеза к-значных сбалансированных

пороговых функций

Будем обозначать Пк = {0,1,..., к — 1}.

Определение 1. Функция к -значной логики f : П^" —^ Пк называется пороговой, если для нее существует линейная форма

Ь(Ж1,Ж2, ...,Ж„) = С1Ж1 + С2Х2 + ... + С„Ж„, С € Ъ, % = 1,...,П,

и пороги Ь0,Ьь...А € Ъ, такие, что для любого а € {0,... , к — 1} выполняется

f (Х1,Х2, . . . ,Хп) = а ^ Ьа ^ С1Х1 + С2Ж2 + ... + С„ж„ < Ьа+1.

Определение 2. Слоем ) (носителем значения а) пороговой функции f будем называть те и только те точки множества П^, в которых функция f принимает значение а, а = 0,... , к — 1. Если из контекста понятно, слой какой функции рассматривается, будем опускать символ функции и писать Да.

В геометрическом смысле каждое неравенство с1х1 + с2х2 + ... + сгажга < Ьа задаёт полупространство, лежащее по одну сторону от гиперплоскости Ьа, определяемой равенством с1х1 + с2х2 + ... + сгажга = Ьа, а слой Да —множество целочисленных точек п-мерного куба со стороной длины к — 1, расположенных между двумя соседними гиперплоскостями Ьа и Ьа+1, включая точки гиперплоскости Ьа.

Далее пороги Ь0 и Ьк и соответствующие им гиперплоскости Ь0 и Ьк рассматривать не будем, поскольку они не несут смысловой нагрузки.

Функция f является сбалансированной, если слои Дa(f), а = 0,... , к — 1, равно-мощные.

Для описания метода построения сбалансированных пороговых функций введём понятие среза Ба —множества точек {(а1, а2,... , ага-1, а) € П^}. Будем говорить, что гиперплоскость Ьа(х1, х2,..., хп) = 0, где Ьа(х1, х2,..., хп) = с1х1 + с2х2 +... + сгажга+Ьа, пересекает срез, если существуют две точки этого среза, для которых выполняется одно из условий:

1) эти точки лежат по разные стороны от гиперплоскости [7];

2) одна точка принадлежит гиперплоскости, а для другой выполнено неравенство Ьа(х1,х2, . . . ,Хп) < 0.

Если Ьа(х1, х2,... , хп) = 0 — уравнение гиперплоскости, то будем говорить, что гиперплоскость отделяет (отсекает) точки среза £а, если для этих точек выполнено условие

Ьа(аьа2,... ,а„_1,а) ^ 0.

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

¿(1) = (г, 0, 0, 0,..., 0, 0, а),

¿(2) = (0, г, 0, 0,..., 0, 0, а),

. . .

¿(га-1) = (0,0, 0, 0,..., 0, г, а), ¿(га) = (к — г, к — 1,...,к — 1, а — 1),

то есть при подстановке их в Ьа(Х1, Х2,..., Хп) выполняется равенство

Ьа (¿(Л) =0, 3 = 1, . . .

Проходя через точки ¿(1), ¿(2),... , ¿(п 1), гиперплоскость Ьа отделяет в срезе 50, множество точек

{(аь а2,..., а«-1, а) е Пп : а + ... + ап_1 ^ г} ,

которые не войдут в слой Да-1. Прохождение гиперплоскости через точку ¿(п) позволяет отделить в срезе 5а-1 множество точек

{(й1, Й2,... , Оп-1, а — 1) е ПП : а + ... + ап-1 ^ (к — 1)(п — 1) — г + 1} , которые войдут в слой Да-1. В силу равномощности множеств

{(аьа2,... ,«п-1,а) е П^ : а1 + ... + ап-1 ^ г — 1} и {(а1, а2,..., ап-1, а — 1) е П^ : а1 + ... + ап-1 ^ (к — 1)(п — 1) — г + 1}

и в случае, если гиперплоскости Ьа не пересекают более двух срезов, такая последовательная компенсация для каждого слоя позволяет сохранит сбалансированность.

Расстояние г будем называть отступом точек от точки

(0, 0,... , 0, а) среза 5а. Отступ первых п — 1 точек в системе (1) связан с удобством задания точки ¿(п) в срезе 5а-1, через которую пройдёт гиперплоскость. Для случая произвольного выбора отступов необходимо найти самую близкую целочисленную точку среза 5а-1 к прямой (для п ^ 4 — к гиперплоскости) пересечения плоскости Ьа и плоскости 5а-1, описываемой уравнением Хп = а — 1. В рассмотренном случае выбор последней точки не вызывает сложности. Для произвольных параметров п, к и произвольных отступов от крайней точки последняя задача не имеет общего решения, но для каждого фиксированного случая её можно решить и построить любую сбалансированную пороговую функцию.

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

Теорема 1. Пусть Яп = к — 2г + (п — 2)(к — 1), РП = г + аЯп для некоторых к ^ 2, г ^ 1, п ^ 2; а = 1,... , к — 1. Пороговая функция f (х1,х2,... ,хп), заданная двусторонними неравенствами

f

где (Ь1, Ь2,... , Ьк-1) = (Рп, Рп,... , Рп-1), при (к — 1)(п — 1) > 3г — 2 является сбалансированной пороговой.

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

С1Х1 + С2Х2 + ... + СпХп = Ьа.

Покажем, что значения порогов и коэффициентов линейной формы в условии теоремы равны соответствующим параметрам:

(Ь1,Ь2,... А-1 ) = (РГ,Р2\...,Рп-1), (с1,С2,...,Сп) = (1, 1,..., 1,Рп).

Уравнение (п — 1)-мерной гиперплоскости, проходящей через точки которые не лежат на одной (п — 2)-мерной гиперплоскости, задаётся следующим образом [7]:

х1-¿

,

Найдём данный определитель для рассматриваемого случая:

А

х1 г х2 Хз х4 . . Хп— 1 хп

г г 0 0 .0 0

г 0 г 0. .0 0

г 0 0 г. .0 0

г 0 0 0. .г 0

к — 2г к — 1 к — 1 к — 1 . . к 1 1

Добавим к первому столбцу все столбцы, кроме последнего. Столбец с номером п, умноженный на к — 2г + (п — 2)(к — 1), прибавим к первому столбцу; к остальным столбцам добавим его же, умноженным на к — 1. Через * обозначим элементы матрицы, которые не влияют на значение определителя. В результате получим

А

(х\ + Х2 + ... + Хп-1 + (хп — а)(к — 2г + (п — 2)(к — 1)) — г * *

0 г 0

0 0 г

0 0

00 00

**

00 00

г0

0 —1J

= —гп-2 (Х1 + Х2 + ... + хга-1 + (хга — а)(к — 2г + (п — 2)(к — 1)) — г).

Приравняем А = 0 и перенесём свободный член в правую часть:

—гп-2(х1 + Х2 + ... + Хп-1 + (хга — а)(к — 2г + (п — 2)(к — 1)) — г) = 0, Х1 + х2 + ... + х„-1 + (х„ — а)(к — 2г + (п — 2)(к — 1)) — г = 0, х1 + Х2 + ... + Хп-1 + Хп(к — 2г + (п — 2)(к — 1)) = а(к — 2г + (п — 2)(к — 1)) + г,

Х1 + х2 + ... + хп— 1 + хпЯп = Ра.

Последнее равенство доказывает требуемое соответствие.

Докажем выполнение условия сбалансированности. Для этого необходимо проверить, что гиперплоскость Ьа не пересекает срез 50,-2. Для выполнения этого условия достаточно, чтобы линейная форма Ь = х1 + ... + хп-1 + хпЯп в точке £ =

(к — 1, к — 1,..., к — 1, а — 2) принимала значение строго меньше Р Ь(£) = (п — 1)(к — 1) + (а — 2)Яп < Р( = г + аЯ

п^ ьп а •

0

Последовательно получаем

г + аЯп > (п - 1)(к - 1) + (а - 2)Я„, г > (п - 1)(к - 1) - 2Дп. г > (к - 1)(п - 1) - 2(к - 2г + (п - 2)(к - 1)), г > -(к - 1)(п - 1) + 4г - 2, (к - 1)(п - 1) > 3г - 2.

Последнее неравенство выполнено по условию.

Замечание 1. При добавлении фиктивных переменных у функций, построенных в теореме 1, свойство сбалансированности не нарушается. Теорема 2 описывает сбалансированные функции построенного типа с произвольным количеством фиктивных переменных.

Теорема 2. В обозначениях теоремы 1 при (к-1)(п-т-1) > 3г-2, 0 ^ т ^ п-2 пороговая функция /к (х^х2,... , хп), заданная двусторонними неравенствами

/(Х1, Х2, . . . , Хп) = а ^ Ьа ^ Хт+1 + Хт+2 + ... + ХпКп_т < Ьа+1

где (Ь1, Ь2,..., Ьк-1) = (РП т, Р2П т,... , Р/П-]™), является сбалансированной пороговой.

Доказательство. Справедливость теоремы 2 следует из замечания 1 и теоремы 1 при замене п на п - т.

При т = 0 утверждение теоремы 2 совпадает с утверждением теоремы 1. Приведём пример построения функции для фиксированных параметров с неодинаковыми отступами.

Пример 1. Пусть п = 3, к = 3, отступы от крайней точки равны 2 по первой и 1 по второй переменной. Тогда набор точек, через которые пройдёт соответствующее семейство плоскостей, следующий:

¿(1) = (2, 0, а), ¿(2) = (0,1, а), ¿(3) = (1, 2, а - 1), а е {1, 2}.

Найдём уравнения плоскостей, проходящих через точки ; для этого необхо-

димо найти соответствующий определитель А и приравнять его к нулю:

А

Х1 - 2 Х2 Х3 - а -2 1 0 1 2 1

х1 - х3 + а - 2 х2 + 2х3 - 2а х3 - а -2 1 0 0 0 -1

'х1 - х3 + а - 2 + 2(х2 + 2х3 - 2а) х2 + 2х3 - 2а х3 - а^ 0 1 0 0 0 -1

= -(х1 - х3 + а - 2 + 2(х2 + 2х3 - 2а)) = -(х1 + 2х2 + 3х3 - 3а - 2). Приравнивая А = 0, получим уравнения плоскостей для а е {1, 2}:

х1 + 2х2 + 3х3 = 3а + 2.

Вектор порогов данной функции следующий: (Ь1, Ь2) = (5, 8). Прохождение плоскостей через соответствующий куб изображено на рис. 1.

Рис. 1. Функция, построенная в примере 1 на трёхмерном кубе трёхзначной логики; Ь1 и Ь — построенные плоскости

2. Построение подстановок на основе сбалансированных к-значных пороговых функций

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

Определение 3. Координатное отображение Р : ПП ^ ,

Р

где /г(х) = /г(х1,х2,... , хп) — к-значные функции, называется биективным, а система функций /1(х), /2(х),... , /п(х) —регулярной системой, если Р — взаимно-однозначное отображение.

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

2.1. Построение подстановок на основе сбалансированных

k-значных пороговых функций

Определение 4. Система функций /i(x), /2(x),... , /n(x) называется треугольной, если она имеет вид

' fi(x) = PiO*^

/2(ж) = ^2(xi,x2),

, /n(x) = ^n(Xl,X2, . . . ,Жга),

где ^2,... , ^n — произвольные k-значные функции.

Если функция , i = 1,... , n, биективна по переменной Xi, т. е. при каждой фиксации переменных x1,x2,... ,xi-1 функция задаёт подстановочное отображение [8, с. 166], то система (5) задаёт биекцию. Действительно, пусть задано равенство

тогда ^i(xi) = (ai). В силу биективности функции ^i(xi) по переменной Xi существует и единственен элемент bi Е П&, такой, что ^i(bi) = ai. Положим Xi = bi. Ввиду биективности функции по переменной X2 существует и единственен b2 Е П, такой, что ^2(bi,b2) = a2. Положим X2 = b2. Продолжая дальше по индукции, получаем, что существует единственный набор (xi, x2,... , Xn) = (bi, b2,... , bn) Е nn, удовлетворяющий равенству (6).

В качестве треугольной регулярной системы можно предложить систему вида ' ^i(xi) = xi,

^2

k <£n(xi ,X2, ...,Xn) = Xn + ^n(xi,X2,... ,Xn-i) mod k.

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

Среди систем (7) представляют интерес системы на основе функций (3) из теоремы 2. Пороговые функции (3) будем обозначать следующим образом:

Tm

где m — количество фиктивных переменных; r — параметр, отвечающий за размер отступа от крайних точек среза, тем самым отвечающий за размер отсекаемой области среза. Систему порогов и максимальный коэффициент линейной формы будем обозначать (bi,b2,... , bk-i) = (Pn-m(r), P2n-m(r),... , Pfcn_T(r)) и Rn-m(r) соответственно.

Для дальнейшего использования доопределим множество функций (8) для случая n =1: Tr0(Xi) = Xi, Ri(r) = 1, Pi(r) = i, i = 1,..., k - 1.

Можно рассмотреть два способа задания функций ... , Первый способ

позволяет параллельно вычислять значения координатных функций, что ускоряет ре-

ализацию подстановки, а именно:

f = т;р(о, о,..., о, xi),

= Trra2-2(0, 0,..., 0,xi ,X2),

^i(xi ,X2, ... ,Xi-i) = Tr"-i+ (0, 0, . . . , 0,Xi,X2, ... ,Xi-i),

. (Х1,Х2, . . . ,Х„_1) = Тг1п_1 (0,Х1,Х2, . . . ,Х„_1).

Второй способ реализует рекуррентное определение значений координатных функций, основанное на последовательном задании функций

Г ^Ы = тп-1 (о, о,..., 0,У1),

^э(У1,У2)= ТГ2(0, 0,..., 0,yi ,У2),

^i(yi,y2,...,yi-i) = 7Г!+1(0, 0,..., 0,yi ,y2,...,yi-i),

, ^n

По)

где

' yi(xi) = ^i(xi) = Xi, У2(xi,X2) = ^2(xi,X2) = X2 + ^2(xi) mod k,

k yn-i(xi,X2,... ,Xn-i) = ^n-i(xi,X2,... ,Xn-i) = xn-i + ^n(xi,X2,..., Xn-2) mod k.

Удобство использования систем (7) с функциями (9) или (10) заключается в том, что для задания подстановки достаточно хранить коэффициенты линейных форм пороговых функций и систему порогов. Матрицы C и P содержат всю информацию о задаваемых подстановках указанного типа:

C=

000 000 000

P

0 0 1 ^0 1 1

Pi

00 01 11

Ri

\

11 11

Rn-2

R„-i

ill)

P2

P2V2)

P

n-i

Pi-i

Pn--i(rn-i)y

Элемент с^- матрицы С задаёт коэффициент линейной формы г-й координатной пороговой функции при переменной х^-. Например, линейная форма г-й пороговой функции имеет вид Ь = х1 + х2 + ... + х^_1 + х^Я^г^) и соответствует линейной форме функции ^¿(х1,х2,. .. ,Хг) систем (9) и (10). В матрице Р строка с номером г задаёт систему порогов г-й пороговой функции.

2.2. Построение подстановок на основе систем однотипных

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

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

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

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

Остановимся подробно на преобразованиях, используемых при генерации функций по каждому каналу. Группой движения Сга назовем группу, порождённую группами 5га и

С«, = (Sra, ^га) ,

где 5га — группа подстановок на множестве {1,... , п}; N = {-1,1}™ — группа инвертирования переменных. Действие данных групп на множестве П^ определяется следующим образом: для любой точки (а^а2,... , ага) € П^, для любых преобразований 8 € и в =(в1,в2,...,вп) € N

(й1, а2,..., ага)5 = (а«-1(1), а«-1(2),..., а5-1(„)),

в \ аг, если вг = 1,

(Й1,Й2, . . . ,а«)в = («1,«2, . . . ,«п), «г =<,

I к — 1 — аг, если вг = — 1.

Обозначим через (вз) Тгт функцию, полученную из функции Тгт по правилу (вз) Тгт = Тгт(жв5). Системе к-значных пороговых функций

Ргт

где в = (в (1),в (2),...,в(о)) € (Ага)га; 5 = (з(1), 5(2),... , 5(га)) € (5га)га, поставим в соответствие матрицу С = (сг,^)гахга аналогично матрице (11) с учётом действия преобразований из группы Ага. Например, функции (ве)Тт, где е — нейтральный элемент группы в = (в1, в2,... , в™), соответствует строка матрицы (в1, в2,... , вп^п-т(г)). Каждой системе (12) соответствует отображение, задаваемое по правилу

п[Ргт(в,5)](ж1,Ж2,...,Жга) =

=

В случае регулярности системы ^"(в, з) отображение п[^т(в, з)] задаёт подстановку на множестве П^.

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

Теорема 3 (критерий Хаффмана). Система к-значных функций /¿(х1,. г = 1,...,п, регулярна тогда и только тогда, когда для любых г Е {1, 1 ^ г1 < г2 < ... < гг ^ п и а1, а2,..., аг € {0,..., к — 1} выполняется

> Хп) ,

, п} ,

П

кП

Теорема 4. Пусть для некоторых (в(1), в(2),... , в(п)) € (5п)п и любых в = (в(1), в(2),... , в(п)) Е (^)п при к > 3 в матрице С, отвечающей системе Ргт(в, в), существуют две различные строки вида

в?

02 в2г)

0р_1 в29-_1 вР>)^га_т(г) 0Р+1вР+1

г(0

(0

0пв")

01 в1 0^в2')

0р_1 вр_ 1 вР(1) ^п_т(г) 0р+1вр+1

гСО

0Пв

— индикаторы фиктивности (существенности) соответствующих переменных; = = п — т +1. Тогда отображение п[^т(в, в)] не является биекцией.

где 0и

Е 0и

«=р и=р

Доказательство. Не ограничивая общности, положим р = п. Пусть / и у — функции, соответствующие строкам г и матрицы С. Зафиксируем а = вПг)(о) и $ = впг?)(к — 1). Тогда справедливы включения Да(/) С 50 и 51, (у) С 5к_2 и 5к_1. Поскольку к > 3, то (50 и 51) П (5к_2 и 5к_1) = 0. Из последних трёх выражений получаем Да(/) П (у) = 0, что противоречит условию критерия Хаффмана.

Следствие 1. Теорема 4 позволяет сократить перебор отображений (13), проверяемых на регулярность при фиксированных параметрах г и т, где (к — 1)(п — т — 1) > > 3г — 2, в пп раз

Доказательство. Действительно, тотальный поиск биективных отображений (13) состоит из задания соответствующей матрицы С и проверки на регулярность порождаемого ею преобразования. Выбор матриц С осуществляется за счёт расположения коэффициента Яп_т(г) в каждой строке (пп вариантов), задания у каждой координатной функции фиктивных переменных (Ст 1 вариантов) и определения инвертирования существенных переменных, что потребует рассмотрения 2(п_т)п вариантов, где (п — т)п — количество ненулевых элементов матрицы С. Следовательно, на основе матрицы С проверке подвергаются N = ппСт 12(п_т)п систем.

Из теоремы 4 следует, что в каждом столбце и в каждой строке матрицы, соответствующей отображению (13), должен присутствовать единственный максимальный по модулю коэффициент вРР1)Дп_т(г). Перестановкой строк матрицы С можно расположить коэффициенты вр"^ Дп_т(г) на главной диагонали, поскольку перестановка координатных функций не нарушает биективности. Таким образом, перебор заключается в фиксации фиктивных переменных и расстановке инвертирования существенных переменных, что составляет 12(п_т)п вариантов.

Приведём алгоритм поиска биективных отображений (алгоритм 1).

Приведём результаты применения программы, реализующей данный алгоритм на основе матрицы С. Во всех случаях п — размерность пространства, к — значность логики, т — количество фиктивных переменных, г — параметр, отвечающий за размер отсекаемой области, Яп_т(г) определено условием теоремы 2, в(1), в(2),..., в(п) Е N — перебираемые параметры.

Алгоритм 1. Поиск биективных отображений 1: Инициализируем параметры 3 := 0, п, к, т, г, Дга-т(г), РП-т(г), (Р>[1-т(г),... ,

РГГ(г)).

2: Проверяем условие сбалансированности (к — 1)(п — т — 1) > 3г + 2. Если выполнено,

то на шаг 3, иначе сообщение «Функция не сбалансирована», конец алгоритма. 3: Инициализируем матрицу коэффициентов С. На главной диагонали располагаем максимальный коэффициент Дга-т(г), оставшиеся элементы каждой строчки заполняем т нулями и п — т — 1 единицами согласно рассматриваемому случаю. 4: Для каждого из 2п-т способов задаём знаки ненулевых коэффициентов матрицы С, проверяем на биективность получившуюся систему. Если биекция, то 3 := 3 + 1.

Выход: 3 — количество найденных подстановок для проверяемого случая.

Случай 1. Общие параметры т = 0,

С

/в^ад в<2) в21) . в22)^п

в

Для заданных т и С (1) рассмотрим два способа задания размера отступа г.

Первый способ соответствует г = 1 , количество подстановок, полученных за счёт перебора в(1),в (2),...,в(п) Е Ага, представлено в табл. 1.

Таблица 1

к

п 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

2 - 8 8 8 8 8 8 8 8 8 8 8 8 8 8

3 192 64 64 64 64 64 64 64 64 64 64 64 64 64 64

4 3328 768 768 768 768 768 768

5 76800 12288 12288

Во втором способе для каждого варианта параметров п и к будем задавать максимально возможный размер отступа г = гтах(к,п,т), удовлетворяющий условию сбалансированности теоремы 2. Значения гтах(к,п,т) и количества подстановок, полученных за счёт перебора в (1),в (2),...,в(п) Е Ага, представлены в табл. 2.

Таблица 2

п к

2 3 4 5 6 7 8 9 10 11 12 13 14

3 1; 192 1; 64 2; 0 3; 0 3; 0 4; 0 5; 0 5; 0 6; 0 7; 0 7; 0 8; 0 9; 0

4 1; 3328 2; 0 3; 0 4; 0 5; 0 6; 0 7; 0

5 1; 76800 3; 0 3; 0

По результатам, представленным в табл. 1, можно сделать предположение, что с ростом к количество подстановок на основе матрицы

С

стабилизируется. Из табл. 2

можно предположить, что для значений 1 < г ^ гтах(к,п,т) подстановок указанного вида нет.

Случай 2. Общие параметры т =1,

С

1 Д„-1

в

0 в

в22)Яп-1(г) 0

в1

в

V

0

в

в

в

в(1) в п— 1

вп- 1

в

\

в(га——11)Дп—1(г) 0

в(п)Дп—1(г)/

в(П) вп- 1

где нули расположены на второй главной диагонали.

Для г =1 нашлись биекции только для случаев к = 2, п = 3, 4, 5.

Для г = гтах(к, п, т) биекции были найдены только при к = 2, п = 3, 4,5, при этом

гтах(к,п,т) = 1.

При г > 1 биекций на основе матрицы

С

не найдено.

Случай 3. Общие параметры т =1, п = 4,

в

/в51)Дэ

С(3) =

в

1

в(3) 0

в3" 0

в

0

0

43)

\

в

в(3) Л3(г) в4 в(4) в44)Дз(г)У

Для г = 1, к = 1,..., 8 нашлись биекции только для случая к = 2.

Для г = гтах(к, п,т), к = 1,..., 8 результат совпадает со случаем г =1.

Отсюда сделаем вывод, что возможно построение подстановок с однотипными координатными пороговыми функциями из теоремы 2 и предположительно только для размера отступа г = 1 .

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

Теорема 5. Пусть заданы две подстановки п1,п2, основанные на пороговых функциях, такие, что

П1 ^ ^П1, П2 :^П2 ^ ^П2, Щ,п2 ^ 2; матрица с' ) — матрица коэффициентов линейных форм и р(«) =

V ' / п х п „

) —матрица порогов координатных функций подстановки п, V = 1, 2;

в(1), в(2) — нулевые матрицы размеров п1 х п2 и п2 х п1 соответственно. Тогда матрицы

С7 =

С(1) 0(1)\ е(2) с(2ч ,

р

(р (1Ч

р

задают подстановку п : ^П1

+П2

^ ^П1+П2 .

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

П(Х1, Х2, ... , Хп1 +п2 ) — (п1 (х 1, х2, . . . , Хп1 ), п2 (хп1 + 1, Хп1 +2, . . . , Хп1 +п2 )).

Данное представление задаёт подстановку.

ЛИТЕРАТУРА

1. Никонов В. Г., Саранцев А. В. Методы компактной реализации биективных отображений, заданных регулярными системами однотипных булевых функций // Вестник Российского университета дружбы народов. Сер. Прикладная и компьютерная математика. 2003. Т. 2. №1. С. 94-105.

2. Никонов В. Г., Саранцев А. В. Построение и классификация регулярных систем однотипных функций // Материалы XXXI Междунар. конф. «Информационные технологии в науке, образовании, телекоммуникации и бизнесе». М., 2004. Т. 5. С. 173-174.

3. Никонов В. Г., Сидоров Е. С. О способе построения взаимно однозначных отображений при помощи квазиадамаровых матриц // Вестник Московского государственного университета леса — Лесной вестник. 2009. №2(65). С. 155-157.

4. Никонов В. Г., Сошин Д. А. Геометрический метод построения сбалансированных k-знач-ных пороговых функций и синтез подстановок на их основе // Образовательные ресурсы и технологии. 2014. №2(5). С. 76-80.

5. Алферов А. П., Зубов А. Ю., Кузьмин А. С., Черемушкин А. В. Основы криптографии. М.: Гелиос АРВ, 2001.

6. Дертоузос М. Пороговая логика. М.: Мир, 1967.

7. Ефимов Н. В., Розендорн Э. Р. Линейная алгебра и многомерная геометрия. М.: Наука, 1970.

8. Глухов М. М., Шишков А. Б. Математическая логика. Дискретные функции. Теория алгоритмов. М.: Лань, 2012.

REFERENCES

1. Nikonov V. G. and Sarantsev A. V. Metody kompaktnoy realizatsii biektivnykh otobrazheniy, zadannykh regulyarnymi sistemami odnotipnykh bulevykh funktsiy [Methods of compact realization of bijective mappings proposed by regular systems of one-type Boolean functions]. Vestnik RUDN. Ser. Prikladnaya i Komp'yuternaya Matematika, 2003, vol. 2, no. 1, pp. 94-105.

2. Nikonov V. G. and Sarantsev A. V. Postroenie i klassifikatsiya regulyarnykh sistem odnotipnykh funktsiy [The construction and classification of the regular systems of one-type functions]. Proc. XXXI Int. rnnf. "Informatsionnye tekhnologii v nauke, obrazovanii, telekommunikatsii i biznese". Moscow, 2004, vol. 5, pp. 173-174.

3. Nikonov V. G. and Sidorov E. S. O sposobe postroeniya vzaimno odnoznachnykh otobrazheniy pri pomoshchi kvaziadamarovykh matrits [About the possibility of one-to-one mappings representation by the quasi-hadamard matrixes]. Vestnik Moskovskogo Gosudarstvennogo Universiteta Lesa — Lesnoy Vestnik, 2009, no. 2

4. Nikonov V. G. and SoshinD.A. Geometricheskiy metod postroeniya sbalansirovannykh k-znachnykh porogovykh funktsiy i sintez podstanovok na ikh osnove [The geometric method for constructing a balanced k-valued threshold functions and construction of substitutions based on them]. Obrazovatel'nye Resursy i Tekhnologii, 2014, no. 2

5. AlferovA.P., ZubovA.Yu., Kuz'minA.S., and Cheremushkin A. V. Osnovy kriptografii [Basics of Cryptography]. Moscow, Gelios ARV Publ., 2001.

6. Dertouzos M. Porogovaya logika [Threshold Logic]. Moscow, Mir Publ., 1967.

7. Efimov N. V. and Rozendorn E. R. Lineynaya algebra i mnogomernaya geometriya [Linear Algebra and Multidimensional Geometry]. Moscow, Nauka Publ., 1970.

8. Glukhov M. M. and Shishkov A. B. Matematicheskaya logika. Diskretnye funktsii. Teoriya algoritmov [Mathematical Logic. Discrete Functions. Algorithms Theory]. Moscow, Lan' Publ., 2012.