Математические основы дискретных систем. Решение 6 заданий.

Задание 1

Для логической функции Y(x1, x2, x3, x4), заданной таблицей истинности, составить совершенную дизъюнктивную нормальную форму (СДНФ) и совершенную конъюнктивную нормальную форму (СКНФ). Полученные выражения функции минимизировать с помощью законов алгебры логики.



Задание 2

На множествах А (|A| = 6), В (|B| = 7), С (|C| = 5) заданы отношения R  A  B 

и Q  B  C в виде матриц смежности. Требуется:

1.	Получить матрицу смежности композиции R  Q.

2.	Изобразить графы отношений R, Q и R  Q.

3.	Определить, является ли каждое из отношений R, Q и R  Q:

а) полностью определенным; б) сюръекцией; в) инъекцией; г) функцией;

   д) биекцией.



Задание 3

Ориентированный граф G с множеством вершин V = {1, 2, 3, 4, 5, 6, 7} задан списком дуг E = {(1, 6), (2, 1), (2, 3), (3, 1), (3, 3), (3, 4), (3, 6), 

  (4, 2), (5, 1), (5, 6), (5, 6), (5, 6), (7, 4), (7, 6)}. 



Требуется: 

1.	Построить реализацию графа G.

2.	Составить матрицу инциденций графа G.

3.	Составить матрицу смежности графа G.

4.	Составить матрицу смежности ассоциированного неориентированного графа G .

5.	Построить списки смежности графов G и G .



Задание 4

Взвешенный неориентированный граф G с множеством вершин V = {1, 2, 3, 4, 5, 6, 7, 8} задан матрицей весов ребер.



Требуется:

1.	Построить реализацию графа G.

2.	Выбрать наилегчайший остов графа G.



Задание 5

Задан взвешенный неориентированный граф G в виде решетки с квадратными ячейками. Узлы решетки являются вершинами графа. Веса ребер помечены числами. Требуется найти кратчайший путь из левого верхнего угла решетки в нижний правый угол.



Задание 6

Разработать универсальную программу для обработки двух отношений, заданных на одном множестве A (|A| = 6). В программе предусмотреть:

1.	Генерацию, ввод, редактирование, загрузку из файла и сохранение в файле матриц исходных отношений.

2.	Вычисление обратного отношения.

3.	Вычисление дополнения отношения.

4.	Вычисление объединения отношений.

5.	Вычисление пересечения отношений.

6.	Вычисление композиции отношений.

7.	Вывод исходных и результирующих отношений в виде матриц и графов