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

Чтение книги онлайн.

      Рис. 1.8

      Фундаментальные произведения также представляют собой разбиение универсального множества.

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

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

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

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

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

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

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

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

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

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

      A = (A ∪ BC ∪ CC) ∩ (A ∪ (B ∩ СКАЧАТЬ