diskr_edit (Методичка по дискретной математике), страница 21
Описание файла
Файл "diskr_edit" внутри архива находится в папке "Методичка по дискретной математике". Документ из архива "Методичка по дискретной математике", который расположен в категории "". Всё это находится в предмете "дискретная математика" из 4 семестр, которые можно найти в файловом архиве РТУ МИРЭА. Не смотря на прямую связь этого архива с РТУ МИРЭА, его также можно найти и в других разделах. Архив можно найти в разделе "книги и методические указания", в предмете "дискретная математика" в общих файлах.
Онлайн просмотр документа "diskr_edit"
Текст 21 страницы из документа "diskr_edit"
14.1. 0 0 1 1 0 0 2. ¥ 2 3 9 ¥ ¥ ¥ 3. ¥ 3 2 4 5
1 0 0 0 0 1 12 ¥ ¥ 10 4 ¥ ¥ 3 ¥ 2 ¥ 1
1 0 0 0 1 0 ¥ ¥ ¥ 2 ¥ 1 ¥ 2 2 ¥ 1 1
0 1 0 0 0 1 ¥ ¥ ¥ ¥ 7 6 ¥ 4 ¥ 1 ¥ 3
0 0 1 0 1 0 ¥ ¥ ¥ ¥ ¥ ¥ 5 5 1 1 3 ¥
0 1 0 1 0 0 ¥ ¥ ¥ ¥ ¥ ¥ 8
¥ ¥ ¥ ¥ ¥ ¥ ¥
15.1. 0 1 0 1 0 0 2. ¥ 2 5 10 ¥ ¥ ¥ 3. ¥ 6 3 10 4
1 0 0 1 0 0 ¥ ¥ ¥ 12 6 ¥ ¥ 6 ¥ 1 2 3
0 0 0 0 1 1 ¥ ¥ ¥ 3 ¥ 1 ¥ 3 1 ¥ 8 6
1 1 0 0 1 1 ¥ ¥ ¥ ¥ 9 8 ¥ 10 2 8 ¥ 3
0 0 1 1 0 0 ¥ ¥ ¥ ¥ ¥ ¥ 7 4 3 6 3 ¥
0 0 1 1 0 0 ¥ ¥ ¥ ¥ ¥ ¥ 10
¥ ¥ ¥ ¥ ¥ ¥ ¥
16.1. 0 0 0 0 1 1 2. ¥ ¥ 5 4 2 2 10 3. ¥ 4 2 10 6
0 0 1 1 0 0 ¥ ¥ 2 1 ¥ 2 1 4 ¥ 3 ¥ 4
0 1 0 0 1 0 2 ¥ ¥ 1 1 ¥ 3 2 3 ¥ 1 5
0 1 0 0 0 1 ¥ 2 1 ¥ 1 ¥ ¥ 10 ¥ 1 ¥ 3
1 0 1 0 0 0 ¥ ¥ 2 2 ¥ 1 6 6 4 5 3 ¥
1 0 0 1 0 0 1 5 ¥ 1 1 ¥ ¥
2 ¥ 1 ¥ 1 2 ¥
1
7.1 0 0 1 0 1 0 2. ¥ 4 9 8 3 1 ¥ 3. ¥ 2 ¥ 3 5
0 0 0 1 0 1 3 ¥ 2 1 ¥ ¥ 4 2 ¥ 8 ¥ 7
1 0 0 0 1 0 1 1 ¥ ¥ ¥ ¥ 1 ¥ 8 ¥ 10 1
0 1 0 0 0 1 ¥ 3 1 ¥ 1 ¥ ¥ 3 ¥ 10 ¥ 12
1 0 1 0 0 0 ¥ ¥ 2 ¥ ¥ 1 5 5 7 1 12 ¥
0 1 0 1 0 0 ¥ 3 ¥ 2 2 ¥ ¥
¥ ¥ 2 ¥ ¥ 2 ¥
18.1. 0 0 1 0 1 0 2. ¥ ¥ 9 ¥ 10 2 12 3. ¥ 1 3 4 5
0 0 0 0 0 0 1 ¥ ¥ ¥ 1 2 4 1 ¥ 2 6 8
1 0 0 0 1 0 2 1 ¥ ¥ 1 ¥ 2 3 2 ¥ 1 7
0 1 0 0 0 1 ¥ 1 1 ¥ ¥ 1 ¥ 4 6 1 ¥ 4
1 0 1 0 0 0 1 2 9 2 ¥ ¥ ¥ 5 8 7 4 ¥
0 1 0 1 0 0 ¥ ¥ ¥ ¥ 1 ¥ 8
¥ 2 1 ¥ 1 2 ¥
19.1. 0 1 1 0 1 1 2. ¥ 3 5 12 20 ¥ ¥ 3. ¥ 1 6 5 14
1 0 0 1 0 0 ¥ ¥ ¥ 13 8 ¥ ¥ 1 ¥ 3 4 6
1 0 0 1 1 1 ¥ ¥ ¥ 5 ¥ 3 ¥ 6 3 ¥ 10 12
0 1 1 0 1 1 ¥ ¥ ¥ ¥ 10 9 ¥ 5 4 10 ¥ 6
1 0 1 1 0 1 ¥ ¥ ¥ ¥ ¥ ¥ 8 14 6 12 6 ¥
1 0 1 1 1 0 ¥ ¥ ¥ ¥ ¥ ¥ 11
¥ ¥ ¥ ¥ ¥ ¥ ¥
20.1. 0 1 0 0 1 0 2. ¥ 1 5 7 9 ¥ ¥ 3. ¥ 6 3 4 5
1 0 0 1 0 0 ¥ ¥ ¥ 10 4 ¥ ¥ 6 ¥ 2 9 1
1 0 0 0 1 1 5 3 ¥ ¥ 1 ¥ ¥ 3 2 ¥ 1 4
0 1 0 0 0 1 ¥ ¥ ¥ ¥ 7 6 ¥ 4 9 1 ¥ 3
0 0 1 0 0 0 ¥ ¥ ¥ ¥ ¥ ¥ 4 5 1 4 3 ¥
0 1 1 0 0 0 ¥ ¥ ¥ ¥ ¥ ¥ 9
¥ ¥ ¥ ¥ ¥ ¥ ¥
21.1. 0 1 0 1 1 1 2. ¥ 1 5 15 ¥ ¥ ¥ 3. ¥ 5 3 6 7
1 0 0 1 0 0 ¥ ¥ 11 12 6 ¥ ¥ 5 ¥ 1 2 4
0 0 0 1 1 0 ¥ ¥ ¥ 3 ¥ 2 ¥ 3 1 ¥ 5 6
1 1 1 0 1 0 ¥ ¥ ¥ ¥ 9 8 ¥ 6 2 5 ¥ 3
1 0 1 1 0 1 ¥ ¥ ¥ ¥ ¥ ¥ 7 7 4 6 3 ¥
1 0 0 0 1 0 ¥ ¥ ¥ ¥ ¥ ¥ 10
¥ ¥ ¥ ¥ ¥ ¥ ¥
22.1 0 0 1 0 1 0 2. ¥ ¥ 3 4 1 5 9 3. ¥ 7 2 11 3
0 0 0 0 0 0 ¥ ¥ 1 2 ¥ 1 6 7 ¥ 3 ¥ 4
0 1 0 0 1 1 4 ¥ ¥ 2 1 ¥ 3 2 3 ¥ 1 5
0 1 0 0 0 1 ¥ 2 3 ¥ 1 ¥ ¥ 11 ¥ 1 ¥ 3
1 1 1 0 0 0 ¥ ¥ 2 2 ¥ 1 6 3 4 5 3 ¥
0 0 0 1 1 0 1 5 ¥ 1 1 ¥ ¥
2 ¥ 1 ¥ 1 2 ¥
23.1. 0 0 1 0 1 0 2. ¥ 4 9 ¥ 3 1 ¥ 3. ¥ 1 9 4 5
0 0 0 1 0 1 3 ¥ 2 1 ¥ ¥ 4 1 ¥ 8 ¥ 7
1 0 0 0 1 0 1 1 ¥ ¥ 10 14 1 9 8 ¥ 10 1
0 1 0 0 0 1 ¥ 3 1 ¥ 1 ¥ ¥ 4 ¥ 10 ¥ 13
1 0 1 0 0 0 ¥ ¥ 2 ¥ ¥ 1 5 5 7 1 13 ¥
0 1 0 1 0 0 ¥ 3 ¥ 1 2 ¥ ¥
¥ ¥ 2 ¥ ¥ 2 ¥
24.1 0 0 1 0 1 0 2. ¥ ¥ 8 ¥ 10 3 12 3. ¥ 3 2 4 6
0 0 0 1 0 0 1 ¥ ¥ ¥ 1 2 3 3 ¥ 5 6 3
0 1 0 0 1 0 2 1 ¥ ¥ 1 ¥ 2 2 5 ¥ 1 7
0 0 0 0 0 1 ¥ 1 1 ¥ ¥ 1 15 4 6 1 ¥ 4
0 1 1 0 0 0 1 2 ¥ 2 ¥ ¥ ¥ 6 3 7 4 ¥
0 1 0 0 0 0 ¥ ¥ ¥ ¥ 1 ¥ 8
¥ 2 1 ¥ 1 2 ¥
25.1. 0 0 1 0 0 1 2. ¥ ¥ 5 4 2 2 10 3. ¥ 1 2 8 5
0 0 1 1 1 1 ¥ ¥ 2 1 ¥ 2 1 1 ¥ 3 ¥ 4
1 1 0 0 0 0 2 ¥ ¥ 1 1 ¥ 3 2 3 ¥ 1 5
0 1 0 0 0 1 12 2 1 ¥ 1 ¥ ¥ 8 ¥ 1 ¥ 3
0 1 0 0 0 1 ¥ ¥ 2 2 ¥ 1 6 5 4 5 3 ¥
1 1 0 1 1 0 1 5 ¥ 1 1 ¥ ¥
2 ¥ 1 ¥ 1 2 ¥
26.1. 0 0 0 0 1 0 2. ¥ 4 9 8 3 2 ¥ 3. ¥ 2 9 3 5
0 0 0 1 0 0 3 ¥ 2 1 ¥ ¥ 5 2 ¥ 8 ¥ 7
1 0 0 0 1 0 2 1 ¥ ¥ ¥ ¥ 1 9 8 ¥ 10 1
0 1 0 0 0 1 ¥ 3 1 ¥ 1 ¥ ¥ 3 ¥ 10 ¥ 12
0 0 0 0 0 0 ¥ ¥ 2 ¥ ¥ 1 5 5 7 1 12 ¥
0 1 0 0 0 0 ¥ 3 ¥ 2 2 ¥ ¥
¥ ¥ 2 ¥ ¥ 2 ¥
27.1. 0 0 1 0 1 0 2. ¥ ¥ 9 ¥ 8 1 12 3. ¥ 1 3 7 2
0 0 1 1 1 1 1 ¥ ¥ ¥ 2 2 4 1 ¥ 5 6 8
1 1 0 0 1 0 2 1 ¥ ¥ 1 ¥ 2 3 5 ¥ 1 7
0 1 0 0 0 1 ¥ 1 1 ¥ ¥ 1 ¥ 7 6 1 ¥ 4
1 1 1 0 0 0 1 2 9 2 ¥ ¥ ¥ 2 8 7 4 ¥
0 1 0 1 0 0 ¥ ¥ ¥ ¥ 1 ¥ 8
¥ 2 1 ¥ 1 2 ¥
2 8.1. 0 1 1 0 1 1 2. ¥ 3 5 12 20 ¥ ¥ 3. ¥ 1 6 5 14
1 0 0 1 0 0 ¥ ¥ ¥ 13 8 ¥ ¥ 1 ¥ 3 4 6
1 0 0 1 1 1 ¥ ¥ ¥ 5 ¥ 3 ¥ 6 3 ¥ 10 12
0 1 1 0 1 1 ¥ ¥ ¥ ¥ 10 9 ¥ 5 4 10 ¥ 6
1 0 1 1 0 1 ¥ ¥ ¥ ¥ ¥ ¥ 8 14 6 12 6 ¥
1 0 1 1 1 0 ¥ ¥ ¥ ¥ ¥ ¥ 11
¥ ¥ ¥ ¥ ¥ ¥ ¥
29.1. 0 1 0 0 1 0 2. ¥ 1 8 6 7 ¥ ¥ 3. ¥ 2 3 4 5
1 0 0 1 0 0 ¥ ¥ ¥ 10 4 ¥ ¥ 2 ¥ 6 9 1
1 0 0 0 1 1 5 3 ¥ ¥ 1 ¥ ¥ 3 6 ¥ 1 4
0 1 0 0 0 1 ¥ ¥ ¥ ¥ 7 6 ¥ 4 9 1 ¥ 3
0 0 1 0 0 0 ¥ ¥ ¥ ¥ ¥ ¥ 4 5 1 4 3 ¥
0 1 1 0 0 0 ¥ ¥ ¥ ¥ ¥ ¥ 9
¥ ¥ ¥ ¥ ¥ ¥ ¥
30.1. 0 1 0 1 1 1 2. ¥ 2 4 13 ¥ ¥ ¥ 3. ¥ 5 3 6 4
1 0 0 1 0 0 ¥ ¥ 11 12 6 ¥ ¥ 5 ¥ 1 2 7
0 0 0 1 1 0 ¥ ¥ ¥ 3 ¥ 2 ¥ 3 1 ¥ 5 6
1 1 1 0 1 0 ¥ ¥ ¥ ¥ 9 8 ¥ 6 2 5 ¥ 3
1 0 1 1 0 1 ¥ ¥ ¥ ¥ ¥ ¥ 7 4 7 6 3 ¥
1 0 0 0 1 0 ¥ ¥ ¥ ¥ ¥ ¥ 10
¥ ¥ ¥ ¥ ¥ ¥ ¥
4. Раздел «Булевы функции»
Для данной формулы булевой функции
а) найти ДНФ, КНФ, СДНФ, СКНФ методом равносильных преобразований;
б) найти СДНФ, СКНФ табличным способом (сравнить с СДНФ, СКНФ, полученными в пункте “а”);
в) указать минимальную ДНФ и соответствующую ей переключательную схему.
Варианты заданий
| Функция | Функция |
| 1. ((x V y) z) V x&y&z 2.(x&(y (xVz))) 3. (x (z&(y ~ x))) 4.(x~y) (xVz) 5.(x y) V (y z) 6. (x&y) ((x&z) ~ x) 7. (y x) ~(x z) 8. (x&y) ((xVz) & y) 9. (x~y) (xVz) 10. (x& y) ((xVz) y) 11.x (y (z y&z)) 12. ((y& z) (xVz)) y 13. (x&(y (x ~ z))) 14. (x (x&(yV(x ~y)Vx))) 15. (x z) V (y ~ z) | 16. (x~y) (xVz) 17. x&y (x&z (xVy)) 18. (y x) ~(x z) 19. (x&y z) (x ~ z) 20. (x&y z) (x y) 21. x (y (z ~x)) 22. y&z (xVz&y) 23. (x&(y (z ~ y))) 24. x (x&(yV(x ~z))) 25. (x y)V (y&(x~z)) 26. (x ~ y) (x ~z) 27. (x y) (x&z) 28. x (z (x Vy&z)) 29. x&(y (z ~ y)) 30. (x z) V (y ~ z) |
Вопросы к экзамену по дисциплине «Дискретная математика»
1. Основные понятия теории множеств: множества, подмножества, пустое множество, универсальное множество, множество-степень.
2. Способы задания множеств.
3. Операции над множествами.
4. Геометрическое моделирование множеств. Диаграммы Эйлера - Венна.
5. Алгебра множеств. Основные тождества алгебры множеств.
6. Эквивалентность множеств. Свойство транзитивности. Мощность множества.
7. Мощность объединения конечных множеств.
8. Эквивалентность множества точек отрезков и интервалов. Теорема Бернштейна.
9. Счетные множества. Теоремы о счетных множествах.
10. Мощность множества точек отрезка [0, 1]. Теорема Кантора.
11. Множества мощности континуума. Теоремы о множествах мощности континуума.
12. Отношения. Основные понятия и определения. Бинарные отношения. Область определения, область значений и область задания бинарного отношения.
13. Операции над отношениями. Обратное отношение, Композиция отношений.
14. Свойства отношений. Рефлексивность, симметричность, транзитивность, эквивалентность.
15. Классы эквивалентности. Разбиение множеств.
16. Отношение частичного порядка.
17. Функция как бинарное отношение. Область определения и область значений функции. Равенство функций.
18. Сюръективные, инъективные, биективные функции.
19. Обратная функция. Композиция функций.
20. Способы задания функций.
21. Определение графа. Различные типы графов.
22. Матричные способы задания графов.
23. Изоморфизм графов.
24. Маршруты, циклы в неориентированном графе.
25. Пути, контуры в ориентированном графе.
26. Связность неориентированного графа. Матрица связности.
27. Связность ориентированного графа. Матрицы односторонней и сильной связности..
28. Экстремальные пути в нагруженных ориентированных графах.
29. Алгоритм Форда – Беллмана нахождения минимального пути.
30. Деревья. Остовные деревья.
31. Минимальное остовное дерево. Алгоритм Краскала.
32. Определение булевой функции. Операции над булевыми функциями.
33. Формулы логики булевых функций.
34. Равносильные преобразования формул булевых функций.
35. Двойственность. Принцип двойственности.
36. Булева алгебра (алгебра логики). Полные системы булевых функций.
37. Нормальные формы формул булевых функций.
38. Разложение булевой функции по переменным.
39. Алгоритм Квайна построения сокращенной ДНФ.
40. Алгоритм Квайна – Мак-Класки построения сокращенной ДНФ.
41. Алгоритм построения минимальной ДНФ с помощью таблицы покрытий.
42. Применение алгебры булевых функций к релейно-контактным схемам.
Список рекомендованной литературы
1. Акимов О. Е. Дискретная математика: логика, группы, графы. – М.: Лаборатория Базовых Знаний, 2001.
2. Кузнецов О. П., Адельсон-Вельский Г. М. Дискретная математика для инженера. – М.: Энергоиздат, 1988.
3. Липский В. Комбинаторика для программистов. – М.: Мир, 1988.
4. Нефедов В. Н., Осипова В. А. Курс дискретной математики. – М.: Издательство МАИ, 1992.
5. Новиков Ф. А. Дискретная математика для программистов. – СПб.: Питер, 2002.
6. Судоплатов С. В., Овчинникова В. В. Элементы дискретной математики. – М.: ИНФРА – М, Новосибирск: Изд-во НГТУ, 2002.
Краткие сведения о математиках
Арнольд Владимир Игоревич – математик, академик Российской Академии наук.
Беллман Ричард – американский математик.
