Сотрудники :: Носов Валентин Александрович :: Публикации Носова В.А.

О построении классов латинских квадратов в булевой базе данных.

Носов В.А.
Кафедра Математической теории интеллектуальных систем

В работе предлагается конструкция параметрических классов латинских квадратов размером 2ⁿ´2ⁿ над множеством булевских векторов длины n, которая не требует запоминания латинского квадрата. Дается один классификационный результат для выполнения данной конструкции.

1) Напомним, что латинский квадрат над множеством S есть таблица размером n´n, где n = ½S½, из элементов множества S, в каждой строке и в каждом столбце которой все элементы различны. Латинские квадраты широко используются в теории кодирования, планирования эксперимента, связи в секретных системах ([3], [4], [5]). В настоящее время имеются различные способы построения латинских квадратов, в том числе и с использованием алгебраических структур на множестве S. Однако, все эти способы предполагают, чтобы соответствующий латинский квадрат запоминался целиком, что затрудняет использование их в случае больших S. Целью настоящей работы является конструкция параметрических классов латинских квадратов в булевской базе данных, т.е. для случая S = E_n – множество булевских векторов длины n. При этом будем предполагать, что латинский квадрат не запоминается целиком, а определяется локальным образом с помощью функций, задающих по номеру строки и столбца значение соответствующего элемента в латинском квадрате. Другой рассмотренный вопрос – конструкция параметрического класса латинских квадратов, в которых при любом значении параметра эффективно определяется номер строки по любому номеру столбца и элементу этого столбца. В данной конструкции это осуществляется на тех же функциях, которые определяют латинский квадрат. Приведен один классификационный результат, связанный с реализацией данной конструкции.

2) Пусть E_n – множество двоичных наборов длины n. В этом случае латинский квадрат над множеством E_n может быть задан системой из n булевых функций

f₁(x₁, …, x_n, y₁, …, y_n) (1)

f₂(x₁, …, x_n, y₁, …, y_n)

…

f_n(x₁, …, x_n, y₁, …, y_n)

от 2n переменных, где x₁, …, x_n определяет номер строки, y₁, …, y_n – номер столбца, значения функций f₁, …, f_n определяют соответствующий элемент квадрата.

Используя результаты о регулярности системы булевых функций [7], можно доказать

Утверждение I. Система n булевых функций f₁, …, f_n от 2n переменных x₁, …, x_n, y₁, …, y_n определяет латинский квадрат тогда и только тогда, когда во всех произведениях f_i1…f_ik, 1 £ i₁ < … < i_k £ n, k < n в полиноме Жегалкина нет членов, содержащих вхождения x₁…x_n либо y₁…y_n, а произведение f₁…f_n содержит оба таких члена и не содержит других членов, их содержащих.

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

3) Предложим теперь способ введения параметра в семейство латинских квадратов.

Пусть дано семейство булевых функций g = (g₁(z₁, …, z_n), …, g_n(z₁, …, z_n)) от n переменных z₁, …, z_n. (2)

Пусть p₁ (x₁, y₁), …, p_n(x_n, y_n) – система булевых функций от 2-х переменных. (3)

Определим систему булевых функций f₁, …, f_n от 2n переменных x₁, …, x_n, y₁, …, y_n соотношениями:

f₁ = x₁ + y₁ + g₁(p₁ (x₁, y₁), …, p_n(x_n, y_n)) (4)

f₂ = x₂ + y₂ + g₂(p₁ (x₁, y₁), …, p_n(x_n, y_n))

…

f_n = x_n + y_n + g_n(p₁ (x₁, y₁), …, p_n(x_n, y_n))

Напомним (см. [1 ]), что семейство булевых функций g = (g₁, …, g_n) называют правильным, если для любых различных наборов переменных и существует a Î такое, что выполнено

Утверждение 2. Система булевых функций f₁, …, f_n вида (4) определяет латинский квадрат для любых функций двух переменных p₁, …, p_n в том и только в том случае, когда семейство функций g = (g₁, …, g_n) является правильным.

Пусть существуют функции p₁, …, p_n от двух переменных, такие, что семейство f₁, …, f_n, определенное (4), не определяет латинский квадрат. Тогда

f₁(x’₁, …, x’_n, y₁, …, y_n) = f₁(x”₁, …, x”_n, y₁, …, y_n) (6)

…

f_n(x’₁, …, x’_n, y₁, …, y_n) = f_n(x”₁, …, x”_n, y₁, …, y_n)

для некоторых x’₁, …, x’_n, x”₁, …x”_n, y₁, …, y_n, причем (x’₁, …, x’_n) ¹ (x”₁, …, x”_n), либо

f₁(x₁, …, x_n, y’₁, …, y’_n) = f₁(x₁, …, x_n, y”₁, …, y”_n) (7)

…

f_n(x₁, …, x_n, y’₁, …, y’_n) = f_n(x₁, …, x_n, y”₁, …, y”_n)

для некоторых x₁, …, x_n, y’₁, …y’_n, y”₁, …, y”_n, причем (y’₁, …, y’_n) ¹ (y”₁, …, y”_n).

Пусть выполнено (6), тогда используя (4) получаем, что

x’₁ + g₁(p₁ (x’₁, y₁), …, p_n(x’_n, y_n)) = x”₁ + g₁(p₁ (x”₁, y₁), …, p_n(x”_n, y_n)) (8)

…

x’_n + g_n(p₁ (x’₁, y₁), …, p_n(x’_n, y_n)) = x”_n + g_n(p₁ (x”₁, y₁), …, p_n(x”_n, y_n))

Введем обозначения

z’ = (z’₁, …, z’_n), где z’_i = p_i(x’_i, y_i), i =

z” = (z”₁, …, z”_n), где z”_i = p_i(x”_i, y_i), i =

Рассмотрим пару наборов

g(z’) = (g₁(z’), …, g_n(z’)) и g(z”) = (g₁(z”), …, g_n(z”)).

Если для всех a Î выполнено g_a(z’) ¹ g_a(z”), то условие правильности семейства функций g₁, …, g_n не выполняется на паре наборов z’ и z”. Если существует a Î , такое, что выполнено g_a(z’) = g_a(z”), то из (8) получаем, что x’_a = x”_a и поэтому p_a(x'_a, y_a) = p_a(x”_a, y_a) и, следовательно, z’_a = z”_a. Значит, в этом случае также не выполняется условие правильности семейства g₁, …, g_n на паре z’, z”. Случай (7) разбирается аналогично. Таким образом, если система функций (4) не определяет латинский квадрат при некоторых функциях p₁, …, p_n, то семейство g₁, …, g_n не является правильным.

Пусть теперь семейство g₁, …, g_n не является правильным. Это значит, что существует пара наборов z’ = (z’₁, …, z’_n) и z” = (z”₁, …, z”_n), что для всех a Î с условием z’_a ¹ z”_a имеем g_a(z’) ¹ g_a(z”). Рассмотрим произвольные x₁, …, x_n и y₁, …, y_n. Определим пару x’₁, …, x’_n и x”₁, …, x”_n, где

x’_i = x_i + g_i(z’), i Î (9)

x”_i = x_i + g_i(z”), i Î

Теперь определим функции p₁, …, p_n так, чтобы

p_i(x’_i, y_i) = z’_i, i Î (10)

p_i(x”_i, y_i) = z”_i, i Î

Этого нельзя сделать лишь в случае, когда x’_i = x”_i, но z’_i ¹ z”_i для некоторого i Î . Но если x’_i = x”_i, то из (9) имеем g_i(z’) = g_i(z”) и согласно условия на выбор z’ и z” имеем z’_i = z”_i. Теперь нетрудно видеть, из (4), что элементы квадрата, соответствующие (x’₁, …, x’_n, y₁, …, y_n) и (x”₁, …, x”_n, y₁, …, y_n) равны (x₁, …, x_n), т.е. квадрат (4) не является латинским при данных функциях p₁, …, p_n.

Заметим, что понятие правильности семейства функций было введено в [1] в связи с изучением регулярности определенного класса булевских автоматов. Там же приведен критерий правильности и доказана NP-полнота задачи проверки правильности семейства булевых функций, заданного в КНФ.

4) Введем понятие равномерной обратимости латинского квадрата. Пусть g = (g₁, …, g_n) – правильное семейство булевых функций, p₁(x₁, y₁), p₂(x₂, y₂), …, p_n(x_n, y_n) – произвольная функция 2-х переменных. Тогда согласно предыдущему – таблица над E_n, в которой в строке x₁, …, x_n и в столбце y₁, …, y_n находится x’₁, …, x’_n, где

x’₁ = x₁ + y₁ + g₁(p₁ (x₁, y₁), …, p_n(x_n, y_n)) (11)

…

x’_n = x_n + y_n + g_n(p₁ (x₁, y₁), …, p_n(x_n, y_n))

будет латинским квадратом для всех функций p₁, …, p_n.

Будем называть данный латинский квадрат равномерно обратимым и семейство g = (g₁, …, g_n) также равно обратимым, если из (11) следует

x₁ = x’₁ + y₁ + g₁(p₁ (’₁ + y₁, y₁), …, p_n(’_n + y_n, y_n)) (12)

…

x_n = x’_n + y_n + g_n(p₁ (’₁ + y₁, y₁), …, p_n(’_n + y_n, y_n))

p₁, …, p_n, x’₁, …, x’_n, y₁, …, y_n.

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

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

g₁ = 1, g₂ = g₂(z₁), …, g_n = g_n(z₁, …, z_n-1) (13)

Будем говорить, что семейство булевых функций (13) удовлетворяет свойству W, если для любого i Î и любого решения z*₁, …, z*_i-1 уравнения

g_i(z₁, …, z_i-1) = 0 (14)

справедливо: функция g_j(z*₁, …, z*_i-1, z_i, …, z_j-1) не зависит от z_i для любого j > i.

Утверждение 3. Семейство функций (g₁, …, g_n) вида (13) равномерно обратимо тогда и только тогда, когда для него выполнено условие W.

Пусть условие W выполнено для семейства g. Покажем, что из (11) следует (12). Доказываем индукцией по n. Для n = 2 имеем

x’₁ = x₁ + y₁ + 1

x’₂ = x₂ + y₂ + g₂(p₁(x₁, y₁))

Отсюда

x₁ = x’₁ + y₁ + 1

x₂ = x’₂ + y₂ + g₁(p₁ (’₁ + y₁, y₁))

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

Пусть для n-1 утверждение доказано. Имеем для x_n соотношение из (11)

x_n = x’_n + y_n + g_n(p₁ (x₁, y₁), …, p_n-1(x_n-1, y_n-1)) (15)

причем

x₁ = x’₁ + y₁ + 1

x₂ = x’₂ + y₂ + g₂(p₁ (’₁ + y₁, y₁))

…

x_n-1 = x’_n-1 + y_n-1 + g_n-1(p₁ (’₁ + y₁, y₁), …, p_n-2(’_n-2 + y_n-2, y_n-2))

по предположению индукции.

Нужно доказать, что

x_n = x’_n + y_n + g_n(p₁ (’₁ + y₁, y₁), …, p_n-1(’_n-1 + y_n-1, y_n-1)) (16)

В соотношениях (15) и (16) у функции g_n значения первых аргументов совпадают в силу x’₁ = x₁ + y₁ + 1. Далее, если g₂(p₁(x₁, y₁)) = 1, то в (15) и (16) значения вторых аргументов совпадают у функции g_n. Если g₂(p₁(x₁, y₁)) = 0, то в силу свойства W, функция g_n не зависит от второго аргумента при данной фиксации первого аргумента и, не меняя значения g_n, мы можем положить в качестве значения второго аргумента p₂(’₂ + y₂, y₂). Продолжая таким образом, получаем, что соотношения (15) и (16) совпадают.

Пусть условие W не выполнено для функции g₁, …, g_n. Значит, существует набор z₁, …, z_n такой, что для некоторого i Î выполнено

g_i(z₁, …, z_i-1) = 0

но g_j(z₁, …, z_i, …, z_j-1) ¹ g_j(z₁, …, _i, …z_j-1) для некоторого j > i. Рассмотрим произвольное x₁, …, x_{n И} y₁ = y₂ = … = y_n = 0. Определим функции p₁, …, p_n так, чтобы

p₁(x₁, y₁) = z₁, p₂(x₂, y₂) = z₂, …, p_n(x_n, y_n) = z_n.

Пусть x’_i = x_i + y_i + g_i(p₁ (x₁, y₁), …, p_n(x_n, y_n)), i = .

Теперь положим

p₁(’₁, y₁) = z₁, p₂(’₂, y₂) = z₂, …, p_i(’_i, y_i) = _i, …, p_n(’_n, y_n) = z_n.

Это можно сделать, так как равенство x_i = _’i влечет g_i = 1, что противоречит выбору z₁, …, z_n.

Теперь ясно, что для (11) не выполняется (12) при данном g₁, …, g_n, p₁, …, p_n на индексе j.

Свойство W позволяет строить конкретные равномерно обратимые семейства g₁, …, g_n. Например,

g₁ = 1, g_i+1 = g_i×z_i, i = , g₁ = 1, g_i+1 = _i×z_i, i = .

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

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

Пусть семейство состоит из мультиаффинных функций. Это значит, что имеет вид

... (17)

где – число перемножаемых линейных функций в , – линейная функция над , .

Определим ориентированный граф вхождения переменных в семейство , полагая , где. функция содержит (т.е. ). (18)

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

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

Утверждение 4 Семейство мультиаффинных булевых функций , является правильным тогда и только тогда, когда для любого простого элементарного цикла графа вхождения семейства выполнено условие

(19)

Пусть существует простой элементарный цикл графа , такой, что условие (19) не выполнено, т.е.

(20)

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

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

... (21)

Здесь – мультиаффинная функция, не содержащая вхождений . Сомножители у отвечают линейным функциям, содержащим вхождение . Аналогично, – мультиаффинная функция, не содержащая вхождений , сомножители у отвечают линейным функциям, содержащим вхождение .

Согласно (20) существует двоичный набор , такой, что .

Следовательно имеем

(22).

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

Тогда на основании (21) получаем, что на данном наборе выполнено

(23).

Из соотношений (22) и (23) следует, что семейство не является правильным, т.е. для него не выполнено условие правильности на наборах и . Обратно, пусть теперь для любого простого элементарного цикла графа выполнено условие (19).

Для семейства рассмотрим семейство функций , положив

(24).

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

т.е. переменные с индексами из замещены константами , – дополнение в . Известно (см.[1], лемма 2), что правильное семейство в том и только в том случае, когда семейство регулярно при всех и всех . Для установления регулярности произвольного семейства булевых функций от переменных будем пользоваться критерием Хаффмена (см. [6]), согласно которому семейство регулярно тогда и только тогда, когда для любых индексов произведение не содержит члена в полиноме Жегалкина при , а произведение содержит такой член. Пусть I=ш. Покажем регулярность семейства .

Имеем

(25).

Суммирование по всем разбиениям множества , где . Покажем, что при любых , не содержит члена . Если, напротив, для некоторого , имеется член x₁x₂…x_n , то выполнено при и содержит член .

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

Пусть теперь существует и индексы , что произведение содержит член .

Имеем

(26).

Суммирование по всем разбиениям , множества i₁, i₂ ,…,i_k . Это значит, что существует (р₁,р₂), р₂?0, такое, что содержит член . Отсюда следует, содержит член , где – дополнение множества в . Рассмотрим подграф с вершинами множества . Поскольку функции с индексами из дают член , то по определению графа из каждой вершины выходит по крайней мере одна дуга с концом в . По условию имеем . Следовательно, граф содержит цикл, поэтому, аналогично предыдущему, имеем и член появиться в (26) не может. Таким образом, – регулярное семейство согласно критерия Хаффмена.

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

Литература.

[1]. Носов В.А. Критерий регулярности булевского неавтономного автомата с разделенным входом. Интеллектуальные Системы, т. 3, вып. 3-4, 1998, с. 269-280.

[2]. Алексеев В.Б., Носов В.А. NP-полные задачи и их полиномиальные варианты. Обзор. Обозрение промышленной и прикладной математики, 1997, т. 4, вып. 2, с.165-193.

[3]. Белоусов В.Д., Белявская Г.Б. Латинские квадраты, квазигруппы и их приложения. Кишинев, 1989, 80 с.

[4]. Шеннон К. Теория связи в секретных системах. В сб. К. Шеннон. Работы по теории информации и кибернетике, М., 1963, с.333-369.

[5]. Denes J., Keedwell A.D. Latin squares and their applications, Budapest, 1974, 547 p.

[6]. Huffman D.A. Canonical forms for information lossless finite-state logical machines. IRE Trans. Circ. Theory, 1959, v.6, p.41-59.

[7]. Клосс Б.М., Мальшев В.А. Oпределениe регулярности автомата по его каноническим уравнениям. Докл. АН СССР. 1967. т. 172, №3, с.543-546.

Интеллектуальные системы, т.4,вып.3-4, 1999 г.

Наверх