3.9. Булевы образы

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

Эти образы комбинируются посредством исчисления высказываний, исходя из некоторого множества (простых) признаков. Сами признаки являются двоичными переменными, принимающими два возможных истинностных значения, скажем «истина» и «ложь». В данном разделе эти признакй служат образующими, а изображения являются правильно построенными булевыми выражениями.

Произвольная булева функция заданная переменными может быть выражена в конъюнктивной нормальной форме

Показатели степени принимают значения 1, 0, —1, причем полагают, что не встречается. Существует и дизъюнктивная нормальная форма, в которой конъюнкции и дизъюнкции меняются ролями. Это представление ниже не будет явно упоминаться.

Это укладывается в формализм образов, если состоит из признаков определенных на некотором опорном пространстве Группа преобразований подобия на X индуцирует отображения произвольный элемент (см. разд. 3.3).

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

Тип соединения 2 показан на рис. 3.9.1. Любой будет состоять из одного или нескольких изолированных подграфов, каждый из которых имеет не более образующих и подграфов с полной графовой структурой.

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

где так что с является комбинацией причем каждая имеет тип соединения «полный». В дальнейшем мы не будем настаивать, чтобы индексы составляли счетное множество.

Пусть даны две конфигурации с (как выше) и они будут отождествляться, если

Другими словами, конфигурации идентифицируются по их логическим функциям.

Рис. 3.9.1.

Случай 3.9.1 (изображения с логическими признаками). Множество состоящее из всех результирующих изображений с логическими признаками называется алгеброй изображений с логическими признаками и структурной сложностью на пространстве образующих .

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

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

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

индуцированного преобразованиями если то .

Предметное пространство часто будет конечным; тогда нет необходимости иметь на нем какую-либо топологию. В противном случае топология будет вводиться посредством всех окрестностей вида

где М — произвольное конечное подмножество Для последующего изложения достаточно считать, что X — регулярное топологическое пространство.

В данной алгебре изображений имеется много операторов вида и бинарный оператор

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

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

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

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

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

где Е — заданное подмножество, некоторый набор признаков. Если «истина» для всех из Е, то мы запишем

Теперь мы готовы к тому, чтобы количественно определить кластеризацию. Если Е — заданное подмножество опорного пространства, то как выразить его кластеризацию? Может случиться, что мы располагаем некоторым естественным объемом или расстоянием в Иногда инвариантность будет выделить

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

Мы будем исходить из других соображений.

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

Если выбрана так, что она действительно отражает степень важности, приписываемой нами различным признакам, то в выше приведенном принципе содержится зародыш применяемого нами определения кластеризации.

Пусть Е — данное подмножество X, рассмотрим множество всех признаков, которые тождественно постоянны в Е:

Определение 3.9.1. Под кластеризацией подмножества Е понимается

Мы тарке будем использовать частичные меры кластеризации

Если то удобно использовать следующую дополнительную величину.

Определение 3.9.2. Размером множества Е называется величина

Часто инвариантна по отрицанию, и тогда достаточно вычислить лишь или и умножить на два.

Впрочем, можно также определить размер в общем виде при помощи выражения, аналогичного (3.9.9), но используя лишь те для которых «истина». Оба варианта кажутся интересными, и мы будем иметь возможность применить их оба; из контекста будет ясно, какой именно вариант выбран.

Если так что . В частности, если Е состоит из одной точки,

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

Пусть даны Е и множество признаков, тождественно истинных на Е,

какое множество опорного пространства описывается при помощи Другими словами, мы вводим замыкание по признакам:

Из (3.9.11) непосредственно следует, что Если они совпадают, то говорят, что Е замкнуто по признакам.

Теорема 3.9.1. Если Е замкнуто по признакам, то оно также топологически замкнуто.

Доказательство. Пусть точка, не принадлежащая Е, такая, что все ее окрестности пересекаются с ?; мы хотим показать, что тогда она сама должна принадлежать Е. Поскольку Е замкнуто по признакам, то это то же самое, что Если то должен существовать признак такой, что

но имеет окрестность

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

Любое множество, описываемое при помощи одного признака автоматически является замкнутым по признаку. Действительно, в этом случае множество состоит из всех импликант т. е. из всех таких, что из «истина» следует «истина». Пусть поскольку «истина», то мы должны иметь «истина», так что множество замкнуто по признаку.

Теперь рассмотрим произвольное пересечение множеств замкнутых по признакам

Тогда Е также замкнуто по признакам, Чтобы убедиться в этом, предположим противное; пусть существует точка такая, что Тогда должен существовать такой а, что поэтому существует такой, что «истина», «ложь». Но поскольку то для любого такого, что «истина», мы должны иметь «истина». Но поэтому отсюда «истина»; полученное противоречие доказывает наше утверждение.

Следовательно, конъюнкции простых признаков образуют множества, замкнутые по признакам. Отсюда

Теорема 3.9.2. Множество в X замкнуто по признакам тогда и только тогда, когда его можно задать в виде

где .

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

Замечание 3.9.1. Если размер определен в терминах тождественно истинных признаков, то размер множества Е равен размеру множества замкнутого по признакам. Это следует из того, что множества тождественно истинных признаков для совпадают. Также, если инвариантна по отрицанию, то

Замечание 3 9.2. Если на опорном пространстве задан объем, то естественно поставить вопрос о том, какие именно множества Данного объема имеют максимальную кластеризацию; более подробно мы рассмотрим этот вопрос позднее; это приведет нас к задаче изопериметрического типа.

Замечание 3.9.3. Иногда мы будем вводить логику признаков в произведении пространств, скажем . Интересно выявить соотношение между размерами (и кластерами) в двух

маргиналах и в произведении Ниже описаны две возможности.

Для данного множества обозначим через его проекции соответственно на два маргинальных пространства. Если известны значения то каково значение Ответ зависит от того, какая мера введена в С и как она выражается через и из

Теорема 3.9.3. а) Пусть где состоит из всех признаков из всех признаков Если просто задана при помощи меры на и на то

б) Пусть состоит из всех признаков истинностное значение где Если то

Доказательство . Признаки из С, которые пересекают Е, составляют множество

Однако для того, чтобы из пересекала Е, необходимо и достаточно, чтобы пересекала так как признак не зависит от другой координаты. Аналогичное утверждение справедливо для второго члена, и учитывая, что члены, входящие в (3.9.18), не пересекаются, получаем (3.9.16).

Доказательство Пока допустим, что Е является произведением множеств Для того чтобы признак пересекал Е, необходимо существование точек таких, что Но это означает, что

Однако это равносильно тому, что либо

либо

Как (3.9.20), так и (3.9.21) сводятся к тому, что либо отделяет от либо отделяет от Следовательно, либо

пересекает либо пересекает С другой стороны, пусть, например, пересекает Тогда очевидно, что равная истинностному значению пересекает Е (напомним, что Е — произведение множеств). Чтобы вычислить мы должны получить меру события, состоящего в том, что или пересекают соответственно или поэтому

где мы использовали нормировку р-меры, .

Для того чтобы освободиться от предположения, что Е — произведение множеств, отметим, что в общем случае и с учетом свойства монотонности размера отсюда следует истинность неравенства (3.9.17).

Замечание 3.9.4. Читатель может убедиться в том, что всегда имеет место

Чтобы освоиться с введенными выше понятиями, мы рассмотрим несколько примеров.

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

или, нормируя , получаем

Здесь каждое множество тривиально замкнуто по признакам.

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

и I — фиксированное натуральное число, не превосходящее разделяет точки опорного пространства. Пусть дано Как образуется его замыкание? Рассмотрим рис. 3.9.2, где Множество состоит из признаков и соответствующие множества вида (2.4) указаны на рисунке. Это приводит к замыканию Очевидно, что в данном случае операция замыкания состоит из заполнения щелей меньшей длины, чем Чтобы определить мы просто должны найти сумму длин оставшихся шелей и вычесть из нее удвоенное число этих щелей. Заинтересованному читателю можно посоветовать рассмотреть соответствующий случай двумерной решетки, где интервалы заменяются переносами данного фиксированного множества. И опять замыкание приводит к регуляризации или очищению исходной картины.

Рис. 3.9.2.

Пример 3. Пусть , причем признаки заданы так:

не замкнуто по отрицанию. Мера определена при помощи соотношения

так что равномерно распределена, так же как и значение двузначного верхнего индекса. Мера инвариантна по отрицанию. Любая конъюнкция, составленная из определяет замкнутый интервал в X, поэтому множества в X, замкнутые по признакам, являются отрезками. Замыкание множества по признакам представляет собой отрезок.

Чтобы выяснить, как в данном случае понимается размер, достаточно предположить, что Е замкнуто по признакам, т. е. является отрезком Тогда, для того чтобы или

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

Пример 4. В нашем четвертом примере роль предметного пространства играет рассмотрим все признаки вида

где - произвольное линейное выражение

Другими словами, мы используем линейную пороговую логику. Для такого признака множество вида «истина») является замкнутой полуплоскостью, которую можно отождествить с направленной прямой. Очевидно, что в этой логике множество замкнуто по признакам тогда и только тогда, когда оно (топологически) замкнуто и выпукло.

Каков размер множества Е в этой логике признаков? Если мы хотим, чтобы модель была инвариантной относительно группы евклидовых движений на плоскости, то мера должна быть однозначна, что известно из интегральной геометрии (см. Бляшке (1955)). Для вычисления размера Е мы просто должны найти -меру множества направленных прямых, пересекающих Е. Но это также является классическим результатом интегральной геометрии: пропорциональна длине границы выпуклого замыкания Е.

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

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

Пример 5. Пусть X — единичный квадрат в плоскости, и пусть признаки имеют вид

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

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

Признак или пересекает тогда и только тогда, когда Е содержит точку вида Аналогичное утверждение справедливо и для других признаков. Следовательно,

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

Определение 3.9.4. Под разделением двух множеств понимается число

Справедливы следующие утверждения:

1) если множества пересекаются, но обратное не всегда верно;

2) Если .

3) Для разделения необязательно выполняется неравенство треугольника.

Утверждение (1) очевидно. Для доказательства (2) заметим, что если тождественно постоянна на причем эти истинностные значения различны, то аналогичное утверждение верно для соответственно. Следовательно, -множество для определяемое по (3.9.35), не уже чем -множество для Справедливость утверждения (3) будет установлена позже.

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

Поучительно выяснить, каков смысл разделения в четвертом примере, приведенном выше Можно считать, что замкнутые выпуклые множества (см. рис. 3.9.3). Тогда в соответствии с одним из классических результатов интегральной геометрии сразу имеем, что

где и две общие касательные (опорные прямые), разделяющие а и дуги, проходящие вдоль границ

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

Рис. 3.9.3.

Мы должны различать 9 возможных взаимоисключающих случаев (см. табл. 3.9.1). В первом случае признак тождественно истинен как на так и на в то время как в случае 3 он является тождественно истинным на но на он не постоянен; он пересекает Выделим последний, девятый случай, когда признаки пересекают как так и р-меру девятого класса обозначим как

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

Используя свойство аддитивности р-меры и определение 3.9.2, получаем следующую теорему:

Теорема 3.9.4. Для двух множеств и с конечными размерами и конечным разделением

Таблица 3.9.1 (см. скан)

Замечание 3.9.5а. Пусть конгруэнтные и параллельные прямоугольники в плоскости, воспользуемся пороговой логикой, описанной в четвертом примере. Если эти прямоугольники касаются, то в (3.9.30) член обращается в нуль, но . С другой стороны, если прямоугольники находятся далеко друг от друга, то становится большой разность и ее легко вычислить. Поэтому значение может быть меньше, равно или больше, чем сумма

Замечание 3.9.56. Если через С обозначить условие пересечения Е признаком то

где последний сомножитель можно вычислить при помощи условной меры Поэтому разделение двух кластеров можно выразить в терминах четырехкратного вычисления размера [см. (3.9.31)].

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

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

При определении кластера (и размера) нам теперь не потребуется множество всех признаков, которые тождественно истинны; такое множество может быть пустым даже в нетривиальных ситуациях. Однако мы будем удовлетворены, если признак окажется истинным с большой вероятностью.

Определение 3.9.5. Пусть дано распределение вероятности Р над опорным пространством X и число а заключено между 0 и 1; под признаковым замыканием Р на уровне а понимается подмножество

Кластером Р на уровне а называется . Очевидно, что является автоматически подмножеством X, замкнутым по признакам. Значения а, которые мы сочли бы подходящими, близки к 1; например, мы могли бы потребовать 95%-ного замыкания кластера и т. д. Отметим, что может быть и пустым.

Поучительно посмотреть, к чему сводится это понятие в примере, рассмотренном выше.

Рассмотрим пример 1; пусть Р определено посредством вероятностей соответствующих членам Признак заданный как подмножество удовлетворяет соотношению (3 9.39) тогда и только тогда, когда

Но отсюда следует, что элемент будет исключен из тогда и только тогда, когда , поэтому в данном неструктуризованном случае просто имеем

Возвращаясь к примеру 2 мы видим, что признак удовлетворяет соотношению (3.9.39) при условии, что

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

Чтобы рассмотреть пример 4 предположим, что Р — двумерное нормальное распределение в Поскольку теперь признаки заданы как полупространства, можно применить любое

несингулярное линейное преобразование Этим способом Р сводится к двумерному нормальному распределению Р с центром в начале координат, со средним квадратичным отклонением, равным 1, и с нулевым коэффициентом корреляции. Однако в этом цилиндрически симметричном случае является просто замкнутым кругом. Если при обратном преобразовании Р к Р получим, что

причем и если то

Признаки должны обладать свойством разделения точек. Р. Вайтал поставил следующую задачу по вероятностной мере Р. Если известно, что «истина») при всех то можно ли этим определить Р?

Рассмотрим пример 4. В этом случае известна масса в любой замкнутой полуплоскости. Но тогда Р однозначно определено (см. Крамер, Уолд

С другой стороны, если мы определим признаки при помощи условия

где параллельный перенос заданного борелевского множества Е, то можно ли по определить Р, если первое задано для всех

Можно дать следующий неполный ответ. Пусть Е замкнуто и ограничено. Тогда

где

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

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

Мы не рассмотрели случай, когда Е не ограничено. Отметим, что последнему соответствует случай с полуплоскостью, только если в включены вращения.

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

Определение 3.9.6. Под логикой признаков второго порядка понимаются все описания вида

где .

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

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

Отметим, что если пересекает Е, то либо либо (либо оба) также должны пересекать Е, поскольку в противном случае должна быть тождественно постоянной на Е. Следовательно,

Эти три множества, появляющиеся в правой части (3.9.52), могут быть описаны иначе следующим образом: в первом множестве тождественно постоянен, но он не может быть тождественно истинным, так как тогда также тождественно истинна и не пересекает Е. Аналогично, во втором множестве «ложь», поэтому с учетом того факта, что мера

произведения на

и если инвариантна по отрицанию, то

Группируя члены в (3.9.54), получим

Отсюда имеем неравенство Тем самым доказана следующая теорема:

Теорема 3.9.5. Всегда выполнено

и если инвариантна по отрицанию, то

С другой стороны, если исследуется лишь при помощи признаков пересекающих , то мы получим другую меру

которая не превосходит

Для конкретности рассмотрим пример 2. Что представляют собой в этом случае и -замыкание? Если признаки из комбинировать при помощи операции «или», то получим признак

Однако отсюда следует, что

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

Но из (3.9.61) следует, что тогда при помощи признака из можно отделить любую точку от : в этом частном случае все множества замкнуты (в смысле -замыкания).

Что происходит в примере 3? Достаточно отметить, что дизъюнкция двух признаков определяет множество в X, состоящее из одного или двух отрезков, либо же оно пусто. Тогда замкнутые в смысле -замыкания множества будут состоять из топологически замкнутых, но произвольных в других отношениях множеств (если допускаются лишь конечные конфигурации, то получаем конечные объединения отрезков), и -замыкание признака совпадает с топологическим замыканием.

Пусть теперь Е — объединение отрезков которые не пересекаются и упорядочены по возрастанию в [0, 1] Тогда можно вычислить размер который является функцией следующих двух величин:

С другой стороны, чтобы вычислить допустим, что пересекает «истина». Если относятся к одному и тому же классу образующих, то или что невозможно. Если они относятся к различным классам образующих, скажем то мы должны иметь либо либо причем интервал попадает в одну из щелей. Следовательно,

Если пересекает «ложь», то с помощью аналогичных рассуждений устанавливаем, что этот случай соответствует нулевому значению меры Следовательно,

Здесь неожиданно появляется мера Хаусдорфа.

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

по модулю . В случае они не сводятся к одной образующей.

Комбинируя такие -признаки, мы получаем множества, показанные на рис. 3.9.5; они обсуждались в разд. 5.

Чтобы найти в этом примере рассмотрим множество, показанное на рис. 3.9.6, где проекции Е соответственно на и Соответствующие длины обозначены через

Рис. 3.9.4

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

Множество истинности дизъюнкции состоит из объединения трех квадрантов, и поскольку также пересекает Е, то множество -мерой содержит точку

Комбинируя все возможные случаи, получим

Отметим, что в то время как в случае одного признака мы имели дело с длиной (периметром), теперь мера (размер) имеет вид площади.

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

Изображение которое р-замкнуто по признакам, может быть выражено в виде конъюнкции (не более чем) дизъюнкций.

Рис. 3.9.6.

Естественно использовать в качестве численной сложности (см. разд. 4.1) мощность множества индексов А, по которому берется конъюнкция, а в качестве структурной сложности — число Дизъюнкции называются (составными) признаками порядка . В рамках линейной пороговой логики множество на рис. 3.9.7 замкнуто в смысле -замыкания, но не обладает этим свойством;

Теорема 3.9.6. Операции р-замыкания удовлетворяют следующему закону сокращения:

Рис. 3.9.7,

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

и получить

что доказывает (3.9.69).

Введем внешние слои множества Е опорного пространства

Внешние слои описывают, насколько «граница» Е поддается исследованию посредством признаков с возрастающей структурной сложностью.

В общем случае мы можем сформулировать следующее утверждение:

Теорема 3.9.7. Пусть Е — (топологически) замкнутое подмножество предметного пространства-, рассмотрим последовательность замыканий Тогда при имеет место монотонная сходимость к исходному множеству

Доказательство. Поскольку не возрастает, и то ясно, что эта последовательность сходится к некоторому множеству . Если , выберем точку , причем Так как Е (топологически) замкнуто, можно найти такую окрестность что (напомним, что X регулярно). Такую окрестность можно определить посредством конечного числа признаков из Если взять большим, чем это число, то р-замыкание Е не будет содержать поэтому , что противоречит нашему предположению, и утверждение доказано.

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