Дискретка. Учебник издание шестое Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов высших технических учебных заведений
 Скачать 1.99 Mb.
|
|
B ∩ C = ∅. 4. P 1 = {ha, 2i, ha, 3i, ha, 4i, hb, 3i, hc, 1i, hc, 4i}, P 2 = {h1, 1i, h2, 3i, h2, 2i, h3, 4i, h1, 4i, h2, 4i, h4, 2i}. 5. P ⊆ (Z + ) 2 , hx, yi ∈ P ⇔ x 2 > y, где Z + = {x ∈ Z | x > 0}. 6. hC \ R; +, ·, :i. 7. B = hC; +, . ıi, X = R. 8. β = [5, 7, 11, 2], a = 43, b = 74, x = [3, 2, 5, 1]. 9. G 1 : • • • • h h h ? @ @ @ R ? ¡ ¡ ¡ ª 1 2 4 3 G 2 : • • • h h h - A A A 3 2 1 10. G: ¡ ¡ ¡ ¡ ¡ ¡ ©© ©© ©© @ @ @ • • • • • • • • 11. x ↔ y ∧ (y → x), x ∨ (y ⊕ z ↓ x | y). 12. x → y ↓ z и (x → y) ↓ (x → z). 13. (x ↔ y → z) | y. 14. f (0, 1, 1) = f (0, 1, 0) = f (1, 0, 1) = f (1, 1, 1) = 1. 15. (0011 1101 0010 1100). 16. J = {x ∨ y, x ↔ y}. 17. A \ (B \ C) = (A \ B) \ C. Указатель терминов Автоморфизм, 55 Аксиома бесконечности, 44 выбора, 45 замены, 44 математической индукции, 24 множества всех подмножеств, 44 регулярности, 45 суммы, 44 существования пары, 44 пустого множества, 44 экстенсиональности, 44 Аксиомы Дедекинда—Пеано, 24 Цермело—Френкеля, 44 метрики, 131 Алгебра, 52 Кантора, 52 булева, 65 булевых функций, 186 компьютерная, 88 отношений, 70 реляционная, 71 Алгебраическая система, 52 Алгоритм Дейкстры, 134 Евклида, 96 Форда—Беллмана, 133 последовательной раскраски, 160 Алфавит, 40 Антидизъюнкция, 182 Антиконъюнкция, 182 Аргумент, 20 Арифметика многомодульная, 111 модулярная, 100 остатков, 100 по модулю M , 111 Ассоциативность, 14, 65, 186 композиции, 19 Атом, 66 Атомарная формула, 180 Базис, 205 индукции, 24 Биекция, 21 Бином Ньютона, 169 Бит, 88 Булеан, 12 Булева алгебра двойственная, 201 решетка, 64 функция, 183 Булева алгебра, 65 Булево кольцо, 67 УКАЗАТЕЛЬ ТЕРМИНОВ 263 В.у.м., 40 Валентность вершины, 136 Вектор, 37 значений булевой функции, 184 оснований, 110 остатков, 110 Вершина, 115 висячая, 136 графа, 115 достижимая, 127 изолированная, 136 концевая, 136 периферийная, 131 центральная, 132 взвешенная, 132 Вершины взаимно достижимые, 130 смежные, 118 Вес вершины, 120 дуги, 120 маршрута, 132 Ветвь остова, 152 Включение множества, 11 Восьмеричная система, 84 Вхождение переменной, 195 Выборка неупорядоченная, 169 с возвращениями, 170 упорядоченная, 168 с возвращениями, 170 Высказывание, 180 простое, 180 сложное, 180 Гомоморфизм, 54 естественный, 60 Граница, 157 Грань верхняя, 39 нижняя, 39 точная верхняя, 39 нижняя, 39 Граф, 115 ациклический, 140 бесконтурный, 127 бихроматический, 159 взвешенный, 120 гамильтонов, 139 двудольный, 159 неориентированный, 116 ориентированный, 116 планарный, 160 полный, 125 получаемый отождествлением вер- шин, 122 помеченный, 120 разреженный, 121 связный, 127 сильно связный, 127 Графы гомеоморфные, 160 изоморфные, 119 Группа, 53 абелева, 53 коммутативная, 53 симметрическая, 167 Группоид, 53 264 УКАЗАТЕЛЬ ТЕРМИНОВ ДНФ, 189 Двоичная система, 83 Декартова степень множества, 16 Декартово произведение алгебр, 62 множеств, 16, 61 отношений, 70 Декомпозиция функции, 206 дизъюнктивная, 207 нондизъюнктивная, 207 простая, 208 функциональная итеративная, 210 множественная, 210 Делитель, 93 наибольший общий, 94 Дерево, 140 бинарное, 151 остовное, 141 упорядоченное, 149 Диагональ, 18 Диаграмма Хассе, 42 Эйлера—Венна, 13 Диаметр графа, 131 Дизъюнкт, 188 Дизъюнктивная нормальная форма, 189 минимальная, 196 совершенная, 190 сокращенная, 195 тупиковая, 196 Дизъюнкция, 180 элементарная, 188 Дистрибутивность, 14 Длина маршрута, 126 слова, 40 Домен, 70 Дополнение графа, 123 множества, 13 функции, 186 элемента, 64 Дуга, 115 графа, 115 заходящая в вершину, 115 инцидентная вершине, 119 исходящая из вершины, 115 Дуги кратные, 116 Единица моноида, 53 решетки, 63 частично упорядоченного множества, 39 Задача коммивояжера, 140, 144 нахождения остова минимального веса, 142 о безопасном хранении ключа, 105 о кенигсбергских мостах, 137 Закон двойного отрицания, 14, 66, 186 де Моргана, 14, 66, 186 дистрибутивности, 14, 65, 186 идемпотентности, 14, 65 нуля и единицы, 14, 66 УКАЗАТЕЛЬ ТЕРМИНОВ 265 поглощения, 14, 66, 186 Значение терма, 58 функции, 20 Идеал, 68 главный, 68 Идемпотентность, 14, 186 Изображение графа, 115 плоское, 160 Изоморфизм, 55 частично упорядоченных множеств, 43 Изоморфные системы, 55 частично упорядоченные множества, 43 Импликанта простая, 195 формулы, 195 функции, 195 Импликация, 180 Инверсия, 180 Инвертор, 206 Индукционный шаг, 24 Интерпретация, 52, 181 Инфимум, 39 Инцидентор, 116 Инъекция, 20 Источник, 133 КНФ, 189 Кардинал, 26 Каркас графа, 141 Карта Карно, 198 декомпозиции, 208 Квазипорядок, 37 Класс функций линейных, 203 монотонных, 203 самодвойственных, 202 эквивалентности, 35 Классы Поста, 202 Кограница, 157 Код двоичный, 82 Кольцевая сумма графов, 123 формул, 182 Кольцо булево, 67 вычетов по модулю m, 100 целых чисел, 76, 78 Комбинаторика, 165 Коммутативность, 14, 65, 186 Композиция графов, 125 отношений, 19 Компонента связности, 127 сильной, 127 сильная, 127 Компьютерная алгебра, 88 Конгруэнция, 59 единичная, 64 нулевая, 64 Конец ребра, 116 Конкатенация, 53 266 УКАЗАТЕЛЬ ТЕРМИНОВ Константа, 22, 51, 52 0, 185 1, 185 Константный символ, 51 Конституента единицы, 190 нуля, 190 Контакт, 213 замыкающий, 213 размыкающий, 213 Континуум, 26 Контрпример, 220 Контур, 127 Конфигурация комбинаторная, 165 Конъюнкт, 188 Конъюнктивная нормальная форма, 189 минимальная, 197 совершенная, 190 Конъюнкция, 180 элементарная, 188 Координата, 16 слова, 40 Коранг, 141 Корень дерева, 143 упорядоченного, 149 характеристический, 174 Кортеж, 16 Коцикл, 154 Коэффициент биномиальный, 169 полиномиальный, 171 Л.у.м., 38 Лемма о рукопожатиях, 137 Лес, 140 упорядоченный, 149 Литера, 188 Литеры контрарные, 188 МДНФ, 196 МКНФ, 197 Маршрут, 126 кратчайший, 132 циклический, 126 Математика дискретная, 6 непрерывная, 6 прерывная, 6 Матрица Квайна, 197 бинарного отношения, 31 весов, 120 достижимости, 129 инцидентности, 119 контрдостижимости, 130 программируемая логическая, 218 расстояний, 131 связности, 129 смежности, 118 соединений, 218 фундаментальных разрезов, 155 циклов, 152 Метод Квайна, 196 бинарный, 102 Многообразие, 62 УКАЗАТЕЛЬ ТЕРМИНОВ 267 Многочлен характеристический, 174 Множества равномощные, 26 равные, 11 совпадающие, 11 эквивалентные, 26 Множество, 10 бесконечное, 26 континуальное, 26 счетное, 26 вполне упорядоченное, 40 вычетов, 99 действительных чисел, 81 коконечное, 69 комплексных чисел, 82 конечное, 26 коциклов фундаментальное, 155 линейно упорядоченное, 38 натуральных чисел, 23, 24 пустое, 12 рацинальных чисел, 79 строго включенное, 12 универсальное, 12 фундаментальных циклов, 152 целых чисел, 78 по модулю m, 99 циклов фундаментальное, 152 частично упорядоченное, 38 Множество-степень, 12 Модель, 52 Моноид, 53 Мономорфизм, 54 Мощность алгебраической системы, 52 множества, 26 Мультиграф, 116 неориентированный, 117 реберный, 159 эйлеров, 138 Мультиграфы изоморфные, 119 Мультиплексор, 217 Набор длины n, 16 остатков стандартный, 110 цепей, покрывающих граф, 139 Наибольший общий делитель, 94 Наименьшее общее кратное, 95 Неорграф, 116 ациклический, 126 связный, 127 соответствующий данному оргра- фу, 117 Неравенство Бернулли, 25 треугольника, 131 Нормальная форма дизъюнктивная, 189 минимальная, 196 сокращенная, 195 тупиковая, 196 конъюнктивная, 189 минимальная, 197 Носитель алгебраической системы, 52 Нуль решетки, 63 частично упорядоченного множества, 39 268 УКАЗАТЕЛЬ ТЕРМИНОВ Область значения, 18 определения, 18 Образ гомоморфный, 54 множества, 19, 22 Обратное отношение, 19 Обхват графа, 126 Обход графа по глубине, 143 по ширине, 143 Объединение графов, 123 конгруэнций, 64 отношений, 70 функций, 186 элементов решетки, 63 Объединение множеств, 12 Ограничение отображения, 22 Операция n-арная, 22 n-местная, 22 бинарная, 22 возведения в степень, 27 выбора, 71 добавления вершины, 122 дуги, 122 кольцевого сложения, 68 кольцевого умножения, 68 конкатенации, 53 логическая, 180 на множестве ассоциативная, 53 отождествления вершин, 122 подразбиения ребра, 160 проекции, 72 сложения, 25, 27 соединения, 72 стягивания дуги, 122 удаления вершины, 122 дуги, 122 умножения, 25, 27 унарная, 22 Определение индукционное, 24 Орграф, 116 Ортогональные подпространства, 158 Основание счисления, 83 Остаток, 94 Остов графа, 141 Отношение, 17 n-местное, 17 Парето, 39 антирефлексивное, 33 антисимметричное, 33 асимметричное, 33 бинарное, 17 иррефлексивное, 33 на множестве, 17 обратное, 19 полное, 18 рефлексивное, 33 симметричное, 33 тождественное, 18 транзитивное, 33 унарное, 17 универсальное, 18 эквивалентности, 35 УКАЗАТЕЛЬ ТЕРМИНОВ 269 Отношения совместимые, 70 Отображение, 20 Отрицание, 180 ПЛМ, 218 Перевод дробных чисел, 87 целых чисел, 86 Переменная логическая, 180 Пересечение графов, 123 конгруэнций, 64 множеств, 12 отношений, 70 функций, 186 элементов решетки, 63 Перестановка, 165 Перешеек, 138 Период дроби, 81 Петля, 118 Плоское изображение графа, 160 Поглощение, 14 Подалгебра, 57 Подграф, 121 Поддерево левое, 151 правое, 151 упорядоченное, 149 Подмножество, 11 собственное, 12 Подмодель, 57 Подпространства ортогональные, 158 Подсистема, 57 порожденная множеством, 57 Подстановка множества, 21, 166 Покрытие множества, 15 Поле действительных чисел, 80 комплексных чисел, 82 конечное, 101 рациональных чисел, 79 характеристики нуль, 101 Полином Жегалкина, 203 линейный, 204 нелинейный, 204 Полное отношение, 18 Полугруппа, 53 Полустепень захода, 137 исхода, 137 Полюс, 212 входной, 213 выходной, 213 Пометка, 120 Порядок двойственный, 38 лексикографический, 40 линейный, 38 полный, 40 строгий, 38 частичный, 38 Последователь, 121 вершины, 118 Последовательность, 22 возвратная, 174 фундаментальная, 80 Поток в сети, 153 Правило 270 УКАЗАТЕЛЬ ТЕРМИНОВ Паскаля, 169 произведения, 28 степени, 28 суммы, 28 Предикат, 17 на множестве, 17 Предпорядок, 37 Представление со смешанными основаниями, 112 Предшественник вершины, 118 Принцип двойственности для булевых функций, 201 математической индукции, 24 полного упорядочения, 45 полной индукции, 26 трансфинитной индукции, 45 Программируемая логическая матри- ца, 218 Проекция, 20 Произведение алгебр, 62 бинарных отношений, 19 векторов внутреннее, 157 графов, 123 множеств, 13 декартово, 16, 61 прямое, 16 остатков, 100 отношений декартово, 70 списков, 92 элементарное, 195 Прообраз множества, 19 Противоречие, 187 Путь, 127 Радиус взвешенный, 132 графа, 132 Разбиение множества, 15 упорядоченное, 170 Разложение Шеннона, 191 Размещение, 168 с повторением, 170 Разность множеств, 13 симметрическая, 13 отношений, 70 Разрез графа, 154 простой, 154 фундаментальный, 155 Ранг коциклический, 141 циклический, 141 Раскраска вершин графа, 158 ребер мультиграфа, 159 Распределение меток, 120 вершин, 120 дуг, 120 Расстояние, 131 взвешенное, 132 Реализация декомпозиционная, 206 Решение общее, 174 частное, 175 Решетка, 63 булева, 64 УКАЗАТЕЛЬ ТЕРМИНОВ 271 дистрибутивная, 64 конгруэнций, 64 подсистем, 63 элементов &, 218 Решето Эратосфена, 98 СДНФ, 190 СКНФ, 190 Свойство, 17 делимости, 94 евклидовости, 94 Связка, 180 Сегмент начальный замкнутый, 43 открытый, 43 Сеть, 153 k-полюсная, 212 Сигнатура, 51 предикатная, 52 функциональная, 52 Система, 52 Дедекинда—Пеано, 76 аксиом ZFC, 45 алгебраическая, 52 булевых функций полная, 202 неотрицательная, 108 остатков наименьших по абсолютной ве- личине, 100 неотрицательных, 100 полная, 100 симметричная, 100, 110 симметричная, 108 счисления восьмеричная, 84 двоичная, 83 позиционная, 82 смешанная, 85 шестнадцатеричная, 84 числовая наименьшая неотрицательная, 110 наименьшая по абсолютной ве- личине, 110 Системы изоморфные, 55 Слово, 40 пустое, 40 Сложение логическое, 182 по модулю 2, 182 Сложность (1, 1)-полюсника, 214 булевой функции, 214 схемы из функциональных элемен- тов, 216 функции, 217 Смешанная система счисления, 85 Соединение графов, 123 контактов параллельное, 213 последовательное, 213 Сомножитель, 96 Соответствие, 17 взаимно однозначное, 21 Соотношение рекуррентное, 174 Сочетание, 169 272 УКАЗАТЕЛЬ ТЕРМИНОВ с повторением, 170 Список дуг, 121 над множеством, 90 пустой, 90 уступчатый, 150 Степень вершины, 136 Стрелка Пирса, 182 Структура, 52 смежности, 121 Сумма кольцевая, 182 множеств, 13 кольцевая, 13 остатков, 100 списков, 92 Суперпозиция функций, 185 Супремум, 39 Схема X n -функициональная минимальная, 217 X n -функциональная, 216 из функциональных элементов, 215 контактов, 213 электрическая, 213 Сюръекция, 21 Таблица Кэли, 53 истинности, 181, 184 Тавтология, 187 Теорема Биркгофа, 62 Дедекинда—Пеано, 76 Жегалкина, 203 Кантора, 29 Кантора—Бернштейна, 27 Квайна, 196 Понтрягина—Куратовского, 161 Поста, 205 Стоуна, 66 Ферма малая, 102 Шеннона вторая, 192 первая, 191 арифметики основная, 97 о гомоморфизме, 60 о единственности неприводимого раз- ложения, 97 о сравнении множеств, 27 о существовании неприводимого раз- ложения, 97 о функциональной полноте, 192 о четырех красках, 162 об остатках китайская, 104 Терм сигнатуры Σ, 58 Тождественное отношение, 18 Тождество сигнатуры Σ, 62 Толщина графа, 162 Транспозиция, 168 Универсальное отношение, 18 Универсум, 12 алгебраической системы, 52 Уравнение линейное диофантово, 95 рекуррентное, 174 линейное неоднородное, 175 Утверждение двойственное, 67 УКАЗАТЕЛЬ ТЕРМИНОВ 273 Фактор-алгебра, 60 Фактор-множество, 35 Факториал, 25 Фильтр, 69 Фреше, 69 главный, 69 двойственный к идеалу, 69 Форма нормальная дизъюнктивная, 189 совершенная, 190 конъюнктивная, 189 совершенная, 190 Формула алгебры логики, 180 атомарная, 180 выполнимая, 187 общезначимая, 187 опровержимая, 187 представляющая функцию, 184 тождественно истинная, 187 тождественно ложная, 187 включений и исключений, 172 рекуррентная, 174 Формулы эквивалентные, 186 Функция, 20 n-местная, 22 алгебры логики, 183 биективная, 21 булева, 183 двоичная, 183 двойственная, 201 индикаторная, 29 инъективная, 20 линейная, 203 монотонная, 203 на, 21 переключательная, 183 проводимости, 213 разложимая, 205 разнозначная, 20 реализуемая (1, k)-полюсником, 214 схемой, 216 самодвойственная, 201 сохраняющая единицу, 202 нуль, 202 ставящая в соответствие элементу элемент, 20 сюръективная, 21 частичная, 20 Характеристика поля, 101 Хорда, 152 Целая часть числа, 92 Центр графа, 132 Цепи покрывающие, 139 Цепь, 126 гамильтонова, 139 простая, 126 эйлерова, 139 Цикл, 126, 167 гамильтонов, 139 простой, 126 фундаментальный, 152 эйлеров, 138 Цифра, 83 Ч.у.м., 38 274 УКАЗАТЕЛЬ ТЕРМИНОВ Частичная функция, 20 Частичный порядок, 38 Частное, 94 пробное, 92 Часть графа, 121 числа целая, 92 Числа Фибоначчи, 174 взаимно простые, 95 Число базисное, 83 вещественное, 81 действительное, 80 иррациональное, 81 кардинальное, 26 комплексное, 82 натуральное, 23 перестановок, 165 планарности графа, 162 разбиений, 171 неупорядоченных, 171 упорядоченных, 171 размещений, 168 с повторениями, 170 рациональное, 79, 81 с плавающей точкой, 89 нормализованное, 89 сочетаний, 169 с повторениями, 170 хроматическое, 158 целое, 78 длинное, 91 короткое, 91 неразложимое, 96 простое, 97 разложимое, 96 составное, 96 цикломатическое, 141 Член числа старший, 112 Шестнадцатеричная система, 84 Штрих Шеффера, 182 Эквивалентность, 35, 181 Эквивалентные (1 |