- •Раздел 3. Основы теории конечных автоматов
- •3.1. Логические функции
- •3.2. Примеры логических функций
- •3.2. Связь логических функций и функциональных схем
- •3.3. Каноническое представление логических функций
- •3.4. Задача минимизации логических функций
- •3.5. Основные понятия теории конечных автоматов
- •1) Для любой входной буквы ai имеется ребро, выходящее из qi , на котором написано aj (условие полноты);
- •2) Любая буква aj встречается только на одном ребре, выходящем из qi (условие непротиворечивости или детерминированности).
- •1) ( Qi , aj ) задается автоматной таблицей s;
- •2) Для любого слова а* и любой буквы аj
- •3.6. Абстрактная и структурная теория конечных автоматов
- •3.6. Сопоставимость конечных автоматов
- •3.7. Синхронные сети из автоматов.
- •1. Параллельное соединение (рис. 3.11). Различаются соединения с общими и раздельными входами (алфавитами).
- •3.8. Пример синтеза конечного автомата
- •X(n) (состояние / выход)
- •Преобразуем исходную таблицу в специальную форму с выделением входных - выходных сигналов и внутренних состояний.
- •X1(n) Комб. Y(n)
- •3.9. Программная реализация логических функций и автоматов.
Раздел 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 переменных можно сделать функцией любого большого числа переменных. Поэтому любую конечную совокупность функций можно считать зависящей от одного и того же множества переменных.