Лекція Курс лекцій, що вам пропонується, носить назву "Основи дискретної математики"



Сторінка1/4
Дата конвертації30.12.2016
Розмір0.77 Mb.
  1   2   3   4


Конспект лекцій




Основи дискретної математики

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


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

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

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

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

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

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

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


Z



X

Y

V

W



ОК - об'єкт керування;

СК - система керування;

Х - вхідний потік;

Y – вихідний потік;

W – інформація про стан ОК;

V - керуючі впливи;

Z – збурюючі впливи


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

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

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


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

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

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

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

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

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

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

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

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



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



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

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

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

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

pxy - вага ребра XY маршруту Мi.

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

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

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

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

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

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

Робота алгоритму для визначення найкоротшого маршруту з пункту А в пункт Е моделі показана на рис 4 – 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) містить 2n підмножин, де n - число елементів у множини U.

Дійсно, P(U) складається з 2n підмножин: , 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 R U

S
S’ U


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 будемо називати множину {R1, R2,…,Rn} її під­мно­жин таку, що виконуються такі умови:

1) R1 (R2,…,(Rn-1Rn)…) = R;

2)Ri Rj =  для кожної пари i, j, де i  j.

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

П1 = {{r1}, {r2}, {r3, r4}, {r5, r6}};

П2 = {{r1, r2}, {r3, r4, r5, r6}};

П3 = {{r1, r2, r3, r4, r5, r6}};

П4 = {{r1, r2, r3, r4}, {r4, r5, r6}};

П5 = {{r1, r2},{r3, r4, r6}}.

Тут множини підмножин П1, П2, П3 - розбиття, а множина підмножин П4 не є роз­бит­тям, тому що не виконується умова 2). Множина підмножин П5 не є розбиттям, тому що не виконується умова 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')' = Ы властивість подвійного доповнення;

7) S   =  S  = S

S  U = S S  U = U властивості виділених елементів;

8) (S  R)' =S'R'

(SR)' = S'R' правила де Моргана;



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

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

Послідовності можуть мати довільне число елементів (довжину) (a1,a2,…,an). Якщо n = 3, то послідовність називають трійкою, n = 4 – четвіркою й у загальному випадку - n-кою. Послідовності (a1,a2,a3,…,an) і (b1,b2,…,bn) однакові тоді і тільки тоді, коли ai = bi для 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 множин у такий спосіб. Нехай А1, А2,…,Аn - множини. Тоді А1  А2 – де­кар­тів добуток двох множин, ((А1  А2)  А3) – декартів добуток трьох множин і в загаль­но­му випадку (((А1  А2)  А3 ) ... Аn ) - декартів добуток n множин, що тепер домовимося запи­сувати без дужок А1  А2 ... Аn. Уведемо декартів n-ий ступінь множини А як декартів добуток A1  А2 ... Аn множин А1, А2,…,Аn таких, що А1 = А, А2 = А,…,А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 :

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

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

F3 = {(b, c), (c, c)} Im F3 = { c};

F4 = {(a, a), (b, c), (c, d), (a, d)}.

Підмножини F1, F2, F3 - функції, підмножина F4 не є функцією, тому що для а  S у F4 є дві пари, що містять даний елемент: (а,а), (а, d).

Якщо ми спробуємо так само, як і для множин узвичаїти однаковість (рівність) функ­цій, то тоді, відповідно до означення, ми повинні розглядати тільки функції, наприклад, F1 : S1 R1 і F2: S2  R2, області і кообласті яких збігаються, тобто S1 = S2, R1 = R2, і для кожного x  S підмножини F1 і F2 включають однакові пари елементів, причому першим з елементів кожної з яких є елемент x. Будемо говорити тоді, що функції F1 і F2 рівні і по­зна­ча­ти цей факт F1 = F2.

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

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

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

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

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

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

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

Так, функції F1, y = x ін’єктивні, а функції F2, y = x2 не ін’єктивні;

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

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

Так, функції F1, y = x, x, y Z - сюр'єктивні, а функції F2, y = x2, x, y  Z не сюр'єктивні;

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

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

Так, функції F1, y = x, x, y Z - бієктивні, a функції F2, y = x2 , x , y  Z не бієктивні;

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

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

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

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

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

- за допомогою графіка, тобто перерахування пар підмножини декартового добут­ку, що визначає функцію (наприклад, функції F1, F2, F3, F4, F5 задані таким способом);



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

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

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

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

Наприклад: Нехай R1 = {a, b}, R2 = {a, c}, R3 = {b, d}. Тоді

R1  R2  R3 = {(a, a, b), (a, a, d), (a, c, b), (a, c, d), (b, a, b), (b, a, d), (b, c, b), (b, c, d)}.

F1 : R1  R2  R3, F1 = {(a, a, b), (a, c, b), (b, a, d), (b, c, d)}.

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

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

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

S = g t2/2,

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

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

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

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

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

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

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

Лекція 2. Бінарні відношення і їхні властивості


  1. Відношення: визначення і приклади. Почнемо з базового визначення.

Визначення. Бінарним відношенням  між елементами множин S і R назвемо будь-яку підмножину декартового добутку S R, тобто   SR.

Якщо (х,у)  , то говорять, що х знаходиться у відношенні  до у і пишуть ху.

Далі будемо розглядати відношення  RR, причому R={r1,r2,...,rn}.

Бінарне відношення може бути задане:



  • графіком відношення, тобто множиною пар (ri,rj);

  • матрицею N, елемент i,j якої дорівнює 1, якщо (ri,rj) і 0, якщо (ri,rj).

Приклад. Нехай R={1,2,3,4,5,6}. Тоді бінарними відношеннями на R є:

1 = {(1,1),(1,2),(2,3),(3,1),(4,5),(5,2),(6,6)};

2 = {(1,1),(5,1),(6,2),(6,6)};

3 = {(1,1),(2,2),(3,3),(4,4),(5,5),(6,6)};

4 = {(1,1),(2,1),(2,2),(3,1),(4,1),(4,2),(5,1),(3,3),(4,4),(5,5,),(6,1),(6,2),(6,3), (6,6)};

5 = {(1,2),(2,1),(3,2),(2,3)};

6 = {(1,2),(2,3),(1,3),(3,4),(1,4),(2,4)}.

Зверніть увагу, що деякі з цих відношень вже нам знайомі, зокрема відношення 3 можна назвати «ri дорівнює rj», а відношення 4 - «ri поділяється без остатку на rj». Цей приклад підкреслює, яке значення для формалізації має поняття «відношення».

Надалі будемо використовувати деякі корисні відношення, які можуть бути визначені для довільної множини.

Визначення. Тотожним відношенням для довільної множини R назвемо відношення IR = {(ri,ri) : riR}. Універсальним відношенням для довільної множини R назвемо відношення UR = {(ri,rj) : riR, rjR}.

З усіх бінарних відношень виділимо класи, що мають корисні властивості.



Визначення. Бінарне відношення RR назвемо рефлексивним, якщо для кожного riR справедливо (ri,ri), інакше - антирефлексивним. Бінарне відношення назвемо ірре­флек­сивним, якщо для кожного riR справедливо (ri,ri). Зокрема, 3, 4 - приклади ре­флекс­сивних відношень, 1, 2 – антирефлексивних, 5, 6 – іррефлексивних.

Визначення. Бінарне відношення   R  R назвемо симетричним, якщо з (ri,rj) випливає (rj,ri). Якщо з (ri,rj)   і (rj,ri)   випливає ri = rj, то відношення назвемо антисиметричним. Зокрема, 5 – приклад симетричного відношення. Якщо з ab випливає (b,a)  , то відношення назвемо асиметричним.

Зазначимо, що властивості симетричності і антисиметричності не є взаємно вик­люч­ними. Легко пересвідчитись, що для будь-якої множини R відношення IR є симетричним і антисиметричним. Ми можемо також визначити відношення, які не є ні симетрич­ними, ні анти­сим­ет­ричними.

Приклад. Нехай маємо множину всіх людей. Визначимо відношення В таке, що xВy тоді і тільки тоді, коли x є братом у. В сім’ї, що складається з двох братів р і q та сестри г, ми отримуємо відношення В, яке не є сим­етричним, тому що pВr, але не rВp. Це відношення також не є антисиметричним, тому що pBq і qBp, хо­ч р і q різні.

Визначення. Бінарне відношення   R  R назвемо транзитивним, якщо з (ri,rj)   і (rj,rl)   випливає (ri,rl)  , ri  rj, ri  rl, rl  rj. Зокрема, 4 і 6 – приклади транзитивного відношення.

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

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

Визначення. Бінарне відношення на множини R, що має властивості рефлексивності, антисиметричності і транзитивності, назвемо відношенням часткового порядку і будемо позначати .

Приклади відношення часткового порядку: 4 ; відношення  на множині позитивних цілих чисел, тобто 7 = (1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (2,2), (2,3), (2,4), (2,5), (2,6), (3,3), (3,4), (3,5), (3,6), (4,4), (4,5), (4,6), (5,5), (5,6), (6,6)}; відношення включення R  S на булеані P(U) і ін.



Визначення. Множина R, на якій задане відношення часткового порядку називається частково упорядкованою.

Для такої множини важливими характеристиками є: верхня універсальна границя I, якщо I  ri для будь-якого riR; нижня універсальна границя О, якщо О  ri для будь-якого riR.

Говорять ще, що О – найменший, а I – найбільший елемент множини R.

Лема 1. У будь-якій частково впорядкованій множині може існувати не більш однієї верхньої і не більш однієї нижньої універсальних границь.

Доведення. Дійсно, нехай існує два найменших елементи О і О*. Тоді справедливо О О* і О* О. Звідси по властивості антисиметричності О = О*. Аналогічно доводиться і випадок для I і I*. Лема доведена.


Існують частково впорядковані множини без універсальних границь, наприклад мно­жина Z не має ні нижньої, ні верхньої універсальної границі, а множина N має тільки нижню універсальну границю.

Існують і скінченні частково впорядковані множини без універсальних границь, на­при­клад множина R={a,b,c,d,e,f} з визначеним на ній частковим порядком 8 = {(a,a), (b,b), (c,c), (a,b), (b,c), (a,c), (d,d), (e,e), (f,f), (d,e), (e,f), (d,f)}. Претенденти на нижні і верхні універсальні границі – елементи a, d і c, f означенню в дійсності не задовольняють.



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

З відношенням часткового порядку  пов'язаний ряд інших відношень:



  • строгого порядку х < y, що означає, що х  у, але х  у (ясно, що це іррефлексивне, асиметричне і транзитивне відношення);

  • незрівнянності х у, що означає, що ні х  у, ні у  х.

Тоді для кожної пари (х,у)  R, де R – частково упорядкована множина, справедливо: або х = у, або х < у, або х > у, або х у.

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

Елемент m частково упорядкованої множини R називається мінімальним (макси­маль­ним), якщо не існує такого ri  R, що ri < m (ri > m).

Очевидно, якщо частково упорядкована множина має універсальну границю О (чи I), то вона є мінімальним (максимальним) елементом.

Легко привести приклад частково упорядкованої множини, що має декілька міні­маль­них і максимальних елементів: на множини R={a, b, c, d, e, f} розглянемо вже знайомий нам частковий порядок 8 = {(a,a), (b,b), (c,c), (d,d), (e,e), (f,f), (a,b), (b,c), (a,c), (d,e), (e,f), (d,f)}. Тоді a і d – мінімальні елементи, а c і f - максимальні елементи.

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


Лема 2. Елементи скінченної частково впорядкованої множини R={r1,...,rn} завжди можна перенумерувати таким чином: R={х1 ...хn }, що з xi < xj буде випливати i < j.


Доведення. Початкову нумерацію виконаємо яким завгодно шляхом. Потім проведемо послідовно ряд перестановок: елементи в отриманій нумерації змінюємо місцями, якщо у від­по­відній парі графіку відношення  вони стоять у зворотньому порядку. Очевидно, число таких перестановок рівне чи менше числа пар. За побудовою нумерації для будь-якої пари xi < xj елемент xi отримає менший номер. Лема доведена.

Для аналізу мінімальних чи максимальних елементів по приналеж­ності до частково впорядкованої множини R по відношенню до її підмножини S також вводять нові поняття.



Визначення. Назвемо елемент а  R нижньою (верхньою) границею підмножини S, якщо а  x (a  x) для всіх хS.

Визначення. Назвемо елемент b  R нижньою гранню підмножини S, якщо:

1) b – нижня границя підмножини S;

2) b  b, де b - будь-яка нижня границя підмножини S.

Визначення. Назвемо елемент c  R верхньою гранню підмножини S, якщо:

1) c – верхня границя множини S;

2) c  c, де c - будь-яка верхня границя множини S.

Далі будемо писати b = inf S, c = sup S (infimum – наголос на другому i, supremum – наголос на e). Іноді використовуються терміни "точна нижня границя" і "точна верхня границя", відповідно.

Аналогічно тому як було доведено єдиність універсальних границь, можна довести єдиність верхньої і нижньої граней.

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

Приклад. На основі порядку, визначеного на множині N, ми можемо формально отри­мати звичайні відношення порядку на множинах чисел Z, Q і R. Спочатку розглянемо Z. Щоб полегшити міркування, розіб’ємо Z таким чином: Z = N{0}A.

Тому A = {-x: x  N}. Визначимо відношення, яке будемо називати повним відношенням порядку на Z, розгляданням всіх можливих елементів x і у із розбиття {N{0}A}.

Якщо x = у, то x  у і у  x. Нехай x у. Тоді:

а) якщо x, у  N, то порядок в Z той же, що й в N;

б) якщо x, у  А, то x у тоді і тільки тоді, коли -у  -x в N (тобто - 5  -4, тому що 4  5);

в) якщо x = 0 і у N, то x  y;

г) якщо x  А і у = 0, то x  y;

д) якщо x  А і yN,то x  y або в супротивному випадку у x.

На основі порядку на Z і звичайних арифметичних операцій з цілими числами ми можемо визначити поря­док на Q:

a/b  c/d тоді і тільки тоді, коли аd < bс.

Легко пересвідчитись, що це твердження виконується. Насамкінець, визначимо відношення порядку на множині дійсних чисел R. Розглянемо десяткові зображе­ння двох дійсних додатних чисел:

D =…0dn…d2d1d012…,

C = …0cm…c2c1c012… .

Якщо di = ci і i = i для всіх i, то D = C і, отже, D  C і C D. В супротивному випадку:

а) якщо dn  0, cm  0 і n  m, то D  C, якщо n < m, і C D, якщо m < n;

б) якщо n = m і di  ci, але dj = cj для всіх j таких, що i < j  n, то із di < ci робимо висновок, що D  C, і, навпаки, якщо ci < di, то C D;

в) якщо n = m і di = ci для всіх i, але k  k для деяких k і j = j для всіх j таких, що 0 < j  k, тоді C D, якщо k <k, і D  C, якщо k < k.

В цьому легко пересвідчитись. Від’ємні числа можуть бути досліджені так же, як в Z.

Насамкінець, зазначимо, що використання природного порядку на R визначає нові множини, що називаються інтервалами:

[а, b] = {x: x  R, а  x  b} - замкнений інтервал (відрізок) від а до b;

]а, b[ = {x: x  R, а < x < b} - відкритий інтервал від а до b.

Тут числа а і b називаються кінцевими точками. Замкнений інтервал включає в себе кінцеві точки, а відкритый ні. Зручно також визначити напіввідкриті інтервали:

[a, b[ = {x: x R , a  x < b},

]a, b] = {x : xR, a < x  b},

Для зручності будемо використовувати такі позна­чення:

] -  , а] = {x: x  а},

]-, а[ = {x : x < а},

[а, [ = {x: а  x},

]a,[ = {x: a < x},

]-,[ = R.

Інтервали і множини чисел ми будемо використовувати час від часу в нашому курсі.



  1. Відношення еквівалентності. Ще одним важливим класом бінарних відношень є відношення еквівалентності.

Визначення. Бінарне відношення на множині R, що має властивості рефлексивності, симетричності і транзитивності, назвемо відношенням еквівалентності і будемо позначати E або =.

Приклад відношення еквівалентності – відношення рівності.

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

Теорема 1. Відношення Е є відношенням еквівалентності на множині R тоді і тільки тоді, коли воно визначає розбиття ПЕ на множині R.


Доведення. а) Пряме. Нехай задане розбиття П. Розглянемо відношення Е(П) таке, що ri Е(П) rj означає, що ri і rj належать одній і тій ж підмножині Ri розбиття П. Тоді відношення Е(П) – рефлексивне (тому що за побудовою ми включаємо в нього пари вигляду (ri,ri) для кожного riR), симетричне (тому що за побудовою, якщо ми включаємо в нього пару вигляду (ri,rj), то включаємо і пару вигляду (ri,ri)), тран­зи­тивне (тому що за побудовою, якщо ми включаємо в нього пари вигляду (ri,rj) і (rj,rl), то включаємо і пару вигляду (ri,rl)). Таким чином, відношення Е(П) – відношення еквівалентності.

б) Обернене. Нехай задано на R відношення еквівалентності E. Легко побудувати функцію fE : R  P(R), котра елементу ri ставить у відповідність підмножину PE (ri) = {rj R | (rj, ri)  E}. Тому що відношення Е рефлексивне, то riPE (ri), а отже PE(r1)  PE(r2)  PE(r3) ... PE(rn) = R. Залишається показати, що будь-які дві підмножини PE(ri) і PE(rl) або не пере­ти­на­ю­ться, або є рівними. Нехай це не так і є загальний елемент rj, але підмножини PE(ri) і PE(rl) не рівні. Але тоді справедливо riErj і rlErj. В силу симетричності відношення E, якщо виконується rlErj, то виконується rjErl. За наявності в відношенні E пар (ri,rj) і (rj,rl) в силу транзитивності відношення E в ньому присутня пара (ri,rl). З того, що для будь-якого rt PE(rl) справедливо rl E rt і, отже, в силу транзитивності справедливо ri E rt слідує, що PE(rl)  PE(ri). Помінявши місцями елементи rI і rl, аналогічно встановлюємо справедливість PE(ri)  PE(rl). Але це означає PE(ri) = PE(rl). Іншими словами, будь-які підмножини PE(ri) і PE(rl) або не пере­ти­на­ю­ться, або є рівними. З кожної групи таких рівних підмножин залишимо по одній підмножині, отримавши різні підмножини, що задовільняють другому обмеженню на розбиття. Теорема доведена.

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

Треба ще сказати, що поняття бінарного відношення припускає узагальнення на n-місні відношення через декартів добуток n множин.



Лекція 3. Ускладнення математичних об’єктів. Розширення уявлень про функції

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

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



  1. Деякі корисні функції й операції над функціями. Розпочнемо з важливої функції слідування Пеано σ, для якої множина Р всіх додатних цілих чисел є і областю, і кооб­ла­стю. Кожному цілому додатному числу n вона ставить у відповідність чис­ло n+1: σ(n)= n+1, σ : РР - функція з Р в Р. Функцію σ також можна задати (нескінченним) списком записів:

σ : 1  2, 2  3, 3  4, …, n n+1,… .

Очевидно, образом Im σ функції σ : РР є множина σ(Р) = {2,3,4,…}, яку ми позначимо символом Р2.

Для довільної множини S тотожна функція 1s: S S відображує будь-який елемент множини S в себе: 1s(s) = s для всіх sS. Наслідком означення є той факт, що тотожні функції різних множин різні.

Визначення. Лівою композицією gf будь-яких двох функцій називається функція, отри­мана в результаті їх застосування в порядку, оберненому написаному. Спочатку засто­со­ву­ється функція f, а потім - функція g за умови, що область функції g співпадає з кообластю функції f. Формально можемо записати: нехай f:S →T і g:T→U,тоді ліва композиція gf є функція gf: S → U, визначена правилом

(gf)(s)=g(f(s)) для всіх s S . (1)

Ц
е спввідношення між трьома функціями f, g і h = gf наглядно зображується такою діаграмою відображень:

Вона ілюструє ту обставину, що ми можемо перейти з множини S в множину U чи безпосередньо, застосовуючи функцію h, чи в два кроки, застосовуючи спочатку функцію f,а потім - функцію g.

Операцію правої композиції f ◊ g отримуємо з описаної вище операції лівої композиції перестановкою символів: f ◊ g = gf. Нехай, наприклад, φm: R → R — операція піднесення до ступеня m, φm (x) = xm. Подібно показнику ступеня m, символ функції φm можна записати праворуч від аргумента: xm =xφm. Якщо домовитися писати символи функцій φ, ψ,… праворуч від аргументу, то природно записувати їх композицію також в правій формі, тому що тоді виконується правило (x φ) ψ = x (φ ◊ ψ). Так, в попередньому прикладі x (φm ◊ φn) = (xm)n = xmn = x φmn, отже, φm ◊ φn= φmn. Інтуїтивно перевага правої композиції в тому, що функції пишуться в тому ж порядку, у якому вони виконуються.

Далі для зручності та скорочення запису символ операції лівої композиції ○ іноді будемо пропускати: композиція позначається просто записом символів функцій-аргументів у рядок.

Лема 3. Композиція функцій підкорюється асоціативному закону:

(h ○ g) ○ f = h ○ (g ○ f) = f ◊ (g ◊ h) = (f ◊ g) ◊ h

Вважається, що всі записані композиції визначені. Хоча інтуїтивно це очевидно, тому що як h ○ (gf), так і (hg) ○ f отримуються послідовним застосуванням функцій f, g і h саме в такому порядку. Те ж можна сказати стосовно f ◊ (gh) і (fg) ◊ h.

Доведення. Нехай f: S → T, g: T → U і h: U → V. Будь-якому елементу xS обидві композиції приписують значення

[(h g) f] x = (h g) (f x) = h (g (f x)) = h ((g f) x) = [h (g f)] x

(h g) f h g f h (g f) h (g f)

Перевірка кожної рівності полягає в застосуванні визначення композиції (1) до тієї композиції, котра вказана під знаком рівності. Після цього означення рівності функцій, наведене в лекції 1, доводить асоціативний закон (hg) f = h(gf): SV. Лема доведена.

Тотожні функції 1S і 1T в композиції з будь-якою функціею f : ST не змінюють її:

f ○ 1S = 1T ○ f = f , 1S ◊ f = f ◊ 1T = f


  1   2   3   4


База даних захищена авторським правом ©lecture.in.ua 2016
звернутися до адміністрації

    Головна сторінка