Использования алгоритмов и методов дискретной математики

[pic 1][pic 2][pic 3][pic 4][pic 5][pic 6][pic 7][pic 8]

Оглавление

Введение.        3

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

2.        Практические задания.        7

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

Задание 1(10).        7

Задание 2(5).        7

Задание 3(10).        8

Задание 4(4).        9

2.2. Алгебра логики.        10

Задание 1(10).        10

Задание 2(9).        10

Задание 3(1).        11

2.3. Теория графов.        13

Задание 1(15).        13

Задание 2(15).        14

Задание 3(15).        15

Задание 4(15).        16

Задание 5(14).        18

Задание 6(1).        19

Заключение.        22

Библиографический список.        23

Введение.

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

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

Задачами работы являются:

1. Решение задач по теме «Теория множеств»;

2. Решение задач по теме «Алгебра логики»;

3. Решение задач по теме «Теория графов»;

4. Ответ на теоретический вопрос «Отношение порядка».

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

Что такое отношение? Отношение, в дискретной математике, представляет собой математическую структуру, которая формально определяет свойства различных объектов. В дискретной математике различают 7 свойств отношений.

Отношение A на множестве B называется рефлексивным, если каждый элемент b множества B находится в отношении A с самим собой. Отношение A на множестве B называется антирефлексивным, если ни один элемент b множества B не находится в отношении A с самим собой.

Отношение A на множестве B называется симметричным, если из-за того, что элемент b находится в отношении A с элементом c, следует, что и элемент c находится в отношении A с элементом b. Отношение A на множестве B называется ассиметричным, если ни для каких элементов b, с из множества B не может случиться, что элемент b находится в отношении A с элементов c  и наоборот. Отношение A на множестве B называется антисимметричным, если из того что b находится в отношении с c, а c находится в отношении с b следует, что c = b. Отношение A на множестве B называется транзитивным, если для любых элементов a, b, c из множества B из того, что a находится в отношении с b, а b находится в отношении с c следует, что a находится в отношении с c. Отношение A на множестве B называется связным, если для любых элементов b, c из множества B b находится в отношении с c или c находится в отношении с b или c = b.

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

Отношение порядка, это отношение, обладающее тремя свойствами. Рефлексивностью, антисимметричностью и транзитивность. Отношения порядка принято делить на 4 порядка:

1. Нестрогий (частично). Выполняются свойства рефлексивности, антисимметричности и транзитивности.
2. Совершенный нестрогий. Выполняются свойства рефлексивности, антисимметричности, транзитивности и связности. (Связность называют полнотой).
3. Строгий. Выполняются свойства антирефлексивности, антисимметричности и транзитивности.
4. Совершенный строгий. Выполняются свойства антирефлексивности, антисимметричности, транзитивности и связности.

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

Ярким примером практического использования данного понятия, является иерархия животных по этапам эволюции (Быть прародителем).