Экзамен Дискретная математика. экзамен. Экзаменационная работа По дисциплине Дискретная математика
 Скачать 0.91 Mb.
|
|
Федеральное агентство связи Сибирский Государственный Университет Телекоммуникаций и Информатики Межрегиональный центр переподготовки специалистов Экзаменационная работаПо дисциплине: “Дискретная математика”Билет №6 Выполнил: Группа: Вариант: 01 Проверила: Новосибирск, 2015 г. Индикатор, или характеристическая функция, или индикаторная функция подмножества  — это функция, определенная на множестве X, которая указывает на принадлежность элемента  подмножеству A.Определение Пусть — выбранное подмножество произвольного множества X. Функция  , определенная следующим образом: называется индикатором множества A. Альтернативными обозначениями индикатора множества A являются:  или  , а иногда даже A(x). Скобка Иверсона позволяет обозначение  .(Греческая буква Х происходит от начальной буквы греческого написания слова характеристика.) Основные свойства Отображение, которое связывает подмножество с его индикатором  инъективно. Если A и B — два подмножества  , то   Более обще, предположим  — это набор подмножеств X. Ясно, что для любого  — произведение нулей и единиц. Это произведение принимает значение 1 точно для тех , которые не принадлежат ни одному множеству  и 0 иначе. Поэтому Разворачивая левую часть, получаем  где | F | — мощность F. Это одна из форм принципа включения-исключения. Этот пример указывает, что индикатор — полезное обозначение в комбинаторике, которое используется также и в других областях, например в теории вероятностей: если X — вероятностное пространство с вероятностной мерой  , а A — измеримое множество, то индикатор становится случайной величиной, чье математическое ожидание равно вероятности A: Это тождество используется в простых доказательствах неравенства Маркова. Заданы универсальное множество U и три его подмножества A, B, C. Проверить (доказать или опровергнуть) справедливость соотношения:  .Решение: Проверим справедливость соотношения  , используя законы алгебры множеств. Обычную операцию разность множеств  можно записать как  , а симметрическую разность  . Тогда для левой части  равенства:  .Для правой части  равенства:  .Очевидно, что левая часть  не равна правой части  . Значит, данное соотношение не является верным.Так же справедливость соотношения можно проверить с помощью диаграмм Эйлера-Венна. Диаграммы множеств и не совпадают. Задано бинарное отношение  , где  . Определить, выполняются ли для данного отношения свойства транзитивности и антирефлексивности. Ответ обосновать.Решение: Определим свойства отношения  , заданного на множестве  .Является рефлексивным, так как  , действительно,  — четно. Является симметричным, так как  , действительно, если  четно, то  тоже четно. Является транзитивным, так как  . Показывается транзитивность отношения  очень просто. Если четно, то  , если  четно, то  . Нужно показать, что  тоже в этом случае будет четным. Из равенства выразим  , получим  , а из равенства выразим  , получим  . Тогда  — четно.Ответ на вопрос задачи: свойство транзитивности выполняется, а свойство антирефлексивности нет. Упростив логическую функцию двух переменных  , проверить ее самодвойственность, монотонность и линейность. Ответ обосновать.Решение: Упростим функцию  , используя законы алгебры логики. Операцию импликацию высказываний  можно записать как  , операцию эквиваленцию:  , сумму по модулю 2:  . Учитывая, что  , получаем:   .Так как  — линейный полином, то функция  является линейной. Так как двойственная функция  совпадает с самой функцией  , то функция является самодвойственной. Так как  , но  , то функция не является монотонной.В корзине 10 красных и 8 зеленых яблок. Выбирают три. Сколькими способами можно выбрать два красных яблока и одно зеленое?  Обозначим множество красных яблок через А, зеленых – В. Обозначив число способов, которыми можно выбрать два красных яблока из множества А и одно зеленое яблоко – из множества В, через N и используя правило произведения, получим: N=  * =  * = 45 * 8 = 360 способов. |