Метод Блека-Порецкого

Используется для получения сокращенной ДНФ из любой произвольной функции представления [5].

Идея построения сокращенной ДНФ по произвольной ДНФ вытекает из следующего определения: если в ДНФ для данной функции f(x₁ … x_n) входит две конъюнкции вида Ax_i и Bx_i, то имеет место равенство D=D\/AB, где D – ДНФ, эквивалентная функция f.

Алгоритм метода Блека-Порецкого.

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

2. Над полученными элементарными конъюнкциями ранга (n-1) провести операции склеивания и поглощения, образовать элементарные конъюнкции нижнего ранга и т.д.

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

4. Строится импликантная матрица и определяется максимальное покрытие.

Метод удобен при машинных способах минимизации.

Пример. Найти минимальную форму для заданной функции:

1. Матрица исходных данных 3. Матрица ранга (n-2)

0 0 0 1 2 0 2 1

0 0 1 0 2 0 2 1

0 0 1 1 2 0 1 2

1 0 0 1 2 0 1 2

1 0 1 0

1 0 1 1

2. Матрица ранга (n-1)*

0 0 2 1

2 0 0 1

0 0 1 2

2 0 1 0

2 0 1 1

1 0 2 1

1 0 1 2

4. Вычеркиваем одинаковые строки матрицы ранга (n-2) и получаем

A B C D

2 0 2 1

2 0 1 2

5.

где 0 – инверсия переменной, 1 – переменная, 2 – отсутствует переменная.