Дискретная математика-самостоятельный раздел математики,изуч-й св-ва структур,имеющих дискретный характер.
Д.М-раздел математики содержащий следующие направления: а) Теория множеств, б) Элементы математической логики, в) Теория булевых.фун. г) Алгебра вычетов, д)Теория Графов.
Объекты Д.М представляют собой комбинации некот.абстракных символов,над которыми осущ-я некот-е манипуляции.
Для объекта важно одно:входит он в состав мн-ва или нет.
Множества. Под множеством будем понимать совокуп.Каких-либо объектов произвольной природы объединенных некот.Общим св-ом.
Способы задания множеств: а)Словестный, б)Перечислением всех элементов мн-ва, в)Указанием основного признака, г)Геометрически
Виды множеств: Множество натуральных чисел-числа кот.использ-я при счете.
Целые числа-числа натуральные, им противоположные и 0. (-10эZ)
Множ-во Рациональных чисел-число вида дробь: m/n где m э Z, а n э N (0.7 э Q: )
Мн-во Иррациональных-число кот.не явл-ярациональным. (-17.3333355 э J)
Мно-во Действительных чисел-числовое мн-во образов.множеством рациональнм и иррациональным множ-вом (R).
Операции над множествами: а) Пересечение мн-в. Пересечением множеств А и В назыв.множ-во сост.из тех и только тех элементов,которые принадлежат одновременно и А и В.
Универсальным множеством называется множество состоящее из всех возможных элементов удовлетворяющих характеристич-у св-ву множеств. (u).
Дополнением к множеству А называют множество, состоящее из тех и только тех элементов, кот. не принадлежат множеству А.
Мощность и классификация множеств. Мощность множества-количество элементов множества |м|.
Два множества называют-я равными, если они составлены из одинаковых елементов.
Два множества назыв-я эквивалентными , если между их элементами можно установить взаимно-однозна-е соответсвие.
Синонимом эквивалентности множеств-явл-я равномощное множество.
Конечное множество. Конечное-если оно содержит конечное число элементов(конкретное число) пустое, студ.гр.АС1-21
Беконечное-множество-не явл-я конечным. Оно бывает: Счетное-если оно эквивалентно множ-ву натуральных чисел. (N, Z, Q)
Несчетное-бесконечное множ-во явл-я счетным. (R, J)
Подмножество. Множество к называется подмножество множества м, если любой элемент множества к явл-я элементов множества м. (к с м) (n с z)
Множество
всех подмножеств данного множества
называется булеаном множества. (
)
|
|=
=8
----
Декартово множество. Декартовым произведением мно-в А и В (АхВ) называется множество упорядоченных пар, таких, что первый элемент пары явл-я элементом множ-ва А, а второй элементом множества В. А х В { (а,в) |а э А, в э В}.
Бинарные отношения. Бинарным отношением на мн-ве М назыв-я подмножество второй декартовой степени множества М.
Способы задания Б.О: Геометрически, и аналитически.
Б/О R на множестве М называется рефлексивным если любой элемент множества М всегда находится в данном Б/О сам с собой. (сидеть на одном раду в А210)
Б/О R на множестве М называется антирефлексивыным, если любой элемент мн-ва М всегда находится в данном Б.О сам с собой.
Б/О R на множестве М называется симметричным, если для любых двух несовпадающих эл-в множества М, из того , что первый элемент находится со вторым в данном Б.О , всегда следует, что и 2 также нахоится в данном Б.О с первым.
Б/О R на множестве М называется антисимметричным, если для любых двух несовпадающих элементов мн-ва М из того, что 1 находится со вторым, всегда следует, что и второй не находится в данном Б.О с 1 .
Б/О R на множестве М называется транзитивным, если для любых трех эл-в множ-ва М из того, что 1 со 2, а 2 с 3находятся в Б.О, всегда следует, что 1 с 3 находятся в Б.О.(для 3 студентов:если 1 со 2, а 2 с 3 сидят на одном ряду, следует что и 1 с 3 сидимт на одном ряду)
Б/О R на множестве М называется антитранзитивным если для любых трех попарно-несовпадающих эл-в множ-ва М из того, что 1 со 2, а 2 с 3, всегда нах.в Б.О следует, 1 с 3-никогда не нах-я в Б.О.
Виды Б.О: а) Б.О R назы-я отношением эквивалентности, если оно одновременно обладает 3 св-ми( рефлекс,симм,транзитивным)
Фактор множества-множество классов эквивалентности одного множества относительно другого.
б) Б.О R называется отношение порядка на множестве если оно обладает св-ми(антисимм,транзитив)
Отношение нестрого порядка должно удовлетворять трем усл-ям(рефлексив,антисимм,транзитив)
Отнош.строго порядка(антирефлекс,антисимм,транзитив).
Высказывание –повествовательное предложение о кот.в данный момент времени можно сказать: истинное оно или ложное, но не то и другое одновременно. (Функция logx-является логарифмической функцией!-истина) (Фобос-спутник юпитера!-ложь),
Виды-высказываний: а) Элементарные-высказывание не содержит логических связок(и,или,не,если,то).
б) Составным назыв-я высказывание содержащее логич.связки.
В алгебре высказываний интересуются не только содержанием высказыванием, сколько его истинностным значением.(истина,ложь)
Отрицание. Отрицанием высказывания А-назыв.высказывание истинное,если А ложное, и ложное,если А-истинное. (НЕ)
Конъюнкцией двух высказываний назыв-я высказывание истинное в том и только в том случае, когда оба высказывания истинные. (и, а, но,как,так)
Дизъюнкцией двух высказываний назыв-я высказывание ложное в том случае,когда оба высказывание-ложные.(или,либо А,либо В,либо оба вместе)
Импликацией двух высказываний наз.высказывание-ложное в том случае,когда первое высказывание-истинное, а второе-ложное. (если,то,из А следует В, значит)
Эквиваленцией двух высказываний назыв-я высказывание истинное, в том случ, когда оба высказывания либо истинные,либо ложные. (тогда и только тогда,необходимо)