Карты Карио представляют собой специально организованные таблицы соответствия, на которых удобно осуществляются операции склеивания при упрощении функции на пути к минимальным формам. Столбчы и строки таблицы соответствуют всевозможным наборам значений переменных, причем эти наборы расположены в таком порядке, что каждый последующий отличается от предыдущего только одной из переменных. Благодаря этому соседнне ячейки по горизонтали и вертикали отличаются значением только одной переменной. Ячейки, расположенные по краям таблицы, также считаются соседними и обладают этим свойством. На рис. 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 правилом достаточно в выражении для инверсной функции заменить все логические операции на дуальные, а вхождения переменных - на инверсные: . Эти же формы можно записать на основе принципа дуальности непосредственно по минимальным покрытиям нулевых ячеек карты Карно. Для этого достаточно каждую группу ячеек идентифицировать как сумму переменных при инверсной разметке карты Карно, т. е. считая отмеченные значения переменных нулевыми.
В 1953 г. Морис Карно опубликовал статью о разработанной им системе графического представления и упрощения булевых выражений. Карта Карно показана на рисунке 1.8. Четыре квадрата (1, 2, 3, 4) соответствуют четырем возможным комбинациям A и B в таблице истинности с двумя переменными. При таком изображении квадрат 1 на карте Карно соответствует произведению , квадрат 2-произведению и т. Д.
Рисунок 1.8 Обозначение квадрантов на карте Карно
Предположим теперь, что нам надо составить карту Карно для логической задачи, проиллюстрированной на рисунке 1.7. Исходное булево выражение для удобства еще раз переписано на рисунке 1.9 а. Разместим логические единицы во всех квадратах, которым соответствуют произведения в исходном булевом выражении на рисунке 1.9 а.
Рисунок 1.9 Нанесение единиц на карту Карно
Заполненная таким образом карта Карно теперь готова для построения, и эта процедура демонстрируется на рисунке 1.10. В соответствии с ней соседние единицы объединяются в один контур группами по две, четыре или восемь единиц. Построение контуров продолжается до тех пор, пока все единицы не окажутся внутри контуров. Каждый контур представляет собой новый член упрощенного булева выражения. Заметим, что на рисунке 1.10 у нас получилось только два контура. Это означает, что новое, упрощенное булево выражение будет состоять только из двух членов, связанных функцией ИЛИ.
Рисунок 1.10 Объединение единиц группами в один контур на карте Карно
Теперь упростим булево выражение, принимая во внимание два контура на рисунке 1.10, повторенные на рисунке 1.11. Взяв сначала нижний контур, замечаем, что А здесь встречается в комбинации с B и . В соответствии с правилами булевой алгебры B и дополняют друг друга и их можно опустить. Тогда в нижнем контуре остается один член А. Аналогично этому вертикально расположенный контур содержит A и , которые можно также опустить, оставив только В. Оставшиеся в результате А и В затем объединяются функцией ИЛИ, что приводит к упрощенному булеву выражению А + В= Y.
Рисунок 1.11 Упрощение булевых выражений на основе карты Карно
Процедура упрощения булева выражения сложна лишь на первый взгляд. На самом деле после некоторой тренировки ее легко освоить, выполняя последовательно шесть шагов, указанных ниже:
Начните с булева выражения в дизъюнктивной нормальной форме.
Нанесите единицы на карту Карно.
Объедините соседние единицы контурами, охватывающими два или восемь квадратов.
Проведите упрощения, исключая члены, дополняющие друг друга внутри контура.
Объедините оставшиеся члены (по одному в каждом контуре) функцией ИЛИ.
Запишите полученное упрощенное булево выражение в дизъюнктивной нормальной форме.
1.5 Карты Карно с тремя переменными
Рассмотрим исходное булево выражение , приведенное на рисунке 1.12 а. Карта Карно для случая трех переменных показана на рисунке 1.12 б. Обратите внимание на то, что имеется восемь возможных комбинаций переменных А, В и С , которые представлены восемью квадратами на карте. В них занесены четыре единицы, отображающие каждый из четырех членов исходного булева выражения. Заполненная карта Карно повторена на рисунке 1.12 в, где каждая группа из двух соседних единиц обведена контуром. Нижний контур содержит B и , вследствие чего B и можно опустить. После этого в составе нижнего контура сохраняются лишь A и , которые дают член . В верхний контур входят C и , поэтому C и опускаются, в результате чего остается только член . Булево выражение в дизъюнктивной нормальной форме получается введением символа операции ИЛИ. Упрощенное булево выражение, записанное на рисунке 1.12 г, имеет вид = Y .
Рисунок 1.12 Упрощение булевых выражений на основе карты Карно
Назначение сервиса . Онлайн-калькулятор предназначен для построения таблицы истинности для логического выражения .Таблица истинности – таблица содержащая все возможные комбинации входных переменных и соответствующее им значения на выходе.
Таблица истинности содержит 2 n строк, где n – число входных переменных, и n+m – столбцы, где m – выходные переменные.
Инструкция . При вводе с клавиатуры используйте следующие обозначения:
Например, логическое выражение abc+ab~c+a~bc необходимо ввести так: a*b*c+a*b=c+a=b*cДля ввода данных в виде логической схемы используйте этот сервис .
Правила ввода логической функции
- Вместо символа v (дизъюнкция, ИЛИ) используйте знак + .
- Перед логической функцией не надо указывать обозначение функции. Например, вместо F(x,y)=(x|y)=(x^y) необходимо ввести просто (x|y)=(x^y) .
- Максимальное количество переменных равно 10 .
Проектирование и анализ логических схем ЭВМ ведётся с помощью специального раздела математики - алгебры логики. В алгебре логики можно выделить три основные логические функции: "НЕ" (отрицание), "И" (конъюнкция), "ИЛИ" (дизъюнкция).
Для создания любого логического устройства необходимо определить зависимость каждой из выходных переменных от действующих входных переменных такая зависимость называется переключательной функцией или функцией алгебры логики.
Функция алгебры логики называется полностью определённой если заданы все 2 n её значения, где n – число выходных переменных.
Если определены не все значения, функция называется частично определённой.
Устройство называется логическим, если его состояние описывается с помощью функции алгебры логики.
Для представления функции алгебры логики используется следующие способы:
По алгебраической форме можно построить схему логического устройства, используя логические элементы.
Рисунок1- Схема логического устройства
Все операции алгебры логики определяются таблицами истинности значений. Таблица истинности определяет результат выполнения операции для всех возможны х логических значений исходных высказываний. Количество вариантов, отражающих результат применения операций, будет зависеть от количества высказываний в логическом выражении. Если число высказываний в логическом выражении N, то таблица истинности будет содержать 2 N строк, так как существует 2 N различных комбинаций возможных значений аргументов.
Операция НЕ - логическое отрицание (инверсия)
Логическая операция НЕ применяется к одному аргументу, в качестве которого может быть и простое, и сложное логическое выражение. Результатом операции НЕ является следующее:- если исходное выражение истинно, то результат его отрицания будет ложным;
- если исходное выражение ложно, то результат его отрицания будет истинным.
не А, Ā, not A, ¬А, !A
Результат операции отрицания НЕ определяется следующей таблицей истинности:
| A | не А |
| 0 | 1 |
| 1 | 0 |
Результат операции отрицания истинен, когда исходное высказывание ложно, и наоборот.
Операция ИЛИ - логическое сложение (дизъюнкция, объединение)
Логическая операция ИЛИ выполняет функцию объединения двух высказываний, в качестве которых может быть и простое, и сложное логическое выражение. Высказывания, являющиеся исходными для логической операции, называют аргументами. Результатом операции ИЛИ является выражение, которое будет истинным тогда и только тогда, когда истинно будет хотя бы одно из исходных выражений.Применяемые обозначения: А или В, А V В, A or B, A||B.
Результат операции ИЛИ определяется следующей таблицей истинности:
Результат операции ИЛИ истинен, когда истинно А, либо истинно В, либо истинно и А и В одновременно, и ложен тогда, когда аргументы А и В - ложны.
Операция И - логическое умножение (конъюнкция)
Логическая операция И выполняет функцию пересечения двух высказываний (аргументов), в качестве которых может быть и простое, и сложное логическое выражение. Результатом операции И является выражение, которое будет истинным тогда и только тогда, когда истинны оба исходных выражения.Применяемые обозначения: А и В, А Λ В, A & B, A and B.
Результат операции И определяется следующей таблицей истинности:
| A | B | А и B |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Результат операции И истинен тогда и только тогда, когда истинны одновременно высказывания А и В, и ложен во всех остальных случаях.
Операция «ЕСЛИ-ТО» - логическое следование (импликация)
Эта операция связывает два простых логических выражения, из которых первое является условием, а второе - следствием из этого условия.Применяемые обозначения:
если А, то В; А влечет В; if A then В; А→ В.
Таблица истинности:
| A | B | А → B |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Результат операции следования (импликации) ложен только тогда, когда предпосылка А истинна, а заключение В (следствие) ложно.
Операция «А тогда и только тогда, когда В» (эквивалентность, равнозначность)
Применяемое обозначение: А ↔ В, А ~ В.Таблица истинности:
| A | B | А↔B |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Операция «Сложение по модулю 2» (XOR, исключающее или, строгая дизъюнкция)
Применяемое обозначение: А XOR В, А ⊕ В.Таблица истинности:
| A | B | А⊕B |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Результат операции эквивалентность истинен только тогда, когда А и В одновременно истинны или одновременно ложны.
Приоритет логических операций
- Действия в скобках
- Инверсия
- Конъюнкция (&)
- Дизъюнкция (V), Исключающее ИЛИ (XOR), сумма по модулю 2
- Импликация (→)
- Эквивалентность (↔)
Совершенная дизъюнктивная нормальная форма
Совершенная дизъюнктивная нормальная форма формулы (СДНФ) это равносильная ей формула, представляющая собой дизъюнкцию элементарных конъюнкций, обладающая свойствами:- Каждое логическое слагаемое формулы содержит все переменные, входящие в функцию F(x 1 ,x 2 ,...x n).
- Все логические слагаемые формулы различны.
- Ни одно логическое слагаемое не содержит переменную и её отрицание.
- Ни одно логическое слагаемое формулы не содержит одну и ту же переменную дважды.
Для каждой функции СДНФ и СКНФ определены единственным образом с точностью до перестановки.
Совершенная конъюнктивная нормальная форма
Совершенная конъюнктивная нормальная форма формулы (СКНФ) это равносильная ей формула, представляющая собой конъюнкцию элементарных дизъюнкций, удовлетворяющая свойствам:- Все элементарные дизъюнкции содержат все переменные, входящие в функцию F(x 1 ,x 2 ,...x n).
- Все элементарные дизъюнкции различны.
- Каждая элементарная дизъюнкция содержит переменную один раз.
- Ни одна элементарная дизъюнкция не содержит переменную и её отрицание.
Поскольку логическую функцию, даже такую простую, как Исключающее ИЛИ, можно реализовать различными способами, часто бывает нужно найти для нее самое простое решение, или, возможно, наиболее удобное схемное решение. Над этой проблемой бились многие светлые умы и в настоящее время существует несколько способов ее разрешения, включая алгебраические методы, реализуемые с помощью ЭВМ. При числе входов, не превышающем четырех, наилучшим методом является составление карты Карно. Этот метод позволяет также найти логическое выражение (если оно заранее неизвестно) по таблице истинности. Проиллюстрируем этот метод с помощью примера. Предположим, что требуется построить схему для мажоритарного подсчета голосов при баллотировке. Будем считать, что имеются три входа, работающие в положительной логике (на любом из них может быть 1 или 0) и выход (0 или 1). Выход равен 1, если 1 присутствует не менее чем на двух входах.
Шаг 1. Составим таблицу истинности
Здесь должны быть представлены все возможные сочетания и соответствующие им состояния выхода (или выходов). В том случае, когда состояние входа не оказывает влияния на выход, ставится X (любое значение).
Рис. 8.27. Карта Карно.
Шаг 2. Составим карту Карно. Она представляет собой нечто очень близкое к таблице истинности, но содержит переменные, которые расположены по двум осям. Переменные должны быть расположены таким образом, чтобы при переходе от каждого квадрата к соседнему менялось бы состояние только одного входа (рис. 8.27).
Шаг 3. Отметим на карте группы, содержащие 1 (можно также использовать и группы, содержащие 0). Три овала на рис. 8.27 определяют логические выражения АВ, АС и ВС.
схемная реализация ее показана на рис. 8.28. Этот результат кажется очевидным, когда он уже получен. Можно было бы составить выражение для нулей и вместо этого получить
Это выражение может оказаться полезным для случая, когда в каких-либо точках схемы имеются дополнения А, В и С.
Некоторые комментарии к картам Карно.
1. Ищите группы, содержащие 2, 4, 8 и т.д. квадратов. Они имеют простые логические выражения.
2. Логика будет тем проще, чем крупнее блок вы опишете.
3. Состыкуйте края карты Карно. Например, карта на рис. 8.29 описывается выражением С.
4. Блок «единиц», содержащий один или два «нуля», лучше всего описывается с помощью группировки, показанной на рис. 8.30. Этому блоку соответствует логическое выражение .
6. Карта Карно может и не привести к лучшему решению. Иногда более сложное логическое выражение имеет более простую схемную реализацию, например в случае, когда некоторые члены выражения уже сформированы схемой в виде логических сигналов, которые можно использовать в качестве входных. Кроме того, реализации Исключающего ИЛИ не очевидны из карты Карно. Наконец, при выборе логической структуры схемы определенную роль играют ограничения, связанные с конструкцией ИМС (например, когда в одном корпусе содержатся четыре -входовых вентиля). Когда используются такие программируемые логические устройства как ПМЛ для конструирования логических функций, внутренняя структура (программируемые вентили И и фиксированные вентили ИЛИ) сдерживает реализацию, которая могла бы быть применена.
Минимизация логических функций является одной из типовых задач в процессе обучения схемотехнике. Посему считаю, что такая статья имеет место быть, надеюсь Вам понравится.
Зачем это нужно?
Сложность логической функции, а отсюда сложность и стоимость реализующей ее схемы (цепи), пропорциональны числу логических операций и числу вхождений переменных или их отрицаний. В принципе любая логическая функция может быть упрощена непосредственно с помощью аксиом и теорем логики, но, как правило, такие преобразования требуют громоздких выкладок.К тому же процесс упрощения булевых выражений не является алгоритмическим. Поэтому более целесообразно использовать специальные алгоритмические методы минимизации, позволяющие проводить упрощение функции более просто, быстро и безошибочно. К таким методам относятся, например, метод Квайна, метод карт Карно, метод испытания импликант, метод импликантных матриц, метод Квайна-Мак-Класки и др. Эти методы наиболее пригодны для обычной практики, особенно минимизация логической функции с использованием карт Карно. Метод карт Карно сохраняет наглядность при числе переменных не более шести. В тех случаях, когда число аргументов больше шести, обычно используют метод Квайна-Мак-Класки.
В процессе минимизации той или иной логической функции, обычно учитывается, в каком базисе эффективнее будет реализовать ее минимальную форму при помощи электронных схем.
Минимизация логических функций при помощи карт Карно
Карта Карно - графический способ минимизации переключательных (булевых) функций, обеспечивающий относительную простоту работы с большими выражениями и устранение потенциальных гонок. Представляет собой операции попарного неполного склеивания и элементарного поглощения. Карты Карно рассматриваются как перестроенная соответствующим образом таблица истинности функции. Карты Карно можно рассматривать как определенную плоскую развертку 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 выражение в формате ДНФ будет иметь вид:
В формате КНФ: