РАСЧЕТНЫЙ МЕТОД

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

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

 

(7)

 

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

(8)

 

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

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

,

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

 

(9)

(10)

 

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

(11)

Оно содержит пять букв и требует три инвертора. Применив закон двойного отрицания и правило де-Моргана, выражение (11) можно преобразовать:

(12)

Последнее выражение содержит пять букв и требует два инвертора.

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

(13)

 

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

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

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

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

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

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