Министерство образования Республики Беларусь
Реферат на тему
МАТЕМАТИЧЕСКИЕ МЕТОДЫ ОПИСАНИЯ МОДЕЛЕЙ КОНСТРУКЦИЙ РЭА
Минск 2010
ВВЕДЕНИЕ
Применение вычислительных машин на этапе конструирования РЭА по-новому ставит задачи разработки математических моделей и методов их анализа и оптимизации. Отличительной чертой в постановке этих задач является максимальная формализация математических описаний и использование для отыскивания оптимальных решений аппарата математического программирования.
В общем случае под математической моделью конструкции понимают систему математических соотношений, описывающих с требуемой точностью изучаемый объект и его поведение в реальных условиях. Процесс составления математических моделей называют математическим моделированием. В основу математического моделирования положен принцип идентичности формы уравнений и однозначности соотношений между переменными в уравнениях оригинала и модели, т. е. принцип аналогии объекта с моделью. При составлении математических моделей могут использоваться различные математические средства описания объекта — дифференциальные или интегральные уравнения, теория множеств, теория графов, теория вероятностей, математическая логика и др. Особое место в математическом моделировании занимает квазианалоговое моделирование, суть которого состоит в изучении не исследуемого объекта, а объекта иной физической природы, но описываемого математическими соотношениями, эквивалентными относительно получаемого результата.
В данной главе рассмотрены вопросы применения теории множеств и теории графов, а также методов конечно-разностных аппроксимаций для описания конструкций РЭА и моделирования протекающих в них процессов.
ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ МНОЖЕСТВ
Определения. Математические методы, положенные в основу алгоритмических процессов конструирования РЭА, а также процессы организации входной и выходной информации о проектируемом объекте широко используют понятия и символы теории множеств.
Под множеством понимают совокупность объектов любой природы, называемых элементами данного множества, обладающих каким-либо общим для множества свойством. Как основное понятие теории понятие множества не подлежит логическому определению.
Элементы множества могут иметь самую различную природу. Например, можно говорить о множестве микросхем, входящих в определенную конструкцию РЭА, или о множестве чертежей, входящих в полный комплект конструкторской документации для производства какого-либо изделия, и т. д.
Множества обозначают заглавными буквами латинского алфавита: X, Y
,
Z
,
а элементы множеств — соответствующими строчными буквами того же алфавита: х, у,
z
или строчными буквами с индексами: х1,
x
2
,…
y
1
, у2
,…
Равенство X = {
x
1
,
x
2
,
..., хп
}
свидетельствует о том, что элементы х1
, х2
,
..., хп
являются элементами множества X.
Множество можно задавать не только перечислением его элементов, но и с помощью описательного способа, указывающего характерное свойство, которым обладают все элементы этого множества. Например, если во всем множестве X микросхем электронного блока сложной радиоаппаратуры есть некоторое множество А
гибридных интегральных схем, то это можно записать следующим образом: А
= {х
Х:х — гибридная интегральная схема}, что читается так: множество А
состоит из элементов х
множества X, обладающих тем свойством, что х
является гибридной интегральной схемой. Здесь введено новое обозначение
, означающее, что объект х
является элементом множества X. Если же некоторый объект у
не принадлежит множеству Х
то это условие записывают в виде у
X.
В том случае, когда не вызывает сомнения, из какого множества берутся элементы х,
принадлежность их к множеству X можно не указывать. Например, если известно, что множество гибридных интегральных схем входит во множество микросхем того же самого электронного блока, то можно записать А —
{х
: х
— гибридная интегральная схема}.
Число элементов множества X = {}
называют мощностью этого множества и обозначают прямыми скобками, например |Х| = п.
Если число элементов множества X конечно, то такое множество называют конечным. В противном случае множество будет бесконечным. В теории множеств вводится понятие пустого множества, в котором не содержится ни одного элемента. Пустое множество обозначают специальным символом Ø.
Так, например, если множество X пусто, то пишут X
= Ø.
Последовательность из п
элементов множества называют n-строкой. В отличие от обычного множества, где порядок элементов безразличен, в n-строке обязательно задается их определенная последовательность.
Множество X равно множеству Y
,
если оба эти множества состоят из одних и тех же элементов. Если множество X полностью содержится во множестве Y
и при этом |Х|<|Y
|,
то говорят, что множество X
является подмножеством множества Y
:
X
Y
.
В случае когда XY
иодновременно 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
= XU У. Если рассматривают объединение нескольких множеств, то запись примет вид
где 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
и Y
2
показано в виде заштрихованной области множества паросочетаний.
Декартово произведение двух множеств используют для исследования всевозможных паросочетаний. Декартово произведение нескольких множеств
представляет собой множество r-строчек, каждая из которых образуется упорядоченной композицией элементов исходных множеств, т. е. zS
= (
x
1
f
,
x
2
j
,
..., xrk
).
Операция декартова произведения множеств не обладает переместительным свойством, т. е. XY
Y
X.
Разбиением множествах называют такое множество множеств {Xj}, где jJ
,
а J — некоторое множество индексов j, при котором:
1) Xj
X
при всех jJ
;
2) Xj
0
при всех jJ
;
3)
Xi
Xj
=
0
при jJ
;
4) Xj
=
X
.
Ряд прикладных задач разбиения множества конструктивных элементов высокого уровня на элементы более низкого уровня (например, задача разбиения множества микросхем блока РЭА на отдельные субблоки) сводится к операциям разбиения множеств. Конкретные решения подобных задач рассмотрены в гл. 4.
Понятие пустого множества 0
аналогично нулю в алгебре чисел. Действительно, если для любого числа а
справедливо а
0 = 0 и а+0 = а,
то для любого. множества X
справедливо X
0 = 0
и X
0 =Х.
Введем понятие множества I, соответствующее единице в алгебре чисел. Такое множество должно обладать тем свойством, что пересечение с ним любого множества X
дает в результате это же множество X
,
т. е. X
I
= X
по аналогии с а
1 = а.
Множество I
, обладающее этим свойством называют универсальным или единичным множеством. В общем случае, если при некотором р
, то это самое большое множество и является универсальным.
В конкретных приложениях в качестве универсального множества могут использоваться различные общие подмножества. Например, среди множества комплектов конструкторских документов на изготовление изделий РЭА полный комплект конструкторских документов является универсальным множеством этих документов или когда при рассмотрении множеств микросхем отдельных субблоков РЭА выделяют универсальное множество таких микросхем на всю данную радиоэлектронную аппаратуру в целом.
Универсальное множество обладает свойством, не имеющим аналога в алгебре чисел, а именно для любого множества X
справедливо соотношение X
I
= I
.
В объединение этих множеств должны входить как элементы множества X, так и дополняющие элементы множества I
. Но, в свою очередь, все элементы множества X
входят в универсальное множество I
, поэтому и объединение XI
равно универсальному множеству I
.
На основании этих рассуждений легко определить дополнение множества X
как .
Двойное дополнение = X
.
С помощью операции дополнения можно в удобном виде представить разность множеств
т. е.
Многие определения теории множеств удобно записывать в виде математических выражений, содержащих некоторые логические символы. К числу таких символов относится символ следствия (импликации). Например, запись ХУ и Y
Z
X
Z
(транзитивность) читают так: если XY и У Z, то XZ. Другие символы связаны с применением кванторов общности и существования. Квантор общности — это операция, которая сопоставляет Р(х)
высказыванию: «Все х
обладают свойством Р(х)». Для этой операции употребляют знак (перевернутое латинское А).
Например, запись х(Р(х)Q
(
x
))
свидетельствует о том, что все объекты, обладающие свойством Р(х),
обладают и свойством Q
(
x
).
Наряду с квантором общности в теории множеств существует понятие квантора существования, обозначаемого (перевернутая латинская буква Е).
Например, запись
утверждает, что существует по крайней мере один объект х,
обладающий одновременно свойствами Р(х)
и Q
(
x
),
т. е. Р(х)
и Q
(
x
)
пересекаются: Р(х) Q(x)0.
В теории множеств часто пользуются понятием логической эквивалентности, обозначаемой. Например, запись
нужно читать: «Выполнение условий X
Y
и
YX
,
т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
x
<
z
— (транзитивность);
для отношения нестрогого порядка:
х
X— истинно (рефлексивность);
ху и ух х = у
— (антисимметричность);
х у и у
z
x
у
z
— (транзитивность).
Множество X
называют упорядоченным, если любые два элемента х
и у
этого множества сравнимы, т. е. если для них выполняется одно из условий: х
< у, х
= у, у
< х.
Упорядоченное множество называют кортежем. В общем случае кортеж — это последовательность элементов, т. е. совокупность элементов, в которой каждый элемент занимает вполне определенное место. Элементы упорядоченного множества называются компонентами кортежа. Примерами кортежа может служить упорядоченная последовательность чисел арифметической или геометрической прогрессий, последовательность технологических операций при изготовлении какого-либо радиоэлектронного изделия, упорядоченная последовательность установочных позиций печатной платы для закрепления конструктивных элементов.
Во всех этих множествах место каждого элемента вполне определено и не может произвольно изменяться.
При обработке конструкторской информации на ЭВМ часто используют отношения доминирования. Говорят, что х
X
доминирует над у
X
,
т. е. х>>у,
если элемент х
в чем-либо превосходит (имеет приоритет) элемент у
того же множества. Например, под х
можно понимать один из списков данных, который должен поступить на обработку первым. При анализе нескольких конструкций РЭА какой-либо из них должен быть отдан приоритет, так как эта конструкция обладает лучшими, с нашей точки зрения, свойствами, чем другие, т. е. конструкция х
доминирует над конструкцией у.
Свойство транзитивности при этом не имеет места. Действительно, если, например, конструкцию х
по каким-либо одним параметрам предпочли конструкции у,
а конструкцию у
по каким-либо другим параметрам предпочли конструкции z, то отсюда еще не следует, что конструкции х
должно быть отдано предпочтение по сравнению с конструкцией г.
Отображение множеств. Одним из основных понятий теории множеств является понятие отображения. Если заданы два непустых множества X
и Y
,
то закон, согласно которому каждому элементу xX
ставится в соответствие элемента,
называют однозначным отображением X
в Y
или функцией, определенной на X и принимающей значение на Y
.
На практике приходится иметь дело и с многозначными отображениями множества X
на множестве Y
,
которые определяют закон, согласно которому каждому элементу х
X
ставится в соответствие некоторое подмножество ,
называемое образом элементов. Возможны случаи, когда Гх = 0.
Пусть задано некоторое подмножество А
X
.
Для любого хА
образом х
является подмножество .
Совокупность всех элементов Y
,
являющихся образами для всех х в А,
назовем образом множества А
и будем обозначать ГА.
В этом случае