РГР по дискретной математике

1. Определить для данной формулы логики высказываний:
а) таблицу истинности;
б) ДНФ, КНФ, СДНФ, СКНФ (методом равносильных преобразований);
в) задать табличным способом соответствующую булеву функцию;
г) определить СДНФ, СКНФ табличным способом (сравнить с пп.1.б);
д) найти минимальную ДНФ, указать соответствующую ей переключательную схему;
е) построить многочлен Жегалкина.
2. Проверить правильность рассуждения.
3. Доказать тождество алгебры множеств.
4. Задано бинарное отношение   на множестве  . Проверить его на рефлексивность, симметричность, антисимметричность, транзитивность. Найти  ; изобразить указанные бинарные отношения на координатной плоскости.
5. График функции   представляет собой ломаную, звенья которой параллельны координатной оси либо биссектрисам координатных углов; координаты каждой вершины ломаной являются целыми числами.   определяет отношение   на множестве  . Доказать, что   - эквивалентность на множестве  . Перечислить все классы эквивалентности.
6. В частично упорядоченном множестве, заданном диаграммой, найти (если таковые есть) наибольший, наименьший, минимальный, максимальный элементы, интервал   (  - выделены кружками). Продолжить до линейного порядка.
7. Определить для орграфа, заданного матрицей смежности:
а) имеются ли контуры;
б) матрицу односторонней связности;
в) матрицу сильной связности;
г) компоненты сильной связности;
д) изображения исходного орграфа и его компонент сильной связности.
8. Используя алгоритм Терри, определить замкнутый маршрут, проходящий ровно по два раза (по одному в каждом направлении) через каждое ребро графа.
9. Используя алгоритм “фронта волны”, найти все минимальные пути из первой вершины в последнюю орграфа, заданного матрицей смежности.
10. Используя алгоритм Форда, найти минимальные пути из первой вершины во все достижимые вершины в нагруженном графе, заданном матрицей длин дуг.
11. Найти остовное дерево с минимальной суммой длин входящих в него ребер.

Значения   приведены в задании, значения   равны 5.
12. Пусть каждому ребру неориентированного графа соответствует некоторый элемент электрической цепи. Составить линейно независимые системы уравнений Кирхгофа для токов и напряжений. Пусть первому и пятому ребру соответствуют источники тока ( ) с ЭДС   и   (полярность выбирается произвольно), а остальные элементы являются сопротивлениями. Используя закон Ома, и, предполагая внутренние сопротивления источников тока равными нулю, получить систему уравнений для токов.
13. Используя алгоритм Форда-Фалкерсона, построить максимальный поток по транспортной сети.
Значения величин   приведены в задании. Начинать с окаймляющих цепей.