1.4. Применение формул логики высказываний в теории однотактных дискретных автоматов Сводка теории

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

Желаемое действие автомата в общем случае может зависеть как от сигналов, поступающих в данный момент времени, так и от сигналов, поступивших ранее.

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

Д ействие автомата условно можно изобразить схемой (рис. 1.8), где , ... , – входы; , ... , – выходы.

При построении дискретного автомата принимают ряд упрощающих допущений:

1) действие автомата должно состоять в исполнении одного акта с двумя возможными исходами (например, включить или выключить электродвигатель);

2) в каждый момент времени на вход автомата поступает некоторое конечное число ( ) сигналов, каждый из которых может принимать одно из двух значений (например, для автомата стрелки сигналы могут принимать значения «Поезд прошел семафор» или «Поезд не прошел семафор»);

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

С учетом перечисленных допущений зависимость вход/выход для абстрактного автомата может быть описана следующим образом:

. (1.1)

Здесь – действие на выходе автомата; – сигналы на n-м входе автомата в моменты времени .

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

Будем рассматривать частный, но очень важный случай, когда действие автомата на выходе зависит от сигналов, поступающих на вход в данный момент времени (а не во все предыдущие). Такие автоматы называются однотактными или автоматами без памяти. В этом частном случае выражение для действия автомата упрощается и принимает вид:

.

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

Э лементарными автоматами, «строительными блоками» для более сложных, являются автоматы, реализующие логические функции (связки): (как следует из теории, они образуют полную систему, т.е. остальные логические функции могут быть выражены через эти три). Они называются соответственно логическими элементами «или», «и», «не» и изображаются следующими функциональными схемами (рис. 1.9).

Заметим, что для реализации отрицания требуется инвертор, но микросхем-инверторов в чистом виде не бывает. Они строятся либо на базе элементов логического умножения, либо на базе элементов логического сложения (т.е. элементов, реализующих дизъюнкцию, как показано на рис. 1.9). Отметим также, что в схемах, реализующих сложные логические функции (формулы), могут применяться функциональные элементы с несколькими входами.

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

Для конъюнкции эта схема выглядит следующим образом (рис. 1.10).

Нажатие кнопки А сообщает логическому элементу о том, что высказывание: А = 1, в противном случае: А = 0. Если нажать кнопку А, то по катушке реле потечет ток и контакты прямого переклю чателя а замкнутся. То же произойдет, если нажать на (отрицательный потенциал) кнопку В.

Сигнал 1 на выходе элемента зажжет лампочку х. Понятно, что лампочка загорится только в том случае, когда одновременно нажаты кнопки А и В, т.е. конъюнкция реализуется именно последовательным соединением переключателей. Сопротивление R требуется для снятия остаточного напряжения.

Для дизъюнкции релейно-контактная схема имеет вид (рис. 1.11).

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

Наконец, для отрицания релейно-контактная схема реализуется с применением обратного переключателя, т.е. контакты переключателя замкнутся при А = 0 и наоборот (рис. 1.12).

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

Т огда отрицание реализуется при помощи устройства, называемого реле с размыкающим (отрицательным) контактом (рис. 1.13).

Е сли по катушке А ток не идет ( ), то пружина оттягивает контакт В вверх и цепь замыкается. В результате, на выходе С будет ток. Если же и по обмотке А идет ток, то контакт В притягивается вниз и на выходе С нет тока. В результате, реализуется функция .

Дизъюнкция (рис. 1.14, а) и конъюнкция (рис. 1.14, б) реализуются при помощи реле с замыкающим (положительным) контактом.

Принято считать, что ток распространяется мгновенно, а на срабатывание реле (замыкание контакта) уходит один такт. Это значит, что на схеме для конъюнкции сигнал поступит на один такт позже сигнала ; сигнал на выходе возникает одновременно с сигналом .

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

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

Контактные схемы, в которых соединяются лишь контакты (нет соединений обмоток реле с контактами) представляют собой графы: ребрам графа приписаны символы логических переменных или их отрицаний; вершины означают соединения контактов, соответствующих отрезкам (двухполюсникам), которые в этих вершинах сходятся. Если по одному изконтактов, идущему в вершину, идет ток, то он распространяется по всем замкнутым в данный момент контактам, имеющим данную вершину в качестве полюса. В графе выделяются две вершины: вход и выход. На вход всегда подается ток. На другие полюсы ток извне никогда не поступает.

Если на обмотки некоторых катушек подан ток, то через один такт замкнутся соответствующие им замыкающие контакты и разомкнутся размыкающие; на контактах остальных катушек возникнет противоположная картина. Если при этом на выход схемы поступит ток, то говорят, что при данных значениях переменных (состояниях обмоток катушек) в схеме есть проводимость; в противном случае – что проводимости нет. Итак, контактная схема работает в один такт.

Логическую функцию (и соответствующую формулу), реализуемую схемой, называют ее функцией проводимости. Такая функция равна при тех значениях аргументов, при которых в схеме есть проводимость, и равна , если проводимости нет.

Для основных логических операций контактные схемы выглядят следующим образом (рис. 1.15).

К омбинируя те или иные схемы, моделирующие основные логические элементы, в соответствии со структурой формулы, предварительно записанной через дизъюнкцию, конъюнкцию и отрицание (например, в виде ДНФ или КНФ), получаем функциональные, релейно-контактные или контактные схемы для формул.

При синтезе (создании) дискретных однотактных автоматов обычно действуют по следующему алгоритму:

1. описать автомат словесно;

2. определить число входов и выходов автомата;

3. составить таблицу желаемой работы автомата (типа таблицы истинности);

4. используя полученную таблицу выписать структурную формулу (как правило, в виде ДНФ или КНФ);

5. вычертить функциональную или иную схему.