СодержаниеЗадание 1
<br>Для логической функции Y(x1, x2, x3, x4), заданной таблицей истинности, составить совершенную дизъюнктивную нормальную форму (СДНФ) и совершенную конъюнктивную нормальную форму (СКНФ). Полученные выражения функции минимизировать с помощью законов алгебры логики.
<br>
<br>Задание 2
<br>На множествах А (|A| = 6), В (|B| = 7), С (|C| = 5) заданы отношения R  A  B
<br>и Q  B  C в виде матриц смежности. Требуется:
<br>1. Получить матрицу смежности композиции R  Q.
<br>2. Изобразить графы отношений R, Q и R  Q.
<br>3. Определить, является ли каждое из отношений R, Q и R  Q:
<br>а) полностью определенным; б) сюръекцией; в) инъекцией; г) функцией;
<br> д) биекцией.
<br>
<br>Задание 3
<br>Ориентированный граф G с множеством вершин V = {1, 2, 3, 4, 5, 6, 7} задан списком дуг E = {(1, 6), (2, 1), (2, 3), (3, 1), (3, 3), (3, 4), (3, 6),
<br> (4, 2), (5, 1), (5, 6), (5, 6), (5, 6), (7, 4), (7, 6)}.
<br>
<br>Требуется:
<br>1. Построить реализацию графа G.
<br>2. Составить матрицу инциденций графа G.
<br>3. Составить матрицу смежности графа G.
<br>4. Составить матрицу смежности ассоциированного неориентированного графа G .
<br>5. Построить списки смежности графов G и G .
<br>
<br>Задание 4
<br>Взвешенный неориентированный граф G с множеством вершин V = {1, 2, 3, 4, 5, 6, 7, 8} задан матрицей весов ребер.
<br>
<br>Требуется:
<br>1. Построить реализацию графа G.
<br>2. Выбрать наилегчайший остов графа G.
<br>
<br>Задание 5
<br>Задан взвешенный неориентированный граф G в виде решетки с квадратными ячейками. Узлы решетки являются вершинами графа. Веса ребер помечены числами. Требуется найти кратчайший путь из левого верхнего угла решетки в нижний правый угол.
<br>
<br>Задание 6
<br>Разработать универсальную программу для обработки двух отношений, заданных на одном множестве A (|A| = 6). В программе предусмотреть:
<br>1. Генерацию, ввод, редактирование, загрузку из файла и сохранение в файле матриц исходных отношений.
<br>2. Вычисление обратного отношения.
<br>3. Вычисление дополнения отношения.
<br>4. Вычисление объединения отношений.
<br>5. Вычисление пересечения отношений.
<br>6. Вычисление композиции отношений.
<br>7. Вывод исходных и результирующих отношений в виде матриц и графов.ВведениеЗадание 1
<br>Для логической функции Y(x1, x2, x3, x4), заданной таблицей истинности, составить совершенную дизъюнктивную нормальную форму (СДНФ) и совершенную конъюнктивную нормальную форму (СКНФ). Полученные выражения функции минимизировать с помощью законов алгебры логики.
<br>
<br>N x1 x2 x3 x4 Y
<br>1 0 0 0 0 0
<br>2 1 0 0 0 1
<br>3 1 1 0 0 0
<br>4 0 1 0 0 1
<br>5 0 1 1 0 0
<br>6 1 1 1 0 1
<br>7 1 0 1 0 0
<br>8 0 0 1 0 1
<br>9 0 0 1 1 0
<br>10 1 0 1 1 1
<br>11 1 1 1 1 0
<br>12 0 1 1 1 1
<br>13 0 1 0 1 0
<br>14 1 1 0 1 1
<br>15 1 0 0 1 0
<br>16 0 0 0 1 1
<br>Решение:
<br>Для построения СДНФ с помощью таблиц истинности су¬ществует алгоритм:
<br>1. необходимо выбрать из таблицы истинности функции все наборы аргументов, на которых функция принимает значения «1»;
<br>2. выписать элементарные конъюнкции, соответствующие этим наборам элементов; если xi входит в данный набор как 1, он вписывается без изменения в конъюнкцию, если xi входит в дан¬ный набор как 0, то в конъюнкцию вписывается отрицание xi (т.е. );
<br>3. все полученные элементарные конъюнкции соединяются между собой знаками дизъюнкции - .
<br>Запишем СДНФ данной функции:
<br>
<br>Для построения СКНФ с помощью таблиц истинности су¬ществует алгоритм:
<br>1. необходимо выбрать из таблицы истинности функции все наборы аргументов, на которых функция принимает значение «0»;
<br>2. выписать элементарные дизъюнкции, соответствующие этим наборам элементов; если xi входит в данный набор как 0, он вписывается без изменения в дизъюнкцию, если xi входит в дан¬ный набор как 1, то в дизъюнкцию вписывается отрицание xi (т.е. );ЛитератураЛитература
<br>1. Кристофидес Н. Теория графов. Алгоритмический подход.
<br>2. Харари Ф. Теория графов.
<br>3. Новиков Ф.А., Дискретная математика для программистов
|
|
