Нулевое покрытие булевой функции и получение МКНФ

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

Принципы построения нулевого покрытия такие же, как и для единичного.

Пример 2.14. Для булевой функции из примера 2.11. найти минимальное нулевое покрытие и составить МКНФ.

Числовое представление булевой функции по единичным значениям имеет вид:

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

Определим множество максимальных кубов нулевого покрытия. Над 0-кубами кубического комплекса

 

               

                            S^a=9

                          S^b=12;

 

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

 

 Поскольку 0-куб (101) не склеивался с другими 0-кубами, а 1-куб – единственный (К²( )=Æ ), то множество максимальных кубов:

                                            

                              S^a=5        

                  S^b=7.

Минимальное нулевое покрытие совпадает с множеством максимальных кубов:

Замечания.

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

 

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

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

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

Представление булевых функций на картах Карно

Одним из способов графического представления булевых функций от небольшого числа переменных являются карты Карно. Карты Карно были изобретены в 1952 г. Эдвардом В. Вейчем (диаграммы Вейча) и усовершенствованы в 1953 г. Морисом Карно, физиком лаборатории Белла (Bell Labs).

Идея построения карт Карно различной размерности и представление булевых функций на них изложены в разделе 2.8.2.

На рис. 2.4. приведены булевы функции от трех переменных из примеров 2.10 (а) и 2.11 (б).

а)            х2х3   х1   00 01 11 10 0   1 1 1 1     1 1	б)            х2х3   х1   00 01 11 10 0 1 1     1 1   1 1

 

 

Рис.2.4. Карты Карно функций от трех переменных

 

В связи с тем, что в основе формирования кубов различной размерности k (k > 0) положены отношения соседства и операции склеивания, порядок проставления координат (х₂ х₃) в столбцах карты {(00), (01), (11), (10)} принят таким, чтобы соседние 0-кубы размещались в геометрически соседних клетках карты.

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

 

	x 3 x 4
x 1 x 2		00	01	10	10
	00	1
	01	1
	11		1		1
	10				1

 

 

Рис.2.5. Карта Карно функции от четырех переменных

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

 

Образование кубов различной размерности на картах Карно

Две соседние клетки образуют 1-куб. При этом имеется в виду, что клетки, лежащие на границах карты, также являются соседними по отношению друг к другу. Примеры образования 1-кубов приведены на рис. 2.6 а), б).

а)

б)

Рис. 2.6. Образование 1- кубов на картах Карно для функций от трех (а) и

четырех (б) переменных

Карты позволяют для функций f ₁ и f ₂, заданных комплексами K ⁰(f ₁)и K ⁰(f ₂)

с ценами S ^а(f ₁) = 15, S^b(f ₁) = 20  и  S^a(f ₂) = 24, S^b(f ₂)=30 определить покрытия

с ценами S^a(f ₁) = 6, S^b(f ₁) = 9, S^a(f ₂) = 12, S^b(f ₁) = 16. Эти покрытия являются минимальными и им соответствуют минимальные ДНФ:

Четыре клетки карты могут объединяться, образуя 2-куб, содержащий две независимые координаты. Примеры образования 2-кубов приведены на рис. 2.7.

Карты построены для функций f ₁, f ₂ и f ₃, заданных в числовой форме:

а)	б)	в)

Рис. 2.7. Образование 2-кубов

На картах определены покрытия, состоящие из 2-кубов:

и имеющие цены  S^a(f ₁) = 6, S^b(f ₁) = 9, S^a(f ₂) = 4, S^b(f ₂) = 6, S^a(f ₃) = 4, S^b(f ₃) = 6.

Покрытия являются минимальными. Составленные по ним МДНФ имеют вид:

Объединение восьми клеток карты приводит к образованию 3-куба. Примеры образования 3-кубов для функций от четырех переменных  f ₁, f ₂, f ₃,  заданных в числовой форме:

приведены соответственно на рис. 2.8, а), б), в).

 

 

 

 

Рис. 2.8. Образование 3-кубов

 

Функциям f ₁, f ₂, f ₃ соответствуют покрытия с одинаковыми ценами S ^а = 2, S^b = 4.

 

⇐ Предыдущая45678910111213Следующая ⇒

Поделиться: