Конспект лекцій з дисципліни «Дискретний аналіз» для студентів спеціальності 050. 102 «Економічна кібернетика» icon

Конспект лекцій з дисципліни «Дискретний аналіз» для студентів спеціальності 050. 102 «Економічна кібернетика»




Скачать 463.33 Kb.
НазваниеКонспект лекцій з дисципліни «Дискретний аналіз» для студентів спеціальності 050. 102 «Економічна кібернетика»
страница1/6
Дата конвертации09.04.2013
Размер463.33 Kb.
ТипКонспект
источник
  1   2   3   4   5   6

Міністерство освіти і науки України

Одеський національний політехнічний університет


Андрієнко В.М., Будорацька Т.Л.

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

з дисципліни «Дискретний аналіз»

для студентів спеціальності 7.050.102 «Економічна кібернетика»

денної та заочної форм навчання


Затверджено на засіданні кафедри інформаційних систем у менеджменті

Протокол № 5 від 27. 12 .2007 р.



Одеса ОНПУ 2007


Міністерство освіти і науки України

Одеський національний політехнічний університет


Андрієнко В.М., Будорацька Т.Л.


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

з дисципліни «Діскретний аналіз»

для студентів спеціальності 7.050.102 «Економічна кібернетика»

денної та заочної форм навчання


Одеса ОНПУ 2007


Конспект лекцій з дисципліни «Дискретний аналіз» для студентів спеціальності 7.050.102 «Економічна кібернетика» денної та заочної форм навчання / Укл.: В.М. Андрієнко,

Т.Л. Будорацька. – Одеса: ОНПУ, 2007. - 26 с.

Укладачі.: В.М. Андрієнко, канд. екон. наук, доц.,

Т.Л.Будорацька,старший викладач

^ Лекція I,2. ЕЛЕМЕНТИ ТЕОРІЇ МНОЖИН


Основні означення теорії множин, операції

над множинами, властивості операцій над множинами

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

Множини будемо позначати прописними латинськими буквами A,B,C, …, X, Y, Z, а елементи, що належать даним множинам - рядковими a, b, c, …, x, y, z…. Якщо a є елемент множини A, то пишуть . Якщо a не є елементом множини A, пишуть .

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

Вихідна множина називається універсальною і позначаються U.

Якщо всі елементи множини ^ A є також елементами множини B, то говорять, що А включається в B або A є підмножиною множини B і позначається . Якщо , то говорять, що ^ A=B або A збігається з B.

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

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

Рисунок 1. Диграма Ейлера- Вена.


^ Об'єднанням двох множин A і B називається множина, яка складається з елементів, що входять хоча б в одну з даних множин, воно позначається .

={x: xA або xB },

Відповідна диграма Ейлера- Вена:




Рисунок 2. Об'єднання двох множин

Об'єднанням деякої сукупності множин називається множина S, яка складається з усіх елементів, що входять хоча б в одну з множин, і позначається .

Перетином двох множин A і B називається множина, яка складається з усіх елементів, що належать як множині A, так і множині B, і позначається .

={x: xA і xB }

Про дві множини A і B говорять що вони не перетинаються, якщо їх перетин порожній.

Відповідна диграма Ейлера- Вена:




Рисунок 3. Перетин двох множин


Перетином деякої сукупності множин називається множина P, яка складається з усіх елементів, що входять у всі множини і позначається .

Різницею двох множин A і B називається множина, яка складається з усіх тих елементів множини A, що не належать множині B. Різниця позначається A \ B.

A \ B = {x: xA і xB }

Відповідна диграма Ейлера- Вена:




Рисунок 4. Різниця двох множин

Прямим (або Декартовим) добутком двох множин A і B називається множина всіх пар

(x, y), де . Декартів добуток множин A і B позначається .

^ Доповненням до множини A називається множина , що складається з елементів універсальної множини, U які не належать множині A, тобто .




Рисунок 5. Доповненням до множини A


Операції над множинами мають такі властивості:

  1. Комутативність: .

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

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

  4. Закони де Моргана: .


Приклад 1. Нехай . Знайти .

Розв’язок: об'єднання - це є множина S={x: xA або xB }, Отже, .

Перетин - це множина P= {x: xA і xB }, Отже,

Різниця A\B - це множина R = {x: xA і xB }, тобто , аналогічно

Доповнення до множини A - це множина ;

Прямий добуток ={(4,2), (4,4),(4,7),(4,9),(7,2),(7,4),(7,7),(7,9),(8,2),(8,4),(8,7),(8,9)}.

Часто буває корисною рівність, що легко перевіряється

. (1)


Приклад 2. Довести рівність (1).

Для доведення рівності (1) необхідно показати:





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



Тепер нехай . З означення перетину випливає, що , а це еквівалентно такому: . Останнє означає, що .

Стислий запис цього міркування виглядає так:



Рівність доведена.

^ Лекція 3. БІНАРНІ ВІДНОШЕННЯ


Бінарним відношенням R на множині A називається будь-яка підмножина R декартова добутку AA . Наприклад, А = {1,2,3}, AA = {(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)},

^ R - підмножина пар, де перша цифра – непарная. Належність пари (x, y) відношенню R позначають

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

1. Аналітичний.

Для завдання R на множині А потрібно указати всі пари (x,y) AA, які містяться в R, тобто для яких виконується R.

2. Завдання матрицею.




  1. Завдання графом.

Елементи множини А відповідають вершинам графа, а відповідає дуги .

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

Нехай і - відношення. ^ Перетин відповідає перетину множин, об’єднання -

об’єднанню множин.

Повернутим до відношення R називають відношення , яке визначається умовою



Якщо R – відношення «більше», то - відношення «менше». Дійсно, коли xy

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

Бінарне відношення R називається відношенням еквівалентності, якщо воно має властивості:

Рефлексивності - Симетричності -

Транзитивності -

Бінарне відношення R називається відношенням порядку, якщо воно має властивості: рефлексивності, транзитивності, антисиметричності -

Приклад 3. Нехай N - множина натуральних чисел. На множині N x N визначимо R у такий спосіб: Показати, що R є відношенням еквівалентності.

Розв’язок. Покажемо, що виконується властивість рефлексивності, тобто

a+b = a+b – очевидно виконується.

Симетричність: тобто з рівності a+d=b+c випливає c+b=d+a - очевидно виконується.

Транзитивність: , тобто з рівності

a + d = b + c; c+ f = d + e випливає рівність a + f = b + e. Додаючи вихідні рівності, одержимо

a + d + c + f = b + d + c + e, тобто a + f = b + e.

Таким чином, дане бінарне відношення є відношенням еквівалентності.

^ Розбиття множини на класи

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

Множина розбита на класи якщо , де , , , . Звичайно доводиться мати справу з розбиттями, побудованими на базі тієї чи іншої ознаки, за якою елементи множини об’еднуються у класи. Наприклад, множина усіх трикутників на площині можна розбити на класи рівних між собою чи на класи рівновеликих трикутників. Ознаки, за якими елементи множини розбиваються на класи, можуть бути найрізноманітнішими, але все ж така ознака не цілком довільна. Припустимо, наприклад, що ми захотіли розбити всі дійсні числа на класи, включаючи число b в той же клас, що і число a, у тім і тільки тім випадку, якщо . Ясно, що таким шляхом ніякого розбиття одержати не можна, тобто якщо , то слід зарахувати в той же клас, що і , разом з тим , тобто число a не можна включити в той же клас, що і b. Крім того, оскільки a не більше, ніж саме , то a не повинно потрапити в один клас із самим собою.

Для того, щоб відношення (ознака) дозволяло розбити множину M на класи, необхідно і достатньо, щоб воно було відношенням еквівалентності. Розбиття множини на класи проілюструємо за допомогою діаграми Ейлера - Венна. З Рисунка 6 видно, що вийшло вісім неперетинних підмножин. Виразимо ці підмножини через операції перетину і доповнення.

  1. 5.

  2. 6.

  3. 7.

  4. 8.




Рисунок 6. Розбиття множини на класи


Множина



Лекція 4,5. ЕЛЕМЕНТИ КОМБІНАТОРИКИ


Загальні правила комбінаторики


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

^ Правило множення. Якщо об'єкт A можна вибрати m способами і якщо після кожного такого вибору об'єкт B можна вибрати n способами, то вибір пари (A, B) можна здійснити m x n способами.

Правило додавання. Якщо деякий об'єкт А можна вибрати m способами, а інший об'єкт В можна вибрати n способами, то вибір “або А, або В” можна здійснити m + n способами.

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

Правила множення і додавання справедливі для будь-якого скінченого числа об'єктів.
^
Формула включень та виключень

Нехай є N предметів, деякі з них мають властивості . При цьому кожний предмет може або не мати жодної з цих властивостей, або має одну або декілька властивостей. Позначимо через число предметів, що мають властивостями Якщо предмет не має якоїсь властивості, то цю властивість пишемо з рискою. Наприклад, - число предметів, що мають властивості і не мають властивості . Число предметів, що не мають жодної з зазначених властивостей, позначається за цим правилом Формула включень та виключень полягає у тому, що



Тут алгебраїчна сума поширена на всі комбінації властивостей (без урахування їхнього порядку), причому знак + ставиться, якщо число властивостей що враховуються парне, і знак - , якщо це число непарне.

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

Приклад 4. У науково-дослідному інституті працює 67 осіб. З них 47 знають англійську мову, 35 - німецьку і 23 - обидві мови. Скільки співробітників в інституті не знають ні англійської, ні німецької мови?

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

четверту - ті, хто не знає жодної мови.

Застосуємо формулу включень та виключень, для цього запровадимо позначення:

- знання англійської мови; - знання німецької мови;

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




^ Перестановки, сполуки, розміщення.

Різні упорядковані множини, що відрізняються лише порядком елементів (тобто можуть бути отримані з тої ж самої множини), називаються перестановками цієї множини. Число різних перестановок із n елементів дорівнює

Довільна k - елементна підмножина n - елементної множини називається сполукою із n елементів по k. Число сполук із n елементів по k дорівнює

Упорядковані k - елементні підмножини з n елементів називаються розміщеннями із n елементів по k. Число розміщень із n елементів по k дорівнює

Застосовуючи формули числа перестановок, сполук і розміщень, слід виходити з означень цих понять.

Приклад 5. В ящику находиться 10 деталей, середи котрих 3 недосконалих. З ящика наугад витягають 5 деталей. Кількість існують способів витягнути деталі таким чином, щоб середи них окажетеся дві недосконалих , а три добрих.

Для рішення задачі застосуємо правило множення та сполуки.

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

^ Перестановки и сполуки з повтореннями.

Дотепер ми розглядали предмети, що були попарно різними. А тепер розглядатемо сукупності, у яких є однакові предмети. Нехай є предмети k різних типів, число предметів першого типу дорівнює , другого типу - k-го типу -

Число різних перестановок, що можна зробити з даних елементів, дорівнює

Число m - елементарних підмножин, порядок у який не приймається до уваги, дорівнює



Можно довести справедливость рівнянь:

1. (a+b)n= Cnkakbn-k. Ця формула носить назву бином Ньютона

2. Cnk.= 2n Цю формулу получаемо, якщо в формуле бинома a=b=1 .

3. . Цю формулу получаемо, якщо в формуле бинома a=1, b=1 .

4.

5.

Лекція 6. ЕЛЕМЕНТИ МАТЕМАТИЧНОЇ ЛОГІКИ


Логічні операції та їхні властивості

Під елементарним висловленням будемо розуміти оповідальне речення, про яке можна сказати однозначно: істинне воно чи хибне. Позначають елементарні висловлення латинськими буквами: A, B, C, …, X, Y, Z, а їхні значення (істину або хибність) відповідно або 1 і 0. Над елементарними висловленнями можуть провадитися логічні операції: кон’юнкція, диз'юнкція, імплікація, еквівалентність, заперечення.

Кон’юнкція (позначається “ ” або “&”) двох висловлень утворить нове висловлення, яке істинне тоді і тільки тоді, коли A і B істинні. Кон’юнкції відповідає така істинностна таблиця:


A

B



1

1

1

1

0

0

0

1

0

0

0

0

Диз'юнкція (позначається “”) двох висловлень A B істинна тоді і тільки тоді, коли хоча б одне з висловлень істинне. Таблиця істинності.


A

B



1

1

1

1

0

1

0

1

1

0

0

0

Імплікація або проходження (позначається “ ”) / A B хибна тоді і тільки тоді, коли A - істинне, а B - хибна. Таблиця істинності така:


A

B



1

1

1

1

0

0

0

1

1

0

0

1


Еквівалентність або подвійна імплікація (позначається  або ) A B істинна тоді і тільки тоді, коли A і B обидва істинні або хибні. Таблиця істинності така:


A

B



1

1

1

1

0

0

0

1

0

0

0

1

Заперечення (позначається “-”) хибне тоді і тільки тоді, коли А істинне і навпаки.

Таблиця істинності:

A



1

0

0

1

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

  1. комутативність

  2. асоціативність

  3. дистрибутивність



  1. закони де Моргана



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

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

^ Лекція 7. ПЕРЕВІРКА ПРАВИЛЬНОСТІ МІРКУВАНЬ
  1   2   3   4   5   6

Добавить документ в свой блог или на сайт



Похожие:

Конспект лекцій з дисципліни «Дискретний аналіз» для студентів спеціальності 050. 102 «Економічна кібернетика» iconПротокол №5 від 27. 12. 2007 р
Методични вказівки до виконання самостійних завдань з дисципліни «Дискретний аналіз» для студентів спеціальності 050. 102 «Економічна...

Конспект лекцій з дисципліни «Дискретний аналіз» для студентів спеціальності 050. 102 «Економічна кібернетика» iconМетодичні вказівки до виконання курсового проекту з дисципліни "проектний аналіз " для студентів денної форми навчання спеціальності 050201 "Менеджмент організацій"
Методичні вказівки до виконання курсового проекту з дисципліни «Проектний аналіз" для студентів спеціальності 050201 "Менеджмент...

Конспект лекцій з дисципліни «Дискретний аналіз» для студентів спеціальності 050. 102 «Економічна кібернетика» iconМетодичні вказівки для вивчення дисципліни «інвестування» І завдання для контрольних робіт студентів спец. 050102 «Економічна кібернетика» інституту заочної освіти
Проблема інвестування – важлива і складна для об’єктів будь-якого рівня і форми власності

Конспект лекцій з дисципліни «Дискретний аналіз» для студентів спеціальності 050. 102 «Економічна кібернетика» iconМетодичні вказівки до виконання курсової роботи з дисципліни "Системне програмне забезпечення " для студентів спеціальності
Методичні вказівки розроблені для студентів денного і заочного відділень спеціальності «Спеціалізовані комп’ютерні системи» на підставі...

Конспект лекцій з дисципліни «Дискретний аналіз» для студентів спеціальності 050. 102 «Економічна кібернетика» iconКонспект лекцій з дисципліни „Бухгалтерський облік
Харакоз Л. В., Гордєєва-Герасимова Л. Ю. Опорний конспект лекцій з дисципліни «Бухгалтерський облік»

Конспект лекцій з дисципліни «Дискретний аналіз» для студентів спеціальності 050. 102 «Економічна кібернетика» iconМетодичні рекомендації та тематика контрольних робіт для студентів заочної форми навчання з дисципліни "Овочівництво та садівництво" для студентів 2 курсу для спеціальності
Відповідальний за випуск Валько М.І., д т н., професор, завідувач кафедри технічної хімії і харчових технологій

Конспект лекцій з дисципліни «Дискретний аналіз» для студентів спеціальності 050. 102 «Економічна кібернетика» iconМетодичні рекомендації та тематика контрольних робіт для студентів заочної форми навчання з дисципліни "Процеси І апарати харчових виробництв" для студентів 2 курсу для спеціальності
Методичні рекомендації і контрольні завдання до виконання практичних занять з дисципліни «Процеси і апарати харчових виробництв»

Конспект лекцій з дисципліни «Дискретний аналіз» для студентів спеціальності 050. 102 «Економічна кібернетика» iconМетодичні вказівки до лабораторних робіт для студентів факультету соціології спеціальності "Адміністративний менеджмент"
Методичні вказівки до лабораторних робіт із дисципліни “Аудит І фінансово-управлінський облік (з використанням комп’ютерних технологій)”...

Конспект лекцій з дисципліни «Дискретний аналіз» для студентів спеціальності 050. 102 «Економічна кібернетика» iconМетодичні вказівки до виконання організаційно-економічної частини дипломного проекту для студентів спеціальності
Дипломного проекту для студентів спеціальності 7 05050313 Обладнання хімічних виробництв І

Конспект лекцій з дисципліни «Дискретний аналіз» для студентів спеціальності 050. 102 «Економічна кібернетика» iconМетодичні вказівки до семінарських занять для студентів спеціальності «Міжнародна інформація» Затверджено
України: Плани та методичні вказівки до семінарських занять для студентів спеціальності «Міжнародна інформація» / Укл. Бучин М. А.,...

Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©znanie.podelise.ru 2000-2013
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы