Нормальные формы логических функций

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

Табличное задание закона функционирования некоторого устройства является наиболее наглядным и универсальным средством описания его работы.

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

Пусть, например, требуется синтезировать цифровое устройство, реализующее сложение двух двоичных цифр полусумматор . 1-й этап синтеза - даётся словесное описание полусумматора и принципа его работы. Он должен анализировать все комбинации входных сигналов т. е. двоичных цифр 00, 01, 10, 11 и в соответствии с ними формировать на выходе двухразрядные суммы.

В первом разряде результата формируется цифра переноса, а во втором - цифра многоразрядной суммы. Следовательно, синтезируемый полусумматор должен иметь два входа n 2 и два выхода. Далее от нестрогого словесного описания переходим к строгому формальному описанию работы полусумматора на табличном языке. Таблица истинности см. табл. 1.1 в общем случае при n входах имеет 2 в степени n комбинаций значений аргументов. Таблица 1.1 Таблица истинности полусумматора. 1-я цифра слагаемое Х1 0 0 1 1 2-я цифра слагаемое Х2 0 1 0 1 Цифра переноса р 0 0 0 1 Цифра суммы s 0 1 1 0 2-й этап синтеза - для того чтобы показать методику перехода от таблицы истинности к аналитическому выражению, рассмотрим некоторую обобщённую таблицу истинности двух аргументов f X1,X2 см. табл. 1.2 . Ограничение на число аргументов не является в данном случае существенным, но значительно упрощает все рассуждения. Таблица 1.2 Обобщённая таблица истинности функции двух аргументов. 1-й логический аргумент Х1 0 0 1 1 2-й логический аргумент Х2 0 1 0 1 Логическая функция f X1,X2 f0 f1 f2 f3 Здесь f0 f 0,0 f1 0,1 f2 1,0 f3 1,1 - конкретные реализации функции f X1,X2 при определённых частных значениях аргументов X1 и X2. Они также являются двоичными переменными.

Десятичные индексы при их символах числено равны тем двоичным числам, которые образуются соответствующими частными значениями аргументов.

Кроме того, каждый десятичный индекс можно трактовать как номер некоторого столбца в Таблице 1.2, изменяющийся в пределах от 0 до 2n -1, так как обычно значения аргументов в таблице записываются таким образом, чтобы получающееся из них по вертикали двоичное число было равно номеру столбца.

Исходя из вышеизложенного, уже можно перейти от табличной записи логической функции f X1,X2 к аналитической f X1,X2 f0 при, х1 0, х2 0 f1 при, х1 0, х2 1 1.1 f2 при, х1 1, х2 0 f3 при, х1 1, х2 1 Такая запись несколько удобнее и компактнее таблицы, однако она всё-таки громоздка и плохо обозрима особенно в случае большого числа аргументов. Но от неё можно перейти к записи другого вида, более удобной и компактной f x1,x2 x1x2f0 x1x2f1 x1x2f2 x1x2f3 1.2 Правило построения каждого члена в этом предложении несложно производится логическое умножение элементов каждого столбца табл.1.2, причём вместо 1 берётся символ соответствующего аргумента, а вместо 0 - его отрицание.

Равносильность соотношений 1.1 и 1.2 простой подстановкой в выражение 1.2 всех возможных комбинаций значений аргумента xi. Обобщив вышеизложенное можно сформулировать правило получения аналитической записи логической функции для некоторого комбинационного узла - для того чтобы получить аналитическое выражение функции, заданной таблично, нужно составить сумму конституент см. ниже единицы для тех наборов значений входных двоичных переменных, для которых реализации функции fi равны 1, причём символ любой переменной в некоторой конституенте берётся со знаком отрицания, если конкретное значение переменной xi в рассматриваемом наборе имеет значение 0 . Поскольку логическая сумма всех элементарных произведений наивысшего ранга n обязательно равна 1, какой бы набор значений входных переменных ни рассматривался, то эти произведения вполне логично называть конституентами составляющими единицы.

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

Таким образом это правило определяет канонический вид любой логической функции.

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

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

Таким образом сформулируем второе правило - для того чтобы получить аналитическое выражение функции, заданной таблично, в совершенной конъюктивной нормальной форме, нужно составить логическое произведение конституент нуля для тех наборов значений, входных двоичных переменных, для которых реализация функции fi равна 0, причём символ любой переменной в некоторой конституенте берётся со знаком отрицания, если её конкретное значение xi в рассматриваемом наборе равно 1 . В общем случае переход к совершенной нормальной форме производится за три шага . 1-й шаг - с помощью многократного применения законов инверсии снимаются общие и групповые отрицания так, чтобы отрицания оставались только у одиночных переменных . 2-й шаг - с помощью распределительных законов производится переход к одной из нормальных форм функции. 3-й шаг - производится преобразование членов ДНФ или КНФ в соответствующие конституенты с помощью правила развёртывания. Пользуясь сформулированными правилами и таблицей 1.1 для полусумматора записываем p x1,x2 x1x2 s x1,x2 x1x2 x1x2 СДНФ 1.3 p x1,x2 x1 x2 x1 x2 x1 x2 s x1,x2 x1 x2 x1 x2 СКНФ 1.4 3-й этап синтеза - анализ и оптимизация минимизация логических функций являются весьма важными компонентами синтеза цифровых автоматов без памяти.

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

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