Лекция №1 в россии исторически сложилось так, что представление об образовании включает в себя органичное единство школы как системы приобретения знаний, фундаментальной  icon

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



НазваниеЛекция №1 в россии исторически сложилось так, что представление об образовании включает в себя органичное единство школы как системы приобретения знаний, фундаментальной
Дата17.10.2016
Размер
ТипЛекция

Лекция № 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

и

и

и

и

л

и

л

и

и

л

л

л

дизъюнкция

x

y

z

и

и

и

и

л

и

л

и

и

л

л

л

конъюнкция

x

z

и

л

л

и

отрицание

x

y

z

и

и

и

и

л

и

л

и

и

л

л

л

Сложение по модулю 2

Контактов














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

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

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


^ Принятые обозначения

Символы «порядка не более». При сравнении скорости роста двух функций f(n) и g(n) (с неотрицательными значениями) очень удобны следующие обозначения:

f(n) = О(g(п)) существуют константы С, N > 0, такие, что f(n) С g(п) для всех п N;

f(n) = О(g(п)) <=> существуют константы С, N > 0, такие, что f(n) С g(п) для любого п N.

Конечно, f(n) = о(g(п)) тогда и только тогда, когда g(п) = О(f(n)). Символы О(g(п)) и о(g(п)) читаются соответственно: «порядка не более чем g(п)» и «порядка не менее чем g(п)».

При изучении курса потребуется следующая символика теоретико-множественных операций и отношений: , , \, , , ,, (Л), card M< смысловое содержание которой приведено в таблице.


Метаобозначения

Обозна-чения

Содержание

Пример

ИЛИ

операция дизъюнкции высказываний

Математическая логика PQ

& И

операция конъюнкции высказываний

P&Q

НЕ

операция отрицания высказывания

P



если и только если






если …, то






тогда и только тогда, когда (влечет в обе стороны)

Ма = Мb Ма Мb и Мb Ма



всякий, все, любой All






некоторый






Знак принадлежности элемента множеству (еуфй – гр. есть, быть)

Теория множеств mM



Знак не принадлежности элемента множеству

mM



пересечение





объединение




(Л)

пустое множество

M=

,

знак включения подмножества

;

;




;



не включение подмножества в множество




│M│,

(card M)

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




По мере необходимости будут вводиться другие символы, смысл которых будет объясняться при их введении.
Индивидуальные символы для обозначения правил сопоставления 2x множеств. Индивидуальными (именными) знаками отношений являются символы: , Ï, Ì, Ë, =, ¹, Ì, Ë, <, >, , >которые означают:

- символ принадлежности элемента множеству;

Ï - символ не принадлежности элемента множеству;

Ì (Ë) - символ строгого включения (не включения) подмножества во множество;

= (¹) - символ равносильности (не равносильности) множеств (языковых выражений);

Ì (Ë) - символ нестрогого включения (не включения) одного множества в другое;

<, >, , >; - символ отношений строго меньше, строго больше, меньше и больше.


Частично упорядоченные множества

Множество S называется частично упорядоченным (ЧУМ), если на нем задано рефлексивное, транзитивной и антисимметричное бинарное отношение частичного порядка с.

Частичным упорядочением (частичным порядком) в непустом множестве X называется всякое подмножество множества , удовлетворяющее следующим аксиомам:

I. При любом справедливо - рефлексивность отношений.

II. Если и , то y = x - антисимметричность отношений.

III. Если и , то - транзитивность отношений.

Часто вместо записи пишут x ≤ y или y ≥ x . Иногда вместо знака могут применять и другие похожие символы например . Тогда аксиомы можно записать в виде:

I. при всех справедливо - рефлексивность отношений.

II. Если x ≤ y и y ≤ x, то y = x - антисимметричность отношений.

III. Если x ≤ y и y ≤ z, то x ≤ z - транзитивность отношений.

Эти соотношения называются неравенствами.

Частично упорядоченное множество – это некоторое множество X вместе с заданным на нем частичным порядком P, то есть пара (X, P).


Аксиомы теории множеств

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

1. ^ Аксиома существования. Существует по крайней мере одно множество.

2. Аксиома объемности (экстенциональности). Если множества Ма и Мb составлены из одних и тех же элементов, то они совпадают (равны): Ма = Мb.

3. Аксиома объединения. Для произвольных множеств Ма и Мb существует множество, элементами которого являются все элементы множества Ма и все элементы множества Мb и которое никаких других элементов не содержит.

Утверждение. Из аксиом объемности и объединения следует, что для произвольных множеств Ма и Мb множество, удовлетворяющее условиям аксиомы объединения, единственно.

Доказательство. От противного, если бы существовало два таких множества Мс1 и Мс2 то они содержали бы одни и те же элементы, т.е. все элементы, принадлежащие множеству Ма, и все элементы множества Мb и поэтому, согласно аксиоме объемности, Мс1 = Мс2 = Мс. ЧТД

Назовем это единственное множество Мс объединением множеств Ма и Мb и будем писать Мс = МаМь.

4. Аксиома разности. Для произвольных множеств Ма и Мb существует множество, элементами которого являются те и только те элементы множества Ма, которые не являются элементами множества Мb.

Аналогично, из второй и четвертой аксиом заключаем, что для произвольных множеств Ма и Мb существует в точности одно множество, содержащее элементы множества Ма, не принадлежащие множеству Мb. Назовем это множество Мс разностью множеств Ма и Мb:

Мс = Маb.

5. Аксиома степени. Для каждого множества М существует семейство множеств В(М) (булеан), элементами которого являются все подмножества Мi, МiМ, и только они.

6. Аксиома существования пустого множества. Существует такое множество , что ни один элемент ему не принадлежит.

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

^ А. Пересечение множеств Ма и Мb определяется формулой

МаМb = Ма\(Маb).

Утверждение. Элементами пересечения МаМb являются те, и только те элементы, которые принадлежат как множеству Ма, так и множества Мb.

Б. Дополнение. неМ множества М определяется формулой

неМ = 1\М.

В. Симметрическая разность множеств Ма и Мb определяется формулой

Ма\яМb = (Маb)ba).


Законы теории множеств

На основании введенной аксиоматики можно доказать справедливость как приведенных выше законов, определяющих свойства сигнатуры алгебры множеств (законы идемпотентности, коммутативности, ассоциативности, дистрибутивности, действия с константами, двойного дополнения, законы де-Моргана), так и следующих законов:

- закон дистрибутивности пересечения относительно разности

Ма\(Маc) = МаМbаМc;

- закон коммутативности симметрической разности

Ма\яМb = Мb\яМа;

- закон ассоциативности симметрической разности

Ма\я(Мb\яМc) = а\яМb)\яМc;

- закон дистрибутивности пересечения относительно симметрической разности

Маb\яМc) = МаMba\яМc;


- законы склеивания

МаМbМанеМb = Ма; МаМbМанеМb = Ма;


- законы поглощения

МаМаМb = Ма; МааМb) = Ма;

- законы Порецкого

МанеМаМb = МаМb;

Ма(неМаМb) = МаМb.


Минимизации представления множества

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

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

Пусть в пространстве 1 = {М1, М2, М3} задано множество вида

М(М1, М2, М3) = неМ1неМ2неМ3неМ1неМ2М3неМ1М2 неМ3 М1неМ2неМ3М1М2неМ3М1М2М3 сложность которого равна 18.

На основании законов идемпотентности, коммутативности и ассоциативности объединения получаем

М(М1, М2, М3) = (неМ1неМ2неМ3неМ1неМ2М3) (неМ1неМ2 неМ3М1неМ2неМ3) (неМ1неМ2неМ3М1неМ2неМ3) 1неМ2неМ3М1М2неМ3) 1неМ2неМ3М1М2М3)

Используя законы коммутативности пересечения и склеивания, имеем

.

Сложность представления уменьшилась до 10.

Согласно законам коммутативности объединения _и пересечения и закону склеивания получаем Сложность представления уменьшилась до 7.

Согласно законам коммутативности пересечения и поглощения, имеем Сложность представления заданного множества уменьшилась от 18 до 5.

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

Рассмотрим алгебру и определим множества, которые могут быть порождены (образованы) из произвольных подмножеств М1, М2,...,Мn, называемых порождающими или образующими пространства 1 с помощью операций .

Множество

i = 1,2, …n,

М, * = < , I = 1, 2,...,п,

в дальнейшем будем называть первичным термом.

Множество вида

I = 0,1 назовем конституентой.

Общее число различных конституент не превышает 2n. Каждой конституенте можно сопоставить двоичный набор длины п, число этих наборов равно 2n. Если некоторые конституенты равны , то общее количество конституент меньше 2n, при этом среди подмножеств найдутся хотя бы два такие, которые можно выразить одно через другое, т. е. зависимые. Например, если п = 2 и , то существуют только две отличные от конституенты

. , .

Лемма 1.1. Пересечение двух различных конституент пусто.

Действительно, если конституенты и различны, то по крайней мере для одного k, k n. Но тогда , следовательно. .

Лемма 1.2. Объединение всех конституент равно 1.

Представим 1 в виде



и, раскрыв скобки, в правой части равенства получим объединение всех конституент.


Упражнения

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

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

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

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

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

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



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

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

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

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

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

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

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

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

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

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

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

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







11.02.201417:29:47

11.02.201417:29:47

11.02.201417:29:47

11.02.201417:29:47

11.02.201417:29:47

11.02.201417:29:47
11.02.201417:29:47




Похожие:

Лекция №1 в россии исторически сложилось так, что представление об образовании включает в себя органичное единство школы как системы приобретения знаний, фундаментальной  iconВведение в объектно-ориентированное программирование
Исторически сложилось так, что программирование возникло и развивалось как процедурное программирование, которое предполагает, что...
Лекция №1 в россии исторически сложилось так, что представление об образовании включает в себя органичное единство школы как системы приобретения знаний, фундаментальной  icon-
Так как это первый семинар, лучше, чтобы он проходил медленно. Цель – дать основное представление о том, что такое Альфа курс. Возможно,...
Лекция №1 в россии исторически сложилось так, что представление об образовании включает в себя органичное единство школы как системы приобретения знаний, фундаментальной  iconТабличное представление продукционных знаний
При создании систем базы знаний, главной задачей является представление описываемой модели системы предметной области (спо) в виде...
Лекция №1 в россии исторически сложилось так, что представление об образовании включает в себя органичное единство школы как системы приобретения знаний, фундаментальной  iconИнформатика в вузе
Информатика, преподаваемая во всех вузах России, включает в себя, как минимум, две фундаментальные компоненты: федеральную обязательную...
Лекция №1 в россии исторически сложилось так, что представление об образовании включает в себя органичное единство школы как системы приобретения знаний, фундаментальной  iconА. И. География России. Природа и население. 8 класс, М., «Дрофа», 2011г. Пояснительная записка
Представление о разнообразии России формируется как путем изучения территориальных различий в состоянии и развитии отдельных компонентов...
Лекция №1 в россии исторически сложилось так, что представление об образовании включает в себя органичное единство школы как системы приобретения знаний, фундаментальной  iconНе учите ребенка так, как учили Вас, потому что он родился в другое время
Меняется время – меняются приоритеты. Меняется представление о том, чему и как учить. На смену «традиционному уроку» пришел «урок...
Лекция №1 в россии исторически сложилось так, что представление об образовании включает в себя органичное единство школы как системы приобретения знаний, фундаментальной  iconЗадача по интегрированию культурного потенциала студентов в подготовку гармонично развитых высококвалифицированных специалистов
Еского образования удовлетворить объективную потребность студентов в освоении системы специальных знаний, приобретения двигательных...
Лекция №1 в россии исторически сложилось так, что представление об образовании включает в себя органичное единство школы как системы приобретения знаний, фундаментальной  iconЛекция 1) гис как специализированная информационная система. Структура информационных систем, представление о модели данных. Последовательность действий при создании информационной системы (структурирование предметной области, выбор модели данных, реализация).
Модели данных для пространственной информации. Геокодирование, общее понятие. Геокодирование как процесс перевода пространственной...
Лекция №1 в россии исторически сложилось так, что представление об образовании включает в себя органичное единство школы как системы приобретения знаний, фундаментальной  iconЛекция по теме преступления и злоупотребления в кредитно-финансовой сфере как угроза экономической безопасности
Я. Возникли новые формы элементов хозяйствования, произошло коренное изменение банковской системы, возникли и развиваются новые системы...
Лекция №1 в россии исторически сложилось так, что представление об образовании включает в себя органичное единство школы как системы приобретения знаний, фундаментальной  iconРоссийской Федерации
Финансовая система РФ совокупность всех входящих в финансы РФ звеньев в их взаимосвязи. Она включает в себя следующие системы финансовых...
Разместите ссылку на наш сайт:
Уроки, сочинения


База данных защищена авторским правом ©izlov.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
связаться с нами