- •1. Основні поняття теорії множин (поняття порожньої множини, універсуму, способи завдання множин).
- •2.Основні операції над множинами.
- •3.Властивості операцій над множинами
- •4.Геометрична інтерпретація множин
- •5.Поняття підмножини, рівність множин.
- •6.Множина підмножин.
- •7.Алгебра множин.
- •8.Узагальнення операцій над множинами.
- •9.Декартовий добуток множин
- •10.Еквівалентність множин.
- •11.Поняття потужності множини.
- •12.Зчисленні та незчисленні множини.
- •13.Множини потужності континуума.
- •14.Поняття відношення
- •15.Поняття фактор – множини
- •16.Подання відношень за допомогою матриці і графа
- •17.Операції над відношеннями
- •18.Симетричне (обернене) відношення
- •19.Поняття композиції відношень
- •20.Властивості композиції відношень
- •26.Поняття функції та відображень.
- •27.Типи відображень
- •28.Поняття образу та праобразу
- •29.Основні властивості відображень
- •30.Відношення еквівалентності
- •31.Матриця та граф відношення еквівалентності
- •32.Відношення толерантності
- •33.Відношення нестрогого порядку
- •34.Відношення строгого порядку
- •35.Матриця та граф відношення нестрогого порядку
- •36.Матриця та граф відношення строгого порядку
- •37.Алгоритм побуд. Транзитивного замикання відношень(алг. Уоршалла)
- •38.Осн. Поняття реляційної алгебри
- •39.Булеві функції, способи задання булевої функції
- •40.Номери булевих функцій та інтерпретацій.Булеві ф-ї двох змінних.
- •41.Закони булевої алгебри
- •42.Поняття двоїстої та самодвоїстої функцій
- •43. Правило розкладаня булевої ф-ї за всіма або декількома змінними.
- •44.Поняття досконалої диз’юнктивної нормальної форми (дднф) та досконалої кон’юнктивної нормальної форми (дкнф).
- •45.Алгоритм переходу від таблиці істинності до дднф.
- •46.Поняття алгебри Жегалкіна, лінійні функції.
- •47.Правила мінімізації булевих функцій (карти Карно).
- •48. Понятя повних систем булевих функцій
- •49.Теорема Поста про повноту.
- •53.Поняття предикату, квантору
- •54. Закони у логіці предикатів
- •55.Алгоритм зведення вільної форми алгебри логіки предикатів до внф.
- •56. Закони математичної логіки першого ступеня. Поняття множини істинності предиката.
- •57.Основні поняття теорії графів (порядок, степені вершин, порожній граф, мультиграф, псевдо граф, орієнтований та неорієнтований граф).
- •58.Задання графа за допомогою матриці інцидентності
- •59.Задання графа за допомогою матриці суміжності
- •60.Задання графа за допомогою матриці Кірхгофа.
- •61. Локальні степені вершини графа.
- •62. Локальні степені вершини орграфа.
- •64. Операції над частинами графа.
- •65. Маршрути, ланцюги, цикли.
- •66. Ознаки зв’язності
- •67. Поняття дерева.
- •73. Поняття гамільтонових графів.
- •75. Поняття укладання графа. Пласкі та планарні графи.
- •76. Теорема. Ейлера та властивості планарного графа
- •77. Критерії планарності
- •80. Критичні графи
- •82. Алгоритм Форда-Беллмана д/знах. Макс. Шляху
- •83. Алгоритм Форда-Фалкерсона – знах. Макс. Потоку в мережі
- •84. Алгоритм Хафмана
- •90. Біном Ньютона. Поліномна формула
27.Типи відображень
Типи відображень: при відображені ху, кожен елемент х з множини Х має один і тільки один образ; якщо будь – який елемент з множини у є образом хоча б одного елемента множини х, то кажуть, що множина х відображається на у – явище сюр’єкції(або покриття); якщо для будь – яких різних елементів множини х1 та х2, що належать множині х, їх образи у1 = f(x), y2=f(x2), x1,x2X називаються ін’єкцією. Відображення, яке є одночасно сюр’єктивним та ін’єктивним називається бієкцією(накладанням).
28.Поняття образу та праобразу
Сукупність елементів f(x), якы э образами всіх ел. множини х, назив. образом цієї множини і позн. f(x). Сукупність всіх ел., образом яких цих всіх ел. є задані ел. У, назив. повним праобразом ел. У і позн. f-x (y).
29.Основні властивості відображень
Властивості відображень: якщо с1 та с2 функціональні відображення між множинами A і В, В і f відповідно, то композиція с1 та с2 – це відображення між А і f; якщо с1 та с2 ін’єктивні відображенню між a і в та в і f, то композиція с1 та с2 – ін’єктивне відображення між а і f; при відображені ху елемент з множини х може бути образом не одного, а кількох елементів з х; сукупність всіх елементів образом яких є заданий елемент у називається повним праобразом елемента у.
30.Відношення еквівалентності
Відношення, що має властивості рефлексивності, симетричності та транзитивності називається відношенням еквівалентності. Класом еквівалентності елемента А називають множину всіх елементів множини х, які еквівалентні елементу А. Якщо на множині х задане відношення еквівалентності, то вона задає розбиття на цій множині і розбиття єдине. Елементи a,bA, для яких виконується aRb, називаються еквівалентними.
31.Матриця та граф відношення еквівалентності
Матриця: Головна діагональ-1, Семетрична, одиничні елементи утвор. Печер. Квадрати, діафон., які розташовані на гол. Діагоналі
Граф кожна компонента з’єдання цього графа,що відповідає класу еквівалентності є повним графом
32.Відношення толерантності
Відношення називається відношенням толерантності, якщо воно: рефлексивне, симетричне і анти транзитивне. Толерантність зображує собою формальне уявлення інтуїтивного поняття схожості. Схожість двох об’єктів не залежить від того, в якому порядку вони порівнюються, в цьому виявляється властивість симетричності. В той же час, якщо один об’єкт схожий з другим, а другий схожий з третім, то це не означає, що перший і третій об’єкти схожі, тобто властивість транзитивності може не виконуватися.
33.Відношення нестрогого порядку
Відношення часткового порядку, що є рефлексивним, антисиметричним і транзитивним, називається також відношенням нестрогого порядку. На відміну від нього, відношення строгого порядку (позначається <) визначається такими властивостями: антирефлексивність; асиметричність, транзитивність. Таким чином, якщо у відношенні нестрогого порядку властивість анти симетричності замінити асиметричністю, то одержимо строгий порядок.
34.Відношення строгого порядку
Відношення часткового порядку, що є рефлексивним, антисиметричним і транзитивним, називається також відношенням нестрогого порядку. На відміну від нього, відношення строгого порядку (позначається <) визначається такими властивостями: антирефлексивність; асиметричність, транзитивність. Таким чином, якщо у відношенні нестрогого порядку властивість анти симетричності замінити асиметричністю, то одержимо строгий порядок.