Введение к работе
Актуальность проблемы. Одним из наиболее.важных даскрег-х модельных объектов теории систем переработки информации, шедшим широкое применение во многих областях науки и техники ких, как конструирование вычислительной техники, исследова-е операций, математическое моделирование в медицине, геоло-и, биологии и др. являются дизъюнктивные нормальные формы .н.ф.) булевых функций.
Исследование д.н.ф. исторически началось в рамках матема-ческой логики. Однако истинной датой рбадения теории д.н.ф. эдует считать начало второй половины XX века, когда появле-э электронной вычислительной техники и революционных работ Леннона выдвинуло д.н.ф. на место одного из основных дискрег-к модельных объектов теории управляющих систем. Особенно бур-з развитие теория д.н.ф. получила в 50-60-х гг. и отчасти в зале 70-х годов. Решающий вклад в становление и развитие твій д.н.ф. внесен советскими математиками С.В.Яблонским, Ю.И. равлевым, А.А.Сапоженко, В.В.Глаголевым, Ю.Л.Васильевым и др. Однако тонкие математические результаты этих лет в весьма юй степени прямо использовались при решении конкретных при-эдных экстремальных задач в основном из-за того, что исследу-ій модельный объект - дизъюнктивные нормальные формы - отли-юь большим числом весьма специфических особенностей, прису-с только этому классу моделей, не получил сколько-нибудь ши-юго распространения в тех прикладных областях, где дейсгви-иьно это было бы необходимо. Специфичность модели д.н.ф. по-збовала преодоления существенных трудностей, присущих не ис-щой содержательной задаче, а возникающих ввиду необходимо-і трансляции ее на алгебраически "бедный" и специфичный язык і.ф.
Тем не менее в настоящее время все практические методы эектирования, синтеза и диагностики схем кодирования и пере-5отки информации на ШС и СБИС, основываются на предваритель-І реализации логических функций в .виде достаточно простых і.ф. Большой, практически необозримый, круг даскретных экстре- чьных задач, задач распознавания образов и т.д. сводится к пению систем нелинейных булевых уравнений. На решение именно к задач и ориентированы основные применения представления
булевых функций в виде д.н.ф.
Таким образом, "кризисное" состояние в теории д.н.ф., о< ловленное недостаточной адекватностью выбранной модели исхода содержательной задаче, может быть преодолено лишь путем отка: от привычной математической модели и перехода к существенно і вой, более адекватной исходной содержательной задаче, модели. избегая при этом существенного усложнения математического аш рата.
Среди требований, предъявляемых к такой модели следует ; делить в качестве основных два следующих:
новая модель должна естественным образом обобщать мода д.н.ф. и допускать.использование алгбераически более "богаты: чем булева алгебра средств, что позволило бы преодолеть неси лансированность в теории д.н.ф. в сторону "геометрических" мі тодов;
переход к новой модели должен сопровождаться существе] ным, принципиально недостижимым в рамках теории д.н.ф., прод жением в решении задачи минимизации булевых функций ив ее ц ложениях.
Поэтому, проблема перехода к новой математической модел удовлетворяющей вышеизложенным требованиям и более адекватно, исходной содержательной задаче, с последующим построением ос: математической теории предложенной модели является актуальное
Цель работы;
предложить естественное обобщение модели дизъюнктивны нормальных форм булевых функций, адекватное задаче решения с: тем нелинейных булевых уравнений;
построить основы математической теории новой модели;
исследовать задачу оптимальной реализации булевых фун ций б рамках новой модели;
разработать методы представления булевых функций новы модельными объектами, основанные на развитой математической рии и ориентированные на решение прикладных задач.
Научная новизна. В качестве естественного обобщения мод дизъюнктивных нормальных форм, адекватного проблеме решения тем нелинейных булевых уравнений, предложена и впервые иссле вана дискретная математическая модель дизъюнктивных нормальн форм над линейными булевыми функциями .'Построена математичес теория представления булевых функций посредством д.н.ф, над
_ 5 -
(ейными функциями.
В рамках, этой теории получены следующие основные результата, принципиально недостижимые в модели обычных д.н.ф.:
- - исследованы важнейшие структурные и метрические характеристики, связанные с трудоемкостью оптимальной реализации буле-щ функций в классе д.н.ф. над линейными функциями;
исследована задача оптимальной реализации для булевых ункций из, некоторых важнейших классов;
получено аналитическое решение задачи оптимального пред-тавления квадратичных булевнх функций;
разработаны методы реализации булевых функций, ориенти- ' >ванные на решение нелинейных систем булевых уравнений;
на основе новой модели получены новые возможности выде-!ния эмпирических закономерностей в задачах распознавания;
разработанные методы применены для решения конкретных жкладных задач.
Все результаты работы являются новыми и получены автором :ервые.
Практическая ценность. Разработанные в работе методы пред-авляют собой новый эффективный и удобный инструмент в научных следованиях, связанных с применением вычислительной техники и скретного математического моделирования в прикладных задачах уки и техники. С помощью этих методов решены прикладные зада-классификации: и распознавания в области молекулярной биоло-и.
Применение предложенной в работе новой дискретной матема-їеской модели позволяет существенно расширить область и раз-рность большого класса прикладных задач, поддающихся практичному решению с помощью дискретного моделирования.
Полученные в работе математические результаты закладывают говы нового перспективного научного направления в исследова-[ и применении дискретных математических моделей, связанных представлением булевых функций.
Апробация работы и публикации. Представленная работа явля-;я частью исследований, выполненных автором в Ереванском гос-.верситете с 1985-1990 гг.
Результаты работы докладывались на научных конференциях ванского госуниверситета (1985-1990 гг.), на ІУ Всесоюзной ференции "Математические методы распознавания образов" (Рига,
1989), на УІ Международной конференции "Основы теории вычисле ний" (Казань, 1987), на советско-германском рабочем семинаре дискретной математике "Логико-комбинаторные методы в.задачах работки информации" (Ереван, 1989), на семинаре отдела пробле распознавания и комбинаторных методов Вычислительного центра АН СССР,'неоднократно докладывались на семинарах кафедр теори систем и математической кибернетики ЕрІУ, на семинаре в Ж Ж УССР, на семинарах Вычислительного центра АН Арм.ССР.
По теме диссертации автором опубликовано 10 научных рабе По материалам исследований в 1990 г. опубликована монография "дизъюнктивные нормальные формы над линейными,функциями. (Ге< рия и приложения)" (издательство ЕІУ).
Структура и объем работы. Диссертация состоит из 6 глав, заключения, содержащего основные результаты и выводы, списка литературы, включающего 48 наименований. Полный объем - 235 страниц машинописного текста.