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. Построение сокращенной ДНФ в классе дизъюнктивных нормальных форм:

  1. Глава 6. Начала логики предложений
  2. СПОСОБЫ ЗАДАНИЯ И ФОРМЫ ПРЕДСТАВЛЕНИЯ БУЛЕВЫХ ФУНКЦИЙ
  3. 1.4. ПОСТРОЕНИЕ ДИЗЪЮНКТИВНОЙ НОРМАЛЬНОЙ ФОРМЫ* СВОБОДНОЙ ОТ СОСТЯЗАНИЙ
  4. СПИСОК ЛИТЕРАТУРЫ
  5. Содержание
  6. 3.3. Элементы алгебры логики
  7. Контрольная работа №2
  8. Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы
  9. Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы
  10. Аналитические методы построения сокращенной д. н. ф.
  11. Дизъюнктивные нормальные формы
  12. Минимизация ДНФ
  13. СОДЕРЖАНИЕ
  14. 2.1.4. Нормальные формы
  15. 2.2.2. Минимизация нормальных форм
  16. 2.2.2.1. Алгоритм Куайна построения сокращенной ДНФ
  17. 2.2.2.2. Построение сокращенной ДНФ в классе дизъюнктивных нормальных форм
  18. 2.2.2.3. Построение всех тупиковых ДНФ
  19. 2.2.2.4. Алгоритм минимизации функций в классе ДНФ
  20. 1.7. Формы представления высказываний