Определение иерархических чисел

Иерарахические числа – это числа вида [s] a₀ . a₁ . a₂ . … . a_i. … .a_n   , где a_i– целые положительные числа из множества N = {0, 1, 2, 3…}.

s– символ знака «+» или «-», положительный знак может не указываться.

Например, иерархические числа могут выглядеть так:

0.0.12.48.0 или -2.33.0.0.4 .

Символом, обозначающим множество иерархических чисел, является H.

 

Прикладное определение. Иерархические числа – это раздел математической теории чисел, который позволяет адекватно оперировать основными характеристиками таксономий.

В теории представления знаний искусственного интеллекта иерархические числа позволяют:

$1−      -   определять семантическое сходство понятий;

$1−      -  вычислять индексы гиперонимов и гипонимов;

$1−     -    получать регулярные структуры знаний;

$1−     -    верифицировать деревья родовидовой и причинно-следственной классификаций.

Эти числа так или иначе уже используются в практике классификации или адресации, например: универсальный десятичный код или IP-адрес компьютера в глобальной сети. Однако, введение алгебраической системы иерархических чисел позволяет совершать с ними операции, схожие с формальной арифметикой, и выделять бинарные отношения для их сравнения и анализа нетривиальных свойств операций и отношений.

 

Пусть N – множество целых положительных чисел с элементами n_i ϵ N, пусть также есть выделенный символ «.».

Множество A = N ᴗ «.» ᴗ ᴧ определяется как алфавит с целыми числами n, где «ᴗ» – операция объединения множеств, а ᴧ – пустой символ.

Тогда грамматика:

ĥ → ᴧ,

ĥ → h,

ĥ → - h,

h → < n >,

h → < n > . <h>  

описывает множество иерархических чисел Ĥ с элементами ĥ.

 

Рассмотрим алгебру бинарных иерархических чисел.

Пусть B – множество чисел с элементами {0, 1}, n ϵ B (n = 0 или n = 1), пусть также есть выделенный символ «.».

Множество A = B ᴗ «.» ᴗ ᴧ определяется как алфавит с целыми числами из B, где «ᴗ» – операция объединения множеств, а ᴧ – пустой символ. Тогда грамматика:

ĥ → ᴧ, ĥ → h, ĥ → -h,

h → < n >, h → < n > . <h>

описывает множество бинарных иерархических чисел H с элементами h.

Можно привести примеры бинарных иерархических чисел: 0.1.0.0.1 или 1.0.-1.0 .

Бинарные иерархические числа представляют собой численные индексы вершин двух

двоичных деревьев: положительного и отрицательного с одной общей вершиной 0.

Порождение вершины влево от 0 производится бинарной операцией 0+0 = 0.0, порождение вершины вправо - бинарной операцией 0 + 1 = 0.1.

Порождение отрицательных вершин выполняется операцией «-» соответственно:

0-0 = -0.0, 0-1 = -0.1.

Графически это можно представить деревом, распространяющимся в положительную или отрицательную сторону:

 

 

 

 

 

 

 

 

 

 

 

 

Впрочем, использование отрицательных элементов может сделать смысл операций более сложным. Например, порождения трассы «+» может выглядеть так:

0.1 + 1.1 = 0.1.1.1, 0 + 0.1 = 0.0.1

 

Однако пример 0.0.-1 + 1.1 = 0.0.-1.1.1 свидетельствует о наличии более сложных трасс путешествия по дереву, использующих не только спуск но и локальные подъемы (рисунок 2). Такое применение иерархических чисел будет рассмотрено далее на конкретных примерах.

 

Операция, обратная порождению, удаление терминальной вершины «--», является унарной:

 

0.1.1.1-- = 0.1.1, 0.1.0-- = 0.1, 0.-1.-1 -- = 0.-1.-1 .

 

 

 

 

 

 

 

 

 

 

 

 

 

 

В графической интерпретации число можно считать абсолютным индексом какой-либо вершины, т.е.начинающимся с вершины дерева 0 или относительным, отображающим путь по дереву от одной из любых вершин к другим вершинам вверх и вниз. Абсолютный индекс всегда начинается с символа 0.

При решении практических задач можно рассматривать только положительную часть алгебры бинарных иерархических чисел. В этом случае операции, претендующие на получение отрицательного индекса, будут иметь результатом 0.

Можно привести еще одну довольно популярную операцию «º», а именно вычисление наиболее общей вершины, что интерпретируется как поиск общего предка двух вершин - аргументов:

                                     0.1.1.1  º   0.1.0 = 0.1.0  º  0.1.1.1  = 0.1

Эта операция генерализации/умножения коммутативна, т.е. a º b = b º a. 

 

Умножение положительного числа на отрицательное всегда равно 0.

 

Важной операцией является «Ù» как вычисление пути из вершины, заданной первым аргументом, в вершину, заданную вторым аргументом. Для предыдущего рисунка можно было бы привести примеры таких вычислений:

 

0.1.0 Ù 0.1.1.1   = 0.1.0. 0.1. 0.1.1. 0.1.1.1

 

0.1.1.1   Ù 0.1.0 = 0.1.1.1 0.1.1. 0.1 0.1.0

 

0.1.0. 0.1. 0.1.1. 0.1.1.1   @ 0.1.1.1 0.1.1. 0.1 0.1.0

 

Здесь « @ » - отношение равенства длин двух иерархических чисел.

 

Однако, такое вычисление приводит к излишне сложному результату.

 

Заметим, что общим предком для 0.1.1.1   и 0.1.0 является   0.1, с которого начинаются оба числа - аргумента. Вследствие этого, при вычислении операции Ù эти фрагменты опускаются для всех вершин пути из первой вершины во вторую. Это необходимо для получения представления о сложности пути из первой вершины во вторую, не смотря на глубину дерева.

 

Тогда правильная операция «Ù» получается так:

 

0.1.0 Ù 0.1.1.1   = [0.1.]0. [0.1.] [ 0.1.]1. [ 0.1].1.1 = 0.1.1.1

 

0.1.1.1 Ù 0.1.0  = [0.1.]1.1 [0.1.]1. [0.1] [0.1.]0   = 1.1.1.0

 

             0.1.1.1 @   1.1.1.0

 

После рассмотрения семантики приведенных операций можно задать универсальную арифметическую алгебру иерархических чисел H:

 

                                                 H = < H, Ω >, Ω = {+, -, --, º , Ù, ⊕ },

 

 

где Ω – сигнатура алгебры, т.е. множество операций. Все операции бинарны, за исключением «--», которая является одноместной. Смысл операции «⊕ » будет рассмотрен позже, на соответствующих примерах.

 

Рассмотренную алгебру можно дополнить до алгебраической системы H = <H,Ω,R>, введя множество отношений R = {< , >, @ , = }, где отношения « a> b» и « b< a» соответственно «число a сложней числа b» и «число b короче числа a».