- •Розділ 3. Основи теорії кінцевих автоматів
- •3.1. Логічні функції
- •3.2. Приклади логічних функцій
- •3.3 Зв'язок логічних функцій і функціональних схем
- •3.4 Канонічне представлення логічних функцій
- •3.5. Задача мінімізації логічних функцій
- •3.6. Основні поняття теорії кінцевих автоматів
- •1) Для будь-якої вхідної букви ai є ребро, що виходить із qi, на якому написане aj (умова повноти);
- •2) Будь-яка буква aj зустрічається тільки на однім ребрі, що виходить із qi (умова несуперечності або детермінованості).
- •1) ( Qi , aj ) задається автоматною таблицею s;
- •2) Для будь-якого слова а* і будь-якої букви аj
- •3.7. Абстрактна і структурна теорія кінцевих автоматів
- •3.8. Співставлення кінцевих автоматів
- •3.9. Синхронні мережі з автоматів.
- •1. Паралельне з'єднання (рис. 3.11). Різняться з'єднання з загальними і роздільними входами (алфавітами).
- •3.10. Приклад синтезу кінцевого автомата
- •X(n) (стан / вихід)
- •Перетворимо вихідну таблицю в спеціальну форму з виділенням вхідних - вихідних сигналів і внутрішніх станів.
- •X1(n) Комб. Y(n)
- •3.11. Програмна реалізація логічних функцій і автоматів.
НГА Украины
Методические материалы Кафедра СА и
У Лекции по основам дискретной математики
Розділ 3. Основи теорії кінцевих автоматів
3.1. Логічні функції
У цьому розділі дискретної математики особливу роль будуть грати двоелементні множини В і двійкові змінні, що приймають значення з В. Його елементи часто позначають 0 і 1, проте вони не є числами в звичайному значенні. Найбільше поширена інтерпретація двійкових змінних - логічна: "так" - "ні", "істинно"(І) і "хибно" (Х). У контексті, що містить одночасно логічного й арифметичного величини, ця інтерпретація звичайно фіксується явно: так у мовах програмування вводиться спеціальний тип змінної - логічна змінна, значення якої позначається true і false.
Алгебра, утворена множиною В разом із усіма можливими операціями на ньому, називається алгеброю логіки. Логічною функцією від n змінних називається n - арна операція на В. Таким чином, логічна функція f(x1, ..., xn) - це функція, що приймає значення 0, 1. Множина всіх логічних функцій позначається Р2, множина всіх логічних функцій n змінних - Р2(n).
Алгебра, утворена k-елементною множиною В разом із всіма операціями на ній, називають алгеброю k-значної логіки, а n - арні операції на k - елементній множині називаються k - значними логічними функціями n змінних; множина всіх k - значних логічних функцій позначається Рk.
Надалі будемо розглядати тільки логічні функції з Р2. Приклад такої функції показаний у табл. 3.1.
Таблиця 3.1 - Приклад логічної функції
-
x1
0
0
0
0
1
1
1
1
x2
0
0
1
1
0
0
1
1
x3
0
1
0
1
0
1
0
1
f
0
1
0
0
1
1
0
0
Будь яка логічна функція n - змінних може бути задана таблицею, у лівій (верхній) частини якої перераховані усе 2n наборів значень змінних, а в правій частині - значення функцій на цих наборах. Наприклад, таблиця 3.1 задає функцію трьох змінних. У цій таблиці набори розташовані в лексико - графічному порядку, що збігається з порядком зростання наборів, що розглядаються як двійкові числа. Цим упорядкуванням будемо користуватися і надалі.
При будь-якому фіксованому упорядкованому наборі логічна функція n змінних цілком визначається вектор - стовпчиком значень функції, тобто 2n елементами. Змінна хi у функції f(x) називається несуттєвої, якщо зміна її значень не змінює значення f(x). У цьому випадку функція f(x) по суті залежить від n-1 змінних, тобто являє собою нову функцію g(x) від n - 1 змінних. Говорять, що функція g(x) отримана з функції f(x) шляхом видалення фіктивної змінної.
Зміст видалення фіктивних змінних очевидний, оскільки вони не впливають на значення функції і є з цього погляду зайвими. Проте іноді буває корисно вводити фіктивні змінні. Завдяки такому введенню усяку функцію n змінних можна зробити функцією будь-якого великого числа змінних. Тому будь-яку кінцеву сукупність функцій можна вважати залежною від однієї множини змінних.