Всё сдал! - помощь студентам онлайн Всё сдал! - помощь студентам онлайн

Реальная база готовых
студенческих работ

pencil
Узнай стоимость на индивидуальную работу!
icon Цены в 2-3 раза ниже
icon Мы работаем
7 дней в неделю
icon Только проверенные эксперты

Дискретная математика

Тип Реферат
Предмет Математика
Просмотров
1000
Скачиваний
188
Размер файла
190 б
Поделиться

Дискретная математика

bookfoldsheets0Федеральное агентство по образованию РФ

«ДИСКРЕТНАЯ МАТЕМАТИКА»

(КОНСПЕКТ ЛЕКЦИЙ)

Преподаватель: профессор,
Архипов Игорь Константинович

1. МНОЖЕСТВА

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

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

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

Бесконечное множество часто называют континуумом (например: совокупность точек на плоскости).

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

Множества задаются различными способами:

1. С помощью перечисления всех его элементов.

{0,1,2,3,4,5,6,7,8,9}

2. Алгоритмическая форма (в виде последовательности или фомул).

а) конечное

М={2;4;6;8} <=> М={m|2n;n-целое;1<=n<=4}

б) бесконечное

А={х| |х-1|<3}

2. СВОЙСТВА СЧЕТНЫХ МНОЖЕСТВ

1. Всякое подмножество счетного множества конечно или счетно

Подмножеством множества А называется множество А` все элементы которого принадлежат множеству А

Пример:

2. Сумма конечного или счетного числа конечных или счетных множеств есть конечное или счетное множество.

3. Множество всех рациональных чисел счетно.

4. Алфавитом называется любое непустое множество.

Пустое множество – множество, которое не содержит ни одного элемента.

Элементы множества под названием АЛФАВИТ называют буквами (символами).

Символом в данном алфавите любая конечная последова­тель­ность букв.

Для каждого множества А существуют множества, элементами которого являются только все его подмножества.

Такое подмножество называют семейством множеств А или булеаном. (обозначается В(А))

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

Количество элементов в векторе называется его длиной, если в векторе 2 элемента, то двойка, если n элементов, то n-ка.

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

1. Аксиома существования:Существует по крайней мере одно множество.

2. Аксиома объемности: Если множества А и В составлены из одних и тех же элементов, то они совпадают.

3. Аксиома объединения:Для произвольных множеств А и В существует множество, элементами которого являются все элементы множества А и все элементы множества В и никакие другие элементы множество не содержит.

4. Аксиома разности:Для произвольных множеств А и В существует множество, элементами которого являются те и только те элементы множества А, которые не содержатся в множестве В.

5. Аксиома существования пустого множества: Существует множество не содержащее ни одного элемента.

3. ОСНОВНЫЕ ОПЕРАЦИИ НАД МНОЖЕСТВАМИ

1. Включение (объединение)

Множество А входит (включено) в множество В, или А является подмножеством В.

Если всякий объект, обладающий свойством , также обладает свойством , то говорят, что свойство включает свойство , т.е.

2. Сумма

Сумма множеств А и В есть множество С, включающее в себя все элементы множество А и В.

Объект входит во множество если он входит во множество Аили во множество В.

3. Пересечение (произведение)

Пересечением множество А и В называется новое множество С. Элементы множества С принадлежат множеству А (обладают его свойствами) и множеству В (обладают его свойствами).

4. Вычитание (разность)

Разность множеств А и В есть множество С, элементы которого обладают свойствами множества Аи не обладают свойствами множества В или принадлежат множеству Аи не принадлежат множеству В.

5. Дополнение

Если имеется некоторое универсальное множество (универсум) U и все рассматриваемые множества есть его подмножества, то дополнением называется такое множество, элементы которого не входят в А, но принадлежат U.

ГРАФИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ

(Диаграммы Эймера, Венна)

1.


2.


В
А
3.

U
4.

4. ПРЯМОЕ ПРОИЗВЕДЕНИЕ А х В

Прямым произведением множеств А и В называется множество М всех пар (), таких, что

Если А=В, то такое произведение называется

Аналогично можно вывести операцию прямого произведения большего числа множеств.

Если в частности одинаковы то получаем

(Например, множество точек на плоскости являются прямым произведением двух множеств).

Если множества конечные, мощность произведений равна мощности произведений

5. ОСНОВНЫЕ ТОЖДЕСТВА АЛГЕБРЫ МНОЖЕСТВ

Независимость расположения:

(1)

(2)

Ассоциативность:

(3)

(4)

Дистрибутивность:

(7)

(8)

(9)

(10)

(11)

(12)

ЗАКОНЫ де Моргана

6. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ И ИХ ПРИМЕНЕНИЕ В ТЕОРИИ МНОЖЕСТВ

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

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

2. Если необходимо выделить все элементы множества, об­ладающие заданными свойствами, то это задача перечисления.

Рассмотрим следующие элементы комбинаторики, позволяющие решать вышеупомянутые задачи. К таким объектам относятся:

- перестановки (с повторением и без них);

- размещения (с повторением и без них);

- сочетания (с повторением и без них);

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

Перестановки с повторениями вычисляются по формуле:

, где - число повторений элементов каждого вида.

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

(без повторения)

(с повторением)

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

(без повторения)

(с повторением)

7. ПРИНЦИПЫ МАТЕМАТИЧЕСКОЙ ИНДУКЦИИ

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

Этот принцип заключается в следующем:

Пусть при n=1 доказательство очевидно. Принимаем гипотезу, что оно очевидно при n=k, которое не равно 1 (). Тогда, если доказано, что требуемое равенство очевидно при k+1, то равенство доказано при любом n.

8. ОТОБРАЖЕНИЕ ОТНОШЕНИЯ ФУНКЦИИ

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

Отображение – множества x во множество y определяется тем, что каждому элементу ставится в соответствие

- графическое изображение отобра­же­ния, f – обозначение отображения. Закон, который выража­ет­ся или в виде формулы или в виде алгоритма, т.е. последова­тельность действий, которые надо предпринять, чтобы полу­чить зависимость элементов множества y от элементов x. Например: всякая нумерация счетного множества является его отображением на множество натуральных чисел N.

Так как отображение может быть истолковано как соот­ве­тствие, то для того, чтобы показать, что данный элемент x поставлен в соответствие элементу y, пишут и говорят, что y есть образ элемента x при данном отображении f.

Пусть x` - подмножество множества x

y` - подмножество множества y

тогда

Совокупность элементов множества x, образом которых является y, называется прообразом и обозначается

Рассмотрим частные случаи отображения одного множества в другое.

1. Если каждый элемент множества Y имеет прообраз, являя­ющийся элементом множества X,то в этом случае отобра­жение f называется сюръективным.

2. Отображение f называется инъективным, если для каждо­го элемента существует не более одного прообраза, т.е. при любых , если .

Если отображение f сюръективно и инъективно, то оно на­зывается биеткивным или взаимооднозначным.

Рассмотрим на примере три функции, отображающие мно­жество F действительных чисел само на себя:

1) - инъективна, но не сюръективна т.к. , однако не каждый y имеет прообраз x т.к. y>0

2) - сюръективна, но не инъектина, т.к. y существует при любом x, однако для образа y существует несколько прообразов, т.к. существует несколько корней кубического уравнения

3) - биективна, т.к. x однозначно выражается через x и x однозначно выражается через y.

Два множества называются эквивалентными, если между ними можно установить биективное отображение.

ТОГДА:

Подмножество называется функцией .

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

Рассмотрим, например, взаимно однозначное отображе­ние множества R на R1, где R1 есть множество всех положи­тельных чисел . Обратным ему будет отображение . Для таких отображений справедливо следующее тождество:

9. КОМПОЗИЦИЯ

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

Для композиции справедливо следующие отображения:

- коммутативное -

- ассоциативное -

10. БИНАРНЫЕ ОТНОШЕНИЯ

Квадратом множестваА называется декартово произведение множества само на себя

Бинарным отношениемТ в множестве А будем называть подмножество его квадрата

1. Отношение выполняется для пар (6,8) (6,6)

2. Отношение имеет общий делитель не равный 1. Выполняется для пар (6,4)(4,2) (8,8) но не выполняется для пар (5,4) (3,8)

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

4. Областью значений (изменением бинарного отношения) называется множество , подчиненное условию

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


(1)


(2)

Бинарные отношения на плоскости можно отобразить с помощью графов. Элементы множества обозначаются вершинами графов. Если пара , то вершины а и в соединяются звеном.

Например:

(ав)(вс)(ас)(аа)


11. ОТНОШЕНИЯ ЭКВИВАЛЕНТНОСТИ

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

СВОЙСТВА:

1. 1.1 Пусть - бинарное отношение, - область его задания, тогда называется рефлексивным, если , граф таких отношений имеет вид петли при каждой вершине


1.2 называется антирефлексивным, если

2. 2.1 Отношение может быть симметричным, если

(изображается любым графом)

2.2 Антисимметричным, если (изображается ориентированным графом)

3. 3.1 Транзитивным. Отношение называется транзитивным, если (изображается транзитивным графом – все вершины пересекаются)

Если для бинарного отношения соблюдается три условия: рефлексивность, симметричность и транзитивность, то такое отношение называется эквивалентностью.


12. МАТРИЦЫ И ГРАФЫ

Понятие матрицы. Виды матриц. Свойства матриц. Линейные операции над матрицами. Единичные матрицы. Обратные матрицы

Матрицей называется прямоугольная таблица чисел размером , где m – число строк, а n – число столбцов.

Если m=n – матрица называется квадратной.

Если m-1матрица-строка.

Если n=1матрица-столбец.

Все числа, входящие в матрицу называются ее элемен­тами. Если все элементы состоят их нулей, то это нулевая матрица, она играет роль нуля в матричном исчислении.

Рассмотрим некоторые линейные операции над матрицами:

1. Сумма

Исходя из определения можно складывать и вычитать матрицы только одного размера.

2. Произведение матрицы на число называется матрица, где каждый элемент матрицы умножается на это число.

3. Матрица умножается на матрицу по правилу строка на столбец



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

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

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

, играет роль единицы в матричном исчислении.

Если такую матрицу умножить на другую матрицу (при возможности умножения) даст исходную матрицу.

- дельта Кронекера

5. Обратной матрицей называется матрица, которая , заметим, что Е – квадратная, соответственно тоже квадратные.

6. (определитель), если , то обратная матрица существует, если , то матрица называется вырожденная.

Нахождение обратной матрицы

1. Метод присоединенной матрицы

1.

2.

3.

3.1 (взаимная)

3.2

4.

5.

2. Метод элементарных преобразований


Нет нужной работы в каталоге?

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

Цены ниже, чем в агентствах и у конкурентов

Вы работаете с экспертами напрямую. Поэтому стоимость работ приятно вас удивит

Бесплатные доработки и консультации

Исполнитель внесет нужные правки в работу по вашему требованию без доплат. Корректировки в максимально короткие сроки

Гарантируем возврат

Если работа вас не устроит – мы вернем 100% суммы заказа

Техподдержка 7 дней в неделю

Наши менеджеры всегда на связи и оперативно решат любую проблему

Строгий отбор экспертов

К работе допускаются только проверенные специалисты с высшим образованием. Проверяем диплом на оценки «хорошо» и «отлично»

1 000 +
Новых работ ежедневно
computer

Требуются доработки?
Они включены в стоимость работы

Работы выполняют эксперты в своём деле. Они ценят свою репутацию, поэтому результат выполненной работы гарантирован

avatar
Экономика
Маркетинг
Информатика
icon
109736
рейтинг
icon
2698
работ сдано
icon
1237
отзывов
avatar
Математика
Физика
История
icon
103537
рейтинг
icon
5274
работ сдано
icon
2373
отзывов
avatar
Химия
Экономика
Биология
icon
74287
рейтинг
icon
1858
работ сдано
icon
1172
отзывов
avatar
Высшая математика
Информатика
Геодезия
icon
62710
рейтинг
icon
1046
работ сдано
icon
598
отзывов
Отзывы студентов о нашей работе
48 866 оценок star star star star star
среднее 4.9 из 5
ФГБОУ ВО "ЗГУ"
Работа была выполнена досрочно (очень быстро ). Реферат был выполнен без замечаний . Испол...
star star star star star
Удгу
Все отлично, очень быстро и качественно, работа принята без замечаний. Спасибо.
star star star star star
Балтийская Государственная Академия Рыбопромыслового Флота (БГАРФ)
Видно, что автору пока не хватает опыта в некоторых моментах связанных с оформлением. испр...
star star star star star

Последние размещённые задания

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

только что

Дана поза номер 11, сделать рисунок и все задания к ней

Контрольная, Анатомия и физиология человека

Срок сдачи к 5 дек.

только что

Сделать все то, что написано в файле

Другое, IT-технологии, программирование

Срок сдачи к 7 дек.

1 минуту назад

Как можно скорее математика 1 курс меда

Контрольная, Математика

Срок сдачи к 1 дек.

2 минуты назад

Решить 4 номера под вариантом 27

Решение задач, Высшая математика

Срок сдачи к 4 дек.

2 минуты назад
2 минуты назад

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

Реферат, Физическая культура и спорт

Срок сдачи к 10 дек.

3 минуты назад

Тема: Основные фонды План работы: 1. Основные фонды предприятия

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

Срок сдачи к 19 дек.

3 минуты назад

Написать подробный реферат, но называется как курсовая Вариант 2

Курсовая, Техническое обслуживание и ремонт кузовов автомобилей

Срок сдачи к 10 дек.

3 минуты назад

Доклад по финансам

Доклад, финансы

Срок сдачи к 10 дек.

4 минуты назад

Инклюзивное образование: проблемы и перспективы»

Эссе, Педагогика

Срок сдачи к 18 дек.

4 минуты назад

Ответить на вопросы

Другое, Гражданское право

Срок сдачи к 3 дек.

5 минут назад

Сделать презентацию в ворде,10-15 слайдов

Другое, Отделение Туризм

Срок сдачи к 3 дек.

5 минут назад

составить курсовой проект по плану

Курсовая, Структуры рудных полей и месторождений, горное дело

Срок сдачи к 11 дек.

5 минут назад
6 минут назад

Социальная инженерия

Реферат, Информатика

Срок сдачи к 5 мар.

6 минут назад

Создание интерактивного демонстрационного материала по физической...

Курсовая, физическая культура

Срок сдачи к 18 дек.

6 минут назад

Эссе о периоде 1945 - 1953 в ссср

Эссе, История

Срок сдачи к 2 дек.

7 минут назад
planes planes
Закажи индивидуальную работу за 1 минуту!

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

«Всё сдал!» — безопасный онлайн-сервис с проверенными экспертами

Используя «Свежую базу РГСР», вы принимаете пользовательское соглашение
и политику обработки персональных данных
Сайт работает по московскому времени:

Вход или
регистрация
Регистрация или
Не нашли, что искали?

Заполните форму и узнайте цену на индивидуальную работу!

Файлы (при наличии)

    это быстро и бесплатно