Логико-алгебраические способы описания геометрических фигур тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Министерство общего и профессионального образования

Российской Федерации Саратовский Государственный Университет им. Н.Г.Чернышевского

РГ6 ол

■•> На правах рукописи

Шакиров Абдыганы Абжамилович

УДК 517.95

Логико-алгебраические способы описания геометрических фигур

Специальность 01.01.09 — математическая кибернетика

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Саратов — 1997

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

Научные руководители:

доктор физико-математических наук,

академик АТН РФ, профессор В.Б.Кудрявцев

кандидат физико-математических наук,

доцент Э.Э.Гасанов

Официальные оппоненты:

доктор технических наук,

академик РАЕН, профессор В.А.Твердохлебов

кандидат физико-математических наук,

доцент Л.В.Кальянов

Ведущая организация — Московский Энергетический Университет

Защита диссертации состоится 1997 г. в

у О час. $0 мин. на заседании Специализированного Совета К 063.74.04 Саратовского Государственного Университета им. Н. Г. Чернышевского по адресу: 410071, г. Саратов, ул. Астраханская, 83, Саратовский Государственный Университет.

С диссертацией можно ознакомиться в библиотеке Саратовского Государственного Университета им. Н. Г. Чернышевского

Автореферат разослан *Л1» 1997 г.

Ученый секретарь Специализированного Совета, кандидат физико-математических наук,

доцент

П. Ф. Недорезов

Общая характеристика работы

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

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

п

ип = СкЧ>к(х) + щ{х), (0.1)

к=1

це <*рь(х){к — 0,1,...,п) — заранее выбранные известные функции, ^,С2,...,С„ — неизвестные постоянные коэффициенты. А функция ;(х) — непрерывная функция, имеющая внутри области С? ограничен-ые и непрерывные производные и удовлетворяющая условиям т{х) > 0 нутри С, го(х) = 0 на границе О.

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

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

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

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

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

Предполагается, что имеется некоторое множество базисных фигур О = {(-и,...,Ст}, причем для каждой фигуры С?,-, где г = 1,2,...,т, имеется ее аналитическое описание гДхх,... ,я„). Предполагается, что фигура С, для которой надо найти ее аналитическое описание, пред-ставима в виде формулы ^(бх,... ,(?„,) над 0 с сигнатурой ГШ)->())5 которая описывает представление фигуры С? через базисные фигуры

,..., Ст с помощью операций П (пересечение), и (объединение), ~ (дополнение). Каждой фигуре Gi (г = 1,2,...,ш) сопоставляется предикат р,-, определенный на К", область истинности которого равна б,-. Производя в формуле Л{Сг\,..., ) формальную замену Gi на р; и операций П;и,~на А (конъюнкция), V (дизъюнкция), (отрицание) соответственно, мы получаем формулу Л{р\,... ,рт) логики предикатов, и эту формулу называем логическим описанием фигуры С?.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Содержание работы

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

Первая глава содержит обзор литературы по исследуемой тематике.

Вторая глава состоит из трех разделов.

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

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

В первом разделе данной главы приводятся основные понятия, используемые в этой главе.

Пусть И и N — множества действительных и натуральных чисел, соответственно; Ег = {0,1}.

Пусть га € ХЧ', И" — га-мерное евклидово пространство и Вп — единичный п-мерный куб, то есть Вп состоит из всех векторов (а1,а2,..., ап), где при г = 1,2,..., п имеет место а,- € Бя, для которых справедлива евклидова метрика.

Пусть 17 = {иг, «2,..., иЛ,. -.} и V = {иь г>2> • ■ • >...} — алфавиты переменных принимающих значения из Е2, и из II, соответственно.

В качестве метаобозначений переменных из алфавита и мы будем использовать символы X, У, а также эти символы с индексами, а в качестве метаобозначений переменных из алфавита V — символы х, у, а также эти символы с индексами.

Множество всех булевых функций обозначим через Р?.

Пусть Х\ !\Х2, Хх V Х2,~°Х суть булевы функции, называемые, соответственно, конъюнкцией, дизъюнкцией и отрицанием и В — множество этих функций.

Понятие формулы и подформулы над В вводится так, как это принято в алгебре логики.

Две функции Р(Хи...,Хп) и 0(Ух,... из Рг называются равными, если множества их существенных переменных совпадают и на любых двух наборах а" и /?"*, различающихся, может быть, только значениями несущественных переменных, выполнено Е(ап) — £(/3™).

Каждая формула Л над В при любой фиксации значений ее переменных позволяет с помощью логических связок вычислить ее значение 0 или 1, а тем самым задает (реализует) некоторую булеву функцию.

Обозначим через Фд множество всех формул над В, а через • ■ • (или просто Фв(п)) — множество всех формул над В,

реализующих функции, зависящие от переменных .XI,..., Хп.

Формулы Л и В из Фв называются равными, если они реализуют равные функции.

Для а € Ет. обозначим через X" булевскую функцию такую, что

Пусть д € N.

Точечное множество в Ш будем называть фигурой. Пустое множество в Ш будем называть пустой фигурой и обозначать через Л.

Рассмотрим некоторое множество фигур вЯ'5 = {(?!, С?2,..., (?т}, и фигуры из этого множества назовем базисными. Каждой фигуре (?< сопоставим предикат р,(а;1,Х2,...областью истинности которого является б;, г = 1,2,..., т.

Поскольку описания фигуры С как в виде точечного подмножества плоскости, тале и в виде предиката р, область истинности которого есть это подмножество в, являются тавтологичными, то мы далее будем использовать предикат р для обозначения фигуры О и будем говорить "фигура р" несмотря на то, что р — предикат, описывающий фигуру <3.

Множество всех т-подстановок обозначим через Пт.

некоторая га-подстановка из Пт. Подставим в Л вместо каждой переменной X] = 1,2,..., то) предикат р{} из V. Данную операцию назовем полной тс-подстановкой (или просто т-подстановкой), а полученное выражение ЛТ(V) = , р-,г,...,р;т) назовем V-формулой.

Понятие 'Р-формулы и ее Р-подформул можно ввести также и по индукции.

Множество всех V- формул обозначим через Ф.в('Р).

Каждая формула Л{7>) из Фв(Р) при любой фиксации значений ее переменных позволяет с помощью логических связок вычислить ее

X" =

'X, если (7 = 0,

X, если <7 = 1.

Пусть

V = {рг(хг,.. .,хя),р2(х х,..., хд),... ,рт(хъ..., хя)} — множество базисных фигур, Л(Х\, Хг,..., Хт) Е Фв(го) и

яачение 0 или 1, а тем самым описывает (реализует) некоторый преди-ат.

Скажем, что ^-формула Д("Р) задает (реализует) такую фигуру \А(7>) из Л7; что область истинности предиката, описываемого "Р-фор-[улой Л(Р), равна Тщ-ру

Фигуры и называются равными (пишем = Тг), если они эвпадают в Ш как множества.

Т'-формулы А1Т) и В(Р) назовем Т-равпъши {А(Р) = В(Р)), если ни задают равные фигуры.

Пусть М — некоторое подмножество множества всех т-подстановок Г.

Формулы А и В из Фв называются (М, V)-равными, (пишем А = В), ели при любой подстановке т € М

мV) = ВТ(Р).

Понятно, что для любого тп € ]М, любых А, В из Фд(Х1,... ,Хт), юбого подмножества М множества всех т-подстановок Пт и любого онечного множества предикатов ~Р = {рг,р2,■ ■ ■ ,Рт} если А = В, то \М=РВ.

Пусть р — некоторая фигура. Через р1 обозначим фигуру р, а через 0 — дополнение к фигуре р, т.е. фигуру р.

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

Пусть

V = {р1(х1,...,х,),р2(х1,...,о;,),...,рт(х1,...,хг)} —

тожество базисных фигур, а М — некоторое подмножество множества сех т-подстановок Пт.

Скажем, что формула А из Фд пуста относительно V и М, если [ри любой подстановке тг £ М в нее предикатов из "Р вместо переменных юлучаемая V- формула реализует пустую фигуру.

V-формулу ... ,рч) = рЦ Л Л • • • Л рЦ, соответствующую

элементарной конъюнкции К{Хх, ..., X;) = Х{1 Л Л ••• Л X,"' назовем V-элементарной конъюнкцией.

Через К.™(М, V) обозначим множество всех элементарных конъюнкций из Фд{Х1,Х2,.. .,Хт) пустых относительно V и М.

При конечном V множество )С™(М, V) конечно.

Пусть А'(Т) есть ^-подформула для А{Т>) и Л"{Т>) М= А'{Т>). Тогда замена А"{9) в Л{Т) на А'{Р) дает А"'(Т) такую, что А"'{Т) М= А(Р).

Пусть 71 — некоторая система (М, "Р)-равенств (тождеств) формул из Фд. Формулы А к В из Фв называются И-соседнимщ если в А есть подформула А', а в Я есть (М, 'Р)-равенство А! т=г В' такое, что после подстановки формулы В' в А вместо А' получается В.

Говорят, что А и В из Фд являются И-эквивалентнымъ {А ~ В), если существует последовательность вида _Дх, • ■ •,где Д1 совпадает с Л, ,43 совпадает с В, а, для всех г = 1,2,..., 5 — 1 формулы и являются 7?.-соседними. В этом случае также говорят, чтс В получается из Ас помощью (М, Р)-тождеств из 71.

Множество (М, 'Р)-тождеств И. называется (М, Т)-полным в Фд, есля для любых А и В из Ф^ отношения А М=* В я А~ В эквивалентны.

Ясно, что множество всех пар .(М, Р)-равных формул образуют (М,Р)-полную систему (М, "Р)-тождеств. Нас будет интересовать вопрос существования конечной (М, "Р)-полной системы (М,7?)-тождеств I классе Фв(Х].,..., Хт) при конечном Р. Введенное нами понятие (М, Р)-тождества обобщает обычное понимание тождества в Фд, где Р. К. Лин доном установлено существование конечной полной системы тождесп в Фв, которую обозначим через Е.

Формально заменим во всех тождествах из Е знак "=" на знак " = " Ясно, что полученные тождества действительно будут (М, Р)-тождест-вами. Полученную систему (М,Р)-тождеств обозначим через Е(М,Р).

Обозначим через К™(А1, V) систему тождеств вида К О пр! К 6 К.™(М,Р).

Пусть Тгр(М,Т) = К?(М,Р) и Е(М,Р).

Основным результатом второго раздела второй главы является еле дующее утверждение.

Теорема 1 Для любого тп из любого подмножества М множеств!

всех т-подстпановок Пт и любого конечного множества предикатов V = {рх,р2,... ,рт} система % = является (М,'Р)-полной

вФв(Х1,...,Хт).

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

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

Отношение (М, Р)-равенства разбивает множество Фд на классы эквивалентности, где каждый класс содержит точно все (М, 7-')-равные формулы. Обозначим это разбиение через Т>м,7>-

Отметим, что обычное равенство формул разбивает множество Фв на классы эквивалентности, где каждый класс содержит точно все равные формулы. Обозначим это разбиение через Т>.

Здесь рассматривается вопрос о нахождении такого множества базисных фигур V = {ръ ■ • ■ ,рт}, чтобы порождаемое им разбиение Т>м,т совпадало с разбиением Т>.

Будем говорить, что множество базисных фигур V обладает М-свойством, если отношения равенства булевских формул и (М, ^-равенства эквивалентны, т. е. разбиения Т> и совпадают, или, что то

же самое, для любых двух формул Л,В€ Фд(п) верно Л М= В тогда и только тогда, когда А = В.

Множество всех граничных точек фигуры р назовем границей др фигуры р.

Область в И2, граница которой является п-угольником, называется п-угольной областью. Заметим, что для любого невырожденного п-угольника существует две п-угольные области, границей которых он является (внешняя и внутренняя).

Если р некоторая фигура, то функцию

Цр) = |

1, если р ф О О, если р = О

гл-подстановка из Пт и V = {рь... ,рт} — множество базисных фигур. Тогда булевскую функцию

назовем определяющей функцией множества базисных фигур V относительно подстановки тт.

Пусть М = {тгь... ,7гь} С П™ и V = {Р1,Р2, • • • ,Рт} — множество базисных фигур, тогда булевскую функцию

назовем определяющей функцией множества базисных фигур V относительно множества подстановок М.

В третьем разделе второй главы доказываются следующие теоремы.

Теорема 2 Пусть М С Пт, тогда множество базисных фигур V = {р\,рг, ■. ■ ,рт) обладает М-свойством тогда и только тогда, когда

Теорема 3 Для любого п из N и любого одноэлементного множества М С Пп существует такое множество базисных фигур V ~ {Р1,Р2, ■ ■ ■ >Рп}> обладающее М-свойством, что для каждого г € {1,2,... ,п фигура р,- является гщ-угольной областью, где

ОСт) = п п... п р£)

ггц =

если г = 1,2,3 если г > 3.

Георема 4 Для любого т из N существует, такое число п в ¡М, что 1ля любого одноэлементного множества М СП" любое множество базисных фигур V = {рг,р2, ■ ■ • ,Рп}> каждая область р,- является с,--угольной и А:,- < т, не обладает М-свойством.

Обозначим через е следующую подстановку

1 2 ... т

£ ~~ 1 1 2 ... т

Георема 5 Для любого п из N и произвольного множества базисных фигур V = {Р1,Р2) • • • ,Рп} справедливо Хп» = 1 тогда и только тогда, когда на каждом слое куба Вп существует хотя бы один набор а такой, 4.то = 1.

Георема 6 Для любого п из N и произвольного множества базисных фигур V = {ра,р2,-•-)Рп}, такого, что рп С рп-1 С ... С рг, справедливо, что Тп обладает Пп-свойством.

Третья глава состоит из трех разделов.

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

В первом разделе данной главы приводятся основные понятия, используемые в этой главе.

Будем рассматривать функции /(х1,х2, ■ ■ ■, хп), аргументы которых определены на множестве Б., и такие, что /(х1,х2,.. .,хп) € И. Такие функции назовем действительными функциями и множество всех дей-:твительных функций обозначим через О,. Пусть В некоторое подмножество функций из £). Обычным образом вводится понятие формулы над Б. Формулы над множеством действительных функций О будем называть аналитическими формулами над £).

В дальнейшем обозначим аналитические формулы заглавными буквами А\,А2,____Если в построении аналитической формулы А участвуют переменные х2,.. ■, хп, то пишем А(х 1, х2,.. хп).

Длиной аналитической формулы А назовем число, равное количеству вхождений переменных в формулу А и обозначим ее через Ь(А).

Каждая аналитическая формула А при любой фиксации значений ее переменных позволяет с помощью функций из В вычислять ее значения и тем самым задает (реализует) некоторую действительную функцию. Функцию / из 2, которая реализуется аналитической формулой А будем обозначать через /д.

Любое открытое множество точек из Ш1 будем называть фигурой.

Пусть 0 = {01,...,0т} множество базисных фигур. Пусть V — {р\,---,рт} множество предикатов, соответствующих фигурам <?!,...,От соответственно.

С помощью 0 и теоретико-множественных операций П, Ц получается множество Ф, вообще говоря, новых геометрических фигур. Любая фигура из Ф определяется некоторой логической формулой .Д((?г,..., над 0 с сигнатурой ГШ)"">(>)• Пусть дана .А((?1,... ,От), задающая фигуру б. В формуле А производим формальную замену (3, на р,- и операций ГЫ^- на Л, V, —соответственно. В результате получим формулу логики предикатов А(р1,...,рт), которую назовем V-формулой, логически описывающей фигуру £?.

Длиной V-формулы А(р1,... ,рт) назовем число вхождений предикатов р,- (г = 1,2,..., т) в формулу А и обозначим ее через Ь(А).

Говорим, что аналитическая формула хг,..., хп) над Б сильно описывает фигуру б из 11", если

• 1а{х1,...,хп) > 0, при (хь ...,хп) 6 й,

• 1а{х1,...,хп) = 0, при (хь...,хп) еде,

• /д(ал,...,хп) < 0, при (хъ...,хп) еВ.п\(£иЭО),

где 5(7 — граница открытого множества б.

Так как в выражении (0.1) не накладывается ограничений на значения ю{х) вне границы области (?, имеет право на существование и следующее определение.

Будем говорить, что аналитическая формула А(х 1, аг2,..., хп) над В слабо описывает фигуру в из Н.п, если

• /а(х1,...,х„) > 0, при (хь...,х„) е (?,

• fA(xu ...,xn) = 0, при ..., xn) € R" \ G.

Во втором разделе третьей главы доказывается нижняя оценка сложности аналитических формул, полученных по методу ií-функций.

Пусть нам дана фигура G и ее логическое описание "Р-формулой А{р\, ■ ■.,рт). Будем считать, что каждая базисная фигура G¡ € Q сильно описывается некоторой аналитической формулой над D, которую обозначим через ..., хп) (г = 1,2,..., т).

Ставится задача по логическому описанию A(pi,... ,рт) фигуры G построить такую аналитическую формулу ..., хп), которая бы

сильно (или слабо) описывала эту фигуру.

Один из методов решения этой задачи, называемый методом R- функций, предложил В. Л. Рвачев (1963 г.).

Метод ií-функций состоит в следующем:

1. Берется логическое описание A(pi,..., рт) фигуры G.

2. В формуле А производится формальная замена символов предикатов pi на символы г,- (г = 1 , т), а связок A, V, -i соответственно на Лд(а), Уща), ~4i(a), ГДе а € (—1; 1]. Полученная формула называется Л-формулой.

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

Г1 Ущс) Г2=Г!+Г2 + \]г\-2-{а)г1-г2 + г1, (0.2)

Г1Лд(а)Г2 = Г! + г2 - \]г\-2-{а)п-Г2+гЪ, (0.3)

~,я(а)>" = -г, (0.4)

Как показал В. Л. Рвачев, получающаяся в результате аналитическая формула будет сильно описывать фигуру G.

Пусть А некоторая V- формула. Через RA обозначим аналитическую формулу получающуюся из 'Р-формулы А по методу ií-функций Рва-чева с помощью соотношений (0.2) - (0.4) при а — 1.

Следующий ниже результат позволяет оценить длину аналитической формулы, полученной по методу Рвачева.

Теорема 7 Для любой V-формулы А(рг,.. -,рт) Ь(11Л)>(ЦА))2 ют ¿(г,),

где г,- — аналитическая формула, сильно описывающая фигуру р^ (г = 1,2,..., т).

Если г — вещественное число, то через |г| обозначим абсолютное значение числа г.

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

¿"-метод состоит в следующем:

1. Берем логическое описание А(рг,... ,рт) фигуры б.

2. С помощью тождеств {рг У р2) = (рГ Л Щ), (рг Л р2) = (рГ V Щ) и р — р, которые не увеличивают длину формулы, преобразуем формулу А(рг,... ,рт) к формуле А'(рх,... ,рт), в которой все отрицания спущены до предикатов.

3. Сохраняем структуру скобок.

4. Заменяем формально знаки "V" и "Л" на знак "+" (сложение) и "•" (умножение) соответственно.

5. Заменяем выражения вида р6{' на ((—1)1+|5, • г,(г)+ | г,-(а;) |), где г; — аналитическая формула, сильно описывающая фигуру р,-.

6. Полученную формулу обозначим Зл и считаем, что если нет скобок, то приоритет операций "+" и одинаков.

Справедливы следующие теоремы.

Теорема 8 Если Т-формула А{р\,.. - ,рт) логически описывает фигуру в, и для любого г (Е {1,2,...,ш} г,- — аналитическая формула, сильно описывающая фигуру р,-, то аналитическая формула , полученная 5-методом, слабо описывает фигуру С?.

Теорема 9 Для любой V-формулы А{р\, ...,рт) Ь{8Л) < 2ЦА) ■ щах Х(г,-),

1<1<ТП

где Г{ — аналитическая формула, сильно описывающая фигуру р,-(г = 1,2,..., т).

Четвертая глава посвящена проблеме эффективного выбора логического описания заданной фигуры.

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

Формально этот результат выглядит следующим образом.

Пусть («х, «2,..., кт) — вектор, где /с,- £ Е%, г = 1,2,..., т.

Октантом 0К с кодом к = к2, ■ ■кт) назовем множество точек (/?!, • • • 0т) € Л"1 таких, что /3,- > 0, если к,- = 1, и Д- < 0, если = 0.

Действительную функцию д(у\,... ,ут) € О. назовем октантно-знакопостоянной, если она не меняет своего знака внутри любого октанта.

Пусть дана булевая функция F(X 1,...,Хт). Октантно-знакопосто-янная функция <7(3/1, • ■ ■, ут) называется сопровождающей для Р(Х\,..., Хт), если для любого октанта с кодом (кг, к2,..., и для любой точки {уг, ■.. ,ут), принадлежащей этому октанту, значение функции д(Уг,---,Ут) > 0, если Г(аъа2,... ,ат) = 1, и 3(2/1,... ,ут) < 0, если Р(аг,а2,...,ат) = 0.

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

Октанты Ок и Оназываются соседними, если наборы к и 7 соседние.

Справедливы следующие теоремы.

Георема 10 Если октантно-знакопостоянная функция <7(2/1,2/2, ••• ,Ут) 8 любых соседних октантах принимает противоположные знаки, то она является сопровождающей функцией для некоторой линейной булевой функции.

Георема 11 Если 2 = {х-у, —1}, то для любой булевой линейной функции Е(Хг,..., Хт) = Х\ ф... ф Хт ф с существует формула над £ длины то, реализующая непрерывно-дифференцируемую сопровождающую функцию функции Р(Х\,..., Хт), и в качестве этой формулы можно взять формулу А{ух, ...,ут) = (-1)т+1~с • уг ■ ... - ут.

Во втором разделе четвертой главы предлагается алгоритм минимизации логического описания геометрических фигур.

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

Список публикаций по теме диссертации

1. ШакировА. А., Об одном способе описания геометрических фигур. — Проблемы теоретической кибернетики: Материалы XI Международной конференции, Ульяновск, 10-14 июня 1996 г. — Изд. центр РГГУ, Москва, 1996, с. 202-204.

2. ГасановЭ. Э., ШакировА. А., К вопросу о предикатной эквивалентности формул алгебры логики. — Труды XII Международной конференции "Проблемы теоретической кибернетики", Красновидово, 23-28 июня 1997 г., с. 18 - 20.

3. ГасановЭ. Э., ШакировА. А.,0 предикатной эквивалентности формул алгебры логики. — Интеллектуальные системы (в печати). Т. 49ЧЪ с ЛЪ\- .

4. ШакировА. А., К логическому описанию геометрических фигур. Фундаментальная и прикладная математика (в печати).

5. ШакировА.А.,О методах перехода от логического описания геометрических фигур к аналитическому. — Интеллектуальные системы (в печати).

В заключение автор выражает глубокую благодарность своим научным руководителям В.Б.Кудрявцеву и Э.Э.Гасанову за помощь в работе и А.С.Строгалову за внимание и поддержку.