Математическая энциклопедия - булевых функций нормальные формы

формулы специального вида, реализующие булевы функции. Различают дизъюнктивные, нормальные формы (д. н. ф.; см. Булевых функций минимизация).и конъюнктивные нормальные формы (к. н. ф.). Произведение где при при , наз. элементарной конъюнкцией ранга , если все переменные в нем различны; 1 считается элементарной конъюнкцией нулевого ранга. Логическая сумма наз. элементарной дизъюнкцией ранга r, если все переменные в ней различны; 0 считается элементарной дизъюнкцией нулевого ранга.

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

По таблице, задающей булеву функцию легко строится совершенная д. н. ф. где и наборы таковы, что . Совершенная д. н. ф., реализующая булеву функцию f, строится однозначно. Аналогично определяется совершенная к. н. ф. Так как "почти все" булевы функции имеют число единичных наборов в пределах от до то асимптотич. сложность совершенной д. н. ф. для "почти всех" булевых функций равна Максимальная сложность совершенной д. н. ф. для функций от n переменных достигается для функций, равных 0, в одной точке. Она равна .

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