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

Раздел Математика
Класс -
Тип Другие методич. материалы
Автор
Дата
Формат doc
Изображения Есть
For-Teacher.ru - все для учителя
Поделитесь с коллегами:

Курсовая работа по дискретной математикеВВЕДЕНИЕ

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

Бинарные отношения служат простым и удобным аппаратом для весьма широкого круга задач. Язык бинарных и 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. Пусть Курсовая работа по дискретной математике - произвольное непустое множество и Курсовая работа по дискретной математике - натуральное число. Любое отображение Курсовая работа по дискретной математикеназывают n-арной (или n-местной) операцией на множестве Курсовая работа по дискретной математике.

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

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

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

Обычно, если Курсовая работа по дискретной математике, пишут Курсовая работа по дискретной математике. При Курсовая работа по дискретной математике и Курсовая работа по дискретной математике говорят соответственно об унарной операции и бинарной операции.

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

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

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

1) ассоциативной, если Курсовая работа по дискретной математике для любых Курсовая работа по дискретной математике;
2) коммутативной, если Курсовая работа по дискретной математике для любых Курсовая работа по дискретной математике;
3) идемпотентной, если Курсовая работа по дискретной математике для любого Курсовая работа по дискретной математике.

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

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

Элемент Курсовая работа по дискретной математике множества Курсовая работа по дискретной математике называют левым (правым) нулем относительно данной операции Курсовая работа по дискретной математике, если Курсовая работа по дискретной математике Курсовая работа по дискретной математике для любого Курсовая работа по дискретной математике.

Если Курсовая работа по дискретной математике - левый нуль, а Курсовая работа по дискретной математике - правый нуль, то они совпадают. Действительно, если Курсовая работа по дискретной математике и Курсовая работа по дискретной математике существуют, то они совпадают, так как Курсовая работа по дискретной математике, и в этом случае говорят просто о нуле относительно операции. Из приведенных равенств следует, что нуль единственный и для него одновременно выполнены оба равенства Курсовая работа по дискретной математике и Курсовая работа по дискретной математике.

Пример 2.1.

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

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

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

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

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

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

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

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

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

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

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

Операция Курсовая работа по дискретной математике (разность множеств) не является ассоциативной, так как Курсовая работа по дискретной математике.

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

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

Действительно, для любого отображения Курсовая работа по дискретной математике и любого Курсовая работа по дискретной математике имеем

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Курсовая работа по дискретной математикедля всех Курсовая работа по дискретной математике (рефлексивность)

Если Курсовая работа по дискретной математике, то Курсовая работа по дискретной математике (симметричность)

Если Курсовая работа по дискретной математикеи Курсовая работа по дискретной математике, то Курсовая работа по дискретной математике (транзитивность)

Обычно отношение эквивалентности обозначают знаком Курсовая работа по дискретной математикеили Курсовая работа по дискретной математикеи говорят, что оно (отношение) задано на множестве Курсовая работа по дискретной математике (а не на Курсовая работа по дискретной математике). Условия 1-3 в таких обозначениях выглядят более естественно:

Курсовая работа по дискретной математикедля всех Курсовая работа по дискретной математике (рефлексивность)

Если Курсовая работа по дискретной математике, то Курсовая работа по дискретной математике (симметричность)

Если Курсовая работа по дискретной математикеи Курсовая работа по дискретной математике, то Курсовая работа по дискретной математике (транзитивность)

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

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

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

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

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

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

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

Классы эквивалентности этого отношения состоят из чисел, дающих при делении на 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. Отношение Курсовая работа по дискретной математикена множестве Курсовая работа по дискретной математикеназывается отношением порядка, если оно обладает следующими свойствами:

Курсовая работа по дискретной математикедля всех Курсовая работа по дискретной математике (рефлексивность)

Если Курсовая работа по дискретной математике и Курсовая работа по дискретной математике, то Курсовая работа по дискретной математике (антисимметричность)

Если и Курсовая работа по дискретной математике, то Курсовая работа по дискретной математике (транзитивность)

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

Курсовая работа по дискретной математикедля всех Курсовая работа по дискретной математике (рефлексивность)

Если Курсовая работа по дискретной математикеи Курсовая работа по дискретной математике, то Курсовая работа по дискретной математике (антисимметричность)

Если Курсовая работа по дискретной математикеи Курсовая работа по дискретной математике, то Курсовая работа по дискретной математике (транзитивность)

Пример 3. Простым примером отношения порядка является отношение, задаваемое обычным неравенством Курсовая работа по дискретной математике на множестве вещественных чисел Курсовая работа по дискретной математике. Заметим, что для любых чисел Курсовая работа по дискретной математике и Курсовая работа по дискретной математикевыполняется либо Курсовая работа по дискретной математике, либо Курсовая работа по дискретной математике, т.е. любые два числа сравнимы между собой. Такие отношения называются отношениями полного порядка.

Предикат данного отношения есть просто утверждение Курсовая работа по дискретной математике.

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

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

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

Если Курсовая работа по дискретной математикеи Курсовая работа по дискретной математике, то Курсовая работа по дискретной математике (однозначность функции).

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

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

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

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

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

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

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

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

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

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

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

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

Рисунок 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 часов в семестр. Студент Иванов посещает лекции по алгебре у Шарипова и по базам данных у Пушникова. Студент Петров посещает лекции по алгебре у Пушникова и по геометрии у Цыганова. Студент Сидоров посещает лекции по геометрии у Цыганова и по базам данных у Пушникова. Для того чтобы формально описать данную ситуацию (например, в целях разработки информационной системы, учитывающей данные о ходе учебного процесса), введем три множества:

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

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

Множество студентов Курсовая работа по дискретной математике= {Иванов, Петров, Сидоров}.

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

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

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

B (Предмет)

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

Пушников

Алгебра

40

Пушников

Базы данных

80

Цыганов

Геометрия

50

Шарипов

Алгебра

40

Шарипов

Геометрия

50

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

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

C (студент)

B (предмет)

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

Иванов

Алгебра

Шарипов

Иванов

Базы данных

Пушников

Петров

Алгебра

Пушников

Петров

Геометрия

Цыганов

Сидоров

Геометрия

Цыганов

Сидоров

Базы данных

Пушников

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Конструкция

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

Болт

Двигатель

Болт

Колесо

Гайка

Двигатель

Гайка

Колесо

Двигатель

Автомобиль

Колесо

Автомобиль

Ось

Колесо

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

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

Конструкция

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

Болт

Двигатель

Болт

Колесо

Гайка

Двигатель

Гайка

Колесо

Двигатель

Автомобиль

Колесо

Автомобиль

Ось

Колесо

Болт

Автомобиль

Гайка

Автомобиль

Ось

Автомобиль

Очевидный смысл замыкания Курсовая работа по дискретной математикесостоит в описании включения деталей друг в друга не только непосредственно, а через использование их в промежуточных деталях, например, болт используется в автомобиле, т.к он используется в двигателе, а двигатель используется в автомобиле.[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). В теории баз данных основными являются отношения степени Курсовая работа по дискретной математике. В математике, как правило, отношения заданы на бесконечных множествах и имеют бесконечную мощность. В базах данных напротив, мощности отношений конечны (число хранимых строк в таблицах всегда конечно).[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. «КнигаФонд» - электронная библиотечная система [Электронный ресурс]. - Электрон. дан. - Режим доступа : knigafund.ru/.

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

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

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

28

© 2010-2022