Метод Блейка - Порецкого

Недостатком рассмотренных методов является то, что сокращенная ДНФ строится по СДНФ, которая при n = 5, 6 становится довольно громоздкой. Например, если функция имеет следующий вид ДНФ:

и требуется определить для нее МДНФ, нужно построить СДНФ, которая состоит из 18 минтермов.

Метод Блейка - Порецкого позволяет строить сокращенную (Сокр. ДНФ) ДНФ не по СДНФ, а по произвольной ДНФ. Метод основан на следующей теореме [16].

Если в ДНФ функции входят две конъюнкции вида и , то имеет место равенство:

, (4.1.)

где P – ДНФ функции .

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

Пример 4.6.

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

Рис. 4.1. Рабочая карта Карно для ФАЛ, заданной таблицей 4.3.

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

На рисунке 4.2. представлена так называемая эталонная карта Карно для n = 3. Она служит для указания расположения переменных, как координат клеток, так и наборов этих переменных. Координатой клеток в горизонтальном направлении служат наборы переменных , а координатой клеток в вертикальном направлении служит одна переменная .

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

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

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

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

Расположение номеров наборов (клеток) в основной карте Карно легко запоминается по мнемоническому “правилу четырёх Z”. Это правило заключается в следующем: Z большое - это клетки 0,1,2,3; Z узкое - 4,5,6,7; Z широкое - 8,9,10,11; Z малое - 12,13,14,15.

В других картах принцип четырёх Z сохраняется, изменяются только направления и начальные точки (рисунок 3.3.).

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

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

Рисунок 4.3. Карта Карно - “правило четырех Z”.

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

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

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

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

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

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

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

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

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

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

покрытиями

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

(4.2.)

(4.3.)

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

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

Пример 4.7. Для клетки с набором 25 на рис. 4.5.б соседними являются клетки с номерами наборов 9, 27, 17, 24 и 29. Для клетки с набором 2 на рис. 4.5.б соседними являются клетки 3, 10, 0, 18 и 6.

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

Для клетки с набором 43 на рис. 4.5.в соседними являются клетки с наборами 59, 42, 35, 41 и 47, 11. Для клетки с набором 22 на рис. 4.5. в соседними являются клетки с наборами 23, 30, 20, 6 и 54, 18.

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

(4.4.)

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

(4.5.)

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

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

(4.6.)

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

(4.7.)

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

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

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

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

(4.8.)

(4.9.)

(4.10.)

(4.11.)

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

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

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

Рисунок 4.8. Рабочая карта Карно неполностью

определённой ФАЛ

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

Для логических функций с числом переменных n ³ 6 наглядность карт Карно теряется и поэтому, такие функции представляются в виде композиции функции меньшего числа переменных:

,

где x₁ - выделяемая переменная;

функции получаются из функции f подстановкой значений x₁=0 и x₁=1.

В качестве выделяемой может использоваться любая переменная. Например,

Процесс выделения более простых функций называется декомпозицией. Полученные функции f₀ и f₁ могут подвергаться дальнейшей декомпозиции.

Достоинства метода минимизации ФАЛ с помощью карт Карно состоят в следующем.

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

2. Их применение оправдано для n = 2 ÷ 6, а при определенных навыках даже для n = 7 и 8, что соответствует большинству реально встречающихся инженерных задач.

3. Карты Карно можно использовать для минимизации ФАЛ, заданных как в СДНФ, так и в СКНФ.

4. Удобно минимизировать системы булевых функций, так как на картах Карно легко выделять общие части реализуемой системы ФАЛ.

5. Легко находятся минимальные комбинации контуров по их виду на карте Карно.

6. На одной карте Карно можно изобразить систему ФАЛ, в каждой из которых одна 1 или один 0 (например, ДС 1 из 4; 8; 16; … с активной “1” или “0”).

7. Для построения карты Карно не обязательно задавать её в СДНФ или СКНФ (можно подставить значения наборов в любой вид ФАЛ и заносить значения ФАЛ на этом наборе в соответствующую клетку карты Карно).

8. Карты Карно сразу позволяют реализовать первые два этапа минимизации (склеивание и выявление лишних импликант).

Недостатки:

1. Затруднительно использовать карты Карно при n > 6.

2. Метод не является алгоритмически систематическим, многое зависит от навыков разработчика. Удобство обращения и экономия времени во многом зависит от его способности распознавать оптимальные конфигурации покрытия карт Карно.

Пример 4.8. Рассмотрим задачу построения схемы отображения цифр, которые набирает пользователь, нажимая клавиши на клавиатуре микрокалькулятора, в их изображение (рис.4.9.). Двоичное кодирование цифр осуществляется непосредственно в момент нажатия клавиши в четырехразрядный двоично-десятичный код. Декодирование изображений осуществляется семисегментной структурой светодиодов, специальное расположение которых позволяет высвечивать различные цифры: подача напряжения на соответствующую полоску f₀ - f₆ вызывает ее свечение. Непосредственно логическая схема отображения СО имеет четыре двоичных входа и семь двоичных выходов (по числу сегментов светодиодов).

Рисунок 4.9. Отображение цифр в микрокалькуляторе (а);

семисегментная структура светодиодов для отображения цифры (б);

и один разряд схемы отображения (в).

Кроме десяти цифр со стандартным двоично-десятичным кодированием пусть в схеме можно представить знак минус кодом <1111>. Семь двоичных функций f₀-f₆ представлены таблицей истинности 1.9; функции эти неполностью определены, поскольку коды, не соответствующие десятичным цифрам и знаку минус не могут появиться на входе схемы отображения. Мы можем дополнить их произвольными значениями исходя, например, из критерия минимальности функции. Заполнение таблицы 4.4. очевидно: например, для изображения цифры 5 (двоичный код на входе СО <0101>) следует подать напряжение на все полоски светодиодов, кроме f₃ и f₆.

Таблица 4.4.

Минимизация неполностью определенных функций f₀-f₆ может быть легко проведена с помощью карт Карно. На рисунке 4.10. приведены две карты Карно функций f₀ и f₂.

Рисунок 4.10. Карты Карно функций f₀ и f₂
схемы отображения микрокалькулятора.

После минимизации можем записать:

Пример 4.9. Рассмотрим проблему словесной формулировки условия достижения консенсуса (общего согласия) в вычислительной сети. Возможность достижения консенсуса в сети зависит от четырех параметров сети:

- тип процессоров; процессоры могут быть асинхронными (А) или синхронными (С);

- сохранение порядка сообщений в канале: {порядок сохраняется (П), либо без сохранения (Б)};

- вид передачи сообщений: {широковещательная передача (Ш), точка-точка (Т)};

- ограничение коммуникации во времени: { коммуникация ограничена (О), не ограничена (Н)}.

Исследования показали, что консенсус достижим только в сетях со следующими наборами параметров: (А,П,Ш,Н), (А,П,Ш,О), (С,Б,Т,О), (С,Б,Ш,О), (С,П,Ш,Н), (С,П,Ш,О), (С,П,Т,Н), (С,П,Т,О). На основе теории двоичных функций сформулировать условия достижимости консенсуса в вычислительных сетях можно, не понимая, что такое консенсус, и не имея никакого представления о вычислительных сетях. Построим карту Карно двоичной функции Консенсус четырех двоичных переменных, каждая из которых соответствует одному из указанных параметров (рис. 4.11.).

Рисунок 4.11. Карта Карно двоичной функции Консенсус.

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

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

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

;

,

.

В рассмотренном примере двум клеткам первого объединения соответствуют минтермы, имеющие две общие переменные

.

Поэтому дизъюнкция этих минтермов равна этим двум общим переменным: .

Четырем клеткам второго объединения соответствуют минтермы имеющие одну общую переменную :

Дизъюнкция этих минтермов также равна общей переменной .

Пример 4.11.Логическая функция задана таблицей.

Найти СДНФ этой функции, и провести минимизацию с помощью карты Карно.

Решение:1. Находим минтермы:

x1	x2	mi	f

2. Логическая функция в форме СДНФ:

.

4. Карта Карно логической функции:

5. Получают МДНФ функции

6.

.