Основные понятия алгебры множеств
Алгебрамножеств лежит в основе многих разделов современной математики. Для неепрактически невозможно установить точную дату открытия и назвать имяпервооткрывателя. Алгебра множеств постепенно развивалась на фонемногочисленных попыток найти строгое математическое основание для Аристотелевойлогики. Некоторые предпосылки этой алгебры содержатся в трудах Лейбница. Вразработку основ этой алгебры внесли значительный вклад многие известные логикии математики (Ж.Д.Жергонн, А. де Морган, Дж. Венн и др.). Но особая заслуга вее развитии и распространении принадлежит Леонарду Эйлеру.
В 1736 г. в«Письмах к германской принцессе о различных физических и философскихматериях» Л. Эйлер в популярной форме изложил свое понимание Аристотелевойсиллогистики. При этом он использовал наглядные схемы, которые впоследствииполучили название «круги Эйлера». В дальнейшем круги Эйлера сталииспользовать не только в учебных курсах по логике, но также и при изложенииазов многих основополагающих разделов современной математики, в которыхиспользуется алгебра множеств. Здесь воспользуемся этими нагляднымиотображениями, позволяющими достаточно быстро овладеть абстрактными понятиямиалгебры множеств.
Идеи Эйлерабыли развиты в работах французского астронома и математика Ж. Д. Жергонна.Жергонну удалось в опубликованной в 1817 г. работе «Основы рациональнойдиалектики» представить все классы суждений, выделенных Аристотелем, спомощью соотношений между множествами. Эти соотношения получили в математике илогике название «жергонновых отношений». Рассмотрим их болееподробно.
В основе силлогистики лежат простые суждения,представленные четырьмя типами: A – общеутвердительное (все X есть Y); E –общеотрицательное (все X не есть Y); I – частноутвердительное (некоторые X естьY); O – частноотрицательное (некоторые X не есть Y). Отметим, что в трудахАристотеля смысл суждений отличается от общепринятого – этот смысл вместе собозначениями утвердился в логике после работ известного схоласта ПетраИспанского. Сам Аристотель не употреблял в суждениях двусмысленную связку «есть»и формулировал суждения следующим образом:
A: Y присущевсем X
E: Y неприсуще всем X
I: Y присущенекоторым X
O: Y неприсуще некоторым X
Термины X и Yможно представить как некоторые совокупности (множества, классы) в виде круговЭйлера. Жергонн выделил 5 возможных соотношений между ними (рис. 1).
/>
Рис. 1
Каждый типЖергонновых отношений имеет собственное название:
G1– совпадение или равнозначность;
G2– левостороннее включение;
G3– частное совпадение;
G4– правостороннее включение;
G5– несовместимость.
Жергоннпоказал, что каждый тип Аристотелевского суждения соответствует некоторым типамэтих отношений, в частности:
- типу Aсоответствует G1 или G2;
- типу E соответствует G5;
- типу I: соответствует G1 или G2 или G3 или G4;
- типу O: соответствует G3 или G4 или G5.
Например,суждение типа I означает, что некоторая непустая часть множества или класса Xсодержится в Y. Посмотрев на рисунок, нетрудноубедиться, что этому условию удовлетворяют все типы Жергонновых отношений кромеG5. В логике слово «некоторые» используется вшироком смысле: «хотя бы один, но не исключено, что и все».Жергонновы отношения часто использовались для строгого обоснования не толькоправил вывода для простого категорического силлогизма, в котором в качествепосылок используются только два суждения, но и для более сложных умозаключений,когда в качестве посылок допускается произвольное число суждений. Вершинойанализа такого рода можно считать работы английского логика и философа Дж.Венна (1834–1923).
Однакоприменение жергонновых отношений в логике связано с рядом трудностей. Главнойиз них является то, что практически для всех типов суждений (за исключениемтипа E) можно использовать несколько вариантов Жергонновых отношений, и приувеличении количества исходных суждений число возможных вариантов анализавозрастает в степенной зависимости. Если допустим, рассматриваем сложноерассуждение, содержащее много суждений, то должны для каждого суждения просмотретьвсе соответствующие ему варианты Жергонновых отношений. Однако работы Эйлера,Жергонна, Венна и многих других стали своеобразной «затравкой» длясоздания алгебры множеств.
С точкизрения современной математики алгебра множеств относится к классу алгебраическихсистем, т.е. структур, в которых имеются (даны):
1) носитель – некоторая совокупностьобъектов (например, числа, геометрические фигуры, слова, множества и т.д.);
2) совокупность отношений (например,больше, меньше, равно и т.д);
3) совокупность операций (например,сложение, умножение, пересечение и т. д).
Заметим, чтосмысловая разница между отношением и операцией заключается в следующем: еслизадано некоторое отношение между объектами, то о нем можно только сказать,истинно оно для данных объектов или нет (например, «2 > 3»является ложным отношением), в то время как в результате некоторой операции собъектами получается некоторый новый объект (например, «2+3=5»).
В алгебремножеств носителем является некоторая совокупность множеств. Основными понятиямиалгебры множеств считаются понятия множество и элемент. Соотношение между ниминазывается отношением принадлежности и обозначается знаком "Î". Запись
bÎA
переводится ссимволического языка как «bявляетсяэлементом множества A» или «элемент b принадлежит множеству A». Если известны все элементымножества (например, a, b и c), то общепринятой является такая записьмножества:
A={a,b,c}.
В этом случаеэлементы множества принято заключать в фигурные скобки. Кроме того, приперечислении элементов порядок несущественен, т.е. A={a,b,c}={c,b,a}={a,c,b} и т.д.
Множествамогут быть заданы двумя способами: с помощью формулировки характерных признаков(например, множество Kцифр, обозначающих четные числа) или с помощью перечисления элементов(например, K = {0, 2, 4, 6, 8})
В современнойматематике пока что нет четкого определения отношения принадлежности. В алгебремножеств этой неопределенности можно избежать, если считать, что это отношениесвязывает два разных типа объектов («элемент»Î«множество»), но ни в коемслучае не должно быть связи типа «множество»Î«множество».
Междумножествами устанавливается другое вроде бы похожее, но в то же времяпринципиально отличающееся отношение – включение, структурные свойства которогов современной математике определены достаточно четко и однозначно. Рассмотримего более подробно. Допускаются два отличающихся варианта этого отношения:
"Ì" – строго включено;
"Í" – включено или равно.
Запись AÌB означает, что множество A включенов множество B, т.е. все элементы множества A являются одновременно элементами множества B, но при этом невозможно равенствоэтих множеств. Запись AÍB означает, что множество A включено в множество B, но при этом неисключается, что они могут быть равными. Изображение отношения включения спомощью кругов Эйлера показано на рисунке 2. В данном случае не обязательноиспользовать правильные круги. Для изображения множества может подойти любаязамкнутая фигура.
/>
Рис. 2
Еслимножества заданы с помощью перечисления элементов, то отношение включения (илиневключения) одного множества в другое множество можно легко установить, еслисравнить элементы этих множеств. Например, если заданы множества
P={a, b, c, d, e}; Q ={b, d, a}; R ={a, c, f},
то можно легкоустановить, что QÌP, но в то же время отношение RÌP для этих множеств неверно, так как элемент f из множества R не является элементом множества P.
Порядокперечисления элементов для множеств несущественен. Например, множества {b,d,a};{a, b, d}; {d, a, b} – это по сути одно и то же множество. Если же порядокперечисления множеств является существенным, то в этом случае имеем дело не смножествами, а с последовательностями или с упорядоченными множествами(некоторые сведения о них приведены ниже). Математические свойствапоследовательностей существенно отличаются от математических свойств множеств.
Заметим, чтонесходство отношений принадлежности и включения можно иллюстрировать следующимпримером. Допустим, aÎP, изчего следует, что a являетсяэлементом, а P – множеством. Можно ли в этом случаезаписать aÍP? Оказывается, нельзя, потому чтоотношение включения применимо только для двух множеств. Правильной в этомслучае является запись {a}Í P, в которой слева записан не элемент, а одноэлементноемножество.
Рассмотримеще одно отношение между множествами – отношение равенства. Множества равны,если у них одни и те же элементы. Для доказательства равенства двух множеств,особенно в тех случаях, когда у них большое или бесконечное число элементов,используется следующее определение.
Определение1. Множества A и B равны, если справедливо как AÍB, так и BÍA.
Еслимножества связаны отношениями AÌB или AÍB, то в этом случае множество A называют подмножеством множества B. Средивсех возможных подмножеств произвольного множества A обязательно содержитсятакже и само множество A. Другими словами, для любого множества A всегдасправедливо AÍA.
В алгебремножеств особо выделяется и часто используется множество, которое называется «пустоемножество» (обозначается "Æ"). Интуитивно пустое множество означает множество, несодержащее никаких элементов. Но это интуитивное определение не раскрываетполностью его сути и роли в алгебре множеств. В большей степени его сутьраскрывается в следующем предложении, которое можно отнести к одной из аксиомалгебры множеств:
Пустоемножество включено в любое множество.
Для пояснениясмысла этого предложения рассмотрим следующий пример. Пусть A – множествокрокодилов. Ясно, что это множество может иметь какие-то подмножества.Например, множество C крокодилов, живущих в зоопарках. Тогда отношение между Aи C можно записать как CÌA. Рассмотрим еще одно подмножество множества A: подмножество крокодилов,говорящих на русском языке. Ясно, что это пустое множество и, тем не менее,можем его считать подмножеством множества A. В математических рассуждениях,когда нам надо доказать, что данное множество X не существует (или существует),сводим доказательство существования к доказательству отношения X=Æ (или X¹Æ). Часто такой метод позволяетнамного упростить доказательство.
Еслимножество задано перечислением элементов, то часто интерес представляетсовокупность всех подмножеств этого множества. Например, для множества A={a, b,c} такая совокупность состоит из восьми подмножеств:
Æ, {a},{b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}.
Самомножество А является подмножеством самого себя. Известно также простоесоотношение, позволяющее сразу же узнать общее число всех возможных подмножествмножества, содержащего ровно N элементов. Оказывается, что для любого N такоечисло равно 2N. Например, для нашего множества A={a, b, c} числовсех возможных подмножеств равно 23.
Обычно вомногих рассуждениях используется некоторый набор множеств. Такой наборназывается в алгебре множеств системой множеств. В систему множеств при этомпомимо пустого множества включается и универсум, т.е. множество, для котороговсе множества системы множеств являются подмножествами. Другими словами,системой множеств является некоторая совокупность подмножеств некоторогомножества, принятого за универсум. Например, для множеств планет, комет, звезди т.д. в качестве универсума можно принять множество астрономических объектов.
Дляуниверсума нет общепринятых обозначений. Далее будем обозначать его символом U.
Перейдем коперациям. Начнем с операции дополнения, которая может быть определена толькотогда, когда для системы множеств задан универсум.
Определение2. Дополнением множества A называется множество />,содержащее все элементы универсума, которые не являются элементами множества A.
В логикедополнению множества соответствует связка «не». Например «некрасный» – любой возможный цвет кроме красного. Обычно дополнениемножества обозначается с помощью черты, расположенной над символьнымобозначением этого множества. Например, /> являетсяобозначением дополнения множества />.
Пример 1.Пусть U={a, b, c, d} и P={a, c}. Тогда />={b,d}.
Определим ещедве основные операции – пересечение и объединение множеств.
Определение3. Пересечением множеств A и B называется множество C, все элементы которогоявляются одновременно элементами множеств A и B.
Операцияпересечения множеств обозначается символом "Ç". Символически определение 3можно записать как формулу
C = AÇB.
Например,пересечением множества всех студентов данного вуза и множества всех участниковКВН, является множество студентов данного вуза, участвующих в КВН. Другойпример: пересечением множества всех чисел, делящихся на 2, и множества всехчисел, делящихся на 3, является множество всех чисел, делящихся на 6.
В логикеоперации пересечения соответствует логическая связка «И»(обозначается как Ù или &). Еслиречь идет об объектах со свойствами P или Q, то логическая формула PÙQ означает, что речь идет только обобъектах, которым присущи оба этих свойства. Если, допустим, свойствам P и Qсоответствуют некоторые множества SP и SQ, то пересечениеэтих множеств SPÇSQ, будет состоять из элементов, каждому изкоторых одновременно присущи свойства P и Q
Пример 2.Пусть A={a, b, c, d} и P={a, c, f}. Тогда AÇP = {a, c}.
Определение4. Объединением множеств A и B называется множество C, все элементы которогоявляются элементами по крайней мере одного из этих множеств.
Операцияобъединения множеств обозначается символом "È". Символически определение 4можно записать как формулу
C=AÈB
В логикеоперации объединения соответствует логическая связка «ИЛИ»(обозначается "Ú"). Если речь идет об объектах со свойствами P или Q, то логическаяформула PÚQозначает, что речь идет только об объектах, которым присуще хотя бы одно изэтих свойств. При этом допускается, что объекты, которым присущи оба этихсвойства, также относятся к этому классу объектов.
Пример 3.Пусть A={a, b, c, d} и P={a, c, f}. Тогда AÈP = {a, b, c, d, f}.
Обратитевнимание, что в примере 3 элементы a и c, которые содержатся в каждом измножеств A и B, в объединении C не удваиваются, а содержатся как однократные. Вматематике и ее приложениях иногда используют множества с кратными элементами(они называются мультимножествами), но нам такие множества не понадобятся. Втаких множествах нарушаются некоторые законы обычной алгебры множеств.
Операциидополнения, пересечения и объединения являются основными операциями алгебрымножеств.
Определение5. Разностью множеств A и B называется множество C=A\B, которое содержит толькоте элементы множества A, которые не являются одновременно элементами множестваB.
Пример 4.Пусть A={a, b, c, d} и B={a,c, f}. Тогда A\B = {b, d}.
Важноотметить, что разность множеств является производной операцией. Это означает,что ее можно выразить с помощью других основных операций – для разностимножеств справедливо следующее соотношение:
A\B = AÇ/>.
Если впримере 4 задать универсум, например, U = {a, b, c, d, e, f}, то нетрудноубедиться в справедливости этого равенства:
/>= {b, d, e}; тогда A\B =AÇ/>= {b, d}.
В то же времяоперацию дополнения можно выразить с помощью операции разности: />=U\A. В некоторых версияхалгебры множеств операция разности множеств представлена как основная операция,а операция дополнения – как производная операция. Однако основные соотношения(или законы) алгебры множеств при этом остаются неизменными.
На рисунке 3соответствующие операции над множествами изображены с помощью «круговЭйлера». Серым цветом показаны результаты операций.
/>
Рис. 3
Здесьхотелось бы обратить внимание на следующее важное обстоятельство. Для множествA и B, у которых нет общих элементов, справедливы следующие соотношения:
AÇB = Æ; A Í />; B Í/>.
Ситуацию,соответствующую этим соотношениям, можно наглядно отобразить с помощьюдиаграммы Эйлера (рис. 4).
/>
Рис. 4
Теперь у насвполне достаточно понятий для того, чтобы отобразить в виде математическойформулировки заданные суждения. Например, суждение «Все члены палатылордов носят титул пэра» то расчленяется на субъект «члены палатылордов» (A) и предикат «носят титулпэра» (B). Тогда математической формулойданного суждения будет
A Í B.
Это означает,что все члены палаты лордов включены в множество тех, кто носит титул пэра.Более сложное суждение, например, «Все члены палаты лордов носят титулпэра и находятся в здравом рассудке» можно выразить, используя двапредиката: «носят титул пэра» (B) и «находятся в здравом рассудке» (С). Тогдаполучим следующую математическую формулировку:
AÍ(B Ç C). (1)
В случае,когда в суждении имеются предикаты с отрицаниями, используем в математическойзаписи операцию дополнения. Например, суждение «Все члены палаты лордовносят титул пэра и не принимают участия в скачках на мулах», можнозаписать как
AÍ(B Ç/>), (2)
где D – предикат «принимают участие вскачках на мулах».
Еслииспользовать диаграммы Эйлера, то получим наглядное изображение формул (1) и(2) (рисунки 5 и 6).
/>
Рис. 5
/>
Рис. 6
Количественныесоотношения в диаграммах Эйлера (т. е. в данном случае – площади фигур) непринимаются во внимание. Среди наших знаний немало таких, когда не знаем, чемуравно число элементов множества, но это не мешает нам знать о том, чтонекоторые из таких множеств строго включены в некоторые другие множества, иличто некоторые из таких множеств точно не содержат общих элементов с некоторымидругими множествами. Количественный анализ множеств во многих случаях являетсясоставной частью наших знаний.
Вматематическую форму суждений можно перевести многие предложения естественногоязыка.
Законыалгебры множеств – это по сути теоремы, которые выводятся из основныхопределений и аксиом. Часто приводятся 26 или 28 законов алгебры множеств.Приведем без доказательства лишь некоторые из них, необходимые для ясногопонимания дальнейшего. Пусть A, B, C – некоторые произвольные множества вуниверсуме U. Тогда законами алгебры множеств являются следующие соотношениямежду ними.
1. />=A.
Пример 5.Пусть U={a, b, c, d} и P={a, c}. Тогда />={b,d} и />={a, c}=P.
В алгебремножеств это соотношение (двойное дополнение) носит название закон инволюции. Влогике этот закон известен под названием закон отрицания отрицания (или закондвойного отрицания): не (не-A) – то же самое, что и A.
2. A Ç/> = Æ (множество и его дополнение не имеютобщих элементов)
В логикеэтому закону соответствует закон непротиворечия (утверждение и его полноеотрицание логически несовместимы).
3. A È/> = U.
В логикеэтому закону соответствует закон исключенного третьего (совмещение любогоутверждения и его полного отрицания не допускает присутствия какого-либотретьего промежуточного варианта).
Следующиесоотношения характеризуют более подробно свойства пустого множества иуниверсума:
4. /> = U;
5. /> = Æ
6. AÇÆ = Æ;
7. AÈÆ = A;
8. AÇU = A;
9. AÈU = U.
Следующиезаконы алгебры множеств связывают друг с другом отношения включения иравенства:
10. Из AÍB следует:
10a. AÇB = A;
10b. AÈB = B;
10c. />ÈB = U;
10d. AÇ/> = Æ.
Соотношение10d можно выразить также с помощью операции разности множеств:
10e. Из AÍB следует A\B = Æ.
Следующиезаконы в логике и алгебре множеств называются законами де Моргана:
11a. />=/>È/>;
11b />=/>Ç/>.
И, наконец,приведем два закона, которые определяют основные свойства отношения включения.Их используют в дальнейшем в правилах логического вывода.
12a. Если AÍB и BÍC, то AÍC (закон транзитивности включения);
12b. Если AÍB, то справедливо также и />Í/> (закон контрапозиции).
Вматематической литературе приводятся разные способы обоснования этих законов.Многие из них весьма сложны для понимания. Здесь рассмотрим относительнопростой способ, который называется комбинаторным.
Пусть намнеобходимо вывести некоторые законы для двух множеств X и Y. Рассмотримдиаграмму Эйлера (рисунок 7), на которой изображены эти множества и объемлющийих универсум (U).
/>
Рис. 7
Выделим надиаграмме участки a, b, c и d,которые не имеют внутренних границ, т.е. выполним разбиение нашего универсумана непересекающиеся друг с другом множества. Такое разбиение позволяет нампредставить эти множества как элементы, из которых состоят универсум U и множества X и Y. Тогда для нихсправедливы соотношения:
U= {a, b, c, d}; X = {a, b}; Y = {b, c}.
Примем этисоотношения в качестве исходных данных и докажем для этого общего представленияданной системы из двух множеств один из законов де Моргана />=/>È/>. Тогда получим:
1) XÇY = {b};
2) />= {a, c, d};
3) />= {c, d};
4) />= {a, d};
5) />È/>={a, c, d};
6) сравнивая 2 и 5 заключаем, что />=/>È/>, что и требовалось доказать.
Законтранзитивности (12a) интуитивнопонятен. Рассмотрим обоснование закона контрапозиции (12b). Поскольку он действителен только втом случае, когда X Í Y, то придется немного изменить нашу исходную систему. Дляэтого примем, что множество, представленное в системе элементом a, равно пустому множеству, и поэтомуего можно исключить из универсума. Тогда получим следующие исходные данные:
U = {b, c, d}; X = {b}; Y = {b, c}.
Ясно, что вэтой системе соотношение X Í Y соблюдается.Приступим к доказательству.
1) />= {c, d};
2) />= {d};
3) сравнивая />и/>, убедимся, что />Í/>, что и требовалось доказать.
Литература
1. Алгебра и началоанализа – Высшая школа – М. 2003 г.
2. Алгебра – подред. Бутинець К.К. – К. – 2000 г.