The constructional knowledge of sets and their properties

Prombles in programming 2014; 1: 3-17

Gespeichert in:

Bibliographische Detailangaben
Datum:	2025
Hauptverfasser:	Ilman, V.M., Shinkarenko, V.I.
Format:	Artikel
Sprache:	rus
Veröffentlicht:	Інститут програмних систем НАН України 2025
Schlagworte:	UDC 517. 519.2 004:512
Online Zugang:	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/726
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Problems in programming

Institution

Problems in programming

id	pp_isofts_kiev_ua-article-726
record_format	ojs
resource_txt_mv	ppisoftskievua/b1/fab6f6971696175c976219ea485bf6b1.pdf
spelling	pp_isofts_kiev_ua-article-7262025-04-09T22:38:00Z The constructional knowledge of sets and their properties Конструктивное представление множественных объектов и их свойства Ilman, V.M. Shinkarenko, V.I. UDC 517. 519.2, 004:512 УДК 517. 519.2, 004:512 Prombles in programming 2014; 1: 3-17 На основе конструктивной структуры предложено унифицированное представление гибридных множественных объектов. Рассмотрены алгебраические свойства и операции над этими объектами.Prombles in programming 2014; 1: 3-17 Інститут програмних систем НАН України 2025-04-09 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/726 PROBLEMS IN PROGRAMMING; No 1 (2014); 3-17 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 1 (2014); 3-17 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 1 (2014); 3-17 1727-4907 rus https://pp.isofts.kiev.ua/index.php/ojs1/article/view/726/778 Copyright (c) 2025 PROBLEMS IN PROGRAMMING
institution	Problems in programming
baseUrl_str	https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date	2025-04-09T22:38:00Z
collection	OJS
language	rus
topic	UDC 517. 519.2 004:512
spellingShingle	UDC 517. 519.2 004:512 Ilman, V.M. Shinkarenko, V.I. The constructional knowledge of sets and their properties
topic_facet	UDC 517. 519.2 004:512 УДК 517. 519.2 004:512
format	Article
author	Ilman, V.M. Shinkarenko, V.I.
author_facet	Ilman, V.M. Shinkarenko, V.I.
author_sort	Ilman, V.M.
title	The constructional knowledge of sets and their properties
title_short	The constructional knowledge of sets and their properties
title_full	The constructional knowledge of sets and their properties
title_fullStr	The constructional knowledge of sets and their properties
title_full_unstemmed	The constructional knowledge of sets and their properties
title_sort	constructional knowledge of sets and their properties
title_alt	Конструктивное представление множественных объектов и их свойства
description	Prombles in programming 2014; 1: 3-17
publisher	Інститут програмних систем НАН України
publishDate	2025
url	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/726
work_keys_str_mv	AT ilmanvm theconstructionalknowledgeofsetsandtheirproperties AT shinkarenkovi theconstructionalknowledgeofsetsandtheirproperties AT ilmanvm konstruktivnoepredstavleniemnožestvennyhobʺektoviihsvojstva AT shinkarenkovi konstruktivnoepredstavleniemnožestvennyhobʺektoviihsvojstva AT ilmanvm constructionalknowledgeofsetsandtheirproperties AT shinkarenkovi constructionalknowledgeofsetsandtheirproperties
first_indexed	2025-07-17T09:48:08Z
last_indexed	2025-07-17T09:48:08Z
_version_	1837887063836327936
fulltext	Теоретичні та методологічні основи програмування © В.М. Ильман, В.И. Шинкаренко, 2014 ISSN 1727-4907. Проблеми програмування. 2014. № 1 3 УДК 517. 519.2, 004:512 В.М. Ильман, В.И. Шинкаренко КОНСТРУКТИВНОЕ ПРЕДСТАВЛЕНИЕ МНОЖЕСТВЕННЫХ ОБЪЕКТОВ И ИХ СВОЙСТВА На основе конструктивной структуры предложено унифицированное представление гибридных мно- жественных объектов. Рассмотрены алгебраические свойства и операции над этими объектами. Введение Множественные структуры играют важную роль не только в классической математике, но и во многих приложениях [1]. Так множественные структуры интер- претируют и отражают технологические процессы предметных областей, являют- ся атрибутами структур данных, языков программирования, используются в сетях Петри, базах данных, в языках запросов и др. И, следовательно, для этих струк- тур во многих прикладных пакетах преду- смотрены способы их задания [2], над ними предусмотрены некоторые операции, например, в [3, 4] операции объединения (union), пересечения (intersect), разности (minus) и пр. Обычно, классические множества принято считать абстрактными не имею- щими семантики, т. е. их элементы лише- ны смыслового признака кроме возмож- ного смысла определяющего универсума. Используя прием именования элементов нетрадиционных множеств последние мо- жно представить в классическом виде. Од- нако, тогда элементы поименованных пре- дставлений множеств приобретают опре- деленный семантический признак, кото- рый, как правило в искусственных систе- мах закрепляется синтаксическими прави- лами или иначе. Например, в языках прог- раммирования это типы, структуры дан- ных и др. Еще одно последствие имено- вания проявляется в том, что при «работе» с такими множествами часто необходимо иметь значения элементов (имен-знаков) или их составных частей. Решение этого вопроса возможно с помощью номинатив- ных отношений [5] или более общо – функций множеств [1]. Существует большое разнообразие подходов для задания множеств. Это ли- нейные подходы на основе правил пере- числения, функциональные на основе характеристических и других функций, геометрические и алгебраические подходы на основе преобразований, конструктив- ные на основе формальных грамматик, ав- томатов, сетей, алгоритмические и иные подходы. Среди множественных объектов по структурному признаку можно выде- лить классические множества, множества- списки, мультимножества, нечеткие мно- жества, множества с предопределенными свойствами и прочие. В прикладных областях среди не- традиционных множественных структур встречаются конструкции с повторяющи- мися свободными элементами – мульти- множества и закрепленными элементами – списки. Достаточно широкий обзор при- ложений этих структур в компьютерных и других науках дан в работе [6] и частично в материалах конференции [7]. В своей ра- боте Д. Кнут [8] обратил внимание на то, что строки программ следует трактовать как мультимножества. Однако в реально- сти строки программ представляют более сложные множественные структуры, кото- рые в приложениях необходимо применять на «полную силу». Исследованию сложных (гибрид- ных) множественных структур на основе мультимножеств и списков посвящена настоящая работа. Подход к представле- нию технологических процессов, а также программированию на основе гибридных множественных моделей более полно от- ражает специфику процессов и техноло- Теоретичні та методологічні основи програмування 4 гию программирования. Известно, что предметные области и соответственно их множественные модели существенно вли- яют на представления объектов исследова- ний. Поэтому важен вопрос унификации представления множеств и задание алгеб- ры над унифицированными множествен- ными объектами. В работе рассмотрены некоторые подходы к заданию множеств и показано, что конструктивные модели построения множественных объектов, их анализ, и «работа напрямую» с такими объектами предпочтительнее. Алгебраический ана- лиз множеств, классов множеств и слож- ных множеств выполняется на мно- жественных объектах порожденных, пред- ложенной в работе, унифицированной конструктивной моделью. Рассмотрены некоторые операции над множественны- ми объектами. Представления множественных объектов Пусть E некоторый (символьный) универсум. Для представления множе- ственных объектов введем нейтральный (пустой) символ  , такой, что E  и { } { }  [1] и предположим, что K  пусть { }K K  . Множество A на универсуме E можно задать перечислением его элемен- тов, т. е. { },iA a i I   , ia E  & ,k ja a A  k ja a , тогда A E или функционально, посредством характери- стической функции 1, ; ( ) 0, ; A a A a a A       (1) или иным известным способом. Можно использовать и конструк- тивный подход к формированию множеств (set) на универсуме E . Так схема- генератор построения любого перечисли- мого множества A E при начальном множестве 1 \{ }E E  на основе подста- новок может быть такой: 1 { }; , ; ; .a E                 (2) Здесь { }  – начальная подста- новка, а подстановка 1a E   для любо- го выбранного a применяется один раз в процессе построения множества A , что можно осуществить подстановкой с логи- ческим выводом 1 1 1 \{ }a E E E a     . Следует отметить, что схема (2) задает как множество { } , так и любое другое, со- держащее пустой элемент  . Нетрудно убедиться в том, что представления множества { },iA a i I  , в виде (1) и (2) взаимнооднозначно. Рассмотрим другую множествен- ную конструкцию – мультимножество. Используем термин мультимножество, введенный Кнутом [9] при рассмотрении элементов комбинаторной математики. Мультимножество M по Кнуту – множе- ство { };iA a i I   с повторяющимися элементами кратности k . Если на обыч- ном множестве B E задать отношение повторяемости элементов 2 : B   ( , )b k , получим мультимножество M . Очевидно, отношение  не рефлексивно, не симметрично, не транзитивно, но упо- рядочено по представлению пар ( , )b k . По- этому, его поименованная структура в скобочной форме имеет вид {( , ); , , }i i i iM a k a E i I k    . (3) Нетрудно видеть, что из мультим- ножества (3) как частный случай получа- ется обычное множество {( , ); 1, }i i iM a k k i I     {( ,1); }ia i I A   . При функциональном подходе – ес- ли :f A , то мультимножеству M можно сопоставить характеристическую функцию Теоретичні та методологічні основи програмування 5 ( ), , ( ) 0, , f f a a M a a M       (4) которая при значениях ( ) 1f a  , a A  является характеристикой (1) для множе- ства A . Если снять ограничения по четвер- той подстановке в схеме (2), то предыду- щая схема (2) порождает мультимно- жество M на универсуме E с про- извольной (заранее неопределенной) крат- ностью элемента. Устранить этот недо- статок можно, введя логический вывод и номинативное отношение ( ) [5] над вто- рым местом пары ( , )  . Так, если принять 0E E за начальное множество в рекур- сивном правиле из (2), то получим иную схему-генератор построения мультимно- жества 0 0 0 0 { }; ( , ), ; ; ; & : \{ }; . a E a E E E a k                        (5) Здесь замечания относительно ак- сиомы и четвертой продукции остаются теми же, что и в схеме (2). Так же как предыдущая схема (2), схема (5) генерирует пустое муль- тимножество и любое другое множество с нейтральным символом. Кроме того, меж- ду представлением мультимножества в ви- де (3) и заданием генератором (5) взаимно- однозначное. На множестве M может быть зада- на, посредством указателей (связыванием элементов), как в программировании, или закреплением мест, неявная списочная структура {[ , ]}i iM a k . Явную структуру списка определим, задав отношение на де- картовом произведении M K  так, что 3 : ( , \| , )M K a m k     или за- дав отношение связывания элементов 2 : ( , )M M a b   , позволяющие пред- ставить список скобочными формами: {(( , ), ); , ,N i ij i i ijM a m k a M m K   1 2, , , , } ii kk j j j j  (6) {( , )}Z i jM a a ; ,i ja a M . (6’) В списочном представлении (6) ijm – порядковый номер элемента ia в по- следовательности или нейтральный сим- вол, а ik – кратность этого элемента во множестве NM . Представление (6’) ука- зывает на связь элемента ja с предше- ственником ia . Представления (6) и (6’) могут задавать связанные и не связанные списки, однорядные и многорядные и дру- гие списки. Пусть однорядные связанные списки образуют списочный базис. Тогда с помощью операций над базисом можно построить другие списочные конструкции. Базисная структура (6) переопределена, так как кратность элемента ia может быть подсчитана через количество мест этого элемента в списке, однако для дальнейше- го удобно использовать это представление. Если в базисной структуре (6) воспользо- ваться условием { } { }E E E E      , (7) то a E  имеем ( , )a a  . Тогда муль- тимножество является частным случаем списка M . Заметим, что отношение  является отношением частичного порядка по вто- рому месту. Отношение  , вообще говоря, также обладает свойством частичного по- рядка. Характеристическая функция ба- зисного списка (6) имеет вид (4), в котором :f A K  . При условии { }   эта характеристика f определяет муль- тимножество M . Для базисного списка со связыванием (6’) характеристическую функцию простого вида построить сложно. Конструктивно список можно по- строить на некотором заданном множестве с помощью операций переименования по второму (и третьему) месту. Теоретичні та методологічні основи програмування 6 Определение 1. Операцией пере- именования tf по параметру t на множе- стве K назовем унарное отображение :t K K  . Операцией переименования t по двухместному параметру t на мно- жестве M назовем бинарное отображение :t M M M M   . Из определения следует, что опера- ции tf и t неоднозначные, однако, если указать конкретные образы отображений, тогда неоднозначность операций устраня- ется, и в этом случае обозначим эти опера- ции так t rf и , t a b . Для списков NM справедлива тео- рема. Теорема 1. Если для списков NM  {(( , ), )}i ij ia m k и {(( , ),N q qlM a m   )}qk имеют место условия: # #N NM M  & ( ,i qa M a M     ) и наоборот; если i qa a & i qk k , то t rf NM M , t rf N NM M  . Здесь символ # обозначает мощ- ность множества. Доказательство теоремы основано на условии (7) и операциях переименова- ния. Аналогичная теорема имеет место и для списков со связыванием элементов ZM . Другие конструктивные схемы ге- нерирования списков (6) и (6’) могут быть следующие { }; (( , ), ), ; ; ; ; . a E m K k                           { }; ( , ), ; ; ; . a E b E                      (8) В схемах (8) –  начальный символ и правило a E   применяется как для различных элементов универсума, так и одинаковых элементов – причем места элементов в списке должны быть различ- ными. Пропущенные места в сформиро- ванном списке по первой схеме из (8) заполняются нейтральным элементом. Во второй схеме, чтобы список был базовым, должно выполняться условие, по которому в смежных парах первый элемент второй пары обязательно равнялся второму эле- менту первой пары. Такое задание кон- структивных схем списков является упрощенным и частично формальным. Бо- лее полной формализации первой схемы из (8) можно достичь с помощью логических выводов на подстановках и последующей операции морфизма  по схеме (9). В схеме-генераторе (9) введены обозначения: \| \|a – значение имени a , \| – символ «или». Отметим, что символ a в правилах 5p повторяется k раз, если это имя в цепочке l образует подцепочку 1 kl a .       1 2 3 4 1 1 5 : { } 0; : ; : 0 & ; ), & : \| \| \| \| \| \| 1& & \| \| 1 & \| \| \| & \| \| \| \| ), ), ), ; (9) ), ), : ( ) ( ), ) ( ), ); ( ), ) ( ) E p i p p m m k m m p m m m i i i m m l S p l                                                                            ( ) ()) (, ); ( ) ( ,; , ( ) \| \|; ()) ); (, ) ,; (, ) . a a E                                                После конструирования множества в схеме (9) к его элементам применяется Теоретичні та методологічні основи програмування 7 свойство поглощения нейтрального сим- вола [10], т. е. x x x   . (10) Отметим, что рекурсивное правило 3p частично определяет структурный уро- вень, конструируемого множества. Предложенный генератор является унифицированной в том смысле, что он обобщает построения множеств по схемам (2), (5) и больше того, может конструиро- вать гибридные множества, составленные из списков и мультимножеств. Так слож- ное множество 1 { ,( ,2),( ,3), , }M a b b c на части { , , , }a b c E  может быть получено по схеме (9) – (10) в результате примене- ния последовательности правил: 1 1 3 3 3 3 2 4,1 4,2 5 4,1 4,1 4,2 5 4,1 4,2 5 4,1 4,2 5 ( , , , , , , (1), , ( ), (2), (3), , ( ), (4), , ( ), (5), , ( )). P p p p p p p p p p a p p p p b p p p p p p c   Последовательность 1P по правилу 3p яв- ляется четырех уровневой, а по правилу 4,1p – двух уровневой и образует конст- рукцию {( , ) ,( ,2),( ,3) ,( , ) ,( , ) }a b b c        . Теперь используя свойство поглощения пустого символа (10) и учитывая условие (7), получаем множество 1M . В получен- ном множестве свободные элементы a , c и  образуют мультимножество ограни- ченное первым, четвертым и пятым места- ми их возможного расположения. Поэтому множество 1M можно записать и так { , , ,( ,3),( ,2)}c a b b или иначе. Представле- ние сложного множества 1M в виде { ,( ,2),( ,3), , }a b b c назовем его нормальной формой. Сложное множество 1M можно также построить на мультимножестве { , , , , }M a b c b , используя операции пе- реименования и результаты теоремы 1, так имеем: { , , , , } {( , ), ( , ), ( , ), ( , ), ( , )} { , ( ,2), ( ,3), , }. t rf a b c b a b c b b b a c           Таким образом, унифицированное представление сложных множеств осу- ществляется через наборы списков (муль- тимножеств) rM . Например, в языковых средах программирования, языках баз дан- ных и др. можно сконструировать слож- ные множественные структуры: на множествах множеств, множества списков и пр. Эти сложные структуры можно пред- ставить единообразно с представлением (6) и (6’) {(( , ), )}r rj rM M m k или {( , )}r iM M M . (11) Выражения (11) несмотря на свою компактность, могут иметь довольно сложные структуры, в них могут разнооб- разно сочетаться списочные и мультимно- жественные конструкции и даже незанятые места – «дыры». Для устране- ния дыр, как и в схемах (8) на свободных местах следует использовать нейтральный элемент. Например, комбинация схемы мультимножества типа (2) со второй спи- сочной схемой (8) дает конструктивную схему-генератор { }; ( , ), ; ( , ), ( , ), ( , ), ; , ; ; ( , ), ( , ), ( , ); ; ), ( ), ( ; ; ; ; ( ( ; ; ) ), ; , E l l h h G c c E a E b b E d d E                                                                       , порождающую сложные множества. Мож- но также воспользоваться при конструиро- вании сложных множеств приемом многоуровневого проектирования, как в программировании [11], используя схему- генератор (9). Множества множеств (11) могут иметь еще более сложные представления Теоретичні та методологічні основи програмування 8 через структуры объектов. Так, например, элементами множеств могут быть объекты связанных элементов (концов) универсума с бинарными связями типа интервалов [12], с n -арными связями типа графовых и др., атрибутивные множественные струк- туры и прочее. Однако, используя прием именования объектов множеств в (11) все- гда можно перейти к представлению мно- жеств в виде (6) или (6’). Утверждение 1. Конструктивные схемы-генераторы (2), (5) и ,E ES G по- рождают перечислимые множества. Дадим несколько необходимых по- нятий и определений. Определение 2. Множественным объектом (МО) M назовем конструктив- ное множество, которое сгенерировано схемой ES или EG (теоремой 1) и пред- ставленное в нормальной форме. Так как элементы мультимножеств этих гибридных объектов могут распола- гаться на различных свободных местах, то представление множественных объектов генератором (9) являются многоэкземпляр- ным. Так для рассмотренного выше объек- та 1M в схеме ES , имеем шесть экземпляров форм представления { ,( ,2),( ,3), , }a b b c , { ,( ,2),( ,3), , }a b b c  , { ,( ,2),( ,3), , }c b b a , { ,( ,2),( ,3), , }c b b a  , { ,( ,2),( ,3), , }b b a c и { ,( ,2),( ,3), , }b b c a . Очевидно, количество экземпляров m представления МО определяется парамет- рами входящего в него мультимножества M . Если #M n и jk , 1,2, ,j s крат- ности элементов множества M такие что, их сумма 1 s j j k n   , то m – полиномиаль- ный коэффициент равный 1 ! ! s j j n k   . В дальнейшем примем 1{ }m i iM M  . При значении 1m  множественный объект вырождается в список или мультимноже- ство. Определение 3. Множество всех МО объектов, порожденных генератором ES ( )EG , образуют класс – E ( GE ). Утверждение 2. Классы E и GE не совпадают. В дальнейшем уделим основное внимание гибридным множествам, порож- даемым генератором ES . К порождаемому МО объекту применяются правила (7) и (10), которые не порождают объект, а только трансформирует его, поэтому мож- но говорить об объекте, порожденном ге- нератором S . Задать класс МО объектов E мож- но также с помощью формального индук- тивного правила: 0M E – МО нулевого уровня; 1 { }, 0ES n nM E M n    ; ES nE M – конечное отображение по схеме (9) – (10) до 1n -го уровня; nM – МО n -го уровня, n  , max{ } 1i ij i j k m   (использованы обозна- чения формулы (6)). Если nM – класс объектов n -го уровня, тогда класс МО строится на клас- сах объектов различного уровня * * 0 i i E M   . Рассмотрим некоторые алгебраиче- ские свойства класса E . Над классом E , как над обычным множеством объектов можно ввести ал- гебру подклассов ( ,{ , , \, , })E E  A A . Так как множество { } E  и, если из класса E исключить пустое множе- ство, то получим подкласс \{ }E E   . Определение 4. Пусть подмноже- ство A E , тогда схема AS – подсхема схемы ES , т.е. A ES S , а множество A по отношению к схеме AS назовем определя- ющим. Теоретичні та методологічні основи програмування 9 Утверждение 3. На определяющем множестве A в схеме AS порождается класс A такой, что A . Из определений 3 и 4 и утвержде- ний 1 и 3 имеем результат. Теорема 2. Если ; ,A E B C E  , то * A E и * B C E , и B C  E , и * * \B C E . Если класс A E , тогда * \E A A есть дополнение класса A до класса E . Для дополнения A справедли- вы свойства. Свойство 1. * A A  . Свойство 2. * A A E . Теорема 3. На любом определяю- щем множестве A E с помощью опера- ции переименования строится тот же класс A , что и по схеме AS . Следствие 1. Алгебра EA – уни- версальная. Следствие 2. Класс E является кольцом по включению его подклассов. Так как из теоремы 2 имеем, что * ,A B E   * * * * & \A B E A B E   . Утверждение 4. По любому под- классу класса E однозначно восстанавли- вается определяющее множество соот- ветствующей схемы. Утверждение 5. Пустое множество – верхний предел последовательностей подклассов класса E . Рассмотрим некоторые операции и отношения над множественными объекта- ми класса E . Операции и отношения над множественными объектами В предыдущем параграфе уже рас- смотрены две операции переименования и их свойства. Эти операции можно приме- нять и ко всем МО объектам. Для коррект- ного задания других операций над слож- ными множествами необходимо ввести некоторые предварительные сведения, ка- сающиеся структуры множеств. Структуру МО объектов удобно задавать через пути их порождения генератором S . Пусть МО M E , тогда он по определению 3 порождается генератором ES . Определение 5. Последовательность (кортеж) правил ip схемы ES P  1 2 ( , , , ) ni i ip p p необходимых для по- строения МО M E назовем путем по- рожденного объекта или его структурой. Отношение между путем P и по- рожденным им объектом M однозначное, но не взаимнооднозначное. Определение 6. Два пути iP и jP эквивалентны ~i jP P , если они порождают один и тот же множественный объект. Отношение ~ является отношением эквивалентности. Обозначим P класс эк- вивалентности по отношению к объекту M его путей. Путь порождения объекта может быть конечным или бесконечным. Ограни- чимся рассмотрением конечных путей. Определение 7. Количество элемен- тов кортежа пути P назовем его длиной \| \|P . Допущение 1. Примем правило 1 1ip p за начало пути, а заключительное правило ni p ограниченного пути – за ко- нец пути. Концом пути в схеме ES может быть любое правило схемы, в том числе и правила 2p или 5p . Определение 8. Два пути iP  1 2 ( , , , ) ni i ip p p и 1 2 ( , , , ) mj j j jP p p p считаются равными i jP P , если имеют место два условия: 1) \| \| \| \|i jP P или n m , 2) имена их правил в схеме ES на одина- ковых местах совпадают. Теоретичні та методологічні основи програмування 10 Равенство путей ( ) является от- ношением эквивалентности, но не задает эквивалентность этих путей. Пусть на некотором определяющем множестве A E в схеме AS порожден МО объект M , структура порождения ко- торого i M P P имеет вид 1 2 ( , , , ) ni i ip p p . Определение 9. Структура jP  1 2 ( , , , ) mj j jp p p в схеме S называется подструктурой пути iP и записывается как j iP P , если m n и , 1 k ki jp p k m   . Путь jP назовем префиксом (префиксным путем) пути iP . Очевидно, что отношение на пу- тях МО объекта задает частичный поря- док. Из допущения 1 и определения 9 имеем, что любой путь подструктуры начинается из правила 1p схемы (9) и мо- жет оканчиваться любым из правил этой схемы, т. е. подструктура jP может по- рождать или не порождать МО. Путь, по- рождающий МО в некоторой схеме S обозначим P . Утверждение 6. Если для опреде- ляющего множества A в схеме AS порож- дены некоторые объекты со структурой iP и jP , причем порождающая структура jP в схеме BS ( B A ) всегда такая, что j iP P в схеме AS , то BS является под- схемой схемы AS , т. е. B AS S . Определение 10. Подмножествен- ным объектом (подмножеством, префикс- ным множеством) iM генерируемым в схеме BS объекта M ( iM M ) в схе- ме AS ( B AS S ) назовем такое под- множество, порожденное путем iM P , что iM M P P . Множество всех подмножеств объекта M назовем классом подмно- жеств (классом префиксных множеств) * { }iM M . Пусть два МО объекта ,iM M E сгенерированы в соответственных схемах BS и AS установим критерий, при кото- ром объект iM будет подмножеством объ- екта M . Теорема 4. Объект iM является подмножеством объекта M тогда и только тогда, когда B A и для их любых по- рождающих путей 1 2 ( , , , ) mi i i iM P p p p , 1 2 ( , , , ) nj j jM P p p p имеет место m n , , 1 k ki jp p k m   , и при этом совпадаю- щие правила порождают, точность до эк- земпляров объекта M , одинаковые пары ( , )sa z ; sa B , z K . Для рассмотренного выше примера путь порождения 1P множественного объ- екта 1 { ,( ,2),( ,3), , }M a b b c позволяет выделить в нем подструктуры 1 2( , )p p , 1 3 2 4,1 4,2 5( , , , ( ), , ( ))p p p p p p a , 1 3 3 2 4,1 4,2 5 4,1 4,2 5 ( , , , , ( ), , ( \| \| ), (2), , ( )), p p p p p p p a c p p p b   Тогда множество подмножеств – для объекта 1M в нормальной форме, со- ставленное из их экземпляров является 1 { },{ , ( ,1)}, { , ( ,1), ( , 2)}, { , ( ,1), ( , 2), },{ , ( ,1), ( , 2), , } a a c c b a c b b M a c b b a c a c b b a c c a                                                                       , (12) где скобками a c       обозначены альтернатив- Теоретичні та методологічні основи програмування 11 ные элементы подмножеств, которые мо- гут располагаться на соответствующих ме- стах без повторений (кратность символов , ,a c равна единице). Замечание 1. Для класса M объ- екта M справедливо: 1) M E ; 2) если iM M и * ji M M  , 1,2, ,j k ; 1 2i i iM M M , то для множественного объекта iM имеет место иерархия по отношению ( ) ; 3) объект * 1M M есть минималь- ный префикс, если jM в классе M , чтобы 1jM M ; 4) в классе M минимальный пре- фикс, в общем, не единственен; так для класса (12) их три { }a , { }c и { } . Так как МО объекты не однородны по составу, то для дальнейшего из них удобно выделить «однородные» части. Для этого введем две операции. 1q – операция извлечения приве- денного списка NM из множественного объекта M , является одноуровневым морфизмом, действующим по правилу: 1 1 1 1 1 1 1 1 1 1 1 ( ) ({ , , ( , ), , }) ({) (, ) ( ) (, ) (( , )) (, ) ( ) (, ) (}); q M q a b q q q a q q q q b q q       1 1 1 1 1 ({) {; (}) }; (, ) ,; (( , )) ( , ); ( ) ; ; q q q q q a a E            2q – операция извлечения муль- тимножества M из МО объекта M , яв- ляется двухуровневым морфизмом с ме- журовневым преобразованием, действую- щая по правилам: на первом уровне 2 2 2 2 2 2 2 2 2 2 2 ( ) ({ , ( , ), ( , ), , ( , ), ( , )}) ({) ( ) (, ) (( , ), ) (( , ), ) ( ) (, ) (( , ), ) (( , )}); q M q a b q q a q q q q b q q q                    2 2 2 2 2 ({) {; (( , )}) ( , )}; (, ) ,; (( , ), ) ; ( ) ; ; q q q q q a a a E              после преобразований поглощения (10) в полученном множестве, имеем 2{ , ,( , )}a b M   ; на втором уровне 2 2 2 2 2 2 2( ) ({) ( ) (,) ( ) (,( , )});q M q q a q q b q   2 2 2 2 ({) {; (, ) ,; (, ( , )}) }; ( ) ; . q q q q a a a E         Утверждение 7. M E  с помо- щью операций 1q и 2q однозначно выде- ляются такой приведенный список NM и мультимножество M , что ,NM M E и вообще говоря ,NM M M . Например, операции 1q и 2q , изв- лекают из объекта 1 { ,( ,2),( ,3)M a b b , 1 { ,( ,2),( ,3), , }M a b b c приведенный спи- сок {[ ,( ,1),( ,2), , ]}b b   и множество { , , }a c . Эти множества не являются под- множествами объекта 1M , хотя список имеет такую же структуру порождения, как и МО, а мультимножество имеет дру- гую структуру – 1 3 3 3 2 4,1 4,2, , , , , , ,p p p p p p p 5 4,1 4,2 5 4,1 4,2 5, , , , , ,p p p p p p p . Здесь, для отличия обычного списка от приведенного, введены скобки ([, ]) . Таким образом, операции 1q и 2q осуществляют однозначную декомпози- цию МО объектов, кроме того, они позво- ляют выполнить декомпозицию и пре- фиксных классов. Например, для класса (12) имеем декомпозицию объектов { } { , } { }, { , } ,{ , , } { } { , } a a M c a c a c c                     и * [ , ( , 2)],[ , ( , 2), ( ,3)], [ , ( , 2), ( ,3), ], [ , ( , 2), ( ,3), , ] N b b b M b b b b                   . Теоретичні та методологічні основи програмування 12 Утверждение 8. Если декомпози- ции M и NM класса M , то справедли- во замечание 1. Для преобразования приведенного списка в обычный, вообще несвязанный список, рассмотрим морфизм g рекурсив- ного парного группирования элементов приведенного списка с последующим при- менением свойств (7) и (10). Пусть приведенный список NM не- которого множественного объекта M E такого, что 3{[ , , , , , , ]}N k kM c c     , где ( , ),ic a i a E  , i ; тогда 3 3 ( ) ({[ , , , , , , ]}) ({[) ( , ), ( , ), ( , ), ( ])}; N k k k k g M g c c g g c g g c g                ({[) {, ( , ) ( , ) , ( , ) ( , ) ; k k kg g c c c g             3 3 3( , ) ( , ) , ( ]) ] ], (]}) }; k k kg c c c g g            1 1 ({ , , , ]}) ({ \| ) ( , ), ( , ])}; k k j k k g c c g c g c g c       1 1({ ) { , ({ ) { {, ( ,])j j k kg c c g g c c       ; Модифицированный с помощью парного группирования g приведенный список NM обозначим, как g NM . Список g NM обладает свойством частичной при- надлежности к классу E . Устранить ча- стичность можно с помощью операции переименования t rf . Очевидно, всякий МО объект мож- но представить через его компоненты де- композиции, если будет задана процедура восстановления объекта. Для этого введем операцию композиции ( )w в определенном смысле противоположную процедуре де- композиции. Пусть для МО объекта M компо- нентами декомпозиции является приве- денный список NM и мультимножество .M Если вначале принять ,T M тогда операцию ( )w определим через последова- тельную подстановку и присвоение , & \{ } : \{ } a a T T T T a         (13) ко всем нейтральным символам приведен- ного списка NM . Отметим, что композицию МО объ- екта M можно частично осуществить и над модифицированным списком g NM , до- полняя его элементами мультимножества до связанного объекта. Лемма 1. Для приведенного списка NM количество подстановок (13) совпада- ет с порядком нейтрального элемента и мощностью мультимножества M , и по ним восстанавливается объект M . Из леммы и определения операции ( )w имеем, что ( , )NM w M M , NM  ( , )Nw M  , ( , )M w M  и ( , )w   . В общем случае операция ( )w не коммута- тивна и не ассоциативна. Кроме того, из леммы 1 также имеем. Теорема 5. Если M и * NM компо- ненты композиции класса M , то N NM M  , M M  , ( , )Nw M M M . Рассмотрим подобие теоретико- множественных операций над компонен- тами классов E и M , при этом учитыва- ем, что для любой из этих операций ( ) имеет место свойство 1 2 1 2 1 2 1 2 1 2 ( , ) ( , ) ( , ). N N N N M M w M M w M M w M M M M        (14) Известно [8, 9, 13 – 15], что к муль- тимножествам применимы операции обычного объединения ( ) и объединения со сложением ( ) , обычного пересечения ( ) и пересечения с умножением ( ) , раз- Теоретичні та методологічні основи програмування 13 ности (\) и др., которые ,i jM M E  вы- полняются по правилам: { ; \| , ( ) max{ ( ), ( )}, ( ) }. i j i j i j M M M M x x M M m x m x m x m x     { ; \| , ( ) ( ) ( ), ( ) }. i j i j i j M M M M x x M M m x m x m x m x      { ; & , ( ) min{ ( ), ( )}, ( ) }. i j i j i j M M M M x x M M m x m x m x m x     { ; & , ( ) ( ) ( ), ( ) }. i j i j i j M M M M x x M M m x m x m x m x       , \ { ; & , ( ) ( ) ( ), ( ) }. i i j i j i j i j M M M M M M M x x M x M m x m x m x m x        Из приведенных правил следует, что операции ( ) , ( ) и (\) – обобщения операции с обычных множеств на муль- тимножества, а операции ( ) и ( ) отсут- ствует в классических множествах. Операция ( ) порождает новое множество присоединением к множеству iM множе- ства jM и поэтому она не коммутативна. Операция ( ) предполагает суммирование порядков общих элементов операндов- множеств. Распространим эти операции на ба- зисные списки ,i jM M E . Пусть имен- ными носителями, для списков iM и jM будут множества ,i jA A E и носителями мест списков ,i jN N  . 2 {( , ); \| , \| , ( ) max{ ( ), ( )}, ( ) } i j i j i j i j M M M M x r x A A r N N m x m x m x m x M       – в общем случае двухкомпонентный (не- связанный) списочный класс такой, что 2 M E . При этом возможны случаи: 1) если ( , )i i ia r M , ( , )j j ja r M и i ja a , i jr r , то в классе 2M имеем об- щую пару \| \|( , )i j i ja r и 2M имеет связное двухрядное представление; 2) если ( , )i i ia r M , ( , )j j ja r M и i ja a , i jr r r  , то в двухкомпонентном классе 2M имеем именную альтернатив- ную пару ( \| , )i ja a r ; 3) если i jM M , то 2 jM M . Класс 2M для первого и второго случаев является двухрядным по пред- ставлению, а в третьем случае вырождает- ся в список класса E . Например, объединение ( ) базисных списков класса E , 1 {( ,1),( ,2),( ,3),( ,4),( ,5)}M a b b c c и 2 {( ,1), ( ,2), ( ,3), ( ,4)}M a c b b является двухрядным списком {( \| ,1),( \| ,2),( \| ,3),( \| ,4),( ,5)}a a b c b b c b c . Следующую операцию присоеди- нения списка jM к списку iM с последу- ющим переименованием по второму параметру элементов – jM зададим так, чтобы результирующий список 1M был связным, т. е. 1M E и     1 1 {( , ); \| , \| , ( ) ( ) ( ), ( ) , ( , ) ( , ) }. i j t s j i j i j i j M M f j j s j M M M x r x A A r N N m x m x m x m x x r M x r M            Так объединением ( ) списков из предыдущего примера будет следующим: {( ,1), ( ,2), ( ,3), ( ,4), ( ,5), ( ,6), ( ,7), ( ,8), ( ,9)}. a b b c c a c b b Анализ операций ( ) и ( ) над мультимножествами и списками показыва- ет, что первая операция, в общем, может Теоретичні та методологічні основи програмування 14 применяться только над множественными объектами префиксного класса M . Дру- гая операция может применяться без огра- ничений на всем классе E . При этом по операции ( ) выполняется свойство за- мыкания на классе M , а по операции ( ) – на классе E . На основе операций объединения ( ) и ( ) рассмотрим комбинированную операцию частичного покрытия ( ) , для которой на мультимножествах –  , а на списках справедливо частичное равен- ство  , по которому имеет место пра- вило: 1 1 11 1 1 ( ) ( ) . i j i j i j M M M M M M M M      Здесь, в списках 1M и 11M совпа- дают имена элементов и их порядок следо- вания. Операция частичного покрытия предполагает использование операции пе- реименования по месту для связности ре- зультата. Операция ( ) обобщает операцию ( ) на классе M , ибо для подмножества i jM M справедливо i j i jM M M M  . Поэтому класс M частично замкнут по операции ( ) . Операция разности над списками имеет смысл тогда, когда они частично имеют одинаковые имена элементов. Рас- смотрим четыре модификации этой опера- ции. Операция естественной разности ( \) объектов. \ {( , ); ( , ) &( , ) , ( , ) ( , )}. t s i i j i j f i s i M M x r x r M x r M x r x r      Операция разности по имени и ме- сту 0( \ ) – (сильная разность). 0 ( , ), ( , ) &( , ) ; \ , ( , ) &( , ) . i j i j i j x r x r M x r M M M x r M x r M        Операция разности по имени 1( \ ) – (обобщенная разность) [1]. 1 ( , ), & , ; \ , & . i j i i j i j x r x A x A r N M M x A x A        Результатом рассмотренных опера- ций разности является приведенный спи- сок, который можно свести к обычному списку, используя операции g и t rf , такой оператор назовем разностью с переимено- ванием \\ \t rf g . Операции разности легко перено- сятся на множественные объекты. Напри- мер, для множественного объекта 1 { ,( ,2), , ( ,4), , ( ,6)}M a a d b c c и объекта 2 {( ,1), , , ( ,4),( ,5)}M c a c e d разность их мультимножеств – 1 2\ { }M M d следова- тельно, 1 2\ {( ,1), , ( ,3),( ,4)}M M a d b c , а обобщенная разность приведенных мно- жеств соответственно является 1 1\NM 2 1\ {[ ,( ,2), , ( ,4), , ]}NM a b    , поэтому 1 1 2\ { ,( ,2), , ( ,4), , }M M d a b   – четы- рехэкземплярный МО. Разность же (\\) на МО объектах неоднозначна, так раз- ность 1M \\ 2M определяет три различных множества { ,( ,2),( ,3)}d a b , {( ,1), ,( ,3)}a d b и {( ,1),( ,2), }a b d . Введенные разности ( \) , 0( \ ) и 1( \ ) позволяют рассмотреть три модифи- кации симметрической разности объектов 1 2 1 2 2 1( \ ) ( \ )M M M M M M  , где под символом ( \) понимается любая из трех операций разности. Теперь рассмотрим операцию пере- сечения списков в модификациях. Сильная операция пересечения по имени и месту ( ) . {( , ); ( , ) & , ( ) min{ ( ), ( )}, ( ) }, i j i j i j M M M M x r x r M M m x m x m x m x     Теоретичні та методологічні основи програмування 15 при этом, если список i jM M не связ- ный, то он дополняется до связного нейтральным символом необходимой кратности или переименовывается его нормальная форма по второму параметру элементов. Отметим, что условие min{ ( ), ( )} i jM M m x m x является лишним при сравнении пар объектов iM и jM , однако необходимо для сравнения поряд- ков нейтрального символа в приведенных списках. Из введенного правила операции ( ) следует, что, если i jM M , то i j iM M M и если в списках нет общих элементов, тогда \{ }i jM M  . Операция пересечения по имени 1( ) объектов. 1 {( , ); & , min{ , }, i j i j i i j j M M x r x A x A r r N r N       ( ) min{ ( ), ( )}, ( ) , ( , ) ( , )}. i j t s j M M f j s j m x m x m x m x x r x r     Операция 1( ) обобщает предыду- щую операцию пересечения. Другая операция пересечения с суммированием ( ) над списками выпол- няется в три этапа    2 ( , ); . i j i j i j M M M M x x A A     Операции первого и второго этапов рассмотрены выше, а правило выполнения операции 2( ) приведено далее [1]. Пусть ( , ) , 1,2i i ix r M i  , тогда 1 2 1 2 2 1 1 1 2 , ; ( , ), . x x M M x r x x      В этой операции, как и в предыду- щих операциях пересечения, может ис- пользоваться операция естественной раз- ности для исключения элементов, не по- павших в пересечение мультимножеств. Продемонстрируем это на МО объ- ектах 1 { ,( ,2), , ( ,4), , ( ,6)}M a a d b c c и 2 {( ,1), , , ( ,4), ( ,5)}M c a c a d при нахожде- нии пересечения с суммированием. Так как элемент d отсутствует в пересечении мультимножеств 1M и 2M , т. е. 2 2 1 2 { , }M M a c M   , то исключим его из первого множественного объекта 1 3\{ } { ,( ,2),( ,3), , ( ,5)}M d a a b c c M  и рассмотрим 1 2 3 2M M M M M    . Операция ( ) над приведенными списками 3 NM и 2 NM определяет приве- денный списочный объект { ,( ,2),( ,3), ,( ,5),( ,6), , ,( ,9),( ,10)}a b c c a d    и пересечение их носителей 3 2 { , , }A A a c . Тогда после применения операции 2( ) получим следующий при- веденный список: { ,( ,2), , , ( ,5),( ,6), , , ( ,9), }NM a c c a      и операция композиции ( , )Nw M M даст результирующий множественный объект { ,( ,2), , , ( ,5),( ,6), , , ( ,9), }M a a a c c c c a  . Анализ применения операции ( ) к множественным объектам 1M и 2M поз- воляет заключить, что для кратности 1 2 1 2 ( ) min{ ( ), ( )} M M M M m m m   спра- ведливо Утверждение 9. 1 2 1 2( ) # M M m M M  . Поэтому часть нейтральных симво- лов  , не превышающих кратности 1 2 ( ) M M m  , используется для получения связности списка 1 2 N NM M и оставшаяся располагается в этом списке за элементом с наибольшим местом. Над множественными объектами 1M и 2M может выполняться комбиниро- ванная операция 1( , ) – на декомпози- Теоретичні та методологічні основи програмування 16 циях 1M и 2M операция ( ) и на приве- денных списках 1 2 1N NM M . Для комби- нированной операции справедливо утверждение 9 и правило использования нейтрального символа. Результаты, рассмотренных опера- ций дают возможность привести следую- щие группы свойств. Для префиксного класса M при множествах 1 2 3, ,M M M M имеем: 1 1M M , 1M  , 1 2 2 1M M M M , 1 1 1M M M , 1 2 2 1M M M M , 1 1 1M M M , 1 2 3 1 2 3( ) ( )M M M M M M , 1 2 3 1 2 3( ) ( )M M M M M M , 1 2 3 1 2 1 3( ) ( ) ( )M M M M M M M , 1 2 3 1 2 1 3( ) ( ) ( )M M M M M M M ; 1 2 1 2 1 2 2 1 ( ) ( ) ( ) \| ( ). M M M M M M M M   В классе E для множественных объектов 1 2 3, ,M M M E справедливо: 1 1 1( \{ }) ( \{ })M M M     , 1 2 2 1M M M M , 1 1 1M M M , 1 2 3 1 2 3 1 2 3 ( ) ( ) , M M M M M M M M M    1 1\| ( )M A B M A B , 1 1\| ( )M A B M A B , * *,A B M E  ; 1 2 2 1M M M M   , 1 2 3 1 2 3 1 2 3 ( ) ( ) , M M M M M M M M M          1 2 2 1M M M M   , 1 2 3 1 2 3 1 2 3 ( ) ( ) , M M M M M M M M M          1 2 3 1 2 1 3( ) ( ) ( )M M M M M M M      , 1 2 3 1 2 1 3( ) ( ) ( )M M M M M M M      , 1 2 3 1 3 2 3( ) \ ( \ ) ( \ )M M M M M M M , 1 2 3 1 3 2 3( ) \ ( \ ) ( \ )M M M M M M M   , 1 2 3 1 3 2 3( ) \ ( \ ) ( \ )M M M M M M M   . Последние три свойства имеют ме- сто и для разностей 0( \ ) и 1( \ ) . Выводы Для задания множественных объек- тов предложена универсальная конструк- тивная схема-генератор, которая может порождать множества, мультимножества, списки или гибридные объекты на основе этих множеств. Кроме того, с помощью введенной схемы определяется структура множественного объекта, выделяются префиксные классы объектов и др. Исследованы алгебраические свой- ства класса множественных объектов и префиксных подклассов. Установлено, что по любому подклассу класса множествен- ных объектов восстанавливается опреде- ляющее множество соответствующей схемы-генератора. Рассмотрены важные для приложе- ний операции декомпозиции и композиции множественных объектов. Дано расшире- ние теоретико-множественных операций с мультимножеств на гибридные множе- ственные объекты их классы и подклассы. Установлены свойства расширенных опе- раций. Предложенная модель конструиро- вания множественных объектов может быть использована при проектировании абстрактных структур данных в програм- мировании, разнообразных технологиче- ских процессов и др. 1. Босов А.А. Функции множества и их при- менение. – Днепродзержинск: Изд. дом „Андрей”, 2007. – 182 с. 2. Левин Д.Я. Язык сверхвысокого уровня СЕТЛ и его реализация. – Новосибирск: Наука, Сибирское отделение, 1983. – 160 с. 3. Прохоров Г.В., Лебедев М.А., Колбеев В.В. Пакет символьных вычислений Maple V. – М.: „Петит”, 1997. – 200 с. Теоретичні та методологічні основи програмування 17 4. Гарсиа-Молина Г., Ульман Дж., Уидом Дж.. Системы баз данных. – М.: Вильямс, 2004. – 1088 с. 5. Никитченко Н.С. Композиционно- номинативный подход к уточнению поня- тия программы // Проблемы программиро- вания. – 1999. – № 1. – С. 16 – 31. 6. Blizard W. The Development of Multiset Theory // Notre Dame Journal of Formal Log- ic. – 1989. – Vol. 30, N 1. – P. 36 – 66. 7. Богатырёва Ю.А. Мультимножества: биб- лиография, решетка мультимножеств // Те- зи доповідей VI Міжнародної конференції „Теоретичні та прикладні аспекти побудо- ви програмних систем”. – TAAPSD’2009. – К., 2009. – С. 13 – 20. 8. Knuth D. Context-Free Multilanguages // Theoretical Studies in Computer Science. – Academic Press, 1992. – P. 1 – 13. 9. Кнут Д. Искусство программирования для ЭВМ. – М.: Мир, Т 2. – 1977. – 727 с. 10. Ільман В.М., Скалозуб В.В., Шинкаренко В.І. Формальні структури та їх застосуван- ня.– Дніпропетровськ: Вид-во Дніпропетр. нац. ун-ту залізн. трансп., 2009. – 205 с. 11. Андон Ф.И., Дорошенко А.Е., Цейтлин Г.Е., Яценко Е.А. Алгебро-алгоритми- ческие модели и методы параллельного программирования. – Киев: Академпери- одика, 2007. – 634 с. 12. Ільман В.М., Скалозуб В.В. Інтервальні об’єкти та їх граматичні структури // Вісник Дніпропетровського національно- го університету – 2010. – Вип. 29. – С. 131–144. 13. Albert J. Algebraic properties of bag data types // Severenteenth International Confer- ence on Very Large Data Bases. – Barcelona, Spain, 1991. – P. 211–219. 14. Singh D., Ibrahim A.M., Yohanna T., Singh J. An Overview of the Applications of Multiset // Novi Sad Journal of Mathematics. – 2007. – Vol. 37, N 2. – P. 73–92. 15. Syropoulos A. Mathematic of Multisets // Multiset Processing: Mathematical, Computer Science and Molecular Computing Points of View, Number 2235 in Lecture Notes in Co- muting Since. – Berlin: Springer-Verlag, 2001. – P. 347 – 358. Получено 13.06.2013 Об авторах: Ильман Валерий Михайлович, кандидат физико-математических наук, доцент, Шинкаренко Виктор Иванович, доктор технических наук, профессор. Место работы авторов: Днепропетровский национальный университет железнодорожного транспорта, кафедра «Компьютерные информационные технологии», 49010, г. Днепропетровск, ул. академика Лазаряна, 2. Каф. КИТ, ДНУЗТ. Тел.: (056) 373 1535. E-mail: shink@diit.edu.ua, ccp@diit-70.dp.ua mailto:ccp@diit-70.dp.ua

The constructional knowledge of sets and their properties

Institution

Ähnliche Einträge