Логико-алгебраические способы описания геометрических фигур Шакиров, Абдыганы Абжамилович

Введение к работе

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

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

u_n = w(x)^2 С_кУк{х) + 4>o(x), (0.1)

к=1

це 0,1,...,n) — заранее выбранные известные функции, \,С2, ,С_п — неизвестные постоянные коэффициенты. А функция )(х) — непрерывная функция, имеющая внутри области G ограничен-ые и непрерывные производные и удовлетворяющая условиям w(x) > 0 нутри G, w(x) = 0 на границе G.

Встает задача построения для заданной области G описанной выше >ункции w(x). Чтобы более формально ввести постановку этой задачи елаются следующие предположения.

Предполагается, что исследуемая область (фигура) G есть подмножество n-мерного евклидова пространства Rⁿ. Предполагается, что име-тся некоторое множество D "хороших" функций, действующих из Rⁿ R. Вводится обычным образом понятие формулы над D, и каждая юрмула над D реализует некоторую функцию, действующую из Rⁿ в I. Считается, что некоторая формула А над D является аналитиче-ким описанием фигуры G, если функция, реализуемая формулой А, оложительна внутри фигуры G и равна 0 на границе фигуры G.

Построение аналитического описания для некоторых областей (круг, ллипс, выпуклый многоугольник) не составляет труда. Но если область

представляет собой сложную фигуру, например, пятиконечную звезду или невьшуклую сложную фигуру и. г. д., то построение аналитического описания не так-то просто.

Метод решения этой задачи, получивший название метода Д-функ-ций, предложил В. Л. Рвачев (1963 г.). Суть этого подхода состоит в следующем.

Предполагается, что имеется некоторое множество базисных фигур Q = {Gi,...,G_m}, причем для каждой фигуры (?,-, где і = 1,2,...,т, имеется ее аналитическое описание гі(хі,...,х_п). Предполагается, что фигура G, для которой надо найти ее аналитическое описание, пред-ставима в виде формулы A(Gi,... ,G_m) над Q с сигнатурой 0)U>^—>(>)> которая описывает представление фигуры G через базисные фигуры Gi,...,G_m с помощью операций П (пересечение), (J (объединение), ~ (дополнение). Каждой фигуре G{ (і = 1,2,...,m) сопоставляется предикат pi, определенный на R", область истинности которого равна G,-. Производя в формуле A(Gi,..., G_m) формальную замену G; на pi и операций П)и,~на Л (конъюнкция), V (дизъюнкция), -> (отрицание) соответственно, мы получаем формулу A(pi,... ,р_т) логики предикатов, и эту формулу называем логическим описанием фигуры G.

Метод Д-функций В.Л.Рвачева предлагает некий способ перехода от логического описания фигуры G к ее аналитическому описанию.

Целью настоящей работы является дальнейшее развитие описанного подхода.

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

Актуальны также проблема выбора среди эквивалентных логиче-ких описаний "лучшего" описания и проблема построения эффектив-[ых методов перехода от логического описания к аналитическому.

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

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

Основные результаты диссертации, выносимые на защиту:

1. Доказано существование конечной полной системы тождеств в классе формул логики предикатов, используемых при описании геометрических объектов, в случае ограниченного числа переменных в формуле.

2. Исследовано отношение Р-равенства формул алгебры логики, которое подразумевает равенство формул в случае равенства описываемых фигур. Установлено, что при надлежащем подборе множества базисных фигур Р отношения ^-равенства и обычного равенства формул являются эквивалентными. Оценена сложность описания базиса Р, при котором эта эквивалентность может быть достигнута.

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

4. Предложен новый алгоритм минимизации формул логики предикатов, являющихся логическими описаниями геометрических фигур.

Методы исследования. В работе используются методы дискретной математики, а также методы аналитической геометрии и теории сложности.

Апробация работы. Результаты данной работы докладывались на Международной конференции по проблемам теоретической кибернетики (Ульяновск, 1996 г., Красновидово, 1997 г.), Международной конференции "Интеллектуальные системы" (Москва, 1997 г.), а также на семинаре по теории автоматов под руководством академика АТН РФ, профессора В.Б.Кудрявцева в МГУ им.М.В.Ломоносова (1997 г.).

Публикации. По теме диссертации опубликовано 5 печатных работ.

Структура и объем работы. Диссертационная работа состоит из введения и четырех глав. Объем диссертации — 83 стр. Список литературы включает 38 наименований.