- •Дискретная математика
- •Минск 2015
- •1.1. Определения
- •1.2. Способы задания множеств
- •1.3. Операции над множествами
- •Рис. 1.1. Операции над множествами
- •2.1. Декартово произведение
- •2.3. Операции над бинарными отношениями
- •3.2. Графическое представление бинарного отношения
- •3.1. Абстрактный граф
- •Рис. 3.3. Представление композиции отношений: а) отношения R и S;
- •3.3. Матричные представления графа
- •4.1. Отношение изоморфизма
- •5.1. Цикломатическое число графа
- •6.1. Доминирующие множества графа
- •6.2. Независимые множества графа
- •7.1. Постановка задачи
- •8.1. Эйлеровы цепи и циклы
- •Рис. 8.3. Граф со взвешенными ребрами и выделенным кратчайшим путем
- •9.1. Определения
- •Рис. 9.1. Плоский граф
- •Рис. 9.2. Максимальный планарный граф
- •Рис. 9.3. Простейшие непланарные графы
- •10.1. Задачи подсчета
- •11.1. Постановка задачи
- •12.1. Способы задания булевой функции
- •Нормальные формы
- •14.1. Булев гиперкуб
- •Рис.14.1. Графическое представление булева пространства: а) одномерное; б) двумерное; в) трехмерное; г) четырехмерное
- •14.2. Представление булевых функций на гиперкубе
- •Рис.14.2. Трехмерный гиперкуб с заданной на нем булевой функцией
- •Рис.14.3. Графическое представление некоторых формул булевой алгебры: а) простое склеивание; б) простое поглощение; в) обобщенное склеивание
- •14.3. Развертка гиперкуба на плоскости. Карта Карно
- •Рис. 14.6. Зоны симметрии карты Карно
- •15.1. Функциональная полнота
- •15.2. Реализация булевых функций комбинационными схемами
- •16.1. Отношения на множестве троичных векторов. Операции над троичными векторами. Эквивалентность матриц
- •16.2. Эквивалентность матриц
- •16.3. Анализ троичной матрицы на вырожденность
- •17.1. Удаление избыточных элементарных конъюнкций
- •17.2. Удаление избыточных литералов
- •18.1. Метод Квайна-МакКласки
- •18.2. Метод Блейка-Порецкого
- •19.1. Постановка задачи
- •19.2. Применение метода Квайна-МакКласки
- •19.3. Минимизация слабо определенной функции
- •19.4. Расширение интервалов
- •20.1. Минимизация системы ДНФ
- •20.2. Минимизация системы слабо определенных булевых функций
- •21.1. Двухблочная разделительная декомпозиция
- •У т в е р ж д е н и е 21.3. Булева функция f (x) допускает параллельную разделительную декомпозицию вида (21.1) тогда и только тогда, когда она допускает двухблочные разделительные декомпозиции вида
- •21.4. Неразделительная декомпозиция
- •21.5. Декомпозиция систем булевых функций
- •22.1. Автомат с памятью
- •22.2. Представления автомата
- •22.3. Связь между моделями Мили и Мура
- •22.4. Автомат с абстрактным состоянием. Булев автомат
- •23.1. Эквивалентность состояний. Постановка задачи минимизации
- •23.2. Установление эквивалентности состояний
- •24.1. Отношение реализации. Постановка задачи минимизации
- •24.2. Совместимость состояний
- •24.3. Нахождение минимальной правильной группировки
- •Таблица 24.7
- •Таблица 24.9
- •Рис. 24.2. Дерево поиска минимальной правильной группировки
- •25.1. Задача кодирования состояний
- •25.2. Метод «желательных соседств»
- •26.1. Явление состязаний элементов памяти
- •26.2. Условие отсутствия опасных состязаний
- •26.3. Минимизация длины кода
- •26.4. Рассмотрение K-множеств
- •Литература
- •Матрица булева 15
- •Ядро 11
Литература
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