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.


 

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

34307. Понятие о системах технологических процессов 24 KB
  Понятие о системах технологических процессов. Система это целое составленное из отдельных частей ке находятся в тесном отношении между собой . Технологическая система это совокупность взаимосвязанных предметов производства исполнителей и направлено на выполнение отдельных операций и процессов в целом. Между операцией в технологическом процессе и системах можно считать условленным так как они имеют опред.
34308. Исторические этапы развития систем технологий 27.5 KB
  В своем развитии системы технологических процессов прошли ряд исторических этапов. Однако сознательная организация системы технологических процессов произошла в средневековье. Впервые организованная система технологических процессов проявила себя в цехах ремесленников. По структуре цехи ремесленников представляли собой систему параллельных технологических процессов.
34309. Классификационные признаки систем технологий 23 KB
  Важнейшим признаком характеризующим технологические системы является их структура. Механизированная отличается использованием различных механизмов для осуществления как рабочих так и вспомогательных процессов в элементах системы участок станков машиностроительного предприятия. Жесткая связь подсистем характеризуются немедленным прекращением функционирования технологической системы в целом при отказе хотя бы одной подсистемы. При нежесткой связи между элементами системы возможно непродолжительное функционирование системы в случае...
34310. Структура технологической системы производства 25.5 KB
  Структура технологической системы производства. Свойства элементарных технологических процессов распространяются и на технологические системы более высокого иерархического уровня которые образованы совокупностями технологических процессов. Таким образом технологическую систему производства образуют параллельные последовательные и комбинированные системы технологических процессов. Еще одним важным фактором в формировании технологических систем являются технологические связи между элементами системы а также их характер.
34311. Взаимосвязь технологических и организационных структур производства 26 KB
  Взаимосвязь технологических и организационных структур производства. Характер формирования систем технологических процессов а также связей между ними имеет определяющее значение для формирования управляющих воздействий. Поэтому можно четко проследить взаимосвязь технологических и организационных структур производства. Например ремесленный цех с его ярко выраженной параллельной системой технологических процессов на определенном этапе исторического развития видоизменился в мануфактуру с последовательными технологическими процессами.
34312. Специфика развития параллельных и последовательных технологических систем 26 KB
  Перевод слабых составляющих системы на более высокую ступень позволит улучшить характеристики системы так как в ней ликвидируются звенья которые обуславливали в наибольшей степени неудовлетворительное функционирование системы. Таким образом ориентация на два различных типа развития позволит ставить задачу определения предпочтительности одного из них применительно к составляющим элементам параллельной системы. Такое целенаправленное развитие дает больший эффект чем при одновременном развитии всех составляющих изза различной готовности...
34313. Основные закономерности и направления развития систем технологических процессов 23.5 KB
  При этом важной особенностью развития технологических систем является их тип параллельной или последовательной связи элементов системы. Технологические системы в общем случае развиваются как и технологические процессы эволюционным и революционным путем. Однако системы технологических процессов неоднородны по восприятию рационалистического и эвристического развития. Как и в случае развития технологических процессов необходимым и достаточным условием революционного развития является совершенствование рабочих процессов хотя бы в...
34314. Реальный и потенциальный уровень технологии системы 25.5 KB
  Реальный и потенциальный уровень технологии системы. Реальная технологическая система характеризуется не только величиной уровня технологии который соответствует конкретным пропорциям между производительностью и затратами прошлого труда то есть реальным уровнем технологии но и максимальным потенциальным уровнем технологии который может быть достигнут в данной технологической системе при неизменных уровнях технологии ее составляющих. Потенциальный уровень технологии является верхней границей достижение которой будет означать что...
34315. Природное сырье и его характеристика 24.5 KB
  Природное сырье и его характеристика Сырьем наз. По агрегатному состоянию сырье делится на твердое жидкое и газообразное. По составу сырье делят на органическое и неорганическое. По происхождению различают сырье минеральное растительное и животное.