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

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

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

ХарактеристикаПравить

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

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

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

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

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

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

СеквенцияПравить

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

Посредством секвенции реализуется двоичная функция $z=\mathrm{\phi <!--\; \phi \; -->}\left(⟨x⟩\right)$$z=\varphi \left(\left\langle x\right\rangle \right)$ , такая, что $z=1$$z=1$  имеет место только в случае

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

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

ВенъюнкцияПравить

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

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

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

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

РеализацияПравить

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

$x\wedge <!--\; \wedge \; -->\left(\stackrel{¯<!--\; ¯\; -->}{x}\vee <!--\; \vee \; -->x\mathrm{\angle <!--\; \angle \; -->}y\right)=x\mathrm{\angle <!--\; \angle \; -->}y,$$x\land \left({\bar {x}}\lor x\,\angle \,y\right)=x\,\angle \,y,$  где формула $\left(\stackrel{¯<!--\; ¯\; -->}{x}\vee <!--\; \vee \; -->x\mathrm{\angle <!--\; \angle \; -->}y\right)$$\left({\bar {x}}\lor x\,\angle \,y\right)$  представляет функцию SR-триггера.

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

секвентора $⟨xyzuv⟩$$\left\langle x\,y\,z\,u\,v\right\rangle$  пригодны следующие формулы: $v\mathrm{\angle <!--\; \angle \; -->}\left(u\mathrm{\angle <!--\; \angle \; -->}\left(z\mathrm{\angle <!--\; \angle \; -->}\left(y\mathrm{\angle <!--\; \angle \; -->}x\right)\right)\right),⟨xy⟩\wedge <!--\; \wedge \; -->⟨yz⟩\wedge <!--\; \wedge \; -->⟨zu⟩\wedge <!--\; \wedge \; -->⟨uv⟩.$$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 .$ 

См. такжеПравить

• Логика в информатике
• Асинхронная логика

ЛитератураПравить

• А. Фридман, П. Менон. Теория переключательных схем. — М.:Мир, 1978. — 580с.
• Васюкевич В. О. Венъюнкция — логико-динамическая операция. Определение, реализация, приложения. // Автоматика и вычислительная техника. — 1984. — №6. — С. 73-78.
• Васюкевич В. О. Элементы асинхронной логики. Венъюнкция и секвенция. — 2009. — 123с. — URL: http://asynlog.balticom.lv/Content/Files/ru.pdf (недоступная ссылка).

СсылкиПравить

• ASYNCHRONOUS LOGIC and NEW ALGEBRA FOR DIGITAL CIRCUITS
• Теория автоматов // mathnet.ru