Топологическая интерпретация правил минимизации

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

Смежные или соседние единицы могут быть объединены в одну группу, причём число единиц в группе равно , например для рис. 2.11. эта группа состоит из четырёх единиц и её соответствует конъюнкция db.

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

Правила минимизации:

1. Объединяем единицы (нули) в группы, число которых в группе равно , причём k=0…n, где n – число переменных, каждой группе соответствует конъюнкция n-k переменных. Исключаются k переменных, относительно осей которых выполняется правило симметрии.

2. В объединение включается как можно большее число единиц и нулей.

3. Одни и те же единицы (нули) могут входить в разные объединения.

4. Минимизация начинается с тех единиц (нулей) которые образуют единственно возможные максимальные объединения.

5. Объединения должны покрывать все единицы (нули) функции.

Дата добавления: 2014-01-05