Дослідження класів упорядкованих двомісних k-значних комутаційних функцій
У статті досліджено метричні властивості добре впорядкованих двомісних k-значних комутаційних функцій. Описаний основний принцип роботи алгоритму обчислення Np та два методи аналізу впорядкованих двомісних функцій k-значної логіки. В статье исследованы метрические особенности хорошо упорядоченных...
Saved in:
| Date: | 2009 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут проблем штучного інтелекту МОН України та НАН України
2009
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/8147 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Дослідження класів упорядкованих двомісних k-значних комутаційних функцій / З.Д. Коноплянко, К.П. Терещук // Штучний інтелект. — 2009. — № 4. — С. 45-51. — Бібліогр.: 8 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859469167478964224 |
|---|---|
| author | Коноплянко, З.Д. Терещук, К.П. |
| author_facet | Коноплянко, З.Д. Терещук, К.П. |
| citation_txt | Дослідження класів упорядкованих двомісних k-значних комутаційних функцій / З.Д. Коноплянко, К.П. Терещук // Штучний інтелект. — 2009. — № 4. — С. 45-51. — Бібліогр.: 8 назв. — укр. |
| collection | DSpace DC |
| description | У статті досліджено метричні властивості добре впорядкованих двомісних k-значних комутаційних
функцій. Описаний основний принцип роботи алгоритму обчислення Np та два методи аналізу
впорядкованих двомісних функцій k-значної логіки.
В статье исследованы метрические особенности хорошо упорядоченных двуместных k-значных функций.
Описан основной принцип работы алгоритма расчета Np и два метода анализа упорядоченных двуместных
функций k-значной логики.
|
| first_indexed | 2025-11-24T08:23:14Z |
| format | Article |
| fulltext |
«Штучний інтелект» 4’2009 45
2К
УДК 519.7
З.Д. Коноплянко, К.П. Терещук
Львівський інститут банківської справи Університету банківської справи
Національного банку України
zenovij@ukr.net, kostyatereshchuk@rambler.ru
Дослідження класів упорядкованих двомісних
k-значних комутаційних функцій
У статті досліджено метричні властивості добре впорядкованих двомісних k-значних комутаційних
функцій. Описаний основний принцип роботи алгоритму обчислення Np та два методи аналізу
впорядкованих двомісних функцій k-значної логіки.
Вступ
При сьогоднішніх соціально-економічних умовах первинна інформація має дуже
велику цінність. Проте при наявних обчислювальних засобах добути деякі важливі
знання надзвичайно складно, і це може займати багато часу і коштів. Одним із методів
зменшення вартості інформації є розвиток та впровадження k-значної логіки у проекту-
вання обчислювальних механізмів. Проте це несе за собою ряд комбінаторних проблем.
k-значна логіка є типом формальної логіки, в основі якої лежать натуральні чис-
ла, визначені на проміжку 1 ..., ,1 ,0 kEk . Функцією k-значної логіки є відобра-
ження виду k
n
kn EExxxf :)...,,,( 21 [1].
Оскільки в основі будь-яких алгебр лежать відповідні двомісні функції додавання та
множення (в комбінаториці – «+» та «», в булевій алгебрі – « » та « » тощо),
розглянемо двомісні функції k-значної логіки виду ))(),(( 2211 xxf , де )(),( 2211 xx –
функції, що реалізуються одновходовим універсальним елементом (мультиплексором) [2] і
пробігають усю множину функцій з 1
kP однієї змінної, тобто їх можна записати у
вигляді одновимірного кортежу. Усі функції, визначені на Ek, зі значеннями також у
1 ..., ,1 ,0 kEk .
Первісні результати у цій сфері щодо аналізу структури і роботи двовходового
k-значного логічного елемента та дослідження метричних властивостей двомісних
функцій k-значної логіки описані у [2-8].
Метою даної роботи є подальша розробка методів аналізу двомісних добре впо-
рядкованих k-значних комутаційних функцій, що дозволить у майбутньому впорядку-
вати деякі слабоструктуровані двомісні k-значні функції.
Суперпозицію двомісної k-значної комутаційної функції можна записати у виг-
ляді квадратної матриці (табл. 1).
При розгортанні суперпозиції функції двох змінних породжується kk 2 функцій,
але не всі з них різні. Проблема в тому, що немає єдиної аналітичної залежності, яка б
дозволила швидко підрахувати кількість різних функцій, які породжує довільна
двомісна функція (ця кількість в роботі позначається Np) [5]. Тому одним із методів
швидкого, але не універсального обчислення Np є пошук серед усіх функцій групи
впорядкованих функцій, Np яких можна обчислити за формулою.
Коноплянко З.Д., Терещук К.П.
«Искусственный интеллект» 4’2009 46
2К
Таблиця 1 – Суперпозиція двомісної функції ))(),(( 2211 xxf
)( 11 x ))(),(( 2211 xxf
0 1 … (k-1)
0 00e 01e … )1(0 ke
1 10e 11e … )1(1 ke
...
...
...
… ...
)( 22 x
(k-1) 0)1( ke 1)1( ke … )1)(1( kke
Де ije – значення функції ))(),(( 2211 xxf в точках, які визначаються функціями
однієї змінної )(),( 2211 xx [3].
Впорядковані функції, схожі на інші досліджувані
k- значні функції
Розглянемо, для прикладу, функцію ))(),(min())(),(( 22112211 xxxxf (даль-
ше min). Суперпозиція цієї функції при k = 3 має такий вигляд:
Таблиця 2 – Суперпозиція функції виду min
)( 11 x ))(),(min( 2211 xx
0 1 2
0 0 0 0
1 0 1 1 )( 22 x
2 0 1 2
У табл. 3 зображено механізм розгортання суперпозиції функції min при k = 3.
Як видно з цієї таблиці, функції однієї змінної )(),( 2211 xx набувають усіх можли-
вих значень від <0 0 0> до <2 2 2> в порядку лексикографічного наступного. Таких
суперпозицій кожної одномісної функції буде kk = 33 = 27, тому породиться 27 × 27= 729
суперпозицій двомісних функцій, але кількість різних буде Np = 411.
Таблиця 3 – Розгортання суперпозиції 3-значної функції виду min
Оскільки функція min є суттєво впорядкованою, то існує аналітичний вираз [9],
який дозволяє знайти Np цієї функції при будь-якому k:
2
1
( ( 1) ) .
k
k k
p
i
N i i
(1)
Дослідження класів упорядкованих двомісних k-значних комутаційних функцій
«Штучний інтелект» 4’2009 47
2К
Також існує певна кількість схожих на min функцій, Np яких обчислюється за
формулою (1).
Введемо число Nf – кількість різних, схожих за властивостями, функцій, Np яких
обчислюється за однією спеціалізованою формулою. Оскільки формула Np k-значної
функції не зміниться, якщо над нею проводити такі операції, як перестановки рядків
або стовпців (перша властивість Np), транспонування (друга властивість) та заміни еле-
ментів (третя властивість) функції, і поки відомо небагато випадків, коли Np не міня-
лась при перетворенні функції без використання жодної з цих операцій, під Nf будемо
розуміти кількість усіх різних двомісних k-значних функцій, утворених з функції
шляхом перестановок рядків (стовпців), транспонування та заміни її елементів. Тож,
усі двомісні k-значні функції, утворені із функції min за допомогою цих операцій,
можна віднести до одного класу еквівалентності (клас функцій виду min). Загалом, усі
3-значні двомісні функції (їх кількість становить 196833
22 3 kk ) можна за цими
трьома властивостями об’єднати аж у 75 класів, але деякі формули обчислення Np
можна зробити більш універсальними, щоб вони об’єднували кілька класів.
Для функції виду min при k = 3 число Nf = 216 (приблизно 1% від усіх 3-значних
функцій). Це залежить від того, що усі рядки і стовпці функцій даного виду є різними
(табл. 2), тому при перестановках рядків (стовпців) утвориться 2)!(!! kkk різних
функцій (згідно з першою властивістю Np). У даному випадку транспонування функції
не враховуємо при обчисленні Nf, тому що дана функція є симетричною відносно основ-
ної діагоналі, тобто її можна транспонувати шляхом перестановок рядків чи стовпців,
що вже було враховано. Дана функція має найбільше число нулів, потім одиниць і так
далі, тобто усі k елементів зустрічаються різну кількість разів (табл. 2), що не дозволяє
переставити місцями елементи функції за допомогою попередніх операцій. Тому можемо
легко обчислити кількість функцій, отриманих шляхом заміни одних елементів на інші
(третя властивість). Таких функцій можна утворити k!. Отже, використовуючи основне
правило комбінаторики (правило множення), маємо 32 )!(!)!( kkkN f .
Є також інші функції, схожі за властивостями на інші суттєво впорядковані
функції. Наприклад, суперпозиція функції
k
xkxkxxxxf ))(),(min())(),(min())(),(( 2211
22112211
відрізняється від ))(),(min( 2211 xx лише значенням при )0,0(f (табл. 2 і табл. 4).
Тому формула обчислення Np виведена із формули Np для функції min:
21
1
2 )12(2))1((
k
k
i
kk
p iiN . (2)
Таблиця 4 – Суперпозиція подібної до min функції
)( 11 x ))(),(( 2211 xxf
0 1 2
0 1 0 0
1 0 1 1 )( 22 x
2 0 1 2
Ще одним прикладом є суперпозиція функції, записаної з умовою:
))(),(min())(),(( 22112211 xxxxf , з умовою, що 0)1,1( f .
Для цієї функції
k
i
kk
p iiN
1
2))1(( .
Як видно, формула Np даної функції така ж, як і у функцій виду min, при чому за
допомогою перестановок рядків (стовпців), транспонування та заміни елементів цієї
Коноплянко З.Д., Терещук К.П.
«Искусственный интеллект» 4’2009 48
2К
функції можна утворити 3)!(kN f різних функцій, що також дорівнює Nf функцій
виду min. Таким чином кількість функцій, Np яких обчислюється за формулою (1) ста-
новить 333 )!(2)!()!( kkk .
Таблиця 5 – Суперпозиція подібної до min функції з додатковою умовою
)( 11 x ))(),(min( 2211 xx ,
0)1,1( f 0 1 2
0 0 0 0
1 0 0 1 )( 22 x
2 0 1 2
Алгоритм обчислення Np. Впорядковані функції,
несхожі на інші досліджувані k-значні функції
Проте є багато функцій, не схожих на інші досліджені впорядковані функції. За
допомогою розроблення універсального оптимізованого алгоритму для обчислення
Np можна вивести формули для таких класів впорядкованих k-значних функцій. Ідея
алгоритму обчислення Np проста [2], [5], [7] – аналізувати і перевіряти на унікаль-
ність потрібно не кожну функцію, а групу подібних за властивостями функцій.
Однією із таких властивостей є цифровість функцій однієї змінної (кількість чисел,
використаних в окремо взятій функції).
Таблиця 6 – Суперпозиція функції виду mod
)( 11 x kxx mod))()(( 2211
0 1 2
0 0 1 2
1 1 2 0 )( 22 x
2 2 0 1
Розглянемо детальніше алгоритм обчислення Np на прикладі впорядкованої
функції виду kxxxxf mod))()(())(),(( 22112211 (далі mod, табл. 6) з викорис-
танням цієї властивості. Для неї
k
kN
k
p
2)(
[8].
При розгортанні суперпозиції двомісної функції посортуємо функції однієї змінної
)(),( 2211 xx на 1-, 2-, ..., k-цифрові. У табл. 7 зображений приклад такого розгортання
для функції mod. Таким чином, можна сформувати таблицю з усіма групами породжених
функцій (табл. 8), у якій суперпозицій є набагато менше –
k
i
ki
kC
1
22 )12()( пере-
формованих суперпозицій. Це означає, що перебір при підрахунку Np буде невеликим
і при зростанні k кількість операцій, яку повинен здійснити комп’ютер, буде зростати
без комбінаторного вибуху, як при застосуванні методу прямого перебору.
У [3], [5] описана формула підрахунку числа різних кортежів i-го класу. Це є під-
хід через число розміщень без повторень i
kA та числа Стирлінга 2-го роду:
),(
1
ikAkN
k
i
i
k
k
,
де
)!(
!
ik
kAi
k
– число розміщень довжиною із k значень Ek;
Дослідження класів упорядкованих двомісних k-значних комутаційних функцій
«Штучний інтелект» 4’2009 49
2К
Таблиця 7 – Таблиця розгортання суперпозиції 3-значної функції виду mod,
трансформована згідно із розбиттям на класи еквівалентності функцій однієї змінної
Таблиця 8 – Вигляд таблиці істинності 3-значної комутаційної функції mod,
трансформованої згідно із розбиттям на класи еквівалентності функцій однієї змінної
kkk kkkk
k
i
ik
,..., 211
!!...!
!1),( – числа Стирлінга 2-го роду (числа розбиттів k-еле-
ментної множини на i блоків), причому
1),( kk , при k > 0;
0)0,( k , при k > 0;
),1()1,1(),( ikiikik , при 0 < i < k [1], [3].
Але кожен i-цифровий клас може містити i
kC підкласів, наприклад, при k = 3,
2-цифрові кортежі можуть містити такі сполучення чисел: {0,1}, {0,2}, {1,2}. Отже,
кількість кортежів розміру k, які можна утворити із i елементів, описується формулою:
!),(
!)!(
)!(!!),(
)!(!
!
)!(
!
),(),( iik
kik
ikikik
iki
k
ik
k
ik
C
Aik
i
k
i
k
.
Коноплянко З.Д., Терещук К.П.
«Искусственный интеллект» 4’2009 50
2К
За допомогою таких комбінаторних властивостей, а також інших особливостей
класів породжуючих функцій, можна швидко обчислити Np довільної функції.
Проте при великих значеннях k (8 і більше) використання такого алгоритму по-
требує дуже багато часу. Отже, для того щоби остаточно уникнути перебору, потрібно
формувати класи впорядкованих функцій та виводити унікальну для них формулу Np .
Найпростішими є уже описані суттєво впорядковані двомісні функції виду min і
mod, а також ті, які залежать тільки від однієї змінної. Для останніх
k
p nN , (3)
де n – кількість різних елементів функції. Суперпозиції деяких із них зображені в табл. 9.
Таблиця 9 – Суперпозиції залежних від однієї змінної двомісних функцій
)( 11 x )( 11 x 2mod)( 22 x
0 1 2
)( 22 x
0 1 2
0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 )( 22 x
2 0 0 0
)( 22 x
2 2 2 2
Усі інші двомісні k-значні комутаційні функції є складнішими. Їх оцінка по-
требує великих затрат часу. Наприклад, суперпозиція функції (табл. 10)
1
mod)1)()((
))(),(min())(),(( 2211
22112211 k
kxxkxxxxf
при розгортанні породжує таку кількість груп функцій, яку легко комбінаторно пере-
лічити і виведена формула обчислення Np повторює механізм описаного алгоритму:
))!1(!)1,(),(2)!),(((!
1
1
1
2
iiikikCiikCkN
k
i
i
k
i
kp , (4)
де ),( ik – числа Стирлінга 2 роду, i
kC – кількість комбінацій з k елементів по і елементах.
Таблиця 10 – Суперпозиція функції виду діагонального мінімуму
)( 11 x ))(),(( 2211 xxf
0 1 2
0 0 0 0
1 0 1 0 )( 22 x
2 0 0 2
Дуже близькою до цієї функції є функція діагонального виду (табл. 11)
1
mod))()(())(),(( 2211
2211 k
kxxxxf
.
Np функцій цього виду обчислюється за такою формулою:
)!)1,(),(2)!1)(,(())1,(21(!2
1
2
22 iikikiikkkkN
k
i
p
. (5)
Таблиця 11 – Суперпозиція функції діагонального виду
)( 11 x ))(),(( 2211 xxf
0 1 2
0 0 0 1
1 0 1 0 )( 22 x
2 1 0 0
Дослідження класів упорядкованих двомісних k-значних комутаційних функцій
«Штучний інтелект» 4’2009 51
2К
Як видно, формальний опис цих функцій є об’ємним, проте оцінка впорядкова-
них двомісних k-значних функцій дозволить оптимізувати роботу комутаційного облад-
нання, зокрема забезпечити необхідний обсяг пам’яті для здійснення відповідного
числа комутацій під час обслуговування процесів обміну даними у системах штучного
інтелекту.
Висновки
1. Серед усіх можливих двомісних k-значних комутаційних функцій існують
суттєво впорядковані функції, які можна об’єднати у класи за принципом того, що
кожну функцію певного класу можна звести до будь-якої іншої функції цього ж класу
за допомогою перестановок рядків, перестановок стовпців, транспонування і переста-
новок елементів функції, в результаті чого Np не зміниться.
2. Суть алгоритму обчислення Np полягає у тому, що аналізувати і перевіряти на
унікальність потрібно не кожну функцію, а групу подібних за властивостями функцій,
що дозволяє значно прискорити процедуру підрахунку Np.
3. Запропоновано два методи виведення формули Np впорядкованих функцій: на
основі порівняння їх з іншими впорядкованими функціями та виведення формули Np
«з нуля» за допомогою алгоритму обчислення Np.
4. Дослідження упорядкованих функцій дозволяє скоротити перебір при підра-
хунку числа різних функцій, які породжує довільна двомісна функція.
Література
1. Алексеев В.Б. Дискретная математика (II семестр): конспект лекций / В.Б. Алексеев, А.Д. Поспелов. –
М. : МГУ имени М.В. Ломоносова, 2002. – 44 с.
2. Пат. 20462 Україна, МКВ H03K 19/08. Двовходовий багатозначний логічний елемент / Бондаренко М.Ф.,
Коноплянко З.Д., Четвериков Г.Г. – № 97031289/24; заявл. 20.03.97; опубл. 15.07.97; Бюл. № 3. – 5 с.
3. Бондаренко М.Ф. Основи теорії багатозначних структур і кодування в системах штучного інтелекту /
Бондаренко М.Ф., Коноплянко З.Д., Четвериков Г.Г. – Х. : Фактор-Друк, 2003. – 336 с.
4. Коноплянко З.Д. Концепції організації інформаційно-інтелектуальних технологій та інтелектуальної
підтримки суспільно-економічних процесів / З.Д. Коноплянко, Д.П. Вєніков // Вісник УБС НБУ. –
2008. – № 1. – С. 180-182.
5. Коноплянко З.Д. Багатозначні структури та кодування систем економічної кібернетики : [монографія] /
Коноплянко З.Д., Чаплига В.М., Чаплига М.В. – Львів : ЛБІ НБУ, 2004. – 314 с.
6. Коноплянко З.Д. Дослідження метричних властивостей k-значних функцій / Коноплянко З.Д.,
Терещук К.П. // Международная научно-практическая конференция «Современные направления
теоретических и прикладных исследований’2008», (15 – 25 марта 2008 г., Одеса, Україна). – С. 37-42.
7. Коноплянко З.Д. Алгоритм обчислення Np у сфері досліджень метричних властивостей k-значних
функцій / З.Д. Коноплянко, К.П. Терещук // Международная научно-практическая конференция
«Современные направления теоретических и прикладных исследований’2008», (15 – 25 марта 2008 г.,
Одеса, Україна). – С. 42-46.
8. Реализация многозначных структур автоматики / под ред. М.А. Ракова. – К. : Наук. думка, 1976. – 350 с.
З.Д. Коноплянко, К.П. Терещук
Исследование классов упорядоченных двуместных k-значных коммутационных функций
В статье исследованы метрические особенности хорошо упорядоченных двуместных k-значных функций.
Описан основной принцип работы алгоритма расчета Np и два метода анализа упорядоченных двуместных
функций k-значной логики.
Стаття надійшла до редакції 27.05.2009.
|
| id | nasplib_isofts_kiev_ua-123456789-8147 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1561-5359 |
| language | Ukrainian |
| last_indexed | 2025-11-24T08:23:14Z |
| publishDate | 2009 |
| publisher | Інститут проблем штучного інтелекту МОН України та НАН України |
| record_format | dspace |
| spelling | Коноплянко, З.Д. Терещук, К.П. 2010-05-13T09:57:31Z 2010-05-13T09:57:31Z 2009 Дослідження класів упорядкованих двомісних k-значних комутаційних функцій / З.Д. Коноплянко, К.П. Терещук // Штучний інтелект. — 2009. — № 4. — С. 45-51. — Бібліогр.: 8 назв. — укр. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/8147 519.7 У статті досліджено метричні властивості добре впорядкованих двомісних k-значних комутаційних функцій. Описаний основний принцип роботи алгоритму обчислення Np та два методи аналізу впорядкованих двомісних функцій k-значної логіки. В статье исследованы метрические особенности хорошо упорядоченных двуместных k-значных функций. Описан основной принцип работы алгоритма расчета Np и два метода анализа упорядоченных двуместных функций k-значной логики. uk Інститут проблем штучного інтелекту МОН України та НАН України Интеллектуальный анализ данных Дослідження класів упорядкованих двомісних k-значних комутаційних функцій Исследование классов упорядоченных двуместных k-значных коммутационных функций Article published earlier |
| spellingShingle | Дослідження класів упорядкованих двомісних k-значних комутаційних функцій Коноплянко, З.Д. Терещук, К.П. Интеллектуальный анализ данных |
| title | Дослідження класів упорядкованих двомісних k-значних комутаційних функцій |
| title_alt | Исследование классов упорядоченных двуместных k-значных коммутационных функций |
| title_full | Дослідження класів упорядкованих двомісних k-значних комутаційних функцій |
| title_fullStr | Дослідження класів упорядкованих двомісних k-значних комутаційних функцій |
| title_full_unstemmed | Дослідження класів упорядкованих двомісних k-значних комутаційних функцій |
| title_short | Дослідження класів упорядкованих двомісних k-значних комутаційних функцій |
| title_sort | дослідження класів упорядкованих двомісних k-значних комутаційних функцій |
| topic | Интеллектуальный анализ данных |
| topic_facet | Интеллектуальный анализ данных |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/8147 |
| work_keys_str_mv | AT konoplânkozd doslídžennâklasívuporâdkovanihdvomísnihkznačnihkomutacíinihfunkcíi AT tereŝukkp doslídžennâklasívuporâdkovanihdvomísnihkznačnihkomutacíinihfunkcíi AT konoplânkozd issledovanieklassovuporâdočennyhdvumestnyhkznačnyhkommutacionnyhfunkcii AT tereŝukkp issledovanieklassovuporâdočennyhdvumestnyhkznačnyhkommutacionnyhfunkcii |