Теория систем и системный анализ

Министерство науки и высшего образования Российской Федерации федеральное государственное бюджетное образовательное учреждение высшего образования «Санкт-Петербургский государственный университет промышленных технологий и дизайна» Теория систем и системный анализ Курс лекций для студентов всех форм обучения направления подготовки 09.03.03 - прикладная информатика Профиль -прикладная информатика в дизайне Составитель Г. П. Мещерякова Санкт-Петербург 2020 Утверждено на заседании кафедры .2020 г., протокол № Рецензент Курс лекций по дисциплине «Теория систем и системный анализ» предназначены для студентов всех форм обучения, обучающихся по направлению подготовки 09.03.03 - прикладная информатика, профиль – прикладная информатика в дизайне. Учебное электронное издание сетевого распространения Издано в авторской редакции Системные требования: электронное устройство с программным обеспечением для воспроизведения файлов формата PDF Режим доступа: http://publish.sutd.ru/tp_get_file.php?id=2020 , по паролю. – Загл. с экрана. ФГБОУВО «СПбГУПТД» Юридический и почтовый адрес: 191186, Санкт-Петербург, ул. Большая Морская, 18. http://sutd.ru 2 Введение Общая теория систем (ОТС) – научное направление, связанное с разработкой совокупности философских, методологических, конкретно научных и прикладных проблем: анализа и синтеза сложных систем произвольной природы. ОТС изучает различные явления, отвлекаясь от их конкретной природы, и основывается лишь на формальных взаимосвязях между различными составляющими их факторами и на характере их изменений под влиянием внешних условий. Она тесно связана с понятиями системный подход и системный анализ. Основные требования, которым должна удовлетворять эта теория: 1. Должна быть настолько общей, чтобы могла охватить многие существующие теории, касающиеся теории систем. 2. Должна иметь строго научный характер, термины и определения должны быть математически однозначны. 3. Научные основания должны быть столько фундаментальными, чтобы выводы имели практическую ценность при изучении конкретных систем. Теория систем имеет теоретическую и прикладную части (рис.1.1). Основные задачи общей теории систем: 1. Исследование аналогий в понятиях, законах и моделях в различных областях науки с тем, чтобы переносить из одной дисциплины в другую. 2. Способствовать построению адекватных теоретических моделей для тех областей науки, в которых нет моделей. 3. Содействовать выявлению единства науки путем установления связей между специалистами различных научных направлений. Глава 1. Цели и закономерности целеобразования 1.1 Системный подход и системный анализ Системный подход—это метод исследования, в основе которого лежит рассмотрение объекта как целостного множества элементов в совокупности отношений и связей между ними, то есть рассмотрение объекта как системы. Системный анализ – методология решения проблем, основанная на структуризации систем и количественном сравнении альтернатив. Применение системного анализа при построении ИС дает возможность выделить перечень и указать целесообразную последовательность 3 выполнения взаимосвязанных задач, позволяющих не упустить из рассмотрения важные стороны и связи изучаемого объекта автоматизации. Рис. 1.1. Структура общей теории систем Задачи системного анализа: 1. Декомпозиция. Означает представление системы в виде подсистем, состоящих из более мелких элементов. 2. Анализ. Состоит в нахождении различного рода свойств системы или среды. Целью анализа может быть определение закона преобразования информации, задающего поведение системы. 3. Синтез. Необходимо по описанию закона преобразования построить систему, фактически выполняющую это преобразование по определенному алгоритму, при этом должен быть предварительно определен класс элементов, из которых строится искомая система, реализующая алгоритм функционирования. Cистемный анализ сложных объектов является тем средством, которое обеспечивает возможность решения различных слабоструктурированных и слабоформализуемых проблем. Есть три базовых этапа исследования систем: 1. Определение цели. 2. Структурирование (декомпозиция). Элементы, связи, отношения. 4 3. Постороение математической модели с проверкой адекватности. Разберем базовые этапы по отдельности. 1.2. Закономерности возникновения и формулирования целей и формирования структур Первым этапом исследование системы является определение цели. Целеобразование (целеполагание) – это направление СА, которое занимается исследованием процесса формулирования и анализа целей в системах разного рода. Этот термин был введен применительно к системам, в которых цели не задаются извне, а формируются внутри системы. Процесс целеобразования до конца не изученный и очень сложен. Для эффективного целеобразования, четко сформулировав цель (что следует сделать, чего достичь), необходимо ответить на пять вопросов: - зачем? (т. е. определить значение цели, ее необходимость и что это даст); - как? (т. е. определить способы достижения цели: как работать, какие методы использовать); - какие этапы? (промежуточные цели и этапы их достижения, т. е. деструктуирование (или декомпозиция) цели, которое связано с деструктуированием системы); - какие проблемы? (возможные трудности в достижении цели и пути их предотвращения; - как контролировать? (формы и методы контроля, насколько выполнение деятельности отвечает целям, насколько успешно идет продвижение к цели, критерии достижения цели). 1. Зависимость представления о цели и формулировки цели от стадии изучения объекта (процесса). Цель должна быть реалистичной и направить деятельность на получение определенного полезного результата. При этом формулировка цели и представление о цели могут в процессе работы переформулироваться. При формулировании и пересмотре цели коллектив, формулирующий и выполняющий ее, должен определить, в каком смысле на данном этапе употребляется понятие «цель», в какой точке условной шкалы «идеальное устремление в будущее конечный результат деятельности» ближе принимаемая формулировка цели. Надо вовремя остановится. 2. Зависимость цели от внешних и внутренних факторов. При анализе причин возникновения и формулирования целей нужно учитывать, что на цель влияют как внешние по отношению к системе факторы (внешние потребности, мотивы, программы), так и внутренние факторы (потребности, мотивы, программы самой системы и ее элементов, исполнителей цели). Поэтому задача формулирования обобщающей цели в сложных системах должна быть сведена к задаче структуризации или декомпозиции цели. 5 Закономерности формирования структур целей. Цели могут представляться в виде декомпозиции (т.е. разделение на части) исходной цели во времени - сетевых структур и в виде декомпозиции в пространстве - матричных и иерархических структур как древовидных (типа «дерева»), так и со «слабыми» связями, следовательно декомпозицию удобнее всего представлять методами теории графов и связанных с ней матриц. Проявление в структуре целей закономерности целостности. Применительно к структуре целей это означает, что достижение целей вышележащего уровня не может быть полностью обеспечено достижением подцелей, хотя и зависит от них, и что потребности, мотивы, программы, влияющие на формулирование целей (как внешние, так и внутренние), нужно исследовать на каждом уровне иерархии. Закономерности формирования иерархических структур целей. Учитывая, что наиболее распространенным способом представления целей является иерархическая структура «древовидного» типа («дерево целей»), рассмотрим основные закономерности их формирования. Во-первых, приемы, применяющиеся при формировании древовидных иерархических структур целей, можно свести к двум классам: - формирование структур «сверху» - методы декомпозиции, целевой или целенаправленный подход; - формирование структур целей «снизу» - морфологический, лингвистический, тезаурусный, терминальный подходы или метод «языка системы». На практике обычно эти подходы сочетают. Во-вторых, в иерархической структуре цели нижележащего уровня всегда можно рассматривать как средства для достижения целей вышележащего уровня; при этом они же являются целями для уровня, нижележащего по отношению к ним (свойство «двуликого Януса», наблюдаемое в любых иерархиях). Удобно этим уровням (а иногда и верхнему уровню) присваивать какие-либо отличные друг от друга конкретные названия (направления, задания и др.). В-третьих, в иерархической структуре по мере перехода с верхнего уровня на нижний происходит как бы смещение рассмотренной выше «шкалы» от цели-направления (цели-идеала, мечты) к конкретным целям, которые на нижнем уровне иерархии могут выражаться в виде ожидаемых результатов конкретной работы с указанием критериев оценки ее выполнения, в то время как указание критериев на верхних уровнях иерархии может быть выражено либо в виде общих требований (например, «повысить эффективность»), либо вообще не приводится в формулировке цели. В-четвертых, процесс «развертывания» обобщающей цели в иерархической структуре в принципе может быть бесконечным. Однако на практике для удобства пользования структурой нужно стремиться число уровней ограничивать до пяти - семи. 6 В-пятых, к структурам целей относится все сказанное о структурах систем, и, в частности, одну и ту же цель или подцель можно представить (в силу закономерности целостности) разными иерархическими структурами. В-шестых, для того, чтобы структура целей была удобной для анализа и оценки, к ней рекомендуется предъявлять некоторые общие требования: на каждом уровне иерархии деление должно быть соразмерным («равномерная» структуризация), а выделенные части, по возможности, логически независимыми; основания (признаки) декомпозиции (при структуризации «сверху») или признаки, объединяющие подцели (при формировании структур «снизу»), в пределах одного уровня иерархии должны быть неизменными. Совмещение этих требований не всегда выполнимо - иногда приходится смешивать признаки декомпозиции, чтобы обеспечить равномерность структуры. В-седьмых, при формировании иерархической структуры следует учитывать ограничение возможностей оперативной памяти человека. Обычно исследователи (гипотеза Миллера, число Колмогорова) для того, чтобы человек мог сохранить представление о целостности и успевать анализировать и сравнивать выделенные части, рекомендуют представлять ему одновременно не более, чем 7 ± 2 компонентов. Практически для «деревьев цели» это означает, что следует стремиться к тому, чтобы на каждом уровне иерархи число ветвей, подчиняющихся одному узлу (вершине), не превышало бы семи — девяти. Эта же рекомендация может относиться и к числу уровней иерархии в «дереве». В-восьмых, при формулировании целей и подцелей не всегда удается сразу отразить в формулировке критерии их оценки. Не всегда также одной подцели соответствует один критерий. Поэтому, иногда строят отдельное «дерево критериев», соответствующее «дереву целей». Глава 2. Анализ систем. Модели и моделирование Третьим этапом исследования систем является моделирование. Современным информационным системам (ИС) и информационным технологиям (ИТ) присуща сложность. Она обусловлена, с одной стороны, «неудовлетворительными способами описания поведения больших дискретных систем», а, с другой стороны, слабой структурированностью и «сложностью реальных предметных областей», из которых, в настоящее время, в основном и исходит заказ на разработку. Некоторые методы системного анализа, оказавшиеся весьма эффективными в самых различных областях человеческой деятельности, возведены в ранг государственных стандартов по анализу и проектированию сложных объектов и процессов. Например: система стандартов I-cam Definition в США или SADM – методология структурного системного анализа и проектирования, стандартизованная в Великобритании. Классификация методов моделирования систем 7 Всю совокупность методов моделирования систем можно разбить на три большие группы: методы, основанные на использовании знаний и интуиции специалистов; методы формализованного представления систем управления (методы формального моделирования исследуемых процессов) и комплексные методы. Первая группа – методы, основанные на выявлении и обобщении мнений опытных специалистов-экспертов, использовании их опыта и нетрадиционных подходов к анализу деятельности организации включают: метод «мозговой атаки», метод типа «сценариев», метод экспертных оценок, метод типа «Дельфи», методы типа «дерева целей», «деловой игры», морфологические методы, SWОТ-анализ и ряд других методов. Вторая группа – методы формализованного представления систем управления, основанные на использовании математических, экономикоматематических методов и моделей исследования систем управления. Среди них можно выделить следующие классы: аналитические (включают методы классической математики – интегральное исчисление, дифференциальное исчисление, методы поиска экстремумов функций, вариационное исчисление и другие, методы математического программирования, теории игр); Недостатки. Для сложных систем получить требуемые аналитические зависимости очень трудно. Если это даже удается сделать, то сложно доказать правомерность применения аналитических выражений, т. е. адекватность модели рассматриваемой задаче. Популярные же (в связи с разработанностью теории и знакомством с ними большинства исследователей) схемы дифференциальных уравнений, отражая динамику системы, не отражают возможности восприятия системами входных сигналов и выдачи выходных, что является одной из основных особенностей сложных систем. статистические (включают теоретические разделы математики – математическую статистику, теорию вероятностей – и направления прикладной математики, использующие стохастические представления – теорию массового обслуживания, методы статистических испытаний, методы выдвижения, и проверки статистических гипотез и другие методы статистического имитационного моделирования); Недостатки. Далеко не всегда можно получить статистические закономерности или доказать правомерность их применения. Определение или получение репрезентативной выборки часто требует недопустимо больших затрат времени. Кроме того, анализ и моделирование систем с помощью средств моделирования случайных процессов или теории массового обслуживания приводят, по мере возрастания сложности задач, к значительному увеличению трудоемкости подготовки моделей. Эти обстоятельства снижают эффективность имитационного моделирования. теоретико-множественные, логические, лингвистические, семиотические представления (разделы дискретной математики, 8 составляющие теоретическую основу разработки разного рода языков моделирования, автоматизации проектирования, информационно-поисковых языков); Недостатки. Трудно вводить правила или закономерности, формально используя которые, можно получить новые результаты, адекватные реальным моделируемым объектам и процессам. Смысловыражающие возможности ограничены базисом и функциями алгебры логики и не всегда позволяют адекватно отобразить реальную проблемную ситуацию. Трудно гарантировать правильность получаемых результатов из-за возникающих проблем алгоритмической разрешимости. графические (включают теорию графов и разного рода графические представления информации типа диаграмм, графиков, гистограмм и т.д.). К третьей группе относятся комплексные методы: комбинаторика, ситуационное моделирование, топология, графосемиотика и др. Они сформировались путем интеграции экспертных и формализованных методов. С практической точки зрения методика проведения исследований, как правило, включает три основных раздела: теоретический, методический, организационный. В теоретическом разделе определяются основные цели, задачи, предмет и объект исследования. Методический раздел содержит обоснование выбора метода проведения исследований, сбора и обработки данных, анализ полученных результатов, способы их оформления. Организационный раздел представляет, план проведения исследований, формирование команды исполнителей, распределение трудовых и финансовых ресурсов. Здесь же определяется и организационная форма проведения исследований, т.е. индивидуальные или коллективные исследования, исследования, проводимые внутренними или внешними специалистами. Выделяются специальные отделы, службы управления изменениями, целевые проектные подразделения, которые будут задействованы в проведении исследования систем управления. Сбор данных является первым этапом исследования. Для этих целей используется ряд методов, среди которых наиболее эффективными являются: беседы со специалистами аппарата управления; изучение технико-экономических и статистических сведений о развитии производства рассматриваемого предприятия; изучение опыта развития родственных предприятий. При сборе данных существенной является теория шкалирования 9 Глава 3. Понятие системы. Основные определения. Теоретикомножественный подход 3.1 Определение системы как множества Второй этап исследования системы, выявление структуры, связей и отношений тесно связан с теорией четких и нечетких множеств. Системой может являться любой объект живой и неживой природы, общества, процесс или совокупность процессов, научная теория и т. д., если в них определены элементы, образующие единство (целостность) со своими связями и взаимосвязями между ними, что создает в итоге совокупность свойств, присущих только данной системе и отличающих ее от других систем. Система (от греч. SYSTEMA, означающего «целое, составленное из частей»). Системой называется множество составляющих единство элементов, связей и взаимосвязей между ними и внешней средой, образующее присущую данной системе целостность, качественную определенность и целенаправленность Практически каждый объект может рассматриваться как система. Для систем вводят понятие внешней среды. Внешняя среда все, что не входит в систему. Понятие множества относится к базовым (исходным) понятиям математики. Оно первоначально, его невозможно определить через другие понятия, так как определить - значит указать, какой частью более общих понятий является данное. Под множеством понимают любой набор определенных и различимых между собой объектов, рассматриваемых как единое целое. Это высказывание не является определением, поскольку слово " множество" заменено словом "набор". Близкими к понятию "множество" являются понятия: собрание, совокупность, комплекс, система и т. д. Из определения следует, что объекты, входящие во множество, определенные (т. е. для каждого объекта можно однозначно сказать, принадлежит ли он данному множеству или нет), различимы между собой (во множестве не может быть двух или более одинаковых объектов) и все объекты, входящие во множество, мыслятся как единое целое. Все объекты рассматриваются в совокупности, а от свойств отдельных объектов абстрагируются. Множества обозначают прописными буквами латинского алфавита А, В, С... Объекты, входящие во множество, называют элементами и их обозначают строчными буквами а, в, с ... Множество, состоящее из конечного числа элементов, называется конечным, в противном случае множество называется бесконечным. Множество может быть задано при помощи правила, позволяющего определить, является ли данный объект элементом множества или нет. В 10 записи правило, задающее множество, отделено вертикальной чертой и при записи используют фигурные скобки. Например, пусть множество В есть множество решений уравнения x2 - 5x + 6 = 0, тогда В можно записать так В = {x | x2 - 5x + 6 = 0}. Элементами множества В являются числа 2 и 3, то есть В = {2, 3}. Конечное множество может быть задано перечислением входящих в него и разделенных запятой элементов, например, A = {a1, a2, ... , an}. Множество может содержать лишь один элемент или вообще ни одного. Без элементное множество называется пустым и обозначается символом  . Например, пусть G есть множество точек на плоскости, удовлетворяющих условию x2 + y2 + c = 0 : G = {(x, y)| x2 + y2 + c = 0}. При c < 0 - окружность, при с = 0 - одна точка, а при с > 0 - пустое множество. Принадлежность элемента данному множеству обозначается знаком . Например, а2  A, 3  B, (0.4, 0.61)  D. Если же объект не принадлежит данному множеству, то пишут знак . Например, а0  A, 7  B, (4,7)  D. Множество B называется подмножеством множества A, если каждый элемент B одновременно является элементом множества A. Это записывается так: B  A. Пример. Пусть заданы множества A = {1, 3, 5, 7} и B = {3, 5}. Тогда B есть подмножество A, т. е. B  A. Из определения следует, что множество A есть подмножество самого себя, т.е. A  A. Говорят, что A – самое широкое подмножество A. Пустое множество является самым узким подмножеством любого множества. Множество A и пустое множество  называются несобственными подмножествами множества A. Все другие подмножества A называются собственными подмножествами A. Пример. Если A = {a1,a2,a3}, то оно имеет следующие подмножества:  , {a1}, {a2}, {a3}, {a1,a2}, {a1,a3}, {a2,a3}, {a1,a2,a3}. Всего 8 подмножеств. Если конечное множество A состоит из n элементов, то оно имеет ровно 2n подмножеств. Из них ровно 2n – 2 являются собственными подмножествами. Элементами множества могут также выступать и другие множества. В этом случае говорят не о множестве множеств, а о системе множеств. Частным случаем системы множеств является система всех подмножеств данного множества A и обозначается P(A). Так, система подмножеств множества A из предыдущего примера имеет вид P(A) = {  , {a1}, {a2}, {a3}, {a1,a2}, {a1,a3}, {a2,a3}, {a1,a2,a3}}. Замечание. Не следует путать символы  и  . Символ  употребляется для обозначения отношения элемента к множеству. Символ  употребляется для обозначения отношения множества к множеству. Если все элементы данной системы множеств принадлежат какому-то одному большому множеству, то такое множество называется базовым или универсальным множеством или, просто, универсумом и обозначают буквой U. Примерами универсума являются: числа в арифметике, слова в языкознании, законы в юриспруденции и т. п. 11 Введенные понятия говорят, что структурирование системы означает ее разбиение на подмножества. В частности, разбиение цели на этапы тоже означает разбиение на подмножества. 3.2. Операции над множествами Равенство множеств. Множества A и B считаются равными, если они состоят из одних и тех же элементов. Равенство множеств обозначают так: A = B. Если множества не равны, то пишут A  B. Запись равенства двух множеств "A = B" эквивалентна записи "A  B и B  A". Пример. Доказать, что множество А = {0, 2, 3} равно множеству В корней уравнения x3 - 5x2 + 6x = 0, т. е. В = {x| x3 - 5x2 + 6x = 0}. Для доказательства решим уравнение. Получим: x1 = 0, x2 = 2, x3 = 3. Следовательно, {0, 2, 3}  {x| x3 - 5x2 + 6x = 0} или А  В. Затем непосредственной подстановкой убеждаемся, что любое из чисел 0, 2, 3 удовлетворяет уравнению, следовательно {x| x3 + 3x2 + 6x = 0}  {0, 2, 3} или В  А. Теперь можно записать, что А = В. Если множество В есть подмножество множества А, но при этом они могут быть равны, то пишут B  A . Объединение множеств. Объединением множеств A и B называется такое множество C, каждый элемент которого содержится хотя бы в одном из множеств A или B. Обозначается: A B. Пример. Если A = {1, 2, 3, 4} и B ={1, 3, 5, 7, 9}, то C = A  B = {1, 2, 3, 4, 5, 7, 9}. Можно рассматривать объединение n множеств: n A Ai  A1 A2 An , i 1 при этом в A входят все элементы, которые входят хотя бы в одно из множеств A1, A2, ..., A n. Например, множество всех действительных чисел R состоит из множества положительных чисел R+, множества отрицательных чисел R- и множества {0}, содержащего один элемент – ноль, то есть R  R   R   {0}. Пересечение множеств. Пересечением множеств A и B называется множество D, составленное из общих для множеств A и B элементов. Обозначение: D = A  B. Например: {1, 2, 3, 4}  {1, 3, 5, 7, 9}={1, 3}. Можно рассматривать пересечение n множеств: n A= A i = A1  A2  ...  An, i 1 при этом в A входят только те элементы, которые входят во все множества A1, A2, ..., A n. Классы - это такие подмножества разбиваемого множества, которые не имеют общих элементов, а их объединение образует исходное множество A. Каждый элемент множества A входит в один и только один класс. Говорят, что задано разбиение множества A на классы A1, A2, ..., A m, если выполнены два условия 12 m A= U Ai и Ai  Aj =  для всех i, j, причем i  j . i 1 Разность двух множеств. Разностью двух множеств A и B называется множество J, содержащее лишь те элементы из A, которые не входят в B. Обозначение: J = A\B. Отметим, что в A могут находиться не все элементы из вычитаемого множества B (рис. 1.3). Например, J = {1, 2, 3, 4}\{1, 3, 5, 7, 9}={2, 4}. Если B - подмножество A (B  A), то разность J = A\B называется дополнением к B до A. Например, если A ={1, 2, 3, 4, 5, 6} и B ={2, 4}, то множество {1, 3, 5, 6} - дополнение к B до A. Дополнение к A до универсума U имеет особое обозначение: U\A  A . Пример. Пусть X = {x| x  0}={0}  R+. Такое множество называется множеством неотрицательных чисел. Тогда X = {x| x < 0}=R- , это множество отрицательных чисел. Рис. 3.1. Объединение множеств Рис.3.4. Симметрическая разность Рис. 3.2. Пересечение множеств Рис. 3.5. Дополнение J к В до А Рис. 3.3. Разность множеств J  A \ B Рис. 3.6. Дополнение А до универсума, то есть A Симметрической разностью двух множеств называется множество, включающее все элементы исходных множеств, не принадлежащие одновременно обоим исходным множествам. Другими словами, если есть два множества А и В, их симметрическая разность есть объединение элементов А, не входящих в В, с элементами В, не входящими в А. Обозначение AB . Симметрическую разность можно задать при помощи других операций с множествами AB  ( A  B) \ ( A  B) . Например, А ={1, 2, 3, 4} и В ={1, 3, 5, 7, 9} , тогда AB = {2, 4, 5, 7, 9}. 13 Для наглядного представления соотношений между несколькими подмножествами какого-либо универсума часто используются круги Эйлера или диаграммы Венна. Универсум представляется множеством всех точек некоторого прямоугольника, а его подмножества - соответствующими кругами. Операция объединения и другие операции иллюстрируются кругами Эйлера (диаграммами Венна), представленными на рис. 3.1 - 3.6. Операции над множествами подчиняются определенным законам. Перечислим их: 1) коммутативный или переместительный закон A B = B A; A  B = B  A; 2) ассоциативный или сочетательный закон (A  B)  C = A  (B  C) = A  B  C, (A B) C = A (B C) =A B C. Так как порядок выполнения операций несущественен, то скобки в записи опускают; 3) дистрибутивный или распределительный закон: (A  B) C = (A C)  (B C), (A B)  C = (A  С) (B  C). 4) закон идемпотентности A  A = A, A A = A; 5) закон поглощения A  (A B) = A, A (A  B) = A; 6) закон двойственности де Моргана ( A  B)  A  B и ( A  B)  A  B ; 7) A U = U, A   = ; 8) A A = U, A  A =; 9)  A: A B = A  B =  ,  A: A  B = A  B = U; 10) если A B = U и одновременно A  B =   B = A . 11) U =  ,  =U; 12) A  A . Из законов 1 – 12 следует принцип двойственности: всякое равенство, тождественно выполняемое в теории множеств, переходит также в тождественно выполняющееся равенство при замене знака объединения на знак пересечения , множество универсум U на пустое множество  , и наоборот. 3.3. Прямое произведение множеств. Кортежи Кортежем называют любую выделенную упорядоченную совокупность объектов (элементов кортежа или его компонентов). Синонимами понятия ―кортеж‖ являются: упорядоченное множество, вектор, упорядоченный набор и др. Отличие кортежа от множества заключается в том, что компоненты кортежа упорядочены и могут полностью или частично совпадать. Длиной кортежа называют число компонентов в кортеже. Когда 14 вместо термина ―кортеж‖ употребляется термин ―вектор‖, то говорят соответственно о координатах и размерности вектора. Два кортежа называются равными, если они имеют одинаковую длину и все их соответствующие компоненты совпадают. Компоненты кортежа в силу упорядоченности имеют номер: первый компонент, второй компонент, ... n-й компонент. Примеры кортежей: N = (8, 7, 4, 4, 7). Это кортеж N длины 5, первый компонент которого – 8, второй – 7, третий – 4 и т. д.; M = (a, 2x + 8, {1, 2, 3}, {a, a}), в этом случае (2х + 8) – второй, а {a, a} – четвертый компонент кортежа M. Прямым или Декартовым произведением двух множеств A и B (обозначается A  B) называется множество, состоящее изо всех и только тех пар, первый компонент которых принадлежит A, второй B. Если первый сомножитель имеет n элементов, а второй - m, то их прямое произведение имеет n × m элементов, каждый из которых - упорядоченная пара. Например, если A ={1, 3} и B={1, 4, 5}, то A  B={(1, 1), (1, 4), (1, 5), (3, 1), (3, 4), (3, 5)}. В общем случае, если A = {a1, a2,..., an} и B = {b1, b2,..., bm}, то A  B = {(a1, b1), (a1, b2), ..., (a1, bm), (a2, b1), ..., (an, bm)}.Тем самым прямым произведением n множеств A1, A2, ..., An называется множество всех кортежей длины n , первый компонент которых принадлежит A1, второй A2, ..., n-й – A n, т. е. A1  A2  ...  An = {(ak1 , am2 , , aij , , aln )} , где aij – i-й элемент множества Aj . Если все множества Аi равны между собой, то есть A1 = A2 = ... = An  А, то прямое произведение множеств обозначается как An A1  A2  ...  An = A  A  ...  A = An. Например: пусть R - множество действительных чисел, тогда R  R = R - множество упорядоченных пар вида (x, y), где x, y  R. Геометрически R множество точек числовой оси, тогда R2 – множество точек плоскости, где x и y - координаты этих точек. Множество P называется графиком, если каждый его элемент является упорядоченной парой, следовательно, любое подмножество множества R2 можно назвать графиком. Проекцией кортежа A = (a1, a2, ..., ai ,..., an) на i-ю ось (ПрiA) называется i-й компонент кортежа, т. е. а i  ПрiA. Проекция точки плоскости на первую ось (Пр1R2 = x) называется абсциссой, на вторую ось - ординатой (Пр2R2 = y). Из определения прямого произведения следует, что оно не коммутативно (не перестановочно), т.е. A  В  B  A. Пример. Пусть A - отрезок [1, 3], B - отрезок [2, 5]. Тогда A  B множество точек прямоугольника заштрихованного на рис. 3.7, а, B  A – прямоугольник, заштрихованный на рис. 3.7, б. 2 15 а б Рис. 3.7. Множество: а – A B , б – B A Пример. Пусть A – множество, элементами которого являются буквы, цифры и все знаки операций и препинания. Такое множество называют алфавитом. Тогда An м множество всех «слов» длины n. Пусть нам дан график Р = {(a, b)}. Тогда инверсией графика Р будет называться график Р-1, элементами которого являются упорядоченные пары с обратным порядком компонентов (b, a), т. е. Р-1 = { (b, a) | (a, b)  P}. Композицией графиков P и Q называется график P Q = {(a, c)}, если существует такой элемент b из множества В, что Р = {(a, b)| a  A, b  B} и Q = {(b, c)|b  B, c  C}(рис. 3.8). Рис. 3.8. Композиция графиков Пример. Дан график Р = {(1, 1), (1, 2), (2, 3), (2, 2)}. Найти Р-1, P P , P1 P . Решение. Р-1 = {(1, 1), (2, 1), (3, 2), (2, 2)}, P P = {(1, 1), (1, 2), (2, 3), (2, 2)} {(1, 1), (1, 2), (2, 3), (2, 2)}. Перебираем все возможные пары, имеющие одинаковые элементы второй в впервой паре и первый во второй: пара (1, 1) и (1, 1) дает элемент (1, 1); (1, 1) и (1, 2) - дает элемент (1, 2); (1, 2) и (2, 3) дает (1, 3); (1, 2) и (2, 2) дает (1, 2); (2, 2) и (2, 2) дает (2, 2). Взяв повторяющиеся пары только один раз, получим P P = {(1, 1), (1, 2), (1, 3), (2, 3), (2, 2)}. Аналогично P1 P = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (3, 2), (2, 3)}. 16 3.4. Соответствия (отображения, в теории систем - связи) Определение связи. Связью называется совокупность зависимостей свойств одного элемента от свойств других элементов системы. Типы связей: Односторонние зависимости (ориентированный граф). Двухсторонние зависимости – взаимосвязи (неориентированный граф). Пусть заданы два множества X и Y. Если для каждого элемента x  X указан элемент y  Y, с которым сопоставляется x, то говорят, что между множествами X и Y установлено соответствие (связь, отображение). Иначе говоря, соответствием называется тройка множеств Г = {X, Y, G}, где G  X  Y. Множество X называется областью отправления, Y – областью прибытия, G - графиком соответствия. Если (x, y)  G, то множество первых проекций (Пр1G) называется областью определения соответствия, множество вторых проекций (Пр2G) – областью значений этого соответствия, G – график соответствия. В теории графов соответствия задаются двудольными графами Два соответствия равны, тогда и только тогда, когда равны их области отправления, области прибытия и графики. Пример. Заданы четыре разных соответствия, имеющие одинаковые области отправления и прибытия: (X, Y, G1) = ({a, b, c},{x, y, z},{(a, x),(b, y),(c, z)}), (X, Y, G2) = ({a, b, c},{x, y, z},{(a, x),(a, y),(b, y),(c, z)}), (X, Y, G3) = ({a, b, c},{x, y, z},{(a, x),(b, y),(c ,y)}), (X, Y, G4) = ({a, b, c},{x, y, z},{(b, y),(c, y)}). На рис. 3.9 а - г различия этих соответствий видны достаточно наглядно. В соответствии (X, Y, G) множество всех y  Y, которые сопоставляются элементу x  X, называется образом x в Y. Множество всех x  X, которым сопоставляют элемент y  Y, называется прообразом y в X. Соответствие называется всюду определенным, если его область определения совпадает с областью отправления (в противном случае говорят о частичном соответствии), т.е. множество Пр1G = X. Если же Пр2G = Y, то соответствие называют сюръективным или накрывающим. Это означает, что область значений соответствия совпадает с его областью прибытия. На рис. 3.9, а, б представлено всюду определенное сюръективное соответствие. Соответствия, представленные на рис. 3. 9, в, г не сюръективны, а соответствие изображенное на рис. 3.9, г не всюду определенное. 17 а б в г Рис. 3.9. Примеры различных соответствий Соответствие (X, Y, G) называется функциональным (или однозначным), если образом любого элемента из Пр1G является единственный элемент из Пр2G. График такого соответствия называется функциональным. Это означает, что в нем нет пар с одинаковыми первыми и различными вторыми компонентами. Например, соответствие, представленное на рис. 3.9 б не функционально. Соответствие называется инъективным, если любому элементу из Пр2G соответствует единственный элемент из Пр1G, на рис.3.9 в изображено инъективное соответствие. Соответствие между X и Y называется взаимно-однозначным (или биективным), если оно всюду определено, сюръективно, функционально и инъективно (рис. 3.10 - 3.12). Пусть X и Y – множества вещественных чисел. В этом случае график соответствия G может быть представлен некоторой линией на плоскости. Например. На рис. 3.10 представлено функциональное соответствие, но оно не инъективно (некоторым y соответствует более одного x), не всюду определено (G определен не для всех x), не сюръективно (G проектируется не на все y) и не биективно. На рис. 3.11 представлено не функциональное соответствие, которое не всюду определено, сюръективно и не биективно. На рис. 3.12 представлено взаимно-однозначное соответствие. 18 Рис. 3.10. Функциональное соответствие Рис. 3.11. Не функциональное соответствие Рис. 3. 12. Взаимно- однозначное соответствие Обратная связь в системе Предполагается, что связи существуют между всеми элементами системы и подсистемами. В теории множеств мы констатируем только факт наличия связи и ее графическое представление в виде графа, но на практике это бывает недостаточно. Связи можно классифицировать. Связями первого порядка называются связи, функционально необходимые друг другу. Дополнительные связи называются связями второго порядка. Если они присутствуют, то в значительной степени улучшают действие системы, но не являются функционально необходимыми. Излишние или противоречивые связи называются связями третьего порядка. Иногда связь определяют как ограничение свободы элементов. Действительно, элементы, вступая в связь друг с другом, утрачивают часть своих свойств, которыми они потенциально обладали в свободном состоянии. Существуют несколько классификаций связей. Связи можно охарактеризовать направлением (связи направленные и ненаправленные) силой (сильные и слабые), характером или видом (связи подчинения, связи порождения (генетические), равноправные (безразличные), управления). Для кибернетических моделей систем, в которых связи условно считаются однонаправленными, более адекватным является такое определение. Связь - это способ взаимодействия входов и выходов элементов. В свете такого определения связи делятся на прямые и обратные (рис. 3.11 а). Прямой называется связь между выходом одного элемента и входом другого, обратной — связь между выходом и входом одного и того же объекта. Причем обратная связь может быть осуществлена непосредственно (рис. 3.11, б) или при помощи других элементов системы (рис. 3.11 в) 19 а б в Рис. 3.11. Прямая (а) и обратная связь (б, в) между элементами Различают положительную (усиливающую) и отрицательную (уравновешивающую) обратные связи. Если ограничиться только внешними причинами изменения выхода, то можно остановиться на таких определениях. Обратная связь, уменьшающая влияние входного воздействия на выходную величину, называется отрицательной, а увеличивающая это влияние — положительной. В общем случае положительная (усиливающая) обратная связь усиливает тенденцию изменения выхода системы, а отрицательная (уравновешивающая) — ее уменьшает. Таким образом, отрицательная обратная связь способствует восстановлению равновесия в системе, нарушенного внешним воздействием или некими внутренними причинами, а положительная — усиливает отклонение от равновесного состояния по сравнению с его величиной в системе без такой обратной связи. Обратная связь является основой саморегуляции, развития системы, приспособления ее к меняющимся условиям существования. Весь наш жизненный опыт состоит из циклов обратной связи. Примеры положительной обратной связи: рост живых клеток, накопление знаний, распространение слухов, уверенность в себе, эпидемия, ядерная реакция, паника, рост коралловых рифов. Примеры отрицательной обратной связи: воздушный кондиционер, температура тела, процентное содержание сахара в крови, кровяное давление, выздоровление, езда на велосипеде, хищники и жертвы, спрос и предложение на рынке, регулирование ассортимента. Имеется любопытная разновидность обратной связи — так называемая упреждающая связь. В этом случае будущее оказывает влияние на настоящее. Например, если вы ожидаете провал, то, скорее всего, его и получите. И наоборот, если вы настраиваетесь на успех, ваша энергия и оптимизм помогают вам и повышают ваши шансы. Упреждающая связь создает так называемые самоосуществляющиеся пророчества. Примером является ситуация с ожиданием дефицита. Люди верят в пророчества и поступают в соответствии с ними. Наше будущее строят наши убеждения. 20 Особенность упреждающей связи состоит в том, что усилия, которые направлены на то, чтобы избежать нежелательных событий, как раз к ним и приводят. В качестве примеров можно привести механизм бессонницы или парадокс-пожелание: "Будьте непринужденны!" Уравновешивающая упреждающая связь возникает, когда ожидание изменения подталкивает систему к прогнозируемому состоянию, и прогноз оказывается самоосуществляющимся пророчеством. 3.5. Мощность множества Мощность множества характеризует количество элементов этого множества. Множества равномощны, если между их элементами можно установить взаимно-однозначное соответствие. Число элементов в конечном множестве A называется кардинальным числом и обозначается |A|. Подсчет элементов конечного множества заключается в установлении взаимнооднозначного соответствия между этими элементами и конечной последовательностью натуральных чисел. Множество называется бесконечным, если оно равномощно хотя бы одному из его собственных подмножеств. Бесконечное множество A называется счетным, если оно равномощно множеству всех натуральных чисел N. Примеры счетных множеств: множество целых чисел, четных чисел, рациональных чисел. Счетное множество образуется при объединении счетного множества конечных множеств (например, множество слов в любом конечном алфавите) и т. д. Счетным будет и объединение счетного множества счетных множеств (множество всех векторов с натуральными компонентами). Множество A называется не более чем счетным (дискретным), если оно конечно (в частности – пусто) или счетно. Счетное множество среди бесконечных множеств имеет наименьшую мощность. Рассмотрим все вещественные числа на отрезке [0,1]. Эти числа не могут быть пронумерованы (теорема Кантора), следовательно, их множество не образует счетное множество, оно несчетно. По определению, множество, равномощное множеству всех вещественных чисел единичного отрезка числовой оси, имеет мощность континуума (непрерывное множество). Мощность множества континуума превышает мощность счетного множества. Любой конечный отрезок числовой оси равномощен единичному отрезку. Более того, любой конечный отрезок равномощен и всей числовой оси. Например, между отрезком [-/2, + /2] и множеством (-  , +  ) можно установить такое соответствие: y = tg(x). Множества наибольшей мощности не существует. Это следует из того, что мощность любого множества A всегда строго меньше мощности множества всех его подмножеств W(A). 21 3.6. Отношения (в теории систем - взаимодействия) Отношения – зависимости состояний элементов системы друг от друга, определяющие необходимость и характер взаимодействия между ними. Взаимодействие. Процесс взаимного влияния (воздействия) элементов, системы и окружающей среды друг на друга Взаимосвязи – совокупность двухсторонних зависимостей свойств одного элемента от свойств других элементов системы. Подмножество прямого произведения M = M1  M2  ...  Mn называется n - местным отношением R на множестве M, т. е. R  M. Это означает, что рассматриваются некоторые n – ки элементов из одного и того же множества M и эти элементы находятся между собой в отношении R. Отношение может быть задано на множестве элементов любой природы. Если n = 1 (M = M1), то отношение называется унарным. Установить на M унарное отношение означает приписать некоторым его элементам признак R. По существу, одноместное отношение есть подмножество M. Примеры унарных отношений: "быть целым числом" на множестве вещественных чисел, "быть открытым слогом" на множестве слогов и т. п. Если n = 2 (M = M1  M2), то отношение называется бинарным. Эти отношения обычно записывают как {xRy | x  M1, y  M2 (или x,y  M)} и говорят, что элементы x и y из множества M находятся между собой в отношении R. Например, ―продукт x чаще покупают, чем y". Существуют также тернарные (n = 3), тетрарные (n = 4),..., n-арные отношения. Для задания бинарных отношений на конечных множествах удобно использовать списки пар или таблицы (матрицы). В этом случае, если элементы x и y находятся между собой в отношении R, то в матрице на соответствующем месте пишут 1, в противном случае пишут ноль. Например, отношение "быть больше" на множестве чисел M = {1, 2, 3, 4, 5, 6} (эта сокращенная запись означает, что в М = {1, 2, 3, 4, 5, 6}×{1, 2, 3, 4, 5, 6} и содержит все пары элементов ( xi , xk ) ) можно задать так: 1, если xi  xk и xi , xk  M , сik   0  в противном случае. Таблица этого отношения имеет вид, представленный на рис.3.13. Отношение называется полным, если все элементы множества M находятся в отношении R. Например, отношение "учиться в одной учебной группе" на множестве студентов данной учебной группы является полным, но отношение "быть сыном" не является полным на множестве всех людей. Если М1 = М2 , то это множество можно обозначить просто М и R = M2. Например, множество М – отрезок числовой оси, тогда полное отношение R 22 = M2, заданное на отрезке числовой оси, геометрически соответствует квадрату со стороной M (рис. 3.14). xi 1 2 3 4 5 6 xk 1 2 3 4 5 6 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Рис. 3. 13. Задание отношения «быть больше» на множестве {1, 2, 3, 4, 5, 6} Рис. 3. 14. Полное отношение Отношение называется тождественным, если оно равносильно отношению x = x. Тождественное отношение обычно обозначают буквой E. Таблица такого отношения представляет собой единичную матрицу. Примером тождественного отношения является отношение равенства на множестве вещественных чисел. Так как отношения – это множества, то для них справедливы все теоретико-множественные операции, но существуют операции специфические для отношений. Для отношения R определена операция обращения. Отношение R-1 обратно к R, если R-1 = {(xi xk) | (xk xi)  R}. Переход от R к R-1 осуществляется взаимной перестановкой компонент каждой упорядоченной 23 пары. Пример обратных отношений: "xi старше xk" и "xk старше xi". Композицией двух отношений R и P заданных на множестве M называется отношение Q  R  P такое, что для любых xi, xk  M, существует хотя бы один элемент xj, M такой, что если (xi xj)  R и (xj xk)  P, то (xi xk)  Q. Можно доказать важное свойство композиции: (R  P)-1 =P-1  R-1 . Пример. Найти композицию отношений P и Q заданных таблицами (рис.3.15). R= X1 X2 X3 Y1 1 Y2 1 Y3 Y4 1 1 Y5 1 Y1 Y2 Y3 Y4 Y5 Y6 P= Z1 1 1 1 Z2 1 1 Z3 1 1 1 Z4 1 1 Рис. 3.15. Таблицы отношений Решение. Паре (X1, Y2) из таблицы R соответствуют пары (Y2, Z1) и (Y2, Z3) из таблицы Р. Следовательно, в композицию R  P войдут пары (X1, Z1) и (X1, Z3). Паре (X1, Y5) соответствует пара (Y5, Z1), но пара (X1, Z1) уже есть. X2 образует пары с Y1 и Y4, которые входят в пары с Z1 , Z3 и Z2. Следовательно, X2 образует пары с Z1 , Z2 и Z3 и т. д. Таблица, соответствующая композиции R  P представлена на рис. 3.16. R  P= X1 X2 X3 Z1 1 1 Z2 1 1 Z3 1 1 Z4 Рис. 3.16. Композиция отношений Отношения удобно представить в виде списков пар. Например, для R это пары {(X1, Y2), (X1, Y5), (X2, Y1), (X2, Y4), (X3, Y4)} , соответственно для P это пары {(Y1, Z1), (Y1, Z3), (Y2, Z1), (Y2, Z3), (Y3, Z2), (Y3, Z4), (Y4, Z2), (Y3, Z1), (Y4, Z3), (Y4,Z4)}. Отношения обладают следующими свойствами. Рефлексивность. Отношение R, заданное на множестве M, называется рефлексивным, если для любого x M имеет место xRx. Формально рефлексивность можно задать так: E  R. Рефлексивное отношение всегда выполняется между объектом и им самим. Наиболее яркими примерами рефлексивных отношений являются самообслуживание и равенство. Антирефлексивность. Отношение R, заданное на множестве M, антирефлексивно, если R  E =  . В антирефлексивных отношениях из 24 условия xRу следует, что x  у. Примеры антирефлексивных отношений: быть старше, быть меньше и др. Симметричность. Отношение R, заданное на множестве M, называется симметричным, если при выполнении соотношения xRу одновременно выполняется и соотношение уRx. Формально соотношение симметрично, если R = R-1. Например, отношения "стоять рядом на полке" на множестве книг или " быть родственниками" на множестве людей симметричны. Асимметричность. Отношение R, заданное на множестве M, называется асимметричным, если R  R-1 =  . В асимметричных отношениях из двух соотношений xRу и уRx может выполняться не более одного (одно или не одного). Пример асимметричного отношения: "быть отцом" (если x – отец у, то у не может быть отцом x). Антисимметричность (связность, полнота). Отношение R заданное на множестве M обладает свойством антисимметричности, если R  R-1  E. Это означает, что если для x, уj  M одновременно выполняются соотношения xRу и уRx, то x = у. Антисимметричны все отношения нестрогого порядка: "быть не больше", "быть не выше" и т. п. Транзитивность. Отношение R заданное на множестве M транзитивно, если для любых x, у, z  M из выполнимости соотношений xRу , yRz следует xRz. Формально это можно записать так: R  R  R. Про отношение, не обладающее таким свойством, говорят, что оно не транзитивно. Например, отношение "стоять рядом на полке" не транзитивно. Действительно, пусть тома некоторой энциклопедии стоят в порядке возрастания номеров томов. Тогда, если первый том стоит рядом со вторым, а второй рядом с третьим, то, очевидно, что первый не стоит рядом с третьим. Все общие свойства отношений можно разбить на три группы: рефлексивности (отношение может быть рефлексивно или антирефлексивно), симметричности (отношение симметрично, асимметрично или антисимметрично), транзитивности (отношение транзитивно или не транзитивно). Отношениям, обладающим определенным набором свойств, присвоены специальные названия. Отношение эквивалентности. Отношение R, обладающее свойствами рефлексивности, симметричности и транзитивности называется отношением эквивалентности. Для эквивалентных отношений вместо записи xRу обычно пишут x ~ у (читается: "x эквивалентно у"). Эквивалентными отношениями являются: "быть конгруэнтными" на множестве плоских треугольников, "быть одного размера" на множестве образцов обуви, "быть родственниками" на множестве людей и т. п. Введение отношения эквивалентности R на множестве M определяет разбиение всех элементов этого множества на классы эквивалентности M1, M2,..., Mm. Множество всех классов эквивалентности {M1, M2, ..., Mm} образует фактор множество множества M и обозначается M/R. При этом каждый элемент данного класса является полномочным представителем 25 этого класса. Совокупность по одному и только по одному представителю каждого класса называется системой представителей соответствующего отношения эквивалентности. Примером введения отношения эквивалентности и образования системы представителей может служить формирование представительного органа власти на основе выборов. Отношение толерантности. Отношение  , заданное на множестве M, называется отношением толерантности, если оно рефлексивно, симметрично и не транзитивно. Обозначение: x у | x,у  M. Если потребовать транзитивность всех пар элементов из M, то получим эквивалентное отношение. Следовательно, толерантность может рассматриваться как расширение эквивалентности. Эквивалентность в смысле равенство, толерантность в смысле сходства, похожести. Содержательно толерантность означает следующее: объект находится в данном отношении сам с собой (рефлексивность), сходство двух объектов не зависит от порядка сравнения (симметричность), но если первый объект сходен со вторым, а второй сходен с третьим, то не обязательно, что первый был сходен с третьим. Толерантность позволяет формализовать интуитивные представление о сходстве объектов, их похожести в чем-то. Например, отношение  = "быть на расстоянии не более r", заданное на множестве точек на плоскости. Рис. 3.17 иллюстрирует этот пример. Точка A отстоит от B и C не более чем на r, так же как точка B от D и C, в то время как A находится от D на расстоянии значительно большим, чем r. Рис. 3.17. Толерантность точек на плоскости Отношение порядка. Отношение R, обладающее свойствами рефлексивности, антисимметричности и транзитивности, называется отношением порядка. Если на данном множестве введено отношение порядка, то это множество называется упорядоченным. В этом случае вместо xRу пишут x  у. Множество совершенно упорядочено, если для любых двух элементов x и у из множества M имеет место либо x  у, либо у  x. В противном случае, говорят, что множество частично упорядочено. Например, отношение "быть выше" на множестве деревьев - совершенно 26 упорядочено, а отношение "быть делителем" на множестве целых чисел – частично упорядочено. Пусть каждому элементу x из множества M по некоторому правилу f поставлено в соответствие вещественное число f(x) - вес элемента x. Введение веса для каждого элемента позволяет упорядочить их по мере возрастания (убывания) весов, а затем сравнивать элементы в соответствии с присвоенным весом. Примерами упорядочения посредством введения весов являются: присвоению каждому товару его цены, каждому станку его надежности, каждому телу его веса, объема и т. п. Взвешивание вариантов решений посредством формирования комплексного показателя качества является одним из самых распространенных способов решения проблемы выбора на множестве разнокачественных признаков. Если отношение обладает свойствами антирефлексивности, асимметричности и транзитивности, то оно называется отношением строгого порядка (обозначается x > у). Примером отношения строгого порядка является порядок букв в фиксированном алфавите. Упорядочение букв в алфавите позволяет, в свою очередь, упорядочить слова в словарях (лексикографическое упорядочение слов). 3.7. Нечеткие множества В предыдущих разделах мы рассмотрели теорию обычных множеств, которые называют также четкими множествами. Как уже было сказано, про каждый элемент множества можно однозначно сказать, входит он в данное множество или нет. Условие принадлежности элемента х множеству A можно записать, используя понятие функции принадлежности (х), a именно 1, если х  A  0, если х  A   х   Пример. Кафедра предлагает пять элективных курсов x1, x2, x3, x4 и x5. В соответствии с программой необходимо сдать три курса. Студент выбрал для изучения курсы x2, х3 и x5. Запишем этот факт с помощью функции принадлежности A   x1 | 0 ,  x2 | 1 ,  x3 | 1 ,  x4 | 0  ,  x5 | 1, где первый элемент каждой пары означает название курса, а второй описывает факт принадлежности его к подмножеству, выбранному данным студентом ("да" или "нет"). Между тем, огромный объем человеческих знаний и связей с внешним миром включают такие понятия, которые нельзя назвать множествами в классическом смысле. Их следует скорее считать классами с нечеткими границами, когда переход от принадлежности одному классу к принадлежности другому происходит постепенно, не резко. Тем самым предполагается, что логика человеческого рассуждения основывается не на 27 классической двузначной логике, а на логике с нечеткими значениями истинности, - нечеткими связками и нечеткими правилами вывода. Например: объем статьи примерно 12 страниц, большая часть территории, подавляющее превосходство в игре, группа из нескольких человек. Впервые термин «нечеткое множество» был применен Лотфи Заде в 1965 г. Основная идея состояла в том, что расширить понятие множества можно, если предположить, что функция принадлежности (х) может принимать любое значение на отрезке [0, 1]. Причем крайние значения предписываются в том случае, если элемент безусловно не принадлежит или однозначно принадлежит данному понятию. Подобное расширение понятия множество позволило моделировать рассуждения человека. Теория нечетких множеств используется на практике, когда необходимо принимать решения в условиях неполной и нечеткой информации. В общем случае условие принадлежности элемента х множеству А можно задать в виде совокупности пар: элемента и значения его функции принадлежности A = {(х|(х))}. Пусть х есть элемент конкретного универсального (так называемого базового) множества E. Тогда нечетким (размытым) множеством A, заданным на базовом множестве E, называют множество упорядоченных пар A = {xA((x)}, x  E, где A(х) - функция принадлежности, отображающая множество E в единичный интервал [0, 1], т.е. A(х): E  [0, 1] (Л. А. Заде). Очевидно, что если область значений A(х) ограничить двумя числами 0 и 1, то данное определение будет совпадать с понятием обычного (четкого) множества. Функция принадлежности нечеткого множества может задаваться не только перечислением всех ее значений для каждого элемента базового множества, но и в виде аналитического выражения. Например, множество вещественных чисел Z очень близких к числу 2, может быть задано так: Z = {xZ(x)}, x  R, где Z(x) = e  ( x  2) 2 0.3 . Множество же вещественных чисел Y, достаточно близких к числу 2, можно задать так: Y = {xY(x)}, x  R, Y(x) = 1 . 1  ( x  2) 2 Графическое изображение этих двух функций принадлежности дано на рис. 3.18. 28 Определение. Нечеткое множество A называется нечетким подмножеством B, если и A и B заданы на одном и том же базовом множестве E и x  E: A(x)  B(x), что обозначают как A  B. Условия равенства двух нечетких множеств A и B, заданных на одном и том же базовом множестве E, имеет вид A = B или х  E: A(x) = B(x). Замечание. Между разными по своей сути понятиями "нечеткости" и "вероятности Р" чувствуется некоторое сходство. Во-первых, эти понятия используются в задачах, где встречается неопределенность либо неточность наших знаний или же принципиальная невозможность точных предсказаний результатов решений. Во-вторых, интервалы изменения и вероятности и функции принадлежности совпадают: и P  [0, 1] и A(x)  [0, 1]. Вместе с тем, вероятность является характеристикой объективной и выводы, полученные на основе применения теории вероятностей, в принципе могут быть проверены на опыте. Функция принадлежности определяется субъективно, хотя обычно она отражает реальные соотношения между рассматриваемыми объектами. Об эффективности применения методов, основанных на теории нечетких множеств, обычно судят после получения конкретных результатов. Рис. 3.18. Функции принадлежности нечетких множеств. 1. μх - числа очень близкие к числу 2; 2. μх–- числа достаточно близкие к числу 2 Если в теории вероятностей предполагается, достоверного события равна единице, т. е. n  P  1, i 1 i что вероятность то соответствующая 29 сумма всех значений функции принадлежности n  x  i 1 A i может принимать любые значения от 0 до . Итак, чтобы задать нечеткое множество A необходимо определить базовое множество элементов E и сформировать функцию принадлежности A(х), являющуюся субъективной мерой уверенности, с которой каждый элемент x из E принадлежит данному нечеткому множеству A. 3.8. Операции над нечеткими множествами Дополнение. Пусть нечеткие множества A и B имеют единое базовое множество E. Нечеткое множество B является дополнением нечеткого множества A, (записывается B = A ), если x  E: B(x) = 1 - A(x). Например, если A = {(x10.2), (x20.7), (x31), (x40.4), (x50)}, То A = {(x10.8), (x20.3), (x30), (x40.6), (x51)}. Объединение. Объединением двух нечетких множеств A и B, заданных на одном и том же базовом множестве E. называется нечеткое множество C  A  B , содержащее и A и B, причем функция принадлежности определяется по правилу х  E: C(х) = max(A(х),B(х)). Пример. Пусть A = {(x10.4), (x20.7), (x30.9)} и B = {(x10.5), (x20.3), (x31)}. Тогда C = A  B = {(x10.5), (x20.7), (x31)}. Пересечение. Пересечением двух нечетких множеств A и B, заданных на одном и том же базовом множестве E называется нечеткое множество D  A  B , содержащие и A и B, причем функция принадлежности определяется по правилу x E: D(x) = min(A(x),B(x)). Для нечетких множеств из предыдущего примера имеем D = A  B = {(x10.4), (x20.3), (x30.9)}. Наглядное представление операций объединения и пересечения двух нечетких множеств, заданных на непрерывном подмножестве, дают схемы, родственные диаграммам Вьенна –Эйлера, которые представлены на рис. 3.19. Границы штрихованных областей изображают графики функций принадлежности соответствующих нечетких множеств. 30 Произведение. Произведением двух нечетких множеств A  B, заданных на одном и том же базовом множестве E называется такое нечеткое множество F  A  B , функция принадлежности которого определяется по правилу x  E: F(x) = A(x)∙B(x). Для нечетких множеств из предыдущего примера имеем F = A×B = {(x10.2), (x20.21), (x30.90}. Сумма. Суммой двух нечетких множеств A и B, заданных на одном и том же базовом множестве E называется нечеткое множество H = A + B, содержащие множества A и B, причем функция принадлежности определяется по правилу х  E: H(х) = A(х) + B(х) - A(х)∙B(х). Для нечетких множеств из предыдущего примера имеем H = A + B = {(x10.7), (x20.79), (x31)}. Замечание. Операции умножения и суммирования нечетких множеств употребляются значительно реже, чем операции пересечения и объединения, поскольку для них не выполняются некоторые свойства, в том числе и такое, как дистрибутивность, т. е. свойство х ∙ (y + z) = (x ∙ y) + (x ∙ z). Разность. Разностью двух множеств A и B, заданном на одном и том же базовом множестве E, называется нечеткое множество G = A - B = A  B , функция принадлежности которого определяется по правилу х  E: G(х) = min(A(х), 1 - B(х)). Для нечетких множеств из предыдущего примера имеем G = A - B = {(x10.47), (x20.7), (x30.1)}. 31 а б в г Рис. 3.19. а - нечеткое множество А, б - нечеткое множество В, в - объединение множеств А и В, г - пересечение множеств А и В Возведение в степень. Пусть задано нечеткое множество A, заданное на базовом множестве E. Возведением в неотрицательную степень "" нечеткого множества A называется нечеткое множество K = A, функция принадлежности которого K(х) определяется по правилу K(х) = (A(х)). Возведение нечеткого множества в квадрат называется операцией концентрирования A2  CON(A). Извлечение корня квадратного из нечеткого множества, рассматриваемого как возведение в степень 0.5, называется операцией растяжения A0.5 = DIL(A). Например, если A = {(x10.4), (x20.7), (x30.9)}, то CON(A) = {(x10.16, (x20.49), (x30.81)}, DIL(A) = {(x10.63), (x20.84), (x30.95)}. Нечетким евклидовым расстоянием множествами A и B называется величина d     x     x  xi A i B i 2 между двумя нечеткими xi  E. Ближайшим к данному нечеткому множеству A называется четкое множество A, расположенное на наименьшем евклидовом расстоянии от A. Это множество определяется функцией принадлежности, формируемой по правилу 0,   xi   0.5 xi  E   xi    1,   xi   0.5 Пример. Пусть заданы два множества А и В: A = {(x10), (x20.1), (x30.3), (x40.7), (x50.8), (x60.9), (x71)}; 32 B = {(x10), (x20), (x30), (x40.6), (x50.8), (x61), (x71)}. Тогда d(AB) = 0.346, а ближайшее к нечеткому множеству A является четкое множество A = {(x10), (x20), (x30), (x41), (x51), (x61), (x71)}. В теории нечетких множеств имеет место принцип обобщения, который можно записать следующим образом: f({xA(x)}) = {f(x)A(x)}, где A - нечеткое множество; f - некоторое отображение X  Y. Например, если y = x2 + 3 и A = {(10.4), (20.6), 30.9}, то f(A) = {(40.4), (70.6), (120.9)}. Этот принцип открывает возможности вводить функциональные описания на нечетких множествах. Нечеткие отношения. Пусть P - четкое декартово произведение n множеств E1, E2, ..., En. Нечеткое подмножество четкого множества называется n-арным нечетким отношением Rn на P: Rn  U  x , x , ...., x n  | Rn  x1 , x2 , ...., x n  , E1E2.....En 1 2 где xi  Ei , i  1, n, Rn  0,1. Величина Rn есть мера того, что совокупность (x1, x2, ...,xn) принадлежит отношению Rn. Знак U в данном случае обозначает объединение соответствующих одноточечных множеств (x1, x2, ..., xn). На практике чаще других используется бинарное нечеткое отношение R2, заданное на двух множествах, например, X и Y: R2  U  xi , y j  | R  xi , y j  , где R: X  Y  [x,1]. x y Бинарное отношение может рассматриваться в качестве двухместного предиката. Примеры нечетких отношений: "Расстояние в пространстве значительно больше 1 м" - тернарное отношение на множестве точек трехмерного пространства; "X - дальний родственник Y" - бинарное отношение на множестве людей. Нечеткие бинарные отношения удобно задавать в виде матрицы. Например, R2 - нечеткое отношение "X значительно больше Y", заданное на множествах Ex = (4, 8, 10) и Ey = (2, 3, 4) может быть задано в виде следующей матрицы (рис. 3.20). Это означает следующее: со степенью уверенности лишь 0.7 можно утверждать, что 4 значительно больше 2; но 8 значительно больше 3 со степенью уверенности 0.8. 2 3 4 33 4  0.7 01 . 0   0.8 0.7 R2 = 8  1   10  1 0.9 0.8 Рис. 3.20. Нечеткое бинарное отношение Глава 4. Конструктивные и функциональные свойства систем. 4.1. Свойства систем Как уже было сказано, понятия системы и множества синонимы. Но если система описывает реальные явления, то она имеет ряд особенностей, которые не нужны в теории множеств. Необходимо уметь определять свойства, присущие только данной системе и отличающих ее от других систем. Эти свойства являются модификацией свойств множеств (все объекты, входящие во множество различны, мыслятся как единое целое, рассматриваются в совокупности, от свойств отдельных объектов абстрагируются, внешняя среда все то, что не вошло в множество). Кроме того, надо учесть, что мы ввели понятие связи (соответствия) и взаимосвязи (отношения). Выделяют следующие основные свойства системы: Система есть совокупность элементов и, при определенных условиях, элементы сами могут рассматриваться как системы, т. е. возможна декомпозиция системы на подсистемы (подмножества, классы) с целью упрощения анализа системы. Наличие свойств присущих системе в целом, но не свойственных ни одному из ее элементов в отдельности. Их наличие показывает, что свойства системы, хотя и зависят от свойств элементов, но не определяются ими полностью. Система не сводится к простой совокупности элементов; декомпозируя систему на отдельные части, нельзя познать все свойства системы в целом. Для описание этого свойства вводят понятие эмерджентности - несводимость свойств отдельных элементов и свойств системы в целом. Наличие существенных связей между элементами, которые определяют общие свойства системы. Наличие определенной организации, что проявляется в возможности определить число элементов системы и число существенных связей, которыми может обладать элемент. Целостность – это общесистемное свойство, заключающееся в том, что изменение любого компонента системы оказывает воздействие на все другие ее компоненты и приводит к изменению системы в целом; и наоборот, любое изменение системы отзывается на всех компонентах системы. 34 Коммуникативность. Любая система функционирует в окружении среды, она испытывает на себе воздействия среды и, в свою очередь, оказывает влияние на среду. Системе присуще свойство развиваться, адаптироваться к новым условиям путем создания новых связей, элементов со своими локальными целями и средствами их достижения. Иерархичность. Под иерархией понимается последовательная декомпозиция исходной системы на ряд уровней с установлением отношения подчиненности нижележащих уровней вышележащим. Иерархичность системы состоит в том, что она может быть рассмотрена как элемент системы более высокого порядка, а каждый ее элемент, в свою очередь, является системой. Важным системным свойством является системная инерция, определяющая время, необходимое для перевода системы из одного состояния в другое при заданных параметрах управления. Многофункциональность – способность сложной системы к реализации некоторого множества функций на заданной структуре, которая проявляется в свойствах гибкости, адаптации и живучести. Гибкость – это свойство системы изменять цель функционирования в зависимости от условий функционирования или состояния подсистем. Адаптивность – способность системы изменять свою структуру и выбирать варианты поведения сообразно с новыми целями системы и под воздействием факторов внешней среды. Адаптивная система – такая, в которой происходит непрерывный процесс обучения или самоорганизации. Надежность – это свойство системы реализовывать заданные функции в течение определенного периода времени с заданными параметрами качества. Безопасность – способность системы не наносить недопустимые воздействия техническим объектам, персоналу, окружающей среде при своем функционировании. Уязвимость – способность получать повреждения при воздействии внешних и (или) внутренних факторов. Структурированность – поведение системы обусловлено поведением ее элементов и свойствами ее структуры. Динамичность – это способность функционировать во времени. Наличие обратной связи. . 4.2. Теоретико-множественного описание системы и ее свойств Системы описывают реальный или абстрактные объекты или процессы. Состояние системы – это мгновенная фотография, или срез системы, остановка ее развития. Состояние определяют либо через входные взаимодействия или выходные сигналы (результаты), либо через 35 макропараметры, макросвойства системы. Задание конкретной системы сводится к заданию всех ее состояний С, начиная с зарождения и кончая гибелью или переходом в другую систему. Но реальная система не может находиться в любом состоянии, так как на а ее состояние накладывают ограничения – некоторые внутренние и внешние факторы (например, человек не может жить 1000 лет). Возможные состояния реальной системы образуют подмножество допустимых состояний системы среди множества всех ее состояний. При это у систем есть два важных свойства. Равновесие – способность системы в отсутствие внешних возмущающих воздействий или при постоянных воздействиях сохранять свое состояние сколь угодно долго. Устойчивость – это способность системы возвращаться в состояние равновесия после того, как она была из этого состояния выведена под влиянием внешних или внутренних возмущающих воздействий. Эта способность присуща системам, когда отклонение не превышает некоторого установленного предела. Рассмотрим принципы построения систем, описывающих объекты или процессы. Объект обладает бесконечным набором свойств различной природы. Но на практике, в процессе исследования, работа проводится только с ограниченным множеством свойств объекта, т. е с конечным множеством (дискретным). Это множество определяется границами возможностей их восприятия и важности для цели исследования. Система, описывающая объект, задаѐтся на множестве отобранных свойств S . Процедура задания системы включает ряд операций: определение переменных, параметров и канала наблюдения. Каждое i -ое свойство объекта обозначается переменной Si , i  1,...N , S  {Si } . Множеству наблюдаемых проявлений свойства ставится в соответствие множество значений переменной X i (тоже дискретное конечное множество). Si  {Sij , j  1,..., n}  X i  {X ij , j  1,..., n} где Si — i-ое свойство, Xi — переменная. Процедура наблюдения свойств объекта включает базу наблюдения и канал наблюдения. Под базой наблюдения понимается то, что в самом общем смысле определяет различия свойств. Если не говорить о глобальных вещах, то типовыми базами наблюдения являются время, пространство, группа и их комбинации и т. д. База характеризуется параметрами наблюдения T  {t} . Операцию сопоставления значению параметра t значения переменной Х назовѐм каналом наблюдения. В этом смысле необходимо различать чѐткий и нечѐткий канал наблюдения. Чѐткий канал назначает одному значению параметра соответствует одно значение переменной. В этом случае система задаѐтся на чѐтком множестве значений переменных. В нечѐтном канале наблюдения не существует однозначного решения о том, какое значение 36 переменной соответствует определѐнному значению параметра. Поэтому система задаѐтся в виде нечѐтких множеств состояний переменных. Формально система может быть представлена в виде множества S  {X , T , R, Z } , где X — множество переменных, T — множество параметров, R — отношения на множествах X и T, Z — цель исследований. Рассмотрим подробнее вводимые отношения. На полном множестве состояний X   X i  вводится отношение эквивалентности C1, что позволяет провести разбиение множества на классы эквивалентности: X1,j, X2,p, ..., Xk,c ∈ C1 где Xk,n — значение k-ой переменной. На множестве X вводится также отношение упорядоченности C2 переменных по роли, вкладу и т. д в достижение цели C2 ⊂ X×X Отношение упорядоченности выделяет подмножество упорядоченных пар на множестве кортежей. Вводится отношение упорядоченности переменных на множестве параметров D D ⊂ X×T; и отношение упорядоченности вида C3  C1  C2  D. Э ти виды отношений отражают соответственно структурные (C1,C2), динамические (D) и интегративные свойства системы ( C3 ), которые объединяют структурные и динамические (качество, эффективность, безопасность, живучесть и т.д.). Структурой системы называется устойчивое множество отношений, которое сохраняется длительное время неизменным, по крайней мере в течение интервала наблюдения. Структура системы отражает определенный уровень сложности по составу отношений на множестве переменных и их значений или что эквивалентно, уровень разнообразий проявлений объекта. В системе заданной на множестве переменных X   X i , i  1,.., N , каждая переменная изменяет свое значение в некоторой области значений заданной множеством физически различных значений X i  {X ij ; j  1,..., n} . Зафиксированное значение всех переменных относительно одного значения параметра представляет вектор состояния системы 37 Ci  [ti , X1k1 , X 2k2 , X 3k2 ,..., X NkN ] Множество всех возможных векторов состояний C  {Ci , i  1,.. C } , образует полное множество состояний. Реально состояние системы не равнозначны. Одни более, другие менее предпочтительны, другие запрещены или практически не осуществлены. Неравнозначность состояния задается в виде функции ограничения. В общем случае она представляет собой отображение, определенное на полном множестве состояний: f0 : C  P , где Р — заданное множество. Предположим, что на множестве интервалов наблюдений объекта для функции ограничения справедливо условие:   f 0  1, Ci  C    f 0  0, Ci  C где Ci — вектор состояния системы, C — подмножество полного множества состояний. В этом случае функция ограничения образует замкнутое множество состояний C . Такие системы будем называть замкнутыми или закрытыми. В обратном случае, когда от интервала к интервалу наблюдения состав элементов C меняется, т. е. f0i  f0j , то система будет не замкнутой (разомкнутой, открытой). Замечание. Информационные системы не замкнуты. Деление систем на открытые и закрытые связано с их характерными признаками: возможность сохранения свойств при наличии внешних воздействий. Если система нечувствительна к внешним воздействиям ее можно считать закрытой. В противном случае — открытой. Все реальные системы являются открытыми. Открытая система является частью более общей системы или нескольких систем. Если вычленить из этого образования собственно рассматриваемую систему, то оставшаяся часть — ее среда. Открытая система связана со средой определенными коммуникациями, то есть сетью внешних связей системы. При описании структуры внешние коммуникационные каналы стараются разделить на входные (по которым среда воздействует на систему) и выходные (наоборот). У открытых систем, по крайней мере, один элемент имеет связь с внешней средой, по меньшей мере, один входной полюс и один выходной, которыми она связана с внешней средой. 38 Для каждой системы связи со всеми подчиненными ей подсистемами и между последним, являются внутренними, а все остальные — внешними. Связи между системами и внешней средой также, как и между элементами системы, носят, как правило, направленный характер. Закрытой называется система, которая не взаимодействует со средой или взаимодействует со средой строго определенным образом (как правило это идеализация). В первом случае предполагается, что система не имеет входных полюсов, а во втором, что входные полюса есть, но воздействие среды носит неизменный характер и полностью (заранее) известно. Очевидно, что при последнем предположении указанные воздействия могут быть отнесены собственно к системе, и ее можно рассматривать, как закрытую. Для закрытой системы, любой ее элемент имеет связи только с элементами самой системы. Разумеется, закрытые системы представляют собой некоторую абстракцию реальной ситуации, так как, строго говоря, изолированных систем не существует. Однако, очевидно, что упрощение описания системы, заключаются в отказе от внешних связей, может привести к полезным результатам, упростить исследование системы. Все реальные системы тесно или слабо связаны с внешней средой — открытые. Если временный разрыв или изменение характерных внешних связей не вызывает отклонения в функционировании системы сверх установленных заранее пределов, то система связана с внешней средой слабо. В противном случае — тесно. Очень сложные системы могут быть комбинированными. Комбинированные системы содержат открытые и закрытые подсистемы. Рассмотрим отображение в интервале наблюдения Т множества моментов времени измерений примененных на множестве наблюдаемых состояний C . f0 : C  T , T  C Здесь возможны два случая. В одном отображение однозначно, в другим — многозначно. В случае однозначного отображения, т.е. когда одному значению времени соответствует только одно состояние системы, последняя будет детерминированной. Если отображение многозначно, т.е. одному значению времени допускается два и более состояний, то система будет стохастической. Для детерминированной системы функция ограничения имеет вид: f 0  1 , если при t = ti, C = Ci f 0  0 , если при t = ti, C ≠ Ci У стохастической системы в момент наблюдения t = ti состояние системы C  C является случайным. Ограничение полного множества 39 состояний системы в этом случае задается нечеткими функциями типа вероятности, возможности, правдоподобности и др. В общем случае они представляют отображения вида: f 0 : |С| → [0,1] При выборе функции ограничения исходят из соотношения мощности полного множества состояний |С| и мощности множества моментов наблюдения |Т|. Если |С| ≤ |Т|, то предпочтительной является функция вероятности. В обратном случае |С| ≥ |Т|, предпочтительней функция возможностей. Функция вероятности задается в следующем виде: P  {Pt , t  1,... T } где Pt  Nk  Nk Nk — число наблюдаемых состояний Ck. |Т| = ∑Nk — общее число наблюдений Функция возможности определяется следующим образом: W  {Wk } где Wk  Nk , i C max Ni Из приведенных формул видно, что в первом случае наблюденное число состояний системы Ck нормируется относительно общего числа наблюдения |Т|, во втором относительное числа состояний с наибольшим значением. 4. 3. Основные определения теории графов Рассмотрим принципы представления систем, их иерархию, связи и взаимосвязи при помощи теории графов Первой научной работой посвященной графам считается статья Л. Эйлера, посвященная задаче о кенигсбергских мостах и опубликованная в 1736 году. Четыре части города Кенигсберга (a, b, c, d на рис. 4.3) были соединены семью мостами. Требовалось определить, можно ли, выйдя из любой части города и пройдя по каждому мосту ровно один раз, вернуться в исходное место. Абстрагируясь от всех других обстоятельств можно построить схему или граф, изображенный на рис. 4.4. Вершинами являются части города, а соединяющими линиями (ребрами) – мосты. Надо было ответить на вопрос: можно ли выходя из любой вершины пройти по всем 40 ребрам и вернуться в исходную вершину? Эйлер доказал, что задача не имеет решения. Неориентированным графом G называется упорядоченная пара множеств G = (X, E), где X - непустое множество вершин Х = {x1, x2, ..., xn}, n  N , а элементами множества E является подмножество всех возможных неупорядоченных пар элементов множества X, т. е. E  {αk = (xi, xj)| xi, xj  Х}. Эти неупорядоченные пары называются ребрами, мы будем их обозначать αk, порядок нумерации k не важен. Например, G = ({x1, x2, x3, x4}, {α1 = (x1, x1), α2 = (x1,x2), α3 = (x1,x3), α4 = (x2,x3), α5 = (x3,x4)}). . Рис. 4.3. Задача о кенигсбергских мостах Рис. 4.4. Граф этой задачи Несложные графы удобно изображать в виде графических схем, где вершины - точки, а ребра - соединяющие их линии. В этих схемах длина линий, их толщина и форма, а также взаиморасположение вершин не имеют никакого значения. Нумеровать вершины графа можно произвольным образом. Рис. 4.5. Петля Рис. 4.6. Мультиграф Если допустимы пары с одинаковыми элементами (xi,xi), то говорят, что в вершине xi имеется петля (рис. 4.5). Если вершины хi и хj принадлежат некоторому ребру (хi,хj), то говорят, что это ребро инцидентно вершинам хi и хj, которые в свою очередь называются смежными. Петля инцидентна одной вершине. Вершина, не инцидентная никакому ребру, называется изолированной. Граф, состоящий из одних изолированных вершин, называется нуль – графом. Граф, не содержащий изолированных вершин, 41 называется связным. Если в графе есть вершины соединенные двумя или большим числом ребер, то такой граф называют мультиграфом (рис. 4.6). Граф, не содержащий петель и кратных ребер, называется простым графом. В дальнейшем, как правило, мы будем рассматривать именно простые графы. Граф, содержащий все возможные ребра, называется полным и обозначается Kn. В полном графе каждая пара вершин соединена одним и только одним ребром. На рис. 4.7 приведен полный граф K5. Рис. 4.7. Полный граф K5 Число ребер полного графа равно n(n  1) , так как из каждой вершины 2 выходит n-1 ребро, всего n(n-1) ребер, но каждое ребро считается два раза. а б в Рис. 4.8. Граф -а, частичный граф -б и подграф -в Граф Gb(Xb, Eb) называется частичным графом (суграфом) графа G(X, E), если он содержит все вершины исходного графа и лишь часть ребер исходного графа, т. е. Xb = X и Eb  E. Подграфом Ga(Xa, Ea) графа G(X, E) называется граф, в который входит подмножество вершин исходного графа (Xа  X) и все ребра, соединяющие вершины Xа этого графа (Eа  E). На рис. 4.8 представлены частичный граф (суграф) и подграф для данного исходного графа G(X, E). Полный подграф называется кликой. В клике убраны все лишние ребра, соединяющие две вершины. Число ребер инцидентных данной вершине называется степенью (кратностью) данной вершины и обозначается Q(xi). В графе изображенном на рис.4.6 вершина х2 имеет степень 6 (Q(x2) = 6), так как ей инцидентны ребра 1, 2, 4, 5, 6, 7, а вершина х1 имеет степень 3 (Q(x1) = 3). Вершина х6 имеет степень 1. 42 Вершина xi называется висячей, если Q(xi) = 1, если Q(xi) = 0 – это изолированная вершина. Если Q(xi) нечетное число, то и вершина называется нечетной, если четное – то четной. Степень каждой вершины полного графа Kn равна Q(xi) = n - 1. Теорема Эйлера о сумме степеней вершин графа. Если у графа n вершин и k ребер, то сумма степеней всех вершин графа равна удвоенному числу его ребер: n  Q ( x )  2k . i 1 i 1 2 Это следует из того, что k   Q( x1 )  Q( x2 )  Q( x3 )  ...  Q( xn )  . Следствие 1. Число нечетных вершин любого графа четно. Следствие 2. Сумма степеней вершин любого графа четна. Теорема 1. В простом связном графе, имеющем n вершин ( n  2 существуют вершины одинаковой степени. Доказательство. Для степени любой вершины справедливо неравенство 0  Q( xi )  n 1 , т.е. Q( xi ) {0,1,..., n 1} . Если все вершины имеют разную степень, то должна существовать и вершина с нулевой степенью, т. е. граф теряет связность. Теорема 2. Если в графе, имеющем n вершин ( n  3 ), существуют ровно две вершины с одинаковой степенью, то существует или ровно одна вершина степени 0, или ровно одна вершина степени n - 1. Граф, у которого степени всех вершин одинаковы Q(xi) = r , называется однородным графом степени r . Полный граф с n вершинами является однородным графом степени r = n – 1 (рис. 4.7). Нуль – граф является однородным графом степени 0. Граф G{X , E} называется двудольным, если все множество его вершин разделено на два непересекающихся подмножества X  X1  X 2 и X1  X 2   , X1  {x1 ...xk } и X 2  { y1 ... ym } , k  m  n , причем ребра соединяют только вершины этих двух подмножеств E  {( xi , y j ) | xi  X 1 , y j  X 2 } . Если в множество Е входя все пары ( xi , y j ) , то граф называется полным двудольным графом, если не все, то граф называется неполным (рис. 4.9, а, б). Двудольный граф описывает соответствия. Ориентированным графом (или орграфом) D называется пара D = (X, A), где X произвольное множество вершин и A - множество упорядоченных пар вершин, называемых дугами A  X  X . В упорядоченной паре (хi, хj) первая вершина хi называется началом дуги, а вторая хj - концом дуги. На рисунках дуги изображаются стрелками (рис. 4.10). 43 . а б Рис. 4.9. Двудольные графы: а - полный граф и б – неполный Рис. 4.10. Ориентированный граф Чтобы лучше понять отличие ориентированного графа от неориентированного, можно привести следующую аналогию: если ориентированный граф описывает систему улиц города с односторонним движением, то неориентированный граф - с двусторонним. Ребро неориентированного графа, соединяющее две вершины, эквивалентно двум разнонаправленным дугам, соединяющим эти же вершины. Таким образом, неориентированный граф можно рассматривать как частный случай ориентированного графа. Петля, по определению, считается неориентированной. Рис. 4.11. Граф, описывающий отношение порядка При помощи ориентированного графа удобно задавать бинарные отношения. Например, отношения порядка. Говорят, что на ориентированном графе G(X,E) задано отношение порядка, если для любых двух вершин хi и хj, удовлетворяющих условию хi  xj, существует путь из хi в хj (рисуется стрелка из хi в хj). На рис. 4.11 представлено изображение графа, на котором 44 определено отношение порядка "хi не больше хj". Для отношения порядка характерны три свойства: рефлексивность, антисимметричность и транзитивность. С позиций теории графов эти свойства можно интерпретировать так. Рефлексивность означает истинность условия хi  хi. Следовательно, вершина хi не больше самой себя, т. е. имеется путь из хi в хi, что обусловливает допустимость петли для вершины хi. Антисимметричность (xi  хj)  (хj  xi)  (хi  хj) показывает, что если на графе имеется путь из хi в хj, то имеется и путь из хj в хi. Таким образом, в графе имеется контур. Транзитивность отношения "быть не больше" означает истинность выражения (хi хj)  (хj  хk)  (хi  xk). Транзитивность эквивалентна тому, что вершины xi, хj, хk последовательно встречаются на одном и том же пути. Отношение строгого порядка антирефлексивно и асимметрично, поэтому его можно задать на графе без петель и без контуров. Операции над графами Для графов определены следующие операции. Удаление (стирание) ребра α. G(X, Е) – α,   E дает граф G1(X,Е1), где E1  E   (рис. 4.12). При этой операции получим суграф (частичный граф). Рис. 4.12. Удаление ребра Удаление вершины xi. Вместе с вершиной xi удаляются и все инцидентные ей ребра. G(X, Е) – xi, xi  X дает граф G1(X1,Е), где X1  X  xi (рис. 4.13). Результат удаления нескольких вершин не зависит от порядка их удаления. При этой операции получим подграф. 45 Рис. 4.13. Удалена вершина x2 Добавление ребра. Если вершины xi и xj графа G(X, Е) не соединены ребром, то его можно добавить   ( xi , x j ) . G1(X, Е1), где E1  E   . Результат добавления нескольких ребер не зависит от порядка их добавления. Объединение графов. G  ( X , E)  G1 ( X1, E1 )  G2 ( X 2 , E2 ) , X  X1  X 2 , E  E1  E2 . Объединение называется дизъюнктным, если X1  X 2   (рис. 4.14). Рис. 4.14. Объединение графов Произведение графов G  ( X , E)  G1 ( X1 , E1 )  G2 ( X 2 , E2 ) . Множество Х определяется как прямое произведение X  X1  X 2 , т. е. это множество пар, при этом первый элемент из Х1 , а второй из Х2 {( x, y) | x  X1, y  X 2} . Каждая такая пара будет вершиной в Х. Новые вершины соединяются ребром, т.е. будут смежны, если или совпадают первые элементы, а вторые были смежны в исходных графах или вторые совпадают, а первые были смежны в исходных графах. Пример. На рис. 4.15 построены графы Х1 и Х2. Прямое произведение X  X1  X 2 дает пары X  {( x1 , y1 ),( x1 , y2 ),( x1 , y3 ),( x2 , y1 ),( x2 , y2 ),( x2 , y3 )} . Каждая пара является вершиной графа Х. В первых трех парах совпадают элементы x1 во вторых трех – x2 . Но вершины у2 и у3 не являются смежными, следовательно ребра между ( x1 , y2 ) и ( x1 , y3 ) не будет. Аналогично не будет ребра между ( x2 , y2 ) и ( x2 , y3 ) . 46 а б Рис. 4.15. Произведение графов: а – исходные графы, б – граф произведения Слияние (отождествление) вершин. Пусть xi , x j две вершины графа G  ( X , E ) , xi , x j  X . Граф G1  ( X1 , E1 ) получается отождествлением вершин xi и x j графа G, если из графа G удаляются вершины xi и x j и вместо них вводится новая вершина yl , не принадлежавшая ранее графу G, yl  G , то тогда она соединяется ребром с каждой из вершин, входящих в объединение окружений вершин xi и x j (рис. 4.16) Рис. 4.16. Слияние вершин x4 и x 6 Раздвоение (расщепление) вершины. Пусть xi одна из вершин графа G. Разобьем окружающие ее вершины на два множества N1 и N2 и удалим вершину вместе со всеми инцидентными ей ребрами. Добавим новые вершины xk и xm и соединяющее их ребро ( xk , xm ) . Далее, вершину xk соединим с каждой вершиной из множества N1, а xm с каждой вершиной множества N2. Получим новый граф G1 (рис. 4.17). Операция не однозначна, может быть несколько вариантов расщепления вершины. Рис. 4.17. Раздвоение вершины x6 47 Рис. 4.18. Соединение графов. Такое соединение называется «колесо» Соединение графов, не имеющих общих вершин. Объединяем вершины и добавляем ребра, соединяющие каждую вершину первого графа с каждой вершиной второго (множество Е3). G( X , E)  G1 ( X1 , E1 )  G2 ( X 2 , E2 ) , X1  X 2   , X  X1  X 2 , E3  {( xi , y j ) | xi  X1, y j  X 2} , E  E1  E2  E3 (рис. 4.18). Дополнение графа G до полного. Если графы G и G имею одни и те же вершины, а вместе ребра графов составляю полный граф, то граф G называется дополнением графа G до полного графа G1 . Если дан полный граф G1 , то удалив ребра, принадлежащие графу G , получим граф G1 . Плоские (планарные) графы Два граф называются изоморфными, если между множествами их вершин установлено взаимно однозначное соответствие и соответствующие вершины, соединенные ребрами в одном из графов, соединены и в другом графе. У изоморфных графов одинаковое число вершин и ребер, но не все графы с одинаковым числом вершин и ребер являются изоморфными. Рис. 4.19. Пара изоморфных планарных графов Следующий алгоритм позволяет установить изоморфность графов G1 и G2 с одинаковым числом вершин. Для каждого элемента x из G1 находим y из G2 с тем же числом исходов и заходов (для орграфов) или числом ребер (для не ориентированных) и соединяем эти вершины ребром, т. 48 е. строим граф соответствия. Потом выписываем подстановку, переводящую граф G1 в G2 (если соответствие установлено для всех вершин). При замене графа на изоморфный все свойства графа сохраняются. Граф может иметь несколько изоморфных с одинаковыми свойствами. Граф называется планарным (плоским), если существует изоморфный ему граф, который может быть изображен на плоскости без пересечения ребер. На рис. 3.17 представлена пара изоморфных графов G1 и G2. В первом из них ребра пересекаются, но поскольку в изоморфном ему графе ребра не пересекаются, то оба они являются планарными. Задача поиска изоморфного планарного графа важна в электротехнике при необходимости избежать пересечений проводников. Всякий подграф планарного графа тоже планарен. Граф планарен тогда и только тогда когда каждая связная компонента графа есть планарный граф. Гранью в планарном графе называют часть плоскости, ограниченной ребрами и не содержащая внутри себя вершин и ребер. По определению, внешняя часть плоскости вне планарного графа также образует грань, которая называется внешней или бесконечной гранью (рис. 4.19). Граф на рис. 4.19 имеет четыре грани: Г2, Г3, Г4 – внутренние грани, Г1 – внешняя. Рис. 4.20. Грани планарного графа Теорема Эйлера. Пусть m - число вершин, n – число ребер и k – число граней планарного графа. Тогда справедливо равенство m + k – n = 2. Эта теорема справедлива и для выпуклых многогранников. В теории графов важное место занимает задача окраски вершин, ребер и граней плоского графа. Например, какое минимальное количество красок нужно для создания политической карты, при этом соседние страны должны быть раскрашены в разные цвета. Доказательство пяти красок было проведено давно. Теорема о четырѐх красках была доказана только в 1976 году Кеннетом Аппелем и Вольфгангом Хакеном из Иллинойского университета. Это была первая крупная математическая теорема, доказанная с помощью 49 компьютера. Авторы использовали специальную компьютерную программу, чтобы доказать это свойство для каждой из рассмотренных ими 1936 карт. После этого Аппель и Хакен пришли к выводу, что не существует наименьшего контрпримера к теореме, потому что иначе он должен бы содержать какую-нибудь из этих 1936 карт, чего нет. Изначально доказательство было принято не всеми математиками, поскольку его невозможно проверить вручную. В дальнейшем оно получило более широкое признание, хотя у некоторых долгое время оставались сомнения. Чтобы развеять оставшиеся сомнения, в 1997 году Робертсон, Сандерс, Сеймур и Томас опубликовали более простое доказательство, использующее аналогичные идеи, но по-прежнему проделанное с помощью компьютера. Кроме того, в 2005 году доказательство было проделано Джорджсом Гонтиром с использованием специализированного программного обеспечения Способы задания графов Существуют следующие способы: Аналитический. В этом случае задается множество вершин Х = {x1, x2, ..., xn} и отображение Е, переводящее множество вершин само в себя E : X  X . Тогда каждому элементу множества Х xi  X ставится в соответствие подмножество множества Х, которому соответствует отображение E : Ex  X . Так задаются ребра или дуги графа. Можно также задать граф, если определено множество его вершин Х, а множество ребер (дуг) есть подмножество множества E  X  X . Геометрический (графический). Вершины графа изображаются кружками и каждую вершину xi  X соединяют линиями с теми вершинами x j  X , для которых выполнено условие x j  Ex . Матричный. В подавляющем большинстве случаев граф задается матрицей. Матрицей смежности графа называется матрица, в которой номера строк и столбцов совпадают с номерами вершин графа, а ее элемент cij есть число ребер, соединяющих вершины xi и хj. Матрица всегда квадратная и симметричная. По главной диагонали стоит количество петель. Для графа, изображенного на рис. 4.21, матрица смежности имеет вид i i 0  2 1 C  0 0  0 50 2 1 0 0 0  0 4 0 0 0 4 0 0 0 1  0 0 01 0 0 01 0 0  0 1 0 0 0  Рис. 4.21. Мультиграф и его матрица смежности На диагонали матрицы смежности стоят петли. Нумеровать вершины можно произвольным образом. Графы, отличающиеся только нумерацией вершин, но сохраняющие отношения между ними, будут изоморфны. В этой связи говорят, что матрица определяет графы с точностью до изоморфизма. В подавляющем большинстве приложений изоморфные графы не различаются и решения задач на изоморфных графах по существу совпадают. Ориентированные графы удобно задавать с помощью матриц инциденций. Номера строк матрицы инциденций равны номерам вершин, а номера столбцов - номерам дуг. Если дуга αj выходит из вершины хi , то соответствующий элемент матрицы инциденций сij равен -1. Если же дуга j входит в вершину хi, то элемент cij равен +1. Если дуга не инцидентна вершине, то сij = 0. Петля по определению не ориентирована, ее обозначаем просто 1. Для ориентированного графа, изображенного на рис.3.20, матрица инциденций имеет вид  1 1 0 0 0     1 0 1 0 1 C   0 1 0 0 0     0 0 1 1 0   0 0 0 1 1   Рис. 4.22. Орграф и его матрица инциденций Для неориентированного графа тоже можно построить матрицу инциденций. В этом случае если ребро αj инцидентно вершине хi , то сij = 1, а если не инцидентно, то сij = 0. Теорема. Графы изоморфны тогда и только тогда, когда их матрицы смежности (инциденций) получаются друг из друга одновременными перестановками строк и столбцов, т. е. при перестановке i–й и j–й строчек одновременно меняются местами и i–й и j–й столбцы. Матрицы часто используются для задания графов в памяти компьютеров. Маршруты на графах Пусть дан неориентированный граф G(X, E). Маршрутом длины m называется некоторая последовательность m ребер графа G(X, E) такая, что вершины двух соседних ребер последовательности совпадают, т. е любые два 51 соседних элемента инцидентны. Если х1 = хк, то маршрут называется замкнутым, если нет, то открытым. Примерами маршрутов на графе, изображенном на рис. 4.21, могут служить следующие последовательности ребер (1, 6, 5, 1, 3) и (2, 1, 4, 3). Первый из них проходит последовательно через вершины х1, х2, х3, х2, х1, х3, соединяя х1 с х3. Второй, проходя через вершины х2, х1, х2, х3, х2, образует замкнутый маршрут, так как приводит в ту же вершину, из которой и начался. Маршрут можно задать как перечислением вершин, так и перечислением ребер. Длина маршрута – это количество ребер в нем (с учетом повторений). Две вершины графа называются связанными, если существует маршрут, соединяющий эти вершины. Граф, любая пара вершин которого связана, называют связным графом. Если существует хотя бы пара несвязных вершин, то граф называется не связным. Представленный на рис. 4.21 не является связным, поскольку, например, отсутствует маршрут из х1 в х4 . Мостом называют ребро, удаление которого увеличивает на единицу число компонент связности графа, т. е. вершины xi и xj перестают быть связными. На рис. 3.20 мостом является ребро α1. Если граф G несвязный граф, то его дополнение G до полного графа будет связным графом (в дополнение входят все ребра полного графа не вошедшие в исходный граф). Орграф называется сильно связанным, если для любых двух его вершин xi и xj найдется путь с вершиной в xi и концом в xj. При установлении простой связности ориентацию дуг в расчет не принимают, при установлении сильной связности это необходимо. На рис. 4.23, а граф сильно связан, на рис. 4.23,б просто связан. а б Рис. 4.23. Сильно связный (а) и просто связный граф (б) Маршрут, все ребра которого различны, называется цепью. Цепь, проходящая через различные вершины, называется простой (элементарной) цепью. Замкнутая цепь называется циклом, а цикл, проходящий через различные вершины - простым циклом, простой цикл с n вершинами обозначается Сn. Так, в графе изображенном на рис.4.21, маршрут (1, 5, 8) является простой цепью, маршрут (2, 5, 6, 1) – циклом С4. 52 В орграфах ориентированная простая цепь называется путем. Путь Р с n вершинами обозначается Рn. Ориентированный простой цикл называется контуром. Граф, имеющий контур, называется контурным графом. Из определений следует, что число ребер графа Рn равно n -1, а число ребер графа Cn равно n. Каждый путь (цикл) содержи в качестве подграфа простой путь. Граф без циклов называется ациклическим. Вершины xi и xj орграфа называются взаимно достижимыми, если существует путь из xi и xj и путь из xj в xi . Расстоянием d(xi, xj) между вершинами xi и xj называется длина (т. е. число ребер) кратчайшего пути между вершинами. Если такого пути не существует, то по определению расстояние равно бесконечности. d ( xi , x j )   . Матрица расстояний D неориентированного графа есть квадратная симметричная матрица элементы которой dij есть расстояния между вершинами xi и xj. .Для мультиграфа, изображенного на рис. 4.21, матрица расстояний равна 0 1 1   2  1 0 1   2 1 1 0   1 D  0 1   1 0   2 2 1   0          Для орграфа G{X, E}графом достижимости называется граф G*{X, E*}, имеющий то же множество вершин, что и граф G, а множество ребер E* состоит из таких пар xi и xj, у которых вершина xj достижима из xi. Матрица достижимости А графа G есть квадратная матрица, элементы которой aij равны 1 ( aij  1 , i, j номера вершин), если соответствующее расстояние есть конечное число d ( xi , x j )   и равны нулю в противном случае, т. е. aij  0 если d ( xi , x j )   . Матрица достижимости для неориентированного графа является симметричной матрицей, причем главная диагональ состоит из единиц aii  1 . Пример. Для орграфа (рис. 4.24) матрицей достижимости будет матрица 1 1 0 0    01 0 0   A 1 1 1 1     0 0 0 1 Рис. 4.24. Граф и его матрица достижимости 53 Для практики большое значение имеют задачи о нахождении различного рода маршрутов. Наиболее известные из них два: эйлеров цикл и гамильтонов цикл. Цикл, содержащий все ребра графа G{X, E} по одному разу, называется эйлеровым, а граф, имеющий эйлеров цикл, называется эйлеровым графом. Если эйлеров граф – плоский, то его можно изобразить одним росчерком пера (не отрывая пера от бумаги), причем начальная и конечная вершины совпадут. На рис. 4.25 изображен граф, обход всех ребер которого ровно один раз возможен по маршруту: 1,  2,  3,  4,  5,  6,  7. Вопрос о существовании эйлерова графа разрешается следующей теоремой: конечный неориентированный граф эйлеров тогда и только тогда, когда он связан и степени всех его вершин четны. Так граф, изображенный на рис 4.26 эйлеров, т. к. степени его вершин х1, х2 и х4 – 2, вершин х3 и х5 – 4. Рис. 4.26. Эйлеров граф Существует алгоритм Флери построения эйлерова цикла в эйлеровом графе. Выбираем произвольную вершину xi и двигаемся по смежным ребрам графа, соблюдая следующие два правила: стирать ребра по мере их прохождения вместе с изолированными вершинами, которые при этом образуются; двигаться по мосту только при отсутствии других вариантов. Простой цикл, который проходит через все вершины графа по одному разу, называется гамильтоновым (У. Гамильтон, 1805 – 1865). Пример гамильтонова цикла приведен на рис. 4.27. 54 Рис. 4.27. Гамильтонов цикл Условий, гарантирующих существование в графе гамильтонова цикла, не установлено. Это обстоятельство существенно усложняет решение практических задач, решение которых сводится к нахождению гамильтонова цикла. Приступая к решению задачи, в общем случае неизвестно, имеет ли она вообще решение или нет. Тем не менее, есть несколько утверждений, справедливых для гамильтоновых графов. Всякий полный граф с числом вершин больше двух ( n  3 ) является гамильтоновым. Это следует из того, что он содержит простой цикл, проходящий через все вершины. Теорема Дирака. Если для графа с числом вершин больше двух ( n  3 ) степень любой вершины d отвечает условию d  n , то граф является 2 гамильтоновым. Наиболее известным примером использования гамильтоновых графов является так называемая задача коммивояжера или задача о странствующем торговце, состоящая в следующем: пусть имеется несколько связанных между собой пунктов (городов). Выходя из фиксированного пункта, коммивояжер должен вернуться в него, посетив все пункты ровно один раз, Обычно задача усложняется введением дополнительного ограничения: например, пройти маршрут за самое короткое время или с минимальными затратами на транспорт. Задача коммивояжера есть задача отыскания в полном орграфе гамильтонова контура минимальной длины (каждая дуга графа имеет положительную длину). В простом случае задача решается методом перебора. Пример. Торговец живет в городе А1 и должен посетить города А2, А3, А4 и вернуться в А1. Расстояния между городами А1А2 = 120 км, А1А3 = 140 км, А1А4 = 180 км, А2А3 = 70 км, А2А4 = 100 км, А3А4 = 110 км (рис. 4.28). 55 Рис. 4.28. Задача коммивояжера Существуют шесть вариантов перемещений: А1А2А3А4А1 –120 + 70 +110 +180 = 480 км А1А2А4А3А1 –120 +100 + 110 +140 = 470 км А1А3А2А4А1 –140 + 70 + 100 +180 = 490 км А1А3А4А2А1 – 140 + 110 +100 +120 = 470км А1А4А2А3А1 – 180 +100 + 70 +140 = 490 км А1А4А3А2А1 – 180 + 110 + 70 + 120 = 480 км Путь А4А1 самый длинный, его не надо использовать. Путь А1А2А4А3А1 = А1А3А4А2А1– длина пути 470 км, является оптимальным. Деревья. Связный граф, не имеющий циклов, называется деревом, а ребра дерева называются ветвями. У дерева с n вершинами есть ровно (n - 1) ветка (ребро) (рис. 4.29, а). Действительно, если добавить лишь одно ребро, соединяющее две вершины дерева, то в графе появится цикл, проходящий через это ребро (рис. 4.29, б). Если же убрать хотя бы одно ребро, то граф станет несвязным (рис. 4.29, в). Таким образом, для связи n вершин необходимо и достаточно ровно n - 1 ребер. Как следует из определения, дерево не имеет кратных ребер и для каждой пары вершин дерева существует единственная соединяющая их цепь. Каждое ребро – это мост. Дерево называют покрывающим, если оно связывает все вершины графа, но может не включать все его ребра. Для графа рис. 4.29, б, граф 4.29, а является покрывающим деревом. Любой связный граф имеет минимум одно покрывающее дерево. 4.29 a 56 4.29 б 4.29 в Рис. 3.27. Иллюстрации к определению дерева Теорема Кэли. Число деревьев на n ( n  2 ) вершинах равно nn2 . При доказательстве теоремы используется схема кодирования деревьев на n вершинах называемая кодом Прюффера. Сопоставим каждому дереву на вершинах {1, 2, 3, n} последовательность {1 , 2 , 3 ,  n2 } , i  N по следующему алгоритму: выберем висячую вершину с минимальным номером и уничтожим ее, взяв в качестве 1 номер соседней с ней вершины, и повторим операцию до тех пор, пока не останутся ровно две вершины, соединенные ребром. Например, для дерева на рис. 4.30 начнем с вершины x3 , 1  2 , вершины x4 и x5 дают также  2  3  2 , после этого, вершины x6 и x7 дают  4  1  1 . Последовательность Прюффера имеет вид {2, 2, 2, 1, 1}. По последовательности Прюффера дерево {1 ,  2 , 3 ,  n2 } , i  N , 1  n восстанавливается по следующему алгоритму: найдем среди чисел {1, 2, 3, n} наименьшее число k , не встречающееся среди чисел  i , соединим ребром вершины в номерами 1 и k , уничтожим число k в списке {1, 2, 3, n} и 1 в списке {1 ,  2 , 3 ,  n2 } . Повторяем действия до тех пор, пока от списка {1, 2, 3, n} не останутся два числа, а все элементы последовательности {1 ,  2 , 3 ,  n2 } буду уничтожены. Соединим соответствующие вершины ребром. Например, последовательность {2, 2, 2, 1, 1}, n  5  2  7 (т. е вершины графа с номерами{1, 2, 3, 4, 5, 6, 8, 7}), генерирует дерево рис. 4.30 следующим образом: в последовательности {2, 2, 2, 1, 1} k  3 , 1  2 , первое ребро (2, 3); в оставшейся последовательности {2, 2, 1, 1} k  4 ,  2  2 , ребро (2, 4); остается {2, 1, 1} k  5 , 3  2 , ребро(2, 5); остается {1, 1} k  2 ,  4  1 , ребро (1, 2); остается {1} k  6 , 5  1 , ребро (1, 6). В списке вершин {1, 2, 3, 4, 5, 8, 7}остались вершины{1, 7}, которые соединяем ребром. Рис. 4.30. Код Прюффера 57 Несвязный граф без циклов называется лесом. При этом любая связная часть леса является деревом (рис. 4.31). Лес, состоящий из k связных компонент и имеющий n вершин, содержит n  k ребер. Могут рассматриваться и деревья с ориентированными ребрами. Ориентированное дерево (граф) G( X , E ) называется прадеревом с корнем y, если выполнены три условия: в нем есть вершина y, в которую не входят ребра. Эта вершина называется корень; в каждую из остальных вершин, которые называются узлами, входит только одно ребро; существует путь между вершиной y и любой другой его вершиной ( рис. 4.32). Y Рис. 4.31. Лес Рис. 4.32. Прадерево с корнем Y С ориентированными деревьями связана специфическая терминология, взятая из ботаники и области семейных отношений. Ботанический вариант: корень – единственная вершина, в которую не входят ребра; листья – вершины, из которых не выходят ребра; путь из корня в лист называется ветвью; высота дерева – максимальная из длин его ветвей, глубина вершины – длина пути из корня в эту вершину; вершины одного уровня образуют ярус дерева. Семейный вариант: если из вершины W есть дуга в вершину W, то V – это отец W, а W – сын V. Если из вершины V есть путь в вершину W, то V называется предком, а W потомком. Вершины, имеющие общего отца, называются братьями или сестрами. Из определения следует, что у каждой вершины, кроме корня, есть единственный отец. Существуют задачи, где ребрам (дугам) приписывается определенное число. Граф G = (X,Е) называется взвешенным графом или сетью S = (G,C), если каждому ребру (дуге) графа при помощи функции С поставлено в соответствие неотрицательное вещественное число с(хi, хj). В зависимости от решаемой задачи, значения функции С называют по-разному: весом дуги, 58 пропускной способностью, длиной дуги и т. п. Сеть иногда называют взвешенным графом, а сумму весов всех дуг - весом графа. Есть стандартный задачи, в которых используются взвешанные графы. Глава 5. Системы в организации. Типы структур систем Существует ряд типовых структур (графов) систем, использующихся при описании организационно-экономических, производственных и технических объектов и имеющих свои названия. Линейная (последовательная) структура (рис. 8) характеризуется тем, что каждая вершина связана с двумя соседними (степень любой вершины равна 2). При выходе из строя хотя бы одного элемента (связи) структура разрушается. Примером такой структуры является конвейер (линейный граф, рис. 5.1.) Рис. 5.1. Линейный граф. Кольцевая структура (гамильтонов и эйлеров цикл, степень любой вершины равна 2) (рис. 5.2) отличается замкнутостью, любые два элемента обладают двумя направлениями связи. Это повышает скорость общения, делает структуру более живучей. Рис. 5.2. Кольцевая структура Сотовая структура (связный граф, эйлеров цикл, рис. 5.3) характеризуется наличием резервных связей, что повышает надежность (живучесть) функционирования структуры, но приводит к повышению ее стоимости. 59 Рис. 5.3. Сотовая структура Многосвязная структура (рис. 5.4) имеет структуру полного графа. Надежность функционирования максимальная, эффективность функционирования высокая за счет наличия кратчайших путей, стоимость — максимальная. Рис. 5.4. Многосвязная структура. Звездная структура (дерево, рис. 5.5) имеет центральный узел, который выполняет роль центра, все остальные элементы системы являются подчиненными. Рис. 5.3. Звездная структура Графовая структура (рис. 5.4) используется обычно при описании производственно-технологических систем и алгоритмов. 60 Рис. 5.4. Графовая структура Сетевая структура (сеть) — разновидность графовой структуры, представляющая собой декомпозицию системы во времени. Например, сетевая структура может отображать порядок действия технической системы (телефонная сеть, электрическая сеть и т. п.), этапы деятельности человека (при производстве продукции — сетевой график, при проектировании — сетевая модель, при планировании — сетевая модель, сетевой план и т. д.). Иерархическая структура получила наиболее широкое распространение при проектировании систем управления, чем выше уровень иерархии, тем меньшим числом связей обладают его элементы. Все элементы кроме верхнего и нижнего уровней обладают как командными, так и подчиненными функциями управления. Иерархические структуры представляют собой декомпозицию системы в пространстве. Все вершины (узлы) и связи (дуги, ребра) существуют в этих структурах одновременно (не разнесены во времени). Иерархические структуры, в которых каждый элемент нижележащего уровня подчинен одному узлу (одной вершине) вышестоящего (и это справедливо для всех уровней иерархии), называют древовидными структурами (структурами типа "дерева"; структурами, на которых выполняются отношения древесного порядка, иерархическими структурами с сильными связями) (рис 5.5, а). Структуры, в которых элемент нижележащего уровня может быть подчинен двум и более узлам (вершинам) вышестоящего уровня, называют иерархическими структурами со слабыми связями (рис 5.5, б). а б 61 Рис. 5.5. Иерархические структуры В виде иерархических структур представляются конструкции сложных технических изделий и комплексов, структуры классификаторов и словарей, структуры целей и функций, производственные структуры, организационные структуры предприятий. В общем случае термин иерархия шире, он означает соподчиненность, порядок подчинения низших по должности и чину лиц высшим, возник как наименование "служебной лестницы" в религии, широко применяется для характеристики взаимоотношений в аппарате управления государством, армией и т.д., затем концепция иерархии была распространена на любой согласованный по подчиненности порядок объектов. Таким образом, в иерархических структурах важно лишь выделение уровней соподчиненности, а между уровнями и компонентами в пределах уровня могут быть любые взаимоотношения. В соответствии с этим существуют структуры, использующие иерархический принцип, но имеющие специфические особенности, и их целесообразно выделить особо. 6. Измерения и шкалы Любое исследование или проект начинаются со сбора информации. Проводятся измерения или анкетирование экспертов или просто участников опроса. Что общее в этих измерениях и как их вообще можно соотнести друг с другом. Одним из важнейших этапов является определение для каждого из случая той шкалы, по которой будут измеряться полученные от респондентов данные. Это важно, прежде всего, потому, что, как будет показано далее, различным типам шкал отвечают различные методы обработки данных. Рассмотрим понятие шкалы, как одного из основных понятий теории измерений. Эта теория основана на понятиях теории множеств. Формальное определение шкалы выглядит следующим образом. Пусть заданы два множества X и Y. где X – множество реальных объектов, Y - множество символов (числовых или нечисловых). Мы говорили, что если для каждого элемента x  X указан элемент y  Y, с которым сопоставляется x, то между множествами X и Y установлено соответствие (связь). Шкалой называют кортеж: {X, φ, Y}, где φ – отображение (соответствие) из множества X в множество Y. Т. е. Х -область отправления, Y – область прибытия и φ – график соответствия. Визуализация делается при помощи теории графов. Таким образом, шкала задает отображение (соответствие), ставящее в соответствие реальному объекту тот или иной числовой или нечисловой символ. 62 В зависимости от того, является ли множество символов Y числовым или нечисловым, будем подразделять шкалы на количественные (числовые) и качественные (нечисловые). Процедура (совокупность операций), осуществляющая отображение φ, то есть ставящая в соответствие реальному объекту из множества X определенный элемент из множества Y, носит название измерение. В случае числовых шкал измерение состоит в определении того, как соотносится одна (измеряемая) величина с другой однородной величиной, принимаемой за эталон (за единицу измерения). Именно так происходит измерение веса, длины, возраста, стоимости и других подобных числовых показателей. Метод измерений при этом обычно обусловлен устройством средств измерений. В случае нечисловых шкал для обозначения той же процедуры измерения зачастую используется понятие оценивание или оценка, причем последнее может также обозначать и сам результат процедуры (например, оценка качества товара, оценка знаний студента на экзамене, оценка степени удовлетворенности населения теми или иными социальными услугами и т.п.) Здесь оценивание – процедура ставящая в соответствие объектам из множества X определенный элемент из нечислового множества Y. Например, в случае оценок на экзамене каждому ответу студента сопоставляется элемент из множества Y = {«отлично», «хорошо», «удовлетворительно», «неудовлетворительно»} (можно вспомнить нечеткие множества и функцию принадлежности). Вместе с тем, нетрудно видеть, что принципиальной разницы в самой сути процедуры, определяющей отображение φ, нет. Поэтому вполне оправданным является употреблять выражение «измерение качества» наряду с выражением «оценивание качества». Все возможные значения, которые могут принимать результаты измерения (то есть все элементы множества Y) называют пунктами шкалы. Продолжим классификацию шкал. Шкалы измерений принято классифицировать по: типам допустимых для данной шкалы математических преобразований (операций), то есть тех действий, которые возможно выполнить с элементами соответствующего множества Y; . типам отношений (вспоминаем определение отношения), в которых могут находиться между собой результаты измерения. Оба эти принципа классификации определяют следующие 4 основных типа шкал измерения, впервые предложенные в 1946 году Стэнли Стивенсом: 1) шкалы наименований (другие названия – номинативные, номинальные, классификационные); 2) шкалы порядка (или же ранговые, ординальные); 3) шкалы интервалов; 4) шкалы отношений. 63 Первые два из этих типов относятся к нечисловым шкалам (их также называют неметрическими или качественными), тогда как последние два – к числовым (иные названия: количественные, метрические). В соответствии с применяемой для него шкалой измерения каждый показатель может быть либо номинальным, либо порядковым, либо числовым. Можно выделить следующие признаки шкал, наличие или отсутствие которых определяет принадлежность шкалы к тому или иному из перечисленных типов: 1. упорядоченность данных означает, что результаты измерения можно сравнивать между собой по принципу «больше-меньше», то есть оправдано сравнивать элементы исходного множества X, определяя, что им соответствующие пункты шкалы являются больше, меньше или равны друг другу (отношение порядка); Отношение порядка. Отношение R, обладающее свойствами рефлексивности, антисимметричности и транзитивности, называется отношением порядка. Если на данном множестве введено отношение порядка, то это множество называется упорядоченным. В этом случае вместо xRу пишут x  у. Множество совершенно упорядочено, если для любых двух элементов x и у из множества M имеет место либо x  у, либо у  x. Если отношение обладает свойствами антирефлексивности, асимметричности и транзитивности, то оно называется отношением строгого порядка (обозначается x > у). Примером отношения строгого порядка является порядок букв в фиксированном алфавите. Упорядочение букв в алфавите позволяет, в свою очередь, упорядочить слова в словарях (лексикографическое упорядочение слов). 2. интервальность пунктов шкалы означает, что интервал между любой парой числовых измерений во столько-то раз больше (меньше) другого аналогичного интервала, либо равен ему; 3. наличие нулевой точки (или точки отсчета) означает, что измеряемое по данной шкале свойство имеет естественную точку отсчета, соответствующую полному отсутствию проявления измеряемого свойства. Кроме того, различают следующие типы данных, относящихся ко всем типам шкал: если в качестве наблюдения производится измерения лишь одной характеристики (или одного параметра), соответствующая величина является одномерной, или скалярной. если результатом эксперимента является регистрация некоторого набора характеристик, соответствующая величина называется многомерной, или векторной. Рассмотрим более подробно отдельные типы шкал. Шкалы наименований. Эти шкалы возникают и используются в случае, когда имеющиеся исходные объекты из множества X требуется 64 классифицировать по тому или иному признаку (одному!). Для обозначения в этой шкале могут быть использованы:  слова естественного языка (например, географические названия, при ответе на вопросы анкеты о месте рождения, проживания и т. п.; собственные имена людей и учреждений – для вопросов относительно места работы или учебы и т. п.);  произвольные символы (гербы и флаги государств, эмблемы родов войск, дорожные знаки и т. д.);  номера (регистрационные номера автомобилей, официальных документов, номера на майках спортсменов), отметим сразу же: эти номера не являются числами, хотя внешне и выглядят как числа; Отметим, что на практике степень детализации при осуществлении классификации может быть различной. Например, при классификации по признаку «цвет»: различимые в русском языке значения этого признака «голубой», «лазоревый» и «синий» в других языках (например, в английском) не различаются. Также заметим, что если у одного спортсмена на спине номер 1, а другого — 2, то никаких других выводов, кроме того, что это разные участники соревнований, делать нельзя: например, нельзя сказать, что «второй в два раза лучше или хуже первого». Здесь учтено, что каждый элемент входит в множество только один раз. Таким образом, шкала наименований имеет пункты, с помощью которых можно лишь установить, отличаются ли по данному признаку объекты друг от друга или нет. Никаких других соотношений между объектами эта шкала не выявляет. Она позволяет разбить все множество изучаемых объектов X на непересекающиеся классы (подмножества), классы эквивалентности (люди одной профессии, автомобили одинакового цвета, граждане одной страны и т.п.). Каждому классу эквивалентности может быть дано наименование или присвоен знак, в качестве которого могут выступать и числа. Эти имена и знаки служат только для целей идентификации объектов, так что каждому элементу из одного класса приписывается одно и то же имя (знак, число). Обязательным является правило: нельзя присваивать одно и то же имя (знак, число) разным классам объектов или разные имена объектам из одного класса. Признаки, измеряемые по шкале наименований (номинальной шкале), удовлетворяют аксиомам тождества: Либо А = В, либо А ≠ В; Если А = В, то В = А (перестановочность); Если А = В и В = С, то А = С (транзитивность). Отметим, что порядок расположения отдельных пунктов номинальной шкалы может быть любым. Основной эмпирической операцией, которую 65 позволяет реализовывать номинальная шкала, является установление того, относятся ли (или не относятся) два данных объекта к одному и тому же классу. В целом ряде случаев измеряемые показатели позволяют представить исследуемую совокупность в виде двух непересекающихся классов. Например, на некоторый вопрос анкеты ответ может принимать два значения: «да»/«нет», или изделие «годно»/«браковано» или (0, 1). Такие показатели (признаки) называются дихотомическими, или альтернативными (это 0-1). При этом исследователь зачастую заинтересован в одном из них, и тогда он говорит, что признак «проявился», если тот принял интересующее его значение, и что признак «не проявился», если он принял противоположное значение. Простейший случай номинальной шкалы – дихотомическая шкала, состоящая всего лишь из двух пунктов, например: «имеет братьев и сестер – единственный ребенок в семье»; «иностранец – соотечественник»; пол «мужской – женский» «черный белый цвет и т. п. При большом числе классов используют иерархические шкалы наименований (деревья). Наиболее известными примерами таких шкал являются шкалы, используемые для классификации животных и растений (где выделены классы, виды, подвиды и т.д.). Итак, с результатами измерений по шкале наименований можно выполнять только одну операцию - проверку их совпадения или несовпадения. Порядковые шкалы. Эти шкалы - применяются в тех случаях, когда наблюдаемый (измеряемый) признак имеет природу, не только позволяющую отождествить исходные объекты с одним из пунктов шкалы, но и дающую возможность каким-либо образом сравнивать сами эти пункты (значения признака) по степени проявления измеряемого показателя. Таким образом, за счет того, что пункты шкалы являются упорядоченными, возникает возможность проранжировать (упорядочить, ввести отношение порядка) и сравниваемые исходные объекты. Можно привести следующие простые примеры порядковых шкал: шкала балльных оценок успеваемости учащихся (неудовлетворительно, удовлетворительно, хорошо, отлично);  шкала академических рангов: бакалавр - Б, дипломированный специалист - С, магистр - М, кандидат наук - К, доктор наук - Д. В этом случае имеет место ранжировка Б < С < М < К < Д  шкала воинских званий, шкала спортивных разрядов – имеют, очевидно, аналогичную природу. 66 Порядковая шкала предполагает возможность упорядочения объектов по какому-либо критерию или свойству. Эта шкала определяется двумя эмпирическими операциями: 1) установлением равенства (отношение эквивалентности) объектов, как относящихся по итогам измерения к одному и тому же пункту шкалы (например, табель о рангах, соотносившая чины в гвардии и чины в не гвардейских полках, или чины военные и гражданские), 2) установлением между объектами отношения «больше – меньше» по итогам измерения данного показателя. Пример порядковой шкалы Ваше образование? № Значение пп. 1 2 3 4 неполное среднее среднее среднее специальное высшее Если в шкале наименований было безразлично, в каком порядке следуют пункты шкалы, то в порядковой шкале этот порядок важен, и значит, должно иметься не менее трех классов, например «положительная реакция – нейтральная реакция – отрицательная реакция» или «подходит подходит с оговорками – не подходит» и т. п. В порядковой шкале не определены численные значения расстояний между ее пунктами, известно лишь, что эти пункты образуют упорядоченную последовательность. Например, классы «подходит для занятия вакантной должности» и «подходит с оговорками» могут быть реально ближе друг другу, чем класс «подходит с оговорками» к классу «не подходит». Фактически речь опять идет о нечетких множествах и функции принадлежности. Вспомним еще и определение ближайшего четкого множества. От наименований пунктов шкалы легко перейти к числам, если мы условимся считать, например, что низшему классу сопоставляется число 1, среднему классу сопоставляется число 2, а высшему классу сопоставляется число 3. Итак, результаты измерений по порядковой шкале не имеют определенной количественной меры. При этом присутствует упорядоченность, но отсутствуют атрибуты интервальности и нулевой точки. Единственными типами отношений между неколичественными значениями шкалы могут быть: а) равенство одинаковых значений порядковых переменных величин, соответствующих объектам одной категории, 67 б) неравенство разных значений переменных величин, соответствующих объектам одной категории; в) отношения «больше» или «меньше» между разными значениями переменных величин, соответствующих объектам одной категории. Арифметические операции для этой шкалы также не имеют смысла. Например, нельзя вычислять выборочное среднее порядковых измерений. Допустимыми являются только операции эквивалентности и сравнения: х = у, х ≠ у, x > y, x < y, x≥ y, x≤y. Типовые порядковые шкалы. Обозначив пункты шкалы символами и установив между этими символами отношения строгого порядка, мы получим шкалу строгого порядка: А → В → C → D → E → F. Примеры: нумерация очередности, призовые места в конкурсе, социально-экономический статус («низший класс», «средний класс», «высший класс»). Иногда оказывается, что имеются пары пунктов шкалы, несравнимые между собой, т. е. ни А ≥ В, ни В ≤ А. В таком случае говорят о шкале частичного порядка. Шкалы частичного порядка часто возникают в социологических исследованиях субъективных предпочтений. Например, при изучении покупательского спроса субъект часто не в состоянии оценить, какой именно из двух разнородных товаров ему больше нравится (например, клетчатые носки или фруктовые консервы, велосипед или магнитофон и т. д.); затрудняется человек и упорядочить по предпочтению любимые занятия (чтение литературы, плавание, вкусная еда, слушание музыки). Важной характерной чертой порядковых шкал является то, что упорядоченность пунктов шкалы ничего не говорит о дистанции между ними. Поэтому порядковые экспериментальные данные, даже если они изображены цифрами, нельзя рассматривать как числа. Примеры порядковых шкал: 1. В 1811 г. немецкий минералог Ф. Моос предложил установить стандартную шкалу твердости минералов, предложив десять ее градаций. 3а эталоны приняты следующие минералы с возрастающей твердостью: 1 — тальк; 2 — гипс; 3 — кальций, 4 — флюорит, 5 — апатит, б — ортоклаз, 7 — кварц, 8 — топаз, 9 — корунд, 10 — алмаз. Из двух минералов тверже тот, который оставляет на другом царапины или вмятины при достаточно сильном соприкосновении. При этом ясно, что номера градаций алмаза и апатита не дают основания утверждать, что алмаз в два раза тверже апатита. 2. В 1806 г. английский гидрограф и картограф адмирал Ф. Бофорт предложил 12- балльную шкалу силы ветра, определяя ее по характеру 68 волнения моря: 0 — штиль (безветрие), …4 — умеренный ветер,.. 6 — сильный ветер,…. 10 шторм (буря), ….12 — ураган. 3. В 1935 г. американский сейсмолог Ч. Рихтер предложил 12-балльную шкалу для оценки энергии сейсмических волн в зависимости от последствий прохождения их по данной территории. Затем он развил метод оценки силы землетрясения в эпицентре по его магнитуде (условная величина, характеризующая общую энергию упругих колебаний, вызванных землетрясением или взрывами) на поверхности земли и глубине очага. Для измерения количественных признаков используются в основном две количественные шкалы – интервальная и шкала отношений. Шкала интервалов (интервальная шкала), в отличие от предыдущих, качественных, шкал уже является количественной шкалой. Интервальная шкала позволяет не только классифицировать и упорядочивать объекты, но и отражать, насколько по степени выраженности заданного свойства один объект отличается от другого. Для задания интервальной шкалы необходимо определить пункты, соответствующие начальной точке и единице измерения. Например, для количественного признака «температура»: 00 – начальная точка, 10 – единица измерения. Структура интервальной шкалы не изменяется при линейном преобразовании y = ax + b, a > 0, которое означает сдвиг начальной точки на b и умножении единицы измерения на a. Например, преобразование y = 9/5 x + 32 переводит шкалу измерения температуры по Цельсию в шкалу температуры по Фаренгейту. Для интервальной шкалы арифметические операции имеют смысл. Поэтому среднее арифметическое, как и медиана, и мода являются подходящими мерами положения центра распределения. Интервальная шкала применяется, когда известны интервалы между любыми двумя из пунктов шкалы. В шкале интервалов присутствуют упорядоченность и интервальность, но нет нулевой точки. Примеры: 1. Температура, время, высота местности — величины, которые по физической природе либо не имеют абсолютного нуля, либо допускают свободу выбора в установлении начала отсчета. 2. Часто можно услышать фразу: «Высота … над уровнем моря». Какого моря? Ведь уровень морей и океанов разный, да и меняется со временем. В России высоты точек земной поверхности отсчитывают от среднемноголетнего уровня Балтийского моря в районе Кронштадта. 69 В этой шкале только интервалы имеют смысл настоящих чисел и только над интервалами следует выполнять арифметические операции. Если произвести арифметические операции над самими отсчетами по шкале, забыв об их относительности, то имеется риск получить бессмысленные результаты. Пример. Нельзя сказать, что температура воды увеличилась в два раза при ее нагреве от 9 до 18° по шкале Цельсия, поскольку для того, кто привык пользоваться шкалой Фаренгейта, это будет звучать весьма странно, так как в этой шкале температура воды в том же опыте изменится от 37 до 42°. Частным случаем интервальных шкал являются шкалы разностей: циклические (периодические) шкалы, шкалы, инвариантные к сдвигу. В такой шкале значение не изменяется при любом числе сдвигов. у = х + nb, n = 0, 1, 2,… Постоянная b называется периодом шкалы. Примеры. В таких шкалах измеряется направление из одной точки (шкала компаса, роза ветров и т. д.), время суток (циферблат часов), фаза колебания (в градусах или радианах). Однако соглашение о хотя и произвольном, но едином для нас начале отсчета шкалы позволяет использовать показания в этой шкале как числа, применять к нему арифметические действия (до тех пор, пока кто-нибудь не забудет об условности нуля, например при переходе на летнее время или обратно). Шкала отношений. Если начало отсчета в числовой шкале является абсолютной нулевой точкой, то возникает возможность отразить, во сколько раз одно измерение отличается от другого. Соответствующая шкала называется шкалой отношений. Измерения в такой шкале являются «полноправными» числами, с ними можно выполнять любые арифметические действия, здесь присутствуют все атрибуты измерительных шкал: упорядоченность, интервальность, нулевая точка. Величины, измеряемые в шкале отношений, имеют естественный, абсолютный нуль, хотя остается свобода в выборе единицы измерения. Допустимыми для шкалы отношений являются преобразования подобия вида: у = ах, а > 0 Примеры: вес, длина, электрическое сопротивление, деньги — величины, природа которых соответствует шкале отношений. Из значений шкалы отношений видно, во сколько раз свойство одного объекта превосходит такое же свойство другого объекта. Все величины, определяющие положение центра распределения в интервальной шкале, подходят и для шкалы отношений. 70 Частным случаем шкалы отношений является абсолютная шкала. Абсолютная (метрическая) шкала имеет и абсолютный нуль (b = 0), и абсолютную единицу (а = 1). В качестве пунктов шкалы при измерении количества объектов используются натуральные числа, когда объекты представлены целыми единицами (то есть когда измеряется «число штук»). Если же кроме целых единиц присутствуют и части объектов, то в качестве пунктов абсолютной шкалы используются действительные числа. Именно такими качествами обладает числовая ось, которую естественно называть абсолютной шкалой. Важной особенностью абсолютной шкалы по сравнению со всеми остальными является отвлеченность (безразмерность) и абсолютность ее единицы. Указанная особенность позволяет производить над показаниями абсолютной шкалы такие операции, которые недопустимы для показаний других шкал, — употреблять эти показания в качестве показателя степени и аргумента логарифма. Примеры: 1. Абсолютные шкалы применяются, например, для измерения количества объектов, предметов, событий, решений и т. п. 2. Примером абсолютной шкалы также является шкала температур по Кельвину. Числовая ось используется как измерительная шкала в явной форме при счете предметов, а как вспомогательное средство присутствует во всех остальных шкалах. К сказанному следует добавить, что в теории измерений существуют известные методы перевода «сырых» тестовых баллов в стандартные шкалы, такие, как шкала стенов или станайнов. Тем самым порядковые измерения переводятся в метрические, где за единицу измерения берутся доли стандартного отклонения или она устанавливается в соответствии с процентильными границами групп в нормальном распределении стандартной шкалы. Можно сказать, что чем сильнее шкала, в которой производятся измерения, тем больше сведений об изучаемом объекте, явлении, процессе дают измерения. Однако важно иметь в виду, что выбор шкалы измерения должен ориентироваться на объективные отношения, которым подчинена наблюдаемая величина, и лучше всего производить измерения в той шкале, которая максимально согласована с этими отношениями. Можно измерять и в шкале более слабой, чем согласованная (это приведет к потере части полезной информации), но применять более сильную шкалу опасно: полученные данные на самом деле не будут иметь той силы, на которую ориентируется их обработка. 71 Сводная таблица Типы шкал и их свойства согласно классификации С. Стивенса Номинальная Порядковая Интервальная Шкала шкала шкала шкала отношений ×÷ нет нет нет да + нет нет да да Логические/ математи< ческие нет да да да операции > = да да да да ≠ Примеры: Дихотомические и недихотомические переменные Дихотомические: Пол (мужской / женский) Дихотомические: Состояние здоровья (здоровый / больной), Недихотомические: Национальность (американец/ китаец/ и т.д) Красота (красивый/ уродливый) Дата (с 1457 до н.э до 2013 н.э) Возраст (от 0 до 99 лет) Широта (от +90° до −90°) Температура (от 10°C до 20°C) Недихотомические: Мнение ('полностью согласен'/ 'скорее согласен'/ 'скорее несогласен'/ 'полностью несогласен') Мера центральной тенденции Метрическая или нет Мода Медиана Неметрическая (качественная) Неметрическая (качественная) Среднее арифметическое Среднее геометрическое Метрическая Метрическая (количественная) (количественная) Иногда же, в том числе и при обработке результатов анкетирования, исследователи усиливают шкалы; типичный случай — «оцифровка» качественных шкал: классам в номинальной или порядковой шкале присваиваются номера, с которыми дальше «работают» как с числами. Если в этой обработке не выходят за пределы допустимых преобразований, то «оцифровка» - это просто перекодировка в более удобную (например, для ЭВМ) форму. Однако применение других операций сопряжено с заблуждениями, ошибками, так как свойства, навязываемые подобным образом, на самом деле не имеют места. По мере развития соответствующей области знания тип шкалы может меняться. Пример. Температура сначала измерялась по порядковой шкале (холоднее - теплее), затем — по интервальным шкалам (Цельсия, Фаренгейта, Реомюра), а после открытия абсолютного нуля температур - по шкале отношений - шкале (Кельвина). 72 С вопросом о типе шкалы непосредственно связана проблема адекватности методов математической обработки результатов измерения. В общем случае адекватными являются те результаты математических операций над данными, которые не меняются при допустимых преобразованиях используемой шкалы измерений. Далее проанализируем некоторые проблемы, которые могут иметь место при более глубоком рассмотрении шкал и измерения показателей, зачастую присутствующих в социологических анкетах. 1. Возраст. В данном случае наиболее естественной представляется метрическая шкала, на которой откладывается полный биологический возраст респондента. Однако, если возраст измеряется с абсолютной точностью при фиксированных единице измерения и точке отсчета, то мы имеем абсолютную шкалу. Если можно менять единицу измерения (например, исчислять возраст в годах, месяцах или днях), то получаем шкалу отношений. Далее, большинство народов считает точкой отсчета возраста момент рождения, но у некоторых принято отсчитывать возраст с момента зачатия - это приводит к шкале разностей, инвариантной относительно сдвига на 9 месяцев. Однако, с социологической точки зрения более важно то, что в большинстве случаев интерпретация данных не позволяет считать их удовлетворяющими даже требованиям интервальной шкалы. Дело в том, что с социальной точки зрения существуют «пороговые» значения возраста, при пересечении которых меняется качественная определенность респондента. Например, в России в 14 лет человек получает паспорт, в 18 лет считается совершеннолетним, с 55 лет наступает пенсионный возраст для женщин, а с 60 лет - для мужчин. Это означает, что разница между мужчинами в возрасте 22 и 23 года не такая же, как между мужчинами в возрасте 18 и 19 или 59 и 60 лет, то есть с формальной точки зрения допустима лишь порядковая шкала. 2. Национальность. При рассмотрении признаков подобного типа возникает дополнительная проблема составления списка возможных значений, а также выбора критериев приписывания значений признака конкретным респондентам. Для такой страны, как Россия, ответы на эти вопросы (необходимые для построения номинальной шкалы) являются далеко не тривиальными. Действительно, перечень национальностей включает более 100 наименований, границы между которыми в ряде случаев довольно расплывчаты и требуют тщательной этнографо-антропологической экспертизы. Непросто и установить, кем считать, например, этнического татарина, проживающего в Башкирии и говорящего только на русском языке. Такие случаи являются далеко не экзотическими, а вполне массовыми, а решение соответствующих проблем имеет весьма деликатные аспекты. 73 3. Профессия и образование. При изучении таких признаков, как профессия и образование, необходимо иметь в виду два аспекта их природы: качественный аспект (профессии врача, учителя, инженера и т.д.) и количественный аспект (разряды рабочих, категории врачей и т.п.). Аналогично образование может быть гуманитарным, техническим, медицинским, естественно-научным в качественном аспекте, а в количественном аспекте можно говорить о начальном, среднем, среднем специальном, высшем образовании, дипломах бакалавра, магистра, кандидата или доктора наук. Количественный аспект профессии или образования имеет очевидную иерархическую упорядоченность и задает измерение этих признаков по порядковой шкале: ясно, что доктор наук «старше» бакалавра, а токарь шестого разряда более квалифицирован, чем выпускник профессиональнотехнического училища. Более того, с довольно высокой точностью можно использовать и интервальную шкалу, предполагая соседние квалификационные разряды примерно равно отстоящими друг от друга: тогда различие между вторым и третьим разрядами приблизительно такое же, как и между пятым и шестым. С качественным аспектом ситуация сложнее. Построение даже номинальной шкалы, скажем, профессий, представляет собой весьма сложную задачу. Так, в США с 1939 года издается «Словарь наименований профессий», содержащий очень полезную для социологов информацию. В последних изданиях каждой профессии соответствует 9-значный код, первые три цифры которого отражают тип технологии, отрасль индустрии и продукт труда, следующие три - степень сложности задач, стоящих перед работником, а последние три являются просто порядковыми номерами, обозначающими профессию. В России аналогичное издание пока отсутствует, что затрудняет работу социологов. 4. Территория. Этот признак определяет принадлежность индивида к той или иной территориальной общности. Поэтому номинальная шкала задается простым указанием места жительства респондента. Для построения порядковой шкалы необходимо использовать общественные предпочтения различных типов поселений. Конечно, большие возможности для удовлетворения потребностей предоставляют крупные города, поэтому для построения порядковой шкалы можно использовать численность жителей в данном населенном пункте. Однако следует принимать во внимание и субъективные предпочтения: некоторые люди предпочитают деревенский образ жизни городскому. 74 Глава 7. Логические методы моделирования систем 7.1. Операции с высказываниями Понятие высказывания. Под высказыванием понимаем всякое утверждение (повествовательное предложение), про которое всегда определенно и объективно можно сказать, является оно истинным или ложным. Например: "5 - 3 = 2" или "В неделе семь дней", – истинные высказывания, а "5 > 8" или "В русском языке 35 букв", - ложные высказывания. Синонимами слова высказывания можно считать: логическое высказывание, булевское выражение, суждение, утверждение и т. п. Фразы: "Ура!", "Который час?" - не являются высказываниями. Если высказывание истинное, то ему предписывается значение "истина" (другие обозначения:"1", "ДА", "И", "+", "true"). Ложному высказыванию предписывается значение "ложь" (или: "0", "НЕТ", "Л", "-", "false"). Совокупность возможных значений высказывания образует множество истинности или логическое множество Е, состоящее из двух элементов E  [0,1} и Е = {И, Л}. Есть два вида высказываний: простые и составные (сложные). Под простым будем понимать высказывание, которое не может быть разбито на более простые высказывания. Про него всегда однозначно можно сказать, что оно истинно или ложно, не интересуясь его структурой. Из простых высказываний при помощи логических операций можно строить сложные высказывания, которые всегда только истинны или только ложные. Высказывания обозначаются заглавными латинскими буквами: A  "5 + 7 = 12", B  "сегодня вторник", C  "если студент успешно сдал сессионные экзамены, то переводится на следующий курс и будет получать стипендию". Логические операции. Операции над высказываниями задают в виде таблиц, называемых таблицами истинности. Отрицание высказывания. Для каждого высказывания A может быть сформировано новое высказывание A - отрицание высказывания A, которое истинно, когда A ложно и ложно, когда A истинно (рис. 7.1 а). A читается "не A" или " не верно, что A". Отрицание - одноместная (или унарная) операция. Последующие операции - двухместные (или бинарные). Например, если A  3  5  8 - истинное высказывание, то A  3 + 5  8 - ложное высказывание (отрицание A), или если B  "в комнате холодно", B  "в комнате не холодно". Отметим, что высказывание "в комнате жарко" не является отрицанием B. Конъюнкция высказываний. Конъюнкцией высказываний A и B называется высказывание C = A  B, которое истинно только в том случае, когда и A и B одновременно истинны (рис. 7.1, б). Выражение A B читается "A и B". Пример: пусть A  "12 делится на 3" и B  "12 делится на 4". Тогда формула A  B имеет смысл: "12 делится на 3 и на 4". 75 Операцию конъюнкции можно определить и для нескольких высказываний как связку высказываний, объединенных союзом "и". Конъюнкция из n высказываний - новое высказывание, причем высказывание n  A= i 1 Ai  A 1  A 2  ...  A n имеет значение ―истина‖, если и A1 и A2 и .... An истинны. Во всех других случаях эта конъюнкция имеет значение "ложь". Пусть, например, A1  "5 > 3", A2  "8 = 3", A3  "отец старше сына", A4  "Мурманск севернее Смоленска". Тогда высказывание A2  A3  A4  ("8 = 3 и отец старше сына и Мурманск севернее Смоленска") - ложное высказывание. В то время как A1  A3  A4   "5 > 3 и отец старше сына и Мурманск севернее Смоленска" истинное A A C=AB B 1 1 1 1 1 0 0 1 0 1 0 а 0 0 0 б Рис. 7.1. Таблицы истинности. а для операции отрицания, б для операции конъюнкция высказывание. Дизъюнкция высказываний. Дизъюнкцией высказываний A и B называется высказывание D = A  B, которое ложно только тогда, когда и A и B ложны одновременно (рис. 7.2, а). Дизъюнкция имеет значение "истина", если хотя бы одно из высказываний, входящее в дизъюнкцию, является истинным. Выражение A  B читается ―A или B‖. Пусть A  "7 < 9" и B  "3 + 5 = 8". Тогда A  B  "7 < 9 или 3 + 5 = 8". Операцию дизъюнкции можно определить для нескольких высказываний как связку высказываний объединенных союзом "или". A n A = i1 Ai  A1  A2  ...  A n . В этом случае высказывание A истинно, если истинно хотя бы одно из высказываний, входящих в связку. Импликация высказываний. Импликацией высказываний A и B называется высказывание F = A  B, которое ложно только в том случае, когда A - истинно, а B – ложно (рис. 7.2, б). Во всех других случаях импликация A  B имеет значение «истина». Символ «  » соответствует логическому союзу: «если А, то В». Например, A – «целое число делится на 4, то оно делится на 2». Для иллюстрации содержательного смысла импликации рассмотрим следующий пример: A  «папа завтра получит премию», B  «папа завтра купит сыну велосипед». Тогда импликация A  B может быть сформулирована так: «если папа завтра получит премию, то купит сыну велосипед». 76 A 1 1 B 1 1 D=AB 1 1 1 A 1 1 B 1 1 F=AB 1 1 1 A 1 1 B 1 1 G=AB 1 1 а б г Рис. 7.2. Таблицы истинности для: а - дизъюнкции, б – импликации, г - эквивалентности Пусть A и B истинны. Тогда папа, получив премию, покупает сыну велосипед. Естественно считать это истинным высказыванием. Когда же папа не купит сыну велосипед (B - ложно), получив премию (A - истинно), то это, мягко говоря, не логичный поступок, а импликация имеет значение "ложь". Если же папа не получит премию (A - ложно), но купит велосипед (B истинно), то результат положителен. В том случае, если, не получив премии (A ложно), папа не купит велосипед (B ложно), обещание не нарушено, результат можно считать истинным. Высказывание В→А называется конверсией высказывания А→В. Эквивалентность высказываний. Эквивалентностью высказываний A и B называется высказывание G = A  B, которое истинно, когда высказывания и A и B оба истинны или оба ложны (рис. 7.2 г). Символ логической эквивалентности "  " соответствует связке "тогда и только тогда". Пример. Пусть A  "число 3n является четным", B  "число n является четным". Высказывание "число 3n является четным тогда и только тогда, когда n - четное число" есть эквивалентность высказываний A и B, т. е А↔В. Эквивалентность высказываний может быть задана таблицей истинности (рис. 7.2). Штрих Шеффера (отрицание конюнкции или антиконюнкция, рис. 7.3, а) M = A|B= A  B . Стрелка Пирса (отрицание дизюнкции или антидизюнкция, рис. 7.3, б) N = A↓B= A  B . Сумма по модулю 2 ( сумма Жегалкина или антиэквивалентность, рис. 7.3, в) P = A  B = AB Замечание. Характерной особенностью операций над высказываниями является введение логических союзов с точно определенным смыслом, не допускающим никакой двусмысленности в толковании этих символов. Таким образом, математическая логика применима не для любых высказываний, а только для таких, которые допускают четкую оценку в двоичной системе 77 "истина - ложь". Для преодоления такого рода ограничений в рамках нечеткой математики разрабатывается нечеткая логика. A 1 1 B 1 1 M=А|B 1 1 1 A 1 1 B 1 1 N=A↓B 1 B P=A  B 0 0 1 1 0 1 1 0 а б в Рис. 7.3.Таблицы истинности для: а - штриха Шеффера, б - стрелки Пирса, в - суммы Жегалкина (сумма по модулю два) A 1 1 Если в выражении встречаются различные логические операции, то в качестве естественного порядка (выполняемого поочередно слева направо) используется следующая последовательность: ,  ,  ,  ,  . Это означает, что сначала выполняются операции отрицания, затем конъюнкции и т. д. Для нарушения порядка служат скобки. Рассмотрим пример. Пусть высказывания A и B имеют значения "истина", а высказывания C и D – "ложь". Тогда формула A  B  C  D  A имеет значение "ложь", так как: 1. D – "истина"; 2. B  C – "ложь"; 3. ( D )  A – "истина"; 4. A  (B  C) – "ложь"; 5. (A  (B  C))  ( D  A) – "ложь". Введя скобки, получим формулу A  B  (C  D )  A, которая уже имеет другое значение – "истина". Действительно: 1. D – "истина"; 2. C  ( D ) – "ложь"; 3. B  (C  D ) – "ложь"; 4. (B  (C  D ))  A – "истина"; 5. A  (B  (C  D )  A) – "истина". Если в выражении присутствуют арифметические операции, операции сравнения и логические операции, то порядок старшинства операций следующий: сначала выполняются арифметические операции (порядок старшинства арифметических операций – первыми выполняются все операции умножения и деления, потом операции сложения и вычитания); затем – операции =,  и операции сравнения (в том порядке, в каком они встречаются в выражении): >, , , <; 78 наконец, логические операции, причем первой везде выполняется операция отрицания, затем конъюнкции, потом дизъюнкции и т. д. Использование различных операций позволяет в удобной аналитической форме задавать различные множества. Например, множество точек А, заштрихованное на рис. 7.4, может быть задано следующей формулой: A = {(x,y) | (y  1 - x)  (x2 + y2  1)  (x,y)  R2} . Рис. 7.4. Множество А: {(x,y) | (y  1 - x)  (x2 + y2  1)  (x, y)  R2} Логические формулы доказываются с помощью таблиц истинности, например надо доказать, что данная логическая формула истина при любых значениях Х и Y: X  ( X  Y )  1 . Составим таблицу, в первых столбцах которой перебираем все возможные пары значений для Х и Y, а потом используем таблицы истинности для логической операции импликация (табл. 7.1). Т а б л и ц а 7.1. Таблица истинности для формулы X  ( X  Y )  1 X Y X X→Y X  (X Y) 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Система операций  называется полной, если всякая формула эквивалентна некоторой формуле, в которую входят только операции из системы  . Система введенных пяти операций (отрицания, конъюнкции, дизъюнкции, импликации и эквивалентности) полная, хотя вообще говоря, избыточна, так как одни логические операции могут быть выражены через 79 другие. Например, импликация и эквивалентность можно выразить через отрицание, конъюнкцию и дизъюнкцию следующим образом: A B  A  B A  B  (A  B)  (B  A). Основные законы математической логики 1. Коммутативность A  B  B  A, A  B  B  A. 2. Ассоциативность A  (B  C)  (A  B)  C, A  (B  C)  (A  B)  C. 3. Дистрибутивность A  (B  C)  (A  B)  (A  C), A  (B  C)  (A  B)  (A  C). 4. Законы де Моргана (A  B)  A  B и ( A  B)  A  B. 5. Закон поглощения A  (A  B)  A  (A  B) ≡ A. 6. Закон идемпотентности A  A  A  A  A. 7. A  "истина"  A, A  "ложь"  A. 8. Закон противоречия A  A  "ложь", 9. Закон исключения третьего A  A  "истина". 10. Закон двойного отрицания A  A. Например, упростить f ( x, y, z)  xy  yz  xyz  yz  x  y  z . В этой записи xy  x  y f ( x, y, z )  xy  yz  xyz  yz  x  y  z   xy  yz  xyz  yz  x yz  xy  yz  xyz  yz   xy  yz  yz  xyz  xy  z  xyz   xy  (( z  x)  ( z  y )  ( z  z ))   xy  (( z  x)  ( z  y ))  xy  z  xy   xy  z  xy  xy  xy  z  y  z 7.2. Булевы функции Всякую формулу логики высказываний можно рассматривать как некоторую функцию: каждая буква (высказывание) может принимать одно из 80 двух значений "истина" или "ложь", при этом сложное высказывание, заданное этой формулой, также может быть истинным или ложным. Так формула (A  B)  C  (B  A) = f(A,B,C) выражает функцию от переменных A, B и C. Запись неудобна, поэтому высказывания будем называть логическими переменными или булевыми переменными и обозначать xi . Булевой функцией от n логических (булевых) переменных x1 , x2 ,... xn называют функцию f ( x1 , x2 ,... xn ) , которая принимает только значения 0 или 1. Так как каждый набор переменных можно рассматривать как кортеж из n множества E  E  E  .....  E , где Е – логическое множество Е = {0, 1}, то булева функция отображает E n на Е. Количества булевых функций равно 2 2n , где n -количество переменных. Для функции одной переменной их четыре, двух – шестнадцать и т. д. Булеву функцию можно задать таблицей истинности. Для функции одной переменной – это табл. 7.2. Т а б л и ц а 7.2. Таблица истинности для функции одной переменной х f1 ( x) f 2 ( x) f 3 ( x) f 4 ( x) 1 1 1 1 1 В табл. 7.2: f1 ( x) – тождественная ложь, f 2 ( x) – тождественная функция, f3 ( x) – отрицание х, а f 4 ( x) – тождественная истина. f1 ( x) = (0 0), f 2 ( x) = (0 1). Для функции двух переменных – это табл. 7.3. Целый ряд булевых функций обладают тем свойством, что они принимают одни и те же значения при любых значениях истинности аргументов. Такие формулы называются тождественно истинными. Например, при любых X и Y истинны формулы X  X и X  ( Y  X). Тождественно ложные функции при любых значениях аргументов имеют значение "ложь". Так формулы X  X и (X  (Y  X))  (Y  Y ) всегда имеют значение "ложь". Две булевых функции равны, если для любых одинаковых кортежей из n Е значения функций равны . Для булевых функций справедливы равенства, аналогичные формулам, сформулированным для высказываний. 81 Т а б л и ц а 7.3. Таблица истинности для функции двух переменных х1 1 1 х2 1 1 f1 f2 1 f3 1 f4 1 1 f5 1 f6 1 1 f7 1 1 f8 1 1 1 f1- тождественная ложь f9 1 f10 1 1 f11 1 1 f12 1 1 1 f13 1 1 f14 1 1 1 f15 1 1 1 f16 1 1 1 1 f9 = х1 ↓ х2 стрелка Пирса отрицание дизъюнкции f10 = х1 ↔ х2 эквивалентность f11 = x2 f2 = х1  х2 конъюнкция f3= x1  x2 отрицание импликации f 4 = х1 f5 = x2  x1 отрицание конверсии f 6 = х2 f7 = х1  х2 сумма Жегалкина отрицание эквивалентности f8 = х1  х2 дизъюнкция f12 = х2→ х1 конверсия f13 = x1 f14 = х1→ х2 импликация f15 = х1 | х2 штрих Шеффера отрицание конъюнкции f16 – тождественная истина Рассмотрим пример: доказать эквивалентность функций f1 ( x, y, z )  x  ( x  z)  ( y  z) и f 2 ( x, y, z)  ( x  y)  ( x  z) . Решение примера. Составим таблицы для булевых функций. Для этого выпишем в первых трех столбцах все 8 вариантов комбинаций значений переменных x, y, z . Потом выполняем операции в скобках. Далее для первой функции f1 выполняем последовательно две конъюнкции (таб. 7.4). Т а б л и ц а 7.4. Таблица истинности для f1 х 1 1 1 1 82 у 1 1 1 1 z 1 1 1 1 xz 1 1 1 1 1 1 yz 1 1 1 1 1 1 x  ( x  z) 1 1 1 1 f1 ( x, y, z)  x  ( x  z)  ( y  z) 1 1 1 f1 ( x, y, z ) = (0 0 0 0 0 1 1 1) Для f2 выполняем первыми операции в скобках, потом дизъюнкцию табл. 7.5. Т а б л и ц а 7.5. Таблица истинности для f2 х у z x y xz 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 f 2 ( x, y, z)  ( x  y)  ( x  z) 1 1 1 f 2 ( x, y, z ) = (0 0 0 0 0 1 1 1) Так как результат одинаков, то f1  (00000111)  f2 и f1 ( x, y, z )  x  ( x  z)  ( y  z ) и f 2 ( x, y, z)  ( x  y)  ( x  z) эквивалентны. функции Два набора (кортежа) булевых переменных называются соседними по i – й переменной, если они отличаются только по этой переменной – в одном кортеже i–я переменная равна нулю, а в другом единице: ( x1 , x2 , x3 ,...xi 1 ,0, xi 1 ,....xn ) и ( x1 , x2 , x3 ,...xi 1 ,1, xi 1 ,....xn ) . Переменная xi называется фиктивной переменной булевой функции f, если для любых соседних по xi наборов значения булевой функции совпадают f ( x1 , x2 , x3 ,...xi 1 , 0, xi 1 ,....xn )  f ( x1 , x2 , x3 ,...xi 1 ,1, xi 1 ,....xn ) . Например, для функции f4 из списка булевых функций для двух переменных: f4 = х1 и не зависит от значений х2. Переменная xi называется существенной переменной булевой функции f, если существует хотя бы одна пара соседних по xi наборов такая, что значения булевой функции не совпадают f ( x1 , x2 , x3 ,...xi 1 ,0, xi 1 ,....xn )  f ( x1 , x2 , x3 ,...xi 1 ,1, xi 1 ,....xn ). 83 Пример. Для булевых функций двух переменных: f4 = х1 - здесь х2 фиктивная переменная, а х1 существенная, f11 = x2 - здесь х1 фиктивная переменная, f16 фиктивными переменными будут и х1 и х2, f10 = х1 ↔ х2 существенными будут обе переменные. Суперпозицией булевых функций f1, f2,… fm называется булева функция f, для которой функции f1, f2,… fm будут аргументами. Например, f ( x1 , x2 )  g ( x1 , x2 , h( x1 , x2 )) . Пусть для функций f и h задана таблица истинности (табл. 7.6). Построим таблицу истинности для суперпозиции g, используя таблицу истинности булевой функции трех переменных g ( x1 , x2 , x3 )  f (h( x1, x2 ), h( x2 , x3 )) (табл. 7.7). Т а б л и ц а 7.6. Таблица истинности для функций f и h х1 1 1 х2 1 1 f ( x1 , x2 ) h( x1 , x2 ) 1 1 1 1 1 Т а б л и ц а 7.7. Таблица истинности булевой функции трех переменных g ( x1 , x2 , x3 )  f (h( x1, x2 ), h( x2 , x3 )) x1 x2 x3 h( x1 , x2 ) h( x2 , x3 ) g( x1 , x2 , x3 ) 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Как следует из этой таблицы g( x1 , x2 , x3 ) = (10001011). Например, упростить и вычислить f ( x, y, z)  xy  yz  xyz  yz  x  y  z . f ( x, y, z)  y  z 84 xyz 000 001 010 011 100 101 110 111 xy 1 1 x y yz xy  yz z xyz 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 yz y z f ( x, y, z ) 1 7.3. Основные методы доказательств В основе любой теории лежат аксиомы или постулаты – высказывания, истина которых утверждается без доказательства. Доказательством называется последовательность высказываний, каждое из которых является или аксиомой или выводится из предыдущих высказываний по логическим правилам вывода. Высказывания, истинность которых установлена доказательством, называются теоремами. Каждая теорема может быть выражена в форме импликации А→В, где А называется условием теоремы, а В – заключением. Теорема верна, если импликация исинна. Существуют следующие методы доказательства. Метод цепочек импликаций состоит в том, что из посылки A выстраивается цепочка из n импликаций, последним высказыванием в которой является заключение теоремы B, т. е. A  A1  A2  ...  An-1  B. В основе этого метода лежит закон цепного высказывания или закон силлогизма (A  C)  (C  B  (A  B). Например, если скалярное произведение ненулевых векторов равно нулю, то вектора ортогональны. Метод от противного. Используя этот метод, вместо доказательства прямого следствия "из A следует B" доказывают, что из "не B" следует "не A". Этот метод основан на законе контрапозиций: (A  B)  ( B  A ). Например, теорема о единственности предела. Метод необходимого и достаточного. Теорема формулируется так: "Чтобы имело место A, необходимо и достаточно выполнение B". Доказательство такого вида теоремы распадается на две части: а) доказывается, что если имеет место A, то справедливо B (B необходимо для A); б) Если имеет место B, то имеет место и A (B достаточно для A). Доказательство таким методом базируется на законе тавтологии. (А  В)  ((А  В)  (В  А)). 85 7.4. Алгебра предикатов В теории множеств мы ввели понятие Декартового произведения, как множества состоящего из упорядоченных наборов - кортежей (векторов или n-ок) M = M1  M2  ...  Mn . При этом сами множества M i , i  1,....., n могли быть любой природы и количество множеств M i любое. Но на практике наиболее часто встречающийся случай двух множеств в произведении. В этом случае удобнее их обозначать как X и Y. Потом ввели понятие соответствия, которое задавалось как упорядоченный набор трех множеств {X, Y, G}, где X и Y можно рассматривать как вершины двудольного (т.е. состоящего из двух не пересекающихся подмножеств) графа, а G – соединяющие их ребра (или дуги), в данном случае подмножество прямого произведения X  Y . Далее, мы ввели понятие n - местного отношения R на множестве M как подмножество прямого произведения, т. е. R  M. То есть, рассматриваются некоторые упорядоченные наборы элементов из множества M и эти элементы находятся между собой в отношении R. Отношение может быть задано на множестве элементов любой природы. При n = 1 (M = M1) возникает унарное (одноместное) отношение. По существу, одноместное отношение есть просто подмножество M. Все входящие в подмножество элемента объединены общим свойством, которое можно задать формулой или описать словесно. Например, быть студентом, если М -множество людей. При n = 2 (M = M1  M2) отношение называется бинарным. Эти отношения мы записывали как {xRy | x  M1, y  M2 (или x,y  M)} и говорят, что элементы x и y из множества M находятся между собой в отношении R. Например, ―продукт x чаще покупают, чем y". Существуют также тернарные (n = 3), тетрарные (n = 4),..., n-арные отношения. Для задания бинарных отношений на конечных множествах удобно использовать списки пар или таблицы (матрицы). В этом случае, если элементы x и y находятся между собой в отношении R, то в матрице на соответствующем месте пишут 1, в противном случае пишут ноль. Эта матрица напоминает матрицу смежности, но она не обязана быть квадратной и симметричной. Рассмотрим прямое произведение M1  M 2  ...  M n  {( x1 , x2 ,..., xn )} . Предикатом P(x1, x2,..., xn), заданным на множестве М, где М подмножество прямого произведения множеств M  M1  M 2  ... M n , называется функция P, отображающая подмножество М на двоичное множество, т. е. P: M  M1  M 2  ...  M n  {0,1}. Тем самым предикат Р ставит в соответствие каждому кортежу из множества М ноль или единицу. Множество M 86 называется предметной областью предиката, а x1, x2, ..., xn  M называются предметными переменными или термами. Предикат представляет собой логическую функцию, принимающую, как и булевская функция, значение "истина" или "ложь", когда ее предметные переменные принимают определенные значения. Например, "x2 - 5x + 6 = 0" - одноместный предикат на множестве комплексных чисел, при этом, например, если x = 2, то "22 - 5  2 + 6 = 0" истинное высказывание (тоже будет и при х = 3) , а положив x = 7, получим "72 - 5  7 + 6= 0" - "ложь". Выражение "X - брат Y" - двухместный предикат, заданный на множестве людей. Здесь термы X и Y указывают места, на которые нужно поставить имена двух людей, чтобы получить правильно построенное высказывание. Очевидно, что X - лицо мужского пола, а Y может выбираться из всего множества людей. Бинарное отношение может рассматриваться в качестве двухместного предиката. Всякий предикат P(x1, x2,..., xn) определяет отношение R, такое, что (а1, а2, ..., аn)  R тогда и только тогда, когда P(а1, а2, ..., аn) – "истина". Т. е. среди всех кортежей выделяются те, для которых предикат «истина». В этом случае говорят, что отношение R задается областью истинности предиката P(x1, x2,..., xn). Например, отношение R(M, N) = "расстояние на плоскости между точками M(x1, y1) и N(x2, y2) больше величины l" можно задать предикатом "(x2 - x1)2 + (y2 - y1)2 > l ". Если в n–местный предикат на место одного из термов подставить определенный элемент из соответствующего множества, по предикат станет (n - 1) – местным. Заменив все термы на конкретные значения из предметной области предиката, получим 0 – местный предикат, т. е. высказывание. Например, "X – брат Y" – двухместный предикат, "X – брат Маши" – одноместный предикат, "Саша – брат Маши" – высказывание. Предикат называется разрешимым (выполнимым), если существуют кортежи, обращающие предикат в истинное высказывание. Если предикат при подстановке любых кортежей из предметной области является истинным, то он называется тождественно истинным и принимает значение 1. Если предикат является всегда ложным, то называется тождественно ложным и принимает значение 0. Например, предикат x2  y 2  0 , заданный на множестве действительных чисел всегда тождественно ложен, а предикат x 2  y 2  0 всегда тождественно истинен на этом же множестве. Предикат x 2  y 2  0 истинен на кортеже (0,0) и ложен в остальных случаях. Логические операции над предикатами Отрицание предиката. Пусть предикат P(x1, x2,..., xn) задан на множестве M  M1  M 2  ... M n . Предикат R(x1, x2,..., xn)) называется 87 отрицанием предиката P(x1, x2,..., xn) тогда и только тогда, если при одних и тех же кортежах (а1, а2, ..., аn), где а1  M1, а2  M2, ..., аn  Mn, высказывание P(а1, а2, ..., аn) истинно, когда R(а1, а2, ..., аn) – ложно, и наоборот. Обозначение R(x1, x2,..., xn)  P ( x1, x2,..., xn). Например, предикат "n – четное число" есть отрицание предиката "n – нечетное число" на множестве целых чисел. Конъюнкция предикатов. Пусть на множестве M  M1  M 2  ... M n заданы два n – местных предиката P(x1, x2,..., xn) и R(x1, x2,..., xn). Конъюнкцией этих предикатов называется предикат Q(x1, x2,..., xn)  P(x1, x2,..., xn)  R(x1, x2,..., xn), который истинен для одних и тех же кортежей только тогда, когда оба предиката и P(x1, x2,..., xn) и R(x1, x2,..., xn) истинны. Дизъюнкция предикатов P(x1, x2,..., xn) и R(x1, x2,..., xn), есть новый предикат S(x1, x2,..., xn) = P(x1, x2,..., xn)  R(x1, x2,..., xn), который имеет значение "ложь" для тех и только тех кортежей из M  M1  M 2  ... M n , для которых оба предиката и P(x1, x2,..., xn) и R(x1, x2,..., xn) имеют значение "ложь". Импликация предикатов P(x1, x2,..., xn) и R(x1, x2,..., xn), есть новый предикат T(x1, x2,..., xn) = P(x1, x2,..., xn)  R(x1, x2,..., xn), который имеет значение "ложь" для тех и только тех кортежей из M  M1  M 2  ... M n , для которых предикат P(x1, x2,..., xn) имеет значение "истина", а предикат R(x1, x2,..., xn) имеет значение "ложь". Например, импликация "n делится на 4"  " n делится на 2" есть предикат: "если n делится на 4, то n делится на 2". Эквивалентность предикатов P(x1, x2,..., xn) и R(x1, x2,..., xn), есть новый предикат V(x1, x2,..., xn) = P(x1, x2,..., xn)  R(x1, x2,..., xn), который имеет значение "истина" для тех и только тех кортежей из M  M1  M 2  ... M n , для которых предикат P(x1, x2,..., xn) и предикат R(x1, x2,..., xn) имеют одинаковые значения – или оба "истина" или оба "ложь". Два предиката, заданных на одних и тех же множествах, называются равносильными, если при всех наборах входящих в них предметных переменных эти предикаты принимают одинаковые значения. Равносильность называют также логической эквивалентностью. Например, эквивалентность предикатов P(n) = "n делится на 6" и R(n) = "n делится на 2 и n делится на 3" есть предикат V(n) = P(n)  R(n): "если n делится на 6, то n делится на 2 и на 3". Предикаты P(n) и R(n) логически эквивалентны. Наряду с логическими операциями важную роль играют операции, называемые кванторами. Квантор всеобщности есть операция, которая одноместный предикат P(x) превращает в высказывание: "все x обладают свойством P(x)". Знак квантора всеобщности "  ". Он заменяет выражения: "Для всех", "каждый", "любой" и т. п. Обозначение  x: P(x) читается так: "Для всех x таких, что P от x"… Например, P(x) = x > 0 , где x – вещественное число, есть предикат "x – положительное число". Тогда  x: P(x) есть высказывание "Каждое число положительно". Это ложное высказывание. Если же x – любое натуральное 88 число (x  N), то  x: P(x) есть выражение: "Каждое натуральное число положительно" – истинное высказывание. Квантор всеобщности есть обобщение серии конъюнкций единичных высказываний. Пусть M - множество очков, которое может выпасть при бросании игральной кости, т. е. M ={1, 2, 3, 4, 5, 6} и P(x) - предикат: "При бросании игральной кости один раз выпадает x очков", где x M. Применение квантора всеобщности позволяет вместо сложного высказывания P(1)  P(2)  P(3)  P(4)  P(5)  P(6) записать равносильное ему компактное высказывание  x: P(x), x  M: "При бросании игральной кости один раз может выпасть любое из шести первых натуральных чисел". Квантор существования есть операция, которая одноместный предикат P(x) превращает в высказывание: "Существует хотя бы один x из M, обладающий свойством P(x)". Знак квантора существования "  ". Он заменяет выражения: "Существует, хотя бы один", "найдется", "некоторый" и т. п. Обозначение  x: P(x) читается так: "Существует хотя бы один x такой, что P от x"… Например, P(x) – предикат: "x - студент", где x - элемент множества жителей Москвы. Тогда выражение  x: P(x) есть высказывание "хотя бы один житель Москвы является студентом". Квантор существования есть обобщение серии дизъюнкций единичных высказываний. Если задано множество M = {a1, a2, ..., an} и на нем определен предикат P(x), то P(а1)  P(а2)  ...  P(аn)  (  x  M): P(x). Кванторы обладают свойствами, являющимися аналогами законов де Моргана: (x : P  х )  х : P  х  , (x : P  х )  х : P  х  . С помощью кванторов можно выражать ряд часто используемых на практике отношений между множествами. Например, высказывание "Все объекты х из данного множества, обладающие свойством P(х), обладают также и свойством R(х)" формально можно записать так;  х: (P(х)  R(х)). Переход от P(х) к  х:P(х) или  х:P(х) называется квантификацией или связыванием переменной х. Связанная переменная фактически не является переменной, т.е. переход от  х: P(х) к  y:P(y) или от  х:P(х) к  y: P(y) не меняет истинности выражений. Навешивание переменной на многоместный предикат уменьшает в нем число свободных переменных и превращает его в предикат от меньшего числа переменных. Рассмотрим пример. На множестве чисел задан двухместный предикат P(х, y) = "число х делится на число y". Связывая одну переменную, можно получить следующие одноместные предикаты:  х: P(х, y) = "каждое число делится на y" - ложь;  x: P(x, y) = "существует число, которое делится на y"- истина;  y: P(х, y) = "число х делится на любое число" - ложь;  y: P(х, y) = "существует число, на которое делится х" - истина. 89 Связывая обе переменные данного предиката, получим высказывания:  х,  y:P(х, y) = "каждое число делится на любое число" – ложное высказывание,  х,  y:P(х, y) = "существует число, на которое делится любое число" – истина, т. к. такое число есть 1,  х,  y:P(х,y) = "существует число, которое делится на любое число" – истина, такое число ноль,  х,  y: P(х, y) = "существует число, которое делится на какое-нибудь число" – истинное высказывание. 7.5. Нечеткая логика Нечеткой высказывательной переменной А называется нечеткое высказывание А, степень истинности которого ( A) может меняться в интервале [0, 1], ( A) [0,1] . Нечеткое высказывание можно записать в виде упорядоченной пары ( A | ( A))  A и для сокращения записи такую пару обозначают A . Так как степень истинности нечеткого высказывания не связана с сутью высказывания, будем в дальнейшем отождествлять нечеткое высказывание с его степенью истинности аналогично тому, как обычное четкое высказывание отождествлялось с его истинностью или ложностью. На множестве нечетких высказываний вводятся логические операции, аналогичные операциям алгебры высказываний. 1. Отрицание нечеткого высказывания A : ( A)  1  ( A) 2. Конъюнкция нечетких высказываний A  B : ( A  B ) = min( (А), (В)). 3. Дизъюнкция нечетких высказываний A  B :  ( A  B ) = max( (А), (В)). 4. Импликация нечетких высказываний A  B : ( A  B )= max (1 –  (А),  (В)) 5. Эквивалентность нечетких высказываний A  B : ( A  B ) = min (max (1 –  (А), (В)), max ( (А), 1 – (В))), Старшинство операций определяется, как и в четкой логике. в порядке 1 – 5. Пример Найти степень истинности высказывания C  ( A  B)  ( A  ( A  B)) , если  (А) =0,8;  (В) =0,3. Порядок действий определяется старшинством операций и скобками. 1. A  B , ( A  B ) = min( (А), (В)) = min(0,8; 0,3) = 0,3. 2. A  B ,  ( A  B ) = max( (А), (В)) = max (0,8; 0,3) = 0,8. 3. A  ( A  B) , ( A  B )= max (1 –  (А),  (В)) 90 ( A  ( A  B) )= max (1 –  (А),  ( A  B )) = max(1-0.8, 0,3) = 0,3 4. C  ( A  B)  ( A  ( A  B)) ( ( A  B)  ( A  ( A  B) ) = min (max (1 – 0,8; 0,3), max (0,8; 1 – 0,3)) = = min(0,3; 0,8) = 0,3. Множество нечетких высказываний вместе с введенными на них операциями образуют алгебру нечетких высказываний. Нечеткой логической формулой называется: а) любая нечеткая высказывательная переменная; б) если (А| ( A) ) и (В | ( A) ) – нечеткие логические формулы, то A , A  B , A  B . A  B , A  B – тоже нечеткие логические формулы. Пусть x1, x2,..., xn нечеткие логические переменные, т. е. для каждой определена функция истинности ( xi ) , а A (x1, x2,..., xn) и B (x1, x2,..., xn) нечеткие логические формулы. Степенью равносильности формул A и B A B называется величина ( A, B)   повсем наборам AB Здесь логические операции конъюнкции и эквивалентности имеют смысл, определенный выше для логических операций над нечеткими высказываниями, причем конъюнкция берется по всем наборам степеней истинности (  1,  2, …,  n) нечетких переменных x1, x2,..., xn . Если ( A, B) = 0,5, то нечеткие формулы A и B называются индиффирентными. Если ( A, B) > 0,5, то нечеткие формулы A и B называются нечетко равносильными. Если ( A, B) < 0,5, то нечеткие формулы A и B называются нечетко неравносильными. Степенью неравносильности формул A и B называется величина ( A, B)  1  ( A, B) Множество всех наборов степеней истинности (  1,  2, …,  n) нечетких переменных (x1, x2,..., xn ) назовем полной областью определения Cn. Очевидно, что множество Cn имеет мощность континуума в отличие от 91 двузначной логики высказываний, где число всех наборов переменных конечно и равно 2n. Пример 1. Определить степень равносильности формул F1  X  Y и F2  X  Y при условии, что X и Y принимают значения степеней истинности из множества М1={0,2; 0,3}; М2 = 0,1; 0,6. Решение. Найдем декартово произведение множеств M 1 и M 2 M1  M 2  {(0.2;0.1);(0.2;0.6);(0.3;0.1);(0.3;0.6)} . равносильность проверяем на всех наборах декартова произведения. Действия запишем в виде таблицы M1  M 2 F1  X  Y max (1 –  ( X X ),  ( Y )) ( X )  1  ( X ) Y (Y )  1  (Y ) F2  X  Y min( ( X ), ( Y )) (0.2;0.1) max (1 – 0,2, 0,1) = 0,8 1-0,2= 0,8 0,9 0,8 (0.2;0.6) max (1 – 0,2, 0,6) = 0,8 1-0,2=0,8 0,4 0,4 (0.3;0.1) max (1 – 0,3, 0,1) = 0,7 1-0,3= 0,7 0,9 0,7 ( 0.3;0.6 ) max (1 – 0,3, 0,6) = 0,7 1-0,3= 0,7 0,4 0,4 F1 F2 ( F1  F2 ) = min (max (1 –  ( F1 ), ( F2 )), max ( ( F1 ), 1 – ( F2 ))), 0.8  0.8 = min(max(1 – 0,8; 0,8), max(0,8; 1 – 0,8)) = min(0,8;0,8)=0,8. 0.8  0.4 = min(max(1 – 0,8; 0,4), max(0,8; 1 – 0,4)) = 0,4. 0.7  0.7 = min(max(1 – 0,7; 0,7), max(0,7; 1 – 0,7)) = 0,7. 0.7  0.4 = min(max(1 – 0,7; 0,4), max(0,7; 1 – 0,4))= 0,4 . ( F1 , F2 )   повсемнаборам F1 F2  0.8  0.4  0.7  0.4  min(0.8, 0.4, 0.7)  0.4 ( F1, F2 )  1  ( F , B) =0.6 Следовательно, формулы F1 и F2 нечетко неравносильны. Пример 2 Определить степень равносильности формул A  X  Y , B  X  Y при условии, что X и Y принимают значения степеней истинности из множества М = {0,1; 0,2}. Найдем декартово произведение М ={(0,1; 0,1); (0,1; 0,2); (0,2; 0,1); (0,2; 0,2)} и определим степени истинности. 92 Вычислим формулы A  X  Y и B  X  Y на каждом из четырех наборов 1 ( A) = max (1 – 0,1; 0.1) = 0,9. 2 ( A) = max (1 – 0,1; 0,2) = 0,9. 3 ( A) = max (1 – 0,2; 0,1) = 0,8. 4 ( A) = max (1 – 0,2; 0,2) = 0,8. 1 ( B) = 1 – min( 0,1; 0.1) = 0,9. 2 ( B) = 1 – min(0,1; 0,2) = 0,9. 3 ( B) = 1 – min(0,2; 0,1) = 0,9. 4 ( B) = 1 – min (0,2; 0,2) = 0,8. Вычислим теперь степень равносильности формул A B Для этого сначала вычислим A B для всех наборов: ( A  B ) = min (max (1 –  (А), (В)), max ( (А), 1 – (В))) Поэтому 0.9  0.9 = min (max (1 – 0,9;0,9), max (0,9; 1 –0,9)) = 0,9. 0.9  0.9 = min (max (1 A – 0,9;0,9), max (0,9; 1 –0,9)) = 0,9. 0.8  0.9 = min (max (1 – 0,8;0,9), max (0,8; 1 –0,9)) = 0,8. 0.8  0.8 = min (max (1 – 0,8;0,8), max (0,8; 1 –0,8)) = 0,8. ( A, B)   A  B = 0.9  0.9  0.8  0.8 = min(0,9; 0,8) = 0,8. повсем наборам Формулы A и B нечетко равносильны. На других наборах степеней истинности нечетких переменных X и Y формулы A и B могут быть нечетко неравносильны. Пусть A (x1, x2,..., xn) и B (x1, x2,..., xn) – две нечеткие логические формулы, рассмотренные на некотором множестве M изменения нечетких переменных x1, x2,..., xn. Областью нечеткой равносильности формул A и B называется подмножество множества M, на котором формулы A и B нечетко равносильны. Вернемся к примеру 2. Для этого примера множество M состоит из девяти наборов: M = {{0,1; 0,1}; {0,1; 0,2}; {0,2; 0,1}; {0,2; 0,2}}. На каждом наборе формулы A и B нечетко равносильны, так как ( A, B) > 0,5. Поэтому областью нечеткой равносильности будет все множество M. Если формула A (x1, x2,..., xn) на всех наборах переменных x1, x2,..., xn из некоторого множества M имеет степень истинности большую или равную 0,5, то она будет на нем нечетко истинной. Обозначается это так: A  И . 93 Если формула A (x1, x2,..., xn) на всех наборах переменных x1, x2,..., xn из некоторого множества M имеет степень истинности меньшую или равную 0,5, то она будет на нем нечетко ложной. Обозначается это так: A  Л . Пример Покажем, что X  X  И переменной X , 0  ( X )  1: и X  X  Л для всех значений нечеткой ( X  X ) = max ( ( X ) , ( X ) )  0,5. ( X  X ) = min ( ( X ) , ( X ) )  0,5. Нечетким предикатом P (x1, x2, ... , xn) называется нечеткая формула, переменные которой определены на некотором множестве М, x1, x2, ... , xn  M, а сама она принимает значения из интервала [0, 1]. Нечеткий предикат от n переменных называется n-местным нечетким предикатом. Нечеткое высказывание A , задаваемое степенью истинности ( A) [0,1] является одноместным нечетким предикатом. Пример. Пусть М = {0, 1, 2, 3}, M  M  {(0,0);(0,1);(0, 2),.....(3,3)} . Зададим нечеткий предикат P( x, y)  P( x,0)  P(0, y)  0 ; P(1,1)  P(3, 2)  P(2,3)  xy . Его значения равны: 9 1 2 1 4 ; P(1, 2)  P (2,1)  ; P(2, 2)  ; P(3,1)  P (1,3)  ; 9 9 9 3 2 ; P(3,3) 1 . 3 Нечеткими кванторами  и  называются логические символы, которые придают включающим их выражениям следующий смысл:  xi P( x1 , x2 ,....xn )   xi P( x1 , x2 ,....xn )   P( x , x ,....x )  min P( x , x ,....x ) 1 xiM 2 n xiM 1 2 n  P( x , x ,....x )  max P( x , x ,....x ) xi M 1 2 n xi M 1 2 n Пример. Найдем значения степени истинности формул P( x,1) и P( x,1) для предыдущего примера: P( x,1) = min{ P (0, 1); P (1, 1); P (2, 1); P (3, 1)} = min{0; 1/9; 2/9; 1/3} = 0. P( x,1) = max { P (0, 1); P (1, 1); P (2, 1); P (3, 1)} = max {0; 1/9; 2/9; 1/3} = 1/3. 94 По аналогии с четкими предикатами вводятся также остальные понятия для нечетких предикатов. 8. Системы управления. Системный подход в исследовании систем управления Подведем итог. Системный подход представляет одну из форм методологического знания, связанную с исследованием и созданием объектов как систем, и относится только к системам (первый принцип системного подхода), т.е. это требование рассматривать совокупность элементов системы как одно целое. Второй принцип - это признание того, что свойства системы это не просто сумма свойств ее элементов. Тем самым постулируется возможность того, что система обладает особыми свойствами, которых может и не быть у отдельных элементов. Третий принцип системного подхода определяет иерархичность познания, требующую многоуровневое изучение предмета: изучение самого предмета - "собственный" уровень; изучение этого же предмета как элемента более широкой системы - "вышестоящий" уровень и, наконец, изучение этого предмета в соотношении с составляющими данный предмет элементами "нижестоящий" уровень. Четвертым принципом системного подхода является его нацеленность на получение количественных характеристик, создание методов, сужающих неоднозначность понятий, определений, оценок. Пятым принципом является нацеленность системного подхода на эффективность системы управления. Теоретически доказано, что всегда существует функция ценности системы — в виде зависимости ее эффективности (почти всегда это экономический показатель) от условий построения и функционирования. Другими словами, системный подход требует рассматривать проблему не изолированно, а в единстве связей с окружающей средой, постигать сущность каждой связи и отдельного элемента, проводить ассоциации между общими и частными целями. Все это формирует особый метод мышления, позволяющий гибко реагировать на изменения обстановки и принимать обоснованные решения. С учетом сказанного определим понятие системного подхода. Системный подход - это подход к исследованию объекта (проблемы, явления, процесса) как к системе, в которой выделены элементы, внутренние и внешние связи, наиболее существенным образом влияющие на исследуемые результаты его функционирования, а цели каждого из элементов определены исходя из общего предназначения объекта. Системные задачи могут быть двух типов: системного анализа и системного синтеза. 95 Задачи анализа - определение свойств системы по известной структуре, изучение свойств уже существующего образования. Задачи синтеза - определение структуры системы по ее свойствам, т.е. создание новой структуры, которая должна обладать желаемыми свойствами. Особенностью выделения объекта как системы из окружающей среды является то, что необходимо выбрать такие его элементы, деятельность или свойства которых проявляются в области исследования данного объекта. Необходимость выявления (либо создания) той или иной связи определяется степенью ее влияния на исследуемые характеристики: должны оставляться те, которые оказывают существенное влияние. В тех случаях, когда связи неясны, необходимо укрупнить структуру системы до известных уровней и проводить исследования в целях последующего углубления детализации до необходимого уровня. Не должны вводиться в структуру системы элементы, не имеющие связей с другими (описывающий систему граф должен быть связным). Сложные системы, как правило, исследуются на моделях. Целью моделирования является определение реакций системы на воздействия, границы функционирования системы, эффективность алгоритмов управления. Модель должна допускать возможность вариаций изменения количества элементов и связей между ними с целью исследования различных вариантов построения системы. Процесс исследования сложных систем носит итеративный характер, и число возможных приближений зависит от априорных знаний о системе и жесткости требований к точности получаемых результатов. Главная практическая задача системного подхода в исследовании систем управления состоит в том, чтобы, обнаружив и описав сложность, обосновать также дополнительные физически реализуемые связи, которые, будучи наложенными на сложную систему управления, сделали бы ее управляемой в требуемых пределах, сохранив при этом такие области самостоятельности, которые способствуют повышению эффективности системы. Включенные новые обратные связи должны усилить благоприятные и ослабить неблагоприятные тенденции поведения системы управления, сохранив и укрепив ее целенаправленность, но при этом ориентируя ее на интересы надсистемы. Критерии как модель целей Для количественной оценки степени достижения цели используются критерии. В этом смысле критерии можно рассматривать как количественные модели качественных целей. Критерии должны как можно полнее отражать цель. 96 Необходимость в критериях возникает при реализации задач управления, в частности, задач оптимизации и принятия решений, когда возникает необходимость оценки имеющихся альтернатив. Определение значения критерия для данной альтернативы является, по существу, косвенным измерением степени ее пригодности (ценности) как средства достижения цели. Реальные задачи многокритериальны, что связано не только с множественностью целей, но и с тем, что одну цель редко удается выразить одним критерием, хотя к этому обычно стремятся. Конечно, возможны случаи, когда единственный критерий отвечает требованиям практики. Пример. По стандартам ЮНЕСКО уровень медицинского обслуживания оценивается по уровню детской смертности. Такие случаи очень редки. Критерий лишь приближенно (как и всякая модель) отображает цель, и адекватность одного критерия может оказаться недостаточной. При этом следует помнить о том, что дело не только и не столько в количестве критериев, сколько в том, чтобы они достаточно полно "покрывали" цель. Это означает, что критерии должны описывать по возможности все важные аспекты цели, но при этом желательно минимизировать число необходимых критериев. Для достижения полноты модели рассматриваемой ситуации кроме критериев необходимо учитывать имеющиеся ограничения. Дело в том, что решение любой реальной задачи сталкивается с ограничениями, которые можно разделить на: объективные — законы природы и ресурсные ограничения; субъективные — связанные с системой ценностей. Целевой критерий как бы открывает возможности для выдвижения все новых и новых альтернатив в поисках лучшей из них, а ограничение заведомо уменьшает их число, запрещая некоторые из альтернатив. Одними целевыми критериями можно жертвовать ради других, а ограничение исключить нельзя, оно должно жестко соблюдаться. В этом смысле ограничения упрощают, а не усложняют работу системного аналитика. В практике системного анализа встречаются случаи, когда наложенные ограничения столь сильны, что делают нереальным достижение цели. Тогда системный аналитик должен ставить перед лицом, принимающим решение, вопрос о том, нельзя ли данные ограничения ослабить или снять совсем. 97 Учебная литература 1. Мещерякова Г. П., Бочкарев В. Б., Крылов А. В. Дискретная математика. Множества. Логика. Графы. - СПб.: СПбГУПТД, 2015. http://publish.sutd.ru/ tp_ext_inf_publish.ph p?id=3359 2. Данелян Т. Я. Теория систем и системный анализ. – М.: Евразийский открытый институт, 2011. http://www.iprbooksh op.ru/10867.html 3. Шапошников А. В., Бережной В. В., Лягин А. М., Плетухина А. А. Теория систем массового обслуживания. Ставрополь: Северо- Кавказский федеральный университет обслуживания, 2017. http://www.iprbooksh op.ru/75605.html Дополнительная литература 1. Силич В. А., Силич М. П. Теория систем и системный анализ. - Томск: Томский государственный университет систем управления и радиоэлектроники, 2011. http://www.iprbooksh op.ru/13987.html 2. Бернштейн Т. В., Храмова Т. В. Практикум по дискретной математике. Новосибирск: Сибирский государственный университет телекоммуникаций и информатики, 2014. http://www.iprbooksh op.ru/55492.html Вспомогательная литература. 1. В. Ф. Пономарев. Дискретная математика для инженеров. Учебное пособие для ВУЗов. - М.: Горячая линия – Телеком, 2009.. – 322 с. 2. Ю. И. Галушкина, А. Н. Марьямов. Конспект лекций по дискретной математике. С упражнениями и контрольными работами. - М.: Айрис-Пресс, 2007. 3. В. В. Тишин. Дискретная математика в примерах и задачах. – СПб.: БХВПетербург, 2008. 4. Ф. А. Новиков Дискретная математика: Учебник для вузов. Стандарт третьего поколения. – СПб.: Питер, 2011. – 384 с. 5. Г. П. Гаврилов, А. А. Сапоженко. Задачи и упражнения по дискретной математике. Учебное пособие. – М.: ФИЗМАТЛИТ, 2009. – 416 с. 6. Р. Хаггарти Дискретная математика для программистов. – М.: Техносфера, 2005. – 400 с. 7. http://www.iprbookshop.ru/10660.html — Ковалѐва Л.Ф. Дискретная математика в задачах 98 8. http://www.iprbookshop.ru/10661.html — Балюкевич Э.Л. Дискретная математика (содержит контрольные задания по темам «множества», «логика», «графы») 9. http://www.iprbookshop.ru/66149.html — Веретенников Б.М. Дискретная математика (содержит развѐрнуто тему «бинарные отношения» и задачи на неѐ) 10. http://www.iprbookshop.ru/67472.html — Кривцова И.Е. Основы дискретной математики (содержит теорию с доказательствами теорем по множествам, соответствиям, бинарным отношениям) 99