90748

Разработка видов алгебраических решеток

Курсовая

Экономическая теория и математическое моделирование

Бинарные отношения, определения Примеры бинарных отношений Отношение эквивалентности Рефлективность, примеры рефлективности Симметричность Транзитивность Отношение порядка Частично-упорядоченные множества Основные определения, свойства ч.у.м. Решетки Дистрибутивность решетки Примеры дестрибутивных и недестребутивных решеток.

Русский

2015-06-10

72.02 KB

2 чел.

Содержание

Введение                                                                                                                            3

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

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

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

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

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

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

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

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

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

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

4.2. Решетки...............................................................................................8

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

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

Заключение                                                                                                                     14

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

Введение

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

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

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

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

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

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

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

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

1.1.1 Пусть 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), (22), (42)} на множестве X = {4, 3, 2} можно определить как свойство "Делится" на этом подмножестве целых чисел.

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

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

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

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

  1.  Рефлексивность: для любого в ,
  2.  Симметричность: если , то ,
  3.  Транзитивность: если и , то .

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

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

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

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

  1.  отношения эквивалентности:
  2.  отношение равенства
  3.  отношение сравнимости по модулю
  4.  отношения нестрогого порядка:
  5.  отношение нестрогого неравенства
  6.  отношение нестрогого подмножества
  7.  отношение делимости

2.2 Симметричность

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

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

2.3 Транзитивность

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

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

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

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

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

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

  1.  Рефлексивность:
  2.  Антисимметричность: .
  3.  Транзитивность: ;

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

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

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

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

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

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

Множество , на котором введено отношение частичного порядка, называется частично упорядоченным. Отношение нестрогого частичного порядка часто обозначают знаком .

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

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

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

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

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

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;
  2.  x  + y = y + x;                         x * y = y * x;
  3.  x + (y + z) = (x + y) + z;        x * (y * z) = (x * y) * z;
  4.  x * (x + y) = x                         x + (x * y) = x;

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

ab = a + b = b;

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

a +  b = sup {a, b};

a*b = inf {a, b};

Доказательство: Рефлективность отношения вытекает из свойства (1). Если ab, и ba, т.е 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,

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

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

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

a + b = sup{ a, b}.

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

Доказательство: Из свойств (1) - (3) вытекает, что aba и ab ≤  b. Если ya и yb то с помощью (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.  Если ab и 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, при чем, abc. Данный набор элементов будет являться  решеткой, так как для всех этих элементов есть наибольшее и наименьше значение, являющееся еще и inf и sup,

проверим это, для a и b найдем inf, т. к inf{a,b} = ab, ab, то inf {a,b} = a. Для b и c. inf{b,c} = bc, bc, 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} и т.д.

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

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

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

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

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

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

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

1.

a.     b.

0.

(рис 2.)

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

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

1.

a.   b.   c.

0.

(рис 3).

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

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

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

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

Заключение.

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

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

1.  Шрейдер Ю. А. Равенство, сходство, порядок. - М.: Наука, 1971.

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

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

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


 

А также другие работы, которые могут Вас заинтересовать

34396. Сущность и содержание прогнозирования. Роль и характер прогнозов 44.5 KB
  Прогнозирование это процесс разработки прогноза построенный на вероятностном научно обоснованном суждении о перспективах развития объекта в будущем его возможном состоянии и альтернативных путях его достижения. Социальноэкономическое прогнозирование является способом предвидения представления о будущем обусловленном закономерностями общественного развития и действием разнообразных и разнонаправленных факторов в прогнозируемом периоде. В соответствии с Законом О государственном прогнозировании и программах социальноэкономического...
34397. Сущность планирования. Директивное, индикативное, стратегическое планирование, их характеристика 47 KB
  При формировании рыночных отношений в Республике Беларусь необходимо видение перспектив ее экономического и социального развития. Планирование это процесс принятия управленческого решения основанный на обработке исходной информации и включающий в себя определение и научную постановку целей средств и путей их достижения посредством сравнительной оценки альтернативных вариантов и выбора наиболее приемлемого из них в ожидаемых условиях развития. Суть планирования состоит не в разработке и доведении многочисленных показателей до...
34398. Предмет курса, его место в системе экономических наук 27 KB
  Пип – наука изучающая экие теории и законы применительно к конкретным условиям производства их специфические проявления в важнейших процессах прва закономерностях темпов и пропорциях с тем чтобы в результате этого изучения с учетом достижений НТП передового опыта обосновать объемы темпы и пропорции общественного производства в целях наиболее эффективного развития экономики. Задача курса состоит в рассмотрении комплекса теоретических методологических организационных вопросов пип экономики на современном этапе. Теория пип является...
34399. Исторический аспект развития прогнозирования и планирования 26 KB
  Экономическая мысль совершая поиск путей становления системы планирования испытывала колебания вступала в противоборство допуская ошибки и избавляясь от них под влиянием реальных явлений хозяйственной жизни. Рассмотрим становление и совершенствование прогнозирования и планирования в бывшем СССР и развитых зарубежных странах. Первый долгосрочный план который представляет интерес с точки зрения общей методологии планирования это план ГОЭЛРО государственный план электрификации России разработанный в 1920 г.
34400. Развитие и особенности ПИП в зарубежных странах (США, Япония, Франция и др.) 45.5 KB
  Для США характерно стратегическое планирование суть которого состоит в выборе главных приоритетов развития национальной экономики ведущую роль в реализации которых играет государство. Основным источником займов на цели разработки и освоения новой технологии является Японский банк развития. Направления стратегического развития разрабатываются в виде целевых государственных программ и сопровождаются комплексом различных финансовых льгот и преференций стимулирующих их реализацию. Она представляет собой модель будущего развития экономики...
34401. Научные основы методологии прогнозирования и планирования 30.5 KB
  Вторая является основой планирования и прогнозирования в странах с рыночной экономикой. Методология прогнозирования и планирования развития экономики определяет основные принципы подходы и методы проведения прогнозных и плановых расчетов раскрывает и характеризует логику формирования прогнозов планов и их осуществления. Принципы это основополагающие правила прогнозирования и планирования т.
34402. Система показателей планов-прогнозов 30.5 KB
  Нормативы показатели в относительном выражении. Лимиты ресурсные показатели представляющие предельно допустимую величину затрат ресурса для достижения установленных конечных результатов. Основными блоками показателей прогнозирования и планирования экономических и социальных процессов являются: показатели производства трудовых ресурсов основных и оборотных фондов капитальных вложений природных ресурсов научнотехнического прогресса финансов и денежного обращения социального развития и уровня жизни населения внешнеэкономических...
34403. Система прогнозов и планов. Методологические основы их сопряжения 32 KB
  Для формирования стратегии и тактики развития экономики разрабатывается система прогнозов включающая прогнозы временного аспекта и по уровням управления а также частные и комплексные прогнозы экономического и социального развития страны и регионов. По масштабу прогнозирования выделяют: макроэкономические прогнозы межотраслевые и межрегиональные прогнозы развития народнохозяйственных комплексов отраслевые и региональные прогнозы прогнозы звеньев экономики: предприятий объединений отдельных производств и продуктов. Во временном аспекте...
34404. Объекты макроэкономического ПиП 26.5 KB
  Система прогнозных расчетов включает прогнозы макроэкономических показателей: валового национального продукта прогнозы показателей эффективности характеризующих качество экономического роста материалоемкости фондоотдачи производительности труда прогнозы структуры экономики. На макроуровне необходимо также осуществлять прогнозные расчеты экономического потенциала занятости спроса на продукцию разрабатывать прогнозы инвестиций экспорта и импорта платежного баланса цен валютного курса инфляции прогнозы государственных операций при...