Дискретно-непрерывная математика (стр. 61 )

Определение. Набор элементов а1, ....., ап будем называть трансверсалью относительно отношения R, если выполнено условия:

1. ті(аі) > 0 для всех і = 1, ...., п,

2. аі аj(mod R) при і 1 j

Вопрос о существовании трансверсали семейства нечетких множеств относительно отношения R решает следующее утверждение.

Теорема 6. Для семейства нечетких множеств X1,...., Хп и отношения эквивалетности R существует трансверсаль в том и только в том случае, когда выполнены условия: функция ту (х) для Y =Хі1 Ė ... Ė Хik отличная от нуля не менее, чем на k классах Y/R для всех k = 1,....., n, и всех 1 i1 <.....< ik n.

Доказательство проводится по той же схеме, что и доказательство теоремы 1.

Перейдем теперь к вопросу о числе систем различных представителей семейства нечетких множеств и отношения эквивалентности R.

Определим матрицу инциденций Р семейства X1 ,.... Хп и отношения эквивалентности R. Строки матрицы Р соответствуют множествам X1 .... Хп , т. е. функциям т1 , ..... , тп, а столбцы - классам эквивалентности множества X = Х1 Ė ... Ė Хп по отношению R. Пусть это классы C1, ....., Cq. Множеству Xі и классу Сj ставим в соответствие число tіj элементов множества Xі, которые лежат в классе Сj и для которых выполнено ті(хj)>0, хj Î Сj (если таких элементов нет - ставим нуль). Справедлива следующая теорема.

Теорема 7. Число трансверсалій семейства нечетких множеств

Х1 .... Хп и отношение эквивалентности R равно перманенту соответствующей матрицы Р инциденций системы множеств и отношений R.

Доказательство аналогично доказательству теоремы 3.

Аналогично предыдущему можно рассмотреть вопрос об учете уровня системы различных представителей и определить число систем различных представителей уровня, не ниже заданной величины a Î R+ . Ясно, что данный вопрос также сводится к вычислению некоторых перманентов неотрицательных матриц.

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

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

5.25. Об автоморфизме нечеткого множества

Пусть (X, т) - произвольное нечеткое множество, на котором задана группа преобразований G. Пусть АG (т) - группа автоморфизмов множества (X, т) в группе G , т. е.

АG (т) = {q Î G 1/2m (qx) = т (х)} для всех х Î X.

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

Определение. Собственная нетривиальная подгруппа Н группы G называется плотно вложенной, если Н имеет нетривиальное пересечение с каждой нетривиальной циклической подгруппой группы G .

Теорема 8. Группа автоморфизмов множества (X, т) в группе G нетривиальна в том и только в том случае, если она нетривиальна в нее плотно вложенной подгруппе Н.

Действительно, пусть АG (т) 1 е . Это значит, что существует q Î G, q 1 е такое, что qт= т. Рассмотрим циклическую группу < q > , (< q > 1 е по условию). Очевидно, что < q > Î AG (т). Поскольку Н плотно вложена, то НG < q > 1 е. Значит, найдется такое целое k, что qkÎ Н, qk 1 е. Очевидно, что qk = т, и тогда имеем АH(т) 1 е. Обратное утверждение очевидно.

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

Теорема 9. Пусть G = < а, ап = е> - циклическая группа порядка п. Тогда, если п свободно от квадратов простых чисел, то G не имеет плотно вложенных подгрупп. Если п не свободно от квадратов, то группа п Н = < а р1,…,ps>порядка р1,..., ps, где n = pa11,..., pass - разложение п на простые множители, будет плотно вложенной подгруппой группы G.

Если п свободно от квадратов простых чисел, то G - прямое произведение циклических подгрупп простых порядков. Если Н плотно вложенная, то Н содержит элементы простых порядков, а значит и группу, порожденную ими. Значит, G = Н.

Если п не свободно от квадратов, то пусть b - элемент простого порядка p1 , т. е. bp1 = е. Тогда b = аk для какого-то k, k< п, т. е. выполнен акр1 = е или k × p1°0 (mod n). Отсюда kp1 = nq, q - целое. Следовательно, имеем

b = (ap1)q=(ap1,..., ps) q ×p2…psÎH,

т. е. элементы простых порядков входят в группу Н. Любая нетривиальная подгруппа содержит циклическую подгруппу простого порядка и поэтому Н имеет не пустое пересечение с любой циклической подгруппой, т. е. Н— плотно вложенная.

5.26. О свойствах нечеткого единичного куба

Нечетким единичным кубом размерности п будем называть пары

(Еп, f), где Еп - множество наборов длины п из элементов 0,1, a f - функция принадлежности элемента (x1 , ....., хп ) множеству Еп , т. е. f: En® R+. В сущности, нечеткий единичный куб определяется псевдобулевой функцией f(x1,....., хп).

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

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

Представление псевдобулевой функции f(xi,....., xn) действительным многочленом определим индуктивно.

При п = 1 функцию f (x) представляет многочлен

Pf(x) = (f(1)-f(0))x+f(0).

Если для п-1 представляющий многочлен определен, то для п функцию f (x1,....., хп) представляет многочлен

Pf(х1 ....., хn) = (Pf(х1 , ....., хn-1) - Pf(х1 , .....,хn-1,0))хn + Pf(х1, ....., хn-1,0).

Определим вес псевдобулевой функции f(x1,....., хп) как действительную сумму

||f|| = åf(x1,.....,xn)

(х1,....,xn)ÎEn

Для произвольной псевдобулевой функции f(x1,....., хп) образуем 2n-1 функций следующим образом:

f ×x1 , f × x2 , ......, f xn, f × x1 × x2 , ..... , f × x1.... xn

Это легко доказывается.

Теорема 10. Система 2п весов || f ||, || f × x1 || , ...., || f × x1.... хп || однозначно определяет псевдобулеву функцию f.

Пусть (En, f) - нечеткий единичный куб. Пусть q : Еп® Еп - некоторая биекция. Рассмотрим вопрос об условиях, когда биекция q является автоморфизмом множества (Еп, f). Ясно, что в этом случае q представляется семейством булевых функций q (q1,....., qn).

Теорема 11. Биекция (q1,....., qn) является автоморфизмом нечеткого множества (Еп, f) тогда и только тогда, когда выполнено 2п - 1 условий.

|| f ×q1,....., qn|| = ||fx1.....xn||

|| f ×q1,....., qn-1|| = ||fx1.....xn-1||

||fqі1,....., qik|| = ||fxі1.....xik|| (*)

|| f qі|| = || fxі||, и = 1,...,n

Доказательство заключается в непосредственной проверке эквивалентности условий (*) и условия q - автоморфизм поэлементно.

Так, первое равенство в (*) дает

f(1........ 1) = f(x1,.....,хп),

где

q1(x1,....., хп) = 1,

qп(х1,....., хп) = 1.

Из следующего равенства получаем

f(1....... 1,0)+f(1,.....1,1)=f(x)+f(y),

где

q1(x1......, xn) = 1, q1 (y1, ...... yn) = 1,

qn(x1,....., xn) = 1, qn(y1......, yn) = 0.

Продолжая таким образом, получаем

f (q-1 (x)) = f (x) "x Î En,

т. е. - автоморфизм нечеткого множества.

Ясно, что справедливо и обратное утверждение.

Модуль 6.

Алгебра структурных чисел

Микромодуль 21

Введение в структурные числа

6.1. Основные понятия

6.1.1. Определение структурного числа

Пусть X — подмножество абстрактного пространства P. Эле­менты множества X обозначим

Рассмотрим систему элементов в виде таблицы

(1.1)

Будем рассматривать эту систему как совокупность столбцов ak, т. е.

(1.2)