- •Буковинський університет
- •Дискретна математика
- •Навчально-методичний посібник
- •Чернівці
- •Задачі та вправи 12
- •Задачі та вправи 28
- •Операції над множинами
- •Тема „Алгебра лінійних множин”
- •Способи задання множин
- •Порожня множина ()
- •Універсум (u)
- •Множина підмножин
- •Алгебра множин
- •Узагальнення операцій над множинами
- •Задачі до теми „Алгебра лінійних множин”
- •Тема „Відношення і функції”
- •Окремі випадки відношень
- •Властивості композицій:
- •Властивості відношень
- •Основні властивості відображень
- •Відношення еквівалентності
- •Відношення порядку
- •Відношення рівнопотужності
- •Властивості скінченних множин
- •Властивості зчисленних множин
- •Задачі до теми „Відношення і функції”
- •Тема „Булеві функції”
- •Способи задання булевих функцій
- •Булеві функції однієї змінної
- •Область визначення булевих функцій
- •Елементарні функції алгебри логіки
- •Булевий простір
- •Властивості функцій
- •Деякі операції над висловленнями
- •Формули в алгебрі логіки
- •Основні тотожності
- •Правила
- •Принцип двоїстості
- •Типи булевих функцій
- •Канонічні форми перемикальних функцій
- •Досконалі диз’юнктивні нормальні форми перемикальних функцій
- •Досконалі кон’юнктивні нормальні форми перемикальних функцій
- •Властивості досконалих форм
- •Скорочена диз’юнктивна нормальна форма перемикальних функцій
- •Утворення скороченої диз’юнктивної нормальної форми методом Квайна
- •Метод Квайна-Маккласкі
- •Утворення мінімальних кон’юктивних нормальних форм
- •Алгоритм утворення мінімальної кнф
- •Геометричне подання функцій алгебри логіки
- •Спрощення булевих функцій
- •Задачі до теми „Способи задання булевих функцій. Операція суперпозиції”
- •Задачі до теми „Істотні та фіктивні змінні”
- •Задачі до теми „Спеціальні види формул. Диз’юнктивні і кон’юнктивні нормальні форми. Поліном Жегалкіна”
- •Задачі до теми „Замкнуті класи і повнота системи булевих функцій” Важливіші замкнуті класи булевих функцій
- •Задачі до теми „Класи функцій, що зберігають константи”
- •Задачі до теми „Двоїстість і клас самодвоїстих функцій”
- •Задачі до теми „Монотонність і клас монотонних функцій”
- •Повнота систем булевих функцій
- •Тема „Рекурсивні функції”
- •Частково-рекурсивні функції
- •Тема „Скінченні автомати. Машина Тьюринга”
- •Машина Тьюринга
- •Тема „Основні поняття і властивості алгоритмів”
- •Основні вимоги до алгоритмів
- •Основні властивості алгоритму
- •Тема „Формальні системи. Алгебра висловлювань”
- •Аксіоматичний спосіб опису висловлювань
- •Властивості числення висловлювань
- •Задачі до теми „Алгебра висловлювань”
- •Тема „Логіка і числення предикатів”
- •Рівносильність формул
- •Задачі до теми „Логіка і числення предикатів”
- •Тема „Алгебри. Типи алгебр. Алгебраїчні системи”
- •Гомоморфізм та ізоморфізм алгебри
- •Типи алгебр
- •Алгебраїчні системи
- •Тема „Елементи комбінаторики”
- •Формула включень і виключень
- •Рекурентні співвідношення
- •Основні властивості кількості сполук
- •Біном Ньютона
- •Властивості розкладу бінома Ньютона і біномних коефіцієнтів
- •Поліномні твірні функції
- •Розміщення і функціональні відображення
- •Розбиття
- •Поліномна формула
- •Задачі до теми „Комбінаторика”
- •Тема „Графи”
- •Задання графа за допомогою матриці інцидентності та списку ребер
- •Задання графа за допомогою матриці суміжності
- •Локальні степені вершин графа
- •Частини графа, суграфи та підграфи
- •Операції з частинами графа
- •Маршрути, ланцюги та цикли
- •Цикломатичне число графа
- •Задачі до теми „Графи”
- •Дискретна математика
- •Література
- •Навчальне видання Пукальський Іван Дмитрович,
- •Лусте Ірина Петрівна,
Утворення мінімальних кон’юктивних нормальних форм
Щоб знайти вираз заданої перемикальної функції, найзручніший для синтезу автомата, потрібно мати мінімальні КНФ і вибрати із них ту, реалізація якої найпростіша.
Алгоритм утворення мінімальної кнф
Перемикальну функцію подають у ДКНФ, тобто у вигляді добутку конституент нуля:
якщо функцію задано таблицею, то її записують „за нулями” ДКНФ;
якщо функцію задано довільною формою, то застосовують формулу розгортання: x = (x + y)(x + ), (x + y) = (x + y + z)(x + y + ). Виконують спочатку всі операції неповного склеювання, а потім операції поглинання, які визначаються виразами (x + y)(x + ) = x (x + )(x + y) та x(x + y) = x відповідно.
Знаходять мінімальні КНФ, використовуючи імплікантні матриці, тобто таблиці, у верхній рядок яких записують конституенти нуля, що входять у ДКНФ, а в ліву частину – члени, що входять у скорочену КНФ. Клітинки імплікантної матриці на перетині колонки з конституентою нуля і рядка з членом, який її поглинає, позначають хрестиком. Мінімальні КНф записують у вигляді добутків, що містять найменшу кількість членів, які перекривають хрестиком всі колонки імплікантної матриці.
Приклад. Знайти мінімальну КНФ функції
f(a, b, c) = (a + )( + + c)(b + c)( + + )
1 2 3 4
Утворимо ДКНФ, для чого застосуємо операцію розгортання до членів 1 і 3:
(a + ) = (a + b + )(a + + );
(b + c) = (a + b + c)( + b + c).
Тоді
f(a, b, c) = (a + b + )(a + + )( + + c)(a + b + c)( + b + c)( + + )
1 2 3 4 5 6
Виконаємо всі операції склеювання та поглинання:
1 – 2 = a + (по b); 1 – 4 = a + b (по c); 2 – 6 = + (по a);
3 – 2 = + c (по b); 3 – 6 = + (по c); 4 – 5 = b + c (по a).
Одержані члени (n = 2) між собою не склеюються, тому скорочена КНФ має вигляд
f(a, b, c) = (a + )(a + b)( + )( + c)( + )(b + c).
Будуємо імплікантну матрицю:
Прості імпліканти |
Конституенти нуля |
|||||
a+b+ |
a+ + |
+ +c |
a+b+c |
+b+c |
+ + |
|
1 |
2 |
3 |
4 |
5 |
6 |
|
a + |
|
|
|
|
|
|
a + b |
|
|
|
|
|
|
+ |
|
|
|
|
|
|
+ c |
|
|
|
|
|
|
+ |
|
|
|
|
|
|
b + c |
|
|
|
|
|
|
Маємо дві мінімальні КНФ:
f(a, b, c) = (a + )( + )(b + c).
f(a, b, c) = (a + b)( + )( + c).