МЕТРИЧЕСКИЕ СВОЙСТВА ДИЗЪЮНКТИВНЫХ НОРМАЛЬНЫХ ФОРМ

— свойства количественных проявлений дизъюнктивных нормальных форм (ДНФ), т. е. свойства разнообразных параметров, связывающих ДНФ и процедуры над ними с числами и отражающих измерение этих объектов. Интерес к М. с. д. н. ф. вызван тем, что членам ДНФ отвечают элементы схем и требуется оценивать затраты оборудования в схемах. Изучение М. с. д. н. ф., связанное с построением для данной булевой функции кратчайшей ДНФ, используют в автоматов теории, теории тестов, кодирования теории, комбинаторном анализе и программировании динамическом. Изучение М. с. д. н. ф. возникло под влиянием работ амер. математика К. Э. Шеннона (р. 1916) по синтезу переключательных схем и работ сов. математика С. В. Яблонского (р. 1924) по алгоритмическим трудностям синтеза схем. Специфика ДНФ как т. н. формул глубины два обусловила три плана, в крторых рассматривают М. с. д. н. ф. Во-первых, при схемных реализациях ДНФ число ступеней в схемах равно двум, что важно для надежности и быстродействия схем. С этим связана роль ДНФ в структурной теории автоматов и широкое применение их при синтезе матем. машин. В этом плане интересны длины различных видов ДНФ.

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

ДНФ для играющей роль экстремума локального. Часто одни упрощения исключают другие, и в зависимости от выбора их приходят к различным дизъюнктивным нормальным формам тупиковым. Для ДНФ характерна ярко выраженная полиэкстремальность, когда глобальный экстремум находится среди большого числа локальных экстремумов. Характерно также наличие у любой ф-ции ДНФ, называемой сокращенной. В ней отражается вся нартина минимизации: и экстремумы, и, в известной степени, алгоритмы минимизации, так что М. с. д. н. ф. отражают измерение и полученного решения, и алгоритмов получения его. Хотя при этом делаются различные допущения об алгоритмах, имеющиеся результаты нетривиальны и полезны. Наряду с длинами ДНФ здесь интересны абсолютные и относительные к-ва различных видов ДНФ, относительные длины ДНФ, протяженность, совмещение на одной ф-ции различных свойств, связность и др.

Геом. трактовка ДНФ придает им наглядность, проясняет их комбинаторную природу, облегчаетностановку и поиски решения задач. В этом случае ДНФ проявляются как комплексы, составленные из граней -мерного единичного куба и через переход к абстрактным комплексам имеют связи с другими комбинаторными задачами. Напр., изучение типичных ситуаций для ДНФ оказало влияние на исследование т. н. статистических, или частотных, свойств поведения автоматов, при котором имеют дело с одномерными комплексами в виде диаграмм переходов. В этом плане интересны некоторые общие черты числовых оценок ДНФ, а также принципы получения этих оценок.

К решению задачи минимизации ДНФ может быть несколько подходов, требующих конечного числа шагов. При этом возникает ряд серьезных препятствий. Принципиальное значение совокупности М. с. д. н. ф. состоит в том, что она при тех или иных ограничениях характеризует переборы; прикладное значение — в том, что знание препятствий в общем случае дает ориентиры для использования возможностей в конкретных ситуациях.

Рассмотрение М. с. д. н. ф. и соответствующих числовых параметров приурочено ко мн-ву всех булевых ф-ций от переменных. Если такого рода параметр, то через обозначается макс. значение его, т. е. Выделение типичных ситуаций производится в форме высказывания, что для почти всех ф-ций под этим подразумевают, что часть тех ф-ций из которые удовлетворяют указанным оценкам, стремится к 1 при п . Рассмотрение ограничивается оценками макс. значений и оценками значений для почти всех ф-ций. Осн. внимание уделяется тому, как изменяются эти величины с ростом . В рассмотренных ниже оценках заметно различие между максимальными и типичными значениями параметров.

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

Макс. значение длины совершенной ДНФ для ф-ции от n переменных равно атипичное значение Пусть длина сокращенной ДНФ. Оценки макс. значения с для почти всех ф-ций где при . В обоих случаях длина сокращенной ДНФ во много раз превышает длину совершенной ДНФ, и свое название, которое ей дано намного раньше, чем получены эти оценки, сокращенная ДНФ оправдывает лишь для небольшого числа ф-ций.

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

Тупиковые ДНФ булевой ф-ции могут быть существенно длиннее кратчайшей ДНФ. Относительной длиной тупиковой ДНФ наз. отношение ее длины к длине кратчайшей ДНФ. Макс. относительная длина тупиковых ДНФ данной функции разбросом ф-ции обозначают ее через Разброс длин в известной мере характеризует актуальность минимизации ф-ции Макс. значение разброса длин гдее при . Для почти всех ф-ций разброс существенно меньше, но тоже увеличивается с ростом , и для него известны оценки п. Относительные длины почти всех тупиковых ДНФ ф-ций ведут себя аналогично: у «самых плохих» ф-ций они тоже равны а у почти всех ф-ций они лежат между . Это означает, что т. н.

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

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

Более того, у почти всех ф-ций так ведут себя длины почти всех тупиковых ДНФ. Что касается , то макс. значение ее Для почти всех ф-ций

т. е. почти всегда длина на порядок меньше длины совершенной ДНФ. Это означает, что минимизация длины представляет интерес. Вместе с тем достаточно велика, и это свидетельствует о том, что т. н. тривиальный подход к минимизации (перебор всех ДНФ длины 1, 2, 3 до тех пор, пока не встретится ДНФ, реализующая данную ф-цию) потребует просмотра ДНФ с достаточно большой длиной, т. е. весьма большого перебора. Так что задача минимизации нетривиальна и с этой стороны. Наряду с оценками найдены алгоритмы, дающие для почти всех ф-ций ДНФ такой длины. В частности, таков аналог градиентного метода.

М. с. д. н. ф. в связи с локальным подходом рассмотрены в трех направлениях. Как известно, алгоритм локальный А строит набор упрощений сокращенной ДНФ и приводит к ДНФ получаемой на этими упрощениями; от ДНФ не требуется, чтобы она была даже тупиковой, но требуется, чтобы для произвольной ф-ции она была единственной. Алгоритм А имеет параметры — индекс и величину памяти v? Он состоит в последовательном сборе и переработке информации на ограниченных частях ДНФ представляющих собой окрестности членов ДНФ индекс задает радиус окрестностей. Идея локальности состоит в ограничении трудоемкости алгоритма А посредством ограничения радиуса окрестностей. Протяженностью булевой ф-ции миним. значение радиуса, при котором окрестность любого члена ДНФ составляет уже всю ДНФ Разность длин ДНФ результативностью локального алгоритма А на и обозначается через Циклом наз. булева ф-ция сокращенной ДНФ которой отвечает в комплекс из ребер, причем каждая вершина покрыта двумя ребрами, и комплекс связен. Упомянутые три направления таковы. Во-первых, прямым построением циклов получено макс. значение протяженности для почти всех булевых ф-ций

Одна из осн. теорем теории локальных алгоритмов — теорема невозможности упрощения цикла при с учетом этих оценок трактуется как свидетельство трудности минимизации ДНФ.

У почти всех ф-ций число т. н. ядровых членов в сокращенной ДНФ и число регулярных вершин невелико. Это означает, что характер перекрытия граней в комплексе для типичных ф-ций довольно сложен, а также, что результативность локальных алгоритмов при для типичных ф-ций мала. Таковы все применяемые локальные алгоритмы — Квайна метод минимизации построение ДНФ «сумма тупиковых» Вместе с тем имеются примеры ф-ций, на которых результативность высока. При оценке ее следует также иметь в виду усложнение сокращенной ДНФ по сравнению с совершенной.

Наконец, построены т. н. плотные булевы ф-ции на которых локальные алгоритмы при имеют трудоемкость порядка которая сравнима с макс. значением числа тупиковых ДНФ для ф-ций от переменных. Это означает, что упомянутая выше идея локальности нуждается в уточнении, т. к. на некоторых ф-циях уже при нет удовлетворительного ограничения трудоемкости. У плотных ф-ций малая протяженность совмещается с выраженностью трудностей минимизации при относительная длина почти всех тупиковых ДНФ все члены сокращенной ДНФ имеют одинаковое число букв. Таковы осн. задачи, приведшие к изучению М. с. д. н. ф.

Для почти всех ф-ций и у почти всех ф-ций почти все грани, составляющие сокращенную ДНФ, имеют размерность, существенно меньшую и равную примерно Связность комплексов, отвечающих сокращенным ДНФ типичных ф-ций, такова, что эти комплексы сосредоточены почти целиком в одной компоненте связности, а прочих компонент немного и они нульмерны. Кратчайшая ДНФ может не быть минимальной по числу букв и наоборот. Максимально возможное отношение их длин а для типичных ф-ций это отношение

Следует также упомянуть минимизацию при ограничении по размерности. Для произвольных комплексов, составленных только из

номерных граней, и для отвечающих им ДНФ имеется алгоритм, основанный на построении макс. паросочетания в графах, который дает минимальную ДНФ для случая переменных при памяти порядка и числе шагов порядка Какое-либо развитие этого подхода для больших значений размерности неизвестно.

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

Отыскание типичных значений сочетает аналогичное конструирование с подсчетами средних, дисперсий и применением неравенства Чебышева. Конструкция расчленяет задачу на определенные этапы, на которых вводятся вспомогательные параметры и производятся для них названные подсчеты, и связывает вспомогательные параметры и оценки для них с осн. оцениваемым параметром. С нескольких нетривиальных конструкций в и даваемых ими различий макс. и типичных значений началось широкое изучение типичных ситуаций для различных видов комплексов.

Лит.: Яблонский С. В. Функциональные построения в -значной логике. «Труды Математического института им. В. А. Стеклова АН СССР», 1958, т. 51; Журавлев Ю.И. Теоретико-множественные методы в алгебре логики. «Проблемы кибернетики», 1962, в. 8; Васильев Ю. Л. О сравнении сложности тупиковых и минимальных дизъюнктивных нормальных форм. «Проблемы кибернетики», 1963, в. 10: Васильев Ю. Л. Трудности минимизации булевых функций на основе универсальных подходов. «Доклады АН СССР», 1966, т. 171, Ke 1; Глаголев В. В. Некоторые оценки дизъюнктивных нормальных форм функций алгебры логики. «Проблемы кибернетики», 1967, в. 19; Глаголев В. В. О длине тупиковой дизъюнктивной нормальной формы. «Математические заметки», 1967, т. 2, в. 6; Сапоженко А. А. О наибольшей длине тупиковой дизъюнктивной нормальной формы у почти всех булевых функций. «Математические заметки», 1968, т. 4, в. 6; Бвдокимов А. А. О максимальной длине цепи в единичном n-мерном кубе. «Математические заметки», 1969, т. 6, в. 3. Ю. Л. Васильев.