Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
— примитивной рекурсии 140, 147
— присоединения элемента 337
— расщепления выходов 338
— С 146
— суперпозиции 16, 91, 146, 239 —‘'удаления множителя 301
? несущественной переменной 12, 151
элементарной конъюнкции
301
— и 146
Определитель Вандермонда 70 Отношение предшествования 28
— о 203
, свойства 203, 204
— О 202
— —, свойства 203, 204
Отношение < 205
— ^ 205 ~
—“ 203 -X 205
— 204 Отрицание 13
— Лукашевича 45 —, обобщение 45 Отросток 241 Ошибка 289
—, коррекция 289 —, обнаружение в коде Хем-минга 291
Перебор 11, 300
Переменная несущественная 11, 143
? в узком смысле 151
— существенная 11
— фиктивная 11 , введение 12
?---, удаление 12
Переменные, отождествление 18 —, переименование 18
—, перестановка 18 Перестанопки 172 —, число 174 —, —, порядок 208 —, —, оценки 176 Петля 223
Поглощение произведения множителем 23 Подграф 226
Поддерево специальное 83 Подпуть 239
— собственный 240 Подразделение графа 225
— ребра 225
Подстановка обобщенная 43
— переменпых 17
— сети вместо ребра 238
— формул 22
— функций бесповторная 18 Подформула 15
—, замена 22 Покрытие 311
— неприводимое 316 —, ранг 312
— точечное 311 Поле Галуа 71
Полином Жегалкина (по mod 2)
32
, единственность представления функции 32
— по mod к 69
ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ
377
Полнота 30, 42, 48 —, критерий 42, 56 —, распознавание 51 Полюс 227 Порядок и! 208
Последовательность векторов 74
— входная 76
— выходная 77
— наборов 75
— унимодальная 178 Правило Крамера 71 Предикат р (х) 120
двузначный 120
трехзначный 120
Представление Клини 160 Преобразование значений 61
— квазиосновного кода в основной 141
— основного кода в /-кратный
137
— переменных 61
— решетчатого кода в основной
138
Преобразователь без входов 77
— дискретный 76, 336
— элементарный 343 Префикс, свойство 261
— слова 261
Примитивная рекурсия 146, 147 , схема 147
Принцип подключения-исключения 189, 194 Программа 115 —двойственная 119 Программирование для машин Тьюринга 124 Путь 80, 223 Пучок граней 326
— ребер 79
Разбиения множества 172
, число 183, 184
Разветвление 344 Разложение функции 26, 48 Д-ра з л ожени е 247 р-разложение 247 s-разложение 247 Размещения 171 —, число 174 Ранг грани 308
— конъюнкции 297
— покрытия 312
Расстояние между вершинами куба 293 Расщепление 248, 249
Расщепление, единственность 251
— каноническое 253
, единственность 253
Д-расщеплсние 249 р-ра«цепление 248
в-р ас щеп л енне 249 Ребро 79, 222 Решетка 133
Связка плоскостей 224
Связь между схемами из Ф. Э.
и формулами 344, 345 Сети изоморфные 229
— неизоморфные, число 232, 234 Сеть 227
— бесконечная 227
— внешняя 246
— внутренняя 246
—, геометрическая реализация 227, 228
— двухполюсная 237 —- конечная 227
— логическая 337 тривиальная 337
— неразложимая 242
— однополюсная 230
— разложимая 242
— Д-разложимая 247
— р-разложиман 247
— «-разложимая 247
— связная 237
— сильно связная 240 —степень 233
—, — средняя 233 —, структура степенная 233
— счетная 227
— тривиальная 242 Я-сеть 243 зт-сети 253
—, число 254 Символ пустой 115
— Л 114
Синтез схем из Ф. Э. 345
— — — — —, асимптотически наилучший метод 361
— — — — — —, качество алгоритма 350, 355
.--—, оптимальный по
порядку метод 357 -—, элементарные методы 351 Система замкнутых классов 54
— подмножеств 171
^ функций полная 30, 48
378
ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ
Система функций полная в замкнутом классе 42 Следование логическое 13 Слово 256
— буферное 136 —, длина 256 —, конец 261 —, начало 261
— неприводимое 265 —, префикс 261
— собственное 261 Сложение логическое 13
— по mod 2 13
— n-разрядных двоичных чисел 18, 365
Сложность д. н. ф. 298
— схемы из Ф. Э. 346 Соединение 346
— ребер параллельное 243
последовательное 244
Сообщение 257 Состояние 88, 115
— заключительное 118
— начальное 117 Сочетания 172
— с повторениями 172 ?-------, число 180
—, число 177 Степень набора 233
— сети 233
— — средняя 233 Строение формул 15 Сумматор 364 Суперпозиция сетей 239
— функций 16, 91, 146 Сфера 293
—, радиус 293 —, центр 293
Схема из функциональных элементов 336, 338
минимальная 346
----------, проводимость 340
— кодирования 258
— одновременной примитивной рекурсии 164
— операторная 122
— примитивной рекурсии 147
Теорема Белла 200
— Жегалкина 32
— Журавлева 327 •—Квайна 326
— Клини 165
— Кратко 110
— Кудрявцева НО
Теорема Кузнецова о функциональной полноте 54
— Лупанова 234, 361
— Маркова 264
— Мартина 65
— Мучника 67
— обращения 191
— о разложении функции 26
— о редукции 283
— о функциональной полноте 40, 54 /
— Пикара 64
— Понтрягина — Куратовского 225, 226
— Поста 42
— С лун едкого 64 , обобщение 61
— Ферма 70
— Янова 67 Тождество Белла 200
— Добинского 202 Точка предельная 202
— регулярная 326, 327 Треугольник Паскаля 179
Укладка дерева 231 Умножение логическое 13 Уравнения канонические 88
Формула 14
— бинома Ньютона 180, 196
— Валлиса 209, 211
— включения-исключения 189, 194
— двойственная 24
— каноническая 108
