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

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

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

---

(a) A = (A ∩ BC) ∪ (A ∩ B),

(b) B = (B ∩ U) ∪ (A ∩ B),

(c) АС ∩ (AС ∪ U)С = Ø,

(d) (AC ∪ BC) ∪ (A ∩ B) = U,

(e) A ∩ BC ∩ C = (A ∩ C) ∩ (AC ∪ BC ∪ CC).

Заменим все ∩, ∪,Ø и U в каждом равенстве и получим двойственные равенства:

(a) A = (A ∪ BC) ∩ (A ∪ B),

(b) B = (B ∪ Ø) ∩ (A ∪ B),

(c) АС ∪ (AС ∩ U)С = U,

(d) (AC ∩ BC) ∩ (A ∪ B) = Ø,

(e) A ∪ BC ∪ C = (A ∪ C) ∪ (AC ∩ BC ∩ CC).

1.17. Пусть имеются множества А, В, С и пусть универсальное множество U = A ∪ B ∪ C. Доказать следующие равенства:

(a) A ∩ B ∩ CС = (A ∩ В)\(A ∩ B ∩ C),

(b) A ∩ BC ∩ C = (A ∩ C)\(A ∩ B ∩ C),

(c) AC ∩ B ∩ C = (B ∩ C)\(A ∩ B ∩ C),

(d) AC ∩ BC ∩ CС= Ø,

(e) AС ∩ BС ∩ C = AС ∩ ВС,

(f) AC ∩ B ∩ CС= AС ∩ СС,

(g) A ∩ BC ∩ CС= BС ∩ СС,

(h) A ∩ B ∩ C = (A ∩ В)\(А ∩ В ∩ СС).

(a) Преобразуем правую часть равенства

(A ∩ В)\(A ∩ B ∩ C) = (A ∩ В) ∩ (AC ∪ BC ∪ CC) = тождество упражнения 1.13.

= (A ∩ В) ∩ (AC ∪ BC ∪ CC) =

= (A ∩ B ∩ АC) ∪ (A ∩ B ∩ ВС) ∪ (A ∩ B ∩ CC) = дистрибутивность

= Ø ∪ Ø ∪ (A ∩ B ∩ CC) = по закону дополнения

= A ∩ B ∩ CC по закону тождества.

(b) (A ∩ C)\(A ∩ B ∩ C) = (A ∩ C) ∩ (AC ∪ BC ∪ CC) =

= (A ∩ C ∩ АC) ∪ (A ∩ C ∩ ВС) ∪ (A ∩ C ∩ CC) =

= Ø ∪ (A ∩ C ∩ BC) ∪ Ø = A ∩ B ∩ CC.

(c) (B ∩ C)\(A ∩ B ∩ C) = (B ∩ C) ∩ (AC ∪ BC ∪ CC) =

= (B ∩ C ∩ АC) ∪ (B ∩ C ∩ ВС) ∪ (B ∩ C ∩ CC) =

= (B ∩ C ∩ АC) ∪ Ø ∪ Ø = AC ∩ B ∩ C.

(d) AC ∩ BC ∩ CС = (A ∪ B ∪ C)C = по закону де Моргана

= (U)C = Ø. замена и дополнение

(e) AС ∩ ВС = (AС ∩ ВС) ∩ (С ∪ CC) = поскольку (С ∪ CC) = U

= (AС ∩ ВС ∩ С) ∪ (AС ∩ ВС ∩ СC) = (AС ∩ ВС ∩ С) ∪ Ø = = (AС ∩ ВС ∩ С).

(f) AС ∩ СС = (AС ∩ CС) ∩ (B ∪ BC) = поскольку (B ∪ BC) = U

= (AС ∩ В ∩ СC) ∪ (AС ∩ ВС ∩ СC) = (AС ∩ В ∩ СC) ∪ Ø = = (AС ∩ В ∩ СC).

(g) BС ∩ СС = (BС ∩ CС) ∩ (A ∪ AC) = поскольку (A ∪ AC) = U

= (A ∩ ВC ∩ СC) ∪ (AСВС ∩ СC) = (A ∩ ВC ∩ СC) ∪ Ø = = (A ∩ ВC ∩ СC).

(h) (A ∩ В)\(А ∩ В ∩ СС) = (A ∩ В) ∩ (А ∩ В ∩ СС)С = тождество упражнения 1.13.

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

= Ø ∪ Ø ∪ (A ∩ B ∩ CC) = по закону тождества

= A ∩ B ∩ C.

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

Для доказательства используем стандартный математический подход, применяемый при доказательстве единственности. Предположим, что существует два различных дополнения для А и обозначим их как А1c и А2c. Тогда каждое из них должно удовлетворять условиям дополнения

А1c ∩ А = А2c ∩ А = Ø и А1c ∪ А = А2c ∪ А = U.

Поэтому

А1c = А1c ∩ U = А1c ∩ (А2c ∪ А) = по закону дистрибутивности

= (А1c ∩ А2c) ∪ (А1c ∩ А) = по закону дополнения

= (А1c ∩ А2c) ∪ Ø = по закону тождества

= А1c ∩ А2c.

Отсюда следует, что каждый х ∈ А1c является также и элементом

А1c ∩ А2c и из этого следует, что А1c является подмножеством А1c ∩ А2c, т. е. А1c ⊆ А1c ∩ А2c, но поскольку А1c ⊆ А2c по определению, то тогда А1c ⊆ А2c.

Пусть теперь

А2c = А2c ∩ U = А2c ∩ (А1c∪ А) =

Выполнив преобразования, как и в первом случае, получим

= А1c ∩ А2c, т. е. А2c ⊆ А1c, но из этого следует, что

А1c = А2c = АС.

Итак, мы предположили, что существует два дополнения, а затем показали, что они совпадают, и это доказывает единственность дополнения множества А.

1.19. Известно, что для чисел операция равенства является транзитивной, т. е. если a = b и b = c, то из этого следует, что a = c. Свойство транзитивности во многих случаях оказывается очень полезным. Например, если необходимо знать, равны ли все три числа a, b и c, то достаточно проверить равенство только двух любых пар, допустим a = b и b = c, третье равенство a = c можно не проверять – оно будет выполнено в силу транзитивности. Однако если рассматривать операцию ≠, то транзитивность не выполняется. Например, a = 2, b = 3, c = 2 и тогда a ≠ b, b ≠ c, но a = c. Для множеств также операция включения множеств А ⊆ В транзитивна, но операция ⊄ не является транзитивной. Доказать, что если А ⊄ В и В ⊄ С, то из этого не следует А ⊄ С.

Для доказательства достаточно рассмотреть следующий случай. Пусть А и В непустые непересекающиеся множества, и пусть А = С. Тогда А ⊄ В и В ⊄ С, но А ⊆ С.

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