НАУКА и ОБРАЗОВАНИЕ

В. В. Павлов, д-р техн. наук, проф., МГТУ "Станкин"

Полихроматические множества в теории систем. Операции над IIS-множествами

Представлен математический аппарат полихроматических множеств как новое средство информационных технологий в теории систем. Рассмотрены основные операции над ПS-множествами.

При моделировании сложных систем важное значение имеют операции над полихроматическими множествами, рассмотренными в [1]. Операции над ПS-множествами, осуществляемые с учетом их унитарных раскрасок и персональных раскрасок входящих элементов, более сложны, чем операции [2] над обычными множествами. В отличие от обычного множества, определяемого составом А своих элементов, IIS-множество в полном виде определяется шестеркой компонент:

             (1)

где А и F(a) — составы элементов и различных персональных цветов всех элементов; F(A) — множество унитарных цветов ПS - множества; [А х F(а)] — булева матрица персональных раскрасок элементов; [А х F(A)] — матрица персональных цветов элементов, одноименных с унитарными цветами ПS -множества; [А х A(F)] — булева матрица вариантов тел, реализующих унитарные цвета ПS - множества. При анализе и синтезе отдельного ПS - множества оно иногда может быть представлено сокращенными наборами компонент [3]:

дизъюнктивное множество — набором

                                                   (2)

конъюнктивное множество — набором

                                  (3)

Отсутствие в (2) матрицы [А х A(F)] обусловлено тем, что в ПS-множестве варианты тел унитарных цветов фактически представлены в матрице [А х F(A)], поскольку при дизъюнктивной форме связи унитарный цвет F_j(A) существует при наличии хотя бы одного элемента a_i  А с персональным цветом F_j(a_i) [1].

Над IIS-множествами в форме (2), (3) может быть осуществлена операция выделения подмножества ПS_i  ПS, так как это подмножество состоит из элементов A_i  А и состав тел его унитарных цветов является подмножеством тел унитарных цветов исходного ПS - множества. Выделение ПS,-осуществляется двумя путями:

·        задается состав A_j элементов ПS_i после чего определяется состав F(A_j) его унитарных цветов, тела которых состоят из элементов A_i,

·        задается состав F(A_i) унитарных цветов IIS_i, после чего определяется состав элементов тел, реализующих данные цвета — эти элементы и образуют состав A_i элементов выделяемого подмножества.

В первом случае выделяемое подмножество IIS_i получается единственным, а во втором случае возможны разные варианты решений, если существуют различные варианты тел унитарных цветов исходного ПS-множества. Рассмотрим, например, П^S-множество (рис. 1, а). Если условием выделения подмножества ПS,- является состав элементов A_i = (a₁, а₂, а₃, a₆), то в матрице [А х A(F)] этим элементам соответствуют только тела A₁(F₁) и A₁(F₄), поэтому выделяемое подмножество имеет состав унитарных цветов F(A_i) = (F₁, F₄) и будет единственным решением (рис. 1, б). Однако, если условием выделения подмножества будет состав унитарных цветов F(A_i) = (F₁, F₄), то этим цветам соответствуют тела A₁(F₁), A₂(F₁) и A₁(F₄) и возможны три варианта решения. При выборе тел A₁(F₁) и A₁(F₄) получим подмножество (рис. 1, б), а при выборе A₂(F₁) и А₁(F₄) получим подмножество (рис. 1, в) с составом элементов A_i = (а₂, а₃, a₄, a₅, a₆) и унитарными цветами F(A_i) = (F₁, F₂, F₃, F₄); наконец, при выборе всех трех тел A₁(F₁), A₂(F₁) и A₁(F₄) решением будет само исходное множество (рис. 1, а).

Рис 1. Выделение подмножества из IIS-множества:

а — исходное ПS-множество; б, в — выделенные подмножества; • — элемент c_i(j) = 1 булевой матрицы

В отличие от операции выделения подмножества, при вычислении разности, пересечения и объединения одновременно участвуют разные ПS-множества, поэтому возникает проблема идентификации элементов этих множеств в целях выявления эквивалентных элементов. Оказавшись в одном и том же ПS - множестве, все эквивалентные элементы — в силу закона идемпотентности [2] — будут поглощены и представлены единственным элементом.

При моделировании реальных систем эквивалентность элементов IIS-множества будет относительным понятием, зависящим от их влияния на определенные свойства системы, описываемые унитарными цветами IIS-множества. Наиболее строгим является условие эквивалентности a_i, a_j, основанное на равенстве составов и матриц взаи­мосвязи персональных цветов если

                      (4)

менее строгим будет условие

                                                 (5)

Если в рассматриваемом случае учитывается только определенный состав цветов F^Δ(a), то условие эквивалентности a_i a_j определяется по отношению к этому составу цветов:

                                   (6)

Проблема идентификации элементов ПS-множества на предмет их эквивалентности решается с помощью булевой матрицы [А х F(a)] персональных раскрасок элементов этого множества. Сравнивая значения логических переменных в строках матрицы, соответствующих элементам a_i, с заданным условием (4), (5) или (6), следует отметить, что каждое из этих условий требует разного уровня детализации описания персональных раскрасок элементов ПS-множества. Так, для проверки условия (6) достаточно описать только те персональные цвета а_i и a_j, которые относятся к заданному составу цветов Р\а), в то время как для проверки условия (5) необходимо описать все цвета F(a_i) и F(a_j); для проверки эквивалентности по условию (4) необходимо не только полное описание раскрасок, но и описание взаимосвязи всех цветов по условиям их существования с помощью матриц [F(a_i) x F(a_i)], [F(aj) x F(aj)].

Как правило, состав эквивалентных элементов IIS-множества сокращается по мере повышения уровня детализации описания их персональных раскрасок и перехода к более строгим условиям эквивалентности. Например, при технологическом проектировании детали (рис. 2, а) будут эквивалентными по составу обрабатываемых поверхностей — персональных цветов F(a_i) и F(a_j), так как для них выполняется условие (5). Однако при более детальном описании, с учетом матриц смежности поверхностей (рис. 2, б) детали a_i и а_j перестанут быть эквивалентными — условие (4) для них не выполняется.

Рис. 2. Эквивалентность механообрабатываемых деталей:

а — обрабатываемые поверхности деталей а_i, а_j;б — матрицы смежности обрабатываемых поверхностей, • — элемент  = 1 булевой матрицы

Поскольку в дизъюнктивных ПS - множествах матрицы [А х F(A)] и [А х F(a)] практически совпадают по составу цветов, то операция объединения дизъюнктивных множеств

                                                           (7)

может выполняться при представлении их в со­кращенной форме (2) следующим образом:

·        задается условие эквивалентности элементов исходных множеств и выявляются такие элементы в составе A_iи А_j

·        вычисляется состав А элементов итогового ПS - ножества

                                                                     (8)

·        вычисляется состав F(A) унитарных цветов ПS - множества

                                                        (9)

·        строится булева матрица [А х F(A)] ПS - множества

                                (10)

логические значения элементов с_р(q) этой матрицы в зависимости от логических значений одноименных элементов в матрицах [A_i x F(A_i)] и [A_j х F(A_j)] вычисляются по формуле

                                                      (11)

Операция объединения конъюнктивных множеств П^S_i и П^S_j может выполняться только при представлении их в полной форме (1), поскольку:

·        в объединяемых множествах одноименные элементы могут иметь в  матрицах  [A_i x F(A_i)] и [A_j х F(A_j)] несопоставимые составы унитарных цветов;

·        персональные цвета элементов, принадлежащих разным множествам, могут порождать тела новых унитарных цветов, ранее не существовавших в F(A_i) и F(A_j).

При объединении конъюнктивных множеств

                                                           (12)

состав унитарных цветов F(A) итогового множества ПS связан с составами F(a)_i F(A_i) и F(a)_j, F(A_j) соотношением

                           (13)

Рассмотрим операцию объединения множеств П^S_i и П^S_j на примере (рис. 3). Объединение выполняется следующим образом.

Рис. 3. Объединение полихроматических множеств:

а — матрицы [А_i х F(a)_i], [A_i х F(A_i)], [A_i x A_i(F)] конъюнктивного множества П^S_i; б — матрицы [A_j x F(a)_j], [A_j x F(A_j)], [A_j x A_j(F)] конъюнктивного множества П^S_j; в — матрицы [А х F(а)], [А х F(A)], [A x A(F)] объединения П^S_i и П^S_j; • — элемент с_i(j) = 1 булевой матрицы, когда а_i входит в состав тела A(F_j); о — элемент с_i(j) = 1 булевой матрицы, когда а_i - не входит в состав тела A(F_j)

1. Задается условие эквивалентности элементов исходных множеств и выявляются элементы, отвечающие этому условию, в составе A_i и A_j. Для определения эквивалентных элементов сравниваются их персональные раскраски в матрицах [A_j х F(a)_i] и [A_j x F(a)_j]. Например, для элементов исходных множеств (рис. 3, а, б) условие эквивалентности принято соответствующим (5); сравнение персональных раскрасок элементов в матрицах [A_i х F(a)_i] и [A_j x F(a)_j] показывает, что эквивалентны элементы a₂  A_i и а₂  A_j, а₃  A_i и а₃  A_j, a₅  A_i и a₅  A_j.

2. Вычисляется состав А элементов итогового П^S - множества по формуле (8). В рассматриваемом примере

3. Вычисляется состав F(a) всех персональных цветов всех элементов П^S_i и П^S_j по формуле

                                                        (14)

В рассматриваемом примере

4. Строится булева матрица [А х F(a)] итогового П^S - множества

                                  (15)

Эта матрица строится объединением строк и столбцов матриц [A_i x F(a)_i] и [A_j x F(a)_j] — см. рис. 3, в. Логические значения элементов с_p(q) матрицы в зависимости от логических значений одноименных элементов в объединяемых матрицах вычисляются по формуле (11).

5. Формируется булева матрица [А х A(F)] вариантов тел, реализующих унитарные цвета итогового П^S - множества, включающая в себя:

а) существовавшие в матрицах [А_i х A_i(F)] и [A_j х A_j(F)] варианты тел унитарных цветов F(A_i) и F(A_j); эта часть матрицы является объединением матриц вариантов тел унитарных цветов П^S_i и П^S_j строится аналогично (15);

б) новые варианты тел, образованные из композиций элементов П^S_i и П^S_j, в том числе тел, реализующих новые унитарные цвета, не существующие в F(A_i) и F(A_j). В рассматриваемом примере (рис. 3, в) в матрице [А х A(F)] появились новые тела A₂(F₂) и A₃(F₃) унитарных цветов F₂, F₃, существующих в F(A_i); кроме того, появились тела A₁(F₆), A₂(F₆), реализующие унитарный цвет F₆(A), не существовавший ранее в F(A_i) и F(A_j).

Таким образом, состав тел в сформированной матрице [А х A(F)] может превосходить объединение составов тел из матриц [A_i x A_i(F)] и [A_j x A_j(F)]:

                                (16)

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

6. По составу тел в матрице [А х A(F)] определяется состав F(A) унитарных цветов П^S - множества. В отличие от объединения дизъюнктивных множеств, где состав унитарных цветов определяется по формуле (9), при объединении конъюнктивных множеств имеет место

                                                       (17)

Так, в примере (рис. 3) имеем

7. При известном составе элементов А и унитарных цветов F(A) формируется матрица [А х F(A)] исключением из матрицы [А х F(a)] столбцов, соответствующих персональным цветам в F(a), не породившим одноименных унитарных цветов в F(A).

Построением матрицы [А х F(A)] операция объединения П^S_i и П^S_j завершается, поскольку все компоненты П^S в форме (1) определены.

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

Пересечением дизъюнктивных множеств П^S_i и П^S_j будет множество

                                                        (18)

являющееся общим подмножеством исходных множеств. Формирование пересечения (18) осуществляется так:

1. Задается условие эквивалентности элементов исходных множеств.

2. Определяется состав A_ij элементов П^S_i эквивалентных элементам П^S_j:

                                                                    (19)

Этот состав и образует пересечение П^S_ij.

3. Формируется булева матрица [A_ij x F(A_ij)] исключением из матрицы [A_i x F(A_i)] или [A_j х F(A_j)] всех строк, соответствующих не вошедшим в A_ij элементам, и столбцов, в которых не осталось ни одной единицы. Оставшиеся столбцы определяют состав F(A_i-j) унитарных цветов пересечения ПS_ij —тем самым пересечение (18) сформировано.

Формирование разности дизъюнктивных множеств

                                                         (20)

осуществляется следующим образом:

1. Задается условие эквивалентности элементов исходных множеств.

2. Определяется состав А_ij элементов ПS_i эквивалентных элементам ПS_j — этот состав образует пересечение ПS_ij.

3. Вычисляется состав элементов А_i-j по формуле

                                                                    (21)

Этот состав и является составом элементов ПS_i-j.

4. Формируется булева матрица [A_i-j х F(A_i-j)] унитарных цветов разности исходных множеств (20) исключением из матрицы [A_i x F(A_i)] всех строк, соответствующих вошедшим в А_ij элементам, и столбцов, в которых не осталось ни одной единицы. Оставшиеся столбцы определяют состав F(A_i-j) унитарных цветов разности ПS_i-j — тем самым разность (20) дизъюнктивных множеств сформирована. Формирование разности

осуществляется аналогичным образом. Состав элементов ПS_i-j вычисляется по формуле

Пересечение конъюнктивных множеств П^S_i и П^S_j

                                                                       (20)

из-за необходимости построения матрицы вариантов тел унитарных цветов F(A_ij) определяется иначе, чем пересечения (18), а именно:

1. Задается условие эквивалентности элементов исходных множеств.

2. Определяется состав A_ij элементов П^S_i эквивалентных элементам П^S_j. В тех случаях, когда установление эквивалентности элементов по матрицам [A_i х F(A_i)] и [A_j x F(A_j)] затруднено, в формировании пересечения (22) используются и матрицы персональных раскрасок элементов исходных множеств. Например, элементы a₂ множеств A_i и A_j (рис. 3, а, б) в матрицах [A_i x F(A_i)] и [A_j х F(A_j)] имеют разные составы персональных цветов, одноименных с унитарными цветами F(A_i) и F(A_j), что не позволяет сделать вывод об их эквивалентности по условию (5). Однако полные составы персональных цветов этих элементов по матрицам [A_i x F(a)_i] и [A_j x F(a)_j] одинаковы и, следовательно, элементы а₂  A_i и а₂  A_j эквивалентны по условию (5). Поэтому в подобных случаях операция пересечения осуществляется при представлении ПS-множеств в полной форме (1).

3. Если исходные множества представлены  в полной форме (1), то после определения состава эквивалентных элементов A_ij формируется булева матрица [A_ij х F(a)_ij] персональных раскрасок этих элементов исключением из матрицы [A_i x F(a)_i] или [A_j х F(a)_j] всех строк, соответствующих не вошедшим в A_ij элементам, и столбцов, в которых не осталось ни одной единицы.

4. Формируется булева матрица [A_i-j x A_i-j(F)] тел унитарных цветов пересечения (22) исключением из матрицы [A_i x A_i(F)] или [A_j x A_j(F)] всех строк, соответствующих не вошедшим в A_ij элементам, и столбцов, в которых утрачен требуемый состав тела унитарного цвета.

5. Формируется булева матрица [A_ij x F(A_ij)] исключением из матрицы [A_i x F(A_i)] или [A_j x F(A_j)] всех строк, соответствующих не вошедшим в A_ij элементам, и столбцов, для которых в матрице [A_ij х A_ij(F)] нет вариантов тел данного унитарного цвета. Оставшиеся столбцы определяют состав F(A_ij) унитарных цветов П^S_ij — тем самым формирование пересечения (22) завершено.

Формирование разности конъюнктивных множеств

                                                       (23)

осуществляется следующим образом:

1. Задается условие эквивалентности элементов исходных множеств.

2. Определяется состав A_ij элементов П^S_i эквивалентных элементам П^S_j, так же, как при определении A_ij в пересечении (22).

3. Вычисляется состав элементов А_i-j по формуле (21) — он и является составом элементов разности П^S_i-j.

4. Если исходные множества представлены в полной форме (1), то после определения состава элементов A_i-j разности (23) формируется булева матрица персональных раскрасок этих элементов вычеркиванием из матрицы [A_i х F(a)_i] всех строк, соответствующих вошедшим в А_ij (не вошедшим в A_i-j) элементам, и столбцов, в которых не осталось ни одной единицы.

5. Формируется булева матрица [A_i-1 x A_i-1(F)] тел унитарных цветов разности (23) исключением из матрицы [А_i х A_i(F)] строк, вошедших в А_ij (не вошедшим в A_i-j), и столбцов, в которых утрачен требуемый состав тела унитарного цвета.

6. Формируется булева матрица [A_i-j x A_i-j(F)] исключением из матрицы [A_i x F(A_i)] строк, соответствующих вошедшим в А_ij (не вошедшим в A_i-j) элементам, и столбцов, в которых в матрице [A_i-j х A_i-j(F)] нет вариантов тел данного цвета. Оставшиеся столбцы определяют состав F(A_i-j) унитарных цветов П^S_i-j — тем самым формирование разности (23) завершено. Формирование разности

                                                       (24)

осуществляется аналогичным образом. Состав элементов П^S_i-j вычисляется по формуле

Симметрическая разность [2] множеств П^S_i П^S_j определяется как объединение разностей (23), (24) этих множеств:

                                        (25)

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

Список литературы

1. Павлов В. В. Полихроматические множества в теории систем. Структура ПS-множеств // Информационные технологии. 1997. № 7. С. 11-16.

2. Куратовский К., Мостовский А. Теория множеств. М.: Мир, 1970, 416 с.

3. Павлов В. В. Полихроматические множества в теории систем. Изменение состава ПS-множеств // Информационные технологии. 1998. № 1. С. 4—8.

ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ, № 3, 1998

ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ

Ключевые слова

Теория систем, моделирование, полихроматические множества, раскраска множеств, выделение подмножеств, операции над множествами, матричные модели.