Метод Карно

Сущность метода Карно заключается в построении специальных диаграмм, представляющих собой прямоугольные таблицы. Каждой конъюнкции исходной логической функции соответствует одна из клеток таблицы. Главная особенность диаграмм Карно заключается в том, что конъюнкциям, которые могут быть склеены соответствуют соседние по строке или по столбцу клетки.

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

Заполнение диаграмм Карно упрощается при использовании эталонных диаграмм. На эталонной диаграмме клетки помечены номерами соответствующих конъюнкций исходной логической функции. Номера конъюнкций соответствуют двоичным комбинациям входных сигналов в таблице истинности логической функции.

При использовании метода Карно идея заключается в том, что отмеченные клетки диаграммы объединяются в группы по 2, 4 и 8 клеток. Каждая отмеченная клетка должна входить по крайней мере в одну группу. Каждая группа должна содержать только отмеченные клетки. Группы клеток должны образовывать квадраты или прямоугольники. При этом число групп должно быть минимальным.

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

Метод Карно практически можно использовать лишь для минимизации логических функций не более, чем четырех переменных.