Карты Карно для 4-х переменных.

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

Например, на рис. показана карта Карно для функции, отображение которой дано на 4-х-мерном кубе (см. рис.).

Для упрощения строки и столбцы, соответствующие значениям “1” для некоторой переменной, выделяются фигурной скобкой с обозначением этой переменной.

Рис. а) отображение функции четырех переменных;

б) отображение ее минимального покрытия.

 

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

у = , рассматриваемой функции.

Считывание минитермов с карты Карно осуществляется по простому правилу. Клетки, образующие S -куб, дают минитерм (n-S)-го ранга, в который входят те (n-S)-переменные, которые сохраняют одинаковые значения на этом S -кубе, причем значениям “1” соответствуют сами переменные, а значениям “0” их отрицание.

Переменные, которые не сохраняют свои значения на S -кубе, в минитерме отсутствуют. Различные способы считывания приводят к различным представлениям функции в ДНФ.

у = у =

у =

Использование карт Карно требует более простых построений по сравнению с отображением на n -мерном кубе, особенно в случае 4-х переменных.

Для отображения функций 5-ти переменных используют две карты Карно на 4-ре переменные, а для функции 6-ти переменных — четыре таких карты.

При дальнейшем увеличении числа переменных карты Карно становятся практически непригодны.

 

Метод Мак-Класски (алгебраический метод)

Алгебраический метод известен как метод Мак-Класски, модифицировавшего в 1956 году метод Квайна. Базируется данный метод на следующей теореме.

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

Элементарную конъюнкцию ранга n будем называть минитермом ранга n.

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

Минимизация булевой функции по методу Мак-Класски осуществляется согласно следующей последовательности действий:

1. Записать минитермы в виде их двоичных кодов и разбить их на непересекающиеся группы по числу единиц в этих группах. В i-ю группу войдут только те кодовые комбинации, которые в своей двоичной записи содержат ровно i единиц. Группы располагаются по мере роста i.

2. Попарное сравнение минитермов.

2.1. Произвести попарное сравнение двоичных номеров всех членов группы с индексом i с членами только группы с индексом (i+1).

2.2. Если некоторые два минитерма имеют вид ax_i и , то выписывают конъюнкцию а, которая является минитермом ранга (n-1), то есть если сравниваемы двоичные коды различаются только в одном разряде, то в столбец остатков записывается двоичный код с прочерком “-” на месте этого разряда (этот код соответствует минитерму (n-1)-го ранга.

2.3. Все двоичные коды номеров, участвующих в операции сравнения при условии их склеивания, отмечаются знаком “*”.

2.4. Пункты 2.1-2.3. повторяются для всех групп последовательно в порядке возрастания i. Двоичные коды, не отмеченные знаком “*”, соответствуют простым импликантам.

2.5. После построения всех минитермов (n-1) ранга по пунктам 2.1-2.3, они также сравниваются между собой и получают минитермы ранга (n-2) и т.д. Работа по первому этапу продолжается до тех пор, пока среди двоичных кодов можно будет обнаружить сравнимые, то есть такие укороченные коды, которые содержат прочерки в одних и тех же разрядах и различаются значением одного разряда.

Все неотмеченные минитермы называются первичными или простыми импликантами.

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

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

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

6. Вычеркивание лишних первичных импликант. Если на пятом этапе появляются строки, в которых нет меток, то первичная импликанта исключается из дальнейшего рассмотрения.

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

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

Пример.

.

1) Получение групп кодовых комбинаций. 0011 0100 0101 0111 1001 1011 1100 1101

1 гр. 0100 2 гр. 0011 3 гр. 0111

0101 1011

1001 1101

2) Попарное сравнение минитермов.

Минитермы 3-го ранга: 010-*, -100, 0-11, -011, -101, 10-1, 1-01, 110-*

Минитермы 2-го ранга: -10-.

 

3) Построение импликантной таблицы и расстановка меток

-100	*				*
0-11		*				*
-011		*					*
-101			*					*
10-1				*			*
1-01				*				*
-10-	*		*		*			*

 

4) Нахождение существенных импликант. Столбец, соответствующий кодовой комбинации 0111 содержит единственную метку. Соответствующая этой метке импликанта является существенной, поэтому включаем ее в минимальную ДНФ , а из таблицы согласно п.4 исключаем столбцы и строку, после чего получаем следующую таблицу:

 

-100	*			*
-011					*
-101		*				*
10-1			*		*
1-01			*			*
-10-	*	*		*		*

 

5) и 6) В полученной таблице нет столбцов, в которых стоят метки в одинаковых строках и нет строк, в которых нет меток, поэтому переходим к п.7.

7) Выбор минимального покрытия. Минимальному покрытию соответствует выбор строк -10- и 10-1. Тогда минимизированная ДНФ запишется как .