4. Примеры решения типовых задач контрольной работы
1.Для выражения z(z Ú y) Ú x z , пользуясь правилами де Моргана, получить ДНФ и упростить её, если возможно.
z(z Ú y) Ú x z = (zz Ú zy) Ú x z = zy Ú x z = zy × x z = (z Ú y)(x Ú z) = zx Ú z Ú yx Ú yz = z Ú yx Использовали x x = 0; x × x = x; x Ú xy = x; xy = x Ú y; x Ú y = x y .
2.а) Для функции f1 (x, y) = ( y → x) + xy составить таблицу истинности, найти по ней полином Жегалкина, СДНФ, СКНФ, упростить СДНФ.
Составим таблицу истинности:
x |
y |
y → x |
xy |
f1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
Найдём полином Жегалкина:
P(x, y) = a0 + a1 x + a2 y + a3 xy
P(0,0) = 1 = a0 . Отсюда a0 = 1.
P(0,1) = 0 = a0 |
+ a2 |
= 1+ a2 , |
a2 = 0 . |
|||||||||||||||||||||||||||
P(1,0) = 1 = a0 |
+ a1 |
= 1+ a1 , |
a1 = 0 |
|||||||||||||||||||||||||||
P(1,1) = 0 = a0 |
+ a1 + a2 |
+ a3 |
= 1+ 1+ a3 = a3 , a3 = 0 . |
|||||||||||||||||||||||||||
P = 1 + y |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
Составим СДНФ по наборам, на которых f (x, y) = 1 |
||||||||||||||||||||||||||||||
f1 |
= |
|
|
|
x |
|
|
|
|
- СДНФ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
x |
y |
y |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
Упростим СДНФ, используя склеивание по «x»: |
|
|
|
Ú x |
|
= |
|
. |
||||||||||||||||||||||
x |
y |
y |
y |
|||||||||||||||||||||||||||
Составим СКНФ по наборам, на которых f (x, y) = 0 |
||||||||||||||||||||||||||||||
f1 |
= (x |
|
)( |
|
|
|
) |
- СКНФ |
||||||||||||||||||||||
y |
x |
y |
||||||||||||||||||||||||||||
б) |
Для функции |
f 2 (x, y, z) = (x + |
|
|
|
|
|
|||||||||||||||||||||||
yz) |
(x → y) составить таблицу |
|||||||||||||||||||||||||||||
истинности. Найти по ней полином Жегалкина, СДНФ, СКНФ. По карте Карно упростить СДНФ и нарисовать эквивалентную РКС.
26
Составим таблицу истинности:
x y z yz x + yz x → y |
f 2 (x, y, z |
|||||
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
|
|
P(x, y, z) = |
a0 |
+ a1 x + a2 y + a3 z + a4 xy + a5 xz + a6 yz + a7 xyz |
||
P(x, y, z) = f (x, y, z)
P(0,0,0) = 1 = a0 отсюда a0 = 1
P(0,0,1) = 1 = a0 + a3 = 1+ a3 , a3 = 0
P(0,1,0) = 1 = a0 + a2 = 1+ a2 , a2 = 0
P(0,1,1) = 1 = a0 + a2 + a3 + a6 = 1+ a6 , a6 = 0
P(1,0,0) = 0 = a0 + a1 = 1+ a1 , a1 = 1
P(1,0,1) = 1 = a0 + a1 + a3 + a5 = 1+ 1+ a5 , a5 = 1
P(1,1,0) = 0 = a0 + a1 + a2 + a4 = 1+ 1+ a4 , a4 = 0
P(1,1,1) = 0 = a0 + a1 + a2 + a3 + a4 + a5 + a6 + a7 = 1+ 1+ 1+ a7 , a7 = 1
P(x, y, z) = 1 + x + xz + xyz
Составим СДНФ: x y z x yz xy z xyz x yz
Составим СКНФ: (x y z)(x y z)(x y z) .
Заполним карту Карно
y |
00 |
01 |
11 |
10 |
z |
|
|
|
|
x |
|
|
|
|
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
27
ДНФ: x yz
РКС: 
в) Составить таблицу Поста для системы функций f1 и f 2 . Проверить полноту системы и найти базисы.
Таблица Поста имеет вид:
Классы |
T0 |
T1 |
L |
S |
M |
f |
|
|
|
|
|
f1 |
- |
- |
+ |
+ |
- |
f 2 |
- |
- |
- |
- |
- |
Так как:
f1 (0,0) = 1; f1 T0 и f1 M f1 (1,1) = 0; f1 T1
f1 (0,0) = 1 = f1 (1,1); f1 (0,1) = 0 = f1 (1,0); f1 S
P1 (x, y) = 1 + y; f1 L
f 2 (0,0,0) = 1; f 2 T0 и f2 M
f2 (1,1,1) = 0; f 2 T1
f2 (0,1,0) = 1 = f2 (1,0,1); f2 S
P2 (x, y, z) = 1+ x + xz + xyz; f2 L
f2 (x, y, z) не линейная, т.к. P(x, y, z) содержит xz и xyz .
28
Система функций полная, т.к. в таблице Поста нет столбца из одних «+». Проверяем на полноту каждую функцию. f1 - не составляет полной системы, т.к. нет функции не входящей в классы L и S. f 2 - образует полную систему и является базисом. Других базисов нет.
3. Для данного графа требуется составить структурную матрицу, по ней найти все простые пути из вершины i в вершину j и совокупность всех сечений между этими вершинами.
i=1, j=5
Для данного графа составим структурную матрицу S, а затем вычеркнем из неё 5-ю строчку и 1=й столбец, тем самым получим минор M51:
æ |
1 e12 |
|
e13 |
0 |
e15 |
ö |
||||||||||||
ç |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
÷ |
ç |
e12 |
1 |
|
0 |
|
e24 |
0 |
÷ |
||||||||||
S=ç |
0 |
|
|
e32 |
1 |
|
e34 |
e35 |
÷ |
|||||||||
ç |
0 |
|
|
|
|
|
|
|
|
|
|
1 |
0 |
÷ |
||||
ç |
|
|
|
e24 |
e34 |
÷ |
||||||||||||
ç |
|
|
|
|
|
|
|
|
|
|
|
|
e |
|
1 |
÷ |
||
e |
|
|
|
|
|
|
|
|
|
|||||||||
|
|
0 |
|
e |
54 |
|||||||||||||
è |
15 |
|
|
|
|
|
ø |
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
35 |
|
|
|
|
|||
|
|
|
|
e12 |
|
|
|
e13 |
0 |
|
e15 |
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|||||||||
М51= |
1 |
0 |
|
e24 |
|
0 |
|
|
||||||||||
e32 |
1 |
|
e34 |
|
e35 |
|
|
|||||||||||
|
|
|
|
e24 |
|
|
|
e34 |
1 |
|
0 |
|
|
|||||
Найдём определитель, используя теорему разложения. Данный определитель удобно раскладывать по 2-й строке, поскольку она содержит два нулевых элемента.
М51=1× |
|
e13 |
0 |
e15 |
|
|
|
|
e12 |
|
e13 |
e15 |
|
|
|
||||||||||
1 e34 |
e35 |
|
Ú |
|
e32 |
|
1 e35 |
|||||
|
|
e34 |
1 |
0 |
|
|
|
|
e24 |
|
e34 |
0 |
Применяя ещё раз теорему разложения для первого определителя по 1- ой строке и для второго определителя по 3-му столбцу, получим:
М51=1× (e13 |
|
e34 |
e35 |
|
Ú e15 |
|
1 |
e34 |
|
) Ú e24 (e15 |
|
e32 |
|
1 |
|
|
Ú e35 |
|
e12 |
|
e13 |
|
|
) = |
|
|
|
|
|
|
|
|
|||||||||||||||||
|
1 |
0 |
|
|
e34 |
1 |
|
e24 |
e34 |
|
e24 |
e34 |
||||||||||||
= e13e34 0 Ú e13e351Ú e1511Ú e15e34 e34 Ú e24 e15 e32 e34 Ú e24e151e24 Ú e24 e35e12 e34 Ú e24 e35e13 × e24 =
29
= e13e35 e15 e12 e24 e43e35
Использовали при упрощении свойства:
x × 0 = 0, x ×1 = x, x × x = 0, x Ú xy = x.
При записи ответа рёбра идут в порядке прохождения вершин от i=1 к j=5.
Для нахождения сечений между вершинами i=1 и j=5 заменим дизъюнкцию на конъюнкцию, а конъюнкцию на дизъюнкцию и раскроем скобки.
(e13 Ú e35 ) × e15 × (e12 Ú e24 Ú e43 Ú e35 ) =
= e13e15e12 |
e13e15e24 |
e13e15e43 |
e13e15e35 e35e15e12 e35e15e24 e35e15e43 e35e15e35 = |
= e13e15e12 |
e13e15e24 |
e13e15e43 |
e35e15 |
Использовали свойства: x × |
x = x, x Ú xy = x . |
||
Примечание. Согласно теореме разложения определитель равен сумме (в данном случае дизъюнкции) произведений элементов любой строки (или столбца), умноженных на свои алгебраические дополнения (в данном случае просто миноры).
4.Заданы сеть (рис.7а) и начальный поток f (рис.7б). Требуется построить максимальный поток и найти минимальное сечение, считая вершину с номером 1 источником и вершину с номером 4 стоком.
Рис.7
1). Поток f из s=1 в t=4 имеет величину Valf |
= 5 + 3 + 2 = 3 + 3 + 4 = 10 . Путь |
|
из s в t: 1 → 3 → 4 . |
|
|
Пометки вершин: s=(0;∞ ) → |
(+ 1, 3 = 7 − 2 = 5) → |
t=(+ 3, 4 = 6 − 4 = 2) . |
Добавка к потоку: = min |
j = min{5,2} = 2 . |
|
|
|
30 |
Строим новый поток f1 (рис.8), Valf1 |
= Valf + |
= 10 + 2 = 12 . |
||
2). Путь из s в t для потока f1: 1 → |
3 ← |
2 → 4 . |
|
|
Пометки вершин: s=(0;¥ ) ® |
(+ 1, D 3 |
= 7 - 4 = 3) ¬ |
(- 3, D 2 = 3 + 2 = 5) ® t= |
|
(+ 2, 4 = 7 − 3 = 4) . |
|
|
|
|
Добавка к потоку: = min |
j = min{3,5,4} = 3 . |
|
||
Строим новый поток f2 (рис.9), Valf2 |
= Valf1 + |
= 12 + 3 = 15 . |
||
Рис.8 Рис.9
3). Путь из s в t, на котором возможно увеличение потока не построить, поскольку не дойти до стока. Значит поток f2 (рис.9) максимален: Valfmax = 15 .
Помеченная вершина: Мs={1}. Непомеченные вершины: Мt={3,2,4}. Минимальное сечение: e13 × e12 × e14 .
Величина минимального сечения: 7+5+3=15=Valf 2 .
5.Введём отношение сравнимости R:x сравнимо с y по модулю m тогда и только тогда, когда x и y имеют одинаковые остатки от деления на m. Запись x ≡ y(mod m). Рассмотрим отношение сравнимости для случая m=2 на множестве А={1,2,3,4,5}. Для этого отношения нужно:
а) записать отношение R
б) построить матрицу смежности и граф отношения
в) проверить, является ли отношение рефлексивным, симметричным, транзитивным.
Отношение R определяется множеством пар
31