Министерство образования РеспубликиБеларусь
Реферат на тему
МАТЕМАТИЧЕСКИЕМЕТОДЫ ОПИСАНИЯ МОДЕЛЕЙ КОНСТРУКЦИЙ РЭА
Минск 2010
ВВЕДЕНИЕ
Применениевычислительных машин на этапе конструирования РЭА по-новому ставит задачиразработки математических моделей и методов их анализа и оптимизации.Отличительной чертой в постановке этих задач является максимальная формализацияматематических описаний и использование для отыскивания оптимальных решенийаппарата математического программирования.
В общемслучае под математической моделью конструкции понимают систему математическихсоотношений, описывающих с требуемой точностью изучаемый объект и его поведениев реальных условиях. Процесс составления математических моделей называютматематическим моделированием. В основу математического моделирования положенпринцип идентичности формы уравнений и однозначности соотношений междупеременными в уравнениях оригинала и модели, т. е. принцип аналогии объекта смоделью. При составлении математических моделей могут использоваться различныематематические средства описания объекта — дифференциальные или интегральныеуравнения, теория множеств, теория графов, теория вероятностей, математическаялогика и др. Особое место в математическом моделировании занимаетквазианалоговое моделирование, суть которого состоит в изучении не исследуемогообъекта, а объекта иной физической природы, но описываемого математическимисоотношениями, эквивалентными относительно получаемого результата.
В даннойглаве рассмотрены вопросы применения теории множеств и теории графов, а такжеметодов конечно-разностных аппроксимаций для описания конструкций РЭА и моделированияпротекающих в них процессов.
ОСНОВНЫЕПОНЯТИЯ ТЕОРИИ МНОЖЕСТВ
Определения.Математические методы, положенные в основу алгоритмических процессовконструирования РЭА, а также процессы организации входной и выходной информациио проектируемом объекте широко используют понятия и символы теории множеств.
Подмножеством понимают совокупность объектов любой природы, называемых элементамиданного множества, обладающих каким-либо общим для множества свойством. Какосновное понятие теории понятие множества не подлежит логическому определению.
Элементымножества могут иметь самую различную природу. Например, можно говорить омножестве микросхем, входящих в определенную конструкцию РЭА, или о множествечертежей, входящих в полный комплект конструкторской документации дляпроизводства какого-либо изделия, и т. д.
Множестваобозначают заглавными буквами латинского алфавита: X, Y, Z, а элементы множеств —соответствующими строчными буквами того же алфавита: х, у, zили строчными буквами с индексами: х1,x2,… y1, у2,… Равенство X = {x1, x2, ..., хп} свидетельствует о том, чтоэлементы х1, х2, ..., хпявляютсяэлементами множества X.
Множествоможно задавать не только перечислением его элементов, но и с помощьюописательного способа, указывающего характерное свойство, которым обладают всеэлементы этого множества. Например, если во всем множестве X микросхем электронного блока сложнойрадиоаппаратуры есть некоторое множество А гибридных интегральных схем,то это можно записать следующим образом: А ={х/>Х: х — гибриднаяинтегральная схема}, что читается так: множество А состоит из элементов хмножества X, обладающих тем свойством, что х являетсягибридной интегральной схемой. Здесь введено новое обозначение />, означающее, чтообъект х является элементом множества X. Если же некоторый объект у не принадлежит множеству Хто это условие записывают в виде у /> X.
В томслучае, когда не вызывает сомнения, из какого множества берутся элементы х, принадлежностьих к множеству X можно не указывать.Например, если известно, что множество гибридных интегральных схем входит вомножество микросхем того же самого электронного блока, то можно записать А —{х : х — гибридная интегральная схема}.
Числоэлементов множества X = {/>} называют мощностьюэтого множества и обозначают прямыми скобками, например |Х| = п. Есличисло элементов множества Xконечно, то такое множество называют конечным. В противном случае множествобудет бесконечным. В теории множеств вводится понятие пустого множества, вкотором не содержится ни одного элемента. Пустое множество обозначаютспециальным символом Ø. Так, например, если множество X пусто, то пишут X= Ø.
Последовательностьиз п элементов множества называют n-строкой. В отличие от обычного множества, где порядокэлементов безразличен, в n-строкеобязательно задается их определенная последовательность.
МножествоX равно множеству Y, если оба эти множества состоят из одних и тех жеэлементов. Если множество Xполностью содержится во множестве Yипри этом |Х|Y|, то говорят, что множество Xявляется подмножеством множества Y:X/>Y. В случае когда X/>Yиодновременно Y/> X, имеет место равенство X=Y, т. е.множества X и У совпадают. Символическая запись X/>Yозначает, что множество X не совпадает с множеством Y.
Действиянад множествами. Над множествами, как и над другими математическими величинами,можно производить некоторые действия, например выполнять пересечение множеств,их объединение, вычитание, находить дополнение, декартово произведение и др.
Пересечениеммножеств Xи Yназывают новое множество Р, которое образуетсяиз элементов, одновременно общих и множеству X, и множеству Y. Нарис. 1, а множество Р показано заштрихованной областью.
/>/>
Рисунок1
Пересечениемножеств Xи Yзаписывают следующим образом: Р = X/> Y. Если рассматривают пересечение нескольких множеств Х1,Х2, ..., Хn,…., Хг, томатематическая запись имеет вид
/>
где r— число пересекающихся множеств.
Операцияпересечения множеств подчиняется переместительному закону, т. е. Р = X />Y= Y/> X. Если множества X и Yне пересекаются, то Р = X /> Y=Ø.
Спомощью операции пересечения множеств можно, например, выявить множествотипоразмеров конструктивных элементов, общих печатным платам X и Y, или множество межплатных соединений для печатных плат X и Y, т. е. выявить любые множества, обладающие какими-либообщими свойствами.
Объединениемножеств ХиУ приводит к образованию нового множества Q, которое получается из всех тех и только тех элементов,которые принадлежат хотя бы одному из множеств X или Y. На рис. 1,6такое множество показано заштрихованной областью.
Математическиобъединение множеств X и Yзаписывают следующим образом: Q= X U У. Если рассматривают объединение нескольких множеств, тозапись примет вид
/>
где r— число объединяемых множеств.Операция объединения множеств, так же как и операция пересечения, подчиняетсяпереместительному закону.
Спомощью этой операции можно подсчитать, например, число типоразмеровконструктивных элементов для печатных плат X и Yилиобщее число внешних электрических соединений печатных плат Xи Y.
Разностьмножеств Х и Y есть новое множество R, которое образуется из элементов множества X, за исключением элементов,принадлежащих одновременно множеству Y. На рис. 2, а множество Rпоказано в виде заштрихованнойобласти. Математически разность множеств Xи Yзаписывают следующим образом: R= X/Y.
Спомощью этой операции можно выявить сугубо индивидуальные признаки объекта, напримерчисло типоразмеров конструктивных элементов, принадлежащих только плате X.
Дополнениеммножествах по отношению к множеству Yназывают множество X, состоящее из элементов множества Y, не принадлежащих множеству X. На рис. 2, б множество X показано в виде заштрихованной области. С помощью операциидополнения множества можно выявить все дополнительные, недостающие признаки проектируемого изделия и подвергнуть их анализу.
/>
Рисунок2
/>
Рисунок 3
Декартовымпроизведением множеств X и Yназывают множество Z упорядоченных пар (х, у), образованныхэлементами множеств X и Y: Z= X/> Y. На рис. 3 декартово произведение множеств Х1и Y2показано в виде заштрихованной области множества паросочетаний.
Декартовопроизведение двух множеств используют для исследования всевозможныхпаросочетаний. Декартово произведение нескольких множеств
/>
представляетсобой множество r-строчек, каждаяиз которых образуется упорядоченной композицией элементов исходных множеств, т.е. zS= (x1f, x2j, ..., xrk). Операциядекартова произведения множеств не обладает переместительным свойством, т. е. X /> Y/> Y/> X.
Разбиениеммножествах называют такое множество множеств {Xj}, где j/>J, а J —некоторое множество индексов j, прикотором:
1) Xj/>Xпри всех j/>J;
2) Xj/> 0 при всех j/>J;
3) Xi/>Xj=0 при j/>J;
4) />Xj= X.
Рядприкладных задач разбиения множества конструктивных элементов высокого уровняна элементы более низкого уровня (например, задача разбиения множествамикросхем блока РЭА на отдельные субблоки) сводится к операциям разбиениямножеств. Конкретные решения подобных задач рассмотрены в гл. 4.
Понятиепустого множества 0 аналогично нулю в алгебре чисел. Действительно, еслидля любого числа а справедливо а /> 0= 0 и а+0 = а, то для любого. множества Xсправедливо X/> 0 = 0 и X/>0 =Х.
Введемпонятие множества I, соответствующееединице в алгебре чисел. Такое множество должно обладать тем свойством, чтопересечение с ним любого множества Xдаетв результате это же множество X, т. е. X/>I = Xпо аналогии с а /> 1= а.
МножествоI, обладающее этим свойством называютуниверсальным или единичным множеством. В общем случае, если при некоторомрассмотрении участвуют только подмножества некоторого фиксированного множества I, то это самое большое множество иявляется универсальным.
Вконкретных приложениях в качестве универсального множества могут использоватьсяразличные общие подмножества. Например, среди множества комплектов конструкторскихдокументов на изготовление изделий РЭА полный комплект конструкторскихдокументов является универсальным множеством этих документов или когда прирассмотрении множеств микросхем отдельных субблоков РЭА выделяют универсальноемножество таких микросхем на всю данную радиоэлектронную аппаратуру в целом.
Универсальноемножество обладает свойством, не имеющим аналога в алгебре чисел, а именно длялюбого множества Xсправедливосоотношение X/>I= I.
Вобъединение этих множеств должны входить как элементы множества X, так и дополняющие элементымножества I. Но, в свою очередь, все элементымножества Xвходят в универсальное множество I, поэтому и объединение X/>Iравно универсальному множеству I.
На основанииэтих рассуждений легко определить дополнение множества Xкак />. Двойное дополнение />=X.
Спомощью операции дополнения можно в удобном виде представить разность множеств
/>
т. е.
/>
Многиеопределения теории множеств удобно записывать в виде математических выражений,содержащих некоторые логические символы. К числу таких символов относитсясимвол следствия (импликации)/>.Например, запись Х/>У и Y/>Z/>X/>Z(транзитивность) читают так: если X/>Y и У /> Z, то X /> Z.Другие символы связаны с применением кванторов общности и существования.Квантор общности — это операция, которая сопоставляет Р(х) высказыванию:«Все х обладают свойством Р(х)». Для этой операции употребляют знак />(перевернутое латинское А).Например, запись />х(Р(х)/>Q(x)) свидетельствует о том, что все объекты, обладающиесвойством Р(х), обладают и свойством Q(x).
Наряду сквантором общности в теории множеств существует понятие квантора существования,обозначаемого />(перевернутаялатинская буква Е). Например, запись
/>
утверждает,что существует по крайней мере один объект х, обладающий одновременносвойствами Р(х) и Q(x), т. е. Р(х) и Q(x) пересекаются: Р(х) />Q(x)/>0.
В теориимножеств часто пользуются понятием логической эквивалентности, обозначаемой/>. Например, запись
/>
нужночитать: «Выполнение условий X/>Yи Y/>X, тoже самое что X= У».
Пример1. Доказать с помощью тождественных преобразований равенство (X/>У) />Z= (X/>Z) /> (У/> Z) и показать с помощью диаграмм его коммутативные свойства.
Решение.Это равенство известно как тождество дистрибутивности операций над множествами.Чтобы убедиться в справедливости этого тождества, положим />. Тогда одновременно/> и />, что возможно в случае,когда />или />, т. е. />.Отсюда можнозаключить, что />.Аналогичнодоказывается соотношение />. Всоответствии с определением равенства множеств приходим к требуемому тождеству.
На рис.4, а показан набор исходных множеств X, У и Z, а на рис. 4, б, в— комбинация множеств в соответствии свыражениями /> и />.
Внутренниеобласти, ограниченные жирными линиями, совпадают. Можно проследить, чтооперации над множествами по их объединению или пересечению обладают такжекоммутативностью и ассоциативностью.
Отношениямножеств. Виды отношений и их свойства
Элементымножества, как правило, находятся в каком-либо отношении друг относительнодруга. Эти отношения можно задать в виде неполных предложений — предикатов,например, «меньше, чем...», «больше, чем ...», «эквивалентно», «конгруэнтно» ит. п.
Тотфакт, что некоторый элемент />находитсяв каком-либо отношении к элементу того же множества xj, математически записывают как XiRxj, где R—символ отношения.
Отношениеиз двух элементов множества Xназываютбинарным. Бинарные отношения множеств Xи Yпредставляютсобой некоторое множество упорядоченных пар (х, у), образованныхдекартовым произведением XхY. В общем случае можно говорить не только о множествеупорядоченных пар, но и о множестве упорядоченных троек, четверок элементов ит. д., т. е. о парных отношениях, получаемых в результате декартовапроизведения />, где п— размерность n-строчек.
Рассмотримосновные виды отношений — отношения эквивалентности, порядка и доминирования.
Некоторыеэлементы множеств можно считать эквивалентными в том случае, когда любой изэтих элементов при определенных условиях можно заменить другим, т. е. данныеэлементы находятся вот-ношении эквивалентности. Примерами отношенийэквивалентности являются отношения параллельности на множестве прямыхкакой-либо плоскости; подобия на множестве треугольников; принадлежности кодной функциональной группе микросхем или к одному классу типоразмеров и т. д.
Термин«отношение эквивалентности» будем применять при выполнении следующих условий:
1)каждый элемент эквивалентен самому себе;
2)высказывание, что два элемента являются эквивалентными, не требует уточнениятого, какой из элементов рассматривается первым, а какой вторым;
3) дваэлемента, эквивалентные третьему, эквивалентны между собой.
Введемдля обозначения эквивалентности символ ~, тогда рассмотренные условия можнозаписать следующим образом:
1) х~ х (рефлективность);
2) х~ у/>у ~ х (симметричность);
3) х~ у и у ~ z/>х ~ z(транзитивность).
Следовательно,отношение Rназывают отношением эквивалентности,если оно рефлексивно, симметрично и транзитивно.
Пустьнекоторому элементу х /> X эквивалентно некоторое подмножествоэлементов А /> X, тогда это подмножество образует класс эквивалентности,эквивалентный х. Очевидно, что все элементы одного и того же классаэквивалентности эквивалентны между собой (свойство транзитивности). Тогдавсякий элемент х/>Х можетнаходиться в одном и только одном классе эквивалентности, т. е. в этом случаемножество Xразбивается на некотороенепересекающееся подмножество классов эквивалентности />, где J— некоторое множество индексов.
Такимобразом, каждому отношению эквивалентности на множестве Xсоответствует некоторое разбиениемножества Xна классы />.
Частосталкиваются с отношениями, которые определяют некоторый порядок расположенияэлементов множества. Например, в процессе автоматизированного конструированиятребуется вводить множество одних исходных данных раньше или позже, чеммножество других. При этом может оказаться, что элементы одного множествабольше или меньше элементов другого и т. д. Во всех этих случаях можнорасположить элементы множества Xилигруппы элементов в некотором порядке (например, в виде убывающей иливозрастающей последовательности), т. е. ввести отношение порядка на множестве X.
Различаютотношения строгого порядка, для которых применяют символы /> и отношения нестрогогопорядка, где используют символы />. Этиотношения характеризуются следующими свойствами:
дляотношения строгого порядка:
хX— ложно (антирефлексивность);
х—взаимоисключаются (несимметричность);
xу x/> xz— (транзитивность);
дляотношения нестрогого порядка:
х />X— истинно (рефлексивность);
х/>у и у/>х /> х = у — (антисимметричность);
х /> у и у /> z/>xу /> z— (транзитивность).
МножествоXназывают упорядоченным, если любыедва элемента х и у этого множества сравнимы, т. е. если для нихвыполняется одно из условий: х у, х = у, у х.
Упорядоченноемножество называют кортежем. В общем случае кортеж — это последовательностьэлементов, т. е. совокупность элементов, в которой каждый элемент занимаетвполне определенное место. Элементы упорядоченного множества называютсякомпонентами кортежа. Примерами кортежа может служить упорядоченнаяпоследовательность чисел арифметической или геометрической прогрессий,последовательность технологических операций при изготовлении какого-либорадиоэлектронного изделия, упорядоченная последовательность установочныхпозиций печатной платы для закрепления конструктивных элементов.
Во всехэтих множествах место каждого элемента вполне определено и не может произвольноизменяться.
Приобработке конструкторской информации на ЭВМ часто используют отношениядоминирования. Говорят, что х/>Xдоминирует над у/>X, т. е. х>>у, если элемент х вчем-либо превосходит (имеет приоритет) элемент у того же множества.Например, под х можно понимать один из списков данных, который должен поступитьна обработку первым. При анализе нескольких конструкций РЭА какой-либо из нихдолжен быть отдан приоритет, так как эта конструкция обладает лучшими, с нашейточки зрения, свойствами, чем другие, т. е. конструкция х доминирует надконструкцией у.
Свойствотранзитивности при этом не имеет места. Действительно, если, например,конструкцию х по каким-либо одним параметрам предпочли конструкции у,а конструкцию у по каким-либо другим параметрам предпочликонструкции z, то отсюда еще не следует, что конструкциих должно быть отдано предпочтение по сравнению с конструкцией г.
Отображениемножеств. Одним из основных понятий теории множеств является понятиеотображения. Если заданы два непустых множества Xи Y, то закон,согласно которому каждому элементу x/>Xставится в соответствие элемента/>, называютоднозначным отображением XвYили функцией, определенной на X и принимающей значение на Y.
Напрактике приходится иметь дело и с многозначными отображениями множества Xна множестве Y, которые определяют закон, согласно которому каждомуэлементу х/>Xставится в соответствие некотороеподмножество />, называемое образомэлементов. Возможны случаи, когда Гх = 0.
Пустьзадано некоторое подмножество А/>X. Для любого х/>Аобразом х является подмножество />.Совокупность всех элементов Y, являющихсяобразами для всех х в А, назовем образом множества А и будемобозначать ГА. В этом случае />