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

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

математическая статистика.

Тема5.1.Множество. Алгебра множеств. Случайные величины.

Математическим понятием, отражающим объединение некоторых объектов, предметов или понятий в единую совокупность, является понятие множества. Это понятие в математике является неопределяемым.

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

Множества А и В называются равными, если они содержат одни и те же элементы. Например, равны множества А={1;2;3} и В={3;2;1}. Равенство множеств А и В записываются в виде: А=В.

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

Множество - совокупность некоторых объектов, объединенных по какому-либо признаку.

Множество A называется подмножеством множества B, если каждый элемент множества A является элементом множества B. Обозначается:

(«А включено в В»).

Пересечением множеств А и В называется множество, состоящее из элементов, каждый из которых принадлежит множеству А и множеству В. Обозначается:

.

Объединением множеств А и В называется множество, состоящее из элементов, каждый из которых принадлежит хотя бы одному из этих множеств. Обозначается:

.

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

.

Симметрическая разность двух множеств А и В называется множество, элементы которого принадлежат только одному из множеств. Обозначение:

.

Некоторые простейшие логические символы:

1. - означает «из следует »;

2. - « и равносильны»;

3. - «принадлежит»;

4. - «для любого», «для всякого»;

5. - «существует», «найдется»;

6. : - «имеет место», «такое что»;

7. N – множество всех натуральных чисел;

8. Z – множество всех целых чисел;

9. Q – множество всех рациональных чисел;

10. R – множество всех действительных чисел;

11. С – множество всех комплексных чисел.

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

Рассмотрим подробнее эти соединения:

1) Если в некотором множестве переставлять местами элементы, оставляя неизменным их количество, то каждая полученная таким образом комбинация называется перестановкой. Общее число перестановок из m элементов обозначается P_m и вычисляется по формуле:

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

.

Перестановки являются частным случаем размещений.

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

.

4) Также одним из вариантов комбинаций являются перестановки с повторяющимися элементами. Если среди т элементов имеется одинаковых элементов одного типа, т₂ одинаковых элементов другого типа и т.д., то при перестановке этих элементов всевозможными способами получаем комбинации, количество которых определяется по формуле:

.

5) Если при выборке m элементов из n элементы возвращаются обратно и упорядочиваются, то говорят, что это размещения с повторениями. Размещения с повторениями могут отличаться друг от друга элементами, их порядком и количеством повторений элементов. Число всех размещений из n элементов по m с повторениями обозначается символом и вычисляется по формуле:

.

6) Если при выборке m элементов из n элементы возвращаются обратно без последующего упорядочивания, то говорят, что это сочетания с повторениями. Число всех сочетаний из n элементов по m с повторениями обозначается символом и вычисляется по формуле:

.

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

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

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

События называются несовместными, если появление одного из них исключает появление других.

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

Полной группой событий называется совокупность всех возможных результатов испытания.

Элементарным исходом называется каждый из возможных результатов испытания.

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

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

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

.

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

.

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

Случайные величины можно разделить на две категории.

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

Это множество может быть как конечным, так и бесконечным.

Непрерывной случайной величиной называется такая величина, которая может принимать любые значения из некоторого конечного или бесконечного промежутка.

Число возможных значений непрерывной случайной величины бесконечно.

Соотношение между возможными значениями случайной величины и их вероятностями называется законом распределения дискретной случайной величины.

Закон распределения может быть задан аналитически, в виде таблицы или графически.

Таблица соответствия значений случайной величины и их вероятностей называется рядом распределения.

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

Определим математические операции над дискретными случайными величинами. Суммой (разностью, произведением) дискретной случайной величины X, принимающей значения с вероятностями и дискретной случайной величины , принимающей значения с вероятностями , называется дискретная случайная величина ( , ), принимающая значения ( , ) с вероятностями для всех указанных значений i и j. В случае совпадения некоторых сумм (разностей , произведений ) соответствующие вероятности складываются. Произведением дискретной случайной величины на число c называется дискретная случайная величина cX, принимающая значения с вероятностями .

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

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

.

1) .

2) .

3) .

4) .

Пусть производится п независимых испытаний, вероятность появления события А в которых равна р.

Теорема. Математическое ожидание М(Х) числа появления события А в п независимых испытаниях равно произведению числа испытаний на вероятность появления события в каждом испытании.

.

Дисперсией (рассеиванием) дискретной случайной величины называется математическое ожидание квадрата отклонения случайной величины от ее математического ожидания.

.

Теорема. Дисперсия равна разности между математическим ожиданием квадрата случайной величины Х и квадратом ее математического ожидания.

.

1) .

2) .

3) .

4) .

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

.

Средним квадратическим отклонением случайной величины Х называется квадратный корень из дисперсии

.

Теорема. Среднее квадратичное отклонение суммы конечного числа взаимно независимых случайных величин равно квадратному корню из суммы квадратов средних квадратических отклонений этих величин

.

Контрольные вопросы

1. Правила комбинаторики.

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

3. Свойства операций над множествами.

4. Теория булевых функций. Булевая алгебра.

5. Определение и способ задания булевых функций.

6. Закон распределения случайной величины.

7. Математическое ожидание и дисперсия случайной величины.

8. Неравенство Чебышева.