- •Розділ 3. Основи теорії скінченних автоматів
- •3.1. Логічні функції
- •3.2. Приклади логічних функцій
- •3.3 Зв'язок логічних функцій і функціональних схем
- •3.4. Канонічне представлення логічних функцій
- •3.5. Задача мінімізації логічних функцій
- •3.6. Основні поняття теорії скінченних автоматів
- •3.7. Абстрактна і структурна теорії скінченних автоматів
- •3.8. Зіставлення скінченних автоматів
- •3.9. Синхронні мережі з автоматів
- •3.10. Приклад синтезу скінченного автомата
- •Перетворимо вихідну таблицю в спеціальну форму з виділенням вхідних-вихідних сигналів і внутрішніх станів.
- •3.11. Програмна реалізація логічних функцій і автоматів
3.2. Приклади логічних функцій
Логічних функцій однієї змінної усього чотири. Вони наведені в таблиці 3.2.
Таблиця 3.2
Логічні функції однієї змінної
-
X
0
1
2
3
0
0
0
1
1
1
0
1
0
1
Функції 0 і 3 - константи 0 і 1 відповідно; їх значення не залежать від значення змінної, і , отже, змінна x для них неістотна. Функція 1 повторює x. Функція 2 називається "запереченням" або функцією "НЕ" і позначається або . Її значення протилежне значенню x.
Логічних функцій двох змінних - 16. Вони наведені в таблиці 3.3.
Таблиця 3.3
Логічні функції двох змінних
х1 x2 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
0 0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
Функції 0 і 15 константи 0 і 1, тобто функції з двома неістотними змінними. Відзначимо, що ці функції відрізняються від наведених у таблиці 3.2. Там вони унарні, а тут бінарні операції на В.
Функція 1 називається кон'юнкцією х1 і х2. Її позначають: або & . У всіх випадках знак кон'юнкції аналогічно знаку множення часто опускають і пишуть х1 х2 . Вона дорівнює 1, тільки якщо х1 і х2 рівні 1, тому її часто називають функцією І. Ще одна її назва - "логічне множення", оскільки її таблиця дійсно збігається з таблицею звичайного множення для чисел 0 і 1.
Функція 7 називається диз'юнкцією х1 і х2. Ії позначають: або . Вона дорівнює 1, якщо х1 або х2 дорівнює 1 ("або" тут розуміється в неподільному змісті - хоча б одне з двох). Тому її часто називають функцією АБО.
Функція 6 - це додавання по модулю 2. Її позначення х1х2. Вона дорівнює 1, коли значення її аргументів різноманітні, і дорівнює 0, коли вони рівні.
Інші функції мають назву: 13 - імплікація: х1х2; 8 - стрілка Пірса: х1х2; 14 - штрих Шеффера: х1 х2.
Інші функції спеціальних назв не мають і виражаються через перераховані вище функції.