Спирина, М.С. Дискретная математика

Т а б л и ц а 1.5 Табличное задание декартова произведения X * Y ■ Y X Yi Y2 У .3 Х\ (хь У|) (*ь У2) (хь Уз) Х2 ( *2 . У 1 ) (* 2 . Уг) (* 2 , Уз) X, (*з> У\) (*з, Уг) (*3, Уз) Х4 (*4. У\) (Хь Уг) (*4, Уз) Например, декартово произведение Л"х Y, где X - {хь х2, х3, х4}, a Y = tvi, у 2 , Уз}, можно представить в виде табл. 1.5. Число элементов в декартовом произведении конечных м н о ­ жеств А и В равно произведению числа элементов множества А на число элементов множества В. Варианты записи: \А х В\ = \А\ ■ |2?| или п(А х В) - п(А) п(В). Если А] = А2= ... = А„ = А, то пишут А" = А х А х . . . х А и назы- П вают я-й декартовой степенью множества А. Например, плоскость является декартовым квадратом двух п р я ­ мых и обозначается соответственно R2. В физике пространствен­ но-временной континуум есть декартово произведение М3 х Т, где R3 — трехмерное пространство, а Т — числовая ось времени. Декартово произведение не обладает переместительным зако ­ ном, т.е., вообще говоря, пары (а, Ь) и ( b , а) различны: X х Y ф ф Y х X. Так, различны точки плоскости с координатами (5; 3) и (3; 5). Но для произвольного и пустого множеств справедливо Х х 0 = 0 х Х = 0 . Примерами декартовых произведений являются таблицы сло ­ жения и умножения, все возможные наборы пар координат на плос­ кости, троек координат некоторой точки в пространстве. Железно­ дорожный билет тоже является кортежем, а совокупность всех б и ­ летов — декартовым произведением множеств паспортов, поса­ дочных станций, станций прибытия, времени и других множеств. Если число элементов множества X обозначить |Л^, то справед­ ливо соотношение lA’]" = |ЛГ"|. Свое название декартово произведение получило в честь вы ­ дающегося французского математика и философа Рене Декарта (1596— 1650), являющегося автором знаменитого метода коорди­ нат. Вспомните выражение «прямоугольная декартова система к о ­ ординат», причем координаты точек в этой системе также явля ­ ются кортежами. На плоскости двумерные кортежи — это пара вида (х; у), а в пространстве — трехмерные кортежи в виде тройки 37