Файл: Дискрет-ная мат-ка_УМП.pdf

Скачать файл (0,67Мб)

Заказать решение

ВУЗ: Томский государственный университет систем управления и радиоэлектроники

Категория: Учебное пособие

Дисциплина: Дискретная математика

Добавлен: 28.11.2018

Просмотров: 6248

Скачиваний: 13

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

101

57. Чем отличается альтернативная дизъюнкция от строгой

дизъюнкции? (90)

58. В чем физический смысл производной от булевой функ-

ции? Пример. (95)

59. Как найти интеграл булевой функции табличным мето-

дом? (98)

60. Как найти интеграл булевой функции аналитическим

методом? (99)

61. Что такое импликация? Пример. (100)
62. Что такое антецедент и консеквент? Пример. (100)
63. Приведите пример доказательства истинности силло-

гизма. (102)

64. Что такое многозначная логика? Пример. (103)
65. Приведите аксиомы дизъюнкции, конъюнкции и отри-

цания в логике Шестакова. (106, 107)

66. Что такое модальная логика? (110)
67. Что такое логика предикатов? Пример. (111)
68. Что такое свободная переменная в логике предикатов?

Пример. (111)

69. Что такое квантор общности? Пример. (114)
70. Что такое квантор существования? Пример. (116)
71. Что такое обобщенная дизъюнкция? Пример (116)
72. Что такое обобщенная конъюнкция? Пример (115)
73. В чем суть аксиоматического метода? (121)
74. Что такое формальная теория? (122)
75. Чем отличается теорема от аксиомы? (122)
76. Что такое интерпретация в формальной системе? При-

мер. (124)

77. Что такое формализованный язык? (124)

íÂÓðËfl ÍÓÌÂ˜Ì˚ı ‡‚ÚÓÏ‡ÚÓ‚
1. Что такое конечный автомат с технической точки зрения?

(127)

2. Какие технические устройства называются контактными?

Пример. (128)

3. Как построить контактную структуру на основе булевой

функции? (131)

102

4. Какое техническое устройство называют элементом

Шеффера? (137)

5. Какое техническое устройство называют элементом Пир-

са? (138)

6. Что такое суперпозиция и в чем ее физический смысл?

Пояснить примером. (139)

7. Что такое двоичный регистр? (142)
8. Что такое автоматный базис? Пример. (146)
9. Перечислите пять замечательных классов булевых функ-

ций и приведите примеры. (147–149)

10. Как формулируется теорема Поста о функциональной

полноте? Приведите пример функционально полной системы
булевых функций. (149)

11. Какие булевы функции называют элементарными? При-

меры. (150)

12. Какие булевы функции называют противоречием? При-

мер. (151)

13. Сколько существует минимальных функционально пол-

ных систем элементарных булевых функций? (154)

14. Какие автоматы называют однотактными и какие —

многотактными? (154, 155)

15. Что такое вероятностный автомат? (155, 244)
16. Какие автоматы называют эквивалентными? Поясните

примерами из комбинационных схем. (155)

17. Что такое RS-триггер? Изобразите его логическую схе-

му. (156)

18. Что такое триггер типа T? Приведите его условное обо-

значение. (157–159)

19. В чем суть асинхронного принципа работы автомата.

Пример. (159)

20. В чем суть синхронного принципа работы автомата.

Пример. (159)

21. Что такое JK-триггер? Изобразите его логическую схе-

му. (164)

22. В чем состоит главное отличие автомата Мили от авто-

мата Мура? (169, 171)

23. Какой автомат называют инициальным? (173)
24. В чем суть тестирования автоматов? (174)

103

äÓÏ·ËÌ‡ÚÓðËÍ‡
1. Что такое комбинаторная конфигурация? (176)
2. Что такое рекуррентное соотношение? Поясните приме-

ром. (177, 192)

3. Что такое факториал? (177)
4. Сформулируйте основное правило комбинаторики (пра-

вило произведения). Приведите пример. (178)

5. Как формулируется правило суммы в комбинаторике?

Пример. (180)

6. В чем суть принципа включения-исключения? (181)
7. Запишите формулы для числа перестановок, размещений

и сочетаний с повторениями и без повторений. Поясните их
примерами. (183–192, 195)

8. Что такое минимальное покрытие множества? (198)
9. Что такое латинский прямоугольник? Пример. (199)
10. Какие латинские квадраты называют ортогональными?

Пример. (200)

11. Что такое матрица Адамара? (203)
12. Что такое шифрование? Пример. (204)

íÂÓðËfl „ð‡ÙÓ‚
1. Что такое подграф, надграф? Примеры. (208, 209)
2. Какой граф называют частичным? Пример. (209)
3. Какие вершины называют висячими? Пример. (210)
4. Что такое инцидентность? Пример. (209)
5. Приведите примеры однородных графов. (210)
6. Что такое полный граф? Пример. (210)
7. Что такое дополнение графа? Пример. (211)
8. Какие графы называют помеченными? (211)
9. Что такое матрица смежности? Пример. (214)
10. Что такое матрица инцидентности? Пример. (214)
11. Что такое степень связности графа? Пример. (217)
12. Какие вершины называют связными? Пример. (216)
13. Что такое эйлерова цепь? Пример. (221)
14. Что такое уникурсальная линия? (222)
15. Что такое обход графа? (222, 223)

104

16. Какие графы называют гамильтоновыми? (223)
17. Как формулируется задача о коммивояжере? (223)
18. Что такое двудольный граф, полный двудольный граф?

Примеры. (225)

19. Какие графы называют плоскими? Пример. (225)
20. Какие графы называют планарными? Пример. 225)
21. Что такое грань графа? Пример. (226)
22. Что такое надразбиение ребра? Пример. (227)
23. Какие графы называют изоморфными? Пример. (211)
24. Какие графы называют гомеоморфными? (226)
25. В чем суть критерия Понтрягина-Куратовского (227)
26. Какие графы называют двойственными? Пример. (228)
27. Что такое остов графа? Пример. (229)
28. Какой граф называют лесом, деревом? Примеры. (228)
29. Как формулируется гипотеза четырех красок? (232)
30. Что такое хроматическое число графа? (231)
31. Какие графы называют ориентированными. (232)
32. Что такое основание орграфа? Пример. (233)
33. Какой граф называют смешанным? Пример. (233)
34. Что такое достижимость в орграфе? Пример. (234)
35. Какие графы называют сильно связными и какие — сла-

бо связными? Примеры. (235)

36. Какие графы называют турнирами? Пример. (236)
37. Что такое трансверсаль? Пример. (236)

ùÎÂÏÂÌÚ˚ ÚÂÓðËË ‡Î„ÓðËÚÏÓ‚
1. Что такое алгоритм в интуитивном представлении?
2. Перечислите общие свойства алгоритмов.
3. Что такое машина Тьюринга-Поста?
4. Перечислите команды машины Поста.
5. Что такое алгоритмически неразрешимые проблемы. По-

яснить примерами.