Суббота, 10.12.2016, 21:26
Главная Регистрация RSS
Вы вошли как Гость | Группа "Гости"Приветствую Вас, Гость
Поделиться
Статистика
Яндекс.Метрика
Flag Counter
Онлайн всего: 28
Гостей: 28
Пользователей: 0
» »
22:49
Карты Карно

Карты Карно

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

Карты Карно были изобретены в 1952 Эдвардом В. Вейчем и усовершенствованы в 1953 Морисом Карно, физиком из «Bell Labs», и были призваны помочь упростить цифровые электронные схемы. В карту Карно булевы переменные передаются из таблицы истинности и упорядочиваются с помощью кода Грея, в котором каждое следующее число отличается от предыдущего только одним разрядом.

 

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

  • Если необходимо получить минимальную ДНФ, то в Карте рассматриваем только те клетки которые содержат единицы, если нужна КНФ, то рассматриваем те клетки, которые содержат нули.

Алгоритм минимизации по методу карт Карно:

1.Метод Карно основан на представлении исходной функции, заданной в форме СДНФ, в виде карты следующего вида:

Карты Карно

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

3. Далее берём первую область и смотрим, какие переменные не меняются в пределах этой области, выписываем конъюнкцию этих переменных; если неменяющаяся переменная нулевая, проставляем над ней инверсию. Берём следующую область, выполняем то же самое, что и для первой, и т. д. для всех областей.

4. Конъюнкции областей объединяем дизъюнкцией.

Пример. Методом Карно минимизировать функцию:

$$y=f\left ( A,B,C \right )=\bar{A}\bar{B}\bar{C}\vee \bar{A}B\bar{C}\vee A\bar{B}\bar{C}\vee A\bar{B}C$$

Решение.

1.Заданную функцию представим с помощью карты Карно:

Карта Карно

2. Затем производится объединение 2-х, 4-х или 8-ми единиц. В данном случае объединение двух единиц по горизонтали соответствует операции склеивания над конституентами $\bar{A}\bar{B}\bar{C}$ и $\bar{A} B \bar{C}$ , в результате которой исключается переменная B и получена импликанта $\bar{A} \bar{C}$ . Объединение двух единиц по вертикали соответствует операции склеивания над конституентами $A\bar{B}\bar{C}$ и $A\bar{B}C$ , в результате которой исключена переменная $С$ и будет получена импликанта $A\bar{B} $ .

Минимизация булевых функций методом Карно

3. Следовательно, минимальная форма заданной функции примет следующий вид: $$y= \bar{A} \bar{C} \vee A \bar{B}$$.

Категория: Дискретная математика | Просмотров: 938 | Добавил: Admin | Теги: булева алгебра | Рейтинг: 0.0/0



Всего комментариев: 0
avatar
  .