АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ ТЕОРИИ ГРУПП И ПОЛУГРУПП 1991 г.

Черва обозначим предикат: , (lS,t)(&>te2&S*Q 8 t t *0& x. =-аЧ. у = я &s\t), где I обозначает, как обычно, отношение делимости. Нетрудно проверить, что имеет место следующая эквивалент- ность ^ ( x , y ) < t = > Р 1 х ) & Р ( у ) % (X, - 1 - > у = 1 ) % &( з . ф 1 -> {Зг\(г(ха 16) - lxa~'6)z$ \2\~ l y l ) . Используя последнюю эквивалентность, получим следующую важ­ ную для дальнейшего эквивалентность В дальнейшем нам будет полезна следующая эквивалентность j i | \ |^|с=> ( \ * \ - 0 * l # l > 0 ) V / { U I > l * O V v ( 3 г ) ( г е 2 & О с z < |асI & |х|||у| - х ) < — > ^ х > ( х - 1 Л | у | я а | ) v ( l a > l > l ^ l ) v W 3^t/>(lais iu|< Iл.I kua - au<xir6 -ovx ilj^l = |t*v| & i x l j m ) . Заметим, что каждая из указанных вш е формул легко преобра­ зу ется в прйдвареннуг формулу, не содержащую отрицания и кванто­ ра общности, . ' 0 \и \ г |х| + 1(У |<=>($&, г/)(т -аш »ьб : fiv-Jtlv/ i H x l * k\v\ е |у( \и \= \WV l}' В чао гное ти, M = i u l l u l £ it// г \ u /& i). Лорошо и звестна следующая эквивалентность : 1 * 1 0 * 1 * l)<K>iJt|jiyi # / i x iH ) ji y i4 I I v z i f l j t l h z i ^ ( l x | + rt|»2f • Заметим, что формула, стоящая в правой части последней экви­ валентности, равносильна предваренной позитивной формуле с прио- тавкой ч$ипа 1/3 a для некоторого небольшого /ь, ) Следующие эквивалентности очевидны: " | у | г | д | й < *> |у 1 + | j t l 1 ) ; 111 г |Л. /•ly |<=> (I X | f ljf.| )*r I X l * t £ IZ I + l y l * . Заметим, что имеют место оледующие эквивалентности: |z| = |xH#.l<~>0*M^I)/l*l * /# IМ ) = 1 Ы ( 1 * Н f)+lyl(l^Hl)^UI«=> < = L > n V f , u , t i / j , uj i w + jf ii'ti- U i + \ y i £ |ц,|=1«||(1К»|н)|- Ш