Секвенційна логіка

Секвенці́йна ло́гіка — це логіка пам'яті цифрових пристроїв. Назва «секвенційна» походить з англ. 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 .}$

Див. також

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

Примітки

1. Класифікація абстрактних автоматів

Література

• А. Фрідман, П. Менон. Теорія перемикальних схем. — М.: Мир, 1978. — 580с.
• Васюкевіч В. О. Вен'юнкція — логіко-динамічна операція. Визначення, реалізація, додатки. / / Автоматика і обчислювальна техніка. — 1984. — №  6. — С. 73-78.
• Васюкевіч В. О. Елементи асинхронної логіки. Вен'юнкція і секвенція. — 2009. — 123с. — URL: http://asynlog.balticom.lv/Content/Files/ru.pdf^[недоступне посилання з червня 2019].

Посилання

• https://web.archive.org/web/20120227135150/http://asynlog.balticom.lv/
• Http://www.mathnet.ru/php/getFT.phtml?jrnid=intv&paperid=28&what=fullt&option_lang=rus Теорія автоматів

Портал «Програмування»   Портал «Математика»