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

Логика возникла тогда, когда человечество сделало актуальным вопрос, как надо рассуждать, чтобы получить правильные выводы. Активный интерес к логике среди математиков и философов приходится на период расцвета греческой культуры в 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/ может быть использована при решении задач исследования операций, вычислительной математики, теории управления.

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

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

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

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

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

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

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

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