Б. Синтез цифровых информационных систем на основе математической логики

Дискретные (цифровые) автоматы и системы

Й5адцатый век ознаменовался грандиозным прогрессом в области цифровой техники и компьютеризации многообразной деятельности челорека. В энергосистемах на смену электромеханическим вилам релейы и автоматики приходят цифровые устройства. Синтез этих систем и устройств базируется на математической логике (алгебра логики, булева алгебра), основы которой были заложены в XIX в. в работах Дс Моргана «Формальная логика» (1847), Джорджа Буля «Исследование законов мышления» (1854) и Чарльза Бэббиджа, создавшего в 1833 г. первую цифровую вычислительную машину.

Начиная с 50-х гг. XX столетия теория контактных систем переходит в теорию логических комбинационных схем, а затем в теорию дискретных (цифровых) автоматов. Автоматы дискретного действия основаны на реле (контактных и бесконтактных). Под реле и релейным элементом понимается элемент, обладающий релейной характеристикой, при которой изменение входной величины х вызывает скачкообразное изменение выходной величины у, принимающей лишь несколько дискретных значений. В большинстве случаев используются двузначные элементы {у = 0, у — 1}, как это имеет место в двоичной системе счисления. На рис. I приведен один из примеров такой характеристики (а) и временная диаграмма (б) изменения у (Г) при некотором поведении x (t). Различают два типа контактов реле: нормально разомкнутые (НРК) и нормально замкнутые контакты (НЗК).

Имеется некоторый разброс порогового значения входного параметра х, при котором происходит срабатывание реле и дискретное изменение выходного параметра у. Множество состояний входного параметрах < х₀ будем трактовать как состояние х = 0, соответственно множество состояний х > х₀ какх = 1.

Рис. 1. Пороговая характеристика реле (я) и дискретное изменение выходной величины (б), соответствующее работе реле с НРК Диаграмма (б) на рис. 1 соответствует работе реле с НРК: сигнал появляется при срабатывании реле, если х > х₀ На рис. 2, а показано типовое обозначение контактов в схемах, диаграмма (6) иллюстрирует работу реле с НЭК.

Рис. 2. Обозначение контактов в схемах (а) и дискретное изменение выходной величины (б), соответствующее работе реле с НЗК Логическое соответствие выхода и входа отображается таблицей соответствия, которая далее будет называться таблицей истинности (ТИ) (см. представленную ниже таблицу для НРК и НЗК).

Таблица истинности для НРК и НЗК

С точки зрения логики НРК можно рассматривать как повторитель, а НЗК — как инвертор. Данные реле можно рассматривать как простейшие дискретные автоматы с одним входом. Если же входов у автомата несколько (/?), то число состояний дискретного автомата N = 2^Р. Каждому состоянию будет соответствовать выходной параметр: либо у = 0, либо у = 1.

Элементарным автоматом будем называть автомат на два входа (*, х_ъ р = 2, N = 4). Примерами элементарных автоматов могут служить два автомата у₁ и у_и, подчиняющиеся следующим таблицам истинности (табл. 1).

Таблица 1.

Пример таблиц истинности для автомата на два входа

Свойства и структурное выполнение этих и других возможных элементарных автоматов будут рассмотрены далее.

В функциональном отношении дискретные автоматы (ДА) и релейные схемы (PC) независимо от их технического исполнения по характеру действия во времени разделяются на однотактные и многотактные.

Однотактные (комбинационные) автоматы не имеют памяти (автомат без памяти) и задержки во времени. Изменение одного из входных параметров приводит к новому состоянию автомата, которому однозначно соответствует некоторое выходное состояние*, (см. два приведенных примера).

Многотактные (последовательностные) автоматы имеют память, которая определяет их внутреннее состояние s (t). Выходу зависит не только от комбинации входных параметров, но и от состояния памяти $, которая зафиксировала некоторые внутренние параметры q_k. Если конечному множеству состояний соответствует некоторое конечное множество состояний у, то такой автомат называют конечным. Если автомат имеет задержки во времени, то его называют динамическим.

Для иллюстрации взаимосвязи между релейными схемами и конечными автоматами рассмотрим схему с нормально замкнутыми и разомкнутыми контактами, изображенную на рис. 3. Реле Х_{ имеет два контакта НРКх, и НЗК*, реле Х₂ имеет НРКх₂ и НЗК*₂, реле Х_ъ имеет один НРК*₃ Нетрудно видеть, что у = 1 лишь в следующих состояниях:

В целом работа такого конечного автомата отражается таблицей состояний (табл. 2).

Рис. 3. Автомат с тремя управляемыми контактами *, х₂, х₃

Таблица 2.

Таблица истинности для автомата с тремя входами

Таким образом, можно утверждать, что у есть некоторая логическая функция аргументов х_г Например, если х, = 1, х₂ = 0, х₃ = 0, то у = 0 и т. д. Алгебра логики предназначена для описания такой функциональной логической связи, а также для преобразования соответствующих формул к виду, в котором их техническая реализация будет по тому или иному критерию оптимальной. Например, можно потребовать минимальное количество контактов. Применяя аппарат алгебры логики, можно вместо схемы, представленной на рис. 3, получить более простую схему (рис. 4) с той же функциональной таблицей состояний.

В теории ДА применяется понятие «высказывание» — основная составляющая алгебры логики. Под высказыванием понимается предложение, относительно которого справедливо утверждение об его истинности (обозначается «1») или ложности (обозначается «О»).

Рис. 4. Оптимальный автомат.

В логике любое высказывание либо истинно, либо ложно, т. е. переменная, которая ставится ему в соответствие, принимает одно из двух значений — 0 или 1. Например, высказывание «электрический ток есть упорядоченное движение электрических зарядов в определенном направлении» признано истинным, а высказывание «по линиям электропередачи протекает переменный ток» не может быть признано истинным, поскольку существуют Л ЭП постоянного тока, т. е. это высказывание ложно.

В дискретных автоматах в качестве высказываний обычно рассматриваются фразы такие, как «сигнал (электрический потенциал) есть в точке х,», «контакт а замкнут», «контакт Ь разомкнут». Как алгебра абстрагируется от физической природы аргумента (длина пути, скорость, напряжение) и ее интересуют лишь математические соотношения в избранной мере (например, соотношение сторон в прямоугольном треугольнике), так и алгебру логики интересует не смысловая сторона высказывания или сложных высказываний и логических выражений, а лишь их истинность или ложность в рассматриваемых случаях.

Подводя итог сказанному, можно сформулировать понятие математической логики: это есть формальная наука о логических соотношениях в высказываниях и утверждениях, имеющая большое значение в теории и синтезе релейных схем, дискретных автоматов, ПВК, передачи и обработки информации. Обобщенно эта наука является основой разработки устройств, в которых используются элементы с двумя устойчивыми состояниями, одно из которых обозначено как «1», другое — как «О». Логические переменные оказываются тесно связанными с числами, записанными в двоичной системе счисления, когда каждый разряд числа можно трактовать как логическую переменную (аргумент), а утверждение, что в данном разряде есть 1, может быть истинным или ложным.