Розв’язок поставленої задачі
Задана логічна функція має наступний вигляд:
1). Для початку приведемо задану функцію до вигляду ДДНФ (Досконала диз’юнктивна нормальна форма):
2). За правилом склеювання мінімізуємо приведену до вигляду ДДНФ функцію аналітичним методом:
3). Мінімізація функції за допомогою карт Карно.
Х2Х3 Х1
00
01
11
10 0
0
0
0
1 1 0 0 1 1
4). Таблиця істинності для заданої логічної функції.
|
Х1 |
Х2 |
Х3 |
|
Х1 Х2 |
|
Х1 Х2 Х3 |
Y |
|
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
|
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
|
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
|
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
|
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
|
1 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
|
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
Висновок. Результати мінімізації логічної функції за допомогою карт Карно та аналітичним методом за допомогою правил склеювання співпадають. Отже функція мінімізована вірно.
2.2. Синтез скінченного автомату.
Під автоматом розуміється пристрій, що самостійно виконує всі операції. Автомат — це схематизований алгоритм. Використовуючи такі обчислювальні моделі, як автомати, можна дослідити питання щодо розв’язності і складності поставленого завдання. Формальний опис автомату називають його логічною структурою. Властивості і методи перетворення логічних структур вивчає теорія кінцевих автоматів, яка підрозділяється на абстрактну та структурну. Абстрактна теорія не торкається структури самого автомата, обмежуючись лише розглядом переходів, що виконуються автоматом при змінні вихідних сигналів, які видаються автоматом у кожному стані. Структурна теорія вивчає способи побудови автоматів, їхню структуру, способи кодування вхідних і вихідних сигналів.
Скінченний автомат представляє собою набір вигляду K={A,B,C,α,β}, в якому:
А – вхідний алфавіт скінченного автомата (список вхідних змінних).
В – алфавіт внутрішнього стану.
С – вихідний алфавіт скінченного автомата (список вихідних змінних).
α – функція переходів (правила змінення внутрішніх станів).
β – функція виходів (правило, за яким формується вихід).
Існує три основних види скінченних автоматів:
1). Комбінаційна схема (КС);
2). Автомат Мура;
3). Автомат Мілі.
Послідовно розглянемо всі ці три типи автоматів.
1). КС є
найпростішим варіантом скінченного
автомата, в якому множина внутрішніх
станів і функція переходів пуста множина
(
).
Іншими словами, КС не містить внутрішніх
станів, не має „пам’яті”.
C= β(A)
2). Автомат Мура. Для автомата Мура характерно заповнення всіх 5-ти компонентів набору К залежності станів цього автомата від входів, а залежність виходів – тільки від станів.
В= α(А), С= β(В).
3). Найскладнішим варіантом є автомат Мілі. Від автомату Мура він відрізняється функцією виходу. Тобто виходи цього автомата залежні від входу і внутрішніх станів.
В= α(А), С=β(В,А).
При синтезі скінченного автомата можуть використовуватися декілька варіантів його представлення. Найбільш широкого використання отримала таблична форма подання кінцевого автомата і подання кінцевого автомата в формі графа.