Отношения порядка

Отношение называется отношением нестрогого порядка, если оно рефлексивно, антисимметрично и транзитивно. Отношение называется отношением строгого порядка, если оно антирефлексивно, антисимметрично и транзитивно. Оба типа отношений называются отношениями порядка. Элементы а, b сравнимы по отношению порядка R, если выполняется aRb или bRа. Множество М, на котором задано отношение порядка, называется полностью упорядоченным, если любые два элемента М сравнимы, и частично упорядоченным в противном случае.

Пример 3.15.

1. Отношения £ и ³ для чисел являются отношениями нестрогого порядка, отношения < и > – отношениями строгого порядка. Оба отношения полностью упорядочивают множества N и R.

2. Определим отношения £ и < на Rⁿ следующим образом: (a₁, …, a_n) £ (b₁, …, b_n), если a₁ £ b₁, …, a_n £ b_n ; (a₁, …, a_n) < (b₁, …, b_n), если (a₁, …, a_n) £ (b₁, …, b_n) и хотя бы в одной координате i выполнено a_i < b_i. Эти отношения определяют частичный порядок на Rⁿ: (5, 1/2, -3) < (5, 2/3, -3); (5, 1/2, -3) и (5, 0, 0) несравнимы.

3. На системе подмножеств множества М отношение включения Í задает нестрогий частичный порядок, а отношение строгого включения Ì задает строгий частичный порядок. Например, {1, 2}Ì{1, 2, 3}, а {1, 2} и {1, 3, 4} несравнимы.

4. Отношение подчиненности в организации задает строгий частичный порядок. В нем несравнимыми являются сотрудники разных отделов или студенческих групп.

5. Пусть в списке букв конечного алфавита А порядок букв зафиксирован, т.е. всегда один и тот же, как, например, в русском или латинском алфавите цифр. Тогда этот список определяет полное упорядочение букв, которое назовем отношением предшествования и обозначим Ü (a_i Ü a_j, если a_i предшествует a_j в списке букв). На основе отношения предшествования букв строится отношение предшествования слов, определяемое следующим образом. Пусть даны слова a₁ = a₁₁ …a_1m и a₂ = a₂₁ …a_2m. Тогда a₁ Ü a₂, если и только если либо 1) a₁ = ba_ig, a₂ = ba_jd и a_i Ü a_j (b, g, d – некоторые слова, возможно, пустые, a_i и a_j – буквы), либо 2) a₂ = a₁b, где b – непустое слово. Это отношение задает полное упорядочение множества всех конечных слов в алфавите А, которое называется лексико-графическическим упорядочением слов.

6. Наиболее известным примером лексико-графического упорядочения является упорядочение слов в словарях. Например, лес Ü лето (случай 1 определения: b = ле, с Ü т, g – пусто, d = о), поэтому слово «лес» расположено в словаре раньше слова «лето», лес Ü лесть (случай 2 определения: b = ть).

7. Если рассматривать числа в позиционных системах счисления (например, в двоичной или десятичной) как слова в алфавите цифр, то их лексико-графическое упорядочение совпадает с обычным, если все сравнимые числа имеют одинаковое число разрядов. В общем же случае эти два вида упорядочения могут не совпадать: например, 10<1073 и 20<1073, но 10 Ü 1073, а 20 Þ 1073. Для того чтобы они совпадали, нужно выравнять число разрядов у всех сравниваемых чисел, приписывая слева нули. В данном примере при этом получим 0020 Ü 1073. Такое выравнивание автоматически происходит при записи целых чисел в ЭВМ.

8. Лексико-графическое упорядочение цифровых представлений дат вида 05.09.99 (пятое сентября 1999 года) не совпадает с естественным упорядочением дат от ранних к поздним: например, 05.09.99 лексико-графически «старше» третьего числа любого месяца любого другого года. Чтобы возрастание дат совпадало с лексико-графическим упорядочением, обычное представление надо «перевернуть», т. е. годы поместить слева: 99.09.05.

3.7. Понятие алгебры

Алгеброй А называется совокупность < > множества М с заданными в нем операциями S = {f₁₁, f₁₂, f₁₃, ... , f_1n , f₂₁, ... f_2n, f_m1, f_m2, ... f_mn}, A = <M, S>, где множество М – носитель, S – сигнатура алгебры. Первый нижний индекс у идентификатора операции указывает ее местность.

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

Рассмотрим алгебру множеств (алгебру Кантора)

носителем которой является булеан универсального множества 1, сигнатурой – операции объединения È, пересечения Ç и дополнения ` . Для операций алгебры Кантора выполняются следующие законы:

· коммутативности объединения и пересечения

· ассоциативности объединения и пересечения

· дистрибутивности пересечения относительно объединения и объединения относительно пересечения

· идемпотентности объединения и пересечения

· действия с универсальным 1 и пустым Æ множествами

· де-Моргана

· двойного дополнения

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

· закон дистрибутивности пересечения относительно разности

· закон коммутативности симметрической разности

A*B = B*A;

· закон ассоциативности симметрической разности

A*(B*C) = (A*B)*C;

· закон дистрибутивности пересечения относительно симметрической разности

· законы склеивания

· законы поглощения

· законы Порецкого

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

Под сложностью представления множества М понимают число символов М_i,`М_i в задающем его выражении.

Пусть в пространстве 1 = {A, B_, C} задано множество вида

На основании законов идемпотентности, коммутативности и ассоциативности объединения получаем

Применив законы коммутативности, пересечения и склеивания, имеем

Использовав законы коммутативности, пересечения и склеивания, получаем

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

Сложность представления множества M(A, B, C) уменьшилась от 21 до 5.