Задать вопрос юристу

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. 1.4. ПОСТРОЕНИЕ ДИЗЪЮНКТИВНОЙ НОРМАЛЬНОЙ ФОРМЫ* СВОБОДНОЙ ОТ СОСТЯЗАНИЙ
  2. 2.2.2.1. Алгоритм Куайна построения сокращенной ДНФ
  3. 2.2.2.4. Алгоритм минимизации функций в классе ДНФ
  4. Дизъюнктивные нормальные формы
  5. 2.2 Дизъюнктивные нормальные формы.
  6. 2.2.2.3. Построение всех тупиковых ДНФ
  7. §1.6. Дизъюнктивные нормальные формы
  8. Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы
  9. Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы
  10. 2.2.2. Минимизация нормальных форм
  11. 3.2. Построение кривой нормального распределения по эмпирическим данным
  12. Аналитические методы построения сокращенной д. н. ф.
  13. 1.5.1 Построение доверительного интервала для мате-матического ожидания, если дисперсия а заранее известна. Таблица стандартного нормального распределения.
  14. Глава 2. Математические основы построения классов ПСП GMW и их свойства
  15. Минимизация ДНФ
  16. Нормальный глаз – нормальное зрение
  17. Дизъюнктивные суждения
  18. с) Дизъюнктивное суждение (Das disjunktive Urteil)
  19. с) Дизъюнктивное умозаключение (Der disjunktive Schiup)
  20. КЛАСС «В СЕБЕ» И КЛАСС «ДЛЯ СЕБЯ»