|
Системное автоматизированное проектирование| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | а) |( |x |y |L1 |L2 |V | |угла| | | | | | |1 |4 |5 |0 |90 |90 | |2 |5 |3 |90 |0 |90 | б) Рис. 11. а) фрагмент изображения, б) таблица значений параметров элементов граничного контура. Достоинства полигональной формы: - не вносит искажений; - позволяет выделять резкие изгибы границ черной и белой областей; - требует меньшего объема памяти (по сравнению с дискретной первичной формой в 10 - 20 раз). Вопросы построения полигональной формы не будем рассматривать. 4.4.2. Отделение символов Задача отделения символов формулируется следующим образом: из полигональной формы отобрать те gi, которые описывают границу фрагмента изображения символа. Изучение реальных изображений показывает, что фрагменты изображения символов более насыщены неоднородностями хода границы черно-белого, чем фрагменты изображений несимвольной части. Это дает возможность предложить достаточно простой критерий для сортировки границ контуров - gi, входящих в полигональную форму. К символьным gi будем относить такой граничный контур, для любых двух соседних элементов ak, ak+1 которого выполняется условие R (ak, ak+1) < D , где R (ak, ak+1) - расстояние между центрами углов ak, ak+1; D - некоторая константа, определяемая максимальным линейным размером символа, допускаемым на документе. Очевидно, что проверка любого gi на принадлежность его множеству символьных граничных контуров осуществляется за один проход. Это не создает трудностей при построении соответствующего алгоритма. ЛЕКЦИЯ (5 Тема: “Специализированная обработка изображений для эскизов слоев топологии плат печатного монтажа” Специализированная обработка изображений выполняется после универсальной обработки. Она зависит от типа документа. В процессе специализированной обработки выделяются отрезки такого типа, который имеется на документе. Задачи специализированной обработки: - обработка базовой линии, - корректировка положения узловой точки по данным обработки базовой линии, - выделение контактных площадок круглой формы, - выделение контуров границ областей металлизации, - отыскание областей библиотечных групп, - обнаружение отрезков трасс печатных проводников, - формирование файла для описания изображения. Кратко рассмотрим отмеченные задачи. 1) Обработка базовой линии Выполняется в два этапа: - обнаружение базой линии; - построение массива описания реального положения рисок базовой линии на поле документа. На первом этапе при обнаружении базовой линии используется информация о том, что к базовой линии должны быть отнесены - все вертикальные элементарные отрезки, имеющие крайнее правое и крайнее левое положения; - все горизонтальные элементарные отрезки, имеющие крайнее правое и крайнее левое положения. На втором этапе определяются координаты центра сечения рисок путем усреднения значений ординат концевых точек риски, для горизонтальной риски и путем усреднения значений абсцисс для вертикальной риски. 2) Корректировка положения узловых точек При этом необходимо привязать к ближайшему узлу ряд точек, относительно которых установлено, что они должны быть помещены в одном из узлов координатной сетки. Привязка точки осуществляется в два этапа, раздельно по оси ординат и оси абсцисс. Рассмотрим привязку по оси ординат. Имеется горизонтальная линия координатной сетки. Она имеет проекции на ось ординат. Значения yп и yл, являются ординатами правого и левого концов линии координатной сетки. Документ имеет левый (правый) перекос, если для каждой горизонтальной линии координатной сетки выполняется условие yп < yл , ( yп > yл ) . На рис.12 приведена иллюстрация левого перекоса изображения. Рис.12. Определение расстояния от точки на эскизе слоя топологии до горизонтальной линии координатной сетки Определение номера горизонтальной линии координатной сетки, к которой должна быть привязана точка а с координатами хa и ya осуществляется по правилу близости этой точки к линии координатной сетки. При небольшом перекосе изображения в качестве расстояния от точки а до линии координатной сетки можно взять длину вертикального отрезка аb, где b - точка пересечения вертикального отрезка с линией координатной сетки. Точка а привязывается к той линии координатной сетки, расcтояние до которой минимально. Суть привязки состоит в замене ya на значение ординаты, соответствующей этой линии координатной сетки. Подобным образом осуществляется привязка произвольной точки по оси абсцисс. 3) Выделение контактных площадок Выделение площадок круглой формы основано на обнаружении коротких отрезков, входящих в состав креста. Крест соответствует изображению площадки. Обнаружение креста инициирует процесс изучения области его расположения. При этом отыскиваются изображения точек, которые несут информацию о типе контактной площадки. 4) Выделение произвольных конфигураций типа контуров Нахождение произвольных конфигураций типа контуров является основой для решения задач корректировки положения узловой точки и выделения контактных площадок. При поиске осуществляется обход контура. Обнаружение контура осуществляется тогда, когда возвращаются к исходному отрезку. Для идентификации обнаруженного контура необходимо знать, является он внутренним или внешним. Если при просмотре внутреннего контура встречается штрих, характерный для границы области металлизации, то это является основанием для его идентификации. Изучение внутренних контуров также служит основой для отыскания границ библиотечных групп. При удалении элементарных отрезков, входящих в состав контактных площадок круглой формы, границ областей металлизации и границ библиотечных групп на изображении остаются только печатные проводники. Обработка этой части информации сводится к обнаружению указателей типа проводников в разрывах трасс печатных проводников и увязки их области действия с отрезками. 5) Генерация завершающего файла Представляет собой процесс формирования записей, которые несут информацию о найденных обьектах, с последующим их включением в файл. ЛЕКЦИЯ (6 Тема: “Основные проектные процедуры в САПР” ВВЕДЕНИЕ Достаточно очевидным является вывод относительно экспертного сопрождения подсистемы моделирования объекта проектирования. Рассмотрим множество операций, которые совершает коллектив проектантов над этой подсистемой. На основе этого анализа представляется разумным установить, насколько поддается формализации инженерная деятельность в среде системы автоматизированного проектирования и существует ли возможность опираться на какие-то фундаментальные положения типа формула изобретения. Попутно целесообразно обобщить практический опыт в различных предметных областях и на разных иерархических уровнях проектирования и сформулировать требования к экспертному сопровождению процедур. ОСНОВНАЯ ЧАСТЬ , если структура синтезируемого объекта оговорена либо ТЗ, либо единственными условиями физической реализуемости (единственный физический принцип, обеспечивающий выполнение ТЗ) . В результате решения задачи синтеза может возникнуть счетное Нестрогая классификационная схема проектных процедур представлена на рис.1. На схеме показаны основные проектные процедуры, их выбор продиктован следующими соображениями. Для большинства объектов низшим уровнем проектирования можно считать компонентный. Понятно, что объект проектирования на этом уровне имеет структурное и параметрическое описания. Композиция отдельных компонент на схемотехническом уровне имеет также двойное описание. То же можно наблюдать на различных уровнях системы автоматизированного проектирования. Любая проектная процедура может быть классифицирована на структурную и параметрическую. Техническое задание на объект проектирования - это всегда некорректно поставленная задача. Поэтому при технологии нисходящего проектирования, даже если возможно выполнение процедуры синтеза, проектных решений всегда может быть больше одного по структуре и значениям конструктивных параметров. Уточнение ТЗ порождает необходимость выполнения процедуры анализа. Заметим, что при восходящем проектировании процедура анализа той или иной гипотехнической структуры объекта проектирования становится едва ли не единственно возможной. Если система автоматизированного проектирования построена по принципу генерации проектных решений, то процедура оптимизации является одной из основных. Даже в случае нисходящего проектирования в САПР, допускающего выполнение синтеза по ТЗ без генерации вариантов, уточнение значений конструктивных параметров осуществляется процедурами оптимизации. Рис.1. Основные проектные процедуры в САПР В процессе выполнения проектных процедур приходится всегда приводить в соответствие способ описания ТЗ, проектного решения (которое часто является ТЗ для более низкого уровня структуры проектирования) способу модельного представления объекта проектирования. Преобразованию может быть подвергнуто либо ТЗ, либо собственно модельное представление. Таким образом, процедура преобразования описаний как структуры так и параметров, является неотъемлемой частью любой САПР. Многие проектные решения принимаются в среде САПР в формализованном виде, зачастую на метаязыке системы. Поэтому для преобразования описания проектного решения (а иногда и ТЗ) используют процедуру идентификации проектного решения (ТЗ). Множество рассмотренных проектных процедур не является замкнутым по номенклатуре и детализации описания. Однако можно утверждать, что для рассматриваемых здесь предметных областей оно достаточно полно детализирует процесс проектирования. Последнее утверждение основывается на том, что в указанных предметных областях существует в той или иной мере адекватное модельное представление объекта проектирования в виде некоторого оператора: La : X ( Y ; a ( A, здесь X и Y описывают множество входных и выходных сигналов . Данное соотношение устанавливает связь между фазовыми переменными над множеством {A} конструктивных параметров a. Теоретико-множественный анализ этого оператора и его отображения для модельного представления объекта проектирования показал, что существует счетное множество его преобразований, а также операций над ним: декомпозиция и композиция (преобразование) синтез и анализ. Операции над множеством {A} связаны с поиском единственного ai , которое определяет La . Возможно также либо определение Y при определенных La {} ,{A} и X, либо La{} при заданных Y и X . Поскольку Y и X зачастую инвариантны к классу объектов проектирования в данной САПР, неизбежно преобразование описаний (представлений) Y , X , {A}. Формализм представления La {} требует решения задачи идентификации. АНАЛИЗ ПРОЦЕДУР 1. Процедура анализа Процедура анализа понимается как процесс представления выходных характеристик объекта проектирования при известных входных воздействиях или начальных условиях по какому-либо описанию объекта проектирования (модельному представлению). Одновариантный анализ проводится с целью установления соответствия входных характеристик требованиям ТЗ. Многовариантный анализ направлен на установление в явном, наглядном виде связи между входными данными, характеристиками и конструктивными параметрами. 2. Процедура синтеза Решение задачи синтеза обеспечивает получение описания объекта проектирования по ТЗ на объект в виде структуры и совокупности значений конструктивных параметров. Параметрический синтез проводится конечное множество проектных решений. Если решение одно, синтезируемый объект будем называть "оптимальным по ТЗ". Оптимизация конструктивных параметров приводит к полному описанию объекта проектирования. Оптимизация допусков проводится с целью установления совокупности значений каждого конструктивного параметра по заданному теоретически обоснованному критерию. Оптимизация технических требований обеспечивает назначение оптимальных (в смысле теоретически обоснованного критерия) требований к выходным характеристикам объекта проектирования. 3. Процедуры преобразования Процедуры преобразования осуществляются над множеством лингвистических и математических переменных. Их последовательность образует запись либо ТЗ, либо проектного решения, с целью: а) обеспечить представление ТЗ на метаязыке конкретной САПР, б) представить в форме, понятной проектанту, то или иное проектное решение, сформулированное на метаязыке системы, в) обеспечить совместимость проектных процедур Вторая группа преобразования выделена в отдельную процедуру идентификации. Если преобразование осуществляется над неформальным описанием, то оно представимо на языке логики предикатов первого порядка. Например, если для множества лексем, образующих определенную совокупность требований технического задания Ln, и множества критериев проектных решений Kp ввести предикат Q (Ln , Kp ), обозначающий факт однозначного соответствия L и K любой лексемы li из множества {L} одной и только одной формальной записи критерия Ki p ({K} , то соответствующая формула имеет вид: (( lin ( Ln ) (( Kip ( Kp) ( Q(Ln, Kp). Если преобразование не выполнимо за одну процедуру, но существуют две совместимые процедуры и результат преобразования не зависит от порядка их применения, то (( lin ( Ln, ( Kip ( Kp) ( Q(Ln, Kp) Q (Ln-m , Kp). Если в качестве терминов, входящих в формулу, используются математические переменные, то операция преобразования записывается математической формулой, которая реализуется алгоритмически. Процедура преобразования, применяемая к тому или иному проектному решению, записанному в виде топологии объекта проектирования, может осуществляться либо объединением (композицией), либо декомпозицией. В свою очередь, композиция проектных решений имеет несколько модифицированных представлений и их множество счетно. То же можно сказать относительно декомпозиции проектного решения. Здесь отметим, что процедура композиции характерна для восходящего проектирования, а декомпозиция - для нисходящего. 4. Процедура идентификации Процедура идентификации осуществляется либо над множеством данных (из базы данных) когда ставится задача преобразования проектного решения, либо над множеством проектных решений, когда ставится задача занесения его в базу данных. Указанные задачи, решаемые в соответствии с классифицируемыми процедурами, как отмечалось, сделаны относительно объектов. Они имеют описание в виде цепочек формульных зависимостей (модельных представлений, реализуемых алгоритмически) либо цепочек термов, лексем, лингвистических переменных). Поэтому можно предположить, что множество перечисленных процедур факторизуется по классификационному признаку, связанному со способом описания и реализации в среде САПР. КЛАССИФИКАЦИЯ ПРОЦЕДУР Каждая из перечисленных процедур может быть отнесена к одному из трех типов процедур: - формальная, - формализуемая, - эвристическая. Дадим несколько определений. а) Формальная процедура - совокупность действий, которая порождает проективное (или счетное множество проектных решений) без участия проектанта. В этом случае проектант только формулирует задачу: назначает входные данные и указывает критерий проектного решения. б) Формализуемая процедура - процедура, которая может лишь частично формально описываться в виде какого-либо алгоритма, иногда даже реализующего численный метод, но исходные данные для нее требуют преобразования, а условия ее протекания, критерии проектных решений требуют уточнения не при переходе от одного объекта проектирования к другому, но и процессе ее выполнения. Проектант может влиять на условия протекания формализуемой и эвристической процедур, руководствуясь только лишь опытом, интуицией, здравым смыслом, причем как своим собственным, так и по выбору, и накопленным в данной САПР. в) Эвристическая процедура - процедура, которая не поддается никакому формальному описанию, не может быть описана никаким алгоритмом и при определенных условиях не обеспечивает принятия проектного решения. Приведем примеры процедур. а) Формальные процедуры: - анализ чувствительности модели проектирования, применяемой в теории автоматического регулирования, - синтез оптимального фильтра (решение задачи Винера-Хопфа), когда критерий сформулирован в ТЗ, - поиск безусловного экстремума целевой функции, сформулированной для задачи непосредственно в ТЗ. Перечисленные процедуры позволяют оперировать со строгими математическими моделями, являются реализацией конкретно поставленной задачи и инвариантны к критерию проектного решения. б) Формализуемые процедуры: - одновариантный анализ объекта проектирования на математической модели при отсутствии полной информации о характере входных воздействий или при нечетко определенной области адекватности, - синтез структуры объекта проектирования, не имеющего аналогов и прототипов, осуществляемый за счет использования сочетания различных физических принципов и компонент разной физической природы. "Суммарный" эффект не является простой суммой отдельных эффектов, возникающих от использования того или иного физического принципа, - условная оптимизация значений конструктивных параметров с использованием многомерной целевой функции (многокритериальная некорректно поставленная задача). Отличительной чертой перечисленных формализуемых процедур является их "экстраполяционный" характер. Во всех указанных совокупностях действий "предсказывается" поведение объекта проектирования на основе гипотетической информации при ограничениях, которые основаны на фундаментальных физических принципах (закон сохранения энергии, не отрицательность времени и т.д.) Формализуемые процедуры занимают "промежуточное" положение между формальными и эвристическими. С одной стороны, они используют математические модели, с другой стороны, характер их использования является экстраполяционным. Например, параметрическая оптимизация, осуществляется с изменением метода оптимизации. Изменение метода происходит в результате анализа как целевой функции, так и влияния ограничений на характер процесса оптимизации. Видно , что проектная операция может быть только формальной (по определению). Поэтому можно говорить, что формальная проектная процедура всегда состоит из конечного числа проектных операций. Эвристическая процедура не содержит проектных операций, а формализуемая состоит из несовместимых операций. Их нельзя применять в любой последовательности и в любом сочетании, или их сечение нельзя заранее определить (предсказать). ЛЕКЦИЯ (7 Тема: “Знания в вычислительных системах (САПР). Формы представления и способы кодирования.” ВВЕДЕНИЕ Одним из первых обобщений, связанных с искусственным интеллектом в САПР, стала работа "Интеллектуальные системы автоматизированного проектирования больших и сверхбольших интегральных схем” В.А.Мищенко, Л.М. Городецкий и др. Радио и связь, 1988." В ней излагаются концепции системы проектирования, "имитирующей деятельность конструктора в части накопления информации об алгоритмах проектируемых схем, модификации исходных алгоритмов для получения необходимых требований технического задания, перебора имеющихся конструктивов для реализации конкретной схемы, решения задач оптимизации при синтезе, проверки корректности требований ТЗ в рамках знаний, заложенных в систему. Понятно, что сформировать требования к "интеллектуальным САПР" независимо от предметной области довольно трудно. В первую очередь эти вопросы привлекли внимание разработчиков интегральных схем. В этой предметной области в значительно большей степени возможно формализованное представление объекта проектирования, различных проектных процедур. Это справедливо, пока речь идет о проектировании алгоритмов, архитектуры и функционально-логической структуры интегральных схем. Как только степень детализации в описании объекта проектирования достигает уровня, на котором требуется оперировать физическими величинами, и если речь идет о моделировании условий протекания физических процессов, то адекватное формализованное описание объекта и процесса проектирования становится все более затруднительным. Поэтому представляется разумным сопоставить возможности строгого и формализованного подходов к проектированию. Он заключается в "жесткой "организации программного обеспечения САПР, и чисто эвристического подхода, используемого в экспертных системах, которые функционируют либо на основе нечеткой логики, либо на стохастических методах обучения. В радиоэлектронном приборостроении используются сочетания разнообразных физических эффектов. В этой области как и в оптическом приборостроении и автоматики распространены системы автоматизированного проектирования с традиционной организацией программного обеспечения. Это связано, прежде всего, со значительными трудностями создания однородного математического описания систем, сочетающих резко отличающиеся по физической природе компоненты. В данной лекции мы обращаем внимание на те проблемы, которые целесообразно решать за счет использования "жестких" и "мягких" компонент программного обеспечения САПР. Обращено внимание на поиск точек соприкосновения формализованных и эвристических подходов на основе анализа основных принципов организации и функционирования таких систем применительно к задачам исследования. Слабые места в формализованном подходе и пути их усиления за счет использования экспертных оценок, определяющих как характер так и последовательность их применения в сочетании с модельным представлением различных объектов проектирования, также будут рассмотрены. Предполагается провести анализ способов модельного представления объектов проектирования, которые дают довольно строгую формализацию описания различных предметных областей. При этом сделан акцент на проблему адекватного описания. ОБЩИЕ СВЕДЕНИЯ Наиболее распространенным определением экспертной системы является утверждение о том, что это вычислительная система, оперирующая знаниями специалистов в определенной предметной области и способная принимать решения на уровне этих специалистов. В этом определении остается неясным, что следует понимать под термином" знания" и что означает способность принимать решения вычислительной системой. Эта неясность возникает, если достаточно строго отнестись к термину "вычислительная система". Если понимать ее как особым способом организованную совокупность программно-аппаратных средств, то способность ЭВМ принимать решения представляется спорной. Экспертная система, как всякая вычислительная система, ни в какой момент времени ее создания и функционирования неотделима от пользователя и разработчика. Первый существенный признак, позволяющий рассматривать экспертную систему как самостоятельный класс вычислительных систем, заключается в том, что она не должна морально устаревать. Большинство работ, посвященных экспертным системам, свидетельствует о том, что основу их архитектуры составляет запас знаний о конкретной предметной области. При этом знания понимаются как совокупность правил, определяющих характер обработки данных, в результате применения которых может формироваться новая совокупность правил. В приведенных определениях используются понятия данные и знания. а) ДАННЫЕ в вычислительных системах - закодированные образы объектов реального мира, имеющих количественную меру. Наличие количественной меры говорит о возможности сопоставления объектов. В соответствии с принятым определением в дальнейшем термин "данные" и производные от него ("база данных", "управление базой данных" и др.) будет использоваться для обозначения любых констант (включая логические, строковые), переменных и функций, а также множеств, их объединяющих. б) Опираясь на определение данных, можно сформулировать определение термина " знания ". Необходимо отметь, что речь идет о знаниях в вычислительных системах, а не о знаниях вообще. Если измеримость объектов реального мира вытекает из возможности их сопоставления, т.е. установления отношений между ними, то среди этих отношений всегда можно выделить подмножество, которое объединяет закономерности. Такая возможность позволяет в дальнейшем оперировать термином "знания" в смысле образов отношений между измеримыми объектами реального мира. Если соотнести теперь определения данных и знаний, то становится ясным, что данные являются частным случаем знаний. В самом деле, измеримость объекта, т.е. существования данных об объекте предполагает его сопоставимость с каким-либо другим. Он условно принят за эталон. Это сопоставление позволяет установить отношения между объектами (например, равно, больше, одинаково по смыслу и т.п.). Отношение, в свою очередь, может быть закодировано и представлено в вычислительной системе. Если результат этого сопоставления кодируется константами, переменными либо функциями, то речь идет о представлении данных. Если же в вычислительной системе представляют (кодируют) способ и результат сопоставления и сущностью этой информации является отношение между данными, которое также может кодироваться константами, переменными и функциями, то такого рода данные в дальнейшем следует называть ЗНАНИЯМИ. Наиболее распространенными формами представления знаний являются логические, семантические и продукционные модели. Проведем анализ этих форм в сопоставлении с неформальным описанием знаний, составляющих основу инженерной деятельности. При этом будем различать формализуемые и эвристические способы построения моделей. В инженерной деятельности используют формализованное описание объектов проектирования и проектных процедур. С появлением САПР - это используется во множестве формализованных проектных процедур и моделей объектов проектирования. Объекты проектирования в сочетании со строгими методами оптимизации образуют жесткую структуру, изменения которой осуществляются разработчиками или специальными лицами, администрирующими информационную компоненту и сопровождающими систему автоматизированного проектирования. Они не являются специалистами в данной предметной области. ЛОГИЧЕСКИЕ МЕТОДЫ ПРЕДСТАВЛЕНИЯ ЗНАНИЙ Предварительно остановимся на изложении некоторых понятий формальной теории. Формальная теория задана, если определены четыре множества B, F, A, R : S = {B, F, A, R}, где B - счетное множество базовых символов (алфавит) теории S ; F - подмножество выражений теории S (формулы теории ); A - выделенное множество формул, образующее аксиомы теории S (множество априорно истинных формул); R - конечное множество отношений между формулами ( правила вывода). Формальная теория S называется РАЗРЕШИМОЙ, если найдется единая процедура, которая позволяет узнать для любой данной формулы, существует ли ее вывод в S. Формальная теория S называется НЕПРОТИВОРЕЧИВОЙ, если не существует такой формулы ai ( A, чтобы ai и (ai были выводимы в S. Теория исчисления предикатов определяется следующими множествами: АЛФАВИТ: знаки пунктуации (,) . ; пропозициональные связки (, ( ,( , ( знаки кванторов ( , ( символы переменных хk , k=1,2,...,n символы функциональных букв fkn символы предикатных букв Pk ВЫРАЖЕНИЯ: множества выражений строятся над множеством символов алфавита с помощью термов и элементарных формул. ТЕРМЫ: символы переменной или константы, например X1,X2, ...,Xn или fk (X1,X2, ...,Xn) ЭЛЕМЕНТАРНЫЕ ФОРМУЛЫ: совокупность предикатных букв, термов и знаков пунктуации, например, Pk (X1,...,Xn) ПРАВИЛЬНО ПОСТРОЕННЫЕ ФОРМУЛЫ: совокупность элементарных формул и пропозициональных связок, например: Pk (X1 ,...,Xn) = P1 (X1,...,Xn). С помощью выражения ((X)D (A) обозначается область действия квантора всеобщности. Это означает: для любого X из D существует правильно построенная формула A. С помощью выражения ((X)D (A) устанавливается существование такого X из D, для которого справедлива правильно построенная формула. Области значений правильно построенных формул кодируются таблицами истинности. Они устанавливают значения 0 либо 1 ("ложь" либо "истина") формулам: (A , A ( B, A ( B НЕЧЕТКОЕ ОТНОШЕНИЕ определяется оператором R и операцией "(": R ( A = B, где A - входное нечеткое множество, B - выходное нечеткое множество. Не будем раскрывать данную запись на уровне системы алгебраических уравнений. Если истинность обозначена для всех наборов интерпретаций, ее называют общезначимой, в противном случае она невыполнима. Говорят, что формула A логически следует из формул B1,B2,...,Bi тогда и только тогда, когда интерпретация формулы B1,B2,...,Bi совпадает с интерпретацией A. (B1,B2,...,Bi ( A) В этом случае B1,...,Bi - посылки, а A - заключение логического следования. В сжатой форме это отношение обозначается как B1,B2,...,Bi => A На практике имеет большое значение теорема дедукции, согласно которой A является логическим следствием B1,...,Bi тогда и только тогда когда формула B1,B2,...,Bi общезначима. Известно использование исчисления предикатов для доказательства теорем. Методы доказательства теорем основываются на том, что если формула исчисления предикатов общезначима, то возможна проверка ее общезначимости на основе исчисления предикатов. Элементы исчисления предикатов используются для кодирования аксиоматики того или иного математического аппарата. Это позволяет использовать его в технологических приложениях для записи спецификаций программ и как следствие для аналитического преобразования формул, модельного представления объектов проектирования и описания проектных процедур, а также для проверки на корректность и полноту программных реализаций систем аналитических вычислений. НЕЧЕТКИЕ МНОЖЕСТВА И НЕЧЕТКАЯ ЛОГИКА Многие продукционные модели представления знаний опираются на аппарат нечетких множеств и нечеткой логики Л.Заде с лингвистическими, а не числовыми значениями истинности. Рассмотрим некоторые основные понятия. Установлено, что нечеткость возникает тогда, когда элемент w(W обладает некоторым свойством А, имеющим субъективную окраску (по мнению различных экспертов). Функция принадлежности (A( ) рассматривается как функция вещественного аргумента. Она определена на интервале [0,1]. Можно считать, что (A: u -> [0,1] ставит в соответствие каждому u число (A(u) из интервала [0,1], характеристическую степень принадлежности u подмножеству A. Нечеткое множество А будет обозначаться как объединение А = ((A(ui) / ui, либо А = {(1 / u1 + ...+ (n / u n} В случае, когда множество непрерывно A = ((A(u) / u. Определим понятие множества уровня (. МНОЖЕСТВО УРОВНЯ ( это четкое множество A( элементов универсального множества U, степень принадлежности которых множеству А больше или равна (: A( = {u / (A(u) > (}, где ( - в общем случае может быть нечеткой константой. ОБЪЕДИНЕНИЕ множеств по ( ((A = (( (A( Операция ДОПОЛНЕНИЕ (A = (u(1- (A(u))/u Операция ОБЪЕДИНЕНИЕ A ( B = (u((A(u) ( (B(u)) /u Операция ПЕРЕСЕЧЕНИЕ A ( B = (u((A(u) ( (B(u)) /u Аппарат, построенный на моделях нечетких операндов, широко используется в процедурных способах представления знаний. С его помощью осуществляется, в основном, эвристическое представление. Конкретные формы, в которых оно реализуется, зависят и от вычислительной среды, СУБД, от концептуальной модели базы знаний и от общей концепции проекта той или иной системы. СЕМАНТИЧЕСКИЕ СЕТИ Семантические сети строятся с помощью ориентированных графов. Вершины сети соответствуют объектам, а дуги семантическим отношениям. Среди объектов выделяют понятия, свойства и события. Семантические отношения можно условно разделить на лингвистические, логические, теоретико-множественные и квантифицированные. Применительно к задачам организации вычислительной среды САПР лингвистические отношения относятся к средствам доступа. К логическим отношениям относятся отношения типа: дизъюнкция, конъюнкция и отрицание. Теоретико-множественные отношения рассматриваются как проявление категорий части и целого, затрагивают иерархическую структуру той или иной САПР в целом. Пример такой сети приведен на рис.1. Семантические сети условно классифицируют на интенсиональные и экстенсиональные. ИНТЕНСИОНАЛЬНАЯ сеть устанавливает те отношения между объектами, которые отличаются объективностью и повторяемостью. ЭКСТЕНСИОНАЛЬНАЯ сеть кодирует отношения между конкретными фактами, объектами и событиями, т.е. между данными. Наибольшее распространение семантические сети получили в концептуальных моделях баз данных и поэтому имеют распространение в САПР. |
|
