Лекція 1. Множини і функції

Вступна лекція

 

Курс лекцій, що вам пропонується, носить назву “Основи дискретної математики”. Що приховує ця назва, тобто що Ви будете вивчати і задля якої мети?

Дискретна математика – складова частина математики, що з найдавніших часів розробляє засоби дослідження дискретних процесів і систем. Звичайно у визначенні предмета дискретної математики звучить властивість “дискретності” як антипод “неперервності”.

Математиці, і в тому числі дискретній математиці, належить велика роль у розвитку науки. Пра­к­ти­ч­но всі галузі науки і техніки підпадають під вплив математики. Це пов'язано з тим, що математика є засобом формалізації знання. Кожна галузь науки вивчає свої об'єкти, але існують підходи і принципи, що об'єднують науку. Один із загаль­но ­ме­то­до­ло­гіч­них підходів науки – моделювання, тобто дослідження об'єктів за допомогою інших об'єктів, що нази­ва­ю­ть­ся моделями. Так, перш ніж будувати запроектований літак реальних розмірів, ство­рю­є­ть­ся і досліджується його маленька модель. Це приклад фізичного моделю­ван­ня, коли модель повторює суть і форму процесів досліджуваного об'єкта. Однак модель може повторювати тіль­ки форму процесів досліджуваного об'єкта. Така модель називається фор­ма­ль­ною чи ма­те­ма­тичною, і її переваги полягають в тому, що вона може бути спільною для об'єктів до­слі­д­­ження різних наук, добре вивченою, дешевою, такою що дозволяє широкий вибір різнома­ніт­них режимів до­слід­ження, вимагає менше часу на дослідження.

Звідки ж випливає необхідність вивчення дискретної математики інженерами з комп’ютеризованих систе­м зі спеціальності “Системи управління і автоматики”?

Відомо, що з комп'ютеризованими системами в керуванні, проектуванні й інших сфе­рах діяльності людини, зокрема, автоматизованими системами керування технологічними процесами (АСКТП), автоматизованими системами керування (АСК), автома­ти­зо­ваними системами обробки інформації і керування (АСОІК), системами автоматизації про­ек­ту­вання (САПР), інформаційно-керуючими системами (ІКС), інформа­цій­но-пошуко­ви­ми си­сте­мами (ІПС), автоматизованими інформаційними системами (АІС) тощо, пов'язана ре­а­лізація кібернетичного підходу до керування з використанням комп'ю­терів. Кібернетика – наука, що вивчає задачі керування і зв'язку в різних об'єктах як живих, так і неживих. Фун­да­тор кібернетики Норберт Вінер увів нову категорію “керування”. Сутність принципу керу­ван­ня полягає в тому, що рух і дія великих мас чи передача і перетворення великих кіль­ко­с­тей енергії направляються і контролюються за допомогою невеликих кількостей енергії, що несуть інформацію.

Таким чином, процеси керування пов'язані з та засновані на процесах обробки ін фор­ма­ції. Більш того, останнім часом усе коло питань, пов'язаних з обробкою інформації, фор­мує предмет науки інформатики, що поглинає значну частину проблематики кібернетики.

Реалізація зазначених принципів пов'язана з реалізацією за допомогою комп'ютерної техніки виниклого в кібернетиці представлення про схему керування зі зворотним зв'язком:

ОК - об'єкт керування; СК - система керування; Х - вхідний потік; Y – вихідний потік; W – інформація про стан ОК; V - керуючі впливи; Z – збурюючі впливи

Рис.1. Схема керування зі зворотним зв'язком.

І кібернетика, і інформатика мають як теоретичну, так і практичну спрямованість. Їхня практична сторона – методи побудови систем керування (СК), що забезпечують най­краще, в якомусь сенсі, керування. Їхня теоретична сторона – вивчення закономірностей побудови СК і процесів керування, щонайменше це Ляпунов відносить до кібернетики.

Сформувалися наступних два підходи до вивчення СК:

- макропідхід, коли система розглядається як “чорний ящик”, і дослідник визначає як залежить вихід від входу; це дозволяє підібрати відповідний вхід для досягнення необ­хід­но­го чи найкращого виходу;

- мікропідхід, коли поведінку системи дослідник намагається побудувати на підставі аналізу структури системи, тобто складу і характеру взаємозв'язків її елементів, дослідник створює модель поведінки, потім синтезує й аналізує алгоритм, що забезпечує найкращу поведінку системи, тобто алгоритм керування. З впровадженням у керування комп'ютерів реалізацію моделей і алгоритмів здійснюють у вигляді комп'ютерних програм.

СК на базі комп'ютерної техніки і моделей керування, реалізованих програмно, стано­в­лять собою АСК. Останні, таким чином, є комп'ютеризованими системами, функціонування яких здійснюється у вигляді процесу реалізації системи алгоритмів, послідовність виконання яких залежить від стану ОК. Такий підхід до організації АСК називають алгоритмічним. Отже, в основі реалізації кібернетичного підходу до побудови АСК лежить тріада:

модель алгоритм програма

 

Проектування, впровадження і експлуатація комп’ютеризованих систем вимагають роз­в’язання цілої низки різноманітних проблем, насамперед створення методів і засобів опи­су й аналізу структур і поводження СК й ОК, алгоритмів керування, засобів оцінки продук­тив­ності алгоритмів, засобів опису і створення програм тощо. В сучасному світі глобальної інформатизації до цих проблем залучаються також створення ефективних систем захисту ін­фор­мації, створення і використання глобальних, корпоративних та локальних мереж, створення і підтримка актуальних баз даних нормативного, комерційного призначення тощо.

Дискретна математика забезпечує кібернетику, інформатику і теорію і практику побудови АСК й інших комп'ютеризованих систем відповідними методами. Звідси й випливає необхід­ність включення дисципліни “Основи дискретної математики” в навчальний план підготовки магістрів та інженерів з комп’ютеризованих систе­м зі спеціальності “Системи управління і автоматики”.

На наступному невеликому прикладі розглянемо, як можна реалізувати стадії кібер­не­тич­ного підходу. У регіоні розташовані кілька підприємств, кожне з яких може бути поста­ча­­ль­­ником і спо­живачем деякої продукції. Між деякими (необов'язково усіма) парами під­при­є­мств про­кла­дені транспортні магістралі, що характеризуються відстанню, пропускною зда­тністю то­що. Розглянемо проблеми керування перевезеннями, зокрема, проблему визна­чен­ня най­мен­шо­го за відстанню (найкоротшого) маршруту транспортування вантажу між довіль­ною парою під­при­ємств. Тобто потрібно встановити проміжні пункти (підприємства), через які пря­мує вантаж і при цьому формується найкоротший маршрут доставки вантажу між обраною парою під­при­ємств.

По-перше, необхідно мати модель системи перевезень. Найпростіший вихід – вико­ри­стан­ня плану магі­стра­лей на місцевості. Але план містить безліч непотрібних деталей. Щоб по­збутися їх, треба залишити тільки факт наявності пункту (підприємства) і магістралі. Ви­ни­кає об'єкт, який можна представити графічно, у вигляді, наведеному на рис.2 (будемо вважати, що він відповідає конкретним вхідним даним нашої проблеми).

Тут підприємствам відповідають позначені літерами A, B, C, D та E точки площини. При­чому ми їх позначаємо, щоб не втратити зв'язок з реальними підприємствами. А наяв­нос­ті транспортної магістралі між парою підприємств відповідає лінія між точками, що відпо­ві­да­ють цим підприємствам.

 

E

C

A

 

 

 

Рис 2.

Цей об'єкт називають графом, заданим геометричним способом. Tочки і лінії нази­ва­ють відповідно вершинами і ребрами. Тоді граф – модель системи перевезень. Розглянемо докладніше граф з цієї точки зору. У графі збережена лише наявність магістралі (у вигляді ребра) між парою вершин, але не її форма. Форма магістралі на плані з урахуванням мас­шта­бу давала можливість зберегти деякі характеристики магістралей, наприклад, відстань. З іншого боку, на плані вже не можна установити пропускну здатність магістралі, якщо не вказати це явно. Таким чином, задати цю характеристику магістралей можна на графі в явному вигляді. Тоді ми одержимо об'єкт, який вже не називають графом. Це вже інший об'єкт дискретного аналізу – мережа. Відстань на графі також потрібно вказувати явно. Тоді ми також одержимо новий об'єкт дискретного аналізу, який звичайно називають зваженим графом. Приклад зваженого графа наведений на рис.3. Кожне ребро характеризується вагою – довжиною відповідної магістралі (відстанню між відповідними підприємствами). Отже, зважений граф на рис.3 зберігає потрібні для розв’язання сформульованої проблеми дані і можна прийняти його за потрібну нам модель.

 

Рис 3.

 

Потім варто створити модель поведінки, тобто модель вибору найкоротшого мар­шру­ту. Будемо позначати ребро, що зв'язує вершини X і Y, парою літер XY. Маршрутом у графі на­зивають послідовність ребер, у якій позначення попереднього ребра закінчується, а поз­на­чен­ня наступного ребра починається з тієї ж літери (природно, жодних дві точки не повинні бути позначені тією ж літерою). Модель поведінки змістовно можна сформулювати в такий спосіб: знайти маршрут з вершини X у вершину Y, сума ваг ребер якого мінімальна серед усіх маршрутів з вершини X у вершину Y.

Для математика все сказане вище означає, що змістовно сформульовано задачу. Він мо­же сфор­му­лювати її чіткіше, використовуючи математичну символіку в більш стислому вигляді, говорять формально поставити задачу, наприклад у вигляді:

де М_i - маршрут i між заданою парою вершин;

{М_i} - множина усіх маршрутів між заданою парою вершин;

p_xy - вага ребра XY маршруту М_i.

Друга стадія полягає в створенні методу розв’язання поставленої задачі. Засто­су­Ван­ня методу розв’язання до вхідних даних (наведеного зваженого графа) і реалізація резуль­та­тів і забезпечать найкращу поведінку. Нехай потрібно визначити найкоротший маршрут з вершини А в вершину Е. Можна було б перебрати всі маршрути, визначити суми їхніх ваг і вибрати маршрут, якому відповідає найменша сума, визначена вище. Наприклад, з маршру­тів АВ, ВЕ й АD, DC, CE вигідніший другий маршрут. Однак вже в нашому прикладі по­тріб­но порівняти п'ять маршрутів, а в більш складних випадках число маршрутів різко зростає. Тому дискретний аналіз ставить не просто проблему визначення методу розв’язання, але проблему створення методу, що працює краще, звичайно швидше інших. Будемо записувати метод розв’язання у вигляді послідовності дій, що повинні бути виконані тим, хто розв’язує задачу. Така послідовність дій звичайно називається алгоритмом. Більш зручним у цьому відношенні буде наступний алгоритм:

Крок 1. Вершині, що відповідає пункту відправлення, приписуємо вагу 0.

Крок 2. Кожній вершині, зв'язаної ребром з вершиною кроку 1, приписуємо відстань, рівну вазі ребра. Позначаємо відстань першою літерою з позначення ребра. Включаємо вер­ши­ни, відстань до яких визначено на кроці 2, у список перегляду в довільному порядку.

Крок 3. Вибираємо зі списку перегляду чергову вершину Z. Визначаємо вершини, з якими вершина Z зв'язана ребрами, приписуємо до списку перегляду ті з них, що у списку не містяться (вершину, що відповідає пункту призначення, у список не включаємо). Для кожної знайденої вершини визначаємо відстань, додаючи вагу відповідного ребра до відстані вер­шини Z. Якщо для вершини відстань вже визначалася раніше, і нова відстань менше, то приписуємо їй нову відстань і позначаємо її літерою Z. Якщо нова відстань не менше, то залишаємо вершину без змін. Якщо вершині раніше відстань не приписувалася, то приписуємо їй визначеним чином відстань і позначаємо її літерою Z. Викреслюємо Z зі списку перегляду.

Крок 4. Якщо список перегляду не порожній, то переходимо до кроку 3, інакше – до кроку 5.

Крок 5. Відновлюємо маршрут по оцінках відстаней, рухаючись по ребрах графа від вершини, що відповідає пункту призначення, до вершини, що відповідає пункту від­прав­лення, використовуючи позначки відстаней, приписаних вершинам.

Робота алгоритму для визначення найкоротшого маршруту з пункту А в пункт Е моделі показана на рис 4 – 8.

	B(5,A)

		E

 

C(4,A)

A(0)

 

	D(3,A) Список: B,C,D

 

Рис. 4

 

 

 

Список: C,D

Рис 5.

 

Список: D

Рис 6.

Список: C

Рис 7.

 

Список порожній

Рис 8.

 

Легко відновити найкоротший маршрут: AD,DC,CE.

Заключна стадія – складання і використання програми – нами не розглядається, але піз­ніше Ви переконаєтеся, що цей алгоритм можна запрограмувати мовами Паскаль, Сі й ін­шими. Ди­скретний аналіз забезпечує засоби для полегшення процесу програмування, ство­рен­ня більш ефективних програм.

Розмаїтість об'єктів керування вимагає розмаїтості використовуваних для моделю­вання, алгоритмізації і програмування засобів і методів дискретної математики, але послідов­ність стадій залишається незмінною.

Отже, основна наша мета – оволодіння набором засобів і методів дискретного аналізу, достатніх для реалізації кібернетичного підходу при створенні АСК для різно­маніт­них об'єктів керування, реалізації ефективних систем збору, передачі, оброблення, відображення, збереження, розподілення і захисту інформації.

Як відібрати достатній набір засобів і методів? Дискретна математика розвивалася одно­ча­с­но з розвитком кібернетики, розширенням впровадження комп'ютерів у керування. Сьогодні ди­скретна математика становить величезну область. Так, до вже сформованих розді­лів, таких як тео­рія чисел, алгебра, алгебра логіки, теорія графів, теорія алгоритмів, пізніше додалися те­о­рія формальних систем, комбінаторний аналіз, цілочисельне прог­рамування, тео­рія автоматів, теорія граматик, теорія кодування й інші. До того ж значно змінилися традиційні розділи дискретної математики.

Більш того, у кібернетиці й теорії управління усе більш рішуче заявляє про свої права новий напрямок – штуч­ний інтелект (ШІ). Це пов'язане з тим, що взагалі в науці відбувається переорієнтація на напрямки, пов'язані з вивченням людини, полегшенням її праці. У кібернетиці і комп'ю­терних системах це явище виразилося в створенні комп'ютерів, моделей і програмних сис­тем, що імітують мислення людини, її логічну діяльність. Виявилося, що для цього необхідно навчити комп'ютер усвідомлювати ситуації навколишнього світу, оцінювати їх і вчинені при цьому дії, вибирати ті дії, що ведуть до мети, навчатися, тобто здобувати знання для наступного використання.

Таким чином, якщо система створюється як інтелектуальна система, вона повинна опиратися на апарат представлення знань і пошуку рішень у базі знань. У цьому випадку традиційний алгоритмічний підхід доповнює схеми виведення. Мовні проблеми в інтелек­ту­а­­льних системах вирішують із залученням фундаментальних понять змісту і цінності мовних конструкцій. Область дискретної математики істотно розширилася, у ній з'явилися відповідні засоби – теорія виведення, граматики із семантикою тощо.

Зважаючи на усталені і сьогодні створювані напрямки дискретної математики, їх роль у створенні комп’ютеризованних систем керування, реалізації інформаційних процесів, беручи до уваги важливість порядку подачі матеріалу, до цьому курсу залучені такі розділи:

1. Проблематика і взаємозв'язок розділів курсу.

2. Вступ до алгебраїчних систем.

3. Теорія графів і мереж.

4. Теорія граматик.

5. Теорія автоматів.

6. Вступ до математичної логіки.

Матеріал зазначених розділів дозволяє відібрати набір засобів і методів математичного моделювання дискретних систем і процесів. Зокрема, засоби моделювання розглядаються в розділах 1-3,5. Засоби для розв’язання мовних проблем розглядаються в розділах 4,5.

Засоби реалізації алгоритмічного підходу будуть розглядатися в курсі “Алго­рит­міка”, що читається в 4-му семестрі. Теорія алгоритмів виникла після того, як з'явилося поняття нерозв'язуваності про­б­лем, коли численні невдалі спроби рішення відомих масових проблем зміцнили математиків у прагненні довести, що відповідних алгоритмів для рішення цих проблем узагалі не існує. Уся множина проблем розділяється на розв'язувані і нерозв'язувані, тобто на ті, котрі мають алгоритм і ті, котрі алгоритмів не мають. Для доведення нерозв'язуваності проблеми необ­хід­не точне визначення алгоритму, оскільки неможливо довести існування чи не існування того, що не визначено.

Точне визначення алгоритму було першою проблемою теорії алгоритмів. У 30 - 40-х роках А.Т'юрінгом, Е.Постом, А.Черчем, а пізніше А.А.Марковим і С.Кліні були запро­поновані уточнення до визначення алгоритму і розроблені перші методи доведення нерозв'язуваності масових проблем.

Коли комп'ютери почали впроваджувати в сферу керування, постала необхідність подальшого розбиття множини розв'язуваних проблем, оскільки склалося так, що з прак­тич­ної точки зору існування алгоритму не завжди дає рішення в прийнятний час в умовах обмеженості часу і ресурсів.

На основі теорії алгоритмів сформувалися теорія складності, теорія NP-повноти і теорія зведення, метою яких була оцінка алгоритмів і проблем, розбиття множини розв'я­зу­ва­них проблем на “гарні” і “погані” і побудова ієрархії “поганих” проблем. Подальший розви­ток теорії алгоритмів пов'язаний з автоматизацією конструювання алгоритмів. У теорії алго­рит­мів з'явився напрямок “Прикладна теорія алгоритмів” чи “Алгоритміка”.

Усе це обумовлює включення теорії алгоритмів у окремий курс лекцій. Необхідні для розвитку систем ШІ методи і засоби розглядаються в розділі 6 і, крім того, складуть предмет згаданого вище курсу “Алгоритміка”.

Крім основної мети, що полягає у формуванні фундаменту дискретної математики, необхідного для інженера з комп’ютеризованих систем, ми поставимо перед собою й інші цілі:

- по-перше, покажемо, які прикладні проблеми формалізації реальних об'єктів обумовили появу тих чи інших засобів дискретної математики;

- по-друге, приділимо увагу суті математичного методу і його сприятливому впливу на ідеї функціонування комп'ютеризованих систем;

- по-третє, продемонструємо на прикладі дискретної математики спільність багатьох проблем логіки, лінгвістики, кібернетики;

- по-четверте, проілюструємо будову дискретної математики як складного комплексу, здатного до синтезу й аксіоматизації.

Побажаємо успіхів у вивченні матеріалу курсу, що не тільки збагатить Вас новими знаннями й ідеями, але й, віриться, принесе інтелектуальне задоволення, відточить здатність маніпулювати алгебраїчними і геометричними образами реальних об'єктів і процесів.

Насамкінець, варто зазначити, що матеріал нашого курсу пов'язаний фактично з усіма загальноосвітніми дисциплінами навчального плану підготовки бакалаврів «Комп'ю­тер­изовані системи, керування і автоматика».

 

РОЗДІЛ 1. ПРОБЛЕМАТИКА І ВЗАЄМОЗВ’ЗОК РОЗДІЛІВ КУРСУ: ПЕРЕДУМОВИ, РІШЕННЯ, ПЕРСПЕКТИВИ.

 

У першому розділі в розрізі сформульованих потребами розвитку теорії проектування й експлуатації комп'ютеризованих систем проблем розглянуті запропоновані дискретною математикою моделі, засоби і методи, їхній взаємозв'язок у загальній схемі створення комп'ютеризованих систем і в пропонованому курсі.

 

ТЕМА 1. Загальний аналіз засобів моделювання дискретної математики

Тема присвячена знайомству з фундаментальними об’єктами дискретної математики – множинами і операціями над ними, функціям та відношенням. Ми введемо відповідні означення, розглянемо важливі класи функцій та відношень, проаналізуємо їх властивості. Насамкінець розглянемо теоретичні основи застосування теорії відношень в сучасних системах керування базами даних.

Лекція 1. Множини і функції

У цій лекції будуть розглянуті фундаментальні поняття дискретної математики, що дозволяють моделювати реальні об'єкти і системи, їхню структуру і поведінку.

1. Множини. Одна з найважливіших умов працездатності кібернетичного підходу – комплексний погляд на проблему керування будь-яким об'єктом, процесом. У першу чергу, це виявляється в уявленнях про ОК як про систему. Звідси випливає необ­хідність нормаль­них уявлень про системи. Яке б визначення системи ми не взяли, скрізь, насамперед, гово­рить­ся про сукупність елементів.

Математики уявлення про сукупність вклали в один з найважливіших об'єктів мате­матики – множину. Звичайно, говорячи про множину, мають на увазі поєднання об'єктів, доб­ре розрізнюваних інтуїцією і думкою людини. Узагалі поняття “множина” – первинне поняття і строгого визначення не має, але використання синонімів “сукупність”, “клас”, “юрба” полегшує положення.

Приклади: множина студентів НТУУ “КПІ”, множини літер українського, росій­сько­го чи англійсько­го алфавітів, множина вершин графа, множина ребер графа.

Для полегшення подальшого викладу матеріалу введемо усталену термінологію. Об'єк­ти, що утворюють множину, назвемо елементами множини і будемо позначати малень­ки­ми літерами латинського алфавіту a, b, c,...,x, y, z. Множини будемо позначати ве­ли­ки­ми літерами латинського алфавіту А, B, C,.... Так склалося, що множини, які часто викорис­то­ву­ють­ся, мають закріплені позначення:

N - множина натуральних чисел;

P - множина додатних цілих чисел;

Z - множина додатних і від’ємних цілих чисел, включаючи нуль;

Q - множина раціональних чисел;

R - множина дійсних чисел.

Якщо множина не містить жодного елемента, назвемо її порожньою і позначимо Ø.

Множину, що складається з скінченного числа елементів, назвемо скінченною. Не скінченну множину назвемо нескінченною.

Отже, використовуючи поняття множини, ми маємо можливість формально об'єднати об'єк­ти (елементи), які цікавлять нас, в одне ціле. Однак, часто з тих чи інших міркувань ча­сти­на елементів множини також розглядається як одне ціле. Формально це закріпилося в уявленні про підмножину.

Будь-яку множину S, всі елементи якої належать множині R, назвемо підмножиною множини R і цей факт позначимо символічно S Ì R.

Наприклад, N Ì Z, N Ì Q, якщо М – множина студентів НТУУ “КПІ”, B – множина студентів НТУУ “КПІ” 1-го курсу, то B Ì M.

Якщо S Ì R і допускається, що множина R складається тільки з елементів множини S, то будемо позначати цей факт S Í R. Позначення S Ì R збережемо для випадку, коли мно­жи­на R має елементи, яких немає в множині S (у цьому випадку множину S назвемо власною підмножиною множини R). Якщо множини S і R складаються з тих самих елементів, тобто якщо R Í S і S Í R, то вони рівні, що символічно позначається S = R. У протилежному випадку будемо говорити, що S не дорівнює R і позначати S ¹ R. Рівність множин – певна формалізація уявлень про однаковість множин.

Далі ми часто будемо використовувати підмножини множи­ни, яку назвемо універса­ль­ною і позначимо U. Для цього множину усіх підмножин універсальної множини U по­зна­чи­мо P(U). Звичайно P(U) називають булеаном.

Наприклад, нехай U містить елементи a, b, c. Тоді P(U) містить підмножини Æ і U, а також підмножини, що містять по одному елементу - {a}, {b}, {c}; і підмножини, що містять по два елемента {a,b}, {a,c}, {b,c}. Отже, P(U) у нашому випадку містить 8 елементів, U - 3 елементи. Напрошується висновок про те, що P(U) містить 2ⁿ підмножин, де n - число елементів у множини U.

Дійсно, P(U) складається з 2ⁿ підмножин: Æ, U, S, таких що: 1) Æ Ì S Ì U; 2) S ¹ Æ; 3) S ¹ U.

Множину необхідно вміти задавати, що особливо істотно, якщо працювати з мно­жи­ною повинен комп'ютер. Природно, задати множину можна перерахуванням її елементів. Наприклад, G = {Київ, Харків, Дніпропетровськ, Донецьк, Одеса}, M = {фізика, хімія, ал­геб­ра, економіка, історія}, B = {А, Б, В, Г, Д, Е, Є, Ж, З, І}. Цей спосіб наочний і зручний, якщо множини містять небагато елементів. З ростом числа елементів такий спосіб задання мно­жини втрачає свої переваги, а для нескінченних множин не має застосування.

Інший спосіб задання множин полягає у визначенні властивостей, які мають ті і тільки ті еле­мен­ти, що утворюють множину. Нехай P(x) символічно означає: елемент x має власти­вість P. Тоді X = {x: P(x)} – множина елементів, кожен з яких має властивість P. Звичайно зада­є­ть­ся попередньо інша множина, на підставі аналізу властивостей елементів якої, фор­му­є­ться дана множина. Нехай задана множина T. Тоді X = {x Î T: P(x)} – множина елементів мно­жи­ни Т, що мають властивість Р.

Приклад:

N = {x Î Z: x > 0} – множина натуральних чисел;

G = {x Î D: x має населення понад 1 мільйон} – задання множини міст України, що мають населення понад один мільйон. Тут D - множина усіх міст України.

Другий спосіб задання множин дуже важливий, тому що дозволяє пов'язати поняття “властивість” і “множина” і тим самим за допомогою останнього формалізувати перше для ком­п'ютера. Наприклад, властивість предмета мати червоний колір для комп'ютера можна задати включенням предмета в певну множину, з елементами якої зв'язуються всі наслідки того, що вони мають червоний колір.

Далі будемо вважати, що кожна розумна властивість визначає деяку множину X еле­мен­тів, що мають цю властивість, і, навпаки, будь-якій множині відповідає властивість її елементів бути елементами цієї множини.

Варто зазначити, що співвідношення “властивість” і “множина” може породити серйозні про­­блеми, пов'язані з тим, що можливе існування властивостей, які визначають множини, що, можливо, не існують. У всякому разі, для логіки прийняте співвідношення властивість - множина є найважливішим положенням.

Відомий фахівець в області штучного інтелекту С.Осуга у своїй книзі “Обробка знань” помилковість інтуїтивного відчуття про можливість задання множини довільним способом демонструє у такий спосіб. Нехай х Î Y ~ P(x) - це формальний запис. Тоді довільною властивістю може бути влас­ти­вість x Ï x. Нехай Y - множина, визначена цією властивістю, тобто Y – це множина, що складається із самої множини, що не є власним елементом. Прийнявши, однак, що така множина існує, поставимо запитання: “ чи є Y елементом Y?” і прийдемо до протиріччя:

Y Î Y еквівалентне Y Ï Y.

Цей факт, відомий як обернена теорема Рассела, використовується для підтвердження необхідності використання інших методів задання множин. Ми будемо говорити про це пізніше при розгляді аксіоматичної теорії множин.

Виділимо і третій спосіб задання множин, близький до другого, але з своїми особ­ли­востями. Суть його полягає в тому, що визначається правило або алгоритм, що дозволяє отриму­вати еле­менти заданої множини. Ми зараз не формалізуємо поняття правила чи алгоритму, але інту­ї­тив­но здатні зрозуміти, що задати множину, яка містить довільної довжини послідовності нулів, можна використовуючи правило приписування ще одного нуля до попередньої послідовності: C = {0, 00, 000,...}. І, крім того, хіба задання множини натуральних чисел не побудовано на правилі додавання одиниці?

Третій спосіб також може породити деякі непрості ситуації. Наприклад, чи всяка мно­жи­на може бути породжена алгоритмічно? Іншими словами, третій спосіб також не завжди можна застосувати. З цією проблемою пов'язаний курс “Алгоритміка”.

Варто зазначити, що третій метод природним чином можна назвати методом пород­жен­ня чи конструктивним методом, що, по суті, починаючи з невеликих множин, які можна задати, наприклад, перерахуванням, шляхом виконання дозволених перетворень приводить до задання нової множини, що додається до попередньої множини і т.д.

Якщо припустити, що існує кілька способів визначення і описання алгоритмів, а в дійсності ситуація виглядає саме так, то повинна бути множина модифікацій для цього способу задання множин.

У природі, суспільстві, навколишній реальності різні об'єкти формують множини різ­ної природи, поєднуючись в різні ситуації. Більш того, у процесі проектування систем конят­руктор своє представлення про цільову ситуацію намагається зліпити з наявних ситуацій, узагалі дослідник намагається виділяти подібні один одному сполучення об'єктів і вста­но­ви­ти закономірності їхнього формування.

На цій основі введене поняття “операція над множинами”, що фактично дозволяє реалізувати формальним чином породження різних ситуацій сполучень елементів. Будемо за­сто­совувати такі операції над множинами.

Визначення. 1. Об'єднання множин S і R - це множина SÈR = {x: x Î S чи xÎ R}.

2. Перетин множин S і R - це множина SÇR = {x: xÎ S і xÎ R}.

3. Різниця множин S і R - це множина S \R= {x: xÎ S і x Ï R}.

4. Доповнення підмножини S до універсальної множини U – це множина S’ = {x ÎU: xÏS}.

S

S

Існує зручний спосіб графічної ілюстрації операцій над множинами – діаграми Венна чи кола Ейлера:

	R   U
		R U

				S’ U

SÈR SÇR S\R S’

Приклад. Нехай задані множини S = {a, b, c}, R = {a, c, d}, U = {a, b, c, d, e}. Тоді SÈR = {a, b, c, d}, SÇR = {a, c}, S\R = {b}, S' = {d, e}.

Узагалі поняття “операція “ дуже важливе і його широко застосовують у різних га­лу­зях математики для конструювання одних об'єктів з інших, для визначення нових мате­ма­тич­них об'єктів тощо. Зокрема, використовуючи представлення про операції об'єднання і пере­тину ­множин, вводять поняття розбиття.

Визначення. Розбиттям П множини R будемо називати множину {R₁, R₂,…,R_n} її під­мно­жин таку, що виконуються такі умови:

1) R₁È (R₂È,…,È(R_n-1ÈR_n)…) = R;

2)R_i ÇR_j = Æ для кожної пари i, j, де i ¹ j.

Приклад. Нехай R = {r₁, r₂,…,r₆}. Розглянемо такі множини підмножин:

П₁ = {{r₁}, {r₂}, {r₃, r₄}, {r₅, r₆}};

П₂ = {{r₁, r₂}, {r₃, r₄, r₅, r₆}};

П₃ = {{r₁, r₂, r₃, r₄, r₅, r₆}};

П₄ = {{r₁, r₂, r₃, r₄}, {r₄, r₅, r₆}};

П₅ = {{r₁, r₂},{r₃, r₄, r₆}}.

Тут множини підмножин П₁, П₂, П₃ - розбиття, а множина підмножин П₄ не є роз­бит­тям, тому що не виконується умова 2). Множина підмножин П₅ не є розбиттям, тому що не виконується умова 1).

Розбиття часто використовується при постановках задач керування. Наприклад, якщо R - множина лекцій, що повинні бути проведені k лекторами, причому кожна лекція про­во­ди­­­ть­ся одним лектором, то тоді закріплення лекцій – розбиття, що включає k підмножин лекцій. Умова 1) гарантує, що всі лекції будуть проведені, а умова 2) забезпечує закріплення кожної лекції за одним лектором.

Інтерес для конструктора становлять властивості операцій. Дійсно, якщо розв’язання проблеми пов'язане з аналізом результатів застосування згаданих вище операцій до якоїсь су­куп­ності множин, то знання того факту, що SÈR = RÈS дозволяє скоротити число комбі­на­цій, які варто аналізувати.

Діаграми Венна допоможуть установити справедливість наступних властивостей опе­ра­цій над множинами:

1) SÈR = RÈS

SÇR = RÇS - комутативність;

2) SÈS = S

SÇS = S - ідемпотентність;

3) S È (R È T) = (S È R) È T

S Ç (R Ç T) = (S Ç R) Ç T - асоціативність;

4) SÈ (R Ç T) = (SÈ R) Ç (SÈ T)

S Ç (R È T) = (S Ç R) È (S Ç T) - дистрибутивність;

5) S È S' = U

S Ç S' = Æ - властивості доповнення;

6) (S ')' = S - властивість подвійного доповнення;

7) S Ç Æ = Æ S ÈÆ = S

S Ç U = S S È U = U - властивості виділених елементів;

8) (S È R)' =S'ÇR'

(SÇR)' = S'ÈR' - правила де Моргана;

9) S \ R = S Ç R' - зв’язок операцій різниці, перетину і доповнення.

Множини, над якими виконується операція, назвемо операндами, а множину, яка одер­­­жується в результаті виконання операції – результатом. У залежності від числа опе­ран­дів операції над множинами розділяють на унарні (наприклад, доповнення), бінарні (наприк­лад, È,Ç,\). До бінарних відноситься ще одна важлива операція, яку ми широко будемо вико­ри­стову­вати надалі – де­кар­тів добуток множин. Для його визначення умовимося вважати важ­ли­вим порядок елемен­тів. Множини {1, 2, 3, 4} і {4, 3, 2, 1} рівні, а нам потрібно їх роз­різ­няти. Тоді введемо по­няття послідовності. Так, пара елементів (а,b), у якій зафіксований їхній порядок, на­зи­ва­є­ть­ся послідовністю.

Послідовності можуть мати довільне число елементів (довжину) (a₁,a₂,…,a_n). Якщо n = 3, то послідовність називають трійкою, n = 4 – четвіркою й у загальному випадку - n-кою. Послідовності (a₁,a₂,a₃,…,a_n) і (b₁,b₂,…,b_n) однакові тоді і тільки тоді, коли a_i = b_i для i = 1,2,…,n.

Декартів добуток множин S і R - це множина S ´ R = {(x, y): x Î S, y Î R}.

Приклад: Нехай S = {a, b, c}, R = {a, c, d}. Тоді S ´ R = {(a, a), (a, c), (a, d), (b, a), (b, c), (b, d), (c, a), (c, c), (c, d)}.

Варто підкреслити, що S x R містить усі можливі пари згаданого у визначенні виг­ля­ду, тобто ніби містить усі можливі зв'язки між елементами двох множин. Декартів добуток по­­ширюється на n множин у такий спосіб. Нехай А₁, А₂,…,А_n - множини. Тоді А₁ ´ А₂ – де­кар­тів добуток двох множин, ((А₁ ´ А₂) ´ А₃) – декартів добуток трьох множин і в загаль­но­му випадку (((А₁ ´ А₂) ´ А₃) ´...´ А_n) - декартів добуток n множин, що тепер домовимося запи­сувати без дужок А₁ ´ А₂ ´...´ А_n. Уведемо декартів n-ий ступінь множини А як декартів добуток A₁ ´ А₂ ´...´ А_n множин А₁, А₂,…,А_n таких, що А₁ = А, А₂ = А,…,А_n = А. Будемо по­зна­чати декартів n-ий ступінь множини А через Аⁿ.

Отже, вже термін “зв'язок“ згадано, але за допомогою понять “множина“ і “операція“ ду­­же важко конкретизувати зв'язок між елементами однієї чи різних множин у явному виді. А необхідність у цьому при моделюванні реальних об'єктів керування виникає по­стій­но. Так, у прикладі, розглянутому у вступній лекції, необхідно мати засоби приписувати еле­мен­там множини вершин графа відстань, тобто елементи множини N, a ребрам - пропускні здатності (також елементи множини N), установити для кожного ребра пов'язані з ним вершини тощо.

2. Функції. Моделювати зв'язки об'єктів, тобто елементів різних множин, можна за допомогою поняття “функція”.

Визначення. Функцією з множини S у множину R будемо називати будь-яку під­мно­жи­ну F Í S ´ R таку, що для кожного x Î S знайдеться не більш одного елемента y Î R такого, що (x, y) Î F.

Звичайно функція позначається F: S → R, причому множини S і R називають відпо­від­но областю існування (визначення) і областю значень функції F. Іноді множину S на­зи­ва­ють об­ластю, множину R – кообластю. Множину елементів з R, що містяться в підмножині F Í S ´ R на­зи­ва­ють образом функції F і позначають Im F.

Приклад: Нехай S ={a, b, c}, R = {a, c, d}.

Розглянемо підмножини S x R:

F₁ = {(a, a), (b, c), (c, d)} Im F₁ = {a, c, d} = R;

F₂ = {(a, a), (b, a), (c, d)} Im F₂ = {a, d};

F₃ = {(b, c), (c, c)} Im F₃ = { c};

F₄ = {(a, a), (b, c), (c, d), (a, d)}.

Підмножини F₁, F₂, F₃ - функції, підмножина F₄ не є функцією, тому що для а Î S у F₄ є дві пари, що містять даний елемент: (а,а), (а, d).

Якщо ми спробуємо так само, як і для множин узвичаїти однаковість (рівність) функ­цій, то тоді, відповідно до означення, ми повинні розглядати тільки функції, наприклад, F₁: S₁® R₁ і F₂: S₂ ® R₂, області і кообласті яких збігаються, тобто S₁ = S₂, R₁ = R₂, і для кожного x Î S підмножини F₁ і F₂ включають однакові пари елементів, причому першим з елементів кожної з яких є елемент x. Будемо говорити тоді, що функції F₁ і F₂ рівні і по­зна­ча­ти цей факт F₁ = F₂.

Існує зручний метод позначення функції F: S® R у вигляді y = F(x), де x Î S, y Î R. Гово­рять тоді, що x - аргумент, а y - значення функції. У цьому випадку рівність функцій можна записати F₁(x) = F₂(x).

Приклади функцій, відомих з курсу математичного аналізу: y = x, y = |x|, y = x², y = 1/x, де x, y Î Z чи іншій числовій множині. Далі, якщо не уточнено інше, будемо вважати, що x, y Î Q.

Пари декартового добутку множин у підмножині F, що визначає функцію, можуть утво­рювати різні особливі сполучення, знання яких полегшує застосування функцій на прак­тиці. Наприклад, розглянемо ще одну функцію з S у R: F₅ = {(a, c), (b, a), (c, d)} і по­рів­ня­ємо F₅ з F₁ і іншими функціями. Загальним у F₅ і F₁ є те, що обидві вони зв'язують еле­менти множин R і S взаємно однозначно, причому ніяка інша функція цієї властивості не має.

Нехай є n робіт і n верстатів. Одна з типових задач автоматизації: необхідно закріпити роботи за верстатами так, щоб одна робота виконувалася тільки одним верстатом, і один верстат ви­ко­нував тільки одну роботу, тобто розподілити роботи. Знаючи це, ми можемо перевірити будь-який розподіл, і якщо в ньому знайдеться вільний верстат чи незакріплена робота, то ми повинні відкинути розподіл як такий, що не відповідає умові. Зазначимо, що ми не говоримо тут про вибір одного з найкращих у якомусь сенсі розподілів з тих, які відповідають умові розподілу, тобто про оптимізацію.

Виділяють такі класи функції на основі аналізу властивостей відповідних під­мно­жин декартового добутку, якими функції визначаються:

а) ін'єктивні функції.

Функція y = F(x) називається ін'єктивною, якщо з x ¹ х' випливає F(x) ¹ F(х').

Так, функції F₁, y = x ін’єктивні, а функції F₂, y = x² не ін’єктивні;

б) сюр'єктивні функції.

Функція y = F(x) називається сюр'єктивною, якщо для кожного yÎ R є такий xÎ S, що F(x) = y.

Так, функції F₁, y = x, x, yÎ Z - сюр'єктивні, а функції F₂, y = x², x, y Î Z не сюр'єктивні;

в) бієктивні функції.

Функція y = F(x) називається бієктивною, якщо вона ін'єктивна і сюр'єктивна.

Так, функції F₁, y = x, x, yÎ Z - бієктивні, a функції F₂, y = x², x, y Î Z не бієктивні;

г) часткові функції.

Функція y = F(x) називається частковою, якщо вона визначена для деяких, але не для всіх x Î S.

Так, функції F₃, y = 1/x часткові.

Уведення поняття часткової функції пояснює, чому у визначенні функції потрібно для кожного xÎ S не більш однієї пари в підмножині F, що містить x.

Як і для множин, для функцій важливий спосіб задання. Існують три способи задання функцій:

- за допомогою графіка, тобто перерахування пар підмножини декартового добут­ку, що визначає функцію (наприклад, функції F₁, F₂, F₃, F₄, F₅ задані таким способом);

- за допомогою матриць;

- за допомогою виразів, аналітично, наприклад, y = x²;

- за допомогою алгоритму, що дозволяє для аргумента х отримати значення y.

Поняття функції можна узагальнити і на декартів добуток більше двох множин. Так, для R₁ ´ R₂ ´…´R_n+1 можна визначити функцію від n аргументів чи n-місну функцію.

Наприклад: Нехай R₁ = {a, b}, R₂ = {a, c}, R₃ = {b, d}. Тоді

R₁ ´ R₂ ´ R₃ = {(a, a, b), (a, a, d), (a, c, b), (a, c, d), (b, a, b), (b, a, d), (b, c, b), (b, c, d)}.

F₁: R₁ ´ R₂ ® R₃, F₁ = {(a, a, b), (a, c, b), (b, a, d), (b, c, d)}.

Тепер можна порівняти поняття “функція” і “операція”. З огляду на те, що вони дозволяють установити зв'язок між елементами, у них багато спільного. Розходження в тім, що операція звичайно використовується для зв'язку елементів тієї ж множини, а функція – для зв'язку елементів різних множин.

Узагалі поняття функції – одне з фундаментальних понять математики. Уміння мис­ли­ти в термінах функціональних залежностей одержало назву функціональне мислення. На рубежі ХІХ і ХХ сторіч боротьба за його впровадження в навчанні, очолювана Ф.Клейном, привела до серйозної реформи освіти в Німеччині.

Застосування функцій дає можливість виразити закони природи, соціальні закони і потім використовувати математичні дії для аналізу цих законів, обґрунтування їхньої прак­тичної користі. Так, Г.Галілей відкрив закон вільного падіння тіл, виразивши його функцією

S = g t²/2,

де S - відстань, пройдена тілом у вільному падінні;

t - час падіння;

g - константа.

Тим самим вхоплена і виражена суть закону у формі, зручній для дослідження роз­ви­не­ним математичним апаратом. Наприклад, можна розрахувати час, якщо заданий шлях. Більш того, якщо шлях виразити у виді функціональної залежності від інших па­ра­метрів, то тим самим можна пов’язати ті параметри з параметрами нашої функції.

Зазначимо, що цей підхід широко використовується при проектуванні й експлу­а­та­ції комп'ютеризованих систем. У більшості випадків керування будується як вибір значень одних параметрів при відомих функціональній залежності і значеннях інших, що беруть участь у цій залежності, параметрів.

У будь-якому випадку використання функцій припускає виконання деяких дій над ними. Крім того, використання функцій для представлення деяких зв'язків між реальними об'єктами неможливе. Зокрема, якщо Т – множина виробів, М – множина матеріалів, то F: Т ® Q дозволяє задати собівартість виробів для підприємства. Однак якщо деякі матеріали використовуються для виготовлення більш одного виробу (а той факт, що при виготовленні практично усіх виробів використовується кілька матеріалів – загальновідомий), то зв'язок між виробами і матеріалами F: T ® M не буде функцією.

Щоб стимулювати думки читача у цьому напрямку, звернемо його увагу на той факт, що F: T x M ® Q - двомісна функція, за допомогою якої можна установити норму витрат матеріалу на виріб. Напрошується використання традиційного для математики прийому узагальнення, тобто мова йде про узагальнення функцій.