БУЛЕВЫХ ФУНКЦИЙ НОРМАЛЬНЫЕ ФОРМЫ

БУЛЕВЫХ ФУНКЦИЙ НОРМАЛЬНЫЕ ФОРМЫ

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

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

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

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

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


то имеют - место следующие оценки:


и для "почти всех" булевых функций


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


Имеют место следующие оценки:


и для "почти всех" булевых функций


Верхняя оценка для и оценка для "почти всех" функции, отличных от тривиальных, пока (1977) не найдены. Большой интерес в задачах минимизации булевых функций представляют оценки сложности тупиковых д. н. ф. и минимальных д. н. <ф. Пусть - число элементарных конъюнкций в тупиковой д. н. ф. Тфункции - число элементарных конъюнкций в кратчайших д. <н. <ф. функции ,


Имеют место следующие оценки:


У "почти всех" булевых функций для почти всех тупиковых д. н. ф. Т:


Для "почти всех" булевых функций


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


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


где и - произвольные тупиковые д. н. ф., реализующие , а - число букв в тупиковой д. н. ф. Т. Построены примеры булевых функций, у к-рых ; установлено, однако, что для "почти всех" булевых функций


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

Лит.:[1] Васильев Ю. Л., "Проблемы кибернетики", 1963, в. 10, с. 5-61; [2] Глаголев В. В., "Проблемы кибернетики", 1967, в. 19, с. 75-94; [3] Коршунов А. Д., "Кибернетика", 1969, т. 6, с. 1-8; [4] Сапоженко А. А., "Матем. заметки", 1968, т. 4, № 6, с. 649-58. Ю. И. Журавлев.


Математическая энциклопедия. — М.: Советская энциклопедия. . 1977—1985.

Игры ⚽ Нужно решить контрольную?

Полезное


Смотреть что такое "БУЛЕВЫХ ФУНКЦИЙ НОРМАЛЬНЫЕ ФОРМЫ" в других словарях:

  • БУЛЕВЫХ ФУНКЦИИ МИНИМИЗАЦИЯ — представление булевых функций нормальными формами (см. Булевых функций нормальные формы). простейшими относительно нек рой меры сложности. Обычно под сложностью нормальной формы понимается число букв в ней. В этом случае простейшая форма наз.… …   Математическая энциклопедия

  • БУЛЕВЫХ ФУНКЦИИ МЕТРИЧЕСКАЯ ТЕОРИЯ — направление, связанное с изучением числовых характеристик и метрич. свойств булевых функций. Основные разделы этой теории посвящены исследованию свойств почти всех булевых функций (см. Булевых функций минимизация), свойств совокупности всех… …   Математическая энциклопедия

  • ДИСКРЕТНОЕ ПРОГРАММИРОВАНИЕ — область математики, занимающаяся исследованием и решением экстремальных задач на конечных множествах. Пусть М={а 1, а 2, ..., а п}и f числовая функция, определенная на элементах множества М. Требуется найти элемент на к ром достигается абсолютный …   Математическая энциклопедия

  • АЛГОРИТМ ЛОКАЛЬНЫЙ — алгоритм, устанавливающий свойства элементов множества и использующий на каждом шаге при этом только информацию об окрестности элемента. В терминах А. л. естественно формулируются и решаются задачи о существовании или несуществовании эффективных… …   Математическая энциклопедия

  • БУЛЕВА ФУНКЦИЯ — функция алгебры логики, функция, аргументы к рой, равно как и сама функция, принимают значения из двухэлементного множества (обычно {0,1}). Б. ф. являются одним из основных объектов дискретной математики, в особенности тех ее разделов, к рые… …   Математическая энциклопедия

  • СОКРАЩЕННАЯ НОРМАЛЬНАЯ ФОРМА — булевой функции дизъюнктивная нормальная форма (д. н. ф.), представляющая собой дизъюнкцию всех простых импликант данной функции. Конъюнкция наз. импликантой булевой функции f, если справедливо соотношение Импликанта наз. простой, если после… …   Математическая энциклопедия

  • ПОКРЫТИЯ И УПАКОВКИ — комбинаторные конфигурации, связанные с многозначным отображением одного множества на другое. Пусть заданы множества Vи Еи многозначное отображение Г множества Ена множество V. Пусть Г(е). образ элемента при отображении Г и для любого пусть Г(С) …   Математическая энциклопедия

  • СОВЕРШЕННАЯ НОРМАЛЬНАЯ ФОРМА — совершенная дизъюнктивная или совершенная конъюнктивная нормальная форма (см. Булевых функций нормальные формы) …   Математическая энциклопедия

  • АЛГЕБРА ЛОГИКИ —         система алгебраич. методов решения логич. задач, а также совокупность задач, решаемых такими методами. А. л. в узком смысле слова алгебраич. (табличное, матричное) построение классич. логики высказываний, в котором рассматриваются… …   Философская энциклопедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»