2.2. Элементы теории множеств и ее применение в моделировании технических систем.

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

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

Афинная геометрия (а) с параллельным проецированием, проективная геометрия (б) с проецированием от точечного источника

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

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

Отдельные объекты представляют собой элементы множества, которое обозначается парой фигурных скобок { }. Для конкретных множеств с этой целью используются различные прописные буквыили прописные буквы с индексами:,, …. Элементы множества обозначаются различными строчными буквамиили строчными буквами с индексами,…. Используются символы принадлежностии непринадлежности (или) элемента или элементов множеству:

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

• (или) – элементне является элементом множества(элементне принадлежит множеству).

Вместо записи ,, …,с целью сокращения можно использовать запись.

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

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

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

Если количество станков в цехе, то множествотокарных станков запишется в виде:

_.

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

проходной резец},

.

В первом случае ясно, что элементы принадлежат к множеству резцов, а во втором – к множеству решений уравнения, т.е. к множеству.

Если – множество целых чисел, то– множество.

Пустыммножеством () называется множество, не содержащее ни одного элемента.

=, так как уравнение не имеет вещественных решений.

Пустое множество будем условно относить к конечным множествам.

Два множества называют равными, если они состоят из одних и тех же элементов.

Множества ине равны, если либо в множествеесть элементы, не принадлежащие, либо в множествеесть элементы, не принадлежащие.

Символу равенства множеств присущи свойства:

• – рефлексивность;

• если , то– симметричность;

• если и, то– транзитивность.

Из определения равенств множеств вытекает, что порядок элементов в множестве несуществен:

.

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

Множество являетсяподмножествоммножества, если любой элемент множестваявляется элементом множества.

Для определения подмножества используются символы:

– квантор, означает «любой», «каков бы ни был», «для всех».

– символследствия(импликации), означающий «влечет за собой».

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

Для любого утверждение « принадлежит_»влечет за собой утверждение «принадлежит_»запишется в виде:

[]

кратко: обозначает, чтоявляется подмножествомили_, содержащий.

Если содержит и другие элементы, кроме элементов из, то используют символ– строгое включение:. Связь между символами:

– обозначение эквивалентности «то же самое, что».

Свойства подмножеств:

• – рефлексивность

• – транзитивность.

Всегда можно считать, что любое множество содержит в себе в качестве подмножества пустое множество:.

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

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

Согласно теореме о верхней и нижней границах подмножества можно утверждать:

если то.

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

Пусть и– некоторые числа, (+₎– их сумма и ()– их произведение. Сумма и произведение чисел обладают следующими свойствами, называемыми законами алгебры:

1. – коммутативный или переместительный закон;

2. – ассоциативный или сочетательный закон;

3. – дистрибутивный или распределительный закон.

В ассоциативном и коммутативном законах можно заменить действие сложения умножением, а действие умножения сложением. Однако в дистрибутивном законе подобной симметрии нет. Если в этом законе заменить сложение умножением, а умножение сложением, то придем к абсурду:

.

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

Рассмотрим числа и. Это замечательные числа! Прибавление первого и умножение на второе не меняет ни одного числа:

,.

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

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

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

Вопросы для самопроверки.

1. Типы геометрии, используемые при описании технических объектов.

2. Определение множества и примеры описания технических объектов с использованием теории множеств.

3. Назвать правила описания множеств и подмножеств.

4. Основные операции над множествами и геометрическое представление.

5. В чем отличие упорядоченных множеств, их определения?

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

Рекомендуемая литература

1. Аверченков, В.И. Основы математического моделирования технических систем: учеб. пособие / В.И. Аверченков, В.П. Федоров., М.Л. Хейфец – Брянск: Изд-во БГТУ, 2004

2. Коршунов, Ю.М. Математические основы кибернетики: учебн. пособие для вузов / Ю.М. Коршунов. –М.: Энергия, 1987.

3. Кузин, Л.Т. Основы кибернетики: В 2 т. Т.2. Основы кибернетических моделей: учебн. пособие для вузов / Л.Т. Кузин. – М.: «Энергия», 1973.

4. Фёдоров, В.П. Математическое моделирование в машиностроении:

учебное пособие. / В.П.Фёдоров – Брянск: БГТУ, 2013.= 112 С.

Лекция 3.(Окончание раздела 2). «Разработка теоретических моделей исследования качества изделий и технологических процессов». (1 час).

План лекции:

3.1. Графовые модели технических объектов и технологических процессов в машиностроении.

3.2. Моделирование технических систем на основе алгебры логики.

3.1. Графовые модели технических объектов и технологических процессов в машиностроении.

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

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

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

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

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

Математически граф можно определить как пару указанных множестви:

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

Для графа на рис. отображение определено следующим образом:

;;;;;.

Граф называется полным, если для любой его пары вершин исуществует дуга.

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

Граф называется планарным, если он может быть изображен на плоскости так, чтобы его ребра пересекались только в вершинах.

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

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

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

_;

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

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

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

, где_.

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

:,.

Другие важные понятия – путь и контур.

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

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

Если граф содержит точно две вершины нечетной степени, то в Эйлеровом пути эти вершины должны быть конечными. Если вершин нечетной степени нет, то граф имеет замкнутый Эйлеров путь (Эйлеров контур).

Элементарный путь– путь, в котором никакая вершина не встречается дважды (Гамильтонов путь).

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

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

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

Неориентированным графом называют граф без учета ориентации дуг.

Для неориентированного графа понятия дуга, путь и контурзаменяются понятиямиребро, цепь, цикл.Ребро– это отрезок, соединяющий две вершины. Граф на рис. имеет восемь дуг, но семь ребер.Цепьюназывается последовательность ребер,циклом– конечная цепь, у которой начальная и конечная вершины совпадают.

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

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

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

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

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

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

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

Для описания свойств графа на множествах его вершин и дуг (ребер) рассматриваются специфические для графов отношения – смежности и инцидентности.

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

а)

б)

в)

г)

д)

е)

Примеры графов:

а – с петлей; б – симметричный; в– в виде дерева; г – неориентированный;

д – ориентированный; е – в виде сети

Инцидентностьхарактеризует отношение между элементами разноименных множестви. Дуга и вершина инцидентны, если вершина является для дуги концевой вершиной.

Степеньювершины(или) для неориентированного графа называют число ребер, инцидентных вершине.

Если – вершина тупиковая, а если– вершина изолированная.

Доказано, что для неориентированного графа с вершинами иребрами сумма степеней вершин составляет– четное число.

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

Для ориентированных графов свойственны:

полустепень исходавершины– число дуг, исходящих из вершины;

полустепень заходавершины– число дуг, заходящих в вершину.

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

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

Обозначим через вершины графа, а черезего дуги. Введем числа:

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

В случае неориентированного графа элемент матрицы равен числу ребер, соединяющих вершиныи.

Матрица смежности ребер – матрица, строки и столбцы которой соответствуют ребрам графа, а элемент равен числу вершин, инцидентных двум ребрами.

Введем, далее, числа

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

Для неориентированного графа элемент матрицы инциденций равен 1, если вершина инцидентна ребру. В противном случае.

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

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