Дискретная математика 64с
| Цена, руб. | 1000 |
| Номер работы | 2906 |
| Предмет | Математика |
| Тип работы | Контрольная |
| Объем, стр. | 64 |
| Оглавление | 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ 1. Доказать, что АВ  АВ = В  АВ = А  А\В =  АВ = U (U – универсум). 2. Доказать, что А (B\A) = 0, А\(В  С) = (А\В)\С. 3. Доказать, что А = В  (А\В)  (В\А) = 0. 4. Решить систему уравнений: где А, В, С – заданные множества и В  А  С. 5. Построить бинарное отношение: а) рефлексивное; б) несимметричное. 6. Построить бинарное отношение: а) нерефлексивное, антисимметричное, транзитивное; б) рефлексивное, антисимметричное, не транзитивное. 7. Какие из следующих отношений являются однозначными, какие обратно однозначными и какие взаимно однозначными: (х, у)  R: для у есть отец х, 8. Найти число возможных антисимметричных бинарных отношений между элементами конечного множества, состоящего из п элементов. 9. Доказать, что два множества равны тогда и только тогда, когда результаты их пересечения и объединения совпадают. 10. Известно, что из 100 студентов живописью увлекается 28, спортом – 42, музыкой – 30, живописью и спортом – 10, живописью и музыкой – 8, спортом и музыкой – 5, живописью, спортом и музыкой – 3. Определить: а) количество студентов, увлекающихся только спортом; б) количество студентов, ничем не занимающихся. 2. ОСНОВЫ АЛГЕБРЫ ЛОГИКИ 1. Доказать, что число всех булевых функций от п аргументов равно . 2. Записать СДНФ и СКНФ булевой функции f(x1, x2, x3), принимающую значения 1 на наборах с номерами 3, 4, 7*. 3. Записать СДНФ и СКНФ булевой функции f(x1, x2, x3 x4), принимающую значения 0 на наборах с номерами 2, 6, 7, 8, 11, 12. 4. Проверить справедливость равенства . 5. Проверить справедливость следующих равенств: 6. Записать следующие функции в виде СДНФ и СКНФ: 6.1. f(x1, x2, x3) = x1  x2  3 ; 7. Найти минимальное представление для каждого из следующих булевых выражений: а) x1x2x3  1 2x3  x1 2 3  1 2 3; 8. Для каждого из булевых выражений (а, б, в) упражнения 7 нарисуйте схему соответствующей логической сети (сеть переключателей). Сравните с минимальной логической сетью. 9. Для каждой из приведенных логических сетей составьте булево выражение, описывающее выход сети 10. Следующие цепи имеют более чем один выход. Запишите булевы выражения для каждого выхода. 3. ГРАФЫ 1. Для заданных матриц смежности нарисовать соответствующие графы. Определить степень каждой вершины. а б в 1 1 1 1 0 1 0 0 0 1 1 2 0 2 1 1 1 1 1 1 0 1 0 0 0 2 1 2 0 1 1 1 1 1 0 1 0 1 0 1 0 2 1 2 1 1 1 1 1 0 0 1 0 1 0 2 0 2 1 1 0 0 0 1 0 1 1 1 1 1 0 1 0 1 0 1 0 2. Записать матрицы смежности и инцидентности для графов. 3. Проверить: а) будет ли нулевой граф эйлеровым; б) может ли несвязанный граф быть эйлеровым. 4. Показать, что графы правильной решетки, показанные на рисунке, являются гамильтоновыми. тетрахедрон куб октахедрон исосахедрон 5. Для каждой из следующих матриц нарисовать диаграммы, представляющие направленный граф, для которого данные матрицы будут матрицами смежности. 6. Для каждого из нижеприведенных направленных графов определить, будет ли направленный граф: a – простым; б – сильно связанным; с – эйлеровым; д – гамильтоновым. а б в г 9. Пусть задан передатчик, который может передавать пять сигналов: a, b, с, d, e. При приеме каждый из этих сигналов может быть истолкован двояко: сигнал а – как р или q, сигнал b – как q или r, сигнал с – как r или s, сигнал d – как s или t, сигнал е – как р или t. Какое наибольшее число сигналов можно принять, не рискуя спутать их друг с другом? 10. Вершина графа, удаление которой вместе с инцидентными ей ребрами, делает граф несвязным, называется точкой сочленения. Блоком называется связный нетривиальный граф, не имеющий точек сочленения. Привести пример блока, удаление одного ребра из которого приводит к появлению точки сочленения. Существует ли блок, в котором удаление любого его ребра приводит к появлению точки сочленения? 4. СЕТИ, ПОТОКИ НА СЕТЯХ 1. Решить задачу о ханойской башне при п = 5. Найти (если они существуют) все решения, на шаг превышающие минимальное. 2. Найти самый короткий путь из вершины v в вершину w в графах, показанных на рисунках (длина дуг приведена около соответствующих ребер). 3. Граф называется взвешенным, если каждому его ребру приписано число, называемое весом ребра и имеющее смысл, например расстояния или пропускной способности. Взвешенный граф имеет множество вершин (v1, v2, …, v10), множество ребер (е1, е2, …, е16) и матрицу инцидентности: 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 1 Веса граней следующие: Ребро е1 е2 е3 е4 е5 е6 е7 е8 е9 е10 е11 е12 е13 е14 е15 е16 Вес 4 8 2 3 7 1 2 3 2 6 5 14 9 7 3 15 Нарисовать граф и найти кратчайший путь: а) из v1 в v2; б) из v4 в v10. 4. Полагая, что в задаче 2 цифры у ребер есть их пропускные способности, а v и w – вход и выход из сети соответственно, найти: а) вариант полного потока; б) наибольший поток. 5. Полагая, что в задаче 3 вес ребер есть пропускная способность соответствующего ребра, а vi и vj – вход и выход из сети соответственно, найти наибольший поток. 6. Решить транспортную задачу: а) по критерию стоимости; б) по критерию времени. Таблица перевозок аi bi 5 20 10 30 15 10 8 6 3 5 2 5 4 10 1 6 7 25 1 8 9 4 3 15 8 3 12 2 5 25 12 3 4 9 7 |
| Цена, руб. | 1000 |
Заказать работу «Дискретная математика 64с»
Отзывы
-
25.04
Спасибо за помощь! Только статистику пришлось немного переделать. Вместе с научным руководителем, о
Марина -
17.04
Рецензия на отлично, спасибо!!!
Марина - 15.04 Михаил