Гаврилов Г.П., Сапоженко А.А. - Задачи и упражнения по дискретной математике, страница 85

(Ч1, ЧП1) ЗЗ. Яблонскии С. В. Функциональные построения в Ь-злачной логике,1/ Труды МИАН СССР. 1958. Т. 51. С. 5 — 142. (1 — П1, У1, 1Х, Х) 34. Яблонский С.В. Введение в дискретную математику. — — Мл Наука,. 1986. (1 — Х) 35. Яблонский С. В., Гаврилов Г. П., Кудрявцев В. Б. Функции алгебры логики и классы Поста. Мл Наука, 1966.

(1, .П) 36. А1оп Ко Брепсег д. ТЬе РгоЬаЬ111всю МеХЬос1. Л. ЪЪГ11еу Зс Вопя, 2000. (Ъг1, У111) 37. Войобав В. Напбот СгарЬв. — ИХл Асабеш1с Ргевв, 1985. (Ъг1, Ъ'П1) Предметный указатель Автомат без входа 147 выхода 146 Алгоритм Квайна 297 Алфавит входной 103 --. выходной 103 — кодирующий 230 — — машины Тьюринга внешний 182 — -- — внутренний 182 Арность функционального символа 10 Базис замкнутого класса 60 схемы 311 Буква (символ) алфавита 102 Вектор значений булевой функции 11 коэффициентов полинома 53 Вершины графа смежные 203 Вес набора 9 — о.-д, функции 103 Глубина формулы 30 Грань булева куба 290 ---плоского графа 216 Граф 203 двудольный 205 кубический 205 направленный 210 однородный (регулярный) 205 ориентированный 210 планарный 215 полный 205 пустой (вполне несвязный) 205 связный 204 ..

й-связный 206 Графы гомеоморфные 205 изоморфные 204 Дерево 205 — бесконечное информативное 104 корневое 219 растущее 212 Леревья одинаковые 220 Диаметр графа 204 Лизъюнкция 12 над множеством переменных 47 -- элементарная 47 Ллина д.н.ф. 47 к.н. ф. 47 Длина маршрута 204, 211 — слова 102 теста 291 Лополнение графа 205 Замыкание множества функций 60 Знак условного равенства 181 Зона работы мапзины Тьюринга 181 Избыточность кода 235 Импликанта 296 --простая 78, 296 ядровая 296 Имплнкация 12, 89 Интервал функдин максимальный 296 ядровый 296 Инцидентность вершины и ребра 203 Источник орграфа 212 Итерация машины Тьюринга 186 Класс вычислнмых функций 196 общерекурсивных функций 196 . — предполный 60 — примитивно рскуреивных функций 196 ".

функционально замкнутый 60 частично рекурсивных функций 196 Код алфавитный 230 — дерева 220 набора основной машинный 190 решетчатый 191 префиксный 231 Композиция машин Тьюринга 186 Предметный указатель 415 Компонента снязности графа 204 Конденсация орграфа 212 Контакт замыкаюший 312 размыкаюший 312 Контур в орграфе 211 Конфигурация машины Тьюринга 179 Конъюнкция 11 над множеством переменных 47 -- элементарная 47 монотонная 52 Критерий планарности 216 Саломаа 97 Слупецкого 97 Яблонского 97 Лемма Бернсайда 274 о нелинейной функции 68 — — немонотонной функции 75 несамодвойственной функции 64 Лес 205 Максимум в и у 89 Маршрут в графе 204 орграфе 211 Метод Блейха 296 минимизирующих карт 298 Нельсона 297 неопределенных коэффициентов 53, 94 Хэмминга 245 Минимум х и у 89 Мультиграф 203 -- ориентированный 210 планарный 215 Набор булев (двоичный) 9 , предшествующий набору 10 Наборы булевы противоположные 9 соседние 9 сравнимые 10 Неравенство Чебышева 279 Объединение графов 205 Оператор, порожденный функциями 120 Операция введения обратной связи 146 — минимизация 196 объединения д.

функций 147 отождествления переменных 33, 146 Операция примитинной рекурсии 195 —. разветвления выхода 149 -- суперпозиции 147 удаления выходной переменной 146 Орграф 203 транзитивный 215 Отрицание Лукасевича 88 Поста 88 т 11 Отросток в сети 223 Ошибка в ханале связи 245 Паросочетание 205 Переменная существенная ЗЗ вЂ” фиктивная 33 Подграф 204 останный 204 порожденный подмножеством вершин 204 Подразбиение графа 205 Подфункция 39 Покрытие матрицы 290 Полинам 7Кегалкина (по модулю 2) 52 Полинам по модулю к 93 Полустепень захода 211 -- исхода 211 Профикс (начало) слова 103, 230 Принцип двойственности 31 Произведение по модулю й 89 Псевдограф 203 — ориентированный 210 Путь н орграфе 211 Разветнление машин Тьюринга 186 Разность по модулю л.

89 -- усеченная 89 Ранг элементарной конъюнкции 47 Расстояние Хэмминга 9 Ребра кратные (параллельные) 203, 210 Связка логическвл 12 Сеть 219 — разложимая 223 - к-полюсная 219 Система Поста 97 Россера — Туркетта 97 функционально полная 60 Слово бесконечное 102 -- хвазипериодическое 102 416 Прееметнььй указатель Слово пустое 102, 180 Сложность д. н. ф.

47 Слой булева куба 9, 247 Соединение слов 102 Степень вершины графа 203 Сток орграфа 212 Стрелка Пирса 12 Сумма по модулю 2 12 ---к 89 Суперпозиция сетей 224 функции 14, 195 Сфера в булевом кубе 241 Схема, реализующая функцию 145 Таблица каноническая 130 критериальнэя 81 Теорема Визинга 217 †. Кенига 205 о представлении вычислимой функции 196 — Пикар 97 Поста (критерий полноты в алгебре логики) 81 .

Шеннона 217 Тост 291 Точка сочленения (разделяющая вершина) 206 Турнир 212 5еравнения канонические 128 Форма дизъюнктивная нормальная 47 -. - -. кратчайшая 296 минималъная 296 - . — совершенная 40 - -. сокращенная 296 тупиковая 296 «онъюнктивна» нормальная 47 совершенная 40 -- й-значной функции вторая 91 первая 91 Формула над множеством связок 13 функциональных символов 12 --- Стирлинга 278 Формулы одинакового строения 14 эквивалентные 14 Функции конгруэнтные 60 равные 31 Функции эквивалентные (неразличимые) 103 Функция автономная (константная, без выхода) 123 . булева 1булевская, алгебры логики) 10 , двойственная к функции 31 линейная 68 монотонная 75 самодвойственная 31, 64 симметрическая 21 , сохраняющая константу 72 шефферова 81 -- - " элементарная 11 — Вебба 89 выходов 127, 179 вычислимая 196 детерминированная 1()3 ограниченно-детерминированная 103 переходов 127, 179 проводимости 312 , реализуемая формулой 13 --.

1е-значной логики 88 , сохраняющая множество 92 разбиение 93 — характеристическая второго рода 88 первого рода 88 — -- элементарная 88 ." й-фактор графа 205 Центр графа 223 Цепь в графе 204 Цикл в булевом кубе 242 графе 204 е4исло кликовое 216 реберно-хроматнческое 216 -- хроматическое 216 Шар в булевом кубе 241 Штрих Шеффера 12 Эквивалентность машин Тьюринга 181 Эквиваленция 12 Элемент единичной задержки 151 )к~ --.

минимальное целое число, не меньшее к 64 я-сеть 224 .