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

13 EMBED Equation.3 1415ВВЕДЕНИЕ
Математика как наука отражает мир взаимодействующих простых и сложных объектов (вещей, явлений, процессов). Абстрагируясь от реальности, математика рассматривает унарные, бинарные и другие отношения.
Бинарные отношения служат простым и удобным аппаратом для весьма широкого круга задач. Язык бинарных и n-арных отношений используется во многих прикладных (для математики) областях, например, таких как математическая лингвистика, математическая биология, математическая теория баз данных. Широкое использование языка бинарных отношений легко объясняется – геометрический аспект теории бинарных отношений есть попросту теория графов.
Таким образом, актуальность проблемы изучения бинарных отношений обусловила тему исследования: «Алгебра бинарных отношений и отображений».
Объект исследования: система бинарных отношений и отображений.
Предмет исследования: совокупность теоретических и практических основ алгебраических операций на множестве.
Цель работы: изучить методы исследования бинарных отношений и отображений.
В соответствии с объектом, предметом и целью исследования определены следующие задачи:
Охарактеризовать понятия бинарных отношений и отображений.
Изучить особенности алгебраических операций на множестве.
Исследовать наиболее важные типы бинарных отношений.
Показать особенности бинарных отношений и отображений на примере решения задач.
Гипотеза исследования основывается на предположении о том, что наиболее важными типами бинарных отношений являются отношения эквивалентности, линейного и частичного порядка отношения.
Методологической основой исследования послужили математические исследования, основанные на теоретико-множественной концепции строения любой математической теории. С этой точки зрения любая математическая теория имеет дело с одним или несколькими множествами объектов, связанных между собой некоторыми отношениями. Основоположником теории множеств и отношений между ними является немецкий математик Георг Кантор (18451918), который говорил: «Множество есть многое, мыслимое как единое». Благодаря дальнейшему развитию теории множеств в трудах Д. Гильберта и Г. Вейля стала возможной аксиоматизация и четкое разделение различных категорий множеств.

ГЛАВА 1. Элементы теории множеств
Теория множеств
Теория множеств - раздел математики, изучающий точными средствами содержание одной из важнейших категорий философии, логики и математики категории бесконечного (Бесконечное и конечное). Основана Г. Кантором (18451918). Предметом теории множеств являются свойства множеств (совокупностей, классов, ансамблей), главным образом бесконечных. Фундаментальным положением теории множеств служит установление различных “порядков” бесконечности. Классическая теория множеств исходит из признания применимости к бесконечным множествам принципов логики, бесспорных в области конечного. Однако развитие теории множеств уже в конце 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. Пусть [ Cкачайте файл, чтобы посмотреть картинку ] произвольное непустое множество и [ Cкачайте файл, чтобы посмотреть картинку ] натуральное число. Любое отображение [ Cкачайте файл, чтобы посмотреть картинку ]называют n-арной (или n-местной) операцией на множестве [ Cкачайте файл, чтобы посмотреть картинку ].
Таким образом, согласно приведенному определению, n-арная операция и каждому кортежу [ Cкачайте файл, чтобы посмотреть картинку ] однозначно сопоставляет элемент [ Cкачайте файл, чтобы посмотреть картинку ]. Компоненты кортежа называют при этом аргументами операции [ Cкачайте файл, чтобы посмотреть картинку ], а [ Cкачайте файл, чтобы посмотреть картинку ] результатом применения операции и к аргументам [ Cкачайте файл, чтобы посмотреть картинку ].
Для n-арной операции используют обозначение
[ Cкачайте файл, чтобы посмотреть картинку ] или [ Cкачайте файл, чтобы посмотреть картинку ].
Обычно, если [ Cкачайте файл, чтобы посмотреть картинку ], пишут [ Cкачайте файл, чтобы посмотреть картинку ]. При [ Cкачайте файл, чтобы посмотреть картинку ] и [ Cкачайте файл, чтобы посмотреть картинку ] говорят соответственно об унарной операции и бинарной операции.
Специально вводят понятие нульарной операции (т.е. для [ Cкачайте файл, чтобы посмотреть картинку ]). Под нульарной операцией на множестве [ Cкачайте файл, чтобы посмотреть картинку ] понимают произвольный фиксированный элемент множества [ Cкачайте файл, чтобы посмотреть картинку ]. Нульарные операции позволяют фиксировать элементы множества [ Cкачайте файл, чтобы посмотреть картинку ], обладающие некоторыми специальными свойствами. Примером выполнения нульарной операции является, например, фиксирование нуля в множестве целых чисел с операцией сложения. Примером унарной операции служит дополнение заданного множества до универсального множества.
Наиболее важными в алгебре и, следовательно, наиболее исследованными являются бинарные операции. Примерами таких операций могут служить сложение и умножение чисел, сложение и умножение матриц, сложение векторов линейного пространства.
Рассмотрим бинарную операцию на множестве [ Cкачайте файл, чтобы посмотреть картинку ], обозначив ее звездочкой [ Cкачайте файл, чтобы посмотреть картинку ]. Эту операцию называют:
1) ассоциативной, если [ Cкачайте файл, чтобы посмотреть картинку ] для любых [ Cкачайте файл, чтобы посмотреть картинку ];2) коммутативной, если [ Cкачайте файл, чтобы посмотреть картинку ] для любых [ Cкачайте файл, чтобы посмотреть картинку ];3) идемпотентной, если [ Cкачайте файл, чтобы посмотреть картинку ] для любого [ Cкачайте файл, чтобы посмотреть картинку ].
Ассоциативность операции [ Cкачайте файл, чтобы посмотреть картинку ] позволяет для любых элементов [ Cкачайте файл, чтобы посмотреть картинку ] однозначно трактовать результат выражения [ Cкачайте файл, чтобы посмотреть картинку ].
Операция сложения, заданная на множестве натуральных чисел, является ассоциативной и коммутативной. Операция умножения матриц ассоциативна, но не коммутативна. Идемпотентными являются операции объединения и пересечения множеств.[8]
Элемент [ Cкачайте файл, чтобы посмотреть картинку ] множества [ Cкачайте файл, чтобы посмотреть картинку ] называют левым (правым) нулем относительно данной операции [ Cкачайте файл, чтобы посмотреть картинку ], если [ Cкачайте файл, чтобы посмотреть картинку ].
Если [ Cкачайте файл, чтобы посмотреть картинку ] левый нуль, а [ Cкачайте файл, чтобы посмотреть картинку ] правый нуль, то они совпадают. Действительно, если [ Cкачайте файл, чтобы посмотреть картинку ] и [ Cкачайте файл, чтобы посмотреть картинку ] существуют, то они совпадают, так как [ Cкачайте файл, чтобы посмотреть картинку ], и в этом случае говорят просто о нуле относительно операции. Из приведенных равенств следует, что нуль единственный и для него одновременно выполнены оба равенства [ Cкачайте файл, чтобы посмотреть картинку ] и [ Cкачайте файл, чтобы посмотреть картинку ].
Пример 2.1.
а. На множестве целых чисел [ Cкачайте файл, чтобы посмотреть картинку ] нулем относительно операции умножения будет число 0.
б. На множестве квадратных матриц вида [ Cкачайте файл, чтобы посмотреть картинку ], где элементы [ Cкачайте файл, чтобы посмотреть картинку ] и [ Cкачайте файл, чтобы посмотреть картинку ] действительные числа, любая матрица вида [ Cкачайте файл, чтобы посмотреть картинку ] будет правым нулем относительно операции умножения.
Однако левого нуля в этом множестве нет, так как иначе он совпадал бы с правым нулем и был бы единственным. Но правых нулей имеется больше одного.
Нейтральные элементы относительно операции
Элемент [ Cкачайте файл, чтобы посмотреть картинку ] множества [ Cкачайте файл, чтобы посмотреть картинку ] называют левым (правым) нейтральным элементом относительно операции [ Cкачайте файл, чтобы посмотреть картинку ], если [ Cкачайте файл, чтобы посмотреть картинку ]. Для левого [ Cкачайте файл, чтобы посмотреть картинку ]; и правого [ Cкачайте файл, чтобы посмотреть картинку ] нейтральных элементов, если они оба существуют, выполнены равенства [ Cкачайте файл, чтобы посмотреть картинку ], согласно которым они совпадают. В этом случае элемент [ Cкачайте файл, чтобы посмотреть картинку ], который является и левым нейтральным, и правым нейтральным, единственный, и его называют просто нейтральным элементом.
Пример 2.2. Нейтральным элементом относительно операции умножения на множестве натуральных чисел является число 1. На множестве целых чисел нейтральным элементом относительно операции сложения будет число 0.
На множестве квадратных матриц вида [ Cкачайте файл, чтобы посмотреть картинку ], где элементы [ Cкачайте файл, чтобы посмотреть картинку ] и [ Cкачайте файл, чтобы посмотреть картинку ] действительные числа, любая матрица вида [ Cкачайте файл, чтобы посмотреть картинку ] будет правым нейтральным элементом по операции умножения.
Поскольку правых нейтральных элементов несколько, то левого нейтрального элемента по этой операции нет, так как иначе существовал бы единственный нейтральный элемент (левый и правый).
Следует заметить, что не для всякой бинарной операции нули и нейтральные элементы (левые и правые, в частности), существуют. [4]
Рассмотрим некоторые примеры бинарных операций на множествах.
Пример 2.3. а. Пусть [ Cкачайте файл, чтобы посмотреть картинку ] универсальное множество. Теоретико-множественные операции [ Cкачайте файл, чтобы посмотреть картинку ] на множестве [ Cкачайте файл, чтобы посмотреть картинку ] являются идемпотентными, ассоциативными и коммутативными, причем пустое множество является нулем относительно пересечения и нейтральным элементом относительно объединения [ Cкачайте файл, чтобы посмотреть картинку ] тогда как универсальное множество есть нуль относительно объединения и нейтральный элемент относительно пересечения [ Cкачайте файл, чтобы посмотреть картинку ]
Операция [ Cкачайте файл, чтобы посмотреть картинку ] (разность множеств) не является ассоциативной, так как [ Cкачайте файл, чтобы посмотреть картинку ].
б. На множестве всех бинарных отношений на множестве [ Cкачайте файл, чтобы посмотреть картинку ] операция композиции отношений является ассоциативной, но не коммутативной, а диагональ множества [ Cкачайте файл, чтобы посмотреть картинку ] будет нейтральным элементом относительно этой операции.
в. Пусть [ Cкачайте файл, чтобы посмотреть картинку ] произвольное множество, содержащее не менее двух элементов. На множестве всех отображений из [ Cкачайте файл, чтобы посмотреть картинку ] в [ Cкачайте файл, чтобы посмотреть картинку ] с операцией композиции отображений постоянное отображение [ Cкачайте файл, чтобы посмотреть картинку ], переводящее любой элемент [ Cкачайте файл, чтобы посмотреть картинку ] в фиксированный элемент [ Cкачайте файл, чтобы посмотреть картинку ], будет правым нулем, но не будет нулем относительно композиции отображений.
Действительно, для любого отображения [ Cкачайте файл, чтобы посмотреть картинку ] и любого [ Cкачайте файл, чтобы посмотреть картинку ] имеем
[ Cкачайте файл, чтобы посмотреть картинку ], то есть [ Cкачайте файл, чтобы посмотреть картинку ],
что и означает, что [ Cкачайте файл, чтобы посмотреть картинку ] правый нуль относительно операции композиции на множестве отображений из [ Cкачайте файл, чтобы посмотреть картинку ] в [ Cкачайте файл, чтобы посмотреть картинку ]. Однако для любого [ Cкачайте файл, чтобы посмотреть картинку ]имеем
[ Cкачайте файл, чтобы посмотреть картинку ] то есть [ Cкачайте файл, чтобы посмотреть картинку ] отображение, которое любой элемент [ Cкачайте файл, чтобы посмотреть картинку ] переводит в элемент [ Cкачайте файл, чтобы посмотреть картинку ]. Поскольку [ Cкачайте файл, чтобы посмотреть картинку ] в общем случае не равно [ Cкачайте файл, чтобы посмотреть картинку ], то [ Cкачайте файл, чтобы посмотреть картинку ]. Значит, [ Cкачайте файл, чтобы посмотреть картинку ] не является левым нулем относительно операции композиции.
Рассмотренные выше примеры множеств с операциями приводят к следующим определениям.
Определение 2.2. Алгебра (универсальная алгебра,
·-алгебра) считается заданной, если заданы некоторое множество [ Cкачайте файл, чтобы посмотреть картинку ], называемое носителем данной алгебры, и некоторое множество операций [ Cкачайте файл, чтобы посмотреть картинку ] на [ Cкачайте файл, чтобы посмотреть картинку ], называемое сигнатурой данной алгебры. Алгебру, носитель которой есть конечное множество, называют конечной алгеброй.[2]
Поскольку алгебра задается ее носителем и сигнатурой, мы будем в записи обозначать алгебру как упорядоченную пару множеств [ Cкачайте файл, чтобы посмотреть картинку ], полагая, что первая компонента этой пары есть носитель, а вторая сигнатура. Подчеркнем, что алгебра это не просто носитель и не просто сигнатура, а „синтез" этих двух объектов.
Замечание 2.1. Операции, включенные в сигнатуру, заданы как некоторые специальные отображения. Однако при этом не оговариваются свойства, которыми обладают операг ции на носителе. Например, они могут быть ассоциативными, коммутативными и т.д. При задании алгебр свойства операций обычно указывают дополнительно.
Если существует нейтральный элемент относительно операции, то его можно задать как нульарную операцию на носителе и включить в сигнатуру, а можно не включать и описать как свойство соответствующей операции.
Таким образом, одну и ту же алгебру можно задавать по-разному. Ниже приведены примеры различных описаний конкретных алгебр.
В ряде случаев указание носителя алгебры предполагает и задание определенной сигнатуры. В этом случае для упрощения пишут не [ Cкачайте файл, чтобы посмотреть картинку ], а просто [ Cкачайте файл, чтобы посмотреть картинку ] и говорят "элемент алгебры [ Cкачайте файл, чтобы посмотреть картинку ]", имея в виду элемент носителя этой алгебры.
Пример 2.4. а. Рассмотрим алгебру
Ее носителем является множество всех подмножеств произвольно фиксированного множества [ Cкачайте файл, чтобы посмотреть картинку ], а сигнатура состоит из следующих операций над множествами: объединения, пересечения, разности, симметрической разности, дополнения, пустого множества и множества [ Cкачайте файл, чтобы посмотреть картинку ] (последние два элемента сигнатуры определяют нульарные операции).
б. Для любого множества [ Cкачайте файл, чтобы посмотреть картинку ] можно определить алгебру
[ Cкачайте файл, чтобы посмотреть картинку ]носителем которой является множество всех подмножеств множества упорядоченных пар на [ Cкачайте файл, чтобы посмотреть картинку ], т.е. множество всех бинарных отношений на множестве [ Cкачайте файл, чтобы посмотреть картинку ], а сигнатура состоит из операций объединения, композиции бинарных отношений и взятия обратного отношения.[7]
в. На множестве [ Cкачайте файл, чтобы посмотреть картинку ] действительных чисел можно, например, определить такую алгебру:
[ Cкачайте файл, чтобы посмотреть картинку ] сигнатура которой состоит из операций сложения, умножения, а также двух нульарных операций, обозначающих два особых числа 0 и 1. Обратим внимание на то, что числа 0 и 1 в данном случае являются соответственно нулем и нейтральным элементом относительно умножения, а число 0 также играет роль нейтрального элемента относительно сложения. Все предыдущие примеры алгебр были алгебрами с конечной сигнатурой, т.е. с сигнатурой, состоящей из конечного числа операций. Однако несложно построить пример алгебры с бесконечной сигнатурой. Например, алгебра [ Cкачайте файл, чтобы посмотреть картинку ]
на множестве действительных чисел [ Cкачайте файл, чтобы посмотреть картинку ] с операцией [ Cкачайте файл, чтобы посмотреть картинку ] возведения в натуральную степень [ Cкачайте файл, чтобы посмотреть картинку ] имеет счетную сигнатуру. Далее будут приведены примеры алгебр и с нечетными сигнатурами.
Определяя алгебру, следует помнить, что результат применения любой операции обязательно должен принадлежать тому же множеству, что и ее аргументы. Например, пару из множества [ Cкачайте файл, чтобы посмотреть картинку ] всех свободных векторов в пространстве и операции скалярного умножения векторов нельзя рассматривать как алгебру, так как скалярное произведение двух векторов не есть вектор. Заменив скалярное умножение векторным, получим алгебру.
Кроме того, нельзя забывать, что n-арная операция, как и всякое отображение, должна быть определена для любого кортежа длины n элементов множества. Поэтому не является алгеброй множество всех матриц с операциями сложения и умножения матриц, так как эти операции определены не для любой упорядоченной пары матриц. Если же при тех же операциях ограничиться множеством квадратных матриц фиксированного порядка [ Cкачайте файл, чтобы посмотреть картинку ], то получим алгебру.[1, 3]
Точно так же множество действительных чисел [ Cкачайте файл, чтобы посмотреть картинку ] с операцией [ Cкачайте файл, чтобы посмотреть картинку ] деления действительных чисел не является алгеброй, поскольку результат деления не определен при нулевом делителе. Пара же [ Cкачайте файл, чтобы посмотреть картинку ] есть алгебра.
Договоримся, определяя конкретную алгебру, записывать ее сигнатуру без фигурных скобок, перечисляя после обозначения носителя все операции. Так, в примере 2.4.а первая алгебра может быть записана как
Для алгебры [ Cкачайте файл, чтобы посмотреть картинку ] обозначим через [ Cкачайте файл, чтобы посмотреть картинку ] подмножество сигнатуры [ Cкачайте файл, чтобы посмотреть картинку ], состоящее из всех n-арных операций. Тогда [ Cкачайте файл, чтобы посмотреть картинку ]. Так, для алгебры [ Cкачайте файл, чтобы посмотреть картинку ] в примере 2.4.а будем иметь: при [ Cкачайте файл, чтобы посмотреть картинку ].

ГЛАВА 2. Отношения на множествах
2.1. Бинарные отношения (отношения степени 2)
В математике большую роль играют бинарные отношения, т.е. отношения, заданные на декартовом произведении двух множеств [ Cкачайте файл, чтобы посмотреть картинку ].
2.1.1 Отношение эквивалентности
Определение 8. Отношение [ Cкачайте файл, чтобы посмотреть картинку ]на множестве [ Cкачайте файл, чтобы посмотреть картинку ]называется отношением эквивалентности, если оно обладает следующими свойствами:
[ Cкачайте файл, чтобы посмотреть картинку ]для всех [ Cкачайте файл, чтобы посмотреть картинку ] (рефлексивность)
Если [ Cкачайте файл, чтобы посмотреть картинку ], то [ Cкачайте файл, чтобы посмотреть картинку ] (симметричность)
Если [ Cкачайте файл, чтобы посмотреть картинку ]и [ Cкачайте файл, чтобы посмотреть картинку ], то [ Cкачайте файл, чтобы посмотреть картинку ] (транзитивность)
Обычно отношение эквивалентности обозначают знаком [ Cкачайте файл, чтобы посмотреть картинку ]или [ Cкачайте файл, чтобы посмотреть картинку ]и говорят, что оно (отношение) задано на множестве [ Cкачайте файл, чтобы посмотреть картинку ] (а не на [ Cкачайте файл, чтобы посмотреть картинку ]). Условия 1-3 в таких обозначениях выглядят более естественно:
[ Cкачайте файл, чтобы посмотреть картинку ]для всех [ Cкачайте файл, чтобы посмотреть картинку ] (рефлексивность)
Если [ Cкачайте файл, чтобы посмотреть картинку ], то [ Cкачайте файл, чтобы посмотреть картинку ] (симметричность)
Если [ Cкачайте файл, чтобы посмотреть картинку ]и [ Cкачайте файл, чтобы посмотреть картинку ], то [ Cкачайте файл, чтобы посмотреть картинку ] (транзитивность)
Легко доказывается, что если на множестве [ Cкачайте файл, чтобы посмотреть картинку ]задано отношение эквивалентности, то множество [ Cкачайте файл, чтобы посмотреть картинку ]разбивается на взаимно непересекающиеся подмножества, состоящие из эквивалентных друг другу элементов (классы эквивалентности).
Пример 1. Рассмотрим на множестве вещественных чисел [ Cкачайте файл, чтобы посмотреть картинку ]отношение, заданное просто равенством чисел. Предикат такого отношения:
[ Cкачайте файл, чтобы посмотреть картинку ], или просто 13 EMBED Equation.3 1415
Условия 1-3, очевидно, выполняются, поэтому данное отношение является отношением эквивалентности. Каждый класс эквивалентности этого отношения состоит из одного числа.[6]
Пример 2. Рассмотрим более сложное отношение эквивалентности. На множестве целых чисел [ Cкачайте файл, чтобы посмотреть картинку ]зададим отношение "равенство по модулю n" следующим образом: два числа [ Cкачайте файл, чтобы посмотреть картинку ]и [ Cкачайте файл, чтобы посмотреть картинку ]равны по модулю n, если их остатки при делении на n равны. Например, по модулю 5 равны числа 2, 7, 12 и т.д.
Условия 1-3 легко проверяются, поэтому равенство по модулю является отношением эквивалентности. Предикат этого отношения имеет вид:

[ Cкачайте файл, чтобы посмотреть картинку ]

Классы эквивалентности этого отношения состоят из чисел, дающих при делении на 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. Отношение [ Cкачайте файл, чтобы посмотреть картинку ]на множестве [ Cкачайте файл, чтобы посмотреть картинку ]называется отношением порядка, если оно обладает следующими свойствами:
13 EMBED Equation.3 1415для всех 13 EMBED Equation.3 1415 (рефлексивность)
Если 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415, то 13 EMBED Equation.3 1415 (антисимметричность)
Если и 13 EMBED Equation.3 1415, то 13 EMBED Equation.3 1415 (транзитивность)
Обычно отношение порядка обозначают знаком 13 EMBED Equation.3 1415. Если для двух элементов 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415выполняется 13 EMBED Equation.3 1415, то говорят, что 13 EMBED Equation.3 1415 "предшествует" 13 EMBED Equation.3 1415. Как и для отношения эквивалентности, условия 1-3 в таких обозначениях выглядят более естественно:
13 EMBED Equation.3 1415для всех 13 EMBED Equation.3 1415 (рефлексивность)
Если 13 EMBED Equation.3 1415и 13 EMBED Equation.3 1415, то 13 EMBED Equation.3 1415 (антисимметричность)
Если 13 EMBED Equation.3 1415и 13 EMBED Equation.3 1415, то 13 EMBED Equation.3 1415 (транзитивность)
Пример 3. Простым примером отношения порядка является отношение, задаваемое обычным неравенством 13 EMBED Equation.3 1415 на множестве вещественных чисел [ Cкачайте файл, чтобы посмотреть картинку ]. Заметим, что для любых чисел 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415выполняется либо 13 EMBED Equation.3 1415, либо 13 EMBED Equation.3 1415, т.е. любые два числа сравнимы между собой. Такие отношения называются отношениями полного порядка.
Предикат данного отношения есть просто утверждение 13 EMBED Equation.3 1415.
Пример 4. Рассмотрим на множестве 13 EMBED Equation.3 1415 всех сотрудников некоторого предприятия отношение, задаваемое следующим образом: сотрудник [ Cкачайте файл, чтобы посмотреть картинку ]предшествует сотруднику [ Cкачайте файл, чтобы посмотреть картинку ]тогда и только тогда, когда выполняется одно из условий: 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415 является начальником (не обязательно непосредственным) 13 EMBED Equation.3 1415. Назовем такое отношение "быть начальником". Легко проверить, что отношение "быть начальником" является отношением порядка. Заметим, что в отличие от предыдущего примера, существуют такие пары сотрудников 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415, для которых не выполняется ни 13 EMBED Equation.3 1415, ни 13 EMBED Equation.3 1415 (например, если 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415 являются сослуживцами). Такие отношения, в которых есть несравнимые между собой элементы, называют отношениями частичного порядка.[5]
2.1.3 Функциональное отношение
13 EMBED Equation.3 1415 Определение 10. Отношение [ Cкачайте файл, чтобы посмотреть картинку ]на декартовом произведении двух множеств 13 EMBED Equation.3 1415называется функциональным отношением, если оно обладает следующим свойством:
Если 13 EMBED Equation.3 1415и 13 EMBED Equation.3 1415, то 13 EMBED Equation.3 1415 (однозначность функции).
Обычно, функциональное отношение обозначают в виде функциональной зависимости - 13 EMBED Equation.3 1415тогда и только тогда, когда 13 EMBED Equation.3 1415. Функциональные отношения (подмножества декартового произведения!) называют иначе графиком функции или графиком функциональной зависимости.[9]
Предикат функционального отношения есть просто выражение функциональной зависимости 13 EMBED Equation.3 1415.
Пример 5. Пусть множество [ Cкачайте файл, чтобы посмотреть картинку ]есть следующее множество молодых людей: {Вовочка, Петя, Маша, Лена}, причем известны следующие факты:
Вовочка любит Вовочку (эгоист).
Петя любит Машу (взаимно).
Маша любит Петю (взаимно).
Маша любит Машу (себя не забывает).
Лена любит Петю (несчастная любовь).
Информацию о взаимоотношения данных молодых людей можно описать бинарным отношением "любить", заданном на множестве [ Cкачайте файл, чтобы посмотреть картинку ]. Это отношение можно описать несколькими способами.
Способ 1. Перечисление фактов в виде произвольного текста (как это сделано выше).
Способ 2. В виде графа взаимоотношений:

[ Cкачайте файл, чтобы посмотреть картинку ]
Рисунок 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 часов в семестр. Студент Иванов посещает лекции по алгебре у Шарипова и по базам данных у Пушникова. Студент Петров посещает лекции по алгебре у Пушникова и по геометрии у Цыганова. Студент Сидоров посещает лекции по геометрии у Цыганова и по базам данных у Пушникова. Для того чтобы формально описать данную ситуацию (например, в целях разработки информационной системы, учитывающей данные о ходе учебного процесса), введем три множества:
Множество преподавателей [ Cкачайте файл, чтобы посмотреть картинку ]= {Пушников, Цыганов, Шарипов}.
Множество предметов [ Cкачайте файл, чтобы посмотреть картинку ]= {Алгебра, Геометрия, Базы данных}.
Множество студентов [ Cкачайте файл, чтобы посмотреть картинку ]= {Иванов, Петров, Сидоров}.
Имеющиеся факты можно разделить на две группы.1 группа (факты 1-3) - факты о преподавателях, 2 группа (факты 4-6) - факты о студентах. Для того чтобы отразить факты 1-3 (характеризующие преподавателей и читаемые ими лекции), введем отношение R1 на декартовом произведении 13 EMBED Equation.3 1415, где 13 EMBED Equation.3 1415 - множество рациональных чисел. А именно, упорядоченная тройка 13 EMBED Equation.3 1415тогда и только тогда, когда преподаватель 13 EMBED Equation.3 1415 читает лекции по предмету 13 EMBED Equation.3 1415 в количестве 13 EMBED Equation.3 1415 часов в семестр. Назовем такое отношение "Читает лекции по". Множество кортежей, образующих отношение13 EMBED Equation.3 1415 удобно представить в виде таблицы:

Таблица 3 Отношение "Читает лекции по"
A (Преподаватель)
B (Предмет)
Q (Количество часов)

Пушников
Алгебра
40

Пушников
Базы данных
80

Цыганов
Геометрия
50

Шарипов
Алгебра
40

Шарипов
Геометрия
50

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

Таблица 4 Отношение "Посещать лекции"
C (студент)
B (предмет)
A(Преподаватель)

Иванов
Алгебра
Шарипов

Иванов
Базы данных
Пушников

Петров
Алгебра
Пушников

Петров
Геометрия
Цыганов

Сидоров
Геометрия
Цыганов

Сидоров
Базы данных
Пушников

Рассмотрим отношение 13 EMBED Equation.3 1415подробнее. Оно задано на декартовом произведении 13 EMBED Equation.3 1415. Это произведение, содержащее 3*3*3=27 кортежей, можно назвать "Студенты-Лекции-Преподаватели". Множество [ Cкачайте файл, чтобы посмотреть картинку ]представляет собой совокупность всех возможных вариантов посещения студентами лекций. Отношение же 13 EMBED Equation.3 1415 показывает текущее состояние учебного процесса. Очевидно, что отношение 13 EMBED Equation.3 1415 является изменяемым во времени отношением.
Итак, факты о ходе учебного процесса удалось отразить в виде двух отношений третьей степени (3-арных), а сами отношения изобразить в виде таблиц с тремя колонками.
Удобство использования табличной формы для задания отношения определяется в данном случае следующими факторами:
Все используемые множества конечны.[4]
При добавлении или удалении студентов, предметов, преподавателей просто добавляются или удаляются соответствующие строки в таблице.
Нас сейчас не интересует вопрос, хороши ли полученные отношения. Заметим пока только, что, как показывают следующие замечания, не любую строку можно добавить в таблицу "Посещать лекции".
Замечание. В таблицу "Посещать лекции" нельзя добавить две одинаковые строки, т.к таблица изображает отношение 13 EMBED Equation.3 1415, а в отношении (как и в любом множестве) не может быть двух одинаковых элементов. Это пример синтаксического ограничения - такое ограничение задано в определении понятия отношение (одинаковых строк не может быть ни в одной таблице, задающей отношение).
Замечание. В таблицу "Посещать лекции" нельзя добавить кортеж (Иванов, Геометрия, Пушников). Действительно, из таблицы "Читает лекции по", представляющей отношение 13 EMBED Equation.3 1415, следует, что Пушников не читает предмет "Геометрия". Оказалось, что таблицы связаны друг с другом, и существенным образом! Это пример семантического ограничения - такое ограничение является следствием нашей трактовки данных, хранящихся в отношении (следствием понимания смысла данных).[2]
Транзитивное замыкание отношений
Введем понятие транзитивного замыкания, связанное с бинарными отношениями, которое понадобится в дальнейшем.
Очевидно, что 13 EMBED Equation.3 1415.
Пример 7. Пусть множество 13 EMBED Equation.3 1415 представляет собой следующее множество деталей и конструкций:
13 EMBED Equation.3 1415= {Болт, Гайка, Двигатель, Автомобиль, Колесо, Ось} причем некоторые из деталей и конструкций могут использоваться при сборке других конструкций. Взаимосвязь деталей описывается отношением 13 EMBED Equation.3 1415 ("непосредственно используется в") и состоит из следующих кортежей:

Таблица 5 Отношение R
Конструкция
Где используется

Болт
Двигатель

Болт
Колесо

Гайка
Двигатель

Гайка
Колесо

Двигатель
Автомобиль

Колесо
Автомобиль

Ось
Колесо

Транзитивное замыкание 13 EMBED Equation.3 1415состоит из кортежей (добавленные кортежи помечены серым цветом):

Таблица 6 Транзитивное замыкание отношения R
Конструкция
Где используется

Болт
Двигатель

Болт
Колесо

Гайка
Двигатель

Гайка
Колесо

Двигатель
Автомобиль

Колесо
Автомобиль

Ось
Колесо

Болт
Автомобиль

Гайка
Автомобиль

Ось
Автомобиль

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

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

3.1 Учебные цели и задачи дисциплины:
- сформировать у учащихся понимание необходимости математических методов познания реальной действительности;
- развить умение самостоятельной работы с учебными пособиями и другой учебно-методической литературой, способствовать развитию математической культуры;
- сформировать у учащихся понимание о развивающих возможностях преподаваемого курса;

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

№ урока
№ урока по теме
Наименование раздела прогр., кол-во часов
Тема урока
Тип урока
Основные тер-мины и понятия
Требования к уровню под-готовки обучающимся
Вид кон-троля

1
1

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

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

2
2

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

3
3

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

4
4

Отношение порядка, функциональные отношения
комбинир.
Опеределения отношения порядка
Знать основные определения и уметь объяснять их.
Самопроверка
Самост. работа

5
5

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

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

Теория множеств
Понятие алгебраической операции на множестве
Бинарные отношения
Отношение эквивалентности
Отношение порядка
Функциональное отношение
n-арные отношения
Транзитивное замыкание отношений
Нейтральные элементы относительно операции

ЗАКЛЮЧЕНИЕ
Множество является основным строительным материалом математики. Создатель теории множеств Г. Кантор определил множество как "объединение в одно целое объектов, хорошо различимых нашей интуицией или нашей мыслью". Математическое понятие множества постепенно выделилось из привычных представлений о совокупности, собрании, классе, семействе и т.д. На место наивного подхода к понятию множества пришел аксиоматический подход [1, 2]. Аксиомы теории множеств постулируют существование некоторых неопределяемых или примитивных объектов, называемых множествами, вместе с символами и аксиомами, регулирующими их использование. Здесь существует аналогия с геометрией, где задаются неопределяемые объекты, называемые точками и плоскостями, вместе с системой аксиом, связывающих эти объекты друг с другом. Наиболее распространенными являются аксиомы теории множеств Цермело-Френкеля [1].
Множество - это неопределяемое понятие, представляющее некоторую совокупность данных. Элементы множества можно отличать друг от друга, а также определять, принадлежит ли данный элемент данному множеству. Над множествами можно выполнять операции объединения, пересечения, разности и дополнения.
Отношение - это одна из форм всеобщей взаимосвязи всех предметов, явлений, процессов в природе, обществе и мышлении. Спектр отношений на множествах многоаспектен, начиная с определения понятия множества, аксиоматики и заканчивая разбором парадоксов. Различных отношений на множестве бесконечно. Но, когда говорят об бинарных отношениях, то подразумевают отношения между двумя величинами, объектами, высказываниями.
Новые множества можно строить при помощи понятия декартового произведения (конечно, есть и другие способы, но они нас в данный момент не интересуют). Декартово произведение нескольких множеств - это множество кортежей, построенный из элементов этих множеств.
Отношение - это подмножество декартового произведения множеств. Отношения состоят из однотипных кортежей. Каждое отношение имеет предикат отношения и каждый n-местный предикат задает n-арное отношение.
Отношение является математическим аналогом понятия "таблица".
Отношения обладают степенью и мощностью. Степень отношения - это количество элементов в каждом кортеже отношения (аналог количества столбцов в таблице). Мощность отношения - это мощность множества кортежей отношения (аналог количества строк в таблице).[6]
В математике чаще всего используют бинарные отношения (отношения степени 2). В теории баз данных основными являются отношения степени [ Cкачайте файл, чтобы посмотреть картинку ]. В математике, как правило, отношения заданы на бесконечных множествах и имеют бесконечную мощность. В базах данных напротив, мощности отношений конечны (число хранимых строк в таблицах всегда конечно).[13]

ЛИТЕРАТУРА
Шапорев, С. Д. Дискретная математика : курс лекций и практических занятий / С. Д. Шапорев. – СПб. : БХВ-Петербург, 2009. – 400 с.
Александрова, Л. Г. Дискретная математика в лекциях и задачах / Л. Г. Александрова, П. Б. Кикоть, С. П. Кикоть. – Ч. 1. – М. : ГИНФО, 2000. – 228 с.
Гаврилов, Г. П. Сборник задач по дискретной математике / Г. П. Гаврилов, А. А. Сапоженко. – М. : Главная редакция физико-математической литературы изд-ва «Наука», 1977. – 368 с.
Галушкина, Ю. И. Конспект лекций по дискретной математике / Ю. И. Галушкина. – 2-е изд., испр. – М. : Айрис-пресс, 2008. – 176 с.
Гончарова, Г. А. Элементы дискретной математики : учеб. пособие / Г. А. Гончарова, А. А. Мочалин. – М. : Форум-Инфра-М, 2003. – 125 с.*
Долгих, Б. А. Основы дискретной математики / Б. А. Долгих. – М. : ГИНФО, 2002. – 104 с.
Канцедал, С. А. Дискретная математика : учеб. пособие для сред. проф. образования / С. А. Канцедал. – М. : Форум ; Инфра-М, 2007. – 221 с.*
Кикоть, П. Б. Дискретная математика в лекциях и задачах / П. Б. Кикоть, С. П. Кикоть. – Ч. 2. – М. : ГИНФО, 2002. – 192 с.
Колмогоров, А. Н. Математическая логика / А. Н. Колмогоров, А.Г. Драгалин. – изд. 2-е, стер. – М. : Едиториал УРСС, 2005. – 240 с.
Кулабухов, С. Ю. Дискретная математика / С. Ю. Кулабухов. – Таганрог, 2001. –150 с.
Просветов, Г. И. Дискретная математика : задачи и решения : учеб.-практ. пособие для вузов / Г. И. Просветов. – 2-е изд., доп. – М. : Альфа-Пресс, 2009. – 238 с.*
Тишин, В. В. Дискретная математика в примерах и задачах / В. В. Тишин. – СПб. : БХВ-Петербург, 2008. – 352 с.
Яблонский, С. В. Введение в дискретную математику : учеб пособие для вузов / С. В. Яблонский. – 2-е изд., перераб. и доп. – М. : Наука, 1986 – 384 с.*
ИНТЕРНЕТ-РЕСУРСЫ

«КнигаФонд» – электронная библиотечная система [Электронный ресурс]. – Электрон. дан. – Режим доступа : http://www.knigafund.ru/.
Библиотека «Genesis» [Электронный ресурс]. – Электрон. дан. – Режим доступа : [ Cкачайте файл, чтобы посмотреть ссылку ].
Образовательный математический сайт [Электронный ресурс]. – Электрон. дан. – Режим доступа : [ Cкачайте файл, чтобы посмотреть ссылку ].
Научная электронная библиотека [Электронный ресурс]. – Электрон. дан. – Режим доступа : [ Cкачайте файл, чтобы посмотреть ссылку ].

13PAGE 15

13PAGE 142815

\omega\colon A^n\to A(a_1,\ldots,a_n)\in A^nRoot EntryEquation Native(x\ast y)\ast z=x\ast (y\ast z)x,y,z\in Aa_1,a_2,\ldots,a_n\in Aa_1\ast a_2\ast \ldots\ast a_nx\in A\bold{0}\ast x= \bold{0}\begin{pmatrix} 0&0\\d&1 \end{pmatrix}\bold{1}\ast x=x\bold{1}'= \bold{1}'\ast \bold{1}''= \bold{1}''U\cap A=A\cap U=A,\quad U\cup A=A\cup U=Ua\in Xf\colon X\to Xx\in X\varphi_{\alpha}\circ f(x)= f(\varphi_{\alpha}(x))= f(a),\varphi_{\alpha}\circ f=\varphi_{f(a)}\varphi_{\alpha}\circ f\ne a\mathcal{A}_2= \bigl(2^{M\times M},\, \{\cup, \circ, \phantom{|}^{-1}\}\bigr).Equation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation Native\mathcal{A}_4= \bigl(\mathbb{R},\, \{\uparrow^n\colon\, n\geqslant 2\}\bigr)n\geqslant 2(\mathbb{R}\setminus\{0\}, \{:\})Equation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation Native