Cтраница 4
В сигнатуре функции не используются все формальные параметры шаблона функции. [46]
При фиксированных сигнатурах Q и П и алфавите R проблема функциональной эквивалентности конечных X-Y - автоматов неразрешима тогда и только тогда, когда R содержит по крайней мере два символа переменных, Q - по крайней мере один функциональный символ арности больше нуля, П - по крайней мере один символ предиката арности больше нуля. [47]
X, сигнатура которой состоит из бинарного или / и-унарного отношения, будем называть графом. Носитель графа X обычно называют множеством вершин, а сигнатуру U - множеством дуг. [48]
Алгебра А сигнатуры Т называется относительно свободной, если она свободна в некотором предмного-образии Г - алгебр. Алгебра А относительно свободна в том и только том случае, если она порождается таким множеством X, что любое отображение из X в А продолжается до эндоморфизма алгебры А. Если А - относительно свободная алгебра, 6 - конгруэнция на А, то факторал-гебра Л / 0 является относительно свободной алгеброй в том и только том случае, если конгруэнция 0 вполне инвариантна. Для такой конгруэнции в справедливо равенство в - К ( А), где К - предмногообразие, порожденное А / в. Таким образом, в относительно свободных алгебрах вербальными являются вполне инвариантные конгруэнции, и только они. [49]
Интерпретация этой сигнатуры называется нормальной, если предикат равенства интерпретируется как тождественное совпадение элементов носителя. [50]