Алгебр. способ минимизации - тождества и теоремы булевой алгебры

Диаграммы Вейча

Число клеток диаграммы= кол-ву наборов переменных: Nкл=Nнаб=2ⁿ.

ПФ неопределенна:

1) набор переменных в реальном логич. устройстве невозможен; 2) значение функции безразлично.

Краткий алгоритм:

1. Функция в СДНФ (СКНФ) в диаграмму путём 1/0

2. Производится объединение1/0, стоящих рядом.

Замечание. объединять максимально возможное кол-во смежных клеток. Верхняя и нижняя строки – смежные. Левый и правый столбцы – смежные. Угловые клетки – тоже смежные (диаграмму можно мысленно свернуть в тор).

3. Выписываются координаты m-кубов. Объединённая дизъюнкция (конъюнкция) конъюнктивных (дизъюнктивных) координат всех m-кубов и есть минимальная форма.

Целью минимизации min ДНФ/КНФ,с min членов с min кол-ом входящих в них переменных.