Александр Казанский - Дискретная математика. Краткий курс. Учебное пособие

если A ∪ B = B ∪ C , то А = В .

Если С непустое множество, С = А и множество В = Ø , тогда А ∪ Ø = Ø ∪ С и А ≠ В .

1.21. Пусть А, В и С непустые попарно пересекающиеся подмножества U . Доказать ложность следующих утверждений:

(a) если А ⊆ ( В ∩ С ), то неверно, что А ∩ В ⊆ В ∩ С и А ∩ С ⊆ В ∩ С ;

(b) если А ∩ В ⊆ В ∩ С и А ∩ С ⊆ В ∩ С , то тогда А ⊆ ( В ∩ С );

(c) если А ⊆ ( В ∩ С ), то А ∩ В ≠ А ∩ С .

(a) Если А ⊆ ( В ∩ С ), то по определению пересечения А ⊆ В, А ⊆ С , но из этого следует, что А ∩ В = А и А ∩ С = А , т. е. А ∩ В = А ∩ С = А , и, значит, верно, что А ∩ В ⊆ В ∩ С и А ∩ С ⊆ В ∩ С . Поэтому исходное утверждение ложно.

(b) Для доказательства рассмотрим следующие множества. Пусть А = {1, 2, 3}, B = {3, 4, 5, 6}, C = {3, 4, 5}. Найдем

А ∩ В = {3}, В ∩ С = (3, 4, 5}, А ∩ С ={3}. Здесь оба пересечения и А ∩ В и А ∩ С включаются в В ∩ С , но множество А не включается в В ∩ С . Поэтому исходное утверждение ложно.

(c) Если А содержится в В ∩ С , то по определению операции пересечения оно сдержится и в В , и в С . Но если А содержится в В , то пересечением А ∩ В будет множество А . Поскольку А содержится в С , то пересечением А ∩ С также будет множество А . Значит, оба множества и А ∩ В и А ∩ С состоят из одних и тех же элементов и поэтому они равны, т. е. А ∩ В = А ∩ С .

1.22. Доказать, что операция разности множеств не ассоциативна, т. е.

( А\В )\ С ≠ А\ ( В\С ).

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

( А\В )\ С = ( А ∩ В С)\ С = ( А ∩ В С) ∩ С С = А ∩ В С ∩ С С.

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

А\ ( В\С ) = А\ ( В ∩ С С) = А ∩ ( В ∩ С С)С = А ∩ ( В С ∪ С ) = = ( А ∩ В С) ∪ ( А ∩ С ) = ( А ∩ В С) ∩ ( С ∪ С С) ∪ ( А ∩ С ) ∩ ( В ∪ В С) =

= ( А ∩ В С ∩ С ) ∪ ( А ∩ В С ∩ С С) ∪ ( А ∩ В ∩ С ) ∪ ( А ∩ В С ∩ С )

= ( А ∩ В С ∩ С ) ∪ ( А ∩ В С ∩ С С) ∪ ( А ∩ В ∩ С ).

Множество левой части не совпадает с множеством правой части, и это доказывает, что операция разности множеств не ассоциативна.

1.23. Доказать, используя элементный метод, что если А, В и С подмножества универсального множества U и если А ⊆ В , то В С ⊆ А С.

Пусть А, В и С подмножество универсального множества U . Рассмотрим любой элемент х ∈ В С. По определению дополнения В С ∩ В = Ø , поэтому если х является элементом В С, то он не может быть элементом В , т. е. х ∉ В . Элемент х также не может принадлежать и множеству А , поскольку А ⊆ В , т. е. х ∉ А , но тогда х ∈ А С. Таким образом, показано, что для любого элемента х из множества В С этот элемент принадлежит и множеству А С, т. е. В С ⊆ А С.

1.24. Доказать, используя элементный метод, что если А ⊆ В , то

(a) А ∩ С ⊆ В ∩ С ,

(b) А ∪ С ⊆ В ∪ С .

(a) Пусть х ∈ А ∩ С . Тогда х ∈ А и х ∈ С и поскольку А ⊆ В , то х ∈ В . Из того, что х принадлежит и В и С , следует, что он принадлежит их пересечению х ∈ В ∩ С . Это означает, что для любого х, входящего в множество А ∩ С , элемент х входит и в множество В ∩ С , т. е. А ∩ С ⊆ В ∩ С .

(b) Поскольку А ⊆ В , то В С ⊆ А С (задача 1.23). Тогда для любого множества С С его пересечение с В С будет включаться в его пересечением с А С (потому что нет ни одного элемента В С, входящего в пересечение В С ∩ С С и не являющегося элементам А С, но В С ∩ С С могут быть элементы из А С, не являющиеся элементами В С), т. е. В С ∩ С С ⊆ А С ∩ С С. Затем, снова применяя результат задачи 1.23, получим, что ( А С ∩ С С)С ⊆ ( В С ∩ С С)С. По закону де Моргана получим А ∪ С ⊆ В ∪ С , что и доказывает искомый результат.

1.25. Дано множество А = {1,2, 3, 4, 5, 6, 7, 8,9}. Какие из приведенных ниже семейств множеств являются разбиениями:

(a) {{1, 2, 3}, {2, 4, 5}, {6, 9}, {7, 8}},

(b) {{1, 3, 5}, { 7, 6}, {2, 4, 8, 9}},

(c) {{1, 2}, {3, 5, 6, 7}, {4, 8, 9}, {1, 2}},

(d) {{1, 2}, {3, 4, 5}, {7, 8}, {9}}.

(a) Не разбиение, потому что элемент 2 входит в {1, 2, 3} и {2, 4, 5}.

(b) Разбиение, потому что каждый элемент А принадлежит точно одному блоку.

(c) Разбиение, потому что можно игнорировать факт, что {1, 2} встречается дважды.

(d) Не разбиение, потому что нет элемента 6.

1.26. Пусть А и В непересекающиеся множества. Обозначим через Sa разбиение множества А , а через Sb – разбиение множества В . Доказать, что Sa ∪ Sb является разбиением множества А ∪ В .

Текст предоставлен ООО «ЛитРес».

Прочитайте эту книгу целиком, на ЛитРес.

Безопасно оплатить книгу можно банковской картой Visa, MasterCard, Maestro, со счета мобильного телефона, с платежного терминала, в салоне МТС или Связной, через PayPal, WebMoney, Яндекс.Деньги, QIWI Кошелек, бонусными картами или другим удобным Вам способом.