Поделиться Поделиться

Реализация метода Квайна – Мак-Класки

С помощью этого метода строят тупиковые НДФ (нормальные дизъюнктивные формы) и из множества тупиковых выбирают минимальные НДФ.

Основой алгоритма являются следующие эквивалентности:

Реализация метода Квайна – Мак-Класки - Инвестирование - 1 ;

Реализация метода Квайна – Мак-Класки - Инвестирование - 2 ;

Реализация метода Квайна – Мак-Класки - Инвестирование - 3 .

Первая часть алгоритма:

1. По заданной СНДФ строят эквивалентную НДФ, получаемую как дизъюнкцию всех нетривиальных попарных склеек. Если некоторый столбец булевых функций ни с чем не склеивается, то его переписывают заново.

2. После склеивания возможно появление элементарных одинаковых конъюнкций. Лишние нужно убрать.

3. Если дальнейшие склеивания неосуществимы, то переход к п. 4, иначе – к п. 1.

В результате приходят к некоторой сокращенной нормальной дизъюнктивной форме.

Вторая часть алгоритма (решение задачи о минимальном покрытии):

4. Рассматривают каждую элементарную конъюнкцию из полученной формулы и проверяют её вхождение в отдельные слагаемые исходной СНДФ.

5. Среди полученных элементарных конъюнкций могут оказаться и лишние. Их нужно отбросить.

В результате получают тупиковые формы, реализующие минимальное покрытие. Их может оказаться несколько. Минимальная НДФ является одной из тупиковых.

Замечания:

– данный алгоритм неизбежно включает в себя прямой перебор;

– алгоритм является NP-сложным (с ростом размерности сложность возрастает быстрее любой степени размерности);

– дальнейшее упрощение можно осуществлять, отказавшись от требования нормальности.

Пример. Требуется минимизировать булеву функцию, заданную в совершенной нормальной дизъюнктивной форме:

Реализация метода Квайна – Мак-Класки - Инвестирование - 4

Реализация метода Квайна – Мак-Класки - Инвестирование - 5

Реализация метода Квайна – Мак-Класки - Инвестирование - 6

Реализация метода Квайна – Мак-Класки - Инвестирование - 7 .

Сопоставим с этой функцией булеву матрицу

Реализация метода Квайна – Мак-Класки - Инвестирование - 8 .

Рассмотрим первый и второй столбцы. Запишем их дизъюнкцию и вынесем общие множители:

Реализация метода Квайна – Мак-Класки - Инвестирование - 9 Реализация метода Квайна – Мак-Класки - Инвестирование - 10 .

Формально это действие сводится к тому, что переменная X2 подвергается удалению. Сопоставим с отсутствием этой переменной символ 2 (возможно использование и других символов):

Реализация метода Квайна – Мак-Класки - Инвестирование - 11 .

Итак, первый и второй столбцы склеиваются. Первый и третий столбцы не склеиваются, так как в компонентах имеется более одного отличия. Далее по очереди выполняем склеивание столбцов, если это возможно (т.е. если в компонентах ровно одно отличие). Формальные действия для отдельных компонент отображаются следующими соотношениями:

(0,1) Реализация метода Квайна – Мак-Класки - Инвестирование - 12 2; (1,0) Реализация метода Квайна – Мак-Класки - Инвестирование - 12 2; (0,2) Реализация метода Квайна – Мак-Класки - Инвестирование - 12 2; (2,0) Реализация метода Квайна – Мак-Класки - Инвестирование - 12 2;

(1, 2) Реализация метода Квайна – Мак-Класки - Инвестирование - 12 2; (2, 1) Реализация метода Квайна – Мак-Класки - Инвестирование - 12 2; (2, 2) Реализация метода Квайна – Мак-Класки - Инвестирование - 12 2.

Результаты склеивания заносим в качестве столбцов в новую матрицу. Некоторые столбцы не склеиваются с другими; записываем такие столбцы в новую матрицу без изменений. Чтобы учесть наличие несклеиваемых столбцов, те из них, которые участвуют в склейках, снабжаем дополнительным символом, например «+»:

+ + + + + + + + + + + +

F =

Выписываем преобразованную матрицу, отмечая номера склеиваемых столбцов, номера полученных столбцов и метки участия в дальнейших склейках:

1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 6, 7, 7, 8, 8, 9, 10,12 11,
-1- -2- -3- -4- -5- -6- -7- -8- -9- -10- -11- -12- -13- -14- -15- -16- -17- -18-
+ + + + + + + + + + + + + + +   + +

Повторяем процесс склеивания:

1, 1, 2, 2, 3, 4, 5, 6, 7, 9, 12, 13, 14, 15,
-1- -2- -3- -4- -5- -6- -7- -8- -9- -10- -11- -12- -13- -14- -15-

Некоторые столбцы одинаковы: (1,3), (2,5), (6,7), (8,9), (11,12), (13,14). В каждой группе указанных столбцов оставляем по одному экземпляру и продолжаем склеивание:

-1- -2- -3- -4- -5- -6- -7- -8- -9-
+ + + +   :+   +  
1, 2, 3,
-1- -2- -3- -4- -5- -6-

После того, как в полученной таблице заменили три совпадающих столбца одним, приходим к окончательной сокращенной нормальной дизъюнктивной форме

Полученная таблица соответствует стандартной записи НДФ в следующем виде:

Реализация метода Квайна – Мак-Класки - Инвестирование - 19 .

Таким образом, исходная функция приведена к дизъюнкции простых импликант Реализация метода Квайна – Мак-Класки - Инвестирование - 20 , Реализация метода Квайна – Мак-Класки - Инвестирование - 21 , Реализация метода Квайна – Мак-Класки - Инвестирование - 22 и Реализация метода Квайна – Мак-Класки - Инвестирование - 23 . Для выяснения вопроса о минимальном покрытии строим таблицу импликант:

Реализация метода Квайна – Мак-Класки - Инвестирование - 20
Реализация метода Квайна – Мак-Класки - Инвестирование - 25
Реализация метода Квайна – Мак-Класки - Инвестирование - 26
Реализация метода Квайна – Мак-Класки - Инвестирование - 27
Реализация метода Квайна – Мак-Класки - Инвестирование - 20 + +   +   +   +   + + +
Реализация метода Квайна – Мак-Класки - Инвестирование - 21     + + + +            
Реализация метода Квайна – Мак-Класки - Инвестирование - 22             + + + +    
Реализация метода Квайна – Мак-Класки - Инвестирование - 23   +             +      

Выбрасывание последней импликанты не приводит к неэквивалентности, т.е. не появляются пустые столбцы. Поэтому минимальная дизъюнктивная нормальная форма (НДФ) для исходной функции имеет вид

Реализация метода Квайна – Мак-Класки - Инвестирование - 32 .

Первая часть рассмотренного алгоритма программируется довольно просто. Нахождение минимального покрытия – нетривиальная задача. В некоторых случаях возможно существование нескольких тупиковых форм.

Контрольное задание

Произвести минимизацию СНДФ методом Квайна – Мак-Класки. Построить таблицу истинности для полученной функции и сравнить с исходной.

Варианты задания


1. 0 1 0 1 0 1 1 0 1 0 1

0 0 1 0 1 1 1 0 0 1 1

0 0 0 1 1 1 0 1 1 1 1

0 0 0 0 0 0 1 1 1 1 1

2.0 1 0 1 0 1 1 1 0 1

0 0 1 1 0 0 1 0 1 1

0 0 0 0 0 0 0 1 1 1

0 0 0 0 1 1 1 1 1 1

3.0 1 0 0 1 1 1 0 1

0 0 1 0 1 0 0 1 1

0 0 0 1 1 0 1 1 1

0 0 0 0 0 1 1 1 1

4.0 1 0 1 0 1 1 1 0 0

0 0 1 1 0 1 0 1 0 1

0 0 0 0 1 1 0 0 1 1

0 0 0 0 0 0 1 1 1 1

5.0 1 0 1 1 1 0 1 0

0 0 1 1 0 0 1 1 1

0 0 0 0 1 0 0 0 1

0 0 0 0 0 1 1 1 1

6.0 1 1 0 1 0 1 0 1 1 0

0 0 1 1 1 0 0 1 1 0 1

0 0 0 1 1 0 0 0 0 1 1

0 0 0 0 0 1 1 1 1 1 1

7.1 0 1 0 1 0 1 0 1 1

0 1 0 1 1 0 0 1 1 1

0 0 1 1 1 0 0 0 0 1

0 0 0 0 0 1 1 1 1 1

8.0 1 1 1 0 1 0 1 0 0 1

0 0 1 0 1 0 1 1 0 1 1

0 0 0 1 1 0 0 0 1 1 1

0 0 0 0 0 1 1 1 1 1 1

9.1 0 1 0 1 0 0 1 1

0 1 1 0 0 0 0 0 1

0 0 0 1 1 0 1 1 1

0 0 0 0 1 1 1 1 1

10. 0 1 0 0 1 0 1 0 1 1 0 1

0 0 1 0 0 1 1 0 0 0 1 1

0 0 0 1 1 1 1 0 0 1 1 1

0 0 0 0 0 0 0 1 1 1 1 1

11. 1 0 1 0 1 1 1 1 0 1

1 0 0 1 1 0 1 0 1 1

0 1 1 1 1 0 0 1 1 1

0 0 0 0 0 1 1 1 1 1

12. 0 1 0 1 0 0 0

0 1 0 0 1 1 1

0 0 1 1 1 0 1

0 0 0 0 0 1 1

13. 0 1 0 1 0 1 0 1 0 1 0 1

0 0 1 1 0 0 1 1 0 1 1 1

0 0 0 0 1 1 1 1 0 0 1 1

0 0 0 0 0 0 0 0 1 1 1 1

14. 1 1 1 1 1 0 1 0 1

0 1 0 1 0 0 0 1 1

0 0 1 1 0 1 1 1 1

0 0 0 0 1 1 1 1 1

15. 0 0 1 0 1 0 1 0 1 0 1

0 1 1 1 1 0 0 1 0 1 1

0 0 0 1 1 0 0 0 1 1 1

0 0 0 0 0 1 1 1 1 1 1

16. 0 1 1 0 0 1 0 1 0 0

0 0 1 0 0 0 1 1 0 1

0 0 0 1 0 0 0 0 1 1

0 0 0 0 1 1 1 1 1 1

17. 1 1 0 1 0 1 0 1 0 1 1 1

0 1 0 0 1 1 0 0 1 1 0 1

0 0 1 1 1 1 0 0 0 0 1 1

0 0 0 0 0 0 1 1 1 1 1 1

18. 0 0 1 1 1 0 1 1 0

0 1 1 0 1 1 1 0 1

0 0 0 1 1 0 0 1 1

0 0 0 0 0 1 1 1 1

19. 1 0 1 0 0 0 1 1 0 1

0 1 1 0 1 0 0 0 1 1

0 0 0 1 1 0 0 1 1 1

0 0 0 0 0 1 1 1 1 1

20. 1 0 1 0 1 1 1 0 0 1

1 0 0 1 1 0 1 0 1 1

0 1 1 1 1 0 0 1 1 1

0 0 0 0 0 1 1 1 1 1

21. 1 1 1 0 1 0 1 0 1 1 0 1

0 1 0 1 1 0 0 1 1 0 1 1

0 0 1 1 1 0 0 0 0 1 1 1

0 0 0 0 0 1 1 1 1 1 1 1

22. 0 1 1 0 1 0 0 0 1 1

0 0 1 0 0 1 0 1 1 0

0 0 0 1 1 1 0 0 0 1

0 0 0 0 0 0 1 1 1 1

23. 0 1 0 1 0 1 0 1 0 1 0 1

1 1 0 0 1 1 0 0 1 1 0 0

0 0 1 1 1 1 0 0 0 0 1 1

0 0 0 0 0 0 1 1 1 1 1 1

24. 1 0 1 0 1 0 1 0 1 1

0 1 1 0 0 1 0 1 0 1

0 0 0 1 1 1 0 0 1 1

0 0 0 0 0 0 1 1 1 1

← Предыдущая страница | Следующая страница →