Секвенциальная логика

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

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

Характеристика

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

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

Синхронная секвенциальная логика

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

Математический аппарат синхронной логики задают автоматные модели Мили и Мура.^[1]

Асинхронная секвенциальная логика

Асинхронная секвенциальная логика для выражения эффекта запоминания использует моменты смены состояний, которые задаются не в явном виде, а исходя из сопоставления логических величин по принципу «раньше-позже». Для асинхронной логики достаточно установить очерёдность смены состояний безотносительно каких-либо привязок к реальному или виртуальному времени. Теоретический аппарат секвенциальной логики составляют математические инструменты секвенции и венъюнкции, а также логико-алгебраические уравнения на их основе.

Секвенция

У этого термина существуют и другие значения, см. Секвенция.

Секвенция (лат. sequentia – последовательность) — это последовательность пропозициональных элементов, представляемая упорядоченным множеством, например, ${\displaystyle \left\langle x\right\rangle =\left\langle x_{1}\,x_{2}\,\ldots \,x_{\mathrm {n} }\right\rangle }$, где ${\displaystyle x_{i}\in \left\{0,1\right\}.}$

Посредством секвенции реализуется двоичная функция ${\displaystyle z=\varphi \left(\left\langle x\right\rangle \right)}$, такая, что ${\displaystyle z=1}$ имеет место только в случае

${\displaystyle \left(x_{1}\land x_{2}\land \,\ldots \,x_{\mathrm {n} }\right)=1}$ при условии, что ${\displaystyle \left(x_{i}=1\right)\prec \left(x_{j}=1\right)}$ для всех ${\displaystyle \mathrm {\,i<j} .}$ (Символ ${\displaystyle \prec }$ задаёт отношение опережения).

Секвенциальная функция обращается в единицу при единичных значениях аргументов, установка которых осуществляется поочерёдно, начиная с ${\displaystyle x_{1}}$ и заканчивая ${\displaystyle x_{\mathrm {n} }}$. Во всех остальных случаях — ${\displaystyle z=0}$.

Венъюнкция

Венъюнкция — это асимметрическая логико-динамическая операция ${\displaystyle \angle \,,}$ согласно которой связка ${\displaystyle x\,\angle \,y}$ принимает единичное значение только в случае ${\displaystyle x\,\land \,y=1}$ при условии, что в момент установления ${\displaystyle x=1}$ равенство ${\displaystyle y=1}$ уже имело место.

Истинность венъюнкции обусловлена переключением ${\displaystyle x=0/1}$ на фоне ${\displaystyle y=1.}$

Логическая неопределённость выражается посредством венъюнкции: ${\displaystyle 1\,\angle \,1.}$

Венъюнкция и минимальная (двухэлементная) секвенция функционально идентичны: ${\displaystyle x\,\angle \,y\ =\left\langle y\,x\right\rangle .}$

Реализация

Венъюнктор является основным операционным элементом памяти секвенциальной логики. Он реализуется на основании равенства

${\displaystyle x\land \left({\bar {x}}\lor x\,\angle \,y\right)=x\,\angle \,y,}$ где формула ${\displaystyle \left({\bar {x}}\lor x\,\angle \,y\right)}$ представляет функцию SR-триггера.

Секвентор строится на основе композиции из соединённых определённым образом венъюнкторов. Например, для реализации

секвентора ${\displaystyle \left\langle x\,y\,z\,u\,v\right\rangle }$ пригодны следующие формулы: ${\displaystyle v\,\angle \,\left(u\,\angle \,\left(z\,\angle \,\left(y\,\angle \,x\right)\right)\right),\,\left\langle x\,y\right\rangle \land \left\langle y\,z\right\rangle \land \left\langle z\,u\right\rangle \land \left\langle u\,v\right\rangle .}$

См. также

• Асинхронная логика