Логический автомат

Преобразования входных величин в выходные, осуществляемые дискретными автоматами без памяти, работающими в двухбуквенном алфавите, эквивалентны преобразованиям, совершаемым в формальной логике. Поэтому мы будем называть их логическими автоматами, а функции, описывающие преобразования, выполняемые логическими ав­томатами, - логическими, функциями. Математическим аппаратом, ис­пользуемым для решения задач анализа и синтеза логических авто­матов, является алгебра логики. Исторически первый вариант ал­гебры логики был разработан английским ученым Джорджем Булем в 1843 г., вследствие чего она часто называется булевой алгеброй.

Каждый выход ид логического автомата может принимать значе­ние 0 или 1 в зависимости от значений входных переменных х. Оп­ределим число всех возможных логических функций преобразования х в y_i, если входных величин равно т, каждая из них может прини­мать значение 0 или 1. Для этого расположим все входные величины в ряд x₁, x₂,…,x_m и будем рассматривать их как разряды двоич­ного числа. Ясно, что число r различных сочетаний значений входных величин равно числу различных двоичных чисел, содержащих r разрядов, откуда следует, что r=2^m. Но каждой из r ситуаций на входе может соответствовать одно из двух значений выхода 0 или 1. Поэтому общее число N всех различных логических функций для логического автомата с m двоичными входами равно

(1)

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

1. `х - отрицание x (читается «не x»). Функция отрицания оз­начает, что x=0, если x=1; и x=1, если x=0.

2. x₁ & x₂ - логическое умножение или конъюнкция (читается «x₁ и x₂»). Функция логического умножения означает, что его резуль­тат равен единице только тогда, когда x₁=1 и x₂=1, и равен нулю во всех остальных случаях.

3. x₁ v x₂ - логическое сложение или дизъюнкция ( читается «x₁ или x₂»). Функция логического сложения означает, что его ре­зультат равен нулю только тогда, когда x₁=0 и x₂=0 , и равен еди­нице во всех остальных случаях.

Логические функции могут задаваться таблицами, в которых указывается значение функции у (индекс i будем опускать) для всех сочетаний аргументов х. В табл.3.1 приведены значения двух элементарных логических функций от двух аргументов: x₁ и x₂. Эту таблицу нужно читать по строкам : « если х₁ = ..., a х₂ = ..., то х₁ и х₂ =..., а х₁ или х₂ = ...". Логические функции широко используются в теории нейронных сетей и входят в математический аппарат, применяемый при исследованиях процессов переработки информации мозгом.

Таблица 1.

Задание логических функций таблицей

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