Обозначение Равносильность формул обозначается знаком =.
_____
Определение Суперпозицией (композицией) функций называется сложная функция, составленная из этих функций.
ТЕОРЕМА 12.4 (Шеннона) Любая булева функция может быть
представлена как суперпозиция трёх операций 
над
двоичными переменными.
Определение Конъюнктом называется любая конъюнкция двоичных переменных или их отрицаний.
Пример 
.
Определение Булева функция вида 
, где 
- конъюнкты, называется дизъюнктивной нормальной формой (ДНФ)
Определение Если каждый конъюнкт содержит все переменные
(причём только саму переменную или её отрицание), то ДНФ называется
совершенной (СДНФ).
СЛЕДСТВИЕ Из формулы Шеннона следует, что любая булева
функция представима в виде СДНФ (причём это представление
единственно, с точностью до перестановки конъюнктов).
АЛГОРИТМ приведения к СДНФ с помощью таблицы
истинности:
1) нарисовать таблицу истинности для функции 
;
2) по строкам, в которых функция равна 
, выписываем формулу Шеннона.
Определение Дизъюнктом называется любая дизъюнкция двоичных переменных или их отрицаний.
Определение Булева функция вида 
где 
-дизъюнкт, называется конъюнктивной нормальной формой (КНФ).
Определение Если каждый дизъюнкт содержит все переменные, причём либо саму переменную, либо её отрицание, то КНФ называется совершенной (СКНФ).
СЛЕДСТВИЕ Каждая булева функция единственным образом представима в виде СКНФ с точностью до перестановки дизъюнктов.
ЗАМЕЧАНИЕ По схеме теоремы Шеннона доказывается такая
формула представления булевой функции в виде СКНФ
.
_____
Определение Замыканием подмножества М булевых функций называется множество 
булевых функций, которые получаются из 
с помощью операции суперпозиции.
Определение Подмножество булевых функций называется функционально полным (базисом), если совпадает со всем множеством булевых функций.
ЗАМЕЧАНИЕ Известен критерий Поста функциональной
полноты произвольного множества .
Определение Функционально полное называется базисом (минимальным базисом), если удаление хотя бы одной функции из делает его не функционально полным.
ТЕОРЕМА 12.5 Следующие подмножества операций являются
базисами: 
.
_____
Определение Минимальной формой булевой функции в базисе называется такая равносильная ей логическая формула, которая содержит минимальное число суперпозиций функций из базиса , причем скобки допускаются.
Приведем один метод построения минимальной булевой формы в
базисе Буля 
. Пусть булева функция 
задана в виде таблицы истинности или СДНФ. Составим "карту" всевозможных конъюнктов, образованных переменными из первых 
столбцов. Эта таблица имеет 
строк.
| 
| . | 
| 
| 
| 
| . | 
| 
| . | …
|
|
| 
| . |
| 
|
|
| . | 
| 
| . | …
|
| . | . | . | . | . | . | . | . | . | . | . | . |
|
| 
| . | 
|
| 
| 
| . | 
| 
| . | …
|
|
| . |
|
| 
| 
| . |
|
| . | …
|
ЗАМЕЧАНИЕ Если конъюнкт 
, стоящий в последнем
столбце 
ой строки таблицы не входит в СДНФ функции
, то любой конъюнкт этой строки не входит ни в одну
ДНФ, равносильную . Действительно, в противном
случае в таблице истинности этой ДНФ в 
- ой строке стояла бы
единица, то есть входил бы СДНФ.
На этом замечании основан метод минимизирующих карт.
АЛГОРИТМ (построения минимальной булевой формы)
1) Вычеркнуть в карте строки, порожденные конъюнктами ,
которые не входят в СДНФ функции .
2) Вычеркнутые в этих строках конъюнкты вычеркнуть также в
остальных строках.
3) В каждой строке оставить только конъюнкты с минимальным
числом сомножителей, а остальные вычеркнуть.
4) В каждой строке выбрать по одному конъюнкту, и составить из
них ДНФ.
5) Из построенных в пункте 4) ДНФ выбрать минимальную.
______
Определение Класс электронных схем, реализующих одну и ту же основную логическую функцию, называется логическим элементом (ЛЭ).
Обозначение Логические элементы называются "и", "или", "не", "и-не", "или-не" и обозначаются ярлыками.
Определение Логической схемой (ЛС) называется схема, составленная из логических элементов (ЛЭ), путем соединения со входами других по следующим правилам:
1) выход ЛЭ можно присоединить ко входам нескольких логических элементов;
2) на вход ЛЭ можно подавать сигналы двух типов (0 или 1);
3) выходы ЛЭ нельзя соединять вместе;
4) выходы ЛЭ нельзя подключать к собственным входам.
Определение Логическая схема с 
входами 
и 
выходами 
, описываемая функциональным преобразователем
называется комбинационной схемой (КС) или (n,m) – полюсником.
ЗАМЕЧАНИЕ В комбинационной схеме могут присутствовать
и контуры (обратные связи). Согласно определению контур
содержит не менее двух ЛЭ.
Определение Две КС называются эквивалентными, если их функциональные преобразователи совпадают.
Определение Задачей анализа КС называется задача нахождения ее функционального преобразователя. Последний формируется пошагово, двигаясь по логическим элементам схемы от ее выходов ко входам.
Определение Задачей синтеза КС называется процесс ее построения, включающий три этапа:
1) нахождение функционального преобразователя по вербальному
описанию; 2) минимизация функционального преобразователя;
3) построение КС в данном элементном базисе.
_____
Определение Конечным автоматом Мили называется множество из пяти объектов 
, в котором:
- конечное непустое множество (пространство) состояний,
- конечное непустое множество входных сигналов (входной
алфавит),
- конечное непустое множество выходных сигналов (выходной
алфавит),
- функция переходов,
- функция выходов.
ЗАМЕЧАНИЕ Автоматы могут задаваться:
1) в виде взвешенного орграфа (граф переходов автомата) или в
виде блок-схемы программы, реализующей поведение автомата,
2) таблично (функции переходов и выходов задаются в виде таблиц)
ЗАМЕЧАНИЕ При графическом изображении автомата состоя
ния обозначают вершинами, а входы – дугами с направлениями,
определяемыми функцией переходов. При этом над дугой указыва
ются соответствующие значения входа и выхода (взвешенная дуга).
Рассмотрим специальный класс автоматов.
Определение Пусть 
. Тогда функции перехода и выхода
являются функциональными преобразователями. Обозначим их
соответственно
и реализуем в виде логических схем (ЛС) с 
входами и соответственно 
выходами. Составим из них ЛС, соединив выходы левого блока с соответствующими входами правого и левого блоков. входов сделаем общими для обоих блоков. Полученная ЛС всегда находится в определен ном состоянии, пока на нее не действуют входные сигналы. Ввиду того, что один и тот же сигнал может вызвать разные выходные сигналы, эта ЛЭ не будет комбинационной. Она называется последовательностной схемой или цифровым автоматом.
ЗАМЕЧАНИЕ Цифровой автомат задается еще и 3) аналитически (
задаются в виде функциональных преобразователей),
4) в виде логической схемы.
Произвольный автомат можно реализовать как составную часть
цифрового автомата. Для построения последнего нам понадобятся
некоторые понятия.
Определение Пусть - конечное множество и 
. Тогда
инъективное отображение 
называется кодировщиком множе ства , а сюръективное 
- декодировщиком множества 
.
ЗАМЕЧАНИЕ Пусть 
- отображение конечного
множества в конечное множество и 
.
Тогда это отображение можно представить в виде композиции
, где 
- кодировщик, 
-
функциональный преобразователь и 
- декодировщик.
Область определения и область значений функционального
преобразователя по числу элементов, вообще говоря, больше
соответственно областей 
для отображения 
.
___
Определение Обозначим 
алфавит, то есть конечное множе
ство элементов (букв), 
- множество всевозможных конечных цепочек букв (слов) вида 
. Количество букв в слове называется его длиной и обозначается 
. Операция составления двух слов в одно 
называется склеиванием (сцеплением, конкатенацией) этих слов. Если 
есть пустая цепочка, то 
.
ЗАМЕЧАНИЕ Множество представляет собой полугруппу
относительно операции склеивания, так как последняя обладает
свойством ассоциативности: 
.
Понятие склеивания позволяет расширить действие автомата с множества букв на множество слов .
Определение Расширенными функциями переходов и выходов автомата 
называются отображения 
, определяемые рекуррентными формулами:
.
Следующее замечание дает развернутый алгоритм вычисления значений (представления) расширенных функций на слове.
ЗАМЕЧАНИЕ
1) 
.
2) 
Определение Реакцией состояния 
автомата Мили называется входное-выходное отображение 
, определяемое по правилу 
.
ЗАМЕЧАНИЕ Реакция совпадает с сужением отображения 
на множество 
. Поэтому знание расширенной функции переходов означает знание всех реакций состояний (-реакции автомата ), и наоборот, реакция автомата определяет расширенную функцию выходов.
_____
Определение Состояния 
автомата называются эквивалентными, если 
, то есть их реакции совпадают: 
.
Определение Состояния автомата называются 
эквива лентными, если они неразличимы для всех входных слов длины 
: 
. То есть их реакции совпадают на множестве слов длины .
Обозначение 
или, что все равно, 
ТЕОРЕМА 12.6 1) Множество состояний разбивается на
совокупность 
максимальных подмножеств (классов)
эквивалентных между собой состояний.
2) 
.
3) Если 
, то 
.
4) (теорема Хаффмана-Мили) 
. То есть, если
реакции 
совпадают на словах длины 
, то
состояния 
эквивалентны
Определение Два автомата с одинаковыми входными и выходными
алфавитами называются эквивалентными автоматами, если каждое состояние одного из них эквивалентно некоторому состоянию другого автомата, и наоборот.
Определение Автомат называется приведенным (сокращенным), если все его состояния попарно не эквивалентны.
СЛЕДСТВИЕ Согласно теореме Хаффмана-Мили, начиная с разбие ния 
пространства 
все состояния, попавшие в один класс, имеют одинаковые реакции. Если отождествить все состояния, попавшие в один класс, то получаем новый автомат, который является приведенным по пост роению. Он эквивалентен исходному автомату, что следует из определения.
АЛГОРИТМ (построения приведенного эквивалентного
автомата). Последовательно строят разбиения 
, используя пункт 2) теоремы. В силу пункта 4) таких шагов будет не более 
. В силу пункта 3) первое разбиение, для которого , определяет классы эквивалентных состояний.
_____
Определение Приведенный автомат Мили называется автоматом с конечной памятью, если существуют такие число 
и отображение 
, что 
имеет место равенство 
. Наименьшее число с таким свойством называется памятью автомата.
ЗАМЕЧАНИЕ Если есть автомат с конечной памятью , то
будет
.
То есть функционирование автомата вполне определяется знанием предыдущих входных букв и откликов на них.
Определение Рассмотрим пути в графе автомата, который по определению является орграфом. Образуем по нему матрицу смежности и заменим в ней каждое число, стоящее на пересечении -ой строки и 
-го столбца на соответствующее количество дуг, начинающихся в вершине 
и оканчивающихся в вершине 
. поставив между ними знаки дизъюнкции 
. Полученная матрица 
называется переходной матрицей первого порядка автомата . Определим относительно операции конкатенации (склеивания) двух путей в качестве умножения и операции дизъюнкции в качестве сложения произведение матриц. так полученная 
-ая степень 
переходной матрицей -го порядка автомата .
ЗАМЕЧАНИЕ 1) Совокупность путей длины , начинающихся в
вершине и оканчивающихся в вершине , совпадает с элементом
матрицы , стоящим на пересечении -ой строки и -го столбца.
2) совокупность путей длины , оканчивающихся в вершине ,
совпадет с совокупностью элементов -го столбца матрицы .
Определение Каждой дуге в графе автомата соответствует пара букв вход-выход. Сопоставим каждому пути этого графа последовательность соответствующих входов- выходов. такая последовательность называется вход-выходным путем.
Обозначение 
- совокупность вход-выходных путей матрицы , соответствующих всем путям -го столбца этой матрицы, 
.
ТЕОРЕМА 12.7 1) (Гилл) Если есть автомат с конечной
памятью, 
, то 
.
2) Автомат имеет конечную память тогда и только тогда, когда для
некоторого не существует двух равных вход-выходных путей
длины , оканчивающихся в разных состояниях: 
_____
Рассмотрим одну разновидность автоматов Мили.
Определение Автомат Мили , у которого функция выходов задается в виде 
, где 
- какое-либо отображение (называемое определяющим), называется автоматом Мура. То есть функция выхода автомата Мура определяется только состоянием автомата, но не 
, как у автомата Мили, а состоянием 
, в которое он переходит при подаче буквы 
.
Обозначение 
.
Определение Реакцией состояния автомата Мура называется отображение 
, определяемое по правилу
.
ЗАМЕЧАНИЕ Каждый автомат Мили порождает эквивален
тный ему автомат Мура с числом состояний 
по
правилу: каждое состояние исходного автомата заменяется на
несколько состояний в количестве, равном числу различных
значений функции выходов в этом состоянии при всевозможных
значениях букв входного алфавита.
_____
Определение Автомат 
всегда находится в определенном состоянии 
. Это состояние называется начальным, а пара 
- инициальным автоматом.
ЗАМЕЧАНИЕ Каждый автомат порождает
инициальных автоматов.
_____
Определение Состояние инициального автомата называется достижимым из 
, если 
.
СЛЕДСТВИЕ Состояние не достижимо из , если
.
АЛГОРИТМ (нахождения множества достижимых состояний
автомата) 1) Положим
.
По построению каждое последующее множество содержит предыду
щее.
2) Так как после первого совпадения 
все последующие множе
ства будут совпадать с 
и 
, то первое совпаде
ние произойдет при 
. Поэтому 
есть множество
достижимых состояний.
Понятие достижимости и следующее понятие являются языком, на котором формулируется алгоритм эквивалентности инициальных автоматов.
Определение Прямым произведением автоматов
называется автомат 
, где
.
ЗАМЕЧАНИЕ Достижимость состояния 
из 
в
прямом произведении равносильна тому, что
.
Определение Инициальные автоматы 
с 
называются эквивалентными, если их реакции 
совпадают, то есть 
.
ТЕОРЕМА 12.7 (Мура) Инициальные автоматы 
эквивалентны тогда и только тогда, когда для любого достижимого
состояния инициального автомата 
имеет место
равенство 
.
ЗАМЕЧАНИЕ Из определения достижимости следует, что если
из пространства состояний инициального автомата выбросить все
недостижимые состояния, то получится инициальный автомат,
который будет эквивалентен исходному.
_____
Определение Параллельным соединением двух автоматов 
с преобразователем информации 
называется автомат 
, функции которого определяются по правилу
,
.
Определение Последовательным соединением (суперпозицией) двух автоматов 
называется автомат 
, функции которого определяются по правилу 
,
.
ЗАМЕЧАНИЕ Параллельное и последовательное соединения
автоматов являются частными случаями каскадной композиции
двух и более автоматов.
Определение Декомпозицией автомата называется представле ние его в виде композиции автоматов с более простой структурой.
Для формулировки алгебраического метода декомпозиции нам понадобится ряд понятий.
Определение Автомат 
с таблицей переходов
| 
|
| 
|
|
|
| 
|
|
|
|
|
называется триггером.
ЗАМЕЧАНИЕ Триггер порождает три отображения пространст
ва состояний: 
. Они составляют
множество всех отображений вида 
, и это множество
замкнуто относительно ассоциативной операции композиции. Оно
называется полугруппой триггера. Аналогично строится полугрупп
па отображений для произвольного автомата без выходов 
Полугруппа этих отображений 
, называется
полугруппой автомата.
Определение Подгруппа 
группы 
называется нормальной, если 
. Группа называется простой, если у нее нет нетривиальных (= 
) нормальных подгрупп.
Определение Автомат 
называется автоматом простой группы, если его полугруппа 
является простой группой.
Определение Группа делит полугруппу 
, если существует гомоморфизм 
какой-либо полугруппы 
на : 
.
Имеет место
ТЕОРЕМА 12.8 (о декомпозиции конечного автомата)
1) Две ортогональные конгруэнции 
автомата без выходов
порождают параллельное соединения автоматов 
,.
эквивалентное автомату .
2) Одна конгруэнция 
автомата без выхода порождают
эквивалентный автомат, который является последовательным
соединением автоматов.
3) (теорема Крона-Роудза) Конечный автомат можно представить в
виде каскадного соединения из триггеров и автоматов простых
групп, которые делят полугруппу исходного автомата.
____
Преобразование информации есть результат выполнения
некоторого алгоритма, при этом операционный автомат (ОА) реализует
шаги алгоритма, а управляющий автомат (УА) реализует порядок
выполнения шагов.
При проектировании автомата выделяют три этапа.
1) Исходной информацией на системном этапе являются сово купность классов решаемых задач и параметры будущего автомата. Строится композиция пар автоматов ОА и УА. Определяются их взаимодействие и объем необходимой памяти.
2) На логическом этапе производится синтез ОА и УА в виде
логических схем. При этом для формализованного синтеза ОА
используется теория бесконечных автоматов, для УА – теория конечных автоматов. В последнем случае выделяются два этапа: этап построения автоматного оператора (состоит из трех подэтапов: а) алгоритмический, б) абстрактный, в) кодирование внутренних состояний) и этап структурного синтеза автомата (реализация его в виде сети или каскадного соединения элементарных автоматов).
3) На техническом этапе строится принципиальная монтажная схема и готовится техническая документация.
_____
С помощью конечного автомата можно реализовать, например, алгоритм сложения дух чисел. Однако не каждый алгоритм допускает реализацию в виде конечного автомата.
Определение Конечное число элементов 
назовем словарем; элементы словаря называются символами (словами); последовательности символов называются цепочками (предложениями); множество выделенных предложений 
называется языком над словарем .
Обозначение 
- язык над словарем ; 
- множество всех цепочек.
Определение Грамматикой называется конечный механизм задания языка.
Приведем два таких механизма.
Определение Порождающей грамматикой языка 
называется конечный набор правил, позволяющий строить правильные предложения и только их.
Определение Распознающей грамматикой языка называется
критерий принадлежности данной цепочки языку. Роль распознающей грамматики может выполнять следующий автомат без выходов. Конечным автоматом-распознавателем называется пятерка 
, где - конечное множество состояний, - входной алфавит, - начальное состояние, 
- функция переходов, 
- множество финальных состояний. Конечный автомат-распознаватель допускает цепочку 
, то есть 
, тогда и только тогда, когда 
переводит его из состояния в состояние 
. Язык, для которого существует распознающий его автомат-распознаватель, называется автоматным языком.
_____
Определение Алгоритм – определенное на некотором языке конечное предписание (рецепт), задающее дискретную последовательность исполняемых элементарных операций для решения задачи.
ЗАМЕЧАНИЕ Существует несколько формальных моделей
алгоритма: Геделя, Черча, Тьюринга, Маркова. Доказано, что
алгоритм, реализуемый в одной из этих моделей, реализуем и в
остальных.
Конечный автомат-распознаватель выполняет преобразование информации по определенным правилам, то есть реализует некоторый алгоритм обработки информации. Один из главных вопросов информатики – построение автоматического устройства, реализующего алгоритмы. Мы показали, что не существует автомата-распознавателя, реализующего алгоритм задания языка 
, 
, как и не существует автомата, реализующего алгоритм умножения двух произвольных чисел. Для того чтобы обобщение понятия авто матно реализуемых алгоритмов было более наглядным, рассмотрим такую интерпретацию конечного автомата-распознавателя.
ЗАМЕЧАНИЕ Конечный автомат (КА) – это устройство с
конечным числом внутренних состояний, одним входом и одним
выходом. Вход реализован в виде считывающей головки, которая
движется вдоль входной ленты и потактово считывает содержимое
<