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

UptoLike

ВУЗ: 

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

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

Рубрика: 

23
.ххх)хх(ххххххххх
)хх(хх)хх(хх)хх(хх)ххх
ххх()хххххх()хххххх(у
13222132212132
332133211132321
321321321321321
Эта формула гораздо проще исходной СДНФ. Здесь в формуле (2.4) в каждой
паре объединяемые элементарные произведения различаются лишь одной перемен-
ной, которая входит в первое произведение с отрицанием, а во второе – без отрица-
ния. Такие элементарные произведения называются соседними. К соседним произве-
дениям применима операция склеивания, в результате которой уменьшается число
суммируемых произведений и на единицу уменьшается число переменных.
2.6. Табличные методы минимизации. Карты Карно
Стремление к алгоритмизации поиска соседних элементарных произведений
привело к разработке табличных методов минимизации логических функций. Одним
из них является метод, основанный на использовании карт Карно.
Карты Карно – это графическое представление таблиц истинности логических
функций. Они представляют собой таблицы, содержащие по 2
n
прямоугольных ячеек,
где n – число логических переменных.
На рис. 2.1, 2.2 и 2.3 приведены структуры карт Карно для функции двух, трех
и четырех переменных, а в таблицах 2.4 и 2.5 представлены таблицы истинности для
функции двух, трех переменных соответственно.
Таблица 2.4
х
1
х
2
f(x
1
, x
2
)
0 0 f(0, 0)
0 1 f(0, 1)
1 0 f(1, 0)
1 1 f(1, 1)
х
2
х
1
0 1
0 f(0,0) f(0,1)
1 f(1,0) f(1,1)
Рис. 2.1. Структура карты Карно для функции двух переменных

Страницы