Пусть Q стандартная система уравнений с множеством неизвестных ДЕЛЬТА и с коэффицентами в алфавите Е.

Отображение f множества ДЕЛЬТА во множество языков алфавита Е называют решением системы Q,если после подстановки в каждое уравнение f(x) вместо х для каждого х принадлежащщего ДЕЛЬТА

Уравнение становится равенством множеств. Отображение f: Дельта -> g(Е*) называют наименьшей неподвижной точкой системы Q, если f решение и для любого другого решения g

f(x)<= g(x) Для любого х принадлежащего ДЕЛЬТА

ЛЕММА1) Каждая стандартная система уравнений Q с неизвестными ДЕЛЬТА обладает единственной наименьшей неподвижной точкой.

ДОК-ВО

Пусть f(x)={w|w принадлежит g(x) для всех решений g системы Q} для всех х принадлежит ДЕЛЬТА. Можно сказать, то f- решение и f(x) включается в g(x) для всех решений g

тоесть f единственная неподвижная точка системы Q

 

ЛЕММА2) Пусть Q-стандартная система уравнений с неизвестными ДЕЛЬТА={X1,X2,..Xn} и уравнение для Xi имеет вид Хi=АЛФАi0+АЛФАi1X1+АЛФАi2X2+....АЛФАinXn

тогда наименьшей неподвижной точкой системы Q будет точка отображения f, что f(xi)=f(w1,w2...wn) wm принадлежит АЛФАim0 и wk принадлежит АЛФАIkJk+1 для некоторой последовательности чисел

j1,j2,...jm, где m>=1, 1<=k<=m, uJ1=i}

 

ЛЕММА3) Пусть Q1 и Q2 системы уравнений до и после одного применения шага2 алгоритма решения стандартной системы уравнений с регулярными коэффицентами. Тогда Q1 и Q2 имеют одну и туже неподвижную точку.

ЛЕММА4) Пусть Q1 и Q2 системы уравнений до и после одного применения шага5 алгоритма решения стандартной системы уравнений с регулярными коэффицентами. Тогда Q1 и Q2 имеют одну и туже неподвижную точку.

ТЕОРЕМА) Алгоритм решения стандартной системы уравнений с регулярными коэффицентами находит наименьшую неподвижную точку стандартной системы уравнений.