Метод минимизации Блейка-Порецкого

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

Лемма:

Если в ДНФ для данной функции f(x1,…,xn) входят две конъюнкции вида Ахi и B , то имеет место следующее равенство:

f=fvAB.

Доказательство леммы:

Запишем функцию f в следующем виде:

.

Из доказанной леммы вытекает метод построения сокращенной ДНФ. Этот метод заключается в том, что исходную функцию необходимо пополнить новыми членами вида АВ согласно лемме. После этого надо провести поглощения и вновь повторить пополнение ДНФ. Этот процесс необходимо производить до тех пор, пока будут возникать новые конъюнкции вида АВ. По окончании преобразований получаем сокращенную ДНФ. Процесс пополнения ДНФ осуществляется согласно лемме по формуле, которая называется операцией обобщенного склеивания:

Axi v B = Axi v B v AB.

В основе метода Квайна так же лежит операция склеивания, но другая, которая называется операцией неполного склеивания.

Операция неполного склеивания является частным случаем операцией обобщенного склеивания при А=В.

Axi v A = A v Axi v A .

Рассмотрим примеры:

1. Найти сокращенную ДНФ для функции трех аргументов:

.

При использовании метода Блейка-Порецкого применяется операция поглощения, которую можно представить в виде х v xy=x.

2. Пусть дана функция трех аргументов:

3.

.