1. Составляем таблицу 1 истинности, по которой записываются все минтермы.
Составим таблицу 2.
Таблица 2
Термы 4 ранга
Термы 3 ранга
Термы 2 ранга
*
1-3
2-9
*
1-5*
3-8
*
1-7*
*
2-3
*
2-6
*
4-5
*
4-6
*
5-8*
*
7-8*
8-9
Получили семь импликант: , , , , , ,
2. Составляется таблица 3 минимального покрытия. Если минтерм содержит первичный импликант, то на пересечении соответствующих им строк и столбцов ставится метка.
Простые импликанты
Исходные минтермы
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
Выделим минимальное число импликант, покрывающих минтермы, в столбцах которых нет меток. Все они переходят в аналитический вид функции:
= Ú Ú Ú
Ответ. = Ú Ú Ú – МДНФ.
7.Используя метод Квайна – Мак-Класки, необходимо найти МНДФ функции, принимающей значения 1 на наборах: 0,1,2,3,4,8,9,10,11,12.
Решение
№
x1
x2
x3
x4
f
1.Составим таблицу истинности.
2. Запишем i-группы двоичных номеров. Признаком образования i - й группы является i единиц в двоичном номере единичной строки.
0-группа: 0000
1-группа: 0001, 0010, 0100, 1000
2-группа: 0011, 1001, 1010, 1100
3-группа: 1011
3. Сравним и склеим группы с номерами i и i+1, в результате чего получим :
9.Задать граф следующим образом: перечислением, матрицами смежности и инцидентности.
Решение
Граф можно задать перечислением элементов множества вершин и множества ребер. Для графа, изображенного на рисунке, эти множества: V={A,B,C,D,E}-множество вершин и E={AB,AD,AC,BC,CE,DE }-множество дуг.
Матрица инцидентности – это прямоугольная матрица, число строк которой равно числу вершин, количество столбцов – числу дуг (рёбер) графа. На пересечении строки и столбца ставится 1, если вершина является началом дуги, -1 – если концом дуги, 0 – если вершина и дуга не инцидентны.
AB
AD
AC
BC
CE
DE
A
B
-1
C
-1
-1
D
-1
E
-1
-1
Матрица смежности – это квадратная матрица, размер которой определяется числом вершин в графе. На пересечении строки и столбца ставится 1, если вершины инцидентны и 0 в противном случае.
A
B
C
D
E
A
B
C
D
E
10.Определить следующие основные характеристики графа:
Число рёбер и дуг;
Число вершин;
Коэффициент связности графа;
Степень всех вершин;
Цикломатическое число графа.
Число рёбер -0, число дуг (направленных рёбер)-6, число вершин-5, число компонент связности -1.
Степенью вершины называется число инцидентных ей ребер. В случае дуг точнее говорить о полустепенях вершин.
Полустепень исхода вершины A равна 3, полустепень захода вершины A равна 0, полустепень исхода вершины B-1, полустепень захода вершины B-1,
Цикломатическим числом или циклическим рангом графа называется наименьшее число ребер (дуг), которое необходимо удалить из графа так, чтобы в нем не осталось ни одного цикла. После такого удаления ребер из связного графа будет получено дерево, называемое остовным деревом или остовом графа.
n(G)=q-p+y =6-5+1=2,
где q-число дуг, p-число вершин, y - число компонент связности графа G.
11.Определить, является ли данный граф:
· Планарным или плоским (обосновать ответ и выполнить обратное преобразование)
· Двудольным графом (обосновать ответ и если необходимо, то достроить до двудольного)
· Деревом ( обосновать ответ, в случае циклического графа, привести один из вариантов основного дерева)
· Псевдографом или мультиграфом, или простым графом (обосновать ответ и выполнить необходимые преобразования)
Плоский, так как все пересечения его рёбер являются вершинами графа. Преобразуем этот граф в планарный.
Данный граф не является двудольным, так как содержит циклы нечётной длины, например A-B-C, и поэтому множество его вершин нельзя разделить на две части.
Для того, чтобы преобразовать граф в двудольный, необходимо, например, разбить дугу AB, на две части с добавлением вершин A1. В результате данного преобразования все циклы в графе будут иметь чётную длину, тогда множество вершин можно разделить на две доли (их номера стоят после названия вершины).
Не является деревом, например, остовным деревом может являться
Преобразуем данный граф в мультиграф (граф с параллельными дугами):
Преобразуем данный граф в псевдограф (мультиграф с петлями):
12.Определить метрические характеристики графа: диаметр, радиус, эксцентриситет каждой вершины, центральные вершины.
Чтобы определить центры, радиус, диаметр графа G, найдем матрицу D(G) расстояний между вершинами графа, элементами dij которой будут расстояния между вершинами vi и vj. Для этого воспользуемся графическим представлением графа.
С помощью полученной матрицы для каждой вершины графа G определим наибольшее расстояние из выражения: для i, j = 1, 2, …,5. В результате получаем эксцентриситеты вершин: r(A) = 2, r(B) =2, r(C) =1, r(D) = 1, r(E) =0. Минимальное из полученных чисел является радиусом графа G, максимальное – диаметром графа G. Значит, R(G) = 0 и D(G) = 2, центром является вершина E.
1-3
2-9
1-5*
1-7*
2-3
*
2-6
4-5
4-6
5-8*
7-8*
8-9
= 
-минимальная дизъюнктивная нормальная форма(МДНФ)
Ú 
для i, j = 1, 2, …,5. В результате получаем эксцентриситеты вершин: r(A) = 2, r(B) =2, r(C) =1, r(D) = 1, r(E) =0. Минимальное из полученных чисел является радиусом графа G, максимальное – диаметром графа G. Значит, R(G) = 0 и D(G) = 2, центром является вершина E.