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

Для булевой функции f, заданной в таблице 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 1 1 1 1 1 1 0 0 1 1 1 0 0 1 1 1

А) Находим сокращенную ДНФ функции методом Квайна-МакКласки.
Составляем таблицу склеиваний, группируя конъюнкции по числу единиц в векторе, отображающем эту конъюнкцию.
0000* 000-*
00-0*
0-00*
-000* 00--
0-0-
-00-
-0-0
0001*
0010*
0100*
1000* 00-1*
0-01*
-001*
001-*
-010*
010-*
100-*
10-0* --01
0011*
0101*
1001*
1010* -101*
1-01*
1-10
1101*
1110* 11-1
111-
1111*
Получили сокращенную ДНФ:
fx1,x2,x3,x4=x1x2⋁x1x3⋁x2x3⋁x2x4⋁x3x4⋁
⋁x1x3x4⋁x1x2x4⋁x1x2x3.
б) Найдем ядро функции.
Составляем матрицу покрытий простыми импликантами единиц функции.
0000 0001 0010 0011 0100 0101 1000 1001 1010 1101 1110 1111
00-- V V V V
0-0- V V
V V
-00- V V
V V
-0-0 V
V
V
V
--01
V
V
V
V
1-10
V
V
11-1
V
V
111-
V V
Ядровыми являются импликанты 00--, 0-0-

.
в) Чтобы найти все тупиковые ДНФ, удалим из таблицы покрытия ядровые импликанты и все столбцы, покрываемые этими импликантами.
1000 1001 1010 1101 1110 1111
a -00- V V
b -0-0 V
V
c --01
V
V
d 1-10
V
V
e 11-1
V
V
f 111-
V V
Воспользуемся методом Петрика - обозначим импликанты буквами a,d,…,f, каждому столбцу поставим в соответствие элементарную дизъюнкцию и построим КНФ:
a⋁ba⋁cb⋁dc⋁ed⋁fe⋁f=
Раскрываем скобки, производим все поглощения, получаем ДНФ, каждая конъюнкция которой совместно с ядровыми импликантами определяет тупиковую ДНФ:
=ade⋁bcf⋁bcde⋁abef⋁acdf.
Таким образом, имеем всего 5 тупиковых ДНФ, а именно:
из конъюнкции ade следует
fx1,x2,x3,x41ТДНФ=x1x2⋁x1x3⋁x2x3⋁x1x3x4⋁x1x2x4,
из конъюнкции bcf следует
fx1,x2,x3,x42ТДНФ=x1x2⋁x1x3⋁x2x4⋁x3x4⋁x1x2x3,
из конъюнкции abef следует
fx1,x2,x3,x43ТДНФ=x1x2⋁x1x3⋁x2x3⋁x2x4⋁x1x2x4⋁x1x2x3,
из конъюнкции acdf следует
fx1,x2,x3,x44ТДНФ=x1x2⋁x1x3⋁x2x3⋁x3x4⋁x1x3x4⋁x1x2x3,
из конъюнкции bcde следует
fx1,x2,x3,x45ТДНФ=x1x2⋁x1x3⋁x2x4⋁x3x4⋁x1x3x4⋁x1x2x4.
Нетрудно подсчитать число символов в каждой тупиковой ДНФ и обнаружит, что имеется единственная тупиковая ДНФ, которая является минимальной:
fx1,x2,x3,x4МДНФ=fx1,x2,x3,x42ТДНФ==x1x2⋁x1x3⋁x2x4⋁x3x4⋁x1x2x3.
Интересно заметить, что тупиковая ДНФ fx1,x2,x3,x41ТДНФ содержит на один символ больше, чем минимальная, хотя число элементов в конъюнкции ДНФ Петрика одинаково.
г) Построим карты Карно для первых двух тупиковых ДНФ, из которых минимальной является вторая.
Для минимальной ДНФ есть следующие покрытия:
fx1,x2,x3,x4МДНФ=x1x2⋁x1x3⋁x2x4⋁x3x4⋁x1x2x3.
69405579375x1x2\x3x4 00 01 11 -438157937510
823595-9525823595-952500 1 -61595-95251 1 1
01 1 1 0 0
11 0 23558531751 1 1
6940551333510 1 1 0 -36195133351
Красным цветом выделены ядровые импликанты.
Построим покрытия, соответствующие первой тупиковой ДНФ.
fx1,x2,x3,x41ТДНФ=x1x2⋁x1x3⋁x2x3⋁x1x3x4⋁x1x2x4.
x1x2\x3x4 -285755651500 01 11 10
823595-9525823595-952500 1 1 1 1
01 1 1 0 0
11 0 -6159531751 22542531751 1
10 -20955161791 1 0 1