Главная » Все файлы » Просмотр файлов из архивов » Файлы формата DJVU » Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров

Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров

DJVU-файл Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров Дискретная математика (1919): Книга - 7 семестрКузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров: Дискретная математика - DJVU (1919) - СтудИзба2017-12-27СтудИзба

Описание файла

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. Здесь укажем лишь, что одной из ее основных задач является разработка средств задания математических объектов вообще и множеств в частности, которые решалн бы все проблемы, связанные с точностью задания, и устраняла бы возможные парадоксы.

Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Нашёл ошибку?
Или хочешь предложить что-то улучшить на этой странице? Напиши об этом и получи бонус!
Бонус рассчитывается индивидуально в каждом случае и может быть в виде баллов или бесплатной услуги от студизбы.
Предложить исправление
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
5057
Авторов
на СтудИзбе
456
Средний доход
с одного платного файла
Обучение Подробнее