ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ МНОЖЕСТВ

Реферат на тему

МАТЕМАТИЧЕСКИЕ МЕТОДЫ ОПИСАНИЯ МОДЕЛЕЙ КОНСТРУКЦИЙ РЭА

 

 

Минск 2010

ВВЕДЕНИЕ

Применение вычислительных машин на этапе конструирования РЭА по-новому ставит задачи разработки математических моделей и методов их анализа и оптимизации. Отличительной чертой в постановке этих задач является максимальная формализация математических описаний и использование для отыскивания оптимальных решений аппарата математического программирования.

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

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

ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ МНОЖЕСТВ

 

Определения. Математические методы, положенные в основу алгоритмических процессов конструирования РЭА, а также процессы организации входной и выходной информации о проектируемом объекте широко используют понятия и символы теории множеств.

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

Элементы множества могут иметь самую различную природу. Например, можно говорить о множестве микросхем, входящих в определенную конструкцию РЭА, или о множестве чертежей, входящих в полный комплект конструкторской документации для производства какого-либо изделия, и т. д.

Множества обозначают заглавными буквами латинского алфавита: X, Y , Z , а элементы множеств — соответствующими строчными буквами того же алфавита: х, у, z или строчными буквами с индексами: х_1, x ₂ ,… y ₁ , у₂,… Равенство X = { x ₁ , x ₂ , ..., х_п} свидетельствует о том, что элементы х₁, х₂, ..., х_п являются элементами множества 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 . Если рассматривают пересечение нескольких множеств Х₁, Х₂, ..., Х_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 декартово произведение множеств Х₁ и Y ₂ показано в виде заштрихованной области множества паросочетаний.

Декартово произведение двух множеств используют для исследования всевозможных паросочетаний. Декартово произведение нескольких множеств

 

 

представляет собой множество r-строчек, каждая из которых образуется упорядоченной композицией элементов исходных множеств, т. е. z_S = ( x _{1 f} , x ₂ j , ..., x_rk ). Операция декартова произведения множеств не обладает переместительным свойством, т. е. X  Y  Y  X.

Разбиением множествах называют такое множество множеств {Xj}, где j J , а J — некоторое множество индексов j, при котором:

 

1) Xj X при всех j J ;

 2) Xj  0 при всех j J ;

3) X_i X_{j =} 0 при j J ;

4) X_j = 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, б, в— комбинация множеств в соответствии с выражениями  и .

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