Міністерство освіти Республіки Білорусь
Реферат на тему
МАТЕМАТИЧНІ МЕТОДИ ОПИСУ МОДЕЛЕЙ КОНСТРУКЦІЙ РЕА
Мінськ 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. У разі коли 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 і Y 2 показано у вигляді заштрихованої області безлічі паросполучення.
Декартовій твір двох множин використовують для дослідження всіляких паросполучення. Декартовій твір кількох множин
являє собою безліч r-рядків, кожна з яких утворюється впорядкованої композицією елементів вихідних множин, тобто z S = (x 1 f, x 2 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, б, в-комбінація множин відповідно до виразами і
.
Внутрішні області, обмежені жирними лініями, збігаються. Можна простежити, що операції над множинами за їх об'єднання чи перетинанню мають також комутативність і асоціативністю.
Відносини множин. Види відносин та їх властивості
Елементи множини, як правило, знаходяться в будь-якому відношенні один щодо одного. Ці відносини можна задати у вигляді неповних пропозицій - предикатів, наприклад, «менше, ніж ...»,« більше, ніж ...», «еквівалентно», «конгруентно» і т. п.
Той факт, що деякий елемент знаходиться в будь-якому відношенні до елемента того ж множини x j, математично записують як 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, то закон, згідно з яким кожному елементу x X ставиться у відповідність елементу
, Називають однозначним відображенням X в Y або функцією, визначеною на X та приймаючої значення на Y.
На практиці доводиться мати справу і з багатозначними відображеннями множини X на безлічі Y, які визначають закон, згідно з яким кожному елементу х X ставиться у відповідність деякий підмножина
, Зване чином елементів. Можливі випадки, коли Гх = 0.
Нехай задано деяку підмножину А X. Для будь-якого х
А чином х є підмножина
. Сукупність усіх елементів Y, які є образами для всіх х в А, назвемо чином безлічі А і будемо позначати ГА. У цьому випадку