Минимизация булевых функций с помощью карт Карно.
Карта Карно или карта (диаграмма) Вейча – графический способ минимизации функций алгебры логики. Карты Карно представляют собой определенную таблицу истинности обычно для двух, трех и четырех переменных и отличаются друг от друга способом обозначения строк и столбцов таблиц истинности. На рисунке представлены карты Вейча для двух, трех и четырех переменных соответственно.
Согласно принятой форме построения карт соседними также считаются клетки первой и последней строк, клетки первого и последнего столбцов. Число клеток карты равно числу возможных комбинаций значений переменных (термов) и в каждую клетку записывается значение логической функции, соответствующее данному набору переменных. Если какая-то из возможных комбинаций присутствует в совершенной дизъюнктивной нормальной форме (СДНФ) записи функции, то в соответствующей клетке карты Карно ставится «1». Например, функция
Таким образом, упрощенное выражение логической функции будет иметь вид Таким образом, для того чтобы получить минимизированную логическую функцию, необходимо сгруппировать все соседние клетки карты Карно, содержащие 1, а затем объединить полученные группы с помощью операции дизъюнкции. Метод карт Карно (диаграмм Вейча), по существу, упрощает нахождение склеиваемых конъюнкций в СДНФ исходной логической функции.
|
, заданная таблицей истинности, может быть минимизирована и с помощью карт Карно. Карта Карно для нее будет иметь вид
1
