Дискретная математика. Краткий курс. Учебное пособие. Александр Анатольевич Казанский
Читать онлайн книгу.
первое тождество A ∩ B = B ∩ A имеет парное A ∪ B = B ∪ A, и это выполняется для всех остальных законов алгебры множеств.
Принцип двойственности состоит в том, что если верно какое-либо тождество, то тождество, полученное из него путем замены каждой из операций ∩, ∪, а также U и Ø на операции ∪, ∩, Ø и U, соответственно, будет также верно. Поэтому у любого тождества есть его «двойник», отличающийся тем, что у него каждая операция замена на парную ей (объединение на пересечение, а пересечение на объединение) и при этом пустое множество заменяется на универсальное, а универсальное на пустое. Принцип двойственности очень важен, поскольку если доказана истинность какого-либо выражения, то истинность двойственного ему можно не доказывать – оно будет истинно вследствие данного принципа. Например, для верного тождества
A = (A ∩ BC ∩ CC) ∪ (A ∩ (B ∪ C))
двойственное ему будет также верным тождеством
A = (A ∪ BC ∪ CC) ∩ (A ∪ (B ∩ C)).
Или для верного тождества
A = (A ∩ U) ∪ (A ∩ B ∩ C),
двойственное ему тождество A = (A ∪ Ø) ∩ (A ∪ B ∪ C).
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 принадлежит объединению