2.2.2.4. Алгоритм минимизации функций в классе ДНФ

1. Строим СДНФ функции f.

2. Строим сокращенную ДНФ функции f.

3. С помощью матрицы покрытий и решеточного выражения строим все ТДНФ функции f.

4. Среди построенных ТДНФ выбираем все минимальные дизъюнктивные нормальные формы функции f.

Пример 40.

В классе нормальных форм минимизировать функцию f=01011110.

Решение.

Для построения сокращенной ДНФ используем алгоритм Куайна. Строим СДНФ для функции f. Таблица значений имеет вид (табл. 43):

Таблица 43

x1 x2 x3 f
0 0 0 0 0
1 0 0 1 1
2 0 1 0 0
3 0 1 1 1
4 1 0 0 1
5 1 0 1 1
6 1 1 0 1
7 1 1 1 0

СДНФ (1): № 1, 3, 4, 5, 6 (табл.44):

Таблица 44

№ слагаемого Слагаемое СДНФ
1
2
3
4
5

2. Проводим все операции неполного склеивания (табл. 45):

Таблица 45

Слагаемые Склеивание по Результат
1, 2 х2
1, 4 х1
3, 4 х3
3, 5 х2

Дальнейшее склеивание невозможно. Все слагаемые предыдущего шага участвовали в операции склеивания, поэтому сокращенная ДНФ имеет вид:

UUU.

3. Строим матрицу покрытий (табл. 46).

Таблица 46

Простые импликанты Конституенты единицы функции f
x1 x2 x3 001 011 100 101 110
1 0 - 1 + +
2 - 0 1 + +
3 1 0 - + +
4 1 - 0 + +

Последовательно выбираем слагаемые: № 4, 1, 2 (табл. 47).

Таблица 47

Простые импликанты Конституенты единицы функции f
x1 x2 x3 001 011 100 101 110
1 0 - 1 + +
2 - 0 1 + +
3 1 0 - + +
4 1 - 0 + +

В результате МДНФ имеет вид: UU.

Пример 41.

Построить МДНФ функции f=11011011.

Решение.

Для построения сокращенной ДНФ используем минимизационную карту (табл. 48).

Шаг 1.

Таблица 48

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 0
3 0 1 1 1 1 3 3 1
4 1 0 0 2 2 0 4 1
5 1 0 1 2 3 1 5 0
6 1 1 0 3 2 2 6 1
7 1 1 1 3 3 3 7 1

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

Таблица 49

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 0
3 0 1 1 1 1 3 3 1
4 1 0 0 2 2 0 4 1
5 1 0 1 2 3 1 5 0
6 1 1 0 3 2 2 6 1
7 1 1 1 3 3 3 7 1

Шаг 3.

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

Таблица 50

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 0
3 0 1 1 1 1 3 3 1
4 1 0 0 2 2 0 4 1
5 1 0 1 2 3 1 5 0
6 1 1 0 3 2 2 6 1
7 1 1 1 3 3 3 7 1

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

Таблица 51

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 0
3 0 1 1 1 1 3 3 1
4 1 0 0 2 2 0 4 1
5 1 0 1 2 3 1 5 0
6 1 1 0 3 2 2 6 1
7 1 1 1 3 3 3 7 1

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

Таблица 52

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 0
3 0 1 1 1 1 3 3 1
4 1 0 0 2 2 0 4 1
5 1 0 1 2 3 1 5 0
6 1 1 0 3 2 2 6 1
7 1 1 1 3 3 3 7 1

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

Строим матрицу покрытий (табл. 53).

Таблица 53

Простые импликанты Конституенты единицы функции f
x1 x2 x3 000 001 011 100 110 111
1 0 0 - + +
2 1 1 - + +
3 0 - 1 + +
4 1 - 0 + +
5 - 0 0 + +
6 - 1 1 + +

Последовательно выбираем слагаемые: № 1, 2, 5, 6 (табл. 54).

Таблица 54

Простые импликанты Конституенты единицы функции f
x1 x2 x3 000 001 011 100 110 111
1 0 0 - + +
2 1 1 - + +
3 0 - 1 + +
4 1 - 0 + +
5 - 0 0 + +
6 - 1 1 + +

В результате МДНФ имеет вид:

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

Еще по теме 2.2.2.4. Алгоритм минимизации функций в классе ДНФ:

  1. 2.2.1 Алгоритм обратного распространения ошибки
  2. ПРИЛОЖЕНИЕ 3. ОСНОВНЫЕ ФУНКЦИИ, ИСПОЛЬЗУЕМЫЕ В ПО МОДЕЛИРОВАНИЯ ПРОЦЕДУРЫ ГИСТОГРАММНОГО АНАЛИЗА
  3. 2.3 АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ
  4. Минимизация целевой функции на основе адаптивных алгоритмов
  5. 3.1. Жизненная сила элемента
  6. Содержание дисциплины
  7. Перечень вопросов к экзамену на первом курсе
  8. СПОСОБЫ ЗАДАНИЯ И ФОРМЫ ПРЕДСТАВЛЕНИЯ БУЛЕВЫХ ФУНКЦИЙ
  9. Практическое занятие №1 "Исследование функции на непрерывность. Вычисление пределов"
  10. 3. Практическое занятие №3 "Исследование функции с помощью производной"
  11. 2.1.2. Методика свободной сортировки понятий как инструмент изучения семантического пространства образа мира подростка.
  12. §1.8. Функции -значной логики
  13. §4.3. Рекурсивные функции
  14. Минимизация ДНФ
  15. Минимизация КНФ
  16. Полиномиальное разложение булевых функций
  17. 2.2.2. Минимизация нормальных форм