АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. I. МЕХАНИКА И ЭЛЕМЕНТЫ СПЕЦИАЛЬНОЙ ТЕОРИИ ОТНОСИТЕЛЬНОСТИ
  2. I. ПРИМЕНЕНИЕ ГЕОМЕТРИИ
  3. III. Типы экономических систем.
  4. V. Множественные волнообразные линии
  5. V. ЭЛЕМЕНТЫ ФИЗИКИ АТОМА
  6. XII. ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ
  7. А. Понятие и элементы договора возмездного оказания услуг
  8. А. Понятие и элементы комиссии
  9. А. Понятие и элементы простого товарищества
  10. Административный менеджмент в классической теории организации и управления
  11. Актеры и элементы Use Case
  12. Активность личности, психоаналитические теории личности

 

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

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

 
 

 

 


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

 

 

 


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

 

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

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

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

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

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

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

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

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



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

.

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

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

.

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

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

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

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

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

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

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

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

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

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

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

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

.

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

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

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

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

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

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

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

" [ ]

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

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

‡агрузка...

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

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

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

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

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

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

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

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

если то .

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

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

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

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

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

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

.

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

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

, .

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

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

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

 

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

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

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

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

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

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

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

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

 

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

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

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

 

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

 

План лекции:

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

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

 

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

 

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

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

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

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

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

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

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

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

; ; ; ; ; .

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

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

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

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

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

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

;

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

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

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

, где .

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

: , .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 
 

 

 


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

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

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |


При использовании материала, поставите ссылку на Студалл.Орг (0.067 сек.)