Метод минимизирующих карт.

Алгоритм метода минимизирующих карт включает в себя следующие этапы:

1. Любая формула приводится к СДНФ.

2. Составляется таблица всевозможных сочетаний переменных.

3. Из таблицы вычеркиваются те строки, которые не содержат конституенты СДНФ. Конъюнкции этих строк вычеркиваются в других строках.

4. В каждой строке оставляются конъюнкции с минимальным количеством переменных.

5. Из каждой строки выбирается олна конъюнкция и составляется ДНФ.

6. Из построенных ДНФ выбирается минимальная.

 

ПРИМЕР

 

Дана СДНФ

 

							*
							*

* - помечены строки, не содержащие конституенты СДНФ.

После соответствующих преобразований получаем следующую таблицу

 

							*
							*

 

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