- •Міністерство освіти і науки,
- •Упорядники: в.І. Хаханов,
- •Рецензент: є.І. Литвинова, д-р техн. Наук, проф. Каф. Апот хнуре
- •1 Основні поняття теорії множин
- •1.1 Відношення приналежності та включення
- •1.2 Способи задання множин
- •1.3 Алгебра множин Кантора
- •1.4 Закони й тотожності алгебри множин
- •1.5 Контрольні запитання
- •2 Відповідності. Функції. Відображення
- •2.1 Поняття впорядкованої пари й вектора
- •2.2 Декартів (прямий) добуток множин
- •2.4 Функції. Відображення
- •2.5 Контрольні запитання
- •3 Відношення. Алгебра відношень
- •3.1 Поняття відношення
- •3.2 Операції над відношеннями
- •3.3 Алгебра відношень
- •3.4 Контрольні запитання
- •4 Бінарні відношення
- •4.1 Способи завдання бінарних відношень
- •4.2 Властивості бінарних відношень
- •4.3 Бінарне відношення еквівалентності
- •4.4 Контрольні запитання
- •5 Бінарне відношення порядку
- •5.1 Упорядковані множини. Бінарне відношення порядку
- •5.2 Типи порядку (лінійний, частковий, передпорядок)
- •5.3 Контрольні запитання
- •6 Структури. Алгебраїчні системи. Ізоморфізм
- •6.1 Структура
- •6.2 Дедекиндові (модулярні) структури
- •6.3 Дистрибутивні структури
- •6.4 Ізоморфізм множин
- •6.5 Контрольні запитання
- •7 Висновки до розділу «Теорія множин»
- •8 Позначення до розділу «Теорія множин»
- •9 Основні поняття булевої алгебри
- •9.1 Логічні операції й логічні функції
- •9.2 Закони й тотожності булевої алгебри
- •9.3 Доведення законів булевої алгебри
- •9.4 Контрольні запитання
- •10 Диз’юнктивні та кон’юнктивні нормальні форми (днф і кнф). Досконалі днф і кнф (дднф і дкнф)
- •10.1 Днф і кнф
- •10.2 Дднф і дкнф
- •10.3 Складність зображення булевих функцій
- •10.4 Теорема Шенона про розкладання булевих функцій
- •10.5 Контрольні запитання
- •11 Елементи логічних схем. Булеві функції від двох змінних
- •11.1 Фізичний зміст логічних функцій і, або, ні та їх схемотехнічне зображення
- •11.2 Таблиця аналітичного й схемотехнічного зображення булевих функцій від двох змінних
- •11.3 Властивості й аналітичні подання елементарних булевих функцій від двох змінних
- •11.4 Приклади розв’язання практичних завдань
- •11.5 Контрольні запитання й завдання
- •12 Способи зображення булевих функцій
- •12.1 Табличний спосіб зображення булевих функцій
- •12.2 Числовий спосіб зображення булевих функцій
- •12.3 Аналітична форма запису булевих функцій
- •12.4 Геометрична інтерпретація булевих функцій
- •12.5 Кубічна форма зображення булевих функцій
- •12.6 Схемотехнічне зображення
- •12.7 Контрольні запитання й завдання
- •13 Системи функцій алгебри логіки. Функціональна повнота
- •13.1 Класи булевих функцій
- •13.2 Повнота функцій алгебри логіки
- •13.3 Контрольні запитання
- •14 Булеві похідні
- •14.1 Булеві похідні першого порядку
- •14.2 Фізичний зміст булевої похідної першого порядку
- •14.3 Змішана похідна -го порядку
- •14.4 Булеві похідні k-го порядку
- •14.5 Контрольні запитання
- •15 Мінімізація булевих функцій. Методи квайна і квайна-мак-класки
- •Булеві функції застосувуються при реалізації логічних схем. Різні вирази однієї й тієї ж функції представляють різні схеми.
- •15.1 Основні положення методу квайна
- •15.2 Мінімізація булевих функцій за методом Квайна-Мак-Класки
- •15.3 Контрольні запитання
- •16 Мінімізація булевих функцій: метод невизначених коефіцієнтів
- •16.1 Основні припущення
- •16.2 Алгоритм знаходження невизначених коефіцієнтів
- •16.3 Контрольні запитання
- •17 Мінімізація булевих функцій: метод карт карно
- •17.1 Основні положення
- •17.2 Спрощений стандарт карт Карно
- •17.3 Мінімізація за картами Карно
- •17.4 Контрольні запитання
- •18 Висновки до розділу «булева алгебра»
- •19 Позначення до розділу «булева алгебра»
- •Перелік посилань
- •Упорядники хаханов Володимир Іванович
2 Відповідності. Функції. Відображення
2.1 Поняття впорядкованої пари й вектора
Під вектором (кортежем) слід розуміти впорядкований набір елементів , де – координати або компоненти вектора.
Розмірність(довжина вектора) визначається кількістю його координат.
Два вектори (кортежі) однакової розмірності рівні, якщо їхні відповідні компоненти рівні, тобто виконується покоординатна рівність:
.
Під упорядкованою пароюслід розуміти вектори розмірності два, тобто упорядкована пара– двоелементна упорядкована множина. Упорядкована пара є одним з первинних понять у теорії множин.
Визначення 2.1.Проекцією векторана i-у вісь називається його i-й компонент (i-а координата):.
Визначення 2.2. Нехай – множина векторів однакової довжини, тоді проекцією множини на i-у вісь називається сукупність проекцій всіх векторів з V на на i-у вісь: .
Приклад 2.1. Координати точки площини утворюють упорядковану пару:. Вони вказуються у фіксованому порядку: на першій позиції – абсциса, на другій – ордината, які є проекціями на першу й другу осі відповідно (рис. 2.1):,.
Рисунок 2.1 – Проекції точки площини на осі
Видно, що упорядковані пари йрізні:.
Приклад 2.2.Розглядається множинавекторів розмірності три (тривимірні вектори):. Потрібно знайти проекції множинина осі.
Розв’язок. Проекціяна першу вісь визначається як сукупність координат, що займають перші позиції у векторах з множини:. Аналогічно визначаються проекції на другу й третю осі. Оскільки елементи множини не повторюються, однакові координати, що розташовуються на тих самих позиціях у різних векторах, ураховуються один раз:,.
2.2 Декартів (прямий) добуток множин
Поряд з операціями (1.2) – (1.8) впроваджується операція декартова (прямого) добутку множин.
Визначення 2.3.Прямий (декартів) добутокдвох множин A і B є множина всіх партаких, що,:
. (2.1)
Приклад 2.3.Дано множини,. Складемо їх декартів добуток за правилом (2.1):.
Приклад 2.4.Декартів добутокмножин,є множина, що містить позначення всіх 64 клітинок шахівниці.
Приклад 2.5. Координатне подання точок площини, що ввів Рене Декарт –французький математик і філософ, – є історично першим прикладом прямого добутку. Множина точок площини, тобто множина пар виду,:.
Декартів добуток множин не є комутативним: .
Визначення 2.4.Якщо, тобто–декартів квадрат.
Визначення 2.5.Прямий добуток n множин є сукупність всіх векторівдовжинитаких, що,, ... ,, тобто
, (2.2)
Ототожнивши множини в декартовому добутку (2.3), одержимо декартову ступіньмножини.
Визначення 2.6. Декартів добуток n однакових множин є декартова ступінь:
. (2.3)
Декартова ступінь множини поряд з іншими n-мірними векторами містить вектори, що складаються з однакових координат, тобто-мірні вектори виду. Кількість таких векторів визначається потужністю множиний дорівнюєn.
Потужність декартова добутку визначається як добуток потужностей множин, що входять у нього.
Нехай – кінцеві множини, потужності яких відповідно дорівнюють. Тоді потужність декартова добутку множиндорівнює добутку потужностей цих множин:
. (2.4)
З формули (2.4) випливає, що потужність декартова ступеня визначається як ступінь потужності множини:
. (2.5)
2.3 Відповідності
Визначення 2.7.Відповідністю між множинамиіназивається підмножина декартового добутку двох множин:.
Запис означає, що елементвідповідає елементув значенні, і впорядкована параналежить множині:.
При цьому називаютьобластю визначення(множиною відправлення) відповідності:;–областю значень(множиною прибуття) відповідності:.
Визначення 2.8. Множина всіх елементів , що відповідають елементу , називається образом елемента у множині при відповідності .
Визначення 2.9.Множина всіх елементів, яким відповідає елемент, називаєтьсяпрообразомелементав множиніпри відповідності.
Приклад 2.6. Дано множиниі. Для відповідностіобласть визначення є проекція на першу вісь:; область значень – проекція на другу вісь:;– образ елементів 1, 2 у множиніпри відповідності; 1, 2 є прообразами елементапри відповідності.
Відповідності прийнято ілюструвати за допомогою діаграм. Для прикладу 2.6діаграма наведена на рис. 2.1.
Рисунок 2.1 – Діаграма відповідності із прикладу 2.6
Визначення 2.10.Відповідністьназиваєтьсявсюди визначеною, якщо її проекція на першу вісь співпадає з множиною відправлення:, тобто у відповідності задіяні всі елементи з області визначення. У протилежному випадку відповідність єчастковою.
Приклад 2.6 ілюструє часткову відповідність, тому що .
Приклад 2.7.Для відповідності(рис. 2.2), де,, проекція на першу вісь співпадає з множиною відправлення:.
S
Рисунок 2.2 – Діаграма відповідності S із прикладу 2.7
Визначення 2.11.Відповідністьназиваєтьсясур’єктивною, якщо її проекція на другу вісь співпадає з множиною прибуття:, тобто у відповідності задіяні всі елементи з області значень.
Приклад 2.8.Для відповідності(рис. 2.3), де,, проекція на другу вісь співпадає з множиною прибуття:.
Т
Рисунок 2.3 – Діаграма відповідності Т із прикладу 2.8
Визначення 2.12.Відповідністьназиваєтьсяін’єктивною (in), якщо різні елементи з його області визначеннямають різні образи в його області значень, тобто прообразом будь-якого елемента з області значень є єдиний елемент із області визначення (інакше – різні елементи з області визначення мають різні образи):
. (2.6)
Отже, при ін’єктивній відповідності кожний образ має єдиний прообраз. Це означає, що в діаграмі ін’єктивної відповідності нема збіжних стрілок.
Приклад 2.9. Відповідності , і із прикладів 2.6 – 2.8 не є ін’єктивними, оскільки образ має два прообрази – елементи 1, 2 у множині . До того ж у відповідності образ також має два прообрази – елементи 2 і 3.
Приклад 2.10.Відповідністьде,, є ін’єктивною, оскільки образи з множинимають єдині прообрази в множині(рис. 2.4).
Р
Рисунок 2.4 – Діаграма відповідності Р із прикладу 2.10
Визначення 2.13.Відповідністьназиваєтьсяфункціональною (однозначною), якщо образом будь-якого елемента з області визначення є єдиний елемент із області значень, тобто– функціонально, якщо
. (2.7)
Діаграма функціональної відповідності не має розбіжних стрілок.
Приклад 2.11.Відповідністьіз прикладу 2.6 є функціональною, томущо кожному прообразу відповідає єдиний образ: прообразу 1 відповідає образ , прообразу 2 відповідає також один образ – . Відповідність із прикладу 2.7.не є функціональною, оскільки існує прообраз – елемент 2, у якого одночасно два образи – елементий.
Визначення 2.14. Бієктивна(взаємо-однозначна) відповідність – це відповідність, що є всюди визначеною, сур’єктивною, ін’єктивною, функціональною, тобто має всі властивості одночасно.
Біекцію (бієктивну або взаємо-однозначну відповідність) можна встановити тільки між множинами однакових потужностей.
Приклад 2.12.Для відповідності(рис. 2.5), де,, характерні всі властивості, отже, вона є бієктивною.
Рисунок 2.5 – Діаграма відповідності із прикладу 2.12
Приклад 2.13. Розглядається відповідність , що геометрично зображена на рис. 2.6. Вона переводить відрізок дійсної осі у відрізок дійсної осі : . Відповідність не є функціональною, тому що образом числа 3, що лежить на осі абсцис, є відрізок осі ординат, а не єдиний елемент: . Дуга є прикладом функціональної відповідності.
Рисунок 2.6 – Ілюстрація відповідності до прикладу2.13