Типовые расчеты по дискретной математике
![]()
|
1 2 Вариант 25 З ![]() Докажите тождества, используя только определения операций над множествами. 1) ![]() ![]() ![]() ![]() и ![]() ![]() ![]() 2) ![]() ![]() ![]() ![]() ![]() Задание 2. Докажите утверждение. ![]() Для доказательства утверждения достаточно доказать, что ![]() Используя арифметику кардинальных чисел, преобразуем левую и правую части к одному виду: ![]() ![]() Так как полученные выражения совпадают, то исходные множества эквивалентны. ![]() ![]() Задание 3. Докажите методом математической индукции, что ![]() Найдем базис индукции: n=1 ![]() Предположим, что ![]() Докажем, что ![]() ![]() ![]() ![]() Значит, так как справедливость утверждения доказана для n+1, то верно, что ![]() ![]() ![]() Задание 4. A={a,b,c}, B={1,2,3,4}, ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() 1 2 3 4 ![]() [ ![]() ![]() ![]() ![]() [ ![]() ![]() ![]() ![]() ![]() 1) ![]() ![]() ![]() 2) ![]() ![]() 3 ![]() ![]() ![]() 4) ![]() ![]() ![]() ![]() ![]() Задание 5. Найдите область определения, область значений отношения P. Является ли отношение P рефлексивным, симметричным, антисимметричным, транзитивным? ![]() Область определения: ![]() Область значений: ![]() 1) Если ![]() ![]() 2) Так как ![]() 3) Пусть ![]() ![]() 4) Так как ![]() ![]() ![]() ![]() ![]() Задание 6. Является ли алгеброй следующий набор B= ![]() Так как константа –3i ![]() ![]() ![]() ![]() ![]() ![]() Задание 7. Постройте подсистему B(X), если B= i + i + i +…=in, n ![]() Складывая всевозможные действительные числа, получаем другие действительные числа, то есть операция сложения замкнута на множестве R. Поэтому, подстановка элементов из X в терм ”+” не образует новых элементов. Таким образом, B(X)= ![]() ![]() ![]() Задание 8. Используя многомодульную арифметику с вектором оснований ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() – ![]() ![]() ![]() ![]() ![]() – ![]() ![]() ![]() ![]() ![]() – ![]() ![]() ![]() ![]() ![]() – ![]() ![]() Определим знак числа ![]() Очевидно, что ![]() ![]() ![]() Вектор оснований сокращаем до ![]() Для вычисления ![]() ![]() Умножим ![]() Таким образом, ![]() Вычитая ![]() ![]() ![]() Вектор оснований ![]() Вычисляем ![]() ![]() Умножаем ![]() Поэтому ![]() ![]() ![]() ![]() Находим ![]() ![]() При умножении на ![]() Отсюда следует, что ![]() Поэтому число x – положительное. ![]() ![]() Задание 9. Даны графы ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Рассмотрим граф ![]() Матрица смежности A= ![]() ![]() ![]() ![]() ![]() ![]() B=E+A+ ![]() ![]() ![]() ![]() ![]() Маршруты длины 2, исходящие из вершины 1: (1;1;1), (1;1;2), (1;1;3), (1;1;4). (1;2;1), (1;2;2), (1;2;3), (1;2;4). (1;3;2), (1;3;3), (1;4;4). ![]() ![]() Задание 10. Найдите матрицы фундаментальных циклов, фундаментальных разрезов, радиус и диаметр, минимальное множество покрывающих цепей графа G. Является ли изображенный граф эйлеровым? Является ли изображенный граф планарным? 3 ![]() 4 Получим остов графа. Для этого удалим из графа 12–8+1=5 ребер. ![]() 3 Матрица фундаментальных циклов: ![]() C= ![]() ![]() Матрица фундаментальных разрезов: ![]() K= ![]() ![]() Диаметр d(G)=4 Радиус r(G)=2 Минимальное множество покрывающих цепей графа – 2. 2,7,3,4,6,5,3,6,7,4,5 1,8,7 Граф не является эйлеровым, так как степени не всех его вершин четные. Граф планарный. ![]() ![]() ![]() Задание 11. Составьте таблицы истинности формул: 1) ![]()
2) ![]()
![]() ![]() Задание 12. Проверьте двумя способами, будут ли эквивалентны следующие формулы ![]() ![]() ![]() ![]() ![]() ![]() ![]() а) составлением таблиц истинности б) приведением формул к СДНФ или СКНФ с помощью эквивалентных преобразований. а)
Так как столбцы ![]() ![]() б) ![]() ![]() Так как СДНФ не совпадают, то формулы неэквивалентны. ![]() ![]() Задание 13. С помощью эквивалентных преобразований приведите формулу к ДНФ, КНФ, СДНФ, СКНФ. Постройте полином Жегалкина. ![]() ![]() ![]() Задание 14. Найдите сокращенную, все тупиковые и минимальные ДНФ булевой функции ![]() а) методом Квайна б) с помощью карт Карно Каким классам Поста принадлежит эта функция? ![]() а)
![]() ![]()
![]() б) ![]() ![]() ![]() ![]() 1) ![]() 2) ![]() 3) ![]() 4 ![]() ![]() ![]() ![]() ![]() Задание 15. С помощью карт Карно найдите сокращенную, все тупиковые и минимальные ДНФ и КНФ булевой функции ![]() (0011 1101 0010 1100)
![]() ![]() ![]() 1) – минимальная ДНФ. ![]() ![]() ![]() 2) – минимальная КНФ. ![]() ![]() Задание 16. Является ли полной система функций 1 2 |