Основы дискретной математики В.А. Осипова (552659), страница 2
Текст из файла (страница 2)
е. х Е В. Если т, Е В, то ддя некоторых целых положительных р и о х = (2р-1) + (2д — 1) = = 2(р+ в — 1), т. е. х Е А. Множество, элементами которого являются обьекты а1, аг, ... ..., а„и только они, обозначают (а1, аг, ..., а„). Пример 1.2. В силу принципа объемности (2,4,6) = (4, 2, 6) = (2, 4, 4, 6); Ц1, 2)) ф (1, 2), так как единственным элементом множества Ц1, 2)) является множество (1т 2), а множество (1, 2) состоит из двух элементов: чисел 1 и 2.
При рассмотрении способов задания множеств возникает проблема нх эффективного описания. Ее решение обычно основано на интуитивном понятии «формы от х». Под формой от х будем понимать конечную последовательность, состояшую нз слов н символа хт такую, что если каждое вхождение х в эту последовательность заменить одним и тем же именем некоторого предмета соответствующего рода, то в результате получится истинное нли ложное предложение. Например, формами от х являются следующие предложения: «3 делит х», «хг = 4», «хе+ 2х+ 1 > х», «т, — родственник Иванова». Напротив, предложения «для всех х ъг = (х — 2)(х+ 2)» и «существует такое х, что х > О» не 1.1.
Начальные полития теории миожеати являются формами от х. Обозначим форму от х через Р(т). Интуитивный принцип абстракции. Любая форма Р(х) определяет некоторое множество А, а именно множество тех и только тпех предметов а, для которых Р(а) — истинное предлоэтсение. Для множества А, определяемого формой Р(х), принято обозначение А = (х~Р(х)). Пример 1.3.
1. (х~х — положительное число, меньшее 9) = (1, 2, 3, 4, б, 6, 7, 8). 2. (х~х — четное число) — множество четных чисел. Описанные выше понятия теории множеств с успехом могут быть использованы в началах анализа, алгебры, математической логики и т. д. Однако надо иметь в виду, что прн более строгих рассмотрениях такое интуитивное восприятие может оказаться неудовлетворительным. Несовершенство интуипшвных предстпавлений о множествах, их недостаточность ттллюстрир1лотся, наттример, известным парадоксом Б.
Рассела. Приведем этот парадокс. Можно указать такие множества, которые принадлеэтсат самим себе как эл менты, например *ттюэтсество всех множеств, и тпакие множества, копи?расе не явллютпся элементами самих себя, наттри.мер множество (1, 2), элемента.ми которого являются числа 1 и 2. Рассмотрим теперь л«ноэтсестпво А всех таких множеств Х, что Х не есть эле.ментп Х. Тогда, если А не есть элеметтт А, то, по определению, А также есть и элемент А. С другой стороны, если А есть элемент А, шо А — одно из тех лтожеств Х, которые не есть элементы самих себя, т.
е. А не есть эле «ент А. В любом случае А есть элемент А и А не есть элемент А. Этот парадокс свидетельствует о том, что широко используемая теория множеств в ее интуитивном, «наивном» изложении является противоречивой. Формализация теории мттожеств, связанная, в частности, с устранением парадоксов, стюсобствовала развитию не только методов теории множеств, но и такой науки, как математическая логика. Через С обозначим отношение вклточет»ия между множествами, т. е.
А С В, если каждый элемент множества А есть элемент множества В. Тогда говорят, что А есть подмножестпво множества В. Бели А С В и А ф В, то говорят, что А есть А + В = (А ~1 В) 0 (В 1 А). А=У1А Заметим, что Х 1 А = Х Г1 А 'Ж и Гис. 1.1 10 Глава 1, МНОЖГвОТВА И ОТНОШЕНИЯ собственное подмножество В, и ппшут А С В. Пример 1.4. Множество четных чисел есть подмножество множества целых чисел; множество рациональных чисел есть подмиожество множества действительных чисел; (1, 2) С (1, 2, 3,4 . Заметим, что: а) Х С Х; б) если Х С У, У С 2', то Х С л; в) если Х С У и У С Х, то Х = У. Не надо смешивать отношения принадлежности и включения, Хотя 1 Е (Ц, (Ц С ((Ц), не верно, что 1 Е ((Ц), так как единственным элементом множества ((Ц) является (Ц.
Множество, не содержащее элементов, называется пустым и обозначается 9. Пустое множество есть подмножество любого множества. Множество всех подмножеств А называется множество.нстепенью и обозначается Р(А). Пример 1.5. Если А = (1, .2, 3), то Р(А) = (6, (Ц, (2), (3), (1, 2), (1, 3), (2, 3), А). В дальнейшем мы неоднократно будем пользоваться утверждением, что если множество А состоит из и элементов, то множество Р(А) состоит из 2" элементов (см. задачу 3). 1.1.2.
Операции над множествами. Алгебра множеств Продолжая рассмотрение методов, с помощью которых из данных множеств можно получить новые множества,, приведем понятие операций над множествами. Эти операции в некотором смысле аналогичны алгебраическим операциям над числами. Обэедпнением множеств А и В называется множество А О В, все элементы которого являются элементаа1и множества А или В: А 0 В = (х(х Е А или х Е В). Пересечением множеств А и В называется множество А О В, элементы которого являются элементами обоих множеств А и В: А Г1 В = (х~х Е А и х Е В). Очевидно, что выполняются включения А О В С А С А 0 В иАГ1ВСВСАОВ.
Относнтельнььм дополнением множества А до множества Х (или разностью множеств Х и А) называется множество 1.1. Начальные понятие теории мвожеств Х 1, А всех тех элементов множества Х, которые не принадлежат множеству А: Х ~ А = (х~х Е Х и х Е А). Симметрической разностью множеств А и В называется множество Если все рассматриваемые в ходе данного рассуждения множества являются подмножествами некоторого множества У, то это множество У называется универсальным для данного рассуждения. Абсааотнььн дополнением множества А называется множество А всех тех элементов х, которые не принадлежат множеству А: Для наглядного представления отношении между подмножествами какого-либо универсального множества используют диаграммы Эйлера — Венна. Само универсальное множество У изображают в виде прямоугольника, а его подмножества — в виде кругов, расположенных внутри прямоугольника.
На рис. 1.1, а подмножество А универсального множества У изображено в виде заштрихованного круга. На рис. 1.1, б — е изображены соответственно объединение, пересечение, относительное дополнение, симметрическая разность, абсолютное дополнение. 13 Глава 1. МНОЖЕСТВА И ОТНОШЕНИЯ 1.1. Начальные понятия теории множеств Утверждение 1.1.
Для любых подмножеств А, В и С универсального лтожества П выполняются следуюи1ие тождества (основные тождестпва алгебры множеств): 1. АОВ = В О А (коммутпа- 1'. АПВ = ВГ1А (коммутативность О); тивность П); 2. АО(ВОС) = (АОВ) ОС 2'. АП(ВПС) = (АПВ) ПС (ассоциативность О); (ассоциативность П); 3. А О (В П С) = (А О В)Г1 3'.
А П (В О С) = (А П В)О П(А О С) (дистрибутив- О(А П С) (дистрибутив- ность О относительно П); ность Г1 относительно О); 4. АОФ=А; 4'. АП17=А; 5. АОА=У; 5'. А П А = Ф; б. АОА=А; 6'. А ПА = А; 7. АОП=П; 7'. АП6 = 6; 8. АОВ=АГ1В (закон 8'. А П В = А О В (закон де Моргана); де Моргана); 9. АО(АПВ) =А (закон 9'.
АП(АОВ) =А ( поглощения); поглощения).. Докажем тождество 3. Сначала покажем, что А О(ВПС) С С (А О В) Г1 (А О С). Действительно, если х Е А О (В П С), то х Е А или х Е В П С. Если х Е А, то х Е А О В и х Е А О С, Следовательно, х Е (А О В) П (А О С). Если х Е В П С хЕВи и х Е С. Отсюда х Е В О А и х Е С О А, а значит, х Е (А О В) П (А О С) . Теперь покажем, что (А О В) П (А О С) С С АО(ВПС).
Если х Е (АОВ)П(АОС), то х Е АОВ их Е АОС. Следовательно, х Е А или х Е В и х Е С, т. е. х Е ВП С. Отсюда х Е А О (В Г1 С) . Докажем тождество 8. Пусть х Е А О В. Тогда х Е 17 и х Е А О В. Следовательно, х Е А и х Е В. Отсюда х Е А и х Е В их,а значит, х Е АПВ. Итак, А О В С АПВ. Пусть теперь х Е АПВ. Тогда х Е А и х Е В. Следовательно, х Е У и хЕ А и х Е В.
Значит, хЕАОВ, т. е. х Е АОВ. Итак, АПВ САОВ. Осталы|ые тождества доказываются аналогично. Утверждение 1.2. Предлохсвния о произвольных множеглпвах А и В попарно зквив лентны: 1) АСВ; 2) АПВ=А; 3) АОВ=В. Докажем, что из первого предложения следует второе. Действительно, так как АПВ С А, то достаточно показать, что в этом случае А С А П В. Но если х Е А, то х Е В, так как А С В, и, следовательно, х Е А П В. Докажем, что из второго утверждения следует третье.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
