Конспект лекцій для студентів спеціальності №05010201 «Обслуговування комп’ютерних систем І мереж» 2015



Сторінка1/8
Дата конвертації20.11.2016
Розмір1.07 Mb.
  1   2   3   4   5   6   7   8
Міністерство освіти і науки України

Новоград-Волинський промислово-економічний технікум

Дискретна математика

КОНСПЕКТ ЛЕКЦІЙ

для студентів спеціальності

№ 5.05010201 «Обслуговування комп’ютерних систем і мереж»

2015

Укладач : Поперечнюк Людмила Миколаївна, викладач Новоград-Волинського промислово-економічного технікуму



Рецензент: Пекарський Б.Г., викладач вищої категорії, викладач-методист НВПЕТ

Схвалено на засіданні циклової

комісії комп’ютерних дисциплін

Протокол № від “___”_______ 2015 р.

Голова комісії ______________Пекарський Б.Г.

ЗМІСТ




ВСТУП


Згідно навчального плану студенти спеціальності № 5.05010201 «Обслуговування комп’ютерних систем і мереж» вивчають курс навчальної дисципліни «Дискретна математика» в загальному обсязі 162 години. Кількість теоретичних занять ЁC 46 годин, практичних ЁC 26 годин, самостійна робота ЁC 90 годин.

В курсі «Дискретна математика» розкривається сутність дискретних процесів. Обмін інформацією в комп’ютерних мережах здійснюється за допомогою сигналів, які за своїм видом можуть бути аналоговими (неперервними) і дискретними.

Дискретна математика (скінченна математика) ЁC розділ математики, що вивчає властивості об’єктів дискретного характеру. Під дискретними об’єктами в математиці розуміють ті, які в сукупності утворюють скінченну або зчисленну множину. Дискретні об’єкти принципово відрізняються від неперервних (таких, наприклад, як всі дійсні числа з відрізка µ §).

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

Основними задачами дискретної математики є:

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

побудова дискретних об’єктів, які задовольняють заданим властивостям (синтез).

У результаті вивчення навчальної дисципліни, студенти повинні

ЗНАТИ:

історію розвитку математичного апарату, орієнтованого на дискретні процеси;



мову теорії множин, алгебри логіки, теорії графів та відношень;

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

апарат дискретної математики, який застосовується в розробці програмного забезпечення ЕОМ.

ВМІТИ:


аналізувати логічну і алгоритмічну структури процесів переробки інформації в природі та суспільстві;

застосовувати апарат дискретної математики в формалізації математичного дослідження задач науки та виробництва;

вирішувати завдання, пов’язані з теорією множин, алгеброю логіки, теорією графів та відношень.

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

Розділ І «Теорія множин».

ТЕМА 1.1: Теорія множин. Відношення і функції.

1.1.1. Теорія множин.

План


Множини. Основні поняття теорії множин. Кортеж.

Операції над множинами. Частково впорядковані множини.

Алгебра множин.

Потужність.

1. Множини. Основні поняття теорії множин. Кортеж.

Визначення. Множиною М називається об’єднання в єдине ціле певних помітних однотипних об’єктів а, які називаються елементами множини (А „Ў М).

Множину можна описати, указавши якусь властивість, властиву всім елементам цієї множини.

Зауваження. Загалом кажучи, поняття множини вважається первинним (вихідним) поняттям, і, як таке, не визначається. Наведене вище визначення треба, скоріше, уважати уточненням поняття множини.

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

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

Множина, що не містить елементів, називається порожньою і позначається символом „w.

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

Приклад. Деякі приклади множин, заданих різними способами.

А) µ §.


Б) µ §.

В) µ § µ §.

Потужністю кінцевої множини М називається кількість її елементів. Позначається µ §. Якщо µ §, то множини А і В називаються рівнопотужними.

Визначення. Якщо всі елементи множини А є також елементами множини В, то говорять, що множина А включається (утримується) у множині В.

А

В

А µ § В.



Визначення. Якщо А „~ В, то множина А називається підмножиною множини В (також говорять, що В покриває А). Якщо при цьому А „j В, то множина А називається власною підмножиною множини В і позначається А „} В.

Зауваження. Не слід вважати рівносильними відношення належності µ §й входження однієї множини в іншу µ §.

Приклад. Нехай А ЁC множина всіх студентів даної групи, а В ЁC множина всіх навчальних груп даного інституту. Тут µ §, але µ §, оскільки елементи цих множин різнорідні. Цей приклад показує також, що елементами множин можуть бути інші множини.

Парадокс Рассела. Задання множин характеристичним предикатом може привести до протиріч. Розглянемо множину всіх множин, що не містять себе як елемент: µ §. Якщо така множина існує, то можна відповістити на наступне запитання: чи належить вона сама собі. З одного боку, якщо µ §, те µ §. З іншого боку, якщо µ §, то µ §!

Г. Кантор запропонував використати поняття “універсальної множини” (универсум), як би протилежного поняттю порожньої множини µ §. По думці Кантора, універсальна множина µ § містить всі мислимі множини і при цьому вона сама втримується в множині своїх підмножин як елемент.

2. Операції над множинами. Частково впорядковані множини.

Визначення. Об’єднанням множин А і В називається множина С, елементи якої належать хоча б одній з множин А і В.

Позначається С = Аµ § В.

А В

Геометричне зображення множин у вигляді області на площині називається діаграмою Эйлера ЁC Вена.



Визначення. Перетином множин А і В називається множина С, елементи якої належать кожній з множин А і В.

Позначення С = А µ § В.

А С В

µ §„w = А; A „x „w = „w;



Визначення. Різницею множин А і В називається множина, що складається з елементів множини А, яка не належить множині В.

Позначається: С= А \ В.

А В

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



Позначається: А µ § В.

Аµ § В = (A \ B) µ §( (B \ A)

A B

Включення (об’єднання).



Множина А входить (включено) у множину В, або А є підмножиною В. µ §

Якщо всякий об’єкт, що володіє властивістю µ §, також має властивість µ §, то говорять, що властивість µ § включає властивість µ §, тобто µ §

Сума.

Сума множин А і В є множина С, що включає в себе всі елементи множин А і В.



Об’єкт входить у множину µ § якщо він входить у множину А або в множину В.

µ §


Перетин (добуток).

Перетином множин А і В називається нова множина С. Елементи множини С належать множинаі А (володіють її властивостями) і множини В (володіють її властивостями).

µ §

Вирахування (різниця).



Різницею множин А і В є множина С, елементи якої мають властивості множини А і не мають властивостей множини В або належать множині А і не належать множині В.

µ §


Доповнення.

Якщо є деяка універсальна множина (универсум) U і всі розглянуті множини є її підмножини, то доповненням µ § називається така множина, елементи якої не входять в А, але належать U.

Графічне подання.

(Діаграми Эйлера, Венна)

1.

µ §


2.

µ §


В

А

3.



µ §

U

4.



µ §

3. Алгебра множин.

Основні тотожності алгебри множи.

Незалежність розташування:

µ § (1)

µ § (2)


Асоціативність:

µ § (3)


µ § (4)

Дистрибутивність:

µ §

µ § (7)


µ § (8)

µ § (9)


µ § (10)

µ § (11)


µ § (12)

Закони де Моргана

µ §

4. Потужність.



Дві множини А і В називають рівнопотужними (еквівалентними), якщо між ними можна встановити бієкцію (взаємно-однозначну відповідність):

Саме в цьому сенсі буде вживатися запис |А| = |В|.

Як показує попередній приклад, існування ін’єкції ,

для якої зовсім не означає, що множина А має «меншу» кількість елементів, ніж В.

Будемо говорити, що потужність множини А менша за потужність множини В і писати |А| < |В|, якщо і ці множини не є рівнопотужними.

Якщо ці означення мають сенс, то повинна мати місце імплікація:

(Теорема Кантора-Бернштейна)

Контрольні запитання

Що називають множиною?

Які бувають множини?

Назвати способи задання множин.

Яке графічне зображення має різниця, об’єднання, перетин множин.

Які властивості множин?

ТЕМА 1.1: Теорія множин. Відношення і функції.

1.1.2. Відношення та їх властивості.

План


Відношення. Бінарні відношення і способи їх задання.

Властивості бінарних відношень.

Відношення еквівалентності і порядку.

Операції над відношеннями. Бази даних і відношення.

Відношення. Бінарні відношення і способи їх задання.

Визначення. Підмножина µ § називається µ § мірним відношенням на множині А. Говорять, що елементи µ § перебувають у відношенні µ §, якщо µ §.

Одномісне (одномірне) відношення ЁC це просто деяка підмножина А. Такі відносини називають ознаками. Говорять, що µ § має ознаку µ §, якщо µ § й µ §. Властивості одномісних відношень ЁC це властивості підмножини А, тому для випадку µ § термін “відношення” вживається рідко.

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

Бінарні відношення.

Квадратом множини А називається декартів добуток множини самої на себе µ §

Бінарним відношенням Т у множині А будемо називати підмножину його квадрата

µ §


Будь-які елементи декартові добутки µ § перебувають у бінарному відношенні, якщо µ §, говорять, що µ § зв’язано відношенням Т.

Областю значень (зміною бінарного відношення) називається множина µ §, підлегла умові

µ §

Способи задання бінарних відношень.



1.

Бінарні відношення на площині можна відобразити за допомогою графів. Елементи множини µ § позначаються вершинами графів. Якщо пари µ §, то вершини а й у з'єднуються ланкою (дугою).

Наприклад:

(ав)(вс)(ас)(аа)

2. Будь-яке бінарне відношення може бути задане у вигляді списку , елементами якого є пари , з яких складається відношення.

3. Бінарне відношення R на множинах Х і У може бути задане за допомогою матриці (W=W (R)), рядки якої відповідають елементам множини Х , стовпці ЁC елементам множини У.

4. Як відомо з курсу математики пари (x,y), де µ § зображують на координатній площині крапкою, тоді множина µ § відобразиться координатною площиною, а його підмножина, тобто бінарне відношення відобразиться відповідним графіком цих відношень.

µ §


Якщо повне відношення задане за допомогою матриці , то всі елементи цієї матриці дорівнюють одиниці . Матриця порожнього відношення складається з нульових елементів.

2. Властивості бінарних відношень.

Нехай µ § ЁC бінарне відношення на довільній множині µ § (µ §). Якщо для двох елементів µ § µ §, тобто µ §знаходяться у відношенні µ §, то це записують як µ §. Якщо для двох елементів µ § не виконується µ §, то це записують як µ §.

Бінарне відношення µ § на довільній множині µ § можна зобразити за допомогою графа ЁC стрілкової схеми, вузли якої відповідають елементам множини µ §, а дуга, спрямована від µ § до µ § показує, що виконується µ §.

Визначення. Відношення µ § називається рефлексивним, якщо воно завжди виконується між елементом і ним самим. (µ §).

Приклади.

Відношення нестрогої нерівності на множинах µ §.

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

Визначення. Відношення µ § називається антирефлексивним, якщо воно не виконується для будь-якого елемента. (µ §).

Приклади.

1. Відношення строгої рівності на множинах µ §.

2. Відношення „бути начальником”, „бути братом”, „бути молодшим” на множині людей.

Приклад. Відношення, яке не є ні рефлексивним, ні антирефлексивним :

Відношення ”бути симетричним відносно осі µ §” не є ні рефлексивним, ні антирефлексивним (точка є симетричною самій собі, якщо вона лежить на осі µ §, і не є симетричною самій собі в протилежному випадку)

Визначення. Відношення µ § називається симетричним, якщо для будь-яких елементів µ § при виконанні µ § виконується µ §. (µ §).

Приклади.

1. Відношення рівності на множинах µ §.

2. ”Бути симетричним відносно осі µ §”.

3. Відношення „бути братом” на множині людей.

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

Визначення. Відношення µ § називається антисиметричним, якщо µ § і µ § виконуються одночасно тоді і тільки тоді, коли µ §. (µ §)

Приклади.

1. Відношення нестрогої нерівності на множинах µ §.

µ § и µ §µ §.

На графі антисиметричного відношення існує хоча б одна пара вузлів, які зв’язані двома стрілками.

Зауваження. Властивості симетричності і антисиметричності не є взаємно виключними.

Визначення. Відношення µ § називається асиметричним, якщо для будь-яких елементів µ § або µ § або µ §. (µ §)

Приклади.

1. Відношення строгого включення в множині всіх підмножин деякого універсуму.

2. Відношення „бути батьком” в множині людей.

Визначення. Відношення µ § називається транзитивним, якщо для будь-яких µ §µ § з µ § і µ § випливає µ §. (µ §)

Приклади.

1. Відношення =, µ §, «жити в одному місті».

2. Відношення ‘‘мати непорожній переріз’’ на системі множин не є транзитивним.

На графі транзитивного відношення для кожної пари стрілок, напрямлених від µ § до µ § і від µ § до µ § існує також стрілка, напрямлена від µ § до µ §.

3. Відношення еквівалентності та відношення порядку.

Відношення еквівалентності.

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

ВЛАСТИВОСТІ:

1. Нехай µ § - бінарне відношення, µ § - область його завдання, тоді µ § називається рефлексивним, якщо µ §, граф таких відносин має вигляд петлі при кожній вершині

2. µ §називається ін’єктивним, бієктивним, якщо µ §.

3. Відношення може бути симетричним, якщо

µ §(зображується будь-яким графом)

4. Антисиметричним, якщо µ § (зображується орієнтованим графом)

Транзитивним. Відношення називається транзитивним, якщо µ § (зображується транзитивним графом ЁC всі вершини перетинаються).

Якщо для бінарного відношення µ § дотримується три умови: ін’єктивності, симетричність і транзитивність, то таке відношення називається еквівалентністю.

Приклад.

А) Відношення рівності (часто позначається µ §) на будь-якій множині є відношення еквівалентності. Рівність ЁC це мінімальне відношення еквівалентності в тому розумінні, що при видаленні будь-якої пари із цього відношення (тобто будь-якої одиниці на головній діагоналі матриці µ §) воно перестає бути рефлексивним й, отже, уже не є еквівалентністю.

Б) Твердження виду µ § або µ §, що складаються з формул, з’єднаних знайомими рівностями, задають бінарне відношення на множині формул, що описують суперпозиції елементарних функцій. Це відношення звичайно називається відношенням рівносильності й визначається в такий спосіб: дві формули рівносильні, якщо вони задають ту саму функцію. Рівносильність у цьому випадку, хоча й позначена “=”, означає не те ж саме, що відношення рівності, тому що воно може виконуватися для різних формул. Втім, можна вважати, що знак рівності в таких відношеннях ставиться не до самих формул, а до функцій, які ними описуються. Для формул же відношення рівності ЁC це збіг формул за написанням. Воно називається графічною рівністю. До речі, щоб у подібних ситуаціях уникнути різночитань, часто для позначення відношень рівносильності використають знак “µ § ”.

Відношення порядку.

З поняття рівності між числами випливає більш широке поняття відношення еквівалентності на множинах. За аналогією деякі нерівності також можуть бути використані як моделі для більш широкого класу відношень.

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

Відношення нестрогого порядку є узагальненням відношення µ § на множині натуральних чисел µ §, тому можна легко перевірити властивості цього відношення:

1) рефлексивність: µ §

2) антисиметричність: µ §;

3) транзитивність: µ §

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

Відношення строгого порядку є узагальненням відношення µ § на множині натуральних чисел µ §, тому можна легко перевірити властивості цього відношення:

1) антирефлексивність: µ §

2) асиметричність: µ §;

3) транзитивність: µ §

Обидва типи відношень називаються відношенням порядку.

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

Визначення. Відношення порядку називається відношенням лінійного порядку, якщо додатково виконується властивість: µ § (для нестрогого порядку) або µ §(для строгого порядку).

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

Приклади:

1. µ § і µ § ЁC відношення нестрогого порядку для чисел; µ § і µ § ЁC відношення строгого порядку. Обидва відношення цілком впорядковують множини µ § і µ §.

2. На множині підмножин множини µ § відношення нестрогого включення µ § задає нестрогий частковий порядок, а відношення строгого включення µ § задає строгий частковий порядок.

Перевіримо властивості відношення нестрогого включення µ §:

1) рефлексивність: µ §;

2) антисимметричність: µ §;

3) транзитивність: µ §.

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

Визначення. Відношення називається відношенням толерантності, якщо воно рефлексивне, симетричне, але не транзитивне.

Операції над відношеннями.

Декартовим добутком множин Хµ §ЧХµ §ЧХµ §ЎKХµ § називається множина всіх можливих упорядкованих наборів з n елементів ( які називають кортежами довжини n), в яких перший елемент належить множині Хµ §, другий - Хµ §ЎKn-й ЁC множині Хµ §.

Декартів добуток Хµ §ЧХµ §ЧХµ §ЎKХµ §, в якому одна й та ж множина Х помножиться n раз сама на себе , називають декартовим степенем множини і позначають Хn . При цьому Х1=Х.

Множину Х2 називають декартовим квадратом множини Х.

Визначення. Нехай R ЁCбінарне відношення . Обернене відношення до R позначається R-1 тоді і тільки тоді , коли (х,у) належить R.

Якщо Rµ §, то R-1µ §

Якщо бінарне відношення задане на двох множинах, то граф відношення можна побудувати таким чином . Вершини графа, що відповідають елементам першої множини, розташовуються ліворуч вершин графа, що відповідають елементам другої множини, розташовуються праворуч. Таким чином дуги графа спрямовані зліва на право. Нехай задані множини А =µ §, В=µ § і відношення R=µ §. Для того, щоб побудувати граф відношення R-1 змінимо напрямки дуг.

Визначення. Нехай R і S ЁC відношення, такі, що Rµ §, Sµ §- деякі множини. Композицією відношень R і S називається відношення, що складається з упорядкованих пар (x,z) , xµ §zµ §, для яких існує елемент у µ §Y, такі, що виконуються умови (х,у) µ §. Композиція відношень R і S позначається Sµ § R.

Визначення. Нехай R- деяке відношення , визначене на множині Х: Rµ §, тоді n- й степінь відношення R позначається Rn і визначається рекурсивно так : R0 ЁC тотожне відношення на множині Х. Rn = Rn-1µ § R , для n=1,2ЎK

Графічне представлення відношень.

Графічні представлення відношень мають властивість наочності (при невеликих µ §) і можливі в наступних формах:

1. Графіки. В декартовій системі координат на осях (ось абсцис відповідає області визначення µ §, ось ординат ЁC області значень µ §) відмічаються точки, які являють собою елементи множин µ § і µ §, на яких визначено відношення µ §. Потім відмічаються точки з координатами µ §, в яких µ §, µ §.

Наприклад, графіки відношень з прикладів 1, 2 і 4 мають відповідно такий вигляд:

1 2 3


2. Стрілкова схема 1. В декартовій системі координат на осях відмічаються точки, що являють собою елементи множин µ § і µ §, на яких визначено відношення µ §. Потім з’єднуються стрілками точки на осях, які відповідають елементам µ §.

Приклад. Стрілкова схема 1 для прикладу має вигляд:

4

Стрілкова схема 2. На двох вертикальних лініях відмічаються точки, які являють собою елементи множин µ § і µ §. Потім з’єднуються стрілками точки на осях, які відповідають елементам µ §.



Приклад. Стрілкова схема 2 для прикладу має вигляд:

Стрілкова схема 3. Будується графічна діаграма у вигляді множин точок (вузлів), які являють собою елементи множин µ § і µ §. Потім з’єднуються стрілками пари точок, які входять у відношення µ §.

Приклад. Стрілкова схема 3 для прикладу має вигляд:

Крім графічного представлення для задання бінарних відношень ще використовують таблиці з двома входами (матриці), які являють собою елементи множин µ § і µ §. Пари, які входять у відношення µ §, зображуються спеціальним символом, наприклад, 1, на перерізі відповідних рядків і стовпців.

Приклад. Таблиця для прикладу має вигляд:

µ § µ §123456111111020101003001000400000050000006000000

Контрольні запитання

Що називають відношенням?

Які способи задання бінарних відношень?

Які властивості відношень?

Яке відношення називають відношенням еквівалентності та порядку?

Як пояснити композицію відношень?

ТЕМА 1.1: Теорія множин. Відношення і функції.

1.1.3. Функції та відображення. Спеціальні функції.

План

Функції.



Спеціальні функції. Зростання функцій.

1. Функції та функціональні відображення.

Твердження виду µ § або µ §, що складаються з формул, з'єднаних знайомими рівностями, задають бінарне відношення на множині формул, що описують суперпозиції елементарних функцій. Це відношення звичайно називається відношенням рівносильності й визначається в такий спосіб: дві формули рівносильні, якщо вони задають ту саму функцію. Рівносильність у цьому випадку, хоча й позначена “=”, означає не те ж саме, що відношення рівності, тому що воно може виконуватися для різних формул. Втім, можна вважати, що знак рівності в таких відношеннях ставиться не до самих формул, а до функцій, які ними описуються. Для формул же відношення рівності ЁC це збіг формул за написанням. Воно називається графічною рівністю. До речі, щоб у подібних ситуаціях уникнути різночитань, часто для позначення відношень рівносильності використають знак “µ § ”.

  1   2   3   4   5   6   7   8


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

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