Файл: Дискретная математика_МУ_Реш.Задач.pdf

31 

2) представим выражение в виде полинома Жегалкина: 















C

A

C

B

A

B

A

C

A

B

A

B

A

f

















C

A

C

B

A

B

A

)

1

(

)

1

(

)

1

(

)

1

(



















AC

C

ABC

BC

AB

B

AB

A

.

AC

C

ABC

BC

B

A













Так как полином Жегалкина содержит конъюнкции, то функция яв-

ляется нелинейной. Ответ относительно линейности: 0; 

3)  функция  четырёх  переменных  может  быть  самодвойственной 

только в том случае, когда она состоит из 8 минтермов. В данном же слу-

чае число минтермов функции равно 10, следовательно, функция не явля-

ется самодвойственной. Ответ относительно самодвойственности: 0; 

4)  подставим  в  заданную  функцию  набор  0000.  Получим  f  =  0, 

т. е. функция  сохраняет  нуль.  Ответ  на  вопрос  о  сохранении  нуля:  1 

(т. е. «да»); 

5) подставим набор 11111. Получим f = 0, т. е. ответ на вопрос о со-

хранении единицы: 0. 

Ответ: 0, 0, 0, 1, 0.  

32 

ТЕМА 10. АВТОМАТЫ С ПАМЯТЬЮ 

Автоматы с памятью содержат запоминающие элементы – триггеры 

A

1

, A

2

, …,  A

n

. На входы триггеров информация поступает с выходов ком-

бинационных  схем,  а  на  входы  комбинационных  схем  сигналы  подаются 

как извне, так и с выходов триггеров A

1

, A

2

, …, A

n

. Таким образом, автомат 

с памятью представляет собой многотактную схему в виде сочетания ком-

бинационных  схем  с  элементами  памяти  в  виде  триггеров,  где  триггеры 

меняют свои состояния под действием прямоугольных импульсов тактово-

го генератора. 

В  общем  случае  прикладная  теория  автоматов  с  памятью  гораздо 

сложнее теории комбинационных схем. Однако в данном курсе дискретной 

математики рассматриваются простейшие многотактные схемы. Их назна-

чение  –  показать  принцип  работы  автоматов  с  памятью,  проиллюстриро-

вать способ их синтеза с применением таблицы переходов. 

В качестве зачётного задания требуется построить многотактный ав-

томат на трёх триггерах типа T и JK, реализующий только одну последова-

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

циклу.  Теоретическая  часть  этой  работы  состоит  в  нахождении  системы 

булевых  функций  для  реализации комбинационного преобразователя, вы-

ходы которого подключаются ко входам триггеров, а на входы преобразо-

вателя поступает информация с выходов тех же триггеров. Булевы функции, 

описывающие работу преобразователя, согласно [17], будем называть урав-

нениями входов. Эти уравнения представляют собой булеву модель синте-

зируемого  автомата.  Построение  булевой  модели  является  целью  работы 

над задачей по синтезу многотактного автомата (автомата с памятью). 

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

В соответствии с этим синтез автоматов проиллюстрируем на двух примерах. 

33 

Пример  1.  Построить  булеву  мо-

дель  автомата  на  JK-триггерах,  меняю-

щего  под  действием  синхроимпульсов 

свои состояния в последовательности: 

4, 0, 3, 2, 5, 1, 6, 7. 

Булевы  функции,  описывающие 

состояния  входов  триггеров  A,  B,  C, 

представить  в  минимальных  ДНФ.  Определить,  сколько  букв  в  каждой 

из функций: J

A

, K

A

, J

B

, K

B

, J

C

, K

C

. 

Решение. Составляем таблицу переходов автомата (табл. 2), как это 

показано  в  п.  9.5  учебного  пособия.  Для  каждого  из  триггеров  находим 

уравнения входов и минимизируем их при помощи карт Вейча (здесь кар-

ты не приводятся). Булева модель автомата имеет вид следующего списка 

минимальных ДНФ функций: 

;

C

B

C

B

J

A





;

B

K

A



;

A

J

B



;

C

A

AC

K

B





;

B

A

J

C





.

B

A

K

C





Ответ: 4, 1, 1, 4, 2, 2.  

Пример 2. Построить булеву модель автомата на T-триггерах, меня-

ющего под действием синхроимпульсов свои состояния в той же последо-

вательности, что и в предыдущем примере: 

4, 0, 3, 2, 5, 1, 6, 7. 

Определить, сколько букв в каждой из функций: T

A

, T

B

, T

C

 (без учёта 

генератора). 

Решение.  Строим  таблицу  переходов  автомата  (табл.  3).  Пусть  ис-

ходным  является  состояние  100.  После  одного  прямоугольного  импульса 

должно установиться состояние 000, т. е. импульс должен пройти на вход 

    Таблица 2 

Дес.  A B C  J

A 

 K

A 

J

B 

K

B

  J

C 

 K

C

4 
0 
3 
2 
5 
1 
6 
7 

1 0 0 
0 0 0 
0 1 1 
0 1 0 
1 0 1 
0 0 1 
1 1 0 
1 1 1 

 ×   1 
 0   × 
 0   × 
 1   × 
 ×   1 
 1   × 
 ×   0 
 ×   0 

 0   × 
 1   × 
 ×   0 
 ×   1 
 0   × 
 1   × 
 ×   0 
 ×   1 

 0   × 
 1   × 
 ×   1 
 1   × 
 ×   0 
 ×   1 
 1   × 
 ×   1 

34 

только одного триггера A, и изменить 

его состояние. В соответствии с этим 

в колонке T

A

 на пересечении со стро-

кой 100 (десятичное 4) ставим едини-

цу,  а  в  остальных  колонках  той  же 

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

Под действием второго импуль-

са  автомат  должен  перейти  в  состояние  011.  Отмечаем  это  единицами 

в колонках T

B

 и T

C

 на пересечении со строкой 000. В колонке T

A

 той же стро-

ки ставим нуль, так как триггер A должен остаться в нулевом состоянии. 

Третий импульс должен сменить состояние триггера C. Следователь-

но,  в  колонке  T

C

  на  пересечении  со  строкой  011  записываем  единицу, 

а в колонках T

A

 и T

B

 ставим нули. 

Аналогично  заполняем  всю  таблицу.  Рассматривая  её  как  таблицу 

истинности для трёх функций, находим их минимальные ДНФ: 

;

C

B

A

C

B

B

A

T

A







;

C

A

C

B

T

B





.

B

A

T

C





В п. 9.3 учебного пособия отмечается, что все полученные выраже-

ния необходимо умножить на φ, где φ – генератор прямоугольных импуль-

сов. Однако в данном случае в соответствии с условием задачи генератор 

не учитывается, т. е. умножение на φ не требуется. Ответом к задаче явля-

ется  упорядоченная  последовательность  чисел  7,  4  и  2,  показывающих, 

сколько букв содержится в минимальных ДНФ функций T

A

, T

B

 и T

C

. 

Ответ: 7, 4, 2. 

Таблица 3 

Дес.  A B C 

T

A 

T

B 

T

C 

4 
0 
3 
2 
5 
1 
6 
7 

1  0  0 
0  0  0 
0  1  1 
0  1  0 
1  0  1 
0  0  1 
1  1  0 
1  1  1 

1 
0 
0 
1 
1 
1 
0 
0 

0 
1 
0 
1 
0 
1 
0 
1 

0 
1 
1 
1 
0 
1 
1 
1 

35 

ЛИТЕРАТУРА 

1. Акимов  О.  Е.  Дискретная  математика:  логика,  группы,  графы  / 

О. Е. Акимов. – М. : Лаборатория Базовых Знаний, 2003. – 376 с. 

2. Березина Л. Ю. Графы и их применение : пособие для учителей / 

Л. Ю. Березина. – М. : Просвещение, 1979. – 143 с. 

3. Бохманн Д. Двоичные динамические системы : пер. с нем. / Д. Бо-

хманн, Х. Постхоф. – М. : Энергоатомиздат, 1986. – 401 с. 

4. Виленкин Н. Я. Комбинаторика / Н. Я. Виленкин, А. Н. Виленкин, 

П. А. Виленкин. – М. : ФИМА, МЦНМО, 2006. – 400 с. 

5. Горбатов В. А. Дискретная математика : учеб. для студентов вту-

зов / В. А. Горбатов, А. В. Горбатов, М. В. Горбатова. – М. : ООО «Изда-

тельство АСТ» ; ООО «Издательство Астрель», 2003. – 447 с. 

6. Ежов И. И. Элементы комбинаторики / И. И. Ежов, А. В. Скороход, 

М. И. Ядренко. – М. : Гл. ред. физ.-мат. лит. изд-ва «Наука», 1977. – 80 с. 

7. Клини С. К. Математическая логика : пер. с англ. / С. К. Клини. – 

М. : Изд-во ЛКИ, 2008. – 480 с. 

8. Колдуэлл С. Логический синтез релейных устройств : пер. с англ. / 

С. Колдуэлл. – М. : Изд-во иностранной литературы, 1962. – 737 с. 

9. Кондаков Н. И. Логический словарь-справочник / Н. И. Кондаков. – 

М. : Наука, 1975. – 720 с. 

10. Нефедов  В.  Н.  Курс  дискретной  математики  /  В.  Н.  Нефедов, 

В. А. Осипова. – М. : Изд-во МАИ, 1992. – 264 с. 

11. Новиков  Ф.  А.  Дискретная  математика  для  программистов.  – 

СПб. : Питер, 2003. – 304 с.  

12. Очков  В.  Ф.  Физико-математические  этюды  с  Mathcad  и  Интер-

нет / В. Ф. Очков, Е. П. Богомолова, Д. А. Иванов. – СПб. : Лань, 2016. – 

388 с.