2.6. ПРЕОБРАЗОВАНИЕ И УПРОЩЕНИЕ ФОРМУЛ

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

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

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

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

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

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

Здесь дополнительный член поглотил , после чего удаляется как не влияющий на значение полученного выражения. В случаях, когда дополнительный член поглощает один из порождающих членов, его удалять нельзя и, следовательно, происходит замещение этого порождающего члена. Например:

Здесь дополнительный член поглощает минтерм и замещает породивший его минтерм . Заметим, что это выражение можно было бы упростить и без введения дополнительного члена с помощью поглощения и замещения: .

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

Например, , так как при этом дополнительный член обращается в тождественный нуль.

Хотя в рассмотренном примере получены минимальные формы, в общем случае процедура склеивания минтермов не гарантирует этого. Она обеспечивает лишь преобразование к сокращенной форме, минтермы которой называют простыми импликантами. Так как склеиваемые минтермы покрываются минтермом низшего ранга, сокращенная форма не содержит таких импликант, которые целиком покрываются какой-либо одной импликантой. В то же время среди простых импликант могут быть такие, которые покрываются совокупностями других импликант и, следовательно, являются избыточными. После удаления избыточных импликант приходим к тупиковым формам, среди которых находятся и минимальные формы. Следует заметить, что для данной функции существует единственная сокращенная форма, в то время как тупиковых и минимальных форм может быть несколько. Для минимизации булевых формул разработан ряд методов, среди которых наиболее известны алгоритм Квайна—Мак-Класки и графический метод, основанный на картах Карно.