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

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

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

Для двух – четыре клетки

трех – восемь клеток

четырех – шестнадцать.

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

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

В таблице указаны номера наборов и записаны, соответственно, конституенты единицы на этих наборах.

Из таблицы видно, что по горизонтали конституенты нулевого и первого наборов склеиваются по букве В, а результатом является , конституенты второго и третьего наборов также склеиваются по В, но результатом является А. По вертикали конституенты первого и третьего наборов склеиваются по А, а результатом является В, а нулевого и второго наборов также по А, но результатом является . 

Таблица 3.2.1

   

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

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

Рассмотрим примеры:

Пример 1.

F(AB)=V(0, 1, 2) – функция задана единицами на трех наборах 0-м, 1-ом и 2-ом.

   

При правильной минимизации мы получаем истинный смысл функций.

Пример 2.

.

Пример 3.

Склеивание не возможно.

Единственной формой для реализации этой функции является СДНФ=  v , которую легко записать по карте.

Пример 4.

Приведем минимизацию 15-ой функции

f(AB)= v(0, 1, 2, 3) 

            

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

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

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

Рассмотрим карту Карно для трех переменных:

.

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

Например 1:

Еще одна ситуация, когда функция имеет четыре еденицы.

.

. То есть одновременно проклеить четыре единицы.

Учитывая эти особенности, можно сформулировать общее правило получения минимальных форм.

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

Такое правило дает минимальное количество членов с минимальным количеством букв.

Пример:

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

  

Еще один пример: . Из карты видно, что можно три раза проклеить по четыре единицы.

.

 

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

Например: . Следовательно реализация этой функции возможно только по СДНФ.  СДНФ =

Проведем минимизацию нашего примера о голосовании

.

Карта Карно для четырех переменных. Следовательно для реализации устройства достаточно одного инвертора, двух двухвходовых схем «И» и одной двухвходовой схемы «ИЛИ».

Рассмотрим различные примеры.

Пример 1:

Из таблицы видно, что конституенты на 6-м наборе ни с одной единицей не склеивается, следовательно она полностью войдет в минимальную форму.

.

 

Пример 2:

Из таблицы видно, что возможно проклеивание по 4-м единицам одновременно.

.

Пример 3:

.

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

Сплошными линиями показаны склейки для . Пунктирами еще два варианта

⇐ Предыдущая1234567Следующая ⇒

Поделиться: