В.Н. Нефедов, В.А. Осипова - Курс дискретной математики

В. Н. НЕФЕДОВ В. А. ОСИПОВА КУРС ДИСКРЕТп'ОИ МАТЕМАТИКИ Дон ущено Гоеунауе таама «омнююм СССР о ауоююму обраааиа ю е не ао уюбнюо но обнн Нан пухам м уо, обу ююнхю но еннюмно т вбн нанн н мате «тню ббвсквв вздвусвьсувв ели еббб ББК 152.12 Н55 УНК 5!9.1(0755) Рекыммпы: лвннр ехвмюаю еу Л. Т КУЗИН. з палат Фюнкс мюемао мс нл н ук В. В. МОРОЗОВ НеФедов В.

Н„Оююова В. А. Н55 Курс дискретной мбтсмитикит Учеб. нссобие.— Лйт И - йуЛИ, 1222.— 256 !5ВМ 5.7056-0157-Х иззаювва соевы вв тв й лн рювю м тмю нкн Р сма рюввтс еюрссы, сказаны * мзв зт ссюю втн *й, тюрней з ° ебра тесак* с, мбннзтсра» й, м рз й рейма пр влк са р з Ректн сю вюач а пмво юрктмы нк ре пю. У бн е «с а кремса ыв л» отме т к юув как*с» а ююна ь «ю Пр юзик а е пака« з мсжю сю атва вмюым ак е н стуле тзы з ювсюююю н тсюю севы Факу в«па, зу впз;нз куре Дю рвана ат ат а таю!Ив!в!6 666(ба!66 ВВК !66.16 15ВЙ 5-7055.0157-Х ©В.Н.

Н Фек,н.д.о юв,!666 ПРЕДИСЛОВИЕ В последние годы икженерм-математики, запимающиеся прикладными исследованиями, все больше используют аппарат дискретной математики. Это объясняется необходимостью создания п эксплуата. цпи современных электронных вычислительных машин, средств передачи и обработки информации, автоматизированных систем управления и проекпьровапня. Наконец, в современной математической науке исследования в областях, традициоппо отпосащихся к дискретной математике (математический логике, теории алгебраических систем, теории графов и сетей и т.

д.), занимают эсе более заметное место. Цель создания учебного пособия — паучпть сту. делтов основам дискретной математики, где дискретность понимается каи антипод непрерывности. В настоящее время наряду с такимп иласскчсскими разделами математики, как математпчесю~й анализ, диффереициальяые уравнения, в учебных клаиах спе. циальностн «Прикладная математикаэ и многих других технических н экономических спеииальностей появилпсь разделы по математической логике, алгеб.

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

М первой главе излагаются основы логики выскаэ зываиий и логики предикатов Аппарат логики вы. 3 сказываний используется прн изучении булевых функций. На примере логики высказыванпй осуществляется знакомство со строгой формализацией математнческой теории — строится исчисление высказмваннй. Затрагиваются вопросы, связанные с эффективной вычнслнмостью. С помощью машин Тьюринга п частично рекурсивных функций уточняются понятия алгоритма н вычнслнмостн.

Во второй главе рассматриваются основные понятна теории групп, колец н полей. В качестве прнло. женив рассматрнваются элементы алгебраической теории кодирования. Третья глава посвящена комбннаторнке н перечнслнтельяой теории Пойа, использующей ряд результатов н методов теории групп. В четвертой главе нзлагаются основы теорнп графов (орнентнровапных н неорнентпрованных]. Приводятся задачи тсорин графов н сетей, являющиеся метематнческнмн моделями ряда прикладных задач. Методы нх решения довелены до уровня про. етых алгорнтмоц реализуемых на ЭВМ. Обсуждается понятие эффскгненосгн номбинаторных алгоритмов. Рассматрнвается приложение теории графов к расчету электрическнк цепей. Учебное пособие ориентировано на лекционный курс, читаемый одним нз авторов ва факультете «Прикладная математнка» Московского авиационного института.

В книгу не включены некоторые специальные вопросы (методы мянямизацин булевых функций, раскраски графов н т. дзд которые студенты научают прн выполненин курсовых работ, а также прн прохождении нмн лабораторного практикума. Введение, гл. 1, 2 н раап. 4.6 написаны В. Уь Оснповой, гл. 3 н раэд. 4.! — 4.5 — В. Н. Нефедовым.

ВВЕДЕНИЕ Рассмотрны понятия «миожества», «отношением «функция», с помощью каторих строится, по существу, любая математическая дисциплина. ЮА. НАЧАЛЬНЫЕ ПОИЯТИЯ ТЕОРИИ МНОЖЕСТВ Под миажеагеом 5 будем понимать любое собрание определеннык н различимых между собой объектов, мыслпмое как единое иелае. Зтн объекты называются эламеитами множества 5. В этом интуитивном аирспелении, прпнаялсжапгем нсмсикаму ыатсматику Г.

Кантору, существенным являетса та обсюятеяьсгво, что собрание предметов само рассматривается как алин дредмет, мыслится как единое целое. Что касается самнк предметов, которые могут входить в множество, то относительна внх существует значительная свобода. Зто может быть множество студентов, присуютвующих иа покипи. миожеспю целых чисел, зпюжество точен плсскости, множества всек людей, живущих ав Земле. Заметим, что канторовская форму гировка позволяет рассматривать множества, эаементы которых ° а гой или иной причине веяьзя точно указать (например, множества простых чисел, множества русских воинов, погибших в битве на Куликовом пале, н т.

л,Е Символом кч обозначается апююеиие лрикадлежжытв. За. вась кэп5 означает, что элемент к прннаалсжит мнОжеству 5. Если элемент к не принадлежит множеству 5. то пишут кей5. Г. Кантором сформулирована несколько интунтнвнык прининпов, которые естественна считать выполняющимися для произвольных множсста. Интуитивный принцип обьемностн. Множества А н В считаются раекыгщ е лиани соспыт иэ одних и тех зсе элемеипж Записывают А В, если А и В равны, а Ачь — а противном случаи Пример йд. Пронллюстрнруем принцип обьеыпасти. Множество А воск паиожнтельнык четных чисел равно множеству В пояожнтельиых целмх чисел, представимых в виде суммы лвух положительных печепгых чисел.

Действительна, если хщд, то лля некоторого целого положительного числа из а х = Вм; тогда к (2ш — 1) + 1, т. е. хш В. Если х ш В. то дэя некоторых велик положительных р и 4 х (2Р— 1) (24 — 1) =2(р+4 — 1), т. е. хшА Множество, элементами которого являются об»гиты о. о и только опн, обозначают (аь ..,, а,). Пример 0.2. В силу принципа объемности (2, 4. 6) = (4, 2 6) = (2. 4. 4, 6); ((1, 2)) ч' (1. 2), так как единственным э.гсментом множества ((1, 2)) является мнаткесгво (1, 2), а мно. жешво (1, 2) состоят иэ двух элементов: чисел 1 и 2.

При рассмотрении способов задания множеств возникает проблема нх эффективного описания. Ее решение обычно основано на нгмуитнвиом понятны «формы от х». Нод бюрмоЛ от х будем понимать конечную последовательность, состояшую из слов и символа х. такую, чта если каждое вкажзение х в эту последовательность заменить одним н тем же именем веко!араго предмета соответствуюжего рода, то и результате пату»итси истинное или ложное предложение.

Например, форманй от х являются следуюшис прсдложенияг «3 делит х», «к — 2х — 1 > >к», «х'=4», «х — родственник Иванова». Напротна, орслложепня «для всех х хт — 4 = (к — 2)(х + 2) и «сушсстьует такое к, что х > 0» не являются формамн ат х. Обозначим форму ат к через Р(х). Интувтивиый принпип абстракции. Любая форма Ргх) олределиет некоторое множество Л.

а именна анаше тео тех и толька тек предметен а, длл «атарик Р( ) — истинное хргдлпмение, Для множества Л, опреаеляемото формой Р(х), зпшято обозначение Л (к( Р(к)(). Пример О.З. 1. (х(к — положительное число, меньшее 9) = (1. 2. Д 4. 5,6,7,8). 2. (х)х — четное чнсао) — множество чсюгых чисел. Описанные выше канатна теории множеств с успехом могтт быть использованы в началах анализа, алгебры, математической лш'нки и т. д. Однако надо иметь в виду, что прп более строгих рассмотрениях такое интуитивное восприятие мшкет оказаться неудовлетворительным.

Песоеершенстео интуктигнык лредсгаелениа о .«номгстаах, их недостаточно ть иллюстрируются, например, итэгстимм парадаксол Б. Рассела. Пригеделг этот парадокс. Мш«на укнзать талие мнаигстеа, которые лр надлежат саням ебе как элем нтм, например мкожестео всех иноэгеста, и такое множества, которые не являются элементами свмик сгбм например мношестеа (1, 2), элементами которого яалхютсл «иола 1 и 2. Рассмотр теперь м аместео А всех таких мнакеше Х, чю Х не ест»элемент Х.

Тогда, если А не есть элемен~ Я, то, но определению, А также есть и элемен~ А С другой стороны, если в Л есть элемент А, го А — одно из тех множеств Х, «огорьы ие есть элементы сами» себя, г. е. А ие есть элемент А. В «юбсы ллрчпе А есть влеыеиг А и Л ле есть элемент А. Втст парадокс свилетельствует о том, что широко мспользусиде теория множеств е ее интуитивном, «пьпэнсм* изломе. иин является протнворечнвсд.

Формализация теории множеств, связаеная, в частности, с устранением парадоксов, слособствоваяа разеитюо не только методов теории множеств, но н такой аауки, как математическая логика. Через си обозначим опююеиие еключеиля между множествами, т. е. АМВ, если кзждыб элемент множества Л есть элемент множества В. Тогда говорят, что А есть подлюке ство ыншкества В. Если АглВ и Ач'В, то говорят, что А есть собсгееииое подмножество В, н пишут ЛшВ.

Пример ОА. Множество четных чисел есть подмножество инсжестеа целых чисел; множество рапнолальнык чисел есть подмножество множества дебствительиых чесел; (1, 2) сп (1, 2, 3, Я). Заметим, чпх а) КглХ1 б) если Хшу, Ушд, то Хсдбг в) если Ха У н УРАХ, то Х= У. Нс надо смешивал. отношения приналлсжности п включения. Хата 1 ш (Ц, (ЦЮ ((1Ц, ие верно, что 1 ш ((Ц), так как единственным элементом множества ((1Ц яелястся (Ц. Мяожеспю, нс содержащее элементов, называется лрггыи ' н обозпачаетс» И. Пустое множество есть подмножество любога множества.

Множества всех подмножеств А называется лшиглством-степенью и обозначается Р(Л). Пример О.б. Если Л = (1, 2 3). то Р(А) = (Ы, (Ц. (2). (3) (1, 2), (1, 3), (2, 3). А). В дальнейшем ныхгеократио будем пользоваться утверждепиевс что если множества Л состоит из л элементов, то множссгсо Р(Л) состоит из 2" элементов (см.