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

формулы специального вида, реализующие булевы функции. Различают дизъюнктивные, нормальные формы (д. н. ф.; см. Булевых функций минимизация).и конъюнктивные нормальные формы (к. н. ф.). Произведение [img: http://localhost:8080/file/010220-146.jpg] где [img: http://localhost:8080/file/010220-147.jpg] при [img: http://localhost:8080/file/010220-148.jpg] при [img: http://localhost:8080/file/010220-149.jpg], наз. элементарной конъюнкцией ранга [img: http://localhost:8080/file/010220-150.jpg], если все переменные в нем различны; 1 считается элементарной конъюнкцией нулевого ранга. Логическая сумма [img: http://localhost:8080/file/010220-151.jpg] наз. элементарной дизъюнкцией ранга r, если все переменные в ней различны; 0 считается элементарной дизъюнкцией нулевого ранга. Формула [img: http://localhost:8080/file/010220-152.jpg] где [img: http://localhost:8080/file/010220-153.jpg] - различные элементарные конъюнкции рангов [img: http://localhost:8080/file/010220-154.jpg] соответственно, наз. д. н. ф., а число [img: http://localhost:8080/file/010220-155.jpg] _ сложностью этой д. н. ф.; формула [img: http://localhost:8080/file/010220-156.jpg] где [img: http://localhost:8080/file/010220-157.jpg] - различные элементарные дизъюнкции рангов [img: http://localhost:8080/file/010220-158.jpg] соответственно, наз. к. н. ф., а число [img: http://localhost:8080/file/010220-159.jpg] -.сложностью этой к. н. ф. Всякая булева функция, отличная от тождественного нуля, может быть задана д. н. ф. и, вообще говоря, неоднозначно. Аналогичный факт имеет место для к. н. ф. п функций, не равных тождественно единице. По таблице, задающей булеву функцию [img: http://localhost:8080/file/010220-160.jpg] [img: http://localhost:8080/file/010220-161.jpg] легко строится совершенная д. н. ф. [img: http://localhost:8080/file/010220-162.jpg] где [img: http://localhost:8080/file/010220-163.jpg] [img: http://localhost:8080/file/010220-164.jpg] и наборы [img: http://localhost:8080/file/010220-165.jpg] таковы, что [img: http://localhost:8080/file/010220-166.jpg]. Совершенная д. н. ф., реализующая булеву функцию f, строится однозначно. Аналогично определяется совершенная к. н. ф. Так как "почти все" булевы функции имеют число единичных наборов в пределах от [img: http://localhost:8080/file/010220-167.jpg] до [img: http://localhost:8080/file/010220-168.jpg] то асимптотич. сложность совершенной д. н. ф. для "почти всех" булевых функций равна [img: http://localhost:8080/file/010220-169.jpg] Максимальная сложность совершенной д. н. ф. для функций от n переменных достигается для функций, равных 0, в одной точке. Она равна [img: http://localhost:8080/file/010220-170.jpg]. Основной задачей в теории Б. ф. н. ф. является задача минимизации булевых функций, т. е. построение для произвольной булевой функции к. н. ф. или д. н. ф. минимальной сложности -м инимальной к. Сокращенная д. н. ф. строится по булевой функции однозначно с помощью достаточно простых алгоритмов. Ее важнейшим свойством является то, что всякая минимальная д. н. ф. функции и хотя бы одна кратчайшая получаются из сокращенной д. н. ф. удалением нек-рых элементарных конъюнкций. Поэтому многие алгоритмы минимизации используют сокращенные д. н. ф. в качестве исходного задания булевой функции. В связи с этим большой интерес представляет определение сложности сокращенных д. н. ф. для "почти всех" функций и выяснение абсолютного максимума этой сложности. Если [img: http://localhost:8080/file/010220-171.jpg] - число элементарных конъюнкций в сокращенной д. н. ф. булевой функции [img: http://localhost:8080/file/010220-172.jpg] и [img: http://localhost:8080/file/010220-173.jpg] то имеют - место следующие оценки: [img: http://localhost:8080/file/010220-174.jpg] и для "почти всех" булевых функций [img: http://localhost:8080/file/010220-175.jpg] Из этих результатов и оценок сложности совершенной д. н. ф. видно, что сложность сокращенной д. н. ф. существенно больше сложности совершенной д. н. ф. как в "типичном", так и в "рекордном" случаях. В отличие от совершенной и сокращенной д. н. ф., у одной булевой функции может быть много тупиковых и минимальных д. н. ф. Пусть [img: http://localhost:8080/file/010220-176.jpg] - число тупиковых д. н. ф., [img: http://localhost:8080/file/010220-177.jpg] - число минимальных д. н. ф. булевой функции [img: http://localhost:8080/file/010220-179.jpg] [img: http://localhost:8080/file/010220-178.jpg] [img: http://localhost:8080/file/010220-180.jpg] Имеют место следующие оценки: [img: http://localhost:8080/file/010220-181.jpg] и для "почти всех" булевых функций [img: http://localhost:8080/file/010220-182.jpg] Верхняя оценка для [img: http://localhost:8080/file/010220-183.jpg] и оценка [img: http://localhost:8080/file/010220-184.jpg] для "почти всех" функции, отличных от тривиальных, пока (1977) не найдены. Большой интерес в задачах минимизации булевых функций представляют оценки сложности тупиковых д. н. ф. и минимальных д. н. - число элементарных конъюнкций в тупиковой д. н. ф. Тфункции [img: http://localhost:8080/file/010220-186.jpg] - число элементарных конъюнкций в кратчайших д., [img: http://localhost:8080/file/010220-188.jpg] Имеют место следующие оценки: [img: http://localhost:8080/file/010220-189.jpg] У "почти всех" булевых функций [img: http://localhost:8080/file/010220-190.jpg] для почти всех тупиковых д. н. ф. Т: [img: http://localhost:8080/file/010220-191.jpg] Для "почти всех" булевых функций [img: http://localhost:8080/file/010220-192.jpg] [img: http://localhost:8080/file/010220-193.jpg] Эти оценки показывают, что кратчайшие (а также минимальные) д. н. ф. составляют у "почти всех" булевых функций малую долю от числа тупиковых д. н. ф. Существуют также оценки относительной сложности тупиковых д. н. ф. и кратчайших д. н. ф. булевых функций. Пусть [img: http://localhost:8080/file/010220-194.jpg] - максимальное число элементарных конъюнкций'в тупиковой д. н. ф. функции [img: http://localhost:8080/file/010220-195.jpg]. Для "почти всех" булевых функций [img: http://localhost:8080/file/010220-196.jpg] Максимальное значение отношения [img: http://localhost:8080/file/010220-197.jpg] оценивается снизу величиной [img: http://localhost:8080/file/010220-198.jpg] при [img: http://localhost:8080/file/010220-199.jpg]. Получены также оценки для величины [img: http://localhost:8080/file/010220-200.jpg], наз. разбросом булевой функции [img: http://localhost:8080/file/010220-201.jpg]. Здесь [img: http://localhost:8080/file/010220-202.jpg] где [img: http://localhost:8080/file/010220-203.jpg] и [img: http://localhost:8080/file/010220-204.jpg] - произвольные тупиковые д. н. ф., реализующие [img: http://localhost:8080/file/010220-205.jpg], а [img: http://localhost:8080/file/010220-206.jpg] - число букв в тупиковой д. н. ф. Т. Построены примеры булевых функций, у к-рых [img: http://localhost:8080/file/010220-207.jpg]; установлено, однако, что для "почти всех" булевых функций [img: http://localhost:8080/file/010220-208.jpg] Приведенные выше оценки позволяют получить полное представление о тех трудностях, к-рые возникают при минимизации булевых функций по схеме: совершенная д. н. ф.- сокращенная д. н. ф.- тупиковая д. н. ф. - минимальная д. н. ф.