Закономерности распределения отношений внутри полных бинарных классов Н. А. Тенетко
Закономерности распределения отношений внутри полных бинарных классов
Автор: Н. А. Тенетко
1. Исходные определения
Рассматривается полный бинарный класс, содержащий все последовательности заданной длины над алфавитом {0, 1}.
Порядок рассматриваемого класса обозначается:
[ \boxed{\operatorname{class}=m} ]
Количество элементов полного бинарного класса:
[ \boxed{N_m=2^m} ]
где:
- m — порядок класса;
- N_m — количество элементов класса;
- p — позиция элемента внутри класса.
Позиция элемента обозначается:
[ \boxed{p} ]
Для полного класса:
[ 1\leq p\leq 2^m ]
При рассмотрении отношений между двумя элементами их позиции обозначаются p и q.
[ 1\leq p,q\leq 2^m ]
При этом возможны два случая:
- p=q — отношение элемента к самому себе.
- p
eq q — отношение различных элементов.
Внутренняя структура последовательностей при подсчёте связей не учитывается.
Исследуются все возможные попарные связи элементов внутри одного полного класса.
2. Отношения с включением тождества
Каждый элемент класса может быть связан со всеми элементами этого класса, включая самого себя.
Количество возможных направленных связей:
[ R_m^{(1)}=N_m\cdot N_m ]
Следовательно:
[ R_m{(1)}=N_m2 ]
С учётом мощности бинарного класса:
[ \boxed{R_m{(1)}=2{2m}=4^m} ]
При переходе к следующему классу количество элементов удваивается:
[ N_{m+1}=2N_m ]
Количество возможных направленных связей с тождеством при этом увеличивается в четыре раза:
[ \boxed{R_{m+1}{(1)}=4R_m{(1)}} ]
3. Отношения без тождества
Исключаются все самопары, для которых:
[ p=q ]
Остаются только отношения различных элементов:
[
p
eq q
]
Каждый элемент класса может быть связан с N_m-1 другими элементами.
Количество возможных направленных связей:
[ R_m^{(2)}=N_m(N_m-1) ]
После раскрытия скобок:
[ R_m{(2)}=N_m2-N_m ]
С учётом бинарной мощности класса:
[ \boxed{R_m{(2)}=2{2m}-2^m} ]
Разница между количеством связей с тождеством и без тождества:
[ R_m{(1)}-R_m{(2)}=N_m ]
Следовательно:
[ \boxed{R_m{(1)}-R_m{(2)}=2^m} ]
Эта разница всегда равна количеству элементов рассматриваемого класса.
4. Отношения без тождества и без направления
Рассматриваются только связи различных элементов:
[
p
eq q
]
При этом противоположные направления считаются одной уникальной связью.
То есть:
[ (p,q)\sim(q,p) ]
Каждая пара различных элементов учитывается только один раз.
Количество уникальных ненаправленных связей:
[ R_m^{(3)}=\frac{N_m(N_m-1)}{2} ]
С учётом мощности бинарного класса:
[ \boxed{ R_m^{(3)}= \frac{2{2m}-2m}{2} } ]
Следовательно:
[ \boxed{R_m{(2)}=2R_m{(3)}} ]
Количество направленных связей без тождества ровно вдвое больше количества уникальных ненаправленных связей.
5. Проверка на конкретных классах
| Класс | Элементов | С тождеством | Без тождества | Без направления и тождества |
|---|---|---|---|---|
| K_3 | 8 | 64 | 56 | 28 |
| K_4 | 16 | 256 | 240 | 120 |
| K_5 | 32 | 1024 | 992 | 496 |
Для класса третьего порядка:
[ \operatorname{class}=3 ]
[ N_3=2^3=8 ]
[ R_3{(1)}=82=64 ]
[ R_3^{(2)}=8(8-1)=56 ]
[ R_3^{(3)}=\frac{56}{2}=28 ]
Для класса четвёртого порядка:
[ \operatorname{class}=4 ]
[ N_4=2^4=16 ]
[ R_4{(1)}=162=256 ]
[ R_4^{(2)}=16(16-1)=240 ]
[ R_4^{(3)}=\frac{240}{2}=120 ]
Для класса пятого порядка:
[ \operatorname{class}=5 ]
[ N_5=2^5=32 ]
[ R_5{(1)}=322=1024 ]
[ R_5^{(2)}=32(32-1)=992 ]
[ R_5^{(3)}=\frac{992}{2}=496 ]
Все вычисленные значения согласуются с общими формулами.
6. Установленные закономерности
Правило 1. Удвоение мощности класса
Каждый следующий полный бинарный класс содержит вдвое больше элементов.
[ \boxed{N_{m+1}=2N_m} ]
Правило 2. Четырёхкратный рост отношений
При увеличении порядка класса на единицу количество возможных направленных связей с включением тождества возрастает ровно в четыре раза.
[ \boxed{R_{m+1}{(1)}=4R_m{(1)}} ]
Правило 3. Разность равна мощности класса
Количество возможных направленных связей с тождеством превышает количество связей без тождества ровно на количество элементов класса.
[ \boxed{R_m{(1)}-R_m{(2)}=N_m} ]
Правило 4. Устранение направления
При исключении самопар и отождествлении противоположных направлений количество уникальных связей уменьшается вдвое.
[ \boxed{R_m{(3)}=\frac{R_m{(2)}}{2}} ]
Правило 5. Взаимное восстановление
Все три количества связей определяются единственным параметром — мощностью класса.
[ \boxed{ R_m{(1)}=2R_m{(3)}+N_m } ]
Соответственно:
[ \boxed{ R_m{(2)}=R_m{(1)}-N_m } ]
И:
[ \boxed{ R_m^{(3)}= \frac{R_m^{(1)}-N_m}{2} } ]
Следовательно, зная мощность класса и один из трёх результатов, можно точно восстановить остальные два.
Правило 6. Восстановление порядка класса
Если известно количество возможных направленных связей с тождеством, то мощность класса определяется извлечением квадратного корня:
[ \boxed{ N_m=\sqrt{R_m^{(1)}} } ]
Порядок полного бинарного класса:
[ \boxed{ m=\log_2 N_m } ]
Следовательно:
[ \boxed{ m=\frac{1}{2}\log_2 R_m^{(1)} } ]
Эти формулы применимы при условии, что исходное число действительно соответствует полному бинарному классу.
7. Дополнительная закономерность роста
Четырёхкратное увеличение количества связей при переходе к следующему классу является точным для связей с тождеством.
Для направленных связей без тождества отношение между соседними классами:
[ \frac{R_{m+1}{(2)}}{R_m{(2)}}
\frac{2{m+1}(2{m+1}-1)} {2m(2m-1)} ]
После преобразования:
[ \boxed{ \frac{R_{m+1}{(2)}}{R_m{(2)}}
4+\frac{2}{2^m-1} } ]
Таким образом, коэффициент роста всегда больше четырёх при m\geq 1.
При увеличении порядка класса он приближается к четырём.
[ \boxed{ \lim_{m\to\infty} \frac{R_{m+1}{(2)}}{R_m{(2)}}=4 } ]
Аналогичная закономерность действует для уникальных ненаправленных связей без тождества.
8. Общий вывод
Количество всех возможных элементарных попарных связей внутри полного бинарного класса определяется его мощностью.
Установлено:
Каждый следующий класс удваивает количество элементов.
Количество направленных связей с включением тождества увеличивается в четыре раза.
Исключение тождества уменьшает количество связей ровно на мощность рассматриваемого класса.
Отождествление противоположных направлений уменьшает количество оставшихся связей вдвое.
Все три способа подсчёта связаны точными формулами взаимного восстановления.
По количеству возможных направленных связей с тождеством можно восстановить мощность и порядок полного бинарного класса.
Коэффициент роста связей без тождества между соседними классами больше четырёх и стремится к четырём с увеличением порядка класса.
Полученные закономерности не зависят от конкретного содержания бинарных слов.
Они определяются количеством элементов класса и выбранным способом учёта связей.
9. Границы применимости
Полученные формулы описывают все возможные попарные связи элементов внутри одного полного бинарного класса.
Они не утверждают, что каждая возможная связь обязательно присутствует в конкретном исследуемом отношении.
Включение самопар в множество возможных связей не означает, что каждое конкретное отношение обязательно является рефлексивным.
Межклассовые отношения, вложенности, внутренняя структура последовательностей и правила их восстановления здесь не рассматриваются.
Для их исследования необходимо отдельно определить соответствующее отношение и границы рассматриваемой области.