Что такое семейство множеств в дискретной математике

Основы дискретной математики

Привет, хабр. В преддверии старта базового курса «Математика для Data Science» делимся с вами переводом еще одного полезного материала.

Об этой статье

Эта статья содержит лишь малую часть информации по заявленной теме. Рассматривайте ее как вводный курс перед началом всестороннего изучения предмета. Надеюсь, вы найдете в ней полезную информацию. Знание дискретной математики помогает описывать объекты и задачи в информатике, особенно когда дело касается алгоритмов, языков программирования, баз данных и криптографии. В дальнейшем я планирую подробнее раскрыть темы, затронутые в этой статье. Приятного чтения!

ЧТО ТАКОЕ ДИСКРЕТНАЯ МАТЕМАТИКА?

Это область математики, изучающая объекты, которые могут принимать только уникальные отдельные значения.

Мы рассмотрим пять основных разделов в следующем порядке.

ЛОГИКА

Что такое логика?

Это наука о корректных рассуждениях. Мы будем использовать приемы идеализации и формализации. Неформальная логика изучает использование аргументов в естественном языке.

Формальная логика анализирует выводы с чисто формальным содержанием. Примерами формальной логики являются символическая логика и силлогистическая логика (о которой писал Аристотель).

Начнем с азов. Рассмотрим следующее высказывание на естественном языке:

«Если я голоден, я ем».

Пусть «голоден» будет посылкой A, а «ем» — следствием B. Попробуем формализовать:

A => B (то есть из A следует B)

NB. Посылка и следствие являются суждениями.

Логические выражения

Для нас важна форма, а НЕ содержание. Значение будет истинным, если оно соответствует форме.

Например, 10 4 — ИСТИНА.

Логические операции

Суждение P — это утверждение, которое может быть как истинным, так и ложным.

Обозначим истинное значение P единицей (1), а ложное значение P нулем (0).

Существует другое суждение; обозначим истинное значение Q единицей (1), а ложное значение Q нулем (0).

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

Источник

Введение в теорию множеств

Концепция бесконечности идеологически далека от обычной математической терминологии — ни одна другая тема не выходит за пределы математики так, что превращается из практического, аналитического инструмента в явление мифического порядка. Понятие бесконечности на короткой ноге с такими культурными темами, как религия и философия, и окутана загадочной аурой божественности.

Когда-то давным давно во всех академических дисциплинах было заложено фундаментальное убеждение — существует единственная бесконечность.

Но 1874 году довольно малоизвестный математик провёл серию революционных наблюдений, подвергавших сомнению это всеми принятое и глубоко укоренившееся убеждение. Георг Кантор в своей (теперь уже ставшей легендарной) публикации On a Property of the Collection of All Real Algebraic Numbers доказал, что множество вещественных чисел «более многочисленно», чем множество алгебраических чисел. Так он впервые показал, что существуют бесконечные множества разных размеров (не волнуйтесь — для прояснения этого мы вскоре подробно изучим его статью).

«Множество — это большое количество, которое позволяет воспринимать себя как одно» — Георг Кантор

С 1874 по 1897 год Кантор неистово публиковал статью за статьёй, разворачивая свою теорию абстрактных множеств в расцветающую дисциплину. Однако она была встречена упорным сопротивлением и критикой; многие педанты считали, что его теории перешли в область философии и нарушили принцип религии.

Однако когда начали находиться практические применения математического анализа, отношение к теории изменилось, а идеи и результаты Кантора начали получать признание. К первому десятилению 20-го века его наблюдения, теории и публикации достигли своей кульминации — признания современной теории множеств новой, совершенно уникальной областью математики:

Теория множеств — это математическая теория о точно определённых наборах (множествах) отдельных объектов, называемых членами или элементами множества.

Сколько чисел есть между 0 и 1?

Первая публикация Кантора, состоящая из четырёх с половиной страниц, является великолепным примером краткости. Она разделена на два отдельных доказательства, совместно приводящих к выводу о существовании по крайней мере двух уникальных видов множеств.

В первой части теории исследуется множество вещественных алгебраических чисел и доказывается, что это бесконечное счётное множество. Здесь не стоит путать — «счётное» не обязательно значит, что счёт ведётся строго в целых числах; в контексте теории множеств «счётное» означает, что множество, пусть даже состоящее из бесконечного числа элементов, можно описать повторяющимся рядом, например упорядоченной многочленной функцией. Кантор назвал это свойство бесконечного набора чисел соответствия «один к одному» с рядом, наличием взаимно однозначного соответствия.

Если говорить вкратце, то набор, или множество всех вещественных алгебраических чисел можно вывести с помощью какого-то теоретического ряда многочленов с различными степенями и коэффициентами; следовательно, множество всех вещественных алгебраических чисел является бесконечным счётным множеством.

Во второй части труда Кантора анализируется роль вещественных комплексных чисел, также называющихся трансцендентными числами. Транцендентные числа (лучшие примеры которых — это пи и e) имеют любопытное свойство: математически невозможно вывести их с помощью многочленной функции — они не являются алгебраическими. Вне зависимости от величин, количества частей, степеней или коэффициентов, никакой ряд никогда не может посчитать пи в своём наборе бесконечного счётного множества.

Затем Кантор указывает, что в любом замкнутом интервале [a,b] существует хотя бы одно транцендентное число, которое никогда нельзя будет подсчитать в бесконечном счётном множестве. Поскольку одно такое число существует, то предполагается, что в семействе вещественных чисел существует бесконечное количество транцендентных чисел.

Таким образом он доказал очень чёткое различие между множеством непрерывных, идущих потоком несчётных чисел и набора счётных чисел, которые можно представить как ряд, например, всех вещественных алгебраических чисел.

Далее: запись и операции

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

Стоит также поделиться интересным наблюдением: большинство людей, использующих теорию множеств на практике, ценят скорее не эту конкретную теорему, а заданный ею обобщённый язык. Благодаря своей абстрактной природе теория множеств скрытно влияет на множество областей математики. В математическом анализе, который требует дифференциального и интегрального исчисления, необходимо понимание пределов и непрерывности функций, окончательно закреплённых в теории множеств. В алгебре логики логические операции «и», «или» и «не» соответствуют операциям пересечения, объединения и разности в теории множеств. И последнее, но не менее важное — теория множеств закладывает основы топологии — исследования геометрических свойств и пространственных отношений.

Вооружившись базовым пониманием истории множеств и совершив кратковременное погружение в глубины его влияния, мы можем приступать к знакомству с основами системы обозначений теории множеств.

Часть вторая. Краткий обзор операций, обозначений и диаграмм Венна.

Как сказано в предыдущей части, одно из фундаментальных преимуществ теории множеств произрастает не из какой-то конкретной теории, а из созданного ею языка. Именно поэтому основная часть этого раздела будет посвящена обозначениям, операциям и визуальному представлению теории множеств. Давайте начнём с объяснения базовых символов обозначения множества — соответствующих ему элементов. В таблице ниже показан пример одного множества A с тремя элементами:

A — это множество с элементами «1», «2» и «3»

«1» — элемент множества A

В первой строке показано множество A с тремя отдельными элементами (A = ); во второй строке показан правильный способ обозначения отдельного конкретного элемента 1, принадлежащего множеству A. Пока всё довольно просто, но теория множеств становится существенно интереснее, когда мы добавляем второе множество — начинается путешествие по стандартным операциям.

Операции: пересечение (intersection) — множество элементов, принадлежащих множеству A и множеству B;

объединение (union) — множество элементов, принадлежащих множеству A или множеству B;

подмножество (subset) — C является подмножеством A, множество C включено во множество A;

собственное (истинное) подмножество — C является подмножеством A, но C не равно A;

относительное дополнение (relative complement) — множество элементов, принадлежащих к A и не к B.

Вот и они, самые распространённые операции в теории множеств; они довольно популярны и в областях за пределами чистой математики. На самом деле, высока вероятность того, что вы уже видели подобные типы операций в прошлом, хоть и не совсем с такой терминологией, и даже пользовались ими. Хорошая иллюстрация: попросите любого студента описать диаграмму Венна из двух пересекающихся групп, и он интуитивно придёт к правильному результату.

Ещё раз взгляните на последнюю строку, относительное дополнение — какое необычное сочетание слов, правда? Относительное к чему? Если относительное дополнение A — B определяется как A и не B, то как нам обозначить всё, что не является B?

Универсальное множество — пустое множество

Оказывается, если мы хотим получить значимый ответ, то для начала нужно предоставить генеральной совокупности нашей задачи множеств некий контекст. Он часто явным образом задаётся в начале задачи, когда допустимые элементы множества ограничиваются некоторым фиксированным классом объектов, в котором существует универсальное множество, являющееся общим множеством, содержащим все элементы для этой конкретной задачи. Например, если мы хотели бы работать со множествами только из букв английского алфавита, то наше универсальное множество U состояло бы из 26 букв алфавита.

Для любого подмножества A множества U дополнение множества A (обозначаемое A′ или U − A) определяется как множество всех элементов в генеральной совокупности U, которое не находится в A. Если вернуться к поставленному выше вопросу, то дополнением множества B является всё в пределах универсального множества, что не принадлежит B, в том числе и A.

Прежде чем мы двинемся дальше, надо упомянуть ещё одно принципиальное множество, которое достаточно важно для базового понимания: нулевое или пустое множество. Учтите, что существует единственное пустое множество, поэтому никогда не говорят «пустые множества». Хотя мы не будем рассматривать в этой статье эквивалентность, основная теория гласит, что два множества эквивалентны, если они имеют одинаковые элементы; следовательно, может быть только одно множество без элементов. Поэтому существует единственное пустое множество.

Диаграммы Венна и остальное

Диаграммы Венна, официально изобретённые в 1880 году Джоном Венном, являются именно тем, что вы и представляете, хотя их научное определение звучит примерно так:

Схематичное изображение всех возможных отношений нескольких множеств

Ниже показано изображение шести самых распространённых диаграмм Венна, и почти во всех показаны недавно изученные нами операнды:

Объединение (union), пересечение (intersection), относительное дополнение (relative complement), симметрическая разность (symmetric difference), собственное множество (proper subset), абсолютное дополнение (universal дополнение).

Начав с очень простых обозначений множества и его элементов, мы узнали затем о базовых операциях, позволивших нарисовать эту визуальную подсказку. Мы рассмотрели все операции, за исключением симметрической разности (внизу слева). Чтобы не оставлять пробелов в знаниях, скажем, что симметрическая разность, также называемая дизъюнктивным объединением — это просто множество элементов, которые находятся в любом из множеств, но не входят в их пересечение.

Закончим мы этот раздел введением понятия мощности (кардинального числа). Мощность множества, обозначаемая символом абсолютного значения — это просто количество уникальных элементов, содержащихся в определённом множестве. Для показанного выше примера мощность трёх множеств равна: |A| = 3, |B| =6, |C| = 2.

Прежде чем двигаться дальше, дам вам пищу для размышлений — какова связь между мощностью и количеством возможных подмножеств?

Часть 3. Мощность и показательные множества

В предыдущих двух частях мы разобрались с основами теории множеств. В третьей части мы укрепим своё понимание, сосредоточившись на самом важном свойстве любого множества: общем количестве содержащихся в нём уникальных элементов.

Количество уникальных элементов во множестве, также известное как мощность, предоставляет нам фундаментальную опорную точку для дальнейшего, более глубокого анализа этого множества. Во-первых, мощность — это первое из рассматриваемых нами уникальных свойств, позволяющее нам объективно сравнивать различные виды множеств, проверяя, существует ли биекция (это, с небольшими оговорками, просто более изысканный термин для function ) одного множества на другое. Ещё один способ применения мощности, а также тема этой части статьи — мощность позволяет оценить все возможные подмножества, существующие в данном множестве. Что достаточно буквально можно применять в повседневных задачах распределения решений, будь то планирование бюджета на поездку в продуктовый магазин или оптимизация портфеля акций.

Примеры мощности множеств

Например, в таблице выше показаны пять отдельных множеств с их указанной справа мощностью. Как мы уже говорили, символ мощности напоминает символ абсолютного значения — значение, заключённое между двумя вертикальными линиями. Все примеры понятны, за исключением, возможно, последней строки, которая подчёркивает тот факт, что на мощность влияют только уникальные элементы множества.

Помните подмножества из предыдущей части статьи? Оказывается, что мощность некоторого множества A и количество возможных подмножеств множества A имеют удивительную связь. Ниже показано, что количество подмножеств, которые можно составить из некоторого подмножества, увеличивается с порядком мощности на предсказуемую величину:

Количество возможных подмножеств в C= 2 |C|

Давайте подробно рассмотрим показанный ниже пример. Однако для начала поразмыслим над формулой. Представим мощность как общее количество «позиций», которое представляет множество. При создании некоторого подмножества для каждой возможной позиции принимается булево решение (да/нет). Это означает, что каждый уникальный элемент, добавляемый к множеству (то есть увеличивающий мощность на единицу) увеличивает количество возможных подмножеств на множитель два. Если вы программист или учёный, то можете уяснить эту логику немного глубже, если поймёте, что все подмножества множества можно вычислить с помощью таблицы двоичных чисел.

Показательное множество (булеан)

Прежде чем мы вычислим все подмножества для примера множества C, я хотел бы ввести последнее понятие — булеан.

Булеан обозначается заглавной буквой S, за которой в скобках указывается исходное множество S(С). Булеан — это множество всех подмножеств C, включая пустое множество и само множество C. В таблице ниже показан булеан S(С) со всеми перестановками возможных подмножеств для множества C, содержащихся в одном большом множестве.

Для удобства форматирования я убрал запятые между множествами***

Чем может быть полезен булеан? На самом деле, вы скорее всего много раз интуитивно использовали булеаны, даже об этом не догадываясь. Каждый раз, когда вы выбираете подмножество элементов из более крупного множества, вы выбираете элемент булеана. Например ребёнок внимательно изучающий кондитерский магазин с купюрой в 5 долларов — какой элемент булеана множества всех доступных сладостей он выберет? Или если взять более технический пример: вам, как разработчику ПО может потребоваться запросить всех возможных пользователей базы данных, также обладающих свойством X и Y — ещё один случай, в котором одно подмножество выбирается из всех возможных подмножеств.

Эквивалентность и биективная функция

Теперь мы понимаем, что такое мощность множества, почему оно важно, и его связь с булеаном. Поэтому вернёмся ненадолго к тому, что упоминали в самом начале: что конкретно определяет эквивалентность в теории множеств?

Очевидно, что два множества с одинаковой мощностью имеют некое общее свойство, но на этом сходства заканчиваются — что если в одном из множеств есть многократно повторяющийся элемент? Что если два множества имеют одинаковую мощность и количество элементов? Нельзя отрицать, что они в какой-то степени «эквивалентны», но даже в этом случае всё равно есть возможность различий, потому что каждое множество может иметь разные элементы, повторяющиеся одинаковое количество раз. Смысл здесь в том, что концепция эквивалентности в теории множеств немного чужда другим областям математики. Установление эквивалентности в этом мире требует знакомства с этой концепцией и нового языка. В последней части этой статьи мы введём понятие эквивалентности, а также таких базисных свойств, как инъективные, биективные и сюръективные функции.

Часть 4. Функции.

В этой части мы подробнее расскажем о функциях в пределах теории множеств. Как и в случае с предыдущими понятиями, терминология стандартных функций в теории множеств слегка отличается от других областей математики, а потому требует объяснения. Терминологии довольно много, так что давайте сразу приступим к делу! В первой таблице внизу отражены понятия области определения, области значений и значения функции:

Функция в мире теории множеств — это просто соответствие некоторых (или всех) элементов из Множества A некоторым (или всем) элементам Множества B. В показанном выше примере набор всех возможных элементов A называется областью определения; элементы A, используемые в качестве входных значений, в частности называются аргументами. Справа набор всех возможных выходных значений (называющихся в других областях математики «областью значений»), называется кообластью; набор настоящих выходных элементов B, соответствующих A, называется образом.

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

Инъекции, сюръекции и биекции

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

Прочитайте заново представленный выше список пунктов. Биекция — это просто функция, удовлетворяющая обоим предыдущим требованиям; то есть, функция инъективна и сюръективна. Инъективная функция не должна быть сюръективной, а сюръективная — инъективной. Ниже показан визуальный пример, в котором эти три классификации привели к созданию функций множеств, определяемых четырьмя возможными комбинациями инъективных и сюръективных свойств:

Биекция (инъекция + сюръекция), инъекция (инъекция + не-сюръекция), сюръекция (не-инъекция + сюръеция), без классификации (не-инъекция + не-сюръекция)

Вот и всё! Теперь мы обладаем элементарным пониманием самых часто встречаемых соотношений, встречающихся в мире множеств. Однако это ни в коем случае не конец нашего пути: напротив, это самое начало.

Фундаментальные основы теории множеств — ключ к пониманию более высокоуровневых областей математики. Чтобы продолжить наше движение вверх, к этим различным областям, далее нужно будет, пользуясь своими знаниями о теории множеств, уяснить одну из самых революционных теорий в истории математики: систему аксиом Цермело-Френкеля.

Источник

Элементы дискретной математики: конспект лекций (стр. 1 )

Из за большого объема этот материал размещен на нескольких страницах: 1 2 3 4 5 6 7 8 9

учебно-методической комиссией филиала ЮУрГУ в г. Златоусте

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

Предназначен для студентов технических университетов, обучающихся по направлению «Информатика и вычислительная техника».

ã Издательство ЮУрГУ, 2008

ВВЕДЕНИЕ

Дискретная математика или дискретный анализ – сравнительно новое направление в математике, объединяющее отдельные её разделы, ранее сформированные как самостоятельные теории. К ним относятся математическая логика и теории множеств, графов, кодирования, автоматов.

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

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

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

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

Методы, разрабатываемые дискретной математикой, используются в различных областях знаний. Так, теоретическая информатика (или теоретическая кибернетика) использует математические методы для построения и изучения моделей обработки, передачи и использования информации. Объекты её изучения – дискретные множества. Теоретическая информатика является как поставщиком задач, так и потребителем методов дискретной математики.

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

Теория информации изучает вид тех форм, в которых информация представляется в компьютере. Формализация любой информации, реально существующей в живой и неживой природе, происходит через компьютерное моделирование.

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

Теория массового обслуживания изучает широкий класс моделей передачи и переработки информации в системах массового обслуживания (СМО).

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

Теория принятия решений изучает общие схемы, используемые при выборе решения из альтернативных возможностей (в условиях неопределенности).

Теория игр изучает модели, в которых выбор происходит в условиях конфликта или противоборства.

Математическое программирование рассматривает проблемы принятия оптимальных решений с помощью математического аппарата.

Искусственный интеллект – одно из молодых и перспективных направлений информатики, появившееся во второй половине XX в. на базе вычислительной техники, математической логики, программирования, психологии, лингвистики и других отраслей знаний. Объектами его изучения являются межпредметные процедуры (метапроцедуры), используемые при решении задач, традиционно называемых интеллектуальными. Проникая в тайны творческой деятельности людей, искусственный интеллект создает программные и программно-аппаратные модели таких метапроцедур.

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

Для нас представляют интерес все эти направления современной информатики. Теперь мы сможем осознать место дискретной математики в системе знаний, необходимых для тех, кто связал свою жизнь с компьютером.

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

Глава 1. МНОЖЕСТВА И ОТНОШЕНИЯ

1.1. Множества

Понятие множества принадлежит к числу фундаментальных неопределяемых понятий. Можно сказать, что множество – это любая определенная совокупность объектов. Объекты, из которых составлено множество, называют элементами. Элементы множества отличают друг от друга. Например, множество всех книг в библиотеке или множество вершин многоугольника.

Множества обозначаются большими буквами. Например, A, B, C, X, N и т. д. Если объект a является элементом множества A, то говорят, что a принадлежит A. Это записывается, как . Запись будет означать, что a не является элементом A.

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

Множество, не содержащее элементов, называется пустым и обозначается .

1.2. Задание множеств

Чтобы задать множество, нужно указать, какие элементы ему принадлежат. Это можно сделать разными способами:

­ перечислением М элементов: ;

­ характеристическим предикатом: ;

­ порождающей процедурой: .

Перечисление задается в фигурных скобках, через запятую.

Здесь и далее фигурными скобками будем обозначать множество, в котором не играет роли порядок следования элементов, и круглыми скобками последовательность, в которой порядок следования элементов важен. Угловыми скобками будем обозначать совокупности элементов, имеющие неоднородную математическую природу (структуру), например, в графе имеем два вида элементов – вершины и дуги (пары) этих элементов ().

Характеристический предикат – это некоторое условие, выраженное в форме логического утверждения. Если для данного элемента условие выполнено, то оно принадлежит определённому множеству. В противном случае – не принадлежит.

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

Пример: .

.

1.3. Операции над множествами

Множества удобно изображать с помощью кругов Эйлера (диаграмм Венна). Элементы множества изображаются точками внутри круга, если они принадлежат множеству ( на рис 1.1 а), и точками вне круга, если они множеству не принадлежат ().

Рис. 1.1. Иллюстрация кругами Эйлера

Будем также использовать символы вместо слов «для любых х», «каждый элемент х» и вместо слов «существует х».

Множество A содержится во множестве B (множество B включает в себя множество A), если каждый элемент A принадлежит также и B (рис 1.1 б):

В этом случае A называется подмножеством B, а B – надмножеством A.

Если и , то A называется собственным подмножеством B.

Два множества равны, если они являются подмножествами друг друга, т. е..

Мощность множества обозначается как |М|. Для конечных множеств мощность – это число элементов. Например, , но .

Если А=В, то множества A и B называются равномощными.

Пример. Множество решений (корней) уравнения , т. е. . Множество простых чисел, меньших пяти . Следовательно, А=В.

Для некоторых числовых множеств приняты стандартные обозначения:

N – множество натуральных чисел ;

Z – множество целых чисел ;

Q – множество рациональных чисел ;

R – множество действительных чисел;

C – множество комплексных чисел.

Тогда и т. д.

Если в множестве A найдется хотя бы один элемент, не принадлежащий B, то A не является подмножеством B, т. е. .

Например, интервал не является подмножеством промежутка , так как , но .

Из определения следует, что любое множество является подмножеством самого себя, т. е. справедливо утверждение . Полагают, что Æ является подмножеством любого множества.

Пример. Рассмотрим множество, состоящее из трех элементов: . Найдем все его подмножества:

а) пустое ;

б) по одному

в) по два

г) по три .

Число всех подмножеств составляет 8=23. Если множество состоит из n элементов, то число всех подмножеств равно 2n. Или булеан |2М|=2|М|.

Множество, состоящее из всех элементов, принадлежащих и множеству A, и множеству B, называется пересечением и обозначается .

.

Пример: .

Если же множества A и B не имеют общих элементов, то их пересечением является пустое множество, то есть . Например, пересечение множества четных чисел с множеством нечетных.

Пересечение пустого множества с любым множеством – пустое множество: .

1. Коммутативность (переместительное свойство). По аналогии с а+b=b+a

.

2. Ассоциативность. По аналогии с

.

3. Свойство нуля. По аналогии с

.

4. Идемпотентность (аналогии нет)

.

5. Дистрибутивность. По аналогии с

;

6. Свойство единицы.

Если задан универсум U и любые , то можно записать: (рис. 1.2 а); (рис. 1.2 б).

Множество, состоящее из всех элементов, принадлежащих или множеству A, или множеству B, называется объединением множеств. Обозначается так: .

Пример. Даны множества и . Их объединением будет .

Даны числовые промежутки (рис. 1.3). Их объединением будет .

Объединение и пересечение множеств хорошо иллюстрируются на плоскости (рис. 1.4). При этом множества изображаются кругами или прямоугольниками.

Свойства объединения множеств можно сравнить со свойствами сложения чисел. Проведем аналогию этих свойств.

1. Коммутативность (переместительное свойство). По аналогии с

.

2. Ассоциативность. По аналогии с

.

3. Свойство нуля. По аналогии с

.

4. Идемпотентность (аналогии нет)

.

5. Дистрибутивность. По аналогии с

.

Рис. 1.3. Множества точек отрезков

Рис. 1.4. Операции над множествами

Записывается так: .

Геометрическое представление разности множеств на рис. 1.5.

Симметричная разность (рис. 1.6):

;

.

Рис. 1.5. Разность множеств Рис. 1.6. Симметричная разность

Дополнение множеств (рис. 1.7):

;

.

Свойства дополнения :

1) ; 4) ;

2) ; 5) ;

3) ; 6) .

Пример. Рассмотрим операцию дополнения множества, являющегося пересечением множеств A и B. Её результат совпадает с объединением дополнений этих множеств, (свойство 6) ; в этом можно убедиться с помощью диаграмм Эйлера – Венна (рис. 1.8).

Рис. 1.8. Геометрическая иллюстрация свойства 6

Декартово произведение множеств

Пусть A – конечное множество, состоящее из n элементов. Кортежем длины n элементов множества A называется упорядоченная последовательность (а1, а2, …, аn) элементов этого множества.

Из двух данных кортежей (а1, а2, …, ai, …, аk), где , длины k и (b1, b2, …, bj, …, bm), где , длины m можно составить новый кортеж длиной , элементы которого (а1, а2, …, аk, b1, b2, …, bm) принадлежат множеству . Эта операция называется соединением кортежей. Кортеж можно образовать двумя способами, поэтому важно, какой кортеж назван первым. Так, соединив кортежи четных и нечетных однозначных чисел и , получим кортеж всех однозначных чисел .

Пусть A – конечное множество, элементами которого являются некоторые символы, например цифры, буквы, знаки препинания. Такие множества принято называть алфавитом над заданным множеством символов. Алфавит есть кортеж попарно различимых символов, называемых буквами алфавита. Элементы множества An принято называть словами длины n в алфавите A. Слово над алфавитом есть просто некоторая конечная последовательность символов. Так, шестизначный телефонный номер является словом длины 6 над алфавитом цифр .

Рассмотрим множество B, состоящее из двух элементов: 0 и 1. Кортежи длины m из этих элементов обозначим Bm. Тогда . Такие кортежи называют упорядоченными наборами или векторами. Они имеют широкое применение в дискретной математике.

Вектор из нулей и единиц можно рассматривать как двоичное представление натурального числа.

Вектор, состоящий из единиц и нулей, описывает состояние памяти вычислительных машин, причём память может содержать числа, тексты, команды и т. д.

Пусть заданы множества . Декартовым произведением этих множеств называется множество , состоящее из всех кортежей длины n, в которых , где . Поскольку для задания кортежа важен порядок, то порядок множителей важен и в декартовом произведении.

Например, декартовым произведением множеств и будет являться множество пар . Скобки для указания пар опускают там, где это не может привести к затруднениям: . Если множества А:= и В:= конечны, то их декартово произведение может быть представлено в общем виде таблицей из m столбцов и k строк (рис. 1.9).

Источник