2.5. СТАНДАРТНЫЕ ФОРМЫ

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

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

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

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

Следующий пример иллюстрирует запись стандартных форм по заданной таблице соответствия

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

Соответствующая таблица истинности имеет вид

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