Теория бинарных отношений

Задание на оформление Отчета о лекциях 1. Изучить материал Лекции (Номер) из раздела ЛК. 2. Выбрать тему самостоятельной работы. 3. Использовать материал Лекции. 4. Собрать материал из Интернета. 5. Оформить материал согласно Отчету о Лекции из раздела ЛК. 6. Положить Отчет в ЛК, указав в комментарии Лекцию (Номер). Полная копия принятого Отчета не принимается. Лекция 1 I. Теория бинарных отношений 1. Множество – фундаментальное, базисное понятие в математике. Большинство понятий основаны на понятии множества. Для построения и описания множества используется характеристическая функция. Характеристическая функция множества является отображением его на единичный интервал Если , то , иначе . Это подход Г. Кантора. Подход Л. Заде использует весь заданный интервал. Если , то с уверенностью 50%. Можно сказать, что нечеткий элемент множества Х. Если Ӿ - множество нечетких элементов, то говорят о нечетком множестве Ӿ как подмножестве множества Х. 2. Декартово произведение множеств – одна из важных операций над множествами. Для двух множеств Х и Y можно построить декартово, или прямое произведение . Здесь Х – множество с характеристической функцией µх и Y множество с характеристической функцией µy. Тогда получим описание декартова произведения . Это означает, что декартово произведение есть множество всех возможных пар элементов исходных множеств. Если мощность множества Х есть card(X), a мощность множества Y есть card(Y), то мощность декартова произведение будет card(D)= card(X) ∙ card(Y). Пример 1. Декартово произведение множества X={x1, x2, x3} и множества Y={y1, y2}. . Мощности card(X)=3, card(Y)=2, card(D)=3∙ 2=6. Графическая интерпретация в виде соответствующего графа имеет следующий вид Обобщение на n множеств осуществляется естественным образом 3. Понятие бинарного отношения опирается на понятие множества. Для двух множеств Х и Y можно построить бинарное отношение как собственное подмножество их декартова произведения . Значит, бинарное отношение есть множество выбранных из декартова произведения пар элементов . Если X=Y, то бинарное отношение называется однородным . Пример 2 . Множество пар четных натуральных чисел, у которых первое число меньше второго числа Первая проекция бинарного отношения Вторая проекция бинарного отношения Сечение по бинарного отношения Если Pr1ρ=X и Pr2 ρ=Y, то бинарное отношение плотное. Обобщение на n исходных множеств следующее 4. Способы задания бинарных отношений: - Перечисление элементов Пример 2. Бинарное отношение для множеств из Примера 1 . - Таблица отношения Y X y1 y2 . . . x1 µ11 µ12 . . . x2 µ21 µ22 . . . . . . . . . . . . . . . Таблица отношения для Примера 1 Y X y1 y2 x1 1 x2 1 1 х3 1 - Граф отношения G (V, R), Здесь V ̶ множество вершин для плотных отношений, R – множество ребер между выбранными вершинами. Граф отношения для Примера 2 Использовано 4 ребра из 6 возможных ребер. - Использование сечений Pr1ρ x1 x2 . . . Y \ ρ Scx1 ρ Scx1 ρ . . . Здесь под обозначением Y \ ρ понимают фактор-множество Y по ρ, так как его элементами являются сечения, или подмножества этого множества. Обобщение способов описания n-арных отношений возможно для перечисления выбранных n-ок и построения соответствующих графов. Табличный способ использовать нельзя, а применение сечений выглядит достаточно громоздко. Пример 3. Тернарное отношение трех множеств X1={x11, x12}, X2={x21, x22, x23}, X3={x31, x32}. Очевидно, что card(X1)=2, card(X2)=3, card(X3)=2, card(D)=2∙3∙2=12. Тернарное отношение - Перечисление выбираемых троек - Граф тернарного отношения - Сечения для тернарного отношения X1 x11 x12 X2 \ ρ { x21} { x22, x23} X3 \ ρ { x31} { x31 ,x32} {x32} Фактор-множество X2 \ ρ состоит из двух сечений, а фактор-множество X3 \ ρ состоит из трех сечений. 5. Операции над бинарными отношениями: - Классические операции - объединение двух бинарных отношений для двух множеств с получением всех пар из исходных отношений. - пересечение двух бинарных отношений для двух множеств с получением общих пар исходных отношений. - дополнение одного бинарного отношения с получением пар из разности D \ ρ1. - Специальные операции - симметризация одного бинарного отношения с получением симметричных пар - композиция двух бинарных отношений с характеристической функцией выбора графическая интерпретация множество Z как композиционное множество исчезает в композиции отношений. - латинская композиция двух указанных бинарных отношений приводит к тернарному отношению Из одного исходного бинарного отношения можно построить однородное бинарное отношение Множество Y оказывается композиционным. Существуют составные композиции. II. Общая теория абстрактных систем 1. Основы общей теории абстрактных систем были опубликованы в работах известного специалиста в области системотехники М. Месаровича. Он ввел понятие формального объекта как правильного высказывания на математическом или естественном языке. Тогда множество формальных объектов имеет характеристическую функцию, которая определяет правило выбора таких высказываний из универсального множества высказываний. Если имеется n множеств формальных объектов Xi, i=1. . .n, то абстрактной системой называется n-арное отношение этих множеств Характеристическая функция μs определяет правило выбора n-ок в S из декартова произведения множеств формальных объектов. Значит, элементом абстрактной системы является n-ка из формальных объектов . Число n в n-арном отношении называют порядком абстрактной системы S. Удобно задавать систему графом. Пример 1. Система 3-го порядка с множествами формальных объектов X1={x11, x12}, X2={x21, x22, x23}, X3={x31, x32}. Этот граф задает конкретную реализацию системы 3-го порядка S1. Другая реализация S2 этой системы может быть задана графом Естественно считать, что система должна быть задана плотной, чтобы исключить свободные формальные объекты. Число реализаций такой системы . Для системы Примера 1 получим NS < 12. 2. Характеристики системы S n-го порядка включает следующие понятия - первая проекция , так как система плотная; - общего вида проекция определяет формальные объекты из множеств Xi, …, Xj, участвующие в n-ках системы; - сечение S по формальному объекту xij из Xi показывает формальные объекты, связанные с формальным объектом xij из Xi - общего вида сечение по подмножеству формальных объектов показывает формальные объекты, связанные в n-ках системы с формальными объектами выбранного подмножества. Построим предлагаемые характеристики системы, приведенной в первой реализации Примера 1. Пример 2. Первая проекция имеет вид Pr1S={x11, x12}=X1. Вторая_Третья проекция имеет вид и включает пары, участвующие в тройках системы. Сечение по формальному объекту x12 включает пару формальных объектов из X2X3, связанную с формальным объектом x12. 3. Сложность абстрактной системы была введена В. Костюком. В сборнике трудов по теории систем им была опубликована статья, в которой для абстрактной системы Месаровича предложена формула оценки сложности системы S . Здесь в больших скобках логарифма записано число сочетаний из N по NS. Если логарифм вычисляется по основанию 2, то сложность C(S) измеряется в битах. При достаточно большой мощности декартова произведения N применяется аппроксимация Стирлинга . Примем NS =10 и N=100, получим по Костюку C(S)=44 бит, по Стирлингу C(S)=47 бита. Разница в 3 бита очевидна. Рассмотрим предельные случаи оценки сложности системы - Вырожденная, минимальная система NS = 0 → C(S)=0 - Вырожденная, максимальная система NS = N → C(S)=0, Для средней системы получим максимальную сложность: NS = N/2 → C(S)=N. Значит, для сложности системы справедливы неравенства Пример 3. Оценить сложность двух реализаций системы из Примера 1. Для первой реализации получим Для второй реализации получим Максимальная сложность могла бы быть C(S)=12 бит. Сложность элементарной системы n-го порядка, имеющей соответствующие для элементарной системы характеристики может быть оценена для двух значений мощности соответствующего декартового произведения 4. Система Вход-Выход имеет два множества формальных объектов. Первыми формальными объектами служат входы, из которых строится множество входов U с характеристической функцией μX. Вторыми формальными объектами служат выходы, из которых строится множество выходов Y с характеристической функцией μY. Тогда, следуя определению абстрактной системы Месаровича, получим для системы Вход-Выход следующую формулу . Множество получаемых пар определяет характеристику вход-выход системы. Сама система имеет порядок 2 и является, в этом смысле, простой абстрактной системой. Если card(U)=card(Y)=2, выполняется условие плотности системы, а все сечения одноточечные, то получим простую, элементарную систему 2-го порядка с двумя реализациями S1={(u1,y1),(u2,y2)}, S2={(u1,y2),(u2,y1)}. Сложность обеих реализаций одинакова и составляет 2.6 бита. Пример 4. Дешифратор как система Вход-Выход. Множество входов двух разрядного дешифратора – U={0,1}, множество выходов –Y={0,1,2,3}. Получим абстрактную систему 3-го порядка, так как дешифратор двух разрядный, и множество входов приходится использовать дважды Описание дешифратора сделаем перечислением четырех троек S={(0,0;0), (1,0;1), (0,1;2), (1,1;3)} Оценка сложности дешифратора как абстрактной системы 3-го порядка Система Вход-Выход может иметь порядок 3 за счет повторения множества выходов . Это означает появление обратной связи в системе, так как выход обратно связывается с входом. Для простой, элементарной системы 3-го порядка c обратной связью получим две реализации S1={(y1,u1,y1),(y2,u2,y2)}, S2={(y1,u1,y2),(y2,u2,y1)}. Таким образом, образом общая теория систем – это полезный инструмент системотехника, дающий возможность на стадии системотехнической разработки конкретной системы изучить ее общие характеристики. Темы для самостоятельной работы I 1. Характеристика понятия множества. 2. Характеристическая функция множества. 3. Построение множества с помощью характеристической функции. 4. Характеристика понятия декартова произведения множеств. 5. Построение декартова произведения множеств. 6. Характеристика понятия бинарного отношения. 7. Способы задания бинарного отношения. 8. Графы как бинарные отношения. 9. Таблицы как бинарные отношения. 10. Построение бинарного отношения. 11. Операции над бинарными отношениями. 12. Построение составных операций над бинарными отношениями. 13. Обобщение понятия бинарное отношение. 14. Построение n-арного отношения. 15. Способы задания n-арного отношения. 16. Операции над n-арными отношениями. 17. Построение проекций n-арного отношения. Темы для самостоятельной работы II 1. Теория абстрактных систем Месаровича 2. Общая теория абстрактных систем 3. Основы системотехники 4. Понятие абстрактной системы Месаровича 5. Абстрактная система n-го порядка 6. Характеристики абстрактных систем 7. Абстрактная система и ее характеристики 8. Оценка сложности абстрактной системы 9. Система Вход-Выход как абстрактная система 10. Характеристики системы Вход-Выход 11. Методы описания абстрактных систем 12. Понятие сложности абстрактной системы 13. Характеристика теории абстрактных систем 14. Общая теория абстрактных систем в системотехнике 15. Применение теории абстрактных систем при принятии решений 16. Принятие решений в системотехнике Лекция 2 I. Абстрактная система Вход-Выход 5. Система Вход-Выход имеет два множества формальных объектов. Первыми формальными объектами служат входы, из которых строится множество входов U с характеристической функцией μX. Вторыми формальными объектами служат выходы, из которых строится множество выходов Y с характеристической функцией μY. Тогда, следуя определению абстрактной системы Месаровича, получим для системы Вход-Выход следующую формулу . Множество получаемых пар определяет характеристику вход-выход системы. Сама система имеет порядок 2 и является, в этом смысле, простой абстрактной системой. Если card(U)=card(Y)=2, выполняется условие плотности системы, а все сечения одноточечные, то получим простую, элементарную систему 2-го порядка с двумя реализациями S1={(u1,y1),(u2,y2)}, S2={(u1,y2),(u2,y1)}. Сложность обеих реализаций одинакова и составляет 2.6 бита. 6. Рассмотрим конструирование системы Вход-Выход, используя две базисные системы cо специальным композиционным множеством Х, так называемых состояний по Л. Заде. Первая система считается подсистемой Вход-Состояние системы Вход-Выход, вторая система – ее подсистемой Состояние-Выход. Выполняя латинскую композицию этих подсистем, получим характеристику Вход-Состояние-Выход, а композиция этих подсистем дает характеристику Вход-Выход Роль композиционного множества в указанных операциях выполняет множество состояний Х. В работах Л. Заде указывалась именно такая роль предложенного им понятия состояния систем управления. Пример 1. Из двух элементарных подсистем Вход-Состояние и Состояние-Выход сконструировать систему Вход-Выход. Характеристика Вход-Состояние-Выход Характеристика Вход- Выход = Полученные результаты дают возможность разработчику систем получить общее описание будущей системы, используя минимальную информацию о ней. II. Динамическая система 1. Понятие управляющей динамической системы строится на основе абстрактной системы Вход-Выход. Все формальные объекты такой системы являются переменными, меняющимися в дискретном времени 2. Математическая модель динамической системы представлена в виде рекуррентных уравнений состояний системы: Здесь x(t) – вектор состояний системы, y(t) – вектор выходов системы, u(t) – вектор входов системы, t – дискретное время. Системные матрицы: • A – (n×n)-матрица коэффициентов, • B – (n×m)-матрица входов, • C – (s×n)-матрица выходов, • D - (s×m)-матрица обхода. Пример. Балансовая система (БС) имеет два состояния с переменными х1(t), х2(t), причем потери в каждом состоянии составляют a∙хi(t). Регулятор БС находится в начале первого состояния, а Измеритель БС в конце второго состояния. Данные из второго сосояния полностью передается в объект управления (ОУ). Уравнения состояния БС строятся на основе баланса: х1(t+1) = х1(t) – a∙ х1(t) – х1(t) + u(u), х1(0) х2(t+1) = х2(t) – a∙ х2(t) –х2(t) + х1(t), х2(0) y(t) = х2(t) Матрицы БС: При увеличении числа состояний растут размеры матриц. 3. Анализ динамических характеристик системы в общем виде строится следующим образом. a. Устойчивость Линейная динамическая система устойчива, если устойчиво решение ее однородного рекуррентного уравнения, т.е. R(A) < 1. Степень устойчивости – это r = 1 - R(A). Если R(A) < 1, или r > 0, то система устойчива. Если R(A) >1, или r < 0, то система неустойчива. Если R(A) =1, или r = 0, то система нейтральна. У нейтральной системы существует нетривиальное, стационарное решение. b. Управляемость Линейная динамическая система управляема, если существует программа управления, которая переводит систему из заданного начального состояния в заданное конечное состояние. Критерий управляемости: rank(G)=n, где матрица управляемости G=[B, A∙ B, A2 ∙B, …, An-1 ∙B]. c. Наблюдаемость Линейная динамическая система наблюдаема, если по результатам измерений входов и выходов можно оценить состояния системы. Критерий наблюдаемости: rank (H) =n, где матрица наблюдаемости H= [C’, A’∙ C', A’2 ∙C’, …, A’(n-1) ∙C’]. d. Реакция на произвольное входное воздействие Вход системы задан на интервале [0, t]. Выход системы рассчитывается по формуле: Произведение C∙Aj∙B называют марковским параметром Мj. Тогда можно получить формулу: . Марковские параметры вычисляют как элементы произведения М = H’∙G. 4. Анализ динамических характеристик БС при потерях а = 0.1 a. Устойчивость Спектральный радиус матрицы коэффициентов трубы R(A)=0.1, следовательно, труба – устойчивый объект. b. Управляемость Матрица управляемости трубы: Определитель этой матрицы равен 1, следовательно, ранг ее равен 2. По критерию управляемости труба управляема. Значит, с помощью КПА ее можно заполнить до любого давления. c. Наблюдаемость Матрица наблюдаемости трубы: Определитель этой матрицы равен -1, следовательно, ранг ее равен 2. По критерию наблюдаемости труба управляема. Значит, с помощью одного манометра на втором участке можно рассчитать давление в первом участке. d. Реакция на постоянную работу КПА Матрица марковских параметров: Работа КПА: u(0)=1, u(1)=1, u(2)=1. Показания манометра при пустой трубе в начале работы КПА: Аналогичный анализ проводится для любых динамических объектов, имеющих балансовую схему работы. Темы самостоятельной работы I 17. Абстрактная система 2-го порядка 18. Система Вход-Выход как абстрактная система 19. Характеристики системы Вход-Выход 20. Характеристика Вход-Выход системы 2-го порядка 21. Характеристика Вход-Состояние-Выход системы 3-го порядка 22. Конструирование системы Вход-Выход 23. Конструирование системы Вход-Выход со специальным, композиционным множеством состояний 24. Конструирование системы Вход-Выход из элементарных подсистем 25. Понятие состояния системы Вход-Выход 26. Состояния системы по Л. Заде Темы самостоятельной работы II 1. Понятие управляющей динамической системы 2. Математическая модель дискретной динамической системы 3. Балансовая дискретная динамическая система 4. Системные матрицы динамической системы 5. Анализ динамических характеристик системы 6. Критерий устойчивости дискретной динамической системы 7. Критерий управляемости дискретной динамической системы 8. Критерий наблюдаемости дискретной динамической системы 9. Реакция на произвольное входное воздействие дискретной динамической системы 10. Критерий устойчивости балансовой дискретной динамической системы 11. Критерий управляемости балансовой дискретной динамической системы 12. Критерий наблюдаемости балансовой дискретной динамической системы 13. Реакция на произвольное входное воздействие балансовой дискретной динамической системы 14. Анализ динамических характеристик балансовой дискретной динамической системы Отчет о Лекции Титульный лист 1. Выбранная тема самостоятельной работы 1.1. Тема Лекции Краткое содержание лекции 1.2. Название пункта Материал пункта 1.2 1.3. И т.д. Материал пункта 1.3 И т.д. 3. Выводы Приводятся результаты и свое отношение к материалу. 4. Список источников Замечания 1. Отчет кладется в ЛК 2. Источники в Лекции и Интернете 3. Ссылки на Источник по стандарту 4. Первая копия принятого Отчета оценивается меньше оригинала. 5. Остальные копии не принимаются