Пример 3.
Пример
4.
Задаваемая для минимизации функция должна быть представлена только либо в СДНФ (ДНФ), либо в СКНФ (КНФ).
Основу рассматриваемого метода минимизации логических функций составляет графический аналог операции склеивания, реализуемый с помощью карты Карно. Сопоставление аналитического вида операции склеивания с её графическим аналогом продемонстрировано в примере5.
Пример 5.
Приведённый пример позволяет отметить следующее:
1. полученное объединение единиц есть графическая форма представления результата склеивания минтермов,
2.
объединение, так же как и исходные
минтермы, имеет координаты в виде
последовательности независимых
переменных
,
3.
аналитический результат склеивания
(минимизированная функция рассматриваемого
примера) получается путём логического
перемножения координат полученного
объединения единиц
.
Несмотря на свою простоту, пример 5 в основном отражает существо рассматриваемого метода минимизации логических функций.
Склеиваются только соседние минтермы, а объединяются только соответствующие им единицы, которые всегда оказываются рядом стоящими. Последнее отражает основную особенность карты Карно. Поэтому, объединять можно:
a) две рядом стоящие единицы,
b) две рядом стоящие пары единицы, образующие «четвёрку» единиц,
c) две «четвёрки», объединяющие восемь единиц.
Конфигурация объединений строго регламентирована. Возможные её варианты представлены на рисунке.
Существуют так же модификации разрешённых конфигураций объединений единиц:
Действительно, если мысленно соединить верхний край карты с нижним, образовав трубочку или сделать то же самое с левым и правым краями карты, или, абстрагируясь от реальности, осуществить это всё одновременно, получим другие конфигурации объединений условно рядом стоящих единиц.
Два объединения на карте могут пересекаться. Допустимость пересечения объясняется возможностью размножить любую единицу в клетке карты. То есть, можно выделить для каждого объединения свою единицу.
Пересечение объединений может быть однократным, двух, трёх, и четырёхкратным. Возможные варианты пересечения показаны на рисунке.
Критерий
выбора варианта объединения единиц на
карте Карно из множества возможностей
формулируется следующим образом. Для
достижения минимальной тупиковой формы
функции необходимо обеспечить:
1. минимум числа объединений единиц,
2. максимум единиц составляющих каждое объединение.
Первый пункт критерия носит безусловный характер. Второй пункт должен соблюдаться только при выполнении первого. Формулировку критерия сопровождают два следствия:
a) каждая единица на карте Карно должна принадлежать какому-либо объединению, даже если объединение содержит только одну единицу,
b) объединение должно содержать хотя бы одну «свою» единицу, не принадлежащую ни к какому другому объединению.
Эти следствия так же важно помнить при формировании вариантов объединений единиц.
Пример 6.
В процедуре минимизации функций обычно не расписывают действия как это сделано в примере. Можно сразу же составлять минтермы, не включая в них координаты заключённые в скобки.
Пример 7.
Карты Карно для пяти переменных в части формирования объединений имеют специфику. Единицы, находящиеся только в левой половине карты или только в правой половине карты, объединяются точно так же, как это делается на картах для четырёх переменных. Единицы, находящиеся в разных половинах карты, считаются рядом стоящими и, следовательно, подлежат объединению, если при сгибе карты по вертикальной средней линии они будут накладываться друг на друга. Если всё же возникает сомнение по поводу близости единиц, всегда можно получить по карте соответствующие им минтермы и оценить соседние они или нет.
Пример 8.
Вопросы для самопроверки
Осуществите минимизацию функций, используя метод карт Карно:
;
;
;
Используя метод карт Карно, минимизируйте функции от пяти аргументов:
