1.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. Начните с булева выражения в дизъюнктивной нормаль­ной форме.

1. Нанесите единицы на карту Карно.

2. Объедините соседние единицы контурами, охватывающи­ми два или восемь квадратов.

3. Проведите упрощения, исключая члены, дополняющие друг друга внутри контура.

4. Объедините оставшиеся члены (по одному в каждом контуре) функцией ИЛИ.

5. Запишите полученное упрощенное булево выражение в дизъюнктивной нормальной форме.

1.5 Карты Карно с тремя переменными

Рассмотрим исходное булево выражение , приведенное на рисунке 1.12 а. Карта Карно для случая трех переменных показана на рисунке 1.12 б. Обратите внимание на то, что имеется во­семь возможных комбинаций переменных А, В и С, которые представлены восемью квадратами на карте. В них зане­сены четыре единицы, отображающие каждый из четырех членов исходного булева выражения. Заполненная карта Карно повторена на рисунке 1.12 в, где каждая группа из двух соседних единиц обведена контуром. Нижний контур содер­жит B и , вследствие чего B и можно опустить. После этого в составе нижнего контура сохраняются лишь A и , которые дают член . В верхний контур входят C и , поэтому C и опускаются, в результате чего остается толь­ко член . Булево выражение в дизъюнктивной нормаль­ной форме получается введением символа операции ИЛИ. Упрощенное булево выражение, записанное на рисунке 1.12 г, имеет вид =Y.

Рисунок 1.12  Упрощение булевых выражений на основе карты Карно

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

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