Инфоурок › Математика ›Другие методич. материалы›Курсовая работа по дискретной математике

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

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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. Пусть — произвольное непустое множество и — натуральное число. Любое отображение $\omega\colon A^n\to A$ называют n-арной (или n-местной) операцией на множестве .

Таким образом, согласно приведенному определению, n-арная операция и каждому кортежу $(a_1,\ldots,a_n)\in A^n$ однозначно сопоставляет элемент $b\in A$ . Компоненты кортежа называют при этом аргументами операции $\omega$ , а — результатом применения операции и к аргументам $a_1,\ldots,a_n$ .

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

$b=\omega (a_1,\ldots,a_n)$ или $b= a_1\ldots a_n\omega$ .

Обычно, если , пишут $a_1\omega a_2$ . При и говорят соответственно об унарной операции и бинарной операции.

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

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

Рассмотрим бинарную операцию на множестве , обозначив ее звездочкой $(\ast)$ . Эту операцию называют:

1) ассоциативной, если $(x\ast y)\ast z=x\ast (y\ast z)$ для любых $x,y,z\in A$ ;
2) коммутативной, если $x\ast y=y\ast x$ для любых $x,y\in A$ ;
3) идемпотентной, если $x\ast x=x$ для любого $x\in A$ .

Ассоциативность операции $\ast$ позволяет для любых элементов $a_1,a_2,\ldots,a_n\in A$ однозначно трактовать результат выражения $a_1\ast a_2\ast \ldots\ast a_n$ .

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

Элемент $\bold{0}$ множества называют левым (правым) нулем относительно данной операции $\ast$ , если $\bold{0}\ast x=\bold{0}$ $(x\ast\bold{0}=\bold{0})$ для любого $x\in A$ .

Если $\bold{0}'$ — левый нуль, а $\bold{0}''$ — правый нуль, то они совпадают. Действительно, если $\bold{0}'$ и $\bold{0}''$ существуют, то они совпадают, так как $\bold{0}'= \bold{0}'\ast \bold{0}''= \bold{0}''$ , и в этом случае говорят просто о нуле относительно операции. Из приведенных равенств следует, что нуль единственный и для него одновременно выполнены оба равенства $\bold{0}\ast x= \bold{0}$ и $x\ast \bold{0}= \bold{0}$ .

Пример 2.1.

а. На множестве целых чисел $\mathbb{Z}$ нулем относительно операции умножения будет число 0.

б. На множестве квадратных матриц вида $\begin{pmatrix}a&0\\b&1\end{pmatrix}$ , где элементы и — действительные числа, любая матрица вида $\begin{pmatrix} 0&0\\d&1 \end{pmatrix}$ будет правым нулем относительно операции умножения.

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

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

Элемент $\bold{1}$ множества называют левым (правым) нейтральным элементом относительно операции $\ast$ , если $\bold{1}\ast x=x$ $(x\ast\bold{1}=x)$ для любого элемента $x\in A$ . Для левого $\bold{1}'$ ; и правого $\bold{1}''$ нейтральных элементов, если они оба существуют, выполнены равенства $\bold{1}'= \bold{1}'\ast \bold{1}''= \bold{1}''$ , согласно которым они совпадают. В этом случае элемент $\bold{1}$ , который является и левым нейтральным, и правым нейтральным, единственный, и его называют просто нейтральным элементом.

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

На множестве квадратных матриц вида $\begin{pmatrix}a&0\\b&0\end{pmatrix}$ , где элементы и — действительные числа, любая матрица вида $\begin{pmatrix} 1&0\\d&0 \end{pmatrix}$ будет правым нейтральным элементом по операции умножения.

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

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

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

Пример 2.3. а. Пусть — универсальное множество. Теоретико-множественные операции $\cup,\,\cap$ на множестве являются идемпотентными, ассоциативными и коммутативными, причем пустое множество является нулем относительно пересечения и нейтральным элементом относительно объединения $\varnothing\cap A=A\cap \varnothing= \varnothing,\quad \varnothing\cup A= A\cup \varnothing= A,$ тогда как универсальное множество есть нуль относительно объединения и нейтральный элемент относительно пересечения $U\cap A=A\cap U=A,\quad U\cup A=A\cup U=U$

Операция $\setminus$ (разность множеств) не является ассоциативной, так как $A \setminus (B \setminus C)\ne (A \setminus B)\setminus C$ .

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

в. Пусть — произвольное множество, содержащее не менее двух элементов. На множестве всех отображений из в с операцией композиции отображений постоянное отображение $\varphi_{\alpha}$ , переводящее любой элемент $x\in X$ в фиксированный элемент $a\in X$ , будет правым нулем, но не будет нулем относительно композиции отображений.

Действительно, для любого отображения $f\colon X\to X$ и любого $x\in X$ имеем

$f\circ\varphi_{\alpha}(x)= \varphi_{\alpha}(f(x))= a= \varphi_{\alpha}(x)$ , то есть $f\circ\varphi_{\alpha}= \varphi_{\alpha}$ ,

что и означает, что $\varphi_{\alpha}$ — правый нуль относительно операции композиции на множестве отображений из в . Однако для любого $x\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$ . Значит, $\varphi_{\alpha}$ не является левым нулем относительно операции композиции.

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

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

Поскольку алгебра задается ее носителем и сигнатурой, мы будем в записи обозначать алгебру как упорядоченную пару множеств $\mathcal{A}=(A,\Omega)$ , полагая, что первая компонента этой пары есть носитель, а вторая — сигнатура. Подчеркнем, что алгебра — это не просто носитель и не просто сигнатура, а „синтез" этих двух объектов.

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

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

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

В ряде случаев указание носителя алгебры предполагает и задание определенной сигнатуры. В этом случае для упрощения пишут не $\mathcal{A}=(A,\Omega)$ , а просто $\mathcal{A}=A$ и говорят "элемент алгебры $\mathcal{A}$ ", имея в виду элемент носителя этой алгебры.

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

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

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

$\mathcal{A}_2= \bigl(2^{M\times M},\, \{\cup, \circ, \phantom{|}^{-1}\}\bigr).$
носителем которой является множество всех подмножеств множества упорядоченных пар на , т.е. множество всех бинарных отношений на множестве , а сигнатура состоит из операций объединения, композиции бинарных отношений и взятия обратного отношения.[7]

в. На множестве $\mathbb{R}$ действительных чисел можно, например, определить такую алгебру:

$\mathcal{A}_3= \bigl(\mathbb{R},\, \{+, \cdot, 0, 1\}\bigr),$ сигнатура которой состоит из операций сложения, умножения, а также двух нульарных операций, обозначающих два особых числа 0 и 1. Обратим внимание на то, что числа 0 и 1 в данном случае являются соответственно нулем и нейтральным элементом относительно умножения, а число 0 также играет роль нейтрального элемента относительно сложения. Все предыдущие примеры алгебр были алгебрами с конечной сигнатурой, т.е. с сигнатурой, состоящей из конечного числа операций. Однако несложно построить пример алгебры с бесконечной сигнатурой. Например, алгебра $\mathcal{A}_4= \bigl(\mathbb{R},\, \{\uparrow^n\colon\, n\geqslant 2\}\bigr)$

на множестве действительных чисел $\mathbb{R}$ с операцией $\uparrow^n$ возведения в натуральную степень $n\geqslant 2$ имеет счетную сигнатуру. Далее будут приведены примеры алгебр и с нечетными сигнатурами.

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

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

Точно так же множество действительных чисел $\mathbb{R}$ с операцией деления действительных чисел не является алгеброй, поскольку результат деления не определен при нулевом делителе. Пара же $(\mathbb{R}\setminus\{0\}, \{:\})$ есть алгебра.

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

Для алгебры $\mathcal{A}=(A,\Omega)$ обозначим через $\Omega^{(n)}$ подмножество сигнатуры $\Omega$ , состоящее из всех n-арных операций. Тогда $\Omega=\mathop{\cup}\limits_{n\geqslant 0}\Omega^{(n)}$ . Так, для алгебры $\mathcal{A}_1$ в примере 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 с.*

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

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

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

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

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

Скачать материал

Скачать материал "Курсовая работа по дискретной математике"

Как учитель может зарабатывать на Инфоуроке?

Скачать материал

Найдите материал к любому уроку, указав свой предмет (категорию), класс, учебник и тему:

6 661 702 материала в базе

Найти материалы

Скачать материал

Другие материалы

docx

Рабочая программа по предмету математика 7 класс (Мордкович +Атанасян), 5 час.

Рейтинг: 5 из 5

08.01.2016
1875
5

docx

Практическая работа по теме "Формулы двойного аргумента" для 10 класса

08.01.2016
2561
33

zip

Исследовательская работа "Калтан в цифрах"

08.01.2016
1143
0

docx

КВН между 9-ми классами.

08.01.2016
765
1

docx

"Квадрат теңдеу. Квадрат теңдеу түрлері" 8 класс

08.01.2016
615
0

pptx

Применение ИКТ технологий на уроках математики

08.01.2016
858
2

docx

Урок по алгебре и началам анализа на тему "Решение тригонометрических неравенств" (10 класс)

Рейтинг: 3 из 5

08.01.2016
1602
13

Вам будут интересны эти курсы:

Оставьте свой комментарий

Авторизуйтесь, чтобы задавать вопросы.

Скачать материал
- 08.01.2016 6587
- DOCX 455.5 кбайт
- 45 скачиваний
- Оцените материал:
Настоящий материал опубликован пользователем Воеводина Анна Викторовна. Инфоурок является информационным посредником и предоставляет пользователям возможность размещать на сайте методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт

Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.
Удалить материал
Автор материала

Воеводина Анна Викторовна
- На сайте: 8 лет и 3 месяца
- Подписчики: 0
- Всего просмотров: 33352
- Всего материалов: 11