Задача 1. Построить минимальную или кратчайшую ДНФ булевой функции, заданной
вектор-столбцом значений f(a,b,c,d) = (0111001100011111)
Решение.
1. По заданному вектор-столбцу значений функции построим таблицу истинности.
|
bcd
|
f(a,b,c,d)
|
|
0000
|
0
|
|
0001
|
1
|
|
0010
|
1
|
|
0011
|
1
|
|
0100
|
0
|
|
0101
|
0
|
|
0110
|
1
|
|
0111
|
1
|
|
1000
|
0
|
|
1001
|
0
|
|
1010
|
0
|
|
1011
|
1
|
|
1100
|
1
|
|
1101
|
1
|
|
1110
|
1
|
|
1111
|
1
|
2. По таблице истинности построим совершенную ДНФ, которая в нашем
примере имеет вид
СовДНФ = 
Используя формулы обобщенного
склеивания и поглощения  выполним
склеивания и поглощения и получим ДНФ = 
3. Представим каждую конъюнкцию троичным вектором, перенумеруем их и
применим алгоритм Блейка-Порецкого.
Положим i = 2 и j = 1. Векторы 2 и 1 не склеиваются.
Увеличиваем i на
1, т.е. i = 3, j = 1. Векторы 3 и 1 склеиваются по первой компоненте,
образуя вектор -11-. Но данный вектор поглощается вектором 2, значит, он не вносится
в список.
Увеличиваем j на 1, т.е. j = 2. Векторы 3 и 2 не склеиваются.
Увеличиваем i на
1, т.е. i = 4, j = 1. Векторы 4 и 1 не склеиваются; j = 2. Векторы
4 и 2 склеиваются по второй компоненте, образуя вектор 0-11, который
поглощается вектором 1 и, следовательно, в список не вносится. j = 3, и
векторы 4 и 3 не склеиваются.
Теперь i = 5. Нетрудно убедиться, что вектор 5 не склеивается с
вектором 1, но склеивается с вектором 2 по второй компоненте, образуя вектор
–11. Полученный вектор не поглощается ни одним из существующих в списке
векторов, следовательно, он заносится в список с номером 7 и помечается парой,
состоящей из номеров векторов, которые, склеиваясь, образуют данный вектор.
Далее из списка удаляются векторы, поглощаемые вектором 7. В нашем примере это
векторы 5 и 6.
Поскольку 5 и 6 векторы удалены из списка, i = 7. Легко увидеть, что вектор 7 может склеиваться лишь
с векторами, которые имеют 0 в третьей или четвертой компоненте, но таких
векторов в списке нет. Значит, множество максимальных интервалов построено.
На языке ДНФ это значит, что построена СокрДНФ = 
4. Обозначим оставшиеся интервалы большими латинскими
буквами и построим матрицу Грея, выделив на ней данные интервалы.
|
Перенумеровав векторы (точки на матрице Грея)
построчно слева направо, построим таблицу Квайна,
строкам которой поставлены в соответствие максимальные интервалы (простые импликанты СокрДНФ), а столбцам –
точки (полные конъюнкции СовДНФ). На пересечении i-й
строки и j-го столбца ставится 1, если
и только если j-й
вектор принадлежит i-ому интервалу.
В нашем примере таблица Квайна
имеет 5 строк и 10 столбцов.
|
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
|
A
|
|
1
|
1
|
1
|
1
|
|
|
|
|
|
|
B
|
|
|
|
1
|
1
|
|
|
1
|
1
|
|
|
C
|
|
|
|
|
|
1
|
1
|
1
|
1
|
|
|
D
|
1
|
1
|
|
|
|
|
|
|
|
|
|
E
|
|
1
|
|
1
|
|
|
|
1
|
|
1
|
Для того, чтобы построить
кратчайшую ДНФ исходной функции, необходимо найти кратчайшее покрытие таблицы Квайна. Это покрытие <
i>P ищется следующим
образом.
Выбирается столбец с наименьшим числом единиц, в
данном случае это столбец 1. Строка D вносится в покрытие P = {D}, и из
таблицы удаляется строка D и все
столбцы, на пересечении с которыми данная строка содержит 1. В данном случае
это столбцы 1 и 2.
В новой таблице, состоящей уже из четырех строк и
восьми столбцов, ищется столбец с наименьшим числом единиц. Это столбец 3.
Строка A заносится в покрытие, т.е. P = {
D, A}и удаляется из таблицы. После этого из таблицы
удаляются столбцы 3, 4 и 5, которые содержат 1 в строке A.
Аналогичным образом можно установить, что строки C
и E войдут в
покрытие, т.е. P = {D,A,C,E}.
Записав интервалы в виде конъюнкций,
получим, что КратДНФ имеет вид .
В данном примере кратчайшая ДНФ является и
минимальной. В общем случае, чтобы найти минимальную ДНФ, необходимо приписать
строкам таблицы веса, равные внешним компонентам соответствующих интервалов. В
терминах ДНФ это значит, что каждой строке приписывается ранг соответствующей
элементарной конъюнкции. Требуется найти такое покрытие, чтобы сумма весов
входящих в него интервалов была минимальной.
Таким образом, в результате получим КратДНФ = МинДНФ = .
Задача 2. Построить минимальную или кратчайшую
ДНФ булевой функции, заданной вектором
столбцом значений f(a,b,c,d) = (0111001101011111).
Задача 3. Построить минимальную или кратчайшую
ДНФ булевой функции, заданной вектором
столбцом значений f(a,b,c,d) = (0101011101111100).
Задача 4. Построить минимальную или кратчайшую
ДНФ булевой функции, заданной вектором
столбцом значений f(a,b,c) = (00111011).
Задача 5. Построить минимальную или
кратчайшую ДНФ булевой функции, заданной
ДНФ =  .
<Задача 6. Построить минимальную или кратчайшую
ДНФ булевой функции, заданной формулой  .
|