Метод Квайна поиска Сокднф

• Название: Метод Квайна поиска Сокднф
• Дата: 09.12.2020
• Размер: 92.04 Kb.
• Имя файла: abd0746177ad9d1f.docx
• Тип: Документы; #158598
• страница: 1 из 6

Метод Квайна поиска СокДНФ
Поэтапная минимизация логических функций предполагает следующий алгоритм минимизации: ДСНФ  СокДНФ (Сокращенная ДНФ)  ТДНФ (Тупиковая ДНФ)  МДНФ (Минимальная ДНФ).
Для записи логической функции в СокДНФ необходимо в исходной функции, записанной в ДСНФ, произвести все операции неполного склеивания и поглощения.
Операция полного склеивания: xy  x y  x (члены xy и x y склеены по переменной y ).



Операция неполного склеивания: xy  x y  x  xy  x y .



Операция поглощения: x  xy  x (член xy поглощается членом x ).
Порядок нахождения СокДНФ по Квайну:

1. 
   Преобразовать исходную логическую функцию к ДСНФ.
   

2. 
   В полученной ДСНФ выполнить все операции неполного склеивания.
   

2. 
   Выполнить все операции поглощения.
   

2. 
   Повторять шаги 2 и 3 до тех пор, пока среди конъюнкций не останется склеивающихся между собой.
   

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

1

2

3

4

5

6

f x1, x 2, x3, x 4

x 4

x3 x 4

x 2

x 4

x 2 x3 x 4 x1 x 2 x3

 x1 x 2 x3 x4

x1

x 2

x3

x1

x 2

x1

x3

x1

x 4

1-2*

x 4

x3 x 4

x 4

 x3

x4

x1

x 2

x3

x1

x 2

x1

x 2

x3

x1

x 2

1

- 3 *

x1

x3

x4

1

- 4