Тема: Частично-упорядоченные множества

  • Вид работы:
    Курсовая работа (т)
  • Предмет:
    Математика
  • Язык:
    Русский
  • Формат файла:
    MS Word
  • Размер файла:
    21,58 Кб
Частично-упорядоченные множества
Частично-упорядоченные множества
Вы можете узнать стоимость помощи в написании студенческой работы.
Помощь в написании работы, которую точно примут!

Содержание

Введение

. Бинарные отношения на множестве

.1 Бинарные отношения, определения

.2 Примеры бинарных отношений

. Отношение эквивалентности

.1 Рефлективность, примеры рефлективности

.2 Симметричность

.3 Транзитивность

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

. Частично-упорядоченные множества

.1 Основные определения, свойства ч.у.м

.2 Решетки

.3 Дистрибутивность решетки

.4 Примеры дестрибутивных и недестребутивных решеток

Заключение

Список используемой литературы

Введение

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

. Бинарные отношения на множестве

.1 Бинарные отношения, определения

Для начала введем несколько вспомогательных определений.

Определение 1. Декартовым произведением множеств X и Y называется множество XxY всех упорядоченных пар (x, y) таких, что x X, yY.

Определение 2. Соответствием между множествами X и Y (или соответствием из X в Y) называется любое подмножество декартова произведения X xY. Если множества X и Y совпадают, то соответствие между множествами X и Y называют также бинарным отношением на множестве X.

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

.2 Примеры бинарных отношений

Пусть X = {a, b, c, d}, Y = {1, 2, 3, 4, 5}. Тогда множество кортежей a={(a, 1), (b, 2), (c, 3), (d, 4)} являются соответствием из X в Y.

Отметим, что обычно соответствия задаются не путем указания подмножества a декартова произведения X xY, а путем указания свойства пар (x, y), принадлежащих этому подмножеству . Отношение a = {(4, 4), (3, 3), (2, 2), (4, 2)} на множестве X = {4, 3, 2} можно определить как свойство "Делится" на этом подмножестве целых чисел.

Отношения могут задаваться формулами:

·формулы y = x2 +5x - 6 или

. Отношение эквивалентности

отношение множество рефлективность решетка

Определение 3 Отношение эквивалентности () на множестве - это бинарное отношение, для которого выполнены следующие условия:

·Рефлексивность <https://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D1%84%D0%BB%D0%B5%D0%BA%D1%81%D0%B8%D0%B2%D0%BD%D0%BE%D0%B5_%D0%BE%D1%82%D0%BD%D0%BE%D1%88%D0%B5%D0%BD%D0%B8%D0%B5>: для любого в ,

·Симметричность <https://ru.wikipedia.org/wiki/%D0%A1%D0%B8%D0%BC%D0%BC%D0%B5%D1%82%D1%80%D0%B8%D1%87%D0%BD%D0%BE%D0%B5_%D0%BE%D1%82%D0%BD%D0%BE%D1%88%D0%B5%D0%BD%D0%B8%D0%B5>: если , то ,

·Транзитивность <https://ru.wikipedia.org/wiki/%D0%A2%D1%80%D0%B0%D0%BD%D0%B7%D0%B8%D1%82%D0%B8%D0%B2%D0%BD%D0%BE%D1%81%D1%82%D1%8C>: если и , то .

Запись вида «» читается как « эквивалентно ».

.1 Рефлективность

Определение 4 Рефлексивное отношение - бинарное отношение на множестве , при котором всякий элемент этого множества находится в отношении с самим собой.

Примеры рефлексивности:

·отношения эквивалентности:

oотношение равенства

oотношение сравнимости по модулю

·отношения нестрогого порядка:

oотношение нестрогого неравенства

oотношение нестрогого подмножества

oотношение делимости

.2 Симметричность

Определение 5 Бинарное отношение на множестве X называется симметричным, если для каждой пары элементов множества выполнение отношения влечёт выполнение отношения .

Примерами симметричных отношений служат отношения типа равенства (тождества, эквивалентности, подобия)

.3 Транзитивность

Определение 6 Бинарное отношение на множестве называется транзитивным, если для любых трёх элементов множества выполнение отношений и влечёт выполнение отношения . Формально, отношение транзитивно, если .

Пример 1. Равенство а = b и b = c, следует, что a = c.

Пример 2. Отношение порядка , если a b и b c, то a c.

Как видно из примеров можно привести много примеров по свойству транзитивности. К таковым относятся операции импликации, эквивалентности, делимости и т.д.

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

Определение 7 Бинарное отношение на множестве называется отношением нестрогого частичного порядка (отношением порядка, отношением рефлексивного порядка), если имеют место

·Рефлексивность <https://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D1%84%D0%BB%D0%B5%D0%BA%D1%81%D0%B8%D0%B2%D0%BD%D0%BE%D1%81%D1%82%D1%8C>:

·Антисимметричность <https://ru.wikipedia.org/wiki/%D0%90%D0%BD%D1%82%D0%B8%D1%81%D0%B8%D0%BC%D0%BC%D0%B5%D1%82%D1%80%D0%B8%D1%87%D0%BD%D0%BE%D0%B5_%D0%BE%D1%82%D0%BD%D0%BE%D1%88%D0%B5%D0%BD%D0%B8%D0%B5>: .

·Транзитивность <https://ru.wikipedia.org/wiki/%D0%A2%D1%80%D0%B0%D0%BD%D0%B7%D0%B8%D1%82%D0%B8%D0%B2%D0%BD%D0%BE%D1%81%D1%82%D1%8C>: ;

Определение 8 Отношение порядка R на множестве А называется нестрогим, если оно рефлексивно на А.

Определение 9 Отношение порядка R строгим (на A), если оно антирефлексивно. Однако из антирефлексивности транзитивного отношения R следует его антисимметричность, следовательно можно дать более точное определения для строгого отношения.

Определение 9.1 Бинарное отношение R на множество A называется строгим порядком на А, если оно транзитивно и антирефлексивно на А.

Пример 1. Пусть P(M) -множество всех подмножеств множества М. Отношение включения на множестве P(M) есть отношение нестрого порядка.

Пример 2. Отношения ≤ и на множестве действительных чисел являются соответственно отношением строгого и нестрогого порядка.

Пример 3. Отношение делимости во множестве натуральных числе есть отношение нестрого порядка.

Множество , на котором введено отношение частичного порядка, называется частично упорядоченным <https://ru.wikipedia.org/wiki/%D0%A7%D0%B0%D1%81%D1%82%D0%B8%D1%87%D0%BD%D0%BE_%D1%83%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BE%D1%87%D0%B5%D0%BD%D0%BD%D0%BE%D0%B5_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%BE>. Отношение нестрогого частичного порядка часто обозначают знаком .

. Частично-упорядоченные множества

.1 Частично-упорядоченное множество

Определение 10: Частично упорядоченное множество, в котором для любых элементов a и b существую inf{a,b} и sup{a,b}, называют решеточно упорядоченным множеством.

Введем операцию +, операцией + на частично упорядоченным множеством будем считать что a∪b = a + b =sup{a,b}. Так же введем операцию * и будем считать, что a⋂b = a*b = inf{a,b}. (рис.1) тогда из определения решетки как ч.у.м мы перейдем к определению решетки как алгебраической структуры с введенной на ней бинарными операциями + и *

.2 Алгебраические решетки, свойства

Определение 11: Алгебраическая решетка - это тройка L = [ L, +, *], где L- непустое множество, а + (объединение), * (пересечение) - бинарные операции на нем, подчиняющимися парами законов коммутативности, ассоциативности, идемпотентности и поглощения.

Из определений частично упорядоченного множества и алгебраической решетки следует, что:

a + b = sup{a, b}, так же a * b = inf{a,b}.

Пусть x, y, z элементы и множества L, тогда:

1.x + x = x; x * x = x;

.x + y = y + x; x * y = y * x;

.x + (y + z) = (x + y) + z; x * (y * z) = (x * y) * z;

.x * (x + y) = x x + (x * y) = x;

Теорема 1. Пусть L - множество с операциями +, *, обладающими свойствами (1 - 4). Тогда отношение

a ≤ b = a + b = b;

является порядком на L, а возникающее частично упорядоченное множество оказывается структурой(решеткой), при чем:

a + b = sup {a, b};*b = inf {a, b};

Доказательство: Рефлективность отношения ≤ вытекает из свойства (1). Если a ≤ b, и b ≤ a, т.е a + b = b и b + a = a, то в силу (3) a = b, т.е отношение ≤ является антисимметричным. Если a + b = b и b + c = c, то применяя (3) получим:

a + c = a + (b + c) = (a + b) + c = b + c = c,

что доказывает транзитивность отношения ≤. Учитывая свойства (1), (2), (3) мы получаем

a + (a + b) = (a + a) + b = a + b,+ (a + b) = b + (b + a) = b + a = a + b,

Следовательно, a ≤ a + b и b ≤ a + b. Если a ≤ x, b ≤ x, то используя (1) - (3) будем иметь

(a + b) + x = a + (b + x) = a + x = x, т.е a + b ≤ x, из определения точной верхней грани получаем что

a + b = sup{ a, b}.

Аналогично можно доказать, что a*b = inf{a, b}, (далее будем отмечать ab = a*b)

Доказательство: Из свойств (1) - (3) вытекает, что ab ≤ a и ab ≤ b. Если y ≤ a и y ≤ b то с помощью (3) - (4) получаем:

y(ab) = [y ( y + b)]b = yb = y(y + b) = y.

В силу свойств (1) и (3) получаем, что y + ab = y(ab) + ab = ab,

т.е y ≤ ab. Таким образом,

ab = inf{a, b}.

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

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

Теорема 2. Если a ≤ b и c ≤ d, то a + b ≤ c + d и ab ≤ cd;

Доказательство: В силу эквивалентности свойств Ia ≤ b; a + b = b; ab = a; из условия следует, что a + c = c, b + d = d; ac = a; bd = d;

Поэтому :

(a + b) + (c + d) = (a + c) + (b + d) = c + d;

(ab)(cd) = (ac)(bd) = ab; откуда и вытекают требуемые неравенства.

Пример 1. Пусть {a, b, c} элементы из множества L, при чем, a ≤ b ≤ c. Данный набор элементов будет являться решеткой, так как для всех этих элементов есть наибольшее и наименьше значение, являющееся еще и inf и sup, проверим это, для a и b найдем inf, т. к inf{a,b} = ab, a ≤ b, то inf {a,b} = a. Для b и c. inf{b,c} = bc, b ≤ c, inf{b,c} = b. используем свойство транзитивности и получим, что inf{a,c} = a. Из наименьших элементов, элемент a наименьший. Аналогично проведем проверку по свойству +, получим, что sup{a,b} = b, sup{b,c} = c; опять же по свойству транзитивности получим sup{a,c} = c; Так как множество состоящее из трех элементов является частично упорядоченным и имеет верхнюю и нижнюю грани, то множество L является решеткой.

Примечание: обычно в алгебре наименьший элемент обозначается 0. А наибольший 1. Далее в примерах можно будет это увидеть.

Пример 2 Пусть S(A) множество всех подмножеств множества A. при чем |A| = n, тогда S(A)-решетка. И n - размерность куба.

Допустим, что множество A состоит из 3 элементов {a,b,c} так же оно имеет пустое множество . Перечислим все подмножества А. {a,b} , {a,c} , {b,c},

{a} , {b} , {c}. Так как n = 3, то получим 3 х мерный куб, элементы которого будут находится на разных уровнях.

Графическое представление:

. А

.{a,b} .{a,c} .{b,c}

.{a} .{b} . {c}

. (рис 1)

Как видно на (рис 1) довольно понятно показано что из себя представляет "множество всех подмножеств множества". На рисунке видно что элемент {a}

не является подмножеством {b,c}, соответственно b не подмножество {a,c} и т.д.

Перейдем к определению дистрибутивной решетки

.2 Дистрибутивная решетка, определение

Определение 12. Дистрибутивная решётка - решетка, в которой справедливо тождество:


равносильное тождествам

и соответственно


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

Дистрибутивной решеткой является :

.

a. b.

0.

Как видно на (рис 2) решетка состоит из элементов 1, a, b, 0 проверим, является ли решетка дистрибутивной, a + b = 1; ab = 0, по определению решетка является дистрибутивной.

Приведем пример недестрибутивной решетки.

1.

a. b. c.

0.

Проверяем свойство дистрибутивности из определения12 . Имеем:

(a+ b)c = ac + bc. Проверяем левую часть равенства. (a+b)c , т.к a + b = 1;

следовательно 1 * c = c. Итак, в левой части равенства получен результат с, следовательно в правой мы должны получить аналогичный результат, проверяем правую часть ac + bc, итак, как видим из (рис 3) ac = 0; аналогично для bc = 0. Получаем, с учетом левой части выражение вида с ≠ 0. Свойства дистрибутивной решетки не выполняется, следовательно решетка недестрибутивная.

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

Заключение

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

Список используемой литературы

. Розен В. В. Цель - оптимальность - решение (математические модели принятия оптимальных решений). - М.: Радио и связь, 1982.

. Столяр А. А., Рогановский Н. М. Основы современной школьной математики. Ч. 1. Язык. Множества. Отношения. Функции. Математические структуры. - Минск: Нар. Асвета, 1975.

. Мальцев А. И. Алгебраические системы. М.: Наука, 1970.

Похожие работы

 

Не нашел материала для курсовой или диплома?
Пишем качественные работы
Без плагиата!