Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Инфоурок / Математика / Другие методич. материалы / Курсовая работа по дискретной математике

Курсовая работа по дискретной математике



Осталось всего 4 дня приёма заявок на
Международный конкурс "Мириады открытий"
(конкурс сразу по 24 предметам за один оргвзнос)


  • Математика

Поделитесь материалом с коллегами:

hello_html_m53d4ecad.gifВВЕДЕНИЕ

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

Бинарные отношения служат простым и удобным аппаратом для весьма широкого круга задач. Язык бинарных и n-арных отношений используется во многих прикладных (для математики) областях, например, таких как математическая лингвистика, математическая биология, математическая теория баз данных. Широкое использование языка бинарных отношений легко объясняется – геометрический аспект теории бинарных отношений есть попросту теория графов.

Таким образом, актуальность проблемы изучения бинарных отношений обусловила тему исследования: «Алгебра бинарных отношений и отображений».

Объект исследования: система бинарных отношений и отображений.

Предмет исследования: совокупность теоретических и практических основ алгебраических операций на множестве.

Цель работы: изучить методы исследования бинарных отношений и отображений.

В соответствии с объектом, предметом и целью исследования определены следующие задачи:

  • Охарактеризовать понятия бинарных отношений и отображений.

  • Изучить особенности алгебраических операций на множестве.

  • Исследовать наиболее важные типы бинарных отношений.

  • Показать особенности бинарных отношений и отображений на примере решения задач.

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

Методологической основой исследования послужили математические исследования, основанные на теоретико-множественной концепции строения любой математической теории. С этой точки зрения любая математическая теория имеет дело с одним или несколькими множествами объектов, связанных между собой некоторыми отношениями. Основоположником теории множеств и отношений между ними является немецкий математик Георг Кантор (1845—1918), который говорил: «Множество есть многое, мыслимое как единое». Благодаря дальнейшему развитию теории множеств в трудах Д. Гильберта и Г. Вейля стала возможной аксиоматизация и четкое разделение различных категорий множеств.

















ГЛАВА 1. Элементы теории множеств

    1. Теория множеств

Теория множеств - раздел математики, изучающий точными средствами содержание одной из важнейших категорий философии, логики и математики — категории бесконечного (Бесконечное и конечное). Основана Г. Кантором (1845—1918). Предметом теории множеств являются свойства множеств (совокупностей, классов, ансамблей), главным образом бесконечных. Фундаментальным положением теории множеств служит установление различных “порядков” бесконечности. Классическая теория множеств исходит из признания применимости к бесконечным множествам принципов логики, бесспорных в области конечного. Однако развитие теории множеств уже в конце 19 в. выявило трудности, в т. ч. парадоксы, связанные с применением законов формальной логики, в частности исключенного третьего закона, к бесконечным множествам. В полемике, возникшей в связи с этим, были поставлены важнейшие гносеологические вопросы математического познания: о природе математических понятий, об их отношении к реальному миру, о конкретном содержании понятия существования в математике и т.д. В ходе полемики появились такие течения в философии математики, как формализм, интуиционизм, логицизм. Особо следует отметить конструктивное направление в советской математике. Методы теории множеств широко используются во всех областях современной математики; они имеют принципиальное значение для вопросов обоснования математики, в частности для современной формы аксиоматического метода. Все вопросы обоснования математики логическими средствами сводятся к вопросам обоснования теории множеств. Однако при обосновании самой теории возникают трудности, не преодоленные и в настоящее время.

Множество A есть любое собрание определенных и различимых между собой объектов, мыслимое как единое целое. Эти объекты называются элементами или членами множества A. Если элемент х принадлежит множеству A, то это обозначается так: хх А; если же х не есть элемент A, то это обозначается так: ххА. Если каждый элемент множества A принадлежит множеству В, то это записывается так: А т В. Множество A называется в этом случае подмножеством множества В, а отношение “а” – отношением включения множеств. Множество, не содержащее ни одного элемента, называется пустым и обозначается символом 0. В приложениях теории множеств часто рассматривают подмножества некоторого фиксированного множества, которое называют универсальным множеством и обозначают символом U. Важнейшими принципами теории множеств являются принцип экстенсиональности и принцип свертывания (абстракции). Согласно принципу экстенсиональности, два множества A и В равны только в том случае, если они состоят из одних и тех же элементов. Согласно принципу свертывания, любое свойство Р определяет некоторое множество А, элементами которого являются объекты, обладающие свойством Р. Объединение множеств A и В обозначается через AAB. Объединение A и В есть множество всех предметов, которые являются элементами множества А или множества В, т. е. х принадлежит объединению А А В, если х принадлежит хотя бы одному из множеств А и В. Пересечение множеств A и В обозначается через AAB. Пересечение A и В есть множество всех предметов, являющихся элементами обоих множеств A и В, т. е. х принадлежит пересечению AAB, если х принадлежит как множеству A, так и В. Разность множеств А – В есть множество элементов A, не принадлежащих В. Дополнением множества A (обозначается A&) называется множество элементов универсального множества U, не принадлежащих A, т. е. U – А. Для любых подмножеств A, В и С универсального множества U справедливы следующие важные равенства: Некоторые из перечисленных равенств имеют специальные названия: 7 и 7& – законы идемпотентности, 9 и 9& – законы поглощения, 10 и 10& – законы де Моргана. Классическая теория множеств исходит из признания применимости к бесконечным множествам принципов логики. В развитии теории множеств в начале XX в. выявились трудности, связанные с обнаружением парадоксов – противоречий, к которым приводит применение законов формальной логики к бесконечным множествам. Дальнейшая разработка теории множеств была связана с уточнением понятия множества и устранением парадоксов.
























1.2. Понятие алгебраической операции на множестве

Предметом рассмотрения в абстрактной алгебре являются произвольные множества с заданными на них операциями. При этом природа множеств и операций может существенно отличаться от привычных числовых множеств и известных операций над числами. Мы уже сталкивались с операциями над множествами и бинарными отношениями, которые оказались в чем-то похожими на операции над числами, но в то же время проявились и их существенные отличия.[5]

В дискретной математике разрабатываются алгоритмы и вычислительные методы, позволяющие манипулировать сложно организованными нечисловыми структурами. Проблема работы с такими объектами возникла в связи с развитием современных информационных технологий и переходом от собственно вычислений (т.е. операций над числами) к обработке сложных структур данных. Так, проблемы программирования и машинного перевода привели к задачам работы с языковыми структурами, проблемы автоматизации проектирования — к задачам обработки графических объектов.

Современная дискретная математика проникнута алгебраическим духом, поскольку оказалось, что именно на алгебраической базе наиболее удобно разрабатывать общие подходы к работе с объектами различной природы.

Множество векторов в пространстве с операцией сложения векторов, операцией векторного умножения, множество квадратных матриц с операциями сложения или умножения, множество функций с операцией сложения — вот примеры некоторых множеств с операциями, рассматривающихся в различных разделах математики. Выясним, что общего есть в свойствах операций на этих множествах и в чем их различие.

Определение 2.1. Пусть hello_html_2d470d3c.png — произвольное непустое множество и hello_html_1886054d.png — натуральное число. Любое отображение hello_html_2ac482c3.pngназывают n-арной (или n-местной) операцией на множестве hello_html_2d470d3c.png.

Таким образом, согласно приведенному определению, n-арная операция и каждому кортежу hello_html_md3409c0.png однозначно сопоставляет элемент hello_html_m3037bdcd.png. Компоненты кортежа называют при этом аргументами операции hello_html_14d3e921.png, а hello_html_m7d1316c8.png — результатом применения операции и к аргументам hello_html_4e607b86.png.

Для n-арной операции используют обозначение

hello_html_2d732865.png или hello_html_m373dd8e9.png.

Обычно, если hello_html_8e597a3.png, пишут hello_html_m7a491e3a.png. При hello_html_36876b82.png и hello_html_8e597a3.png говорят соответственно об унарной операции и бинарной операции.

Специально вводят понятие нульарной операции (т.е. для hello_html_m66753a41.png). Под нульарной операцией на множестве hello_html_2d470d3c.png понимают произвольный фиксированный элемент множества hello_html_2d470d3c.png. Нульарные операции позволяют фиксировать элементы множества hello_html_2d470d3c.png, обладающие некоторыми специальными свойствами. Примером выполнения нульарной операции является, например, фиксирование нуля в множестве целых чисел с операцией сложения. Примером унарной операции служит дополнение заданного множества до универсального множества.

Наиболее важными в алгебре и, следовательно, наиболее исследованными являются бинарные операции. Примерами таких операций могут служить сложение и умножение чисел, сложение и умножение матриц, сложение векторов линейного пространства.

Рассмотрим бинарную операцию на множестве hello_html_2d470d3c.png, обозначив ее звездочкой hello_html_me062551.png. Эту операцию называют:

1) ассоциативной, если hello_html_m56f34c93.png для любых hello_html_5ebd268b.png;
2) коммутативной, если
 hello_html_a605fb0.png для любых hello_html_m448b7d17.png;
3) идемпотентной, если
 hello_html_m60ff7c4a.png для любого hello_html_48ddc9e8.png.

Ассоциативность операции hello_html_m7b1fc02f.png позволяет для любых элементов hello_html_7cca30a8.png однозначно трактовать результат выражения hello_html_m309d6457.png.

Операция сложения, заданная на множестве натуральных чисел, является ассоциативной и коммутативной. Операция умножения матриц ассоциативна, но не коммутативна. Идемпотентными являются операции объединения и пересечения множеств.[8]

Элемент hello_html_4d37fd72.png множества hello_html_2d470d3c.png называют левым (правым) нулем относительно данной операции hello_html_m7b1fc02f.png, если hello_html_3b30e0b9.png hello_html_m420830f9.png для любого hello_html_48ddc9e8.png.

Если hello_html_3e865417.png — левый нуль, а hello_html_3039bd68.png — правый нуль, то они совпадают. Действительно, если hello_html_3e865417.png и hello_html_3039bd68.png существуют, то они совпадают, так как hello_html_273312b4.png, и в этом случае говорят просто о нуле относительно операции. Из приведенных равенств следует, что нуль единственный и для него одновременно выполнены оба равенства hello_html_3b30e0b9.png и hello_html_7c765f24.png.

Пример 2.1. 

а. На множестве целых чисел hello_html_m4d4e92f9.png нулем относительно операции умножения будет число 0.

б. На множестве квадратных матриц вида hello_html_mc83e9e7.png, где элементы hello_html_m1e92ddf9.png и hello_html_m7d1316c8.png — действительные числа, любая матрица вида hello_html_52cf38b8.png будет правым нулем относительно операции умножения.

Однако левого нуля в этом множестве нет, так как иначе он совпадал бы с правым нулем и был бы единственным. Но правых нулей имеется больше одного.

Нейтральные элементы относительно операции

Элемент hello_html_m1d112bc2.png множества hello_html_2d470d3c.png называют левым (правым) нейтральным элементом относительно операции hello_html_m7b1fc02f.png, если hello_html_m2e7081a2.png hello_html_m1cdef6f7.png для любого элемента hello_html_48ddc9e8.png. Для левого hello_html_m16607526.png; и правого hello_html_m36b3ef52.png нейтральных элементов, если они оба существуют, выполнены равенства hello_html_23e8021f.png, согласно которым они совпадают. В этом случае элемент hello_html_m1d112bc2.png, который является и левым нейтральным, и правым нейтральным, единственный, и его называют просто нейтральным элементом.

Пример 2.2. Нейтральным элементом относительно операции умножения на множестве натуральных чисел является число 1. На множестве целых чисел нейтральным элементом относительно операции сложения будет число 0.

На множестве квадратных матриц вида hello_html_m5860b33c.png, где элементы hello_html_m1e92ddf9.png и hello_html_m7d1316c8.png — действительные числа, любая матрица вида hello_html_164841f7.png будет правым нейтральным элементом по операции умножения.

Поскольку правых нейтральных элементов несколько, то левого нейтрального элемента по этой операции нет, так как иначе существовал бы единственный нейтральный элемент (левый и правый).

Следует заметить, что не для всякой бинарной операции нули и нейтральные элементы (левые и правые, в частности), существуют. [4]

Рассмотрим некоторые примеры бинарных операций на множествах.

Пример 2.3. а. Пусть hello_html_aea161f.png — универсальное множество. Теоретико-множественные операции hello_html_m25c33583.png на множестве hello_html_5baf3465.png являются идемпотентными, ассоциативными и коммутативными, причем пустое множество является нулем относительно пересечения и нейтральным элементом относительно объединения hello_html_m63629425.pngтогда как универсальное множество есть нуль относительно объединения и нейтральный элемент относительно пересечения hello_html_2f46029f.png

Операция hello_html_m568c4d41.png (разность множеств) не является ассоциативной, так как hello_html_643c2ec7.png.

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

в. Пусть hello_html_m7f725043.png — произвольное множество, содержащее не менее двух элементов. На множестве всех отображений из hello_html_m7f725043.png в hello_html_m7f725043.png с операцией композиции отображений постоянное отображение hello_html_2a5df01c.png, переводящее любой элемент hello_html_m19c74de0.png в фиксированный элемент hello_html_63c20cc7.png, будет правым нулем, но не будет нулем относительно композиции отображений.

Действительно, для любого отображения hello_html_m43fef743.png и любого hello_html_m19c74de0.png имеем

hello_html_m4be7512e.png, то есть hello_html_2c14f21.png,

что и означает, что hello_html_2a5df01c.png — правый нуль относительно операции композиции на множестве отображений из hello_html_m7f725043.png в hello_html_m7f725043.png. Однако для любого hello_html_m19c74de0.pngимеем

hello_html_m68043e68.pngто есть hello_html_m2c0bf1b9.png — отображение, которое любой элемент hello_html_2d470d3c.png переводит в элемент hello_html_m14c4f11e.png. Поскольку hello_html_m14c4f11e.png в общем случае не равно hello_html_m1e92ddf9.png, то hello_html_m45246f3f.png. Значит, hello_html_2a5df01c.png не является левым нулем относительно операции композиции.

Рассмотренные выше примеры множеств с операциями приводят к следующим определениям.

Определение 2.2. Алгебра (универсальная алгебра, Ω-алгебра) считается заданной, если заданы некоторое множество hello_html_2d470d3c.png, называемое носителем данной алгебры, и некоторое множество операций hello_html_m124c90bf.png на hello_html_2d470d3c.png, называемое сигнатурой данной алгебры. Алгебру, носитель которой есть конечное множество, называют конечной алгеброй.[2]

Поскольку алгебра задается ее носителем и сигнатурой, мы будем в записи обозначать алгебру как упорядоченную пару множеств hello_html_m69cf5b21.png, полагая, что первая компонента этой пары есть носитель, а вторая — сигнатура. Подчеркнем, что алгебра — это не просто носитель и не просто сигнатура, а „синтез" этих двух объектов.

Замечание 2.1. Операции, включенные в сигнатуру, заданы как некоторые специальные отображения. Однако при этом не оговариваются свойства, которыми обладают операг ции на носителе. Например, они могут быть ассоциативными, коммутативными и т.д. При задании алгебр свойства операций обычно указывают дополнительно.

Если существует нейтральный элемент относительно операции, то его можно задать как нульарную операцию на носителе и включить в сигнатуру, а можно не включать и описать как свойство соответствующей операции.

Таким образом, одну и ту же алгебру можно задавать по-разному. Ниже приведены примеры различных описаний конкретных алгебр.

В ряде случаев указание носителя алгебры предполагает и задание определенной сигнатуры. В этом случае для упрощения пишут не hello_html_m69cf5b21.png, а просто hello_html_73774348.png и говорят "элемент алгебры hello_html_m14fbb08.png", имея в виду элемент носителя этой алгебры.

Пример 2.4. а. Рассмотрим алгебру

Ее носителем является множество всех подмножеств произвольно фиксированного множества hello_html_m12aefff9.png, а сигнатура состоит из следующих операций над множествами: объединения, пересечения, разности, симметрической разности, дополнения, пустого множества и множества hello_html_m12aefff9.png (последние два элемента сигнатуры определяют нульарные операции).

б. Для любого множества hello_html_m12aefff9.png можно определить алгебру

hello_html_m7542d339.png
носителем которой является множество всех подмножеств множества упорядоченных пар на hello_html_m12aefff9.png, т.е. множество всех бинарных отношений на множестве hello_html_m12aefff9.png, а сигнатура состоит из операций объединения, композиции бинарных отношений и взятия обратного отношения.[7]

в. На множестве hello_html_38c4e623.png действительных чисел можно, например, определить такую алгебру:

hello_html_4bff49a.png сигнатура которой состоит из операций сложения, умножения, а также двух нульарных операций, обозначающих два особых числа 0 и 1. Обратим внимание на то, что числа 0 и 1 в данном случае являются соответственно нулем и нейтральным элементом относительно умножения, а число 0 также играет роль нейтрального элемента относительно сложения.  Все предыдущие примеры алгебр были алгебрами с конечной сигнатурой, т.е. с сигнатурой, состоящей из конечного числа операций. Однако несложно построить пример алгебры с бесконечной сигнатурой. Например, алгебра hello_html_m5cc2ab3d.png

на множестве действительных чисел hello_html_38c4e623.png с операцией hello_html_m202f9d5c.png возведения в натуральную степень hello_html_m16402acb.png имеет счетную сигнатуру. Далее будут приведены примеры алгебр и с нечетными сигнатурами.

Определяя алгебру, следует помнить, что результат применения любой операции обязательно должен принадлежать тому же множеству, что и ее аргументы. Например, пару из множества hello_html_m27d25562.png всех свободных векторов в пространстве и операции скалярного умножения векторов нельзя рассматривать как алгебру, так как скалярное произведение двух векторов не есть вектор. Заменив скалярное умножение векторным, получим алгебру.

Кроме того, нельзя забывать, что n-арная операция, как и всякое отображение, должна быть определена для любого кортежа длины n элементов множества. Поэтому не является алгеброй множество всех матриц с операциями сложения и умножения матриц, так как эти операции определены не для любой упорядоченной пары матриц. Если же при тех же операциях ограничиться множеством квадратных матриц фиксированного порядка hello_html_1886054d.png, то получим алгебру.[1, 3]

Точно так же множество действительных чисел hello_html_38c4e623.png с операцией hello_html_m63a16da9.png деления действительных чисел не является алгеброй, поскольку результат деления не определен при нулевом делителе. Пара же hello_html_m566a8ab7.png есть алгебра.

Договоримся, определяя конкретную алгебру, записывать ее сигнатуру без фигурных скобок, перечисляя после обозначения носителя все операции. Так, в примере 2.4.а первая алгебра может быть записана как

Для алгебры hello_html_m69cf5b21.png обозначим через hello_html_3d09a4ed.png подмножество сигнатуры hello_html_m124c90bf.png, состоящее из всех n-арных операций. Тогда hello_html_449b421d.png. Так, для алгебры hello_html_762bfe7d.png в примере 2.4.а будем иметь: при hello_html_2311001.png.


ГЛАВА 2. Отношения на множествах

2.1. Бинарные отношения (отношения степени 2)

В математике большую роль играют бинарные отношения, т.е. отношения, заданные на декартовом произведении двух множеств hello_html_75fa3d90.png.

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

Определение 8. Отношение hello_html_m4f34938e.pngна множестве hello_html_m2a90300f.pngназывается отношением эквивалентности, если оно обладает следующими свойствами:

hello_html_m53cd914b.pngдля всех hello_html_a17f716.png (рефлексивность)

Если hello_html_m7a018574.png, то hello_html_m7641bb5a.png (симметричность)

Если hello_html_m7a018574.pngи hello_html_775ce36e.png, то hello_html_b9f45ef.png (транзитивность)

Обычно отношение эквивалентности обозначают знаком hello_html_m6eb804ab.pngили hello_html_5ab04b12.pngи говорят, что оно (отношение) задано на множестве hello_html_73bad42b.png (а не на hello_html_m2a90300f.png). Условия 1-3 в таких обозначениях выглядят более естественно:

hello_html_m9d0099f.pngдля всех hello_html_a17f716.png (рефлексивность)

Если hello_html_2c828062.png, то hello_html_m4dae616e.png (симметричность)

Если hello_html_2c828062.pngи hello_html_63ccb28c.png, то hello_html_95b74c.png (транзитивность)

Легко доказывается, что если на множестве hello_html_73bad42b.pngзадано отношение эквивалентности, то множество hello_html_73bad42b.pngразбивается на взаимно непересекающиеся подмножества, состоящие из эквивалентных друг другу элементов (классы эквивалентности).

Пример 1. Рассмотрим на множестве вещественных чисел hello_html_257ccf8d.pngотношение, заданное просто равенством чисел. Предикат такого отношения:

hello_html_m8465c3b.png, или просто hello_html_m5a61b7b5.gif

Условия 1-3, очевидно, выполняются, поэтому данное отношение является отношением эквивалентности. Каждый класс эквивалентности этого отношения состоит из одного числа.[6]

Пример 2. Рассмотрим более сложное отношение эквивалентности. На множестве целых чисел hello_html_m71c579d4.pngзададим отношение "равенство по модулю n" следующим образом: два числа hello_html_73568079.pngи hello_html_m588bb435.pngравны по модулю n, если их остатки при делении на n равны. Например, по модулю 5 равны числа 2, 7, 12 и т.д.

Условия 1-3 легко проверяются, поэтому равенство по модулю является отношением эквивалентности. Предикат этого отношения имеет вид:


hello_html_m1629b792.png


Классы эквивалентности этого отношения состоят из чисел, дающих при делении на n одинаковые остатки. Таких классов ровно n:

[0] = {0, n, 2n, …}

[1] = {1, n+1, 2n+1, …}

[n-1] = {n-1, n+n-1, 2n+n-1, …}

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

Определение 9. Отношение hello_html_m4f34938e.pngна множестве hello_html_m2a90300f.pngназывается отношением порядка, если оно обладает следующими свойствами:

hello_html_6fbc43c0.gifдля всех hello_html_m1ff8df2a.gif (рефлексивность)

Если hello_html_6fbc43c0.gif и hello_html_69b73e3b.gif, то hello_html_m5a61b7b5.gif (антисимметричность)

Если и hello_html_m5340c6ed.gif, то hello_html_m6fb75c00.gif (транзитивность)

Обычно отношение порядка обозначают знаком hello_html_m78774d40.gif. Если для двух элементов hello_html_m5547f17b.gif и hello_html_m11fb3721.gifвыполняется hello_html_m56666f63.gif, то говорят, что hello_html_m5547f17b.gif "предшествует" hello_html_m11fb3721.gif. Как и для отношения эквивалентности, условия 1-3 в таких обозначениях выглядят более естественно:

hello_html_m1ceb3b52.gifдля всех hello_html_m1ff8df2a.gif (рефлексивность)

Если hello_html_m56666f63.gifи hello_html_61949f0c.gif, то hello_html_2f27c206.gif (антисимметричность)

Если hello_html_m56666f63.gifи hello_html_686a5951.gif, то hello_html_2574153b.gif (транзитивность)

Пример 3. Простым примером отношения порядка является отношение, задаваемое обычным неравенством hello_html_m7ceebba.gif на множестве вещественных чисел hello_html_257ccf8d.png. Заметим, что для любых чисел hello_html_m5547f17b.gif и hello_html_m11fb3721.gifвыполняется либо hello_html_m56666f63.gif, либо hello_html_61949f0c.gif, т.е. любые два числа сравнимы между собой. Такие отношения называются отношениями полного порядка.

Предикат данного отношения есть просто утверждение hello_html_m56666f63.gif.

Пример 4. Рассмотрим на множестве hello_html_mcd9c74f.gif всех сотрудников некоторого предприятия отношение, задаваемое следующим образом: сотрудник hello_html_m58a23a8a.pngпредшествует сотруднику hello_html_47cd92b6.pngтогда и только тогда, когда выполняется одно из условий: hello_html_954f544.gif, hello_html_m5547f17b.gif является начальником (не обязательно непосредственным) hello_html_m11fb3721.gif. Назовем такое отношение "быть начальником". Легко проверить, что отношение "быть начальником" является отношением порядка. Заметим, что в отличие от предыдущего примера, существуют такие пары сотрудников hello_html_m5547f17b.gif и hello_html_m11fb3721.gif, для которых не выполняется ни hello_html_m56666f63.gif, ни hello_html_61949f0c.gif (например, если hello_html_m5547f17b.gif и hello_html_m11fb3721.gif являются сослуживцами). Такие отношения, в которых есть несравнимые между собой элементы, называют отношениями частичного порядка.[5]

2.1.3 Функциональное отношение

hello_html_m53d4ecad.gifОпределение 10. Отношение hello_html_m4f34938e.pngна декартовом произведении двух множеств hello_html_md4676bd.gifназывается функциональным отношением, если оно обладает следующим свойством:

Если hello_html_6fbc43c0.gifи hello_html_m5340c6ed.gif, то hello_html_3b1813d0.gif (однозначность функции).

Обычно, функциональное отношение обозначают в виде функциональной зависимости - hello_html_6fbc43c0.gifтогда и только тогда, когда hello_html_18a58ebd.gif. Функциональные отношения (подмножества декартового произведения!) называют иначе графиком функции или графиком функциональной зависимости.[9]

Предикат функционального отношения есть просто выражение функциональной зависимости hello_html_18a58ebd.gif.

Пример 5. Пусть множество hello_html_73bad42b.pngесть следующее множество молодых людей: {Вовочка, Петя, Маша, Лена}, причем известны следующие факты:

Вовочка любит Вовочку (эгоист).

Петя любит Машу (взаимно).

Маша любит Петю (взаимно).

Маша любит Машу (себя не забывает).

Лена любит Петю (несчастная любовь).

Информацию о взаимоотношения данных молодых людей можно описать бинарным отношением "любить", заданном на множестве hello_html_m2a90300f.png. Это отношение можно описать несколькими способами.

Способ 1. Перечисление фактов в виде произвольного текста (как это сделано выше).

Способ 2. В виде графа взаимоотношений:


hello_html_m59453a78.png

Рисунок 1 Граф взаимоотношений

Способ 3. При помощи матрицы взаимоотношений:

Способ 4. При помощи таблицы фактов:


Таблица 2 Таблица фактов

Кто любит

Кого любят

Вовочка

Вовочка

Петя

Маша

Маша

Петя

Маша

Маша

Лена

Петя


С точки зрения реляционных баз данных наиболее предпочтительным является четвертый способ, т.к он допускает наиболее удобный способ хранения и манипулирования информацией. Действительно, перечисление фактов как текстовая форма хранения информации уместна для литературного произведения, но с трудом поддается алгоритмической обработке. Изображение в виде графа наглядно, и его удобно использовать как конечную форму представления информации для пользователя, но хранить данные в графическом виде неудобно. Матрица взаимоотношений уже больше соответствует требованиям информационной системы. Матрица удобна в обработке и компактно хранится. Но одно небольшое изменение, например, появился еще Вася и влюбился в несчастную Лену, требует перестройки всей матрицы, а именно, добавления и колонок, и столбцов. Таблица фактов свободна от всех этих недостатков - при добавлении новых действующих лиц просто добавляются новые строки.

Что касается предиката данного отношения, то он имеет следующий вид (дизъюнктивная нормальная форма):

R (x,y) = { (x = "Вовочка" AND y = "Вовочка") OR (x = "Петя" AND y = "Маша") OR (x = "Маша" AND y = "Петя") OR (x = "Маша" AND y = "Маша") OR (x = "Лена" AND y = "Петя") }

Замечание. Приведенное отношение не является ни транзитивным, ни симметричным или антисимметричным, ни рефлексивным, поэтому оно не является ни отношением эквивалентности, ни отношением порядка, ни каким-либо другим разумным отношением.

Замечание. Большая часть мировой литературы существует и имеет смысл лишь постольку, поскольку бинарное отношение "любить" не является отношением эквивалентности. В частности, по этой причине человечество не разбивается на классы эквивалентности взаимно любящих особей. Изучением характеристик данного отношения и соответствующего ему предиката занималось (и продолжает заниматься) большое количество экспертов, таких как Толстой Л.Н., Шекспир В. и др.[3]

2.2. n-арные отношения (отношения степени n)

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

Пример 6. В некотором университете на математическом факультете учатся студенты Иванов, Петров и Сидоров. Лекции им читают преподаватели Пушников, Цыганов и Шарипов, причем известны следующие факты: Пушников читает лекции по алгебре и базам данных, соответственно, 40 и 80 часов в семестр. Цыганов читает лекции по геометрии, 50 часов в семестр. Шарипов читает лекции по алгебре и геометрии, соответственно, 40 и 50 часов в семестр. Студент Иванов посещает лекции по алгебре у Шарипова и по базам данных у Пушникова. Студент Петров посещает лекции по алгебре у Пушникова и по геометрии у Цыганова. Студент Сидоров посещает лекции по геометрии у Цыганова и по базам данных у Пушникова. Для того чтобы формально описать данную ситуацию (например, в целях разработки информационной системы, учитывающей данные о ходе учебного процесса), введем три множества:

Множество преподавателей hello_html_73bad42b.png= {Пушников, Цыганов, Шарипов}.

Множество предметов hello_html_2f8da111.png= {Алгебра, Геометрия, Базы данных}.

Множество студентов hello_html_6af9affc.png= {Иванов, Петров, Сидоров}.

Имеющиеся факты можно разделить на две группы.1 группа (факты 1-3) - факты о преподавателях, 2 группа (факты 4-6) - факты о студентах. Для того чтобы отразить факты 1-3 (характеризующие преподавателей и читаемые ими лекции), введем отношение R1 на декартовом произведении hello_html_39a35a0c.gif, где hello_html_4e3dd032.gif - множество рациональных чисел. А именно, упорядоченная тройка hello_html_m2fcdec0e.gifтогда и только тогда, когда преподаватель hello_html_m5547f17b.gif читает лекции по предмету hello_html_m11fb3721.gif в количестве hello_html_m601acf03.gif часов в семестр. Назовем такое отношение "Читает лекции по…". Множество кортежей, образующих отношениеhello_html_m1430adca.gif удобно представить в виде таблицы:


Таблица 3 Отношение "Читает лекции по…"

A (Преподаватель)

B (Предмет)

Q (Количество часов)

Пушников

Алгебра

40

Пушников

Базы данных

80

Цыганов

Геометрия

50

Шарипов

Алгебра

40

Шарипов

Геометрия

50


Для того чтобы отразить факты 4-6 (характеризующие посещение студентами лекций), введем отношение hello_html_m6cba6fce.gifна декартовом произведении hello_html_m3f803f9f.gif. Упорядоченная тройка hello_html_m70e9cc00.gifтогда и только тогда, когда студент hello_html_m2c47ab3a.gifпосещает лекции по предмету hello_html_m11fb3721.gifу преподавателя hello_html_m5547f17b.gif. Назовем это отношение "Посещать лекции". Его также представим в виде таблицы:


Таблица 4 Отношение "Посещать лекции"

C (студент)

B (предмет)

A(Преподаватель)

Иванов

Алгебра

Шарипов

Иванов

Базы данных

Пушников

Петров

Алгебра

Пушников

Петров

Геометрия

Цыганов

Сидоров

Геометрия

Цыганов

Сидоров

Базы данных

Пушников


Рассмотрим отношение hello_html_m6cba6fce.gifподробнее. Оно задано на декартовом произведении hello_html_m2a05576a.gif. Это произведение, содержащее 3*3*3=27 кортежей, можно назвать "Студенты-Лекции-Преподаватели". Множество hello_html_67b7b75d.pngпредставляет собой совокупность всех возможных вариантов посещения студентами лекций. Отношение же hello_html_m6cba6fce.gif показывает текущее состояние учебного процесса. Очевидно, что отношение hello_html_m6cba6fce.gif является изменяемым во времени отношением.

Итак, факты о ходе учебного процесса удалось отразить в виде двух отношений третьей степени (3-арных), а сами отношения изобразить в виде таблиц с тремя колонками.

Удобство использования табличной формы для задания отношения определяется в данном случае следующими факторами:

Все используемые множества конечны.[4]

При добавлении или удалении студентов, предметов, преподавателей просто добавляются или удаляются соответствующие строки в таблице.

Нас сейчас не интересует вопрос, хороши ли полученные отношения. Заметим пока только, что, как показывают следующие замечания, не любую строку можно добавить в таблицу "Посещать лекции".

Замечание. В таблицу "Посещать лекции" нельзя добавить две одинаковые строки, т.к таблица изображает отношение hello_html_m6cba6fce.gif, а в отношении (как и в любом множестве) не может быть двух одинаковых элементов. Это пример синтаксического ограничения - такое ограничение задано в определении понятия отношение (одинаковых строк не может быть ни в одной таблице, задающей отношение).

Замечание. В таблицу "Посещать лекции" нельзя добавить кортеж (Иванов, Геометрия, Пушников). Действительно, из таблицы "Читает лекции по…", представляющей отношение hello_html_m1430adca.gif, следует, что Пушников не читает предмет "Геометрия". Оказалось, что таблицы связаны друг с другом, и существенным образом! Это пример семантического ограничения - такое ограничение является следствием нашей трактовки данных, хранящихся в отношении (следствием понимания смысла данных).[2]

Транзитивное замыкание отношений

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

Очевидно, что hello_html_20e7bbb.gif.

Пример 7. Пусть множество hello_html_718f0f76.gif представляет собой следующее множество деталей и конструкций:

hello_html_718f0f76.gif= {Болт, Гайка, Двигатель, Автомобиль, Колесо, Ось} причем некоторые из деталей и конструкций могут использоваться при сборке других конструкций. Взаимосвязь деталей описывается отношением hello_html_m1c13e92f.gif ("непосредственно используется в") и состоит из следующих кортежей:


Таблица 5 Отношение R

Конструкция

Где используется

Болт

Двигатель

Болт

Колесо

Гайка

Двигатель

Гайка

Колесо

Двигатель

Автомобиль

Колесо

Автомобиль

Ось

Колесо


Транзитивное замыкание hello_html_33ab9303.gifсостоит из кортежей (добавленные кортежи помечены серым цветом):


Таблица 6 Транзитивное замыкание отношения R

Конструкция

Где используется

Болт

Двигатель

Болт

Колесо

Гайка

Двигатель

Гайка

Колесо

Двигатель

Автомобиль

Колесо

Автомобиль

Ось

Колесо

Болт

Автомобиль

Гайка

Автомобиль

Ось

Автомобиль


Очевидный смысл замыкания hello_html_33ab9303.gifсостоит в описании включения деталей друг в друга не только непосредственно, а через использование их в промежуточных деталях, например, болт используется в автомобиле, т.к он используется в двигателе, а двигатель используется в автомобиле.[8]










ГЛАВА 3. Разработка факультативного курса


3.1 Учебные цели и задачи дисциплины:

- сформировать у учащихся понимание необходимости математических методов познания реальной действительности;

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

- сформировать у учащихся понимание о развивающих возможностях преподаваемого курса;




























3.2. Рабочая программа факультативного курса



урока

урока по теме

Наименование раздела прогр., кол-во часов

Тема урока

Тип урока

Основные тер-мины и понятия

Требования к уровню под-готовки обучающимся

Вид кон-троля

1

1





Алгебра бинарных отношений














Теория множеств

комбинир.

Теория множеств.

Знать, что такое теория множеств.

самопроверка

2

2

Понятие алгебраической операции на множестве

комбинир.

Алгебраические операции на множестве.

Знать, что такое алгебраические операции, выяснить что общего есть в свойствах операций на этих множествах и в чем их различие.

самопроверка взаимопро-

верка

3

3

Бинарные отношения, отношения эквивалентности

комбинир.

Бинарные отношения, отношения эквивалентности.

Знать, что такое бинарные отношения, отношения эквивалентности.

взаимопро-

верка

4

4

Отношение порядка, функциональные отношения

комбинир.

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

Знать основные определения и уметь объяснять их.

Самопроверка

Самост. работа

5

5

Контрольная работа № 1 «Алгебра бинарных отношений и отображений»

проверка знаний и умений

Теория множеств, алгебраические операции на множестве, бинарные отношения.

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

контрольная работа


Примерный перечень вопросов к зачету


  1. Теория множеств

  2. Понятие алгебраической операции на множестве

  3. Бинарные отношения

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

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

  6. Функциональное отношение

  7. n-арные отношения

  8. Транзитивное замыкание отношений

  9. Нейтральные элементы относительно операции



















ЗАКЛЮЧЕНИЕ

Множество является основным строительным материалом математики. Создатель теории множеств Г. Кантор определил множество как "объединение в одно целое объектов, хорошо различимых нашей интуицией или нашей мыслью". Математическое понятие множества постепенно выделилось из привычных представлений о совокупности, собрании, классе, семействе и т.д. На место наивного подхода к понятию множества пришел аксиоматический подход [1, 2]. Аксиомы теории множеств постулируют существование некоторых неопределяемых или примитивных объектов, называемых множествами, вместе с символами и аксиомами, регулирующими их использование. Здесь существует аналогия с геометрией, где задаются неопределяемые объекты, называемые точками и плоскостями, вместе с системой аксиом, связывающих эти объекты друг с другом. Наиболее распространенными являются аксиомы теории множеств Цермело-Френкеля [1].

Множество - это неопределяемое понятие, представляющее некоторую совокупность данных. Элементы множества можно отличать друг от друга, а также определять, принадлежит ли данный элемент данному множеству. Над множествами можно выполнять операции объединения, пересечения, разности и дополнения.

 Отношение - это одна из форм всеобщей взаимосвязи всех предметов, явлений, процессов в природе, обществе  и 
мышлении. Спектр отношений на множествах многоаспектен, начиная с определения понятия множества, аксиоматики 
 
и заканчивая разбором парадоксов. Различных отношений на множестве бесконечно. Но, когда говорят об бинарных
 
отношениях, то подразумевают отношения между двумя величинами, объектами,  высказываниями.

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

Отношение - это подмножество декартового произведения множеств. Отношения состоят из однотипных кортежей. Каждое отношение имеет предикат отношения и каждый n-местный предикат задает n-арное отношение.

Отношение является математическим аналогом понятия "таблица".

Отношения обладают степенью и мощностью. Степень отношения - это количество элементов в каждом кортеже отношения (аналог количества столбцов в таблице). Мощность отношения - это мощность множества кортежей отношения (аналог количества строк в таблице).[6]

В математике чаще всего используют бинарные отношения (отношения степени 2). В теории баз данных основными являются отношения степени hello_html_409df8c9.png. В математике, как правило, отношения заданы на бесконечных множествах и имеют бесконечную мощность. В базах данных напротив, мощности отношений конечны (число хранимых строк в таблицах всегда конечно).[13]












ЛИТЕРАТУРА

  1. Шапорев, С. Д. Дискретная математика : курс лекций и практических занятий / С. Д. Шапорев. – СПб. : БХВ-Петербург, 2009. – 400 с.

  2. Александрова, Л. Г. Дискретная математика в лекциях и задачах / Л. Г. Александрова, П. Б. Кикоть, С. П. Кикоть. – Ч. 1. –
    М. : ГИНФО, 2000. – 228 с.

  3. Гаврилов, Г. П. Сборник задач по дискретной математике / Г. П. Гаврилов, А. А. Сапоженко. – М. : Главная редакция физико-математической литературы изд-ва «Наука», 1977. – 368 с.

  4. Галушкина, Ю. И. Конспект лекций по дискретной математике / Ю. И. Галушкина. – 2-е изд., испр. – М. : Айрис-пресс, 2008. – 176 с.

  5. Гончарова, Г. А. Элементы дискретной математики : учеб. пособие / Г. А. Гончарова, А. А. Мочалин. – М. : Форум-Инфра-М, 2003. – 125 с.*

  6. Долгих, Б. А. Основы дискретной математики / Б. А. Долгих. – М. : ГИНФО, 2002. – 104 с.

  7. Канцедал, С. А. Дискретная математика : учеб. пособие для сред. проф. образования / С. А. Канцедал. – М. : Форум ; Инфра-М, 2007. – 221 с.*

  8. Кикоть, П. Б. Дискретная математика в лекциях и задачах / П. Б. Кикоть, С. П. Кикоть. – Ч. 2. – М. : ГИНФО, 2002. – 192 с.

  9. Колмогоров, А. Н. Математическая логика / А. Н. Колмогоров, А.Г. Драгалин. – изд. 2-е, стер. – М. : Едиториал УРСС,
    2005. – 240 с.

  10. Кулабухов, С. Ю. Дискретная математика / С. Ю. Кулабухов. – Таганрог, 2001. –150 с.

  11. Просветов, Г. И. Дискретная математика : задачи и решения : учеб.-практ. пособие для вузов / Г. И. Просветов. – 2-е изд., доп. – М. : Альфа-Пресс, 2009. – 238 с.*

  12. Тишин, В. В. Дискретная математика в примерах и задачах / В. В. Тишин. – СПб. : БХВ-Петербург, 2008. – 352 с.

  13. Яблонский, С. В. Введение в дискретную математику : учеб пособие для вузов / С. В. Яблонский. – 2-е изд., перераб. и доп. – М. : Наука, 1986 – 384 с.*

ИНТЕРНЕТ-РЕСУРСЫ


  1. «КнигаФонд» – электронная библиотечная система [Электронный ресурс]. – Электрон. дан. – Режим доступа : http://www.knigafund.ru/.

  2. Библиотека «Genesis» [Электронный ресурс]. – Электрон. дан. – Режим доступа : http://gen.lib.rus.ec/.

  3. Образовательный математический сайт [Электронный ресурс]. – Электрон. дан. – Режим доступа : http://www.exponenta.ru/.

  4. Научная электронная библиотека [Электронный ресурс]. – Электрон. дан. – Режим доступа : http://www.elibrary.ru/.

28




57 вебинаров для учителей на разные темы
ПЕРЕЙТИ к бесплатному просмотру
(заказ свидетельства о просмотре - только до 11 декабря)


Автор
Дата добавления 08.01.2016
Раздел Математика
Подраздел Другие методич. материалы
Просмотров478
Номер материала ДВ-315536
Получить свидетельство о публикации
Похожие материалы

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