Размещено на http://www.allbest.ru/

Минимизация булевых функций с помощью карт Карно

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

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

При заполнении карты Карно в ее клетки проставляют значения функции для соответствующих наборов, которые являются координатами клеток. Например, для функции двух переменных А и В (рис. 5) карта Карно имеет вид

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

Всегда нужно стремиться к минимальному количеству контуров и максимальной площади каждого из них, руководствуясь следующими правилами:

· площадь контура покрытия должна быть S

_k = 2^m-i клеток,

где - целое число, m - число переменных. Если, например, m = 3, то S_k = 1, 2, 4, или 8 клеток;

· число сокращаемых переменных

N_перем. = log₂ S_k,

т.е. при S_k = 1 не сокращается ни одна переменная, при S_k = 2 сокращается одна переменная и т.д.

В примере на рис. 5 пара единиц верхней строки охватывается импликантой В (т.е. обе клетки) имеют общий аргумент В). Пара единиц правого столбца накрывается импликантой B, как общей для обеих клеток. Следовательно, минимальная ДНФ функции F(A,B) = В Ъ B.

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

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

.

Карта Карно, состоящая из 2³ = 8 клеток, может быть размечена, как показано на рис. 6.

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

.

Графический метод минимизации - Карты Карно

Карты Карно - это графическое представление операций попарного неполного склеивания и элементарного поглощения.

Карты Карно рассматриваются как перестроенная соответствующим образом таблица истинности функции.

Карты Карно - определенная плоская развертка n-мерного булева куба.

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

Карта Карно для функции 4-х переменных:

Карта Карно рассматривается как поверхность фигуры под названием тор ("бублик").

p-клетки - клетки карты Карно, соответствующие единичному значению функции.

Соседние наборы - наборы, которые различаются только одним аргументом (одной орбитой).

Любой паре соседних наборов в Карте Карно соответствуют соседние клетки.

Две соседние p-клетки на карте Карно дают импликанту первого ранга. Например, клетки 1100 и 1101 отличаются только значением переменной x₃, следовательно, они дают импликанту 124.

Две соседние импликанты первого ранга образуют импликанту второго ранга.

На этой карте соседние клетки образуют импликанты a, b, c, d, e. При этом импликанты a и b являются соседними, поэтому они образуют импликанту второго ранга.

Если функция имеет 5 переменных, то рисуются 2 Карты Карно: для x₅=0 и для x₅=1. Если 6 переменных - 4 Карты, так чтобы в соседних картах соседние клетки имели одинаковые координаты:

Соседние p-клетки, соответствующие импликанте образуют компактную группу.

Количество p-клеток в компактной группе является степенью двойки.

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

Если на картах Карно выделить все компактные группы наибольшей размерности, то дизъюнкция соответствующих конъюнкций даст СкДНФ.

Пример минимизации функции 4-х переменных методом Карт Карно:

Обозначения:

Цветом выделены компактные группы наибольшей размерности, вошедшие в ядро.

Ядро: v v

МДНФ: v v , цена=7

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

карно булев импликанта тупиковый

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

Пусть задана функция 3-х переменных

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

Затем производится объединение 2-х, 4-х или 8-ми единиц. В данном случае объединение двух единиц по горизонтали соответствует операции склеивания над конституантами и , в результате которой исключается переменная B и получена импликанта .Объединение двух единиц по вертикали соответствует операции склеивания над конституантами и , в результате которой исключена переменная С и будет получена импликанта . Следовательно, минимальная форма заданной функции примет следующий вид:

Ниже приведены ряд примеров, поясняющие процесс минимизации функции 3-х переменных методом Карно.

В последнем примере показано, что может быть получено несколько минимальных форм. Если объединить единицы так, как показано сплошной линией, то получим форму . При объединении единиц способом, показанным пунктирной линией, получим другую минимальную форму

Рассмотрим минимизацию функции 4-х переменных. Пусть задана функция

.

Представим в виде карты Карно.

В данном случае возможно объединение 4-х единиц, в результате получим минимальную форму

Ниже приведены примеры минимизации функции 4-х переменных.

Методом Карно возможна минимизация функций 5 переменных. Карта в этом случае имеет 32 поля. Рассмотрим минимизацию следующей функции 5 переменных , которая задана в виде карты Карно.

В результате минимизации, получим следующую форму:

Таким образом, при объединении 2-х полей исключается одна переменная, при объединении 4-х полей - две переменные, при объединении 8-ми полей - три переменные.

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

Размещено на Allbest.ru