Булевы алгебры.

 

Определение 1: Пусть - отношение порядка на множестве . Элемент называется наименьшим (наибольшим) элементом множества , если выполнено условие:

(для наименьшего элемента);

(для наибольшего элемента).

Определение 2: Пусть - отношение порядка на множестве . Элемент называется минимальным (максимальным) элементом множества , если выполнено условие:

(для минимального элемента);

(для максимального элемента).

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

Если во множестве есть наименьший элемент, то он будет и минимальным. Обратное не всегда верно. Кроме того, в некотором множестве при заданном отношении порядка может быть много минимальных элементов, но ни одного наименьшего.

Пример:

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

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

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

Рассмотрим класс частично упорядоченных множеств, удовлетворяющих следующим эквивалентным между собой условиям:

1) Условие минимальности. Всякое непустое подмножество частично упорядоченного множества обладает хотя бы одним минимальным во множестве элементом.

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

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

Теорема 1: Условия минимальности, обрыва убывающих цепей и индуктивности - эквивалентны между собой.

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

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

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

Определение 3: Частично упорядоченное множество называется структурой или решёткой, если в нем любое двухэлементное подмножество имеет точную верхнюю границу и точную нижнюю границу . Точная верхняя граница для элементов и обладает свойствами: , и причем , если - любая другая верхняя граница этих элементов. Аналогично определяется точная нижняя граница.

Определение 4: Решетка называется дистрибутивной, если операции и связаны дистрибутивными законами, т.е. выполнены соотношения:

,

.

Замечание: Указанные соотношения называются двойственными. Отметим, что в решетке одно из этих соотношений является следствием другого.

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

Определение 6: В решетке можно определить следующим образом дополнение: является дополнением для (а - дополнением для ), если одновременно и .