Что называют декартовым произведением множеств

10.04.202214.04.2022 admin 0 Comments

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

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

Содержание

Прямое произведение в теории множеств

Произведение двух множеств

Произведение множества <в, и, к> на множество цветов радуги
в	в	в	в	в	в	в	в
и	и	и	и	и	и	и	и
к	к	к	к	к	к	к	к

Отображения произведения множеств в его множители ( и ) называют координатными функциями.

Аналогично строятся произведения нескольких множеств.

Декартова степень

Прямое произведение семейства множеств

Прямое произведение отображений

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

Воздействие на математические структуры

Прямое произведение групп

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

Прямое произведение других алгебраических структур

Аналогично произведению групп, можно определить произведения колец, алгебр, модулей и линейных пространств, причём в определении прямого произведения 1_i (см. выше) следует заменить нулём. Однако, как правило, произведения этих структур называют прямой суммой.

Прямое произведение топологических пространств

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

Теорема Тихонова утверждает компактность произведений любого количества компактных пространств; однако для бесконечных произведений её не удаётся доказать без использования аксиомы выбора (или равносильных ей утверждений теории множеств).

Также, теорема Александрова показывает, что любое топологическое пространство можно вложить в (бесконечное) произведение связных двоеточий, если только выполнена аксиома Колмогорова (а иные пространства и не рассматриваются).

Прямое произведение графов

Множество вершин прямого произведения двух графов G и H задаётся как произведение вершин графов сомножителей. Рёбрами будут соединены следующие па́ры вершин:

Иначе говоря, множество рёбер произведения графов является объединением двух произведений: рёбер первого на вершины второго, и вершин первого на рёбра второго.

Вариации и обобщения

Источник

Декартово произведение. Разбиение множеств на классы

Онлайн-конференция

«Современная профориентация педагогов
и родителей, перспективы рынка труда
и особенности личности подростка»

Свидетельство и скидка на обучение каждому участнику

КАРТА – СХЕМА УЧЕБНОГО ЗАНЯТИЯ

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

расширить знания студентов с темы действия с множествами, рассмотреть Декартово произведение, разбиение множеств на классы;

способствовать развитию памяти, внимания, логического мышления;

создать условия для применения полученных знаний при выполнении расчетных заданий.

Необходимое аппаратное и программное обеспечение:

Карточки с заданиями самостоятельной работы

Тип и вид учебного занятия:

ОРГАНИЗАЦИОННАЯ СТРУКТУРА УРОКА

Содержание и виды деятельности преподавателя

1. Организационный этап

Приветствие, выявление отсутствующих, информирование о теме и целях занятия.

2. Актуализация ЗУН

— Что такое множество? Что означает задать множество?

— Способы задания множеств

— Что такое подмножество?

-какие действия выполняем над множествами?

— Что такое пересечение? Объединение?

— Какие свойства пересечения, объединения?

Самостоятельная работа (с взаимопроверкой)

Найдите: а) А∩В; б) А∩С; в) С∩В.

Найдите: а) АUВ; б) АUС; в) СUВ.

Найдите а)(А∩В)∩С; б) )(АВ)С; в) (А В)∩С

3. Изучение нового материала

— разбиение множеств на классы

4. Первичное закрепление

Практическое выполнение заданий

5. Информация о домашнем задании

Методические рекомендации для самостоятельной работы

6. Подведение итогов урока

Подведение итогов работы группы, отдельных студентов.

Корректирование пробелов знаний.

В начальных классах ученики решают задачу: используя цифры 1, 2, 3 образовать всевозможные двузначные числа.

Путем перебора дети получают:

Запись каждого числа состоит из двух цифр, причем существенен порядок их следования. Например, из цифр 1, 2 образованы числа 12 и 21.

В том случае, когда важен порядок следования элементов множества, в математике говорят об упорядоченных наборах элементов. В данной задаче – упорядоченные пары (а; b), образованные из элементов а и b. Это (1; 2), (1; 3), (1; 4) и т.д. Первый элемент а называют первой координатой пары, элемент b – второй.

Значит, в нашей задаче мы оперировали множеством А=<1, 2, 3> и образовывали всевозможные пары.

Рассмотрим другой пример. Пусть А=<1, 2, 3>, B=<4, 5>. Образуем всевозможные пары (а;b) так, что аА, bВ. Получим некоторое новое множество <(1; 5), (1; 4), (2; 4), (2; 5), (3; 4), (3; 5)>, элементами которого являются упорядоченные пары чисел. Это новое множество называют декартовым произведением множеств А и В.

Декартовым произведением множеств А и В называется множество пар, первая компонента которых принадлежит множеству А, вторая множеству В. Обозначают АВ. Таким образом АВ = <(x;y) | xA, yB>.

Операцию нахождения декартового произведения множеств А и В называют декартовым умножением этих множеств.

Количество пар в декартовом прoизведении АВ будет равно произведению числа элементов множества А и числа элементов множества В: n(АВ)=n(A)n(B).

В математике рассматривают не только упорядоченные пары, но и наборы из трех, четырех и т.д. элементов. Такие упорядоченные наборы называют кортежами. Так, набор (1, 5, 6) есть кортеж длины 3, так как в нем три элемента.

Используя понятие кортежа, можно определить понятие декартового произведения n множеств.

Декартовым произведением множеств А, А,…, A называют множество кортежей длины n, образованных так, что первая компонента принадлежит множеству А, вторая – А, …, n-ая – множеству А: АА…A.

Пусть даны множества А=<2, 3>; А=<3, 4, 5>; A=<7, 8>. Декартово произведение ААА=< (2, 3, 7), (2, 3, 8), (2, 4, 7), (2, 4, 8), (2, 5, 7),
(2, 5, 8),(3, 3, 7), (3, 4, 7), (3, 3, 8), (3, 4, 8), (3, 5, 7), (3, 5, 8)>.

Понятие разбиения множества на классы

Понятие множества и операций над множествами позволяют уточнить представление о классификации.

Классификация – это действие распределения объектов по классам на основании сходств внутри класса и их отличия от других объектов. Классификация широко применяется в математике.

Например, натуральные числа делятся на четные и нечетные; углы бывают острые, тупые и прямые и т.д.

Любая классификация связана с разбиением некоторого множества объектов на подмножества.

Считают, что множество Х разбито на классы Х, Х,…, Х, если:

1) подмножества Х, Х,…, Х попарно не пересекаются;

2) объединение этих подмножеств совпадает с множеством Х.

Если не выполнено хотя бы одно из этих условий, классификацию считают неправильной.

Например: а) Множество треугольников Х разбито на три класса: остроугольные, прямоугольные и тупоугольные. Действительно, выделенные подмножества попарно не пересекаются, а их объединение совпадает с множеством Х; b) Из множества треугольников Х выделили подмножества равнобедренных, равносторонних и разносторонних треугольников. Так как множества равнобедренных и равносторонних треугольников пересекаются, значит, не выполнено первое условие классификации, и разбиения множества Х на классы мы не получили.

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

Рассмотрим, например, множество натуральных чисел. Его элементы обладают различными свойствами. Нас интересуют числа со свойством «быть кратным 3». Это свойство позволяет выделить из множества N подмножество, состоящее из чисел, кратных 3. Тогда про остальные натуральные числа можно сказать, что они не кратны 3, т.е. получаем еще одно подмножество множества N. Так как выделенные подмножества не пересекаются, а их объединение совпадает с множеством N, то имеем разбиение данного множества на два класса.

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

Рассмотрим ситуацию, когда для элементов множества заданы два свойства. Например, свойства натуральных чисел: «быть кратным 3» и «быть кратным 5». При помощи этих свойств из множества N можно выделить два подмножества: А – множество чисел, кратных 3 и В – множество чисел, кратных 5. Эти множества пересекаются, но ни одно из них не является подмножеством другого (рис. 13). Разбиения на подмножества А и В в данном случае на произошло. Но круг, изображающий множество N, можно рассматривать как состоящий из четырех непересекающихся областей. Каждая область изображает некоторое подмножество множество N. Множество I состоит из чисел, кратных 3 и 5, множество I – из чисел, кратных 3 и не кратных 5, множество III – из чисел, кратных 5 и не кратных 3, множество IV – из чисел, не кратных 3 и не кратных 5. Объединение этих четырех множеств есть множество N.

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

Не следует думать, что задание двух свойств элементов множества всегда приводит к разбиению этого множества на четыре класса. Например, при помощи таких двух свойств «быть кратным 3» и «быть кратным 6» множество натуральных чисел разбивается на три класса (рис. 14): I – класс чисел, кратных 6; II – класс чисел, кратных 3, но не кратных 6; III – класс чисел, не кратных 3.

Примеры

Приведем несколько примеров разбиения:

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

2. Множество четырехугольников разбито на три класса:
квадраты, параллелограммы, прямоугольники. Так как прямоугольник и квадрат – частные случаи параллелограмма, то данные подмножества пересекаются, значит, не выполнено первое условие классификации, и разбиение множества не получено.

3. Дано множество прямых в пространстве, которое разбито на классы по их взаимному расположению: параллельные, пересекающиеся, скрещивающиеся. Данные подмножества попарно не пересекаются, а их объединения совпадают с множеством .

4. Дано множество , которое можно разделить на два класса: и , где – множество натуральных четных чисел, а – множество натуральных нечетных чисел.

5. Множество разбито на три класса: , и . множество чисел, которые делятся на , – множество чисел, которые делятся на , множество чисел, которые делятся на . Но существуют числа, которые могут делится одновременно и на , и . Отсюда следует, что подмножества пересекаются, и разбиение не получено.

Решение. Элементами множества А₁´ А₂ ´А₃ будут кортежи длины 3 такие, что первая их компонента принадлежит множеству А_1,вторая – множеству А₂, третья – множеству А₃.

Пример 2. Пусть на множестве Х= <3, 5, 7>задано отношение «меньше» (т.е. первый элемент меньше второго, второй меньше третьего). Записать декартово произведение XX. Из этого множества следует выбрать элементы, которые должны удовлетворять отношению «меньше».

Декартово произведение X  Х может быть записано в виде множества из упорядоченных пар:

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

В новом множестве все пары являются элементами декартова произведения XX. Отношение «меньше» на множестве Х является подмножеством декартова произведения XX. Бинарное отношение на множестве Х есть подмножество декартова произведения W XX.

Пусть заданы два множества: X = <2, 6, 1>, Y = <7, 4, 8>.

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

Источник

Лекция 2. Декартово произведение. Мощность множества

п.2. Декартово произведение. Мощность множества.

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

Упорядоченная пара интуитивно определяется как совокупность, состоящая из двух элементов x и y, расположенных в определенном порядке. Две пары и считаются равными тогда и только тогда, когда x=u и y=v.

Определение 2.1. Пусть A и B – два множества. Прямым (декартовым) произведением двух множеств A и B называется множество всех упорядоченных пар, в котором первый элемент каждой пары принадлежит A, а второй принадлежит B:

Пример. Пусть и . Тогда

Пример. На координатной плоскости построить следующее множество:

Решение. Первое множество помещаем на оси OX, второе на оси OY. Множество всех пар, т. е. декартово произведение, изображается точками заштрихованного прямоугольника, но без левой и нижней стороны.

Как вы знаете, точка на плоскости может быть задана упорядоченной парой координат, то есть двумя точками на координатных осях. Поэтому координатную плоскость можно задать в виде . Метод координат ввел в употребление Рене Декарт (), отсюда и название «декартово произведение».

Понятие прямого произведения допускает обобщение.

Прямое произведение множеств

Степенью множества A называется его прямое произведение самого на себя. Обозначение:

Соответственно, и вообще .

Решение. Множество Bn состоит из последовательностей нулей и единиц длины n. Они называются строкой бит или битовой строкой длины n.

Альберт Эйнштейн как-то говорил: «Не все, что можно сосчитать, сосчитано, и не все, что сосчитано, можно сосчитать». Хотя это высказывание не очень воодушевляет, попытаемся заняться подсчетами.

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

Определение 2.2. Два множества A и B называются эквивалентными, или равномощными, если между этими множествами может быть установлено взаимно однозначное соответствие. В этом случае пишут: A

Пример. 1) Множество десятичных цифр равномощно множеству пальцев на руках человека.

Пример 2.5. В компьютере все множества реальных объектов конечны: множество адресуемых ячеек памяти, множество исполнимых программ, множество тактов работы процессора.

Множества, которые не являются конечными, называются бесконечными. Если некоторое множество A равномощно множеству N, т. е. A

N, то множество A называется счетным (в зарубежной литературе: множество называются счетным, если оно конечно или счетно бесконечно). Счетное множество A – это такое множество, все элементы которого могут быть занумерованы в бесконечную последовательность a1, a2, …, an, …, так, чтобы при этом каждый элемент получил лишь один номер n и каждое натуральное число n было бы номером лишь одного элемента множества A. Мощность счетного множества принято обозначать через ( – первая буква древнееврейского алфавита, называемая «алеф», символ читается: «алеф-нуль»). В частности |N|=.

На первый взгляд, кажется, что это множество невозможно перенумеровать. Однако эту нумерацию можно осуществить, применив следующую хитрость: двигаясь не в одном направлении, а все время менять его. Иными словами, будем нумеровать так: числу 0 дадим номер 1, числу 1 – номер 2, числу —1 – номер 3, числу 2 – номер 4, числу —2 – номер 5, и т. д. Таким образом, получаем взаимно однозначное соответствие между множеством Z и N. А значит, множество Z счетно.

Множество A называется несчетным, если его мощность больше мощности множества N. В таком случае множество A называется континуальным или континуумом. Мощность континуума обозначается . Следующую теорему примем без доказательства.

2.3. Теоремы сложения и умножения.

Формула включений и исключений.

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

Теорема 2.2. (Теорема сложения)

Пусть – конечные попарно непересекающиеся множества, т. е. . Тогда

(2.3.1.)

Теорема 2.3. (Теорема умножения)

Пусть заданы конечные множества . Тогда

(2.3.2.)

т. е. число элементов декартова произведения множеств равно произведению количеств элементов сомножителей.

Пример. Сколько существует целых чисел между 0 и 1000, содержащих ровно одну цифру 6?

S1 – множество, которое содержит число, состоящее из одной цифры, и эта цифра 6;

S2 – множество, содержащее двузначные числа ровно с одной цифрой, равной 6;

S3 – множество, содержащее трехзначные числа ровно с одной цифрой, равной 6.

В множестве S2 каждый элемент, содержащей 6, имеет ее либо первой, либо второй цифрой. Если 6 – вторая цифра, то существует 8 различных чисел, которые будут стаять на первом месте, поскольку первое число не может быть 0 или 6. Если 6 – первая цифра, то таких чисел 9, поскольку вторая цифра не может быть 6. Таким образом, S2 содержит 8+9=17 элементов, т. е. | S2|=17.

Элемент из S3 содержит 6 как первою, вторую или третью цифру. Если 6 – первая цифра, то существует 9 вариантов выбора второй цифры и 9 вариантов выбора третьей цифры. Согласно комбинаторному принципу умножения, S3 содержит 9 ´9=81 чисел с первой цифрой. Если 6 – вторая цифра, то имеются 9 вариантов выбора третьей цифры и 8 вариантов выбора первой цифры, поскольку первая цифра не может быть нулем. Следовательно, S3 содержит 9´8=72 числа, у которых 6 – вторая цифра. Аналогично, S3 содержит 72 числа, у которых 6 – третья цифра. Следовательно, всего S3 содержит 81+72+72=225 элементов, т. е. |S3|=225.

Поскольку и множества S1, S2 и S3 попарно непересекающиеся, то

Поставим задачу подсчитать число элементов в объединении

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

Теорема 2.4. (Формула включений и исключений).

Для конечных множеств , справедлива формула включений и исключений.

(2.3.3.)

В частности для двух множеств эта формула примет вид:

Для трех множеств формула включений и исключений примет вид:

Название этой теоремы подчеркивает использование последовательных включений и исключений элементов подмножеств.

X1 – множество положительных целых чисел, которые делятся на 2. Число элементов или мощность этого множества равно .

X2 – множество положительных целых чисел, которые делятся на 3. Число элементов или мощность этого множества равно .

X3 – множество положительных целых чисел, которые делятся на 5. Число элементов или мощность этого множества равно .

Тогда множество X1ÇX2 – множество положительных целых чисел, которые делятся на 2 или 3. Число элементов или мощность этого множества равно . Множество X1ÇX3 – множество положительных целых чисел, которые делятся на 2 или 5. Число элементов или мощность этого множества равно . Множество X2ÇX3 – множество положительных целых чисел, которые делятся на 3 или 5. Число элементов или мощность этого множества равно .

Множество X1ÇX2ÇX3 – множество положительных целых чисел, которые делятся на 2, 3 или 5. Число элементов или мощность этого множества равно .

Воспользуемся формулой включения и исключения, чтобы найти число элементов множества X. Получаем

2.4. Представление множеств в компьютере.

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

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

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

Новиков математика для программистов. Учебник для вузов. 2-е изд. – СПб.: Питер, 2006.

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

Пусть задан конечный универсум U, и число элементов в нем не превосходит разрядности компьютера, . Элементы универсума нумеруются:

где – это i-й разряд кода C.

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

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

Источник

визитки установка дверей шаблоны →

Добавить комментарий Отменить ответ

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Комментарий *

Имя *

Email *