Карта Карно — это графический способ минимизации булевых функций, обеспечивающий относительную простоту работы с большими выражениями.
Общие сведения о минимизации логических функций
Процесс минимизации логических функций считается одной из важных типовых задач в схемотехнике. Уровень сложности логических функций, а, следовательно, сложность и стоимость выполняющей эти функции схемной реализации (цепи), являются пропорциональными количеству логических операций и количеству вхождений переменных или их отрицаний. В теории любые логические функции могут быть упрощены непосредственно при помощи логических аксиом и теорем, но обычно подобные преобразования подразумевают громоздкие выкладки.
Кроме того, процесс упрощения булевых выражений не всегда может быть отображён в форме алгоритма. По этой причине более целесообразно применять специализированные алгоритмические методики минимизации, которые позволяют осуществлять упрощение функций более простыми процедурами, оперативно и без ошибок. К таким методикам следует отнести, к примеру, методику карт Карно и многие другие. Эти методики считаются самыми пригодными для обычной практики, в частности это касается и метода, позволяющего минимизировать логические функции с применением карт Карно. Метод карт Карно обладает достаточной наглядностью при количестве переменных не больше шести. В тех вариантах, когда количество аргументов превышает шесть, как правило, используется метод Квайна-Мак-Класки.
Минимизация записи логической функции с помощью карт Карно
Карта Карно является графическим способом минимизации переключательных функций, который способен обеспечить сравнительно простой процесс работы с выражениями больших размеров и устранение потенциальных гонок. Этот способ может быть представлен в виде процедур попарного неполного склеивания и поэлементного поглощения. Карты Карно могут рассматриваться как преобразованные необходимым способом таблицы истинности функций. Карты Карно могут быть представлены так же как определенная плоская развертка n-мерного булева куба.
Карты Карно изобрёл в 1952-ом году Эдвард В. Вейч, а усовершенствовал их в 1953-ем году Морис Карно, физик из «Bell Labs», и эти карты предназначались для упрощения цифровых электронных схем. В карту Карно булевы переменные могут передаваться из таблицы истинности, а упорядочиваться они могут при помощи кода Грея, в котором каждое последующее число может отличаться от предыдущего лишь одним разрядом.
Главным методом, позволяющим минимизировать логические функции, представленные в виде СДНФ или СКНФ считается процедура попарного неполного склеивания и элементарного поглощения. Операция попарного склеивания может быть осуществлена среди двух термов (членов), содержащих одинаковые переменные, вхождения которых (прямые и инверсные) должны совпадать для всех переменных, помимо одной. В таком случае все переменные, кроме этой одной, могут быть вынесены за скобки, а оставшиеся в скобках прямое и инверсное вхождение одной переменной должны быть подвергнуты склейке.
Это означает, что основной задачей при минимизации СДНФ и СКНФ может считаться поиск термов, которые пригодны к склейке с последующим поглощением, что для больших форм может превратиться в достаточно сложную задачу. А Карты Карно способны предоставить наглядные методы отыскания таких термов.
Общеизвестно, что булевы функции N переменных, которые представлены в форме СДНФ или СКНФ, способны обладать 2N различными термами. Все эти члены могут составлять определённую структуру, которая топологически является эквивалентной N–мерному кубу. При этом любые два терма, которые соединены ребром, являются пригодными для склейки и поглощения. На рисунке ниже представлена простая таблица истинности для функции из двух переменных, соответствующий этой таблице двумерный куб (квадрат), а также двумерный куб с обозначением членов СДНФ и эквивалентная таблица для группировки термов.
Рисунок 1. Таблица истинности для функции из двух переменных. Автор24 — интернет-биржа студенческих работ
Если функция имеет три переменные, то необходимо использовать трёхмерный куб. Это выполнить, конечно, более сложно и при меньшей наглядности, но с технической точки зрения вполне возможно. На рисунке ниже в качестве примера изображена таблица истинности для булевой функции трёх переменных, а также куб, который ей соответствует.
Рисунок 2. Таблица истинности для булевой функции трёх переменных, а также куб, который ей соответствует. Автор24 — интернет-биржа студенческих работ
Как следует из рисунка, для трёхмерного варианта могут быть более сложные конфигурации термов. К примеру, четыре терма, которые принадлежат одной грани куба, могут объединяться в один терм при поглощении двух переменных. В общем случае можно утверждать, что 2K термов, которые принадлежат одной K–мерной грани гиперкуба, могут склеиваться в один терм, при этом будут поглощены K переменных.
Для того чтобы упростить работу с булевыми функциями, имеющими большое количество переменных, существует очень удобный способ. Куб, который представляет собой структуру термов, может быть развёрнут на плоскость как показано на рисунке выше.
Данный приём обеспечивает возможность представления булевых функций с количеством переменных более двух в форме плоской таблицы. При этом необходимо учитывать, что порядок кодов термов в таблице (00 01 11 10) может не соответствовать порядку следования двоичных чисел, а клетки, которые находятся в крайних столбцах таблицы, могут соседствовать между собой.
Аналогично можно осуществлять работу с функциями четырёх, пяти и более переменных. Примеры таблиц для N=4 и N=5 представлены на рисунке ниже.
Рисунок 3. Примеры таблиц для N=4 и N=5. Автор24 — интернет-биржа студенческих работ
Для данных таблиц необходимо учитывать, что соседними считаются клетки, которые находятся в соответствующих клетках крайних столбцов и соответствующих клетках верхней и нижней строки. Для таблиц, имеющих пять и больше переменных, следует учесть также, что квадраты 4х4 виртуально расположены друг над другом в третьем измерении, поэтому соответственные клетки двух соседних квадратов 4х4 считаются соседними, и соответствующие им термы могут быть склеены.
