Содержание к диссертации
Введение
Глава 1. Монотонные классы с бесконечной надструктурой 15
1.1. Основные понятия 15
1.2. Семейство классов монотонных функций с бесконечной надструктурой 43
1.3. Минимальные логики, содержащие классы монотонных функций с бесконечной надструктурой 53
Глава 2. Свойства надрешетки классов монотонных функций 63
2.1. Невырожденные предикаты 63
2.2. Общие свойства надрешеток классов монотонных функций 72
2.3. Надструктура классов монотонных функций, сохраняющих несвязное ЧУМ 81
Глава 3. Необходимые и достаточные условия для бесконечной надструктуры класса монотонных функций 99
3.1. Достаточные условия для конечной надструктуры класса монотонных функций 99
3.2. Необходимые и достаточные условия для наличия бесконечной надструктуры у некоторых семейств классов монотонных функций 103
3.3. Неограниченность конечной надструктуры классов монотонных функций 115
Глава 4. Надструктура замкнутых классов самодвойственных функций 120
4.1. Семейства классов, содержащих замкнутый класс самодвойственных функций 120
4.2. Надструктура классов самодвойственных функций 127
4.3. Структура решетки замкнутых классов над Sa 139
Литература
- Семейство классов монотонных функций с бесконечной надструктурой
- Минимальные логики, содержащие классы монотонных функций с бесконечной надструктурой
- Надструктура классов монотонных функций, сохраняющих несвязное ЧУМ
- Необходимые и достаточные условия для наличия бесконечной надструктуры у некоторых семейств классов монотонных функций
Введение к работе
Актуальность работы. В современной математике и технике теория булевых функций занимает важное положение. Двухзначная логика используется как во многих теоретических областях, так и в прикладных. Всевозможные цифровые устройства, системы искусственного интеллекта, управляющие системы решают сложнейшие задачи, выполняя при этом элементарные двоичные операции и храня данные в виде нулей и единиц.
До сих пор доминирующее положение занимает именно двухзначная логика. Однако сложность решаемых задач, а, следовательно, и технических устройств, постоянно возрастает. Уже подходят к своему пределу многие технологические возможности, такие как увеличение плотности элементов на схемах, повышение рабочей частоты. Применение многозначной логики является одним из путей решения указанных проблем.
Многозначная логика предоставляет более широкие возможности для разработки различных алгоритмов во многих областях. Она позволяет уменьшить как вычислительную сложность, так и размеры, число соединений в различных арифметико-логических устройствах, повысить плотность размещения элементов на схемах, найти альтернативные методы решения задач.
Уже сейчас многозначная логика с успехом применяется при решении многих задач и во множестве технических разработок. Среди них flash-память, различные арифметические устройства, системы искусственного интеллекта и обработки данных, обработка сложных цифровых сигналов и т. д.
Одной из основных задач в многозначной логике является проблема выразимости функций: заданную /с-значную функцию или класс функций требуется выразить, используя суперпозицию функций некоторого имеющегося множества. Указанную задачу, несколько уменьшив общность постановки, можно переформулировать в задачу описания решетки замкнутых относительно операции суперпозиции классов функций /с-значной логики.
Следуя авторам, будем обозначать через Р& множество всех /с-значных функций.
Задача описания всех замкнутых классов функций двухзначной логики была решена Э. Постом1'2. Было показано, что в Pсчетное число замкнутых классов, каждый из которых имеет конечный базис. Существует в точности
1 Post Е. L. Introduction to a general theory of elementary propositions. Amer. J. Math. 1921. Volume 43,
№ 4. P. 163-165.
2 Post E. L. Two valued iterative systems of mathematical logic. Annals of Math. Studies, Princeton
Univ. Press, 1951. V. 5.
пять предполных классов, образующих критериальную систему для разрешения проблемы полноты.
Ю. И. Яновым, А. А. Мучником было показано3, что в Р& при к ^ 3 существуют замкнутые классы со счетным базисом, а также замкнутые классы, не имеющие базиса. Следствием этого результата является континуальная мощность множества замкнутых классов /с-значных функций при к ^ 3. Оказалось, что описать решетку классов в Р& для к ^ 3, как это было сделано Э. Постом для Р25 невозможно. В связи с этим важной проблемой является описание именно фрагментов решетки замкнутых классов /с-значных функций.
И. Розенберг изучил все предполные классы в решетке замкнутых классов /с-значных функций. Указанные классы были описаны через сохраняемые отношения в виде шести семейств, два из которых, обозначаемые через М и S, являются соответственно подмножествами всех монотонных и самодвойственных классов в Р^.
B. В. Мартынюком установлено5, что класс монотонных функций, сохра
няющих частичный порядок г, принадлежит семейству М (то есть является
предполным) тогда и только тогда, когда г имеет в точности единственный
минимальный и единственный максимальный элементы.
C. В. Яблонским доказано6, что класс функций, самодвойственных отно
сительно некоторой подстановки <т, принадлежит семейству S тогда и только
тогда, когда подстановка а разлагается в произведение циклов одинаковой
длины, являющейся простым числом.
Возникает вопрос о строении фрагмента решетки замкнутых классов /с-значных функций над классами монотонных или классами самодвойственных функций, не являющимися предполными.
Цель диссертационной работы. Основной целью диссертации является изучение надрешеток классов монотонных функций и классов самодвойственных функций в Р^ при к ^ 3.
Научная новизна. Все результаты диссертации являются новыми. Исследованы новые фрагменты решетки замкнутых классов в Р^.
3 Янов Ю. И., Мучник А. А. О существовании /г-значных замкнутых классов, не имеющих конечного
базиса. Доклады АН СССР. 1959. Т. 127, № 1. С. 44-46.
4 Rosenberg I. G. La structure des fonctions de plusiers variables sur un ensemble fini. Comptes Rendus
Acad. Sci. Paris. 1965. Volume 260. P. 3817-3819.
5 Мартынюк В. В. Исследование некоторых классов функций в многозначных логиках. Проблемы
кибернетики, вып. 3. М.: Наука, 1960. С. 49-61.
е Яблонский С. В. Функциональные построения в /г-значной логике. Труды математического института им. В.А.Стеклова АН СССР. 1958. Т. 51. С. 5-142.
Теоретическая и практическая ценность. Работа носит теоретический характер. Методы исследования, разработанные в диссертации, могут, по мнению автора, быть применены при дальнейшем изучении решетки замкнутых классов.
Методы исследования. Результаты диссертации получены с применением методов теории предикатов и теории Галуа для алгебр Поста, а также элементов теории частично упорядоченных множеств и теории чисел.
Публикации и апробирование. По теме диссертации опубликовано 9 работ. Результаты диссертации докладывались на следующих конференциях: XV Международной конференции «Проблемы теоретической кибернетики» (Казань, 2—7 июня 2008 г.), XVII Международной школе-семинаре «Синтез и сложность управляющих систем» имени академика О. Б. Лу-панова (Новосибирск, 27 октября—1 ноября 2008 г.), VIII Международной конференции «Дискретные модели в теории управляющих систем» (Москва, 6—9 апреля 2009 г.), VII молодежной научной школе по дискретной математике и ее приложениям (Москва, 18—23 мая 2009 г.), XVIII Международной школе-семинаре «Синтез и сложность управляющих систем» имени академика О.Б.Лупанова (Пенза, 28 сентября—3 октября 2009 г.), X Международном научном семинаре «Дискретная математика и ее приложения» (Москва, 1—6 февраля 2010 г.).
Также результаты диссертации обсуждались на спецсеминаре «Дискретная математика и математическая кибернетика» кафедры математической кибернетики факультета ВМК МГУ.
Структура и объем диссертации Объем диссертации 157 страниц. Работа состоит из введения, четырех глав и списка литературы.
Семейство классов монотонных функций с бесконечной надструктурой
Предположим, что в графе Gp есть ориентированные циклы. Выберем любой из них. Пусть он состоит из вершин, отвечающих свободным переменным жі,...,ж/ и связанным Уъ---,ут- Отождествим в формуле F все переменные хі,..., хі, ї/1,..., ут и обозначим полученную переменную z. Рассмотрим формулу F", получаеющуюся из F проекцией по всем переменным, являющимися связанными в формуле F; при этом мы берем проекцию и по переменной z тогда и только тогда, когда в рассматриваемом цикле графа Gp не было ни одной свободной переменной (то есть 1 = 0). Обозначим через р[ реализуемый формулой F" предикат. Отметим, что граф GF» формулы F" получается из графа Gp склейкой вершин рассматриваемого цикла (то есть соответствующих переменным xi,...,xi,yi,...,ym формулы F) и помечива-иием результирующей вершины символом z или "3z". Далее докажем, что предикаты р и р[ эквивалентны. Пусть I 1. Рассмотрим следующий предикат: р(хи ..., xh жі+і,..., хп) = 3zp[(z, xt+i,..., xn)d(z, xi)... d(z, x{). Отсюда следует, что предикат р реализуется формулой над системой {р[, d}. Обозначим через р2 конъюнкцию (без общих переменных) предикатов р[ и d. Поскольку р[ и d можно получить из указанной конъюнкции соответствующими проекциями, то р Є \р2\. По леммам 1, 2 получаем, что Polp Э Polp2 = Pol (р[Ш). Из леммы 4 следует Ро1(р[Ы) = Polpi C\Po\d = Ро\р[ f]Pk — Polp . Объединяя соотношения, имеем Pol 4 С Pol р. Остается заметить, что р = р, поскольку если р{а) — TRUE, то все переменные, соответствующие вершинам из цикла, обязаны принять равные значения (так как по построению графа формулы переменные, соответствующие соседним вершинам цикла, связаны отношением R).
Итак, получаем, что Polp С Polp С другой стороны, пусть предикатр получен из предикатар отождествлением первых I переменных. Тогдар Є \р]. Аналогично предыдущему случаю, р = р[. Опять, воспользовавшись леммой 1, получаем Polp С Ро\р[. Если I = 0 или 1 = 1, положим в доказательствах выше р — р[ и р = р соответственно. То есть в этом случае предикаты р и р[ равны. Далее, если графр содержит цикл, повторив описанную процедуру уже для р ъ получим 2, эквивалентный р г и р, и так далее, пока не получим предикат р с графом без циклов (процесс конечен, так как на каждом шаге не может появиться новый цикл). Первый пункт доказан.
Для доказательства второго утверждения леммы достаточно выше взять формулу F, реализующую предикат р, из условия леммы. Поскольку любой ориентированный цикл в графе GF содержит не более одного элемента, соответствующего свободной переменной формулы F, то будет справедливо I = О или Z = 1, то есть при удалении любого цикла, как описано выше, предикат р не будет меняться.
Согласно лемме 6 в графе Gpi формулы F нет ориентированных циклов. Следовательно, формуле F можно следующим образом сопоставить частично упорядоченное множество Lpi. Между множеством элементов ЧУМ Lp и множеством всех переменных в формуле F существует взаимно однозначное соответствие (опять обозначим это так: элемент vx Є Lp соответствует переменной х Є F ). Для всех переменных полагаем vx vx и, если формула F содержит запись R(x,y), то vx vy. Замыканием по транзитивности получаем искомое ЧУМ Lp (поскольку в графе Gp отсутствуют ориентированные циклы). Докажем некоторые общие свойства замкнутых классов предикатов. Лемма 7. Для любого мнооїсества предикатов Р справедливо PolP — Pol[P]. Доказательство. Если множество Р пусто, то утверждение очевидно. Предположим далее, что Р непусто. Поскольку PC [Р], то Ро1[Р] С PolP (любая функция, сохраняющая все предикаты из множества [Р], в частности сохраняет любой предикат из множества Р). Рассмотрим произвольный предикат р Є [Р]. Пусть р реализуется над Р формулой F. Поскольку указанная формула конечна, то существует конечное множество предикатов ii,...,tm такое, что ti Є Р (і Є {l,...,m}) и p Є [ti,..., tm]. Обозначим через t предикат, равный конъюнкции t\h ... Sztm без отождествления переменных. Поскольку каждый предикат реализуется над {t} формулой, представляющей собой некоторую проекцию по подходящим переменным, то U Є [t] для всех г Є {1,... ,га}. Откуда следует р Є [і\. По лемме 1 получаем РоН С Pol р. Но с другой стороны из {} С Р следует PolP С РоН, откуда PolP С Polp.
Минимальные логики, содержащие классы монотонных функций с бесконечной надструктурой
Заметим, что предикат р не может быть тождественно истинным или ложным в силу А ф Р а также не может быть одноместным в силу следствия из леммы 3.
Пустьр ф Т. Тогда либо существует проекция предикатар(х±,...,хп) по переменной ХІ, такая что Polpj — Pol р, либо р вырожден (Polp Pol R выполнено по условию леммы). В первом случае вместор рассмотрим предикат Pi и повторим рассуждения сначала. Во втором случае применив к предикату р лемму 31, получим А = ПГ=1 PlPi) причем для любого г Є {1,... ,п} выполнено А у Polpi (следует из рассмотрения первого случая). Рассмотрим теперь аналогичным образом все предикаты рг-. Если рі Є Т, оставим множество Polpi В пересечении,
предикат, то вычеркнем множество Роїрг (оно равно Pk) из пересечения (при этом, в силу сказанного выше ирі Є [R], у нас не останется одноместных предикатов), иначе проделаем описанную процедуру разложения с классом Pol pi (опять, поскольку А ф Pol R, то Polpj Ф POIJR, РІ отличен от тождественно истинного или ложного предиката). Поскольку на каждом шаге местность рассматриваемых предикатов уменьшается на единицу, процесс завершится. В конце мы получим представление:
Лемма 33. Число замкнутых классов над MR бесконечно тогда и только тогда, когда множество А(Т) содержит бесконечное число классов. Доказательство. Если множество А(Т) бесконечно, то достаточно учесть, что по построению любой р Є Т реализуется формулой над {R}, откуда по лемме 1 получаем, что Ро\р Э MR.
Пусть теперь над MR существует бесконечное число классов. Если существует класс А, содержащий MR такой, что А не является предикатно-опису-емым, то по лемме 15 существует бесконечное число различных предикатно-описуемых классов, содержащих класс А, а следовательно, и класс MR.
Если же все классы А, содержащие MR, являются предикатно-описуе-мыми, то мы опять получаем, что существует бесконечное число различных классов, представимых в виде Polp, содержащих класс MR.
Предположим, что множество А(Т) содержит конечное число классов: AL,...,A/V, АІ — Pol pi, pi Є Т. Рассмотрим произвольный класс А такой, что MR С А С Pk, А = Polp. По лемме 13 получаем, что р Є [R]. Из леммы 32 следует, что замкнутый класс А представим пересечением классов Polpi. Поскольку классов, представимых указанным пересечением, конечное число, а всего классов вида Polp, содержащих MR, бесконечно, приходим к противоречию, то есть множество А(Т) бесконечно.
Доказательство. Пусть р Є [R] — невырожденный предикат. Предположим, что формула F\ $ F задает р. Согласно лемме 11, мы можем построить эквивалентный предикатр , задаваемый формулой F Є F. При построениир мы сначала используем лемму 6. При этом предикат меняется, если существует пара вершин, отвечающих свободным переменным и входящих в один ориентированный цикл графа G . После этого применяется лемма 11, в которой из графа формулы удаляются компоненты связности, в которых нет ни одной вершины, соответствующей свободной переменной. При этой процедуре предикат не меняется.
Предположим, что в графе G существуют две вершины vXl и vX2, соответствующие свободным переменным xi, Х2 формулы JFI, входящие в один ориентированный цикл. Заметим, что в любом наборе а = [а\,..., ап) таком, что р(а) — TRUE будет выполнено ai = а (мы считаем, что жг- = щ).
Если р — двухместный предикат, то с учетом следствия из леммы 3 и рассуждений выше получаем, что р — диагональ, откуда Polp = Pk, что противоречит условию леммы.
Пусть местность предиката р больше 2. Поскольку р — невырожденный предикат, то существует набор а такой, что р{а) — FALSE и (3xip)(a\,..., a,i-i,ai+i,... ,ап) = TRUE для любого і Є {І,...,п}. Если а\ = а і, то с учетом описанного выше цикла получаем, что для любого Ъ ф &2 справедливо p(b, а і,..., ап) — FALSE, откуда (Зхір)(а,2,..., ап) = FALSE. Приходим к противоречию. Если же ai -ф а , то {Зх2,р){а\,а2,а ... ,ап) = FALSE (тут мы учитываем, что местность предиката р больше 2). Получа ем, что невырожденный предикат местности больше 2 не может иметь переменных, вершины, соответствующие которым, входят в ориентированный цикл графа формулы. Отсюда получаем, что при применении лемм 6 и 11 предикат р не изменится.
Доказательство. Рассмотрим предикат Pj(x{,..., х\). По условию все переменные х{,...,х1. принадлежат множеству X. Дополним предикат Pj несущественными переменными из множества X \ Xj (если такие переменные существуют). Обозначим полученный предикат через hj(x\,..., хп). По определению равенства предикатов hj{x\,..., хп) = Pj(x{,..., х\ ). Если Xj — X, то предикат hj получен из предиката Pj перестановкой переменных (возможно единичной).
Надструктура классов монотонных функций, сохраняющих несвязное ЧУМ
Рассмотрим произвольный замкнутый класс А такой, что М# С А, А ф Pk и Ф(А) — (Р[г,..., Pih). Возьмем произвольный номер і Є {1,..., h}. Поскольку АІ = Piv то из (2.7) следует, что для любого р Є Inv А выполнено РоІ7г(р) = Pk- Зафиксируем некоторый предикату Є Inv А. Из Мн Q Polp и леммы 12 следует, чтор Є [R]. Обозначим через F некоторую формулу, реализующую предикат р над {R}. По следствию из леммы 38, та же формула реализует 7»(р) над {7г(#)} в Pk.
С учетом рассуждений, проведенных выше, получаем, что предикат7г(р) является диагональю в Р/.. Если у предиката 7г{р) есть эквивалентные переменные xr,xq (г т о), то есть для любого Ъ из Ji(p)(b) = TRUE следует br = bq, то по лемме 10 получаем, что для любой формулы, задающей 7г(р), в том и числе и для F, в графе будет ориентированный цикл, в который входят вершины, соответствующие переменным xr, xq. Отсюда следует, что и в исходном предикате р переменные хг и xq будут эквивалентны. Таким образом, мы получим, что во всех предикатах р, 71 (р), ,7/г(р) эквивалентны одни и те же подмножества переменных. Обозначим соответствующее отношение эквивалентности через є.
Предположим, что граф GF связен. В этом случае покажем, чтор(х) = TRUE тогда и только тогда, когда эквивалентные относительно є компоненты набора х примут равные значения, и все значения компонент Х{ принадлежат одной компоненте СВЯЗНОСТИ Ні.
Пусть р{х) = TRUE, но некоторые две компоненты Xi,Xj такие, что e(xi,Xj) приняли разные значения. Но по лемме 21 все значения компонент набора принадлежат одной компоненте связности Щ, откуда получаем, что в Ji(p){ji{x)) = TRUE у двух эквивалентных переменных будут разные значения. Это противоречит тому, что7г(р) — диагональ. Если в наборе х найдутся две компоненты Х{, Xj с наборами из разных компонент связности ЧУМ Н, и при этом р(х) = TRUE, то мы сразу получаем противоречие с леммой 21.
Обратно, пусть р(х) = FALSE, все компоненты набора х принадлежат одной компоненте связности Щ, все эквивалентные относительно є компоненты приняли равные значения. Но тогда 7г(р)(7г( )) — FALSE, что противоречит тому, что 7г(р) — диагональ.
Изучим вопрос, каким может быть замкнутый класс Pol р. Воспользуемся леммой 11 и преобразуем формулу F к F Є F. При этом в графе Gp будут отсутствовать ориентированные циклы. В силу леммы 10 данная процедура будет соответствовать отождествлению в предикате р всех переменных, эквивалентных относительно е. Обозначим полученный предикат через р . Согласно лемме 11, Pol р = Pol р.
Если местность р равна единице, то по следствию из леммы 3 получаем, ЧТО Polp = Pfc. Пусть местность I предиката р больше единицы. Предикату р удовлетворяют все наборы, состоящие из компонент, принадлежащих одному множеству Щ, и только они. h Обозначим разбиение Ek = \J Щ через D. Справедливо следующее со t=i отношение: RD{xi,x2) = Зу1:... ,yl_2p (xi,x2,y1,y2,... ,yi). С другой стороны, р {х1,х2, ...,xi) = 3yRD(xi,y)&RD(x2, з/)&... kRD(xm, у). По лемме 1 получаем, что Polp = Pol У = Pol RD — {#J Если граф Gp несвязен, то предикат р задает класс Polp, являющийся пересечением уже рассмотренных U .y и Р&. Но указанное пересечение не дает новых классов. Итак, мы показали, что для любого р Є InvA выполнено Polp = Р& или Polp = Щн{}- Поскольку А — Р Polp, то класс А может быть либо Рь, pSlnv А либо U{m}. Первый пункт доказан. Докажем теперь второй пункт. Рассмотрим замкнутый класс А такой, что М# Q А, Ф(А) — (Ai,..., Ah). Пусть для некоторого номера j Є {1,..., h} выполнено Aj — мНг Обозначим через Р систему предикатов 7j(p) Для всевозможных р Є InvA Из (2.7) следует, что PolP = Aj — Мну По определению функтора Inv множество InvA содержит двухместную диагональ d. Следовательно, множество Р содержит предикат jj (d), являющийся двухместной диагональю в Pi.. По лемме 2 получаем, что множество Р содержит все диагонали из Р/..
Возьмем произвольный предикат р Є InvA. Из М# С Polp следует PolP С Polp. По лемме 12 выполнено р Є [R]. Используя лемму 38, получаем Ijip) \із(Щ\і откуда Р С [jj(R)]. Поскольку РоїтДР) = Мщ является в Р/. классом монотонных функций, сохраняющих ЧУМ Hj (с некоторым переименованием элементов, соответствующим отображению7j)J т0 п0 лемме 16 получаем, что существует предикат t Є Р такой, что РоН = Мцу Пусть
Из Мн С Polp и леммы 12 следует, что р Є [R]. Обозначим через F формулу, реализующую р над {R}- По следствию из леммы 38, формула F", полученная из формулы F заменой всех подформул Р(-, ) на jj(R(-, )), реализует предикат t над { jj(R)}. Рассмотрим случай, когда формула F не принадлежит семейству F. Поскольку графы формул F и F" совпадают, то формула F" также не принадлежит семейству F. Осуществим одновременное преобразование формул F и F" по лемме 11. При этом мы получим некоторые формулы F и F" из семейства F, реализующие предикаты р и t, являющиеся эквивалентными соответственно предикатам р и t. В силу того, что формулы F и F" отличаются лишь системами {R} и { jj(R)}, то для формул Ff, F" сохранится важное для нас свойство: формула F" получается из формулы F заменой всех подформул R(-,-) на jj(R(-, )). По следствию из леммы 38 имеем соотношение t = 7j(p ) Покажем теперь, чтор Є Inv А Пусть это не так, следовательно найдется функция / Є А такая, что / не сохраняет р , то есть / Polp . Поскольку Polp = Polp , то / ф Polp . Получаем, что в классе А существует функция /, не сохраняющая предикат р , откуда следует р Inv А. Данное противоречие доказывает соотношение р Є Inv А.
Необходимые и достаточные условия для наличия бесконечной надструктуры у некоторых семейств классов монотонных функций
Возьмем произвольный элемент Ъ Є М а- Пусть Ъ принадлежит циклу подстановки а, имеющему длину ГП{. Поскольку ГПІ\ НОК (mi,..., тр), то по определению 29 имеем Ь Є Мн0К(тІ!...,тр), 7 С другой стороны, пусть элемент 6, входящий в цикл подстановки а, име ющий длину т , принадлежит множеству Мцок(mb...,m ),сг- По определению 29 получаем, что т!\ НОК (m-i,..., тр). Откуда, с учетом НОК (mi,..., mp)\d, получаем m \d, то есть Ъ Є М и. П В силу леммы 48 мы можем рассматривать только множествам , где число d равно наименьшему общему кратному длин циклов подстановки а, элементы которых образуют рассматриваемое множество М )СГ.
Определение 30. Пусть подстановка 7г определена на подмножестве Md,a множества Ek таком, что М а 0 Mi,a 7 Ек, и равна о на указанном множестве. Классом Н назовем множество функций fc-значной логики, сохраняющих следующий предикат: R (x\, Х2) = TRUE тогда и только тогда, когда Х\,Х2 Є Md,n и хч — 7гг(жі), где г — произвольный делитель числа h , являющегося минимальным, удовлетворяющим 7Thir — е.
Определение 31. Через Тст будем обозначать множество классов Hay, где d — наименьшее общее кратное длин циклов подстановки ст, элементы которых образуют множество М а, к — подстановка, определенная на множестве Md,a, где Md,cr 7 0 и MdiCr Ek, и совпадающая с подстановкой а на нем, t — произвольный делитель числа hn, являющегося минимальным, удовлетворяющим irh7r = е.
Пусть предикат р Є [Ra], где Ra предикат, задающий класс самодвойственных функций Sa. Пусть F — формула, реализующая предикат р над {Ra}- Как и в случае классов монотонных функций, везде далее будем считать, что в формуле F вынесены вперед все кванторы существования. Пусть Gp — граф формулы F. Пусть vVl,..., vVN - все вершины графа GF Определение 32. Путем из вершины vVi в вершину vy. (i,j Є {1,..., N}) в графе GF будем называть любую последовательность ребер вида {(vy.,vZl), (vZl,vZ2), (v22,vZ3),..., {vZm,vyj)}, где все zm Є {yu ...,yN} (вершины и ребра в последовательности могут повторяться). Ориентация ребер указанной последовательности может быть любая. Замкнутым путем называется путь, в котором первая и последняя вершины совпадают. Циклом называется замкнутый путь, в котором каждая вершина (кроме первой и последней) встречается не более одного раза. Длиной пути будем называть разность количества ребер, пройденных в прямом направлении, и количества ребер, пройденных в обратном.
Определение 33. Матрицей расстояний для графа Gp будем называть матрицу Dp размера iV на N, элементами которой являются множества оіц, построенные по следующему правилу: число 0 I ha принадлежит о\ц тогда и только тогда, когда в графе GF существует путь из вершины vVi в вершину vyj длины т и т = / ( mod ha), других элементов в d нет.
Отметим, что, если граф GF содержит только циклы длины, кратной ha, то каждое множество d состоит из единственного элемента.
Лемма 50. Пусть все циклы связанного графа GF имеют длины сі,..., cq. Тогда для любой вершины vyi и любого целого а в графе Gp есть замкнутый путь длины ас, где с = НОД(сі,..., \cq\), проходящий через вершину vyv Замкнутых путей с другими длинами в графе Gp нет.
Доказательство. Поскольку знак чисел Q зависит от направления обхода соответствующего цикла, будем считать, что все Q 0.
Докажем вначале, что граф Gp содержит только замкнутые пути, имеющие ДЛИНЫ 5Zi=l агСг Для Любых ЦвЛЫХ ОСі, . . . ,Ctq. Мы можем пройти а.\ раз цикл длины С\ (знак числа а.\ указывает направление обхода). Поскольку граф связный, существует путь S от какой-нибудь вершины указанного цикла к какой-то вершине цикла длины с?,. Пройдем по нему в прямом направлении, пройдем а раз цикл длины С2, затем
Рассмотрим произвольный замкнутый путь С в GF- Пусть v — некоторая вершина, входящая в путь С. Пойдем по ребрам С из указанной вершины. Если некоторая вершина w встретится второй раз (возможно w = v), то разрежем С на два замкнутых пути: ТЇ. — участок пути С между двумя вхождениями вершины w и замкнутый путь С\ = С\Т\. По построению каждая вершина входит в Ті один раз. Возможны варианты: либо ТЇ представляет собой замкнутый путь, состоящий из одного ребра, проходимого в прямом и обратном направлении, либо Ті — цикл графа Gp- Проделаем теперь аналогичную процедуру для замкнутого пути Сі и так далее. В итоге мы разобьем замкнутый путь С на множество циклов графа GF-, а также вырожденные замкнутые пути, состоящие из одного ребра, проходимого два раза. Длина последних путей равна 0, поэтому исключим их из рассмотрения. Поскольку каждое ребро С войдет в некоторый цикл или вырожденный замкнутый путь длины 0, то получаем, что длина пути С равна сумме длин некоторых циклов графа Gp, то есть длина С имеет вид ХХ=і агг (каждый цикл в С может проходится несколько раз).
Пусть теперь с = НОД(сі,..., cq). Согласно алгоритму Евклида ([1]), существуют целые числаbi,...,bq такие, что ХХ=1 Ьсг = НОД(сі,...,cq) = с. По доказанному выше в графе Gp существует замкнутый путь длины с.
Рассмотрим произвольную вершину vVi. Поскольку граф GF связный, то существует путь С от вершины vVi до некоторой вершины, входящей в замкнутый путь длины с. Составим новый замкнутый путь следующим образом: пройдем из вершины vVi путь С, потом пройдем а раз замкнутый путь длины с, где а — произвольное целое число, а направление обхода зависит от знака числа а, наконец пройдем в обратную сторону по пути G. При этом мы вернемся в вершину vy.. Поскольку путь С пройден два раза в противоположные стороны, то его длина уничтожится. Получаем, что мы построили замкнутый путь длины ас для любого целого числа а, проходящий через выбранную вершину vVi.
