Минимизация логических функций с помощью карт Карно
Карно — это представление таблицы истинности в виде прямоугольной таблицы с соответствующим числом клеток, каждая из которых отвечает определенной конъюнкции (произведению переменных). Переменные следуют так, чтобы в соседних клетках отличалась только одна из них, т. е. вместо чередования 00; 01; 10 и 11 используют код Грея 00; 01; 11 и 10. Внимание: необходимо учесть, что рабочей частью карты… Читать ещё >
Минимизация логических функций с помощью карт Карно (реферат, курсовая, диплом, контрольная)
При большом числе переменных использование алгебраических преобразований резко усложняется, поэтому применяют карты Карно.
Карно — это представление таблицы истинности в виде прямоугольной таблицы с соответствующим числом клеток, каждая из которых отвечает определенной конъюнкции (произведению переменных). Переменные следуют так, чтобы в соседних клетках отличалась только одна из них, т. е. вместо чередования 00; 01; 10 и 11 используют код Грея 00; 01; 11 и 10. Внимание: необходимо учесть, что рабочей частью карты Карно является часть, выделенная жирным шрифтом (таблица 5) и содержащая в нашем случае 8 клеток, соответствующие 8 строкам таблицы истинности.
Например, левая верхняя клетка, которой соответствуют а; в (указаны выше) и с (указана слева), очевидно, отвечает 1-ой строке таблицы с номером 0. Правая нижняя клетка карты, которой соответствуют переменные а;в и с, отвечает строке таблицы с номером 5, и т. д. Карта Карно для функции, рассмотренной выше в примере 2, представлена в таблице 7.
Таблица 7.
В клетки карты заносим 0 или 1 в соответствии с таблицей истинности 5.
Далее необходимо в карте выделить один или несколько прямоугольников, включающих возможно большее число клеток с «1». При этом прямоугольники могут содержать 2 n клеток, т. е.1, 2, 4, 8 и т. д.
Одна и та же клетка может входить в несколько прямоугольников. В нашем случае таких прямоугольников можно выделить 3, каждому из них соответствует один член искомого уравнения. Для вертикального прямоугольника можно записать:
а? в? с? а? в? с = а? в? (с? с) = а? в .
Для двух оставшихся получаем в? с и, а? с; т. е. ту переменную, которая повторяется дважды — один раз «0», другой «1» — исключаем, а ту, которая не меняется, оставляем. Сокращенная ДНФ функции:
у =а?в?а?с?в?с.
Заметим, что если для функции п переменных, заданных своей таблицей истинности, все возможные наборы переменных можно представить как вершины n-мерного куба со стороной равной 1 (всего вершин будет 2n) в «уравнения» этих прямых или гиперплоскостей, проведенные через те вершины, на которых значение функции равно 1. Карты Карно позволяют эти геометрические идеи использовать при п = 3, 4, 5, для функций, заданных своей таблицей истинности. При больших п карты Карно практически не используются. Надо учесть, что в карте Карно можно объединить клетки в крайних строках (таблица 8), рассматривая карту как цилиндр, и даже в углах, рассматривая карту как шар (таблица 9).
Таблица 8.
Таблица 9.