Прикладная теория цифровых автоматов

Приведены сведения об абстрактных автоматах 
Мили и Мура, способах их представления, понятие 
реакции автомата на входное слово и определение 
эквивалентных автоматов. Описаны методы взаимного эквивалентного преобразования автоматов. 
Даны примеры синтеза структурных автоматов на 
базе RS-, D-, Т- и JK-триггеров. Представлены общие сведения о микропрограммном управлении, 
методы разметки граф-схем микропрограмм и правила построения по ним автоматов Мили и Мура. 
Рассмотрены методы канонического синтеза структурных управляющих автоматов с жесткой и программируемой логикой, а также структурная организация и принципы синтеза операционных автоматов. Может использоваться для самостоятельного 
внеаудиторного изучения дисциплины.

А. И. Постников, О. В. Непомнящий, Л. В. Макуха
ПРИКЛАДНАЯ ТЕОРИЯ 
ЦИФРОВЫХ АВТОМАТОВ

Учебное пособие

ИНСТИТУТ КОСМИЧЕСКИХ  
И ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

А. И. Постников, О. В. Непомнящий, Л. В. Макуха  
 Прикладная теория цифровых автоматов

Министерство образования и науки Российской Федерации 
Сибирский федеральный университет 
 
 
 
 
 
 
 
 
 
 
 
 
А. И. Постников, О. В. Непомнящий, Л. В. Макуха 
 
 
ПРИКЛАДНАЯ ТЕОРИЯ 
ЦИФРОВЫХ АВТОМАТОВ 
 
 
Учебное пособие 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Красноярск 
СФУ 
2017 

УДК 519.713(07) 
ББК 22.181.3я73 
П759 
 
Р е ц е н з е н т ы: 
Н. Г. Кузьменко, кандидат технических наук, доцент, директор 
ООО «Предприятие связи и радионавигации Енисейского бассейна»; 
Н. В. Титовская, кандидат технических наук, доцент Красноярского государственного аграрного университета 
 
 
 
Постников, А. И.  
П759 
 
Прикладная теория цифровых автоматов : учеб. пособие / 
А. И. Постников, О. В. Непомнящий, Л. В. Макуха. – Красноярск : 
Сиб. федер. ун-т, 2017. – 206 с. 
ISBN 978-5-7638-3661-5 
 
 
 
Приведены сведения об абстрактных автоматах Мили и Мура, способах 
их представления, понятие реакции автомата на входное слово и определение эквивалентных автоматов. Описаны методы взаимного эквивалентного 
преобразования автоматов. Даны примеры синтеза структурных автоматов 
на базе RS-, D-, Т- и JK-триггеров. Представлены общие сведения о микропрограммном управлении, методы разметки граф-схем микропрограмм 
и правила построения по ним автоматов Мили и Мура. Рассмотрены методы 
канонического синтеза структурных управляющих автоматов с жесткой 
и программируемой логикой, а также структурная организация и принципы 
синтеза операционных автоматов. Может использоваться для самостоятельного внеаудиторного изучения дисциплины. 
Предназначено для студентов, обучающихся по направлению «Информатика и вычислительная техника». 
 
Электронный вариант издания см.: 
УДК 519.713(07) 
http://catalog.sfu-kras.ru 
ББК 22.181.3я73 
 
 
 
 
ISBN 978-5-7638-3661-5 
© Сибирский федеральный 
университет, 2017 

Введение 

3 

ВВЕДЕНИЕ 
 
 
Переход от индустриального общества на принципиально новый 
уровень общественного и экономического развития к информационному 
обществу и информационной экономике, которые в передовых странах 
уже получили определенное развитие, – историческая необходимость. 
В отличие от индустриального общества, материальной базой которого являются материальные, природные, трудовые, финансовые и энергетические ресурсы, в информационной экономике акцент смещается на информационный ресурс, представляющий собой знания, накопленные людьми 
для социального использования в обществе. 
Перевод экономики на принципиально иные основы предполагает не 
совершенствование технологии на отдельных участках экономической 
системы, а представление информатизации как процесса преобразования 
хозяйственных, научных и социально-бытовых структур путем производства информации, необходимой для выработки и реализации решений, направленных на достижение качественно новых результатов деятельности 
человека, на базе внедрения и использования средств вычислительной техники, связи и информационных технологий. 
Основная роль в современной инфраструктуре информатизации принадлежит вычислительным сетям и системам коммуникаций, в которых 
сосредоточены новейшие средства вычислительной техники, информатики, связи, а также самые прогрессивные информационные технологии. Таким образом, решающим фактором ускорения научно-технического прогресса и развития всех отраслей экономики страны является процесс информатизации экономики, который полностью зависит от уровня 
внедрения вычислительной техники. 
Теория автоматов – сравнительно молодая наука. Началом ее возникновения считается середина 1950-х гг. За 60 лет своего существования 
теория автоматов превратилась в самостоятельную дисциплину с широким 
кругом собственных проблем и методов и многочисленными связями 
с другими дисциплинами информатики и вычислительной техники. Как 
оказалось, идея дискретного преобразователя с конечной памятью – идея 
конечного цифрового автомата – находит применение в целом ряде дисциплин: математической логике и теории алгоритмов, алгебре, теории вероятностей, кибернетике, математическом программировании, теории графов 
и теории формальных языков. 
Прикладная теория цифровых автоматов – раздел теории автоматов, в котором рассматриваются прикладные вопросы анализа и синтеза 
логических функциональных схем вычислительной техники. В этом случае 

Введение 

4 

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

1. Основы алгебры логики и формы представления её функций 

5 

1. 
ОСНОВЫ АЛГЕБРЫ ЛОГИКИ  
И ФОРМЫ ПРЕДСТАВЛЕНИЯ ЕЁ ФУНКЦИЙ 
 
 
Аппарат алгебры логики (алгебры Буля, булевой алгебры), созданный в XIX в. английским математиком Дж. Булем, применяется для формального описания цифровых автоматов. 
 
 
1.1. Основные понятия 
 
Основным понятием алгебры логики является высказывание [10]. 
Высказывание – предложение, о котором можно утверждать, что оно 
истинно или ложно. 
Любое высказывание можно обозначить символом х и считать, что 
х = 1, если высказывание истинно, а х = 0, если высказывание ложно. 
Логическая (булева) переменная – такая величина х, которая может 
принимать только два значения (0 или 1). 
Высказывание абсолютно истинно, если соответствующая ей логическая величина принимает значение х = 1 при любых условиях. 
Высказывание абсолютно ложно, если соответствующая ей логическая величина принимает значение х = 0 при любых условиях. 
Логическая функция (функция алгебры логики, ФАЛ) – функция 
f (x1, x2, ..., xn), принимающая значение, равное 0 или 1 на наборе логических переменных x1, x2, ..., xn. 
Логические функции от одной переменной представлены в табл. 1.1. 
 
Таблица 1.1 
 
x 
f1(x) 
f2(x) 
f3(x) 
f4(x) 

0 
1 
0 
0 
1 

1 
1 
0 
1 
0 

 
Функция f1 (x) является абсолютно истинной (константа единицы); 
функция f2 (x) – абсолютно ложная (константа нуля). 
Функция f3 (x) – тождественная функция, а функция f4 (x) называется 
функцией логического отрицания (функция НЕ, функция инверсии). Математически функция логического отрицания описывается следующим 
образом: 

x
x
x
f



)
(
4
. 

Прикладная теория цифровых автоматов 

6 

В табл. 1.2 приведены 5 наиболее часто употребляемых на практике 
логических функций от двух переменных из 16 возможных. 
 
Таблица 1.2 
 
x1 x2 
f1(x1, x2) 
f2(x1, x2) 
f3(x1, x2) 
f4(x1, x2) 
f5(x1, x2) 

0 0 
0 1 
1 0 
1 1 

0 
1 
1 
1 

0 
0 
0 
1 

1 
1 
1 
0 

1 
0 
0 
0 

0 
1 
1 
0 

 
Функция f1(x1, x2), называемая функцией дизъюнкции (функция логического сложения, функция ИЛИ), истинна тогда, когда истинны или х1, 
или х2, или обе переменные. Алгебраическое обозначение функции: 
 
f1 (x1, x2) = х1 + х2 = х1  x2. 
 
Функция f2 (x1, x2) – функция конъюнкции (функция логического умножения, функция И), истинна только тогда, когда истинны х1 и х2. Алгебраическое обозначение функции: 
 
f2 (x1, x2) = x1 x2 = x1 x2 = x1  x2 = x1 & x2. 
 
Функция f3(x1, x2) называется «штрих Шеффера» (функция Шеффера). Эта функция ложна только тогда, когда х1 и х2 истинны. Алгебраическое обозначение функции: 
 
f3 (x1, x2) = х1 | х2. 
 
Если сравнить функции f2 (x1, x2) и f3 (x1, x2) (см. табл. 1.2), то видно, 
что функция Шеффера является инверсией функции И. Следовательно, 
функцию Шеффера можно еще назвать функцией И-НЕ. Алгебраическое 
обозначение можно записать так: 
 
f3 (x1, x2) = х1 | х2 =
2
1x
x
. 

 
Функция f4 (x1, x2) называется «стрелка Пирса» (функция Пирса, 
функция Вебба). Эта функция истинна только тогда, когда х1 и х2 ложны. 
Алгебраическое обозначение функции: 
 
f4 (x1, x2) = x1 ↓ x2 = x1 ○ x2. 
 
Если сравнить функции f1 (x1, x2) и f4 (x1, x2), то видно, что функция 
Пирса является инверсией функции ИЛИ. Следовательно, функцию Пирса 
можно еще назвать функцией ИЛИ-НЕ. Алгебраическое обозначение 
функции можно записать так: 

1. Основы алгебры логики и формы представления её функций 

7 

f4 (x1, x2) =
2
1
x
x 
. 

 
Функция f5 (x1, x2) называется функцией сложения по модулю 2 
(функция неравнозначности, функция разноименности, функция ИСКЛЮЧАЮЩЕЕ ИЛИ). Функция истинна, когда истинны или х1, или х2 в отдельности. Алгебраическое обозначение этой функции: 
 
f5 (x1, x2) = х1  х2. 
 
Функции импликации, эквивалентности и другие [4] в данном пособии не рассматриваются. 
 
 
1.2. Аксиомы и свойства алгебры логики 
 
Используя основные положения алгебры логики, подставляя вместо 
булевой переменной х ее возможные значения, нетрудно убедиться в справедливости следующих аксиом: 

1. x
x

 – закон исключения двойного отрицания.  
2. х + 0 = х, 
х + 1 = 1, 
х + х = х, 
х + x  = 1. 
3. х  0 = 0, 
х  1 = х, 
х  х = х, 
х  x  = 0. 
4. х  0 = х, 
х  1 = x , 
х  х = 0, 
х  x  = 1. 
Дизъюнкция, конъюнкция и функция сложения по модулю 2 обладают рядом свойств, аналогичных свойствам обычных арифметических 
операций сложения и умножения [6]. 
1. Свойство ассоциативности (сочетательный закон): 
 
х1 + (х2 + х3) = (х1 + х2) + х3, 
 
х1  (х2  х3) = (х1  х2)  х3, 
 
х1  (х2  х3) = (х1  х2)  х3. 
 

Прикладная теория цифровых автоматов 

8 

2. Свойство коммутативности (переместительный закон): 
 
х1 + х2 = х2 + х1, 
 
х1  х2 = х2  х1, 
 
х1  х2 = х2  х1. 
 
3. Свойство дистрибутивности (распределительный закон): 
 
х1 (х2 + х3) = х1 х2 + х1 х3, 
 
х1 + х2 х3 = (х1 + х2)(х1 + х3), 
 
x1· (x2  x3) = x1·x2  x1·x3. 
 
Правила и законы: 
 правила «склеивания»: 
 
х1 х2 + х1
2
x  = х1; 

 
 
(х1 + х2)(х1 +
2
x ) = х1; 
(1.1) 

 
 законы де Мόргана, с помощью которых можно выразить конъюнкцию через дизъюнкцию и отрицание или дизъюнкцию через конъюнкцию и отрицание: 
 

.

,

2
1
2
1

2
1
2
1
x
x
x
x

x
x
x
x









 
 
Следствия из законов де Моргана: 
 

 
.

,

2
1
2
1

2
1
2
1

x
x
x
x

x
x
x
x








 
(1.2) 

 
Законы де Моргана справедливы для любого числа переменных; 
 законы поглощения: 
 
х1 + (х1  х2) = х1, 
 
х1 (х1 + х2) = х1; 
 
 законы обобщенного поглощения: 
 
х1 х2 + 1x  х3 + х2 х3 = х1 х2 + 1x  х3; 

 
(х1 + х2)( 1x + х3)(х2 + х3) = (х1 + х2)( 1x + х3). 

1. Основы алгебры логики и формы представления её функций 

9 

Порядок выполнения логических операций: 
1. Инверсия отдельных переменных. 
2. Операции в скобках и операции со знаком отрицания. 
3. Конъюнкция. 
4. Дизъюнкция. 
Кроме алгебры Буля, включающей три операции – отрицание, конъюнкцию и дизъюнкцию, существует алгебра Жегалкина, использующая 
две операции – конъюнкцию и сложение по модулю 2. 
 
 
1.3. Табличное и аналитическое представление  
функций алгебры логики 
 
В табличном способе задания функций алгебры логики функция задается в виде таблицы, в которой для каждого набора значений переменных указывается значение самой логической функции. Табличный способ 
задания ФАЛ от трех переменных отражён в табл. 1.3. 
 
Таблица 1.3 
 
x1 
x2 
x3 
f (x1, x2, x3) 

0 
0 
0 
0 
1 
1 
1 
1 

0 
0 
1 
1 
0 
0 
1 
1 

0 
1 
0 
1 
0 
1 
0 
1 

1 
1 
0 
1 
0 
0 
1 
1 

 
Этот способ показателен и может быть применен для записи ФАЛ от 
любого числа переменных. Однако при задании ФАЛ от большого числа 
переменных таблицы получаются слишком большие, так как число строк 
в такой таблице составляет 2n, где n – число переменных. 
При аналитической форме записи ФАЛ задается в виде объединения термов. Различают два вида термов – дизъюнктивные термы (макстермы) и конъюнктивные термы (минтермы). 
Макстерм – терм, связывающий все переменные, представленные 
в прямой и инверсной форме, знаком дизъюнкции, например: 
 
Ф = 1x + х2 + х3.