Метод минимизирующих карт.
Алгоритм метода минимизирующих карт включает в себя следующие этапы:
1. Любая формула приводится к СДНФ.
2. Составляется таблица всевозможных сочетаний переменных.
3. Из таблицы вычеркиваются те строки, которые не содержат конституенты СДНФ. Конъюнкции этих строк вычеркиваются в других строках.
4. В каждой строке оставляются конъюнкции с минимальным количеством переменных.
5. Из каждой строки выбирается олна конъюнкция и составляется ДНФ.
6. Из построенных ДНФ выбирается минимальная.
ПРИМЕР
Дана СДНФ
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | |
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | |
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | * |
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | |
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | |
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | * |
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | |
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() |
* - помечены строки, не содержащие конституенты СДНФ.
После соответствующих преобразований получаем следующую таблицу
![]() | ![]() | ||||||
![]() | ![]() | ||||||
* | |||||||
![]() | ![]() | ||||||
![]() | ![]() | ||||||
* | |||||||
![]() | ![]() | ||||||
![]() | ![]() |
После всевозможного перебора остаются следующие МДНФ: