Навигация

 

 Меню раздела

Цифровая электроника
Логические элементы
Комбинированные элементы
Анализ схем
Таблица истинности и цифровая схема
Логические функции и цифровые схемы
Требуемая функция и реальная функция
Алгебра логики
Переменные и постоянные величины
Законы алгебры логики
Аксиомы и тождества алгебры логики
Функции «И-НЕ» и «ИЛИ-НЕ»
Синтез схем
Нормальные формы записи
Упрощение и преобразование
Метод карт Карно
Расчет логических схем
Задания по схемотехническому проектированию
Семейства схем
Бинарные уровни напряжения
Положительная и отрицательная логика
Свойства схем
ДТЛ-схемы
МПЛ-схемы
ТТЛ-схемы
Стандартные ТТЛ-схемы
Предельные значения и параметры схем
ТТЛ с пониженным энергопотреблением
Шотки-ТТЛ (ТТЛШ)
ТТЛШ с пониженным энергопотреблением
Сравнительная оценка логических элементов
Эмиттерно-связанная логика
Логические элементы на МОП-транзисторах
Логические элементы на р-канальных МОП-транзисторах
Логические элементы на л-канальных МОП-транзисторах
Логические элементы на КМОП-транзисторах
Логические элементы на МОП-транзисторах
Бинарные схемы с временной зависимостью
Классификация триггеров
Не тактируемые триггеры
Триггер на элементах «И-НЕ»
Тактируемые триггеры
ЯБ-триггеры с доминирующим Я-входом
Е-триггер
D-триггер
Триггеры, управляемые по фронту синхроимпульса
RS-триггеры, управляемые по одному фронту
T-триггеры, управляемые по одному фронту
JK-триггеры, управляемые по одному фронту
D-триггеры, управляемые по одному фронту
ЯБ-триггеры, управляемые по обоим фронтам
Ж-триггеры, управляемые по обоим фронтам
Дополнительные триггерные схемы
Временные диаграммы
Характеристические уравнения
Моностабильные ячейки
Элементы задержки


Метод карт Карно

Метод карт Карно служит для наглядного представления и упрощения нормальной формы ИЛИ. Он был придуман математиком Карно, и его еще называют методом диаграмм Карно.

Карта Карно для двух переменных

Карты Карно могут быть представлены в виде таблиц истинности для полных конъюнкций.
3—2114
Карты Карно всегда имеют количество полей, равное количеству возможных полных конъюнкций.
При двух переменных возможны 4 полные конъюнкции. Таким образом, карта Карно для двух переменных должна иметь 4 поля (см. рис. 5.12). По краям карты записываются переменные. Каждая переменная величина должна быть представлена в инвертированной и в неинвертированной форме (рис. 5.12).
Переменные по краям являются координатной сеткой. Они определяют, какая полная конъюнкция какому полю принадлежит. На рис. 5.13 по своим полям расписаны 4 полных конъюнкции.

Карта Карно для двух переменных (А, В)

Поле полной конъюнкции А а В обозначено координатами А и В
(рис. 5.13). Соответственно поле полной конъюнкции А а В находится по
координатам А и В. Так как полные конъюнкции определяются координатами, то нет необходимости записывать их в полной форме, как на рис. 5.13. Наличие полной конъюнкции может обозначаться 1 в соответствующем поле.
1 в поле карты Карно означает наличие полной конъюнкции.
На карте Карно (рис. 5.14) отмечены полные конъюнкции А а В и А а В. Карта Карно отражает следующую нормальную форму ИЛИ:
Z = (AaB)v(AaB).
Символ Z в верхнем левом углу карты на рис. 5.14 показывает, что полные конъюнкции относятся к Z.
Отсутствующие полные конъюнкции обозначены нулем в соответствующем поле, или поле не заполняется.
Присваивание переменных координатам карты Карно производится произвольным образом.
Также возможно менять местами А и В на карте (рис. 5.15). Разумеется, переменные могут иметь совершенно другие обозначения, например Ег и Ег Прямое и инверсное значения переменной должны обязательно находиться на одной стороне карты.
Другое распределение координатных переменных ведет, естественно, к другому распределению полных конъюнкций по полям карты.
Желательно придерживаться определенной схемы распределения переменных и не менять ее без причины. Для облегчения работы рекомендуется первую переменную, например А, и ее инверсию все время ставить на верхнюю часть карты. Вторую переменную (например В) и ее инверсию ставить на левую часть карты.

Карта Карно с измененными координатами

                                                                                                                                            
Покажем на примере заполнение карты Карно нормальной формой ИЛИ и восстановление нормальной формы ИЛИ по карте Карно.
Пример 1
Занесите в карту Карно нормальную форму ИЛИ:
Z = (Л л В) v (А л В) v (Л а В).
Сначала нужно нарисовать карту Карно с данными координатами. Затем найти поля с полными конъюнкциями, присутствующими в нормальной форме и обозначить их 1. Результат показан на рис. 5.16.
                              
Карта Карно для нормальной формы "ИЛИ"
                              
Пример 2---------------------------------------------------------------
Запишите нормальную форму ИЛИ, представленную на карте Карно (рис. 5.17).
Нормальная форма ИЛИ содержит 2 полные конъюнкции: одна А д В, вторая АлВ. Следовательно, нормальная форма:
W = (АлВ)ч(АлВ).
Представленная на карте Карно нормальная форма ИЛИ может быть упрощена при наличии определенных условий.
«Соседние» полные конъюнкции можно объединять в «группы».
Соседними считаются полные конъюнкции, клетки которых имеют общие стороны (рис. 5.18). Если клетки с полными конъюнкциями имеют только общий угол, то они не являются соседними.

Соединение и несоединение конъюнкции

Рис. 5.18. Соединение и несоединение конъюнкции

В одной группе могут быть объединены 2 или 4 соседние полные конъюнкции.
Каждая группа имеет определенные координаты. Группа слева наверху на карте Карно (рис. 5.18) имеет по одной стороне координату Д по другой —
координату А и А.
Содержание группы характеризуется ее координатами. Переменные, чьи координаты присутствуют в прямой и инверсной форме одновременно, исключаются.
Представленная на рис. 5.19 группа имеет координаты А, В ж В. Переменная В имеет как прямую, так и инверсную формы. Следовательно, она исключается. Значение группы будет А. Нормальная форма ИЛИ

Это упрощение может быть проверено с помощью алгебры логики.

Образование группы в карте Карно

Особый случай представляет группа из 4 полных конъюнкций (рис. 5.20).
Она имеет координаты А, А, В, В. Значит, переменные Аж В исключаются. Значение группы равно 1. Справедливость этого можно доказать с помощью таблицы истинности. Алгебра логики также приведет к этому результату:
Z = (А а В) v (А а В^ v (А а В} v [А а В^;
Z = [А а (В v 5)] v \_А а (В v 5)];
Z = (AaI)v(AaI);
Z = Av А;
Z = l.

Карта Карно с несколькими группами

На одной карте можно образовать несколько групп (рис. 5.21). Одна полная конъюнкция может присутствовать в нескольких группах.
При наличии нескольких групп упрощенное уравнение получается в результате логического сложения значений отдельных групп.
Для карты (рис. 5.21) значения групп получаются равными А и В.
Упрощенное уравнение:
Z = AvB.
На карте Карно (рис. 5.20) можно образовать также две группы из двух полей. Тогда получится упрощенное уравнение, но не в самом простом виде. Покажем это. На рис. 5.22 показана карта Карно с такой группировкой. Значения групп равны В ж В. Упрощенное уравнение, следовательно:
Z = Bv В.
Сложение переменной величины с ее инверсией дает в итоге по правилам алгебры логики 1. Поэтому самой простой формой уравнения является Z = 1.
Для максимального упрощения уравнения необходимо образовывать группы как можно большего размера.
Чтобы закрепить полученные знания, решим следующий пример.
Пример 3-------------------------------------------------------
Максимально упростите при помощи карты Карно нормальную форму ИЛИ. Запишите упрощенное уравнение:
X = (AaB)v(AaB)v(AaB).
Сначала полные конъюнкции заносятся в карту (рис. 5.23).

Карта Карно

Рис. 5.23. Карта Карно

Затем образуются две группы по два поля. Они имеют значения А и В. Упрощенное уравнение:
X = А а В.

Карта Карно для трех переменных

Для трех переменных возможны 8 различных полных конъюнкций (рис. 5.24). Следовательно, карта Карно для трех переменных должна иметь 8 клеток.
Распределение переменных по координатам может происходить, как и в карте для двух переменных любым образом. Однако целесообразно первые переменные поместить на верхнюю сторону диаграммы, а вторые величины — на левую сторону диаграммы. Третья переменная величина размещается на нижней стороне диаграммы. Для переменных величин А, В и С карта Карно изображена на рис. 5.25.

Карта Карно для трех переменных


Третья переменная С должна быть размещена, как указано на рис. 5.25.
Если обозначить обе левые стороны клетки как С, а обе правые как С, то для некоторых полных конъюнкций будет двойное место, а для некоторых — ни одного. На рис. 5.26 полные конъюнкции расписаны по ячейкам.
Для карт Карно с тремя переменными действуют правила, установленные для карт Карно с двумя переменными, со следующими дополнениями:
В одной группе могут быть объединены 2, 4 или 8 соседних полных конъюнкций .
Если быть совсем точными, карта Карно для трех переменных имеет цилиндрическую форму (рис. 5.27). Поэтому клетки, находящиеся в противоположных концах одной строки, являются соседними.

Карта Карно для трех переменных с занесенными полными конъюнкциями

Группировка по принципу расширенного соседства

Рис. 5.28. Группировка по принципу расширенного соседства

Карту Карно сложно представлять в виде цилиндра. Поэтому предпочитают форму на рис. 5.25, соблюдая принцип расширенного соседства. На рис. 5.28 представлены соседние полные конъюнкции и их группировки.
Группа из двух клеток на верхней диаграмме имеет в итоге значение В и С.
Группа из четырех клеток на нижней диаграмме имеет значение С. Группа должна быть прямоугольной или квадратной. Группа, изображенная на рис. 5.28а, недопустима.

Недопустимая группа карты Карно

Рис. 5.28а. Недопустимая группа карты Карно

Рассмотрим несколько примеров работы с картами Карно для трех переменных.
Пример 1-------------------------------------------------------------------
Заполните карту Карно полными конъюнкциями следующего уравнения:
Y — {^А а В а v а В а v а В а v [А а В а С).
Сначала надо правильно разместить полные конъюнкции по ячейкам (рис. 5.29). Запись лучше производить в алгебраической форме, тогда можно легко контролировать правильность выбора ячейки.
Каждую полную конъюнкцию обозначим 1 (рис. 5.30). При отсутствии затруднений можно сразу же рисовать обычную карту Карно.

Карта Карно с занесенными полными конъюнкциями к примеру 1

Пример 2--------------------------------------------------------------------
Занесите данную нормальную форму ИЛИ в карту Карно и максимально упростите:
Z — (А а В а С) v {А а В л С) v {А а В л С) v а В л С1).
Имеющиеся полные конъюнкции обозначаются 1 (рис. 5.31). Затем производится группировка. Группу из четырех элементов образовать невозможно. Зато можно образовать 3 группы из двух клеток. Однако выделенная пунктиром группа является избыточной, так как двумя основными серыми группами все 1 уже охвачены. Если бы мы выбрали пунктирную группу в качестве основной, найденное уравнение не было бы максимально простым.

 Карта Карно к примеру 2

Рис. 5.31. Карта Карно к примеру 2
Верхняя серая группа (рис. 5.31) имеет значение А а В. Значение нижней серой группы — В а С. (Переменная А выпадает, так как встречается в координатах этой группы как в прямой, так и в инверсной формах.) Значения групп логически складываются. При этом получается упрощенное уравнение:
Z = (AaB)v(B аС).
Пример 3-------------------------------------------------------------
Запишите нормальную форму ИЛИ, заключенную в карте Карно (рис. 5.32).

Карта Карно к примеру 3

Рис. 5.32. Карта Карно к примеру 3

Максимально упростите нормальную форму ИЛИ.
Нормальная форма ИЛИ по карте Карно:
Z = [А аВ aC^v (А а В aC)v {А аВ aC^v {А а В aC}v (А аВ aC^v А аВ аС.
Могут быть образованы 2 группы из четырех клеток. Одна имеет значение В, другая С. Упрощенное уравнение:
Z = BvC.
Так как возможно образование двух больших групп из четырех клеток, то получается значительное упрощение нормальной формы.

Карта Карно для четырех переменных

Карта Карно для четырех переменных должна иметь 16 клеток, так как возможны 16 различных полных конъюнкций (рис. 5.33). Карта Карно для четырех переменных изображена на рис. 5.34.

Карта Карно для четырех переменных


Переменные обозначены, как и раньше, А, В и С. Плюс добавлена переменная величина D. Разумеется, переменные могут быть обозначены иначе, например Ev   Е2,  Е3,  Ег 16 полных конъюнкций показаны на рис.  5.35.
Для карт Карно с четырьмя переменными действуют правила, ранее установленные для карт Карно, со следующими дополнениями:

Карта карно для четырех переменных с занесенными полными конъюнкциями

Рис. 5.35. Карта карно для четырех переменных с занесенными полными конъюнкциями

В одной группе могут быть объединены 2, 4, 8 или 16 соседних полных конъюнкций.
Карта Карно для четырех переменных имеет форму шара. Поэтому клетки, находящиеся в противоположных концах одной строки или столбца, являются соседними.
Разъясним подробнее принцип расширенного соседства. Рассмотрим рис. 5.36. Карта (а) показывает, что группы из двух клеток можно образовать не только из полных конъюнкций, которые находятся на концах одной строки, но и из полных конъюнкций, находящихся на концах одного столбца.

5.36. Группировка по принципу расширенного соседства

Рис. 5.36. Группировка по принципу расширенного соседства

Диаграмма (б) показывает образование группы из четырех клеток.
Диаграмма (в) также показывает образование счетверенной группы. Единицы по У У I \ К              углам являются соседними, так как при
форме шара поля прилегают друг к другу
смежными сторонами.
Другое дело карта на рис. 5.37. Только две единицы по углам не могут образовать сдвоенную группу, так как они не являются смежными — как показано на виде снизу. Рассмотрим ряд примеров с картами Карно для четырех переменных.
Пример 1 -----------------------------------------------------
Составьте карту Карно по следующей нормальной форме ИЛИ:
Y = [А л В лС л D^v л В лС л D^v (А л В лС л D)

'{А /\ В аС a (А л В лС л Z)).
Для большей наглядности полные конъюнкции отмечены серыми номерами. Они обозначают соответствующие клетки. На рис. 5.38 показана искомая диаграмма.

Карта Карно к примеру 1

Рис. 5.38. Карта Карно к примеру 1

Пример 2----------------------------------------------------------------
Для задач управления требуется схема, удовлетворяющая таблице истинности (рис. 5.39). Эта схема должна быть максимально простой.

Таблица истинности к примеру 2

Рис. 5.39. Таблица истинности к примеру 2

Из таблицы истинности может быть определена нормальная форма ИЛИ Z = [А а В а С a D^jv {А а В а С a D^v [А а В а С a Z))'
v{A А В аС A (А А В аС A (А А В аС A D).
Номера полных конъюнкций совпадают с номерами вариантов таблицы истинности. Полные конъюнкции далее заносятся в диаграмму (рис. 5.40).

Карта Карно к примеру 2


Следующим шагом является упрощение нормальной формы ИЛИ с помощью группировки соседних полных конъюнкций. Возможно образование двух групп из 4 клеток со значениями С лВи АлС. Упрощенное уравнение выглядит так:
Z = (с aD)v(AaC).
Переменная С может быть вынесена за скобку:
Z = (С л D)v (А аС) = С а(А v/>).
Получившаяся схема представлена на рис. 5.41.

Карта Карно для пяти переменных

Для пяти переменных возможны 32 различные полные конъюнкции. Следовательно, карта Карно для пяти переменных должна иметь 32 поля. Но на одном уровне в диаграмму для четырех переменных новые переменные уже добавить не получится.
Диаграмме надо добавить второй уровень. На рис. 5.42 показано, что имеется в виду. Переменные величины будут, как раньше, обозначены А, В, С и D. К ним добавляется переменная Е.
К нижнему уровню диаграммы присоединяется координата Е, к верхнему — координата Ё. Нарисовать такую двухуровневую карту сложно, поэтому уровни рисуют рядом.
Диаграмма для пяти переменных состоит из двух таблиц, расположенных одна над другой (рис. 5.42а). Такая диаграмма имеет 32 ячейки для 32 полных конъюнкций.
Для карт Карно с пятью переменными действуют правила, ранее установленные для карт Карно, со следующими дополнениями:

Карта Карно для пяти переменных

Рис. 5.42. Карта Карно для пяти переменных

Карта Карно для пяти переменных, состоящая из двух таблиц

Рис. 5.42а. Карта Карно для пяти переменных, состоящая из двух таблиц

В одной группе могут быть объединены 2, 4, 8, 16 или 32 соседних полных конъюнкций.
Сгруппированы могут быть также те полные конъюнкции, чьи поля находят-ся друг под другом в таблицах (рис. 5.42).
Рассмотрим эти правила на примерах.
Пример 1------------------------------------------------------------
Занесите данную нормальную форму ИЛИ в карту Карно и максимально упростите:

Для большей наглядности полные конъюнкции отмечены серыми номерами. Они обозначают соответствующие клетки диаграммы. Возможно образование двух групп из 4 клеток. Серая группа на правой таблице имеет значение АлСлЕ. Переменные В и D в этой группе исключаются.

ее

Рис. 5.43. Карта Карно к примеру 1.

Выделенная пунктиром группа из 4 клеток проходит сквозь оба уровня. Для этого следует мысленно положить друг на друга уровни (рис. 5.43).
Значение этой группы АлВ лС. Так как группа проходит сквозь два уровня, переменная Е выпадает. Переменная D также выпадает. В итоге получается упрощенное уравнение:
Z ^{А а В aC|v [А а С а Еу
Пример 2-------------------------------------------------------------
В диаграмме на рис. 5.44 задана нормальная форма ИЛИ. Максимально упростите ее.

Карта Карно к примеру 2

Рис. 5.44. Карта Карно к примеру 2

Единицы по углам обоих уровней образуют восьмерную группу (группа
из восьми ячеек). Эта группа проходит через два уровня. Ее значение С л D. Далее можно сформировать группы из 2 и 4 клеток. Группа из 4 клеток
имеет значение В aD л Е. Значение сдвоенной группы В л С л D л Е. Получается упрощенное уравнение:
Y = (CaD)v(BaDaE)v(BaCaDaE).
Упрощение значительно. Это видно, если записать содержащуюся в диаграмме на рис. 5.44 нормальную форму ИЛИ.
Пример 3-------------------------------------------------------
Запишите содержащуюся в диаграмме на рис. 5.44 нормальную форму ИЛИ.
Левая таблица диаграммы содержит 6 полных конъюнкций, правая таблица — 8. Таким образом, получается нормальная форма ИЛИ с 14 полными конъюнкциями:
Y = (А А В аС A D A          {А А В аС A D A (А А В аС A D A E)v
v(v4 л В аС aD а Е) v (A aBaCaDaE)v (A aBaCaDaE)v

Карта Карно для более чем пяти переменных

На практике нормальные формы ИЛИ с более чем пятью переменными встречаются редко. Поэтому редко возникает необходимость и в диаграммах Карно для более чем пяти переменных. Однако такие диаграммы реальны. Диаграммы для шести переменных еще можно наглядно представить.
При семи и более переменных наглядное представление диаграммы затруднительно.
Для шести переменных возможны 64 различные полные конъюнкции. Следовательно, карта Карно для шести переменных должна иметь 64 поля. Если в качестве исходной брать диаграммы ДЛЯ пяти переменных величин, то к ней надо добавить еще третий и четвертый уровни-этажи (рис. 5.45).

Карта Карно для шести переменных                            

Рис. 5.45. Карта Карно для шести переменных                                            

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

Карта Карно для шести переменных, развернутая на одной плоскости

Рис. 5.45. Карта Карно для шести переменных, развернутая на одной плоскости

Для нормальной формы ИЛИ с шестью и более переменными целесообразно заменять две или три переменных новой переменной. Упрощение может происходить в несколько этапов:
Z = [А а В а С a D л Е л Fjv (л а В а С a D а Е л F'jv v ^А aBaCaDaEa v (A aBaCaDaEa F).
Пример -----------------------------------------------------------
Все четыре полные конъюнкции содержат переменные А и Е в одинаковом, в данном случае, неинвертируемом виде. Будем рассматривать А а Е как одну переменную.
А а Е = Р.
При таком условии получается нормальная форма ИЛИ только с пятью переменными:
Z = {р А В аС A D A F^{p А В аС A D A F^v
v^PaBaCaDaF^v^PaBaCaDaF).
После упрощения снова заменим Р на А а Е.

Похожие статьи