Решить 16 задач по дискретной математике

Условия задач
1. Докажите тождества, используя только определения операций над
множествами.
2. Докажите методом математической индукции.
3. Докажите утверждение.
4. A = {a, b, c}, B = {1, 2, 3, 4}, P1 ? A ? B, P2 ? B2
. Изобразите
P1, P2 графически. Найдите [(P1 ? P2)
?1
]. Проверьте с помощью
матрицы [P2], является ли отношение P2 рефлексивным, симметричным, антисимметричным, транзитивным?
5. Найдите область определения, область значений отношения P.
Является ли отношение P рефлексивным, симметричным, антисимметричным, транзитивным?
6. Является ли алгеброй следующий набор B = hB; ?i?
7. Постройте подсистему B(X), если...
8. Даны графы G1 и G2. Найдите G1?G2, G1?G2, G1?G2, G1?G2.
Для графа G1 ? G2 найдите матрицы смежности, инцидентности,
сильных компонент, маршрутов длины 2 и все маршруты длины
2, исходящие из вершины 1.
9. Найдите матрицы фундаментальных циклов, фундаментальных
разрезов, радиус и диаметр, минимальное множество покрывающих цепей графа G. Является ли изображенный граф эйлеровым?
Является ли изображенный граф планарным?
10. Составьте таблицы истинности формул.
11. Проверьте двумя способами, будут ли эквивалентны следующие
формулы...
а) составлением таблиц истинности;
б) приведением формул к СДНФ или СКНФ с помощью эквивалентных преобразований.
12. С помощью эквивалентных преобразований приведите формулу к
ДНФ, КНФ, СДНФ, СКНФ. Постройте полином Жегалкина.
13. Найдите сокращенную, все тупиковые и минимальные ДНФ булевой функции f(x, y, z) двумя способами:
а) методом Квайна; б) с помощью карт Карно.
Каким классам Поста принадлежит эта функция?
14. С помощью карт Карно найдите сокращенную, все тупиковые и
минимальные ДНФ, КНФ булевой функции f(x1, x2, x3, x4), заданной вектором своих значений.
15. Является ли полной система функций? Образует ли она базис?
16. С помощью алгебры логики проверьте истинность соотношения
для любых множеств A, B, C. Если соотношение неверно, постройте контрпример.