Дискретная математика (стр. 2 из 3)
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>02)
- сюръективна, но не инъектина, т.к. 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)
Бинарные отношения на плоскости можно отобразить с помощью графов. Элементы множества
обозначаются вершинами графов. Если пара 
, то вершины а и в соединяются звеном.