Доказательство законов алгебры множеств

Рассмотренные операции над множествами подчинены некоторым законам, которые напоминают известные элементарные законы алгебры чисел. Этим определяется название алгебра множеств, которую часто называют булевой алгеброй множеств, что связано с именем английского математика Джона Буля, который положил в основу своих логических исследований идею аналогии между алгеброй и логикой.

Для произвольных множеств А, В, и С справедливы следующие тождества (табл. 3.1):

1. Закон тождества

2. Коммутативность объединения

2’. Коммутативность пересечения

3. Ассоциативность объединения

3’. Ассоциативность пересечения

4. Дистрибутивность объединения относительно пересечения

4’. Дистрибутивность пересечения относительно объединения

5. Законы действия с пустым и универсальнымU множествами

(закон исключённого третьего)

5’. Законы действия с пустым и универсальнымU множествами

(закон противоречия)

6. Закон идемпотентности объединения

6’. Закон идемпотентности пересечения

7. Закон де Моргана

7’. Закон де Моргана

8. Закон элиминации (поглощения)

8’. Закон элиминации (поглощения)

9. Закон склеивания

9’. Закон склеивания

10. Закон Порецкого

10’. Закон Порецкого

11. Закон инволюции (двойного дополнения)

Законы алгебры множеств по отношению к операциям пересечения () и объединения () подчинены принципу двойственности: если в каком-либо законе все знаки пересечения заменить знаками объединения, а все знаки объединения – знаками пересечения, знак универсума (U) заменить знаком пустого множества (Ø), а знак пустого – знаком универсума, то получим снова верное тождество. Например (в силу этого принципа), из следует и т. п.

3.1. Проверка истинности тождеств при помощи диаграмм Эйлера-Венна

Все законы алгебры множеств можно наглядно представить и доказать, используя диаграммы Эйлера-Венна. Для этого необходимо:

Начертить соответствующую диаграмму и заштриховать все множества, стоящие в левой части равенства.

Начертить другую диаграмму и сделать то же для правой части равенства.

Данное тождество истинно тогда и только тогда, когда на обеих диаграммах заштрихована одна и та же область.

Замечание 3.1. Два пересекающихся круга делят всё универсальное множество на четыре области (см. рис.3.1)

А  ;

В;

.

Замечание 3.2. Три пересекающихся круга делят всё универсальное множество на восемь областей (см. рис.3.2):

А В  ;

А   С;

А   ;

В  ;

С;

.

Замечание 3.2. При записи условий различных примеров часто используются обозначения:

 – тогда и только тогда, когда… .

Задача 3.1. Упростить выражения алгебры множеств:

;

;

.

;

Задача 3.3. Доказать следующие соотношения двумя способами: с помощью диаграмм и с помощью определения равенства множеств.

1. Доказательство с помощью диаграммы:

2. Доказательство с помощью определения равенства множеств.

По определению, множества Х и Y равны, если одновременно выполнены соотношения: XY и YX.

Сначала покажем, что . Пустьх – произвольный элемент множества , то естьх. Это означает, чтохU и х. Отсюда вытекает, чтохА или хВ. Если хА, то тогда хĀ, а значит, . Если жехВ, то , а значит,. Таким образом, всякий элемент множества .. есть также элементом множестваТо есть

Теперь докажем обратное, то есть, что . Пусть. ЕслихĀ, то хU и хА, а значит, хАВ. Отсюда следует, что . Если же, тохU и хВ. Значит, хАВ, то есть . Отсюда следует, что всякий элемент множестваявляется также элементом множества, то есть.

Значит, , что и требовалось доказать.

1. Доказательство с помощью диаграммы:

2. Доказательство с помощью определения равенства множеств.

Пусть хА(ВС). Тогда хА и хВС. Если хВ, то хАВ, что не противоречит сказанному, а значит, х(АВ)(АС). Если же хС, то хАС. Следовательно, х(AB)(AC). Итак, доказано, что A(BC)  (AB)(AC.

Пусть теперь х (AB)(AC). Если хАВ, то хА и хВ. Отсюда следует, что хА и хВС, то есть хА(ВС). Если же хАС, то хА и хС. Отсюда вытекает, что хА и хВС, то есть хА(ВС). Таким образом, (AB)(AC) A(BC). Следовательно, A(BC) = (AB)(AC). Что и требовалось доказать.

Пересечение множеств А и В есть подмножеством множества С тогда и только тогда, когда множество А является подмножеством объединения множеств не-В и С.

При доказательстве достаточности мы получили, что АВ=. Очевидно, что С, поэтому соотношение доказано. При доказательстве был рассмотрен самый общий случай. Однако здесь возможны ещё некоторые варианты при построении диаграмм. Например, случай равенства АВ=С либо , случай пустых множества и так далее. Очевидно, что все возможные варианты учесть бывает затруднительно. Поэтому считается, что доказательство соотношений с помощью диаграмм не всегда является корректным.

2. Доказательство с помощью определения равенства множеств.

Необходимость. Пусть АВС и элемент хА. Покажем, что в этом случае элемент множества А будет являться также и элементом множества .

Рассмотрим два случая: хВ или .

Если хВ, то хАВС, то есть хС, и, как следствие этого, .

Если же , то и. Необходимость доказана.

Пусть теперь ихАВ. Покажем, что элемент х также будет элементом множества С.

Если хАВ, тогда хА и хВ. Поскольку , значитхС. Достаточность доказана.

Если множество А является подмножеством множества В, то тогда множество будет подмножеством множества Ā.

1. Доказательство с помощью диаграммы:

2. Доказательство с помощью определения равенства множеств.

Пусть АВ. Рассмотрим элемент хВ (или ). Аналогично:хА (или хĀ). То есть всякий элемент множества есть также элементом множества Ā. А это может быть в случае, если. Что и требовалось доказать.

Задача 3.4. Выразить символически указанные области и упростить полученные выражения.

Искомая область состоит из двух изолированных частей. Условно назовём их верхней и нижней. Множество, которое они изображают, можно описать так:

Из определения операций над множествами получим:

Запишем это выражение с помощью основных операций – дополнения, объединения и пересечения:

.

Упростить это выражения нельзя, поскольку имеем по одному вхождению каждого символа. Это и есть простейший вид данной формулы.

Данную область можно рассматривать как объединение множеств АВС и АВС. По определению M = <x xA и xВ и хС или хА и хВ и хС>. Упростим:

Задачи для самостоятельного решения.

(ответ V).

2. Доказать с помощью диаграмм, законов алгебры множеств и определения равенства множеств:

3. Выяснить, существует ли множество Х, удовлетворяющее при любом А равенству:

1.8. Алгебра множеств и двойственность

Абстрактная алгебра занимается изучением операций, производимых над некоторыми элементами. К настоящему времени идеи абстрактной алгебры используются не только для математических методов, но и позволяют получать практические результаты. Операции объединения, пересечения и дополнения, производимые над множествами, удовлетворят определенным законам (или тождествам) и образуют алгебру множеств. Поскольку числовая алгебра появилась раньше, то возникает вопрос, какая из операций (пересечение или объединение) «похожа» на операцию сложения чисел и какая – на операцию умножения. Ответить на этот вопрос едва ли возможно. Для чисел, например, выполняется только дистрибутивность умножения относительно сложения, а в алгебре множеств рассматривают два закона дистрибутивности: пересечения относительно объединения и объединения относительно пересечения.

Важным при выполнении операций является их приоритет. Сначала выполняется операция дополнения, затем пересечения и затем объединения.

Множества удовлетворяют следующим законам (или тождествам):

Принцип двойственности алгебры множеств

Нетрудно заметить, что тождества в таблице располагаются парами, например первое тождество A ∩ B = B ∩ A имеет парное A ∪ B = B ∪ A, и это выполняется для всех остальных законов алгебры множеств.

Принцип двойственности состоит в том, что если верно какое-либо тождество, то тождество, полученное из него путем замены каждой из операций ∩, ∪, а также U и Ø на операции ∪, ∩, Ø и U, соответственно, будет также верно. Поэтому у любого тождества есть его «двойник», отличающийся тем, что у него каждая операция замена на парную ей (объединение на пересечение, а пересечение на объединение) и при этом пустое множество заменяется на универсальное, а универсальное на пустое. Принцип двойственности очень важен, поскольку если доказана истинность какого-либо выражения, то истинность двойственного ему можно не доказывать – оно будет истинно вследствие данного принципа. Например, для верного тождества

двойственное ему будет также верным тождеством

Или для верного тождества

1.9. Доказательство тождеств с множествами

Для доказательства равенства тождеств обычно используются четыре метода:

1) элементный метод;

2) диаграммы Венна;

3) табличный метод;

4) алгебраический метод.

Элементный метод основан на том, что для произвольно выбранного элемента x из множества, заданного в левой части тождества, доказывается, что этот элемент принадлежит и множеству правой части этого тождества. Затем выбирается произвольный элемент из правой части и показывается, что он входит и в левую часть. Вместе это доказывает, что оба множества состоят из одних и тех же элементов.

Докажем далее законы алгебры множеств.

Доказательство коммутативности (или сочетательного свойства) операций объединения и пересечения самоочевидно, поскольку ни в определении пересечения, ни в определении объединения ничего не говорится о порядке подмножеств.

Ассоциативность (или сочетательный закон) также просто доказывается. Покажем, что (A ∩ B) ∩ C ⊆ A ∩ (B ∩ C). Если x ∈ (A ∩ B) ∩ C, то x ∈ (A ∩ B) и x ∈ С, из x ∈ (A ∩ B) следует, что x ∈ А и x ∈ B, т. е. x принадлежит всем трем множествам A, B и C. Следовательно, x ∈ (B ∩ C) и x ∈ A ∩ (B ∩ C). Обратное включение показывается аналогично, поскольку множество в правой части тождества также образовано из элементов (и только из таких), которые входят в каждое из множеств A, B и C. Ассоциативность для операции объединения следует из того, что элементы в множестве левой части тождества и элементы в множестве правой части состоят из таких и только таких элементов, которые принадлежат по крайней мере одному из подмножеств A, B и C.

Идемпотентность означает, что если x ∈ A ∩ A, то, значит, x принадлежит пересечению множества A с самим собой, т. е. x принадлежит самому множеству A. Если элемент x ∈ A ∪ A, то x принадлежит объединению множества A с самим собой, т. е. и в этом случае он принадлежит только множеству A.

Докажем дистрибутивность пересечения относительно объединения.

Необходимо убедиться, что множества, стоящие в левой и правой частях этого тождества, состоят из одних и тех же элементов. Сначала покажем, что множество левой части включается в множество правой части.

Пусть x ∈ A ∩ (B ∪ C). Тогда по определению операции пересечения x ∈ A и x ∈ (B ∪ C). Если x ∈ B, то тогда x принадлежит и A и B и поэтому он принадлежит и их пересечению x ∈ (A ∩ B). Но поскольку x принадлежит объединению B и C, то он может принадлежать не только B, но и С и даже обеим этим множествам. Если x ∈ С, тогда он принадлежит и пересечению А и С, т. е. x ∈ (A ∩ C). Но отсюда можно видеть, что в любом из этих случаев x принадлежит к какому-то из множеств: либо (A ∩ B), либо (A ∩ C), и тогда в соответствии с определением операции объединения x принадлежит и объединению этих множеств x ∈ (A ∩ B) ∪ (A ∩ C) и поэтому A ∩ (B ∪ C) ⊆ (A ∩ B) ∪ (A ∩ C).

Теперь покажем, что множество из правой части включается в множество левой.

Пусть x ∈ (A ∩ B) ∪ (A ∩ C). Если x ∈ (A ∩ B), то отсюда x ∈ A и x ∈ В. Но поскольку x ∈ В, то он принадлежит и объединению множества В с любым другим множеством, в частности и с множеством С, т. е. x ∈ (B ∪ C). В связи с тем, что x входит в множество A и в множество (B ∪ C), то он входит и в их пересечение. Если же x ∈ (A ∩ C), то тогда x ∈ A и x ∈ С. Но поскольку x ∈ С, то он принадлежит и объединению В с любым другим множеством, т. е. x ∈ (B ∪ C). Поскольку и в этом случае x входит в оба множества: и в А и в (B ∪ C), то он входит и в их пересечение x ∈ A ∩ (B ∪ C), поэтому(A ∩ B) ∪ (A ∩ ∩ C) ⊆ A ∩ (B ∪ C).

Докажем теперь двойственное тождество, т. е. дистрибутивность объединения относительно пересеченияA ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C). Для этого надо показать, что всякий элемент x множества A ∪ (B ∩ C) принадлежит и множеству (A ∪ B) ∩ (A ∪ C). Если элемент x принадлежит множеству А, то он принадлежит и множеству A ∪ (B ∩ C), потому что оно содержит множество А. В то же время если x ∈ A, то он входит и в пересечение (A ∪ B) ∩ (A ∪ C). Допустим, x не является элементом множества А. Тогда он должен принадлежать пересечению (B ∩ C), а также каждому из множеств B и C в отдельности. Тогда по определению операции объединения x ∈ (A ∪ B) и x ∈ (A ∪ С). Из этого следует, что x принадлежит и пересечению этих множеств (A ∪ B) ∩ (A ∪ C). И в том и в другом случае x из левого множества входит и в правое. Пусть x принадлежит правому множеству. Тогда если он принадлежит множеству А, то он принадлежит и множеству A ∪ (B ∩ C) по определению объединения. Если он не принадлежит А, то тогда он принадлежит и В и С в отдельности, а значит, он принадлежит и пересечению (B ∩ C) и поэтому в каждом из этих случаев любой элемент из правого множества входит в левое множество, что и требовалось доказать.

Докажем законы поглощения.

Доказательство обоих законов очевидно. Пусть, например, x ∈ A ∩ (А ∪ В). Тогда мое x ∈ A и x ∈ (А ∪ В). Если допустить, что поскольку x принадлежит объединению А и В, то он принадлежит множеству В, но не принадлежит множеству А, но это приводит к противоречию, поскольку по определению пересечения x ∈ A. Другими словами, любой элемент левого множества может быть только из множества А.

Для доказательства закона де Моргана (A ∩ B)С = AC ∪ BC покажем сначала, что левое множество включается в правое (A ∩ B) С ⊆ AC ∪ BC. Пусть x∈(A ∩ B)С. Тогда x ∉ A ∩ B. Из этого следует, что х не входит в оба множества одновременно, т. е. он не входит либо в А, либо в В. Если он не входит в А, то тогда он входит в АС, а если он не входит в В, то тогда он входит в ВС. Отсюда следует, что х ∈ AC ∪ BC и поэтому (A ∩ B) С ⊆ AC ∪ BC.

Докажем теперь, что всякий элемент х из множества AC ∪ BC принадлежит и множеству (A ∩ B)С. Если x ∈ AС, то тогда x ∉ A и поэтому х не может принадлежать пересечению x ∉ A ∩ B. Если x ∈ ВС, то тогда x ∉ В и поэтому х также не может принадлежать пересечению x ∉ A ∩ B. В любом из этих случаев x ∉ A ∩ B и потому x ∈ (A ∩ B)С.

Докажем двойственный закон де Моргана (A ∪ B)C= = АC ∩ ВC. Поскольку элемент х принадлежит множеству (A ∪B)C тогда и только тогда, когда он не принадлежит ни множеству А, ни множеству В, то из этого следует, что он должен входить и в множество АC, и в множество ВC, т. е. в их пересечение АC ∩ ВC. С другой стороны, если х входит в пересечение АC ∩ ВC, то он не может входить ни в А, ни в В, потому что в пересечении дополнений множеств ни могут находиться элементы самих этих множеств. Но тогда х входит в дополнение к их объединению, т. е. x ∈ (A ∪ B)С, что и требовалось доказать.

Доказательство закона инволюции (AC)C = A следует из того факта, что любой элемент из U принадлежит либо А, либо AC. Поэтому когда берется дополнение к множеству А, то получается множество АС, а когда берется дополнение к АС, то снова получается множество А.

Законы дополнения и тождества очевидны и не требуют доказательства.

Второй метод доказательства равенства тождеств состоит в использовании диаграмм Венна. Однако здесь иногда приходится рассматривать всевозможные случаи, при которых множества не имеют общих элементов, пересекаются или вкладываются друг в друга.

Докажем, например, закон де Моргана (A ∩ B)С = AC ∪ BC. На рис. 1.9 представлены три случая: (а) когда А и В не пересекаются, (b) когда А включается в В и (с) когда в пересечение входят элементы и из А, и из В (имеется и случай, когда В включается в А, но он аналогичен случаю (b)). На рис. 1.9 (d), (e) и (f) показаны их дополнения. Далее на (а1), (b1) и (с1) показаны множества (AC ∪ BC) для каждого из этих случаев. Можно видеть, что на каждом рисунке области для множества (A ∩ B)С и множества (AC ∪ BC) одинаковые во всех трех случаях и поэтому эти множества равны.

Рассмотрим табличный метод доказательства равенства множеств. Докажем ассоциативность пересечения (A ∩ B) ∩ C = A ∩ (B ∩ C). Пусть имеется диаграмма Венна для трех множеств A, B и С из универсального множества U на рис. 1.10. Три овальные области представляют собой множества A, B и С. Прямоугольная область определяет множество U, и она разбита на восемь областей, которые помечены цифрами от 0 до 7. Можно видеть, что область разбиения 7 определяет множество A ∩ B ∩ C, область 6 – множество A ∩ B ∩ CС и т. д. Чтобы по диаграмме Венна проверить ассоциативность пересечения, можно использовать следующую идею. Заменим множества A, B и С и их пересечения на соответствующие им множества из областей разбиения на этой диаграмме. Множество А заменяется на <4, 5, 6, 7>, В – на <2, 3, 6, 7>и С – на <1, 3, 5, 7>, A ∩ B – на <6, 7>, B ∩ C – на <3, 7>.

Несмотря на то, что множества А, В и С могут быть какими угодно, доказать любое тождество для этих множеств можно, сведя доказательство к проверке этого тождества на уменьшенных множествах разбиения.

Нетрудно увидеть, что и левое, и правое множества этого тождества состоят из одного-единственного элемента 7, что и доказывает ассоциативность пересечения множеств.

Докажем то же самое используя табличный метод. Для этого построим таблицу, столбцы которой соответствуют различным множествам тождества, а каждая строка соответствует одному из множеств разбиения (строк 8, поскольку разбиение состоит из 8 множеств в соответствии с рис. 1.9). Строки содержат ответы на вопрос, входит ли соответствующее данной строке множество разбиения во множество доказываемого тождества или нет. Три первые столбца таблицы дают ответы, входит ли соответствующее множество разбиения во множество А, во множество В и во множество С. Столбец «Левая часть» соответствует левой части доказываемого тождества (A ∩ B) ∩ C, столбец «Правая часть» – правой части A ∩ (B ∩ C).

Поскольку ответы для всех строк «Левой части» те же самые, что и для «Правой части», тождество является доказанным. Табличный метод особенно удобен при построении доказательств с использованием компьютера.

Алгебраический метод основывается на идее разбиения доказательства на шаги, при этом переход от одного шага к следующему осуществляется за счет применения какого-либо закона алгебры множеств (например, закона ассоциативности, дистрибутивности, поглощения и т. д.). Доказательство требует хорошего знания базисных законов алгебры множеств, а также определенный опыт их применения. Рассмотрим метод на следующем примере. Пусть требуется доказать, что

При переходе от одного шага к другому будем указывать (в правой части соответствующей строки) причины, позволяющие делать такие переходы:

В этом примере левое выражение преобразовано в правое. Это преобразование облегчается тем обстоятельством, что известно, какое выражение должно быть получено. В то же время можно и правое выражение привести к левому. Чтобы понять, как это сделать, достаточно просмотреть первое преобразование от конца к началу. Какой путь легче, не всегда бывает сразу ясно, поэтому иногда необходимо попробовать оба способа, чтобы добиться правильного результата.

1.10. Математическая индукция

Имеется следующее существенное свойство множества натуральных чисел:

N = <1, 2, 3, …>, которое используется при построении различных доказательств.

Принцип математической индукции

Пусть Р – некоторое утверждение, определенное на положительных целых N, т. е. утверждение Р(n) либо истинно, либо ложно для каждого n из N. Если для Р выполняются два следующих свойства:

2) P(n+1) истинно, если истинно P(n), тогда Р истинно для каждого положительного целого.

Обычно этот принцип используется как аксиома для доказательства других результатов. Используем его для доказательства следующего результата.

Путь Р будет утверждением, что сумма первых n натуральных чисел, возведенных в куб, равна

Легко видеть, что P(n) истинно при n = 1, т. е. P(1): 13 =

Допустим теперь, что P(n) истинно и докажем, что P(n+1) также будет истинно. Для этого прибавим к обеим частям выражения для P(n) следующее слагаемое (n+1)3:

Преобразуем далее правую часть

Таким образом, P(n+1) истинно, когда истинно P(n). Теперь по принципу математической индукции утверждение Р истинно для всех n. Иногда принцип математической индукции записывают в более удобном для использования виде

Очень часто в задачах по дискретной математике, а именно в теории множеств, требуется доказать равенство множеств. Напомним, что равенство множеств $M=N$ означает выполнение взаимного включения, то есть $Msubseteq N$ и $Nsubseteq M$. Следовательно, для доказательства равенства $M=N$ множеств $M, N$ нужно показать выполнение этих включений. Делать это можно различными способами:

1. по определению теоретико-множественных операций;
2. с помощью законов алгебры множеств;
3. построением диаграмм Эйлера-Венна;
4. построением таблиц принадлежности;
5. используя индикаторные функции.

Продемонстрируем каждый из этих способов на конкретном примере.

Доказать равенство множеств:

$$left(Acap B
ight)ackslash C=left(Aackslash C
ight)cap left(Backslash C
ight)$$

1. Равенство двух множеств $M=N$ эквивалентно двум включениям $Msubseteq N, Nsubseteq M$.

Докажем, что $left(Acap B
ight)ackslash Csubseteq left(Aackslash C
ight)cap left(Backslash C
ight)$. Пусть $xin left(Acap B
ight)ackslash C$, тогда по определению разности множеств $xin left(Acap B
ight)$ и $x
otin C$. По определению пересечения множеств $xin left(Acap B
ight)$ тогда и только тогда, когда $xin A$ и $xin B$. Так как $xin A$ и $x
otin C$, то $xin Aackslash C$. Так как $xin B$ и $x
otin C$, то $xin Backslash C$. По определению пересечения получаем, что $xin left(Aackslash C
ight)cap left(Backslash C
ight)$. Что доказывает то, что $left(Acap B
ight)ackslash Csubseteq left(Aackslash C
ight)cap left(Backslash C
ight)$.

Докажем, что $left(Aackslash C
ight)cap left(Backslash C
ight)subseteq left(Acap B
ight)ackslash C$. Пусть $xin left(Aackslash C
ight)cap left(Backslash C
ight)$, тогда по определению пересечения множеств $xin left(Aackslash C
ight)$ и $xin left(Backslash C
ight)$. По определению разности множеств $xin A$, $x
otin C$ и $xin B, x
otin C$. По определению пересечения получаем, что $xin left(Acap B
ight) и x
otin C$, то есть $xin left(Acap B
ight)ackslash C$. Что доказывает то, что $left(Aackslash C
ight)cap left(Backslash C
ight)subseteq left(Acap B
ight)ackslash C$. Из доказанных включений следует, что $Aleft(Acap B
ight)ackslash C=left(Aackslash C
ight)cap left(Backslash C
ight)$.

2. Докажем справедливость соотношения $left(Acap B
ight)ackslash C=left(Aackslash C
ight)cap left(Backslash C
ight)$, используя основные законы алгебры множеств.

Операцию разность $Xackslash Y$ произвольных множеств $X, Y$ можно записать, как $Xackslash Y=Xcap overline$. Тогда для левой части данного соотношения $left(Acap B
ight)ackslash C=Acap Bcap overline$. Для правой части: $left(Aackslash C
ight)cap left(Backslash C
ight)=Acap overlinecap Bcap overline=Acap Bcap overline$. Видим, что левая и правая части в результате преобразований совпали $Acap Bcap overline=Acap Bcap overline$. Соотношение верно.

3. Видим, что диаграммы множеств $left(Acap B
ight)ackslash C$ и $left(Aackslash C
ight)cap left(Backslash C
ight)$ полностью совпадают, значит, равенство $left(Acap B
ight)ackslash C=left(Aackslash C
ight)cap left(Backslash C
ight)$ верно.

4. Построим таблицу принадлежности для левой и правой частей данного равенства $left(Acap B
ight)ackslash C=left(Aackslash C
ight)cap left(Backslash C
ight)$.

egin <|c|c|>hline A & B & C & Acap B & left(Acap B
ight)ackslash C & Aackslash C & Backslash C & left(Aackslash C
ight)cap left(Backslash C
ight) \ hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \ hline 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \ hline 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \ hline 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \ hline 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \ hline 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \ hline 1 & 1 & 0 & 1 & 1 & 1 & 1 & 1 \ hline 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \ hline end

Видим, что $left(Acap B
ight)ackslash C=left(Aackslash C
ight)cap left(Backslash C
ight)=left(00000010
ight)$.

5. Докажем справедливость соотношения $left(Acap B
ight)ackslash C=left(Aackslash C
ight)cap left(Backslash C
ight)$ с помощью индикаторных функций. Индикаторная функция для левой части соотношения:

$$ <chi >_<left(Acap B
ight)ackslash C>left(x
ight)=<chi >_left(x
ight)-<chi >_left(x
ight)<chi >_Cleft(x
ight)=<chi >_Aleft(x
ight)<chi >_Bleft(x
ight)-<chi >_Aleft(x
ight)<chi >_Bleft(x
ight)<chi >_Cleft(x
ight)=<chi >_Aleft(x
ight)<chi >_Bleft(x
ight)cdot left(1-<chi >_Cleft(x
ight)
ight)$$ Индикаторная функция для правой части: $$<chi >_<left(Aackslash C
ight)cap left(Backslash C
ight)>left(x
ight)=<chi >_<left(Aackslash C
ight)>left(x
ight)<chi >_<left(Backslash C
ight)>left(x
ight)=left(<chi >_Aleft(x
ight)-<chi >_Aleft(x
ight)<chi >_Cleft(x
ight)
ight)left(<chi >_Bleft(x
ight)-<chi >_Bleft(x
ight)<chi >_Cleft(x
ight)
ight)=<chi >_Aleft(x
ight)<chi >_Bleft(x
ight)-<chi >_Aleft(x
ight)<chi >_Bleft(x
ight)<chi >_Cleft(x
ight)-<chi >_Aleft(x
ight)<chi >_Bleft(x
ight)<chi >_Cleft(x
ight)+<chi >_Aleft(x
ight)<chi >_Bleft(x
ight)<chi >_Cleft(x
ight)=<chi >_Aleft(x
ight)<chi >_Bleft(x
ight)-<chi >_Aleft(x
ight)<chi >_Bleft(x
ight)<chi >_Cleft(x
ight)=<chi >_Aleft(x
ight)<chi >_Bleft(x
ight)left(1-<chi >_Cleft(x
ight)
ight). $$ Видим, что индикаторные функции обеих частей совпали $$<chi >_Aleft(x
ight)<chi >_Bleft(x
ight)cdot left(1-<chi >_Cleft(x
ight)
ight)=<chi >_Aleft(x
ight)<chi >_Bleft(x
ight)cdot left(1-<chi >_Cleft(x
ight)
ight).$$ Соотношение верно.