ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 15247
Скачиваний: 187
216
47.
Уилсон Р. Введение в теорию графов / Р. Уилсон ; пер. с англ. – М. :
Мир, 1977. – 207 с.
48.
Фистер М. Логическое проектирование цифровых вычислительных
устройств / М. Фистер. ; пер. с англ. – Киев : Техника, 1964. – 382 с.
49.
Форд Л. Потоки в сетях / Л. Форд, Д. Фалкерсон ; пер. с англ. – М. :
Мир, 1966. – 276 с.
50.
Фор Р. Современная математика / Р. Фор, А. Кофман, М. Дени-
Папен /; пер. с фр. – М. : Мир, 1966. – 271 с.
51.
Фудзисава Т. Математика для радиоинженеров: Теория дискретных
структур / Т. Фудзисава, Т. Кассами ; пер. с япон. – М. : Радио и связь,
1984. – 240 с.
52.
Харари Ф. Теория графов / Ф. Харари ; пер. с англ. – М. : КомКнига,
2006. – 296 с.
53.
Чупахин И. Я. Формальная логика / И. Я. Чупахин, А. М. Плотников,
К. А. Сергеев и др. – Л. : Изд-во Ленинградского ун-та, 1977. – 357 с.
54.
Шалыто А. А. Логическое управление. Методы аппаратной и про-
граммной реализации алгоритмов / А. А. Шалыто. – СПб. : Наука,
2000. – 780 с.
55.
Шевелев Ю. П. Дискретная математика : учеб. пособие / Ю. П. Шеве-
лев. – СПб. : Лань, 2016. – 592 с.
56.
Шевелев Ю. П. Математическая логика и теория алгоритмов /
Ю. П. Шевелев. – Томск : Дельтаплан, 2007. – 219 с.
57.
Яблонский С. В. Введение в дискретную математику / С. В. Яблон-
ский. – М. : Высш. шк., 2003. – 384 с.
58.
Многотактное устройство [Электронный ресурс] // Большая энцикло-
педия нефти и газа. – Режим доступа:
http://www.ngpedia.ru/id554468p1.html (дата обращения: 19.01.2017).
217
Ответы
1.1. Понятие множества.
1.
1) 12; 2) 101; 3) 41.
2.
1) 5; 2) 3; 3) 4.
1.2. Понятие подмножества.
1.
1, 3, 5, 6.
2.
32.
3.
6.
4.
а. 7; б. 8; в. 58.
1.3. Объединение, пересечение и дополнение множеств.
1.
1) 0, 1, 3, 5, 9;
2) 2, 3, 6, 7, 8; 3) 1, 2, 6; 4) 0, 1, 4, 6; 5) 8.
2.
1) 2, 7, 8, 9; 2) 0, 5; 3) 4.
1.4. Разность и симметрическая разность множеств.
1.
1) 0, 2, 3, 8; 2) 0,
5, 7, 8; 3) 2, 3.
2.
1) 0, 3, 4, 8; 2) 0, 1, 2, 3, 5, 9; 3) 0, 2, 3, 9.
1.5. Диаграммы Венна.
1.
1) 0, 2, 5, 6, 7; 2) 1, 3, 4, 8, 9; 3) 1, 3, 4, 8, 9; 4) 0,
2, 5, 6, 7.
2.
1) 3, 5, 6, 7, 9; 2) 3, 6, 9; 3) 7; 4) 0, 3, 4, 6, 7, 8, 9.
1.6. Декартово произведение множеств.
1.
1) 9; 2) 5; 3) 6; 4) 6; 5) 4; 6) 10.
2.
1) 0; 2) 1; 3) 4; 4) 1.
3.
1) 7, 2; 2) 2, 7; 3) 5, 3; 4) 3, 5.
2.2. Факториал.
1.
1) 8!; 2) 9!; 3) (k – 1)!; 4) 11!.
2.
1) 15; 2) 32.
3.
1) 8; 2) 2.
4.
3, 5, 7, 8, 9.
5.
0, 4.
2.3. Правило произведения в комбинаторике.
1.
125.
2.
243.
3.
3125.
4.
96.
5.
30.
6.
1800.
7.
900.
2.4. Правило суммы в комбинаторике.
1.
10.
2.
3.
3.
7.
2.5. Перестановки без повторений.
1.
24.
2.
95.
3.
720.
4.
144.
2.6. Перестановки с повторениями.
1.
252.
2.
126.
3.
64.
4.
20.
5.
а. 4; б. 0;
в. 179; г. 179; д. 0; е. 1.
2.7. Размещения без повторений.
1.
60.
2.
720.
3.
120.
4.
3024.
5.
720.
2.8. Размещения с повторениями.
1.
100.
2.
162.
3.
4096.
4.
36.
5.
180.
6.
1024.
7.
128.
2.9. Сочетания без повторений.
1.
35.
2.
210.
3.
35.
4.
512.
5.
5, 6.
6.
56
7.
220.
8.
126.
9.
210.
2.10. Сочетания с повторениями.
1.
816.
2.
1) 1001; 2) 286; 3) 36.
3.1. Понятие графа.
1.
32.
2.
256.
3.
21.
4.
1) 8; 2) 64; 3) 1024.
5.
а. 190;
б. 153; в. 6.
3.2. Смежность. Инцидентность. Степень вершины.
1.
а. 2, 5, 6; б. 3, 4,
7; в. 1; г. 2, 4, 6; д. 3211221.
2.
1) а, в, д, е, ж; 2) а, б, г, е; 3) в, г, е.
3.3. Однородный граф. Полный граф. Дополнение графа.
1.
21.
2.
2, 3, 5, 7.
3.
45.
4.
15.
5.
12.
6.
а. 8; б. 124.
7.
13.
3.4. Маршруты, цепи, циклы.
1.
1, 5.
2.
2, 3, 4.
3.
б, е.
3.5. Связность графа.
1.
3.
2.
3.
3.
а, в, г, д.
218
3.6. Нахождение простых цепей в простом графе.
1.
19.
2.
4, 7, 7.
3.
а. 8;
б. 1, 1, 3, 3.
4.
в, г, д.
3.7. Двудольные графы.
1.
28.
2.
13, 11.
3.
48.
4.
162.
5.
16.
6.
б, д, е, з.
7.
1,
2, 4, 5, 7.
8.
1, 2, 7.
3.8. Двойственные графы.
1.
7, 9, 4.
2.
4, 6, 4.
3.
3, 4, 5, 6, 8.
4.
3, 5.
3.9. Древовидные графы.
1.
0.
2.
17.
3.
37.
4
. 28.
5.
21.
6.
14.
7.
1, 2, 3, 4,
5, 7.
4.1. Вводные понятия.
1.
1, 0, 0, 1, 1.
2.
1) 20; 2) 15; 3) 15; 4) 20.
3.
1) 1022;
2) 1002.
4.2. Логические операции и формулы.
1.
1, 2, 3.
2.
2, 4,
3.
2, 3.
4.3. Нормальные формы булевых выражений.
1.
1, 2, 5, 6, 7.
2.
2, 3, 5.
3.
1,
2, 3, 5, 6, 7.
4.
2, 5.
5.
1, 5, 6.
6.
1, 2, 3, 4.
4.4. Вычисление значений булевых формул.
1.
1) 1, 0, 1; 2) 1, 0, 0; 3) 1, 0, 0;
4) 1, 0, 0.
2.
1) 0, 1, 0, 0; 2) 1, 0, 1, 0; 3) 0, 1, 1, 0; 4) 0, 1, 1, 0.
4.5. Основные теоремы алгебры логики.
1.
A, K.
2.
1) PQ; 2) XZ; 3) ABC;
4) AD.
3.
1) AB; 2) 0; 3) 1; 4) A + B; 5) 1; 6) 1; 7) 0; 8) 0.
4.6. Понятие булевой функции.
1.
4, 4.
2.
2, 6.
3.
13.
4.
1) 3, 6; 2) 1, 6, 7;
3) 0, 3, 7; 4) 5, 6, 7.
4.7. Совершенная дизъюнктивная нормальная форма.
1.
1) 11001; 2) 010;
3) 0101; 4) 1101; 5) 101010; 6) 01.
2.
1, 6, 7.
3.
1) 9; 2) 1; 3) 2; 4) 1; 5) 5; 6) 0.
4.
32.
5.
32.
6.
34.
4.9. О формах высших порядков.
1.
1) 5; 2) 5; 3) 6; 4) 5; 5) 6.
2.
1) 6; 2) 7;
3) 7; 4) 6; 5) 7; 6) 7.
5.1. Алгебраическое упрощение булевых формул.
1.
1) 3, 3; 2) 3, 5; 3) 1, 4;
4) 1, 4; 5) 2, 8; 6) 2, 7; 7) 3, 5; 8) 1, 4.
2.
1) Q; 2) P; 3) P + Q; 4) ABC; 5) P;
6) B + C.
5.2. Метод Квайна.
1.
1) 10, 40; 2) 1, 10; 3) 3, 2; 4) 6, 17.
2.
1) 3, 5; 2) 4, 9;
3) 3, 8; 4) 3, 6; 5) 5, 11.
5.3. Метод Петрика.
1.
1) 10, 12; 2) 10, 16; 3) 2, 8; 4) 2, 11; 5) 1, 6; 6) 2, 11.
2.
1) 6, 24; 2) 3, 10; 3) 4, 14; 4) 2, 4; 5) 4, 7.
5.6. Операции над функциями, представленными в СДНФ.
1.
1)
7; 2)
13;
3) 1; 4) 9; 5) 19; 6) 25.
2.
32.
3.
1024.
4.
1) 7; 2) 5; 3) 12; 4) 14; 5) 13; 6) 12.
5.
1) 12;
2) 3; 3) 15; 4) 1; 5) 6; 6) 7.
6.
2, 4, 8, 16.
5.7. Минимизация ДНФ при помощи карт Вейча.
1.
1) 2, 3; 2) 3, 6; 3) 2, 5;
4) 1, 1; 5) 3, 3; 6) 2, 4.
2.
1) 3, 6; 2) 3, 4; 3) 4, 6.
219
6.1. Минимизация конъюнктивных нормальных форм булевых функций.
1.
1) 8, 12; 2) 7, 11; 3) 5, 8; 4) 7, 12; 5) 6, 11.
2.
1) 7, 11; 2) 8, 12; 3) 4, 7; 4) 7, 12; 6,
10.
6.5. Упрощение логических выражений в алгебре Жегалкина.
1.
1) 1, 0, 0;
2) 0, 1, 0.
2.
1) 0, 1, 1; 2) 0, 1, 0.
3.
1) ABC; 2) BC; 3) AC; 4) BC.
4.
1) A ⊕ B ⊕ C;
2) A ⊕ BC; 3) A ⊕ B ⊕ C ⊕ 1; 4) AB ⊕ CD.
5.
1) B + C; 2)
;
C
B
A +
3)
.
C
B
A +
6.6. Производная от булевой функции.
1.
0, 1, 2.
2.
1) 1, 3, 5; 2) 0, 2, 4; 3) 1,
3, 7; 4) 2, 4, 6.
3.
1) BC; 2)
;
D
C
B
3) B; 4) B + C.
4.
1)
;
C
A +
2)
;
C
A
3)
;
C
A
4) 0.
6.7. Дифференцирование булевых функций с применением карт Вейча.
1.
14, 5.
2.
7, 12.
3.
10, 11.
6.8. Симметрические булевы функции.
1.
35.
2.
2, 3, 4, 7.
3.
1, 2, 3.
7.8. Задача о звонке и осветительных лампах.
1.
а, б, в.
2.
0, 0.
3.
220, 220.
4.
110, 110, 0, 220.
7.9. Инверсные структуры.
1.
а.
4, 8, 3; б. 0, 1, 4, 5, 7, 9, 11, 12, 13, 15; в. 2,
3, 6, 8, 10, 14; г. 3, 8, 5.
2.
1) 4, 10, 2; 2) 5, 8, 2; 3) 2, 8, 6; 4) 0, 1, 2, 3, 6, 10.
8.2. Электрическая схема элемента И.
1.
0.
2.
5.
3.
5.
8.3. Электрическая схема элемента ИЛИ.
1.
5.
2.
5.
3.
0.
8.4. Электрическая схема элемента НЕ (инвертора).
1.
5.
2.
5.
3.
0.
8.6. Построение комбинационных схем.
1.
1) 1, 1; 2) 1, 2; 3) 3, 3.
2.
2, 2.
8.7. О весовых и невесовых кодах.
1.
8, 10.
2.
6, 10.
3.
2.
4.
6, 9.
9.2. Линейные функции.
1.
1, 3, 5.
2.
1, 2, 5.
3.
1, 3, 4, 5.
9.3. Монотонные функции.
1.
1, 2, 3, 4.
2.
1, 4, 5.
3.
3, 4, 5.
9.4. Самодвойственные функции.
1.
1, 5.
2.
2, 4, 5, 6.
9.5. Функции, сохраняющие единицу.
1.
1, 2, 6.
2.
2, 4, 6.
9.6. Функции, сохраняющие нуль.
1.
1, 2, 5, 6.
2.
1, 2, 3, 5, 6.
10.3. Синтез синхронного автомата на Т-триггерах.
1.
13.
2.
15.
10.5. Синтез многотактных автоматов на JK-триггерах.
1.
1) 5; 2) 3;
3) 8; 4) 6, 9, 9, 6.
2.
1) 8; 2) 0; 3) 8; 4) 3, 2, 1, 0.
220
Предметный указатель
Автомат конечный 194
– многотактный 195
– однотактный 195
– с памятью 209
Алгебра булева 77
– Жегалкина 132
– логики 77
Аксиома объёмности 11
– экстенсиональности 11
Амперсанд 10
Аргументы логические 88
– фиктивные 101
Ассоциативность 80, 133
Булеан 12
Вершины графа висячие 57
– изолированные 54
– концевые 57
– нечётные 58
– смежные 57
– чётные 58
Выборка 26
Высказывание 77
Выход триггера инверсный 171
– прямой 171
Грань графа 70
– внешняя 70
Граф 54
– двойственный 71
– двудольный 67
– полный 68
– древовидный 72
– линейный 54
– несвязный 63
– однородный 59
– планарный 70
– плоский 70
– полный 60
– полуэйлеров 58
– помеченный 54
– простой 54
– пустой 56
– регулярный 59
– связный 63
– частичный 56
– эйлеров 58
Графы двойственные 71
Дерево 72
Диаграммы Венна 18
– Эйлера – Венна 18
Дизъюнкция 79
Дистрибутивность 14, 80
Дифференцирование 140
ДНФ 82
Длина цепи 62
Дополнение графа 60
– множества 15
Закон поглощения 15
– склеивания 15
Импликанта простая 105
Инверсия 80
Инвертор 169
Интерпретация 148, 165
Инцидентность 57
Карты Вейча 109
Квадрат множества 24
Классы булевых функций 183