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.


 

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

29384. Научно-методические принципы изучения литературных произведений в начальных классах 50.5 KB
  Принцип целенаправленности Этот принцип гласит: изучение произведения в том числе и его анализ должны быть целенаправленным. Изучение произведения в начальной школе всегда преследует две группы целей. 1 Коррекция субъективного первичного восприятия произведения объективным смыслом текста углубление восприятия прочитанного постижение художественной идеи и авторской позиции – полноценное восприятие художественного текста. 1 Основная цель каждого урока литературы – освоение художественной идеи произведения.
29385. Методика чтения и изучения эпических произведений. Модель урока литературного чтения по изучению рассказа (сказки) 35.5 KB
  Модель урока литературного чтения по изучению рассказа сказки Эпос – один из трёх родов литературы повествовательный род. Их захватывает острый занимательный сюжет сказок необычность обстановки в которой развертываются события; привлекают герои смелые сильные находчивые удалые люди; сказки подкупают своей идейной направленностью: добрые силы всегда побеждают. Сила воздействия образов и сюжета сказки такова что младшие школьники уже в процессе первого чтения ярко проявляют свои симпатии и антипатии к персонажам сказок всецело...
29386. Методика чтения и изучения лирических произведений. Модель урока литературного чтения по изучению стихотворения 42 KB
  Модель урока литературного чтения по изучению стихотворения. В книгах для чтения Родная речь представлены эпические и лирические стихотворения. Анализ эпического стихотворения направлен на выяснение сюжета раскрытие особенностей действующих лиц идеи произведения его художественного своеобразия. В эпических стихотворениях часто используется диалог что позволяет автору живо описать событие как бы включить самого читателя в круг описываемых событий.
29387. Современные концепции начального литературного образования 33 KB
  приоритетная задача курса углубление интереса к чтению и литературе осознанию учеником значения читательской деятельности как средства успешности обучения и развития человека формирование умений работать с произведениями разного жанра вида и стиля; расширение круга классических и современных произведений при литературном анализе которых особое внимание уделяется сравнению произведений разных авторов жанров и тематики а также моделирующей деятельности учащихся; частью курса является Литературное слушание идея которой – в...
29388. Пропедевтический этап в системе литературного образования школьников 49 KB
  Важнейшей особенностью предмета является формирование и развитие навыка чтения а также таких качественных характеристик чтения как сознательность и выразительность. Развитие навыка чтения предполагает на первом году обучения становление механизма чтения овладение слоговым и комбинированным способами чтения; на втором году обучения – интенсивное овладение способом чтения целыми словами наращивание темпа чтения освоение способа чтения молча; на третьем году обучения – становление способа чтения целыми словами в темпе соответствующем...
29389. Принципы построения учебных книг по литературному чтению: традиционное и инновационное. Детские книги как особый учебный материал для формирования читателя 23 KB
  Эту функцию выполняет учебник. Учебник рассматривает текст как информационное поле на котором состоится встреча автора и читателя. Типы книг для начальной школы: Обязательные: учебник хрестоматия учебникхрестоматия Факультативные: справочник энциклопедия словари рабочие тетради Принципы организации учебника: тематический по темам жанровый стихи рассказы сезонный Виды вопросов и заданий в учебниках: до текста и после текста репродуктивные на выявление первичного восприятия на анализ на синтез продуктивные...
29390. Урок литературного чтения и его особенности. Моделирование урока литературного чтения в логике одной из образовательных программ (на примере одного литературного произведения) 57 KB
  Урок литературного чтения и его особенности. Моделирование урока литературного чтения в логике одной из образовательных программ на примере одного литературного произведения Современный урок литературного чтения имеет свои особенности: Каждый урок рассматривается как часть более широкой системы литературное развитие школьника Урок – это этап в изучении литературного произведения Урок – это художественнопедагогическое целое содержание форма уока будет определяться жанром и особенностями произведения а так же художественным миром...
29391. Конструктивное исполнение электрооборудования в НГП 30 KB
  Конструктивное исполнение электрооборудования в НГП должно соответствовать условиям его эксплуатации. исполнение характеризуется тем что электродвигатели имеют специальные приспособления крышки кожухи сетки. Водозащищенное IP55 IP56 исполнение электродвигатели недоступны проникновению внутрь струй воды любого направления.
29392. Нерегулируемый ЭП буровых насосов 27.5 KB
  Двигатели брызгозащишенные с влагостойкой изоляцией с самовентиляцией; наверху корпуса двигателя смонтирован возбудитель связанный клиноременной передачей с валом двигателя. Номинальное напряжение двигателя 6 кВ частота вращения 750 об мин. Так как условия пуска двигателя бурового насоса сравнительно легкие момент статического сопротивления на валу двигателя составляет примерно 20 от номинального момента двигателя а время разгона составляет 34 сек в схеме предусмотрен прямой пуск двигателя с наглухо подключенным возбудителем. Для...