Новиков Ф.А. Дискретная математика для программистов (860615), страница 7
Текст из файла (страница 7)
Другимисловами,|Л|=\В\D~А ~ В.Из определения и отмеченных свойств взаимно-однозначного соответствия непосредственно следуетТЕОРЕМАРавномощность множеств обладает следующими свойствами:1. УД (\А\ш\А\).2. V A J 3 ( | Л | - | £ | — Н Л | - | Л | ) .3.(|Л| - \В\ к \В\ - \С\ - Ф \ А \ ш I d ) .Примеры1. Множество десятичных цифр равиомощно множеству пальцев па руках человека (для подавляющего большинства людей), по пе равиомощно множествупальцев на руках и па ногах.2.
Множество чётных натуральных чисел равиомощно множеству всех натуральных чисел.311.2. Алгебра подмножеств1.2.3. Конечные и бесконечные множестваДля приложений дискретной математики в программировании наибольшее значение имеют множества с конечным количеством элементов. Вопрос о том, чемконечное отличается от бесконечного, неподготовленного человека может поставить в тупик. Здесь мы рассматриваем применительно к множествам один извозможных ответов на этот вопрос. С античных времен известен принцип: «частьменьше целого». Оказывается, этот принцип можно использовать в качествехарактеристического свойства конечных множеств. Для бесконечных множествэтот принцип не имеет места.Множество А называется конечным, если у него пет равиомощного собственногоподмножества:VB ((В С А к \В\ = \А\) =>(В = А)).Для конечного множества А используется запись |Л| < оо. Все остальные множества называются бесконечными. Взяв отрицание условия конечности, получаем,что для бесконечного множества АЗВ {В с A k\B\= \A\ к В ф А),то есть бесконечное множество равиомощно некоторому своему собственному подмножеству.
Для бесконечного множества А используется запись |А| = оо.Пример Множество натуральных чисел бесконечно, \N\ = оо, поскольку оноравномощно своему собственному подмножеству чётных чисел.ОТСТУПЛЕНИЕВ компьютере все множества реальных объектов (множество адресуемых ячеек памяти,множество исполнимых программ, множество тактов работы процессора) конечны.ТЕОРЕМАМножество, имеющее бесконечное подмножество, бесконечно:(ВсАк\В\^оо)^Ф(\А\шоо),Множество В бесконечно, то есть существует взаимпо-одпозлачное соответствие В ~ С между множеством В и некоторым его собственнымподмножеством С. Обозначим это соответствие х х'. Построим соответствиемежду множеством А и его собственным подмножеством D\ДОКАЗАТЕЛЬСТВОх м> if х б В then х' else х end if.Другими словами, на элементах из В мы пользуемся заданным соответствием, а остальным элементам сопоставляем их самих (рис.
1.1). Это взаимпо-одпозначпое соответствие между множеством А и его собственным подмножествомА и значит, |Л| = оо.•32Глава 1. Множества и отношенияРис. 1.1. К доказательству теоремы (к п. 1.2.3)ЗАМЕЧАНИЕВ обозначениях подраздела 1.2.6 D — С U (А \ В).СЛЕДСТВИЕ Все подмножества конечного множества конечны.1.2.4. Добавление и удаление элементовЕсли А — множество, а х — элемент, причём х <£ А, то элемент х можно добавитьв множество А:А + £=f {у | у е А V у — ж} .Аналогично, если А — множество, а х — элемент, причём х е А, то элемент хможно удалить из множества А:A - x^f{у\уе А & у ф х} .Легко видеть, что при удалении и добавлении конечного числа элементов конечные множества остаются конечными, а бесконечные — бесконечными.ОТСТУПЛЕНИЕНа самом деле операции добавления и удаления элементов являются частными случаями операций объединения и разности множеств, рассматриваемых в подразделе 1.2.6(А + х = A U {х}, А - х = А \ {х}), и потому, строго говоря, излишни.
В стандартныхучебниках по теории множеств такие операции не рассматриваются и не упоминаются.Здесь они введены для упрощения обозначений. Такой подход акцентирует «программистское» отношение к математике: мы вводим новые операции, если это практическиудобно, даже если это теоретически излишне.1.2.5. Мощность конечного множестваТЕОРЕМА 1 Любое непустое конечное множество равномощно некоторому отрезку натурального ряда:VA {А ф 0 & |Л| < оо3k е N {\А\ = |l..fc|)).331.2. Алгебра подмножествРассмотрим следующую программу:г: = 0 { счётчик элементов }while А Ф 0 doselect х е А { выбираем элемент }г: = г + 1 { увеличиваем счётчик }х I—> г { ставим элементу в соответствие его номер }А: = А - х { удаляем элемент из множества }end whileДОКАЗАТЕЛЬСТВОЕсли эта программа не заканчивает работу, то она даёт соответствие В ~ Nдля некоторого множества В с А, что невозможно ввиду конечности А.
Значит,процедура заканчивает работу при г = к. Но в этом случае построено взаимнооднозначное соответствие А ~ 1..к.•Л ЕМ М А Любое непустое подмножество множества натуральных чисел содержитнаименьший элемент.Пусть А — произвольное подмножество множества натуральных чисел, конечное или бесконечное. Рассмотрим задание множества А следующей порождающей процедурой:ДОКАЗАТЕЛЬСТВОА : = {пG N | п : = 0 ; w h i l e t r u e d o п: = п + 1; i f п е A t h e n y i e l d п e n d i f e n d w h i l e } .Ясно, что множество А действительно порождается этой процедурой, причём тотэлемент, который порождается первым, является наименьшим.•ТЕОРЕМА 2Любой отрезок натурального ряда конечен:Vn € N (|1..п| < оо).О Т противного.
Пусть существуют бесконечные отрезки натурального ряда. Рассмотрим наименьшее п такое, что |1..п| = оо. Тогда отрезок 1 ..правпомощеп некоторому своему собственному подмножеству А, |1..п| = \А\, тоесть существует взаимпо-однозпачпое соответствие между отрезком \..п и подмножеством А. Пусть при этом соответствии п н-• г. Рассмотрим соответствиемежду отрезком l..(n — 1) и его собственным подмножеством А — г, задаваемоесоответствием между 1 ..п и А.
Это соответствие является взаимпо-однозначпым,а значит, отрезок 1 ..(п — 1) изоморфен своему собственному подмножеству иявляется бесконечным, что противоречит выбору п.•ДОКАЗАТЕЛЬСТВОСЛЕДСТВИЕРазличные отрезки натурального ряда неравномощны:п фт\1..п\ ф \1..т\.Пусть для определённости п > т. Тогда 1..т с 1 . . п и 1 . . т ^ 1 ..п.Если |1..п| = |1..т|, то |1..т| = оо, что противоречит теореме.•ДОКАЗАТЕЛЬСТВО34Глава 1. Множества и отношенияГоворят, что конечное множество А имеет мощность к (обозначения: \А\ = к,card Л = к, #А = к), если оно равиомощно отрезку 1..к:\А\ = кD=A~l..k.ЗАМЕЧАНИЕТаким образом, если множество А конечно, \А\ = к, то элементы А всегда можно перенумеровать, то есть поставить им в соответствие номера из отрезка l..fc с помощьюнекоторой процедуры.
Наличие такой процедуры подразумевается, когда употребляетсязапись А = {ai,..., a*,}.По определению |0| = 0.1.2.6. Операции над множествамиОбычно рассматриваются следующие операции над множествами:объединение:= F {Х I X GАивAV I GВ}\пересечение:А Г) В=F{X|ZGАЬхеву,разность:=f{x|zG АА\В&х£В}\симметрическая разность:АДВ =f (AUВ) \ (АПВ) = {х | (Х € Ах £ В)V(х$А&хG 5)};дополнение:A =f {х | х £ А}.Операция дополнения подразумевает, что задай некоторый универсум U:А = U \ А.
В противном случае операция дополнения не определена.Пример Пусть А: ={1,2,3}, В-. ={3,4,5}. Тогда АиВ = {1,2,3,4,5}, АГ)В = {3},А\В = {1,2}, А Л В = {1,2,4,5}. Если определён универсум U : ={0,1,2,3,4,5,6,7,8,9}, то А = {0,4,5,6,7,8,9}, В = {0,1,2,6,7,8,9}.На рис. 1.2 приведены диаграммы Венна1, иллюстрирующие операции над множествами. Сами исходные множества изображаются фигурами (в данном случаеовалами), а результат выделяется графически (в данном случае для выделенияиспользована штриховка).1Джон Вепн (1834-1923).351.2. Алгебра подмножествРис. 1.2. Операции над множествамиЕсли множества А и В конечны, то из определений и рис.
1.2 нетрудно видеть,что\А U В\ = \А\ + \В\\А\В\=-\АПВ\,\А\-\АПВ\,\А к В\ = \ А\ + \В\— 2\АП В\.Операции пересечения и объединения двух множеств допускают следующее обобщение. Пусть задано семейство множеств {Ai}ieJ. Тогда[jAiD={x\3iel(яеЛОЬf)AiD={x\Viel(®еЛ4)}.1.2.7. Разбиения и покрытияПусть £ = {Ei} i £ l — некоторое семейство подмножеств множества М, Ei с М.Семейство £ называется покрытием множества М, если каждый элемент Мпринадлежит хотя бы одному из EfVx Е М (3iel( I G Е{)).Семейство £ называется дизъюнктным, если элементы этого семейства попарнопе пересекаются, то есть каждый элемент множества М принадлежит не болеечем одному из множеств Ef.V i J el{ i ^ j ^ E i n Ej= 0).Дизъюнктное покрытие называется разбиением множества М. Элементы разбиения, то есть подмножества множества М, часто называют блоками разбиения.36Глава 1. Множества и отношенияПример Пусть М : ={1,2,3}.
Тогда {{1,2}, {2,3}, {3,1}} является покрытием,по не разбиением; {{1}, {2}, {3}} является разбиением (и покрытием), а семейство {{1}, {2}} является дизъюнктным, по не является ни покрытием, ни разбиением.Если£ = {Ei}iel есть дизъюнктное семейство подмножеств множества М, то существует разбиение Ъ = {£?i}te/ множества М такое, что каждыйэлемент дизъюнктного семейства £ является подмножеством блока разбиения Ъ:ТЕОРЕМАviei(EiCBi).Выберем произвольный элемент го G / и построим семействоследующим образом:ДОКАЗАТЕЛЬСТВОЪ = {Bi}ieIBi0=M\(JEi,ViGJ-го(Bi =Ei).Семейство Ъ по построению является дизъюнктным покрытием, то есть разбиением.
Ясно, что Ei0 с Bi0, а для остальных элементов требуемое включениеимеет место по построению.•Пример Пусть М : = { 1,2,3}. Тогда элементы дизъюнктного семейства {{1}, {2}}являются подмножествами блоков разбиения {{1}, {2,3}}.1.2.8. БулеанМножество всех подмножеств множества М называется булеаном множества Ми обозначается 2 м :2 м = f {А|А с М] .Если множество М конечно, то |2 М | = 2' м !.ДОКАЗАТЕЛЬСТВОИндукция по \М\. База: если \М\ = 0, то М = 0 и 2 0 = {0}.Следовательно, |2 0 | = |{0}| = 1 = 2° = 2'01. Индукционный переход: пустьVM (|М| < k|2 М | = 2l M | ).
Рассмотрим М = {аъ...,ак},\М\ = к. ПоложимMi : = { Х С 2 м | а к $ X ) и М 2 : = {X С 2 м | а к G X } .ТЕОРЕМАИмеем 2 м = Mi U М2, Mi П М2 = 0 , Mi ~ М2 за счёт взаимно-одпозначпогосоответствия X н-> X + ак и Mi ~По индукционному предположению |2^ ai ' --.afc-i}| = 2 fc_1 , и значит, |Mi| = |Мг| = 2 f c _ 1 . Следовательно,\2М\ = |Mi| + |М 2 | = 2 fc - 1 += 2к = 2lMl.•Пересечение, объединение и разность подмножеств множества U (универсума)являются его подмножествами, то есть применение операций к подмножествамуниверсума не выводит за его пределы. Множество всех подмножеств множества U с операциями пересечения, объединения, разности и дополнения образуеталгебру подмножеств множества U.371.2.
Алгебра подмножеств1.2.9. Свойства операций над множествамиОперации над множествами обладают целым рядом важных свойств, которыерассматриваются в этом подразделе. Пусть задай универсум U. Тогда V Л, В, С с Uи выполняются следующие равенства:1) идемпотентность:AUA = А, АПА = А;коммутативность:AUB = BUA,АпВ = В ПА;ассоциативность:A U (В U С) = (A U В). U С, А П (В П С) = {А П В) П С;дистрибутивность:А И (В П С) = {A U В) П (Л U С), А П (В U С) = (А П В)поглощение:{А П В) U А = A , (A U В) П А = А;свойства нуля:AU0 = А, АП0 = 0;свойства единицы:AUU = U, A nU = А]инволютивность:1= А;законы де МорганаА ПВ = AUB,AUB = АпВ;10) свойства дополнения:АиА = [/, АпА = 0;11) выражение для разности:А \ В = А П В.U(АПС);В справедливости перечисленных равенств можно убедиться различными способами. Например, можно нарисовать диаграммы Веипа для левой и правой частейравенства и убедиться, что они совпадают, или же провести формальное рассуждение для каждого равенства.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
