Булева алгебра (1023551), страница 7

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 7)

Рис. 8. Эталонная карта Карно для n = 3

Известно, что каждая из n переменных встречается в половине наборов без инверсии, а в другой половине с инверсией. Три линии, расположенные с внешней стороны карты Карно, указывают, что в соответствующих им половинах клеток указанная рядом с этой линией переменная встречается в наборе без инверсии и, соответственно, в другой половине с инверсией. (Можно предположить и обратное – там, где черта – переменная с отрицанием) Так как переменным , , , условно присваиваются “веса” соответственно 2⁰ = 1, 2¹ = 2 и 2² = 4, то восемь наборов в клетках карты Карно будут расположены так, как указано на рис. 8.

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

Правильность оформления эталонной карты Карно можно проверить следующим образом. Если линию, соответствующую переменной протянуть вправо по горизонтали над клетками карты Карно, то она пройдет над клетками, в которых минимальный номер набора должен совпадать с весом переменной , равным 2² = 4. Аналогично линия, соответствующая переменной , при перемещении вниз по вертикали пройдет над клетками, в которых минимальный номер набора должен совпадать с весом переменной , равным 2¹ = 2. Это должно выполняться для всех переменных.

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

Рабочая карта Карно, соответствующая табл. 5, будет иметь вид, представленный на рис. 9.

Рис. 9. Рабочая карта Карно для ФАЛ, заданной табл. 1

Буква y рядом с косой линией, расположенной в левом верхнем углу карты Карно, обозначает реализуемую функцию, а цифры 0 и 1 в клетках карты указывают значения этой функции на соответствующих наборах. Полученную рабочую карту Карно можно интерпретировать как компактное представление ФАЛ в СДНФ (по значениям истинности), либо в СКНФ (по значениям ложности). Дальнейшее изложение ведется в предположении, что минимизация ведется в дизъюнктивных формах.

Процесс минимизации с помощью карт Карно базируется на использовании операции склеивания и основан на следующих положениях:

1. На картах Карно необходимо выделить монолитные области единичных клеток, образующих строку, столбец, прямоугольник или квадрат и содержащие одну, две, четыре, восемь и т. д. клеток. Эти выделенные области (или контуры покрытия) будут соответствовать импликантам. Очевидно, что одна изолированная 1-я клетка будет соответствовать конституенте единицы. Две смежные клетки будут соответствовать импликанте, ранг которой r = n - 1, четыре смежные клетки будут соответствовать импликанте, ранг которой r = n - 2 и т.д.

2. Переменные, от которых импликанта не зависит, входят в соответствующий выделенный контур как в виде , так и в виде , а остальные переменные только либо в виде , либо в виде .

3. На основании закона тавтологии любая 1-я клетка может быть включена в любое число различных контуров.

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

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

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

7. Если в карте Карно нет ни одной 1, то ФАЛ эквивалентна константе 0; если нет ни одного 0, то ФАЛ эквивалентна константе 1; если единицы занимают половину клеток карты Карно и представляют из себя монолитный массив в виде строки, столбца, прямоугольника или квадрата, то соответствующая импликанта состоит из одной переменной со знаком или без знака инверсии.

С учетом сказанного на картах Карно рис. 10 можно выделить три контура, содержащих по две 1(единицы).

Рис. 10. Рабочие карты Карно с двумя эквивалентными покрытиями

Два варианта покрытия обусловлены тем, что 1 в клетке с набором 5 может образовать контур из двух клеток либо с набором 4 (рис. 10,а), либо с набором 1 (рис. 10,б). Поясним получение импликанты для контура, образованного двумя клетками в нижней строке карты. Переменная входит в этот контур только с инверсией, переменная входит в этот контур и с инверсией и без инверсии, поэтому по ней осуществляется склеивание, и она исчезает, переменная входит в этот контур только без инверсии, поэтому импликанта имеет вид . Другой способ определения импликанты будет показан ниже. Для выявленных двух покрытий можно записать:

(22)

(23)

Простота получения уравнений (22) и (23) показывает существенное преимущество табличного метода карт Карно перед расчетным методом.

На рис. 11 показаны эталонные карты Карно для n = 4, 5 и 6, причем карты Карно для n = 5 и 6 можно рассматривать как соответственно две и четыре карты Карно для n= 4, имеющие общие границы (они выделены толстыми центральными линиями). Карты Карно для n = 4, являющиеся составной частью карт Карно для n = 5 и 6 и имеющие общие границы, называются соседними. Правило соседства, для какой либо клетки в этих случаях, будет выглядеть так: для любой выделенной клетки соседними являются четыре соседние клетки в карте Карно для n = 4 и клетки, расположенные в соседних картах Карно для n = 4 симметрично выделенной клетке относительно границ соседних карт Карно.

Р
ис. 11. Эталонные карты Карно для n = 4, 5 и 6.

Пример. Для клетки с набором 25 на рис. 11,б соседними являются клетки с номерами наборов 9, 27, 17, 24 и 29. Для клетки с набором 2 на рис. 11,б соседними являются клетки 3, 10, 0, 18 и 6. Для клетки с набором 43 на рис. 11,в соседними являются клетки с наборами 59, 42, 35, 41 и 47, 11. Для клетки с набором 22 на рис. 11,в соседними являются клетки с наборами 23, 30, 20, 6 и 54, 18.

Рассмотрим еще несколько примеров для функций, зависящих от 4-х, 5-ти и 6-ти переменных. На рис. 12,а четыре 1-е клетки образуют квадрат, которому соответствует импликанта . На рис. 12,б контур, выделенный штриховой линией, оказывается лишним, так как все его клетки являются составными частями четырех контуров из двух клеток. Из карты Карно (рис. 12,б) получаем:

Р
ис. 12. Рабочие карты Карно произвольных ФАЛ,

зависящих от четырёх переменных

. (24)

Для карты Карно (рис. 12,в) покажем еще один способ определения импликант, соответствующих выделенным контурам, состоящих в данном случае из двух столбцов. Для левого контура запишем минимальный и максимальный наборы . Таковыми являются наборы 2 и 14. Запишем их двоичные представления 0010 и 1110 одно под другим и проверим их поразрядно на равенство. В результате получим 0011. Переменные, соответствующие позициям с 0, склеиваются, а совпадающие позиции с 1 соответствуют искомой импликанте . Аналогичная процедура для правого контура дает импликанту . В итоге получаем:

. (25)

Если теперь на той же карте Карно выделить контуры, соответствующие импликантам и (см. рис. 12,г), то окажется, что общая часть этих контуров будет содержать нулевые клетки.

Для ФАЛ, представленной на рис. 12,д, можно записать:

(26)

Преобразуем это выражение

(27)

Если на той же карте Карно выделить контуры, соответствующие импликантам (см. рис. 12,е), то окажется, что общая часть этих контуров содержит нуль.

Теперь можно сделать следующий вывод: если в карте Карно можно выделить два пересекающихся контура с общей нулевой частью, то импликанты, соответствующие этим контурам, объединяются знаком операции “сумма по mod2”.

Картам Карно, показанным на рис. 13,а-г, соответствуют следующие выражения:

(28)

(29)

(30)

(31)

Карты Карно удобно использовать и для минимизации не полностью определенных функций. Пусть требуется выработать осведомительный сигнал о том, что содержимое одноразрядного двоично-десятичного счетчика равно 6 или 7. Выходные переменные его четырех двоичных разрядов обозначим . Очевидно, что на наборах 0 - 5 и 8, 9 , на наборах 6 и 7 , а наборов 10 - 15 никогда не будет в нормально работающем двоично-десятичном счетчике и, следовательно, значение на этих наборах безразлично. Безразличные значения ФАЛ на картах Карно обозначаются каким-либо символом: крестиком, чертой, буквой и т. п. Карта Карно для этого случая приведена на рис. 14.

Доопределив безразличные значения на наборах 14 и 15 единицами, получим следующее минимальное выражение

(32)

После реализации этой функции она становится полностью определенной, то есть на безразличных наборах, включенных в контур, будут реализовываться значения 1, а на не включенных в контур - значение 0.

Характеристики

Список файлов книги