Для булевой функции f, заданной в таблице: а) найти сокращенную ДНФ; б) найти ядро

Для булевой функции f, заданной в таблице: а) найти сокращенную ДНФ; б) найти ядро функции; в) получить все тупиковые ДНФ и указать, какие из них являются минимальными; г) на картах Карно указать ядро и покрытия, соответствующие минимальным ДНФ. x1 x2 x3 x4 fx1,x2,x3,x4 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 1 0 1 0 1 0 0 1 1 0 1 0 1 1 1 1 1 0 0 0 0 1 0 0 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0

А) СДНФ содержит 10 слагаемых,
x1x2
x3x4 00
01
11
10
00 1 1 1 0
01 0 0 1 1
11 0 1 0 1
10 0 1 1 1
fx1,x2,x3,x4=x2x4∨x1x3x4∨x1x2x4∨x1 x3 x4∨x1 x2x3
Сокращенная ДНФ содержит 5 слагаемых.
б)
0000 *
0-00
-1-0
0100 * * *
01-0 *
0110
*
* *
-100
*
1001
* *
-110
*
1010
* *
1-01
1100
*
* *
1-10
0111
*
10-1
1011
*
*
11-0 *
1101
*
*
011-
1110
*
*
*
101-
110-
Простые импликанты: 0-00, 1-01, 1-10, 10-1, 011-, 101-, 110-, -1-0
0000 0100 0110 1001 1010 1100 0111 1011 1101 1110
0-00 + +
1-01
+
+
1-10
+
10-1
+
+
011-
+
+
101-
+
+
110-
+
+
-1-0
+ +
+
+
Выбираем импликант x2x4 -1-0
0000 1001 1010 0111 1011 1101
0-00 +
1-01
+
+
1-10
+
10-1
+
+
011-
+
101-
+
+
110-
+
Выбираем импликант x1x3x4 1-01
0000 1010 0111 1011
0-00 +
1-10
+
10-1
+
011-
+
101-
+
+
Выбираем импликант x1x2x3 101-
0000 0111
0-00 +
011-
+
Выбираем оставшиеся импликанты x1 x3 x4 0-00 и x1 x2 x3 011-
Данные импликанты образуют ядро: f=x2x4∨x1x3x4∨x1x2x3∨x1 x3 x4∨x1 x2 x3 .
в) получить все тупиковые ДНФ и указать, какие из них являются минимальными;
 Тупиковой ДНФ (ТДНФ) функции f называется такая ДНФ ее простых импликант, из которых нельзя выбросить ни одного импликанта, не изменив функции f.
x1
x2
x3
x4
0000 0100 0110 1001 1010 1100 0111 1011 1101 1110
1 0 - 0 0 + +
2 1 - 0 1
+
+
3 1 - 1 0
+
4 1 0 - 1
+
+
5 0 1 1 -
+
+
6 1 0 1 -
+
+
7 1 1 0 -
+
+
8 - 1 - 0
+ +
+
+
f=x2x4∨x1x2x3∨x1x3x4∨x1 x3 x4∨x1 x2 x3
x1
x2
x3
x4
0000 0100 0110 1001 1010 1100 0111 1011 1101 1110
1 0 - 0 0 + +
2 1 - 0 1
+
+
3 1 - 1 0
+
4 1 0 - 1
+
+
5 0 1 1 -
+
+
6 1 0 1 -
+
+
7 1 1 0 -
+
+
8 - 1 - 0
+ +
+
+
f=x1 x3 x4∨x1x3x4∨x1x3x4∨x1x2x4∨x1 x2 x3∨x2x4
x1
x2
x3
x4
0000 0100 0110 1001 1010 1100 0111 1011 1101 1110
1 0 - 0 0 + +
2 1 - 0 1
+
+
3 1 - 1 0
+
4 1 0 - 1
+
+
5 0 1 1 -
+
+
6 1 0 1 -
+
+
7 1 1 0 -
+
+
8 - 1 - 0
+ +
+
+
f=x2x4∨x1 x3 x4∨x1 x2 x3∨x1x2 x4∨x1x3x4∨x1x2x3
f=x2x4∨x1 x3 x4∨x1 x2 x3∨x1x2 x4∨x1x2x3∨x1x2x3
f=x2x4∨x1 x3 x4∨x1 x2 x3∨x1x2 x4∨x1x3x4∨x1x3x4
Минимальными являются f=x2x4∨x1 x3 x4∨x1 x2 x3∨x1x2x3∨x1x3x4
г) на картах Карно указать ядро и покрытия, соответствующие минимальным ДНФ.
Покрытие ядра
f=x2x4∨x1x3x4∨x1x2x3∨x1 x3 x4∨x1 x2 x3
Построим функцию Патрика:
0000 0100 0110 1001 1010 1100 0111 1011 1101 1110
-1-0
+ +
+
+ K1=x2x4
0-00 + +
K2=x1 x3 x4
1-01
+
+
K3=x1x3x4
1-10
+
K4=x1x3x4
10-1
+
+
K5=x1x2x4
011-
+
+
K6= x1 x2 x3
101-
+
+
K7=x1x2x3
110-
+
+
K8x1x2x3
P=K2K1+K2K1+K6K3+K5K4+K7K1+K8K6K5+K7K3+K8K1==K1K2K6K3+K5K4+K7K5+K7K3+K8==K1K2K6K3K4+K4K5+K3K7+K5K7K5K3+K5K8+K3K7+K7K8==K1K2K6K3K4K3K5+K4K5K3K5+K3K7K3K5+K5K7K3K5+K3K4K5K8+K4K5K5K8++K3K7K5K8+K5K7K5K8+K3K4K3K7+K4K5K3K7+K3K7K3K7+K5K7K3K7+K3K4K7K8+K4K5K7K8+K3K7K7K8+K5K7K7K8==K1K2K6K3K4K5+K3K4K5+K3K5K7+K3K5K7+K3K4K5K8+K4K5K8++K3K5K7K8+K5K7K8+K3K4K7+K3K4K5K7+K3K7+K3K5K7+K3K4K7K8+K4K5K7K8+K3K7K8+K5K7K8==K1K2K6K3K4K5+K3K5K7+K4K5K8+K5K7K8+K3K7==K1K2K3K4K5K6+K1K2K3K5K6K7+K1K2K4K5K6K8+K1K2K5K6K7K8+K1K2K3K6K7
Таким образом, рассматриваемая функция имеет пять сокращенных ДНФ:
D1=x2x4∨x1 x3 x4∨x1x3x4∨x1x3x4∨x1x2x4∨ x1 x2 x3D2=x2x4∨x1 x3 x4∨x1x3x4∨x1x2x4∨ x1 x2 x3∨x1x2x3D3=x2x4∨x1 x3 x4∨x1x3x4∨x1x2x4∨ x1 x2 x3∨x1x2x3D4=x2x4∨x1 x3 x4∨x1x2x4∨ x1 x2 x3∨x1x2x3∨x1x2x3D5=x2x4∨x1 x3 x4∨x1x3x4∨ x1 x2 x3∨x1x2x3
Видно, что у все сокращенных ДНФ есть общая часть- это ядро, входящее в каждую сокращенную ДНФ x2x4∨x1 x3 x4∨ x1 x2 x3.
Минимальная ДНФ D5=x2x4∨x1 x3 x4∨x1x3x4∨ x1 x2 x3∨x1x2x3