One approach to constructing a transitive class of block transformations.pdf 1. Понятие сети Пусть {x1, x2,... , xn} - множество переменных и * - символ бинарной операции. Множество всех формул в алфавите {x1,... , xn, *} будем обозначать W. При сопоставлении символу * конкретной бинарной квазигруппы F e Q(H) формула w(x1,... ,xn) реализует отображение wF: Qn - П. Для исследования свойств отображений (wF,... , w^): Пп - Пт, F e Q(H), соответствующих определённому набору формул (w1,... ,wm) e Wm, введём дополнительное представление отображений в виде сети. Пусть t, n0, n1,..., nt e N и хо = {xi), x2),..., xno)}, X1 = {x1), x2),..., xni},..., Xt = {x1), x2),..., xnt} - семейство попарно непересекающихся конечных непустых множеств. Тогда квазигрупповой сетью (далее просто сетью) длины t будем называть простой ориентированный граф Е с множеством вершин X0 U X1 U ... U Xt, содержащий только рёбра вида (xis 1),xjs)), s e {1,... ,t}, с тем ограничением, что степень захода каждой вершины xjs), s e {1,... , t}, равна 1 или 2. При этом если степень захода вершины xjs) равна 1, то ребро (xis 1) ,xjs)) имеет метку 0, а если степень захода вершины xjs) равна 2, то рёбра (xis 1),xjs)) и (x^ 1),xjs)) имеют различные метки из множества {1, 2}. Число n0 будем называть размерностью сети Е, а число max{n0,..., nt} - шириной сети Е. Подграф Es сети Е, основанный на множестве вершин Xs-1 UXs, будем называть s-м слоем сети Е. Сеть Е будем называть однослойной, если она имеет длину 1. Пусть Е' и Е" - сети с множествами вершин X' = X0UX1U...UXs и X" = X0'UXf U U ... U Xt'' соответственно и при этом X' П X'' = Xs = Xq . Тогда естественным образом можно определить сеть длины s+t с множеством вершин X0UX1U.. .UXsUX1'U.. .UXf, которую будем называть произведением сетей Е' и Е'' и обозначать Е' • Е''. Нетрудно понять, что всякая сеть является произведением своих слоёв. Произвольный набор формул (w1,...,wm), в котором каждая формула wj, j E E {1,... , m}, либо имеет вид vi1 * vi2, г1, г2 E {1,... , n}, либо является некоторой формулой Vi, г E {1,..., n}, будем называть преобразованием набора формул (v1,..., vn). Один из естественных способов построения произвольного набора формул (w1,... , wm) заключается в последовательном преобразовании набора переменных (x1,..., xn). Данный процесс допускает наглядную интерпретацию при использовании введённой терминологии сетей. Пусть (v1,... , vn) - произвольный набор формул и Е - однослойная сеть с множеством вершин {x1,... , хП0)} U {x11),..., Xm}. Тогда определим набор формул (w1,... , wm) по следующим правилам: - если вершине xj1) инцидентно ребро (xi0) ,xj1)) с меткой 0, то полагаем wj = vi; (1) "С / (0) (1К / (0) (1)ч о - если вершине xj инцидентны рёбра (x^ , xj ) и (xi2 , xj ) с метками 1 и 2 соответственно, то полагаем wj = vi1 * vi2. При этом будем говорить, что сеть Е описывает преобразование набора формул (v1,... , vn) в набор формул (w1,... , wm). Произвольная сеть Е является произведением однослойных сетей, являющихся её слоями, и естественным образом описывает преобразование произвольного набора формул, являющееся произведением преобразований, соответствующих слоям. Пусть F E

Скачать электронную версию публикации