О локальности информационных систем
( About Local Information Systems
Preprint, Inst. Appl. Math., the Russian Academy of Science)

A realibus ad realiora.

От реального к реальнейшему (лат.).

Введение. Мы исходим из представления формальной модели физической системы, описанной в работе [1]. Напомним, что физическая система есть ограниченная детерминированная функция, а ее информационная модель (ИМ) – это характеристическая логическая функция в расширенном базисе. В связи с этим признаки объектов мыслится как последовательности булевских переменных.

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

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

Исследование локальности ПО позволяет увидеть ряд их интересных свойств, важных для разработки ИМ, так как позволяет оценить необходимые ресурсы. В частности – это многозначность характеристики классов объектов, когда один и тот же класс можно описать несколькими способами. Из этого вытекает ограниченность числа различных классов объектов.

Пример 2. В содержательной речи это свойство связано с синонимичностью. При проектировании ИМ оно заметно при синтезе банков данных, когда одно отношение обладает несколькими ключами.

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

1. Бинарные матрицы. Бинарные матрицы служат для представления к.н.ф. Пусть D есть множество {D₁, D₂, ..., D_m} дизъюнктов, зависящих от переменных х₁, х₂, ..., х_n. Изобразим его в виде матрицы M_D, столбцы которой занумерованы от 1 до m,  а строки - от 1 до n. Ее элемент a_ij = 1, если переменная х_i входит в дизъюнкт D_j, a_ij = 0, если в D_j входит литера`х_i, и a_ij = _, если ни переменная х_i ни ее отрицание не входят в D_j. Символы 0 и 1 назовем значащими, символ _ - не значащим. Матрицу, не содержащую значащих символов, обозначим L.

Будем мыслить бинарные матрицы, как конечные множества векторов, элементы которых суть: 0, 1, _. При этом каждый вектор есть в точности один столбец. Размерность матриц будем обозначать в виде [n, m],  что значит, что она имеет n строк и m столбцов. Назовем n - глубиной, а m - шириной матрицы.

Множество {0, 1, _}  обозначим Е. Таким образом, матрица размерности  [n, m] представляет собой  m векторов из  Еⁿ.

Введем операции сложения матриц.

Пусть М₁ и М₂ суть матрицы, строкам которых поставлены в соответствие переменные, образующие множества соответственно Var(М₁) и Var(М₂). Тогда сумма М₁ + М₂ есть матрица, содержащая Var(М₁) È Var(М₂) переменных, получающаяся объединением их столбцов.

Пример 3. Пусть матрицы М₁ и М₂ выглядят соответственно, как на рис.1а и 1б. Их сумма изображена на рис. 1в.

Пусть М есть матрица и d₁ и d₂ - ее столбцы такие, что d₁ есть собственный подстолбец d₂. В этом случае говорим, что d₁ поглощает d₂.  Из логической эквивалентности X Ù (X Ú Y) = X следует, что если в матрице М вычеркнуть столбец d₂, то получим эквивалентную матрицу. Поэтому полагаем, что в рассматриваемых нами матрицах вычеркнуты все поглощаемые столбцы.

Назовем строку матрицы М фиктивной, если она содержит оба значащих символа, и всякий столбец, содержащий в этой строке 0, в оставшихся компонентах, совпадает с некоторым столбцом, который содержит в этой строке 1. И наоборот, всякий столбец, содержащий в этой строке 1, в оставшихся компонентах, совпадает с некоторым столбцом, который  содержит в этой  строке  0. Из  логической  эквивалентности (X Ú Y) Ù (`X Ú Y) = Y следует, что если в матрице М вычеркнуть фиктивную строку, то получим эквивалентную матрицу. Поэтому полагаем, что в рассматриваемых матрицах вычеркнуты все фиктивные строки.

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

2. Свойства означиваний переменных. Пусть М есть бинарная матрица. Будем говорить, что матрица М₁  есть результат означивания переменных Х матрицы М путем присвоения им значений соответственно s_Х, когда она получена из М следующим образом: если означивание превращает некоторый столбец из М в ложь, то М₁ - тождественно ложная матрица; в противном случае М₁ получается из М вычеркиванием всех строк, соответствующих переменным Х, и всех столбцов, которые на пересечении с этими строками имеют значащие символы, совпадающие с соответствующими компонентами из s_Х.

Различные означивания переменных определяют различные матрицы.

Пример 4. Пусть матрица М выглядит, как на рис.2. Тогда в случае присвоение  переменной x единичного значения, из М₂ удаляется верхняя строка и столбец d₁; если же этой переменной присвоить нулевое значение, то - столбец d₀. Таким образом, эти означивания порождают разные матрицы.

Введем отношение эквивалентности @ на множестве наборов, означивающих переменные матрицы М: два набора s₁ и s₂ находятся в отношении s₁ @ s₂, если матрицы М₁ и М₂, полученные из М при означиваниях соответственно s₁ и s₂, эквивалентны.

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

Пусть Х = {x₁, x₂, ..., x_n} есть множество литер. Бинарным деревом над Х называется конечное дерево с единственным корнем; его каждый не висячий узел N имеет в точности двух потомков N₀ и N₁, дуга NN₀  помечено литерой`x_i, а NN₁ - литерой x_i, i Î {1, 2, ..., n}.

Каждому простому пути t_N из корня в некоторый узел N соответствует единственный вектор s_N из Еⁿ когда в t_N  нет дуг, помеченных контрарными литерами: если в t_N  входит дуга с меткой x_i (`x_i), то i-ый компонент вектора s_N  есть 1 (0), в противном случае i-ый компонент есть _. Таким образом, каждое бинарное дерево однозначно определяет множество векторов из Еⁿ.

Бинарное дерево называется полным, если его простые пути из корня в висячие узлы определяют все 2ⁿ бинарных векторов длины n.

Нетрудно увидеть, что если векторы s₁ и s₂ эквивалентны, то их одинаковые продолжения s₁s  и s₂s  также эквивалентны. Установим некоторые свойства фактор-множества À/@. Для этого введем необходимые определения и докажем ряд утверждений.

Назовем класс [s] означиваний переменных матрицы М 1-константным (0-константным), если при означивании s она превращается в тождественную истину (ложь).

Очевидно, что если [s] есть константный класс, то всякое продолжение означивания s  также принадлежит этому классу.

Через s_х, где s Î {0, 1} и х - переменная, обозначим, что переменной х  присваивается значение s.

Лемма 1. Класс [s] включает набор s1_х тогда и только тогда, когда он включает набор s0_х.

Назовем класс [s], не включающий набор s1_х (s0_х), альтернативным (по х).

Лемма 2. Если наборы s1_х и s0_х эквивалентны, то оба принадлежат классу [s].

Доказательство. Напомним, что мы рассматриваем матрицы, в которых вычеркнуты все поглощаемые наборы. Поэтому совпадение матриц, полученных при означиваниях s1_х и s0_х означает, что в матрице М^*, полученной при означивании s, в строке х различные значащие символы 0 и 1 располагаются в столбцах, не отличающихся своими другими компонентами. Поэтому строка х в матрице М^* фиктивная. И матрица, которая получается из М^* вычеркиванием этой строки, эквивалентна М^*.

Лемма доказана.

Пример 5. Пусть матрица М выглядит как на рис.3а. Тогда матрицы М₀ и М₁, полученные различным означиванием первой переменной, выглядят соответственно, как на рис.3б и 3в.

Построим ор-граф Г_М следующим образом: его узлами являются классы эквивалентности @, и два узла [s₁] и [s₂] соединены дугой от [s₁] к [s₂], если [s₁] альтернативный класс по переменной х и s₁s_x Î [s₂], где s Î {0, 1}.

Легко увидеть, что граф Г_М есть дерево с корнем, которому приписано пустое означивание, и его висячими узлами являются два константных класса.

Представление фактор-множества в виде графа Г_М позволяет сопоставить матрице М логическую формулу, используя равенство f(x) = x f(1) Ú`x f(0). В результате, если для М удается построить простое фактор-множество, то соответствующая логическая функция также проста.

Исследуем число классов эквивалентности в зависимости от вида анализируемой матрицы. С этой целью докажем следующее утверждение.

Теорема 4. Пусть матрица М есть сумма М₁ + М₂ матриц,  как на рис.4, и Х-слой содержит k строк. Тогда означивания всех переменных из М₁  порождает не более  2^k  классов эквивалентности.

Доказательство. Пусть N₁ = {s₁, s₂, ..., s_q} есть множество всех единичных означиваний матрицы М₁. Каждое из них включает Х-проекцию, т.е. подвектор, означивающий только переменные Х. Число таких проекций не более 2^k. Каждое означивание из N₁ превращает М в некоторую подматрицу матрицы М₂ в результате вычеркивания ее столбцов. Пусть единичное означивание s_i = s_Хs¢_i  принадлежит множеству N₁, где s_Х  есть ее Х-проекция и s¢_i - остальная часть, i = 1, 2, ..., q. При означивании переменных матрицы M₂ вектором s_Хs¢_i в ней вычеркиваются в точности те столбцы, Х-составляющие которых не ортогональны вектору s_Х хотя бы в одном компоненте. Но все столбцы, которые таким образом вычеркиваются при всех означиваниях из N₁, образуют не более 2^k различных одновременно вычеркиваемых семейств.

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

4. Вертикальная локальность матриц. Назовем два непересекающихся фрагмента матрицы М смежными по столбцу d, если d имеет непустое существенное пересечение с этими фрагментами. Например, когда этими фрагментами служат горизонтальные слои Н₁ и Н₂, в столбце d есть существенные компоненты из обоих слоев. Частным случаем этого определения является смежность строк, когда они имеют существенные пересечения с одним столбцом.

Определим по М нагруженный граф G_M: его узлы однозначно соответствуют строкам матрицы, каждый узел помечен номером соответствующей строки; два узла i₁ и i₂ графа G_M смежны, если в матрице строки i₁ и i₂ также смежны. Назовем множество ребер одной компоненты связности графа G_M сечением, если выбрасывание этих ребер приводит к увеличению числа компонент связности.

Матрица М называется вертикально k-связной, если в любом сечении графа G_M имеется не более k ребер.

Теорема 5. Для всякой вертикально k-связной матрицы с n строками размерность фактор-множества, определяемого некоторым полным бинарным деревом, не превосходит величины (n/2) 2²_k.

Доказательство. Пусть M есть вертикально k-связная матрица. Выделим максимальное сечение в графе G_M  и все столбцы, соответствующие сечению, переставим влево, как на рис.5а.

Матрицы M₁ и M₂ не имеют смежных строк, одна из которых принадлежит M₁, а другая - M₂. Поэтому исходная матрица только за счет перестановки столбцов преобразуется к виду, как на рис.5б.

Затем только перестановкой столбцов получим матрицу, как на рис.5в.

Далее все строки из верхней половины матрицы, смежные со строками из нижней половины, переставим вниз, к горизонтальной разделительной линии, а все строки из нижней половины матрицы, смежные со строками из верхней половины, - вверх, к горизонтальной разделительной линии.

От противного покажем, что матрица M₁ представима, как на рис. 5г. Действительно, пусть в матрице M₁ имеется столбец, определяющий смежность строк, одна из которых имеет пересечение с матрицей G^*, а другая – с матрицей M₁₂.

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

Аналогично рассуждая, получим, что матрица M₂ представима, как на рис. 5г. Понятно, что строк в матрице G^*  ∆^* не более k.

После означивания всех переменные матрицы G^*  ∆^* получим не более 2^2k классов эквивалентности. В единственной результирующей матрице число строк, по меньшей мере, на две меньше, чем в исходной. Рассуждая индуктивно, убеждаемся в справедливости теоремы.

4. Горизонтальная локальность матриц. Рассмотрим еще один класс локальных матриц. Для этого введем следующие определения.

Пусть М есть бинарная матрица. Назовем два непересекающихся фрагмента матрицы М смежными по строке i, если строка i имеет с ними непустое пересечение. Например, для столбцов d₁ и d₂ это значит, что в дизъюнкты, соответствующие d₁ и d₂, входит переменная, которой в матрице соответствует строка с номером i).

Определим по матрице М нагруженный граф G_M: узлы его однозначно соответствуют столбцам матрицы, каждый узел помечен номером соответствующего столбца; два узла графа смежны, если соответствующие им столбцы также смежные.

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

Матрица М называется горизонтально k-связной, если в любом сечении графа G_M имеется не более k ребер.

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

Теорема 6. Для всякой горизонтально k-связной матрицы с n строками размерность фактор-множества, определяемого некоторым полным бинарным деревом,  не превосходит величины (n/2)2²_k.

5. Локальные матрицы. Опишем еще один класс локальных матриц, которые обладают ограниченным число классов эквивалентности при определенном порядке означиваний переменных.

Введем следующие определения.

Определим по матрице М нагруженный граф G_M:

- узлы его однозначно соответствуют не пересекающимся подматрицам этой матрицы;

- сумма всех выделенных подматриц равна рассматриваемой матрице; каждый узел помечен соответствующей подматрицей;

- два узла графа смежны, если соответствующие им подматрицы  имеют общие переменные; ребро инцидентное двум узлам М₁ и М₂ графа помечено множеством Х общих переменных.

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

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

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

Пусть М есть k-локальная матрица. Рассмотрим подграф графа G_M, как на рис.7. Для выполнимости M необходима выполнимость всех матриц М₂, М₂₁, ..., М_2q. Выполнимость суммы М₂ + М₂₁ + ... + М_2q, имеет место, когда имеется непустое пересечение единичных означиваний для М₂ и М₂₁, ..., М_2q по компонентам, определяемым множествами Y₁, Y₂, ..., Y_q переменных.

Рассмотрим, как выглядит единичное означивание для всей матрицы М, учитывая, что граф G_M есть дерево, узлами которого служат выделенные подматрицы. При этом анализ каждого подграфа, как на рис.7, сводится к построению всех Х-проекций единичных означиваний для М₂, каждая из которых может быть продолжена до единичного означивания матрицы, включающей все подматрицы М₂, М₂₁, ..., М_2q.

В результате, если описаны все Х-проекции, то при переходе от матрицы М₂ к М₁ излишне анализировать остальные компоненты единичных означиваний, определяемые переменными множества  Y₁ È...È Y_q.

Покажем, что справедлива следующая теорема.

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

Доказательство проведем индукцией по величине графа G_M.

Базис индукции. Если матрица М имеет не более k строк и ей соответствует граф G_M, состоящий из одного узла, то утверждение элементарно.

Индукционный переход. Пусть в графе G_M выделен подграф, как на рис.7, где узлы М₂₁, ..., М_2q висячие в G_M. Каждая матрица М_2i  имеет не более k переменных, которые включают переменные множества Y_i. Строим совокупность N  единичных означиваний для матрицы М^*₂ = М₂₁ + ... + М_2q + М₂. Пусть N_Х есть множество всех Х-проекций N.

Каждое означивание из N представляет собой вектор s_Xs_Y, где s_X - это Х-проекция и s_Y - компоненты, соответствующие всем переменным матриц М₂₁, ..., М_2q. Эти Х-проекции определяют логическую функцию f(X) от переменных Х, которая истинна в точности на этих наборах переменных. Заменим матрицу М^*₂ на М_Х, которая однозначно определяется функцией f(X) и соответствующим образом перестроим граф G_M. Затем вместо матриц М₂, М₂₁, ..., М_2q, в матрице M оставляем единственную матрицу М_Х. Пусть M^* есть результирующая матрица.

Покажем, что построение единичных означиваний для результирующей матрицы М^* влечет построение единичных означиваний для исходной матрицы. Действительно, если s есть ее единичное означивание, то s = s_Xs_Z, где s_X - ее Х-проекция. Но Х-проекция s_X расширяется  до единичных означиваний матрицы М^*₂. Таким образом, построение всех единичных означиваний для матрицы М^* влечет построение единичных означиваний для исходной матрицы.

Отметим, что с каждым перестроением подграфа получается не более 2^k классов эквивалентности.  Действительно, всевозможные означивания всех переменных матрицы М^*₂ разбиваются на не более, чем 2^k классов, так как множества переменных матриц М₂₁, ..., М_2q не пересекаются, а мощность множества Y₁ È...È Y_q не превосходит k.

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

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

Пусть å: S_i = s_i, i = 1, 2, ..., m, s_i Î {0, 1}, есть система булевских уравнений от n переменных {x₁, x₂, ..., x_n}, каждое из которых имеет в точности k_i £ k различных переменных, переменные входят только положительно и каждая переменная входит в точности в два уравнения.

Верно утверждение.

Лемма 8. Система уравнений å совместна  тогда  и  только тогда, когда s₁ + s₂ +…+s_m = 0.

Доказательство. Сложим по модулю 2 правые и левые части уравнений этой системы. Получим S₁+S₂+…+S_m =s₁ + s₂ +…+s_m. Так как каждая переменная входит в сумму S₁+S₂+…+S_m дважды, то она равна 0. Поэтому, если s₁ + s₂ +…+s_m ¹ 0, то система решений не имеет.

Пусть теперь s₁ + s₂ +…+s_m = 0. Доказательство проведем индукцией по числу переменных в системе. Система, содержащая в точности одну переменную, совместна.

Пусть теперь в системе имеются два уравнения: x + S¢_i = s_i, x + S¢_j = s_j. Подставим значение x = 0. В результате получим, что эти уравнения превратятся в такие: S¢_i = s_i, S¢_j = s_j. В силу индукционного предположения результирующая система совместна. Отсюда следует совместность исходной системы.

Лемма доказана.

Лемма 9. В системе å уравнений  каждая переменная существенная.

Доказательство. Пусть в системе å уравнения, включающие не существенную переменную x, имеет вид: x + S¢_i = s_i, x + S¢_j = s_j. Но тогда исходная система и система å¢, полученная из нее заменой этих уравнений на S¢_i = s_i, S¢_j = s_j, имеют одинаковое множество решений. Но это не так потому, что решение, включающее единичное значение переменной x и любое решение системы å¢, не будет являться решением исходной системы. Противоречие.

Лемма доказана.

Поставим в соответствие системе å граф G_S, содержащий m узлов, каждый его узел N_i помечен меткой s_i и ему соответствует уравнение S_i = s_i, i = 1, 2, ..., m. Узлы N_i  и N_j соединены ребром с меткой x Î {x₁, x₂, ..., x_n}, если x есть переменная общая для уравнений S_i = s_i и S_j = s_j. Очевидно, что в графе G_S метки всех ребер покрывают все множество {x₁, x₂, ..., x_n} переменных и метки разных ребер различны. 

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

Поставим в соответствие системе å матрицу М приведением каждой суммы S_i  в уравнении  S_i = 1 к к.н.ф. и представлением ее в виде столбцов; аналогично к к.н.ф. приводится выражение ØS_i , если в å имеется уравнение S_i = 0, i = 1, 2, ..., m.

Опишем преобразование графа G_S, когда некоторая переменная х принимает фиксированное значение s_х Î {0, 1}. Допустим, что эта переменная входит в уравнение х + S¢_i = s. Если  s_х = 0, то уравнение превращается в S¢_i = s, если s_х = 1, то в S¢_i = 1 - s. Пусть переменная х есть метка некоторого ребра, как на рис.8. Тогда ребро  N_iN_j  стирается, при s_х = 0 метки узлов N_i  и N_j не меняются, при s_х = 1 – обе метки инвертируются.

Соответствующие преобразования матрицы М состоят в следующем. Если s_х = 0, то в матрице М вычеркиваются все столбцы, которые на пересечении со строкой х имеют 0, и после этого вычеркивается сама строка х. Аналогично, при s_х = 1, вычеркиваются все столбцы, которые на пересечении со строкой х имеют 1, после этого вычеркивается строка х.   

Таким образом, означивание переменной приводит к соответствующим изменениям в системе å, графе G_S и матрице М. В итоге результирующая система, граф и матрица остаются связанными подобно исходным. Обозначим их соответственно å_sх, G_sх и М_sх. Аналогичными обозначениями будем пользоваться, когда рассматривается означивание s_х  совокупности х  переменных.

Пусть х есть совокупность переменных, |х| = h, и À_х  = {s₁, s₂, ..., s_q} - множество различных означиваний этих переменных. Множество х выделяет подграф G_х, узлы которого образуют множество N_х, а ребра - множество D_х: метка каждого ребра из D_х помечена переменной из х, каждый узел из N_х инцидентен по меньшей мере одному ребру из D_х.  

Назовем узел N Î N_х внутренним, если ему инцидентны ребра только из множества D_х, в противном случае назовем узел N Î N_х - граничным. Таким образом, каждый граничный узел смежен с некоторыми узлами, вне N_х.  Пусть число граничных узлов, определяемых переменными х,  равно k.

Выделим в множестве х те переменные, которыми помечены ребра, инцидентные граничным узлам. Допустим, что N₁, N₂, ..., N_k  суть все граничные узлы графа G_х  и подмножества Y₁, Y₂, ..., Y_k  Í х переменных, которыми помечены ребра, инцидентные соответственно узлам N₁, N₂, ..., N_k. Так как метки ребер графа G_S не пересекаются, то для не смежных граничных узлов эти множества различны.

Пусть s есть означивание переменных х. Сформируем по s бинарный вектор s = (s₁, s₂, ..., s_k)  длины k, где s_i, i = 1, 2, ..., k, есть сумма по модулю 2 компонентов из s, определяемых множеством Y_i. Назовем этот вектор ассоциированным с s.

Из определения ассоциированного вектора следует, что если s_i = 1, то означивание s приводит к инвертированию метки граничного узла N_i. Если же s_i = 0, то инвертирования нет. А так как различные инвертирования приводят к различным логическим функциям, то справедлива

Лемма 10. Если два различных вектора s₁ и s₂, означивающие переменные х, обладают различными ассоциированными векторами, то s₁ и s₂ принадлежат разным классам эквивалентности.

Лемма 11. Если мощность множества À_х равна 2^h, то оно разбивается на не менее, чем  различных классов эквивалентности.

Доказательство индукцией по числу h = |х|.

Базис индукции, когда h = 1, соответствует в точности двум граничным узлам. В этом случае лемма верна.

Индукционный переход. Пусть мощность множества х равна h + 1. Полагаем, что (h+1)-я переменная – это x и множество x – {x}  определяет k граничных узлов. Возможны следующие случаи.

1. Пусть ребро с меткой x Î x инцидентно двум граничным узлам. Присвоим переменной x значение s_x = 0. Это соответствует тому, что ребро x стирается и метки граничных узлов не меняются. Но тогда выполняются условия индукционной гипотезы, т.к. значения ассоциированных векторов определяются только остальными переменными x – {x}.

2. Пусть теперь ребро x инцидентно в точности одному граничному узлу, из тех, которые определяются множеством x – {x} переменных. Это означает, что число граничных узлов, определяемых множеством x, увеличилось на один по сравнению с множеством граничных узлов, определяемых множеством x – {x}, и новому граничному узлу инцидентно ребро x. При фиксированном значении s_x = 0 и при всех означиваниях остальных переменных из x – {x} получается не менее  различных ассоциированных векторов, которые имеют вид (s₁, s₂, ..., s_k, 0). При фиксированном значении s_x = 1 в точности один граничный узел из тех, которые определяются множеством x – {x}, приобретет инвертированную метку. Но при всех означиваниях переменных x – {x}  получается не менее  различных ассоциированных векторов. С фиксированным значением s_x = 1 они будут иметь вид (s₁, s₂, ..., s_k, 1). Отсюда вытекает, что число всех ассоциированных векторов, определяемых множеством x, будет не менее 2 = >.

3. Пусть теперь ребро x не инцидентно ни одному граничному узлу, из тех, которые определяются множеством x – {x} переменных. Это означает, что число граничных узлов, определяемых множеством x, увеличилось на два по сравнению с множеством граничных узлов, определяемых множеством x – {x}, и новым граничным узлам инцидентно единственное ребро x с меткой из множества x. По индукционной гипотезе всевозможные означивания переменных x – {x} приводят к  различным ассоциированным вектором (s₁, s₂, ..., s_k). При различных значениях s_x = 0 и s_x = 1 переменной x и при всех означиваниях остальных переменных из x – {x} получаются различные ассоциированные векторы вида (s₁, s₂, ..., s_k, 0, 0) и (s₁, s₂, ..., s_k, 1, 1) длины k + 2. При этом вектор (s₁, s₂, ..., s_k) из первых k компонентов пробегает не менее  различных значений. Но тогда при всех означиваниях переменных x порождается 2 =  различных ассоциированных векторов.

Лемма доказана.

Следствие. Множество переменных х определяет не менее  классов эквивалентности.

Пусть степень вершин графа G_S ограничена некоторой константой и для него существуют константы 0 < c₁, c₂ < 1 такие, что любой подграф, обладающий c₁n ребрами, имеет c₂n граничных узлов. Такие графы называются расширителями.

Из указанного свойства расширителя и следствия вытекает

Теорема 11. Существуют матрицы с n строками, мощность фактор-множеств которых для любого полного бинарного дерева не менее  2^сn, где c -  некоторая положительная константа.

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

Лемма 12. Пусть переменные x выделяют граф G_x, в котором никакая пара граничных узлов не соединена ребром. Тогда все означивания переменных x разбивается на классы эквивалентности с одинаковыми долями.

Доказательство. В этом случае ребра с метками Y_i  x, инцидентные любому граничному узлу N_i, не имеют общих меток с ребрами, инцидентными остальным граничным узлам N₁, N₂, …,N_i-1, N_i+1, …, N_k. Следовательно, классы эквивалентности, определяемые переменными x, представимы в виде (Y₁, Y₂, …, Y_k),  при i j. Здесь Y_i есть сумма по модулю 2 значений переменных Y_i при соответствующем означивании. Отсюда следует, что классов эквивалентности ровно 2^k и доля каждого 2^-k.

Лемма доказана.

В общем случае справедлива

Теорема 13. Все означивания переменных x разбиваются на классы с одинаковыми долями.

Доказательство проведем индукцией по |x|.

Базис индукции. Если |x| = 1, то x = {x} и граф G_x представляет собой два узла, пусть N₁ и N₂, соединенных ребром с меткой x. При x = 0 метки узлов N₁ и N₂ не меняются, при x = 1 обе метки – инвертируются. Тем самым, получаем в точности два класса эквивалентности с одинаковыми долями.

Индукционный переход. Пусть теорема верна для всякого множества  переменных x, для которого |x| = m-1. Добавим еще одну новую переменную x.

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

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

Индукционный переход. Допустим теперь, что ребро x соединяет два граничных узла N_i и N_j. Если присвоить переменной x значение 0, то выполняются условия индукционной гипотезы, т.к. метки узлов N₁ и N₂ не меняются. Поэтому все классы, определяемые переменными x, имеют одинаковые доли. Все означивания переменных x разбиваются на 4 вида: O₁( = 0,  = 0), O₂( = 0,  = 1), O₃( = 1,  = 0), O₄( = 1,  = 1), где  - это результирующая метка узла N_i и  - узла N_j, полученные после всех инвертирований.

Рассмотрим теперь, что произойдет, когда переменная x принимает значение 1. В этом случае метки узлов N_i и N_j  инвертируются, а все означивания классов O₁( = 0,  = 0), O₂( = 0,  = 1), O₃( = 1,  = 0), O₄( = 1,  = 1) будут характеризоваться иначе – соответственно O₁( = 1,  = 1), O₂( = 1,  = 0), O₃( = 0,  = 1), O₄( = 0,  = 0).

В итоге порождаются новые классы эквивалентности, обладающие также равномерным распределением. Отсюда и из того, что при x = 0 мы получили равномерное распределение классов эквивалентности, следует, что доли всех классов эквивалентности, порожденных переменными множества x  {x}, совпадают.

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

Заключение. Показано, что свойством локальности обладают достаточно простые ИМ, для которых легко обнаружить аналогию среди содержательных ПО. Их характерная черта состоит еще в том, что один класс эквивалентности обладает относительно большой мощностью. На содержательном уровне это соответствует многозначности описания объектов ПО. С другой стороны, не локальные ИМ не имеют аналогов среди содержательных ПО из-за их сложного описания.

Литература

1. Брошкова Н.Л., Попов С.В. О проектировании информационных систем, Препринт ИПМ РАН, 2005.