2 Теоретические основы

2.1 Конечный автомат

Рассмотрим некоторое устройство, приведенное на рисунке 2.1. Конечный автомат можно представить как устройство преобразования дискретной информации, имеющее конечное множество входных Х и выходных Y бинарных каналов и находящееся в каждый дискретный момент времени t в одном из состояний конечного множества Z.

Такое устройство, которое характеризуется входным множеством сигналов X, выходным множеством сигналов Y, множеством внутренних состояний Z(t), функцией переходов (t) и выходов (t), называется цифровым конечным автоматом.

Цифровой автомат без элементов памяти называют тривиальным автоматом, или комбинационной схемой.

Существует два подхода при изучении, анализе и синтезе цифровых автоматов - макроподход и микроподход. При макроподходе интересуются внешним поведением автомата. Вид входной информации и выходной, в какой последовательности изменяются его состояния. При этом, не рассматривается внутреннее строение автомата, содержание его логических элементов, связей. На этом пути приходят к понятию абстрактного цифрового конечного автомата, который может быть задан с помощью набора входных сообщений, выходных логических функций, количества его состояний и переходов между ними, описывающих его поведение во времени и многомерном пространстве функций.

При микроподходе учитывается состав логических элементов, структура устройства, междуэлементные связи, логическая схема и математическое описание процесса функционирования при смене состояний автомата в различных последовательностях, его зависимость от входных булевых переменных. На этом пути приходят к понятию структурного конечного цифрового автомата.

Структурный автомат может быть задан системой логических функций аналитического описания, табличным способом, графом автомата, граф-схемой алгоритма и другими способами.

2.2 Основные логические операции

При образовании из простых высказываний сложных, большую роль играют соединительные связки, определяющие смысл и логику целого предложения. Например: "Я пойду в парк и встречу друга", "Я пойду в парк или встречу друга", "Если я пойду в парк, то встречу друга", "Я пойду в парк, если и только если встречу друга", "Я пойду в парк тогда и только тогда, когда встречу друга".

В алгебре логики соединительные связки, кроме связи переменных, определяют логические операции. Основные из них будут приведены ниже с принятыми в технической литературе обозначениями и таблицами истинности.

Таблицей истинности называется таблица, в которой приведены возможные значения {0,1} переменных высказываний и соответствующие им из множества {0,1} значения основной цели (функции) сложного высказывания.

2.2.1 Операция отрицания

Операция отрицания - НЕ, в алгебре логики обозначается черточкой (чертой) над переменной (формулой): . Встречается обозначение ¯|Х, ~X.

Отрицанием называется такая логическая операция между входной логической переменной X и выходной логической переменной Y, при которой Y истинно только тогда, когда X ложно, и наоборот, Y ложно только тогда, когда истинно X.

С помощью логико-математической символики логическая функция НЕ записывается как у= и читается "у равно не х."

Например, если X - утверждение о наличии сигнала Лог.1 на входе микросхемы, то соответствует утверждению о наличии сигнала Лог.0 на выходе (см. рисунок 2.2).