Дискретная математика (Хороший учебник по дискретной математике), страница 4

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

Благодарности Автор выражает благодарность своей жене Елене Владимировне Новиковой за постоянную поддержку в работе, коллеге Вадиму Эдуардовичу Халепскому за неоценимую помощь в оформлении рукописи и многочисленным студентам, прослушавшим этот курс, за выявление ошибок в тексте. От издательства Ваши замечания, предложения, вопросы отправляйте по адресу электронной почты согпрФрйег-ргеез.ги (издательство «Питер», компьютерная редакция). Мы зудем рады узнать ваше мнение! Подробную информацию о наших книгах вы найдете на ЪЧеЪ-сейте издательства Ггпр://ведя.рйег-ргевв.го.

ГЛАВА 1 Множества и отношения В этой книге рассматриваются некоторые элементарные понятия «дискретнои» или «конечной» математики, то есть математики, не связанной с понятиями бесконечности, предела и непрерывности. Дискретная математика имеет широкий спектр приложений, прежде всего в областях, связанных с информационными технологиями и компьютерами. В самом первоначальном (ныне редко используемом) названии комяьютера —.«электронная цифровая вычислительная машин໠— слово «цифровая» указывает на принципиально дискретный характер работы данного устройства. Понятия «множества», «отношения», «функции» и близкие к ним составляют основной словарь дискретной (равно как и классической «непрерывной») математики.

Именно эти базовые понятия рассматриваются в первой главе, закладывая необходимую основу для дальнейших построений. Отличие состоит в том, что здесь рассматриваются почти исключительно конечные множества, а тонкие и сложные вопросы, связанные с рассмотрением бесконечных множеств, сознательно опущены. С другой стороны, значительное внимание уделяется «представлению» множеств в программах. Эти вопросы не имеют никакого отношения к собственно теории множеств в ее классическом виде, но очень важны для практикующего программиста, 1.1. Множества Человеческое мышление устроено так, что мир представляется состоящим из отдельных «объектов».

Философам давно ясно, что мир — единое неразрывное целое, и выделение в нем объектов — это не более чем произвольный акт нашего мышления, позволяющий сформировать доступную для рационального анализа картину мира Но как бы там ии было, выделение объектов и их совокупностей— естественный (или даже единственно возможный) способ организации нашего мышления, поэтому неудивительно, что он лежит в основе главного инструмента описания точного знания — математики. 20 Глава П Множества и отношение 1.1.1. Элементы и множества Понятие множества принадлежит к числу фундаментальных неопределяемых понятий математики. Можно сказать, что множество — это любая определенная совокупность объектов.

Объекты, из которых составлено множество, называются его элементами. Элементы множества различны и отличимы друг от друга. Пример Множество Я страниц в данной книге. Множество г( натуральных чисел 1, 2, 3, ... Множество Р простых чисел 2, 3, 5, 7, 11, ... Множество 2 целых чисел: ..., — 2, — 1, О, 1, 2, ... Множество К вещественных чисел. Множество А различных символов на этой странице. Если объект х является элементом множества М, то говорят, что х принадлежит М. Обозначение. 'х 6 М. В противном случае говорят, что х не принадлежит М.

Обозначение: х ф М. ЗАМЕЧАНИЕ Обычно множества обозначают прописными буквами латинского алфавита, а элементы множеств — строчными буквами. ОТСТУПЛЕНИЕ Понятия множества, элемента н принадлежности, которые на первый взгляд представляются интуитивно яснымн, при ближайшем рассмотрении такую ясность утрачивают. Во-первых, проблематична отличнмость элементов. Например, символы о н и, которые встречаются на этой странице, — это один злпиент множесгва А нли лва разных элемента? Во-вторых, проблематична возможность (без дополнительных усилий) указать, принадлежит ли данный элемент данному множеству.

Например, является ли число 86958476921537485067857467 простым7 Множества, как объекты, могут быть элементами других множеств. Множество, элементами которого являются множества, обычно называется классом или семейством. ЗАМЕЧАНИЕ Семейства множеств обычно обозначают прописными «рукописными» буквами латинского алфавита, чтобы отличить их от множеств, не содержащих множеств в качестве элементов.

Множество, не содержащее элементов, называется пустым. Обозначение:а. Обычно в конкретных рассуждениях элементы всех множеств берутся из некогорого одного, достаточно широкого множества У (своего для каждого случая), которое называется универсальным множеством (нли универсумом). 21 ЬК Множества 1.1.2. Задание множеств Чтобы задать множество, нужно указать, какие элементы ему принадлежат. Это можно сделать различными способами: перечислением элементов: М:=(аг,аз,..,,аь) характеристическим предикатом: М; = (х ~ Р(х)); поролсдаюшрй процедурой' М:=(х ~ х:=Д, ЗАМЕЧАНИЕ Прн задании множеств перечислением обозначения элементов обычно заключают в фигурные скобки н разделяют запятыми.

Характеристический преднкат — зто некоторое условие, выраженное в форме логического утверждения или процедуры, возвращающей логическое значение. Если для даннога элемента условие выполнено, то он принадлежит определяемому множеству, в противном случае — не принадлежит. Параждзюпщя процедура — это процедура, которая, булучн запущенной, порождает некоторые объекты, являющиеся элементами определяемого множества.

Пример 1. Мэ: =(1, 2, 3, 4, 5, 6, 7, 8, 9); 2 Мэ: = (и ( и и 1Ч Йи ( 10)' 3. Мэ .. = (и ~ Гог и 6огп 1 ьо 9 у)е!д и). ЗАМЕЧАНИЕ Множество пелых чнсез в диапазоне ат т до и обозначают таю тп..и. Та есть т..и: =(й н Е ~ 0 < Й й ь (» и) . Перечислением можно задавать только конечные множества. Бесконечные множе- ства задаются характеристическим предикатом или порождающей процедурой. Пример 11: = (и ! и 0; иЕйе Хгпе и и+ 1 до у)е!д и епдтчЫе) 1.1.3.

Парадокс Рассела Задание множеств характеристическим предикатом может приводить к противоречиям. Например, все рассмотренные в примерах множества не содержат себя в качестве элемента. Рассмотрим множество всех множеств, не содержащих себя в качестве элемента: У = (Х ( Х ф Х) Глава 1.

Множества и отношения гг Если множество У существует, то мы должны иметь возможность ответить на следующий вопрос: У Е У? Пусть У Е У, тогда У Ф У. Пусть У К У, тогда У Е У. Получается неустранимое логическое противоречие, которое известно как парадокс Рассела, Вот три способа избежать этого парадокса. 1. Ограничить используемые характеристические предикаты видом Р(х) = х Е А 8г Я(х), где А — известное, заведомо существующее множество (универсум).

Обычно при этом используют обозначение (х Е А ( Я(х)). Для У универсум не указан, а потому У множеством не является. 2. Теория типов. Объекты имеют тип О, множества имеют тип 1, множества множеств — тип 2 и т. д. У не имеет типа и множеством не является. 3. Характеристический предикат Р(х) задан в виде вычислимой функции (алгоритма). Способ вычисления значения предиката Х Е Х не задан, а потому У множеством не является. ОТСТУПЛЕНИЕ Последний из перечисленных способов лежит з основе так называемого когхтруктивизма — направления в математике, з рамках которого рассматриваются только такие объекты, для которых известны процедуры (алгоритмы) нх порождения. В конструктивной математике исключаются из рассмотрения некоторые понятия и методы классической математики, чреватые возможными парадоксами.

1.2. Операции над множествами Самого по себе понятия множества еще недостаточно — нужно определить способы конструирования новых множеств из уже имеющихся, то есть операции над множествами. 1.2.1. Сравнение множеств Множество А содврлгнтся в множестве В (множество В включает множество А), если каждый элемент А есть элемент В: АСВ:=хеА~хЕВ. В этом случае А называется подмножеством В,  — надмножвством А. Если А С В и А эь В, то А называется собственным подмножеством В. Заметим, что г М М с М. По определению УМ ю ~ М.

ЗАМЕЧАНИЕ Если требуется различать собственные и несобственные подмножества, то для обозначе. аия включения собственных подмножеств используется знак С, а для несобственных — ~ гз Ь2. Операции ньд множествами Ква множества равны, если они являются подмножествами друг друга: А= В:=А с Взгв с А. Моигность множества М обозначается как ~М~.

Для конечных множеств мощность — это число элементов. Например, )а( = О, но ЯИЦ = 1. Если (А~ = )В~, то множества А и В называются раеноиоигными. 1.2.2. Операции над множествами Обычно рассматриваются следующие операции над множествами: обьединение: АОВ;=(х ~ х е АЧх Е В); пересечение: АПВ: =(х ) х е Азгх е В); разность: А ~ В:=(х ( х е Азгх ф В); симметрическая разность; АЬВ: =(А 0 В) 1 (А П В) = (х ~ (х е А зг х ф В)ч (х ф А зг х е В)); дополнение: А:=(х ~ х ф А). Операция дополнения подразумевает некоторый универсум У: А = У 1, А. Прииер Пусть А:=(1,2,3), В: =(3,4,5).

Тогда А 11 В = (1, 2, З, 4, 5), А Г1 В = (З), А ~ В = (1, 2), АЛВ = (1, 2, 4, 5) На рис. 1.1 приведены диаграммы Эйлера, иллюстрирующие операции над множествами. Сами исходные множества изображаются фигурами'(в данном случае овалами), а результат графически выделяется (в данном случае для выделения использована штриховка). Операции пересечения и объединения допускают следующее обобщение. Пусть г — некоторое множество, элементы которого используются как индексы, и пусть для любого г е Х множество А; известно. Тогда Й Аг:=(х ) Чг е1х ~ Аг).