Вычислительная техника. Захаров Н.Г - 26 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

26
х
2
х
3
х
1
00 01 11 10
0 1 1 1 1
1 0 1 0 0
Рис. 2.4. Структура карты Карно для функции
Ячейки, в которых функция принимает значение 1, заполняются единицами.
Процесс минимизации заключается в формировании прямоугольников, содержащих
по 2
k
ячеек, где k – целое число. В прямоугольники объединяются соседние ячейки,
которые соответствуют соседним элементарным произведениям. Например, на
рис. 2.4 объединены ячейки с координатами 001 и 101. При объединении этих ячеек
образовался прямоугольник, в котором х
1
изменяет свое значение. Следовательно,
оно исчезает при склеивании соответствующих элементарных произведений
321
ххх и
321
ххх . Ячейки, расположенные в первой строке, содержат 1 и явля-
ются соседними. Поэтому они объединяются в прямоугольник, содержащий 2
2
= 4
ячейки. Переменные х
2
и х
3
в пределах прямоугольника меняют свое значение, следо-
вательно, они исчезнут из результирующего элементарного произведения. Перемен-
ная х
1
является неизменной и равной нулю. Таким образом, элементарное произведе-
ние, полученное в результате объединения ячеек первой строки, содержит лишь эле-
мент
1
х . Это следует из того, что четырем ячейкам первой строки соответствует сум-
ма четырех элементарных произведений:
.х)хх(ххххх)хх(хх)хх(хх
хххххххххххх
1221212133213321
321321321321
Совокупность прямоугольников, покрывающих все единицы, называют покры-
тием. Одна и та же ячейка может покрываться несколько раз. Итак, можно сделать
следующие выводы:
1. Формула, получающаяся в результате минимизации логической функции с
помощью карт Карно, содержит сумму стольких элементарных произведений, сколь-
ко прямоугольников имеется в покрытии.
2. Чем больше ячеек в прямоугольнике, тем меньше переменных содержится в
соответствующем ему элементарном произведении.

Страницы