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

• Название: Дискретная математика. Краткий курс. Учебное пособие
• Автор: Александр Казанский
• Жанр: Математика

В пособии изложены основные разделы современной дискретной математики. Рассматриваются вопросы, связанные с теорией множеств, теорией отношений, теорией графов и логикой. Материал построен на основе курса лекций, читаемого автором в технических вузах. В каждой главе рассмотрено большое число задач с подробными решениями и примерами, что позволяет эффективно и быстро осваивать изучаемую тему. Для студентов, обучающихся по специальности «Прикладная математика», а также для студентов технических и экономических факультетов, изучающих курс «Дискретная математика» и компьютерные технологии. Представляет интерес для тех, кто связан с использованием методов дискретной математики.

---

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

если 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 Кошелек, бонусными картами или другим удобным Вам способом.