Симметричные бинарные отношения

Бинарное отношение R называется симметричным на множестве A, если для любой пары выполняется, что пара также принадлежит множеству R.

Пример 4. Пусть , а R – отношение равенства, т.е. или . Тогда взяв, например, пару , замечаем, что симметричная ей пара . Отсюда следует, что отношение равенства на множестве А симметрично.

Раздел 2 «Комбинаторика»

Лекция 2.1 «Комбинаторика»

Вопросы:

1.Введение в комбинаторику.

2.Основные правила комбинаторики (правило суммы, правило произведения).

3.Комбинаторные конструкции (перестановки).

Правило произведения. Если элемент A можно выбрать из множества элементов n способами и для каждого такого выбора элемент B можно выбрать m способами, то два элемента (пару) A и B можно выбрать mn способами.

Пример 1. Сколько можно составить различных чайных пар, каждая из которых состоит из чашки из блюдца, если всего есть 7 чашек и 5 блюдец?

Решение: Выберем сначала чашку. В пару ей можно выбрать любое из 5 блюдец. Таким образом, получаем 5 разных пар, содержащих эту чашку. Так как всего 7 чашек, то число различных пар равно 5∙7 = 35.

Правило суммы. Если элемент A можно выбрать из множества элементов n способами, а элемент B можно выбрать другими m способами, то выбор «либо A, либо B» можно осуществить m + n способами.

Пример 2. Сколько можно составить комплектов из двух предметов, если имеется 7 чашек, 5 блюдец и 6 ложек?

Решение: пары можно составить так: чашка и блюдце, чашка и ложка, ложка и блюдце. Количество пар чашка и блюдце равно 5∙7 = 35, пар чашка и ложка 5∙6 = 30, пар ложка и блюдце 6∙7 = 42. Так как можно выбрать либо одну пару, либо другую, либо третью, то полученные значения, по правилу суммы необходимо сложить: 35+30+42=107.

Произведение первых n натуральных чисел называется факториал ом и имеет особое обозначение: (читается «Эн факториал»), т.е.

Например, , , , и т.д.

Принято считать, что .

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

В общем случае пусть имеется n предметов k различных типов. Число различных перестановок с повторениями из элементов 1-го типа, элементов 2-го типа, …, элементов k -го типа, где равно:

Пример 3. Сколько различных анаграмм можно составить из слова «ЛИНИЯ»? (анаграммами называются перестановки букв некоторого слова).

Решение: В этом слове 2 буквы «И». Временно будем считать их разными «И₁» и «И₂». Тогда все буквы различны и получаем слов. Однако те слова, которые получаются друг из друга перестановками букв «» и «» на самом деле одинаковы. Две буквы можно переставлять способами. Поэтому всего получаем различных слов .

Лекция 2.2 «Комбинаторика»

Вопросы:

1.Комбинаторные конструкции (размещения, сочетания).

Размещения без повторений.

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

При составлении k – размещений без повторений из n предметов нам надо сделать k выборов.

На первом шаге можно выбрать любой из имеющихся n предметов. Если этот выбор уже сделан, то на втором шаге мы сможем выбрать из оставшихся предметов – ведь повторять сделанный выбор нельзя. Аналогично, на третьем шаге для выбора остаётся только свободных предмета; на четвёртом – предмета, …, на k -м шаге – предметов.

Поэтому, по правилу произведения, получаем, что

Эту формулу можно записать иначе, используя символ n! Умножим и разделим правую часть равенства на , получим:

Размещения с повторениями.

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

Выведем формулу для вычисления количества размещений с повторениями . Выбор первого элемента выборки можно осуществить n способами. Так как мы рассматриваем выборки с возвращениями, т.е. выбранный элемент возвращается во множество и, значит, может быть выбран повторно, то число способов выбрать 2-й элемент тоже равно n. Аналогично, число способов выбрать 3-й, 4-й, …, k- й элемент так же равно n. Поскольку нас интересуют упорядоченные выборки, то, по правилу произведения, находим, что общее число различных размещений с повторениями из n элементов равно , т.е.

Сочетания без повторений.

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

Формула для числа сочетаний легко получается из выведенной ранее формулы для числа размещений без повторений. Пусть у нас имеется n элементов, из которых мы составляем всевозможные k – сочетания. Всего таких сочетаний будет . Теперь внутри каждого k – сочетания образуем всевозможные перестановки, отличающиеся друг от друга порядком следования в них элементов. Таких перестановок в каждом сочетании будет , поэтому различных k -расстановок из элементов, отличающихся друг от друга либо составом элементов, либо порядком их следования, будет . Но такие k – расстановки называются размещениями, т.е. . Откуда получаем: или

Сочетания с повторениями.

Пусть имеются предметы n различных типов. Сочетанием с повторением называется расстановка из k предметов, если не принимать во внимание порядок их размещения (т.е. различные расстановки должны отличаться хотя бы одним предметом, но не их порядком).

Пусть среди k предметов n различных типов: элементов 1-го типа, элемента 2-го типа, …, элементов n -го типа. Причем . Тогда число перестановок с повторениями обозначается и вычисляется по формуле:

Раздел 3 «Введение в теорию вероятностей»

Лекция 3.1 «Введение в теорию вероятностей»

Вопросы:

1.Основные определения теории вероятностей.

2.Классическое, статистическое, геометрическое определение вероятности события.

3.Действия над событиями.

4.Теоремы суммы и произведения вероятностей.

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

Например, если опыт состоит в бросании монеты, тогда событиями будут: A ={появление герба} или В ={появление решки}. Если опыт состоит в стрельбе по мишени, то событиями являются A ={попадание в цель} или В ={промах}.

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

Вероятность события – это численная мера степени объективной возможности этого события. Вероятность события А обозначается .

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

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

Таким образом, численное значение вероятности события изменяется от 0 до 1, значит .

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

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

Относительной частотой случайного события называют отношение , где - количество появлений события, - общее число опытов.

Например, студент Петров 100 раз подбросил монету, при этом появилось 52 орла. Значит, относительная частота появления орла равна 0,52. А в 18 веке французский естествоиспытатель Жорж Луи де Бюффон провел 4040 опытов с подбрасыванием монеты, при этом орел выпал 2048 раз. Таким образом, относительная частота появления орла равна .

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

Недостатком статистического определения вероятности является его неоднозначность. Например, в рассмотренных выше примерах в качестве вероятности появления орла можно принять и 0,52 и 0,5069

Введем некоторые вспомогательные понятия.

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

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

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

Пример 1. Опыт состоит в вынимании одной карты из колоды в 36 карт. Рассматриваются следующие события:

={появление карты червовой масти}; ={появление карты пиковой масти}; ={появление карты бубновой масти}.

Определите, образуют ли эти события полную группу; являются ли несовместными; являются ли равновозможными?

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

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

Пример 2. Если опыт состоит в вынимании одной карты из колоды в 36 карт, то появление червовой карты, пиковой карты, бубновой карты и трефовой карты являются случаями, т.к. события являются полной группой (никакой другой масти появиться не может), несовместны и равновозможны.

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

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

Если результаты опыта сводятся к схеме случаев, и - общее число случаев, - число случаев, благоприятных событию , тогда вероятность события вычисляется по формуле:

– классическая формула вероятности.

Пример 3. В коробке находятся 4 белых и 5 черных шаров. Из коробки наугад вынимается один шар. Найти вероятность того, что этот шар будет белым.

Решение: Событие А={появление белого шара}. Общее число случаев , число случаев, благоприятных событию . Тогда .

Статистическое и классическое определение вероятности неприменимо к испытаниям с бесконечным числом исходов. Поэтому для исследования таких событий необходимо ввести еще одно определение вероятности. Для этого введем несколько предположений:

1. Размер бросаемого предмета (фишки, монеты, мяча, шайбы и т.д.) сколь угодно мал по сравнению с размером поверхности, куда он попадает.

2. Брошенный предмет с одинаковой вероятностью попадает в любое место поверхности.

Тогда геометрическая вероятность определяется как отношение размера исследуемой части поверхности к размеру всей поверхности.

Действия над событиями.

Суммой двух событий А и В называется событие С, состоящее в появлении хотя бы одного из событий А или В (или обоих вместе).

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

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

Пример 4. В городе объявлен розыск четырех опасных преступников. Дл того, чтобы предотвратить утечку информации, майор Иванов зашифровал сообщения первыми буквами фамилий преступников:

П – обнаружен преступник Пупков; Р – обнаружен преступник Ручников; Д – обнаружен преступник Дундуков; Т – обнаружен преступник Трошкин.

а). Как зашифровать сообщение, что обнаружен по крайней мере один из преступников Пупков или Ручников?

б). Как зашифровать сообщение, что обнаружены сразу два преступника Дундуков и Трошкин?

в). Что означают следующие шифровки Р + Д, ПТ, , ?

Решение: а). данное событие состоит в появлении хотя бы одного из событий П или Р, значит шифруем как П + Р.

б). событие состоит в одновременном появлении событий Д и Т, т.е. равно произведению событий ДТ.

в). Исходя из определения суммы, произведения событий и противоположного события, расшифруем:

Р + Д – пойман хотя бы один из преступников Ручников или Дундуков;

ПТ – пойманы оба преступника Пупков и Трошкин;

- непоявление события Р, т.е. преступник Ручников не пойман;

- одновременное выполнение событий и , т.е. не пойман Пупков и не пойман Дундуков.