8. Из вершины x7 выходят дуги в вершины x6 и x8. Но вершина x6 уже имеет постоянную метку, поэтому ее не рассматриваем. Вычислим ярлык для x8: l¢8=25+7=32. Так как l¢8 = 32<33, то присваиваем вершине x8 новую временную метку (32, x7).
Осталась одна временная метка – у вершины x8. Делаем ее постоянной и заканчиваем работу алгоритма.
Теперь по построенным меткам выпишем кратчайшие пути из x0 в каждую вершину. Например, для вершины x8: длина пути – это ярлык l8 = 32. Сам путь получим по вторым компонентам постоянных меток, двигаясь от x8 до x0: у вершины x8 – это x7, у x7 – это x5, у x5 – это x2, у x2 – это x0.
Получили путь: x0 ® x2 ® x5 ® x7 ® x8. Аналогично получим остальные кратчайшие пути.
Ответ: кратчайший путь от x0
до x1: x0 ® x1 имеет длину 10, до x2: x0 ® x2 имеет длину 11,
до x3: x0 ® x2 ® x3 имеет длину 15, до x4: x0 ® x1 ® x4 имеет длину 23,
до x5: x0 ® x2 ® x5 имеет длину 17, до x6: x0 ® x1 ® x6 имеет длину 22,
до x7: x0 ® x2 ® x5 ® x7 имеет длину 25,
до x8: x0 ® x2 ® x5 ® x7 ® x8 имеет длину 32.
14.0. Для приведенной ниже формулы булевой функций f найти ДНФ, КНФ, СДНФ, СКНФ методом равносильных преобразований: 
.
Решение. ДНФ: 
.
СДНФ: 
.
КНФ: 
&1
.
СКНФ: 
.
Ответ: ДНФ 
, СДНФ 
, КНФ x,
СКНФ 
.
15.0. Для булевых функций задачи 14 найти СДНФ и СКНФ табличным способом.
x | y | z | f |
0 | 0 | 0 | 0 |
0 | 0 | 1 | 0 |
0 | 1 | 0 | 0 |
0 | 1 | 1 | 0 |
1 | 0 | 0 | 1 |
1 | 0 | 1 | 1 |
1 | 1 | 0 | 1 |
1 | 1 | 1 | 1 |
Решение. Составим таблицу истинности для функции 
.
СДНФ:
.
СКНФ:
.
16.0. Для булевых функций задачи 14 постройте полином Жегалкина.
Решение. Рассмотрим полином по модулю 2 от трех переменных с неопределенными коэффициентами:
.
Используя таблицу истинности, составляем систему уравнений для определения коэффициентов 
:
,
,
,
,
,
,
,
.
Находим, что все коэффициенты равны нулю, кроме 
.
Ответ: x.
17.0. Укажите существенные и фиктивные переменные булевой функции задачи 14.
Решение. Переменная x является существенной, так как существуют два набора (0, 0, 0) и (1, 0, 0) на которых функция принимает разные значения, т. е. f(0, 0, 0) = 0 ≠ 1 = f(1, 0, 0).
Переменная y является фиктивной, так как f(0, 0, 0) = 0 = f(0, 1, 0),
f(0, 0, 1) = 0 = f(0, 1, 1), f(1, 0, 0) = 1 = f(1, 1, 0), f(1, 0, 1) = 1 = f(1, 1, 1).
Переменная z является фиктивной, так как f(0, 0, 0) = 0 = f(0, 0, 1),
f(0, 1, 0) = 0 = f(0, 1, 1), f(1, 0, 0) = 1 = f(1, 0, 1), f(1, 1, 0) = 1 = f(1, 1, 1).
Ответ: x – существенная, y и z – фиктивные переменные.
18.0. Получите сокращенную ДНФ задания 14 методом Блейка.
Решение. Применим метод Блейка к СДНФ:
.
Ответ: x.
19.0. Получите сокращенную ДНФ задания 14 из КНФ.
Решение. Рассмотрим в качестве КНФ построенную в задаче 15 СКНФ:
= x.
Ответ: x.
20.0. Получите все тупиковые ДНФ для функции f = (0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1). Выделите из них минимальные.
Решение.
Таблица истинности для заданной функции имеет вид:
x1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
x2 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
x3 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
x4 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
f | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 |
1. Составим СДНФ:
2. Получим сокращенную ДНФ:
3. Обозначим: 
, 
, 
,
P1 | P2 | P3 | P4 | P5 | |
K1 | 1 | 1 | 0 | 0 | 0 |
K2 | 0 | 1 | 0 | 1 | 0 |
K3 | 0 | 0 | 1 | 0 | 1 |
K4 | 0 | 0 | 0 | 1 | 1 |
, P1= (0, 1, 0, 0),
P2= (0, 1, 1, 0), P3= (1, 0, 1, 1),.
P4= (1, 1, 1, 0), P5= (1, 1, 1, 1).
4. (1)&(1˅2)&(3)&(2˅4)&(3˅4) = 1&2&3 ˅ 1&3&4 ˅ 1&2&3&4 =
5. = 1&2&3˅1&3&4.
Ответ: данная функция имеет две тупиковые ДНФ 
и 
, которые являются и минимальными ДНФ.
21.0. Постройте структурную схему для любой минимальной ДНФ предыдущей задачи.
Решение. Построим схему для формулы 
.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 |
