С.В. Яблонский - Введение в дискретную математику (1060464), страница 56
Текст из файла (страница 56)
Э. 347 — точек а слое л-мерного куба 179, 182, 183 — туйаковых покрытий 194, 196 — упорядоченаых покрытай 195 — функций з-зпачпой логика от к переменных 44 -е 174 — я-сетей 254 Члены ккформационаые 290 — ковтрольпые 290 Шар 293 †, радиус 293 †, центр 293 Экакзалепткость аскмптотаческая 204, 355 — деревьев 83 — с точвостью до порядка 205, 355 — — — — — абсолютных величав 203 — формул 20 Элемеат 336 †функциональн 336 Энтропия 236 Ядро 325 Язык операторный 121 Ярус 79 Ячейка ленты 115 — — начальная 1!7 — - пустая 119 УКАЗАТЕЛЬ ОБОЗНАЧЕНИЙ Е< — мыожество (О, Ц 9 Р< — система всех функций алгебры логики 10 р<(в) — число Функций вз Рь зависящих от а перемеккыт 11 й — отрицание з 13 з«азз — конъюнкция з< в з< 13 в< ~1 зз — дизъюякция з< и з< 13 з«- зз — аппликация з< и зз 13 з< + яз — сложеиие по шоб 2 13 з</зз — функция Шеффера 13 6(1<, ..., 1<) — Формула 6 построена иэ фуыкций 1<, ..., 1, 15 6(з<, ..., з») — формула 6 содержит перемеыыые зь ..., з» (а ые содержат других) 15 6 СНь Ь ", 1,) — форыула 6 имеет строение С 15 6 6 — формулы 6 и 6 эквивалентны 20 Г' » — фуыкция, двойственная фувкцив 1 23 " — формула, двойственная формуле 6 24 за 25 а< <а ...
з< — полипом Жегалкпва 32 (<,...Зд й<) — аамыкаиие множества 6) 33 — класс всех линейных функций ЗЗ Т< — класс всех функций, сохраняющих коястапту 0 ЗЗ Т< — класс всех функций, сохранлющвх константу 1 34 Š— класс всех самодвойствепвых функций 34 а — векторная запись набора 36 ~ — отиошеыие предшествовапия 36 3( — класс всех монотонных функций 36 Е» — множество (О, 1, ..., « — Ц 43 Р< — система всех функций й-скачкой логики 44 й — обобщение отрицания в смысле циклического сдвига зпачевпй 45 з †отрицан Лукашевича 45 1<(з) — фуякция, обобщаюзцая векоторые свойства отрпцаиав 45 1<(з) — характеристическая функция аыачеиив 1 45 ш<п (з<, з<) — обобщевае ковъювкции 45 з<зз(шоб й) — второе обобщение конъюнкции 45 шах (*ь зз) — обобщение дизъюпкции 45 з, +зз(шоб)<) 45 Ь, ь < (з) 49 »(з<, *з) — фувкцвя Вебба 50 аз<(з, ..., я,) — функцив, раввая з< 51 6)„з — мвожество всех фуыкций из 6<, зависящих от переменных зь ..
» зз 51 Уклзлтель ОБОзнАчений й — пустое множество 52 ]О( — число элементов множества О 57 з<'»<о<ад — максимум иа миол<естве (О, Ц Х (О, Ц 62 а<3<о<ад — мвпвмум иа множестве (О, Ц Х (О, Ц В2 ]а[ — наименьшее целое чвсло, ве мевьшее а 68 С вЂ” операция суперлозиции 73 (Рд, С) — алгебра логики 73 (Р», С) — й-злачная логика 73 Р , С) — счеткозначиая логика 73 "о )( — расширеииый натуральный ряд 73 ( Р, С) — ковтияуумзвачпая логика 73 с' Š— мволсество всех й-звачкых последовательностей 73 с,ь Р— множество всех функций, определенных иа наборах < а с компонентами ва Е и прииииающих авачеппя из Е 73 » <.
а Рдл — Миажсство вСеХ ДетЕрмияврозавкых функций взР 75 с,ь (о — детермиввровавиая функция, соответствующая функции Ф вз Р» 77 У» — множество всех функций ге, Ф ш Р» 78 Р,дд — множество всех огравичевво-детерминированных фупкций из Рд,» 86 р(а, я, г) — число о.-д. функций иа Р„,», зависящих от и переменных и имеющих вес г 87 Х вЂ” перемениая, описывающая аначение входной величины 83 Π— перемеииая, описывающая авачеиие состояпия 88 2 — перемеипая, описывающая значение выходной величины 88 Π— операция введеввя обратной связи 94 з — о.-д.
функция, сдвигающая входную последовательность па одив разряд 94 (Род», С, О) 105 (ко», С) 106 Род,», С) 110 Род,», О) 110 Л вЂ” символ, обозначающий отсутствие икформацив Ц4 ... а<<аз ... — головка в данный момент обозревает символ а< 118 То — программа, двойственная программе Т 119 р< — оператор проверки логических условий 122 рт †операт проверки логических условий 122 1 е — специальный оператор 122 м — специальпый оператор 122 Е< — подмножество ваборов, па котором определена функция г' 143 Р' -множество всех частичных функций счетвоавачвой лад„ гики 143 Родо — класс всех вычислимых функций 144 3(д) — фуикция, равная д+ 1 145 удд [г, ..., д„) — фуикция, равпая з~ 145 Пр — операция примитивной рекурсии 146 в олерацвв миикмиаацив 146 УКАЗАТЕЛЬ ОБОЗНАЧЕНПИ Р,р — класс частично-рекурсивных функцвй 149 Р, — класс рекурсивных функций 149 Раг — класс примитивно-рекурсивных функций 149 88 (а) 149 88 (е) 149 а/2) — целая часть з 149 * — покааательная функция 149 з1 ° ат — умножение 149 е, — 'эг 149 л~ — '1 150 р(а) 162 ба(*ь ..., аа) 162 п(з„зт) — йеановская функция 162 2(з) 162 «( ) 162 Цэ) 163 г(а) 163 Ю 171 Е" — л-ыерный куб раамера й 172 (л)ь — число раамещений иа я элементов по 5 174 ~) л '1 «) — число сочетаний из л элементов по 5 177 ̈́— число сочетаний с повторениями вэ л элементов по й 180 а Ф(л, й) — число разбиений ыножества иа л элементов ва 5 непустых частей (чвсло Стирлинга 2-го рода) 483 Ф(л) — число всех разбиений множества иэ л элементов на непустые часта (число Велла) 183 6 — число функций из Рь существенно зависящих от л переыенных 190 5(л) — число всех тупиковых покрытий множества из л элементов 196 Ео(л) 197 /„— числа Фвбоначчн 198 /(з) 0(л(я)) 202 /(з) л(а) — равенство абсолютных величин /(а) в 6(з) с точностью до порядка 203 /(а) о(д(е)) 203 /(л) 8(з) — /(з) эквивалентна (асимптотвчески раааа) л(э) 204 /(а) ъ., (а) — /(х) не больше Л(з) по порядку 204 /(х) ~ л(а) — /(э) аслмптотвчески не больше л(э) 204 /(з) Х Х(а) — /(з) равна Л(а) по порядку 205 Аа а.
— ПутЬ, СОЕднвя|Ощнй ВЕРШИНЫ а~ И аг 223 7(5) — максимальное число попарно неиаоморфных графов без взолированных вершин с й ребрами 226 52(Еы Еь Еь ...) — сеть с набором полюсов Ее 227 <Е> — множество объектов ие набора Е 228 6(5) — максимальное число попарно неиаоьсорфных деревьев с И ребрами 232 га — степень сети 233 (Аь йе,..., /м) — степенная структура сети 233 УКАЗАТЕЛЬ ОБОЗНАЧЕНИЙ к — средняя степень сети 233 3(е«, Ьь ..., Ь ) — максимальное число попарно неиэоморфных сетей беэ иаолврованных вершин, имеющих ««полюсов и степеяную структуру (Ь«, Ь ) 234 3(««, к, т, Ь) — максимальное число попарно неизоморфных сетей беэ изолированных вершин, имеющих е«полюсов, среднюю степень к, максимальную степень ю и число наборов Ь 234 Г(а, Ь) — сеть ив двухобъектных наборов с полюсами а и 5 237 Гэ(а, Ь) — параллельное соединенве Ь ребер 243 Г'(а, 5) — последовательное соединение Ь ребер 244 я(Ь) — максимальное число попарно неиэоморфных яюетей с Ь ребрами 254 1(А) — длина слова А 256 3(Я) †множест всех непустых слов в алфавите Я 257 Ва(6) — обреа множества 3(Я) при алфавитном кодировании 260 5 — длина слова В« ...
В„ т. е. схемы 2 263 й — длина слова В« 283 И' 263 Вл(Я) †множест всех непустых слов в алфавите й, имеющих длину, ве превосходящую В 264 1,р — средняя длина слова 276 (« †средн длина слова длв оптвмального кода 277 9«280 Нт« — множество наборов кода Хэмминга 291 р((У, ~)") — расстояние мел«ду точками ()' и ()" в кубе 293 (гэ«(() ) — шар с центром в (1«и радиусом р 293 Уэ«(() ) — сфера с центром в 6«и радиусом р 293 5(Я) — вндекс простоты, «сложность«д. н.
ф. Я 298 5«(Я) — число букв переменных в эаииси д. н. ф. Я 298 5«(Я) — чвсло элементарных конъюнкций в Я 298 5«(Я) — число символов — в Записи д. н. ф. Я 299 В" — в-мерный единичный куб 307 )Уа — множество, соответствующее кояъюнкцип К 308 Вк — мнол«ество соответствующее конъюнкции К 308 Яс — сокращенная д. н. ф. 313 Яка — д. в. ф. Квайка 326 Ятз — д. н. ф, тапа ЪГ 326 В„(Ь«д«) — окрестность порядка и максимальной грани )Уд« 331 27л,..., и; з,..., «1 — схема па Ф.Э. с выходамп э « и выходами э,, ..., «, 339 а Ф вЂ” класс всех схем иэ Ф.
Э. над )г 344 Ф« — подкласс всех схем нэ Ф. Э. иад г" с одним выходом л беэ ветвления выходов элементов 344 ЦХ) — число элементов в схеме 2 346 В«(э, р, Ь) — число соединений с л входами, р выходамв и Ь элементами 347 3«(а, р, Ь) — число минимальных схем иэ Ф. Э. с л входами, р выходамв и Ь элемевтав«и 347 ппдпдткпь опозпдчпппп Е(!) — сложность мавамальной схемы для фувкцвв ! 350 Б(л) -функция Шеннона 350 Ел(л) — функция Шеннона 350 Е" — мвогополвсваи, реалиаувщкй множество всех коньвнкПвй 353 (7„-универсальный мвогополвсвии длв множества всех булевых фувкцай от я переменных 358 31 < (и, ...,*„) — свмметраческая функция с рабочими (з,-, г числами 10 ..., 1, 307 Учебное издание Яблонский Сергей Всеволодович ВВЕДЕНИЕ В ДИСКРЕТНУЮ МАТЕМАТИКУ Редактор Ж.И. Я«саге«а Художественный редактор Ю.Э.
И«оно«а Технический реда(гор ДА. Ос«иннино«а Липензия НД № 06236 от 09.11.2001 Нзд. № ФМ-2!5. Поди. а печать 07.072003. Формат 60х90(lи Бум. газетнаа. Гарнитура «Таймс». Печать офсетная Объем: 24,0 уел. печ. л., 24,50 уел. кр.-отт., !9,76 уч.-изд. л.
Тираж 8000 экь Заказ № 2973 ФГУП «Изаатсльспю «Высшая шмтвь 127994, Москва, ГСП-4 Неглинная ул., 29П4 Тел. (095) 200-04-56 Е-шай: ! пбз(фт-з)(1(о! алп Ыр:((а«шн.т-зЫ(о! ало Отдел реаиаоиии( (095) 200.07.69, 200-59-39, факс (095) 200 03-01 Е-ша11: за!езбйвз)йо!алп Отдел «Книга-почтой»( (095) 200-33-36 Е-шай: Ьоо!(розафч-зЫ(о!алп Отпечатано с готовьж днапозвгияоа яо ФГУП ИПК «Ульякояский Дом печати», 432980, г. Ульяаоаск, ул. Гончарова, 14 БВ)Ч 5-06-004681-8 !!!!!!!!!! .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
