2.3. Метричні властивостіk-значних комутацiйних структур

Принципове значення метричних властивостей двомісних k-значних функцій полягає в тому, що вони характеризують алгоритмічні складності синтезу мінімальних структур, тобто відображають затрати обладнання чи компонентів, а також впливають на вибір методів у суміжних теоріях кодування, ймовірностей, комбінаторному аналізі, надійності та динамічному програмуванні [149]. Результати отриманi в [76] (див. р. 1.7) стосуються тiльки суттєво впорядкованих суперпозицiй i тому вимагають узагальнення та розвитку.

Для подальшого викладу введемо ряд позначень та визначень i проiлюструємо їх на прикладах суперпозицiї (1.22) для k = 3. У довiльнiй k-значнiй логiчнiй системi використовуються k констант: 0, 1, ..., k – 1, що належать множинi E_k. Функцiї k-значної логiки приймають значення також з E_k  {0, 1, ..., k – 1}, утворюючи при цьому впорядкованi кортежi довжиною k. Так, для прикладу, при k = 3 це будуть кортежi виду <000>, <002>, ..., <222>, число яких дорiвнює k^k = 3³ = 27. У викладi ми будемо використовувати комбiнаторне поняття кортежу як скiнченної упорядкованої послiдовностi компонент із множини E_k, оскільки всi подальшi дослiдження спираються на комбiнаторику та вiдповiдну термiнологiю [150-158].

Умовимося, що два кортежi  та  і вiдповiднi їм функцiї рiвнi, якщо вони мають однакову довжину i кожна компонента кортежу  збігається (рiвна) із вiдповiдною компонентою кортежу  з тим же номером, тобто кортежi (функцiї) <201> та <201> рiвнi, а <201> та <102> – нi. Вiдповiдно для суперпозицiї (1.22) функцiї двох змiнних будуть зображатися кортежами довжини k² i при k = 3 будуть мати вигляд: <000 000 000>, <000 000 001>, <000 000 002>, ..., <222 222 222>, а число їх дорiвнює k^k = = 19 683.

Рiвнiсть кортежiв також може бути встановлена й описана через відстань Лі [149]:

.

Виходячи з того, що k-значна логiка тісно пов’язана із k-значним кодуванням, у подальших викладах також використовується символiка та термiнологiя теорiї кодування.

Наступним є визначення класу еквiвалентностi функцiй, пiд яким розумiється потужнiсть пiдмножини функцiй, що володiють певною властивiстю, наприклад, до них можуть належати класи функцiї Q_k-i, що приймають iз Е_k значення не менше k – i, i = 0, 1, ..., k– 1.

Для подальших дослiджень та оцiнок розiб’ємо множину k-значних двомiсних суперпозицiй iз на класи еквiвалентностi Q_{k – i}. Потужнiсть множини функцiй дорiвнюєk^2k. Аналогiчно необхiдно розбити множину , потужнiсть якоїk^k, на класи еквiвалентностi Q_{k – i}, i = 1, 2, ..., k. Тут справедливе твердження [76], що число цих класiв – k. Таке розбиття множини дозволяє визначити спочатку число однакових функцiй (кортежiв) у кожному з класiв еквiвалентностi iз функцій однієї змінної. При цьому можливi два пiдходи до розбиття, що дають однаковий результат.

Розглянемо перший із них: довiльне значення одномісної k-значної функцiї  (х) може складатись iз k – i цифр: k цифр, k– 1 цифр, ..., 1 цифри або з використанням комбiнаторних спiввiдношень:

при k = 2:

, (2.11)

де – число сполучень ізm по n; P(k₁, k₂, ..., k^k) – число перестановок із повтореннями; k_i – число повторень і-ї компоненти кортежу довжини k;

при k = 3:

;

при k = 4:

Інший пiдхiд – через число розмiщень без повторень та числа Стирлiнга 2-го роду [150]:

, (2.12)

де – число розміщень ізk значень E_k довжиною і; – числа Стирлінга 2-го роду (число розбиттiвk-елементної множини на i блокiв), причому

Ф (k, k) = 1, при k  0;

Ф (k, 0) = 0, при k > 0;

Ф (k, i) = Ф (k – 1, і – 1) + i Ф (k – 1, i), при 0 < i < k.

Для значностей k = 3, 4, ..., 10 потужностi множин класiв еквiвалентних функцiй iз , обчислені згiдно з (2.12), наведено в табл. 2.2.

Для k = 3 прикладами класiв еквiвалентностi Q_{k– i} будуть такі iз : <000>, <111>, <222> – перший, <001>, <002>, <010>, ..., <202> (усього таких функцiй 18 у класi еквiвалентностi) – 2-й та <102>, <120>, <201>, ..., <210> – 3-й (усього 6 функцiй) класи еквiвалентностi відповідно.

Уведення поняття рiвностi кортежiв та еквiвалентностi класiв функцiй однiєї змiнної дозволяють розбити множину функцiй iз наk еквiвалентних класiв та, з одного боку, запропонувати ефективний метод дослiдження NP-складної задачi, а з iншого – зменшити число переборiв на множинi функцiй двох змiнних . Метод полягає в тому, що завдяки розбиттю функцiй однiєї змiнної на класиQ_{k – i} (i-цифровi), для дослiджень суперпозицiй функцiй двох змiнних достатньо задати та дослiдити лише k варiантiв першого рядка таблицi iстинностi. Для решти рядкiв – компоненти кортежiв формуються комбінаторно iз множини .

Таблиця 2.2

Потужності множин еквівалентних функцій із

Знач-ність k	1-й клас	2-й клас	3-й клас	4-й клас	5-й клас	6-й клас	7-й клас	8-й клас	9-й клас	10-й клас	Np
3	3	18	6	–	–	–	–	–	–	–	27
4	4	84	144	24	–	–	–	–	–	–	256
5	5	300	1500	1200	120	–	–	–	–	–	3125
6	6	930	10800	23400	10800	720	–	–	–	–	46656
7	7	2646	63210	294000	352800	105840	5040	–	–	–	823543
8	8	7112	324576	2857680	7056000	5362560	1128960	40320	–	–	16777216
9	9	18360	1524600	23496480	105099120	1600030080	83825280	13063680	362880	–	3874420489
10	10	45990	6717600	171889200	1285956000	843524896	738743296	1360800000	163296000	3628800	10000000000

85

Із метою формалізації такого пiдходу на даному етапi дослiджень уведемо узагальнений запис для таблиць iстинностi при k = 3:

f()		1(х1)
		0	1	2
	0	e00	e01	e02
	1	e10	e11	e12
	2	e20	e21	e22

Вiдповiдно до (2.11), пiсля пробiгання функцiями ,однiєї змiнної всiєї множини значень iз, узагальнена таблиця істинності трансформується в промiжну (табл. 2.3), із якої отримуємо матрицю iнцидентностi (табл. 2.4) кортежiв двомiсних функцiй приk = 3.

Таблиця 2.3

Таблиця істинності тризначної двомісної функції однієї змінної, трансформована за класами еквівалентності

f[]

1-цифрові

2-цифрові

3-цифрові

0

1

2

0

1

0

2

1

2

0

1

2

1-цифрові

0

e00

e01

e02

e00

e01

e00

e02

e01

e02

e00

e01

e12

1

e10

e11

e12

e10

e11

e10

e12

e11

e12

e10

e11

e12

2

e20

e21

e22

e20

e21

e20

e22

e21

e22

e20

e21

e22

2-цифрові

0

e00

e01

e02

e00

e01

e00

e02

e01

e02

e00

e01

e12

1

e10

e11

e12

e10

e11

e10

e12

e11

e12

e10

e11

e12

0

e00

e01

e02

e00

e01

e00

e02

e01

e02

e00

e01

e12

2

e20

e21

e22

e20

e21

e20

e22

e21

e22

e20

e21

e22

1

e10

e11

e12

e10

e11

e10

e12

e11

e12

e10

e11

e12

2

e20

e21

e22

e20

e21

e20

e22

e21

e22

e22

e21

e22

3-цифрові

0

e00

e01

e02

e00

e01

e00

e02

e01

e02

e00

e01

e12

1

e10

e11

e12

e10

e11

e10

e12

e11

e12

e10

e11

e12

2

e20

e21

e22

e20

e21

e20

e22

e21

e22

e20

e21

e22

Таблиця 2.4

Матриця інцидентності кортежів f []

aij	1	2	3	4	5	6	7
1	a11	a12	a13	a14	a15	a16	a17
2	a21	a22	a23	a24	a25	a26	a27
3	a31	a32	a33	a34	a35	a36	a37
4	a41	a42	a43	a44	a45	a46	a47
5	a51	a52	a53	a54	a55	a56	a57
6	a61	a62	a63	a64	a65	a66	a67
7	a71	a72	a73	a74	a75	a76	a77

У табл. 2.4 коефiцiєнт а₁₁ вiдповiдає за iнцидентнiсть одноцифрових двомiсних функцiй i завжди дорівнює 1, оскільки таких функцiй мусить бути хоч би одна, а в крайньому разі – k, залежно вiд того, скiльки цифр iз k входить у породжуючу суперпозицiю. Звiдси й випливає, що всього табл. 2.4 вмiщатиме при k = 3 не 9  9 коефiцiєнтiв а_ij, a 7  7 для довiльного k:

.

Решта коефiцiєнтiв a_ij = 1, коли кортежi у суперпозицiї, пiд час її розгортання за рахунок пробiгання всiєї множини, трапляються вперше та не мають собi рiвних серед ранiше переглянутих, у протилежному разіа_ij = 0.

Звiдси, згiдно з (2.11), значеннями a_ij та табл. 2.2, отримуємо алгоритмiчну залежнiсть для числа рiзних двомiсних функцiй (кортежiв):

, (2.13)

де g_i, g_j = P (k₁, ..., k_k) – числа перестановок із повтореннями i-го значення з Е_k.

Для визначення числа суперпозицiй двомiсних комутацiйних функцiй 3-значної логiки розроблено комплекс програм [52] пiдрахунку числа рiзних функцiй, породжуваних будь-якою суперпозицiєю iз P_k, а також сортування їх згiдно з цими числами, тобто програма розбиття множини P_k на класи еквiвалентностi за ознакою N_р.

У результатi проведених дослiджень отримано розбиття на класи еквiвалентностi всiх 19 683 породжуючих функцiй для k = 3 та n = 2. У порядку наростання числа рiзних N_p породжуваних суперпозицiй, представники 45 класів типових породжуючих функцiй наведено дальше списком, де N_f – число функцій у кожному класі еквівалентності:

	1	2	3	4	5	6	7
	0 0 0	0 0 0	0 0 0	1 0 0	0 0 0	0 0 0	1 0 0
А	0 0 0	0 0 0	1 1 1	1 0 0	0 0 0	0 0 0	1 0 0
	0 0 0	1 1 1	2 2 2	0 1 1	1 0 0	2 1 1	0 2 2
	Nf= 3	Nf= 8	Nf= 12	Nf= 54	Nf= 216	Nf= 216	Nf= 108
	Np = 1	Np = 36	Np = 27	Np = 32	Np = 50	Np = 57	Np = 63
	0 0 0	0 0 0	1 0 0	1 0 0	0 0 0	0 0 0	1 0 0
B	1 0 0	2 1 1	0 1 0	1 1 1	1 1 1	0 1 1	1 0 0
	0 11	1 2 2	0 0 1	1 0 0	2 0 0	200	2 2 0
	Nf= 216	Nf= 108	Nf= 36	Nf= 324	Nf= 432	Nf= 432	Nf= 720
	Np = 86	Np = 105	Np = 110	Np = 122	Np = 141	Np = 165	Np = 171
	1 0 0	1 0 0	1 0 0	0 0 0	0 0 0	0 0 0	1 0 0
C	1 0 0	1 0 0	0 2 2	1 0 0	2 1 1	1 0 0	1 1 0
	2 2 1	2 0 1	0 0 0	1 1 0	1 2 1	0 0 2	0 1 1
	Nf= 180	Nf= 648	Nf= 72	Nf= 432	Nf= 216	Nf= 120	Nf= 216
	Np =177	Np = 183	Np = 189	Np = 194	Np = 213	Np = 243	Np = 248
	1 0 0	0 0 0	0 0 0	1 0 0	0 0 0	0 0 0	1 0 0
D	0 1 0	2 1 1	2 0 0	0 1 2	1 0 0	0 1 2	1 1 0
	0 0 2	2 2 1	2 2 1	0 2 1	2 2 0	0 2 1	0 0 2
	Nf= 108	Nf= 216	Nf= 540	Nf= 108	Nf=1296	Nf= 54	Nf= 216
	Np =279	Np = 285	Np = 315	Np = 321	Np = 327	Np = 339	Np = 351
	0 0 0	1 0 0	1 0 0	0 0 0	0 0 0	1 0 0	0 0 0
E	1 0 0	2 0 0	0 1 1	1 1 0	1 1 0	0 1 0	1 1 0
	0 1 2	0 1 2	0 1 2	2 1 1	2 1 0	0 2 2	2 0 1
	Nf= 408	Nf= 108	Nf= 432	Nf=1908	Nf= 432	Nf=2376	Nf= 864
	Np =363	Np = 375	Np = 393	Np = 399	Np = 411	Np = 435	Np = 447
	1 0 0	0 0 0	0 0 0	1 0 0	1 0 0	1 0 0	1 0 0
F	0 1 0	1 1 0	2 1 1	1 1 0	2 2 0	2 2 0	2 2 1
	2 0 1	0 1 2	0 1 2	2 0 2	2 1 1	0 1 2	2 1 0
	Nf= 216	Nf= 456	Nf=1080	Nf=1512	Nf= 864	Nf= 864	Nf= 108
	Np =465	Np = 471	Np = 483	Np = 501	Np = 513	Np = 537	Np = 555
	1 0 0	1 0 0	1 0 0
G	2 2 0	2 2 0	2 2 0
	0 2 1	2 1 2	1 2 1
	Nf= 216	Nf= 432	Nf= 72
	Np =573	Np = 585	Np = 615

Отриманi результати дають можливiсть без додаткового аналiзу та дослiджень у майбутньому оптимiзувати роботу комутацiйного обладнання, зокрема потрібний - обсяг пам’ятi для здiйснення необхiдного числа комутацiй пiд час обслуговування процесiв обмiну даними, а також програмне забезпечення керуючих комплексiв у цифрових системах. Річ у тому, що, застосовуючи метричні оцінки до двовходових k-значних об’ємно-просторових комутаторiв, а також унiверсальних функцiональних перетворювачiв, можна на базi цих результатiв завжди обирати те чи iнше оптимальне рiшення щодо необхiдного чи потрiбного для реалiзацiї числа рiзних комутацiйних функцiй, а звiдси i необхiдного обсягу пам’ятi керуючих комплексiв, комутацiйних блокiв та полiв i їх програмного забезпечення.

Варто зазначити також можливiсть їх застосування в теорiї синтезу структур і систем із k-значним структурним алфавiтом, адже тепер при декомпозицiї логiчних функцiй до двомiсних можна одразу вибрати оптимальний базис такий, що вимагатиме найпростiшої реалiзацiї та налагодження. Суттєвим буде застосування отриманих результатiв для створення систем штучного iнтелекту.