ВОПРОСЫ ТЕОРИИ ГРУПП И ПОЛУГРУПП 1972 г.

- 124- Г I, Нвйдутов такие o \ i l , U . f j . ) , wo * 3 U \ 0 . \ г. Ч-v. 3. v.--vi ou t7 / ( Сткуд» ораву ааюютаем, что формул» Р„( К, ^ ^ иотники 88 полугрупп» Л » . Теорема 2. Сущ»ствует алгоритм, который для любо! формулы фЫ . , t i ') уакого исчислокия предикатов о рем ш- ством оигнатуры (5^ строит позитивную формулу ( Г>> стами же оамымк свободными р»р»меинымм тс,, ■,У/> теку», что для любых слов V, , У р в алфавит» 2?„ формуле ф ( V., , Vf>) иотиии» на полугрупп» П „о' ». г* т I (V,, , У ) истинна на полугруппе Пя Доказательство. Известно ( См Ш ) * что сумествует алгоритм, который по произвольной формул» фГх., ,~tf ) узкого ясчиол»иия предикатов с равенством отроит ее предваренную 1 яа"юяктивиую норывльную формулу Ф ( * . , . , *г ) : Тогжв, очевидно,для всех слов V.. Уе » вяфошти Z r формула ф ( V., y f ) истинна на полугрупп» П„ „„«■rn.a формула р\\! , .V,.) истинве не полуг­ рупп» Пп пусть Ф' / х. , Y ' Vy f f Ai ’ t j j г гд» X — зн к графического равенств» , — кванторы, Ъ ; у , , |^ слов» ОТX,, ,Ttr<y (. < 0 . 3 J +