Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров, страница 2

Танин образом, в первичной простоте понятия «множество», которая декларировалась в начале главы, при более внимательном рассмотрении не оказывается ни простоты, ни первичности. Однако сказанное там остается в силе, и понятие множества будет по-презкнему считаться исходным ввиду сделанной в отступлении 1.1 оговорки, которую здесь сформулируем следующим образом: для тех теорий, использующих понятие множества, которые будут рассматриваться в дальнейшем, знать все сложности, связанные с заданием множеств, ве обязательно (за исключением гл.

5 н 6); достаточно зафиксировать некоторыс хоннретные средства их задания. Со своей стороны обещаем, что зги средства всегда будут конструктивнымн и не будут вызывать неясностей в их толконаиии. Операции над множествами, Объединением множеств Л 13 и В (обозначение — А()В) называется множество, состоящее нз всех тех элементов, которые принадлежат хотя бы одному нз множеств А, В. Символически это можно записать так: А()В =- (х)хЕА или хЕВ).

Аналогично определяется объединение произвольной (в том числе бесконечной) совокупности множеств. Если совокупность содержит небольшое количество множеств, то нх объединение описывается явно: А () В () С() 0 и т, д. В об- щем случае используется обозначение () А, которое читает- А!аз ся так: «объеднненне всех множествА, принадлежащих со- вокупности 5». Если же все множества совокупности зану- мерованы индексами, то используются другие варианты обо- значений () А, (для случая, когда Я=(Л!, Аг, -, Аь)), () Л! !' =! к=! (для случая, когда 5 — бесконечная совокупность и ее мно- жества занумерованы подряд натуральнымн числами), и А! (для случая, когда набор индексов множеств задан ! э!г множеством 1), Пример 1.2.а.

Л (а, Ь, д), В=(Ь, с(, е, !!), А()В =(а, Ь, г(, е, Ь). б. М1()М,=М»=М4 (так как М» и М« равны). в. Обозначим футбольные команды высшей лиги через !б Ф!: Мг (Ф!, Фм ... Ф!«). Тогда и Ф! — множество всех фут!=! болнстов (но пе команд!) высшей лиги. Обобщая последнее замечание, отметим, что всегда А«:-(А() В), но неверно Аев(А 0 В). г. Обозначим через Ь!» множество всех натуральных чи- сел, делящихся на Ь н не равных Ь, а через Р— множество всех простых чисел (прннято считать, что АР). Тогда 0)Ч! — множество всех составных, т.

е. непростых, чисел. !е я Пересечением множеств А и В (обозначение А () В) на- зывается множество, состоящее из всех тех н только тех элементов, которые принадлежат н А, н В: Л(')В ° (х(хЯА и хЕВ). Аналогично определяется пересечение произвольной (в том числе бесконечной) совокупности множеств, Обозна- чения для пересечения системы множеств аналогичны при- веденным выше обозначениям для объединения. 14 Пример 1.3. а. А=(а, Ь, аг), В=(Ь, д, е, 6), АПВ (Ь, с(). б Мз П Мв=Мв =Ми |в в. ПФг=Я; более того, для любых 1 и / ФЯФ; Я, в ! Заметим, что в общем случае из первого свойства не следует второе: например, если А=(а, Ь), В=(Ь, с) С=(а, с), то А ДВП С пусто, однако все попарные пересечения непусты.

Система множеств, в которой все попарные пересечения множеств пусты, называется разбиением множества У всех элементов этих множеств, а множества такой системы называются классами или блоками разбиения. Всякий элемент (г входит в один и только в один класс разбиения. Например, Мг является разбиением множества всех футболистов высшей лиги; классы этого разбиения — команды; всякий футболист из множества () Ф, может входить только в одг=! ну команду.

Подробнее о разбиениях см. 3 1.3 и 2.2. г. П У;= О (обозначения те же, что и в и. «г» примера вше 1.2), так как элемент такого множества долгкен делиться на все простые числа; ввиду бесконечности множества простых чисел это невозможно. Разностью множествА и В (обозначениеА В) называется множество всех тех и только тех элементов А, которые не содержатся в В: А',В = (х)хЕА и хфВ~. В отличие от двух предыдущих операций разность, вопервых, строго двухместна (т. е.

определена только для двух множеств), а во-вторых, некоммутативна: А' Вчь чаВ,А. Если А,В-3, то АаВ. Пример 1А. а. А=(а, Ь, с(), В= (Ь, д, е, 6), А ' В (а), В' А (е, Й). б МЗ ~М4 Мв МЭ О. в. М; М,— множество всех команд высшей лиги,за исключением «Арарата». Эта запись не вызывает разночтений, однако, строго говоря, она неточна: из М, вычитается не множество Мв футболистов (это бессмысленно, так как Мв и Мг имеют элементы разной природы), а одноэлементное множество (Мв) команд. Правильная запись М,' (Мв). Аналогично этому для множества А = (а, Ь, с() запись А' а неверна, а запись А,(а) верна. Напротив, в раз!в мости (1Фг'~,Мв (множество всех футболистов высшей лиги, Вся и не выступающих в «Арарзте») л4з является именно множеством футболистов и заключать его в фигурные скобки не следует.

В случаях, когда одновременно рассматриваются множества и множества множеств, соблюдение подобных тонкостей не является пустым педантизмом, а предо. храняет от возможной путаницы. Если все рассматриваемые множества являются подмножеством некоторого «универсального» множества У, то может быть определена операция дополнения. Дополнением (до (') множества А (обозначепиеА) называется множество всех элементов, не принадлежащих А (но принздлежащнх 6'): А=У';А. Множество У должнобытьлибозадано, либо очевидно из контекста, в противном случае проще пользоваться выражением У" А.

Например, из определения М» очевидно, что л4, — это множество натуральных чисел, ббльших 100. Запись же У без контекста, т, е, без указания У, неясна — то ли это множество отрицзтельпых целых чисел, то ли множество положительных дробных чисел, то ли пустое множество натуральных чисел. Операции объединения, пересечения н дополнения часто называют булевыми операциями над множествами.

Позднее (в гл. 2 и 3) будет пояспеп смысл этого названия и рассмотрены соотношения между этими операциями. Векторы н прямые произведения. Вектор — это упорядоченный набор элементов. Сказанное пе следует считать определением вектора, поскольку тогда потребуется давать объяснения по поводу его синонима «упорядоченный набор». Понятие «вектор» (другой синоним — «кортеж») будем считать, как и понятие множества, неопределяемым.

Элементы, образующие вектор, называются координатами или компонентами вектора. Координаты нумеруются слева направо. Число координат называется длиной или размерностью вектора, Бесконечные векторы рассматриваться не будут, В отличие от элементов множества координаты вектора могут совпадать. Вектор будем заключать в круглые скобки, например (О, 5, 4, 5). Иногда скобки и даже запятые опускаются. Векторы длины 2 часто называются упорядоченными парзми (или просто парами), векторы длины 3 — тройками и т. д, Вектор длины и иногда называют и-кой («энкой»). Два вектора равны, если они имеют одинаковую длину и соответствующие координаты их равны.

Иначе говоря, векторы (аь ..., а ) и (Ьь ..., Ь„) равны, если и=и и а,= =Ьь а~=Ь~, ..., а„=Ь . 1В Прямым произведением множеств А н В (обозначение АХВ) называется множество всех пар (а, Ь), таких, что аенЛ, ЬенВ. В частности, если Л =В, то обе координаты принадлежат А. Такое произведение обозначается Л'. Аналогично прямым произведением множеств Л1, ..., А, (обозначение Л1Х... ХА,) называется множество всех векторов (а,, а,) длины и, таких, что а1яЛ1, ..., а4енА . АХ...ХЛ обозначается А'.

Пример 1.5. а. Множество НХЯ=И3 — это множество точек плоскости, точнее, пар вида (а, Ь), где а, Ь~)7 и являются координатами точек плоскости. Координатное представление точек плоскости, предложенное французским математиком и философом Декартом, исторически первый пример прямого произведения, Поэтому иногда прямое произведение называют декартовым. б. А=(а, Ь, с, 4(, е, 1, д, Ь), В=(1, 2, „8). Тогда АХВ= =(а1, а2, аЗ, ..., Ь7, Ь8) — множество, содержашее обозначения всех 64 клеток шахматной доски.

в. Рассмотрим множество числовых матриц ЗХ4, т. е. матриц вида а11 а1, а1, а,4 ам ам ам ам а31 а33 а33 а34 где аи принадлежит множеству Й действительных чисел. Строки матрицы — это элементы множества 714 (векторы длины 4). Сама матрица, рассматриваемая как упорядоченный набор (т. е. вектор) строк, — это элемент множества (Й4)3=В4ХЙ4ХЙ4, Компоненты матрицы, задашюй таким образом,.— строки, а не числа. Поэтому (141) 3Ф)713. Содержательный смысл этого неравенства в том, что в векторе из Й13 не содержится никакой информации о строении матрицы; тот же вектор из Я13 мог бы перечислять элементы матриц 4ХЗ или 2Х6, которые как математические объекты вовсе не совпадают с матрицами ЗХ4. Приведенный пример показывает, в частности, что компонентами векторов могут быть также векторы. г, Пусть Л вЂ” конечное множество, элементами которого являются символы (буквы, цифры, знаки препинания, знаки операций и т.

д.). Такие множества обычно называют алфавитами. Элементы множества А" называются словами длины и в алфавите А. Множество всех слов в алфавите А — это множество Л3=()Л1=Л1() А3()Л3() ... При написа- 1ЕП 2 — 750 17 нии слов (которые по нашему определению являются векторами) не принято пользоваться ни запятыми, ни скобками как разделителями; но онн могут оказаться символами самого алфавита. Поэтому слово в алфавите А — это просто конечная последовательность символов алфавита А, Например, десятичное целое число — это слово в алфавите цифр (О, 1, ..., 9). Текст, напечатанный на пишущей машинке, является словом в алфавите, определяемом клавиатурой данной машинки (включая знаки препинания и пробел1).

Теорема 1.1. Пусть Аь Ат,, А, — конечные множества и 1А,~ =им (Аз(=гпз, ..., (А ~ =т,. Тогда мощность множества А~ХА»Х...ХА„равна произведению мощностей Ан Аз,,,А: ~А,хАзх ... хА„~ т,тз ... гп„, Эту теорему докажем методом математической индукции. Для и 1 теорема тривиально верна. Предположим, что она верна для и л, и докажем ее справедливость для п=й+1. По предположению, ~А«ХАзХ...ХАа~ ттптз, ..., пть. Возьмем любой вектор (аь ..., аь) из А~ХАзХ...ХАа и пРипишем спРава элемент аа+,ееАа+ь Это можно сделать иачч разными способами; при этом получится тачч различных вектоРов из А,ХА,Х...ХАа+ь Таким обРазом, из Дсех пть..та векторов приписыванием справа элемента из Аач« можно полУчить гпь..тагпачч вектоРов из А~ХАзХ...ХАанм причем все они различны, и никаких других векторов в А~Х ХАзХ ° .ХАачч не содеожится.

Поэтому для п=й+1 теорема верна и, следовательно, верна для любых п. П' Следствйе, (А"~=~А~", Эта простая теорема и ее следствие лежат в основе очень многих комбннаторных фактов. Проекции. Проекцией вектора о на 1-ю ось (обозначение пргп) называется его 1-я компонента, Проекцией вектора и= =(а„..., а,) на оси с номерами 1ь ..., 1« называется вектор (а;„..., а; ) длины й (обозначение прн,„о), Пусть т' — множество векторов одинаковой длины. Тогда проекцией множества )г на гчю ось называется множество проекций всех векторов нз )г на 1-ю осам пр;)' (нрпо~пап ен)г).