Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
— Клини 162
—, реализация функции 16
— Стирлинга 208 , константа 211
— строение 15
Формулы обращения 191, 192
— эквивалентные 20 Функции равные 12 —, суперпозиция 16
?— элементарные 13, 45
, свойства 21, 46, 47
Функциональный элемент 336 Функция алгебры логики (булева функция) 9, 10
— Вебба 50
— вычислимая 143
— двойственная 23
— детерминированная 75 ---, вес 83
ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ
379
Функция детерминированная, задание 78
— линейная 33, 88
— монотонная 36
— не всюду определенная 96, 143
— нелинейная 38
— немонотонная 37
— несаыодвойственная 35
— ограниченно - детерминированная (о-д.) 86
— пеановская 162
— примитивно-рекурсивная 149
— производящая 198
? экспоненциальная 200
—, разложение по всем п переменным 26 —, — по переменной 26 —, — по т-неременным 25
— рекурсивная 149
— самодвойственная 34
— симметрическая 366
относительно переменных
12
всех своих переменных
12, 13
существенных переменных 13 —, сохраняющая константу 0 34 —, — константу 1 34 —, — множество 50 —, функций 53
— существенная 56
— тождественная 13
— характеристическая 45
— частичная 143
? счетнозначной логики 143
— частично-рекурсивная 149
— Шеннона 350
— Шеффера 13, 65
, аналог 408, 170
Ф. Э. 336
Цепь 240 Цикл 223
— ориентированный 269 Цилиндр 89
Числа Белла 184, 187 • , формула 193
— Стирлинга 2-го рода 184, 185, 187
—, формула 192, 193
— Фибоначчи 198, 200
— Sm(n) 196, 197
Число булевых функций от п переменных 11 --------, существенно зависящих от п переменных 190,
192
— нензбыточпых покрытий 194, 196
— неизоморфных графов 226, 227, 237
сетей 254
— о.-д функций 87
— перестановок 174 , порядок 208
— —, оценки 176
— подмножеств 173
— рабочее 306
— размещений 174
— соединений 347
— сочетаний 177
с повторениями 180
— схем из Ф. Э. 347
— точек в слое «-мерного куба 179, 182, 183
— тупиковых покрытий 194, 196
— упорядоченных покрытий 195
— функций ft-значной логики от п переменных 44
— е 174
— л-сетей 254
Члены информационные 290
— контрольные 290
Шар 293 —, радиус 293 —, центр 293
Эквивалентность асимптотическая 204, 355
— деревьев 83
— с точностью до порядка 205, 355
—-------------абсолютных вели-
чин 203
— формул 20 Элемент 336
— функциональный 336 Энтропия 236
Ядро 325
Язык операторный 121 Ярус 79
Ячейка ленты 115
начальная 117
пустая 119
УКАЗАТЕЛЬ ОБОЗНАЧЕНИЙ
Еч — множество {0, 1} 9
1Pj — система всех функции алгебры логики 10
р2(«)—число функций иа Рз, зависящих от п переменных 11
х — отрицание х 13
Xl&Xt — КОНЪЮНКЦИЯ Х\ И ZS 13
*1 V *2 — ДИЗЪЮНКЦИЯ Xj И Х2 1 3
X] —*? х2— импликация х\ и х2 13 + *2 — сложение по mod 2 13 xrfxa — функция Шеффера 13
SI[/|, /,]—формула fit построена из функций /ь /а 15
fit(zi, хл) — формула fil содержит переменные хи хп (и не содержит других) 15
Й = С[Д, /а, }а]—формула S имеет строение С 15
fit = SS — формулы fit и S8 эквивалентны 20 /* — функция, двойственная функции / 23 fit* — формула, двойственная формуле fit 24 х° 25
а л г х. ... х. — полином Жегалкина 32
амыкание множества Ф1 33 L — класс всех линейных функций 33 То — класс всех функций, сохраняющих константу 0 33 Т\ — класс всех функций, сохраняющих константу 1 34 S — класс всех самодвойственных функций 34 а — векторная запись набора 36 =< — отношение предшествования 36 М — класс всех монотонных функций 36 Eh — множество (0, 1, ..к — 1) 43 Ph — система всех функции А--значной логики 44 х — обобщение отрицания в смысле циклического сдвига значений 45
~ х — отрицание Лукашевича 45
li (х) — функция, обобщающая некоторые свойства отрицания 45
ji(x) — характеристическая функция значения i 45 min (24, ж2) — обобщение конъюнкции 45 . х 1^2 (mod к) — второе обобщение конъюнкции 45 max (аг[, яа) — обобщение дизъюнкции 45 ху + ?2 (mod к) 45 /а, i (я) 49
V*(®i, хз) — функция Вебба 50
g\ (Zj, Zp) — функция, равная xt 51
SJL у — множество всех функций из 2JI, зависящих от не-
*vj т
ременных хи хр 51
УКАЗАТЕЛЬ ОБОЗНАЧЕНИЙ
381
Л — пустое множество 52
|С| —число элементов множества С 57
хі\/оі^2 — максимум па множестве {0, 1} X {0, 1} 62
хі&сіх^ — минимум на множестве {0, 1} X {0, 1} 62
]а[ — наименьшее целое число, не меньшее а 66
С — операция суперпозиции 73
[Р2, С) — алгебра логики 73
(Р*. С) — /с-значная логика 73
(?^х » С)-счетнозначная логика 73
^ — расширенный натуральный ряд 73 С)— континуумзвачная логика 73
Е —множество всех &-значных последовательностей 73
к
Р —множество всех функций, определенных на наборах
Ц я
с компонентами из Я? ^и принимающих значения из Е? 73
Рд.й — множество всех детерминированных функций изР 75
і ^
/ф — детерминированная функция, соответствующая функции Ф из Рк 77
Фь — множество всех функций /ф, ФєА 78 Родд — множество всех ограниченно-детерминированных функций из Рдд 86
р(к, п, г)—число о.-д. функций ИЗ Род,л, зависящих от п переменных и имеющих вес г 87 ,
X — переменная, описывающая значение входной величины 88 <2 — переменная, описывающая значение состояния 88 І — переменная, описывающая значение выходной величины 88
