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

Из двух данных кортежей (аь аъ ..., а„ ..., ак), где а , е А, длины к и Ф\, h , ..., bj, ..., bm), где bj е В, длины т можно составить новый кортеж длиной к + т, элементы которого (аь а2, ..., ак, Ьь Ь2, ..., Ь„) принадлежат множеству A U В. Эта операция называется соеди­ нением кортежей. Кортеж можно образовать двумя способами, по­ этому важно, какой кортеж назван первым. Так, соединив кортежи четных и нечетных однозначных чисел <0, 2, 4, 6, 8) и (1, 3, 5, 7, 9), получим кортеж всех однозначных чисел (0, 2, 4, 6, 8, 1, 3, 5, 7, 9). Пусть А — конечное множество, элементами которого являются некоторые символы, например цифры, буквы, знаки препинания. Такие множества принято называть алфавитом над заданным мно­ жеством символов. Алфавит есть кортеж попарно различимых сим ­ волов, называемых буквами алфавита. Элементы множества А" при ­ нято называть словами длины п в алфавите А. Слово над алфавитом есть просто некоторая конечная последовательность символов. Так, шестизначный телефонный номер является словом длины 6 над алфавитом цифр {0, 1, 2, 9}. Если число элементов кортежа длины л можно представить в виде суммы л = я, + п2 + ... + пк, то кортеж длины л можно разбить на к кортежей, имеющих соответственно длины пь пъ ..., пк. Рассмотрим множество В, состоящее из двух элементов: 0 и 1. Кортежи длины т из этих элементов обозначим Вт. Тогда п(Вт) = = 2т. Такие кортежи называют упорядоченными наборами или век­ торами. Они имеют широкое применение в дискретной математике. Каждый такой л-мерный вектор единственным образом опреде­ ляет вершину куба, построенного на единичных векторах (рис. 1.13). В зависимости от величины п кубы могут быть одномерными (а), двумерными (б), трехмерными (в) и т.д. Вектор из нулей и единиц можно рассматривать к ак двоичное представление натурального числа. Вектор, состоящий из единиц и нулей, описывает состояние памяти вычислительных машин, причем память может содержать числа, тексты, команды и т.д. Рис. 1.13. Иллюстрация «-мерного куба: а — одномерного; б — двумерного; в — трехмерного 2 * 35