2-5. МЕТОД БЛЕКА—ПОРЕЦКОГО

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

Н требуется минимизировать эту функцию, то предварительно надо выписать ДСНФ этой функции, состоящую из 18 минитермов.

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

Лемма. Если в ДНФ для данной функции входят две конъюнкцни вида то имеет место равенство

где эквивалентная функции

Для доказательства нужно показать, что левая и правая части соотношения (2-13) принимают одинаковые значения на всех возможных наборах значений аргументов. Рассмотрим произвольный набор для которого

В силу эквивалентности между имеет место равенство, вытекающее из (2-13): . Это равенство тождественно, так как в дизъюнкции, стоящей справа, имеется единица.

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

На основании (2-13) имеем:

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

Так как на рассматриваемых наборах то одновременно выполняются следующие три равенства: Из двух последних равенств вытекает, что либо А, либо В, либо А и В одновременно обращаются в нуль, так как одновременно в нуль обратиться не могут.

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

Пример 2-10. Найти СДНФ для функции

Выпишем пары, удовлетворяющие лемме. Таких пар пять:

Построим пополненную ДНФ, не выписывая тех дополнительных членов, которые обращаются в нуль:

После элементарных поглощений получим:

В этой ДНФ есть только одна пара, удовлетворяющая условиям леммы Однако пополнение за счет этой пары не вносит ничего нового в ДНФ. Полученное выражение есть СДНФ.