152

25.10.2017

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ СТРОИТЕЛЬНЫЙ УНИВЕРСИТЕТ»

ИНСТИТУТ ЭКОНОМИКИ, УПРАВЛЕНИЯ И ИНФОРМАЦИОННЫХ СИСТЕМ В СТРОИТЕЛЬСТВЕ

(ИЭУИС)

Факультет информационных систем, технологий и автоматизации в строительстве

(ИСТАС)

Ф.К. Клашанов

Курс лекций

по дисциплине

ДИСКРЕТНАЯ МАТЕМАТИКА

Учебное пособие

Москва 2011

Клашанов Ф. К. Дискретная математика. Курс лекций. Учебное пособие. М.: МГСУ, 2011. – 198 с.

В учебном пособии по дискретной математике представлены материалы в помощь бакалаврам, изучающим дискретную математику в Московском государственном строительном университете на факультете ИСТАС и обучающихся по направлению подготовки 230100 «Информатика и вычислительная техника», а профиль подготовки: Автоматизированные системы обработки информации и управления в строительстве (АСОИУ) и Системы автоматизации проектирование (САПР) в строительстве. Учебное пособие представляет собой единый методически взаимоувязанный материал, состоит из следующих взаимосвязанных разделов: элементы теории множеств; сведения из булевой алгебры; элементы комбинаторики; основы теории графов. Учебное пособие взаимосвязано с методическими пособиями по практическим и самостоятельным работам, в которых даются математические понятия приведенные в учебном пособии. Материал рассчитан на односеместровое занятие на 108 часов, куда входят аудиторные и самостоятельные занятия. В конце каждой темы приведены вопросы для самоконтроля.

Учебное пособие будет полезно при изучении курса «Дискретная математика».

СОДЕРЖАНИЕ

Лекция 1 …………………………………………………………………………………. ВВЕДЕНИЕ ……………………………………………………………………... Цель и задачи предмета ………………………………………………………. Предмет дискретной математики ……………………………………………. Основные разделы дискретной математики ………………………………. Изоморфизм …………………………………………………………………… Контрольные вопросы …………………………………………………………………	8 8 8 9 10 11 15
Лекция 2 …………………………………………………………………………………. ОСНОВЫ ТЕОРИИ МНОЖЕСТВ …………………………………………………... Интуитивное понятие множества. Основные принципы …………………. Множество и элементы множества …………………………………………. Конечные и бесконечные множества ……….………………………………. Задание множества .…………………………………………………………….. Мощность множества …………………………………………………………... Подмножество, собственное подмножество ……………………………….. Кортеж …………………………………………………………………………… Символический язык содержательных теорий множеств ……………… Добавление и удаление элементов …………………………………………. Булеан и универсумом ………………………………………………………. Диаграммы Венна (Круги Эйлера) …………………………………………… Ограниченные множества. Границы множеств ……………………………. Точная верхняя (нижняя) граница ………………………………………….. Принцип двойственности ……………………………………………………… Линейные пространства ………………………………………………………... Контрольные вопросы …………………………………………………………………	16 16 16 16 18 18 18 20 21 22 23 24 24 24 25 26 26 31
Лекция 3 …………………………………………………………………………………. ОПЕРАЦИИ НАД МНОЖЕСТВАМИ ……………………………………………... Симметрическая разность ……………………………………….……………. Дополнение ………………………….…………………………………………. Двуместные операции ……….…………………………………………………. Порядок выполнения операций .…………………………………………….. Теоретико-множественные тождества ……………………………………… Законы для объединения и пересечение …………………………..………. Законы для дополнений ………………………………………………………. Законы для разностей множеств …………….………………………………. Покрытие и разбиение множеств …..……………………………………… Частично упорядоченные множества …………………………………………….. Контрольные вопросы …………………………………………………………………	33 33 34 34 34 34 35 31 32 32 37 38 40
Лекция 4 …………………………………………………………………………………. ОТНОШЕНИЯ. ОТОБРАЖЕНИЯ. СООТВЕТСТВИЯ …………………………... Бинарные отношения …………………………………………….……………. Свойства бинарных отношений ………………………………………………. Отношение эквивалентности ……………………………………………. Отношение толерантности .……………………………………………….. Отношения порядка ………………………………..……………………… Тернарные отношения ………………………………………………………… n-арные отношения …………………………..…………………………………. Отображения ……………………………………………………………………. Соответствие ……………………..………….…………………………………. Функция …..………………………………………………………..…………… Представление функции в терминах отношений ………………………….. Функции, функционалы, операторы ………………………………………….. Суперпозиция бинарных отношений ………………………………………. Обратная функция ………………………………………………………………. Классификация отображений ……………………………………………….. Операция ………………………………………………………………………… Частично упорядоченные множества ……………………………………….. Минимизации представления множества ………………………………….. Контрольные вопросы …………………………………………………………………	41 41 41 42 43 45 45 46 45 46 46 46 47 50 51 51 51 51 52 52 53
Лекция 5 …………………………………………………………………………………. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ ……….….……………………………………... Основные правила комбинаторики …………..………………………………. Правило произведения ……………………………………………………. Правило сумм ………………………………………………………………. Перечислительная комбинаторика ………………………………………….. Перестановки ………………………….…………………………………… Размещения ……………………………….………………………………… Размещения с повторениями …………….…………………….………. Упорядоченное размещение ……………………………………………. Сочетания ………………………….………………………………………. Сочетания с повторениями ……..………………………………………… Комбинации элементов с повторениями ……………………………… Бином Ньютона …………………………………………………………………. Разбиения. Комбинаторные числа Стирлинга и Белла …………………. Числа Стирлинга 2-го рода ……………………………………………... Метод производящий функций ………………………………………………... Контрольные вопросы …………………………………………………………………	55 55 55 55 55 54 54 56 56 57 59 59 59 61 62 63 64 66
Лекция 6 …………………………………………………………………………………. АЛГЕБРАИЧЕСКАЯ СИСТЕМА ……….…………………………………………... Замыкание и подалгебры ………………………………………….……….… Морфизмы …..…………………….……………………………………………. Гомоморфизмы …………..…………………………………………………. Фундаментальные алгебры .……………….………………………………….. Алгебры с унарными операциями ……...…………………………………… Алгебры с бинарными операциями ………………………………………… Алгебры с одной бинарной операцией …………………………..…………. Полугруппа ………………………….……………………………………………. Моноид …………………………..…………….…………………………………. Группоид …..…………………………….……………………………………… Группа ……………………………………………………………………………… Абелева группа ………………………………………………………………… Алгебра с двумя операциями ……………………………………………….. Кольца ……………………….………………………………………………… Тело ……………………………………………………………………………. Поля …………………………………………………………………………… Отношения ……………………………………………………………………… Граф ……………………………………………………………………………… Матрица смежности ……………………………………………………………. Фактор-множества и фактор-алгебра …………………………………………… Целые числа по модулю m ………………………………………………………… Конгруэнции ………………………………………………………………………. Контрольные вопросы …………………………………………………………………	67 67 67 68 68 69 69 69 69 70 71 71 72 72 72 72 73 73 73 73 73 74 74 75 76
Лекция 7 …………………………………………………………………………………. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ ……. ……………………………………………... Определение ……………………………………….……………. ………………... Граф, вершина, ребро …………………………….………………………….……. Неориентированный граф ……….……………………………………………. Инцидентность, смешанный граф .…………………………………………….. Эквивалентный ориентированный граф ……………………………………… Обратное соответствие …………………….……………………………………… Изоморфизм графов ……………………………………..………………..………. Путь, ориентированный маршрут ………………………………………………. Смежные дуги, смежные вершины, степень вершины ………………………. Компонентная связность ………………...……………………………………… Граф со взвешенными дугами …………...……………………………………… Подграф …………...……………………………………………………………..… Контрольные вопросы …………………………………………………………………	76 76 76 77 78 78 78 79 79 79 80 80 81 87 87
Лекция 8 …………………………………………………………………………………. ДЕРЕВЬЯ ……. …………………………………………………………………..……... Свободные деревья …………………………….……………. ………………... Ориентированные, упорядоченные и бинарные деревья …….………………….. Упорядоченные деревья ………………………………………………………. Представление деревьев в компьютере ………………………………………….. Контрольные вопросы …………………………………………………………………	88 88 88 91 91 93 97
Лекция 9 …………………………………………………………………………………. БУЛЕВА АЛГЕБРА ...………………………………………………………………..... Основные логические функции ………………………………………………….. Булева функция ……………………………………………………….……………. Двухэлементная булева алгебра ……………………………………. ……………. Функции одной переменной y = f(x) ………………………………...................... Таблицы булевых функций ………………………………………………………. Функции двух переменных z = f(x,y) ……………………………………………… Порядок выполнения операций …………………………………………………… Эквивалентность формул …………………………………………………………. Графический способ задания булевой функции …………………………………. Фактор-алгебра алгебры формул ………………………………………………….. Контрольные вопросы …………………………………………………………………	98 98 98 99 100 100 101 101 105 105 107 109 109
Лекция 10 …………………………………………………………………………………. ДИЗЪЮНКТИВНЫЕ И КОНЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ Определение ………………………….…………………………………………. Алгоритм приведения формулы к ДНФ ….……………………………………. Совершенные ДНФ (СДНФ) и КНФ (СКНФ) ……………………………….. Первая теорема Шеннона ……………….……………………………………… Вторая теорема Шеннона ………………………………………………………… Функциональная полнота ……………………………………………………..………. Алгоритм нахождения СДНФ ………………………………………………………. Минимизация булевых функций в классе ДНФ ….…………………………………. Метод Квайна …..……………………………………………………….. Контрольные вопросы …………………………………………………………………	110 110 110 110 111 112 112 113 113 114 115 116
Лекция 11 …………………………………………………………………………………. ПОЛНЫЕ СИСТЕМЫ БУЛЕВЫХ ФУНКЦИЙ ………………………………. Каноническое представление логических функций …………………………….. Системы булевых функций ….…………………………………………………. Теорема (о двух системах) ………..…………………………………………….. Базис Жегалкина ………………..……………………………………………… Классы булевых функций ………………………………………………………. Теорема (Пост-Яблонского) …………………………..…………………………. Теорема (Пост) ……………………………………………………………………. Алгебра Жегалкина …………………………….…………………………………. Контрольные вопросы …………………………………………………………………	116 116 116 117 117 118 118 119 120 122 123
Лекция 12 …………………………………………………………………………………. ЛОГИКА ВЫСКАЗЫВАНИЙ ………………………………………………………. Определения ………………………….…………………………………………. Формулы логики высказываний ………………………………………………. Порядок выполнения операций .…………………………………………….. Правила преобразования формул ……………………………………… Основные равносильности ……………..……………………………………… Правило перехода к булевым функциям …………………………..………. Нормальные формы формул логики высказываний ………………………. Законы логики высказываний. Тавтологии .…………………………………. Контрольные вопросы …………………………………………………………………	123 123 123 125 126 126 127 128 129 129 131
Лекция 13 …………………………………………………………………………………. ЛОГИКА ПРЕДИКАТОВ ………………………………………………………. Определение предиката …………………………………………………………. Язык логики предикатов ……….…………………………………………………. Логические операции (связки) над предикатами ………………………….…….. Кванторы ………………………………………………….………………………… Квантификация многоместных высказывательных форм ……………………… Булева алгебра предикатов …………………………………..…………..………. Формулы ……………………..…………………………………………………. Алгоритм преобразования формул в нормальную форму……………………. Исчисление предикатов …..……………………………………………………… Следование и эквиваленция ……………………………………………………… Правила вывода исчисления предикатов ……………………………………….. Отрицания в исчислении предикатов ……………………………………………. Контрольные вопросы …………………………………………………………………	131 131 131 132 134 138 139 142 143 145 146 146 147 150 151

Лекция № 1

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

Садовничий В.А. академик РАН,

из предисловия С.В. Яблонский Введение в дискретную математику. М.: Высшая школа, 2003

ВВЕДЕНИЕ (2 часа)

Цель и задачи предмета

Данное учебное пособие представляет собой единый методически взаимоувязанный материал, который будет полезен студентам, изучающим дискретную математику в Московском государственном строительном университете на факультете ИСТАС и рассчитан на студентов, обучающихся по специальности 220200 «Автоматизированные системы обработки информации и управления» (код по ОКСО 230102) по направлению 654600 «Информатика и вычислительная техника» (код по ОКСО 230100), а также по специальности 220100 – Вычислительные машины, комплексы, сети системы. Тематикой данного пособия являются языки, модели и методы решения задач теории множеств, математической логики и теории графов, интерпретированные на дискретные объекты.

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

Как отмечает /60/, в истории развития цивилизации человечества можно выделить три периода: аграрный, индустриальный и информационный. Аграрный период, закончившийся в XVII, являлся основоположником элементарной математики (арифметики) количественно описывающей материальное представление мира и удовлетворявшейся числом. Индустриальный период, с XVII по XX века, потребовал развития другого уровня математики, описывающей процессы и их развитие, как в пространстве, так и во времени и потребовал развития высшей математики – анализа, введения функции. Информационный период начался с XX века, базируется на обработке информации, и потребовал развития дискретной математики, основанной на алгебре и использующей понятия радикала.

Таким образом, математику как науку можно разделить на дискретную и непрерывную (континуальную). В континуальной математике явно или неявно содержится идея теории пределов и непрерывности, применявшаяся при решении задач сплошных сред. С развитием физики стал развиваться квантовый подход к описанию вещества. Все остальное, что не относится к континуальной математике – это дискретная математика, куда в частности входят арифметика, алгебра, теория множеств и общая теория отображений, математическая логика, комбинаторный анализ, теория алгоритмов и др. Дискретная математика особенно активно стала развиваться в XX веке, как основная ветвь математики. Это объясняется следующими причинами:

• язык дискретной математики является метаязыком всей современной математики;

• дискретная математика – это теоретическая основа компьютерной математики;

• модели и методы дискретной математики являются хорошим средством и языком для построения и анализа моделей в различных науках, включая и вопросы, связанные со строительством;

• проблемы абстрагирования конкретной проблемы и перевода ее на язык доступный ЭВМ наиболее просто и объемно решаются методами дискретной математики.

Цель читаемого курса – помочь студентам овладеть математическим аппаратом синтеза и анализа дискретных структур (систем с сосредоточенными параметрами; процессов, протекающих в дискретные моменты времени), а его содержанием - являются теория множеств, математическая логика и теория графов. Студент должен самостоятельно изучить соответствующий теоретический материал и ознакомиться с решением типовых примеров, приведенных в настоящем учебнике. Задачи по дискретной математике не требуют предварительных дополнительных знаний и любой здравомыслящий человек, претендующий на получение высшего технического образования, должен суметь выполнить эти задачи. Важность изучения дискретной математики проявляется в том, что, современная жизнь абсолютно немыслима без компьютеров, а в основе любого вычислительного устройства лежат знания именно дискретной математики, (которая является наукой 21-го века, и без ее развития немыслимы успехи технического прогресса). Поэтому освоение элементарных знаний в области дискретной математики расширит кругозор студента, повысит его математическую культуру и позволит ему в какой-то степени понимать работу вычислительных устройств и лучше ориентироваться в современном мире. Дискретная математика является основой для таких спецкурсов, как базы данных и базы знаний, теории алгоритмов, компьютерной алгебры, геометрии, текстовых и графических редакторов и т.п. В классический курс дискретной математики входят также такие разделы, как кодирование (необходимое для безошибочной передачи информации на расстояние, именно с помощью кодирования работают Интернет и электронная почта), теория графов и алгоритмов. Тема теории графов важна тем, что она помогает проанализировать ряд прикладных задач в том числе и сети (сетевой граф).

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

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

Предмет дискретной математики

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

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

Простейшим (но нетривиальным) таким множеством является множество, состоящее из двух элементов, на котором строится алгебра логики. Здесь же вводится понятие булевой функции.

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

Основные разделы дискретной математики

Логика возникла тогда, когда человечество сделало актуальным вопрос, как надо рассуждать, чтобы получить правильные выводы. Активный интерес к логике среди математиков и философов приходится на период расцвета греческой культуры в VI-IV вв. до н.э. Первое большое сочинение, посвященное специально логике – это "Аналитики " Аристотеля, (384 - 322 гг. до н.э. ). Параллельно и независимо возникла буддистская логика. В Европе развитие логики начинается от изучения Аристотеля. В "обычную" логику начинают проникать математические и логические знаки с целью замены слов обычного живого языка. Появилась идея о том, что, записав все исходные допущения на языке специальных знаков, похожих на математические, можно заменять рассуждения вычислением. В последствии правила логических вычислений были переведены на язык вычислительной машины, которая выдает следствия из введенных в нее исходных допущений. Такую "логическую машину" сконструировал еще в средние века Раймунд Луллий (1235-1315). Далее Лейбниц (1646-1716) внес свой вклад в универсальное логическое исчисление в надежде, что в будущем философы вместо того, чтобы бесплодно спорить, будут брать бумагу и вычислять, кто из них прав.

Начало созданию аппарата современной математической логики (логики высказываний) заложил Джордж Буль (1815-1864). Логико-математические языки и теория их смысла были затем значительно развиты в работах Фрече (1848-1925). Применение математической логики в некоторых разделах математики произвел Пеано (1858-1932). В 20-м веке – это работы Рассела и Уайтхеда, изданные в 1910 - 1913 гг. и программа обоснования математики на базе математической логики, предложенная крупнейшим математиком Гильбертом (1862-1943). В принципе с программы Гильберта и начинается современное развитие математической логики. В этот период происходит применением точных математических методов при изучении формальных аксиоматических теорий /7/. Символический язык математической логики оказался очень важным подспорьем в изучении логических основ математики, поскольку он позволял избегать всякой неточности мысли, которая может иметь место при использовании слов обычного языка. Смысл слов живого языка даётся не точным определением, а созданием привычки к принятому словоупотреблению.

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

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

Следующая проблема – это полнота теории. Во многих математических теориях возникают конкретные проблемы, которые не удаётся ни доказать, ни опровергнуть. Иногда это бывает в силу технической сложности самой проблемы, но спустя определённое время, проблему всё же удаётся разрешить. Но возможна и такая ситуация: проблему невозможно ни доказать, ни опровергнуть в рамках исследуемой теории. Математик Гедель доказал теорему о неполноте, которая утверждает, что всякая достаточно богатая теория необходимо содержит утверждения, которые нельзя ни доказать, ни опровергнуть в рамках теории. Но такие теории, как элементарная геометрия, теория векторных пространств оказываются полными. Татарский в 1948 г. построил конкретный алгоритм, позволяющий по всякому утверждению элементарной геометрии выяснить, является ли это утверждение истинным или ложным.

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

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

Если коснуться истории, то математический аппарат, пригодный для описания систем событий, возник первоначально в качестве аппарата символической логики /7/. Создание «алгебры высказываний» связано с именем Дж. Буля (1815— 1864), хотя и у него были предшественники, к которым в первую очередь относятся Лейбниц и братья Бернулли. Появившаяся в 1847 г. работа Буля положила начало исследованиям, результатом которых был расцвет математической логики, составляющий одну из характернейших черт математики двадцатого века. В своей монографии «Исследование законов мышления, на которых основаны математические теории логики и вероятностей» отчетливо указал на связь построенного им исчисления так же с основаниями теории вероятностей. Эта связь основывается на аналогии между «событиями» и «высказываниями», позволяющей обслуживать логику и теорию вероятностей одним формальным аппаратом. Так как «событие» — это то, что может произойти или не произойти; «высказывание» же — это то, что может быть истинно или ложно. Среди событий есть достоверные и невозможные; высказывания могут оказаться тождественно истинными или тождественно ложными. Между событиями возможна причинно-следственная связь: одно событие бывает иногда следствием другого. Точно так же между высказываниями возможна логическая связь; они могут вытекать одно из другого. Каждому событию может быть сопоставлено некоторое высказывание, утверждающее, что это событие произошло. С другой стороны, всегда можно истолковать высказывание как утверждение об осуществлении некоторого события. Сказанное сейчас убеждает в возможности построения единого «исчисления», которое могло бы, смотря по обстоятельствам, служить то «исчислением высказываний», то «исчислением событий». Такое исчисление и было создано Дж. Булем.

В течение полувека оно развивалось в чисто «логическом» русле. Мерное значительное исследование по аксиоматике теории вероятностей появилось лишь в 1917 г.; его автором был С. Н. Бернштейн. Последующие исследования в этой области, связанные в первую очередь с работами А. Н. Колмогорова, окончательно поставили теорию вероятностей на твердую почву и оказали большое влияние на смежные разделы математики, в особенности - на теорию меры.

В 20 и 21 веках в связи с развитием компьютерных технологий алгебраические методы все более активно применяются во всех областях человеческой деятельности, в том числе и технологии строительства и производства строительных машин и материалов. Но применение вычислительной техники в различных сферах человеческой деятельности базируются на вычисления на дискретных структурах. Разработка комплексных интегрированных автоматизированных систем обработки информации и их компонент требует знаний дискретной математики, в которой отсутствует предельный переход и непрерывность, что уже знакомо студенту при изучении классического анализа.

Дискретная математика является одним из основных для дальнейшего изучения и практического решения задач, встречающихся при производстве строительства. Логика применения дискретной математики в данном случае сводится к следующему. Требуется четко и лаконично описать реальную ситуацию, имеющую место при производстве строительства, на обычном языке. Затем сделать перевод понятий обычного языка на язык символики дискретной математики. Для анализа задач строительства нужно после получения решения алгебраической задачи провести обратный перевод – с алгебраического на технический язык.

Для производства решения разрабатываются алгоритмы, учитывающие аппаратурные возможности (емкость памяти) и временной фактор при условии, что сходимость и устойчивость задачи обеспечена. Емкостные и временные проблемы связаны с размерностью задачи и выбором эффективного алгоритма. Решение таких задач возможно на основе теории алгоритмов. Вычисления на ЭВМ производятся на дискретных структурах, где необходима комбинаторная грамотность. Таким образом, сама жизнь требует изучения дискретной математики.

Дискретная математика является одним из разделов математики. Любая математическая теория имеет дело с двумя объектами /5/ с множествами и функциями (соответствиями, отношениями) на этих множествах. Если аргументы функции f пробегают множество M и функция принимает значения, принадлежащие этому же множеству f, то эта функция f называется алгебраической операцией на множестве M. Вот это и есть первые примеры введения абстрактных символов для решения реальных практических задач.

Элементы булевых алгебр будут использоваться при изучении теории вероятностей, функционального анализа, теории меры. Булева алгебра—это алгебраическая система, которая в зависимости от обстоятельств может быть интерпретирована либо как система событий, либо как система высказываний (допуская и иные истолкования). Аксиомы булевой алгебры выражают то общее, что роднит «события» и «высказывания». Причинно-следственная связь событий или логическая связь высказываний описывается формулами, имеющими вид неравенств. Булева алгебра представляет собой разновидность частично упорядоченного множества: неравенство х<у выражает «большую достоверность» события у по сравнению с событием х или «большее правдоподобие» высказывания у сравнительно с х. Среди элементов булевой алгебры должны содержаться наибольший и наименьший, соответствующие «абсолютно достоверному» и «абсолютно невозможному» событиям («тождественно истинному» и «тождественно ложному» высказываниям). Каждый элемент должен иметь дополнение, которое можно истолковывать как «событие, противоположное данному» или как «отрицание данного высказывания».

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

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

Теория графов /2/ может быть использована при решении задач исследования операций, вычислительной математики, теории управления.

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

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

Задачи о деревьях, кратчайших остовах и задача Штейнера позволяют применить их для практических задач: к проектированию электрических и газовых распределительных сетей.

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

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

Рассматривается задача нахождения гамильтонова цикла в неполном графе и ее приложение к машинному планированию, задаче поиска кратчайшего гамильтонова цикла, широко известного под названием «задача коммивояжера», и ее приложениям к выбору транспортных маршрутов.

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

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

Изоморфизм

Наука, изучающая алгебраические операции называется алгеброй. Это понятие по мере изучения курса будет конкретизироваться и углубляться. Алгебру интересует только вопрос, КАК действует та или иная алгебраическая операция f, а не на чем она действует, т.е. M. Для этой цели, т.е. исключения M, вводится такое важное понятие, как изоморфизм, которое позволяет расширить область применения теории алгебраических структур. Поэтому раскроем его содержание.

Отображение µ множества X на множество Y является изоморфизмом (изоморфным отображением), если оно взаимно однозначно и сохраняет порядок, то есть если x ≤ y, то µ(x) ≤ µ(y).

Обратное отображение также является изоморфизмом. Такие отображения, то есть если x ≤ y, то µ(x) ≤ µ(y) называют изотонными.

Взаимно однозначное отображение ω множества X на множество Y называется дуальным изоморфизмом, если x ≤ y следует ω(x) ≥ ω(y). Если такое отображение существует, то X и Y дуально изоморфны.

Алгебры
Множеств	T Объединение	T Пересечение	Дополнение	Симметрическая разность
Высказываний	x y z и и и и л и л и и л л л дизъюнкция	x y z и и и и л и л и и л л л конъюнкция	x z и л л и отрицание	x y z и и и и л и л и и л л л Сложение по модулю 2
Контактов

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

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

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

Упражнения

1. Докажите, что изоморфное отображение всегда изотонно, а обратное утверждение неверно.

2. Запишите на языке множеств свою группу.

3. Запишите на языке множеств предметы, которые изучаете.

4. Выделите элемент в группе, изучаемых предметов.

5. Запишите множество арабских цифр

6. Запишите множество натуральных чисел как объединение множеств четных и нечетных целых чисел.

Контрольные вопросы

1. Что изучает дискретная математика?

2. Какие основные разделы входят в состав дискретной математики?

3. Чем отличается дискретная математика от классической?

4. Как соотносятся между собой классическая и дискретная математика?

5. Укажите основные области применения дискретной математики?

6. Какие функции выполняет дискретная математика при программировании?

7. Где можно применять дискретную математику в строительной технологии?

8. Как можно представить строительный процесс методами дискретной математики?

9. Как можно представить строительную машину методами дискретной математики?

10. Что такое изоморфизм и его функции в дискретной математике?

11. Назовите основные аксиомы теории множеств.

12. Какие основные символы, используемые в теории множеств, вы знаете?

13. Что такое множество? Как его обозначить? Как можно задать множество? Что такое подмножество?

14. Какие основные операции выполняются над множествами?

15. Какое множество можно назвать универсальным?

16. Что такое диаграмма Эйлера-Венна? Проиллюстрируйте с помощью диа­граммы Эйлера-Венна объединение и пересечение трех множеств.

17. Каковы соотношения между множествами и составными высказывани­ями?

18. Сформулируйте и докажите основные тождества алгебры множеств.

19. Что называется кортежем и какие кортежи называются равными?

20. Что такое счетное множество?

21. Дайте определение мощности множества.

22. Чему равна мощность конечного множества?

23. Какие операции можно совершать над множествами.

24. Дайте определение объединения множеств.

Лекция № 2

Математики – это некоторый род французов: если говоришь им что-нибудь, они переводят это на свой язык, и тогда это становится тотчас же чем-то совсем другим.

И.В. Гёте Ferneres uber Mathematik und Mathematikers, s. Werke, Grosse Weimarische Ausg. Abt.II,Bd. 11 (1893),s. 102

ОСНОВЫ ТЕОРИИ МНОЖЕСТВ

Понятие множества — одно из основных, если не основное, понятий матема­тики. Оно не имеет точного определения, и его следует отнести к аксиомати­ческим понятиям. Такими аксиоматическими понятиями, например, в эле­ментарной геометрии являются понятия точка, прямая, плоскость.

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

Интуитивное понятие множества. Основные принципы

Как было сказано выше, понятие множества относится к аксиоматическим понятиям математики, и точное его определение дать невозможно. Часто принимается формулировка интуитивного понятия множества Г. Кантора, основоположника этой теории:

"Произвольная совокупность определенных предметов нашей интуиции или интеллекта, которые можно отличить один от другого и которые представ­ляются как единое целое, называется множеством. Предметы, которые вхо­дят в состав множества, называются его элементами".

Множество и элементы множества

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

Агрегатная точка зрения рассматривает множество как набор вещей (по Кантору), а с атрибутивной точки зрения множеством считается свойство (атрибут) вещи.

Символическая запись этих точек зрения следующая:

(m есть элемент множества М).

m М (m обладает свойством М).

Здесь m, М – исходные неопределяемые (первичные) понятия "элемент" и "множество" а отношение принадлежности (инцидентности) и предикации относятся к первичным (неопределяемым) отношениям.

Фундаментальное понятие «множество», как первичное понятие, не имеет прямого определения, но, тем не менее, оно широко применяется в математике, например, точка, прямая и т.п.. При чем любое понятие дискретной математики можно определить с помощью понятия множества.

Согласно Г.Кантору (одному из основоположников "наивной" теории множеств), множеством (конечным или бесконечным), является неупорядоченная совокупность строго различимых (дискретных) объектов (агрегатов) для каждого из которых можно установить принадлежность его данному множеству.

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

Пример. 1

А. По признаку принадлежности к МГСУ можно сформировать множество M – коллектив МГСУ.

Б. По признаку студент факультета ИСТАС создать множество S - студенты факультета ИСТАС.

В. Совокупности вершин и диагоналей в многоугольнике.

Г. Множество зайцев в лесу Московской области и т.д. и т.п.

Д. Решение квадратного уравнения есть множество, элементами которого являются корни заданного уравнения (алгоритмом установления принадлежности элемента множеству решений является его подстановка в квадратное уравнение).

Е. Все натуральные числа образуют бесконечное множество N: N = {1, 2, 3, 4, 5…….}

Ж. Все точки вещественной оси равномощно множеству всех действительных чисел .

З. Множество, не содержащее элементов, есть пустое множество = {}.

Таким образом, объекты, объединенные по определенному признаку, образуют множество.

Как правило, множество обозначается большой буквой, часто, латинского алфавита (M, S и т.п.), а элементы, составляющие этого множества одноименными прописными буквами (m, s и т.п.).

Определение множества

Объекты, обладающие схожими свойствами (характеристиками) можно объединить в группы.

Множество - это любое объединение или совокупность объектов, объединенных по определенным признакам (характеристикам).

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

Пример. 2. Общепринятые стандартные обозначения наиболее важных множеств:

N - Множество целых положительных (натуральных) чисел - (1, 2, 3, 4, . . . ).

Z - Множество всех целых чисел - (1,2,3,4, . . . ).

Q - Множество рациональных чисел.

R - Множество вещественных чисел.

C - Множество комплексных чисел.

P - Множество простых чисел (2, 5, 7, 11,. . . , . . . ).

E₂ - Множество, состоящее из нуля и единицы (0, 1).

P_n - Множество булевых функций n аргументов.

На протяжении изучения всего курса будем стараться придерживаться этих обозначений.

Замечание:

Элементами множества могут быть множества.

Термин "множество" есть экспликация интуитивно явных понятий "класс", "семейство", "ансамбль", ets.

Термин "элемент" множества есть экспликация интуитивно явных понятий "участие", "член", "представитель".

Не следует связывать понятие множество с обыденным представлением о множестве, как о большом количестве. Так множество {х} есть синглетон, а пустое множество не содержит элементов.

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

- студент, вчера сдавший зачет,

- он же, сегодня защитивший курсовой проект,

- он же, намеревающийся завтра сдать экзамен

образуют множество из трех элементов.

Предостережение:

Можно говорить о множестве снежинок (дождинок) при снегопаде (дожде), но нельзя говорить о множестве снежинок (дождинок) в сугробе (луже), (так как в последнем случае нет дискретности).

Конечные и бесконечные множества

То, из чего состоит множество, т.е. объекты, образующие множество, называется его элементами. Элементы множества различны и отличаются друг от друга.

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

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

Если элемент т принадлежит множеству М, то используется запись включение ,которое указывает, что т является элементом множества М. В противном случае - запись указывает на то, что т не является элементом множества М.

Примеры

Множество степеней 2, заключенных между 1 и 10 – {1, 2, 4, 8}

Множество адресуемых ячеек памяти компьютера.

Множество программ исполнимых компьютером.

Множество тактов работы процессора.

В компьютере все множества реальных объектов конечны.

Задание множества

Чтобы задать множество, нужно указать, какие элементы ему принадлежат. Если для данного элемента условие выполнено, то он принадлежит определяемому множеству, в противном случае - не принадлежит.

Множество может быть задано различными способами:

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

Характеристический предикат. Множество задается указанием свойств элементов Р(х), которые записываются в фигурных скобках { }, т.е при помощи характеристического предиката: М : = {m| Р(х)}. Характеристический предикат — это некоторое условие, выраженное в форме логического утверждения или процедуры, возвращающей логическое значение, и позволяющее проверить, принадлежит ли любой данный элемент множеству. Вообще предикат – это высказывание, содержащее одно или несколько переменных, т.е повествовательное предложение, которое может быть только истинным или ложным.

Порождающая процедура. При задании множества порождающей процедурой множество имеет вид: М: = {х | х: = f}. Порождающая процедура - это процедура, которая в процессе работы порождает некоторые объекты, являющиеся элементами определяемого множества.

Пример.

А. Множество М цифр десятичного алфавита можно задать в виде М = {0, 1,...,9} - перечисление элементов.

Б. М = {i|i - целое, }, где справа от наклонной черты указано свойство элементов этого множества – характеристический предикат.

Множество М четных чисел можно записать в виде М = {т/т - четное число} . характеристический предикат.

В. М := {i|i := 0; for i from 0 to 9 do i := i + 1; yield i end for}, - множество задано порождающей процедурой.

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

Мощность множества

Мощность для конечного множества равна числу его элементов. Например, мощность универсума В(A) множества A мощностью n равна 2ⁿ.

Множества, эквивалентные множеству всех действительных чисел, принадлежащих интервалу [0,1] имеют мощность континуума. Название «континуум» происходит от латинского слова continuum (непрерывное).

Мощность объединения множеств. Число элементов (мощность) конечного подмножества А через |А|, для мощности двух множеств А и В можем записать

|АB| = |А| + |B| - |АB|,

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

|АBC| = |А| + |B| + |C| - |АB| - |АB| - |АC| - |CB| + |АBC|. Для n множеств А₁, ..., А_n мощность равна

|А₁А₂…А_n| = |А₁| + |А₂| + … + |А_n| -

- |А₁А₂| - … - |А₁А_n| - |А₂А₃| - … - |А₂А_n| - … - |А_n-1А_n| +

+ |А₁A₂A₃| + … + |А₁A₂A₃| + … + |А₁A₂A_n| + … + |А_n-2A_n-1A_n| + (-1)^n-1 |А₁A₂A₃…A_n|.

Конечное множество А имеет мощность k, если оно равномощно отрезку 1.. k;:

.

Если множество А конечно, |А| = k, то элементы А всегда можно перенумеровать, то есть поставить в соответствие элементам номера из отрезка 1..k с помощью некоторой процедуры. Наличие такой процедуры подразумевается, когда употребляется запись А = {а₁,...,а_k}.

По определению .

Мощность множества М это число его элементов, обозначается как .Здесь |М| - количество элементов конечного множества М, в дальнейшем называемое мощностью множества

Пример.

Множество натуральных чисел бесконечно, |, поскольку оно равномощно своему собственному подмножеству чётных чисел.

ТЕОРЕМА 1 Любое непустое конечное множество равномощно некоторому отрезку натурального ряда:

|А| = |1...k|.

доказательство

Рассмотрим следующую программу.

i = 0 { счётчик элементов }

wihle do

select { выбираем элемент }

i = i + 1 { увеличиваем счётчик }

{ ставим элементу в соответствие номер }

А: = А - x { и удаляем элемент из множества }

end while

Если эта процедура не заканчивает работу, то она даёт соответствие А ~ N. что невозможно ввиду конечности А. Значит, процедура заканчивает работу при i = k. Но в этом случае построено взаимно-однозначное соответствие А~1..k.

ТЕОРЕМА 2 Любой отрезок натурального ряда конечен:

.

доказательство

От противного. Пусть существуют бесконечные отрезки натурального ряда. Рассмотрим наименьшее п такое, что |1..п| = ∞. Тогда отрезок 1..п, равномощен некоторому своему собственному подмножеству А, |1..п| = |А|, то есть существует взаимно-однозначное соответствие f из отрезка 1..п в подмножество А. I: Обозначим . Рассмотрим соответствие из отрезка 1..n-1 в его собственное множество А - i, задаваемое следующим правилом:

if f(x) < i then f(x) else f(x) -1 end if.

Это соответствие является взаимно однозначным, а значит, отрезок 1..n-1 является бесконечным, что противоречит выбору п.

СЛЕДСТВИЕ Различные отрезки натурального ряда неравномощны:

п≠т=> \1..п\ ≠ |1..т|.

доказательство

Пусть для определённости п > т. Тогда . Если |1..п| = |1..т|, то |1..т| = ∞, что противоречит теореме.

Пример.

Условия равенства (неравенства) множеств

Множества М_а и М_b совпадают (равны),если у них одни и те же элементы. Символически это запишется следующим образом

М_а = М_b М_а М_b и М_b М_а

Если множество М_a - подмножество множества М_b и множество М_b - подмножество множества М_a, то оба этих множества состоят из одних и тех же элементов. Такие множества называются равными: М_а = М_b,.

Подмножество, собственное подмножество

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

Множество М', каждый элемент, которого является элементом другого множества М, называется подмножеством данного множества М. Таким образом, множество М' называется подмножеством множества М тогда и только тогда, когда любой элемент множества М' принадлежит множеству М:

,

где - знак включения подмножества; — «если..., то....», — «если и только если...».

Или это же можно записать в виде импликации

Множества М' и М могут совпадать. Невключение подмножества М' в множество М обозначается так: .

Для выделения подмножества М_а М_b можно использовать какое-либо свойство присущее только элементам из М_а.

Символическая запись А М (здесь - символ отношения включения всех элементов А в М).

Графической интерпретацией этого отношения между множеством может быть диаграмма, или индикатором (характеристической функцией):

xA, xM, A M f: M → {0,1}.

Логическая экспликация понятия подмножества А множества М с агрегатной и атрибутивной точек зрения следующая:

(AM) ~ (х((xA) → (xM))) (1)

(AM) ~ (x((xA) → (xM))) (2)

здесь метасимволы ~ и → следует считать соответственно как "эквивалентность" и "если…то".

Замечание:

1) Говорят что индикатор f_A(х) множества А, определенный на множестве М, задает четкое подмножество А множества М (индикатор множества условно записывают f_A(х): М → {0,1}).

Пусть M = {x₁,x₂,x₃,x₄,x₅}, A = {x₂,x₃,x₅}. Так как A ‹‹не строго содержится ›› в M, то, используя понятия характеристической функции множества A, имеем:

A={‹x₁,0›, ‹x₂,1›, ‹x₃,1›, ‹x₄,0›, ‹x₅,1›}.

В этом выражении множество есть множество кортежей, первой компонентой которых являются элементы множества M, а второй компонентой – принадлежности элемента множества M множеству A.

2) Если степень принадлежности множества M множеству A есть субъективно множественная оценка

то говорят о нечетком подмножестве A множества М (множество М всегда четко!).

3) (AB) ~ ((xU):

Пример:

1) Множество студенток-красавиц ИСТАС, есть нечеткое подмножество A всех студенток ИСТАС M, т.е. A ‹‹не строго содержится в›› M, (очевидно, что понятие "красавица" для каждого человека субъективно и, следовательно, степень его оценки той или иной студентки различна).

2) Пусть M = {0,1,2,3,4,5,6,7,8,9}. Привести подмножество "большие цифры". Возможный вариант:

A={‹0,0›,‹1,0›,‹2,1/1000›,‹3,1/100›,‹4,1/10›,‹5,0.5›,‹6,0.6›,‹7,0.7›,‹8,0.9›,‹9,1›}. Здесь первая компонента каждого кортежа есть цифра множества M, а вторая компонента этих же кортежей есть степень принадлежности цифры к искомому подмножеству.

Кортеж

Определение. Пусть даны множества Х₁ ,Х₂, ...,Х_n кортежем длины п, составленным из элементов этих множеств, называется конечная последовательность α = { х₁ ,х₂, ...,х_n }, где для всех k, 1 ≤ k ≤ п, имеем х_k Х_k

Элемент х_k называется k-й координатой или k -й компонентой кортежа α.

Два кортежа равны в том и только в том случае, когда они имеют одинаковую длину, причем их координаты, стоящие на местах с одинаковыми номерами, равны, т.е. кортежи α = { х₁ ,х₂, ...,х_m } и β = { y₁ ,y₂, ...,y_n } равны только в том случае, когда т = п, причем х_k = у_k для всех 1 < k < п.

Кортежи длины два называют упорядоченными парами, длины три — упорядоченными тройками, длины n — упорядоченными n-ками. Для краткости речи слово «упорядоченные» часто опускают.

Кортеж, не содержащий ни одной координаты, т.е. кортеж длины 0, называется пустым.

Основные отличия понятий кортежа и множества следующие:

а) в множестве порядок элементов не играет роли, а кортежи, отличающиеся порядком элементов, различны, даже в случае, когда они имеют одинаковый состав;

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

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

Пусть А₁, А₂, ..., А_п — некоторые множества. Их декартовым произведением называют множество, состоящее из кортежей вида <а₁, а₂,..., a_n>, где а₁ A₁, а₂ A₂,; а₃ A₃,; ...; а_n A_n,. Декартово произведение обозначается так:А₁ × А₂ × ... × А_п.

Произведение А × А × ... × А ( п раз) сокращенно обозначается как Аⁿ и называется декартовой n-й степенью множества А.

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

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

Условно кортеж записывают в угловых скобках ‹a,b,c›

Примеры:

1. Слово в алфавите A есть кортеж.

2. Команда в программе для ЭВМ есть последовательность символов из алфавита языка программирования.

3. Алфавит русского языка есть алфавит.

4. Программа для ЭВМ есть кортеж команд.

5. Координаты точки в n-мерном пространстве образуют кортеж.

Отметим следующее:

1. В условной записи кортежа элементы, его образующие, называются компонентами (координатами).

2. Число компонент кортежа называется его длиной. Так принято кортеж длиной два ‹a₁,a₂› называть парой (или упорядоченной парой), кортеж длины три ‹x₁,x₂,x₃› - тройкой. В общем случае ‹a₁,a₂› ≠ ‹a₂,a₁›.

3. Кортеж длины n можно интерпретировать как n-мерный вектор, или как точку в n-мерном пространстве, а каждую компоненты кортежа можно рассматривать в этом случае как проекцию вектора на соответствующую ось.