- •Логічні операції та логічні змінні
- •2. Булеві функції
- •3. Булеві функції однієї та двох змінних
- •Практичне заняття 1
- •4. Системи базових (елементарних) операцій
- •Булеві функції багатьох змінних
- •Практичне заняття 2
- •6. Булева двохелементна алгебра. Алгебра логіки
- •Практичне заняття 3
- •7. Алгебра Жегалкіна
- •Практичне заняття 4
- •8. Диз’юнктивні нормальні форми (днф) булевих функцій
- •Практичне заняття 5
- •9. Досконала диз’юнктивна нормальна форма булевої функції
- •Практичне заняття 6
- •10. Кон’юнктивні нормальні форми (кнф) булевих функцій
- •Практичне заняття 7.
- •11. Досконала кон’юнктивна нормальна форма булевих функцій
- •Практичне заняття 8.
- •12. Двоїстість булевих функцій
- •Практичне заняття 9.
- •13. Поліном Жегалкіна. Лінійні функції
- •Практичне заняття 10.
- •14. Функції, що зберігають нуль та функції, що зберігають одиницю. Монотонні функції
- •Практичне заняття 11.
- •15. Класи Поста. Теорема Поста
- •Практичне заняття 12
- •16. Мінімізація булевих функцій
- •16.1 Постановка задачі. Основні поняття
- •16.2. Мінімізація булевих функцій методом карт Карно
- •Практичне заняття 13
- •16.3. Мінімізація на множині кнф
- •Практичне заняття 14
- •16.4. Мінімізація функцій методом Квайна – Мак-Класкі
-
Логічні операції та логічні змінні
Нехай множина . Елементи цієї множини називають логічними значеннями, а змінні, які можуть приймати логічні значення – логічними змінними.
Визначимо на множина логічні операції:
-
0-арні (нульмісні) операції – константи 0 та 1; (0), (1)
-
1-арні (одномісні) операції:
-
повторення
(2)
-
заперечення;
(3)
-
2-арні (двомісні) операції: кон’юнкцію, імплікацію, заперечення імплікації, суму за модулем 2, диз’юнкцію, стрілку Пірса, еквівалентності, штрих Шиффера.
-
Кон’юнкція
; (4)
-
Імплікація
; (5)
-
Заперечення імплікації
; (6)
-
Сума за модулем 2
; (7)
-
Диз’юнкція
; (8)
-
Стрілка Пірса
; (9)
-
Еквівалентність:
; (10)
-
Штрих Шиффера:
; (11)
Вирази 0, 1, , , , , , , , , називаються логічними виразами (формулами). Вони є найпростішими логічними формулами. Більш складні формули можна одержати суперпозицією, при якій у вихідній формулі замість змінних підставляють інші вирази.
Приклад 1. Якщо в формулі взяти , , то одержимо більш складну формулу , яку також можна використати для одержання ще більш складної формули, наприклад, такої
.
2. Булеві функції
Функція називається булевою, якщо її значення і аргументи можуть приймати значення 0 і 1: і ().
Область визначення логічних функцій – множина ( разів). Елементи цієї множини – кортежі (n-ки) , які в математичній логіці називають словами і позначають рядком символів або стовпчиком із символів .
Кількість слів скінчена і дорівнює .
Приклад 1. При маємо два слова: 0, 1. При є чотири слова: 00, 01, 10, 11. При маємо вісім слів: 000, 111, 001, 101, 010, 011, 100, 110,
Кожному слову можна поставити у відповідність ціле число (номер слова)
. (1)
Приклад 2. Слову 010101 можна поставити у відповідність ціле число (номер)
.
Співставлення словам їх номерів дозволяє ввести на множині слів ідеальний строгий порядок: слово з меншим номером передує слову із більшим номером. Іншими словами, множину слів можна впорядкувати за зростанням їх номерів.
Приклад 3. При впорядкована множина слів така: 000 (відповідне число 0), 001(1), 010(2), 011(3), 100(4), 101(5), 110(6), 111(7).
Область значень будь-якої
Булевій функції n змінних можна поставити у відповідність число (номер функції)
, (2)
де
– значення
Співставлення функціям їх номерів дозволяє також ввести на множині функцій ідеальний строгий порядок: функція з меншим номером передує функції із більшим номер.
Номери
повністю визначають булеві функції і
дозволяють будувати таблиці
істинності (таблиці
істинності є одним із способів подання
Приклад 4. Випишемо таблицю істинності функції , враховуючи, що .