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

При задании некоторого конечного множества списком его элементов порядок указания элементов этого множества не имеет значения. Например, множества {a, b} и {b, a} совпадают, так как они состоят из одних и тех же элементов, хотя порядок указания элементов в этих записях различен. Кроме этого, каждый элемент входит в множество в точности один раз, то есть среди элементов множества нет повторяющихся. Так, запись {a, a} означает множество, состоящее из единственного элемента a, то есть {a, a} = {a}.

Введем новое исходное понятие – понятие упорядоченной пары (a, b), которая представляет собой набор двух объектов a и b, не обязательно различных, первым элементом которого является a, а вторым – b.

Декартовым (прямым) произведением множества А на множество В называют множество всех упорядоченных пар (a,b), где первый элемент пары a является элементом множества А, а второй b – множества B и обозначается А х В.

Пример. Даны множества А={1,2,5} и B={4,6}. Тогда декартовое произведение AxB={(1,4),(1,6),(2,4),(2,6),(5,4),(5,6)}.
Декартово произведение множеств само является множеством и по- этому к нему применимы все изученные ранее способы задания и операции.

Декартовым квадратом множества А называют декартовое произведение множества А на множество А (т.е. само на себя). Координатное представление точек плоскости было впервые предложено Р. Декартом и исторически является первым примером прямого произведения. Поэтому часто прямое произведение множеств называют декартовым произведением.

dpm.jpg

Обобщением понятия упорядоченной пары является понятие кортежа (вектора) – упорядоченного набора произвольных, не обязательно различных n объектов. Кортеж, состоящий из элементов x1, x2, …, xn, обозначается (x1, x2, …, xn) или < x1, x2, …, xn >. Элементы xi (i = 1, 2, …, n) называются координатами или компонентами кортежа.
Число координат называется длиной кортежа (размерностью вектора). Кортежи длины 2 называют также упорядоченными парами, кортежи длины 3 – упорядоченными тройками и т.д., кортежи длины n – упорядоченными n-ми («энками»).
Два кортежа (x1, x2, …, xn) и (y1, y2, …, ym) называются равными (пишут (x1, x2, …, xn) = (y1, y2, …, ym)), если: 1) n = m; 2) xi = yi (i = 1, 2, …, n).

Проекцией вектора a(a1, a2, … an) на некоторую ось называется его компонента (координата) с соответствующим порядковым номером (обозначается прia). Например, проекция точки плоскости на 1-ю ось есть её абсцисса (первая координата).
Два вектора равны, если они имеют равную длину и их соответствующие координаты равны.

При разработке информационных систем часто бывает необходимо описывать запросы на получение информации. Для этого можно использовать язык теории множеств. Массивы однородных данных Мi представляют собой множества, а файл базы данных является подмножеством М их декартового произведения. Каждый запрос к этому файлу представляет собой проекцию множества М, полученную в соответствии с условиями запроса.Рассмотрим пример нахождения множества следователей моложе 30 лет со стажем работы в ОВД более 3 лет с указанием специальных званий и фамилий.
Для решения задачи может быть использована следующая таблица реляционной базы данных:
prv.jpg

Полезные ресурсы:

http://www.vimvd.ru/institute/structure/chairs/vm/methodical/fzodm.pdf

http://www.slideshare.net/guseva89/1-3-5399763
Электронный вариант издания «Элементы комбинаторики» д.м.н. Мищенко С. П. http://ipk.ulstu.ru/files/ipk/distanc/kons/fmo/m_9kons.pdf

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

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