8.4. Минимизация переключательных функций по картам Карно

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

Метод минимизации по картам Карно позволяет графически получать экономное покрытие переключательной функции правильными конфигурациями её единиц. Карта Карно – это таблица истинности специального вида, в которой переменные функции расположены не одномерным, а двумерным массивом (по горизонтали и вертикали), причем каждому набору переменных поставлена в соответствие одна клетка. В эту клетку записывается значение функции (0 или 1) на данном наборе. Входные переменные располагаются по внешним сторонам карты напротив её строк и столбцов. При этом единичное значение переменной традиционно обозначается скобкой или линией «влияния» на строки или столбцы, для остальных строк (столбцов) значение этой переменной равно нулю.

Каждая из входных переменных делит карту Карно на две разные части, в одной из которых значение этой переменной равно 1, а в другой 0.

Каждой клетке карты Карно соответствует один определенный набор, а каждая сторона клетки представляет собой границу между значениями переменных. Карты Карно для одной и двух переменных изображены на рис. 41.

Рис. 41. Карты Карно для одной и двух переменных

В правом углу для пояснения указаны наборы переменных, соответствующих клеткам, в базе переменных «аb» («а» имеет вес 2¹, «b» –2⁰).

Задание переключательных функций картами Карно является более компактным, а самое главное – более наглядным, с точки зрения визуального выделения групп рабочих (единичных) наборов. Число клеток карты Карно равно числу таблицы истинности, т.е. 2ⁿ, где n – число входных переменных. В каждой новой переменной число клеток удваивается, т.е. карта увеличивается вдвое.

Пусть задана таблица истинности функции 3-х аргументов, равная единице тогда, когда две входных переменных равны единице (две и только две!). Это так называемая мажоритарная функция или функция голосования по большинству «2 из 3-х» (табл. 38).

Таблица 38

Мажоритарная функция

Представим эту функцию в виде карты Карно (рис. 42).

Рис. 42. Задание мажоритарной функции картой Карно

Если функция задана СДНФ, её также просто представить в виде карты Карно. Если функция задана в ДНФ, то необходимо проставить единицы в те клетки, которые соответствуют областям конъюнкции соответствующих переменных. Пусть задана та же функция «голосование по большинству голосов» («2 из 3-х» или мажоритарная функция): f(аbс)=аb Ú bс  ас.

Тогда в карте Карно на три переменных единицы проставляются в клетках, соответствующих пересечению «областей влияния» одновременно двух переменных: а и b, b и с, а и с (рис. 43).

Рис. 43. Задание картой Карно f(аbс)=аb Ú bс  ас

Можно получить СДНФ, рабочие наборы этой функции:

.

Аналогично может быть получена СКНФ функции:

.

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

Карта Карно на четыре переменных содержит 16 клеток (рис. 44).

Рис. 44. Карта Карно на четыре переменных

Такая таблица гораздо компактней, чем таблица истинности из 16 строк. Заметим, что переменные в карте Карно проставляются в определенном порядке так, чтобы каждая покрывала половину карты и не повторяла других переменных. Переменные базы в карте Карно 4-х переменных следуют: по вертикали – снизу вверх, по горизонтали – справа налево (кстати, карты Карно и подобные им карты Вейча отличаются способом кодировки – вариантами проставления переменных).

Карты Карно имеют замечательное свойство, заключающееся в том, что наборы значений переменных для клеток, стоящих рядом (соседние клетки), отличаются значением лишь одной переменной. При переходе от одной клетки в соседнюю, всегда изменяется значение лишь одной переменной («1» на «0» или наоборот).

Так для карты четырех переменных (рис. 44) для второго столбца и третьей строки получаются следующие конституенты или наборы переменных номера клетки (рис. 45).

Очевидно, что наборы переменных (соответствующие конституентам переключательной функции) двух соседних клеток отличаются друг от друга значением только одной переменной. Такие наборы, отличающиеся значением одной переменной, называются соседними наборами (кодами). Таким образом, соседние клетки карты Карно имеют соседние коды (наборы). Можно также сказать, что между соседними кодами имеется кодовое расстояние, равное единице (кодовое расстояние равно количеству разрядов, в которых коды отличаются друг от друга). Соседними являются также крайние левые клетки карты Карно с крайними правыми клетками и крайние верхние клетки с крайними нижними (как если бы карта была свернута по вертикали и по горизонтали). В этом легко убедиться, сравнивая наборы (рис. 45).

Рис. 45. Иллюстрация соседних клеток карты Карно

(соседние по переменной а),

(соседние по переменной с).

На картах Карно до 4-х переменных соседние клетки расположены рядом, граничат друг с другом, т.е. соседство очевидно.

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

Минимизация переключательной функции по карте Карно в классе ДНФ заключается в покрытии ее единиц минимальным количеством максимальных правильных контуров. В эти контуры могут включаться и условные наборы. Контуры могут пересекаться, но не могут включаться друг в друга – иначе не получатся простые импликанты. Правильными контурами для карты 4-х переменных могут быть следующие:

одноклеточный – одна клетка с единицей, окруженная нулями;

двухклеточный – две соседние клетки, окруженные нулями;

четырехклеточный – квадрат из четырех соседних клеток, окруженных нулями;

восьмиклеточный – куб из восьми соседних клеток, окруженных нулями;

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

Типичные конфигурации максимальных правильных контуров представлены: на рис. 46-48 [17].

Рис. 46. Двухклеточные

Рис. 47. Четырехклеточные

Рис. 48. Восьмиклеточные

На этих рисунках изображена так называемая цифровая кодировка карт. Особое внимание следует обращать на контуры, которые имеют видимый разрыв, так как объединяемые ими соседние клетки находятся в крайних строках или столбцах карты Карно. Найдем импликанты соответствующих функций для рис. 46а. Воспользуемся методом Квайна-Мак-Класки: f(х₁х₂х₃х₄)=0000001001011101. Ясно, что наборы 0000 и 0010 склеиваются по переменным х₁х₂х₄ (00-0), а наборы 0101 и 1101 – по переменным х₂х₃х₄ (-101). Получаем две импликанты:

Однако нет необходимости производить склеивания – нетрудно убедиться, что простая импликанта легко находится по карте следующим образом: в нее входят те переменные, которые во всех клетках данного контура не меняют своего значения (речь идет о номере клетки!). Для рис. 46б получаем:

Для рис. 47а:

Для рис. 47б:

Для рис. 47в:

Для рис. 48а:

Для рис. 48б:

Для рис. 48в:

По карте Карно удобна также минимизация в классе КНФ. В этом случае каждому контуру из нулей с возможным добавлением «тильд» соответствует имплицента – член КНФ, которая строится также из переменных, не меняющих своего значения в номере клеток «нулевого» контура, только, если переменная в номере клетки равна нулю, то в КНФ она будет без инверсии, а если равна единице – то в КНФ она будет с инверсией.

Так, для рис. 46б f(х₁х₂х₃х₄) получим имплиценты:

1) (х₂ х₄) – угловые клетки;

2) – квадрат (0100,1100,0101,1101);

3) – квадрат (1111,1110,1011,1010);

4) – квадрат (0011,0010,1011,1010).

Таким образом: