Введение в анализ, синтез и моделирование систем

Гибкость системы будем понимать как способность к структурной адаптации системы в ответ на воздействия окружающей среды.

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

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

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

Для формализации фактов в системном анализе (как и в математике, информатике и других науках) используется понятия "отношение" и "алгебраическая структура".

Отношение r, определенное над элементами заданного множества Х, - это некоторое правило, по которому каждый элемент хХ связывается с другим элементом (или другими элементами) уХ. Отношение r называется n-рным отношением, если оно связывает n различных элементов X. Множество пар (х,у), которые находятся в бинарном (2-рном) отношении друг к другу, - подмножество декартового множества X×Y. Отношение r элементов хХ, yY обозначают как , r(x,y) или r(X,Y).

Пример. Рассмотрим классическую схему ЭВМ из устройств: 1 - ввода, 2 - логико-арифметическое, 3 - управления, 4 - запоминающее, 5 - вывода. Отношение "информационный обмен" определим так: устройство i находится в отношении r с устройством j, если из устройства i в устройство j поступает информация. Тогда можно это отношение определить матрицей R отношений (наличие r на пересечении строки i и столбца j свидетельствует о том, что устройство i находится в этом отношении с устройством j, а наличие - об отсутствии между ними этого отношения):

R = r r r r

    r r r

      r  

Отношение, задаваемое фразой "для каждого хХ" обозначается xX и называется квантором общности, а отношение "существует хХ" имеет обозначение хХ и называется квантором существования. Факт того, что элементы хХ связаны, выделены некоторым отношением r, обозначают как Х={х: r} или Х={х|r}.

Композиция (произведение) r=r1o r2. отношений r1 и r2, заданных над одним и тем же множеством Х, - это третье отношение r, определяемое правилом:

Отношение r называется отношением 1) тождества; 2) рефлексивным; 3) mpанзитивным; 4) симметричным; 5) обратным к отношению s, если, выполнены, соответственно, условия

Пример. Бинарное отношение равенства чисел "=" - рефлексивное (так как x=x), симметричное (так как x=y => y=x), транзитивное (так как x=>y, y=>z => x=>z). Бинарное отношение "иметь общий делитель" - рефлексивное, симметричное, транзитивное (проверить). Бинарное отношение вложенности множеств "" - рефлексивное, антисимметричное, транзитивное (проверить).

Частично упорядоченной по отношению r системой Х называется система, для которой (т.е. для любых элементов которой) задано отношение r(Х), являющееся транзитивным, несимметричным, рефлексивным.

Упорядоченная по отношению r(Х) система - система Х, такая, что x, yX, либо , либо .

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

Пример. Пусть N - множество натуральных чисел. Отношение r(x,y): "x кратно y" определенное на N, как легко проверить, является отношением частичного порядка. Отношение r(x,y): "xy" определенное на множестве действительных чисел R, - отношение частичного порядка и полного порядка. Отношение r(x,y): "x<y" определенное на R не является отношением полного порядка (не рефлексивно). Отношение вложенности множеств "xy" - отношение частичного упорядочивания множеств, определенное на множестве всех множеств, но оно не является отношением полного порядка (не для любых двух множеств имеет место включение в ту или иную сторону).

Теперь можно дать и формализованное определение понятия структуры.

Структурой, определенной над множеством (или на множестве) Х называется некоторое отношение над Х типа упорядочивания. Более формальное, математическое определение: структура (решетка) - частично упорядоченное множество X, для которого любое двухэлементное подмножество {х,у} из Х имеет наибольший или наименьший элемент (супремум или инфинум).

Таким образом, систему можно понимать как целостный комплекс (кортеж) объектов S = <A, R>, А = {а}, R = {r), где r - отношение над А, A - произвольное множество элементов. Такая система называется замкнутой системой. В замкнутых системах важная характеристика функционирования системы - внутренняя структура системы. Замкнутые системы - абстрактный продукт, продукт мышления, логического построения. Они ограничены ("замкнуты") уровнем их теоретического рассмотрения.

Если Y - множество элементов внешней (по отношению к А) среды С, а в С определены отношения r над C, то тогда кортеж S = <A,Y,R> задает, определяет открытую систему. В открытых системах важной характеристикой функционирования является обмен системы ресурсами (одного или нескольких типов) с другими системами, с окружающей средой, а также характер этого обмена.

Транзитивное, рефлексивное, симметричное отношение называется отношением эквивалентности. Отношение эквивалентности r(Х) разбивает множество систем Х на классы или классы эквивалентности - непустые и непересекающиеся множества систем, каждое из которых вместе с любым своим элементом содержит также все элементы X, эквивалентные ему по отношению r(Х), и не содержит других xХ.

Теорема. Два класса эквивалентности над одним и тем же множеством не пересекаются. Если два элемента x,yX не связаны отношением эквивалентности r(x,y), определенным на Х, то классы эквивалентности по этим элементам не пересекаются. Если на множестве X задано отношение эквивалентности r(x,y), x,yX, а Xx, Xy - классы эквивалентности по x, y соответственно, то Xx=Xy.

Пример. Отношение между x, y, выражаемое равенством x = y+ka, x, y, k, aZ, называется отношением сравнения x и y по модулю a и записывается как x = y (mod a). Это отношение является отношением эквивалентности:

1. x = x (mod a), k=0 (рефлексивность);

2.       x = y (mod a) => x = y+ka => y = x+(-k)a => y = x (mod a) (симметричность);

3.       x = y(mod a), y = z(mod a) => x = y+ka, y = z+ma => x = z+(k+m)a => x=z(mod a) (транзитивность).

Множество целых чисел Z разбивается этим отношением на k классов:

X0={x: x=ka, k, aZ},

X1={x: x=1+ka, k, aZ},

X2={x: x=2+ka, k, aZ},

. . .

Xk-1 = {x: x=k-1+ka, k, aZ}.

В частности, при k=2 происходит разбиение множества Z на множество X0 - четных и множество X1 - нечетных чисел; при k=3 - множество Z разбивается на классы X0 - кратные 3, X1 - дающие при делении на 3 остаток 1, Х2 - дающие при делении на 3 остаток 2.

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

Можно также говорить об "ослабленном" типе эквивалентности - эквивалентности по цели (элементам, структуре).

Пусть даны две эквивалентные системы X и Y и система X обладает структурой (или свойством, величиной) I. Если из этого следует, что и система Y обладает этой структурой (или свойством, величиной) I, то I называется инвариантом систем X и Y. Можно говорить об инвариантном содержании двух и более систем или об инвариантном погружении одной системы в другую. Инвариантность двух и более систем предполагает наличие такого инварианта.

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

Соответствие S - бинарное отношение r над множеством X×Y:

Обратное соответствие к r - это соответствие S-1Y×X вида

Отношения часто используются при организации и формализации систем. При этом для них (над ними) вводятся следующие основные операции:

1. объединение двух отношений r1(x1, x2, ..., xn), r2(x1, x2, ..., xn), заданных над множеством X, есть третье отношение r3(X)=r1 r2 получаемое как теоретико-множественное объединение всех элементов X, для которых справедливо r1 или r2;
2. пересечение - r3(X)=r1 r2 - теоретико-множественное пересечение всех элементов из X, для которых справедливы r1 и r2;
3. проекция отношения r1(Х) размерности k, т.е. отношения r1=r1(x1, x2,..., xk), связывающего элементы x1, x2, ..., xkX (это могут быть и не первые k элементов), - это отношение r2 размерности m<k, т.е. оно использует некоторые из аргументов (параметров) исходного отношения;
4. разность двух отношений r1(x1, x2, ..., xk), r2(x1, x2, ..., xk) - это отношение r3=r1 - r2, состоящее из всех тех элементов X, для которых справедливо отношение r1, но не справедливо отношение r2;
5. декартово произведение двух отношений r2(x1, x2,..., xk) и r1(xn+1, xn+2,..., xn+m) - отношение r3=r1×r2, составленное всевозможными комбинациями всех элементов X, для которых справедливы отношения r1, r2; первые n компонентов отношения r3 образуют элементы, для которых справедливо отношение r1, а для последних m элементов справедливо отношение r2;
6. селекция (отбор, выборка) по критерию q компонентов, принадлежащих отношению r; критерий q - некоторый предикат.

Алгебры отношений часто называют реляционными алгебрами.

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

Алгеброй A=<X, f> называется некоторая совокупность определенных элементов X, с заданными над ними определенными операциями f (часто определяемые по сходству с операциями сложения и умножения чисел), которые удовлетворяют определенным свойствам - аксиомам алгебры.

Операция f называется n-местной, если она связывает n операндов (объектов - участников этой операции).

Совокупность F={f} операций алгебры A называется ее сигнатурой, а совокупность элементов X={x} - носителем алгебры.

Алгеброй Буля называется алгебра с введенными в ней двумя двухместными операциями, которые поименованы, по аналогии с арифметикой чисел, сложением и умножением, и одной одноместной операцией, называемой штрих-операцией или инверсией, причем эти операции удовлетворяют аксиомам (законам) алгебры Буля:

1. коммутативности - х+у = у+х, ху = ух;
2. ассоциативности - (х+у)+z = х+(у+z), (xy)z = x(yz);
3. идемпотентности - х+х = х, xx = x;
4. дистрибутивности - (x+y)z = xz+yz, xy+z = (x+z)(y+z);
5. инволюции (двойной инверсии) - ;
6. поглощения - x(x+y) = x, x+xy = x;
7. де Моргана - x+y = xy, xy = x+y
8. нейтральности: x(y+y) = x, x+yy = x.
9. существования двух особых элементов (называемых "единица -1" и "нуль-0"), причем 0 = 1, 1 = 0, x+x = 1, xx = 0.

Группоид - алгебра A=<X, f> с одной двухместной операцией f.

Полугруппа - группоид, в системе аксиом которой есть аксиома ассоциативности. Поэтому она называется ассоциативным группоидом.

Пример. Пусть Х={x1, x2, ..., xn} - некоторый алфавит. Тогда он образует полугруппу относительно операции конкатенации слов из S(X). В таких (называемых свободными) полугруппах рассматривается одна из важнейших алгебраических проблем информатики в полугруппах - проблема тождества слов: указать конструктивный процесс установления совпадения двух слов из полугруппы S(X). Эта проблема алгоритмически неразрешима и встречается, например, при разработке архитектуры процессора.

Группа - полугруппа с единицей (с элементом е: еа=ае=а), в которой бинарная операция f является однозначно обратимой, т.е. на этом множестве (на его носителе) разрешимы однозначно уравнения вида xfa=b, afx=b.

Пример. Пусть Х={x1, x2, ..., xn} - некоторая свободная полугруппа. Каждому из хi, i=1, 2,..., n сопоставим его обратный элемент xi-1, а единицу положим равной пустому слову . Тогда Х образует (свободную) группу, если в качестве критерия разрешимости уравнений выбрать соотношения: xixi-1=, xi-1xi=. Одна из важнейших алгебраических проблем информатики в группах - проблема изоморфизма (преобразования с сохранением групповой операции) двух групп: указать конструктивный процесс установления такого преобразования одной группы к другой. Эта проблема возникает при обработке информации, преобразовании одной информационной системы к другой с сохранением информации.

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

Поле - кольцо, у которого все ненулевые элементы по одной из операций образуют абелеву группу.

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

Изоморфизм двух упорядоченных (по отношению r) множеств X и Y - такое взаимно-однозначное соответствие f : X Y, где из того, что x1X и x2X находятся в отношении r следует, что y1=f(x1) и y2=f(x2) находятся в отношении r и наоборот.