Расчётный метод минимизации логических функций

Пусть нам требуется минимизировать ФАЛ, заданную выражением (1).

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

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

Дальнейшее склеивание на может быть выполнено, так как все члены выражения (8) являются изолированными.

2 этап. Необходимо выявить лишние импликанты в выражении (8). Это можно сделать двумя способами. При первом способе развертывают одну импликанту до конституент единицы, а затем смотрят, не поглощаются ли эти конституенты осталь­ными импликантами. Первая импликанта развертывается до суммы

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

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

ни одной импликантой, следовательно, импликанта не является лишней. Выявлены две лишний импликанты, но это не значит, что обе они могут быть отброше­ны, так как каждая из них проверялась при вхождении второй в выражение (8). Сле­довательно, отбросить наверняка можно одну из них, а затем снова произвести про­верку возможности отбросить и другую. Если отбросить импликанту , то про­верка показывает, что импликанта не будет лишней, а если отбросить  то не будет лишней. Итак, можно отбросить одну из выявленных двух импликант и в результате получаются две ТДНФ одинаковой сложности, содержащих по шесть букв:

3 этап. Выражение (9) можно записать в виде

Аналогично можно упростить и выражение (10):

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

Применим это правило к выражению (8).

Импликанта принимает значение 1 на наборе . Подставив этот набор в оставшуюся сумму

 , получим , что говорит о том, что первая импликанта не является лишней. Импликанта    принимает значение 1 на наборе  . Подставив этот набор в сумму ,   получим

 , что говорит о том, что импликанта лишняя.

Оставим пока эту импликанту и продолжим анализ других импликант. Импли­канта принимает значение 1 на наборе . Подставив этот набор в

сумму , получим , что говорит о том, что импликанта лишняя.

Оставляем и ее и продолжаем процедуру. Импликанта принимает значение 1 на наборе . Подставив этот набор в сумму

Получаем , что говорит о том, что импликанта не является лишней.

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

Можно сделать вывод, что даже для этого простого примера пришлось выпол­нять достаточно много однообразных действий, требующих внимания и времени, поэтому расчетный метод минимизации ФАЛ применяется в основном для ФАЛ, зави­сящих от двух или трех переменных.