З дисципліни Економічна кібернетика

МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ

Криворізький економічний інститут

ДВНЗ «Київський національний економічний університет імені Вадима Гетьмана»

МЕТОДИЧНІ ВКАЗІВКИ

До проведення практичних та самостійних занять

з дисципліни “Економічна кібернетика”

для студентів денного та заочного відділення

спеціальності „Економічна кібернетика”

 

 

Кривий Ріг, 2010

  Рецензент: Тищенко С.В., д.т.н., завідувач кафедри економічної кібернетики

Розділ 1. Теорія множин

Поняття множини. Способи задання множин. Порожня множина. Операції над множинами. Властивості множин. Алгебра множин.

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

Поняття логічної функції. Алгебра Буля, її закони. Методи мінімізації булевих функцій. Загальна характеристика висловлювань. Логічні операції. Таблиці істинності.

Розділ 3. Комбінаторний аналіз

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

Розділ 4. Бінарні відношення

Поняття бінарного відношення. Завдання бінарного відношення з допомогою матриці та графа. Композиція відношень.

Розділ 5. Теорія графів

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

 

 

Елементи теорії множин

Для позначення конкретних множин використовують різні прописні літери A, S, X,… або прописні літери з індексами , і т.і. Для позначення елементів… В теорії множин використовується поняття „порожньої множини”. Позначається… Розглянемо дві множини та , та введемо декілька операцій над ними. Для графічної ілюстрації будемо використовувати так…

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

Логіка Буля

Об’єднання множин та : Іншими словами, елемент належить або/і , можна виразити формулою: ,

Табл.1

Між таблицею істинності та колами Ейлера існує взаємно однозначна відповідність. Тому число одиниць для завжди буде дорівнювати числу заштрихованих областей на діаграмі Ейлера. Чотири комбінації аргументів x₁ та x₂ будуть відповідати чотирьом областям. Крім того, неважко підрахувати, що число комбінацій нулей та одиниць для функції дорівнює 16 (7 елементів та варіант, коли елемент не належить ні однієї із множин). Отже, загальне число можливих операцій на двох множинах теж дорівнює цьому числу.

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

Таблицю істинності для кон’юнкції можна представити слідуючим чином:

			табл.2

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

Множина доповнює множину до універсуму (або 1). Доповнення до логічної змінної , тобто (не-), називають у логіці частіше за все запереченням .

Розглянемо дві нові операції: стрілка Пірса та штрих Шеффера. Діаграми цих операцій доповнюють об’єднання та пересічення до фундаментальної множини (універсуму U).

 

Стрілка Пірса

 

Штрих Шеффера

Таблиця істинності для даної операції має вигляд: … З цієї таблиці бачимо, що

Для різниці для імплікації

. Залишається розглянути ще дві взаємно доповнюючі операції – симетричну різницю (або диз’юнктивну суму) та…

Симетрична різниця тотожність

~ ~ ~  

Мінімізація логічних функцій

Якщо виписати відповідні кон’юнкти напроти одиничних значень , ми отримаємо ДДНФ: . Якщо ми випишемо диз’юнкти напроти нульових значень , то в результаті отримаємо вже ДКНФ:

Тема3. Комбінаторний аналіз.

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

ЗАВДАННЯ ДЛЯ САМОСТІЙНОГО ОПРАЦЮВАННЯ

Логіка висловлювань

2. Довести, що формули , , , , де - значення «хибності», мають ту саму таблицю істинності, що й формула . 3. Довести, що формули та мають однакові таблиці істинності. 4. Застосувавши таблиці істинності, довести закони дистрибутивності.

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

2. Задано множини та . Побудувати множини: а) ; б) ; в) ; г) . 3. Знайти множини та , якщо , , і . 4. Довести рівність .

Комбінаторний аналіз

2. Обчислити кількість перестановок множини , які закінчуються буквою . 3. Обчислити значення: а) ; б) ; в) ; г) ; д) ; е) ; ж) ; з) ; и) ; к) ; л) ;… 4. У групі чоловіків і жінок. Скількома способами їх можна вишикувати в шеренгу так, щоб чергувалися чоловік і…

Теорія графів

Література

1. Нікольський Ю.В., Пасічнік В.В., Щербина Ю.М. Дискретна математика. – К.: Видавнича група BHV, 2007. – 368 с.

2. Горбатов В.А. Основы дискретной математики: Учеб. пособие для студентов вузов. – М.: Высш. шк., 1986. – 311 с.

3. Капітонова Ю.В., Кривий С.Л., Луцький Г.М., Печурін М.К. Основи дискретної математики: Підручник. – К.: Наукова думка, 2002. – 568 с.

4.