Графы и частично упорядоченные множества (стр. 2 из 2)

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

Рассмотрим два очень важных понятия теории у-множеств, которые позволяют существенно облегчить решение некоторых задач анализа рассуждений. Это верхние и нижние конусы. Пусть A - произвольное подмножество у‑множества M (т.е. AÍM). Определим для множества A верхний и нижний конусы.

Нижним конусом

множества A называется множество всех таких элементов x, принадлежащих множеству M, каждый из которых будет меньше или равен (£) относительно любого элемента a, принадлежащего множеству A.

Верхним конусом

множества A называется множество всех таких элементов x, принадлежащих множеству M, для каждого из которых любой элемент из множества A будет меньше или равен (£) ему.

Нижний и верхний конусы можно определять не только для подмножеств, но и для элементов у‑множества M. Если у-множество изображено в виде ориентированного графа, то верхний и нижний конус для любого элемента X можно "вычислить", используя свойство достижимости:

верхний конус элемента X- это множество элементов, в это множество входит сам элемент X и все элементы, достижимые из X;

нижний конус элемента X- это множество элементов, в это множество входит сам элемент X и все элементы, из которых X достижимо.

Например, на множестве чисел M = {2, 4, 5, 7}, упорядоченном по величине, нижним конусом числа 4 является множество {2, 4}, а верхним - {4, 5, 7}. Если рассмотреть у‑множество, показанное на рисунке 9, b, то

={p, q, r} и = {r, s, t, u}.

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

Теорема. Пусть в произвольном у-множестве выбрано некоторое подмножество M = {q₁, q₂,... q_n} его элементов. Тогда

(i) M^D =

Ç Ç... Ç ;

(ii) M^Ñ=

Ç Ç... Ç .

Доказательство. Пусть m_i - произвольный элемента множества M^D. Чтобы для каждого q_k (q_kÎM) соблюдалось условие q_k£m_i, необходимо и достаточно, чтобы элемент m_i содержался в верхнем конусе каждого из элементов множества M. А это означает, что элемент m_i содержится в пересечении

Ç Ç... Ç верхних конусов всех этих элементов. Аналогично, если m_i - произвольный элемента множества M^Ñ, то для каждого q_k (q_kÎM) соблюдается условие m_i£q_k, а это означает, что элемент m_i содержится в нижнем конусе каждого из элементов множества M. Следовательно, все элементы множества M^Ñ должны находиться в пересечении Ç Ç... Ç нижних конусов. Конец доказательства.

Для лучшего понимания соотношений, связанных с конусами, рассмотрим граф, изображающий диаграмму Хассе некоторого у-множества (рисунок 3).

Рис.3

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

R^D= {R, G, F, Q}

(элемент R содержится в верхнем конусе по определению, а остальные элементы введены как достижимые из R);

M^D= {M, N, G, F, Q}; D^D= {D}; C^D= {C, D}; D^Ñ = {D, C, A}

(элемент D содержится в нижнем конусе по определению, а элементы C и A введены в нижний конус, поскольку из них достижим элемент D);

R^Ñ = {R, A}; M^Ñ = {M}; C^Ñ = {C, A}, G^Ñ = {G, M, R, A}.

Зная верхние или нижние конусы элементов, можно по теореме легко вычислить соответственно верхние и нижние конусы для множеств, состоящих их этих элементов. Например,

{R, M}^D = R^DÇM^D= {R, G, F, Q}Ç{M, N, G, F, Q}={G, F, Q};

{R, C}^D = R^DÇC^D= {R, G, F, Q}Ç{C, D}= Æ

(посмотрев на рисунок 10, можно убедиться, что в графе нет ни одной вершины, которая достижима как из R, так и из C);

{R, M}^Ñ = R^ÑÇM^Ñ= {R, A}Ç{M}= Æ;

{R, C}^Ñ = R^ÑÇC^Ñ= {R, A }Ç{C, A}= {A}.

Рассмотрим еще одно соотношение, связанное с конусами.

Теорема 2. Пусть r и q - различные элементы у-множества, при этом r £ q. Тогда для верхних и нижних конусов этих элементов соблюдаются соотношения

Í и Í .

Доказательство. Данные соотношения следуют из определений верхних и нижних конусов. Если r £ q, то это означает, что q содержится в

и, следовательно, все элементы из также содержится в . В то же время в нижних конусах наоборот: если r £ q, то это означает, что r содержится в и, следовательно, все элементы из также содержится в . Конец доказательства.

Например, для у-множества, изображенного на рисунке 3, элементы A и G- сравнимы, т.е. A£G (элемент A предшествует элементу G). Построим верхние и нижние конусы этих элементов:

A^D = {A, C, D, R, G, F, Q }; G^D = {G, F, Q }; A^Ñ = {A}; G^Ñ = {G, R, A, M}.

Сравнивая эти конусы по включению, мы увидим, что в соответствии с теоремой 2 соблюдаются следующие соотношения: G^DÍA^D и A^ÑÍG^Ñ. Если же выбрать для анализа пару элементов, для которых отношение £ не имеет места (например, элементы Q и N на рисунке 3), то мы увидим, что для них, соотношения, сформулированные в теореме 2, не верны.

Для анализа E-структур очень важными являются еще два понятия - минимальные и максимальные элементы. Суть в том, что они существенно отличаются от наименьшего и наибольшего элементов. Начнем с минимальных элементов. Как мы уже знаем, если в структуре существует наименьший элемент, то он меньше любого другого элемента этого у‑множества. Но существуют элементы (в алгебре их иногда называют атомами), которые больше наименьшего, но при этом обладают одним удивительным свойством. Предположим, что элемент A- атом, а X_i произвольный элемент этого у-множества, кроме наименьшего. Тогда при сравнении атома A с любым элементом X_i возможны только два варианта:

1) A £ X_i либо 2) элементы A и X_i несравнимы. Атомы в отличие от наименьших элементов называются минимальными элементами.

Чтобы лучше понять это рассмотрим рисунок 10. Видно, что в этом у-множестве наименьшего элемента не существует, так как ни один элемент в нем не обладает тем свойством что он предшествует любому элементу. Например, элементу A не предшествует ни один элемент, но при этом он сам не предшествует таким элементам как M и N (т.е. пары (A, N) и (A, M) не сравнимы, так как неизвестно, какой из элементов в каждой из этих пар является предшественником другого). Поэтому элемент A можно считать минимальным (но не наименьшим!) элементом. Нетрудно видеть, что в этой же структуре есть еще один минимальный элемент - M, который обладает теми же свойствами, что и элемент A.Т. е. в этой структуре существуют два минимальных элемента (хотя наименьшего в ней нет). Если в структуре имеется наименьший элемент, то в этом случае минимальными элементами являются другие элементы, которые больше наименьшего, но при этом непосредственно примыкают к нему.

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

1) если наибольший элемент существует, то максимальные элементы непосредственно предшествуют наибольшему элементу;

2) любой элемент у‑множества (кроме наибольшего) либо предшествует максимальному элементу, либо не сравним с ним.

Посмотрев на у-множество на рисунке 10, можно с учетом этих свойств легко определить его максимальные элементы: это D, F и Q.