Множини і відношення.
Множини та їх специфікації. Операції над множест-вами. Діаграми Ейлера-Венна. Потужність безлічі. Конеч-ні та лічильні безлічі. Відносини. Властивості відносин. Операції над відносинами. Ставлення еквівалентності. Раз-биття і відношення еквівалентності. Відносини часткового і строгого порядку. Функції та відображення. Ін'єкція, сюр'єкція, суперпозиція, біекція, зворотні функції.
Література: [1], с. 5-10; [3], частина 2; [4], гл. 1-3; [5], гл. 1.
Булеві алгебри. Елементи математичної логіки.
Булеві функції. Способи завдання. Істотні і фіктивні змінні. Булеві формули. Основні властивості логічних операцій. Вчинені нормальні форми. Полі-ном Жегалкина. Замкнені класи функцій. Функціонально повні системи. Теореми про функціональну повноту. Приклади функціонально-повних базисів. Проблема мінімізації булевих функцій. Схеми з функціональних елементів. Кінцеві автомати. Формальні теорії. Поняття висловлюючи-ня. Тавтології. Обчислення висловлювань. Логіка предикатів.
Література: [1], с. 14-53; [2], гл. 3,8; [3], частини 1,4; [4], гл. 4, 5; [5], гл. 3,4.
Еквівалентність булевих формул.
Булеві функції можуть бути задані або за допомогою таблиць істинності (єдиним чином), або за допомогою логічних формул (неєдиним чином). Якщо таблиці істинності двох булевих формул збігаються, то ці формули еквівалентні і визначають одну і ту ж булеву функцію.
Приклад. Перевірити еквівалентність булевих формул:
Побудуємо таблицю істинності для функції.
Результуючі стовпці в таблицях істинності збігаються, отже, формули еквівалентні.
Істотні і фіктивні змінні.
Змінна () булевої функції називається фіктивною. якщо має місце рівність
для будь-яких значень змінних. У проти-ном випадку змінна називається суттєвою. Набори значень змінних в останній рівності називаються сусідніми по змінної.
Приклад. Визначити суттєві і фіктивні змінні функції (11110011).
Для зручності наведемо таблицю істинності.
Перевіримо, чи є змінна суттєвою або фіктивною. Розглянемо значення функції на наборах, сусідніх по змінної:
. Значить, змінна - істотний-ная.
Розглянемо тепер значення функції на наборах, сусід-них по змінної:
. Отже, змінна - су-громадської.
Розглянемо значення функції на наборах, сусідніх по змінної:
На всіх парах сусідніх по змінної наборів зна-ний змінних функція приймає рівні значення, таким чи-тельно, змінна - фіктивна.
Уявлення булевих функцій розкладаннями по змінним.
Досконала діз'юнктівная нормальна форма (СДНФ) для булевої функції. не рівної тождест-венно нулю, має вигляд:
де символ визначається наступним чином:
Алгоритм побудови СДНФ.
1. Побудувати таблицю істинності даної булевої функції.
2. Кожному одиничному значенню булевої функції буде відповідати елементарна кон'юнкція. де - відповідний набір значень змін-них. У кон'юнкції ми записуємо. якщо. і. якщо. Кон'юнкції з'єднуються знаком.
Досконала кон'юнктивна нормальна форма (СКНФ) для функції. відмінною від тотожної одиниці, має вигляд:
Алгоритм побудови СКНФ.
1. Побудувати таблицю істинності даної булевої функції.
2. Кожному нульового значення булевої функції буде відповідати елементарна диз'юнкція. де - відповідний набір значень змінних. У диз'юнкції ми записуємо. якщо. і. якщо. Диз'юнкції з'єднуються знаком.
Будь-яка булева функція може бути представлена у вигляді полінома Жегалкина:
де. де знак позначає суму по модулю 2.