Булевых Функций Нормальные Формы

Формулы специального вида, реализующие булевы функции. Различают дизъюнктивные, нормальные формы (д. н. ф.; см. Булевых функций минимизация).и конъюнктивные нормальные формы (к. н. ф.). Произведение где при при , наз. элементарной конъюнкцией ранга , если все переменные в нем различны; 1 считается элементарной конъюнкцией нулевого ранга. Логическая сумма наз. элементарной дизъюнкцией ранга r, если все переменные в ней различны; 0 считается элементарной дизъюнкцией нулевого ранга. Формула где — различные элементарные конъюнкции рангов соответственно, наз. д. н. ф., а число _ сложностью этой д. н. ф.; формула где — различные элементарные дизъюнкции рангов соответственно, наз. к. н. ф., а число — .сложностью этой к. н. ф. Всякая булева функция, отличная от тождественного нуля, может быть задана д. н. ф. и, вообще говоря, неоднозначно. Аналогичный факт имеет место для к. н. ф. п функций, не равных тождественно единице. По таблице, задающей булеву функцию легко строится совершенная д. н. ф. где и наборы таковы, что . Совершенная д. н. ф., реализующая булеву функцию f, строится однозначно. Аналогично определяется совершенная к. н. ф. Так как "почти все" булевы функции имеют число единичных наборов в пределах от до то асимптотич. сложность совершенной д. н. ф. для "почти всех" булевых функций равна Максимальная сложность совершенной д. н. ф. для функций от n переменных достигается для функций, равных 0, в одной точке. Она равна . Основной задачей в теории Б. ф. н. ф. является задача минимизации булевых функций, т. е. построение для произвольной булевой функции к. н. ф. или д. н. ф. минимальной сложности -м инимальной к. Верхняя оценка для и оценка для "почти всех" функции, отличных от тривиальных, пока (1977) не найдены. Большой интерес в задачах минимизации булевых функций представляют оценки сложности тупиковых д. н. ф. и минимальных д. н.