Designers sets and multisets of objects

Prombles in programming 2014; 1: 18-30

Saved in:

Bibliographic Details
Date:	2025
Main Author:	Terletskyi, D.O.
Format:	Article
Language:	Ukrainian
Published:	PROBLEMS IN PROGRAMMING 2025
Subjects:	UDC 510.2:004.8
Online Access:	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/727
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Problems in programming
Download file:

Institution

Problems in programming

id	pp_isofts_kiev_ua-article-727
record_format	ojs
resource_txt_mv	ppisoftskievua/16/c48563092aa81b58c2234c7eb7cc2116.pdf
spelling	pp_isofts_kiev_ua-article-7272025-04-09T22:38:00Z Designers sets and multisets of objects Конструктори множин та мультимножин об’єктів Terletskyi, D.O. UDC 510.2:004.8 УДК 510.2:004.8 Prombles in programming 2014; 1: 18-30 Пропонуються певні операції над об’єктами, що описують деякі сутності, досліджується процес утворення множин та мультимножин об’єктів та пропонуються конструктивні методи їх створення (автоматичної генерації), що дозволяє будувати, класифікувати та порівнювати об’єкти та множини або мультимножини об’єктів, виділяти нові класи об’єктів, генерувати множини та мультимножини об’єктів за певним класом, що дозволяє у певному сенсі практично реалізувати для машини здатність оперувати такими базовими категоріями людського мислення як «множина» та «мультимножина».Prombles in programming 2014; 1: 18-30 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2025-04-09 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/727 PROBLEMS IN PROGRAMMING; No 1 (2014); 18-30 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 1 (2014); 18-30 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 1 (2014); 18-30 1727-4907 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/727/779 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	Ukrainian
topic	UDC 510.2:004.8
spellingShingle	UDC 510.2:004.8 Terletskyi, D.O. Designers sets and multisets of objects
topic_facet	UDC 510.2:004.8 УДК 510.2:004.8
format	Article
author	Terletskyi, D.O.
author_facet	Terletskyi, D.O.
author_sort	Terletskyi, D.O.
title	Designers sets and multisets of objects
title_short	Designers sets and multisets of objects
title_full	Designers sets and multisets of objects
title_fullStr	Designers sets and multisets of objects
title_full_unstemmed	Designers sets and multisets of objects
title_sort	designers sets and multisets of objects
title_alt	Конструктори множин та мультимножин об’єктів
description	Prombles in programming 2014; 1: 18-30
publisher	PROBLEMS IN PROGRAMMING
publishDate	2025
url	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/727
work_keys_str_mv	AT terletskyido designerssetsandmultisetsofobjects AT terletskyido konstruktorimnožintamulʹtimnožinobêktív
first_indexed	2025-07-17T09:53:32Z
last_indexed	2025-07-17T09:53:32Z
_version_	1850410130298896384
fulltext	Теоретичні та методологічні основи програмування © Д.О. Терлецький, 2014 18 ISSN 1727-4907. Проблеми програмування. 2014. № 1 УДК 510.2:004.8 Д.О. Терлецький КОНСТРУКТОРИ МНОЖИН ТА МУЛЬТИМНОЖИН ОБ’ЄКТІВ Пропонуються певні операції над об’єктами, що описують деякі сутності, досліджується процес утво- рення множин та мультимножин об’єктів та пропонуються конструктивні методи їх створення (автома- тичної генерації), що дозволяє будувати, класифікувати та порівнювати об’єкти та множини або муль- тимножини об’єктів, виділяти нові класи об’єктів, генерувати множини та мультимножини об’єктів за певним класом, що дозволяє у певному сенсі практично реалізувати для машини здатність оперувати такими базовими категоріями людського мислення як «множина» та «мультимножина». Вступ Поняття «множина» є центральним для теорії множин і одним із базових по- нять для математики в цілому. Окрім цьо- го це поняття має дуже важливе та глоба- льне значення, в життєдіяльності людини, оскільки ми повсякденно використовуємо множини в своїй розумовій діяльності в процесі сприйняття, аналізу, порівняння, пошуку, класифікації тощо. Ми свідомо чи підсвідомо оперуємо ними, створюючи та змінюючи їх, застосовуючи до них різні операції. Проте аналізуючи визначення поняття «множина», наведені в [1–3] ви- никають питання про походження «конк- ретних» множин. Згідно з класичною теорією мно- жин, «нові» множини можна отримувати шляхом застосування теоретико-множин- них операцій до «вже існуючих» множин і це дійсно так. Проте не зникають питання про походження цих так званих «вже іс- нуючих» множин, їхню кількість, їх види і так далі. Дана стаття є продовженням дос- ліджень розпочатих в [4], де були запро- поновані основи конструктивної версії теорії множин (CST) у рамках якої вводиться новий рівень – рівень об’єктів, які є складовими для створення множин; концепція класу об’єктів, що дозволяє в певному сенсі формалізувати класифіка- цію самих об’єктів. В основу CST покла- дається принцип нескінченності за Бра- уером та відкидаються такі поняття як «одноелементна множина» та «пуста множина». Використовуючи базові поняття CST визначимо деякі операції над об’єктами та детально розглянемо процеси утворення множин та мультимножин об’єктів. Об’єкти, класи об’єктів та множини об’єктів Об’єкти. Відомо, що будь-яка множина складається з елементів, які її утворюють (визначають). Як елементи множини можуть виступати будь-які пре- дмети, явища нашої уяви або навколиш- нього світу, називатимемо такі елементи об’єктами. Розглянемо такий об’єкт, як натуральне число, очевидно, що кожне на- туральне число має бути цілим та бути до- датнім – що є за суттю характеристичними властивостями натуральних чисел, звідси не важко переконатися, що 8 це дійсно на- туральне число, а − 4 або 2.9 – не є такими. Аналізуючи вище наведені факти, можна зробити висновок, що будь-який об’єкт володіє певними властивостями, які є для нього характеристичними і визначають його, як деяку сутність та дозволяють від- різняти його від інших об’єктів. Об’єкт A – це носій деякої сукуп- ності характеристичних властивостей та ознак ))(),...,(()( 1 ApApAP n , яка назива- ється специфікацією об’єкта A і визначає його, як деяку сутність. Будемо позначати довільний об’єкт наступним чином: ))(),...,(/()(/ 1 ApApAAPAA n . Очевидно, що специфікація будь- якого об’єкта містить певну кількість влас- Теоретичні та методологічні основи програмування 19 тивостей, тому доцільно ввести поняття розмірності об’єктів. Розмірність об’єкта )(AD це нату- ральне число n , яке визначає кількість властивостей об’єкта A , що входять до його специфікації )(AP . Об’єкти A і B є однотипними тоді й тільки тоді коли вони мають однакову розмірність і їм властива одна і та ж спе- цифікація. Властивості об’єктів глобально можна поділити на два типи – якісні та кількісні. Кількісні властивості представлятимемо наступним чином: )))(()),((()( ApuApvAp iii  , де )(Api – ідентифікатор i -ї властивості, ))(( Apv i – кількісне значення, ))(( Apu i – одиниці вимірювання кількісного значення властивості. Якісні властивості представ- лятимемо наступним чином: )()( AfAp ii  , де )(Afi – функція перевірки виконання властивості ip для об’єкта A і приймає значення з множини ]1,0[M . Якщо ( ) 1,if A  то властивість ip виконується для об’єкта A , якщо ( ) 0,if A  то власти- вість ip не виконується для об’єкта A і якщо kAfi )( , де ]1,0[k , то властивість ip частково виконується для об’єкта A , тобто виконується з певною мірою. Класи об’єктів. У загальному об’єкти можна поділити на конкретні (реально матеріально існуючі) та абстрак- тні. Кожен конкретний об’єкт, не залеж- но від того коли і як він був створений, є нічим іншим, як матеріальною реаліза- цією свого абстрактного образу – прото- типу. Кожен прототип за суттю, є абст- рактною специфікацією для створення майбутніх реальних об’єктів. Окрім влас- тивостей об’єктів також варто виділити операції (методи), які можна застосувати до об’єктів враховуючи особливості їх специфікації. В об’єктно-орієнтованому програмуванні [5], використовують спе- цифікацію та сигнатуру об’єкта без само- го об’єкта називаючи це типом або кла- сом об’єкта, тому використавши цю ідею сформулюємо визначення класу об’єктів. Клас об’єктів – це абстрактна спе- цифікація та набір операцій (сигнатура) певної кількості довільних об’єктів. Поз- начатимемо клас об’єктів наступним чи- ном:  ))(),(( TFTPT )))(),...,(()),(),...,((( 11 TfTfTpTp kn , де T – ім’я класу, )(TP – абстрактна спе- цифікація, а )(TF – набір операцій (мето- дів), які можна застосовувати до об’єктів класу T враховуючи особливості їх спе- цифікації. Клас об’єктів є однорідним тоді і тільки тоді коли до нього відносяться ли- ше однотипні об’єкти. Якщо клас T – однорідний клас, то його специфікація матиме наступний вигляд: ))(()( TCoreTP  , де )(TCore – ядро специфікації )(TP , що містить властивості, які є спільними для всіх об’єктів класу T . Якщо клас T – неоднорідний клас, то його специфікація матиме наступний вигляд: ))(),...,(),(()( 11 nn AprAprTCoreTP  , де )(),...,( 11 nn AprApr – проекції об’єктів nAA ,...,1 , що містять властивості які вико- нуються лише для цих об’єктів. Зрозуміло, що )(TCore існуватиме лише тоді, коли специфікації )(),...,( 1 nAPAP , міститимуть хоча б одну спільну властивість. Важливою особливістю неоднорід- них класів є те, що до цих класів можуть належати об’єкти, що володіють різними специфікаціями, на відміну від ООП, де кожен конкретний об’єкт, що належить до певного класу володіє у повній мірі всією специфікацією батьківського класу, а та- кож до нього можна застосувати всі мето- ди, які оголошені в даному класі. Теоретичні та методологічні основи програмування 20 Очевидно, що будь-який об’єкт A належить, як мінімум до одного класу AT , проте це все залежить від того, як трак- тувати поняття належності. Спираючись на роботу Л. Заде [3], множна виділити три типи належності – повна, часткова і нульова. Для формального представлення належності, особливо часткової, Л. Заде використовує характеристичну функцію ]1,0[)( x , яка відображає міру належ- ності елемента x до деякої нечіткої множини A . Використаємо цю ідею у на- шому випадку і опишемо належність об’єкта A до однорідного та неоднорі- дного класу. Розглянемо будь-який однорідний клас T , який описується деякою специфі- кацією ))(),...,(()( 1 TpTpTP n та будь- який об’єкт A , що описується специфіка- цією ))(),...,(()( 1 ApApAP n . Якщо )()( TDAD  або i , ni ,1 )),(())(( TpvApv ii  або ))(( Apu i )),(( Tpu i або )()( TfAf ii  , то об’єкт A не належить до однорідного класу T , тобто 0)( TA – нульова належ- ність. Якщо )()( TDAD  та i , ni ,1 ))(())(( TpvApv ii  та ))(())(( TpuApu ii  або )()( TfAf ii  , то об’єкт A належить до однорідного класу T , тобто 1)( TA – повна належність. Якщо )()( TDAD  та i , ni ,1 ))(())(( TpvApv ii  і ))(())(( TpuApu ii  або )()( TfAf ii  , то об’єкт A належить до однорідного класу T частково, тобто kTA  )( , де k визначається наступ- ним чином: ))(( ))(( Tpv Apv k i i , коли )(Api та )(Tpi – кількісні властиво- сті об’єкта A ; )( )( Tf Af k i i , коли )(Api та )(Tpi – якісні властивості об’єкта A . Якщо клас T – неоднорідний клас, то він описується наступною специфіка- цією ))(),...,(()( 1 TpTpTP m . Якщо )()( TDAD  або ji, , ni ,1 , mj ,1 ))(())(( TpvApv ii  або ))(())(( TpuApu ii  , або )()( TfAf ii  , то об’єкт A не належить до неоднорідного класу T , тобто 0)( TA – нульова на- лежність. Якщо )()( TDAD  та i , ni ,1 і j , mj ,1 для яких ))(())(( TpvApv ji  та ))(())(( TpuApu ji  або )()( TfAf ji  , то об’єкт A належить до неоднорідного класу T , тобто 1)( TA – повна нале- жність. Якщо )()( TDAD  та ji, , ni ,1 mj ,1 для яких ))(())(( TpvApv ji  і ))(())(( TpuApu ji  або )()( TfAf ji  , то об’єкт A належить до неоднорідного кла- су T частково, тобто kTA  )( , де k визначається наступним чином: ))(( ))(( Tpv Apv k j i , коли )(Api та )(Tpi – кількісні властиво- сті об’єкта A ; )( )( Tf Af k j i , коли )(Api та )(Tpi – якісні властивості об’єкта A . Множини об’єктів. Спираючись на поняття «об’єкт» і «клас об’єкта», сфор- мулюємо визначення поняття «множина об’єктів». Множина об’єктів S – це об’єдна- ння, що задовольняє одну із наступних схем: ,/...:)1 1 Sn TSOOS  ,/......:)2 11 Snm TSOOSSS  ,/...:)3 1 Sm TSSSS  де iO , ni ,1 – це об’єкти, jS , mj ,1 – Теоретичні та методологічні основи програмування 21 множини об’єктів, при цьому iO та jS можуть відноситись до абсолютно різних класів, а ST – клас новоутвореної множини об’єктів S , специфікація якого має насту- пну структуру: ))(),...,(),(()( 11 nnSS OprOprTCoreTP  , де )( STCore – ядро специфікації класу ST , що включає у себе властивості, які є спіль- ними для специфікацій об’єктів nOO ,...,1 , а )(),...,( 11 nn OprOpr – проекції об’єктів, що містять властивості, які властиві лише об’єктам nOO ,...,1 . Елементами множини об’єктів мо- жуть бути лише об’єкти. Множина об’єктів 1S є підмножи- ною множини об’єктів S тоді і тільки тоді коли всі її об’єкти також входять до мно- жини об’єктів S . Тобто, якщо },{1 BAS  , а },,,{ DCBAS  , то SS 1 . Потужність множин об’єктів S – це кількість об’єктів, що відносяться до цієї множини. Позначатимемо потужність мно- жини об’єктів nS \|\| . Операції над об’єктами В класичній теорії множин [3] визначають операції об’єднання, перети- ну, різниці, доповнення та симетричної різ-ниці. Ці ж самі операції визнача- ються і в теорії нечітких множин [6, 7], де окрім класичних операцій визначають ще операції алгебраїчного добутку та суми, декартового добутку, концентрації, деконцентрації та декомпозиції, що базу- ється на понятті  -розрізу. Проте всі вище згадані операції визначені на мно- жинах, в нашому ж випадку визначимо операції на об’єктах, як складових части- нах множин і цим самим введемо новий рівень у теорії множин – рівень об’єктів, який є нижчим ніж рівень множин, які вони утворюють. Об’єднання (схема 1). Об’єднання  в єдине ціле не менше ніж двох довіль- них об’єктів довільних класів – це множи- на об’єктів S , що визначається наступним чином: SnAnA TAATATAS n /},...{/.../ 11 1  , де ST – клас новоутвореної множини, який утворюється, як SAA TTT n ... 1 і його специфікація має наступну структуру: ))(),...,(),(()( 11 nnSS AprAprTCoreTP  , де )( STCore – це ядро специфікації класу ST , що включає у себе властивості, які є спільними для специфікацій об’єктів nAA ,...,1 , а )(),...,( 11 nn AprApr – це проекції об’єктів, що містять властивості, які влас- тиві лише об’єктам nAA ,...,1 . Об’єднання (схема 2). Об’єднання  в єдине ціле не менше ніж деякої однієї множини об’єктів },...,{ 11 mBBS  та не менше ніж одного довільного об’єкта до- вільного класу – це множина об’єктів S , що визначається наступним чином: SmAS TABBTATSS /},,...,{// 1111 11  , де ST – клас новоутвореної множини, який утворюється, як SAS TTT  11 , а його спе- цифікація має наступну структуру: ))(),(),(()( 11 AprBprTCoreTP miiSS  , mi ,1 де )( STCore – це ядро специфікації класу ST , що включає у себе властивості, які є спільними для специфікацій об’єктів 11 ,,..., ABB m , а )(),( 11 AprBpr mii  – це прое- кції об’єктів, що містять властивості, які властиві лише об’єктам 11 ,,..., ABB m . Об’єднання (схема 3). Об’єднання  в єдине ціле не менше ніж двох довіль- них множин об’єктів довільних класів },...,{ 11 nAAS  та },...,{ 12 mBBS  – це множина об’єктів S , що визначається на- ступним чином: SjiSS TBATSTSS /},{// 21 21  , ni ,1 , а mj ,1 , де ST – клас ново- утвореної множини, утворений, як Теоретичні та методологічні основи програмування 22 SSS TTT  21 , а його специфікація має наступну структуру: ))(),(),(()( jjiiSS BprAprTCoreTP  , ni ,1 , а mnnj  , , де )( STCore – це яд- ро специфікації класу ST , що включає у себе властивості, які є спільними для спе- цифікацій об’єктів mn BBAA ,...,,,..., 11 , а )(),...,(),(),...,( 1111 mmnn BprBprAprApr – це проекції об’єктів, що містять властиво- сті, які властиві лише об’єктам ji BA , . Приклад 1. Розглянемо три об’єкти 321 ,, AAA , що описують деякі геометричні фігури, зокрема об’єкта 1A відповідатиме квадрат, об’єкта 2A – паралелограм, а об’єкта 3A – трапеція. Опишемо їх за до- помогою наступної специфікації: ))(),(),(),(()( 4321 iiiii ApApApApAP  , де )(1 iAp – кількість сторін, )(2 iAp – кі- лькість вершин, )(3 iAp – площа фігури і )(4 iAp – периметр фігури. Кожен з цих об’єктів належить до певного класу, зокрема, об’єкт 1A нале- жить до класу 1AT , об’єкт 2A до класу 2AT і об’єкт 3A до класу 3AT . Застосуємо опе- рацію об’єднання до цих об’єктів та ство- римо множину S  321 /// 321 AAA TATATAS STAAA /},,{ 321 . Створивши множину S , ми цим самим створили новий клас ST , який є класом множини об’єктів S і має наступну спе- цифікацію: )()( SS TCoreTP  , де ),,,(),,,(()( 32123211 AAApAAApTCore S  )),,,(),,,( 32143213 AAApAAAp оскільки об’єкти 321 ,, AAA описуються одною і тою ж специфікацією, при цьому кожен з них відповідає цій специфікації «по-своєму», з чого випливає однорідність класу ST . Отже, клас ST – це клас, що описує квадрати класу 1AT , паралелограми класу 2AT та трапеції класу 3AT , відповід- но множина об’єктів S – це множина ква- дратів класу 1AT , паралелограмів класу 2AT та трапецій класу 3AT . Приклад 2. Розглянемо два об’єкти 1A та 2A , що описують деякі геометричні фігури, зокрема об’єкта 1A відповідатиме трикутник, а об’єкта 2A – паралелепіпед. Опишемо їх за допомогою наступних спе- цифікацій: ))(),(),(),(()( 141312111 ApApApApAP  , ))(),(),(),(()( 242322212 ApApApApAP  , де )( 11 Ap – кількість сторін; )( 12 Ap – кі- лькість вершин; )( 13 Ap – площа фігури; )( 14 Ap – периметр фігури; )( 21 Ap – кіль- кість сторін; )( 22 Ap – кількість вершин; )( 23 Ap – кількість граней; )( 24 Ap – об’єм фігури. Кожен з цих об’єктів належить до певного класу, зокрема, об’єкт 1A нале- жить до класу 1AT , а об’єкт 2A – до класу 2AT . Застосуємо операцію об’єднання до цих об’єктів та створимо множину S ./},{// 2121 21 SAA TAATATAS  В результаті створення множини ми також отримали новий клас ST , який є класом множини об’єктів S і має наступну спе- цифікацію: ))(),(),(()( 2211 AprAprTCoreTP SS  , де )),,(),,(()( 212211 AApAApTCore S  )),(),(()( 141311 ApApApr  )),(),(()( 242321 ApApApr  Оскільки специфікації )( 1AP та )( 2AP Теоретичні та методологічні основи програмування 23 мають спільні властивості )()( 2111 ApAp  , )()( 2212 ApAp  , проте ці властивості не повністю не вичерпують специфіка- ції )( 1AP та )( 2AP , чим власне і поясню- ється існування проекцій )( 11 Apr та )( 22 Apr , з чого випливає неоднорідність класу ST . Отже новоутворений клас ST – це клас, що описує трикутники класу 1AT та паралелепіпеди класу 2AT , відпо- відно множина об’єктів S – це множина трикутників класу 1AT та паралелепіпе- дів класу 2AT . Перетин. Перетин  двох довіль- них об’єктів, 1A та 2A – це абстрактний об’єкт A класу AT , специфікація якого визначається наступним чином:       )),(),(min(, ;1))(),((),( )( 2121 211 211 ADADiibreak ApApEqAp TP iii A де )( 11 Api та )( 22 Api – властивості спе- цифікацій )( 1AP та )( 2AP . Приклад 3. Розглянемо два об’єкти 1A та 2A , що описують натуральні числа 1563725 та 382729 відповідно. Опишемо об’єкти 1A та 2A , за допомогою наступних специфікацій: )),(),...,(()( )),(),...,(()( 29212 110111 ApApAP ApApAP   де )(),...,( 1711 ApAp та )(),...,( 2621 ApAp – цифри з яких складається число, )( 18 Ap та )( 27 Ap – кількість цифр у числі, )( 19 Ap та )( 28 Ap – кількість парних цифр у числі і )( 110 Ap та )( 29 Ap – кількість непарних цифр у числі. Застосуємо операцію пере- тину до об’єктів 1A та 2A (табл. 1). В ре- зультаті отримаємо новий абстрактний об’єкт A AAA TATATA /// 21 21  , який матиме наступну специфікацію: ))(),...,(()( 61 ApApAP  . Таблиця 1. Результати операції перетину об’єктів 1A та 2A iij AAp /)( 1A 2A A 1p 1 3 3 2p 5 8 7 3p 6 2 2 4p 3 7 3 5p 7 2 1 6p 2 9 2 7p 5 6 8p 7 3 9p 2 3 10p 5 В результаті операції перетину об’єктів 1A та 2A ми отримали новий об’єкт A , який має специфікацію )(AP , де )(),...,( 31 ApAp – це цифри з яких скла- дається число, )(4 Ap – кількість цифр у числі, )(5 Ap – кількість парних цифр у числі і )(6 Ap – кількість непарних цифр у числі. Різниця. Різниця \ двох довільних об’єктів 1A та 2A – це абстрактний об’єкт A класу AT , специфікація якого визнача- ється наступним чином:       ),(, ;0))(),((),( )( 11 211 211 ADibreak ApApEqAp TP iii A де )( 11 Api та )( 22 Api – властивості спе- цифікацій )( 1AP та )( 2AP . Приклад 4. Розглянемо об’єкти 1A та 2A з прикладу 3, та застосуємо до них операцію різниці (табл. 2). В результаті отримаємо нові абстрактні об’єкти 2\1A та 1\2A ,//\/ 2\121 2\121 AAA TATATA  ,//\/ 2\121 2\121 AAA TATATA  які матимуть наступні специфікації: )),(),...,(()( 2\172\112\1 ApApAP  Теоретичні та методологічні основи програмування 24 )).(),...,(()( 1\251\211\2 ApApAP  Таблиця 2. Результати операції різниці об’єктів 1A і 2A та 2A і 1A iij AAp /)( 1A 2A 2\1A 1\2A 1p 1 3 1 8 2p 5 8 5 9 3p 6 2 6 2 4p 3 7 5 1 5p 7 2 4 1 6p 2 9 1 7p 5 6 3 8p 7 3 9p 2 3 10p 5 В результаті операції різниці об’єктів 1A і 2A та 2A і 1A ми отримали нові об’єкти 2\1A та 1\2A відповідно, які мають специфікації )( 2\1AP та )( 1\2AP , де )(),...,( 2\142\11 ApAp та )(),( 1\221\21 ApAp – це цифри з яких складається число, )( 2\14 Ap та )( 1\23 Ap – кількість цифр у числі, )( 2\15 Ap та )( 1\24 Ap – кількість па- рних цифр у числі і )( 2\16 Ap та )( 1\25 Ap – кількість непарних цифр у числі. Симетрична різниця. Симетрична різниця  двох довільних об’єктів 1A та 2A – це абстрактний об’єкт A класу AT , специфікація якого визначається наступ- ним чином:          )),(),(max(, ;0))(),((),( ;0))(),((),( )( 2121 122 211 122 211 ADADiibreak ApApEqAp ApApEqAp TP iii iii A де )( 11 Api та )( 22 Api – властивості спе- цифікацій )( 1AP та )( 2AP . Приклад 5. Розглянемо об’єкти 1A та 2A з прикладу 3, та застосуємо до них операцію симетричної різниці (табл. 3). Як результат отримаємо новий абстрактний об’єкт A AAA TATATA /// 21 21  , який матиме наступну специфікацію: ))(),...,(()( 91 ApApAP  . Таблиця 3. Результати операції симетрич- ної різниці об’єктів 1A та 2A iij AAp /)( 1A 2A A 1p 1 3 1 2p 5 8 5 3p 6 2 6 4p 3 7 5 5p 7 2 8 6p 2 9 9 7p 5 6 6 8p 7 3 2 9p 2 3 4 10p 5 В результаті операції симетричної різниці об’єктів 1A та 2A ми отримали новий об’єкт A , який має специфікацію )(AP , де )(),...,( 61 ApAp – це цифри з яких складається число, )(7 Ap – кіль- кість цифр у числі, )(8 Ap – кількість пар- них цифр у числі і )(9 Ap – кількість непа- рних цифр у числі. Клонування. Результатом операції клонування об’єкта A буде новий об’єкт (клон) iA , ni ,1 , який володітиме такою ж специфікацією буде належати до того ж класу, що й об’єкт A , тобто )()( APAP i  та )()( ATAT i  )),(),...,(()( 1 ApApAClon ni  де iA – i -й клон об’єкта A . Мультимножини об’єктів З робіт [8–10] відомо, що мульти- множина – це множина елементи якої мо- жуть входити до цієї множини більше ніж один раз. Тобто мультимножина це деяке узагальнення поняття множини. Теоретичні та методологічні основи програмування 25 Формально мультимножину визна- чають, як впорядковану пару ),( mA , де A – множина, а m – функція, що ставить у відповідність кожному елементу мно- жини A деяке натуральне число, яке називається кратність елемента, тобто NAm : . Проте, як і у випадку множин, кла- сична теорія не дає відповіді на питання про походження так званих «вже існую- чих» мультимножин. Тому визначимо по- няття «мультимножина об’єктів» та за- пропонуємо деякі методи створення му- льтимножин об’єктів. Мультимножина об’єктів S – мно- жина об’єктів, що містить не менше двох еквівалентних об’єктів і в залежності від схеми її створення для неї має виконува- тися одна з наступних умов: 1. kS , таке що nk OOS  ...1 ; 2. kS , таке що                    m j j n i ik SOS 11 , 3. kS , таке що mk SSS  ...1 ; де kS – множина об’єктів, що містить не менше двох еквівалентних об’єктів. Тепер введемо деякі допоміжні ви- значення. Потужність мультимножини об’єк- тів S – це кількість об’єктів, що до неї відносяться. Позначатимемо потужність мультимножини об’єктів S . Базисна множина bS – це множина об’єктів, які входять хоча б один раз до мультимножини об’єктів S . Тепер ми можемо ввести наступну операцію: bSSbs )( , де )( bSbs – операція результатом якої є базисна множина об’єктів bS для мульти- множини об’єктів S . Тобто у нас є деяка мультимножина об’єктів },,,,{ CCBAAS  , то для неї },,{)( CBASSbs b  . Конструктори мультимножини об’єктів Універсальний конструктор. Роз- глянемо деякий об’єкт A , який має специ- фікацію ))(),...,(()( 1 ApApAP n та нале- жить до класу AT . Застосуємо до нього тричі операцію клонування ;/)))(),...,(/(()( 11 An TApApAAClone  ;/)))(),...,(/(()( 12 An TApApAAClone  ./)))(),...,(/(()( 13 An TApApAAClone  Тепер застосуємо до об’єкта A та до його клонів 321 ,, AAA операцію об’єднання та створимо множину об’єктів  AAAA TATATATAS //// 321 STAAAA /},,,{ 321 , де ST – клас новоутвореної множини об’єктів S , специфікація якого в зага- льному випадку має вигляд )()( SS TCoreTP  . Очевидно, що S – однорідна мульти- множина об’єктів, оскільки 321 AAAA  . Виходячи з всього вище сказаного, можна зробити висновок, що в загальному випад- ку   n i i ACloneAS 1 )(   , де S – однорідна мультимножина об’єктів. Тепер можемо покращити цей конструктор шляхом його узагальнення на випадок неоднорідних мультимножин. Розглядатимемо два різнотипні об’єкти A та B , що володіють різними специфікаціями )(AP та )(BP і належать до класів AT та BT відповідно. Тепер за- стосуємо до них операцію клонування, та двічі клонуємо об’єкт A та тричі об’єкт B , тобто: ;/)))(),...,(/(()( 11 An TApApAAClone  Теоретичні та методологічні основи програмування 26 ;/)))(),...,(/(()( 12 An TApApAAClone  ;/)))(),...,(/(()( 11 Bm TBpBpBBClone  ;/)))(),...,(/(()( 12 Bm TBpBpBBClone  ./)))(),...,(/(()( 13 Bm TBpBpBBClone  Також застосуємо до об’єктів A , B та їх клонів операцію об’єднання та ство- римо нову множину об’єктів  AAA TATATAS /// 21  BBBB TBTBTBTB //// 321 STBBBBAAA /},,,,,,{ 32121 , де ST – клас новоутвореної множини об’єктів S , специфікація якого в загаль- ному випадку матиме вигляд ))(),(),(()( 21 BprAprTCoreTP SS  . Очевидно, що S – це неоднорідна мульти- множина об’єктів, оскільки 21 AAA  , і 321 BBBB  а об’єкти A та B нале- жать до різних класів. Спираючись на ви- ще наведені факти можна зробити висно- вок, що в загальному випадку    n i n j iji i ACloneAS 1 1 )(            , де S – це неоднорідна мультимножина об’єктів. Детерміновані конструктори. За- пропонований вище універсальний конст- руктор мультимножин об’єктів дозволяє створювати довільні мультимножини об’єктів. У результаті чого ми можемо отримувати однорідні та неоднорідні му- льтимножини об’єктів. Проте не важко помітити, що такий підхід є досить віль- ним, що дозволяє адаптувати його до різ- них конкретних випадків, але основною його особливістю є суб’єктивний фактор. Розглянемо декілька детермінова- них конструкторів мультимножин об’єк- тів, які дозволяють будувати мультимно- жини об’єктів різних класів за певними, чітко визначеними правилами. Конструктор-1 (К-1). Розглянемо концепцію множини всіх підмножин де- якої множини наведене в [2]. Множина всіх підмножин множини A називається множиною-степенем множини A та поз- начається }\|{)( APPAP  . Тобто, для множини }3,2,1{A },3,2{},3,1{},2,1{},3{},2{},1{{)( AP }}{},3,2,1{  . Враховуючи поняття «об’єкт» та «множина об’єктів», ми приходимо до то- го, що множини }1{ , }2{ , }3{ та }{ не підпадають під наведене вище визначення множини об’єктів і тому не є такими. Про- те, ми можемо використати концепцію бу- леану деякої множини, для побудови му- льтимножин об’єктів. Розглянемо деяку множину об’єктів },,{ CBAS  . Тепер побудуємо для неї всі можливі підмножини об’єктів, тобто },,{},,{ 21 CASBAS  },,{},,{ 43 CBASCBS  . З роботи [2] відомо, що кількість усіх мо- жливих підмножин деякої множини A ви- значається за формулою nAP 2)(  , де An  . У випадку обчислення кількості усіх можливих підмножин об’єктів деякої множини об’єктів S , попередня формула зводиться до наступного вигляду: 12)(  nSq n w , де SSw  , )( wSq – це кількість усіх мож- ливих підмножин об’єктів множини об’єктів S , а Sn  . Застосуємо операцію об’єднання до множин 4321 ,,, SSSS , та створимо нову множину об’єктів , тобто  4321 ////)( 4321 SSSS TSTSTSTSSP  321 /},{/},{/},{ SSS TCBTCATBA  4 /},,{ STCBA )(/},,,,,,,,{ SPTCBACBCABA , де )(SP – це мультимножина об’єктів, а )(SPT – її клас. Очевидно, що )(SP ство- Теоретичні та методологічні основи програмування 27 рена за схемою 3MS і при цьому викону- ється умова 3, отже )(SP – дійсно муль- тимножина об’єктів. Узагальнюючи вище сказане можна прийти до висновку, що  12 1 )(    n w w n SSP . Теорема 1. Потужність довільної мультимножини об’єктів S , що створена за допомогою К-1 обчислюється за насту- пною формулою: n n S n  2 2 , де Sn  , S – базисна множина для S . Доведення. Розглянемо множину },,{ cbaA  , що є множиною у розумінні класичної теорії множин. Відомо, що по- тужність її булеану 822)( 3  nAP . Побудуємо )(AP },,{},{},{},{},{{)( bacbaAP  }},,{},,{},,{ cbacbca . Можна помітити, що всі підмножин )(AP містять 12 елементів, тобто 12 2 23 )( 3   pq , де p – елемент однієї з підмножин )(AP . Використовуючи математичну індукцію приходимо до 2 2 )( nn pq  . Тепер побудуємо )(AP з урахуванням по- няття «множина об’єктів», тобто: }},,{},,{},,{},,{{)( cbacbcabaAP  . Тому логічно, що n n pq n  2 2 )( . Звідси випливає, що потужність мультимножини об’єктів, що створена за допомогою К-1 обчислюється за форму- лою n n S n  2 2 , що і треба було довести. Кількість підмножин об’єктів різної потужності, що побудовані на основі де- якої базисної множини об’єктів та потуж- ності мультимножин об’єктів утворених за допомогою К-1 можна рахувати, за допо- могою спеціальної матриці ........................... 16152015657186 15101052675 14641128 13349 1212 ...65432)( bw SSqS , де стовпчики S та )( wSq відображають потужність побудованої мультимножини об’єктів, та кількість підмножин об’єктів з яких вона була утворена відповідно. Стов- пчик bS відображає потужність базисних множин об’єктів, на основі яких генеру- ються відповідні мультимножини об’єктів. Перший рядок починаючи з 4-го стовпчика відображає кількість підмножин об’єктів певної потужності, де потужність збігаєть- ся з значенням 4,1 ja . Елементи стовпчика )( wSq розра- ховуються за формулою    4,2 ,)( ji jikw aSq , де i – фіксоване, або формулою 12)(  nSq n kw , а елементи стовпчика S за формулою    4,2 ,1, ji jjik aaS , де i – фіксоване, або за формулою n n S n k  2 2 . Елементи матриці, для яких ni ,2 та Теоретичні та методологічні основи програмування 28 mj ,4 обчислюються наступним чином:        .2, ;2,1 ,11,1 , ijaa ij a jiji ji Конструктор-2 (К-2). Розглянемо декомпозицію множини об’єктів на такі пари підмножин об’єктів об’єднавши які можна отримати початкову множину об’єктів. Нехай },,,{ DCBAS  – множина об’єктів. Виконаємо її декомпозицію на підмножини об’єктів. Існує три варіанти такої декомпозиції },,{},,{ 21 DCSBAS  },,{},,{ 43 DBSCAS  }.,{},,{ 65 CBSDAS  Кількість усіх підмножин об’єктів множини об’єктів S які можливо утворити шляхом декомпозиції обчислюється на- ступним чином: 222)(  nSq n i , де Sn  . Застосуємо операцію об’єднання до множин об’єктів 61,..., SS та утворимо но- ву множину об’єктів, тобто:  321 ///)( 321 SSS TSTSTSSD  654 /// 654 SSS TSTSTS )(/},,,,,,,,,,,{ SDTCBDADBCADCBA , де )(SD – це мультимножина об’єктів, а )(SDT – її клас. Очевидно, що )(SD ство- рена за схемою 3MS і при цьому викону- ється умова 3, отже )(SD – дійсно муль- тимножина об’єктів. Узагальнюючи вище сказане можна прийти до висновку, що  222 1 )(    n w w n SSD , де )(SD – множина об’єктів, SSw  , а Sn  . Лема 1. На основі будь-якої мно- жини об’єктів потужності n можна побу- дувати n підмножин об’єктів розмірності 1n . Доведення. Розглянемо множину об’єктів },,,{ DCBAA  . Очевидно, що на її основі можна побудувати 4 підмножини об’єктів потужності 3, тобто: },,{},,,{ 21 DBAACBAA  , },,{},,,{ 43 DCBADCAA  . Використовуючи математичну індукцію, приходимо до того, що на основі множини об’єктів потужності n можна побудувати n підмножин об’єктів потужності 1n , що і треба було довести. Наслідок. Результатом об’єднання множини об’єктів потужності n та n під- множин об’єктів потужності 1n , які мо- жна на її основі побудувати, є множина об’єктів потужності 2n . Теорема 2. Потужність довільної мультимножини об’єктів S , що створена за допомогою К-2 обчислюється за насту- пною формулою: )( 2 2 2 nn n S n  , де Sn  і S – базисна множина для *S . Доведення. Розглянемо множину об’єктів },,,{ DCBAS  , та дві мульти- множини об’єктів A та B , що побудовані на її основі за допомогою К-1 та К-2 від- повідно, тобто:  },{},{},{},{ CBDACABAA  },,{},,{},{},{ DBACBADCDB  },,,{},,{},,{ DCBADCBDCA ,,,,,,,,,,,,,,,{ CBADCDBCBDACABA },,,,,,,,,,,, DCBADCBDCADBA ;  },{},{},{},{ DBCADCBAB  },{},{ CBDA },,,,,,,,,,,{ CBDADBCADCBA . Дивлячись на мультимножину об’єктів B , можна помітити, що на відміну від муль- тимножини об’єктів A в об’єднання не потрапляють одна підмножина об’єктів потужності n та n підмножин об’єктів потужності 1n (це випливає з леми 1). За теоремою 1 Теоретичні та методологічні основи програмування 29 n n A n  2 2 . Враховуючи цей факт, специфіку К-1 за відношенням до К-2 та наслідок леми 1, приходимо до того, що )( 2 2 2 nn n B n  , що і треба було довести. Кількість підмножин об’єктів різної потужності, що побудовані на основі де- якої базисної множини об’єктів та потуж- ності мультимножин об’єктів утворених за допомогою К-2 можна рахувати, за допо- могою спеціальної матриці, , ........................... 28567056288238952 213535217112392 152015650150 101052050 64612 ...65432)( bw SSqS де стовпчики S та )( wSq відображають потужність побудованої мультимножини об’єктів, та кількість підмножин об’єктів з яких вона утворена відповідно. Стовпчик bS відображає потужність базисних мно- жин об’єктів, на основі яких генеруються відповідні мультимножини об’єктів. Пер- ший рядок починаючи з 4-го стовпчика відображає кількість підмножин об’єктів певної потужності, де потужність збігаєть- ся з значенням 4,1 ja . Елементи стовпчика )( wSq розра- ховуються за формулою    4,2 ,)( ji jikw aSq , де i – фіксоване, або за формулою 222)(  nSq n kw , а елементи стовпчика \|\| S за формулою    4,2 ,1, ji jjik aaS , де i – фіксоване, або за формулою )( 2 2 2 nn n S n k  . Елементи матриці, для яких ni ,2 та mj ,4 обчислюються наступним чином:            .21, ;2,4, ;4,2,6 ,11,1 2,11,1, jaa ijjaa ji a jiji jjiji Загальна схема конструктора. Узагальнюючи К-1 та К-2, можна прийти до висновку, що побудову мультимножин об’єктів можна розглядати, як деяку функ- цію від базисної множини об’єктів, за до- помогою якої власне і утворюється муль- тимножина об’єктів. Називатимемо таку функцію генеруючою функцією або просто конструктором мультимножин, та позна- чатимемо її наступним чином: SSg b )( , де bS – базисна множина на основі якої за допомогою генеруючої функції )( bSg , утворюється мультимножина об’єктів S . Зрозуміло, що К-1 та К-2 є конкре- тними прикладами детермінованих конст- рукторів мультимножин. Очевидно, що повинна існувати і зворотна функція до функції )( bSg bSSg  )(1 , результатом якої буде базисна множина об’єктів bS . Прикладом такої функції є операція )(Sbs . Висновки У даній статті пропонується ви- значення певних операцій над об’єктами, що описують деякі сутності, визначення поняття «мультимножина об’єктів» та схеми створення однорідних та неоднорід- них множин та мультимножин об’єктів у рамках CST. Запропоновані схеми створення однорідних та неоднорідних множин і му- льтимножин об’єктів, дозволяють кон- структивно визначити поняття «множина Теоретичні та методологічні основи програмування 30 об’єктів» та «мультимножина об’єктів», що в свою чергу дозволяє говорити про можливість деякої практичної реалізації так званих конструкторів множин та муль- тимножин об’єктів. Також у статті пропонуються два універсальних та два детермінованих кон- структори мультимножин об’єктів різних класів, пропонується загальна схема конс- труктора мультимножин об’єктів. Запропоновані операції над об’єк- тами дозволяють будувати, класифікувати та порівнювати об’єкти та множини або мультимножини об’єктів, виділяти нові класи об’єктів, генерувати множини та му- льтимножини об’єктів за певним класом тощо, що дозволяє у певному сенсі прак- тично реалізувати для машини здатність оперувати такими базовими категоріями людського мислення як «множина» та «мультимножина». Отримані результати можуть бути застосовані в області програмування, шту- чного інтелекту, при проектуванні та роз- робці інтелектуальних інформаційних сис- тем, зокрема інтелектуальних експертних систем. 1. Ван Хао, Мак-Нортон Р. Аксиомати- ческие системы теории множеств. – М.: Издательство иностранной литературы, 1963. – 56 с. 2. Кантор Г. Труды по теории множеств. – М.: Наука, 1985. – 430 с. 3. Столл Р.Р. Множества. Логика. Акси- оматические теории. – М.: Просвещение, 1968. – 231 с. 4. Терлецький Д.О. Множини як сукупності- сутностей об’єктів // Комп’ютерна матема- тика. – 2013. – № 2. – C. 64–71. 5. Страуструп Б. Язык программирования С++. Специальное издание. – М.: Издате- льство Бином, Невский диалект, 2004. – 1054 с. 6. Рутковская Д., Пилиньский М., Рут- ковский Л. Нейронные сети генетические алгоритмы и нечеткие системы. – М.: Го- рячая линия-Телеком, 2006. – 452 с. 7. Zadeh L.A. Fuzzy sets. Іnformatіon and control. – 1965. – N 8. – P. 338–353. 8. Петровский А.Б. Пространства мно-жеств и мультимножеств.– М.: Едиториал УРСС, 2003. – 248 с. 9. De Bruijn N.G. Denumerations of rooted trees and multisets, Discrete Applied Mathematics. – 1983. – Vol. 6. – P. 25–33. 10. Syropoulos A. Mathematics of Multisets. – Proceedings of the Workshop on Multiset Processing: Multiset Processing, Mathema- tical, Computer Science, and Molecular Computing Points of View. – London, Springer-Verlag, 2001. – P. 347–358. Одержано 16.07.2013 Про автора: Терлецький Дмитро Олександрович, аспірант 2-го року навчання. Місце роботи автора: Київський національний університет імені Тараса Шевченка, факультет кібернетики, проспект Глушкова 4д. Тел: +38(044) 259 0511. E-maіl: dmytro.terletskyі@gmaіl.com

Designers sets and multisets of objects

Institution

Similar Items