Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров
Описание файла
DJVU-файл из архива "Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров", который расположен в категории "". Всё это находится в предмете "дискретная математика" из 7 семестр, которые можно найти в файловом архиве МГТУ им. Н.Э.Баумана. Не смотря на прямую связь этого архива с МГТУ им. Н.Э.Баумана, его также можно найти и в других разделах. Архив можно найти в разделе "книги и методические указания", в предмете "дискретная математика" в общих файлах.
Просмотр DJVU-файла онлайн
Распознанный текст из DJVU-файла
т. е. практически не устрапимой никаким увеличением мощности вычислительных средств. Рассмотрение этих задач поучительно еще и потому, что почти все они имеюг характерный для дискретной математики эффект сочетания простоты формулировки со сложностью решения.
Главы последнего раздела (гл. 4 и 9) написаны Г, М. Адельсоном-вельским, остальные главы — О. П. Кузнецовым. К сожалению, объем книги не позволил включить в нее задачи. Некоторой компенсацией за это может служить внимательный разбор многочисленных примеров и настоятельно рекомендуемое читателю восстановление опушенных мест в доказательствах (впрочем, мы не настаиваем на этой рекомендации по отношению к теоремам Черча и Геделя в гл.
6). Литература сгруппирована в четыре списка, соответствующих указанным разделам; все онн помещены в конце книги. Учитывая широкое назначение книги, мы стремились сделать библиографию компактной и общедоступной. Поэтому она состоит в основном из книг на русском язы. ке, журнальные статьи указаны лишь в необходимых случаях, А. Я. Макаревский, много и плодотворно работавший в теории автоматов, был одним из инициаторов написания книги.
Неожиданная смерть в 37 лет помешала ему начать работу над ней. Памяти этого замечательного человека и исследователя посвящают авторы эту книгу. А вторы ГЛАВА ПЕРВАЯ мнажествл, функции, отношении ЕЕ МНОЖЕСТВА И ОПЕРАЦИИ НАД НИМИ Множества и подмножества. Одними из основных, исходных понятий математики являются понятия множества и его элементов. Множество состоит из элементов. При. надлежность элемента а множеству М обозначается аыМ («а принадлежит М»); непринадлежность а множеству М обозначается а~М или ае=М. Пример 1.1*.
М1 — многкество всех натуральных чисел: 1, 2, 3... В дальнейшем будем обозначать его У; элементы )т' — натуральные числа. Часто 0 также считают натуральным числом (см., например, [351); множество, полученное добавлением 0 к Аг, будем обозначать Лго. Мз — множество всех натуральных чисел, не превосходящих 100.
Мз — множество всех решений уравнения з(п х=1; элементы Мз — числа, являющиеся решениями этого уравнения. М4 — множество всех чисел вида я/2+-йзс, где АенЛге. Л1з — множество всех действительных чисел (в дальнейшем 1с). ЛТз — футбольная команда «Арарат» (т. е. множество ее футболистов). М, — множество всех футбольных команд высшей лиги в сезоне 1985 г. Элементами Мт являются футбольные команды, т.
е. множества типа Ме. Таким образом, множества могут служить элементами других множеств; возможны множества множеств (М,), множества многкеств множеств (множество всех лиг футбольного первенства) и т. д. Отступление ЕЕ Понятие множества, как и любое другое всход. ное понятие математической теории, не определяется. Ведь всякое определение содержит другие понятия, логически предшествуюпгне опреде.
ляемому; поэтому по крайвей мере первое определение теории обяза- а Обозначения Мз — Мт сохраняются до конца параграфа, тельно содержит неопределяемые понятии, которые н принимаются за исходные. В ка ~естес исходных обычно выбираются понятия, в понимании которых не возникает существенных разногласий; более точно: разли шя в понимании которых не нарушают правильности ни одного положения теории.
Для теорий, рассматриваемых в данной книге, понятие множества именно таково. Основные принципы построения математических теорий более подробно изложены в гл. 6. Множество А называется подмножеством множества В (обозначение АыВ; знак с= называется знаком включения), если всякий элемент Л является элементом В. При этом говорят, что В содержит или покрывает А. Множества А н В равны, если их элементы совпадают, иначе говоря, если Л:-В и ВыА, Второй вариант определения равенства множеств указывает и на наиболее типичный метод доказательства того, что данные множества равны, заключающийся в доказательстве сначала утверждения Ай=В («в одну сторону»), а затем В~А («в другую сторону»).
Форму утверждения о равенстве двух множеств имеют многие математические теоремы. Пример — тригонометрическая теорема Мз =М«, состоящая из двух утверждений: а) всякое решение уравнения з(пх *1 имеет вид я/2».ип (Мз=М4); б) всякое число вида и/2» йя является решением уравнения и!и х 1 (Мес:-Мз). Если ЛыВ и АФВ, то А часто называется собственным, строгим или истинным подмножеством В (обозначение Ас:В; знак с: называется знаком строгого включения).
Заметим, что в случае множества множеств возникает опасность смешений знаков ы и с:. Например, верно МеепМт, но неверно Ме~Мт (так как Ма и М, — множестваа р аз ной при роды1) . Множества могут быть конечными (т. е. состоящими из конечного числа элементов) и бесконечными. Число элементов в конечном множестве М называется мощностью М и часто обозначается 1М~.
Мощность бесконечного множества — более сложное понятие. Оно будет рассмотрено после введения понятия соответствия. Множество мощности О, т. е. не содержащее элементов, называется пустым и обозначается Я, Принято считать, что пустое множество является подмножеством любого множества. Пустое множество введено в математике для удобства и единообразия языка. Например, если исследуется множество объектов, обладающих каким-либо свойством, и впоследствии выясняется, что таких объектов не 10 существует, то гораздо удобнее сказать, что исследуемое множество пусто, чем объявлять его несуществующим, Ут- ве жденне «множество М непусто» являет о: ся б лее ком- вер пактной формулировкой равносильного у у р ем тве ждения «с шествуют элементы, принадлежащие М».
«су Способы задания множеств. Множество м ж может быть задано перечислением (списком своих элементов), поро- ждающей процедурой или описанием характеристических свойств, которыми должны обладать его элементы. Списком можно задавать лишь конечные множества. За ание типа Л/= 1, 2, 3... — это не список, а условное обозначение, допустимое лишь тогда, когда оно д а оно заведомо заключается не вызывает разночтений. Список обычно зак. в фигурные скобки. Например, А=(а, Ь, и', й) означает', что множество А состоит из четырех элементов а, Ь, г( и й. Порождающая процедура описывает способ получения эле ментов множества из уже полученных элементов либо из других объектов, Элементами множества считаютс объекты, которые могут быть построены с помощью такой процедуры.
Примером служит описание множества Мь где исходными объектами для построения являются нату- ральные числа, а порождающей процедурой — вычисле. ние, описанное формулой и/2+. Ьн. Другой пример— множество М «=1, 2, 4, 8, 16..., порождающая процедура для которого определяется следующими двумя правила- ми: 1) 1енМ «; 2) если т~М,ь то 2тенМ.,«. (Правила, описанные таким образом, называются индуктивными или рекурсивными; о них будет речь в дальнейшем.) Третий пример — множество Л4, заданное следующим образом.
П сть имеется процедура вычисления цифр разложения уст числа и в бесконечную десятичную дробь: н= =3,1415926536... По мере вычисления будем образовывать из последовательно стоящих цифр трехразрядные числа: 314, 159, 265 и т. д. Множество всех таких чисел обозначим М~, Весьма распространенной порождающей процедурой является образование множеств из других множеств с по- мощью операций над множествами, которые будут рас. смотрены ниже.
Задание множества описанием свойств его элементов, пожалуй, наиболее обычно. В примере 1.1 так заданы мно- жества Мм Мз, Мз, да и задание М4 можно интерпретиро- вать как описание свойства его элементов, заключающего. !! ся в возможности представнть нх в виде лг2+-йп. Множество М»л можно задать фразой «Мел — множество всех целых чисел, являющихся степепямн двойки», В случае, когда свойство элементов М может быть описано коротким выражением Р(х) (означающнм «х обладает свойством Р»), М задается прн помощи обозначения М= =(х~Р(х)), которое читается так: «М — это множество х, обладающих свойством Р». Например, М л=(х1х=2", где ленйге)~ Мч=(х1х=п/2+Ь, где йенса).
К описанию свойств естественно предъявить требование точности н не- двусмысленности. Например, множество всех хороших фильмов 1985 г. разные люди зададут разными списками (быть может, пустыми); сами критерии, по которым производится отбор, прн этом будут различны. Такое множество нельзя считать строго заданным.
Надежным способом точно описать свойство элементов данного множества служит задание распознающей (нлн, как говорят в математике, разрешающей) процедуры, которая для любого объекта устанавливает, обладает оп данным свойством н, следовательно, является элементом данного' множества нлн цет. Например, для Мед т. е. для свойства «быть степенью двойки», разрешающей процедурой может служить любой метод разложения целых чисел на простые м ногкнтелн. Отметим, что в этом примере разрешающая процедура не является порождающей. Однако ее нетрудно сделать таковой: берем последовательно все натуральные числа н каждое нз ннх разлагаем на простые множители; те чнсла, которые не содержат множителей, отличных от 2, включаем в М,».
С другой стороны, порождающая проце. дура может не быть разрешающей. В этой связи предлагаем чнтателю поразмыслить над множеством М, однако предостережем его от поспешных заключений. К этому множеству мы еще вернемся. К какому виду принадлежит задание множества Мзу Нн к какому: Ма по существу не задано, а только названо.
Задать его можно, например, списком нлн следующим описанием: «Ма — множество всех лнц, имеющих удостоверения футбольного клуба «Арарат», Разрешающая процедура для такого опнсапня связана, как легко понять, с проверкой документов. Отступление 1Д. Рассмотрение способов задания множеств приво. дит и мысли о том, что само понятие «точно задать множество» нужь 12 дается в уточнении. Такое уточнение совсем не просто, а его важность крайне велика и выходит далеко за пределы самой теории множеств. Язык множеств — эта универсальный язык математики. Любое математическое утверждение можно сформулировать иак утверждение о некотором соотношении между множествами: о равенстве двух мвожеств (см.
ранее М»=М«), о непустоте некоторого множества («существует непрерывная нигде не дифференцнруемая функция»), о непринадлежности элемента мнозкеству («с помощью циряуля и линейки нельзя построить круг, равновеликий данному квадрату») и т.д. Поэтому анализ способов задания множеств связан с анализом строгости математических утверждений вообще, т.е. с обсу»кдением самих оснований математики, В чем трудности вопроса о задании множеств? Одна из основных трудностей заключается в том, что даже из множеств, точность описания ноторых не вызывает сомнений, с помощью, казалось бы, вполне законных средств можно сконструировать описания множеств, которые приводят я противоречиям — «парадоисам теории множеств», хорошо известным в истории математики.
Примером является «множество всех множеств>. По смыслу своего описания оно долгино содержать все мыслимые множества. Однано оно само содержится в множестве своих подмножеств в качестве элемента. Более точный комментарий этого примера должен опираться на понятие мощности бесконечного множества и будет дан позднее (см. теорему Кантора).
Анализ возникших трудностей привел в первой третй ХХ в. к бурному развитию области математики, получившей название основанай математини, илн метаматематики. Некоторое представление об этой области будет дано в гл. 5 и 6. Здесь укажем лишь, что одной из ее основных задач является разработка средств задания математических объектов вообще и множеств в частности, которые решалн бы все проблемы, связанные с точностью задания, и устраняла бы возможные парадоксы.