90748

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

Курсовая

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

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

Русский

2015-06-10

72.02 KB

3 чел.

Содержание

Введение                                                                                                                            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.


 

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

23168. Літературний гурт Молода муза 89 KB
  То й не дивно гурток становила молодь вихідці із сіл та провінційних містечок Галичини вчорашні випусники університету або ті що його не закінчили канцеляристи вчителі гімназій чи €вільні художники€. І все ж таки його положення було краще ніж інших скажімо Яцківа чи Карманського. Нам зашивалися роти в його товаристві бо ми добре знали гостроту його язика та великі відомості з якими не один із нас не міг суперечити Говоріть що врешті відзивався Франко якому хотілося поговорити і забути...
23169. Місце і значення творчості В. Симоненка в українській літературі 24.5 KB
  Симоненка в українській літературі Поезія Василя Симоненка вийшла з глибин народного життя з мужності народу з його горя і героїчної боротьби. Симоненка. Симоненка досить широкий про що свідчить і поезія і художня проза. Симоненка в літературі про значення його поезії Олесь Гончар: Серед літераторів трапляються й такі без яких їхня доба могла б спокійно обійтись нічого істотного не втративши.
23170. Мотиви лiрики Василя Симоненка 30 KB
  Центральною в його творчостi слушно вважається патрiотична тема любовi до України її безталанного народу висловленої з недвозначною вiдвертiстю i в цьому пряме продовження шевченкiвських традицiй поєднана з iдеєю неповторностi людського я . Мiж цими датами напiвголодне довоєнне дитинство лихолiття й злиднi студентське братерство але й нашпигована пильними шукачами ворогiв народу атмосфера лiтературна студiя iменi Василя Чумака скорочено СIЧ творчi суперечки в гуртожитку далi активна участь у роботi Черкаського обласного...
23171. Нацiональний пафос поезiї Олега Ольжича 28 KB
  Звичка оцiнювати творчiсть поетiв за вiдповiднiстю тiй або iншiй iдеологiї зазвичай виправдана. До того ж подiбний пiдхiд нерiдко породжував флюгерiв вiд поезiї що завжди намагаються дотримуватись офiцiйного найзручнiшого курсу. Та все ж таки часом треба переступати через iдеологiчнi забобони й вiдокремлювати подумки поета вiд полiтика в однiй особi талант вiд переконань.
23172. Неокла́сики 34 KB
  На відміну від інших груп Неокласики не дбали про своє організаційне оформлення і не виступали з ідейноестетичними маніфестами. Те що неокласики прагнули впроваджувати в своїй творчості форми та методи грецького й римського мистецтва представникам влади здалось невизнанням радянської дійсності. Неокласики позиціонували себе як естетів і жорстко протиставляли себе народництву і романтизму. Неокласики належать до так званих письменників доби розстріляного відродження.
23173. Неоромантизм поезiї Олени Телiги 28.5 KB
  Але крiм бiльшої наближеностi до дiйсностi неоромантизм мав ще одну суттєву вiдмiннiсть вiд течiїпопередника: полiтичне зумовлення що розкидало естетично близьких митцiв по рiзних таборах революцiйної романтики що iдейно грунтувалася на своєрiдному месiанiзмi свiтової пролетарської революцiї та неоромантизму нацiональновизвольної боротьби що набув розквiту трохи пiзнiше: напередоднi й пiд час Другої свiтової вiйни. Телiгу до боротьби та залишилося в її творчостi назавжди. Скорiше це розмiрковування над ролями чоловiкiв i жiнок що...
23175. ОЛЕГ ОЛЬЖИЧ 34 KB
  Олег Ольжич народився 8 липня 1907 р. після заснування ОУН організації українських націоналістів Ольжич став одним з найактивніших її членів очолив культурний сектор організації а трохи пізніше став заступником голови проводу ОУН. у Львові вийшла збірка Ольжича Рінь.