<<
>>

2.2.2.1. Алгоритм Куайна построения сокращенной ДНФ

1. Получить СДНФ функции.

2. Провести все операции неполного склеивания.

3. Провести все операции поглощения.

Пример 35.

Минимизировать функцию f=1111010010101111.

Решение.

1. Строим таблицу значения для данной функции (табл.

20). Строим СДНФ функции. При этом слагаемые нумеруем и записываем в столбец (табл. 21).

Таблица 20

x1 x2 x3 x4 f(x1, x2, x3, х4)
0 0 0 0 0 1
1 0 0 0 1 1
2 0 0 1 0 1
3 0 0 1 1 1
4 0 1 0 0 0
5 0 1 0 1 1
6 0 1 1 0 0
7 0 1 1 1 0
8 1 0 0 0 1
9 1 0 0 1 0
10 1 0 1 0 1
11 1 0 1 1 0
12 1 1 0 0 1
13 1 1 0 1 1
14 1 1 1 0 1
15 1 1 1 1 1

СДНФ (1): № 0, 1, 2, 3, 5, 8, 10, 12, 13, 14, 15.

Таблица 21

№ слагаемого слагаемое
1
2
3
4
5
6
7
8
9
10
11

2. Проводим все операции неполного склеивания.

Первый этап склеивания (табл. 22):

Таблица 22

Слагаемые Склеивание по Результат Новые слагаемые
1, 2 x4 1
1, 3 x3 2
1, 6 x1 3
2, 4 x3 4
2, 5 x2 5
3, 4 x4 6
3, 7 x1 7
5, 9 x1 8
6, 7 x3 9
6, 8 x2 10
7, 10 x2 11
8, 9 x4 12
8, 10 x3 13
9, 11 x3 14
10, 11 x4 15

В первом этапе склеивания участвовали все слагаемые СДНФ, значит, ни одно из исходных слагаемых не войдут в сокращенную ДНФ. После первого этапа склеивания (и возможных поглощений) получаем, что

Пронумеруем дизъюнктивные члены в полученной ДНФ в порядке их следования от 1 до 15 (табл.

23).

Второй этап склеивания:

Таблица 23

Слагаемые Склеивание по Результат
1, 6 x3
2, 4 x4
2, 9 x1
3, 7 x3
9, 13 x2
10, 11 x3
12, 15 x3
13, 14 x4

В процедуре склеивания на втором этапе не принимали участие слагаемые № 5, 8 с предыдущего шага, поэтому после второго этапа склеивания и последующих поглощений получаем, что

Поскольку дальнейшее склеивания невозможны, то это и будет сокращенная ДНФ исходной функции.

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

Еще по теме 2.2.2.1. Алгоритм Куайна построения сокращенной ДНФ:

  1. 2.3. Разработка методики оценки характеристик достоверности прн использовании алгоритмов диагностирования с учетом методической составляющей погрешности, погрешности измерения н дополнительной погрешности.
  2. Мысленный эксперимент
  3. 2.4 Проблема отбора наиболее информативных показателей.
  4. 2.1. Оценка результатов научных проектов
  5. Глава 39. МАССОВЫЙОПРОС ИИНТЕРВЬЮИРОВАНИЕ  
  6. Содержание дисциплины
  7. ПЕРЕЧНЬ ТЕМ ДЛЯ САМОСТОЯТЕЛЬНОГО ИЗУЧЕНИЯ
  8. Перечень вопросов к экзамену на первом курсе
  9. 1.4. ПОСТРОЕНИЕ ДИЗЪЮНКТИВНОЙ НОРМАЛЬНОЙ ФОРМЫ* СВОБОДНОЙ ОТ СОСТЯЗАНИЙ
  10. Знание как сознательный феномен Катречко С.Л.
  11. 2.1. Рабочая программа (объем дисциплины 150 часов)
  12. 3.3. Элементы алгебры логики
  13. Контрольная работа №2
  14. 1.10. Построение профиля местности и определение полей невидимости
  15. Аналитические методы построения сокращенной д. н. ф.
  16. 2.2.2. Минимизация нормальных форм