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

Зачем это нужно?

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

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

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

Минимизация логических функций при помощи карт Карно

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

Карты Карно были изобретены в 1952 Эдвардом В. Вейчем и усовершенствованы в 1953 Морисом Карно, физиком из «Bell Labs», и были призваны помочь упростить цифровые электронные схемы.

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

Основным методом минимизации логических функций, представленных в виде СДНФ или СКНФ является операция попарного неполного склеивания и элементарного поглощения. Операция попарного склеивания осуществляется между двумя термами (членами), содержащими одинаковые переменные, вхождения которых (прямые и инверсные) совпадают для всех переменных, кроме одной. В этом случае все переменные, кроме одной, можно вынести за скобки, а оставшиеся в скобках прямое и инверсное вхождение одной переменной подвергнуть склейке. Например:

Возможность поглощения следует из очевидных равенств

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

Как известно, булевы функции N переменных, представленные в виде СДНФ или СКНФ могут иметь в своём составе 2N различных термов. Все эти члены составляют некоторую структуру, топологически эквивалентную N–мерному кубу, причём любые два терма, соединённые ребром, пригодны для склейки и поглощения.

На рисунке изображена простая таблица истинности для функции из двух переменных, соответствующий этой таблице 2-мерный куб (квадрат), а также 2-мерный куб с обозначением членов СДНФ и эквивалентная таблица для группировки термов:

В случае функции трёх переменных приходится иметь дело с трёхмерным кубом. Это сложнее и менее наглядно, но технически возможно. На рисунке в качестве примера показана таблица истинности для булевой функции трёх переменных и соответствующий ей куб.

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

В общем случае можно сказать, что 2K термов, принадлежащие одной K–мерной грани гиперкуба, склеиваются в один терм, при этом поглощаются K переменных.

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

Аналогичным образом можно работать с функциями четырёх, пяти и более переменных. Примеры таблиц для N=4 и N=5 приведены на рисунке. Для этих таблиц следует помнить, что соседними являются клетки, находящиеся в соответственных клетках крайних столбцов и соответственных клетках верхней и нижней строки. Для таблиц 5 и более переменных нужно учитывать также, что квадраты 4х4 виртуально находятся друг над другом в третьем измерении, поэтому соответственные клетки двух соседних квадратов 4х4 являются сосоедними, и соответствующие им термы можно склеивать.

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

Если необходимо получить минимальную ДНФ, то в Карте рассматриваем только те клетки которые содержат единицы, если нужна КНФ, то рассматриваем те клетки которые содержат нули. Сама минимизация производится по следующим правилам (на примере ДНФ):

Далее берём первую область и смотрим какие переменные не меняются в пределах этой области, выписываем конъюнкцию этих переменных, если неменяющаяся переменная нулевая, проставляем над ней инверсию. Берём следующую область, выполняем то же самое что и для первой, и т. д. для всех областей. Конъюнкции областей объединяем дизъюнкцией.
Например(для Карт на 2-ве переменные):

Для КНФ всё то же самое, только рассматриваем клетки с нулями, не меняющиеся переменные в пределах одной области объединяем в дизъюнкции (инверсии проставляем над единичными переменными), а дизъюнкции областей объединяем в конъюнкцию. На этом минимизация считается законченной. Так для Карты Карно на рис.1 выражение в формате ДНФ будет иметь вид:

В формате КНФ:

) по так называемым картам Карно.

Карты Карно — это другое графическое представление таблиц истинности. Структура таких карт для функции двух, трех и четырех переменных имеет вид:

Каждая клетка такой таблицы содержит значение логической функции x при фиксированном значении всех ее аргументов a 3 , a 2 , a 1 , a 0 т.е. Изображает одну из строчек таблицы истинности. Соответствующий аргумент считается истинным для данной клетки, если эта клетка входит в строки или столбцы, помеченные сбоку или снизу символом этого аргумента, в противном случае аргумент для данной клетки считается ложным. Сокращенную ДНФ записывают по прямоугольным группам смежных клеток карты содержащих единицу. Допустимое число клеток в группе равно 2 n , n=1,2,3,…

Правило записи сокращенной ДНФ аналогичны правилам записи ДСНФ и отличаются только тем, что в элементарных произведениях не указываются те аргументы, которые истинны лишь для половины клеток соответствующей группы.

Запишем, для примера, ДНФ в последующей карте Карно:

Сокращенная ДНФ для данного случая имеет вид:

При выделении прямоугольных групп клеток следует иметь в виду, что:

1. выделение групп часто неоднозначно, а, следовательно, неоднозначно и решение задачи синтеза;

2. группы должны быть как можно больше, а число групп как можно меньше;

3. группы могут пересекаться, т.е. иметь общие клетки

4. с точки зрения формирования прямоугольных групп, карты трех и четырех переменных следует считать трехмерными. Карму функции с тремя переменными следует рассматривать как цилиндр со склеенными правым и левым краями. Поэтому на плоском рисунке карты прямоугольные группы смежных клеток могут оказаться разорванными. Например:

В прямоугольной группе смежных клеток на нашем рисунке сокращенной ДНФ соответствует слагаемое.

Карту функций с четырьмя аргументами следует рассматривать как поверхность тора. Поэтому здесь следует считать склеенными не только правый и левый, но и верхний и нижний края карты. В этих условиях на карте функции четырех переменных тоже могут оказаться разорванные группы смежных клеток. Примеры таких разрывов иллюстрируют рисунки:

По карте Карно можно записать также и сокращенную КНФ . Она записывается по прямоугольным группам смежных клеток содержащих нули. Прямоугольные группы выделяются также как и при записи ДНФ . Правило записи сокращенной КНФ аналогичны правилам записи КСНФ и отличаются только тем, что в элементарных суммах не учитываются те аргументы, которые истинны лишь для половины клеток соответствующей группы.

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

Логика работы цифрового устройства описывается таблицей истинности, в которой показывается, какие логические уровни будут присутствовать на выходе цифровой схемы при заданных логических уровнях на входе этой схемы. Для того чтобы синтезировать схему с заданной логикой работы необходимо составить булево уравнение (в случаи если у схемы предполагается один выход) или систему уравнений (в случаи если выходов у схемы больше одного). Рассмотрим два способа составления уравнений из таблицы истинности: прямым и методом карт Карно.

Способ первый: составление уравнений из таблицы истинности прямым способом.

При составлении булевых уравнений прямым способом нужно учитывать, что получившиеся уравнения могут быть не минимально возможными.

Выделим алгоритм составления уравнения по таблице истинности:

• 1. Выделим те строки, в которых функция принимает истинное значение;
• 2. Составим для этих строк минтермы операндов;
• 3. Соединим минтермы при помощи операции дизъюнкции.

Рассмотрим пример.

Составим уравнение для устройства, имеющего один выход y, три входа x 0 , x 1 , x 2 . Логика работы устройства описана в таблицы 8.

Таблица 8 - Описание работы устройства

Составим функцию для строки три. В этой строке x 0 и x 2 принимают ложные значения, x 1 принимает истинное значение. Соединим эти операнды при помощи конъюнкции (элемент И):

Такая функции (принимающая истинное значения), в которую входит конъюнкция переменных или их отрицания называется минтермом.

Составим минтерм для строки пять:

Так как имеется два минтерма, соединим их при помощи дизъюнкции (элемент ИЛИ):

Что и будет уравнением устройства описанной таблицей истинности 8.

Выделим алгоритм составления системы уравнений по таблице истинности:

• 1. Определим количество выходов, следовательно, и количество уравнений в системе;
• 2. Для каждого из выходов составим уравнение:
• 2.1 Выделяем те строки, в которых функция принимает истинное значение;
• 2.2 Составлим для этих строк минтермы операндов;
• 2.3 Если минтермов больше одного, то соединим минтермы при помощи операции дизъюнкции.
• 3. Объединим полученные уравнения в систему.

Рассмотрим пример.

Пусть заданно устройство, логика работы которого описана в таблице 10. У устройства имеется два входа x 0 и x 1 , и два выхода y 1 , y 0 . Так как задано два выхода уравнения для каждого из выходов будут составляться отдельно. Составим систему уравнений, состоящую из двух уравнений.

Таблица 10 - Описание работы устройства

Выделим строки, в которых y 0 принимает истинные значения. y 0 принимает истинное значение только в одной строке, а именно в четвертой строке. Составим уравнение для y 0:

Выделим строки, в которых y 1 принимает истинные значения. Здесь имеется две строки: вторая и пятая. Для второй строки минтерм будет иметь вид. Для пятой. Объединим их с помощью операции ИЛИ, тем самым составив уравнение для y 1:

Остается составить систему уравнений, описывающую заданное устройство:

Способ второй: составление уравнений из таблицы истинности методом карт Карно.

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

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

Перед тем как привести примеры, отметим основные положения, которыми будем руководствоваться при объединении областей (групп):

• 1. Область, которая подвергается объединению, должна состоять из логических единиц, при этом объединению подлежат только прямоугольные области, содержащие число логических единиц 2 n (т.е. 2 клетки, 4 клетки и т.д.).
• 2. Клетки, находящиеся на границе карты, граничат между собой, и могут быть объединены.
• 3. Все единицы должны быть объединены в какую-либо область, причем количество областей должно быть минимальным.
• 4. Одна ячейка может быть включена в разные области.

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

Уравнение составляется следующим образом: в конъюнкцию области входит только те операнды, которые не меняют свои состояния на противоположные в пределах области. В случае если областей больше одного, между конъюнкциями областей ставятся дизъюнкции.

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

Пример 1. Составим уравнение содержащих два операнда (или их инверсию) по таблице истинности 11 посредствам карт Карно.

Таблица 11 - Карта Карно для двух операндов

Составим карту Карно, для этого преобразуем таблицу истинности к виду, показанному на рисунке 18.

Рис. 18.

Здесь, горизонтальная часть отводится операнду x 1 , которое принимает значение 0 и 1 (). Вертикальной части таблицы аналогично соответствует x 0 .

Выделим те строки таблицы истинности 11, где y принимает значение логической единицы: строки два и три. Заметим, что во второй строке x 0 и x 1 принимает значение 00 (), в третьей строке x 0 и x 1 принимает значение 10 ().

Проставим в карте Карно 18 на пересечениях x 0 x 1 единицы в тех местах, где и (рис. 19).

Рис. 19.

Выделим область согласно положениям объединения областей (Рис. 20).

Рис. 20.

Получена одна область, составим уравнение. Операнд меняет в области свое значение на инверсию. Неинвертированный операнд x 1 не входит в область. Единственный операнд, который не меняет своего значения в полученной области - . Тогда уравнение примет вид:

Заметим, что если составлять уравнение из таблицы 10 прямым способом, то получилось бы не минимизированное уравнение:

которое можно преобразовать к минимально возможной форме путем применения аксиом и свойств алгебры логики.

Пример 2. Составим уравнение содержащих три операнда (или их инверсию) по таблице истинности 12 посредствам карт Карно.

Таблица 12 - Карта Карно для трёх операндов

Составим карту Карно дл трех операндов (рис. 21).

Рис. 21.

Для трех операндов горизонтальная часть соответствует операндам x 1 x 2 , которые принимают значение 00, 01, 11, 10. Важно отметить, что порядок 00, 01, 11, 10 должен соблюдаться в точности, изменения его на другой порядок не допускается. Вертикальной части таблицы соответствует операнд x 0 , принимающей значение 1 и 0).

Заполним карту Карно. Аналогично предыдущему примеру: выделим строки в таблице истинности 12, где y принимает истинное значение (вторая, третья, четвертая, седьмая строки). Проставим единицы в те ячейки карты Карно, которые соответствуют значениям операндов в этих строках (рис. 22).

Рис. 22.

Выделим области согласно положениям объединения областей (Рис. 23).

Рис. 23.

Выделено две области. В первой области полностью находится операнды и, объединим их конъюнкцией. Во второй области не меняют своего значения операнды, объединим их в конъюнкцию. Так как есть две области, объединим конъюнкции областей операцией дизъюнкции, тем самым составив конечное уравнение:

Пример 4. Составим уравнение содержащих четыре операнда (или их инверсию) по таблице истинности 13 посредствам карт Карно.

Таблица 13 - Карта Карно для четырех операндов

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

Карты Карно были изобретены в 1952 Эдвардом В. Вейчем и усовершенствованы в 1953 Морисом Карно, физиком из «Bell Labs», и были призваны помочь упростить цифровые электронные схемы. В карту Карно булевы переменные передаются из таблицы истинности и упорядочиваются с помощью кода Грея, в котором каждое следующее число отличается от предыдущего только одним разрядом.

Карта Карно может быть составлена для любого количества переменных, однако удобно работать при количестве переменных не более пяти. По сути Карта Карно — это таблица истинности составленная в 2-х мерном виде. Благодаря использованию кода Грея в ней верхняя строка является соседней с нижней, а правый столбец соседний с левым, т.о. вся Карта Карно сворачивается в фигуру тор (бублик). На пересечении строки и столбца проставляется соответствующее значение из таблицы истинности. После того как Карта заполнена, можно приступать к минимизации.

• Если необходимо получить минимальную ДНФ, то в Карте рассматриваем только те клетки которые содержат единицы, если нужна КНФ, то рассматриваем те клетки, которые содержат нули.

Алгоритм минимизации по методу карт Карно:

1.Метод Карно основан на представлении исходной функции, заданной в форме СДНФ, в виде карты следующего вида:

2. Объединяем смежные клетки, содержащие единицы, в область так, чтобы одна область содержала 2 n (т.е. 2, 4, 8, и т.д.) клеток (помним про то, что крайние строки и столбцы являются соседними между собой), в области не должно находиться клеток, содержащих нули, области могут пересекаться, возможно несколько вариантов покрытия.

3. Далее берём первую область и смотрим, какие переменные не меняются в пределах этой области, выписываем конъюнкцию этих переменных; если неменяющаяся переменная нулевая, проставляем над ней инверсию. Берём следующую область, выполняем то же самое, что и для первой, и т. д. для всех областей.

4. Конъюнкции областей объединяем дизъюнкцией.

Пример. Методом Карно минимизировать функцию:

$$y=f\left (A,B,C \right)=\bar{A}\bar{B}\bar{C}\vee \bar{A}B\bar{C}\vee A\bar{B}\bar{C}\vee A\bar{B}C$$

1.Заданную функцию представим с помощью карты Карно:

2. Затем производится объединение 2-х, 4-х или 8-ми единиц. В данном случае объединение двух единиц по горизонтали соответствует операции склеивания над конституентами $\bar{A}\bar{B}\bar{C}$ и $\bar{A} B \bar{C}$ , в результате которой исключается переменная B и получена импликанта $\bar{A} \bar{C}$ . Объединение двух единиц по вертикали соответствует операции склеивания над конституентами $A\bar{B}\bar{C}$ и $A\bar{B}C$ , в результате которой исключена переменная $С$ и будет получена импликанта $A\bar{B} $ .

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

Каждому набору значений переменных по строкам и столбцам соответствует своя ячейка, расположенная на их пересечении. Она заполняется единицей, если на соответствующем наборе функция принимает единичное значение, или нулем при нулевом значении функции (нули обычно не вписываются, а оставляются пустые клетки). Таким образом, отмеченные ячейки соответствуют ыицтермам, а неотмеченные - макстермам канонических форм. Например, на рис. 2.2,а показана карта Карно для функцин, заданной таблицей соответствия из рассмотренного в § 2.7 примере.

Операции склеивания двух минтермов ранга исходной формулы соответствует на карте Карно объединение двух соседних ячеек, отмеченных единицами, и эта объединенная пара ячеек представляет собой результирующий минтерм ранга. Аналогично склеивание двух минтермов ранга в минтерм ранга представляется объединением соответствующих пар ячеек в прямоугольную группу из четырех соседних ячеек и т. д. Полное число ичеек в любой группе всегда выражается целой степенью двойки , где а и b - соответственно целые числа пар ячеек по горизонтали и вертикали, причем каждая такая группа отображает минтерм ранга и покрывает минтермов ранга исходной канонической формы. Так, на рис. показано сокращенное покрытие, импликанты которого образованы в результате склеивания минтермов функции, изображенной на рис. 2.2,а. На рис. показаны тупиковые покрытия рассматриваемой функции, причем покрытие на рис. 2.2,в является минимальным.

Считывание минтермов с карты Карно осуществляется последовательным рассмотрением групп ячеек. В минтерм входят только те переменные, которые сохраняют свои значения в данной группе, причем значениям 1 соответствует сама переменная, а значению 0 - ее отрицание. Переменные, которые принимают в данной группе различные значения (0 и 1), являются свободными и в данном минтерме отсутствуют. Примеры считывания минтермов с карт Карно для различного числа переменных показаны на рис. 2.3.

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

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

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

В качестве примера на рис. 2.4 показана функция, заданная таблицей соответствия:

Сначала строятся простейшие покрытия на каждой карте раздельно, с которых списываются две функции: для левой карты и для правой карты .

Затем ищутся такие импликанты в этих функциях, которые различаются только вхождением и их можно объгдннить. В данном случае это (соответствующие им группы ячеек, обведенные жирной линией на рис. 2.4, а, совпадают при наложении, а на рис. 2.4, б они расположены симметрично), в результате объединения которых получается иыпликанта . Наконец, можно также дополнять одну из карт несущественными нмпликантами, которые можно считать соседними имплшеантам другой карты и, объединяя их между собой, упрощать результирующее выражение. Так, в левую карту можно добавить импликанту (на рис. 2.4 она показана пунктиром), которая, объединяясь с имплнкантой правой карты , дает . Окончательное выражение получаем как сумму с учетом выполненных преобразований:

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

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

Для получения минимальной формы инверсии функции необходимо найти на карте Карно минимальное покрытие совокупности нулевых ячеек и описать соответствующую формулу по указанному выше правилу. Так, для функции на рис. имеются два таких покрытия (рис. 2.5), отличающихся только одной импликантой. Если требуется найти минимальную форму как произведения макстермов, то в соответствии с изложенным в § 2.4 правилом достаточно в выражении для инверсной функции заменить все логические операции на дуальные, а вхождения переменных - на инверсные: . Эти же формы можно записать на основе принципа дуальности непосредственно по минимальным покрытиям нулевых ячеек карты Карно. Для этого достаточно каждую группу ячеек идентифицировать как сумму переменных при инверсной разметке карты Карно, т. е. считая отмеченные значения переменных нулевыми.