Метод минимизации с помощью карт Вейча

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

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

2. Составляется карта Вейча. Карта Вейча – это таблица всех возможных комбинаций значений переменных. В соответствующие ячейки заносятся единицы, соответствующие конституентам СДНФ.

3. Единицы, стоящие по вертикали и горизонтали, объединяются (по 2, по 4. по 8 и т.д.). Объединение единиц соответствует операциям склеивания и поглощения. Иначе говоря, формируются максимальные подкубы.

4. Для каждого объединения выписываются конъюнкции из элементов, общих для каждой единицы, входящих в объединение..

5. Выше полученные конъюнкции составляют МДНФ.

Карты Вейча удобны при поиске МДНФ функций двух, трех и четырех переменных.

n=2

СДНФ=

1

МДНФ=

n=3

СДНФ=

1

МДНФ=

n=4

СДНФ=

	1	1

МДНФ=

Дата добавления: 2014-01-04