Стандартные формы

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

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

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

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

У = `х<sub>1</sub>`х₂ х₃ + `х<sub>1</sub> х<sub>2</sub>`х₃ + х₁`х<sub>2</sub>`х₃ + х₁`х₂ х₃+ х₁х₂х₃=

= (х₁ + х₂ + х₃) (х₁ +`х<sub>2</sub> +`х₃)(`х<sub>1</sub> +`х₂ + х₃).

Если булева функция задана логической формулой, то ее можно привести к стандартной форме последовательностью эквивалентных преобразований, основанных на свойствах булевой алгебры. Сначала с помощью теорем де Моргана исходное выражение приводится к такому виду, чтобы знаки отрицания относились только к отдельным переменным. Затем на основе свойств дистрибутивности осуществляется преобразование к одной из форм – сумме произведений или произведению сумм. На заключительном этапе используются свойства х +`х=1 и х`х=0 для введения недостающих переменных в минтермы и макстермы, а также свойства идемпотентности х+х=х и хх=х для исключения повторяющихся слагаемых и сомножителей.