Новиков Ф.А. Дискретная математика для программистов (860615), страница 5
Текст из файла (страница 5)
Из этого правила имеется несколько исключений, то есть утверждений, доказательства которыхне приводятся, поскольку автор считает их технически слишком сложными длявыбранного уровня изложения. Отсутствие технически сложного доказательствавсегда явно отмечается в тексте. Иногда же доказательство опускается, потому что утверждение легко может быть обосновано читателем самостоятельно.Такие случаи не отмечаются в тексте. Доказательства и обоснования начинаются с соответствующего ключевого слова («доказательство» или «обоснование»)и заканчиваются специальным значком • .
Если формулировка теоремы содержит несколько утверждений или если доказательство состоит из несколькихшагов (частей), то оно делится на абзацы, а в начале каждого абзаца указывается[в скобках], что именно в нем доказывается.Замечания и отступления также начинаются с соответствующего ключевого слова: «замечание» или «отступление». Назначение этих абзацев различно. Замечание сообщает некоторые специальные или дополнительные сведения, прямоотносящиеся к основному материалу учебника.
Отступление не связано непосредственно с основным материалом, его назначение — расширить кругозор читателя и показать связь основного материала с вопросами, лежащими за пределамикурса.22ВведениеЗАМЕЧАНИЕВ очень редких случаях курсив используется не для выделения определяющих вхожденийтерминов и формулировок утверждений, а для того, чтобы сделать эмфатическое удареииена каком-то слове в тексте.ОТСТУПЛЕНИЕИспользование отступлений необходимо, в противном случае у читателя может сложитьсяошибочное впечатление о замкнутости изучаемого предмета и его оторванности от другихобластей знания.Алгоритмы, как уже было сказано, записаны на псевдокоде, синтаксис которогократко описан выше. Как правило, перед текстом алгоритма па естественном языке указываются его назначение, а также входные и выходные данные.
Ключевыеслова в текстах алгоритмов выделяются полужирным шрифтом. Исполняемыеоператоры, как правило, комментируются, чтобы облегчить их понимание. Послеалгоритма приводятся его обоснование и иногда пример протокола выполнения.Примеры, как правило, приводятся непосредственно вслед за определением понятия, поэтому не используется никаких связующих слов, поясняющих, к чемуотносятся примеры.
В самих примерах интенсивно используются факты, которыедолжны быть известны читателю из курса математики средней школы, и понятия,рассмотренные в предшествующем тексте книги.БлагодарностиАвтор выражает благодарность члену-корреспонденту РАН Святославу Сергеевичу Лаврову за сотни ценных замечаний по тексту первого издания книги, многочисленным студентам, прослушавшим этот курс, за выявление ошибок в тексте,и научному редактору, профессору Никите Юрьевичу Нецветаеву, за огромнуюпомощь в работе над третьим изданием.От издательстваВаши замечания, предложения, вопросы отправляйте по адресу электронной почты comp@plter.com (издательство «Питер», компьютерная редакция).
Можно обратиться непосредственно к автору по адресу fedornovlkov@ramblar.ru Мы будемрады узнать ваше мнение!Подробную информацию о наших книгах вы найдете на веб-сайте издательстваhttp: //www. plter. com,Глава 1Множестваи отношенияПонятия «множество», «отношение», «функция» и близкие к ним составляютосновной словарь дискретной (равно как и «непрерывной») математики. Именноэти базовые понятия рассматриваются в первой главе, тем самым закладываетсянеобходимая основа для дальнейших построений. Особенность изложения состоит в том, что здесь рассматриваются почти исключительно конечные множества, атонкие и сложные вопросы, связанные с рассмотрением бесконечных множеств,излагаются с «программистской» точки зрения.
С другой стороны, значительное внимание уделяется «представлению» множеств в программах. Эти вопросыне имеют прямого отношения к собственно теории множеств в её классическомвиде, но очень важны для практикующего программиста.1.1. МножестваПри построении доступной для рационального анализа картины мира часто используется термин «объект» для обозначения некой сущности, отделимой отостальных. Выделение объектов — это не более чем произвольный акт нашегосознания. В одной и той же ситуации объекты могут быть выделены по-разному,в зависимости от точки зрения, целей анализа и других обстоятельств.
Но какбы то ни было, выделение объектов и их совокупностей — естественный (илидаже единственно возможный) способ организации нашего мышления, поэтомунеудивительно, что он лежит в основе главного инструмента описания точногознания - математики.1.1.1. Элементы и множестваПонятие множества принадлежит к числу фундаментальных понятий математики. Можно сказать, что множество — это любая определённая совокупностьобъектов. Объекты, из которых составлено множество, называются его элементами. Элементы множества различны и отличимы друг от друга. Как множествам,так и элементам можно давать имена или присваивать символьные обозначения.24Глава 1. Множества и отношенияЗАМЕЧАНИЕВ современной математике основным способом определения фундаментальных понятийявляется аксиоматический метод.
В рамках этого метода группа понятий, образующихоснову некоторой теории, определяется путем постулирования набора аксиом (утверждений об этих понятиях, принимаемых без доказательства), так что остальные утверждениявыводятся из аксиом с помощью логических доказательств. Применение аксиоматического метода предполагает наличие развитого логического языка для формулировки утверждений, и, как правило, требует значительных усилий, времени и места для построениястрогих формальных доказательств. Теория множеств не является исключением — длянеё предложено несколько систем аксиом, весьма поучительных и оказавших значительное влияние на развитие математики в целом.
Альтернативой аксиоматическому методуявляется апелляция к интуиции, здравому смыслу и использование неопределяемых понятий. Применительно к теории множеств такой подход получил название «наивной теориимножеств», элементы которой излагаются в этом учебнике.ПримерыМножество S страниц в данной книге. Множество N натуральных чисел {1, 2,3, ...}. Множество Р простых чисел {2, 3, 5, 7, 11, ...}.
Множество Z целых чисел {..., - 2 , - 1 , 0, 1, 2, ...}. Множество Ш вещественных чисел. Множество Аразличных символов на этой странице.Если объект х является элементом множества М, то говорят, что х принадлежитМ. Обозначение: х € М. В противном случае говорят, что х не принадлежит М.Обозначение: х <£ М.ЗАМЕЧАНИЕОбычно множества обозначают прописными буквами латинского алфавита, а элементымножеств — строчными буквами.Множество, не содержащее элементов, называется пустым. Обозначение: 0 .ЗАМЕЧАНИЕВведение в рассмотрение пустого множества является сильным допущением.
Например,известно, что синих лошадей в природе не бывает. Тем не менее мы позволяем себерассматривать «множество синих лошадей» как полноправный объект, вводить для негообозначения и т. д.ОТСТУПЛЕНИЕПонятия множества, элемента и принадлежности, которые на первый взгляд представляются интуитивно ясными, при ближайшем рассмотрении такую ясность утрачивают.Во-первых, даже отличимость элементов при более глубоком рассмотрении представляет некоторую проблему. Например, символы «а» и «а», которые встречаются на этойстранице, — это один элемент множества А или два разных элемента? Или же, например, два вхождения символа «о» в слово «множество» — графически они неотличимы251.1.
Множестваневооружённым глазом, по это символы букв, которые обозначают звуки, а читаются этидве гласные по-разному: первая под ударением, а вторая — безударная. Во-вторых, проблематична возможность (без дополнительных усилий) указать, принадлежит ли данныйэлемент данному множеству. Например, является ли число 86958476921537485067857467простым?Множества как объекты могут быть элементами других множеств. Множество,элементами которого являются множества, иногда называют семейством.ЗАМЕЧАНИЕСемейства множеств часто обозначают прописными «рукописными» буквами латинскогоалфавита.Совокупность объектов, которая не является множеством, называется классом.Неформально говоря, называя совокупность элементов классом, а не множеством, мы берём на себя сравнительно меньшую ответственность за определённость, отличимость и бесповторность элементов.ОТСТУПЛЕНИЕТермин «класс» в объектно-ориентированном программировании (ООП) употребляетсяправомерно.
Можно было бы сказать, что класс в ООП — это множество объектов, являющихся экземплярами класса. Однако такое определение не вполне корректно. Например, возможность динамического изменения класса объекта, существующая в некоторыхязыках ООП, ставит под сомнение статическую определённость класса, а возможностьклонирования объектов ставит под сомнение отличимость экземпляров как элементовкласса.Обычно в конкретных рассуждениях элементы всех рассматриваемых множеств(и семейств) берутся из некоторого одного, достаточно широкого множества U(своего для каждого случая), которое называется универсальным множеством(или универсумом).1.1.2. Задание множествЧтобы задать множество, нужно указать, какие элементы ему принадлежат. Этоуказание заключают в пару фигурных скобок, оно может иметь одну из следующих основных форм:перечисление элементов:характеристический предикат.порождающая процедура:М: ={а, 6, с , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
