- •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. Біном Ньютона. Поліномна формула
46.Поняття алгебри Жегалкіна, лінійні функції.
Алгебра (В,,,0,1), що утворена множиною В – {0,1} разом з операціями (кон’юнкції), , і константами 0, 1, називається алгеброю Жегалкіна. Будь – яка булева функція може бути зображена через операції кон’юнкції, диз’юнкції, заперечення. Для доведення зображення будь – якої булевої функції формулою алгебри Жегалкіна достатньо виразити диз’юнкцію і заперечення через кон’юнкцію і XOR – операції алгебри Жегалкіна. За видом полінома Жегалкіна визначається така важлива властивість булевих функцій, як лінійність. Булава функція називається лінійною, якщо її поліном Жегалкіна не містить кон’юнкцій змінних.
Поліномом Жегалкіна назив. скінченна сума за модулем 2 попарно різних елементарних кон’юнкцій над множиною змінних (x1,x2,…,xn). К-ть попарно різних ел. функцій назив. довжиною полінома. Булева ф-я назив. лінійною, якщо її поліном не містить кон’юнкцію змінних. Для побудови поліному Жегалкіна функції, що задана деякою формулою алгебри Жегалкіна, необхідно розкрити всі дужки в даній формулі за законом дистрибутивності і виконати всі можливі спрощення. Якщо ф-я задана в ДДНФ або цю форму легко знайти, доцільно замінити диз’юнкції ксором, застосув. операції інверсії та зведення подібних. Метод невизначених коефіцієнтів: для ф-ї f(x1,x2,…,xn) записують найзагальніший вигляд поліному Жегалкіна (Р(x1,x2,…,xn)) з невизначеними коеф., їх буде 2n . Поліном Жегалкіна 2-х змінних має заг. вигляд P(x,y): a0a1x a2ya3xy. Для трьох: P(x,y,z): a0a1x a2ya3za4xy a5xza6yza7xyz. Для кожного двійкового набору (a1…an) записують 2n рівнянь: f(a1…an) = P(a1…an). Розв’язавши їх, отримують коефіцієнти полінома.
47.Правила мінімізації булевих функцій (карти Карно).
Задача мінімізації складається з пошуку найпростішої, згідно з обраним критерієм мінімізації, формули. Критерії можуть бути різними, наприклад: кількість змінних у формулі, кількість знаків кон’юнкції та диз’юнкції або комбінація подібних критеріїв. Мінімальною ДНФ булевої функції називається одна з її тупикових ДНФ, якій відповідає найменше значення критерію мінімізації ДНФ. Мінімізація на множині ДНФ і КНФ називається канонічною задачею мінімізації. Мінімальні форми, що одержанні в результаті її розв’зку, називаються мінімальними ДНФ і КНФ. Мінімізація на множині КНФ: для мінімізації на множині КНФ використовують карти Карно. На карті позначають клітки, що відповідають інтерпретаціям, на яких функція дорівнює нулям та одиницям. Після цього проводиться склеювання кліток, що містять нулі для формування мінімальної КНФ, та склеювання клітинок зодиницями для ДНФ. При склеюванні кліток потрібно захопити якнаймога більшу область. Кожна група кліток, що одержана в результаті склеювання, відповідає диз’юнкції (додаванню) тільки тих змінних, які мають однакове значення для всіх кліток групи. Змінні беруться без заперечення, якщо їм відповідає нульове значення, і із запереченням – в іншому випадку. Кон’юнкція одержаних елементарних диз’юнкцій є результатом мінімізації формули.