Литература

1. Андерсон Д.А. Дискретная математика и комбинаторика. – М.: Издательский дом «Вильямс», 2003. – 960 с.

2. Ангер С. Асинхронные последовательностные схемы. – М.: Наука,

1977. – 400 с.

3. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979. – 536 с.

4. Баранов С.И. Синтез микропрограммных автоматов. – Л.: Энергия,

1979. – 232 с.

5. Быкова С.В., Буркатовская Ю.Б. Булевы функции: Учебное пособие. – Томск: Томский государственный университет, 2010. – 192 с.

6. Вавилов Е.Н., Портной Г.П. Синтез схем электронных цифровых машин. – М.: Советское радио, 1964. - 440 с.

7. Глушков В.М. Синтез цифровых автоматов. – М.: ГИФМЛ, 1962. – 476 с. 8. Закревский А.Д. Логический синтез каскадных схем. – М.: Наука. 1981. –

414 с.

9. Закревский А.Д., Поттосин Ю.В., Черемисинова Л.Д. Основы логического проектирования. В 3 кн. Кн.1. Комбинаторные алгоритмы дискретной математики. – Мн.: ОИПИ НАН Беларуси, 2004. – 226 с.

10. Закревский А.Д., Поттосин Ю.В., Черемисинова Л.Д. Основы логического проектирования. В 3 кн. Кн.2. Оптимизация в булевом пространстве. – Мн.: ОИПИ НАН Беларуси, 2004. – 240 с.

11. Закревский А.Д., Поттосин Ю.В., Черемисинова Л.Д. Основы логического проектирования. В 3 кн. Кн.3. Проектирование устройств логического управления. – Мн.: ОИПИ НАН Беларуси, 2006. – 254 с.

12. Закревский А.Д., Поттосин Ю.В., Черемисинова Л.Д. Логические основы проектирования дискретных устройств. – М.: ФИЗМАТЛИТ, 2007. –

592с.

13.Зыков А.А. Основы теории графов. – М.: Наука, 1987. – 384 с.

14.Кнут Д.Э. Искусство программирования, том 4, А. Комбинаторные алгоритмы, часть 1. – М.: ООО «И. Д. Вильямс», 2013. – 960 с.

15.Кристофидес Н. Теория графов. Алгоритмический подход. – М.: Мир,

1978. – 432 с.

16.Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженеров. – М.: Энергия, 1988. – 480 с.

17.Лазарев В.Г., Пийль Е.И. Синтез управляющих автоматов. – М.: Энергоатомиздат, 1989. – 328 с.

18. Лекции по теории графов / Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. – М.: Наука, 1990. – 384 с.

19. Миллер Р. Теория переключательных схем, т.I. – М.: Наука, 1970. –

416 с.

191

20. Миллер Р. Теория переключательных схем, т.II. – М.: Наука, 1971. –

304с.

21.Новиков Ф.А. Дискретная математика для программистов. (2-е изд.). – М., С.-Пб.: Питер. – 2005. – 364 с.

22.Поспелов Д.А. Логические методы анализа и синтеза схем. – М.; Л.: Энергия, 1964. – 320 с.

23.Поттосин Ю.В. Основы теории проектирования цифровых устройств. – Saarbrücken: LAP LAMBERT Academic Publishing, 2011. – 336 c.

24.Скляров В.А. Синтез автоматов на матричных БИС. – Минск: Наука и техника, 1984. – 287 с.

25.Фридман А., Менон П. Теория и проектирование переключательных схем. – М.: Мир, 1978. – 580 с.

26.Яблонский С.В. Введение в дискретную математику. – М.: Наука,

1986. – 384 с.

192

Предметный указатель

Автомат асинхронный 146

–булев 151

–комбинационный 144

–конечный 145

–Мили 145

–Мура 145

–не полностью определенный 146

–полностью определенный 146

–с абстрактным состоянием 151

–синхронный 146

–частичный 146

алгебра булева 72

− логики 71 алгоритм жадный 46

антисимметричность 20 антиядро 112 аргумент 18

–существенный 70

–фиктивный 70 ассоциативность 12

Базис 88

– циклов 32 булево пространство 68

булевы переменные 68

Вектор булев 10

– троичный 69 вершина графа 22 высказывание 76

Гиперкуб 87 граф 22

−бихроматический 47

−гамильтонов 50

−двудольный 24

−неориентированный 22

−ориентированный 22

−полный 23

−планарный 54

−плоский 54

−поведения автомата 147

−эйлеров 49 группировка 159

– правильная 159

– – минимальная 159

Декартово произведение 15

декомпозиция 128

–двублочная разделительная 128

–неразделительная 137

–параллельная разделительная 135

–последовательная разделительная 133 дерево поиска 60

–остовное 32

дизъюнкция 71

–с исключением 71

–элементарная 78 дистрибутивность 12 дихотомия 20

ДНФ (дизъюнктивная нормальная форма)

77

−безызбыточная 100

– кратчайшая 104

– минимальная 104

−совершенная 79

– сокращенная 104 дополнение графа 23

− множества 11 дуга графа 22

Закон двойного отрицания 73

−поглощения 73

−простого склеивания 73 законы де Моргана 73 значение функции 18

Изоморфизм графов 29 импликанта 104

–простая 104 импликация 71

–формальная 100 инварианта 30 инверсия 71

интервал булева пространства 69

–максимальный 104

–обязательный 108

Канонизация графа 30 карта декомпозиции 129 карта Карно 84 класс эквивалентности 20 K-множество 185

КНФ (конъюнктивная нормальная форма)

80

код Грея 85

193

коммутативность 12 композиция отношений 17 компонента (связности) 27 конституента единицы 80

− нуля 81 корень дерева 60 контур 27

конъюнкция полная 78

– элементарная 78

Литерал 78

Матрица булева 15

−инцидентности 26

−смежности 25

–совместимости 161

–троичная 69

–− вырожденная 93

–условий 182

–фундаментпльных разрезов 35

–фундаментпльных циклов 34

–эквивалентности 155

метод Блейка–Порецкого 109

–Квайна–МакКласки 104 минор 94 множество 8

–интервально поглощаемое 118

–– – максимальное 118

−независимое 38

−− максимальное 38

−− наибольшее 38

–непосредственно производное 159

–совместимое 163, 182

− пустое 8

– характеристическое 68 мощность множества 9 мультиграф 27

Область значений функции 16

– определения функции 16 объединение множеств 12 окрестность вершины 23 отношение 15

−бинарное 15

−взаимно однозначное 18

– между матрицами 92

– между векторами 91

– – – ортогональности 91

– – – пересечения 91

– – – поглощения 91

–– – смежности 91

–– – соседства 91

–реализации между булевыми функциями

116

Пара переходов 180 пересечение множеств 11 петля 23 подграф 26

−остовный 26

−полный 35

−порожденный 27 подмножество 8

−несобственное 8 покрытие 62

−кратчайшее 62

−столбцовое 121

полнота системы функций 88 полный перебор 58 порядок 20

− лексикографический 21 правила редукции 65, 95 принцип двойственности 13 противогоночное кодирование 181

Равносильность формул 11 размерность булева пространства 68 разрез 33

− фундаментальный 34 ранг конъюнкции 78 раскраска графа 44 расстояние в графе 27 ребро графа 22 рефлексивность 20

Сечение 16 симметричность 20 склеивание 13

–обобщенное 14

− простое 13 совместимость 20

–состояний 161

–строк матрицы условий 182 соответствие 15 состояние автомата 145 состязания 179

–неопасные 179

–опасные 179

степень множества 15

– вершины 23

194