Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
О — операция введения обратной связи 94 ->
х — о.-д. функция, сдвигающая входную последовательность на один разряд 94 (Рпд к, С, О) 105 (?>*, С) 106 (Рода С) 110 {Рода О) 110
А — символ, обозначающий отсутствие информации 1 14
а^й2 ... —головка в данный момент обозревает символ а1 118
Р* — программа, двойственная программе Т 119 р! — оператор проверки логических условий 122 р| —оператор проверки логических условий 122 * — специальный оператор 122 ю — специальный оператор 122
Е/ — подмножество наборов, на котором определена функция / 143
Р4К —множество всех частичных функций счетнозначной логики 143
Риыч — класс всех вычислимых функций 144 5(я) — функция, равная х + 1 145 /” (гг ..агп) —функция, равная хт 145 Пр — операция примитивной рекурсии 146 Д — операция минимизации 146
382 УКАЗАТЕЛЬ обозначений
Рчр — класс частично-рекурсивных функций 149
Р? — класс рекурсивных функций 149
Рпр — класс примитивно-рекурсивных функций 149
вг(я) 149
8?{х) 149
[л/2] — целая часть ж 149
2* — покааательная функция 149
X] ? х2 — умножение 149
*] — ха 149
ж, — 1 150
р(х) 162
0П(Х1, .жп) 162
л(хь х2) —пеановская функция 162
Цж) 162
й(ж) 162
1(х) 163
г(х) 163
©П 171
2?”—и-мерный куб размера А* 172
(п)ь — число размещений из п элементов по к 174
о-
число сочетаний из п элементов по к 177
число сочетаний с повторениями из п элементов по к 180
Ф(га, А)—число разбиений множества из п элементов на к непустых частей (число Стирлинга 2-го рода) *,ЙЗ
Ф(и)—число всех разбиений множества, из л элементов на непустые части (число Белла) 183
рп — число функций из Р2, существенно зависящих от п переменных 190
Ъ (и) — число всех тупиковых покрытий множества из п элементов 196 Sm(n) 197
/„ — числа Фибоначчи 198 /(х) «О(*(*)) 202
f(x)„g{x)— равенство абсолютных величин /(х) и g(x) с точностью до порядка 203 f{x)=o(g(z)) 203
/(х) ~ g(x) — /(х) эквивалентна (асимптотически равна)
у(ж) 204
/ (х) (х) — /(х) не больше g[x) по порядку 204
/(х) ^ g{x)—i(x) асимптотически не больше g(x) 204 fix) X ?{*) “/(*) равна g(x) по порядку 205 Ла.а. — путь, соединяющий вершины at и а} 223
'((ft) —максимальное число попарно неизоморфяых графов без изолированных вершин с ft ребрами 226
9й(?о; Ей Е2, ...) —сеть с набором полюсов -2?о 227 .
<?> — множество объектов из набора Е 228 б (ft) — максимальное число попарно нензоморфных деревьев с А ребрами 232
т — степень сети 233
{hit }i2, ,.ftm) — степенная структура сети 233
УКАЗАТЕЛЬ ОБОЗНАЧЕНИЯ 383
и — средняя степень сети 233
<S(e0. ..., hm) —максимальное число попарно неизоморфных
сетей без изолированных вершин, имеющих е0 полюсов в степенную структуру (fti hm) 234
5(е0, и, т, h)—максимальное число попарно неизоморфных сетей без изолированных вершин, имеющих во полюсов, среднюю степень н, максимальную степень т и число наборов h 234
Г (о, б) — сеть из двухобъектных наборов с полюсами а и b 237 (я, Ь) — параллельное соединение h ребер 243 Г? {а, Ъ)— последовательное соединение h ребер 244 п (h)— максимальное число попарно неизоморфных л-сетеЙ о h ребрами 254
1{А) — длина слова А 256
«S(5t) —множество всех непустых слов в алфавите Я 257 Sе (S) — образ множества S (SI) при алфавитном кодировании 260
L — длина слова В\ ... Вг, т. е. схемы 2 263
/,? — длина слова 263 И7 263
5К(Щ — множество всех непустых слов в алфавите Sf, имеющих длину, не превосходящую N 264 /Ср — средняя длина слова 276
?#—средняя длина слова для оптимального кода 277 '
Qo 280
Я] —множество наборов кода Хэмминга 291 р(Р', р") —расстояние между точками р' и р" в кубе 293 — шар с центром в и радиусом р 293 (р°) —сфера с центром в р° и радиусом р 293 ?(91)—индекс простоты, «сложность» д. н. ф. К 298 Le (3?) — число букв переменных в записи д. н. ф. К 298 Lh (91) — число элементарных конъюнкций в 91 298 ?0 (9*0 — число символов ~ в записи д. н. ф. 91 299 Еп — n-мерный единичный куб 307 Л7К — множество, соответствующее конъюнкции К 308 NK — множество' соответствующее конъюнкции К 308 Кс — сокращенная д. н. ф. 313 9*кв — Д. н. ф. Квайна 326 S?ir — Д. и- ф. типа 2Г 326
Su — окрестность порядка и максимальной грана
NKо 331
2 (х. ..... х. ; z • ,.,., г; W схема нз Ф. Э. с выходами х. , ... 1 ?1 1тг ^1 jpJ г1
..,, г, и выходами г , 339
tn 7i Jv
©— класс всех схем из Ф. Э. над F 344
©о — подкласс всех схем из Ф. Э. над F с одним выходом и без ветвления выходов элементов 344
?,(2) — число элементов в схеме 2 346
S*(п, р, А) —число соединений с п входами, р выходами n h элементами 347
S0{n, p. h)—число минимальных схем пз Ф. Э. с п входами, р выходами ц h элементами 347
384
УКАЗАТЕЛЬ ОБОЗНАЧЕНИЙ
?{/) — сложность минимальной схемы для функции / 350 ?(л) —функция Шеннона 350 ЬА{п) — функция Шеннона 350-
?п — многополюсник, реализующий множество всех конъюнкций 353
— универсальный многополюсник для множества всех булевых функций от п переменных 358
хп)— симметрическая функция с рабочими
числами /ц ..1Т 367
