Основные понятия. Тема 8. Рекуррентные уравнения

Тема 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ

Тема 8. Рекуррентные уравнения

ТЕМА7. Конечные автоматы

Тема 6.. Основные понятия теории графов

ТЕМА 5. Многозначные функции

Тема 4. Булевы функции

Тема 3 Отношения на множествах

Тема 2 Элементы комбинаторики

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

1.1. Основные понятия

1.2. Операции над множествами

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

2.1. Основные правила комбинаторики

2.2. Выборки элементов без повторений

2.3. Выборки элементов с повторениями

2.4. Объединение комбинаторных конфигураций

2.5. Бином Ньютона

3.1. Декартово произведение множеств

3.2. Булев куб и его свойства

3.3. Понятие отношения

3.4. Операции над отношениями

3.5. Свойства отношений на множестве

3.6. Отношения эквивалентности, толерантности и порядка

3.7. Понятие отображения

3.8. Алгебраическая операция

3.9. Общие сведения об алгебраических системах

4.1. Основные определения и операции над высказываниями

4.2. Типы ПФ.

4.3. Равносильность формул

4.4. Дизъюнктивные и конъюнктивные нормальные формы

4.5 Алгоритм приведения ПФ к нормальным формам

5.1. Функции и формулы k -значной логики

5.2. Полнота и замкнутость функций k -значной логики

5.3. Особенности k – значной логики

6.1. Задачи теории графов.

6.2. Основные определения.

6.3. Степени вершин графа.

6.4. Изоморфизм графов.

6.5. Матричные способы задания графов.

6.6. Основные операции над графами.

6.7. Маршруты в графах

6.8. Связность в графах.

6.9. Матрица взаимодостижимости.

6.10. Деревья

6.11. Эйлеровы графы.

6.12 Гамильтоновы графы.

6.13. Планарные графы.

6.14. Потоки в сетях.

7.1. Понятие конечного автомата

7.2 Абстрактное определение конечного автомата

7.3. Автоматные функции и эксперименты с автоматами

7.4. Эксперименты с автоматами

8.1. Определение рекуррентного уравнения/ Решение линейного однородного рекуррентного уравнения.

8.2. Решение линейного неоднородного рекуррентного уравнения

8.3. Решение рекуррентного уравнения для чисел Фибоначчи

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

Множеством называется любая совокупность определенных и различимых между собой объектов нашей интуиции и интеллекта, мыслимая, как единое целое. Эти объекты называются элементами множества. Множества обозначаются большими буквами латинского алфавита, а их элементы – малыми. Запись xÎX означает, что элемент x принадлежит множеству X, в противном случае пишут xÏX.

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

В “определении” множества нет никаких ограничений на природу элементов. Это может быть множество студентов первого курса, множество пятен на солнце, множество зелёных яблок, множество звёзд на небе и так далее. Заметим, что в качестве элементов множеств могут быть также множества. Например: с одной стороны, группа студентов – это множество, состоящее из людей, а с другой стороны, эта группа является элементом множества всех групп в институте.

В математике часто используют числовые множества, элементами которого являются числа. Некоторые из этих множеств часто используются математиками и имеют стандартные названия и обозначения. К ним относятся множества N – натуральных, Z – целых, Q – рациональных, I – иррациональных, R – действительных чисел.

Геометрически множество действительных чисел изображается точками числовой оси, то есть прямой на которой выбрано: 1) начало отсчёта, 2) положительное направление и 3) единица масштаба.

Между множеством действительных чисел и точками числовой оси существует взаимно однозначное соответствие.

Множества точек X числовой оси называются:

a ≤ x ≤ b – отрезком,

a < x < b – интервалом,

a < x ≤ b, a ≤ x < b – полуинтервалом,

Все указанные множества называются промежутками.

Всякий интервал, содержащий точку a, называется окрестностью точки a.

Если множество содержит конечное число элементов, то оно называется конечным, а в противном случае – бесконечным.

Мощностью конечного множества называется число его элементов. Мощность множества X обозначается символом | X |.

Конечное множество обычно задаётся перечислением его элементов с заключением их в фигурные скобки, то есть

X= { x₁,x₂,,…,x_n }.

Здесь порядок, в котором записываются элементы множества, значения не имеет.

Перечисление элементов является громоздким для описания больших множеств и не применимо для бесконечных множеств. Такие множества задаются с помощью характеристических свойств. Пусть P(x) - предикат, т. е. некоторое предложение, зависящее от x. Оно может быть истинным или ложным в зависимости от x. Тогда множество задаётся в виде:

X= { x|P(x) }.

Эта запись означает, что xÎX тогда и только тогда, когда P(x) истинное утверждение.

Например: A= { 1,2 } = { xÎN | x<3 }.

Способ задания множеств с помощью характеристических свойств таит в себе некоторые опасности, которые могут привести к противоречиям. Например, парадокс Рассела заключается в том, что рассматривается множество всех множеств, которые не являются своими собственными подмножествами. То есть, К= { М|М Ï М }. Является ли множество К своим элементом? С одной стороны, если КÎК, то должно выполняться свойство, задающее множество К, т.е. К Ï К, Получили противоречие. С другой стороны, если К Ï К, то исходя из свойства, задающего К, приходим к тому, что КÎК. А это также противоречит предположению. Таким образом, любое характеристическое свойство, должно всегда приводить к осмысленному заданию множества.

Дата добавления: 2014-01-11