С.В. Яблонский - Введение в дискретную математику

ВЫСШАЯ МАТЕМАТИКА Вод общей редакцией академика Российской Академии наук В.А.Садооничего Архипов Г.И., Садовничий' В.А,, Чубариков В.Н. Лекции по математическому анализу Виноградов И.лч. Элементы высшей математики (Аналитическая геометрия. Дифференциальное исчисление. Основы теории чисел) Привалов И.И. Введение в теорию функций комплексного переменного Садовничий В.А. Теория операторов Гошков С.Б., Чубариков В.Н. Арифметика.

Алгоритмы. Слолпгость вычислений Нечаев В.И. Элементы криптографии. Основы теории защиты информации Виноградово И.А., Олехник С.Н., Садовничий В.А. Задачи и упражнения по математическому анализу Бахвалов Н.С., Лапин А.В., Чиэсонков Е.В. Численные методы в задачах и упражнениях Яблонский С В. Введение в дискретную математику Благодшнских В.И. Введение в оптимальное управление (линейцая теория) С.В. Яблонский ВВЕДЕНИЕ В ДИСКРЕТНУЮ МАТЕМАТИКУ Издание четвертое, стереотипное Допущено Министерством образованнк Росснаскоа Фепермщн в качестве учебного пособпа длк студентов вузов, обучазощнлск по специальности «Првкладвак математвка» ф Москва «Высшая школа» 2003 УДК 519,6(075.8) ББК 22.18 Я 14 Яблонский, С.В. Я 14 Введение в дискретную математику: Учеб.

пособие для вузов /Под ред. В.А. Садовиичею. — 4-е изд., стер.— М.: Вмсш шк.; 2003. — 384 с. 18ВХ 5-06-004681-8 Книга является введением в дискретную математику — раздел приклеивай матемазики, бурно развиваюшийся в последиие годы и являюшийся базой для математической кибериепши. Оиа иаписаиа иа основе курса лекций, который автор читал в течение ряда лет иа факультете вычислительной математики и кибернетики Московского госуларствеииого уииверсизета.третье изделие вышло в 2ЕО1 г. Дея студентов вузов, а такзсе кмхенеров н и специалистов, рабопюкнцкх в области прикеадной математики. УДК 519.6(075.8) ББК 22.18 18В)з( 5-06-004681-8 О фгуп «Издательство а Высшая школы>, 2003 Оригинал-макет даииого издания является собственностью издательства еиысшая школаз, и его репродуцирование (воспроизведеиие) любым способом без согласия издательства запрещается.

ОГЛАВЛКНИж 06 авторе Предисловие ЧАСТЬ 1 ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ Глава 1. Алгебра логввв $1. Функции алгебры логики 2 2. Формулы. Реааиеация фуваций формулами $ 3. Эквивалентность формул. Свойства ааементарных функций. Принцип двойственности $4. Рааложевие булевых фуккпдй по перемеввым. Соаершеивая дваъюнктввиак нормальная форма $5. Полнота и аамквутость 2 6. Важнейшие аамкиутые классы.

Теорема о полноте 1 7. Представление о рееукьтатах Поста 20 25 30 ЗЗ 42 43 48 51 56 65 Г а а а а 3. Огравичевво-детермивироаапвые (автоматвые) фувкцпи е операцпамв $1. Детермввироаавиые функции 1 2. Задаипе детермквироваввых функций прп помощв деревьев. Вес дерева $3. Огравичевво-детермивироваввые функции п способы вх аадавия $4. Оверацик вед о.-д.

функциями 1 5. Примеры поквых систем 8 6. О соотвошевии операций С и О 73 73 78 86 91 105 110 Глава 2. й-опачкав логика $1. Функции й-звачвой логики. Формукы и реалпаацвя фувкций формулами 1 2. Првмеры полных систем $ 3. Распоавававие полноты. Теорема о полноте $4. Некоторыа свойства существенных функций.

Крите. рий полноты $5. Особеввости а-окатных логик ОГлапдкнки к вычисли- ЧАСТЬ П КОМБЯНАТОРНЫИ АНАЛИЗ $1. Комбпваторпые объекты в комбияаторные числа $2. Простейшие свойства комбпяаторпых объектов п чисел $3. Методы паучекия комбиваторвых объектов в чисел $ 4 Оцеики и асимптотики для комбииаториых чисел ЧАСТЬ И1 ГРАФЫ И СЕТИ Глава 1. Графы $1. Реализациа в евклидовом пространстве. Изоморфизм $2.

Оценка числа графов Глава 2. Сети $1. Сети в их свойстьа $2.Сцепка числа сетей $3. Двухполюскые сети из дзухобъекткых паборов $4. я-сетв ЧАСТЬ 1т ТЕОРИЯ КОДИРОВАНИЯ $1. Критерий одвозяачиости декодировавия $2. Алгоритм распознавания одяозвачкоств заявя $3, Об одном свойстве взаимно однозначных $4. Коды с мивималькой избыточностью $5. Самокорректирующиеся коды 260 268 декодвро- кодов 272 276 г88 Глава $1. $2. $3. $4.

$5. $6. $7. 4. Вычислимые фупкцяи Машипы Тьюринга Один метод построения мзшпк Тьюринга Машинные коды и пх преобразования Вычислимые фуккцви Операция С, Пр в р Вычислимые функцяп я операции С, Пр, Формула Клики. г1астпчкая рекурспвкость мых функцвй. Примеры поляых систем Нз Мз 121 129 143 146 151 16г 171 173 188 202 222 222 226 227 227 232 237 253 огллплкннн г)АСТЬ Ч НЕКОТОРЫЕ ПРИЛОУКЕПИЯ К КИБЕРНЕТИКЕ Глава 1. Дипьюпктпвные нормальные формы.... 297 $1. Понятие д. н.

ф. Проблема мпнпмпзации булевых функций............ 297 4 2. Упрощение д. н. ф. п тупиковые д. н. ф. (относительно упрощения).......,, 300 $3. Постановка аадачи в геометрической форме, . 307 4 4. Сокращенная д. н. ф......,... 312 4 5. Тупиковость на основе геометрических представлений. Методы построения тупиковых д. и. ф... 318 $6. Некоторые одпоаначно получаемые д. н. ф... 324 4 7. Понятие локального алгоритма . . . . . .

331 Глава 2. Спнтеа схем пз функциональных элементов ., 336 5 1. Понятие схемы из функциональных злементов . 336 8 2. Проблема синтеза схем из Ф. Э...... 345 4 3. Элементарные методы синтеза...... 351 1 * Нижняя оценка для Ь(л)....., .. 355 4 5. Оптимальный по порядку метод синтеза схем из Ф. Э. (метод Шеннона)......., 357 4 В. Асиьгптотическп наилучший метод синтеза схем на Ф. Э. (метод Луканова), ...., . 361 4 7. Синтез сумматора......,...

364 1 8. Синтез схем из Ф, Э„реализующих симметрические функции..........., 368 Спясок литературы............ 370 Предметный указатель........... 373 Указатель обоаначенпй .......... 381 СЕРГЕЙ ВСЕВОЛОДОВИЧ ЯБЛОНСКИЙ Сергей Всеволодович Яблонский родвлсл 6 декабря 1924 г. в Москве в сеьа е профессора, специалиста в области мехавикв. Математические вакловиости Сергея Всеволодовича прояввшкь в рванем возрасте. В 1940 г.

ои стал победителем шестой математической олимпиады школьников Москвы. В 1941 г. С.В. Яблонский поступил иа механико-математвческий факультет Московского увиверсвтета. Семвадцатвлетлвм юношей оп уходят в армию и после оковчаиик краткосрочвых курсов радистов направляется иа фронт. В составе 242-го тавкоаого полка участвует в боях ва Курской дуге — в срюкевви под Прохоровкой. Война для него заковчилась боями в Чехословакив.

Боевые заслуги Сергек Всеволодовича отмечевы двумя орденами Отечественной войны, двумя орденами Красной Звезды в орденом Славы. В 1945 г. С.В. Яблонский вернулся ва мехаввко-математвческий факультет, с отличием закончил его в 1950 г, и поступил а аспираатуру, которую усшяпво окончил в 1953 г., эащвтив кавдидатскую диссертацвю. В 1962 г. ов защитил докторскую диссертацию.

С 1953 г. Сергей Всеволодович работает ва Отделенви прикладной математики Математического ивствтуга им. В.А. Стеклова (впоследстави это Отделевие было преобразовано в Ивствтут приклалиой математвки им. М.В. Келдыша), а с 1958 г. ставоавтся заведующим отделом этого института. Педагогическая деательвость С.В. Ябловского неразрывно связана с Московсквм увиверсвтетом, профессором которого ои стал в 1963 г.

в возглавил кафедру математвческой кибернетики с момеата ее основаввя ва факультете вышслительиой математаки и киберветяюь В 1966 г. С.В. Ябловскому вместе с О.Б. Лупалоаым и Ю.И. Журавлевым была присупдева Левинская премил эа цикл работ по математической теории сивтеза управляюшвх систем. В 1986 г. С.В. Ябловсквй избвраетск члевом-корреспондентом Акалемяв наук по Отделению математвкв. СВ. Яблонский ввес фувдамевтальвый вклад в создаиве математической киберветвки как самостоятельного раздела математики.

Ол постоявво подчеркивал глубокую ее взаимосвязь с методами двскретвой математика. Ваилым шагом была разработка им общего поватия упраалюощей системы как одного яз осиоввых обьектоа, изучаемых математической кибернетикой. С.В. Яблонский выскезат гвпотезу о неизбепиости перебора (значительной части вариантов) при решении массовых каберветических задач и получил первые вапиые результаты в ваправлевяв обосвовавик этой гюютезы. Сергей Всеволодович разработал оратявальвые освоввые курсы по математической гдберветике и двскретвой математике, которые ов чатал по пи в течение трилцати лет а МГУ. Много сил С.В.

Яблонский вкладывал в яздавие научной и учебной литературы в этих областях, а частности, сборияков научных работ «Проблемы кибернетики» и «Математические вопросы кибернетики». Ов — автор учебника «Ваедевие а дискретную математвку» и нескольких монографий. С.В. Яблонский — призванный глава научной школы с широкой тематикой исследований и обширной географией научных центров, созданных при его участии. С.В. Ябловскяй скончался ва семьдесят четвертом году вязли 26 мая 1998 г.

ПРКДИСЛОВИК В России исторически сложилось так, что представление об образовании включает в себя органичное единство школы как системы приобретения знаний, фундаментальной науки как показателя уровня подготовки специалистов и гуманитарной культуры как основы духовного богатства человека. Формулируя задачи образования, академик А.Н. Крылов говорил: «Школа не может дать вполне законченного знания; главная задача школы — дать общее развитие, дать необходимые навыки, одним словом...

главная задача школы — научить учиться, и для того, кто в школе научыися учиться, практическая деятельность вас его жизнь будет наилучшей школой». Отметим, что особенность отечественной школы состоит в сочетании четкости рассуждений с глубиной содержания и простотой, доступностью, конктретностью изложения материала, которые всегда предпочитаются формальным конструкциям. Практическое воплощение данных идей подразумевает наличие высококвалифицированных и творчески мыслящих преподавателей. Математическое образование и математическая культура составляют стержень научного знания, и значение математики как основы фундаментальных исследований постоянно возрастает. Для решения этих задач требуются учебники, отражающие в определенной полноте современное состояние исследований и мировоззренческие принципы данной области науки.