Перелік і зміст розділів і тем, що розглядаються у курсі



Скачати 271.9 Kb.
Сторінка1/3
Дата конвертації01.01.2017
Розмір271.9 Kb.
  1   2   3
Вказівки до виконання контрольних робіт з курсу "Основи дискретної математики" для студентів бакалаврату "Комп’ютеризовані системи, автоматика і управління" заочної форм навчання.

Перелік і зміст розділів і тем, що розглядаються у курсі



Тема 1. Предмет і організація курсу

Вступна лекція. Дискретна математика та її предмет. Кібернетичний підхід, сутність і значення. Системи: структура і функціонуван­ня, статика й динаміка. Роль дискретної математики при реалізації кібернетичного підходу. Зміст розділів. Мета й завдання курсу.

Література: [13, вступ, гл.1; 10, вступ, ч.І, гл.І-4]

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

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

Лекція І. Множини й операції над ними;

функції та їхні властивості; функції та операції, операції над функціями;

функції з множини S в S , тотожні функ­ції. Обернені й оборотні функції.

Лекція 2. Відношення; відношення еквівалент­ності й розбиття; відношення порядку - грані й межі; роль у ТПР. Решітки.

Лекція 3. Основні поняття теорії графів. Способи завдання графів. Спе­ціальні види графів. Графи й відношення.

Лекція 4. Об’єкт і його функціонування. Стан, облік часу, мета, автомат, скінченний автомат.

Лекція 5. Основи алгебраїчного підходу. Множина всіх підмножин універсальної множи­ни й операції над нею як система. Роль по­рожньої та універсальної множин. Алгебраїчна система. Можливість збереження й використан­ня абстрактних властивостей операцій на довільних множинах у вигляді алгебраїчних систем. Алгебра Кантора як булева алгебра.

Література: [1, гл.0, розд.1. § 1-3. 5, 6; 2, гл.1, § 1, 3-5; гл.2, § І, 2, 4, 5, 8, 9, 10; гл.3. § 1-3; 3, гл.1, § 1-4 ]



Тема 3. Загальний аналіз алгоритмічних і мовних засобів дискретної математики

Лекція 6. Мова та її роль. Проблеми дослідження мов. Розпізнання, задання, належність до двох мов. Природні й штучні мови. Семантика. Алфавіт і формальне визначення мови. Грама­тики й автомати. Роль граматик й автоматів як генераторів і розпізнавачів мови.

Лекція 7. Логіка і її предмет. Роль символічної логіки. Формальні аксіоматичні системи. Формальна система алгебри Кантора й Буля. Перехід від операцій до висловлювань. Пробле­ми істинності, повноти, несуперечності. Проблема повноти на прикладі алгебраїчних систем, їхні значення для АСУ на прикладі СОД.

Лекція 8. Інтуїтивне визначення алгоритму й необхідність його уточнення. Напрями уточ­нень алгоритмів. Проблема Поста. Вирішуваність.

Література: [1, гл.0. розд.2; гл.1. розд.1, § 1, 2; гл.2. розд.1, § 1, 2, 4; 4, гл.16. § 7-А; 20. ч.1, гл.4; 26, гл.3, § 3. 1] .

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

Тема 4. Загальна характеристика алгебраїчного підхо­ду і його роль в КСУ

Лекція 9. Алгебраїчний підхід. Необхідність його виникнення на прикладі груп в історично­му аспекті. Алгебра й прикладна алгебра. Загальне уявлення про алгебраїчну систему. Алгебри з однією операцією: півгрупа, моноїд, група. Алгебри з двома операціями. Алгебра відношень.

Лекція 10. Універсальні алгебри й проблема породження. Замикання множини за операцією. Підалгебра й система твірних. Властивості перетину носіїв пїдалгебр. Породження елементів носія. Властивості скінченних систем твірних. Постановка проблеми повноти. Максимальні підалгебри і їхні властивості. Кри­терій Поста повноти системи елементів. Базис алгебри. Значення скінченного базису. Основа алгебри.

Література: [3, гл.7. § 1, 3, 6. 7; гл.1. § 1, 2; гл.5, § 1, гл.10, § 1, 2; 25. гл.3. § 2. 3]



Тема 5. Числові системи як алгебраїчні системи

Лекція 11. Півгрупа натуральних чисел, кому­тативне кільце цілих чисел, поле раціональ­них чисел.

Лекція 12. Система Пеано з однією операцією. Принцип Діріхле. Алгебри з двоосновними носіями: лінійний векторний простір, лінійна алгебра.

Література: [2, гл.1, § 7, 9; гл.7, § 5; гл.10, § 1, 2, 3]

Розділ 3. Теорія граматик

Тема 6. Визначення і класифікація граматик за Хомським, автоматні граматики й регулярні мови.

Лекція 13. Класифікація граматик за Хомським. Приклади граматик типів 0-З. Властивості ре­гулярних множин: визначення, зв’язок з регулярними виразами, розростання, булева алгебра регулярних множин.

Лекція 14. Регулярні множини й автоматні граматики: співпадання класів регулярних множин і мов, які породжені автоматними граматиками. Контекстно - вільні мови та їхні властивості.

Література: [1, гл.2, розд.2; 3, гл.4, § 1; гл.16, § 1, 2, 4 ]



Тема 7. Когтекстно – вільні мови та їхні властивості

Лекція 15. Контекстно - вільні граматики. Дерева виведення. Виведення й дерева виве­дення. Проблема пустоти мови. Проблема пере­ведення. Нормальні форми Хомського і Грейбах. Зведення граматик до нормальних форм.

Лекція 16. Властивості контекстно - вільних мов: лема Огдена, алгебраїчні властивості. Уявлення про граматику мови програмування Паскаль.

Література: [1. гл.2, розд.4, 6; 4. гл.16. § 3, 27]



Тема 8. Контекстно - залежні граматики й граматики без обмежень. Інші моделі граматик.

Лекція 17. Властивості граматик без обмежень і контекстно - залежних граматик. Загальне уяв­лення про завдання АМП граматиками. Форма Бекуса - Наура і розширена форма Бекуса - Наура.

Лекція 18. Інші моделі граматик. Програмні та індексні граматики. Перехід до граматик з семантикою.

Література: [4, гл.16, § 3, 5]

Розділ 4. Теорія автоматів

Тема 9. Скінченні автомати і їхні властивості. Скін­ченні автомати і регулярні мови. Аналіз і синтез скінченних автоматів

Лекція 19. Автомати, їхні властивості. Скінченні автомати й регулярні мови. За­дача аналізу скінченного автомата. Зада­ча синтезу скінченного автомата. Алгоритм синтезу за регулярним виразом. Мінімізація скінченних автоматів.

Лекція 20. Еквівалентність станів і екві­валентність скінченних автоматів. Еквіва­лентне розбиття.

Література: [1, гл.2, розд.2, § 3. 4, розд.3, § 1, 2; гл.3, § 1-6; 4, гл.16. § 6А; 11, гл.1. § 1-10; гл.2, § 1-3. 5, 6. 8-12. гл.3, 16, гл.5, § 1-3. гл.6, § 4, 5; 13. гл.7]



Тема 10. Розпізнавання й експеримент на прикладі скінченних автоматів

Лекція 21. Класифікація експериментів. Постановка діагностичних експериментів з двома станами. Зв’язок з розпізнаванням образів.

Література: [11, гл.4, § 1-8; 22, передмова, гл.1, вступ]



Тема 11. Автомати з магазинною пам’яттю.

Лекція 22. Автомат з магазинною пам’яттю. Нескінченні автомати. Визначення МП-автомата. Детермінований і недетермінований МП-автомати. Розширений МП-автомат. Мови, що допускаються МП-автоматами.

Лекція 23. МП-автомати й контекстно - вільні мови. Загальна проблема розпізнавання й проблема трансляції. Розпізнавачі й пе­ретворювачі.

Література: [1, гл.2. розд.5; 4, гл. 16. § 6Б]



Тема 12. Лінійно-обмежені автомати й машина Т’юрінга

Лекція 24. Машина Т’юрінга. Визначення і властивості, функціонування. Машина Т’юрін­га й мови без обмежень. Лінійно-обмежений автомат. Його визначення на базі машини Т’юрінга. Лінійно-обмежені автомати й контекст­но - залежні мови. Зв’язок машини Т’юрінга з алгоритмами.

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

Література: [2, гл.З, § 7; 4. гл.Іб., §6В ]

Тема 13. Складні висловлювання й проблема встанов­лення істинності

Лекція 25. Загальні проблеми математичної логіки. Прості й складні висловлювання. Таблиці істинності. Властивості таблиць. Відношення слідування. Визначення алгебри висловлювань, тотожність і еквівалентність.

Лекція 26. Алгоритмічний спосіб встанов­лення істинності. Зведення окладних вислов­лювань шляхом алгебраїчних перетворень до висловлювань меншого порядку. Встановлен­ня істинності й нормальні форми: елементар­ні диз’юнкція і кон’юнкція, абсолютна істинність і хибність. Зображення будь-якого складного висловлювання у нормальній формі. Двоїстість висловлювань.

Література: [4, гл.15. § 4; 6 гл.І, 5 І, І; 10, гл.І, с.7, гл.2. с.25-54, 56-64, гл.З, с.70-83. 88-94, гл.4, с.125-128; 12, § І, 2.1, 2.3, 2.6, 2.6, 2.7, 3; 13. гл.4]



Тема 14. Числення висловлень

Лекція 27. Визначення аксіоматичної теорії числення висловлень. Дедуктивні властивос­ті теорії. Теорема дедукції Ербрана.

Лекція 28. Повнота, несуперечність числен­ня висловлень. Незалежність аксіом. Вибір аксіом та інші аксіоматизації.

Література: [4. гл.15, § 4; 6, гл.І, § 4-6; 26, гл.З. § З.1]



Тема 15. Застосування засобів математичної логіки на практиці

Лекція 29. Вентильні схеми, їхній аналіз і проектування. Структурний синтез автома­тів.

Література: [2. гл.6, § 4;гд.б, § 1-8; 12. § 8.1. § 8.2, 16, гл.9, § 1-3 ]


Розділ 6. Теорія графів та сіток

Тема 16. Загальні властивості неорієнтованих і орієнтованих графів

Лекція 30. Роль теорії графів як самостій­ного розділу дискретної математики. Опера­ції над графами. Неорієнтовані дерева: виз­начення, властивості, ліс, теорема Келі про перечислення.

Лекція 31. Кореневі дерева: визначення, властивості, зв’язок із задачами класифі­кації. Ейлерові й гамільтонові графи. Визначення і властивості ейлерових і гамільтонових неорієнтованих графів. Визначення й властивості ейлерових і гамільтонових орграфів. Турніри та їхнє застосування для оцін­ки альтернатив. Практична користь графів даного виду.

Література: [7; 19. § 1. 2, 3, 5-7, 9-11, 22, 23 ]



Тема 17. Спеціальні властивості графів, що використовуються теорією надійності, КСУ, САПР

Лекція 32. Розріз і розрізаюча множина. Проблеми прикладної теорії надійності й графи. Визначення й основні властивості розрізу й розрізаючої множини. Співвідно­шення розрізу й розрізаючої множини.

Лекція 33. Планарність у графах. Визначення плоского й планарного графів. Існування планарних графів і теореми про непланарність деяких графів. Теорема Куратовського. Планар­ність і стягування. Грані й ступені графів. Теорема Ейлера і теореми про властивості ступенів планарних графів. Укладення графів на інші фігури. Задача розведення плат. Розфарбування графів. Постановка задачі. Хроматичне число та ступені вершин графа. Теореми про розфарбування планарних графів. Розфарбування карт. Двоїстість у графах. Планарність і двоїстість.

Література: [17; 19, § 4, 5, 12, 13, 17-20 ]



Тема 18. Мережі й задачі на сітках.

Лекція 34. Потоки у мережах. Визначення мережі, потоку й розрізу. Теорема Форда - Фалкерсона. Найпростіші алгоритми розв’язання задачі про максимальний потік. Практичні задачі й мережі.

Лекція 35. Мережі Петрі. Практична необхідність і виникнення мереж Петрі. Визначення й основні властивості. Основні висновки з курсу.

Література: [7; 19, § 29, 21]


В першому семестрі вивчаються розділи 1, 2, 6 та виконується контрольна робота №1.

Завдання для контрольних робіт

Контрольна робота №1 (за перший семестр)
Варіант 1.

Вправа 1.1 теми 2. Вправа 3.1 теми 2. Вправа 8.1 теми 2. Вправа 13.1 теми 2. Вправа 18.1 теми 2. Вправа 18є.1 теми 2. Вправа 19.1 теми 2. Вправа 21.1 теми 2. Вправа 23.1 теми 2. Вправа 24.1 теми 2. Вправа 27 теми 2. Вправа 27а.1 теми 2. Вправа 1.1 теми 4. Вправа 23.1 теми 4. Вправа 1.1 теми 16. Вправа 2.1 теми 16. Вправа 21.1 теми 16. Вправа 1.1 теми 17. Вправа 2.1 теми 17. Вправа 1.1 теми 18.


Варіант 2.

Вправа 1.2 теми 2. Вправа 3.2 теми 2. Вправа 13.2 теми 2. Вправа 8.2 теми 2. Вправа 18.2 теми 2. Вправа 18є.2 теми 2. Вправа 19.2 теми 2. Вправа 21.2 теми 2. Вправа 23.2 теми 2. Вправа 24.2 теми 2. Вправа 27 теми 2. Вправа 27а.2 теми 2. Вправа 1.2 теми 4. Вправа 23.2 теми 4. Вправа 1.2 теми 16. Вправа 2.2 теми 16. Вправа 21.2 теми 16. Вправа 1.2 теми 17. Вправа 2.2 теми 17. Вправа 1.2 теми 18.


Варіант 3.

Вправа 1.3 теми 2. Вправа 3.3 теми 2. Вправа 13.3 теми 2. Вправа 8.3 теми 2. Вправа 18.3 теми 2. Вправа 18є.3 теми 2. Вправа 19.3 теми 2. Вправа 21.3 теми 2. Вправа 23.3 теми 2. Вправа 24.3 теми 2. Вправа 27 теми 2. Вправа 27а.3 теми 2. Вправа 1.3 теми 4. Вправа 23.3 теми 4. Вправа 1.3 теми 16. Вправа 2.3 теми 16. Вправа 21.3 теми 16. Вправа 1.3 теми 17. Вправа 2.3 теми 17. Вправа 1.3 теми 18.


Варіант 4.

Вправа 1.4 теми 2. Вправа 3.4 теми 2. Вправа 13.4 теми 2. Вправа 8.4 теми 2. Вправа 18.4 теми 2. Вправа 18є.4 теми 2. Вправа 19.4 теми 2. Вправа 21.4 теми 2. Вправа 23.4 теми 2. Вправа 24.4 теми 2. Вправа 27 теми 2. Вправа 27а.4 теми 2. Вправа 1.4 теми 4. Вправа 23.4 теми 4. Вправа 1.4 теми 16. Вправа 2.1 теми 16. Вправа 21.1 теми 16. Вправа 1.4 теми 17. Вправа 2.4 теми 17. Вправа 1.4 теми 18.


Варіант 5.

Вправа 1.5 теми 2. Вправа 3.5 теми 2. Вправа 13.5 теми 2. Вправа 8.1 теми 2. Вправа 18.5 теми 2. Вправа 18є.5 теми 2. Вправа 19.5 теми 2. Вправа 21.5 теми 2. Вправа 23.5 теми 2. Вправа 24.5 теми 2. Вправа 27 теми 2. Вправа 27а.5 теми 2. Вправа 1.5 теми 4. Вправа 23.5 теми 4. Вправа 1.5 теми 16. Вправа 2.2 теми 16. Вправа 21.2 теми 16. Вправа 1.5 теми 17. Вправа 2.5 теми 17. Вправа 1.5 теми 18.


Варіант 6.

Вправа 1.6 теми 2. Вправа 3.6 теми 2. Вправа 13.6 теми 2. Вправа 8.2 теми 2. Вправа 18.6 теми 2. Вправа 18є.6 теми 2. Вправа 19.6 теми 2. Вправа 21.6 теми 2. Вправа 23.6 теми 2. Вправа 24.6 теми 2. Вправа 27 теми 2. Вправа 27а.6 теми 2. Вправа 1.6 теми 4. Вправа 23.6 теми 4. Вправа 1.6 теми 16. Вправа 2.3 теми 16. Вправа 21.3 теми 16. Вправа 1.6 теми 17. Вправа 2.1 теми 17. Вправа 1.6 теми 18.


Варіант 7.

Вправа 1.7 теми 2. Вправа 3.7 теми 2. Вправа 13.7 теми 2. Вправа 8.3 теми 2. Вправа 18.7 теми 2. Вправа 18є.7 теми 2. Вправа 19.7 теми 2. Вправа 21.7 теми 2. Вправа 23.1 теми 2. Вправа 24.1 теми 2. Вправа 27 теми 2. Вправа 27а.1 теми 2. Вправа 1.7 теми 4. Вправа 23.7 теми 4. Вправа 1.1 теми 16. Вправа 2.1 теми 16. Вправа 21.1 теми 16. Вправа 1.7 теми 17. Вправа 2.2 теми 17. Вправа 1.1 теми 18.


Варіант 8.

Вправа 1.8 теми 2. Вправа 3.8 теми 2. Вправа 13.8 теми 2. Вправа 8.4 теми 2. Вправа 18.8 теми 2. Вправа 18є.8 теми 2. Вправа 19.8 теми 2. Вправа 21.8 теми 2. Вправа 23.2 теми 2. Вправа 24.2 теми 2. Вправа 27 теми 2. Вправа 27а.2 теми 2. Вправа 1.8 теми 4. Вправа 23.8 теми 4. Вправа 1.2 теми 16. Вправа 2.2 теми 16. Вправа 21.2 теми 16. Вправа 1.8 теми 17. Вправа 2.3 теми 17. Вправа 1.2 теми 18.


Варіант 9.

Вправа 1.9 теми 2. Вправа 3.9 теми 2. Вправа 13.9 теми 2. Вправа 8.1 теми 2. Вправа 18.9 теми 2. Вправа 18є.9 теми 2. Вправа 19.9 теми 2. Вправа 21.9 теми 2. Вправа 23.3 теми 2. Вправа 24.3 теми 2. Вправа 27 теми 2. Вправа 27а.3 теми 2. Вправа 1.9 теми 4. 23.1 теми 4. Вправа 1.3 теми 16. Вправа 2.3 теми 16. Вправа 21.3 теми 16. Вправа 1.1 теми 17. Вправа 2.4 теми 17. Вправа 1.3 теми 18.


Варіант 10.

Вправа 1.10 теми 2. Вправа 3.10 теми 2. Вправа 13.10 теми 2. Вправа 8.2 теми 2. Вправа 18.10 теми 2. Вправа 18є.10 теми 2. Вправа 19.10 теми 2. Вправа 21.10 теми 2. Вправа 23.4 теми 2. Вправа 24.4 теми 2. Вправа 27 теми 2. Вправа 27а.4 теми 2. Вправа 1.10 теми 4. Вправа 23.2 теми 4. Вправа 1.4 теми 16. Вправа 2.1 теми 16. Вправа 21.1 теми 16. Вправа 1.2 теми 17. Вправа 2.5 теми 17. Вправа 1.4 теми 18.


Контрольна робота №2 (за другий семестр)
Вправи та приклади їх виконання до розділу І. ПРОБЛЕМАТИКА ТА ВЗАЄМОЗВ’ЯЗОК РОЗДІЛІВ КУРСУ.

Тема 2. Множини, функції, відношення, графи, алгебраїчні системи та їх роль у моделюванні.

Вправа 1. Нехай U={a,d,c,d,e,f,g,h}. Необхідно задати об’єднання, перетин, різницю множин S та T, доповнення множини S до множини U, доповнення множини S T до множини U


  1. S={a,b,c}; T={b,c,f}; 6) S={g,d,f,a}; T={b,c,e};

  2. S={d,f,g}; T={d,g,h}; 7) S={a}; T={a,b,f,h};

  3. S={a,b,c,d}; T={d,e,f,g}; 8) S={a,b,e,f}; T=Ø;

  4. S={h,g,d}; T={a,b,d,g}; 9) S=U; T={a,b,e,h};

  5. S={g,d,b,c}; T={b,c,d}; 10) S=U; T=Ø.

Приклад: S={a,b,c}, T={b,c,f}. Об’єднання ST=={a,b,c,f}

Перетин ST={b,c}. Різниця S\T={a}. Декартовий добуток ST=

{(a,b), (a,c), (a,f), (b,b), (b,c), (b,f), ), (c,b), (c,c), (c,f)}.

Доповнення S={d,e,f,g,h}. Доповнення (ST)={a,d,e,f,g,h}.



Вправа 3. Нехай S та T -множини із вправи 1. Необхідно задати:

1. Функцію із S в T : а) довільну; б) ін’єктивну; с) сюр’єктивну; г) бієктивну.



Приклад: F1={(a,b), (b,b), (c,c)} –довільна функція із S в T;

F2={(a,b), (b,c), (c,f)} - сюр’єктивна функція із S в T;

F2 також є ін’єктивне, отже, вона є бієктивною функцією із S в T.

2. Довільну функцію із T в S.



Приклад: F3={(b,c), (c,b), (f,a)} - довільна функція із T в S.

3. Ліву та праву композиції функції із T в S та із S в T.



Приклад: F1 F3 ={(b,c), (c,b), (f,b)} -ліва композиція;

F1F3 ={(c,b), (b,c), (a,c)} -права композиція.

4. Функцію із S в S.



F4={(a,b), (b,с), (c,а)} - довільна функція із S в S.

5. Тотожні функції tS та tT.



Приклад: S={a,b,c}; T={b,c,f}.

tS = {(a,a), (b,b), (c,c)}, tT = {(b,b), (c,c), (f,f))}.

6. Обернену зправа та зліва для бієктивної функції із S в T.



Приклад: F2 - бієктивна функція із S в T;

F= {(b,a), (c,b), (f,c)} – обернена зліва для F2 , знайдена з рівняння FF2 =tS

чи F ◦ {(a,b), (b,c), (c,f)} = {(a,a), (b,b), (c,c)};



F={(b,a), (c,b), (f,c)} - обернена зправа для F2 , знайдена з рівняння F2 F=tT

чи {(a,b), (b,c), (c,f)} ◦ F= {(b,b), (c,c), (f,f)}.

7. Обернену зправа та зліва для ін’єктивної, але не сюр’єктивної функції із S в T.

Приклад: Нехай S={a,b}, T={b,c,f}. F5= {(a,b), (b,c)} - ін’єктивна, але не сюр’єктивна функція із S в T.

F’5= {(b,a,), (c,b)} – часткова функція із T в S , обернена зліва для функції F5 , знайдена з рівняння F’5 F5 = tS чи F’5 ◦{(a,b), (b,c)} = {(a,a), (b,b)}.

Функції із T в S ,оберненої зправа для функції F5 , не існує, оскількі рівняння



F5 F’5= tT чи {(a,b), (b,c)} ◦ F”5={(b,b), (c,c), (f,f))} не має розв”язку на множині функції із

TS в S.

8. Обернену зправа та зліва для сюр”єктивної , але не ін”єктивної функції із S в T.



Приклад: Нехай S={a,b,c}, T={c,f}. F6= {(a,c), (b,c), (c,f) } - сюр’єктивна, але не ін’єктивна функція із S в T. F”6= {(c,a,), (f,c)} - обернена зправа для F6 , знайдена з рівняння

F6 F”6 = tT чи {(a,c), (b,c), (c,f) } ◦ F”6 = {(c,c), (f,f)}.

Оскільки рівняння має ще один ров”язок F”6 ={(c,b,), (f,c)}, то цей ров”язок теж становить функцію, обернену справа для F6 .

Функція із Т в S, оберненої зліва для функції F6 , не існує, тому що рівняння

F 6 ◦ F = ts чи F’6 {(а,с),(b,c),(с,f)} = {(а,а),(b,b),(с,с)} не має розв’язку на множині функцій із Т в S /хоч це рівняння має розв’язок на множині бінарних відношень/:

F’6={(с,a),(с,b),(f,c)}.

Вправа 8. Нехай задана множина Х . Необхідно задати за допомогою графіка відношення на Х : а/ довільне; б/ рефлексивне;

в/ симетричне; г/ антисиметричне; д/ транзитивне; є/ таке, яке

мало б змістовну трактовку:

1/ X= {1,2,3,4,5,6}; 2/ X= {a,b,c,d,f};

3/ X={5,6,7,8,9,10}; 4/ X={000, 001, 010, 011, 100, 101, 110, 111}



Приклад; α={(1,2), (4,3), (6,6)} - довільне відношення;

α2={(1,1), (2,2), (3,3), (4,4), (5,5), (6,6), (1,6)} -рефлексивне відношення;

α3={(1,2), (1,3), (2,4), (3,5), (4,6), (2,1), (3,1), (4,2), (5,3), (6,4)} - симетричне відношення;

α4={(1,1), (2,2), (3,3), (4,4), (5,5), (6,6),

(1,2), (1,3), (1,4), (1,5), (1,6), (2,3), (2,4), (2,5), (2,6), (3,4), (3,5), (3,6), (4,5),.(4,6), (5,6)}

-антисиметричне відношення;



α5={(1,2), (2,3), (1,3), (3,4), (1,4), (2,4), (4,4)} - транзитивне відношення.

Треба зауважити, що відношення α4 є також рефлексивним та

транзитивним; α6 = {(1,1), (1,2), (1,3), (1,4), (1,5), (1,6),

(2,2), (2,4), (2,6), (3,3), (3,6), (4,4), (5,5), (6,6)}-це відношення можна задати, як відношення " Х1 ділить Х2 націло", де (X1, Х2 ) - кожна пара з графіка відношення.

На множині Х={ 0,1,2,3,4,5,6 } задати бінарне відношення, для кожної пари ( xi xj ) графіка якого використовується умова xi. = xi+ xj .



Вправа 13. Задати відношення часткового порядку на множині:

1/ A={a1, a2, a3, a4, a5, a6 } ; 2/ B={b1, b2, b3, b4, b5, b6 } ;

3/ C={c1, c2, c3, c4, c5, c6 } ; 4/ D={d1, d2, d3, d4, d5, d6 } ;

5/ E={e1, e2, e3, e4, e5, e6 } ; 6/ F={f1, f2, f3, f4, f5, f6 } ;

7/ G={g1, g2, g3, g4, g5, g6 } ; 8/ H={h1, h2, h3, h4, h5, h6 } ;

9/ I={i1, i2, i3, i4, i5, i6 } ; 10/ J={j1, j2, j3, j4, j5, j6 } ;

11/ K={k1, k2, k3, k4, k5, k6 } ; 12/ L={l1, l2, l3, l4, l5, l6 } ;

13/ M={m1, m2, m3, m4, m5, m6 }; 14/ N={n1, n2, n3, n4, n5, n6 } ;

15/ P={p1, p2, p3, p4, p5, p6 } ; 16/ R={r1, r2, r3, r4, r5, r6 } .

Приклад: Множина S={S1, S2, S3, S4, S5, S6 }

Відношеня



α1={ (S1,S1),(S2,S2),(S3,S3),(S4,S4),(S5,S5),(S6,S6),(S1,S2),(S1,S3),(S1,S4),(S1,S5),

(S1,S6),(S2,S3),(S2,S4),(S2,S5),(S2,S6),(S3,S4),(S3,S5),(S3,S6),(S4,S5),(S4,S6),(S5,S6};

α2={(S1,S1),(S2,S2),(S3,S3),(S4,S4),(S5,S5),(S6,S6),(S1,S2),(S1,S3),(S1,S4),(S1,S5),

(S1,S6),(S2,S4),(S2,S6),(S3,S5),(S3,S6),(S4,S6),(S5,S6};

α3={(S1,S1),(S2,S2),(S3,S3),(S4,S4),(S5,S5),(S6,S6),(S1,S2),(S2,S3),(S1,S3)};

α4={(S1,S1),(S2,S2),(S3,S3),(S4,S4),(S5,S5),(S6,S6),(S1,S2),(S1,S3),(S2,S3),(S4,S5),(S4,S6),(S5,S6)}

є рефлексивними, антисиметричними, транзитивними; отже, ці відношення - відношення часткового порядку.



Вправа 18. Задати частковий порядок на множинах із вправи 13 та встановити межі та грані для підмножини, яка містить: а/ перший, третій та п’ятий елементи; б/ другий, третій та четвертий елементи.

Приклад: S={S1, S2, S3, S4, S5, S6 }. Нехай S впорядкована за допомогою відношення α1
  1   2   3


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

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