<<
>>

2.2.2.2. Построение сокращенной ДНФ в классе дизъюнктивных нормальных форм

Этот метод не отличается большой эффективностью, но он прост для изложения и не требует введения дополнительных понятий.

Пусть булева функция задана таблицей истинности или СДНФ.

Минимизирующая карта булевой функции представляет собой квадратную матрицу 2n´2n, где n – число переменных. Первые столбцы отводят для аргументов, дальнейшие – для их всевозможных конъюнкций по 2, по 3 и т. д. сомножителей, предпоследний - для конъюнкции всех аргументов, последний – для значений функции.

Шаг 1. Столбцы для аргументов, как обычно в таблицах истинности, заполняются всевозможными наборами 0 и 1. В столбцах для конъюнкций проставляются десятичные значения двоичных чисел, соответствующих наборам значений аргументов. Последний столбец заполняется соответственно значению функции.

Далее работа чередуется по строкам, по столбцам.

Шаг 2. Вычеркиваются строки, в которых функция обращается в нуль.

Шаг 3. В каждом столбце из сохранившихся чисел вычеркивают те, равные которым уже вычеркнуты в этом столбце на предыдущем шаге.

Шаг 4. В сохранившихся строках выбирают «значения» наименьших по числу множителей конъюнкций (включая и конъюнкции с одним множителем – переменные) и обводят их кружочками.

Шаг 5. Если в одном столбце обведено несколько одинаковых чисел, то вычеркивают все, кроме одного.

Шаг 6. С помощью оставшихся обведенных чисел образуют конъюнкции. Для этого переводят каждое число в двоичную систему. Переменную, которой соответствует 1, берут сомножителем без отрицания, которой соответствует 0 – с отрицанием.

Шаг 8. Составляют дизъюнкцию полученных конъюнкций. В результате получаем сокращенную ДНФ функции.

Пример 36.

Построить сокращенную ДНФ для функции f=11100101.

Решение.

1.Строим минимизационную карту (табл. 24):

Таблица 24

x1 x2 x3 x1x2 x1x3 x2x3 x1x2x3 f(x1, x2, x3)
0 0 0 0 0 0 0 0 1
1 0 0 1 0 1 1 1 1
2 0 1 0 1 0 2 2 1
3 0 1 1 1 1 3 3 0
4 1 0 0 2 2 0 4 0
5 1 0 1 2 3 1 5 1
6 1 1 0 3 2 2 6 0
7 1 1 1 3 3 3 7 1

2.

Вычеркиваем строки, в которых функция обращается в нуль (табл. 25):

Таблица 25

x1 x2 x3 x1x2 x1x3 x2x3 x1x2x3 f(x1, x2, x3)
0 0 0 0 0 0 0 0 1
1 0 0 1 0 1 1 1 1
2 0 1 0 1 0 2 2 1
3 0 1 1 1 1 3 3 0
4 1 0 0 2 2 0 4 0
5 1 0 1 2 3 1 5 1
6 1 1 0 3 2 2 6 0
7 1 1 1 3 3 3 7 1

3. В каждом столбце из сохранившихся чисел вычеркиваем те, равные которым уже вычеркнуты в этом столбце на предыдущем шаге (табл. 26):

Таблица 26

x1 x2 x3 x1x2 x1x3 x2x3 x1x2x3 f(x1, x2, x3)
0 0 0 0 0 0 0 0 1
1 0 0 1 0 1 1 1 1
2 0 1 0 1 0 2 2 1
3 0 1 1 1 1 3 3 0
4 1 0 0 2 2 0 4 0
5 1 0 1 2 3 1 5 1
6 1 1 0 3 2 2 6 0
7 1 1 1 3 3 3 7 1

4.

В сохранившихся строках выбираем «значения» наименьших по числу множителей конъюнкций (включая и конъюнкции с одним множителем – переменные) и обводим их (табл. 27):

Таблица 27

x1 x2 x3 x1x2 x1x3 x2x3 x1x2x3 f(x1, x2, x3)
0 0 0 0 0 0 0 0 1
1 0 0 1 0 1 1 1 1
2 0 1 0 1 0 2 2 1
3 0 1 1 1 1 3 3 0
4 1 0 0 2 2 0 4 0
5 1 0 1 2 3 1 5 1
6 1 1 0 3 2 2 6 0
7 1 1 1 3 3 3 7 1

5. Если в одном столбце обведено несколько одинаковых чисел, то вычеркиваем все, кроме одного (табл. 28):

Таблица 28

x1 x2 x3 x1x2 x1x3 x2x3 x1x2x3 f(x1, x2, x3)
0 0 0 0 0 0 0 0 1
1 0 0 1 0 1 1 1 1
2 0 1 0 1 0 2 2 1
3 0 1 1 1 1 3 3 0
4 1 0 0 2 2 0 4 0
5 1 0 1 2 3 1 5 1
6 1 1 0 3 2 2 6 0
7 1 1 1 3 3 3 7 1

6.

С помощью оставшихся обведенных чисел образуем конъюнкции. Для этого переводим каждое число в двоичную систему. Переменную, которой соответствует 1, берем сомножителем без отрицания, 0 – с отрицанием. Составляем дизъюнкцию полученных конъюнкций.

Сокращенная ДНФ имеет вид:

Пример 37.

Построить сокращенную ДНФ функции f=1111010010101111 с использованием минимизационной карты.

Решение.

Строим минимизационную карту (табл. 29) и пошагово выполняем алгоритм.

Шаг 1.

Таблица 29

x1 x2 x3 x4 x1x2 x1x3 x1x4 x2x3 x2x4 x3x4 x1x2x3 x1x2x4 x1x3x4 x2x3x4 x1x2x3x4 f
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 1 0 0 1 0 1 1 0 1 1 1 1 1
2 0 0 1 0 0 1 0 1 0 2 1 0 2 2 2 1
3 0 0 1 1 0 1 1 1 1 3 1 1 3 3 3 1
4 0 1 0 0 1 0 0 2 2 0 2 2 0 4 4 0
5 0 1 0 1 1 0 1 2 3 1 2 3 1 5 5 1
6 0 1 1 0 1 1 0 3 2 2 3 2 2 6 6 0
7 0 1 1 1 1 1 1 3 3 3 3 3 3 7 7 0
8 1 0 0 0 2 2 2 0 0 0 4 4 4 0 8 1
9 1 0 0 1 2 2 3 0 1 1 4 5 5 1 9 0
10 1 0 1 0 2 3 2 1 0 2 5 4 6 2 10 1
11 1 0 1 1 2 3 3 1 1 3 5 5 7 3 11 0
12 1 1 0 0 3 2 2 2 2 0 6 6 4 4 12 1
13 1 1 0 1 3 2 3 2 3 1 6 7 5 5 13 1
14 1 1 1 0 3 3 2 3 2 2 7 6 6 6 14 1
15 1 1 1 1 3 3 3 3 3 3 7 7 7 7 15 1

Шаг 2.

Вычеркиваем строки, в которых функция обращается в нуль (табл. 30):

Таблица 30

x1 x2 x3 x4 x1x2 x1x3 x1x4 x2x3 x2x4 x3x4 x1x2x3 x1x2x4 x1x3x4 x2x3x4 x1x2x3x4 f
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 1 0 0 1 0 1 1 0 1 1 1 1 1
2 0 0 1 0 0 1 0 1 0 2 1 0 2 2 2 1
3 0 0 1 1 0 1 1 1 1 3 1 1 3 3 3 1
4 0 1 0 0 1 0 0 2 2 0 2 2 0 4 4 0
5 0 1 0 1 1 0 1 2 3 1 2 3 1 5 5 1
6 0 1 1 0 1 1 0 3 2 2 3 2 2 6 6 0
7 0 1 1 1 1 1 1 3 3 3 3 3 3 7 7 0
8 1 0 0 0 2 2 2 0 0 0 4 4 4 0 8 1
9 1 0 0 1 2 2 3 0 1 1 4 5 5 1 9 0
10 1 0 1 0 2 3 2 1 0 2 5 4 6 2 10 1
11 1 0 1 1 2 3 3 1 1 3 5 5 7 3 11 0
12 1 1 0 0 3 2 2 2 2 0 6 6 4 4 12 1
13 1 1 0 1 3 2 3 2 3 1 6 7 5 5 13 1
14 1 1 1 0 3 3 2 3 2 2 7 6 6 6 14 1
15 1 1 1 1 3 3 3 3 3 3 7 7 7 7 15 1

Шаг 3. В каждом столбце из сохранившихся чисел вычеркиваем те, равные которым уже вычеркнуты в этом столбце на предыдущем шаге (табл.

31):

Таблица 31

x1 x2 x3 x4 x1x2 x1x3 x1x4 x2x3 x2x4 x3x4 x1x2x3 x1x2x4 x1x3x4 x2x3x4 x1x2x3x4 f
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 1 0 0 1 0 1 1 0 1 1 1 1 1
2 0 0 1 0 0 1 0 1 0 2 1 0 2 2 2 1
3 0 0 1 1 0 1 1 1 1 3 1 1 3 3 3 1
4 0 1 0 0 1 0 0 2 2 0 2 2 0 4 4 0
5 0 1 0 1 1 0 1 2 3 1 2 3 1 5 5 1
6 0 1 1 0 1 1 0 3 2 2 3 2 2 6 6 0
7 0 1 1 1 1 1 1 3 3 3 3 3 3 7 7 0
8 1 0 0 0 2 2 2 0 0 0 4 4 4 0 8 1
9 1 0 0 1 2 2 3 0 1 1 4 5 5 1 9 0
10 1 0 1 0 2 3 2 1 0 2 5 4 6 2 10 1
11 1 0 1 1 2 3 3 1 1 3 5 5 7 3 11 0
12 1 1 0 0 3 2 2 2 2 0 6 6 4 4 12 1
13 1 1 0 1 3 2 3 2 3 1 6 7 5 5 13 1
14 1 1 1 0 3 3 2 3 2 2 7 6 6 6 14 1
15 1 1 1 1 3 3 3 3 3 3 7 7 7 7 15 1

Шаг 4. В сохранившихся строках выбираем «значения» наименьших по числу множителей конъюнкций (включая и конъюнкции с одним множителем – переменные) и обводим их (табл. 32):

Таблица 32

x1 x2 x3 x4 x1x2 x1x3 x1x4 x2x3 x2x4 x3x4 x1x2x3 x1x2x4 x1x3x4 x2x3x4 x1x2x3x4 f
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 1 0 0 1 0 1 1 0 1 1 1 1 1
2 0 0 1 0 0 1 0 1 0 2 1 0 2 2 2 1
3 0 0 1 1 0 1 1 1 1 3 1 1 3 3 3 1
4 0 1 0 0 1 0 0 2 2 0 2 2 0 4 4 0
5 0 1 0 1 1 0 1 2 3 1 2 3 1 5 5 1
6 0 1 1 0 1 1 0 3 2 2 3 2 2 6 6 0
7 0 1 1 1 1 1 1 3 3 3 3 3 3 7 7 0
8 1 0 0 0 2 2 2 0 0 0 4 4 4 0 8 1
9 1 0 0 1 2 2 3 0 1 1 4 5 5 1 9 0
10 1 0 1 0 2 3 2 1 0 2 5 4 6 2 10 1
11 1 0 1 1 2 3 3 1 1 3 5 5 7 3 11 0
12 1 1 0 0 3 2 2 2 2 0 6 6 4 4 12 1
13 1 1 0 1 3 2 3 2 3 1 6 7 5 5 13 1
14 1 1 1 0 3 3 2 3 2 2 7 6 6 6 14 1
15 1 1 1 1 3 3 3 3 3 3 7 7 7 7 15 1

Шаг 5. Если в одном столбце обведено несколько одинаковых чисел, то вычеркиваем все, кроме одного (табл. 33):

Таблица 33

x1 x2 x3 x4 x1x2 x1x3 x1x4 x2x3 x2x4 x3x4 x1x2x3 x1x2x4 x1x3x4 x2x3x4 x1x2x3x4 f
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 1 0 0 1 0 1 1 0 1 1 1 1 1
2 0 0 1 0 0 1 0 1 0 2 1 0 2 2 2 1
3 0 0 1 1 0 1 1 1 1 3 1 1 3 3 3 1
4 0 1 0 0 1 0 0 2 2 0 2 2 0 4 4 0
5 0 1 0 1 1 0 1 2 3 1 2 3 1 5 5 1
6 0 1 1 0 1 1 0 3 2 2 3 2 2 6 6 0
7 0 1 1 1 1 1 1 3 3 3 3 3 3 7 7 0
8 1 0 0 0 2 2 2 0 0 0 4 4 4 0 8 1
9 1 0 0 1 2 2 3 0 1 1 4 5 5 1 9 0
10 1 0 1 0 2 3 2 1 0 2 5 4 6 2 10 1
11 1 0 1 1 2 3 3 1 1 3 5 5 7 3 11 0
12 1 1 0 0 3 2 2 2 2 0 6 6 4 4 12 1
13 1 1 0 1 3 2 3 2 3 1 6 7 5 5 13 1
14 1 1 1 0 3 3 2 3 2 2 7 6 6 6 14 1
15 1 1 1 1 3 3 3 3 3 3 7 7 7 7 15 1

Шаг 6. Сокращенная ДНФ имеет вид

<< | >>
Источник: Лекции - Дискретная математика. 2016

Еще по теме 2.2.2.2. Построение сокращенной ДНФ в классе дизъюнктивных нормальных форм: