Атомы и шкалы решеток подмножеств

⇐ ПредыдущаяСтр 13 из 27Следующая ⇒

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

Определение 7.20. Пусть L — решетка подмножеств для X . Элемент а ∈ L называется атомом решетки, если а ≠ ∅ и не существует l ≠ а , l ≠ ∅ , такого, что

∅ ⊂ l ⊂ a .

В решетке L 2рассмотренного примера атомами будут μ 1— доктора наук, μ 2— кандидаты наук, μ 3— без научных степеней. Это самые конкретные понятия решетки. Алгоритм проверки на атомарность — отсутствие более конкретных непустых понятий.

Определение 7.21. Пусть L — решетка подмножеств для X . Тогда подсемейство элементов Ш решетки L называется шкалой решетки, если любой элемент решетки выражается через элементы шкалы Ш с помощью операций пересечения, объединения и разности ( ∩ , ∪ , ).

Итак, в силу того что L имеет алгебраическую структуру, в L можно выбрать систему образующих — шкалу.

Пусть Ш = {ω 1, … ω k} — шкала L . Тогда ∀ δ ∈ L существует его выражение через элементы шкалы, т. е.

δ = f (ω 1, … ω k),

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

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

Шкала называется атомарной или разбиением опорного множества, или координатной сеткой, если все ее элементы — атомы.

Базовая шкала в конечной решетке L называется минимальной ( максимальной ), если в решетке L нет шкалы с меньшим (большим) числом элементов.

Теорема 7.3. Любая решетка имеет хотя бы одну шкалу, например саму решетку.

Теорема 7.4. Решетка подмножеств определяется однозначно любой своей шкалой.

Доказательство . От противного. Пусть существуют две решетки подмножеств L и с одной и той же шкалой Ш.

Тогда для любого элемента λ ∈ L имеем представление его через элементы шкалы с помощью операций объединения, пересечения и разности.

Но в силу того что элементы шкалы Ш принадлежат также и другой решетке , то, производя действия над элементами Ш в соответствии с представлением X, будем получать каждый раз элементы L . Таким образом,

Аналогично доказывается, что элемент принадлежит и решетке L , т. е. решетки L и совпадают.

Теорема 7.5. Пусть L — произвольная решетка для X и L ≠ L 0.

Тогда ее атомарная шкала Шат= {а 1, ..., ап} = Ш mахявляется максимальной шкалой (самой большой, самой неэкономной). Мощность |Шат| = n , | L | = 2п.

Теорема 7.6. Пусть L — конечная решетка для X и L ≠ L 0. Тогда существует

Ш min= {ω 1, … ω k}, и число ее элементов k подчиняется равенству:

k = |Ш min| = [ log 2|Ш mах|] + 1,

где [ log 2|Ш mах|] — целая часть числа. Число элементов решетки

Пример 7. 21. Пусть X — времена событий, происходящих в определенные дни недели, и пусть

Шат= {пн, вт, ср, чт, пт, сб, вс}.

Тогда число элементов соответствующей решетки подмножеств | L | = 27.

Найдем Ш minдля L . Число k = [ log 27] + 1 = 3. Следовательно, минимальная шкала

Ш min= {ω 1, ω 2, ω 3}.

Построим эту минимальную шкалу следующим образом. Пронумеруем элементы атомарной шкалы двоичными числами:

пн — 001,

вт — 010,

ср — 011,

чт — 100,

пт — 101,

сб — 110,

вс — 111.

Тогда за ω 1возьмем объединение тех атомов, у которых в первом разряде 1, т. е.

ω 1= {пн ∪ ср ∪ пт ∪ вс},

далее ω 2— объединение тех атомов, у которых во втором разряде 1, и т. д.:

ω 2= {вт ∪ ср ∪ сб ∪ вс},

ω 3 = {чт ∪ пт ∪ сб ∪ вс}.

Теперь все элементы можно выразить через элементы минимальной шкалы. В самом деле:

и т. д.

Замечание 7.4. На практике часто выгоднее использовать минимальные шкалы, а не атомарные.

Вывод . Всякая решетка L подмножеств X обладает тремя важными свойствами, которые делают ее одним из основных понятий математической информатики.

• Решетка L — частично упорядоченное множество с отношением включения множеств.

• Решетка L — булева алгебра с тремя операциями: две бинарные операции (объединение и пересечение) и одна унарная операция (дополнение), для которых выполняются аксиомы булевой алгебры.

• Решетка L — топология на опорном множестве X и, следовательно, пара ( X , L ) — топологическое пространство.

Цит. по: Дискретная математика: учебник для студ. вузов /
Т.С. Соболева, А.В. Чечкин; под ред. А.В. Чечкина. —
М.: Издательский центр «Академия», 2006. — С. 96 – 108. —
(Университетский учебник. Сер. Прикладная математика и информатика).

Горбатов В.А. Основы дискретной математики / Учеб. пособие для вузов. — М: Высшая школа, 1986. — 312 с.;

Горбатов В.А. Фундаментальные основы дискретной математики. Информационная математика: Учеб. пособие для вузов. — М.: Наука, 2000. — 540 с.;

Кузнецов О.П. Дискретная математика для инженера / О.П. Кузнецов, Г.М. Адельсон-Вельский. — М: Энергоатомиздат, 1988 г. — 450 с.

Там же.

Горбатов В.А. Основы дискретной математики / Учеб. пособие для вузов. — М: Высшая школа, 1986. — 312 с.

Там же.

Горбатов В.А. Основы дискретной математики / Учеб. пособие для вузов. — М: Высшая школа, 1986. — 312 с.

Там же.

Горбатов В.А. Основы дискретной математики / Учеб. пособие для вузов. — М: Высшая школа, 1986. — 312 с.

АЛГЕБРА ЛОГИКИ

⇐ Предыдущая 8 9 10 11 121314 15 16 17 Следующая ⇒