При ответе проектирования и задач анализа логических схем главными параметрами их оптимальности, в большинстве случаев, являются минимумы общего количества функциональных либо релейных элементов, входящих в них, и общего количества соединений в схеме. Эта минимизация упрощает последующую физическую реализацию схем, повышает их надежность и одновременно с этим – сокращает габариты, материалоемкость, себестоимость.
Разглядим построение булевых функций, соответствующих логических схемам с данными особенностями.
Определение: Минимальной ДНФ (МДНФ) функции алгебры логики f(хn) именуется её ДНФ, содержащая в собственной формуле предельное количество знаков переменных.
Подобно вводятся понятия минимальных КНФ (МКНФ), минимальных ВНФ (МВНФ), минимальных ШНФ (МШНФ).
Каждую из идеальных обычных форм произвольной булевой функции f (хn)(СДНФ, СКНФ, СВНФ, СШНФ) возможно представить в виде:
f = F(j(x1a11 ,…, xn a1n) , …,j (x1ak1,…, xn akn)),
где F — внешняя функция, j (x1ai1 ,…, xnain) — внутренняя функция, которая при подстановке переменных (x1ai1, …, xnain)есть конституентой нуля или единицы на одном из комплектов значений переменных `хn , т.е. принимает на нем значение нуль (единица) , а на всех других комплектах — противоположное значение. В СВНФ и СШНФ внешними являются функции O¯ =U и O | = .
Определение. Комплекты переменных (x1ai1,…,xnain), входящие во внутренние функции jв идеальных обычных формах, назовем элементарными комплектами.
Множество элементарных комплектов в разглядываемой идеальной форме булевой функции будем обозначать через {N} = {N1, … , Nk}, где k — число нулей (единиц) в векторе значений исходной функции, равное числу внутренних функций jв форме. Как отмечалось ранее, в идеальных обычных формах употребляются лишь пороговые функции. СДНФ и СВНФ строятся по единичным значениям функции, СКНФ и СШНФ — по нулевым.
В ходе минимизации производится параллельное сокращение:
а) чисел переменных во внутренних функциях j(x1ai1 ,…, xnain),
б) числа k самих внутренних функций j(x1ai1 ,…, xnain) .
Для характеристики данных сокращений вводятся вспомогательные понятия несложных комплектов, сокращенных и тупиковых обычных форм.
Определение. Комплект переменных (x1ai1,…, xnain), входящий во внутреннюю функцию jединичной (нулевой) обычной формы булевой функции f (хn ), именуют ее несложным комплектом, в случае если при удалении из (x1ai1 , … , xnain) любой переменной xaiк новая функция j(x1ai1, … ,xk-1ai(к-1),xk+1ai(к+1), … ,xnain) приобретает новые единичные (нулевые) значения в векторе истинности, которых нет у исходной f (х n).
Множество несложных комплектов в обычных формах будем обозначать через {P} = {P1,…,Ps}, где s — неспециализированное число таких комплектов.
Пример 1. Разглядим функцию f(x,y,z)= (00101100). Нужно узнать, какие конкретно из её элементарных комплектов являются несложными.
Ответ. СДНФ имеет форму: f =`x y z U x`y`z U x`y z.
Элементарные комплекты будут следующими:
N1=(x , y,`z), N2= (x,`y,`z), N3=(x,`y, z).
Разглядим элементарный комплект N1=(x, y,`z)и попытаемся удалить из него поочередно каждую из его переменных.
а) Удаление`x ведет к тому, что новая сокращенная конъюнкция у`z будет иметь кроме единицы на комплекте (0, 1, 0)дополнительное значение 1 на комплекте (1, 1, 0). Но f (1, 1, 0) = 0, исходя из этого переменную
из комплекта удалять запрещено.
б) Удаление у ведет к тому, что новая конъюнкция `х`z будет иметь дополнительное значение 1 на комплекте (0, 0, 0), но f(0, 0, 0) = 0, исходя из этого переменную у кроме этого удалять запрещено.
в) Подобно удаление`z ведет к тому, что новая конъюнкция будет иметь значение 1 на комплекте (0, 1, 1). Потому, что f (0, 1, 1) = 0, то эту переменную нельзя удалять из комплекта.
Из а), б), в) направляться, что элементарный комплект N1= (x, y,`z)есть несложным комплектом. Подобная проверка элементарных комплектов N2= (x,` y,`z ) и N3= (x,`y, z) говорит о том, что у них возможно удалить третью переменную. Наряду с этим конъюнкции, соответствующие новым комплектам N¢2= N¢3= (x,`y),примут дополнительные единичные значения на тех комплектах ((1,0,1) и (1,0,0)), где функция равна 1. Из этого следует, что элементарные комплекты N2=(x,какое количество y,`z) и N3= (x,`y, z) не являются несложными комплектами в СДНФ функции f.
Разумеется, что у любой минимальной обычной формы внутренние функции должны содержать лишь простые комплекты переменных. Потому, что обратное условие не есть достаточным, то вводится понятие сокращенных обычных форм.
Определение. Сокращенной дизъюнктивной, (шефферовой, конъюнктивной, веббовой) обычной формой СкДНФ (СкШНФ, СкКНФ, СкВНФ) функции f(`хn ) именуют соответствующую обычную форму, у которой во всех внутренних функциях j подставлены лишь простые комплекты переменных.
Суть сокращенных форм в том, что у них уже нельзя удалить переменные во внутренних функциях без нарушения правильности представления исходной функции.
Определение. Тупиковой дизъюнктивной, (шефферовой, конъюнктивной, веббовой) обычной формой ТДНФ (ТШНФ, ТКНФ, ТВНФ) функции f(хn) именуют соответствующую обычную форму, у которой нельзя удалить никого из внутренних функций j, входящих во внешнюю функцию F.
Так как внутренние функции j являются доводами внешней функции F, то понятие тупиковой обычной формы имеет суть, сходный с сокращенной, с той только отличием, что минимальным есть комплект доводов внешней функции, а не внутренних.
Разумеется, минимальная форма любой функции есть одновременно и тупиковой. На этом свойстве основаны методы минимизации обычных форм. Сущность их содержится в том, что сначала строится множество всех тупиковых обычных форм функции {Т}, а после этого из них выбирается минимальная форма (обычно их не редкость пара).
Урок 5. Минимизация логических функций. Математическая логика. Видеоуроки по информатике
