Лабораторная работа Лабораторная работа Основы теории множеств

Пример. Доказать тождество: A\(A\B)=B\(B\A). Решение: Упростим левую часть тождества. Имеем: A\(A\B) = A( A\B)^d (применили свойство 14) = A(AB^d)^d( еще раз применили свойство 14) = A(A^dB^dd) (применили закон де Моргана 10б) = A(A^dB) (применили свойство 13) = (A A^d) (AB)(применили свойство 3б)= (AB) (применили свойство 5б) = AB (применили свойство 4а). Аналогичными преобразованиями правую част доказываемого тождества приводим к виду BA. Так как AB= BA в силу свойства 1б), тождество доказано.

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

Пример. Доказать теорему де Моргана (AB)^d=A^dB^d, основываясь на отношении принадлежности. Решение: Имеем цепочку равносильностей: (x(AB)^d)  (x(AB))  ((xA) и (xB))  ((xA^d) и (xB^d))  (x( A^d B^d)), которая и означает, что множества (AB)^d и A^dB^d состоят из одни и тех же элементов, а поэтому совпадают.

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

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

Чтобы установить структуру формулы алгебры множеств и проверить ее правильность нужно повести грамматический разбор формулы. Результатом грамматического разбора является построение дерева формулы или установление ошибочности данной формулы. Дерево формулы строится рекурсивно от корня. Для корня находится один или два его потомка, также являющиеся формулами алгебры множеств, а относительно исходной формулы- ее подформулами. Далее к каждому из потомков применяется тот же алгоритм, что и исходному корню дерева, т.е. применяется рекурсия. Программа разбора формулы в процессе своей работы вызывает ту же программу. Рекурсия завершает свою работу, если к текущей формуле применимо правило 1), т.е. разбираемая на данном шаге формула является или одним из базовых множеств, либо пустым множеством, либо универсумом. В общем случае в выражении разбираемой формулы необходимо выделить знак центральной операции, т.е. операции, выполняемой последней при вычислении формулы. Пусть центральная операция выделена и относительно ее данная формула имеет вид: . Т.е. операция является бинарной и для нее имеются подформулы , являющиеся левым и правым операндом центральной операции. Тогда знак операции помещается в корень дерева на данном уровне разбора главной формулы, а подформулы помещаются в дереве на один уровень ниже, являясь потомками узла с символом центральной операции и при дальнейшем разборе к этим потомкам применяем тот же алгоритм. Когда текущая подформула не содержит символов теоретико- множественных операций, процесс ветвления прекращается, формируется узел дерева, называемый его листом и в этот лист помещается символ базового множества, пустого или универсума, в зависимости от содержания текущей подформулы. Таким образом, внутренние узлы дерева грамматического разбора формулы алгебры множества содержат символы теоретико- множественнх операций, а листья- символы базовых множеств, пустого множества или универсума. Для эффективного построении дерева формулы необходимо уметь быстро определять позицию символа центральной операции в строке, выражающее анализируемую формулу. Для той цели служит понятие индекса связки в формуле. Индексом связки или теоретико- множественной операции является число, равное разности количества открывающих скобок и закрывающих скобок , расположенных слева от данной связки в строке формулы. Для центральной связки индекс равен 1. Если в результате анализа формулы оказалось, что таких связок нет или их несколько, разбираемая формула построена неправильно, содержит ошибку, программа анализа формулы прекращает свою работу с сообщением некорректности формулы.

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

Дано:

- универсум,

- набор базовых множеств, подмножеств универсума, где ,

,

,
.

Решение.

Анализируем главную формулу .

Находим индексы всех связок формулы и определяем центральную связку.

op
Ind(op)	2	3	1

Таким образом, центральной связкой в формуле является операция пересечения и относительно ее имеем , где и . Таким образом на данном этапе построено начальное дерево высоты 2 с корнем , имеющим два потомка и . Это начальное дерево имеет вид:

Анализируем формулу .

Находим индексы всех связок формулы и определяем центральную связку.

op
Ind(op)	1	2

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

В исходное дерево вместо узла

подставляем структуру

Анализируем формулу . Имеем: - лист.

Замещаем узел

на узел

Анализируем формулу .

Находим индексы всех связок формулы и определяем центральную связку.

op
Ind(op)	1

В данной формуле центральной и единственной связкой является операция объединения, относительно которой, анализируемая подформула имеет структуру:

т.е. является поддеревом высоты 2, завершаемым листьями. Грамматический разбор формулы алгебры множеств завершен. Дерево формулы имеет вид:

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

Имеем:

- дано,

- дано,

- дано,

Таким образом, получено значение анализируемой формулы.

Классическое определение вероятностей. Применение формул комбинаторики для расчета вероятностей.

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

, (1)

где — число исходов испытания, благоприятствующих событию А. Число называют вероятностью события при данном испытании.

Пример 1. Из 35 экзаменационных билетов, занумерованных с помощью целых чисел от 1 до 35, наудачу извлекается один. Какова вероятность того, что номер вытянутого билета есть число, кратное трем?

Решение. Испытание состоит в том, что извлекается один билет. Так как билет вытягивается наудачу, то все исходы испытания равновероятны и, кроме того, они несовместны. Число возможных исходов испытания равно 35. Событие означает, что

номер взятого билета кратен трем. Этому событию благоприятствуют 11 исходов испытания {3; 6; 9; ...; 33}. Следовательно, по формуле (1) искомая вероятность равна

.

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

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

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

Пример 3. Hа книжной полке произвольно расставлены 4 книги по теории вероятностей и 3 книги по теории множеств. Какова вероятность того, что книги по одному и тому же предмету окажутся рядом?

Решение. Испытание состоит в том, что 7 книг ставятся на полку. Так как они ставятся на полку произвольно, то все исходы испытания равновероятны, кроме того, они несовместны. Семь книг на полке могут быть упорядочены 7! способами. Следовательно, число всех исходов испытания . Событию , состоящему в том, что книги по одному и тому же предмету окажутся рядом, благоприятствует исходов. Действительно, комплект книг по теории вероятностей может быть упорядочен 4! способами, и после каждого такого расположения книги по теории множеств могут быть упорядочены 3! способами. Кроме того, сами комплекты книг могут быть упорядочены двумя способами. Таким образом, вероятность события равна << предыдущая страница