Автор Л.П. Бойченко Методические указания для выполнения заданий по теме "Основы работы двоичных автоматов" в рамках изучения дисциплины "Информатика"

ДЕПАРТАМЕНТ ОБРАЗОВАНИЯ ГОРОДА МОСКВЫ

Государственное бюджетное профессиональное образовательное учреждение

ПИЩЕВОЙ КОЛЛЕДЖ № 33

Методические указания

для выполнения заданий по теме

 «Основы работы двоичных автоматов»

в рамках изучения дисциплины «Информатика»

Москва, 2016

Автор-составитель - Л. П. Бойченко

Данные методические указания подготовлены для выполнения заданий по теме «Основы работы двоичных автоматов» в рамках изучения дисциплины «Информатика».

Они могут быть использованы также при изучении курсов «Информатика и ИКТ»,  «Компьютерные сети», «Компьютерные технологии», «Системы управления базами данных», «Информационные технологии в профессиональной деятельности», «Электроника».

Полезно использовать для студентов СПО, обучающихся в колледжах.

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

Оглавление

Введение......................................................................................................................................... 4

Глава 1. Основы теории двоичных функций.............................................................................. 5

1.1. Двоичные переменные и функции……………………………………………………5

1.2. Двоичные функции одного и двух двоичных аргументов......................................... 7

1.3. Основная функционально полная система двоичных
функций (ОФПС)……………………………………………………………………..9

1.4. Элементы алгебры логики............................................................................................. 9

1.5. Представление двоичной функции формулой........................................................... 13

1.5.1. Конституенты единицы и нуля....................................................................... 13

1.5.2. Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы...................................................................................................................................... 15

1.5.3. Переход от формульного задания функции
к табличному............................................................................................................... 16

1.5.4. Примеры............................................................................................................ 20

Глава 2. Дискретные автоматы.................................................................................................. 25

2.1. Основные понятия........................................................................................................ 25

2.2. Анализ автоматов без памяти...................................................................................... 27

2.3. Синтез автоматов без памяти...................................................................................... 36

Библиографический список........................................................................................................ 40

Введение

В данных методических указаниях  рассматривается материал по теме «Основы работы двоичных автоматов». Учебный материал включает в себя две главы по изучаемой  теме.

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

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

Изложенный материал может быть полезным студентам при усвоении материала, связанного с основами преобразования информации в компьютере.

Глава 1. Основы теории двоичных функций

1.1. Двоичные переменные и функции

Пусть  – переменные, каждая из которых может принимать лишь два значения. Будем кодировать значения переменных буквами двоичного алфавита 0 и 1.

Тогда  называют двоичными переменными, а функцию  – двоичной функцией n двоичных аргументов. Функция у также может принимать значение только 0 и 1 при любом наборе значений двоичных аргументов.

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

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

В качестве примера в табл. 1.1 приведены все возможные наборы трёх двоичных переменных. Так как , то число наборов будет .

При построении таких таблиц наборов переменных удобно аргументы

 рассматривать как разряды двоичного кода числа и располагать в таблице в порядке возрастания числа от 0 до  (табл. 1.1).

Таблица 1.1

№ набора	х1,	х 2	х 3	Двоичный код числа	Десятичный код числа
0	0	0	0	0	0
1	0	0	1	1	1
2	0	1	0	10	2
3	0	1	1	11	3
4	1	0	0	100	4
5	1	0	1	101	5
6	1	1	0	110	6
7	1	1	1	111	7

1.2. Двоичные функции одного и двух двоичных аргументов

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

Функция одного аргумента  представлена в табл. 1.2.

Таблица 1.2

x	y0	y1	y2	y3
0	0	0	1	1
1	0	1	0	1

Для удобства записи функции целесообразно представлять в порядке возрастания индекса. При этом индекс i при функции  соответствует двоичному коду числа, записанного в i-м столбце. Например, функции  соответствует двоичный код числа 2, то есть 10.

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

Функция  принимает значение её аргумента , записывается и называется тавтологией.

Функция  принимает значение, противоположное её аргументу, и называется инверсией, она записывается так: , и произносится:  тождественно не  или просто  не .

Операция отыскания функции  называется операцией отрицания, а автомат, её реализующий, – автоматом НЕ.

Функция  принимает значение 1 при любом значении аргумента, то есть , и называется константой единица.

Следует иметь в виду, что знак «=» во всех случаях произносится не равно, а «тождественно» или «есть».

Рассмотрим теперь двоичные функции двух двоичных аргументов  . В данном случае число аргументов , поэтому число возможных наборов аргументов будет , а число функций . Значения функции приведены в табл. 1.3.

Таблица 1.3

x1	x2	y0	y1	y2	y3	y4	y5	y6	y7
0	0	0	0	0	0	0	0	0	0
0	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1
x1	x2	y8	y9	y10	y11	y12	y13	y14	y15
0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1

Представим некоторые из функций табл. 1.3 формулами. Аналогично функции одного аргумента  можно записать:

.

Функции и  есть, соответственно, константы нуль и единица, функции  и  – тавтология  и тавтология  , функции  и  – инверсии, соответственно,  и .

Функция принимает единичное значение только тогда, когда оба аргумента принимают единичное значение. Такая функция называется конъюнкцией, операция по её отысканию называется логическим сложением, а автомат, её реализующий, – автоматом И. Эта функция записывается в одной из форм:

                                                                            (1.1)

Читается у тождественно (есть)   и . Конъюнкция может быть функцией любого числа двоичных аргументов, то есть

                                                                                        (1.2)

Здесь у принимает единичное значение только тогда, когда все аргументы принимают единичное значение.

Если  – некоторые простые события, каждое из которых может совершиться (1) и не совершиться (0), а  – сложное событие, то выражение (1.2) означает: сложное событие  произойдёт только в том случае, если совершатся все простые события  .

Функция y₇ принимает единичное значение тогда, когда хотя бы один из аргументов ,  принимает единичное значение. Такая функция называется дизъюнкцией, а соответствующая операция называется операцией логическое сложение, а автомат – автоматом ИЛИ.

Эта функция записывается в одной из форм:

                                                                                    (1.3)

Дизъюнкция может быть функцией любого числа аргументов. Тогда

                                                          (1.4)

y₇ в данном случае принимает единичное значение тогда, когда хотя бы один из аргументов принимает единичное значение.

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

1.3. Основная функционально полная система двоичных функций (ОФПС)

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

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

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

1.4. Элементы алгебры логики

Над логическими функциями и выражениями можно совершать действия в соответствии с правилами алгебры логики (Булевой алгебры).

Непосредственно из определения конъюнкции, дизъюнкции и инверсии вытекают следующие соотношения:

Для конъюнкции и дизъюнкции справедливы следующие законы:

а) переместительный  (коммутативный):

                                                                                                    (1.5)

                                                                                                    (1.6)

б) сочетательный (ассоциативный):

                                                      (1.7)

                              (1.8)

в) первый распределительный:

                              (1.9)

г) второй распределительный:

                              (1.10)

Из второго распределительного закона вытекают следующие полезные для практического использования соотношения:

                             (1.11)

                             (1.12)

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

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

Например, если, то на основании теоремы

Из теоремы де Моргана вытекают следующие важные соотношения:

                              (1.13)

                              (1.14)

В алгебре логики существуют различные приёмы преобразования формул с целью их упрощения. Наиболее часто используются приёмы: вынос за скобки, склеивание и поглощение.

Преобразование, называемое выносом за скобки, внешне ничем не отличается от выноса за скобки общего члена в алгебре:

        (1.15)

Операция склеивания состоит в преобразовании вида

                                      (1.16)

Справедливость (3.16) легко доказать. Вынесем за скобки двоичную переменную , тогда получим:

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

                                      (1.17)

Доказательство (1.17) очевидно.

Преобразования, вынос за скобки, склеивание и поглощение, если исходные выражения представлены в виде конъюнкций:

 – вынос за скобки:

                                      (1.18)

– склеивание:

                                     (1.19)

– поглощение:

                                      (1.20)

Выражения (1.18), (1.19), (1.20) легко доказать, если раскрыть скобки и использовать соотношения (1.4) – (1.10).

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

Задание 1.1. Минимизировать функции, приведённые в табл. 1.4.

Таблица 1.4

№ вар.	Функция	Ответ
1
2
3	(
4
5
6
7
8
9
10
Оконч. табл. 1.4
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

Рассмотрим пример, типичный для задания 1.1.

Пусть необходимо упростить функцию

.

Первоначально преобразуем первый и третий конъюнктивные члены по теореме де Моргана. Получим:

.

Раскроем теперь скобки:

.

Так как , то  тогда

.

1.5. Представление двоичной функции формулой

1.5.1. Конституенты единицы и нуля

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

В табл. 1.5 приведены конституенты единицы функции двоичных
аргументов:

Таблица 1.5

х1	х 2	с00	с 11	с 21	с 31
0	0	1	0	0	0
0	1	0	1	0	0
1	0	0	0	1	0
1	1	0	0	0	1

В таблице обозначено  – конституента единицы на i-м наборе аргументов.

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

                                      (1.21)

В правильности формул можно убедиться подстановкой в них аргументов табл. 3.5 на всех наборах. В качестве примера рассмотрим конституенту единицы . Так как при , то на наборах 00 и 10 конституента. Она также равна нулю на наборе 11, так как при , . Только при одном наборе 01 .

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

В табл. 1.6 приведены все конституенты нуля функции двух двоичных
аргументов:

Таблица 1.6

х1	х 2	с00	с10	с20	с30
0	0	0	1	1	1
0	1	1	0	1	1
1	0	1	1	0	1
1	1	1	1	1	0

В таблице  – конституента нуля на i-м наборе аргументов.

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

                              (1.22)

В правильности формул можно убедиться подстановкой в них аргументов табл. 1.6 на всех наборах.

1.5.2 Совершенная дизъюнктивная и совершенная
конъюнктивная нормальные формы

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

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

СДНФ и СКНФ позволяют представить двоичную функцию любого числа аргументов, заданную таблично, формулой. Из определения СДНФ вытекает, что для представления функции формулой достаточно образовать СДНФ, для чего необходимо:

а) записать в виде формул все конституенты единицы для тех наборов аргументов, на которых функция принимает единичное значение;

б) образовать дизъюнкцию конституенты единицы.

Рассмотрим пример.

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

Таблица 1.7

х1	х2	х3	y
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	1

Из табл. 1.7 видно, что функция принимает единичное значение на тр`х наборах аргументов: 010, 101, 111. Тогда конституенты единицы, соответствующие этим наборам, будут:

.

Получим СДНФ, образуя дизъюнкцию конституент единицы:

.

Для представления двоичной функции формулой с помощью СКНФ необходимо:

– записать в виде формул все конституенты нуля для тех наборов аргументов, на которых функция принимает нулевое значение;

– образовать конъюнкцию конституент нуля.

В качестве примера представим функцию , данную табл. 1.7, формулой с помощью СКНФ. Из таблицы видно, что функция принимает нулевое значение на пяти наборах аргументов: 000, 001, 011, 100, 110. Тогда конституенты нуля, соответствующие указанным наборам, будут:

Получим СКНФ функции:

.

1.5.3. Переход от формульного задания функции к табличному

Возможны два способа перехода от формульного задания функции к табличному:

а) путём непосредственного определения значения функции на каждом наборе аргументов;

б) путём формального определения СДНФ или СКНФ.

При непосредственном определении значения функции используются соотношения (3.4) и понятия дизъюнкции, конъюнкции и инверсии. В качестве примера представим таблицей функцию

При наборе аргументов

При наборе  

Функция представлена в табл. 1.8:

Таблица 1.8

х1	х2	х3	y
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	1

Из табл. 1.8 следуют СДНФ и СКНФ:

.

.

При табличном значении функции путём определения СДНФ используется следующий приём. Каждый дизъюнктивный член логически умножается на, где  – недостающий аргумент. Затем раскрываются скобки, а дизъюнктивные члены группируются в порядке возрастания наборов аргументов. Образованная таким образом СДНФ позволяет представить функцию в виде таблицы. Рассмотрим пример. Пусть необходимо представить таблицей функцию . Так как в первом члене не достаёт аргументов а во втором – , то

.

Так как  , то окончательно СДНФ будет иметь вид:

Тогда функция будет принимать единичное значение на пяти наборах двоичных аргументов: 111, 110, 101, 100, 010. Функция представлена табл. 1.9:

Таблица 1.9

х1	х2	х3	y
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	1

Задание 1.2. Функции трёх двоичных аргументов  заданы в табл. 3.10. Необходимо функции представить формулой в виде СДНФ и СКНФ.

Таблица 1.10

х1	х2	х3	y1	y2	y3	y4	y5	y6	y7	y8	y9	y10	y11	y12	y13
0	0	0	0	0	1	0	1	0	0	0	1	0	0	0	1
0	0	1	1	0	0	1	0	1	0	0	1	1	0	0	0
0	1	0	0	1	1	0	1	1	0	1	0	1	1	0	1
0	1	1	1	1	0	1	0	0	1	1	0	1	1	1	1
1	0	0	1	0	1	0	1	1	1	0	1	0	1	1	0
1	0	1	0	1	0	1	1	0	0	1	0	0	0	1	0
1	1	0	1	0	0	0	0	0	1	1	1	0	1	0	0
1	1	1	0	1	1	1	0	1	1	0	0	1	0	1	1

Оконч. табл. 1.10

y14	y15	y16	y17	y18	y19	y20	y21	y22	y23	y24	y25	y26	y27	y28	y29	y30
0	1	0	0	1	1	0	1	1	0	0	1	0	0	1	0	1
1	0	0	1	0	0	1	0	0	0	1	1	0	1	1	1	0
0	0	1	0	1	1	1	0	0	1	1	1	0	0	1	0	0
1	0	0	1	0	0	0	1	0	1	0	0	1	1	0	1	1
1	0	1	0	0	1	0	1	1	1	0	0	1	0	1	1	1
1	1	0	1	1	0	1	0	1	0	1	1	1	1	0	0	0
0	1	1	1	0	0	1	0	1	0	0	0	0	1	0	1	0
0	1	1	0	1	1	0	1	0	1	1	0	1	0	0	0	1

Задание 1.3. Функция  задана в виде формулы. Необходимо представить функцию в виде таблицы и найти СДНФ и СКНФ.

.

2.      .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

1.5.4. Примеры

Пример 1.1. Функция  задана табл. 1.11. Необходимо её представить с помощью СДНФ и СКHФ, а затем найти минимальную форму.

Таблица 1.11

х1	х2	х3	y
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	1

Функция принимает единичное значение на четырёх наборах аргументов 010, 011, 110, 111. Тогда конституентами единицы, соответствующими данным наборам, будут:,  а СДНФ запишется в следующем виде:

.

Функция принимает нулевые значения на наборах аргументов 000, 001, 100, 101. Тогда конституентами нуля будут: а СКНФ запишется в виде:

.

Теперь минимизируем функцию, записанную в виде СДНФ:

.

Сгруппируем конституенты  и вынесем за скобки общие члены. Тогда получим:

.

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

Пример 1.2. Двоичная функция трёх двоичных аргументов задана формулой

.

Необходимо представить функцию таблицей и записать СДНФ.

Из формулы видно, что если . Функция приобретает нулевое значение также, если . Она примет нулевое значение также при наборе аргументов   , так как на этом наборе тождественно 0. При наборе аргументов и  функция принимает единичное значение.

Действительно:

Функция представлена табл. 1.12:

Таблица 1.12

х1	х2	х3	y
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	0
1	1	1	1

Из таблицы видно, что функция имеет единичное значение на наборах 011 и 111, конституенты единицы на этих наборах будут  и . Тогда СДНФ функции запишется в виде

.

Пример 1.3. Двоичная функция трёх аргументов задана формулой

.

Необходимо представить функцию в виде СДНФ и в табличной форме. На основании теоремы де Моргана . Тогда  Домножим первый дизъюнктивный член на, а второй – на  и раскроем скобки

Так как СДНФ содержит четыре конституенты единицы, то функция принимает единичное значение также на следующих четырёх наборах: 110, 101, 100, 001. Данная функция представлена в виде табл. 1.13:

Таблица 1.13

х1	х2	х3	y
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	0

Глава 2. Дискретные автоматы

2.1. Основные понятия

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

Автоматы делятся на два класса: непрерывного действия и дискретного действия.

В автоматах непрерывного действия для предоставления и преобразования информации используются сигналы, непрерывные по уровню. В дискретных автоматах носителями информации являются сигналы, дискретные по уровню. Для дискретных автоматов важным является не величина сигналов-носителей информации, а их наличие или отсутствие, которые кодируются с помощью алфавита, состоящего из двух букв (цифр) – нуля и единицы. Так как состояние дискретного автомата может быть описано совокупностью нулей и единиц, то для описания функционирования автомата используются двоичные функции двоичных аргументов. Математическим аппаратом теории дискретных автоматов является алгебра логики, или Булева алгебра (по имени английского математика середины XIX века Джорджа Буля).

Дискретные автоматы делятся на синхронные и асинхронные.

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

Асинхронным называется такой автомат, у которого изменения состояния происходят не в фиксированные моменты времени. Такой автомат не имеет синхронизатора.

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

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

В автоматах с памятью значения выходных переменных в данный момент времени зависят от значений переменных в данный момент и в предшествующие моменты времени.

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

Любой дискретный автомат состоит из простых (элементарных) автоматов, между которыми существуют определённые связи. Состав простых автоматов и вид связей между ними определяют структуру автомата.

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

Рассмотрим элементарные автоматы без памяти, реализующие функции ОФПС.

Автомат, реализующий функцию «дизъюнкция», называют схемой ИЛИ, или собирательной схемой. Такая схема на два входа изображена на рис. 2.1. Автомат, реализующий функцию «конъюнкция», называется схемой И, или схемой совпадения. Такой автомат на два входа изображен на рис. 2.2.

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

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

Рис. 2.1

Рис. 2.2

Рис. 2.3

2.2. Анализ автоматов без памяти

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

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

Анализ автомата выполняется в такой последовательности:

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

2) решение системы логических уравнений и получение зависимости  где – двоичные аргументы, представляющие собой входные переменные анализируемого автомата;  – выходная функция, реализуемая автоматом;

3) преобразование выходной функции в СДНФ или СКНФ;

4) составление таблицы функции  

Рассмотрим методику анализа автомата на примере.

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

Рис. 2.4

Будем анализировать автомат в последовательности, изложенной выше.

1.      Введём новые переменные  и обозначим их на структурной схеме. Тогда система логических уравнений, составленных для всех выходов, будет иметь вид:

 

 

 

 

 

2.      Получим зависимость  методом подстановки:

3.      Преобразуем функцию в СДНФ:

 

4.      Представим искомую функцию в виде таблицы.

Из выражения функции в виде СДНФ видно, что она принимает значение единицы на следующих наборах аргументов: 110, 100, 010, то есть конституентами единицы являются  Искомая функция представлена в табл. 2.1:

Таблица 2.1

х1	х2	х3	y
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	0

 

Рис. 2.5

Из выражения для искомой функции видно, что она может быть упрощена.

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

Задание 2.1. Провести анализ автомата без памяти, для чего необходимо:

а) определить функцию, реализуемую автоматом в виде формулы;

б) представить функцию в виде таблицы;

в) упростить структуру автомата, если это возможно.

Варианты структурных схем приведены ниже.

Варианты 1, 2, 3. Структурная схема изображена на рис. 2.6. Элементарные автоматы А₁, А₂, А₃, для каждого из вариантов приведены в табл. 4.2:

Таблица 2.2

№ варианта	Автоматы
	А1	А2	А3
1	ИЛИ	И	ИЛИ
2	ИЛИ	И	И
3	И	ИЛИ	ИЛИ

Таблица 2.3

№ варианта	Автоматы
	А1	А2	А3
4	ИЛИ	ИЛИ	И
5	ИЛИ	И	И
6	И	ИЛИ	ИЛИ
7	И	И	ИЛИ

Рис. 4.6

 

Рис. 2.7

Варианты 4-7. Структурная схема автомата изображена на рис. 4.7, а элементарные автоматы А₁, А₂, А₃ для каждого из вариантов приведены в табл. 2.3.

Варианты 8-11. Структурная схема автомата изображена на рис. 2.8, а элементарные автоматы А₁, А₂, А₃ для каждого из вариантов приведены в табл. 2.4:

Рис. 4.8

Таблица 2.4

№ варианта	Автоматы
	А1	А2	А3
8	ИЛИ	И	ИЛИ
9	И	ИЛИ	ИЛИ
10	И	ИЛИ	И
11	И	И	И

Таблица 2.5

№ варианта	Автоматы
	А1	А2	А3
12	ИЛИ	ИЛИ	ИЛИ
13	ИЛИ	ИЛИ	И
14	ИЛИ	И	ИЛИ
15	И	ИЛИ	И
16	И	И	ИЛИ
17	И	И	И

Рис. 4.9

Варианты 12-17. Структурная схема автомата изображена на рис. 2.9, а элементарные автоматы А₁, А₂, А₃ для каждого из вариантов приведены в табл. 2.5.

Варианты 18-21. Структурная схема автомата изображена на рис. 2.10, а элементарные автоматы А₁, А₂, А₃ для каждого из вариантов приведены в табл. 2.6:

Таблица 2.6

№ варианта	Автоматы
	А1	А2	А3
18	ИЛИ	ИЛИ	ИЛИ
19	ИЛИ	ИЛИ	И
20	И	И	ИЛИ
21	И	И	И

Таблица 2.7

№ варианта	Автоматы
	А1	А2	А3
22	ИЛИ	ИЛИ	ИЛИ
23	ИЛИ	ИЛИ	И
24	И	ИЛИ	ИЛИ
25	И	И	ИЛИ
26	И	И	И

Рис. 4.10

 

Рис. 4.11

Варианты 22-26. Структурная схема автомата изображена на рис. 2.11, а элементарные автоматы А₁, А₂, А₃ каждого из вариантов приведены в табл. 2.7.

Варианты 27-30. Структурная схема автомата изображена на рис. 2.12, а элементарные автоматы А₁, А₂, А₃ для каждого из вариантов приведены в табл. 2.8:

Таблица 2.8

№ варианта	Автоматы
	А1	А2	А3
27	ИЛИ	ИЛИ	ИЛИ
28	ИЛИ	И	ИЛИ
29	ИЛИ	И	И
30	И	ИЛИ	ИЛИ

Рис. 4.12

2.3. Синтез автоматов без памяти

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

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

Нужно иметь в виду, что при решении задачи синтеза набор элементарных автоматов должен образовать функционально полную систему двоичных функций.

Оператор, реализуемый автоматом без памяти, называет истинностным оператором. Он может быть задан в виде таблицы, которая называется таблицей истинности, или в виде формулы. Этапами синтеза автоматов без памяти являются:

1)      составление таблицы истинности по содержательному описанию функционирования автомата;

2)      описание оператора формулой в виде СДНФ или СКНФ;

3)минимизация формулы с учётом заданного набора функций алгебры логики, реализуемых заданными элементарными автоматами;

4)      составление структурной схемы автомата.

Усвоить и понять методику синтеза легко на примере.

Необходимо построить автомат на элементах И, ИЛИ, НЕ, позволяющий определить знак произведения двух чисел. Элемент И, ИЛИ на два входа.

1. Обозначим  – знаки первого и второго числа соответственно, а у – знак произведения. Положительное число будем кодировать нулём, а отрицательное – единицей. Тогда реализуемым автоматом оператор представим в виде таблицы истинности (табл. 2.9).

Таблица 2.9

х1	х2	y
0	0	0
0	1	1
1	0	1
1	1	0

2. Двоичная функция принимает единичное значение на наборах 01, 10, тогда функция может быть представлена в виде СДНФ, в дизъюнктивные члены которой входят две конституенты:

.

3. Упрощение полученной СДНФ известными нам способами невозможно, поэтому функция у является минимальной формой.

4. Из выражения для СДНФ видно, что автомат должен состоять из двух
автоматов НЕ, одного автомата ИЛИ на два входа и двух автоматов И, каждый из которых на два входа. Структурная схема автомата представлена на рис. 2.13.

Задание 4.2. Построить автомат на элементах И, ИЛИ, НЕ, если задан оператор в виде формулы или таблицы истинности.

Варианты 1-15. Функция задана в виде табл. 4.10. Необходимо записать функцию в виде СДНФ и построить минимальный автомат на элементах И, ИЛИ, НЕ. Автоматы И, ИЛИ на два входа. Индекс при у означает номер варианта.

 

Рис. 2.13

Таблица 2.10

х1	х2	х3	y1	y2	y3	y4	y5	y6	y7	y8	y9	y10	y11	y12	y13	y14	y15
0	0	0	0	0	0	0	1	1	1	1	1	1	1	0	1	0	1
0	0	1	0	0	1	1	1	0	1	0	1	1	1	0	I	0	0
0	1	0	1	1	0	0	1	1	0	1	1	1	1	1	0	1	1
0	1	1	1	1	1	0	1	0	0	1	1	0	0	1	0	1	1
1	0	0	0	0	0	0	0	1	0	1	1	1	1	0	1	1	0
1	0	1	0	0	0	1	0	1	0	1	1	1	0	1	0	0	0
1	1	0	0	1	0	0	1	1	1	1	0	1	1	0	0	1	1
1	1	1	1	0	1	1	1	1	1	1	1	0	1	0	1	0	1

Варианты 16-30. Функция задана в виде формулы (табл. 2.11). Необходимо представить функцию в виде СДНФ и построить минимальный автомат на элементах И, ИЛИ, НЕ. Элементы И, ИЛИ на два входа.

Таблица 2.11

№ варианта	Функция y
16
17	(
18
19
20
21
22
23
24
25
26
27
28
29
30	)

Библиографический список

1.            Берлинер, Э. М. Офис от Microsoft: Начинающему пользователю о работе с Windows 95. Microsoft Office 97 [Текст] / Э. М. Берлинер, Б. Э. Глазырин, И. Б. Глазырина. – М.: ABF, 1997. – 752 c.

2.            Якушина, Е. В. Internet для школьников и начинающих пользователь [Текст] / Е. В. Якушина. – М.: Аквариум, 1997. – 256 с.

3.            Фигурнов, В. Э. IBM PC для пользователя: краткий курс [Текст] / В. Э. Фигурнов. – М.: Инфра-М, 1997. – 480 с.

4.            Макарова, Н. В. Информатика [Текст] : учебник / под ред. Н. В. Макаровой. – 4-е изд., перераб. – М.: Финансы и статистика, 2004. – 768 c.: ил.

5.            Хауцкова, Л. З. Информатика 10-11 [Текст] / Л. З. Хауцкова. – М.: Просвещение, 2000. – 420 с.

6.            Пряшников, В. А. Электроника [Текст] : курс лекций / В. А. Пряшников. – СПб.: Корона принт, 1998. – 400 с.: ил.

7.            Хабловски, И. Электроника в вопросах и ответах [Текст]: пер. с польск. под ред. В. И. Котикова / И. Хабловски, В. Скулимовски. – М.: Радио и связь, 1984. – 304 с.: ил.

8.            Данилов, И. А. Общая электротехника с основами электроники [Текст] : учеб. пособие для студ. неэлектротехн. спец, средних спец. учеб. заведений. –
4-е изд., стереотип. / И. А. Данилов, П. М. Иванов. – М.: Высш. шк., 2000. – 752 с.: ил.

9.            Бобровников, Л. З. Радиотехника и электроника [Текст] : учеб. для вузов / Л. З. Бобровников. – 4-е изд., перераб. и доп. – М.: Недра, 1990. – 374 с.: ил.

10.        Морозов, А. Г. Электротехника, электроника и импульсная техника [Текст] : учеб. пособие для инженерно-эконом. спец. вузов / А. Г. Морозов. – М.: Высш. шк., 1987. – 448 c.: ил.

11.        Забродин, Ю. С. Промышленная электроника [Текст] : учебник для вузов / Ю. С. Забродин. – М.: Высш. шк., 1982. – 496 с.: ил.

12.        Гусев, В. Г. Электроника [Текст] : учеб. пособие для приборостроит. спец. вузов / В. Г. Гусев, Ю. М. Гусев. – 2-е изд., перераб. и доп. – М.: Высш. шк., 1991. – 622 c.: ил.

13.        Основы промышленной электроники [Текст] : учебник для вузов / под ред. В. Г. Герасимова / В. Г. Герасимов [и др.]. – 2-е изд., перераб. и доп. – М.: Высш. шк., 1978. – 336 с.: ил.

14.         Ягубов З. Х. Расчёт низкочастотного усилителя [Текст] : метод. указания / З. Х. Ягубов, И. А. Тарасенко. –  Ухта: УГТУ, 2001. – 38 с.: ил.

15.        Ягубов З.Х. Логические элементы [Текст]: учебное пособие /З.Х.Ягубов, Л.П. Бойченко, Т.А.Туманова. – Ухта: УГТУ, 2005. – 260 с.:ил.

16. Бойченко Л.П. Арифметические и логические элементы компьютеров и двоичных автоматов [Текст]: учебное пособие / Л.П. Бойченко, З.Х.Ягубов, Н.М. Выборова, Т.А. Туманова. – Ухта: УГТУ, 2011. – 100 с.:ил.